Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site ames.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!vax135!cornell!uw-beaver!tektronix!zehntel!dual!ames!eugene
From: eugene@ames.UUCP (Eugene Miya)
Newsgroups: net.arch
Subject: Re: Hyperhelp, please?
Message-ID: <950@ames.UUCP>
Date: Sun, 21-Apr-85 19:04:21 EST
Article-I.D.: ames.950
Posted: Sun Apr 21 19:04:21 1985
Date-Received: Wed, 24-Apr-85 03:04:38 EST
References: <545@hou2e.UUCP>
Organization: NASA-Ames Research Center, Mtn. View, CA
Lines: 204
Keywords: Hypercube references

> 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