Neighbors of a Node in a Hypercube q-14q-2…X2X1X iD of node x q-1q2…x2X1x0 dimension-0 neighbor; No(X) q-1q2…X2X1 Xo dimension-1 neighbor N,X) The neighbors of node x ⅩX1X q dimension-(g-1)neighbor; Na-1(x) 0100 Dim o Nodes whose labels differ in k bits Dim 3 (at Hamming distance k) connected Dim 2 1100 by shortest path of length k 0000 Dim 110 Both node-and edge-symmetric l111 Strengths: symmetry, log diameter, 0110 and linear bisection width 0111 Weakness: poor scalability 1010101 Fa2010 Parallel Processing, Low-Diameter Architectures Slide 9
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 9 Neighbors of a Node in a Hypercube xq–1xq–2 . . . x2x1x0 ID of node x xq–1xq–2 . . . x2x1x0 dimension-0 neighbor; N0 (x) xq–1xq–2 . . . x2x1 x0 dimension-1 neighbor; N1 (x) . . . . . . xq–1 xq–2 . . . x2x1x0 dimension-(q–1) neighbor; Nq–1 (x) The q neighbors of node x Nodes whose labels differ in k bits (at Hamming distance k) connected by shortest path of length k Both node- and edge-symmetric Strengths: symmetry, log diameter, and linear bisection width Weakness: poor scalability Dim 0 Dim 1 Dim 2 Dim 3 0100 0101 0110 0000 1100 1101 1111 0111 0011 x 1011 0010 1010 x
13.2 Embeddings and Their Usefulness Dilation Congestion 5Fig.132 \b Load tactor= Embedding a even-node 0 2 binary tree f into 2D 3」|4 meshes of Various sizes Dilation 2 Dilation Congestion =2 Congestion =2 Load factor Load factor s b「 Expansion: tio of the number of e nodes(9/7,8/7 3 4 5 and 4/7 here) Dilation: Longest path onto which an edge is mapped (routing slowdown) Congestion Max number of edges mapped onto one edge(contention slowdown) Load factor: Max number of nodes mapped onto one node(processing slowdown) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 10
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 10 Dilation: Longest path onto which an edge is mapped (routing slowdown) Congestion: Max number of edges mapped onto one edge (contention slowdown) Load factor: Max number of nodes mapped onto one node (processing slowdown) 13.2 Embeddings and Their Usefulness Fig. 13.2 Embedding a seven-node binary tree into 2D meshes of various sizes. 0 2 3 4 1 5 6 0 2 3 4 1 6 5 0,1 2 4 3 6 5 6 1 0 3,4 2,5 a b c d e f a b c d e f a b c d e f b c, d f Dilation = 1 Congestion = 1 Load factor = 1 Dilation = 2 Congestion = 2 Load factor = 1 Dilation = 1 Congestion = 2 Load factor = 2 Expansion: ratio of the number of nodes (9/7, 8/7, and 4/7 here)
13.3 Embedding of Arrays and Trees g-1)-bit O Gray code 0000...000 0000...001 Ng((x) 0000...011 0100...000 q-Dcube 0 (q-1]ube 1 1:100...000 Fig. 13.3 Hamiltonian cycle in the g-cube Alternate inductive proof: Hamiltonicity of the q-cube 000...011 is equivalent to the existence of a g-bit Gray code 1000...010 000...000 Basis: q-bit Gray code beginning with the all-Os codeword (9-1)-bit and ending with 10q-1 exists for g= 2: 00, 01, 11, 10 Gray code In reverse Fa2010 Parallel Processing, Low-Diameter Architectures Slide 11
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 11 13.3 Embedding of Arrays and Trees Alternate inductive proof: Hamiltonicity of the q-cube is equivalent to the existence of a q-bit Gray code Fig. 13.3 Hamiltonian cycle in the q-cube. (q ?1)-cube 0 x (q ?1)-cube 1 N (x) k N (x) q? N (N (x)) q? k (q – 1)-bit Gray code 000 . . . 000 000 . . . 001 000 . . . 011 . . . 100 . . . 000 0 0 0 0 1 1 1 1 100 . . . 000 . . . 000 . . . 011 000 . . . 010 000 . . . 000 (q – 1)-bit Gray code in reverse Basis: q-bit Gray code beginning with the all-0s codeword and ending with 10q–1 exists for q = 2: 00, 01, 11, 10 q （q -1） q （q -1）
Mesh/Torus Embedding in a Hypercube Dim 2 Column 3 Column Column Dim o Column o Fig 13.5 The 4 x 4 mesh/torus is a subgraph of the 4-cube Is a mesh or torus a subgraph of the hypercube of the same size? We prove this to be the case for a torus(and thus for a mesh) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 12
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 12 Mesh/Torus Embedding in a Hypercube Is a mesh or torus a subgraph of the hypercube of the same size? Dim 0 Dim 1 Dim 2 Dim 3 Column 0 Column 1 Column 2 Column 3 Fig. 13.5 The 4 4 mesh/torus is a subgraph of the 4-cube. We prove this to be the case for a torus (and thus for a mesh)
Torus is a subgraph of same-size Hypercube O a A tool used in our proof Ob 3-by-2 Product graph G1×G2 Hasn1×n2 nodes Each node is labeled by a pair of labels, one from each component graph Two nodes are connected if either component of the two nodes were connected in the component graphs Fig 13. 4 Examples of product graphs The 2a x 2x 2C. torus is the product of 2a, 2b, 2C ,. node rings The(a+ b+c+.)-cube is the product of a-cube, b-cube, c-cube, The 2q-node ring is a subgraph of the g-cube If a set of component graphs are subgraphs of another set, the product graphs will have the same relationship Fa2010 Parallel Processing, Low-Diameter Architectures Slide 13
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 13 Torus is a Subgraph of Same-Size Hypercube A tool used in our proof Product graph G1 G2 : Has n1 n2 nodes Each node is labeled by a pair of labels, one from each component graph Two nodes are connected if either component of the two nodes were connected in the component graphs Fig. 13.4 Examples of product graphs. The 2 a 2 b 2 c . . . torus is the product of 2 a -, 2 b -, 2 c -, . . . node rings The (a + b + c + ... )-cube is the product of a-cube, b-cube, c-cube, . . . The 2 q -node ring is a subgraph of the q-cube If a set of component graphs are subgraphs of another set, the product graphs will have the same relationship = 3-by-2 torus = = 0 1 2 a b 0a 1a 2a 0b 1b 2b