Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

On the scalability and dynamic load-balancing of optimistic gate level simulation

Published: 01 September 2010 Publication History

Abstract

As proscribed by Moore's law, the size of integrated circuits has grown geometrically, resulting in simulation becoming the major bottleneck in the circuit design process. Parallel simulation provides us with a way to cope with this growth. In this paper, we describe an optimistic (time warp) parallel discrete event simulator which can simulate all synthesizeable Verilog circuits. We investigate its scalability and describe a machine learning based dynamic load balancing algorithm for use with the simulator. We initially developed two dynamic load balancing algorithms to balance the load and the communication, respectively, during the course of a simulation. Making use of reinforcement learning (RL), we then created an algorithm which is an amalgam of these two algorithms. To the best of our knowledge, this is the first time that RL has been used for the dynamic load-balancing of time warp. We investigated the scalability and the effectiveness of the dynamic load balancing algorithms on gate level simulations of several realistic very large scale integration (VLSI) circuits. Our experimental results showed that our simulator is indeed scalable. They also reveled a 88.6% improvement in the simulation time through the use of our RL algorithm.

References

[1]
S. Meraji, W. Zhang, and C. Tropper, "On the scalability of parallel verilog simulation," in Proc. 38th ICPP, Vienna, Austria, 2009, pp. 365- 370.
[2]
H. Avril and C. Tropper, "Clustered time warp and logic simulation," SIGSIM Simul. Dig., vol. 25, no. 1, pp. 112-119, 1995.
[3]
H. Avril and C. Tropper, "The dynamic load balancing of clustered time warp for logic simulation," SIGSIM Simul. Dig., vol. 26, no. 1, pp. 20- 27, 1996.
[4]
D. R. Jefferson, "Virtual time," ACM Trans. Program. Lang. Syst., vol. 7, no. 3, pp. 404-425, 1985.
[5]
L. P. Kaelbling, M. L. Littman, and A. W. Moore, "Reinforcement learning: A survey," J. Artif. Intell. Res., vol. 4, pp. 237-285, 1996.
[6]
L. Li, H. Huang, and C. Tropper, "DVS: An object-oriented framework for distributed verilog simulation," in Proc, 17th Workshop PADS, 2003, pp. 173-179.
[7]
Q. XU and C. Tropper, "XTW, a parallel and distributed logic simulator," in Proc. ASP-DAC, Shanghai, China, 2005, pp. 1064-1069.
[8]
S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Upper Saddle River, NJ: Prentice Hall, 2003.
[9]
R. Schlagenhaft, M. Ruhwandl, C. Sporrer, and H. Bauer, "Dynamic load balancing of a multicluster simulator on a network of workstations," SIGSIM Simul. Dig., vol. 25, no. 1, pp. 175-180, 1995.
[10]
G. E. Moore, "Cramming more components onto integrated circuits," Readings in Computer Architecture. 2000, pp. 56-59.
[11]
B. Cohen, VHDL Coding Styles and Methodologies. Norwell, MA: Kluwer Academic, 1995.
[12]
S. Palnitkar, Verilog® hdl: A Guide to Digital Design and Synthesis, 2nd ed. Englewood Cliffs, NJ: Prentice Hall, 2003.
[13]
R. M. Fujimoto, Parallel and Distribution Simulation Systems. New York: Wiley, 1999.
[14]
Y. Lin and P. A. Fishwick, "Asynchronous parallel discrete event simulation," IEEE Trans. Syst. Man Cybernet., vol. 26, no. 4, pp. 397- 412, Jul. 1996.
[15]
S. Meraji, W. Zhang, and C. Tropper, "On the scalability and dynamic load-balancing of parallel verilog simulations," in Proc. WSC, Austin, TX, 2009, pp. 1366-1374.
[16]
D. E. Martin, R. Radhakrishnan, D. M. Rao, M. Chetlur, K. Subramani, and P. A. Wilsey, "Analysis and simulation of mixed technology VLSI systems," J. Parallel Distrib. Comput., vol. 62, no. 3, pp. 468-493, 2002.
[17]
V. Krishnaswamy and P. Banerjee, "Design and implementation of an actor based parallel vhdl simulator," in Proc. 9th Workshop PADS, 1995, pp. 135-143.
[18]
D. Lungeanu and C. J. R. Shi, "Parallel and distributed VHDL simulation," in Proc. IEEE DATE, 2000, pp. 568-578.
[19]
B. Prithviraj, Parallel Algorithms for VLSI Computer-Aided Design. Englewood Cliffs, NJ: Prentice-Hall, 1994.
[20]
H. Avril and C. Tropper, "On rolling back and checkpointing in time warp," IEEE Trans. Parallel Distrib. Syst., vol. 12, no. 11, pp. 1105- 1121, Nov. 2001.
[21]
E. Ajaltouni, A. Boukerche, and M. Zhang, "An efficient dynamic load balancing scheme for distributed simulations on a grid infrastructure," in Proc. 12th IEEE/ACM Int. Symp. DS-RT, 2008, pp. 61-68.
[22]
B. Zhang, Z. Mo, G. Yang, and W. Zheng, "Dynamic load balancing efficiently in a large scale cluster," Int. J. High Perform. Comput. Netw., vol. 6, no. 2, pp. 100-105, 2009.
[23]
S. Aote and M. U. Kharat, "A game-theoretic model for dynamic load balancing in distributed systems," in Proc. ICAC3, 2009, pp. 235-238.
[24]
T. Xiaonian and S. Wanneng, "An efficient dynamic load balancing scheme for heterogenous processing system," in Proc. Int. Conf. Comput. Intell. Natural Comput., vol. 2. 2009, pp. 319-322.
[25]
S. R. Das, "Adaptive protocols for parallel discrete event simulation," in Proc 28th WSC, 1996, pp. 186-193.
[26]
S. Srinivasan and P. F. Reynolds, "NPSI adaptive synchronization algorithms for PDES," in Proc. WSC, 1995, pp. 658-665.
[27]
S. R. Das and R. M. Fujimoto, "An adaptive memory management protocol for time warp parallel simulation," in Proc. ACM SIGMETRICS, 1994, pp. 201-210.
[28]
S. R. Das, "Adaptive protocols for parallel discrete event simulation," in Proc. 28th WSC, 1996, pp. 186-193.
[29]
H. Gabow and R. Tarjan, "Almost-optimum speed-ups of algorithms for bipartite matching and related problems," in Proc. 20th Annu. ACM STOC, 1988, pp. 514-527.
[30]
R. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, MA: MIT Press, 2003.
[31]
L. Panait and S. Luke, "Cooperative multiagent learning: The state of the art," Autonomous Agents MultiAgent Syst., vol. 11, no. 3, pp. 387-434, 2005.
[32]
J. Wang and C. Tropper, "Optimizing time warp simulation with reinforcement learning techniques," in Proc. 39th WSC, 2007, pp. 577- 584.
[33]
T. Mason and D. Brown, Lex and Yacc. Sebastopol, CA: O'Reilly and Associates, 1995.
[34]
Message Passing Interface (MPI). Jan. 2009 {Online}. Available: http://www-unix.mcs.anl.gov/mpi/
[35]
H. Christopher and P. A. Wilsey, "Optimistic fossil collection for time warp simulation," in Proc. 29th HI Int. Conf. Syst. Sci., 1996, pp. 364- 372.
[36]
J. G. Carbonell, Machine Learning: Paradigms and Methods. New York: Elsevier North-Holland, Inc., 1990.

