IEEE Transactions on Circuits and Systems II Analog and Digital Signal Processing · 1992 · 65 citations · 32 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitecturePerformance-based DesignSystem-on-chip DesignIntegrated Circuit DesignInterconnect DesignLayout OptimizationRoutingRouting AlgorithmsVery-large-scale Integration LayoutConstraintsInterconnect DelayInterconnect Delay AnalysisLagrangian RelaxationPerformance ConstraintsPlacementPlacement AlgorithmsPlacement Optimization
An algorithm for obtaining a placement of large scale cell-based ICs subject to performance constraints is described. The problem is formulated as a constrained programming problem and is solved in two phases: continuous and discrete. Constraints are placed on total path delays including cell and interconnect delays, and the behavior of all the paths is captured. Mathematical techniques and heuristics based on Lagrangian relaxation are used to find an approximate solution to the constrained problem. The algorithm yields good results, as shown on a set of real examples. On the average, between 8% and 30% improvement in the interconnect delay of these examples is obtained with little or no impact on chip area after routing by modifying the placement alone.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
32
Linear and nonlinear programming.
Mathematics and Computers in Simulation · 1986 · 4.9K citations
The Traveling-Salesman Problem and Minimum Spanning Trees
Michael Held, Richard M. Karp · Operations Research · 1970 · 1.4K citations
Validation of subgradient optimization
Michael Held, Philip Wolfe, Harlan Crowder · Mathematical Programming · 1974 · 1.4K citations