Loop Parallelism, Task Queue, Graph Implementation Strategy and Pipeline, Geometric Decomposition and Data Parallelism

This is one of the most practical patterns I have read about parallelizing code. Its premise is so simple. It starts out by identifying key loops within a program. Then you analyze how that loop handles data and its dependencies. The next step is the heart of the pattern and the most work, in my opinion, to identify key loop transforms. The author provides a list of common transforms that can be used on most occasion. The programmer will then keep applying these transforms, ensuring that serial equivalence at each step.

The Task Queue pattern can be defined as a “mechanism to synchronously distribute a sequence of tasks among parallel threads of execution”. The idea is that problem is broken down into smaller “tasks” which are then placed in a queue. Parallel threads will then take tasks off the queue and perform computations on them.

The graph implementation strategy paper seemed to talk more about how to partition the graph than how to incorporate parallelism by exploiting the concurrency in those graphs.

Pipeline is a very simple pattern that achieves parallelism by dividing the operations or the data into stages that can be acted on in parallel. It seems very familiar to the pipes and filters pattern. I have not personally used this pattern, but I understand why this pattern is widely used.


I don't think there is much to say about the Data Parallelism pattern. I just thought it was weird that it was only 3 sentences long.