Embedding star networks into hypercubes

The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1996-02, Vol.45 (2), p.186-194
Main Authors: Bettayeb, S., Bin Cong, Girou, M., Sudborough, I.H.
Format: Article
Language:English
Subjects:
Applied sciences
Computer networks
Computer science
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Concurrent computing
Exact sciences and technology
Genetic mutations
Hypercubes
Multiprocessor interconnection networks
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n).
ISSN:0018-9340
1557-9956
DOI:10.1109/12.485371