Thoughts on OPL patterns: Task Parallelism, Recursive Splitting, and Discrete Event

This blog is about the three parallel algorithm strategy patterns I read in OPL: Task Parallelism, Recursive Splitting, and Discrete Event. All three patterns are written from the point of view of providing a strategy on the parallel implementation of a problem. Thus, one may already choose a structural or a computational pattern to solve the problem conceptually, here we focus on the actual implementation, mapping the conceptual solution to a parallel implementation.

It is a good thing that the Task Parallelism pattern brings up the two prerequisites to make the pattern work: understanding the application concurrency characteristics and understanding the platform characteristics. Typically, many people only master one or the other. This is typical since we are so used to concentrating our mastery effort in one particular layer of abstraction. Here it shows in order to truly take advantage of parallelism, one needs to have thorough knowledge of both the algorithm and the hardware. On the flip side, this also shows the difficulty of having one universal efficient parallel algorithm implementation across platforms.

The Recursive Splitting pattern focus on problems solved by recursion. Conceptually, we have been taught that recursion as continuously splitting problems into smaller chunks. I believe most of us also conceptually think those small chunks are done in parallel as we often draw the tasks in the same level as one horizontal row of a recursion tree. Thus, this pattern should not be too far fetched for us. One good point this pattern and the previous pattern both mention is the trade-off between the costly overhead due to fine task division vs. less chance of concurrency due to course-grain tasks. This seems to be a common design decision one needs to make when making the solution of a problem concurrent.

The last pattern is Discrete Event which conceptually seems similar to the Event-Based Implicit Invocation pattern. The author raises a good point that the pattern can be used in the case when control flow of the data is not as clean-cut as in the case of Pipes and Filters. After reading it, I am still unsure the significance of the term "Discrete" in the context of this pattern, perhaps it is because I always picture the events as discrete from a source to a sink.