Modifying Min-Cut for Hardware and Software Functional Partitioning

The Kernighan/Lin heuristic, also known as min-cut, has been extended very successfully for circuit partitioning over several decades. Those extensions customized the heuristic and its associated data structure to rapidly compute the minimum-cut metric required during circuit partitioning; thus, those extensions are not applicable to problems requiring other metrics. In this paper, we extend the heuristic for functional partitioning in a manner applicable to the codesign problem of hardware/software partitioning as well as to hardware/hardware partitioning. The extension customizes the heuristic and data structure to rapidly compute execution-time and communication metrics, crucial to hardware and software partitioning, and leads to nearlinear time-complexity and excellent results. Our experiments demonstrate extremely fast execution times (just a few seconds) with results matched only by the much slower simulated annealing heuristic, meaning that the extended Kernighan/Lin heuristic w..