From kragen@dnaco.net Thu Sep 24 21:30:59 1998 Date: Thu, 24 Sep 1998 21:30:53 -0400 (EDT) From: Kragen X-Sender: kragen@pike To: jakob@ostenfeld.dk cc: Beowulf Mailing List Subject: Re: Topologies ? In-Reply-To: <19980925001331.A1673@ostenfeld.dk> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Keywords: X-UID: 2134 Status: O X-Status: On Fri, 25 Sep 1998 jakob@ostenfeld.dk wrote: > I answered a question in a newsgroup, which actually made me wonder > whether I'm right or not... Then I promised to followup if I wasn't. > > The question is: > What is the name of the topology, if you have eg. five nodes connected > eache with four nics, so that every node has a connection to every other > node ? In graph theory, this topology is known as the complete graph of five nodes. In religious studies, this toplogy is known as the pentagram. I don't know what it's called in parallel processing. > By the way, my answer was ``hypercube''. Wonder how far that was off... A hypercube of four nodes would be a square, and would have the four connected as follows: 0: 1 2 1: 0 3 2: 0 3 3: 1 2 Strictly speaking, a hypercube contains nodes numbered 0 through N-1, where N is a power of two, and all nodes are connected to all other nodes whose nodenumbers differ from theirs by exactly one bit. So in a 128-node hypercube, node 53 (0110101 binary) is connected to node 52 (0110100 binary), node 55 (0110111 binary), node 49 (0110001 binary), node 61 (0111101 binary), node 37 (0100101 binary), node 21 (0010101), and node 117 (1110101). Hypercubes are nice because: - it's easy to compute paths between nodes; - the connections to any individual node grow as the base-2 log of the number of nodes, keeping the number of connections reasonable for any reasonable number of nodes; - it's easy to broadcast to all nodes; - as the number of parts grows, the amount of redundancy grows; - they're mathematically elegant. I suspect that dedicated switches are probably better at forwarding messages between large numbers of nodes than nodes also acting as routers. IBM's SP2 switch is unbelievably fast, something like three orders of magnitude less latency than IP packet forwarding. One of the early Beowulfs (at Los Alamos?) was a sixteen-node hypercube. Kragen -- Kragen Sitaker The sages do not believe that making no mistakes is a blessing. They believe, rather, that the great virtue of man lies in his ability to correct his mistakes and continually make a new man of himself. -- Wang Yang-Ming