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