Cited By

View all
  • (2020)An Adaptive Persistence and Work-stealing Combined Algorithm for Load Balancing on Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/336421830:2(1-26)Online publication date: 20-Mar-2020
  • (2019)Optimistic Modeling and Simulation of Complex Hardware Platforms and Embedded Systems on Many-Core HPC ClustersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286001430:2(428-444)Online publication date: 1-Feb-2019
  • (2019)Parallel Stochastic Discrete Event Simulation of Calcium Dynamics in NeuronIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2017.275693016:3(1007-1019)Online publication date: 1-May-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems  Volume 29, Issue 9
September 2010
153 pages

Publisher

IEEE Press

Publication History

Published: 01 September 2010
Revised: 06 April 2010
Received: 13 November 2009

Author Tags

  1. Dynamic load-balancing
  2. dynamic load-balancing
  3. parallel circuit simulation
  4. reinforcement learning (RL)
  5. time warp
  6. verilog

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2020)An Adaptive Persistence and Work-stealing Combined Algorithm for Load Balancing on Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/336421830:2(1-26)Online publication date: 20-Mar-2020
  • (2019)Optimistic Modeling and Simulation of Complex Hardware Platforms and Embedded Systems on Many-Core HPC ClustersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286001430:2(428-444)Online publication date: 1-Feb-2019
  • (2019)Parallel Stochastic Discrete Event Simulation of Calcium Dynamics in NeuronIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2017.275693016:3(1007-1019)Online publication date: 1-May-2019
  • (2019)PSMLThe Journal of Supercomputing10.1007/s11227-018-2682-175:5(2691-2724)Online publication date: 1-May-2019
  • (2018)Adaptive Methods for Irregular Parallel Discrete Event Simulation WorkloadsProceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3200921.3200936(189-200)Online publication date: 14-May-2018
  • (2017)Optimizations for neuron time warp(NTW) for stochastic reaction-diffusion models of neuronsProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242281(1-12)Online publication date: 3-Dec-2017
  • (2017)A work-stealing based dynamic load balancing algorithm for conservative parallel discrete event simulationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242242(1-12)Online publication date: 3-Dec-2017

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media