A system for routing arbitrary communication graphs on simd architectures
S. Tomboulian · 1986
There is a class of problems that can be loosely called connected information problems. This class includes areas such as semantic networks, data base processing, VLSI circuit simulation, topological processing, and many general graph theoretic problems. These problems are characterized by points of information connected to other points (or nodes in a graph connected by arcs), and it is desirable to traverse many paths in the graph simultaneously. Typically, the real-world version of these problems are very large, containing thousands or hundreds of thousands of nodes. These problems are not well suited to current methods of serial computation. As the possibility of having massive parallelism is quickly approaching reality, it is necessary to ask what kind of machine would best solve these problems. A natural way to attack these problems on a parallel system would be to assign each information point to a processor. This solution has a great deal of appeal but has several architectural requirements. The first one is that many processors are needed--on the order of hundreds of thousands. It is also necessary to have a way to realize the edges. These two requirements conflict. Currently, MIMD computers being developed have a few dozen to a few hundred processors that generally have robust communication links, but they do not lend themselves to the concept of having one processor per vertex. SIMD machines can and have been built with large numbers of processors. However, the communication problem is much more difficult, and for this reason they have been essentially ignored as a reasonable means for handling general graph problems. The paper will present a simple SIMD architecture model that is bit-serial and uses only nearest neighbor connections for communication. Several algorithms are given that will be used to implement communication between arbitrary points. This architecture and algorithm defines a system that is relatively simple to build, but can do connected information processing. It will decide on the placement of data items and construct paths through the nearest neighbors to join these items. It does this automatically. All connections can be traversed in parallel in time O(diameter). Modifying or adding a new connection takes the same time as parallel traversal.