We do not mean to denigrate the efforts to produce a general-purpose parallel machine. Machines that can realize any communication pattern are of course desirable, and necessary for those cases when the communication needs of a program cannot be predicted in advance. A wide variety of such general-purpose networks have been designed and built. The choice of network topology has varied with builder and over time:
โข KSR has chosen a high speed ring with directory caches [3];
โข Thinking Machines chose first a hypercube network [14], and then a fat-tree [15];
Other researchers have suggested active messages, multithreading, pre-fetching, and novel cache schemes to reduce overhead and make general-purpose communication more practical. Each method has its expenses and drawbacks. We only argue that, since flexibility comes at a cost, one might want to consider trading reduced generality for reduced cost.
In some sense, any machine topology that forms a single connected component is general-purpose-that is, it is possible to send a message from any processor to any other processor. It may, however, be quite difficult (i.e., expensive in terms of time or resources) to send messages between particular pairs of processors or to send several messages at the same time. The question of how to efficiently route the messages arising from common algorithms on particular networks has been extensively studied. For example, Bajwa [1] discusses routing on tori and grids, and Sibeyn [13] gives an extensive survey of routing on a mesh. The field of graph embedding (e.g., [6]) can be interpreted as providing mappings of algorithms' communication patterns onto various network topologies, or showing that they do not exist. Some of the limitations of graph embeddings for this purpose have been removed by looking at work-preserving emulations [9,16].
Many researchers have attempted to classify those sets of communication patterns that can be implemented efficiently on particular architectures. Nassimi and Sahni [11] consider the class of BPC permutations, which includes many common communication patterns such as matrix re-