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.

 

 

Summary of monday's class

Multiported Memory Network and Multistage Network

Multiported Memory Network

The crossbar network closely resembled a PRAM model. It’s scalability was not great, and the cost of the network increased as we added more processors/memory modules.

In a multiported memory, we have as many ports as there are memory modules. A wire goes into the port from each memory module. On the other side are the processors. In this way, each processor can communicate with any memory.

So, in a multiported model, we can have all the possible permutations of memory-processor connection.

Let ‘W’ represent the width of a single bus [ideally, data bus should be considered]

Minimum Bandwidth = w

Maximum Bandwidth = O(w*n)

In this model, the reliability increase. If one port malfunctions, the processors can still access the rest of the modules. Also, we can add additional memories by simply increasing the number of ports. This improves scalability.

Data security is also increases because we can map each of the ports to limit the access of different processors to the memory modules.

Multistage Network

In this, the processors are connected to the memory modules using multiple stages of switching elements.The output from each stage is connected to the inputs of the next stage using a perfect shuffle (logical circular shift left) connection system.

In terms of binary representation of the processors, each stage of the perfect shuffle can be thought of as a cyclic logical shift left; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit.

Different settings of a 2*2 switch box:

• Multistage network makes use of shuffling.

• There is a unique path from a processor to a memory.

• Some of the permutations of memory-processor connections are not allowed (as can be seen from the figures below).

In the above diagram:

• Single stage Shuffle-Exchange is show on left

• Perfect shuffle mapping function is shown on right

• Perfect shuffle operation: cyclic shift 1 place left, eg 101 --> 011

• Exchange operation: invert least significant bit, e.g. 101 --> 100

Complexity = O((logk n) * n/k)     [for the figure shown below, k = 2]

Wiring complexity = O(n log n)

Latency = O(log n)

Switching complexity = O(n log n)

Omega Network

The table shows the various complexities of different interconnecting networks:

Network	Latency	Switching Complexity	Wiring Complexity	Blocking
Bus	O(n)	O(1)	O(w)	Yes
Multistage	O(log n)	O(n log n)	O(n*w logn)	Yes
Crossbar	O(1)	O(n*n)	O(n*n*w)	No

• This network is more reliable than a crossbar. If a switch box stops working, only a part of the memory becomes inaccessible.

• It is more scalable than bus-based networks. Its scalability cost is also less than that of a bus’.

• The total number of switches used in a multistage network of n switches (each switch k X k) is (n/k)logkn i.e., its cost is O(n log n) as compared to O(n*n) for a crossbar.

• There exist a single path from source to destination, thus contrary to a crossbar network, omega network is a blocking network.

• This is shown here as:

--the path from 010 -->110 (red)

--the path from 110 -->100 (blue)

has blockage as at input 110 has to wait till 010 has passed otherwise it results in collision.

Another type of network is Benes Network.

In this network, for 8 bits:

I Stage = 4 shuffles of 8 objects

II Stage = 2 shuffles of 4 objects

Similarly, for 16 bits:

I Stage = 8 shuffles of 16 objects

II Stage = 4 shuffles of 8 objects

III Stage = 2 shuffles of 4 objects

by Rishabh Jain and Rudra Pratap Singh Nirvan

Crossbar Switch Network

CROSSBAR SWITCH NETWORK

A crossbar is an assembly of switches between multiple inputs and multiple outputs arranged in the form of a matrix. If a crossbar has ‘m’ inputs and ‘n’ outputs, then it has a matrix with m*n crosspoints. At each crosspoint is a switch, which when closed, it connects one of the ‘n’ inputs to one of ‘m’ outputs. Note that the crossbar is a network that allows multiple connections to be achieved simultaneously. It is an example of a dynamic switch based interconnection network.

Deductions from the figure:-

-> The number of switching elements required are n*m.

-> The message delay to traverse from input to output is constant, regardless of which i/o are communicating.

For a general n*m crossbar,

1. The network complexity (or switching complexity) is measured in terms of switching points i.e O(n*m). Due to this, they are expensive to build. However, the crossbar has highest bandwidth and routing capability. Therefore, for small networks, it is a desired choice.

2. The time complexity is measured in terms of input to output delay is O(1).

3. The number of wires required are O((n+m)*w).

where, w is the width of buses.

For example, consider an 8*8 crossbar connecting 8 processors to 8 memory modules.

The bandwidth will depend on

1. Material of the wire (optical fibres are preferred).

2. Width of the bus. By increasing the width of the bus the bandwidth increases.

