Parallel Processing & Distributed Systems - Chapter 6: Processor Organization

ThoaiNam
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Criteria:
– Diameter, bisection width, etc.

 Processor Organizations:
– Mesh, binary tree, hypertree, pyramid, butterfly, 
hypercube, shuffle-exchange
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Diameter
– The largest distance between two nodes
– Lower diameter is better

 Bisection width
The minimum number of edges that must be removed in 
order to divide the network into two halves (within one)

 Number of edges per node

 Maximum edge length
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Q-dimensional lattice

 Communication is allowed only between 
neighboring nodes. Interior nodes communicate 
with 2q other nodes.
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Q-dimensional mesh with kq nodes
– Diameter: q(k-1)
– Bisection width: kq-1
– The maximum number of edges per node: 2q
– The maximum edge length is a constant
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Depth k-1: 2k-1 nodes

 Diameter: 2(k-1)

 Bisection width: 1

 Length of the longest edge: increasing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Bandwidth problem on binary tree
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Hypertree of degree k and depth d: a complete k-ary tree of 
height d. 
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 A 4-ary hypertree with depth d has 4d leaves and 2d(2d+1-1) nodes 
in all
– Diameter: 2d
– Bisection width: 2d+1
– The number of edges per node ≤ 6
– Length of the longest edge: increasing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Size k2: base a 2D mesh network containing k2 processors, the 
total number of processors=(4/3)k2 -1/3

 A pyramid of size k2: 
– Diameter: 2logk
– Bisection width: 2k
– Maximum of links per node: 9
– Length of the longest edge: increasing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 (k+1)2k nodes divided into k+1 rows (rank), each contains n=2k
nodes.

 Ranks are labeled 0 through k

 Node(i,j): j-th node on the i-th rank

 Node(i,j) is connected to two nodes on rank i-1: node(i-1,j) and 
node (i-1,m), where m is the integer found by inverting the i-th
most significant bit in the binary representation of j

 If node(i,j) is connected to node(i-1,m), then node (i,m) is 
connected to (i-1,j)

 Diameter=2k

 Bisection width=2k-1

 Length of the longest edge: increasing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Rank 0
Rank 1
Rank 2
Rank 3
Node(1,5): i=1, j=5
j = 5 = 101 (binary)
i=1
001 = 1
Node(1,5) is connected 
to node(0,1)
0 1 2 3 4 5 6 7
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 2k nodes form a k-dimensional hypercube

 Nodes are labeled 0, 1, 2,…, 2k-1

 Two nodes are adjacent if their labels differ in exactly 
one bit position

 Diameter=k

 Bisection width= 2k-1

 Number of edges per node is k

 Length of the longest edge: increasing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6
7
3
2
1
0
4
5
3
2
1
0
1
00
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6
7
3
2
1
0
4
5
14
15
11
10
9
8
12
13

 5 = 0101

 1 = 0001

 4 = 0100

 13 = 1101
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Cube-Connected cycles

 Shuffle-Exchange

 De Bruijn