Actor based parallel VHDL simulation using time warp

ABSTRACT

One of the methods used to reduce the time spent simulating VHDL designs is by parallelizing the simulation. In this paper, we describe the implementation of an object-oriented Time Warp simulator for VHDL on an actor based environment. The actor model of computation allows the exploitation of fine grained parallelism in a truly asynchronous manner and allows for the overlap of computation with communication. Some preliminary results obtained by simulating a set of multipliers and some ISCAS benchmark circuits are provided. In addition, the importance of placing processes based on circuit partitioning techniques for improving runtimes and scalability is demonstrated. Results are reported on a Sun SPARCServer 1000 and an Intel Paragon.

REFERENCES

• 1: IEEE, New York, NY, IEEE Standard VHDL Language Reference Manual, 1988,
• 2: 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]
• 3: Steven Parkes , John A. Chandy , Prithviraj Banerjee, A library-based approach to portable, parallel, object-oriented programming198383: interface, implementation, and application, Proceedings of the 1994 conference on Supercomputing, p.69-78, December 1994, Washington, D.C., United States
• 4: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 5: Jade Simulations Int. Co., "Implementation issues of Jade's VHDL simulator," tech. rep., Calgary, Alberta, Canada, 1989.
• 6: Timothy J. McBrayer , Philip A. Wilsey, Process combination to increase event granularity in parallel logic simulation, Proceedings of the 9th International Symposium on Parallel Processing, p.572-578, April 25-28, 1995
• 7: John C. Willis , Daniel P. Siewiorek, Optimizing VHDL Compilation for Parallel Simulation, IEEE Design & Test, v.9 n.3, p.42-53, July 1992 [doi>10.1109/54.156157]
• 8: 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
• 9: 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]
• 10: B. Vellandi and M. L1ghtner, "Parallelism extraction and program restructuring of VHDL for parallel simulation," in Proc. European Design Automation Conf. (EDAC-93), March 1993.
• 11: C.-P. Wen and K. Yelick, "Portable runtime support for asynchrnous simulation," in Proc. of the 1995 Int. Conf. on Parallel Processing, vol. 2, pp. ii-196- II-204, The Pennsylvania State University, 1995.
• 12: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• 13: Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
• 14: 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]
• 15: 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]
• 16: B. Ramkumar and P. Banerjee, "ProperCAD: A portable object-oriented parallel environment for VLSI CAD," IEEE Trans. Computer-Aided Design, vol. 13, pp. 829-842, July 1994.
• 17: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 18: B. Rarnkumar and P. Banerjee, "'ProperEXT: A portable parallel algorithm for VLSI circuit extraction," in International Parallel Processmg Symposium, pp. 434- 438, 1993.
• 19: Steven Parkes , Prithviraj Banerjee , Janak Patel, ProperHITEC: a portable, parallel, object-oriented approach to sequential test generation, Proceedings of the 31st annual conference on Design automation, p.717-721, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196624]
• 20: Steven Parkes , Prithviraj Banerjee , Janak Patel, A parallel algorithm for fault simulation based on PROOFS, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.616, October 02-04, 1995
• 21: Sungho Kim , Prithviraj Banerjee , Balkrishna Ramkumar , Steven Parkes , John A. Chandy, ProperPLACE: A Portable Parallel Algorithm for Standard Cell Placement, Proceedings of the 8th International Symposium on Parallel Processing, p.932-941, April 01, 1994
• 22: Kaushik De , John A. Chandy , Sumit Roy , Steven Parkes , Prithviraj Banerjee, Parallel algorithms for logic synthesis using the MIS approach, Proceedings of the 9th International Symposium on Parallel Processing, p.579-585, April 25-28, 1995
• 23: Behrokh Samadi, Distributed simulation, algorithms and performance analysis (load balancing, distributed processing), 1985
• 24: Y. B. Lin and E. D. Lazowska, "Determining the global virtual time in a distributed simulation.," in Proceedings of International Conf. on Parallel Processing, pp. 201 - 209, 1990.
• 25: Loy M. D'Souza , Xianzhi Fan , Philip A. Wilsey, pGVT: an algorithm for accurate GVT estimation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.102-109, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 26: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 27: J.G. Holm, A. Lain, and P. Banerjee, "Compilation of scientific programs into multithreaded and message driven computation," in Proceedings of the 1994 Scalable High Performance Computing Conference, (Knoxville, TN), pp. 5t8- 525, May 1994.
• 28: Y. Levendel, P. Menon, and S. Patel, "Special purpose computer for logic simulation using distributed processing," Bell System Tech. J., vol. 61, pp. 2873-2910, Dec. 1982.
• 29: E Brglez and H. Fujiwara, "A Neutral Netllst of I0 Combinational Benchmark Circuits and a Target Translator in Fortran," IEEE Intl. Symp. on Circuits and Systems, vol. 3, June 1985.
• 30: F. Brglcz, D, Bryan, and K. Kor, mln~ki, "Combinational Profiles of Sequential Benchmark Circuits," IEEE Intl. Syrup. on Circuits and Systems, pp, 1929-1934, May 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation; Hardware description languages

General Terms:
Measurement, Performance, Theory

Keywords:
Parallel Discrete Event Simulation, Time Warp, VHDL