Question

In a 4x4 multistage butterfly network, Pe is the probability that a link is fault-free. write expressions for the bandwidth BW, connectability Q, and the expected number of accessible processors. Assume that a processor generates memory requests with a probability Pr. assume that switchboxes do not fail.

Answer 1

• In mulitistage network ( butterfly network it is built out 2*2 switches two inputs and two outputs).
• Switch has four settings –

1. S- Straight - top input line connected to top output and bottom input line to bottom output
2. C – Cross – top input line connected to bottom output and bottom input line to top output.
3. UB – Upper broadcast – top input lie connected to both output lines
4. LB – lower broadcast – bottom input line connected to both output lines.

• Pe is the probability that the link is fault free.

Bandwidth Analysis (BW) – It depends not only on network conditions but also on the memory requirements of processors.

Q(t) – number of paths does not indicate how many distinct processor and memories are still accessible

BW- The Expected number of processor actively communicating with some memory

Simplyfying assumptions – The destinations of memeory request by processors are statistically independent and uniformly distributed among the N memories

Ntework bandwidth – The product of number of memories

N and Tm – the probability that a given memory ( say memory0 is non faulty and has a request at its input.

The Probability of a request on an output link of a switch – calculated from the probability that a request has been accepted at the input links to this switch.

Connectability Analysis - Q – The Average number of operational paths – connected processor – memory pairs.

Exactly one path between a processor and a memory

Q = product of number of processor – memory pairs and the probability of a fault – free path

Latter probability – pr p ^k+1 pm

N^2 – number of processor – memory paths

Q= N^2 pr p ^k+1 pm.

Expected number of accessible processor – Ar- The Expected number of accessible processor – product of N and the probability Er that a processor 0 is accessible.

Link is in state X = 0 (X=1) idf all ( not all) paths from it to the memories are faulty.

A faulty path is a path with at least one faulty link

A faulty link is in state x=0

Thus by assuming processor generates memory requests with a probability Pr. and that switchboxes do not fail.