cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (11/18/88)
Efficient Linear Programming Approaches
for Solving VLSI Layout Problems
by
Prof. Anthony Vannelli
of
Department of Electrical Engineering
University of Waterloo
Abstract
In this talk, we introduce linear programming (LP) models for
solving two fundamental VLSI layout problems - netlist partition-
ing and routing. First, a fast heuristic technique is developed
to obtain good approximate solutions to the netlist partitioning
problem. Moreover, we generate bounds on the optimal partition.
This feature allows a designer to assess "how far" a netlist par-
tition or routing is from optimality.
Second, a new optimization technique based on a promising interi-
or point (Karmarkar) method for solving LP problems is used to
solve a routing problem. The power of the interior point method
on certain classes of very large optimization problems can allow
us to tackle engineering design and analysis problems in a more
effective manner. We show how one can exploit the structure of
the routing problem to accelerate the solution to an optimal
routing or determine that no feasible routing exists.
DATE: Wednesday, November 23, 1988
TIME: 3:30 p.m.
PLACE: University of Waterloo, Davis Centre, Room 1302
Everyone is welcome. Refreshments served.