Hypercube Fa2010 Parallel Processing, Low-Diameter Architectures Slide 1
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 1 Hypercube
LOW-Diameter Architectures Study the hypercube and related interconnection schemes Prime example of low-diameter(logarithmic) networks Theoretical properties, realizability, and scalability Complete our view of the sea of interconnection nets Fa2010 Parallel Processing, Low-Diameter Architectures Slide 3
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 3 Low-Diameter Architectures Study the hypercube and related interconnection schemes: • Prime example of low-diameter (logarithmic) networks • Theoretical properties, realizability, and scalability • Complete our view of the “sea of interconnection nets
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)