Section#5: Direct interconnection networks I+II
(CS838: Topics in parallel computing, CS1221, Tue+Thu, Feb 2+4, 1999, 8:00-9:15 a.m.)

The contents

  1. Basic notions and terminology
  2. Requirements on interconnection networks
  3. Mesh-based topologies
  4. Hypercubic topologies
  5. Tree-based topologies
  6. Shuffle-based topologies
A direct interconnection network (IN) of a multiprocessor system is represented by a connected graph whose vertices represent processing nodes and edges represent communication links. A processing node (PN) usually consists of one or more processors, local memory, and communication router. This section is devoted to the description and analysis of topologies and properties of important INs.

Back to the beginning of the page Back to the CS838 class schedule

Basic notions and terminology

Alphabets and strings

d-ary alphabet
is denoted by Zd={0,1,..,d-1}. The operation + modulo n is denoted by +n.
n-letter d-ary strings
Zdn={xn-1... x0; xi in Zd}, n>= 1. The length of string x is denoted by len(x). The empty string (i.e., of length 0) is denoted by e. The i-fold concatenation of string x is denoted by xi.
Binary alphabet
is denoted by B. The inversion of bit bi is \non(bi)=1-b1. If b=bn-1.. bi+1bibi-1.. b0 in Bn, then \noni(b)=bn-1.. bi+1\non(bi)bi-1.. b0.

Graph theory

Vertex and edge set
of graph G is denoted by V(G) and E(G), respectively. Two adjacent vertices u and v form edge ( u,v). They are incident with the edge. Edges ( u,v) and ( v,w) are adjacent.
H = subgraph
of G, H\subset G, if V(H)\subset V(G) and E(H)\subset E(G).
H = induced subgraph
of G if it is a maximal subgraph of G with vertices V(H).
H = spanning subgraph
of G if V(H)=V(G).
of two disjoint graphs G1 and G2, G1\cup G2, is a graph with vertices V(G1)\cup V(G2) and edges E(G1)\cup E(G2).
Cartesian product
of G1 and G2 is graph G=G1 x G2 with V(G)={(x,y); x in V(G1), y in V(G2)} and E(G)={( (x1,y),(x2,y)); ( x1,x2) in E(G1)}\cup {( (x,y1),(x,y2)); ( y1,y2) in E(G2)}.

CAPTION: An example of a cartesian product

Degree of vertex
u, degG(u), is the number of neighbors of u.
Degree set of graph
G, deg(G), is the set {degG(u); u in V(G)}.
Maximum degree
of G is \triangle(G)=max(deg(G)).
Minimum degree
of G is \delta(G)=min(deg(G)).
k-regular graph
G has \triangle(G)=\delta(G)=k.
Connected graph
Every pair u, v of vertices is joined by a path P(u,v), a sequence of adjacent edges.
Path length
len(P(u,v)), is the number of edges P(u,v).
between vertices u and v, distG(u,v), is the length of a shortest path joining u and v.
Average distance
in G, distG(u,v), is \Sigmau,vdistG(u,v)/(N(N-1)).
of G, diam(G), is the maximum distance between any two vertices of G.
is a closed path.
Vertex-disjoint paths
P1(u,v) and P2(u,v) have no vertices in common except for u and v
Edge-disjoint paths
P1(u,v) and P2(u,v) have no edges in common.
(Vertex) connectivity of G, \kappa(G), is the minimum number of vertices whose removal results in a disconnected graph. Edge connectivity of G, \lambda(G), is the minimum number of edges whose removal results in a disconnected graph. It follows that
\kappa(G)<= \lambda(G)<=\delta(G).

CAPTION: Example of a graph G with \kappa(G)=1 and \lambda(G)=\delta(G)=2.

k-connected graph
has \kappa(G)=k. Similarly, k-edge-connected graph has \lambda(G)=k.
Optimal connectivity
Menger's theorem
Between any two distinct vertices of G, there are at least \kappa(G) vertex-disjoint paths and at least \lambda(G) edge-disjoint paths.
Fault diameter
of a connected graph G is the maximum over the lengths of all the shortest vertex-disjoint paths between any two vertices in G. Similarly, we can define the fault distance between any two vertices.
Bipartite graph
There exists a bipartition (or 2-coloring) of its vertex set V, which is a partitioning of V into two disjoint subsets V1 and V2 such that each edge of G has one vertex in V1 and the other vertex in V2.
Balanced bipartite graph
has a bipartition (V1,V2) with |V1|=|V2|.

CAPTION: Examples of bipartite graphs, the first one is not balanced

