TBPart: An Effective Topological Order Balanced Hypergraph Partitioning Algorithm for VLSI Processor-based Hardware Emulation

As the complexity of circuit designs continues growing, processor-based emulation is becoming more and more popular for design verification. In a large-scale design, there are significant dependencies among the basic logic cells, which is represented as cells' topological order if the design is mapped to a graph. During the circuit partitioning stage, assigning the same topological order cells to one processor would significantly increase the delay of scheduling, further degrading the over-all performance. However, some well-known partitioners, like hMETIS and PaToH, mainly focus on cut size minimization without considering such topological order balance constraints, which limits their practical usage in processor-based hardware emulation. In this paper, we propose a partitioning algorithm TBPart considering the topological order balance to address the issue of wasting computational resources in hardware emulation. TBPart improves the topological balance of the partitioning results by considering the gain brought by vertices movement in improving the topological balance while also taking into account the cut-size loss, ensuring the quality of the cut-size while improving the topological balance of the partitioning results. We evaluate TBPart using the ISPD98 benchmark tests, and experimental results demonstrate its effectiveness in improving the topological order balance. On average hand, 0.26 times cut-size loss can result in a 2-fold improvement in topological order balance.