Parallel Processing & Distributed Systems - Chapter 8: Processor Organization - Thoai Nam

Nội dung text: Parallel Processing & Distributed Systems - Chapter 8: Processor Organization - Thoai Nam

1. Processor Organization Thoai Nam
2. Criteria  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 Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
3. Mesh (2)  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 Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
4. Fat Tree  Bandwidth problem on binary tree Khoa Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
5. Hypertree (2)  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 Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
6. Butterfly (1)  (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 node(i-1,j)  Diameter=2k  Bisection width=2k  Length of the longest edge: increasing Khoa Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
7. Hypercube (1)  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 Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM
8. Hypercube (3) 4 12  5 = 0101 0 8  1 = 0001 5 13  4 = 0100 1 9  13 = 1101 6 14 2 10 7 15 3 11 Khoa Khoa học và Kỹ thuật Máy tính - Đại học Bách Khoa Tp.HCM