Communication and matrix computations on large message passing systems (Q750124)

This paper studies the consequences for matrix computations of working with a large number of general purpose processors, say from 10000 to 20000, connected through a topology that allows any processor to communicate directly only to its immediate neighbors, and assuming a rate of a million arithmetic operations per second for each processor. (No such a system has been built so far.) One consequence of these hypotheses is that problems can be posed that are too large to be solved in a reasonable amount of time. This suggests that the next generation of parallel computers must be designed to solve smaller matrix problems faster, rather than to solve the largest problems they could handle. To be computationally intensive, parallel algorithms must communicate a lot. However, it is known that the rate of computation to communication decreases with problem size. But if a problem is large enough to be efficiently solved, is it also so large that its solving can only be reached in an unreasonable time span? The author partitions an arbitrary matrix into square submatrices and assigns these to individual processors. Some typical communication tasks are then considered and their implementation done in two types of networks: a grid and a hypercube. The communication times for problems of different sizes are then computed and compared with the computation costs, so as to determine break-even points. The main result assures that the efficiency of certain important matrix algorithms at fine granularity is restricted by the granularity of the communication. A remedy, called simple streaming, is then proposed.