Summary of monday's class

Static Networks

 

Hi all,

Previously we discussed about some of the dynamic networks which include Cross-bar networks, Multiported Memories, Multistage networks in the class .There are other dynamic networks too like Benes network, Baseline network etc. But today we discussed a network which is rather a static network . We have already discussed one static network which was Linear static network (we've considered this model during Prefix computation ).

 

Hypercube Interconnection Network

 

Systems were designed to reduce the amount of time required for processors to perform simple message routing and Hypercube and Mesh are among two of the popular interconnection schemes. Here we are going to discuss about the Hypercube Interconnection Network.

 

·         A k-dimensional hypercube  contains 2^k processors (nodes).

·         Each processing node contains a switch.

·         The nodes are numbered from 0 to 2^k – 1, usually in binary.

·         Two nodes are separated by a single link if the binary values of their numbers differ by one bit i.e. they are neighbors.

Following fig. shows the various dimensional hypercubes along with the binary equivalents of their nodes.

Note:- As can be seen from the fig.,the no. of bits for the binary equivalent are equal to the log(no.of processors(N)) i.e logN which is also the degree of a processor.

 

Now we discuss the Hypercube n/w with an eg. of a 4D n/w and analyzing various factors such as:-

·         Latency

·         Scalability

·         Diameter

·         Bisection Width

·         No. of Links

·         Dimension

Later on we’ll calculate the overall complexity of matrix multiplication algo.

 

·         Latency:- logN (maximum path taken for processing).

·         Scalability:- These kind of static networks are not scalable as their degree are changing but linear networks have constant degree(except corner nodes).

 

·         Diameter:- 2*logN (diameter tells about the communication overhead. It is the minimum number of steps it takes for one processor to send a message to the processor that is the farthest away).

 

·         Bisection width:- it tells how well two parts of a interconnection are connected.

In linear network bisection width is constant but here it depends upon the no of processors i.e., it is equal to N/2.

 

·         No of Links:- N*logN/2

 

·         Dimention of hypercube of NxN processors :-

total no. of nodes = N*N

dimension = 2*logN

 

 

Multiplication of two 4x4 matrices

 

Using the above interconnection technique, we have to majorly perform the following 5 steps(in bracktes time required is specified) :-

1).Broadcast A (N*logN)

2).Transpose B ( N )

3).Broadcast B (N*logN)

4).Multplication and addition of rows and columns on N*N processors

   (particularly N multiplications and N-1 additions)

5).Rearrange the matrix to get required elements(N*logN)

 

In Broadcasting A we have to perform the following:

        First apply R1 and R2 at 2 and 7 (diagonal edge) and R3 and R4

        at 8 and 13 repectively.

1st stage - send the rows to their respective 4th neighbour(other                neighbours will remain masked)

2nd stage - now simultaneously broadcast the information to their              respective 3rd neighbours.

This simplifies the control unit as there is a single control line for all the processors.

Hence, in log(N) (in general) stages we will have R1, R2, R3, R4 at the front face of the cube i.e, at 0th ,1st , 2nd and 3rd processor we have R1 ,R2, R3, R4 respectively.

Similarly on other faces too.

 

After transposing the columns of matrix B we will broadcast the transpose of C1, C2, C3, and C4 on their respective processors. Let C1, C2, C3 and C4 represents transpose of columns.

        First apply C1 and C2 at 0 and 1 and C3 and C4 at 8 and 12 repectively.

1st stage - send the columns to their respective 1st neighbour(other           neighbours will remain masked)

2nd stage - now simultaneously broadcast the information to their              respective 2nd neighbours.

After this we'll have C1 at all processors of front face of cube.

       

Now multiplication and addition of R1 and transpose of C1 will be performed on 0th processor , of R2 and C1 on 1^st processor, of R3 and C1 on 2^nd processor, of R4 and C1 on 4^th processor... this will happen simultaneously on other processors too for other columns.

Now we rearrange the elements of hypercube to form the final resultant matrix.

 

Conclusion

Considering all the above steps, we get the overall complexity to be O(N*logN).

The value obtained when we considered N^3 processors was O(logN).

Here broadcasting is done in order to utilize parallelism and hence the factor logN comes into the picture as an overhead.

 

 

Submitted by:-

Sweety Yadav and Uzma.