Hamiltonian path/cycle
of a connected G is a path/cycle joining all vertices of G. A graph having a hamiltonian cycle is hamiltonian. A bipartite graph can have a hamiltonian cycle only if it is balanced.
(Edge) bisection width
of G, bwe(G), is the smallest number of edges removal of which divides G into two parts of equal size (up to one vertex).
Vertex bisection width
of G, bwv(G), is the smallest number of vertices removal of which divides G into two parts having at most [|V|/2] vertices each.

CAPTION: An example of a graph with both edge and vertex bisection width 3

Two graphs are isomorphic if they can be made identical by relabeling vertices.
of G is any isomorphic mapping of G to itself.
graph looks the same independently of from which vertex you look at it, i.e., for any two distinct vertices u and v, there is an automorphism of the graph sending u to v.
graph looks the same independently of from which edge you look at it, i.e., for any two distinct edges e1 and e2 in E(G), there is an automorphism of G sending e1 to e2. Graph G on Figure is edge symmetric, but it is not vertex symmetric. It becomes vertex symmetric if the vertices 1 and 3 are merged. A vertex symmetric graph must be regular.
Digraphs = Oriented graphs
A digraph G has arc set A(G). Arc ( u->v) is incident from u to v u,v in V(G). Vertex u (v) is incident from (to) arc ( u->v), respectively. Arcs ( u->v) and ( v->w) are adjacent. The in-degree and out-degree of u in V(G), denoted by \indegG(u) and \outdegG(u), is the number of arcs incident to and incident from u, respectively. The other notions are derived similarly, digraphs have oriented paths (dipaths), oriented diameters, strong connectedness, and strong connectivity.
While describing INs, we will often use terms nodes and links (or channels) instead of vertices and edges, terms input (output) links or channels, respectively, instead of arcs incident from (incident to) a vertex. We will often use the terms vertices/nodes or edges/links interchangeably. All logarithms are binary if not stated otherwise.
Back to the beginning of the page Back to the CS838 class schedule

Requirements on interconnection networks

An IN should transfer a maximum number of messages in the shortest time with minimum cost and maximal reliability. Clearly, any design of an IN is a tradeoff of various contradictory requirements. The most important requirements are the following:
Small diameter and small average distance
Small average distance allows small communication latency, especially for distance sensitive routing, such as store-and-forward. But it is also crucial for distance insensitive routing, such as wormhole routing, since short distances imply less used links and buffers, and therefore less communication contention.
Small and fixed vertex degree
Small and constant vertex degree allows simple and low-cost universal (i.e., independent of the network size) routers which amortizes the design costs. On the other hand, it implies less links and lower connectivity and larger distances. Ideally, we would like to get low constant vertex degree and at most logarithmic diameter simultaneously. Given N-vertex graph such that \triangle(G)<= k for some constant k, the number of vertices reachable in G within i steps from any vertex is O(ki). Hence, N=O(k^diam(G)), which is equivalent to diam(G)=\Omega(log N). Fixed-degree networks cannot have better than logarithmic diameter.
Large bisection width
Many problems can be solved in parallel using binary divide-and-conquer: split the input data set into two halves and solve them recursively on both halves of the IN in parallel, and then merge the results in both halves into the final result. Small bisection width implies low bandwidth between both halves and it can slowdown the final merging phase. On the other hand, a large bisection width is undesirable for a VLSI design of the IN, since it implies a lot of extra chip wires.
High connectivity and fault tolerance
The network should provide alternative paths for delivering messages in case of link or node faults or communication congestions. Large packets can be delivered faster if they can be split into smaller chunks sent along disjoint paths.
Small fault average distance and diameter
To have these alternative or parallel disjoint paths as short as possible, small fault average distances and small fault diameter are naturally desirable.
The existence of at least a hamiltonian path is not the most important requirement, but it is useful whenever we need to label processors with numbers 1,...,p so that adjacent processors get successive numbers (for example in sorting algorithms).
Hierarchical recursivity
INs are usually defined using some independent parameters, called dimensions. The set of all graphs of different dimensions based on a given definition forms a topology. A topology is hierarchically recursive if a higher-dimensional graph contains lower-dimensional graphs with the same topology as subgraphs. Many INs used in parallel systems are hierarchically recursive, topologies based on cartesian product are one example. Recursiveness makes the design and technology of manufacturing INs easier. Large scale problems that can be solved in parallel by recursive decomposition into smaller subproblems can be easily and efficiently mapped on the hierarchically recursive topologies using induction.
Incremental extendability and incremental scalability
If the definition of the topology allows graphs of any size, the topology is said to be incrementally extendable. There are incrementally extendable topologies, and some are at least partially extendable, since they allow size granularity only greater than 1. Some hierarchically recursive topologies allow graphs of specific discrete sizes, such as powers of two. If a topology is incrementally extendable, a very important question is how the structure of an instance of size n differs from the structure of an instance of size n+k for some integer constant k>=1. An (n+k)-vertex instance can be obtained from a n-vertex one by removing r(k) edges (to get a subgraph of the larger instance) and by adding additional vertices and corresponding edges to this subgraph. If r(k)=O(k), the topology is said incrementally scalable. Very few topologies are incrementally scalable. For example, 2-D meshes are incrementally extendable, but not scalable.
This is a very important requirement. Many IN topologies are vertex or edge symmetric. Intuitively, a symmetric network is easy to understand and the design of parallel and communication algorithms is very much easier, since it is irrelevant where the computation and/or communication starts or in which directions it will evolve. Also, the symmetry is helpful for solving issues related to VLSI design.
Support for routing and collective communication
This is a crucially important property and we will devote it several lectures. The network topology should enable an simple shortest path routing, so that the basic routing algorithm could be implemented in hardware. Equally important parameters of an IN are complexities of permutation routing and one-to-all and all-to-all communication operations. The design of efficient communication algorithms is very simplified if the topology is symmetric and it also depends on the communication technology and router architecture.
Embeddability of and into other topologies
The efficiency of a parallel algorithm running on a parallel machine depends on the similarity between the process graph and the underlying physical IN topology. We need a suitable mapping or embedding of the process graph into the topology. Desirable are those topologies which are able to simulate efficiently other topologies.
Simple VLSI or 3-D layout
Any VLSI implementation of an IN implies VLSI-related requirements, such as easy mapping to rectangular grid, decomposition of a large IN into building blocks so that the lengths and numbers of inter-chip wires is minimal (recall the bisection width above). Except for the bisection width, the discussion of VLSI design issues is beyond the scope of this course.
In the rest of the section, we give a survey of definitions and properties of several well-known topologies for INs. Some topologies are understood better than some others so that the description of properties will vary for various topologies.
Back to the beginning of the page Back to the CS838 class schedule

