Multiprocessors Interconnection Networks

Question 1

Two Types of Bus-based Dynamic Interconnection Networks

Answer 1

Single Bus Systems and Multiple Bus Systems

Question 2

generally consists of N processors, each having its own cache, connected by a shared bus; Use of local caches reduces the processor-memory traffic.

Answer 2

Single Bus Systems

Question 3

A multiple bus multiprocessor system uses several parallel buses to interconnect multiple processors and multiple memory modules

Answer 3

Multiple Bus Systems

Question 4

What are the 4 Possible connections of a multiple bus systems

Answer 4

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)

Question 5

Formula for counting the number of connections in a Multiple Bus with Full Bus-Memory Connection (MBFBMC)

Answer 5

B(N+M), where B is the no. of buses, N is no. of processors, M is no. of memory banks.

Question 6

Formula for calculating the “load on bus i” in a Multiple Bus with Full Bus-Memory Connection (MBFBMC)

Answer 6

N+M, where N is no. of processors, M is no. of memory banks.

Question 7

Formula for counting the number of connections in a Multiple Bus with Single Bus-Memory Connection (MBSBMC)

Answer 7

BN+M, where B is the no. of buses, N is no. of processors, M is no. of memory banks.

Question 8

Formula for calculating the “load on bus i” in a Multiple Bus with Single Bus-Memory Connection (MBSBMC)

Answer 8

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

Question 9

Formula for counting the number of connections in a Multiple Bus with Partial Bus-Memory Connection (MBPBMC)

Answer 9

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.

Question 10

Formula for calculating the “load on bus i” in a Multiple Bus with Partial Bus-Memory Connection (MBPBMC)

Answer 10

N+M/g, where N is no. of processors, M is no. of memory banks, g is the no. of buses per group.

Question 11

One of the well-known Multi-Staged Interconnection Networks

Answer 11

The Banyan Network

Question 12

Formula for the No. of MIN stages in a Banyan Network

Answer 12

log2 (N), where N is the number of memory modules

Question 13

Formula for the No. of switching element per stage in a Banyan Network

Answer 13

N/2, where N is the number of memory modules

Question 14

Formula for the total no. of switching element in a Banyan Network; Is also the network complexity

Answer 14

N * log2 (N) or O(N log2 N), where N is the number of memory modules

Question 15

Formula for the no. of switching elements along the path from input to output; Is also the time complexity

Answer 15

log2 (N) or O(log2 N), where N is the number of memory modules

Question 16

It is characterized by having fixed paths, unidirectional or bidirectional, between processors

Answer 16

Static Interconnection Networks

Question 17

Two types of Static networks

Answer 17

Completely Connected Networks (CCN) and Limited Connection Networks (LCN)

Question 18

• 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

Answer 18

Completely Connected Networks (CCN)

Question 19

Formula for the no. of links in a CCN

Answer 19

N(N-1)/2, where N is the no. of nodes

Question 20

Formula for the Degree in a CCN

Answer 20

N-1, where N is the no. of nodes

Question 21

Formula for the Diameter in a CCN

Answer 21

1, it is constant

Question 22

• 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

Answer 22

Limited Connection Networks (LCN)

Question 23

Formula for the no. of links in a Linear Array (LCN)

Answer 23

N-1, where N is the no. of nodes

Question 24

Formula for the Degree of a Linear Array (LCN)

Answer 24

2, it is constant

Question 25

Formula for the Diameter of a Linear Array (LCN)

Answer 25

N-1, where N is the no. of nodes

Question 26

Formula for the no. of links in a Binary Tree (LCN)

Answer 26

N-1, where N is the no. of nodes

Question 27

Formula for the Degree of a Binary Tree (LCN)

Answer 27

3, it is constant

Question 28

Formula for the Diameter of a Binary Tree (LCN)

Answer 28

2([log2 N]-1), where N is the no. of nodes, and “[]” represents the ceiling operation.

Question 29

Formula for the no. of links in a n-cube (LCN)

Answer 29

nN/2, where N is the no. of nodes, and n refers to the dimension of the cube which is 3

Question 30

Formula for the Degree of a n-cube (LCN)

Answer 30

log2 N, where N is the no. of nodes

Question 31

Formula for the Diameter of a n-cube (LCN)

Answer 31

log2 N, where N is the no. of nodes

Question 32

Formula for the no. of links in a 2d-mesh (LCN)

Answer 32

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)

Question 33

Formula for the Degree of a 2d-mesh (LCN)

Answer 33

4, it is constant

Question 34

Formula for the Diameter of a 2d-mesh (LCN)

Answer 34

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)