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 6Fall 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)