Study On Digital Circuit Gate-level Parallel Logic Simulation

Logic simulation is an important component of EDA software, and is an important tool that is employed to verify the correctness of design. As the scale of circuit is improved continuely, logic simulation costs more time. High cost-time of logic simulation becomes a bottleneck of IC design, and cost of development is increased. For depressing the simulation time, we research the parallel logic simulation algorithm based on cluster and its corresponding acyclic circuit partition algorithm.Event-driven algorithm is major one of serial circuit simulation. Based on it, we explored the parallel logic simulation algorithm used MPI message passing technique. For parallel simulation, there are a series of challenges. The first challenge is choice of synchronous protocol. After analysis and comparing of conservative and optimistic protocol, we choose first one. The other challenge is deadlock. We employ flow technique to avoid deadlock. The difficulty of development decreases. For improving performance, we employ non-block communication technique to depress the cost of passing message, so that the communication and computing are overlayed at most extent.Circuit partition is the other major research content. For avoiding deadlock and flowing the parallel logic simulation, we need an acyclic circuit partition. We show the mathematical description and definition of circuit using directed-graph. Then, we show the definition of acyclic partition. Based on maximum free fanout cone(MFFC), we propose the concept of no-output cyclic cluster(NOCYC), such that we can do cluster identification in circuit that contains cyclic path. These are the basic theory of circuit partition. MFFC and NOCYC identification algorithms are employed to decompose the circuit into cluster network that don't contain cyclic path. Then, an acyclic initial partition is achieved from cluster networks. At last, simulated annealing optimizing is discussed. During the optimization procedure, balanced condition, acyclic condition and min-cut condition are considered, and the final partition is achieved.We choose eight circuits for testing from ISCAS85 and 89. At first, we do 2, 4 ,..., 16-way acyclic circuit partition. Then, we do parallel logic simulation on Shuguang Cluster. From the testing data, we come to a dicision that cost-time decrease intensely for large scale circuits as number of parallel processes increase from 1 to 8. But for less scale circuits, cost-time decrease slowly as number of processes increase. As number of parallel processes is more than 8, cost-time fluctuates. As for speedup-rate, there is a similar conclusion. As number of parallel processes increase from 1 to 8, speedup-rate approachs linear speedup-rate, even super-linear speedup-rate. As number of parallel processes is more than 8, speedup-rate trends to move down. In general, a relatively ideal of speedup-rate can be achieved as number of parallel processes less than 8.