In this section we present an example of how waiting time analysis can help a programmer understand the influence of multiprogramming on parallel program performance. We will examine the effects of multiprogramming via time-sharing on the triangular solver and Cholesky factorization applications described earlier.
These programs were initially developed on the SGI Challenge under multiprogramming. We observed that the running time of the implementations that use a cyclic distribution were very sensitive to the effects of multiprogramming, and varied significantly across multiple runs. The implementations that use a blocked distribution were not as sensitive to the effects of multiprogramming. For Cholesky, we observed that the implementation using a blocked distribution sometimes performed better and sometimes performed worse than the implementation using a cyclic distribution, depending on the load on the machine. For the triangular solver, the blocked distribution always performed better. The question we want to answer is: why is a cyclic distribution more sensitive to multiprogramming effects than a blocked distribution?
To investigate this issue we generated an artificial multiprogramming load and varied the multiprogramming level (i.e., the number of processes that compete for a single processor) between one and four. We executed both of the implementations of triangular solver and Cholesky factorization on four processors, while varying the multiprogramming load. We then performed waiting time analysis on the resulting traces.
As seen in the previous sections, the primary sources of waiting time in the cyclic implementations occur during the receive operations, and the overall amount of waiting time is small. In the blocked implementations, most of the waiting time occurs at the final barrier, and the total waiting time (across all processors) is significant.
The profiles from our experiments with multiprogramming on triangular solver and Cholesky factorization show that both the waiting time and the overhead directly due to multiprogramming (i.e., time spent by the processor on another job) increase with the multiprogramming level. (Waiting time may increase whenever two processes synchronize and one of them is not running due to multiprogramming.) However, the waiting time differs dramatically for the blocked and cyclic implementations. For example, under light load (a multiprogramming level of 2), the blocked implementation of Cholesky takes 80.3 seconds, and has 45.1 seconds of waiting time; the cyclic implementation takes 73.5 seconds, and has 14.8 seconds of waiting time. When we increase the multiprogramming level to 3, the blocked implementation takes 140 seconds, with 52 seconds of waiting time; the cyclic implementation takes 211 seconds, and has 93 seconds of waiting time. Thus, the cyclic implementation is better under light load, while the blocked implementation is better under heavier load, and the difference between these implementations is almost entirely attributed to the increase in waiting time caused by multiprogramming.
Using waiting time analysis, we see that the characterizations for waiting time in the blocked implementation of Cholesky don't change much despite an increase in multiprogramming level; most of the waiting time is still at the final barrier, and the characterizations still identify load imbalance and communication overhead as the cause of waiting time. In the cyclic implementation however, the characterizations change significantly with an increase in multiprogramming level, attributing nearly all of the increase in waiting time to the effects of multiprogramming. Since the cyclic distribution involves twice as many synchronization operations as the blocked distribution, and its processes are more tightly synchronized, there is a greater opportunity for multiprogramming to introduce waiting time in the cyclic implementation, as shown by the characterizations.