Combinatorial optimization techniques for VLSI placement.

摘要

Current Integrated Circuits contain billions of components. This makes the VLSI Physical Design process an extremely challenging task. The growing count of components, complex objectives and constraints has demanded strong algorithmic break throughs in this area.; Placement of modules is one of the most critical stages in VLSI Physical Design [57]; current placement algorithms need to be both fast and effective. Optimization of interconnect length is an important objective during placement as it is directly related to signal delay in current integrated circuits. In this dissertation, we present novel combinatorial optimization techniques for the interconnect length driven VLSI Placement problem.; We first present a new fast and effective global placement algorithm [7] for today's multi-million module circuits, which is based on a combination of continuous and discrete optimization techniques; specifically, it uses nonlinear optimization in conjunction with network flows. Next, we look at the placement legalization problem; two different algorithms based on dynamic programming [5] and a greedy technique [8] are proposed. Finally, a new optimization technique called enumeration sieve is proposed, which can be applied to problems of discrete nature. Algorithms and techniques presented as part of this dissertation have produced competitive published results on a variety of benchmarks.