An Efficient Two-Level Partitioning Algorithm for VLSI Circuits*

In this paper, a new two-level bipartitioning algorithm TLP, combining a hybrid clustering technique with an iterative improvement based partitioning process, is proposed. The hybrid clustering algorithm consisting of a local bottom-up clustering technique to merge modules and a global topdown ratiocut technique for decomposition can be used to reduce the partitioning complexity and improve the performance. To generate a highquality partitioning solution, a module migrahon based partitioning algorithm MMP is also proposed as the base partitioner for the TLP algorithm. The MMP algorithm implicitly promotes the move of clusters during the module migration processes by paying more attention to the neighbors of moved modules, relaxing the size constraints temporarily during the migration process, and controlling the module migration direction. Experimental results obtained show that the TLP algorithm generates stable and highquality partitioning results. The TLP algorithm improves the unstable property of module migration based algorithms such as FM [6] and STABLE [3] in terms of the average net cut value. On the other hand, TLP outperforms MELO [2], GFM, [I I], and C D I P L A ~ [ ~ ] by 23%, 7%, and IO%, respectively and is competitive with hMetis [8], MLc [I], and LSIUMFFS [4] which have generated better results than many recent state-of-the-art partitioning algorithms.