About message routing in different hypercube interconnection network types

Abstract

The paper treats the problem of message routing in different hypercube interconnection network types. Because the communication algorithms frequently use a few basic communication operations, the purpose was to optain relationships for the total communication time at the implementation of these basic operations in different hypercube interconnection types. The basic communication operations considered were: simple message transfer between two processors, one to all broadcast, all to all broadcast, one to all personalized communication, and all to all personalized communication. For establishing the desired relationships, the starting point were the relationships for the total communication time for the above mentioned operations implemented on three basic interconnection networks: classical hypercube, ring and mesh. The different hypercube interconnection network types considered were: the cube connected cycles network, the extended hypercube, the hypernet network, the k array n hypercube and the composed hypercube. The obtained relationships are useful to establish the performances of the considered networks, from the total communication time point of view, making comparisons between them and between them and the classical hypercube interconnection network with the same number of nodes. The most advantageous interconnection network from the above mentioned point of view, is the composed hypercube with the dynamic position of the nodes.