Mesh-based topologies

This family of topologies, also called strictly orthogonal, include hypercubes, meshes, and tori. These are the most important interconnection topologies due to their simplicity and they are also the best understood topologies.

Binary hypercube of dimension n, Qn

The n-dimensional binary hypercube (or n-cube) is a graph with 2n vertices labeled by n-bit binary strings, with edges joining two vertices whenever their labels differ in a single bit (see Figure).

CAPTION: Hypercube Q4

V(Qn)=Bn |V(Qn)|=2n
E(Qn)={( x,\noni(x)); x in V(Qn),0<= i<n} |E(Qn)|=n2n-1
diam(Qn)=n deg(Qn)={n}

CAPTION: Q6=Q3 x Q3.
The notion of subcubes is extremely important for using a hypercube multiprocessor as a multiuser multitasking machine. Users declare the numbers of required nodes for their tasks and the operating system allocates, if possible, subcubes of the appropriate size, which are released upon completion of the tasks. This is called the subcube allocation problem and there exist many algorithms for it which must maintain lists of allocated and free subcubes. Dynamic allocation and releasing of subcubes lead to the fragmentation problem in the hypercube similar to segment fragmentation of dynamic or virtual memory. The hypercube is the best topology for implementing most parallel and communication algorithms. It serves as a testbed for parallel feasibility of problems on distributed memory architectures. Its only drawback is the logarithmic vertex degree and lack of scalability. Several families of older massively parallel multiprocessors were based on the hypercube: nCUBE series 1 and 2, Intel's iPSC/2 and iPSC/860, TMC's CM-2, and several others. Currently, SGI Origin's interconnection network uses hypercube topology.

n-dimensional mesh of dimensions z1,z2,..,zn, M(z1,z2,..,zn)

Given integers zi>= 2, 1<= i<= n, the n-dimensional mesh with side lengths zi, M(z1,z2,..,zn), is defined as follows (Figure(a) shows mesh M(3,3,4)).
V(M(...))={(a1,a2,..,an) ; 0<= ai<= zi-1 for all i in {1,..,n}} |V(M(...))|=\prodi=1n zi
E(M(...))={( (..,ai,..),(..,ai+1,..)); 0<= ai<= zi-2} |E(M(...))|=\sumi=1n(zi-1)\prod_j=1\atop j\not=in zj
diam(M(...))=\sumi=1n(zi-1)=\Omega(\root n \of |V(M(...))|)
deg(M(...))={n,..,n+j}, j=|{zi; zi>2}|
bwe(M(...))=(\prodi=1n zi)/maxizi if maxizi is even,
                         \Omega((\prodi=1n zi)/maxizi) otherwise.
