- A master process/thread sets up a pool of workers (processes/threads) and a bag of tasks.
- Workers take tasks from the bag, and process them in a concurrent fashion.
Each worker continues processing, until all tasks have been processed or some other condition has been reached. In some implementations no explicit master is present.
– It is suitable for non-deterministic execution time of tasks.
– It is used when tasks should be distributed among workers.
– Since creating and terminating processes/threads is expensive workers should be reused.
– Not applicable when tasks are interdependent.
– Usually the number of tasks exceeds the number of UEs.
– Usually number of workers <= PE.
How tasks are assigned to workers?
Using a single shared queue as bag of tasks, tuple space, monotonic counter.
Each worker enters a loop, at the top of the loop in a synchronized way the worker takes a task from the bag.
UE: Unit of execution (process/thread)
PE: Processing element (core/processor)
A note from Patterns for Parallel Programming by Mattson, Sanders ,Massingill
See also: fork/join and loop parallelism patterns.