The Kyklos Multicomputer Network: Interconnection Strategies Topological Properties Applications.

Abstract

KYKLOS, a new multiple tree-based interconnection network for multi/parallel processing systems, is proposed. This architecture provides fault tolerance and asymptotic improvements in performance while retaining the simplicity and low fanout of the binary tree unlike other augmented tree architectures proposed in the literature. Different topological variations of KYKLOS are presented. In particular, the interconnection for a dual tree KYKLOS involves a shuffle of the links in one of the two trees. Simple distributed routing strategies are defined for KYKLOS and it is shown that the cross product: { Topology x Routing Strategy } maps to different distance and traffic characteristics. Maximum link traffic grows subquadratically with network size (O(N^1.5)), while the cost of the network increases only linearly with the number of processor resources. Also, normalized communication latencies are shown to be superior to competing tree topologies and to the Hypercube. Applications of this network topology to facilitate parallel access to I/O and parallel processing of relational join operations is explored. Finally, it is shown that KYKLOS has excellent potential in minimizing network diameter under the constraints of maximum node degree for a given network size.