Modeling Performance
Execution time (sums are over P nodes) is
T = (sum[Tcomp]+ sum[Tcomm] + sum[Tidle])/P
Computation time comprises both
- Operations required by sequential algorithm
- Additional work, replicated work
Idle time due to
- Load imbalance, and/or
- Latency (waiting for remote data)