Task Parallelism, Recursive Splitting, Discrete Event

Task Parallelism

As name suggested task parallelism is nothing but task level parallelism, breaking a large task into many smaller ones, and then proceeding to find which ones can operate in parallel. This pattern has lot of details in it along with some hardware details that are relevant for the parallelism (needed 2 passes to grasp what author is saying about). I like the context and Forces section but thought solution section may need some more improvement with more clear information on how to approach the solution.

Recursive Splitting

This pattern describes how one can effectively implement parallel execution for the recursive algorithm that splits the data and each part of the recursion will execute as a separate task. This paper talked about following as solution steps for algorithmic strategy involving recursive splitting:

1. Express problem recursively with more than one task generated per call
2. Use a balanced data structure, if possible
3. Use a fork-join or task-queue implementation
4. Use optimizations to improve locality
I like the clarity and simplicity of the paper.

Discrete Event

This pattern is interesting one. Here the problem described for this pattern(from paper) :

Suppose a computational pattern can be decomposed into groups of semi-independent tasks interacting in an irregular fashion. The interaction is determined by the flow of data between them which implies ordering constraints between the tasks. How can these tasks and their interaction be implemented so they can execute concurrently?

And solution (from paper):

A good solution is based on expressing the data flow using abstractions called events, with each event having a task that generates it and a task that processes it. Because an event must be generated before it can be processed, events also define ordering constraints between the tasks. Computation within each task consists of processing events.

I like the approach of how it makes easier to detect deadlocks, but like see more examples in implementation point of view.