A hypercube (http://en.wikipedia.org/wiki/Hypercube) also gets you exponential space; the max hops is the dimension (3 for a 3-dimensional cube) and the number of nodes is exp(base 2) of the dimension (8 vertices on a cube). To do a tesseract (4-cube), which looks like two cubes nested, you'd need 4 ports per node, 16 nodes, 32 cables, max hop 4. I've poked around and don't see a great 4 ports per node solution; I like the suggestion of putting a router on a motherboard.
But you've made me curious about this Kautz and de Bruijn graphs, I'll go look, thanks. Peter On 5/22/07, Larry Stewart <[EMAIL PROTECTED]> wrote:
Robert G. Brown wrote: > On Tue, 22 May 2007, Larry Stewart wrote: > >> What would the advantages of a diamond lattice be? In terms of >> bisection and diameter? >> Ease of wiring? > > > Four ports per system, probably, in a 3d lattice. 3d is good because > the volume (number of hosts) scales like the maximum number of hops > between hosts cubed. Ah. I see that. I looked at the diamond lattice picture in http://phycomp.technion.ac.il/~nika/diamond_structure.html and it did make my head twinge. With Kautz or deBruijn graphs, you get an exponential number of nodes, for node degree k >= 2, and diameter (hopcount D) you get O(k**D) nodes. However, you don't get any obvious mapping of 2D or 3D problems to the graph. You could do this with two NICs per node, if you can send the transmit data and the receive data to different places. Of course even on BlueGene/L they use simulated annealing to map the problem to the machine, because the obvious mapping is often not the best one. See "Optimizing Task Layout on the BlueGene/L Supercomputer" in IBM JSRD March 2005. -Larry _______________________________________________ Beowulf mailing list, Beowulf@beowulf.org To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf
_______________________________________________ Beowulf mailing list, Beowulf@beowulf.org To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf
