No Access

OPTIMAL SUBCUBE EMBEDDABILITY IN HYPERCUBES WITH ADDITIONAL DIMENSIONS

Department of Electrical and Computer Engineering, University of Nevada Las Vegas, 4505, Maryland Parkway, Las Vegas, Nevada 89154-4026, USA

Search for more papers by this author

and

SHAHRAM LATIFI

Department of Electrical and Computer Engineering, University of Nevada Las Vegas, 4505, Maryland Parkway, Las Vegas, Nevada 89154-4026, USA

Search for more papers by this author

https://doi.org/10.1142/S0129626410000077Cited by:1 (Source: Crossref)

Abstract

Subcube embeddability of the hypercube can be enhanced by introducing an additional dimension. A set of new dimensions, characterized by the Hamming distance between the pairs of nodes it connects, is introduced using a measure defined as the magnitude of a dimension. An enumeration of subcubes of various size is presented for a dimension parameterized by its magnitude. It is shown that the maximum number of subcubes for a Q_n can only be attained when the magnitude of dimension is n-1 or n. It is further shown that the latter two dimensions can optimally increase the number of subcubes among all possible choices.

Keywords:

References

Y. Saad and M. H. Shultz, IEEE Trans. on Computers 37, 867 (1988), DOI: 10.1109/12.2234. Crossref, Web of Science, Google Scholar
H. J. Siegel, IEEE Trans. on Computers 28, 907 (1979). Web of Science, Google Scholar
F. P. Preparata and J. Vuillemin, Communication of the ACM 24, 300 (1981), DOI: 10.1145/358645.358660. Crossref, Web of Science, Google Scholar
M. S. Chen and K. G. Shin, Embedment of Interacting Task Modules into A Hypercube Multiprocessor, Proc. Second Hypercube Conf. pp. 121–129. Google Scholar
L. Songet al., LNCS 4208, 61 (2006). Google Scholar
T. Calamoneri and A. Massini, Networks 47, 1 (2006), DOI: 10.1002/net.20089. Crossref, Web of Science, Google Scholar
R. Wuet al., Parallel and Distributed Processing Symp. 19, 4200 (2007). Google Scholar
A. Al-Dhelaan and B. Bose, A New Strategy for Processor Allocation in an N-cube Multiprocessor, Proc. on Int'l Phoenix Conf. on Comp. and Comm. pp. 114–118. Google Scholar
M. S. Chen and K. G. Shin, IEEE Trans. on Computers 36, 1396 (1987). Web of Science, Google Scholar
J. Kim, C. R. Das and W. Lin, A Processor Allocation Scheme for Hypercube Computers, Proc. Int. Conf. on Parallel Processing pp. II-231–238. Google Scholar
G. B. Adams and H. J. Siegel, IEEE Trans. On Computers 31, 443 (1982). Web of Science, Google Scholar
F. J. Meyer and D. K. Pradhan, IEEE Trans. On Computers 37, 472 (1988), DOI: 10.1109/12.2194. Crossref, Web of Science, Google Scholar
S. Latifi and A. El-Amawy, On Folded Hypercubes, Int'l Conf. on Parallel ProcessingI pp. I-180–I-187. Google Scholar
A. Ghafoor, T. R. Bashkow and I. Ghafoor, IEEE Trans. On Computers 38, 1425 (1988), DOI: 10.1109/12.35837. Crossref, Web of Science, Google Scholar
S. Latifi, IEEE Trans. on Reliability 39, 361 (1990), DOI: 10.1109/24.103019. Crossref, Web of Science, Google Scholar
J. Chen, I. A. Kanj and G. Wang, Hypercube Network Fault Tolerance: A Probabilistic Approach, Int'l Conf. on Parallel Processing pp. 65–72. Google Scholar