Methods for Message Routing in Parallel Machines

The problem of getting the right data to the right place within a reasonable amount of time is one of the most challenging and important tasks facing the designer (and, in some cases, the user) of a large-scale general-purpose parallel machine. This is because the processors comprising a parallel machine need to communicate with each other (or with a common shared memory) in a tightly constrained fashion in order to solve most problems of interest in a timely fashion. Supporting this communication is often an expensive task, in terms of both hardware and time. In fact, most parallel machines devote a significant portion of their resources to handling communication between the processors and the memory. In the talk, we surveyed several of the ideas and approaches that have been proposed for solving communication problems in parallel machines. Particular emphasis was placed on recent work involving randomly wired networks (known as multibutterflies). Results were presented that indicate that randomly wired networks significantly outperform traditional networks such as the butterfly in terms of both speed and fault tolerance.