On the Generation of Distinct Gray Codes for Load-Balancing in Hypercubes

The hypercube topology has always been popular for the interconnection network of massively parallel systems, even if network topologies designed for modern supercomputers combine it with other network layers to realise hierarchical interconnection networks (HIN). This is mostly due to its advantageous topological properties, such as a one single bit difference between any two adjacent nodes, which greatly facilitate algorithm design, like data routing strategies, and attaining high performances. By definition, a Gray code produces a Hamilton cycle in a hypercube, that is, a path that includes each of all vertices of the network and that ends at its starting vertex. It is thus very convenient to be able to generate such a code for efficient communication in a hypercube, such as for broadcasting. And it is even more interesting to be able to generate several, distinct such codes to achieve load-balancing. This is precisely the objective of this paper: we propose and evaluate an algorithm for the generation of distinct Gray codes. The correctness and complexity of the described algorithm are formally proved, and an empirical evaluation is conducted by means of a computer experiment.