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