Research On The Circuit Partitioning Algorithm Of Gate-level Parallel Simulation In EDA

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 computational resource 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,the research on gate-level circuit partitioning algorithm is carried out in this paper.The main work is as follows:1)A complete mathematical expression method of gate-level netlist of digital integrated circuits was proposed.This method included: the directed drive graph,3 drive matrices and 5 vectors.They can express all the information of the gate-level netlist without ambiguity,and provide an effective mathematical description form for the analysis and calculation of digital integrated circuits.2)A gate-level circuit partitioning algorithm based on cut vertex and betweenness centrality was proposed.This algorithm took minimizing interconnections as the primary goal,partitioned based on cut vertex in graph theory,and introduced the concept of betweenness centrality to evaluate the equilibrium of the partitioning based on cut vertex.Firstly,calculated the betweenness centrality of all vertices,and searched for the optimal cut vertex in descending order of betweenness centrality;then,used the enumeration method to calculate the combination of the least cut edges of the optimal cut vertex to realize the partitioning;finally,repeated the above process until the algorithm terminated.The experimental results show that the number of interconnections obtained by this algorithm is reduced by an average of 76% compared with the KL algorithm,and an average of 25% compared with the METIS partitioning tool,which is beneficial to reduce the time and computational resource overhead of gate-level parallel simulation.3)A gate-level circuit partitioning algorithm based on clustering was proposed.Firstly,based on betweenness centrality,the relatively independent and closely connected vertices were clustered to realize the preliminary partitioning of the circuit;then,the improved genetic algorithm was used to refine the remaining vertices,the fitness function was designed with the goal of minimizing interconnections,reducing the number of interconnections.The experimental results show that the number of interconnections obtained by this algorithm is reduced by an average of 55% compared with the KL algorithm in bipartitioning,and 38%compared with the METIS partitioning tool in 3-way partitioning,which is beneficial to reduce the time and computational resource overhead of gate-level parallel simulation.