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 9Fall 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