Embedding hierarchical networks into the hypercube

The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods for the embedding of hierarchical interconnection networks in the hypercube to minimize the dilation and the expansion costs, and mathematically proves their optimality. To the best of our knowledge, this is the first result on embedding hierarchical networks into the hypercube. Thus, this embedding has significant practical importance in enhancing the capabilities of the hypercube since hierarchically constructed networks have proven to be very cost-effective in a wide range of applications, and are considered as the future generation topologies for massively parallel computer systems.