Improving conservative VHDL simulation performance by reduction of feedback

ABSTRACT

This paper describes two forms of feedback in the simulation runtime of VHDL circuits that greatly influences performance. While circuit feedback and strongly connected components have been observed and documented as detrimental influences to conservative parallel discrete event simulation (PDES) efficiency, that influence has never been quantified. Moreover, in this study, the phenomenon of induced feedback was observed to diminish speedup to the same degree as explicit feedback. In this paper the influence of feedback on simulation runtime is analyzed and an algorithm for its elimination is presented. In addition, a metric for the quantification of feedback is introduced. By measuring feedback, it is possible to balance its influence on simulation runtime with that of other factors (e.g. load balance, number of processors, machine granularity, etc. ) through the use of a cost-based partitioning approach. This paper reports significant improvements in runtime for three circuits due to the prevention of feedback using the partitioning algorithm presented. In addition, strong correlation between the feedback metric and conservative parallel simulation overhead is demonstrated.

REFERENCES

• 1: D. L. Mannix, "Distributed discrete-event simulation using variants of the chandy-misra algorithm on the intel hypercube," Master's thesis, Air Force Institute of Technology (AU), Wright-Patterson AFB, OH, December 1988. AFIT/GCS/ENG/88D-14.
• 2: R. M. Fujimoto, Parallel discrete event simulation, Proceedings of the 21st conference on Winter simulation, p.19-28, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76741]
• 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: Azzedine Boukerche , Carl Tropper, SGTNE: semi-global time of the next event algorithm, Proceedings of the ninth workshop on Parallel and distributed simulation, p.68-77, June 13-16, 1995, Lake Placid, New York, United States
• 5: 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
• 6: D. B. Wagner , E. D. Lazowska, Parallel simulation of queueing networks: limitations and potentials, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.146-155, May 1989
• 7: J. F. Hurford, "Accelerating conservative parallel vhdl simulation," Master's thesis, Air Force Institute of Technology (AU), Wright-patterson AFB, OH, December 1994. AFIT/GCS/ENG/94D-10.
• 8: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 9: T. A. Breeden, "Parallel simulation of vhdl circuits on intel hypercubes," Master's thesis, Air Force Institute of Technology (AU), Wright-Patterson AFB, OH, December 1992. AFIT/GCE/ENG/92D-1.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

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

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
parallel simulation, conservative simulation, circuit simulation