Issues in Changing the Algorithm
Issues in Changing the Algorithm
- Trading communication (slow) for computation (fast)
- Example: Solving a small linear system whose results are needed by all processes
- Parallel solution latency dominated (ps + …)
- Single solution uses gather/bcast, leaves processes idle
- All solve uses single gather (but has duplicate work)
- Multicoloring
- Divide computation into different “colors”, each of which is independent of the others
- Loop unrolling