9 Reusable Parallel Data Structures and Algorithms

As I mentioned before, cpu development has moved into a multi-core stage. To fully utilize the computing power in the chip, concurrency programming is the key. This MSDN article introduced 9 parallel data structures and algorithms which allow one to design a multi-threaded program in a very intuitive way. The best part of this article I found is the author explained why the source code executes correctly and which parts of the code, if changed, could result into a deadlock.

1. Countdown Latch - This class allows a program to wait for a counter to reach zero. It uses Interlocked.Decrement to substract the counter and EventWaitHandle to coordinate to wait and signal events.
   
2. Reusable Spin Wait - Sometimes putting a program to sleep can be expensive due to the cost, i.e., context switch, involved. For a short period of time, i.e., cycles, spin wait is a good choice. This structure instructs a cpu to wait based on the number of processors in a computer. If there is only one cpu, the structure puts the program to sleep. If there is more than one cpu, the structure instructs the cpu to spin.
   
3. Barriers - Say, task1 and task2 can be executed in parallel, but task3 can not proceed until both task1 and task2 are completed. One way to code this is to run task2 in thread2 and execute task1 in thread1. After task1 complete, call Join in thread2 to wait for the completion of task2. Or we can use Barriers to wait for something to complete before proceed to the next step.
   
4. Blocking Queue - Very straightforward and easy to understand. It's also a good example of how to use Monitor.Pulse / Monitor.Wait in a correct way.
   
5. Bounded Buffer - This is a data structure to solve consumer/ producer problem. The class is implemented similar to Block Queue.
   
6. Thin Event - Win32 events can be expensive to allocate. This class uses the SpinWait structure to wait first and, if an event is still not signaled, it allocates a Win32 Event to wait on. Lazy evalation is the design philosophy behind this class.
   
7. Lock-Free LIFO Stack - You don't have to lock an entire stack to push or pop an item. The author showed that an Interlocked.CompareExchange operation is enough to ensure push or pop operations thread-safe in a stack.
   
8. Loop Tiling - If you know what parallel query is, you know what loop tiling is doing. It's easier to show you the codes than describe them in words.
   
   List<T> list = ...;
   foreach(T e in list) { S; }
   
   A C# for loop above can be run in parallel using the function below.
   
   Parallel.ForAll(list, delegate(T e) { S; }, Environment.ProcessorCount);
   
9. Parallel Reductions - Some operations, such as, max, min, count, sum, can be performed in parallel. The author provided a Reduce function to simplify the task. The function reminded me of the MapReduce method.