Efficient embeddings into the hypercube using matrix transformations

Mounir Hamdi, S. W. Song

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods, based on matrix transformations, for efficiently embedding different networks into the hypercube (binary n-cube). First, we use this method to embed r-ary m-cubes into a binary n-cube of the same size with dilation 1. While our method has the same dilation as traditional methods using reflected Gray code, it has the additional property of making the layout of the binary n-cube more suitable for divide-and-conquer algorithms. Second, we use our matrix transformation method to optimally embed hierarchical interconnection networks into the binary n-cube which we would not achieve using reflected Gray code embedding. Thus, this embedding method has significant practical importance in enhancing the capabilities of the hypercube.

Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Supercomputing, ICS 1995
PublisherAssociation for Computing Machinery
Pages280-288
Number of pages9
ISBN (Electronic)0897917286
DOIs
Publication statusPublished - 3 Jul 1995
Externally publishedYes
Event9th International Conference on Supercomputing, ICS 1995 - Barcelona, Spain
Duration: 3 Jul 19957 Jul 1995

Publication series

NameProceedings of the International Conference on Supercomputing
VolumePart F129361

Conference

Conference9th International Conference on Supercomputing, ICS 1995
Country/TerritorySpain
CityBarcelona
Period3/07/957/07/95

Keywords

  • Dilation
  • Embedding
  • Hierarchical networks
  • Hypercube
  • R-ary m-cube

Fingerprint

Dive into the research topics of 'Efficient embeddings into the hypercube using matrix transformations'. Together they form a unique fingerprint.

Cite this