next up previous

4.2 Matrix Multiplication on a Distributed Memory Machine

In this section it will be convenient to number matrix entries (or subblocks) and processors from 0 to n-1 instead of 1 to n.

On distributed memory machines the cost model is more complicated than on shared memory machines, because we will need to worry about the data layout, or how the matrices are partitioned across the machine. This will determine both the amount of parallelism and the cost of communication. Recall from the chapter on Computer Architecture gif that the cost of sending a message of k words from one processor to another is , where is the start-up cost or latency, and is the per-word cost, or reciprocal of bandwidth. Therefore to assess the cost of an algorithm we need to count the number of floating point operations, the number of messages sent (at a cost of per message), and the total length of messages sent (at a cost of per word). We begin by showing how best to implement matrix multiplication without regard to the layout's suitability for other matrix operations, and return to the question of layouts in the next section.