An algebraic multigrid-based algorithm for circuit clustering

作者：Rakai Logan; Behjat Laleh^*; Martin Sebastian; Aguado Jose

来源：Applied Mathematics and Computation, 2012, 218(9): 5202-5216.

DOI：10.1016/j.amc.2011.10.084

• Clustering
• Algebraic multigrid (AMG)
• Graph coarsening
• Design automation
• Physical design

Digital circuits have grown exponentially in their sizes over the past decades. To be able to automate the design of these circuits, efficient algorithms are needed. One of the challenging stages of circuit design is the physical design where the physical locations of the components of a circuit are determined. Coarsening or clustering algorithms have become popular with physical designers due to their ability to reduce circuit sizes in the intermediate design steps such that the design can be performed faster and with higher quality. In this paper, a new clustering algorithm based on the algebraic multigrid (AMG) technique is presented. In the proposed algorithm, AMG is used to assign weights to connections between cells of a circuit and find cells that are best suited to become the initial cells for clusters, seed cells. The seed cells and the weights between them and the other cells are then used to cluster the cells of a circuit. The analysis of the proposed algorithm proves linear-time complexity, O(N), where N is the number of pins in a circuit. The numerical experiments demonstrate that AMG-based clustering can achieve high quality clusters and improve circuit placement designs with low computational cost.

• 出版日期2012-1