Exact Wirelength of Hypercube Layout on $s$-Cube Necklace

Abstract

Embeddings capabilities play a vital role in evaluating interconnection networks. Wirelength is an important measure of an embedding. As far as the most versatile architecture, the hypercube, is concerned, only approximate estimates of the wirelength of various embeddings are available. This paper presents an optimal embedding of the hypercube into a new architecture called $k$-cube necklace, which minimizes wirelength. In addition, this paper gives an exact formula for the minimum wirelength of the hypercube into $k$-cube necklace and thereby we solve completely the wirelength problem of the hypercube into $k$-cube necklace.