On the area of hypercube layouts |
| |
Authors: | Ronald I Greenberg Lee Guan |
| |
Affiliation: | a Department of Mathematical and Computer Sciences, Loyola University, 6525 N. Sheridan Rd., Chicago, IL 60626-5385, USA b Acecomm Corporation, 704 Quince Orchard Rd., Gaithersburg, MD 20878, USA |
| |
Abstract: | This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N2 nodes in the plane, in an N×N grid arrangement, uses ⌊2N/3⌋+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection). |
| |
Keywords: | Interconnection networks Hypercube Wire density VLSI layout area Mincut linear arrangement Optimal linear arrangement Channel routing |
本文献已被 ScienceDirect 等数据库收录! |
|