In our first example we study the sources of waiting time
in several implementations of a triangular solver for
a system of linear equations AX = B,
where A is an
lower triangular matrix,
and X and B are n-element vectors.
During iteration k the owner of row k computes X[k] and sends it
to all other processors.
Every processor then updates entries in B using the value of X[k].
There are two synchronization points in the program:
(1) at the beginning of each iteration k of the outermost loop,
each processor waits to receive X[k] from its owner and
(2) after termination of the outermost loop,
all processors wait at a barrier.
In our first implementation,
we distribute the matrix A among P processors in a row-cyclic fashion,
where row i is assigned to processor
.
We executed this program on a
matrix
using 4 processors under PVM on the SGI Challenge.
Execution profiles show that over 14% of the 10 seconds
of cumulative execution time is waiting time.
According to WT analysis only 1% of this waiting time is attributed
to the final barrier; the rest is attributed to the receive operations.
Each receive operation is responsible for only a small
amount of waiting time, but there are so many receive operations
that the overall accumulation of waiting time is significant.
This observation indicates a need to reduce
the amount of communication in the program.
Our second implementation reduces communication by using a blocked distribution of data, wherein processor 0 owns the first 1/P rows, processor 1 owns the next 1/P rows, and so on. Cumulative execution time using this data distribution is 5 seconds, or half the time of the cyclic distribution, although waiting time is now 26% of the cumulative time. WT analysis shows that 90% of this waiting time arises at the final barrier, since all processors must wait for the owner of the last block to finish. However, WT analysis attributes only 20% of the barrier waiting time to computational load imbalance in the outmost loop and 80% to communication imbalance within the loop. This somewhat surprising result is due to the fact that the last processor not only performs more work, but must also receive more data. Since PVM receive is relatively expensive on the SGI, it dominates the load imbalance in the loop, and is the main cause of waiting time at the barrier.
Our third implementation uses a blocked-cyclic data distribution with 32-row blocks, both to reduce communication and to minimize load imbalance in the outermost loop. Each processor executes a send operation after having computed a block of 32 elements in the X vector. This implementation requires 1.14 seconds of cumulative time, with 17.5% of that time devoted to waiting. WT analysis shows that 7% of this waiting time arises at the last barrier and 93% at the receive operations. Of the waiting time at the receive operations, 35% is caused by communication and 65% by computational imbalance.
To reduce waiting time further, we might consider using a smaller block size, thereby reducing the waiting time due to computational imbalance. However, a smaller block size increases communication, and there is no reason to equalize the relative contributions of communication and computation imbalance, if doing so increases communication. We confirmed this observation by executing the program with 16-row blocks. For this implementation, waiting time is still 17.5% of the cumulative execution time, again mostly due to receive operations. As expected, the waiting time at receive operations is now distributed more evenly, with 45% due to communication and 55% due to imbalance. However, the execution time (1.41 seconds) did not improve, because the time devoted to communication (send and receive) increased.
We note that the relative contributions of load imbalance and communication to waiting time (which dictate the relative efficiency of blocked and cyclic data distributions) cannot be readily determined from profiles alone. The insights into waiting time provided by WT analysis help us to understand the tradeoffs between communication and imbalance, which dictate the choice of block size.
To further examine this tradeoff, we performed a comparable analysis for Cholesky factorization. As with triangular solver, there is a tradeoff between load imbalance and communication in the blocked and cyclic implementations of Cholesky. The results are different however due to differences in the algorithms.
In dense Cholesky factorization,
we compute a lower triangular matrix B with positive diagonal elements
such that
,
where A is a dense symmetric positive definite matrix.
We distribute matrix A among the processors
in either row-wise blocked or cyclic fashion,
and then during iteration k each processor does the following:
We executed the blocked implementation on a
matrix
using 4 processors under PVM on the SGI Challenge.
The cumulative execution time was 24.5 seconds, with 40% due to waiting time.
As with the blocked implementation of triangular solver,
the bulk of the waiting time arises at the final barrier.
WT analysis identifies the loop that updates columns k+2 to n
as the source of 78% of the waiting time.
The remaining waiting time in the program cannot
be characterized compactly by WT analysis.
As explained earlier, each successive iteration of the loop
is slightly different than the previous iteration,
and therefore cannot be merged into a single characterization.
Based on the results from the triangular solver we might expect the cyclic distribution of Cholesky to perform worse than the blocked distribution. In fact, cyclic Cholesky performs better than blocked Cholesky, reducing cumulative execution time from 24 seconds to 14 seconds, while essentially eliminating waiting time. There are two reasons for this: (a) unlike triangular solver, there is the same amount of communication in our blocked and cyclic distributions of Cholesky factorization, and (b) the algorithm allows us to overlap communication and computation, eliminating any accumulation of small amounts of waiting time for each communication operation.