Macro-star networks: efficient low-degree alternatives to star graphs for large-scale parallel architectures

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 a node degree that is considerably smaller than that of a star graph of the same size, and diameter that is 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. In particular we obtain asymptotically optimal algorithms to execute the multinode broadcast and total exchange communication tasks in a macro-star network, under both the single-port and the all-port communication models.