Speaker: Dorothy Kucar, E&CE Department, University of Waterloo 
Time:    Wednesday, March 27, 1:30 p.m.
Place:   room: HP4369, SITE: Carleton University
Title:   Combinatorial Methods in VLSI Physical Design 

Abstract:

Very Large Scale Integrated design is concerned with the 
design and implementation of integrated circuits. The trend 
today is to put more functionality onto individual
chips, which translates to increasing numbers of smaller 
connected components. In practical terms, a modern chip  
consists of components connected by several kilometers of 
wire on an area the size of a quarter. At this scale of 
integration, physical phenomena such as signal delay, 
crosstalk and power dissipation are dominated by wire length 
and component placement. Physical design is concerned with 
optimizing the placement of components and the course of 
wires to minimize these phenomena.

The process is generally broken up into logic partitioning-
where it is determined which components should be physically 
placed in proximity to one another, component placement-where 
components are assigned to a physical grid and finally routing, 
where components are connected via a sequence of horizontal and 
vertical wire segments. These problems can be modelled as a 
sequence of discrete optimization problems. The task of solving 
them is rendered difficult owing to their inherent NP-hardness 
and is further complicated by the fact that there are millions 
of variables and constraints. In practice, approximation 
algorithms with complexities O(n log n) or better are sought. 

In this talk, I will describe some mathematical models and 
solution methodologies used by industry to tackle the problems 
of logic partitioning and placement.