A new clustering approach and its application to BBL placement

A new approach for clustering applied to building block placement is presented. Unlike traditional approaches, which only consider local factors such as connectivity and shape matching of blocks in a cluster, the authors´ approach (called the GAC method) not only considers connectivity and shape matching of clustering, but also takes a more important factor, global analyses, into account. Furthermore, the authors propose a new shape matching and a propagating method to compute the connectivity of clusters. The new method makes connectivity computation more precisely. This clustering algorithm has been implemented in Fortran 77 on Micro VAX II. The experimental placement results are much better than BEAR and TimberWolfMC, the latter of which adopts the simulated annealing approach, and the GAC method has a much better run time