BT

Explaining .NET’s Barrier Class

by Jonathan Allen on Jun 15, 2011 |

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.

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread
Community comments

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Discuss

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT