Imagine sorting a large pile of sand instead of moving a few bricks: fine-grained decomposition breaks a computation into many small tasks. Those tasks give a concurrent system more choices for distributing work across processors, helping keep them busy and reducing load imbalance. section 7.9 section 13.4
Use fine-grained decomposition as a starting point, then account for its costs:
- During partitioning, identify as many independently executable tasks as possible before worrying about processor count or the target machine. section 13.4
- Aim for at least an order of magnitude more tasks than target processors, preserving choices for later design stages. section 13.4
- Expect more communication and task-creation overhead as tasks become smaller; too many tasks can overload the operating-system scheduler. section 7.9
- Seek a middle ground between fine and coarse granularity, sometimes grouping tasks assigned to one processor. section 7.9
Two ways to split a concurrent computation
For a large data-processing algorithm, divide the data into independently processed parts. Alternatively, divide the calculations by functionality. The first is data decomposition; the second is task decomposition, and both can be combined. section 13.4
