next up previous

Exercise 7: Illustrate the block scattered layout of a matrix on a processor grid with blocks.

By being a little more flexible about the algorithms we implement, we can mitigate the apparent tradeoff between load balance and applicability of BLAS. For example, the layout of A in Figure 3 is identical to the layout in Figure 2 of , where P is a permutation matrix.

This shows that running Cannon's algorithm from the last section to multiply A times B in scatter layout is the same as multiplying and to get , which is the desired product. Indeed, as long as (1) A and B are both distributed over a square array of processors; (2) the permutations of the columns of A and rows of B are identical; and (3) for all i the number of columns of A stored by processor column i is the same as the number of rows of B stored by processor row i, the algorithms of the previous section will correctly multiply A and B. The distribution of the product will be determined by the distribution of the rows of A and columns of B. We will see a similar phenomenon for other distributed memory algorithms later.