Parallel logic simulation of VLSI systems

ABSTRACT

Fast, efficient logic simulators are an essential tool in modern VLSI system design. Logic simulation is used extensively for design verification prior to fabrication, and as VLSI systems grow in size, the execution time required by simulation is becoming more and more significant. Faster logic simulators will have an appreciable economic impact, speeding time to market while ensuring more thorough system design testing. One approach to this problem is to utilize parallel processing, taking advantage of the concurrency available in the VLSI system to accelerate the logic simulation task.Parallel logic simulation has received a great deal of attention over the past several years, but this work has not yet resulted in effective, high-performance simulators being available to VLSI designers. A number of techniques have been developed to investigate performance issues: formal models, performance modeling, empirical studies, and prototype implementations. Analyzing reported results of these techniques, we conclude that five major factors affect performance: synchronization algorithm, circuit structure, timing granularity, target architecture, and partitioning. After reviewing techniques for parallel simulation, we consider each of these factors using results reported in the literature. Finally we synthesize the results and present directions for future research in the field.

REFERENCES

• 1: ACKLAND, B. D., AHW& S. R., LINDSTROM, T. L., ant) ROMERO~ 7). J. 1985. CEMU--A concurrent timing simulator. In Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE, New York, 122-124.
• 2: AG~^WAb, P. 1986. Concurrency and communication in hardware simulators. IEEE Trans. Comput. A~ded Des. Integr. Ctrc. Syst. CAD-5, 4 (Oct.), 617 623.
• 3: V. D. Agrawal , S. T. Chakradhar, Performance Analysis of Synchronized Iterative Algorithms on Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.739-746, November 1992 [doi>10.1109/71.180628]
• 4: AGRAWAL, P. AND DALLY, W.J. 1990. A hardware logic simulation system. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 9, 1 (Jan.), 19-29.
• 5: ARNOLD, J. 1985. Parallel simulation of digital circuits. MS thesis, Massachusetts Institute of Technology, Cambridge, Mass.
• 6: ARNOLD, J. AND TERMAN, C. 1985. A multiprocessor implementation of a logic-level timing simulator. In Proceedmgs of the IEEE InternatLonal Conference on Computer-Aided Design. IEEE, New York, 116 118.
• 7: ARWND, D. K. AND SMART, C.R. 1991. A unified framework for parallel event-driven logic simulation In Proceedings of the SCS Summer Simulation Conference. SCS, San Diego, Calif., 92-97.
• 8: BAILEY, M.L. 1993. A delay-based model for circuit parallelism. IEEE Trans. Comput. Azded Des. Integr. Circ. Syst. 12, 12 (Dec.), 1903-1912.
• 9: BAILEY, M. L. 1992a. How circuit size affects parallelism IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 11, 2 (Feb), 208-215.
• 10: BAILEY, M.L. 1992b. A time-based model for investIgatmg parallel logic-level simulation. IEEE Trans. Comput. Aided Des. Integr Czrc. Syst. 11, 7 (July), 816 824.
• 11: 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
• 12: BAILEY, M. L. AND LIN, Y.-B. 1993. Synchronization strategies for parallel logic-level simulation. Int. J. Comput. Simul. 3, 3, 211 230.
• 13: Abdulla Bataineh , Füsun Özgüner , Imre Szauter, Parallel logic and fault simulation algorithms for shared memory vector machines, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.369-372, November 1992, Santa Clara, California, United States
• 14: BAUER, H. AND SPORRER, C. 1993. Reducing rollback overhead in Time-Warp based distributed simulation with optimized incremental state saving. In Procee&ngs of the 26th Annual S~muIation Symposmm. IEEE Computer Society Press
• 15: BAUER, H., SPOaaER, C., AND KRODEL, T.H. 1991. On distributed logic simulation using T~me Warp. In Procee&ngs o/the Internatzonal Conference on Very Large Scale Integration VLSI 91. North-Holland, Amsterdam, 127-136.
• 16: Daniel K. Beece , George Deibert , Georgina Papp , Frank Villante, The IBM engineering verification engine, Proceedings of the 25th ACM/IEEE conference on Design automation, p.218-224, June 12-15, 1988, Atlantic City, New Jersey, United States
• 17: BILLOWITCH, W.D. 1993. IEEE 1164: Helping designers share VHDL models. IEEE Spectr. 30, 6 (June), 37.
• 18: BLANK, T. 1984. A survey of hardware architectures used in computer-aided design. IEEE Des Test Camput. 1, 4, 21 39
• 19: BRGLEZ, F. AND FUJIWARA, H. 1985. A neutral netlist of 10 combinational benchmark circuits and target translator in Fortran. IEEE International Symposium on Circuits and Systems. IEEE, New York.
• 20: BROLEZ, F., BRYAN, D., AND KOZMINSKL K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedmgs of the 1989 IEEE International Symposium on Circmts and Systems IEEE, New York.
• 21: Jack Vedder Briner, Jr. , Gershon Kedem , John L. Ellis, Parallel mixed-level simulation of digital circuits using virtual time, 1990
• 22: BRINER, J. V., JR. 1988. A framework for analyzing parallel discrete event simulation. In Pro~ ceedings of the Computer Measurement Group. CMG, Dallas, Tex., 180-185.
• 23: BRINER, J. V., JR., ELLIS, J. L., AND KEDEM, G. 1988 Taking advantage of optimal on-chip parallelism for parallel discrete event simulation. In Proceedings of the IEEE InternatLonal Conference on Computer-Aided Design. IEEE, New York, 312 315.
• 24: 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]
• 25: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 26: 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]
• 27: CHAMBERLAIN, R. D. AND FRANKLIN, M. A. 1991. Analysis of parallel mixed-mode simulation algomthms. In Proceedzngs of the 5th International Parallel Processing Sympostum. IEEE, New York, 155-160.
• 28: Roger D. Chamberlain , Mark A. Franklin, Hierarchical Discrete-Event Simulation on Hypercube Architectures, IEEE Micro, v.10 n.4, p.10-20, July 1990 [doi>10.1109/40.57727]
• 29: CHAMBERLAIN, R. D. AND FRANKLIN, M. A. 1988. Discrete-event simulation on hypercube architectures. In Proceedings of the 1988 IEEE International CoTzference on Computer-Aided Destgn. IEEE, New York, 272 275.
• 30: CHAMBERLAIN, R. D. AND FRANKLIN, M. A. 1986. Collecting data about logic simulation. IEEE Trans. Comput. Azded Des. Integr. Circ. Syst. CAD-5, 3 (July), 405-412.
• 31: Roger D. Chamberlain , Cheryl D. Henderson, Evaluating the use of pre-simulation in VLSI circuit partitioning, Proceedings of the eighth workshop on Parallel and distributed simulation, p.139-146, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 32: 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]
• 33: Moon Jung Chung , Yunmo Chung, Efficient parallel logic simulation techniques for the connection machine, Proceedings of the 1990 conference on Supercomputing, p.606-614, October 1990, New York, New York, United States
• 34: M. J. Chung , Y. Chung, Data parallel simulation using time-warp on the connection machine, Proceedings of the 26th ACM/IEEE conference on Design automation, p.98-103, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74400]
• 35: DAVOREN, M. 1989. A structural mapping for parallel digital logic simulation. In Proceedings of the SCS Multiconference on Distributed Stmulatwn. SCS, San Diego, Calif., 179 182.
• 36: DEY, S., BRGLEZ, F., AND KEDEM, G. 1990. Corolla based circuit partitioning and application to logic synthesis. Tech. Rep. TR90-40, MCNC Research Triangle Park, N.C.
• 37: DENNEAU, M., KRONSTADT, E., AND PFISTER, G. 1983. Design and implementation of a software simulation engine. Comput. Aided Des. 15, 3 (May), 123-130.
• 38: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 39: FLYNN, M. J. 1966. Very high-speed computing systems. Prec. IEEE 54, 1901 1909.
• 40: 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
• 41: Edward Harrison Frank, A data-driven multiprocessor for switch-level simulation of vlsi circuits, 1985
• 42: 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]
• 43: Richard M. Fujimoto, Time warp on a shared memory multiprocessor, Transactions of the Society for Computer Simulation International, v.6 n.3, p.211-239, Jul. 1989
• 44: GAFNI, A. 1988. Rollback mechanisms for optimistic distributed simulation. In Proceedings of the SCS Mult~conference on D~str~buted Simulation. SCS, San Diego, Calif., 61-67.
• 45: GOERINC, R. 1988. Simulation accelerators used in CAD. Comput. Des. (Mar. 15).
• 46: Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977 [doi>10.1145/356698.356700]
• 47: HAHN, W. 1989. The Munich simulation computer: Design principles and performance prediction. In {-1-arclware Accelerators for Electrtcal CAD, T. Ambler, P. Agrawal, and W. Moore, Eds. Adam Hilger, Bristol, U.K.
• 48: W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
• 49: 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]
• 50: JUN, Y.-H., HA J J, I. N., LEE, S.-H., AND PARK, S.-B. 1990. High speed VLSI logic simulation using bitwise operations and parallel processing. In Proceedings of the IEEE International Conference on Computer Design. IEEE, New York, 171-174.
• 51: KERNIGHAN, B. W. AND LIN, S. 1970 An efficient heuristm procedure for partitioning graphs. Bell Syst. Tech. J. 49, 2, 291 307.
• 52: Hong K. Kim , Soon Myoung Chung, Parallel Logic Simulation Using Time Warp on Shared-Memory Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.942-948, April 01, 1994
• 53: KRAVITZ, S. A. AND ACKLAND, B. D. 1988. Static vs. dynamic partitioning of circuits for a MOS timing sinqulator on a message-based processor. In Proceedings of the SCS Multwonference on D~stributed Simulation. SCS, San Diego, Calii:, 136-140.
• 54: KRAV~TZ, S. A., BRYANT, R. E., AND RUTENBAR, R. A. 1991. Massively parallel switch-level simulation: A ibasibility study. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 10, 7, 871 894.
• 55: LEVENDEL, Y. H., MENON, P. R., AND PATEL, S. H. 1982. Special-purpose computer for logic simulation using distributed processing. Bell Syst. Tech. J. 61, 10, 2873 2909.
• 56: LEWIS, D.M. 1991. A hierarchical compiled code event-driven simulator. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 10, 6 (June), 726-737.
• 57: LIN, Y.-B. AND LAZOWSKA, E.D. 1991. Processor scheduling for Time Warp parallel simulation. In Proceedings of the SCS Multiconference on Dzstrtbuted S~mulation. SCS, San Diego, Calif., 11 14.
• 58: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 59: A. Mahmood , W. I. Baker , J. Herath , A. Jayasumana, A logic simulation engine based on a modified data flow architecture, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.377-380, November 1992, Santa Clara, California, United States
• 60: Naraig Manjikian , Wayne M. Loucks, High performance parallel logic simulations on a network of workstations, Proceedings of the seventh workshop on Parallel and distributed simulation, p.76-84, May 16-19, 1993, San Diego, California, United States
• 61: MAURER, P. M. AND LEE, Y.S. 1994. Gateways: A technique for adding event-driven behavior to compiled simulations. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 13, 3 (Mar.), 338 352.
• 62: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 63: R. B. Mueller-Thurns , D. G. Saab , J. A. Abraham, Design of a scalable parallel switch-level simulator for VLSI, Proceedings of the 1990 conference on Supercomputing, p.615-624, October 1990, New York, New York, United States
• 64: MUELLER-THUNS, R. B., SAAB, D. G., DAMIANO, R. F., AND ABRAHAM, J. A. 1993. VLSI logic and fault simulation on general-purpose parallel computers. IEEE Trans. Comput. Aided Des. Integr. Czrc. Syst. 12, 3 (Mar.), 446 460.
• 65: Biswajit Nandy , Wayne M. Loucks, On a parallel partitioning technique for use with conservative parallel simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.43-51, May 16-19, 1993, San Diego, California, United States
• 66: NANDY, B. AND LOUCKS, W. M. 1992. An algorithm for pamtionmg and mapping conservative parallel mmulation onto multicomputers. In Proceedings of the 6th Workshop on Parallel and D~str~buted S~mulation. SCS, 139-146.
• 67: N~COL, D. M AND REYNOLDS, P. R., JR. 1985 A statistical approach to dynamic partitioning In Proceedings of the SCS Multtconferenee on Distributed Simulation SCS, San Diego, Calif', 53-56
• 68: PF~STER, G. F 1986. The IBM Yorktown simulation engine. Proe. IEEE 74, 6 (June), 850 860.
• 69: Minoru Saitoh , Kenji Iwata , Akiko Nokamura , Makoto Kakegawa , Junichi Masuda , Hirofumi Hamamura , Fumiyasu Hirose , Nobuaki Kawato, Logic simulation system using simulation processor (SP), Proceedings of the 25th ACM/IEEE conference on Design automation, p.225-230, June 12-15, 1988, Atlantic City, New Jersey, United States
• 70: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
• 71: Emily J. Shriver , Karem A. Sakallah, Ravel: assigned-delay compiled-code logic simulation, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.364-368, November 1992, Santa Clara, California, United States
• 72: 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
• 73: SMITH, S. P., UNDERWOOD, B., AND MERCER, M. R. 1987. An analysis of several approaches to circuit partitioning for parallel logic simulation. In Proceedings of the 1987 International Conference on Computer Design. IEEE, New York, 664-667.
• 74: ~MITH, ~. P., UNDERWOOD, B., AND NEWI~IAN, J. 1988. An analysis of parallel logic simulation on several architectures. In Proceedings of the 1988 Internattonal Conference on Parallel Processzng. Penn State University Press, University Park, Pa., 65-68.
• 75: SOKOL, L. M., BmscoE, D. P, AND WIELAND, A. P 1988. MTW: A strategy for scheduling discrete simulation events for concurrent execution. In Proceedings of the SCS Multtconference on Dzstr,buted S~mulatmn SCS, San Diego, Calif., 34-42.
• 76: Lawrence Peter Soule , Anoop Gupta, Parallel logic simulation: an evaluation of centralized-time and distributed-time algorithms, 1992
• 77: 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
• 78: 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]
• 79: SOUI,E, L. AND GUPTA, A. 1992 An evaluatmn of the Chandy-Misra-Bryant algorithm for digital logic simulatmn In Proceedings of the 6th Workshop on Parallel and D~stributed Szmulation. SCS, 129 138.
• 80: 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
• 81: Su, W -K. AND SE~TZ, C.L. 1989. Variants of the Chandy-Misra-Bryant distributed discreteevent simulation algorithm. In Proceedings of' the SCS Multzconference on D~strzbuted Szmulatmn. SCS, San Diego, Cahf., 38 43.
• 82: K. Subramanian , M. R. Zargham, Distributed and parallel demand driven logic simulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.485-490, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123348]
• 83: Shigeru Takasaki , Tohru Sasaki , Nobuyoshi Nomizu , Hiroshi Ishikura , Nobuhiko Koike, HAL II: a mixed level hardware logic simulation system, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.581-587, July 1986, Las Vegas, Nevada, United States
• 84: TERMAN, C.J. 1983 Simulation tools for digital LSI design. Ph.D thesis, Massachusetts Institute of Technology, Cambridge, Mass
• 85: K. Wong , M. A. Franklin, Performance analysis and design of a logic simulation machine, Proceedings of the 14th annual international symposium on Computer architecture, p.46-55, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30356]
• 86: WONG~ K. AND FRANIiLIN1 M A. 1987b. Load and communications balancing on multiprocessor logic simulation engines In Hardware Accelerators for Electrical CAD, T. Ambler and W. Moore, Eds. Adam Hilger, Bristol, UK.
• 87: 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.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed; Parallel; Discrete event

General Terms:
Algorithms, Experimentation, Performance

Keywords:
circuit structure, parallel architecture, parallelism, partitioning, synchronization algorithm, timing granularity