2001/05/29 by Ronald I. Greenberg, Lee Guan
Computer Science · #cs.DC
published as condensed and revised in Information Processing Letters, v. 84, n. 1, pp. 41--46, Sep. 2002 · 8 pages, 4 figures, LaTeX
arxiv created 2001/05/29 · arxiv updated 2009/11/30
This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. The most natural, regular layout of a hypercube of N2 nodes in the plane, in a N x N grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (The number of tracks per row can be reduced by 1 with a less regular design.) 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).