Using a Block-Distributed Matrix

Let us try to modify the matrix-vector multiplication algorithm from section 6.4.1 to improve the scalability. The poor scalability was a result of the relatively large communication overhead incurred by using a row distribution for the matrix A. When A is distributed by rows, all elements of the b or c vector must visit (or be stored by) each process during the computation if b and c are replicated, no data exchange is required for b, but an all-to-all broadcast is required to replicate c at the end of the computation if both vectors are distributed, no communication is required for c but all elements of b must visit all processes during the execution. 

The first requirement for the new algorithm therefore is to distribute A differently. A column distribution will not reduce the communication requirement, so we need to distribute A by blocks. We will employ the data 

The communication overhead for this algorithm is the cost of performing a broadcast and a reduce operation that both involve nj fp elements and 

Parallel matrix-vector multiplication Ab = c on p processes using fuUy distributed data. The processes are shown on a grid with process Pj, j in row i and column j (0 i 0 j , /p). 

The steps indicated with arrows are (1) an initial broadcast within each column putting a copy of hi on every process in column j (2) computation of the contribution = A dbi to the block d on P (3) summation of across each row, putting the complete block c on Pi,o and (4)redistributionofc (Pi,0 sends c to Po, ) to match the initial distribution of b. The index m represents the value yp — 1. A is distributed by square blocks, and Pj, j holds the block A i. The vectors b and c are divided into uniform blocks, and Po, j holds the block bi and (at the end) ch 

---