Lecture summary for 19th of Feb

Various types of topologies used for static

                                 networks

There are various types of static networks, all of which are characterized by their node degree;

Node degree  is the number of links (edges) connected to the node. Some well-known static networks are the following:

Degree 1: shared bus

Degree 2: linear array, ring

Degree 3: binary tree, fat tree, shuffle-exchange

Degree 4: two-dimensional mesh (Illiac, torus)

Varying degree: n-cube, n-dimensional mesh, k-ary n-cube

 

Now we would discuss some of the static networks studied in the class.

Ring Network:-

A ring is obtained by connecting the two terminal nodes of a linear array with one extra ring.Here degree of each node is two.

By increasing the degree of each node to d (where d is greater than 2) we can obtain a chordal ring. And for d = N – 1  , we obtain a completely connected network

Specifically we would study Chordal Ring Network.

No. of Links :- Degree of node * no. of nodes/2  (N represents no. of nodes)

For a completely connected network:-

Degree :- N-1

No. of Links :- N*(N-1)/2

Latency :- O(1)

Bisection Width :- N/2 * N/2

 

Barrel Shifter:-

The barrel shifter is obtained from the ring by adding extra links from each node to those nodes having a distance equal to an integer power of 2.That is node i is connected to node j if

                                        |j – i| = 2^r

Where r can 0 ,1 , 2 ,……..,n-1 and N = 2^n (N is number of processors)

A barrel shifter is sometimes called a plus-minus- 2i network.

Routing functions:

B+i (j ) = (j + 2i) mod N

B–i (j ) = (j – 2i) mod N

 where 0 ≤ j = N– 1 and 0 ≤ i < log2N.

 For example, a 16-node barrel-shifter network would have not just ±1 and ±4 shifts, like a mesh network, but also ±2 and ±8 shifts. 

Each node in an N-node barrel shifter is directly connected to 2 logN–1 different nodes.

Diameter:- The diameter of a barrel shifter is (log2N)/2.

 

Tree:-

TREE

Basic concept:

In a tree network there is only one path between any two nodes. The taller the tree, the higher is communication bottleneck at high levels of the tree. Two remedies are possible:

          

We may have (a) static tree networks, or (b) dynamic tree networks.

A binary tree with N nodes has diameter 2(h-1), where

h = ceil(logN) is the height of the tree. The binary tree has the advantages of being expandable and having a simple implementation. Nonetheless, it can still cause long communication delays between faraway leaf nodes. Leaf nodes farthest away from each other must ultimately pass their message through the root. Since traffic increases as the root is approached, leaf nodes farthest away from each other will spend the most amount of time waiting for a message to traverse the tree from source to destination.

Fat tree network:-

Alternatively, we may introduce fat tree networks (see below).

One problem with the binary tree is that there can be heavy traffic toward the root node. Consider that the root node acts as the single connection point between the left and right subtrees. As can be observed in Figure, all messages have to be passed through the root.To reduce the effect of such a problem, the fat trees were introduced. Fat trees are more like real trees in which the branches get thicker near the trunk.Proceeding up from the leaf nodes of a fat tree to the root, the number of communication links increases, and therefore the communication bandwidth increases.

The structure of the fat tree is based on a binary tree. Each edge of the binary tree corresponds to two channels of the fat tree. One of the channels is from parent to child, and the other is from child to parent. The number of communication links in each channel increases as we go up the tree from the leaves and is determined by the amount of hardware available.

Star topology of interconnection networks

The star is a two level tree with a high node degree at the central node of d = N-1 and a small constant diameter of 2 .

The star architecture has been used in systems with centralized supervisor node. It is shown in fig.

                          

Mesh and Torus  

A two-dimensional mesh consists of k1*k0 nodes, where ki >= 2 denotes the number of nodes along dimension i. In  general , a k-dimensional mesh with N = n^k nodes has an interior node degree of 2k and the network diameter K(n-1).

In a two-dimensional mesh network each node is connected to its north, south, east, and west neighbors(except the corner ones).

                     

                Routing path from node 6 to node 12.

The mesh is frequently used architecture which has been implemented in the Illiax IV , MPP , DAP and Intel Paragon with variations.

A variation of the mesh by allowing wraparound connections we can obtain illiac mesh

                 

                           A 16-node Illiac network.            

In general , an nxn iliac mesh should have a diameter of d = n-1, which only half of the diameter for a pure mesh.

To further reduce the diameter of a mesh network, another variation of this network, called torus (or two-dimensional  torus ), has also been proposed.

A torus is a combination of ring and mesh networks.

The diameter of a torus with N=n^2 nodes is 2*floor(n / 2) , which is the distance between the corner and the center node. Note that the diameter is further decreased from the mesh network.

 

                                    

 

 

K-ary n-cube Networks

 

Rings , mashes , tori ,binary n-cubes (2 nodes in each  dimension , hypercubes)  and omega networks are topologically isomorphic to a family of k-ary n-cube networks .

 

The parameter n is the dimension and k is the radix , or the number of nodes ( multiplicity ) along each dimension . These two numbers are relative to the numbers of nodes , N , in the network by :

                        N = k^n , (k = nth root of N , n = logN with base k)

 

                   

 

 

Cube connected cycles

 

This architecture is modified from the hypercube. In general one can construct k-cube-connected cycles(CCC) from a k-cube with n = 2^k cycles nodes. The idea is to replace each vertex of the k-dimensional hypercube by a ring of k-nodes. A k-cube can be thus transformed to a k-CCC with k*(2^k) nodes.

Diameter = 2*k

 

 

Summary of Static Network characteristics

 

Network type	Node degree,d	Network diameter	No of Links,l	Bisection Width, B	Symmetry	Remarks on Network size
Linear array	2	N - 1	N-1	1	No	N nodes
Ring	2	Floor(N/2)	N	2	Yes	N nodes
Completely connected	N - 1	1	N(N-1)/2	(N/2)^2	Yes	N nodes
Binary tree	3	2(h-1)	N-1	1	No	Tree height, h =ceil(logN)
Star	N - 1	2	N-1	Floor(N/2)	No	N nodes
2-D  Mesh	4	2(r-1)	2N – 2*r	R	No	r*r mesh where r = r^(1/2)
Illiac mesh	4	r - 1	2N	2r	No	Equivalent to a chordal ring of r = N^(1/2)
2-D torus	4	2*floor(r/2)	2N	2r	Yes	r*r torus where r = N^(1/2)
Hypercube	n	n	nN/2	N/2	Yes	N nodes, n = logN (dimension)
CCC	3	2k-1 + floor(k/2)	3N/2	N/(2k)	Yes	N = k*2^k nodes with a cycles length k>=3
k-ary n-cube	2n	n * floor(k/2)	nN	2k^(n-1)	Yes	N = k^n nodes

 

 

 

Hypercube interconnection has the following limitations :-

 

1.   Scalability:- because of change in degree on adding extra node . this can be overcome by using cyclic cube.

2.   Hot spot:- When algorithms are not symmetrical (alike matrix multiplication ), then some of the processors remain more busy then the others ,hence reducing the reliability. Because of this reason higher dimensional hypercubes are not so much in practice. This is overcome by using lower dimensional hypercubes.

3.   Latency :- This problem is overcome by worm-hole routing.

 

(We've tried to summarize all the topics discussed in class. If some of the

 topic are still uncovered, pls do comments )

Thanx .

Posted by Uzma and Sweety Yadav.