1987 · 20 citations · 18 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureMessage PassingParallel ComputingCommunication NetworksMesh NetworksNetwork ArchitectureNetwork DiameterNetwork OptimizationNetwork TopologyCommunication DelaysGraph IsomorphismInterconnect TopologiesInterconnection GraphsInterconnection Network Topology DesignSimd ArchitecturesSimd ParallelismWraparound Mesh Networks
A class of mesh networks with wrap-around links is obtained from a class of circulant graphs by means of a graph isomorphism. We demonstrate how to obtain, from the adjacency pattern of the graph, simple parameters that serve to construct a planar design of the network. Several performance parameters are evaluated: in particular, we show that diameter and average distance are simultaneously minimized. This implies a minimization of the network communication delays. Due to its easy implementation and good behavior characteristics, the proposed interconnection scheme is appropriate in several architectural environments. Specifically, this topology is suitable as an interconnection subsystem for message passing MIMD architectures, as well as for SIMD machines with a static interconnection scheme. In the particular case of SIMD machines, a comparison is made with the ILLIAC IV-type networks. As a consequence, we propose still another topology, when the number of processing elements is an even power of 2; for this solution, we show that a reduction in the network distances is achieved, without losing speed in performing arbitrary permutations.
18
Charles L. Seitz · Communications of the ACM · 1985 · 1.2K citations · Full text
Very high-speed computing systems
Michael Flynn · Proceedings of the IEEE · 1966 · 951 citations
Greg Barnes, Rebecca M. Brown, M. Kato et al. · IEEE Transactions on Computers · 1968 · 526 citations
THE MAXIMUM CONNECTIVITY OF A GRAPH
Frank Harary · Proceedings of the National Academy of Sciences · 1962 · 331 citations
Analysis of Chordal Ring Network
Hikyu Lee · IEEE Transactions on Computers · 1981 · 276 citations