Pipeline, Geometric Decomposition, Data Parallelism

The three patterns describe how to achieve parallelism by dividing the data or dividing the operations that are performed on the data. I think all parallel patterns can be classified into the two categories: data parallel patterns and task parallel patterns.

The pipeline pattern is probably one of the most used patterns. Pipeline can be used in any system where a sequence of identical operations is processed in stages. I have used this pattern in a network adapter’s code to significantly reduce latency and increase throughput of sending and receiving packet over a fiber channel network.

The geometric decomposition pattern involves decomposing the data structure into chunks and decomposing the update operations on the data into tasks with each task managing a set of chunks. The biggest challenge in this pattern is to ensure that non local data required to perform an update operation is available before the update operation. So data exchange mechanism is critical for this pattern as it affects the potential parallelism.

The Data parallelism pattern advocates treating the problem as a single stream of operations applied to each element of a data structure. This is a similar idea as in the geometric decomposition, but here there are no details about the implementation of the pattern. I am not sure if the solution can be useful without a combine stage. The idea of applying instructions to each element of the data structure is good, but the results need to be combined to produce the final result.