PROP: A Recursive Paradigm for Area-Efficient and Performance Oriented Partitioning of Large FPGA Netlists

In this paper, we introduce a new recursive partitioning paradigm PROP which combines partitioning, replication, optimization, to be followed by another recursion of partitioning, etc. We measure the quality of partitions in terms of total device cost, logic and terminal utilization, and critical path delay. Traditionally, the minimum lower bound into which a given netlist can be partitioned is determined by disregarding the logic interconnect while distributing the logic nodes into a minimum number of devices. PROP paradigm challenges this assumption by demonstrating feasible partitions of some large netlists such that the number of device partitions is smaller than minimum lower bounds postulated initially. Overall, we report consistent reductions in the total number of partitions for a wide range of combinational and sequential circuit benchmarks while, on the average, reducing critical path delay as well