<div>A hypercube (<a href="http://en.wikipedia.org/wiki/Hypercube">http://en.wikipedia.org/wiki/Hypercube</a>) 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.
</div>
<div> </div>
<div>But you've made me curious about this Kautz and de Bruijn graphs, I'll go look, thanks.</div>
<div>Peter<br><br> </div>
<div><span class="gmail_quote">On 5/22/07, <b class="gmail_sendername">Larry Stewart</b> <<a href="mailto:larry.stewart@sicortex.com">larry.stewart@sicortex.com</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Robert G. Brown wrote:<br><br>> On Tue, 22 May 2007, Larry Stewart wrote:<br>><br>>> What would the advantages of a diamond lattice be?  In terms of
<br>>> bisection and diameter?<br>>> Ease of wiring?<br>><br>><br>> Four ports per system, probably, in a 3d lattice.  3d is good because<br>> the volume (number of hosts) scales like the maximum number of hops
<br>> between hosts cubed.<br><br>Ah.  I see that.  I looked at the diamond lattice picture in<br><br><a href="http://phycomp.technion.ac.il/~nika/diamond_structure.html">http://phycomp.technion.ac.il/~nika/diamond_structure.html
</a><br><br>and it did make my head twinge.<br><br>With Kautz or deBruijn graphs, you get an exponential number of nodes,<br>for node degree<br>k >= 2, and diameter (hopcount D) you get O(k**D) nodes.  However, you<br>
don't get any<br>obvious mapping of 2D or 3D problems to the graph.   You could do this<br>with two<br>NICs per node, if you can send the transmit data and the receive data to<br>different places.<br><br>Of course even on BlueGene/L they use simulated annealing to map the
<br>problem to the<br>machine, because the obvious mapping is often not the best one.<br>See "Optimizing Task Layout on the BlueGene/L Supercomputer" in IBM JSRD<br>March 2005.<br><br>-Larry<br><br>_______________________________________________
<br>Beowulf mailing list, <a href="mailto:Beowulf@beowulf.org">Beowulf@beowulf.org</a><br>To change your subscription (digest mode or unsubscribe) visit <a href="http://www.beowulf.org/mailman/listinfo/beowulf">http://www.beowulf.org/mailman/listinfo/beowulf
</a><br></blockquote></div><br>