Benchmarking Open Access VLSI Partitioning Tools

Most algorithms used in VLSI CAD tackle NP-hard problems, and face scalability issues arisen from the ever-increasing circuit size. Partitioning enables the use of divide-to-conquer strategy, allowing the usage of complex algorithms by reducing the problem in instances of smaller sizes. Several open-access tools have arisen to tackle partitioning problem. This work performs a comprehensive evaluation of four partitioning tools, investigating the performance in actual benchmarks. We investigate graph and hypergraph partitioning, considering different graph models of hypergraphs and edge-weighting schemes. The analysis compares graph and hypergraph partitionings in terms of hyperedge cut, number of terminals, and runtime. Finally, the robustness of the tools is evaluated by testing different numbers of final partitions and how they are balanced. The results present difference up 2X in hyperedge cut and more than 1000X in runtime. The presented data can define the applicability and advantages of each tool and possible methods to alleviate those downfalls.