Let “BW” be the bandwidth per channel.

Also, let us assume that n = m [the smaller value between  ‘n’ and ‘m’ is considered]

Then, maximum bandwidth utilized = n*BW

Minimum bandwidth utilized = BW

=> Range of utilization of communication channel = BW  to  n*BW

Some factors to be considered with regards to a Crossbar:

1. Scalability: This refers to the change in performance by increasing or decreasing the number of memory modules.

2. Reliability: This refers to the impact on the system when a switch, wire, or any other part of the network breaks down.

3. Latency: It refers to the time required by the processor to access memory.

Advantages of Crossbar Networks:

1. It is a Non Blocking Network that allows multiple i/o connections to be achieved simultaneously.

2. It provides full connectivity, i.e., any permutation can be implemented using a crossbar.

3. It is highly useful in a multiprocessor system, as all processors can send memory requests independently and asynchronously.

4. It gives maximum utilization of bandwidth as compared to other networks like bus system, multistage networks, etc.

by Rishabh Jain and Rudra Pratap Singh Nirvan

Lecture summary for 10 Feb (Monday)

Ma'am

Pasted below is the summary of the 10 Feb (Monday) lecture on the topic "Prefix Computation and Linear Network".

Regards

Rudra Pratap Singh Nirvan

COE 3 (6th Semester)

______________________________________________________________________________________________

Prefix Computation

It is a binary, closed and associative computation.

Let '(o)' represent a computation, and x0, x1, x2, … x(n-1) be a set of 'n' numbers. Then,

C1   =   x0 [C1 = computation 1]

C2   =   x0 (o) x1

C3   =   x0 (o) x1 (o) x2

.

.

C(n-1)   =   x0 (o) x2 (0) … (o) x(n-1)

Algorithm:

for i = 1  to  (n - 1) {

   sum[i] = x[i] + x[i-1]

}

for i = 2  to  (n - 1) {

   sum[i] = sum[i] + sum[i-2]

}

We keep adding such loops  and get the final loop as:

for i = n - 1  to  (n - 1) {

   sum[i] = sum[i] + sum[i-(n-1)]

}

The above code is written using high level syntax. Changing it to machine level instructions results in the following:

for i = 1  to  (n - 1) {

   Read M[i] into R1

   Read M[i-1] into R2

   Write (R1 + R2) into M[i]

}

M[i] = ith memory location

Read = memory read operation

Write = memory write operation

R1, R2 = registers

---

The same algorithm can be written in a compact form:

for j = 0  to  log n - 1 {

   for i = 2j to (n - 1) { __

       Read M[i] into R1   |

       Read M[i - 2j] into R2   |--> Simultaneous Read/Write

       Write (R1 + R2) into M[i] _| O(1)

   }

}

Time Complexity = O(log n)

Processors = O(n)

---

• The read/write operations used above are "exclusive" read/write operations (matrix multiplication had used concurrent read/write).

• Access time is same because it is a shared memory model.

• The operations occur parallely. Hence, it is a PRAM model.

• The PRAM model can be considered to be an almost SIMD model (which has one CU and various PUs) with masking.

• As an MIMD, the code has be written for each processor.

• We are ignoring network delays and the PRAM model is an idealistic RAM model.

Some concurrent write models:

1. Common model

2. Random model

3. Aggregation model

4. Priority model

Linear Network

It employs message passing paradigm and not the shared memory paradigm. It is a static network. The data is not read in O(1) time, but has to travel in a linear fashion.

So, this type of network involves the concept of "routing".

We change the "Read" operation in the above mentioned algorithm to "Route" operation to show this change.

for j = 0  to  log n - 1 {

   for i = 2j to (n - 1) {

       Read M[i] into R1

       Route M[i - 2j] into R2  ←- "Read" changed to "Route"

       Write (R1 + R2) into M[i]

   }

}

Time complexity:

1 + 2 + 22 + 23 + … (log n - 1) times

=  2log n - 1  

=  O(n)

---

• Any processor was reading from any memory location without any delay in the shared memory model. This is not the case in linear network.

• It is a static network.

• This network is a fine granularity model.

• Diameter is the largest of the shortest paths between any two nodes of the network.

• Diameter of the above network  =  n - 1

• Our aim should be to minimize this diameter.

• If we connect the first node with the last node, the diameter changes.

• New diameter = floor( n / 2 )

In the above divide algorithm, we used a bottom-up approach. A top-down approach could also have been used.

By Rishabh Jain and Rudra Pratap Singh Nirvan