Publication Details
Title: Multiple Network Embeddings into Hypercubes
Author: A. Gupta and S. E. Hambrusch
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-20.pdf
Overview:
In this paper we study the problem of how to efficiently embed r interconnection networks G(subscript 0),...G(subscript r-1), r is less than or equal to k, into a k-dimensional hypercube H so that every node of the hypercube is assigned at most r nodes all of which belong to different G(subscript i)s. When each G(subscript i) is a complete binary tree or a leap tree of 2(superscript k)-1 nodes, we describe an embedding achieving a dilation of 2 and a load of 5 and 6, respectively. For the cases when each G(subscript i) is a linear array of a 2-dimensional mesh of 2(superscript k) nodes, we describe embeddings that achieve a dilation of 1 and an optimal load of 2 and 4, respectively. Using these embeddings, we also show that r(subscript 1) complete binary trees, r(subscript 2) leap trees, r(subscript 3) linear arrays, and r(subscript 4) meshes can simultaneously be embedded into H with constant dilation and load, (4 over sum over i=1) (r(subscript i)) is less than or equal to k.
Bibliographic Information:
ICSI Technical Report TR-89-020
Bibliographic Reference:
A. Gupta and S. E. Hambrusch. Multiple Network Embeddings into Hypercubes. ICSI Technical Report TR-89-020, April 1989
Author: A. Gupta and S. E. Hambrusch
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-20.pdf
Overview:
In this paper we study the problem of how to efficiently embed r interconnection networks G(subscript 0),...G(subscript r-1), r is less than or equal to k, into a k-dimensional hypercube H so that every node of the hypercube is assigned at most r nodes all of which belong to different G(subscript i)s. When each G(subscript i) is a complete binary tree or a leap tree of 2(superscript k)-1 nodes, we describe an embedding achieving a dilation of 2 and a load of 5 and 6, respectively. For the cases when each G(subscript i) is a linear array of a 2-dimensional mesh of 2(superscript k) nodes, we describe embeddings that achieve a dilation of 1 and an optimal load of 2 and 4, respectively. Using these embeddings, we also show that r(subscript 1) complete binary trees, r(subscript 2) leap trees, r(subscript 3) linear arrays, and r(subscript 4) meshes can simultaneously be embedded into H with constant dilation and load, (4 over sum over i=1) (r(subscript i)) is less than or equal to k.
Bibliographic Information:
ICSI Technical Report TR-89-020
Bibliographic Reference:
A. Gupta and S. E. Hambrusch. Multiple Network Embeddings into Hypercubes. ICSI Technical Report TR-89-020, April 1989