Multiprocessors Interconnection Networks Flashcards
Two Types of Bus-based Dynamic Interconnection Networks
Single Bus Systems and Multiple Bus Systems
generally consists of N processors, each having its own cache, connected by a shared bus; Use of local caches reduces the processor-memory traffic.
Single Bus Systems
A multiple bus multiprocessor system uses several parallel buses to interconnect multiple processors and multiple memory modules
Multiple Bus Systems
What are the 4 Possible connections of a multiple bus systems
Multiple Bus with Full Bus-Memory Connection (MBFBMC), Multiple Bus with Single Bus-Memory Connection (MBSBMC), Multiple Bus with Partial Bus-Memory Connection (MBPBMC), Multiple Bus with Class-based Memory Connection (MBCBMC)
Formula for counting the number of connections in a Multiple Bus with Full Bus-Memory Connection (MBFBMC)
B(N+M), where B is the no. of buses, N is no. of processors, M is no. of memory banks.
Formula for calculating the “load on bus i” in a Multiple Bus with Full Bus-Memory Connection (MBFBMC)
N+M, where N is no. of processors, M is no. of memory banks.
Formula for counting the number of connections in a Multiple Bus with Single Bus-Memory Connection (MBSBMC)
BN+M, where B is the no. of buses, N is no. of processors, M is no. of memory banks.
Formula for calculating the “load on bus i” in a Multiple Bus with Single Bus-Memory Connection (MBSBMC)
N+Mj, where N is no. of processors, Mj is no. of memory modules in class j.
Since this type of connection does not have a class, each memory will be its own class. Thus, Mj = 1
Formula for counting the number of connections in a Multiple Bus with Partial Bus-Memory Connection (MBPBMC)
B(N+M/g), where B is the no. of buses, N is no. of processors, M is no. of memory banks, g is the no. of buses per group.
Formula for calculating the “load on bus i” in a Multiple Bus with Partial Bus-Memory Connection (MBPBMC)
N+M/g, where N is no. of processors, M is no. of memory banks, g is the no. of buses per group.
One of the well-known Multi-Staged Interconnection Networks
The Banyan Network
Formula for the No. of MIN stages in a Banyan Network
log2 (N), where N is the number of memory modules
Formula for the No. of switching element per stage in a Banyan Network
N/2, where N is the number of memory modules
Formula for the total no. of switching element in a Banyan Network; Is also the network complexity
N * log2 (N) or O(N log2 N), where N is the number of memory modules
Formula for the no. of switching elements along the path from input to output; Is also the time complexity
log2 (N) or O(log2 N), where N is the number of memory modules
It is characterized by having fixed paths, unidirectional or bidirectional, between processors
Static Interconnection Networks
Two types of Static networks
Completely Connected Networks (CCN) and Limited Connection Networks (LCN)
- each node is connected to all other nodes in the network
- fast delivery of message from any source node
- expensive in terms of number of links needed
Completely Connected Networks (CCN)
Formula for the no. of links in a CCN
N(N-1)/2, where N is the no. of nodes
Formula for the Degree in a CCN
N-1, where N is the no. of nodes
Formula for the Diameter in a CCN
1, it is constant
- do not provide a direct link from every node to every other nod in the network
- communications between some node have to be routed through other nodes
Limited Connection Networks (LCN)
Formula for the no. of links in a Linear Array (LCN)
N-1, where N is the no. of nodes
Formula for the Degree of a Linear Array (LCN)
2, it is constant
Formula for the Diameter of a Linear Array (LCN)
N-1, where N is the no. of nodes
Formula for the no. of links in a Binary Tree (LCN)
N-1, where N is the no. of nodes
Formula for the Degree of a Binary Tree (LCN)
3, it is constant
Formula for the Diameter of a Binary Tree (LCN)
2([log2 N]-1), where N is the no. of nodes, and “[]” represents the ceiling operation.
Formula for the no. of links in a n-cube (LCN)
nN/2, where N is the no. of nodes, and n refers to the dimension of the cube which is 3
Formula for the Degree of a n-cube (LCN)
log2 N, where N is the no. of nodes
Formula for the Diameter of a n-cube (LCN)
log2 N, where N is the no. of nodes
Formula for the no. of links in a 2d-mesh (LCN)
2(N-n), where N is the no. of nodes, and n refers to the dimension of the mesh (i.e., is it a 3x3, 2x2, 4x4 mesh, then n=3, 2, or 4)
Formula for the Degree of a 2d-mesh (LCN)
4, it is constant
Formula for the Diameter of a 2d-mesh (LCN)
2(n-1), where n refers to the dimension of the mesh (i.e., is it a 3x3, 2x2, 4x4 mesh, then n=3, 2, or 4)
