An algorithm for the optimal placement and routing of a circuit within a ring of pads
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 360-370
- https://doi.org/10.1109/sfcs.1983.6
Abstract
As the final stage in laying out a chip, the logic of the integrated circuit is assembled into one (not necessarily rectangular) module which must then be connected to pads lying along a rectangular frame. A placement for the module must be determined to assure the feasibility of the (river) routing from the logic inside to the pads on the periphery. We first show how to solve the routing problem in a stationary context: given the placement, can the signals be wired in the given doughnut-shaped area? Then we use the routability analysis developed in the first part to find a placement of the circuit that yields a feasible routing (if one exists). Both algorithms run in time that is quadratic in the size of the input, and there exist cases for which this bound cannot be improved upon.Keywords
This publication has 7 references indexed in Scilit:
- Optimal Placement for River RoutingSIAM Journal on Computing, 1983
- River Routing: Methodology and AnalysisPublished by Springer Nature ,1983
- On Routing Two-Point Nets Across a ChannelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- An optimal solution to a wire-routing problemJournal of Computer and System Sciences, 1981
- The Separation for General Single-Layer Wiring BarriersPublished by Springer Nature ,1981
- Optimal wiring between rectanglesPublished by Association for Computing Machinery (ACM) ,1981
- A polynomial time algorithm for optimal routing around a rectanglePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980