Collective Communication in Recursive Dual-Net: An Interconnection Network for High-Performance Parallel Computer Systems of the Next Generation

In this paper, we propose efficient routing algorithms for collective communication in a newly proposed, versatile network, called a recursive dual-net (RDN). The RDN can be used as a candidate for the interconnection of supercomputers of the next generation. The RDN is generated by recursively applying dual-construction on a base network. Given a regular and symmetric graph of size n and node-degree d, the dual-construction generates a regular and symmetric graph of size 2n² and node-degree d+1. The RDN has many interesting properties including small node-degree and short diameter. Our results show that collective communication can be done efficiently in RDN.