Header menu link for other important links
X
Exact wirelength of hypercubes on a grid
P. Manuel, , B. Rajan, H. Mercy
Published in
2009
Volume: 157
   
Issue: 7
Pages: 1486 - 1495
Abstract
Grid embeddings are used not only to study the simulation capabilities of a parallel architecture but also to design its VLSI layout. In addition to dilation and congestion, wirelength is an important measure of an embedding. There are very few papers in the literature which provide the exact wirelength of grid embedding. As far as the most versatile architecture hypercube is concerned, only approximate estimates of the wirelength of grid embedding are available. In this paper, we give an exact formula of minimum wirelength of hypercube layout into grids and thereby we solve completely the wirelength problem of hypercubes into grids. We introduce a new technique to estimate the wirelength of a grid embedding. This new technique is based on a Congestion Lemma and a Partition Lemma which we study in this paper. © 2008 Elsevier B.V. All rights reserved.
About the journal
JournalDiscrete Applied Mathematics
ISSN0166218X