The requirements of parallel computing structures are somewhat different from those of a telephone system. In a telephone network requests for the connection of a circuit-switched link between an originator and a respondent may occur at any time. The primary aim is to maximise the number of concurrent circuits. In a parallel architecture a network is required to support either processor-to-memory connections or processor-to-processor communication links. It is instructive to visualise an interconnection network in a parallel computer simply as a `black box', with a number of input ports and a number of output ports, which performs a specified routing function to connect inputs to outputs.
In SIMD systems, where a single instruction operates on a multiplicity of data, the routing function may be completely defined within each data-movement instruction. Consequently all input-output connections will be distinct. Much of the remainder of this chapter discusses interconnection networks which fall into this category. In MIMD systems, where each connection is defined by individual processors operating independently, no assumptions can be made about the input-output connections requested by each processor. For example, two processors may both request data from the same shared memory bank simultaneously, resulting in network requests with distinct input ports but the same output port. Although this problem is not found exclusively in MIMD systems most of the research into solving this problem had been on MIMD systems (q.v.).
An idealised interconnection structure takes a set of labelled input ports and sets up a number of connections them to a similar set of output ports, as shown in the figure. In order to simplify this discussion of interconnection networks it is assumed that the number of input and output ports in the network are equal. Hence if A is defined to be an ordered set of N port labels, then
A = {0, 1, 2, .... , N-1}
and a routing function f is a function from port labels to port labels:
f:A → A
If f is an injection on A, then it can often be represented as a sequence of simple permutations of the labels in A.
For example, if A represented a labelled deck of playing cards then a possible permutation to perform would be a perfect shuffle, and in fact this is a very useful permutation for interconnection networks.