TY - GEN
T1 - Optimal wiring between rectangles
AU - Dolev, Danny
AU - Karplus, Kevin
AU - Siegel, Alan
AU - Strong, Alex
AU - Ullman, Jeffrey D.
N1 - Funding Information:
One useful structure to place on VLSI circuits is a hierarchy of rectangles, where two or more are wired together to form a larger rectangle, which is the smallest rectangle ttmt circumscribes them. \[J\]i s an example of such an approach. In order to make the circumscribing rectangle as small as possible, we must wire together ports, which are points on the borders of the: rectangles, in some designated order, which we shall generally assume is tim same for both rectangles; that ;s, no crossovers are mandated. We shall assume, as seems sen-Work supported by a Chaim Weizmann postdoctoral fellowship and DARPA contract MDA903-80-C-0t02. Supported by a fellowship from the Hert~ Foundation. tt Work partially supported by DARPA contract MDA903--80-C-0102 and NSF grant MCS-79-04528.
Publisher Copyright:
© 1981 ACM.
PY - 1981/5/11
Y1 - 1981/5/11
N2 - We consider the problem of wiring together two parallel rows of points under a variety of conditions. The options'include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. In almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. We also compare two fundamentally different wiring approaches, where one and two layers are used. We show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out VLSI circuits there is no substantial advantage to the two-layer approach over the one-layer approach.
AB - We consider the problem of wiring together two parallel rows of points under a variety of conditions. The options'include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. In almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. We also compare two fundamentally different wiring approaches, where one and two layers are used. We show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out VLSI circuits there is no substantial advantage to the two-layer approach over the one-layer approach.
UR - http://www.scopus.com/inward/record.url?scp=85023387204&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85023387204&partnerID=8YFLogxK
U2 - 10.1145/800076.802484
DO - 10.1145/800076.802484
M3 - Conference contribution
AN - SCOPUS:85023387204
SN - 0897910419
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 312
EP - 317
BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PB - Association for Computing Machinery
T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981
Y2 - 11 June 1981 through 13 June 1981
ER -