Tech Report CS-90-12

VLSI Placement Using Uncertain Costs

Cheryl L. Harkness and Daniel P. Lopresti

May 1990


Many objective functions used to evaluate placement quality contain uncertain parameters. While these values (e.g., channel width, cell area, wire length, and circuit delay) can be estimated, they cannot be precisely known until the layout is finished or sometimes until the chip is fabricated. As a result, current automatic placement algorithms must use `expected' values in their objective functions providing one possible estimate of placement nquality. An algorithm that uses the full range of potential values when computing placement cost can yield a more credible prediction of placement quality and reveal more about the structure of optimal configurations. In this paper, we propose an interval-based approach to modeling uncertainty in automatic placement algorithms. We illustrate our methodology by implementing an interval branch-and-bound placement algorithm. Using this example, we demonstrate how interval operators can be used to compute bounds on placement cost and to determine minimum-cost configurations. We also test the performance of our algorithm and analyze the results.

(complete text in pdf)