Multiway partitioning with pairwise movement

This work proposes a simple yet effective hill climbing method called PM (Pairwise cell Movement) that overcomes the limitation of K-FM and provides partitioners the capability to explore wider range of solution space effectively while ensuring convergence to satisfying suboptimal solutions.

Abstract

It is know to many researchers in the partitioning community that the recursive bipartitioning approach outperforms the direct non-recursive approach in solving the multiway partitioning problem. However, fittle progress has been made to identify and overcome the weakness of the direct (dtematively called flat) approach. In this paper, we make the fit observation that the performmce of iterative improvement-based flat multimy petitioner K-FM [10, Then, we prp ose a simple yet effective hill-cfimbing method called PM (P-e cell hfovement) that overcomes the ~iitation of K-FAI and providw partitioners the capability to e\Tlore tider range of solution space effectively while ensuring convergence to satisfying suboptirnd solutions. The main idea is to reduce the mtitiway partitioning problem to sets of concurrent bipartitioning problems. Starting tith an initial mtitimy partition of the netfist, we apply 2-way FM [7] to pairs of blocks so as to improve the qufllty of overall multiwy partitioning solution. The pairiig of blocks is based on the gain of the last pass, and the Ptise cell Movement (Phi) passes continue until no further gain can be obtained. We observe that Phl passes are effective in distributing clusters evenly into mtitiple blocks to minimize the connections across the multiway cut~iea. Our iterative improvementbased flat multiway partitioned K-PM/LR improves K-FM by a surprising average mmgin of up to 86.2% and outperforms its counterpart recursive FM by up to 17.3% when tested on LICNC and large scale ISPD98 benchmark circuits [1].