An evaluation of the Chandy-Misra-Bryant algorithm for digital logic simulation

ABSTRACT

We explore the suitability of the Chandy-Misra-Bryant (CMB) algorithm for the domain of digital logic simulation. Our evaluation is based on results for six realistic benchmark circuits, one of them being the R6000 microprocessor form MIPS. A quantitative evaluation of the concurrency exhibited by the CMB algorithm shows that an average of 42-196 element activations can be evaluated in parallel if arbitrarily many processors are available. One major factor limiting the parallel performance is the large number of deadlocks that occur. We present a classification of the types of deadlocks and describe them in terms of circuit structure. Using domain-specific knowledge, we propose and evaluate several methods for both reducing the number of deadlock occurences and for reducing the time spent on each occurence. Running on a 16-processor Encore Multimax we observe speedups of 6-9. While these self-relative speedups are larger than a parallel version of the traditional centralized-time event-driven algorithm, they come at the price of large overheads: significantly more complex element evaluations, extra element evaluations, and deadlock resolution time. These overheads overwhelm the advantages of using distributed time and consistently make the parallel performance of the CMB algorithm about three times slower than that of the traditional parallel event-driven algorithm. Our experience leads us to conclude that the distributed-time CMB algorithm does not present a viable alternative to the centralized-time event-driven algorithm in the domain of parallel digital logic simulation.

REFERENCES

• 1: Mary L. Bailey , Lawrence Snyder, An empirical study of on-chip parallelism, Proceedings of the 25th ACM/IEEE conference on Design automation, p.160-165, June 12-15, 1988, Atlantic City, New Jersey, United States
• 2: BLANK, T. A survey of hardware accelerators used in computer-aided design. IEEE Des. Test Comput. (Aug 1984), 21 39.
• 3: Jack V. Briner, Jr. , John L. Ellis , Gershon Kedem, Breaking the barrier of parallel simulation of digital systems, Proceedings of the 28th conference on ACM/IEEE design automation, p.223-226, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127669]
• 4: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 5: 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]
• 6: DAVIS, H., GOLDSCHMIDT, S., AND HENNESSY, J. Mult~processing s~mulation and tracing using Tango. In Proceedlngs of the International Conference on Parallel Proces~'Ing 1991.
• 7: Tom Diede , Carl F. Hagenmaier , Glen S. Miranker , Jonathan J. Rubinstein , William S. Worley, Jr., The Titan Graphics Supercomputer Architecture, Computer, v.21 n.9, p.13-28, 30, September 1988 [doi>10.1109/2.14344]
• 8: Edward H. Frank, Exploiting parallelism in a switch-level simulation machine, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.20-26, July 1986, Las Vegas, Nevada, United States
• 9: FUJiMOTO, R. Lookahead in parallel discrete event simulation. In The 1988 International Conference on Parallel Processing. 1988, pp. 34 41.
• 10: J. W. Smith , K. S. Smith , R. J. Smith, II, Faster architectural simulation through parallelism, Proceedings of the 24th ACM/IEEE conference on Design automation, p.189-194, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37917]
• 11: 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]
• 12: Giovanni De Micheli , David C. Ku, HERCULES—a system for high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.483-488, June 12-15, 1988, Atlantic City, New Jersey, United States
• 13: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 14: LIN, Y.-B., LAZOWSK& E. D., AND BArnEY, M. L.. Comparing synchronization protocols for parallel logac-level simulation. Tech. Rep. 89-09-06, Dept. of Computer Science and Engineerrag, Umv of Washington, 19,q9.
• 15: Peter M. Maurer , Zhicheng Wang, Techniques for unit-delay compiled simulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.480-484, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123346]
• 16: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 17: Gregory F. Pfister, The Yorktown Simulation Engine: Introduction, Proceedings of the 19th conference on Design automation, p.51-54, January 1982
• 18: Paul F. Reynolds, Jr., A shared resource algorithm for distributed simulation, Proceedings of the 9th annual symposium on Computer Architecture, p.259-266, April 26-29, 1982, Austin, Texas, United States
• 19: Robert J. Smith, II, Fundamentals of parallel logic simulation, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.2-12, July 1986, Las Vegas, Nevada, United States
• 20: L. Soule , R. Blank, Statistics for parallelism and abstraction level in digital simulation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.588-591, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37980]
• 21: Larry Soulé , Tom Blank, Parallel logic simulation on general purpose machines, Proceedings of the 25th ACM/IEEE conference on Design automation, p.166-171, June 12-15, 1988, Atlantic City, New Jersey, United States
• 22: L. Soule , A. Gupta, Characterization of parallelism and deadlocks in distributed digital logic simulation, Proceedings of the 26th ACM/IEEE conference on Design automation, p.81-86, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74397]
• 23: Larry Soule , Anoop Gupta, Parallel Distributed-Time Logic Simulation, IEEE Design & Test, v.6 n.6, p.32-48, November 1989 [doi>10.1109/54.41672]
• 24: Wen-King Su, Reactive-process programming and distributed discrete-event simulation, California Institute of Technology, Pasadena, CA, 1990
• 25: WAGNER, D., LAZOWSKA, E., AND BERSHAD, B. Techniques for efficient shared-memory parallel simulation. Tech. Rep. 88-04-05, Univ. of Washington, Dept. of Computer Science, 1988.
• 26: L.-T. Wang , N. E. Hoover , E. H. Porter , J. J. Zasio, SSIM: a software levelized compiled-code simulator, Proceedings of the 24th ACM/IEEE conference on Design automation, p.2-8, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37889]
• 27: Zhicheng Wang , Peter M. Maurer, LECSIM: a levelized event driven compiled logic simulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.491-496, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123349]
• 28: WILSON, A. Parallelization of an event driven simulator on the Encore Multimax. Tech. Rep. ETR 86-005, Encore Computer, 1986.
• 29: K. F. Wong , M. A. Franklin , R. D. Chamberlain , B. L. Shing, Statistics on logic simulation, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.13-19, July 1986, Las Vegas, Nevada, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

          Nouns: MIPS R6000

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

General Terms:
Algorithms, Performance, Verification