Partitioning with cone structures

Circuit partitioning for packages that have limited numbers of IO pins is a critical problem with FPGAs. Common FPGAs have prespecified maximum gate count limits on the order of five to ten times the number of usable IO pins. Traditional min-cut approaches lack the ability to find such constrained partitions with high gate to IO pin ratios. In this paper, a new partitioning algorithm is presented that uses cone structures. Cone structures are minimum cut partitioning structures for netlists with low fanout, and clustering structures for partitioning netlists with high fanout. Cone structures also allow for full containment of critical paths. When used with good Merging/Cutting strategies, results show that the cone partitioning algorithms introduced here produce better partitions than min-cut.