A Clustering Utility-Based Approach for ASIC Design
By Matt Thompson, MASc, June 2000
Abstract:
This research presents two new approaches for dealing with the high
complexity of ASIC design. A novel utility-based search technique is
applied to iterative improvement in the standard-cell placement
problem. Utility theory is used to guide a deterministic (greedy)
search heuristic in finding a local minimum quickly by ranking moves
based on an estimate of their proximity to an optimal location. Moves
are then chosen that are statistically more likely to improve than if
the moves were chosen randomly, greatly increasing the rate of
convergence. Then a new hierarchal clustering heuristic is presented
which clusters a standard-cell circuit by greedily collapsing net
hyperedges by size, but not permitting very large clusters from
forming. The clustering heuristic demonstrates excellent
characteristics for reducing the execution time of standard-cell
placement while achieving better results compared to non-clustered
circuit placement and placement using other edge-based clustering
