Recursive Diagonal Torus: An interconnection network for massively parallel computers

Recursive Diagonal Torus (RDT), a class of interconnection network is propo sed for massively parallel computers with up to 2(16) nodes. By making the best use of a recursively structured diagonal mesh (torus) connection, the RDT has a smaller diameter (e.g., it is II for 2(16) nodes) with a smaller number of links per node (i.e., 8 links per node) than those of the hypercu be. A simple routing algorithm, called vector routing, which is near-optima l and easy to implement is also proposed. Although the congestion on upper rank tori sometimes degrades the performance under the random traffic, the RDT provides much better performance than that of a 2D/3D torus in most cas es and, under hot spot traffic, the RDT provides much better performance th an that of a 2D/3D/4D torus. The RDT router chip which provides a message m ulticast for maintaining cache consistency is available. Using the 0.5 mum BICMOS SOG technology, versatile functions, including hierarchical multicas ting, combining acknowledge packets, shooting down/restart mechanism, and t ime-out/setup mechanisms, work at a 600MHz clock rate.