Article

A Multi-State Q-Learning Approach for the Dynamic Load Balancing of Time Warp

Authors:

Carl TropperAuthors Info & Claims

PADS '10: Proceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation

Pages 142 - 149

https://doi.org/10.1109/PADS.2010.5471661

Published: 17 May 2010 Publication History

Abstract

In this paper, we present a dynamic load-balancing algorithm for optimistic gate level simulation making use of a machine learning approach. We first introduce two dynamic load-balancing algorithms oriented towards balancing the computational and communication load respectively in a Time Warp simulator. In addition, we utilize a multi-state Q-learning approach to create an algorithm which is a combination of the first two algorithms. The Q-learning algorithm determines the value of three important parameters- the number of processors which participate in the algorithm, the load which is exchanged during its execution and the type of load-balancing algorithm. We investigate the algorithm on gate level simulations of several open source VLSI circuits.

References

[1]

Elie El Ajaltouni, Azzedine Boukerche, and Ming Zhang. An efficient dynamic load balancing scheme for distributed simulations on a grid infrastructure. In DS-RT'08: Proceedings of the 2008 12th IEEE/ACM International Symposium on Distributed Simulation and Real-Time Applications, pages 61-68, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[2]

Shailendra S. Aote and M. U. Kharat. A game-theoretic model for dynamic load balancing in distributed systems. In ICAC3'09: Proceedings of the International Conference on Advances in Computing, Communication and Control, pages 235-238, New York, NY, USA, 2009. ACM.

Digital Library

[3]

Hervé Avril and Carl Tropper. Clustered time warp and logic simulation. SIGSIM Simul. Dig., 25(1):112-119, 1995.

Digital Library

[4]

Hervé Avril and Carl Tropper. The dynamic load balancing of clustered time warp for logic simulation. SIGSIM Simul. Dig., 26(1):20-27, 1996.

Digital Library

[5]

Yi bing Lin and Paul A. Fishwick. Asynchronous parallel discrete event simulation. IEEE Transactions on Systems, Man and Cybernetics, 26, 1996.

Digital Library

[6]

J. G. Carbonell, editor. Machine learning: paradigms and methods. Elsevier North-Holland, Inc., New York, NY, USA, 1990.

Digital Library

[7]

Richard M. Fujimoto. Parallel and Distribution Simulation Systems. John Wiley & Sons, Inc., New York, NY, USA, 1999.

Digital Library

[8]

Harold Gabow and Robert Tarjan. Almost-optimum speed-ups of algorithms for bipartite matching and related problems. In STOC'88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 514-527, New York, NY, USA, 1988. ACM.

Digital Library

[9]

David R. Jefferson. Virtual time. ACM Trans. Program. Lang. Syst., 7(3):404-425, 1985.

Digital Library

[10]

Lijun Li, Hai Huang, and Carl Tropper. Dvs: An object-oriented framework for distributed verilog simulation. In PADS'03: Proceedings of the seventeenth workshop on Parallel and distributed simulation, page 173, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[11]

Sina Meraji, Wei Zhang, and Carl Tropper. On the scalability of parallel verilog simulation. In THE 38th INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING (ICPP-2009), pages 1064-1069, 2005.

Digital Library

[12]

Silvano Mignanti, Alessandro Di Giorgio, and Vincenzo Suraci. A model based rl admission control algorithm for next generation networks. Next Generation Mobile Applications, Services and Technologies, International Conference on, 0:303-308, 2008.

Digital Library

[13]

Gordon E. Moore. Cramming more components onto integrated circuits. pages 56-59, 2000.

Digital Library

[14]

mpi. Message Passing Interface. http://www-unix.mcs.anl.gov/mpi/, Accessed on January 2009.

[15]

Samir Palnitkar. Verilog®hdl: a guide to digital design and synthesis, second edition. Prentice Hall Press, Upper Saddle River, NJ, USA, 2003.

Digital Library

[16]

Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the art. Autonomous Agents and Multi-Agent Systems, 11(3):387-434, 2005.

Digital Library

[17]

Rolf Schlagenhaft, Martin Ruhwandl, Christian Sporrer, and Herbert Bauer. Dynamic load balancing of a multi-cluster simulator on a network of workstations. SIGSIM Simul. Dig., 25(1):175-180, 1995.

Digital Library

[18]

R. Sutton and A. G. Barto. Reinforcement Learning: an introduction. The MIT Press, 2003.

Digital Library

[19]

Xiaonian Tong and Wanneng Shu. An efficient dynamic load balancing scheme for heterogenous processing system. Computational Intelligence and Natural Computing, International Conference on, 2:319-322, 2009.

Digital Library

[20]

Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279-292, 1992.

Digital Library

[21]

Qing XU and Carl Tropper. Xtw, a parallel and distributed logic simulator. In ASP-DAC'05: Proceedings of the 2005 conference on Asia South Pacific design automation, pages 1064-1069, New York, NY, USA, 2005. ACM.

Digital Library

[22]

