Hypercubes and Their algorithms Study the hypercube and its topologicallalgorithmic properties Develop simple hypercube algorithms(more in Ch. 14) Learn about embeddings and their usefulness Topics in This Lecture 13.1 Definition and Main Properties 13.2 Embeddings and Their Usefulness 13.3 Embedding of Arrays and Trees 14.5 Broadcasting in Hypercube 14.6 Adaptive routing in Hypercube 15 Inverting a Lower-Triangular Matrix Fa2010 Parallel Processing, Low-Diameter Architectures Slide 4
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 4 Hypercubes and Their Algorithms Study the hypercube and its topological/algorithmic properties: • Develop simple hypercube algorithms (more in Ch. 14) • Learn about embeddings and their usefulness Topics in This Lecture 13.1 Definition and Main Properties 13.2 Embeddings and Their Usefulness 13.3 Embedding of Arrays and Trees 14.5 Broadcasting in Hypercube 14.6 Adaptive routing in Hypercube 15 Inverting a Lower-Triangular Matrix
13.1 Definition and main properties P P P Intermediate architectures logarithmic or sublogarithmic diameter P Begin studying networks that are intermediate between diameter -1 complete network and diameter-p12 mesh Sublogarithmic diameter Superlogarithmic diameter 2 log n/loglog n log n n/2 n Complete PDN Star Binary tree Torus Ring Linear network pancake hypercube arr ray Fa2010 Parallel Processing, Low-Diameter Architectures Slide 5
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 5 13.1 Definition and Main Properties P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 0 P P P P P P P P P 0 1 2 3 4 5 6 7 8 Intermediate architectures: logarithmic or sublogarithmic diameter Begin studying networks that are intermediate between diameter-1 complete network and diameter-p 1/2 mesh Complete network 1 2 log n / log log n log n n n/2 n − 1 Sublogarithmic diameter Superlogarithmic diameter PDN Star, pancake Binary tree, hypercube Torus Ring Linear array
Hypercube and Its History Binary tree has logarithmic diameter, but small bisection Hypercube has a much larger bisection Hypercube is a mesh with the maximum possible number of dimensions 2×2×2 2 9= log p We saw that increasing the number of dimensions made it harder to design and visualize algorithms for the mesh Oddly, at the extreme of log2 p dimensions things become simple again Brief history of the hypercube(binary g-cube)architecture Concept developed: early 1960s [Squi63 Direct(single-stage)and indirect(multistage)versions: mid 1970s Initial proposals[Peas771, [Sull77]included no hardware Caltech's 64-node Cosmic Cube: early 1980s [ Seit85 Introduced an elegant solution to routing(wormhole switching) Several commercial machines mid to late 1980s Intel PSc (personal supercomputer), CM-2, nCUBE(Section 22. 3) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 6
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 6 Hypercube and Its History Binary tree has logarithmic diameter, but small bisection Hypercube has a much larger bisection Hypercube is a mesh with the maximum possible number of dimensions 2 2 2 . . . 2 ⎯ q = log2 p ⎯→ We saw that increasing the number of dimensions made it harder to design and visualize algorithms for the mesh Oddly, at the extreme of log2 p dimensions, things become simple again! Brief history of the hypercube (binary q-cube) architecture Concept developed: early 1960s [Squi63] Direct (single-stage) and indirect (multistage) versions: mid 1970s Initial proposals [Peas77], [Sull77] included no hardware Caltech’s 64-node Cosmic Cube: early 1980s [Seit85] Introduced an elegant solution to routing (wormhole switching) Several commercial machines: mid to late 1980s Intel PSC (personal supercomputer), CM-2, nCUBE (Section 22.3)
Basic Definitions 0 Hypercube is generic term;(a)Binary 1-cube (b)Binary 2-cube 3-cube, 4-cube,., g-cube built of two built of tw binary o-cubes binary 1-cubes, labeled o and 1 labeled 0 and 1 In specifIc cases Fig.13.1 The recursive structure of binary hypercubes (c)Binary 3-cube, built of two binary 2-cubes, labeled 0 and 1 Parameters: 2q 0 B=0/2=291 D=g=log2p d=g= log2p (d) Binary 4-cube, built of two binary 3-cubes, labeled 0 and 1 Fa2010 Parallel Processing, Low-Diameter Architectures Slide 7
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 7 Basic Definitions Hypercube is generic term; 3-cube, 4-cube, . . . , q-cube in specific cases 0 1 00 01 10 11 (a) Binary 1-cube, built of two binary 0-cubes, labeled 0 and 1 (b) Binary 2-cube, built of two binary 1-cubes, labeled 0 and 1 0 1 (c) Binary 3-cube, built of two binary 2-cubes, labeled 0 and 1 0 000 001 010 011 100 101 110 111 1 000 001 010 011 100 101 110 111 (d) Binary 4-cube, built of two binary 3-cubes, labeled 0 and 1 0 1 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Fig. 13.1 The recursive structure of binary hypercubes. Parameters: p = 2q B = p/2 = 2q–1 D = q = log2p d = q = log2p
The 64-node Hypercube Only sample wraparound links are shown to avoid clutter amorphic to the4×4×4 3D torus (each has 64×6/2 links) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 8
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 8 Only sample wraparound links are shown to avoid clutter The 64-Node Hypercube Isomorphic to the 4 4 4 3D torus (each has 64 6/2 links)