Conservative circuit simulation on shared-memory multiprocessors

ABSTRACT

We investigate conservative parallel discrete event simulations for logical circuits on shared-memory multiprocessors. For a first estimation of the possible speedup, we extend the critical path analysis technique by partitioning strategies. To incorporate overhead due to the management of data structures, we use a simulation on an ideal parallel machine (PRAM). This simulation can be directly executed on the SB-PRAM prototype, yielding both an implementation and a basis for data structure optimizations. One of the major tools to achieve these is the SB-PRAM's hardware support for parallel prefix operations. Our reimplementation of the PTHOR program on the SB-PRAM yields substantially higher speedups than before.

REFERENCES

• 1: E Abolhassan, J. Keller, and W.J. Paul. On the Cost- Effectiveness of PRAMs. In Proc. 3rd IEEE Symp. on Parallel and Distributed Processing, pages 2-9, 1991.
• 2: George S. Almasi , Allan Gottlieb, Highly parallel computing (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 3: Mary L. Bailey , Jack V. Briner, Jr. , Roger D. Chamberlain, Parallel logic simulation of VLSI systems, ACM Computing Surveys (CSUR), v.26 n.3, p.255-294, Sept. 1994 [doi>10.1145/185403.185424]
• 4: O. Berry and D. Jefferson. Critical path analysis of distributed simulation. In Proceedings 1985 SCS Multiconference on Distributed Simulation, pages 57-60, January 1985.
• 5: Azzedine Boukerche , Carl Tropper, A static partitioning and mapping algorithm for conservative parallel simulations, Proceedings of the eighth workshop on Parallel and distributed simulation, p.164-172, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 6: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 7: K. M. Chandy and J. Misra. Deadlock absence proofs for networks of communicating processes. Information Processing Letters, 94:185-189, November 1979.
• 8: 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]
• 9: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 10: Thomas Grtin, Thomas Rauber, and Jochen R6hrig. The programming environment of the SB-PRAM. In Proc. 7th IASTED/ISMM Int. I Conf. on Parallel and Distributed Computing and Systems, Washington DC, October 1995.
• 11: Michial A. Gunter, Understanding supercritical speedup, Proceedings of the eighth workshop on Parallel and distributed simulation, p.81-87, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 12: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 13: David Jefferson , Peter Reiher, Supercritical speedup, Proceedings of the 24th annual symposium on Simulation, p.159-168, April 1991, New Orleans, Louisiana, United States
• 14: Kevin L. Kapp , Thomas C. Hartrum , Tom S. Wailes, An improved cost function for static partitioning of parallel circuit simulations using a conservative synchronization protocol, Proceedings of the ninth workshop on Parallel and distributed simulation, p.78-85, June 13-16, 1995, Lake Placid, New York, United States
• 15: Pavlos Konas , Pen-Chung Yew, Partitioning for synchronous parallel simulation, Proceedings of the ninth workshop on Parallel and distributed simulation, p.181-184, June 13-16, 1995, Lake Placid, New York, United States
• 16: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 17: Yi-Bing Lin, Parallelism analyzers for parallel discrete event simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.239-264, July 1992 [doi>10.1145/146382.146401]
• 18: M. Livny. A study of parallelism in distributed simulation. In Proceedings 1985 SCS Multiconference on Distributed Simulation, pages 94-98, San Diego, CA, January 1985.
• 19: Jochen R6hrig. Implementierung der P4-Laufzeitbibliothek auf der SB-PRAM. Master's Thesis, Universit~it des Saarlandes, 1996.
• 20: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 21: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 22: Lawrence Peter Soule , Anoop Gupta, Parallel logic simulation: an evaluation of centralized-time and distributed-time algorithms, 1992
• 23: Christian Sporrer , Herbert Bauer, Corolla partitioning for distributed logic simulation of VLSI-circuits, Proceedings of the seventh workshop on Parallel and distributed simulation, p.85-92, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Measurement, Performance, Theory

Keywords:
circuit simulation, conservative simulation, multiprefix operation, parallel random access machine (PRAM), shared memory multiprocessor, speedup estimation