Placement is one of the central problems in Chip Design. The problem can be stated as follows: Given a netlist, which can be abstractly looked upon as a hypergraph, where nodes represent instances, and edges as connections, the problem is to place the instances on a rectangular size chip of area larger than the sum of areas of the individual instances, such that various objective functions such as total wirelength, critical slack, routing congestion etc are minimized. This problem is NP-hard, however there are reasonable practical algorithms that solve this problem for netlists commonly occuring in VLSI. We describe limitations of these algorithms and propose new algorithms both for placement and decongesting a given placement.

DATE: September 26, 2003, Friday @ 09:40
PLACE: EA-409