MULTES: Multi-level Temporal-parallel Event-driven Simulation

Hardware simulation remains the most widely used technique for functional and timing verification and, owing to its many advantages, will remain so for a foreseeable future. However, simulation suffers from very low runtime performance that is dictated by its inherently sequential nature. Parallel Discrete Event-driven Simulation (PDES), proposed in the past to address this issue, has failed to achieve sufficient performance improvement due to the synchronization, inter-module communication, and load balancing problems. A different type of parallel simulation, called Time-parallel simulation (TPS) has been proposed in 1990\u27s. In contrast to PDES, TPS partitions the entire simulation into a set of shorter simulation runs (slices) in temporal domain. This approach theoretically allows the simulation to achieve high parallelism as the technique does not suffer from synchronization and communication overhead. Nevertheless, this concept has been neglected for a long time because it was faced with a host of new problems. One of them is obtaining the initial state of each simulation slice, which remains a difficult problem for complex industrial designs. This dissertation describes a new, radically different approach to simulation of designs described in Verilog HDL, based on a concept similar to TPS. The technique, termed Multi-level Temporal-parallel Event-driven Simulation (MULTES), specifically addresses the gate-level timing simulation, important in final, post-layout timing verification of designs implemented in nanometer device technology. MULTES solves the problem of finding the initial state of each time slice in the design by using a design model at a higher abstraction level, such as RTL (Register Transfer Level) or ESL (Electronic System Level). MULTES consists of two major steps: (1) fast reference simulation that runs on a higher level (reference) design model and collects the necessary information about the design state; and (2) target simulation, which runs on a lower level (target) model and distributes the simulation slices to individual simulators. The proposed approach improves not only the performance of the simulation but also the debugging efficiency. This is because MULTES involves both the reference and target simulation, allowing comparison of simulation results between the two models to be achieved naturally, as part of the design flow. As a result, MULTES has the potential to provide a smarter simulation-based verification methodology in a design implementation and verification flow. This dissertation describes the theory and the implementation of MULTES and discusses how the initial state for each target slice is obtained from the reference simulation and used for target simulation. In addition, several practical solutions to some challenging problems are described to make this approach practical. They include: handling multiple asynchronous clocks, solving load balancing problem, simulating a design with unsynthesizable blocks, and others. The presented experimental results demonstrate that MULTES is applicable to a variety of industrial designs and provides significant improvement of simulation performance by yielding a high-degree of parallelism