next up previous contents
Next: Processor Allocation in Radar Up: Applications of WT Analysis Previous: Applications of WT Analysis

Load Imbalance vs. Communication in Triangular Solver

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 tex2html_wrap_inline1825 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 tex2html_wrap_inline1851 . We executed this program on a tex2html_wrap_inline1853 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 tex2html_wrap_inline1867 , 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 tex2html_wrap_inline1813 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.


next up previous contents
Next: Processor Allocation in Radar Up: Applications of WT Analysis Previous: Applications of WT Analysis

Wagner Meira
Wed Feb 28 15:37:47 EST 1996