Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes
- PDF / 1,478,906 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 175 Views
Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes R. Sundara Rajan1 · Thomas Kalinowski2 · Sandi Klavžar3,4,5 · Hamid Mokhtar6 · T. M. Rajalaxmi7
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keywords Embedding · Dilation · Wirelength · Edge congestion · Bisection width · Hypercube · Complete multipartite graph · Folded hypercube · Wheel · Cartesian product of graphs Mathematics Subject Classification 05C10 · 68R10
1 Introduction A suitable interconnection network is an important part for the design of a multicomputer or multiprocessor system. Such a network is usually modeled by a symmetric graph, where the nodes represent the processing elements and the edges represent the communication channels. Desirable properties of an interconnection network include symmetry, embedding capabilities, relatively small degree, small diameter, scalability, robustness, and efficient routing [42]. One of the most efficient interconnection networks is the hypercube due to its structural regularity, * R. Sundara Rajan [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
R. Sundara Rajan et al.
potential for parallel computation of various algorithms, and the high degree of fault tolerance [43]. The hypercube has many excellent features and thus becomes the first choice of topological structure of parallel processing and computing systems. The machines based on hypercubes such as the Cosmic Cube from Caltech, the iPSC/2 from Intel, and Connection Machines have been implemented commercially [11]. Hypercubes are very popular models for parallel computation because of their symmetry and relatively small number of interprocessor connections. Among the hypercube-based interconnection networks designed for extremely large-scale supercomputers that were studied in the last decade, we mention metacubes [29], hierarchical cubic networks [6, 31], and k-ary n-cubes [16, 51]. The hypercube embedding problem is the problem of mapping a communication graph into a hypercube multicomputer. Hypercubes are known to simulate other structures such as grids and binary trees [9, 33]. Graph embedding is an impor
Data Loading...
