jerry@oliveb.UUCP (Jerry Aguirre) (03/02/85)
An explaination of what we are talking about was requested so I will include it here. Other readers can skip this article. This series of articles is discussing buss verses hypercube designs. What are they? Well they are ways of connecting large numbers of processors (computers) together so that they can work together on some problem that is to big for a single computer. A buss topology connects many processors to a common communications medium (like an ethernet) and looks like this: p1 p2 p3 p4 p5 ... | | | | | | ========================================= The buss must be shared by all the processors as it can only handle 1 message at a time. Accesses to it must be arbitrated by some sort of scheduling algorithm. Simply put this means that if processor 1 (p1) needs to send a message to p3 it may have to wait until p2 is done using the bus. The hyper-cube design uses dedicated channels to connect each processor to another. It looks something like this: p1-----p2-----p3 | \ / | \ /| | \/ | \ / | | /\ | /\ | | / \ | / \ | p4-----p5-----p6 There is no need to arbitrate a channel because it is not shared. However you can see that connecting every processor to every other processor can use a lot of wires. In this example p1 is not connected to p3 and p6 because it would have been to hard to show. In a real computer it would also be hard to do. In practice only some of the connections are made and the rest are forwarded thru intermediate machines. So, if p1 wishes to communicate with p6 it sends the message to p5 with a request to forward it to p6. It turns out that there is a way of connecting the processors where 2**N processors only need N connections each. This is the Hyper-cube design. Jerry Aguirre @ Olivetti ATC {hplabs|fortune|idi|ihnp4|tolerant|allegra|tymix}!oliveb!jerry
brooks@lll-crg.ARPA (Eugene D. Brooks III) (03/06/85)
If you are going to explain what a hypercube is you should get the topology correct. This topology is very important. A hypercube is composed of { 2 sup n } processors. n is called the order of the hypercube. A hypercube of order n+1 is constructed by taking two of order n and placing them side by side connecting pairs of processors like so. order 0 p0 /* Bet you didn't that there are a lot of hypercubes out there already *? order 1 p0---p1 order 2 p0---p1 | | | | p2---p3 order 3 p0-----p1 | \ | \ | p4--|--p5 | | | | p2-----p3 | \| \| p6-----p7 By inspection of the processor numbers you can discover the master plan. The processors run from 0 to N-1 where N is some power of 2. Each processor is connected to all of the processors whose index differs in one and only bit. The position of the differing bit is the port which the two processors are connected with.