Data parallel simulation using time-warp on the connection machine

ABSTRACT

A new data parallel simulation technique of Time-Warp on the Connection Machine is presented. Our scheme handles the rollback problem of Time-Warp efficiently, and maximizes data parallelism, where the parallelism is extracted from simultaneous evaluation of different circuit elements. Each event is assigned to one of the processors of the Connection Machine to achieve high data parallelism. A new scheme to reduce space overhead in Time-Warp is proposed.

REFERENCES

• AP85: Agrawal, P., "Circuit Partitioning For Hardware Simulation Engines," Proceedings of the 1985 International Conference on Computer Aided Design, pp.161-163.
• BR88: Bryant, R. E., " Data Parallel Switch-Level Simulation," ICCAD '88 Proceedings.
• CM: "Using The Connection Machine System," Thinking Machines Corporation, May 1988.
• CM81: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• HS86: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• JD85: Jefferson, D.R. et al, " Implementation of Time Warp on the Caltech Hypercube", 1985 Society for Computer Simulation Multiconference, San Diego, California, January 1985.
• JS85: Jefferson, D., "Fast Concurrent Simulation using the Time Warp Mechanism," 1985 Society for Computer Simulation Mulficonference, San Diego, California, January 1985.
• PS88: Pitts, D.L., and Smith, D.L., "Central Concurrency Control for Distributed Simulations",Proceedings of 1988 Summer Computer Simulation Conference, 1988.
• WS87: D. M. Webber , A. Sangiovanni-Vincentelli, Circuit simulation on the connection machine, Proceedings of the 24th ACM/IEEE conference on Design automation, p.108-113, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37904]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance