Multi-transputer systems

The availability of only four point-to-point links on a transputer is a limiting factor on the range of possible topologies of transputer networks. Perhaps the most obvious topology is the two-dimensional mesh which, depending on the edge connections, can be extended to either a cylinder or torus (c.f. the DAP interconnection structure). A fully connected torus has problems communicating with the outside world, however, since every available link is in use.

If processes in non-adjacent transputers wish to communicate they must do so via intermediate processors, which must themselves be programmed to perform message routing since the link protocol does not support store-and-forward directly. The number of links traversed by a message in transit between an arbitrary pair of processors is referred to as the path length, and in a two-dimensional mesh this is exactly 2(n^½-1) hops for an n processor system. In general, for a k dimensional square mesh, the upper bound on path length is k(n^1/k-1) hops.

It would appear at first glance that a square mesh in three dimensions cannot be constructed from processors with just four links, as each node in a three-dimensional (3D) mesh must have at least six links (up, down, left, right, back and front). However, a chain of exactly two transputers has six spare links, and can therefore be used to implement a single node in a 3D square mesh. Such a square mesh has a maximum path length of exactly 4(n/2)^1/3-2 hops.

Near-neighbour mesh topologies are very efficient for algorithms with predominantly local communication patterns, but for algorithms with little communication locality an upper bound distance between processors that is better than O(n^1/3) may be required. The binary k-cube network has a maximum path length of k = ⌈log₂n⌉ and this is less than 4(n/2)^1/3-2 for all values of n for which a perfect square 3D mesh can be constructed. Clearly cubes of dimension one, two, three and four can be constructed from transputers, but k-cubes with k>4 cannot be constructed directly. Instead, a network known as the cube-connected cycle can be used to model the binary k-cube, where nodes have degree which is logarithmic in n, from processing elements which actually have a fixed degree. Each node in the k-cube is constructed from a ring (or cycle) of c=k/2 transputers (c > 2). A network containing 2^2c nodes is hence created with a maximum path length between any two nodes of 2c. Within a node the maximum distance between any pair of transputers is c/2, and this routing distance may be incurred at any node visited on a path between an arbitrary pair of nodes. Consequently, the maximum distance between any pair of transputers is limited to c² hops, which means that the upper bound on path length is O(log²n). This is a graph-theoretic distance, and is not directly related to the physical wire lengths. In practice the 300mm limit on transputer link lengths places a strict upper bound on the size of system that can actually be constructed using k-cube topologies without using reconstituted link protocols.

Another topology which has fixed degree and logarithmic path length, but which has wire lengths which grow more slowly, is the ternary tree. A binary tree comprises nodes with links to two offspring nodes and a parent node. A ternary tree is a simple extension to this which makes use of all four links on a transputer by having three offspring nodes instead of two. At the leaves of the tree there will be a large number of unconnected links, and these could be used for I/O or to link two trees (of similar depth) together. The maximum path length of a ternary tree is simply twice the depth of the tree, and is therefore 2⌈log₃(2n+1) - 1⌉ which is O(log n).

An alternative to having one of the above fixed topologies is to have a configurable array of transputers from which any of the previously described networks can be constructed. The logical structure of such an architecture is depicted in the figure and essentially consists of n transputers and a 4n-input to 4n-output full permutation network. Assuming one could build a full permutation network for the required value of n, it would then be possible to configure all n! possible permutations of link connections. Computing the configuration control signals has been shown to take O(nlog n) time but since the number of permutations that is likely to be of real interest is only a small proportion of the total number of possible permutations, the power of a full permutation network is unlikely to be required in practice.