Fine granularity clustering for large scale placement problems

摘要

In this paper we present a linear-time Fine Granularity Clustering (FGC) algorithm to reduce the size of large scale placement problems. FGC absorbs as many nets as possible into Fine Clusters. The absorbed nets are expected to be short in any good placement; therefore the clustering process does not affect the quality of results. We compare FGC with a connectivity-based clustering algorithm proposed in [1] and simulated-annealing-based algorithm in TimberWolf [2], both of which also reduce the number of external nets between clusters. The experimental results show that our algorithm achieves better net absorption than the previous approaches while using much less CPU time for large scale problems. With our FGC algorithm, we propose a Fast Placer Implementation (FPI) framework, which combines our FGC-based size reduction with traditional placement techniques to handle large-scale placement problems. We compared FPI placement results with a public-domain fast standard cell placer Capo[4] on large scale benchmarks. The results show that FPI can reduce CPU time for large scale placement by a factor of 3~5x while obtaining placement results of comparable or better quality.