Randomized, oblivious, minimal routing algorithms for multicomputers

Abstract

Efficient data motion has been critical in high performance computing for as long as computers have been in existence. Massively parallel computers use a sparse interconnection network between processing nodes with local memories. Minimizing the potential for high congestion of communication links is an important goal in the design of routing algorithms and interconnection networks in these systems. In these distributed{memory architectures, the communication system represents a significant portion of the total system cost, but is nevertheless often a weak link in the system with respect to performance. Efficient interprocessor communication is one of the most important and most challenging problems associated with massively parallel computing. Communication delays can easily represent a large fraction of the total running time, inhibiting high performance computing for a wide range of problems. Efficient use of the communication system is the focus of this thesis. The design of the interconnection network and the routing algorithms used to transport data between nodes are critical to overall system performance. The constraints imposed by a sparse interconnection network suggest that preserving locality of reference through careful data allocation and minimizing network load by using minimal algorithms are desirable objectives. In this thesis, we present ROMM, a new class of general-purpose message routing algorithms for large-scale, distributed-memory multicomputers. ROMM is a class of Randomized, Oblivious, Multi-phase, Minimal routing algorithms. We will show that ROMM routing offers the potential for improved performance compared to both fully randomized algorithms and deterministic oblivious algorithms, under both light and heavy loads. ROMM routing also offers close to best-case performance for many common routing tasks. These claims are supported by extensive analysis and simulation of ROMM routing on several different interconnection network architectures, for a set of representative routing tasks. Furthermore, our results show that non-minimality and adaptivity, two common techniques for reducing congestion, are not always required for good routing performance.