Single Program, Multiple Data (SPMD)
Decomposition
- We want to decompose a problem into multiple smaller tasks that can be carried out in parallel
- Our goal is to create enough tasks to keep every execution unit busy
- Dependency is a hard problem to deal with when doing decomposition
Task Scheduling
Balancing Workload
Ideal Situation
所有的 processor 都會在相同的時間開始，相同的時間結束
Reality
因為我們工作分配的 imbalance，有些 processor 會提早結束工作，有些則會跑得比其他更久