MACRO-STAR NETWORKS - EFFICIENT LOW-DEGREE ALTERNATIVES TO STAR GRAPHS

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node d egree that is considerably smaller than that of a star graph of the sa me size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree) . We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown . This enables us to obtain through emulation a variety of efficient a lgorithms for the macro-star network, thus proving its versatility. Ba sic communication tasks, such as the multinode broadcast and the total exchange, can be executed in macro-star networks in asymptotically op timal time under both the single-port and the all-port communication m odels. Moreover, no interconnection network with similar node degree c an perform these communication tasks in time that is better by more th an a constant factor than that required in a macro-star network. We sh ow that macro-star networks can embed trees, meshes, hypercubes, as we ll as star, bubble-sort, and complete transposition graphs with consta nt dilation. We introduce several variants of the macro-star network t hat provide more flexibility in scaling up the number of nodes. We als o discuss implementation issues and compare the new topology with the star graph and other popular topologies.