Limited Connection Networks

• Limited connection networks (LCNs) do not provide a direct link from every node to every other node in the network. Instead, communications between some nodes have to be routed through other nodes in the network.
• Two other conditions seem to have been imposed by the existence of limited interconnectivity in LCNs.
  1. the need for a pattern of interconnection among nodes and
     • linear arrays;
       • in the worst possible case, when node 1 has to send a message to node N, the message has to traverse a total of $N-1$ nodes before it can reach its destination.
       • Therefore, although linear arrays are simple in their architecture and have simple routing mechanisms, they tend to be slow. This is particularly true when the number of nodes N is large.
       • The network complexity of the linear array is O(N) and its time complexity is O(N).
     • ring (loop) networks;
     • tree networks;
       • In a tree network, of which the binary tree (shown in Fig. 1.8d) is a special case, if a node at level $i$ (assuming that the root node is at level 0) needs to communicate with a node at level $j$, where $i>j$ and the destination node belongs to the same root's child subtree, then it will have to send its message up the tree traversing nodes at levels $i-1,i-2,\ldots,j+1$ until it reaches the destination node.
       • If a node at level $i$ needs to communicate with another node at the same level $i$ (or with node at level $j \ne i$ where the destination node belongs to a different root's child subtree), it will have to send its message up the tree until the message reaches the root node at level 0. The message will have to be then sent down from the root nodes until it reaches its destination.
       • It should be noted that the number of nodes (processors) in a binary tree system having $k$ levels can be calculated as:
         $$N(k)=2^0+2^1+2^2+\ldots+2^k$$

       • Notice also that the maximum depth of a binary tree system is $log_2 N$, where N is the number of nodes (processors) in the network.
       • Therefore, the network complexity is $O(2^k)$ and the time complexity is $O(log_2 N)$.
     • cube networks;
       • Cube-connected networks are patterned after the n-cube structure. An n-cube (hypercube of order n) is defined as an undirected graph having 2n vertices labeled 0 to $2n-1$ such that there is an edge between a given pair of vertices if and only if the binary representation of their addresses differs by one and only one bit.

         Figure 2.8: A 4-cube.

         
       • A 4-cube is shown in Fig. 2.8. In a cube-based multiprocessor system, processing elements are positioned at the vertices of the graph. Edges of the graph represent the point-to-point communication links between processors.
       • As can be seen from the figure, each processor in a $4$-cube is connected to four other processors. In an $n$-cube, each processor has communication links to $n$ other processors.
       • Recall that in a hypercube, there is an edge between a given pair of nodes if and only if the binary representation of their addresses differs by one and only one bit. This property allows for a simple message routing mechanism.
       • The route of a message originating at node $i$ and destined for node $j$ can be found by XOR-ing the binary address representation of $i$ and $j$.
       • If the XOR-ing operation results in a 1 in a given bit position, then the message has to be sent along the link that spans the corresponding dimension.
         • For example, if a message is sent from source (S) node 0101 to destination (D) node 1011, then the XOR operation results in 1110.
         • That will mean that the message will be sent only along dimensions 2, 3, and 4 (counting from right to left) in order to arrive at the destination.
         • The order in which the message traverses the three dimensions is not important. Once the message traverses the three dimensions in any order it will reach its destination.
       • The hypercube is referred to as a logarithmic architecture. This is because the maximum number of links a message has to traverse in order to reach its destination in an n-cube containing $N=2^n$ nodes is $log_2 N=n$ links.
       • It is worth mentioning that the Intel iPSC is an example of hypercube-based commercial multiprocessor systems. A number of variations to the basic hypercube interconnection have been proposed.
     • two-dimensional arrays (nearest-neighbor mesh);

       Figure 2.9: A $3 \times 3 \times 2$ mesh network.

       
       • An n-dimensional mesh can be defined as an interconnection structure that has $K_0 \times K_1 \times \ldots \times K_{n-1}$ nodes where $n$ is the number of dimensions of the network and $K_i$ is the radix of dimension $i$. Figure 2.9 shows an example of a $3 \times 3 \times 2$ mesh network.
       • A node whose position is $(i,j,k)$ is connected to its neighbors at dimensions $i \pm 1, j \pm 1$, and $k \pm 1$. Mesh architecture with wrap around connections forms a torus.
       • A number of routing mechanisms have been used to route messages around meshes. One such routing mechanism is known as the dimension-ordering routing.Using this technique, a message is routed in one given dimension at a time, arriving at the proper coordinate in each dimension before proceeding to the next dimension.
         • Consider, for example, a 3D mesh. Since each node is represented by its position $(i,j,k)$, then messages are first sent along the $i$ dimension, then along the $j$ dimension, and finally along the $k$ dimension.
         • At most two turns will be allowed and these turns will be from $i$ to $j$ and then from $j$ to $k$.
         • In Fig. 2.9, it is shown the route of a message sent from node $S$ at position $(0,0,0)$ to node $D$ at position $(2,1,1)$.
       • Other routing mechanisms in meshes have been proposed. These include dimension reversal routing, the turn model routing, and node labeling routing.
       • Multiprocessors with mesh interconnection networks are able to support many scientific computations very efficiently. It is also known that n-dimensional meshes can be laid out in n dimensions using only short wires and built using identical boards, each requiring only a small number of pins for connections to other boards.
       • Another advantage of mesh interconnection networks is that they are scalable. Larger meshes can be obtained from smaller ones without changing the node degree (a node degree is defined as the number of links incident on the node).
       • Because of these features, a large number of distributed memory parallel computers utilize mesh interconnection networks. Examples include MPP from Goodyear Aerospace, Paragon from Intel, and J-Machine from MIT.
  2. the need for a mechanism for routing messages around the network until they reach their destinations.