The best view for multi-threaded applications

Question

Today in an interview I had a question about what kind you use for a multi-threaded application. It seems like a merge sort or a quick sort.

Answer 1

You are using merge sort for multi-threaded applications.

Cause:

Combine sorting divides the problem into separate smaller tasks (smaller arrays), and then combines them. This can be done in separate threads.

Quick sorting makes summary sorting in a single array, so it’s more difficult to efficiently split the problem between threads.

Answer 2

Each separation and rest algorithm can be easily parallelized. Merging sorting and quick sorting are performed according to the same basic scheme, which can be performed in parallel:

procedure DivideAndConquer(X) if X is a base case then Process base case X return Divide X into [Y0 … Yn[ for Y ∈ [Y0 … Yn[ in parallel do DivideAndConquer(Y) Merge [Y0 … Yn[ back into X 

Where they differ, it is that in quick sorting separation is difficult, and merging is trivial (without operation). In merging, sorting is the other way around: division is trivial and merging is difficult.

If you implement the above scheme, quicksort is actually easier to parallelize because you can just forget about the merge step. To sort a merge, you need to track completed parallel tasks. This delays load balancing.

On the other hand, if you follow the above diagram, you will have a problem: the very first section and the most recent merge will use only one processor, and all other processors will be idle. Thus, it makes sense to parallelize these operations as well. And here we see that the parallelization of the split step into quicksort is much more complicated than the parallelization of the merge step in the merge sort.

Answer 3

The merge sort seems to be easier to parallelize and distribute ... think about it, you decompose it into pure subprocesses that can be easily split and distributed. But then again, the same goes for quicksort. However, I would prefer to do this with a merge sort, as this will probably be easier.

Answer 4

Assuming a decent choice, this is not all.

Subroutines are trivial for parallelization; they use (mostly) disjoint memory and do not need synchronization, so the actual difference lies in bottlenecks: the initial section of quick sort and the final merge in sorting merge. Neglecting parallelization will lead to poor accelerations for many cores or several elements (this becomes noticeably much faster than you think!).

Both algorithms can be parallelized efficiently. See this MCSTL article for some experimental results and implementation details. MCSTL was the basis for what is now GNU C ++ parallel mode std-lib.

Not everything is clear which algorithm will work better under any circumstances, since it depends on the distribution of data and whether swaps or comparisons are slower.

Answer 5

I think they are looking for merge-sort as an answer, as it is easy to figure out how to split this between threads. Although another comment indicates that qsort can also be split into smaller issues. Probably many can be divided into smaller problems.

There is one critical aspect that cannot be ignored. Communication with other threads takes a lot of time. The dataset you are sorting must be huge or very expensive to compare before you create threads, and communication between them will be better than just using a single thread.

In addition to this, in any case, you have a serious problem of false exchange. Using multiple threads with the same data can (despite the communication time) be slower because the CPU is forced to share and update data between multiple cores. If your algorithm cannot correctly align the data, passing it to different threads will slow it down.