BaoYin Zhang, ZeYao Mo, GuangWen Yang, and WeiMin Zheng. Dynamic load balancing efficiently in a large scale cluster. Int. J. High Perform. Comput. Netw., 6(2):100-105, 2009.

Digital Library

Cited By

Marotta RMontesano FQuaglia F(2023)Effective Access to the Committed Global State in Speculative Parallel Discrete Event Simulation on Multi-core MachinesProceedings of the 2023 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3573900.3591117(107-117)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3573900.3591117
Helms TReinhardt OUhrmacher ADiallo STolk A(2015)Bayesian changepoint detection for generic adaptive simulation algorithmsProceedings of the 48th Annual Simulation Symposium10.5555/2876341.2876350(62-69)Online publication date: 12-Apr-2015
https://dl.acm.org/doi/10.5555/2876341.2876350
de Carvalho EJunqueira MMoreira ECarpinteiro ODe Rango FRisco Martín JCetinkaya D(2015)An analysis on the metrics for dynamic process scheduling on distributed simulation using optimistic protocolsProceedings of the Conference on Summer Computer Simulation10.5555/2874916.2874958(1-8)Online publication date: 26-Jul-2015
https://dl.acm.org/doi/10.5555/2874916.2874958
Show More Cited By

Recommendations

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

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 ...
On Process Migration and Load Balancing in Time Warp

A load balancing algorithm for a discrete event simulation executed under Time Warp ispresented. The algorithm rests upon recent developments in active process migration,which permit the use of dynamic strategies. Dynamic load balancing allows ...
Dynamic Load-Balancing for BSP Time Warp
SS '02: Proceedings of the 35th Annual Simulation Symposium

The performance of a parallel simulation system depends very much on partitioning simulation workload evenly among the set of processors in the computing environment to ensure load-balance between processors. Most parallel simulation systems employ user-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PADS '10: Proceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation

May 2010

164 pages

ISBN:9781424472925

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

IEEE Computer Society

United States

Publication History

Published: 17 May 2010

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
97
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Marotta RMontesano FQuaglia F(2023)Effective Access to the Committed Global State in Speculative Parallel Discrete Event Simulation on Multi-core MachinesProceedings of the 2023 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3573900.3591117(107-117)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3573900.3591117
Helms TReinhardt OUhrmacher ADiallo STolk A(2015)Bayesian changepoint detection for generic adaptive simulation algorithmsProceedings of the 48th Annual Simulation Symposium10.5555/2876341.2876350(62-69)Online publication date: 12-Apr-2015
https://dl.acm.org/doi/10.5555/2876341.2876350
de Carvalho EJunqueira MMoreira ECarpinteiro ODe Rango FRisco Martín JCetinkaya D(2015)An analysis on the metrics for dynamic process scheduling on distributed simulation using optimistic protocolsProceedings of the Conference on Summer Computer Simulation10.5555/2874916.2874958(1-8)Online publication date: 26-Jul-2015
https://dl.acm.org/doi/10.5555/2874916.2874958
Solar RGil-Costa VMarin MDe Rango FRisco Martín JCetinkaya D(2015)Dynamic load balance for approximate parallel simulations with consistent hashingProceedings of the Conference on Summer Computer Simulation10.5555/2874916.2874934(1-10)Online publication date: 26-Jul-2015
https://dl.acm.org/doi/10.5555/2874916.2874934
Helms TEwald RRybacki SUhrmacher A(2015)Automatic Runtime Adaptation for Component-Based Simulation AlgorithmsACM Transactions on Modeling and Computer Simulation10.1145/282150926:1(1-24)Online publication date: 19-Oct-2015
https://dl.acm.org/doi/10.1145/2821509
Wienß JStein MEwald RHimmelspach JVanmechelen KCai W(2013)Evaluating simulation software components with player rating systemsProceedings of the 6th International ICST Conference on Simulation Tools and Techniques10.5555/2512734.2512740(41-50)Online publication date: 5-Mar-2013
https://dl.acm.org/doi/10.5555/2512734.2512740
Helms TEwald RRybacki SUhrmacher ALoper MWainer G(2013)A generic adaptive simulation algorithm for component-based simulation systemsProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486095(11-22)Online publication date: 19-May-2013
https://dl.acm.org/doi/10.1145/2486092.2486095
Vitali RPellegrini AQuaglia F(2012)Towards Symmetric Multi-threaded Optimistic Simulation KernelsProceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2012.46(211-220)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1109/PADS.2012.46
Peluso SDidona DQuaglia F(2011)Application Transparent Migration of Simulation Objects with Generic Memory LayoutProceedings of the 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2011.5936755(1-9)Online publication date: 14-Jun-2011
https://dl.acm.org/doi/10.1109/PADS.2011.5936755
Chen LLu YYao YPeng SWu L(2011)A Well-Balanced Time Warp System on Multi-Core EnvironmentsProceedings of the 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2011.5936752(1-9)Online publication date: 14-Jun-2011
https://dl.acm.org/doi/10.1109/PADS.2011.5936752

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents