A New Length-Based Algebraic Multigrid Clustering Algorithm

Abstract

Clustering algorithms have been used to improve the speed and quality of placement. Traditionally,clustering focuses on the local connections between cells. In this paper, a new clustering algorithmthat is based on the estimated lengths of circuit interconnects and the connectivity is proposed. Inthe proposed algorithm, first an a priori length estimation technique is used to estimate the lengthsof nets. Then, the estimated lengths are used in a clustering framework to modify a clusteringtechnique based on algebraic multigrid (AMG), that finds the cells with the highest connectivity.Finally, based on the results from the AMG-based process, clusters are made. In addition, anew physical unclustering technique is proposed. The results show a significant improvement,reductions of up to 40%, in wire length can be achieved when using the proposed technique withthree academic placers on industry-based circuits. Moreover, the runtime is not significantlydegraded and can even be improved.