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
Embedding Trees in the Hypercube The( 2q-1)-node complete binary tree even weight is not a subgraph of the q-cube odd weights ○○. Q. even weights Proof by contradiction based on the parity of node label weights(number of 1s in the labels) The 2q-node double-rooted complete even weights binary tree is a subgraph of the g-cube odd weights lew roots NC(NEx) Fig 13.6 The 2q-node N(N fx) double-rooted 入△八 complete binary tree is a subgraph of 2q-node double-rooted Double-rooted tree Double-rooted tree the g-cube complete binary tree n the(q? -cube 0 n the(q?)-cube 1 Fa2010 Parallel Processing, Low-Diameter Architectures Slide 14
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 14 Embedding Trees in the Hypercube The (2 q – 1)-node complete binary tree is not a subgraph of the q-cube even weight odd weights even weights odd weights even weights Proof by contradiction based on the parity of node label weights (number of 1s in the labels) The 2 q -node double-rooted complete binary tree is a subgraph of the q-cube Fig. 13.6 The 2q -node double-rooted complete binary tree is a subgraph of the q-cube. New Roots x N (N (x)) N (N (x)) 2 -node double-rooted complete binary tree q Double-rooted tree in the (q?)-cube 0 Double-rooted tree in the (q?)-cube 1 N (x) c N (x) b N (x) a b c c b N (N (x)) N (N (x)) c a a c
14.5 Broadcasting on a Hypercube Flooding: applicable to any network with all-port communication 00000 Source node 00001,00010,00100,01000,10000 Neighbors of source 00011,00101,01001,10001,00110,01010,10010,01100,10100,11000 Distance2 nodes 00111,01011.10011,01101,10101,11001,01110,10110.11010.11100 Distance-3 nodes 01111410111,11011,11101,11110 Distance- 4 nodes 11111 Distance-5 node Binomial broadcast tree with single-port communication 00000 Time Fig. 14.9 l0000 The binomial 01000 l1000 broadcast tree 01100 l1100 for a 5-cube 00010 00001 2345 Fa2010 Parallel Processing, Low-Diameter Architectures Slide 15
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 15 14.5 Broadcasting on a Hypercube Flooding: applicable to any network with all-port communication 00000 Source node 00001, 00010, 00100, 01000, 10000 Neighbors of source 00011, 00101, 01001, 10001, 00110, 01010, 10010, 01100, 10100, 11000 Distance-2 nodes 00111, 01011, 10011, 01101, 10101, 11001, 01110, 10110, 11010, 11100 Distance-3 nodes 01111, 10111, 11011, 11101, 11110 Distance-4 nodes 11111 Distance-5 node Binomial broadcast tree with single-port communication 0 1 2 3 4 5 Time 00000 10000 01000 11000 00100 01100 10100 11100 00001 00010 Fig. 14.9 The binomial broadcast tree for a 5-cube