학술논문
Gate-level Circuit Partitioning Algorithm Based on Cut Vertex and Betweenness Centrality
Document Type
Conference
Author
Source
2022 34th Chinese Control and Decision Conference (CCDC) Control and Decision Conference (CCDC), 2022 34th Chinese. :1555-1562 Aug, 2022
Subject
Language
ISSN
1948-9447
Abstract
Circuit partitioning is a key link in gate-level parallel simulation. Existing circuit partitioning algorithms usually require the number of cells included in each subset to be balanced first, and secondly, the number of interconnections between each subset is as small as possible. The time and computing resources overhead of gate-level parallel simulation will increase significantly as the number of interconnections between the partitioned subsets increases, and the requirement for balanced result of the partitioning takes second place. To this end, a gate-level circuit partitioning algorithm based on cut vertex and betweenness centrality was proposed, which evaluated cut vertex through betweenness centrality, searched and partitioned based on the optimal cut vertex that met the equilibrium condition, minimized interconnections first, and made the number of logic gates contained in each subset relatively balanced. The experimental results of this algorithm in the actual gate-level circuit partitioning show that compared with the KL algorithm and the METIS partitioning tool, the algorithm can get fewer interconnections.