Gate-level circuit division method based on cut set and vertex characteristics

Abstract

The invention provides a cut set and vertex feature-based gate-level circuit division method, and the method comprises the following steps: S1, preprocessing a driving matrix of a gate-level circuit, and converting the driving matrix into a standard adjacent matrix; S2, based on weak connectivity preliminary division of a directed graph, dividing the directed graph into at least one independent primary unit; S3, taking the maximum unit in all the units, and dividing the maximum unit into one or more secondary units: if the number of the secondary units is more than one, executing the step S4, and if the number of the secondary units is one, executing the step S5; S4, repeating the step S3 until the maximum unit in all the current units does not meet the effective division condition, and turning to the step S5; and S5, outputting vertex vectors and adjacent matrixes of all divided units. Compared with the prior art, the number of connecting lines between the subsets after division can be reduced, the number of gate circuits contained in the subsets is relatively balanced, and the parallel simulation speed of the gate-level circuit is increased.

Description

technical field [0001] The invention relates to circuit division of gate-level circuit simulation, in particular to a gate-level circuit division method based on cut sets and vertex features. Background technique [0002] Gate-Level Simulation (Gate-Level Simulation) is an important verification process in Electronic Design Automation (EDA). As the complexity of VLSI (Very large-scale integration, VLSI) continues to increase, the running time of gate-level simulation becomes very long. In order to increase the speed of gate-level simulation, parallelization of gate-level simulation has become a trend, that is, the gate-level circuit is divided into multiple smaller parts, so that it can be simulated in parallel by distributed machines. [0003] Most of the existing circuit partitioning algorithms are applied to the physical design of VLSI. The circuit composed of logic gates or standard cells is divided into multiple subsets. It usually requires the number of components con...

AI Technical Summary

Problems solved by technology

[0004] There are few existing circuit division methods for gate-level simulation parallelization, and fully parallel simulation is very sensitive to the number of connecting lines between subsets in gate-level circuit causal division, and the increase in the number of connecting lines will greatly increase the calculation of fully parallel simulation resource overhead

Images