[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.16, No.1, pp.81-95 (January 2000)

Properties and Embeddings of Interconnection Networks
Based on the Hexcube

Jung-Sing Jwo, Show-May Chen, Chin-Yun Hsieh+ and Yu Chin Cheng+
Department of Computer and Information Sciences
Tunghai University
Taichung, Taiwan 407, R.O.C.
E-mail: jwo@mail.thu.edu.tw
+Department of Electronics Engineering
National Taipei University of Technology
Taipei, Taiwan 106, R.O.C.
E-mail: {hsieh, yccheng}@en.ntut.edu.tw

A new class of interconnection networks called the hexcube is proposed. The hexcube is similar to the base-6 generalized hypercube in structure but has a simpler interconnection scheme. The present work shows that the hexcube is vertex symmetric and possesses topological properties similar to those of the hypercube. This implies that the costs of building parallel computers using the hexcube and using the binary hypercube are similar, and are much lower than those incurred using the based-6 generalized hypercube. A one-port broadcasting algorithm for the hexcube is proposed. New results for embeddings using the hexcube as the host topology are also presented. First, a reflected Gray code-like method for finding Hamiltonian cycles is developed. Second, algorithms for all two-dimensional mesh embedding with unit expansion and a dilation of no more than two are developed. Third, it is shown that a relatively large binary hypercube can be embedded into a hexcube with a dilation of no more than three and with almost optimal expansion.

Keywords: interconnection networks, hexcube, hypercube, one-port broadcasting, Hamiltonian cycles, mesh embeddings, binary hypercube embeddings

Full Text () Retrieve PDF document (200001_05.pdf : 3,563,874 bytes)

Received March 2, 1998; revised July 9, 1998; accepted August 12, 1998.
Communicated by Jang-Ping Sheu.