On the area of hypercube layouts.

DOI10.1016/S0020-0190(02)00218-1MaRDI QIDQ1853103zbMATH OpenFDO

Authors Lee Guan, Ronald I. Greenberg

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(02)00218-1

zbMATH Keywords

Channel routingHypercubeInterconnection networksMincut linear arrangementOptimal linear arrangementVLSI layout areaWire density

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Review text

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 \(N^{2}\) nodes in the plane, in an \(N\times N\) grid arrangement, uses \(\lfloor2N/3\rfloor+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).

Recommendations

• scientific article; zbMATH DE number 2119684
• Graph Drawing
• Linear layouts of generalized hypercubes
• On embedding rectangular grids in hypercubes
• LINEAR LAYOUT OF GENERALIZED HYPERCUBES
• On the area of square lattice polygons.
• Covering a unit hypercube with hypercubes.
• On a covering problem in the hypercube
• On a covering problem in the hypercube
• On area-universal quadrangulations

Cites work

• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• The congestion of \(n\)-cube layout on a rectangular grid

Cited in

(8)

• Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
• Layout of the cube-connected cycles without long wires
• VLSI layouts of complete graphs and star graphs
• Nearly optimal three dimensional layout of hypercube networks
• scientific article; zbMATH DE number 2119684 (Why is no real title available?)
• LINEAR LAYOUT OF GENERALIZED HYPERCUBES
• Graph Drawing
• Linear layouts of generalized hypercubes

This page was built for publication: On the area of hypercube layouts.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853103)