Massively parallel switch-level simulation: a feasibility study

ABSTRACT

This work addresses the feasibility of mapping the COSMOS switch-level simulator onto a computer with thousands of simple processors. COSMOS preprocesses transistor networks into Boolean behavioral models, capturing the switch-level behavior of a circuit in a set of Boolean formulas. We describe a class of massively parallel computers and a mapping of COSMOS onto these computers. We discuss the factors affecting the performance of such a massively parallel simulator including: the amount of parallelism in the simulation model, performance measures for massively parallel machines, and the impact of event scheduling on simulator performance. We have developed compilation tools which automatically map a MOS circuit onto a massively parallel computer. Massively parallel switch-level simulation is illustrated by describing our pilot implementation on a 32k processor Thinking Machines Connection Machine System.

REFERENCES

• Bailey 88: 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
• Bryant 87: R. E. Bryant , D. Beatty , K. Brace , K. Cho , T. Sheffler, COSMOS: a compiled simulator for MOS circuits, Proceedings of the 24th ACM/IEEE conference on Design automation, p.9-16, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37890]
• Coffman 80: E. Coffman, Jr., et.al., "Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms", SIAM J. Computing, V9 (1980), pp. 808-826.
• Denneau 82: Monty M. Denneau, The Yorktown Simulation Engine, Proceedings of the 19th conference on Design automation, p.55-59, January 1982
• Frank 86: 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
• Hillis 86: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• Hillis 86a: 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]
• Kravitz 89: S. Kravitz , R. E. Bryant , R. Rutenbar, Logic simulation on massively parallel architectures, Proceedings of the 16th annual international symposium on Computer architecture, p.336-343, April 1989, Jerusalem, Israel
• Kravitz 89a: Saul Abram Kravitz, Massively parallel switch-level simulation: a feasibility study, 1989
• Sheffler 87: T.J. Sheffler, "A Graph Separator Theorem and Its Application to Gaussian Elimination to Optimize Boolean Expressions for Parallel Evaluation", MS Thesis, Dept. of ECE, Carnegie Mellon University, 1987.
• Smith 86: 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
• Webber 87: 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]
• Wong 86: 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.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

General Terms:
Algorithms, Design, Measurement, Performance