COLLECTIVE COMMUNICATION IN WORMHOLE-ROUTED MASSIVELY-PARALLEL COMPUTERS

The supercomputer market is now dominated by parallel architectures, among which massively parallel computers (MPCs) are an important class of systems. The memory of an MPC is physically distributed among an ensemble of computing nodes that communicate by sending data through a network. Communication operations can be either point-to-point, with one source and one destination, or collective, with more than two participating processes. The design of collective communication operations depends on the MPC's underlying network architecture. While there has been little consensus on some aspects of communication architectures, such as network topology, a good deal of agreement exists regarding the most efficient way to switch messages through the network. Most MPCs use wormhole routing, in which each message is divided into small pieces that are pipelined through the network. Compared with the store-and-forward switching method used in early multicomputers, wormhole routing reduces the effect of path length on communication time. However, in situations where multiple messages exist in the network concurrently, wormhole routing can exacerbate channel contention, which occurs when blocked messages hold some communication channels while waiting for others. Invoking a collective operation, which can involve many messages, poses this situation. In recent years, many projects have addressed the design of efficient collective communication algorithms for wormhole-routed systems. By exploiting the relative distance-insensitivity of wormhole routing, these new algorithms often differ fundamentally from their store-and-forward counterparts. This article examines software and hardware approaches to implementing collective communication operations, illustrating several issues arising in this research area and describing the major classes of algorithms proposed to solve these problems.