PARALLEL EVENT-DRIVEN LOGIC SIMULATION ALGORITHMS - TUTORIAL AND COMPARATIVE-EVALUATION

Parallel processing offers a viable way to improve the enormous execut ion time of the simulation of large VLSI designs. Various parallel log ic simulation approaches have been proposed in recent years resulting in some ambiguity as to the best parallelism and address these issues, the authors provide a detailed comparison of all four major types of event-driven logic simulation algorithms (synchronous, conservative as ynchronous with deadlock avoidance, conservative asynchronous with dea dlock detection and resolution, and optimistic asynchronous). The comp arisons are carried out on an ideal parallel machine capable of extrac ting all available parallelism in a given algorithm. The simulation ex ecution time, average parallelism and total messages required for a pa rticular simulation algorithm are measured on the ISCAS combinational and sequential benchmark circuits. The use of an ideal parallel machin e exposes characteristics of the simulation algorithms independent of the effects caused by particular parallel architectures or implementat ions. It is shown that a recently developed conservative asynchronous algorithm of the deadlock avoidance type and the optimistic asynchrono us algorithm achieve the best parallel execution time results. However , the new conservative algorithm requires much less implementation ove rhead than the optimistic algorithm.