Electrical & Computer Engineering     |     Carnegie Mellon

Tuesday, December 12, 12:00-1:00 p.m. HH-1112


Brian Taylor
Carnegie Mellon University

Exact Combinatorial Optimization Methods for Physical Design of Regular Logic Bricks

As minimum feature sizes continue to scale down, increasing difficulties with subwavelength lithography have spurred research into more regular layout styles, such as Restrictive
Design Rules (RDRs) and regular logic fabrics. In this talk I will show that the simplicity and discreteness of regular fabrics give rise to powerful exact combinatorial optimization methods for the brick layout problem (the regular fabric equivalent of the cell layout problem). These methods are either inapplicable or intractable for less regular layout styles, such as the DRC-based approach of standard cell layout.

Brick layout generation is done in two steps - transistor placement followed by routing - and in each step, the regularity of the logic fabric is leveraged by the layout algorithm. In the transistor placement step, the 'single-row' diffusion style lends itself to highly effective routability metrics, and to an efficient branch and bound algorithm that is optimal with respect to area and strongly Pareto optimal with respect to the routability metrics. Similarly, the discreteness of the coarse routing grid makes feasible a formulation of the brick routing step as a decision problem in the class NP. In turn, this formulation leads to a routing methodology based on Boolean Satisfiability (SAT) which can make strong guarantees of completeness and optimality that virtually no other routing method can make.

The ideas discussed in this talk have been implemented in a prototype tool. Promising results from this tool will be presented, and applications of related techniques to other problems in VLSI design will be discussed.


Brian Taylor is a third-year Ph.D. student in Electrical and Computer Engineering at Carnegie Mellon University, where he works with the Regular Fabrics group under Prof. Larry Pileggi. His current research focus is on the application of modern optimization techniques to problems in VLSI design, particularly synthesis-related problems in the second and higher levels of the polynomial hierarchy. He was awarded an AMD/SRC Graduate Fellowship in 2005.