Event-driven gate-level simulation with GP-GPUs

ABSTRACT

Logic simulation is a critical component of the design tool flow in modern hardware development efforts. It is used widely -- from high-level descriptions down to gate-level ones -- to validate several aspects of the design, particularly functional correctness. Despite development houses investing vast resources in the simulation task, particularly at the gate-level, it is still far from achieving the performance demands required to validate complex modern designs.

In this work, we propose the first event-driven logic simulator accelerated by a parallel, general purpose graphics processor (GP-GPU). Our simulator leverages a gate-level event-driven design to exploit the benefits of the low switching activity that is typical of large hardware designs. We developed novel algorithms for circuit netlist partitioning and optimized for a highly-parallel GP-GPU host. Moreover, our flow is structured to extract the best simulation performance from the target hardware platform. We found that our experimental prototype could handle large, industrial scale designs comprised of millions of gates and deliver a 13x speedup on average over current commercial event-driven simulators.

REFERENCES

• 1: J. Babb, R. Tessier, M. Dahl, S. Hanono, D. Hoki, and A. Agarwal. Logic emulation with virtual wires. IEEE Trans. on CAD, 1997.
• 2: W. Baker, A. Mahmood, and B. Carlson. Parallel event-driven logic simulation algorithms: Tutorial and comparative evaluation. IEEE Journal on Circuits, Devices and Systems, 1996.
• 3: Z. Barzilai, J. Carter, B. Rosen, and J. Rutledge. HSS--a high-speed simulator. IEEE Trans. on CAD, 1987.
• 4: H. Bauer and C. Sporrer. Reducing rollback overhead in time-warp based distributed simulation with optimized incremental state saving. Proc. ANSS, 1993.
• 5: O. Berry and G. Lomow. Speeding up distributed simulation using the time warp mechanism. In Proc. of workshop on Making distributed systems work, 1986.
• 6: R. Bryant, D. Beatty, K. Brace, K. Cho, and T. Sheffler. COSMOS: a compiled simulator for MOS circuits. In Proc. DAC, 1987.
• 7: K. Chandy and J. Misra. Asynchronous distributed simulation via a sequence of parallel computations. Comm. ACM, 1981.
• 8: D. Chatterjee, A. DeOrio, and V. Bertacco. High-performance gate-level simulation with GP-GPUs. In Proc. DATE, 2009.
• 9: M. Denneau. The Yorktown simulation engine. Proc. DAC, 1982.
• 10: R. Fujimoto. Parallel discrete event simulation. Comm. ACM, 1990.
• 11: K. Gulati and S. Khatri. Towards acceleration of fault simulation using graphics processing units. Proc. DAC, 2008.
• 12: H. Kim and S. Chung. Parallel logic simulation using time warp on shared-memory multiprocessors. Proc. IPPS, 1994.
• 13: Y.-I. Kim, W. Yang, Y.-S. Kwon, and C.-M. Kyung. Communication-efficient hardware acceleration for fast functional simulation. Proc. DAC, 2004.
• 14: D. Lewis. A hierarchical compiled code event-driven logic simulator. IEEE Trans. on CAD, 1991.
• 15: N. Manjikian and W. Loucks. High performance parallel logic simulations on a network of workstations. Proc. of workshop on Parallel and distributed simulation, 1993.
• 16: Y. Matsumoto and K. Taki. Parallel logic simulation on a distributed memory machine. Proc. EDAC, 1992.
• 17: J. Misra. Distributed discrete-event simulation. ACM Computing Surveys, 1986.
• 18: NVIDIA. CUDA Compute Unified Device Architecture, 2007.
• 19: Opencores. http://www.opencores.org/.
• 20: A. Perinkulam and S. Kundu. Logic simulation using graphics processors. In Proc. ITSW, 2007.
• 21: Sun microsystems OpenSPARC. http://opensparc.net/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

General Terms:
Performance, Verification

Keywords:
gate-level simulation, general purpose graphics processing unit (GP-GPU), high-performance simulation