
212 CHAPTER 4 Workload-Driven Evaluation
times the number of iterations to convergence, which we can conservatively assume
to be 0(n) (the number of iterations taken for values to flow from one boundary of
the grid to the other). This leads to a sequential computational complexity of
0(n
3
).
Consider the execution time and memory requirements under the three scaling
models, assuming speedups due to parallelism equal to the number of processors p
in all cases. With PC scaling, as the same n-by-n grid is divided among more proces-
sors p, the memory requirements per processor decrease linearly with p, as does the
execution time. In TC scaling,