A unified cost model for min-cut partitioning with replication applied to optimization of large heterogeneous FPGA partitions

Abstract

This paper introduces the concept of functional replication and a unifled cost model for min-cut partitioning with replication. We apply this concept to the problem of partitioning large logic circuits into a collection of subcir- cuits each of which is implemented with a device from a speciflc (FPGA) library. We measure the quality of each k-way partition not only in in terms of the minimum size of the cutset but also the total device cost, the average utilization of logic as well as the terminal capacity. Bench- mark results show signiflcant improvements in the size of the cutset when partitioning without terminal constraints as well as when partitioning with size and terminal con- straints.