Integration of Physical Design and Sequential Optimization

Philip Chong

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-21
March 6, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-21.pdf

This work examines the interaction between the physical design of digital integrated circuits and sequential optimization techniques used for performance enhancement. In particular, the integration of floorplanning and placement with retiming and clock skew scheduling is explored. A theoretical result is given which addresses the computational complexity of circuit partitioning under constraints derived from sequential optimization; this motivates the need for heuristic approaches to the related placement problem. Another theoretical result provides a characterization of the feasible retimings of a sequential circuit; this result is used to motivate an effective method for floorplanning integrated with sequential optimization. Practical techniques for using sequential slack to drive standard-cell placement are shown here; experiments demonstrate significant improvement in final design performance using these methods. Another part of this work examines how the role of sequential optimization and physical design changes when the design allows for asynchronous or latency-insensitive communication between modules. A theoretical result relating to the problem of clock tree implementation for clock skew scheduling under process variation is given. Finally an experimental technique for floorplanning using nonlinear programming is demonstrated.

Advisor: Robert K. Brayton


BibTeX citation:

@phdthesis{Chong:EECS-2006-21,
    Author = {Chong, Philip},
    Title = {Integration of Physical Design and Sequential Optimization},
    School = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-21.html},
    Number = {UCB/EECS-2006-21},
    Abstract = {This work examines the interaction between the physical design of digital integrated circuits and sequential optimization techniques used for performance enhancement. In particular, the integration of floorplanning and placement with retiming and clock skew scheduling is explored. A theoretical result is given which addresses the computational complexity of circuit partitioning under constraints derived from sequential optimization; this motivates the need for heuristic approaches to the related placement problem.  Another theoretical result provides a characterization of the feasible retimings of a sequential circuit;  this result is used to motivate an effective method for floorplanning integrated with sequential optimization.  Practical techniques for using sequential slack to drive standard-cell placement are shown here; experiments demonstrate significant improvement in final design performance using these methods. Another part of this work examines how the role of sequential optimization and physical design changes when the design allows for asynchronous or latency-insensitive communication between modules. A theoretical result relating to the problem of clock tree implementation for clock skew scheduling under process variation is given. Finally an experimental technique for floorplanning using nonlinear programming is demonstrated.}
}

EndNote citation:

%0 Thesis
%A Chong, Philip
%T Integration of Physical Design and Sequential Optimization
%I EECS Department, University of California, Berkeley
%D 2006
%8 March 6
%@ UCB/EECS-2006-21
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-21.html
%F Chong:EECS-2006-21