Document Type
Article
Publication Date
9-2002
Publication Title
Information Processing Letters
Volume
84
Issue
1
Pages
41--46
Publisher Name
Elsevier
Abstract
This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(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).
Recommended Citation
Ronald I. Greenberg and Lee Guan. On the area of hypercube layouts. Information Processing Letters, 84(1):41--46, September 2002.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Included in
OS and Networks Commons, Theory and Algorithms Commons, VLSI and Circuits, Embedded and Hardware Systems Commons
Comments
© 2003 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.