IC20 Homework 5 Solved

Exercise 1
Write the function drawButterfly that: 

-       takes the value n for expressing the size N=2n of the Butterfly network  - draw the Butterfly network  

Write the function self-routing-Butterfly that: 

-       takes a permutation in input  

-       calculates the routing on the Butterfly using the self-routing algorithm - gives as output: o the matrix P of size N x 2n, where each column represents the element of the permutation, in particular odd columns represent the sequence before traversing nodes in a stage and even columns represent the sequence after traversing nodes in a stage. In the case a conflict occurs, the program stops after completing the computation for all the nodes in the current stage and writes the number of the first stage where the conflict occurs (assuming all inputs traverse the network in parallel)

o the matrix S of size (N/2) x n, representing the switch setting of the Butterfly, where 0 represents the state straight, 1 represents the state cross, and a value at your choice (any value different from 0 and

1, or NaN) for switches not set yet   

Write the script that:

-       takes the value n for expressing the size N=2n of the Butterfly network as a parameter 

-       chooses a random permutation of N elements 

-       calls the function self-routing-Butterfly 

-       draws the picture of the Butterfly calling the function drawButterfly using different colors for straight and cross state of nodes (or drawing the node setting with lines inside the switch), and using the color gray for nodes of stages not traversed (or leaving the switch empty), furthermore, in case of conflict the nodes involved must be highlighted

 

Remark The following definition of the Butterfly stage and Butterfly network can be useful:

An edge stage is a Butterfly edge stage of size l, l= 1, 2, ···, n−1, if any node, with (n−1)-bit binary label v, in the first node stage is connected to node v′ in the second stage if and only if v = v′ (straight edge) or v and v′ differ only in the l-th bit (cross edge). A Butterfly is a log N stage network consisting of an ordered sequence of Butterfly edge stages of increasing size from 1 to n−1. 

 

Exercise 2 - Interconnection Networks – CLOS
Write a script (for the design of a Clos network) that :

-       takes as input: N, number of inputs/outputs, and n, size of the crossbar module used for building switches – in the first stage, n is also the number of inputs per module allowed

-       calculates the number of modules in each of the three stages of a Clos network, and the number of inputs and outputs of modules in both cases, strictly non-blocking and rearrangeable network

-       writes in output the number and size of modules, for each of the three stages, in the two cases

-       calculates the gain when using the Clos network, with respect to the Crossbar N x N, comparing their costs, in both cases strictly non-blocking and rearrangeable non-blocking,  

Reference: Exercise discussed in lecture given on 11 May 2020