With the increased emphasis on multi-core systems an understanding of parallel and concurrent programming is more important than ever. Fortunately .NET 4 has made a lot of advances in the types of synchronization primitives available to developers. One such primitive is the Barrier, which Emad Omara uses to implement a parallel merge sort.
Emad Omara’s parallel merge sort algorithm assumes that you will have full access to the machine’s CPUs for the duration of the sorting operation. While this isn’t necessarily true, it serves the purpose of the demonstration. The input array is first divided into N partitions of roughly equal size, where N is the number of logical CPUs. One thread is started for each CPU to perform a singled-threaded sort within its own partition.
At this point the threads must be synchronized before continuing with the next phase. Half the threads will exist while the other half will perform merge sorts across adjacent partitions. In previous versions of .NET this would be done with low-level primitives or the careful use of Thread.Join. The Barrier class provides another option.
The Barrier class is somewhat like Thread.Join in that it waits for all the threads to complete. But unlike it the threads being waited for don’t need to exit. Instead they merely need to signal that they have completed the current phase and are ready to start the next one. This eliminates the need to break-down and recreate threads, which is especially important when working with thread pools.
By default the Barrier class assumes that every thread needs to signal that it is complete before any of the threads proceed to the next phase. Clearly this won’t work here because each pass in the merge sort needs half as many threads. So instead Emad calls the Barrier.RemoveParticipant method, which reduces the expected number of signaling threads by one.
Again it should be noted that this algorithm was designed as a teaching aid and further refinement is needed it can be used in a production setting.