Network structures and algorithms for large multiprocessors
Peter F. Corbett · 1990
Many existing and proposed multiprocessors are interconnected using network topologies describable by simple mathematical relationships. This thesis deals with several aspects of interconnection networks for highly parallel computers. Point-to-point and multistage interconnection schemes are discussed, with application made to multiprocessors with both highly synchronized and highly autonomous processors. Algorithmic aspects of multiprocessors are as important as the structure of their interconnection networks. These two factors are highly interdependent, and it is essential that they be studied together to achieve the greatest possible improvements in computer performance. Current trends are for the highest performance computers to be used for symbolic as well as numerical computations. This will require increasingly more flexible computer architectures, and, in particular, will demand that many powerful, highly autonomous processors be connected efficiently. Two new network structures are proposed: the Generalized Shuffle-Exchange network, primarily for use in shared memory multiprocessors, and the Rotator graph for use in point-to-point connected networks. In each case, the networks are characterized analytically. Routing algorithms are given that exploit the structure of the networks to give better performance than existing networks. Communication overhead is a limiting factor in the speedup achievable in multiprocessors. The overhead is highly dependent on the network structure of the multiprocessor, as well as on the algorithms implemented in the multiprocessor. Sorting on multiprocessors is examined, and a new sorting algorithm is presented that generalizes two known algorithms. The generalized algorithm can be extended to several other classes of multiprocessors. All of these different aspects of multiprocessor network architectures are related by a common theme: increasing multiprocessor performance through the synergistic interaction of algorithm and network structure. In each case, the algorithms developed are shown to be applicable to other structures, and the structures proposed are shown to address the problems encountered by the algorithms when executed on current network structures.