Parallel event-driven logic simulation algorithms: tutorial and comparative evaluation

Parallel processing offers a viable way to improve the enormous execution time of the simulation of large VLSI designs. Various parallel logic simulation approaches have been proposed in recent years resulting in some ambiguity as to which scheme offers the best parallelism and execution time. To address these issues, the authors provide a detailed comparison of all four major types of event-driven logic simulation algorithms (synchronous, conservative asynchronous with deadlock avoidance, conservative asynchronous with deadlock detection and resolution, and optimistic asynchronous). The comparisons are carried out on an ideal parallel machine capable of extracting all available parallelism in a given algorithm. The simulation execution time, average parallelism and total messages required for a particular simulation algorithm are measured on the ISCAS combinational and sequential benchmark circuits. The use of an ideal parallel machine exposes characteristics of the simulation algorithms independent of the effects caused by particular parallel architectures or implementations. It is shown that a recently developed conservative asynchronous algorithm of the deadlock avoidance type and the optimistic asynchronous algorithm achieve the best parallel execution time results. However, the new conservative algorithm requires much less implementation overhead than the optimistic algorithm