pauldan@hou2e.UUCP (P.SAUNDERS) (04/16/85)
### Always put your disclaimer first. ###
I have heard a lot of talk about hypercube architectures, but have yet to
see any substantial definition of one.
Can anybody help describe it to me, or point me to some literature? I know
what a hypercube is (I think), but I would like to know specifically how
this geometric creature is being applied to parallel computing.
Thanks much for any help!
Dan Masi
{allegra,...}!hou2e!pauldan or
" !ark2!danrkl@ahuta.UUCP (k.laux) (04/16/85)
REFERENCES: <545@hou2e.UUCP> The hypercube is a 4 dimensional construct, also known as a tesseract. Unfolded into 3D space it looks like a stack of 4 cubes and has another 4 cubes attached to the 4 sides of the second cube from the bottom (or top, whichever). In other words, picture a cross, then hang two cubes off of the front and back. To fold the tesseract back up, one must fold the four hanging cubes toward the first cube (short end), then make the 4th cube in the stack circle around to the 1st cube and be attached there but with a half twist. Got it? :-) Another way to look at it is to picture a small cube centered within a larger cube where each corner of the small cube is connected to the corresponding corner of the larger cube. All in all a hypercube is 8 cubes mangled through the 4th dimension. R. Kevin Laux Software Vendor Tech Support ATTIS Lincroft ahuta!rkl
wcs@ho95b.UUCP (Bill Stewart) (04/17/85)
An n-hypercube can be represented as a complete set of n-vectors of 0's
and 1's (eg {0001, 0010, 0011,..}) forming the vertices, with edges
joining "adjacent" vertices, which differ in only one value.
Each vertex has n edges attached to it. You can show that the distance
between any two vertices is <=n.
At each node, put a small computer (e.g. 68000 + 1 Meg + Floating Pt.)
with n bus controllers (typically some kind of DMA Ethernet).
You now have an array of 2**n processors, which can communicate in a
fixed time. You have to worry a bit about thoughput limitations at
each node, but it's real easy to distribute work to the 2**n nodes.
(A "broadcast" message can reach everyone in time n.)eugene@ames.UUCP (Eugene Miya) (04/22/85)
> Can anybody help describe it to me, or point me to some literature? I know > what a hypercube is (I think), but I would like to know specifically how > this geometric creature is being applied to parallel computing. > Dan Masi > {allegra,...}!hou2e!pauldan or > " !ark2!dan Others tried to describe cubes. You can see a model of the projection of a 4-D cube in Sagan's text Cosmos (not computers, but geometry), p. 262 hardbound. Plus several papers below have diagrams. You are fortunate; I just put a cube proposal together, so I have the refs before me. There are over 150 Caltech Cube papers plus numerous other non-Tech papers on hypercubes. One of the proposed benefits of cubes is that they incorporate many of the other topologies in one: limited meshes, rings, cubes, etc. It's a communication cost optimization problem. I'm trying to move a production Cray code to a Cube. A small cube, quickly turned out to be a joke (8 processors, a cube in the normal sense or 3 space cube). A 32-(or 5 space cube barely holds a 2-D for fluid dynamics. A 3-D problem can be a 20 by 100 by 100 mesh with 30 variables per point. Collapsing to 2-D increases the storage requires O(n^2). Needless to say, we have to simplfy the problem. We'll try a ring topolgy first, then a limited mesh, and so on. Nice to have one architecture to try and compare all this. ----- %T Caltech Concurrent Computation Project - List of memos/ papers %R Hm 0 %D Currently 1984 %I California Institute of Technology %C Pasadena, CA %K Caltech Cosmic Cube, hypercube, C^3P %A K. V. S. Bhat %T Fault Diagnosis in Hypercube Connected Array of Processors %J 3rd International Conference on Distributed Computing Systems %C Miami, FL %D October 1982 %I IEEE %P 318-322 %K %O Network Topology %A Laxmi N. Bhuyan %A Dharma P. Agrawal %T Generalized Hypercube and Hyberbus Structures for a Computer Network %J IEEE Transactions on Computers %V C-33 %N 4 %D April 1984 %P 323-333 %K Distributed computers, hyperbus structures, hypercube structures, local area networks, multistage interconnection networks, parallel computers, topological optimization %O Interconnection networks %A James R. Goodman %A Carlo H. Sequin %T Hypertree: A Multiprocessor Interconnection Topology %J IEEE Transactions on Computers %V C-30 %N 12 %D December 1981 %P 923-933 %K Communication networks, hypercube, message traffic, multicomputers, routing algorithms, tree structure %X Reproduced in the 1984 tutorial: \fI Interconnection Networks for parallel and distributed processing\fP by Wu and Feng. %A C. L. Seitz %T Concurrent VLSI Architecture %R Hm84 %I California Institute of Technology %C Pasadena, CA %D June 1984 %K Caltech Cosmic Cube, hypercube, C^3P %X To appear Dec 1984 IEEE TC. %A C. L. Seitz %T The Cosmic Cube %J Communications of the ACM %V 28 %N 1 %D January 1985 %P 22-33 %r Hm83 %d June 1984 %K CR Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); C.5.4 [Computer System Implementation]: VLSI Systems; D.1.2 [Programming Techniques]: Concurrent Programming; D.4.1 [Operating Systems]: Process Management General terms: Algorithms, Design, Experimentation Additional Key Words and Phrases: highly concurrent computing, message-passing architectures, message-based operating systems, process programming, object-oriented programming, VLSI systems, homogeneous machine, hypercube, C^3P %X Excellent survey of this project. %A T. Feng %T A survey of interconnection networks %J Computer %V 14 %N 12 %D December 1981 %P 12-27 %X Reproduced in the 1984 tutorial: "Interconnection Networks for parallel and distributed processing" by Wu and Feng. %A Chuan-lin Wu %A Tse-yun Feng %T Routing Techniques for a Class of Multistages Interconnection Networks %J Proceedings of the 1978 International Conference on Parallel Processing %I IEEE %D August 1978 %P 197-205 %K Indirect binary n-cube network, simplified data manipulator network, flip network, omega network, regular SW banyan network, reverse baseline network, baseline network %O Interconnection Technology %X Attempts to the the equivalence of the following interconnection switching structures: indirect binary n-cube network, simplified data manipulator network, flip network, omega network, regular SW banyan network S=F=2, reverse baseline network, baseline network. %T On the Number of Permutations Performable by the Augmented Data Manipulator Network %A George B. Adams, III %A Howard Jay Siegel %J IEEE Transactions on Computers %V C-31 %N 4 %D April 1982 %P 270-277 %K Augmented Data Manipulator (ADM) network, Generalized Cube network, parallel processing, PASM, permutation network, SIMD machines %O Interconnection networks %A George B. Adams, III %A Howard Jay Siegel %T The Extra Stage Cube: A Faault-Tolerant Interconnection Network for Supersystems %J IEEE Transactions on Computers %V C-31 %N 5 %D May 1982 %P 443-454 %K Distributed processing, Extra Stage Cube, fault tolerance, Generalized Cube, indirect binary n-cube, interconnection network, omega, parallel processing, PASM, PUMPS, shuffle-exchange, supersystems %O Special issue on supersystems %X Reproduced in the 1984 tutorial: "Interconnection Networks for parallel and distributed processing" by Wu and Feng. %A Howard Jay Siegel %A Robert J. McMillen %A P. T. Mueller, Jr. %T A survey of interconnection methods for reconfigurable parallel processing systems %J AFIPS Proc. of the NCC %V 48 %D 1979 %P 529-542 %K Purdue U, recommended %A Howard Jay Siegel %T A Model for SIMD Machines and a Comparison of Various Interconnection Networks %J IEEE Transactions on Computers %V C-28 %N 12 %D December 1979 %P 907-917 %K Algorithm correctness,array processors, computer architecture, ILLIAC IV, interconnection networks, n-cube array, parallel processing, perfect shuffle, permutation networks, SIMD machines, STARAN %A Howard Jay Siegel %A Robert J. McMillen %T The multistage cube: a versatile interconnection network %J Computer %V 14 %N 12 %D Dec. 1981 %P 12-27 %A Bart Locanthi %T The Homogeneous Machine %R 3759:TR:80, Ph.D. thesis %I Caltech %C Pasadena, CA 91125 %D 1980 _____________________________ Note: portions of this have been removed due to Copyright restrictions. --eugene miya NASA Ames Research Center {hplabs,ihnp4,dual,hao,decwrl,allegra}!ames!aurora!eugene emiya@ames-vmsb.ARPA
wdr@faron.UUCP (William D. Ricker) (04/23/85)
In article <617@ahuta.UUCP> in net.arch, rkl@ahuta.UUCP (R. Kevin Laux) answered the question of what is a hypercube, which is relevant to certain exoctic SIMD multiproccessor architectures: > The hypercube is a 4 dimensional construct, also known as a tesseract. >Unfolded into 3D space it looks like a stack of 4 cubes and has another 4 >cubes attached to the 4 sides of the second cube from the bottom (or top, >whichever). ... Well, mostly true. The tesseract is the 4-cube, or hyper-cube in 4 dimensions. There are hyper cubes for all n>0, which are constructed by translating a (n-1)-cube through the n-th dimension a unit distance, connecting each node with its image. The 2**64 processor architectures are 64-cubes, which would only /look cubish/ if you looked at them in a 64-dimensional space. A 64 cube is built by translating a 63-cubes through the 64th dimension. ... {Recurse deeply} ... The 1-cube is two 0-cubes (points) connected by a unit-line in 1-space. The more familiar family members: The 2-cube, which we call a square, is two 1-cubes connected, forming four 1-cube faces. The 3-cube is two 2-cubes connected by four 1-cubes, to form six 2-cube faces. The 4-cube, a tesseract, is formed by connecting two 3-cubes node-to- corresponding node, which then has eight 3-cube hyper-faces in the 4-space in which it is embedded. A 5-cube can be similarly constructed /et/ tedius /cetera/, /ad infinitum/. Other Topological Trivia: The 0-cube is also the 0-ball. A 1-ball is the set of points in a one-dimensional space within a given radius of a certain point: a closed line segment. The 1-cube = 1-ball. The 0-sphere is the boundary of the 1-ball, two points or 0-balls!. The 2-ball is the disk, all points in 2-space within a radius. Its boundary is the 1-sphere, a circle, which is topologically identical to two lines, 1-balls, joined at their boundaries. The 3-ball is what we call a ball or spherical solid, all 3-space within a radious. Its boundary is called the 2-sphere, which is topologically equivalent to two 2-balls joined at their 1-spheres. There is likewise in 4-space a 4-ball whose 3-sphere surface is two 3-balls joined surface to surface. {Follow-up the topology to net.math. This is last bit is a bit far afield from computer architecture. Although Weiner did set up standing waves in an anulus of turtle muscle.} -- William Ricker wdr@faron.UUCP (UUCP) decvax!genrad!linus!faron!wdr (UUCP) {allegra,ihnp4,utzoo,philabs,uw-beaver}!linus!faron!wdr (UUCP) Opinions are my own and not necessarily anyone elses. Likewise the "facts".