Title

Timing driven placement through net length constraints

Date of Award

2005

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

C. Y. Roger Chen

Keywords

Net length constraints, Recursive bisection placement, VLSI

Subject Categories

Electrical and Computer Engineering | Engineering

Abstract

This thesis presents a comprehensive approach to the VLSI CAD placement problem and proposes several new techniques for timing driven placement. It implements a global placement algorithm that optimizes cell locations to meet net length constraints. A Net Length Constraint ( NLC ) is an upper bound on the half perimeter bounding box of the pins of a net. This NLC placement technique is implemented within the popular Recursive Bisection Placement ( REP ) algorithm. The proposed method utilizes linear programming at each level of the recursive bisection to reduce net constraint violations. Moreover, this method can be easily incorporated with existing RBP methods. In order to study the effectiveness of the NLC approach, several net constraint sets are generated for MCNC and Intel Corporation benchmark designs. These sets constrain a subset of nets in each design. In experiments with these designs and constraint sets, the NLC global placer, on an average, is able to keep net lengths within 1% of their constraint. Total wirelength increases less than 2%, on an average, compared to the same placer without NLC optimization.

Whereas many previous works have focused only on the global placement aspect, this thesis will also develop new detailed placers. Two new detailed placement algorithms that optimize cell placement for net constraints are proposed. These detailed placement algorithms work in conjunction with the global placer to create a design rule correct result. The first detailed placement algorithm uses a grid assignment paradigm and numerical programming. In addition to incorporating net constraints into detailed placement for the first time in published research, this detailed placement algorithm also introduces new techniques for handling the cell recombination problem [1]. The second detailed placer uses simulated annealing to optimize NLC s while generating and maintaining a design rule correct placement. In experiments using MCNC and Intel Corporation designs and constraint sets, the grid assignment and simulated annealing placers produce legalized placements where, on an average, net lengths are within 2.76% and 1.96% of their constraints, respectively.

Finally, this thesis presents a net constraint based timing driven placer. A method is presented that computes NLC s on nets in critical paths. The proposed timing driven placer with net constraints is compared against previous timing driven work on the MCNC benchmark circuits. The new method significantly improves timing results, reducing worst path delay, on an average, by 22%. Its effectiveness is also measured on Intel Corporation circuits compared to a Force-directed timing driven placement algorithm [2]. On an average, our net constraint placer improves worst path delay by 3.8% over the Force-directed placer's solution. We conclude by suggesting several ideas for continued improvements in timing driven timing algorithms.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=1947083901&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS