Network Topology

A network is a collection of switches, connected by communication channels. A processor and memory have more than one ports connected to these switches. The connection may be in bus, mesh, hypercube, two stage multi-stage network or fat-tree topology.

The simplest network topology is a bus. This network can be used in both local-memory machine models and modular memory machine models. In either case, all processors and memory modules are typically connected to a single bus. In each step, at most one piece of data can be written onto the bus. This data might be a request from a processor to read or write a memory value, or it might be the response from the processor or memory module that holds the value. In practice, the advantage of using a bus is that it is simple to build and, because all processors and memory modules can observe the traffic on the bus, it is relatively easy to develop protocols that allow processors to cache memory values locally. The disadvantage of using a bus is that the processors have to take turns accessing the bus. Hence, as more processors are added to a bus, the average time to perform a memory access grows proportionately.

Figure: Interconnection Networks: (a) Bus, (b) Mesh, (c) hypercube.

In two-dimensional rectangular mesh topology, each switch has distinct label $(x, y)$, where $0 \leq x \leq X -1$ and $0 \leq y \leq Y -1$, where $X, Y$ are lengths of the sides of the rectangle. The number of switches in a mesh is thus $X . Y$. Every switch, except those on boundary, communicate to four neighbors. This network is good for local memory machines.

A hypercube is a network with $2^n$ switches in which each switch has a distinct $n$-bit label. Two switches are connected by a communication channel in a hypercube if and only if the labels of the switches differ in precisely one bit position.

Many parallel algorithms exists for mesh and hypercube networks, they are fine tuned, but have disadvantages that they may not perform well other networks. Hence, in order to work on a new machine, an algorithm need to be developed from scratch. The algorithm that routes the information through network should exploit the network topology.

A multistage network is used to connect one set of switches called the input switches to another set called the output switches through a sequence of stages of switches. Such networks were originally designed for telephone networks. The stages of a multistage network are numbered $1$ through $L$, where $L$ is the depth of the network. The switches on stage 1 are the input switches, and those on stage $L$ are the output switches. In most multistage networks, it is possible to send a message from any input switch to any output switch along a path that traverses the stages of the network in order from 1 to $L$.

Multistage networks are frequently used in modular memory computers; typically processors are attached to input switches, and memory modules are attached to output switches. A processor accesses a word of memory by injecting a memory access request message into the network. This message then travels through the network to the appropriate memory module. If the request is to read a word of memory, then the memory module sends the data back through the network to the requesting processor. There are many different multistage network topologies. Figure , for example, shows a depth-2 network that connects 4 processors to 16 memory modules. Each switch in this network has two channels at the bottom and four channels at the top. The ratio of processors to memory modules in this example is chosen to reflect the fact that, in practice, a processor is capable of generating memory access requests faster than a memory module is capable of servicing them.

Figure: (a)2-Level multi-stage network (b) Fate-tree network topologies.

A complete binary tree of height $k, k \geq 0$ an integer, has $n = 2^{k+1} - 1$ nodes. The root node is at level 0 and the $2^k$ leaves are at level $k$. Each node at level $1, \dots , k - 1$ has two children and one parent, the root node does not have a parent node, and the leaves at level $k$ do not have children nodes. Notice that the degree of the network is $3$ and that the communication diameter is $2k = 2\lfloor \log_2 n\rfloor$. One severe disadvantage of a tree is that when extensive communication occurs, all messages traveling from one side of the tree to the other must pass through the root, causing a bottleneck. This is because the bisection bandwidth is only 1. Fat trees (fig. ), alleviate this problem by increasing the bandwidth of the communication links near the root. This increase can come from changing the nature of the links, or, more easily, by using parallel communication links. Other generalizations of binary trees include complete $t$-ary trees of height $k$, where each node at level $0, \dots , k - 1$ has $t$ children. There are $(t^{k+1} - 1)/(t − 1)$ nodes, the maximum degree is $t + 1$, and the diameter is $2k = 2\lfloor \log_t n\rfloor$.