The most important mesh-based parallel computers are Intel's Paragon (2-D mesh) and MIT J-Machine (3-D mesh). Also transputers used 2-D mesh interconnection. Processors in mesh-based machines are allocated by submeshes and the submesh allocation strategy must handle possible dynamic fragmentation and compaction of the global mesh network, similarly to hypercube machines.

CAPTION: Mesh M(3,3,4)

n-dimensional torus of dimensions z1,z2,..,zn, T(z1,z2,..,zn)

Given integers zi>= 2, 1<= i<= n, the n-dimensional torus T(z1,z2,..,zn), also called toroidal or wrapped mesh, with side lengths z1,z2,..,zn, is defined as follows.
V(T(...))=V(M(...)) |V(T(...))|=\prodi=1n zi
E(T(...))={( (..,ai,..),(..,ai+_zi1,..)); 0<= ai<zi} |E(T(...))|=n x \prodi=1n zi
diam(T(...))=\sumi=1n\left[ zi/ 2\right] deg(T(...))={2n}
Figure(b) shows a 3-dimensional torus T(3,3,4). Adding wrap-around edges changes dramatically many structural properties, even though many feature remain similar to meshes. We will highlight some of them.

CAPTION: Torus T(3,3,4).

Comparisons of hypercubes, meshes, and tori

%See Chapter \refEmbeddingsChapter for more details. For example, Figure illustrates that torus T(4,4) is isomorphic to Q4.

CAPTION: T(4,4)= Q4.
Table shows the tradeoff between the diameter, number of edges, and bisection width of M(8,8,4), T(8,8,4), and Q8. All these graphs have the same size |V()|=256 and M(8,8,4)\subset T(8,8,4)\subset Q8.

M(8,8,4) T(8,8,4) Q8
diam() 17 10 8
|E()| 640 768 1024
bwe() 32 64 128
CAPTION: Comparison of several characteristics of meshes, tori, and hypercubes.
The tori are likely to become widely used interconnection networks. For example, Cray/SGI T3D and T3E and Convex Exemplar are based on 3-D torus, Intel/CMU iWarp uses 2-D torus, and several commercial machines use rings as a primary interconnect.
Back to the beginning of the page Back to the CS838 class schedule

Hypercubic topologies

Hypercubic networks are logarithmic-diameter and constant-degree derivatives of the hypercube. The price to be paid for the constant vertex degree is worse extendability: the size of instances becomes n2n or similar. Therefore, they grow even faster with increasing dimension than the hypercube. They share many properties, such as bisection width \Omega(N/log N). Let us shortly describe two representants: cube-connected cycles and butterflies.

Cube-connected cycles of dimension n, CCCn

CAPTION: Cube Connected Cycles CCC3.

V(CCCn)={(i,x) ; 0<= i<n \wedge x in Bn} |V(CCCn)|=n2n
E(CCCn)={((i,x),(i+n1,x)),((i,x),(i,\noni(x))); (i,x) in V(CCCn)} |E(CCCn)|=n2n-1+n2n
diam(CCCn)=(2n-2)+[ n/2] for n>3, diam(CCC3)=6 deg(CCCn)={3}
CCCn is constructed from Qn by replacing each hypercube vertex with a cycle of n vertices so that each vertex takes care of just one hypercube direction. See Figure where (*,x) stands for {(0,x), (1,x), (2,x)}. Figure shows other possible ways how to view CCC topology. Part (b) is a useful simplification, CCC is viewed as a pancake made of all cycles, all the cycles look alike, and all hypercube edges are projected into vertex loops.

CAPTION: Another view of CCC.

Butterfly of dimension n

Actually, there are two kinds of butterfly networks, wrapped and ordinary. The wrapped butterfly, wBFn, is defined as follows:
V(wBFn)={(i,x); 0<= i<n \wedge x in Bn} |V(wBFn)|=n2n
E(wBFn)={( (i,x),(i+n1,x)),((i,x),(i+n1,\noni(x)))\mid(i,x) in V(wBFn)} |E(wBFn)|=n2n+1
diam(wBFn)=n+[ n/ 2] deg(wBFn)={4}
If each cycle of wBFn shrinks to a single vertex and redundant edges are removed, we get Qn (see Figure). Wrapped butterfly topology has basically the same properties as CCC, except that it has more edges, and therefore larger bisection width and lower diameter.

