Characterization of parallelism and deadlocks in distributed digital logic simulation

ABSTRACT

This paper explores the suitability of the Chandy-Misra algorithm for digital logic simulation. We use four realistic circuits as benchmarks for our analysis, with one of them being the vector-unit controller for the Titan supercomputer from Ardent. Our results show that the average number of logic elements available for concurrent execution ranges from 10 to 111 for the four circuits, with an overall average of 68. Although this is twice as much parallelism as that obtained by traditional event-driven algorithms for these circuits, we feel it is still too low. One major factor limiting concurrency is the large number of global synchronization points — “deadlocks” in the Chandy-Misra terminology — that occur during execution. Towards the goal of reducing the number of deadlocks, the paper presents a classification of the types of deadlocks that occur during digital logic simulation. Four different types are identified and described intuitively in terms of circuit structure. Using domain specific knowledge, the paper proposes methods for reducing these deadlock occurrences. For one of the benchmark circuits, the use of the proposed techniques eliminated all deadlocks and increased the average parallelism from 40 to 160. We believe that the use of such domain knowledge will make the Chandy-Misra algorithm significantly more effective than it would be in its generic form.

REFERENCES

• 1: Tom Blank. A Survey of Hardware Accelerators Used in Computer-Aided Design. IEEE Trans. on Design and Test, 21-39, August 1984.
• 2: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 3: 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]
• 4: 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]
• 5: 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
• 6: 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]
• 7: 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
• 8: 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]
• 9: Larry Soule , Anoop Gupta, Analysis of Parallelism and Deadlocks in Distributed-Time Logic Simulation, Stanford University, Stanford, CA, 1989
• 10: 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:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Control design
      B.5.2 Design Aids
          Subjects: Verification

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Performance, Verification