Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes

Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2021-04, Vol.77 (4), p.4135-4150
Main Authors: Sundara Rajan, R., Kalinowski, Thomas, Klavžar, Sandi, Mokhtar, Hamid, Rajalaxmi, T. M.
Format: Article
Language:English
Subjects:
Algorithms
Cartesian coordinates
Compilers
Computer Science
Congestion
Dilation
Embedding
Fault tolerance
Graphs
Hypercubes
Interpreters
Lower bounds
Parallel processing
Processor Architectures
Programming Languages
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:Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-020-03420-w