CAPTION: Wrapped butterflies
An n-dimensional ordinary butterfly, oBFn, can be made form wBFn by replacing n-vertex cycles with (n+1)-vertex paths (or in other words, an ordinary butterfly is a hypercube with each vertex unfolded into a path).

CAPTION: Ordinary butterfly oBF3.

V(oBFn)={(i,x); 0<= i<= n \wedge x in Bn} |V(oBFn)|=(n+1)2n
E(oBFn)={((i,x),(i+1,x)), ((i,x),(i+1,\noni(x)))\mid(i,x) in V(oBFn),i<n} |E(oBFn)|=n2n+1
diam(oBFn)=2n deg(oBFn)={2,4}
Back to the beginning of the page Back to the CS838 class schedule

Tree-based topologies

Process graphs have often tree-like structure. However, the bottleneck at the root and poor connectivity and robustness disqualifies any simple complete tree as a potential general purpose IN topology. Fortunately, tree-like graphs can be efficiently mapped on most usual INs. The only commercially important tree-based parallel machine have been TMC's CM-5 with its famous fat tree and some special-purpose pyramidal machines. In this course, we will describe an interesting hybrid of meshes and trees.

2-D mesh of trees of height n, MTn

2-D and 3-D meshes suffer from large diameter, whereas trees suffer from small connectivity and bisection width. 2-D mesh of trees is a hybrid topology based on the 2-D mesh and complete binary tree, which has the diameter of the tree topology (i.e., logarithmic) and the bisection width of the 2-D mesh topology (i.e., square root of the size). For integer n>= 1, let N=2n. Then MTn is defined as follows:

CAPTION: Mesh of trees MT2.

V(MTn)=(Bn x \cupi=0nBi)\cup(\cupi=0nBi x Bn) |V(MTn)|=3N2-2N
E(MTn)={((x,y),(xa,y)); len(x)< n\wedge a in B} |E(MTn)|=4N(N-1)
                   \cup {((x,y),(x,ya)); len(y)< n\wedge a in B} bwe(MTn)=N=\Theta(\sqrt|V(MTn)|)
deg(MTn)={2,3} diam(MTn)=4log N=4n
No commercial machine has been built upon this topology yet.
Back to the beginning of the page Back to the CS838 class schedule

Shuffle-based topologies

The adjacency in orthogonal and hypercubic topologies is based on incrementing and/or inverting coordinates. In shuffle topologies, the adjacency is based on shifting the whole strings, typical operation is left shift and left rotation by one position, which enforces orientation on edges. Since most of notions and results apply equally to both directed and undirected versions of these topologies and digraphs are regular in contrast to undirected graphs, we will concentrate on digraphs only. Shuffle-based topologies have very rich, but also rather complicated structure. In general, they are more difficult to understand compared to previous topologies. They have the following properties: The shuffle-based family includes three main topologies, shuffle exchange, de Bruijn, and Kautz, and their variations. We will describe only the first two main ones.

Shuffle-exchange networks

Even if the shuffle-exchange topology can be defined for any alphabet, the focus of computer science has always been primarily on the binary shuffle-exchange topology. The shuffle of a binary string x, \sigma(x), is its left rotation by one bit. The inversion of the least significant bit of x is called the exchange operation. Shuffle-exchange digraph of dimension n, SEn, is defined as follows:

CAPTION: Digraph SE3.

V(SEn)=Bn |V(SEn)|=2n
A(SEn)={( x->\non0(x)); x in Bn}\cup{( x->\sigma(x)); x in Bn} |A(SEn)|=2n+1
in deg(SEn)=\outdeg(SEn)={2} diam(SEn)=2n-1

De Bruijn digraph of degree d and dimension n, dB_d,n

The adjacency is based on only one general operation of left shift by 1 position \lambda: If x=xn-1.. x0 in Zdn and a in Zd, then \lambda(x,a)=xn-2.. x0a.
V(dBd,n)=Zdn |V(dBd,n)|=dn
E(dBd,n)={( x->\lambda(x,a)); x in Zdn,a in Zd} |E(dBd,n)|=dn+1
in deg(dBd,n)=\outdeg(dBd,n)={d} diam(dBd,n)=n

CAPTION: De Bruijn digraphs dB2,3 and dB3,2.
Back to the beginning of the page Back to the CS838 class schedule

Last modified: Fri Jan 23 by tvrdik