Fine granularity clustering-based placement

TitleFine granularity clustering-based placement
Publication TypeJournal Article
Year of Publication2004
AuthorsHu, B, Marek-Sadowska, M
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination527 - 536
Date Publishedapril
Keywordscircuit layout CAD, circuit optimisation, fast placer implementation framework, fine granularity clustering-based placement, FPI, graph theory, IC design, integrated circuit design, integrated circuit interconnections, integrated circuit layout, interconnect prediction, net absorption, netlist, placement algorithm efficiency, wire-length prediction
AbstractIn this paper, we address the problem of improving the efficiency of placement algorithms. We employ a fine granularity clustering technique to reduce the original placement problem size. The reduction is feasible because a global placer may not need to operate on the bottom level netlist in order to achieve a competitive result. In general, placement algorithm efficiency is well correlated with the number of nodes in the netlist. Reducing the size of the placement problem (the number of nodes to be placed) leads to greater efficiency. We propose two new clustering algorithms. One applies net absorption, and the other is based on wire-length prediction. We have integrated those algorithms into our fast placer implementation (FPI) framework. We demonstrate experimentally that FPI achieves significant speedup while maintaining placement quality comparable to the state-of-the-art standard cell placer.