A generic adaptive simulation algorithm for component-based simulation systems

ABSTRACT

The state of a model may strongly vary during simulation, and with it also the simulation's computational demands. Adapting the simulation algorithm to these demands at runtime can therefore improve the overall performance. Although this is a general and cross-cutting concern, only few simulation systems offer re-usable support for this kind of runtime adaptation. We present a flexible and generic mechanism for the runtime adaptation of component-based simulation algorithms. It encapsulates simulation algorithms applicable to a given problem and employs reinforcement learning to explore the algorithms' suitability during a simulation run. We evaluate the approach by executing models from two modeling formalisms used in computational biology.

References

1. W. Armstrong, P. Christen, E. McCreath, and A. Rendell. Dynamic algorithm selection using reinforcement learning. In Proc. International Workshop on Integrating AI and Data Mining (AIDM'06), pages 18--25, Dec. 2006.
2. P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3):235--256, May 2002.
3. D. M. Ball and S. M. Hoyt. The adaptive Time-Warp concurrency control algorithm. In Proc. SCS Multiconference on Distributed Simulation, pages 174--177, Jan. 1990.
4. A. G. Barto and S. Mahadevan. Recent Advances in Hierarchical Reinforcement Learning. Discrete Event Dynamic Systems, 13(4):341--379, Oct. 2003.
5. A. Boukerche and S. K. Das. Dynamic load balancing strategies for conservative parallel simulations. In Proc. 11th Workshop on Parallel and Distributed Simulation (PADS'97), pages 20--28, July 1997.
6. Y. Cao, H. Li, and L. Petzold. Efficient formulation of the stochastic simulation algorithm forchemically reacting systems. The Journal of Chemical Physics, 121(9):4059--4067, Sept. 2004.
7. F. E. Cellier and E. Kofman. Continuous System Simulation. Springer, 2010.
8. S. R. Das. Adaptive Protocols for Parallel Discrete-Event Simulation. In Proc. Winter Simulation Conference (WSC'96), pages 186--193, Dec. 1996.
9. O. Decroly and A. Goldbeter. Birhythmicity, chaos, and other patterns of temporal selforganization in a multiply regulated biochemical system. In Proc. Natl. Acad. Sci. USA, pages 6917--6921, July 1982.
10. R. Ewald. Automatic Algorithm Selection for Complex Simulation Problems. PhD thesis, University of Rostock, 2010.
11. R. M. Fujimoto and M. Hybinette. Computing global virtial time in shared-memory multiprocessors. ACM Transactions on Modeling and Computer Simulation, 7(4):425--446, Oct. 1997.
12. E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Software Components. Addison-Wesley Professional, 1995.
13. M. A. Gibson and J. Bruck. Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels. The Journal of Chemical Physics, 104(9):1876--1889, Feb. 2000.
14. D. T. Gillespie. Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry, 81(25):2340--2361, Dec. 1977.
15. D. T. Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. Journal of Chemical Physics, 115(4):1716--1733, July 2001.
16. C. P. Gomes and B. Selman. Algorithm portfolios. Artificial Intelligence, 126(1--2):43--62, Feb. 2001.
17. T. Helms. Adaptive Laufzeit-Konfiguration von ML-Rules Simulationen. Master's thesis, University of Rostock, 2012.
18. T. Helms, J. Himmelspach, C. Maus, O. Röwer, J. Schützel, and A. M. Uhrmacher. Toward a language for the flexible observation of simulations. In Proc. Winter Simulation Conference (WSC'12), Dec. 2012.
19. J. Himmelspach and A. M. Uhrmacher. The event queue problem and PDEVS. In Proc. of the SpringSim '07, DEVS Integrative M&S Symposium, pages 257--264. SCS, 2007.
20. J. Himmelspach and A. M. Uhrmacher. Plug'n simulate. In Proc. 40th Annual Simulation Symposium (ANSS'07), pages 137--143, Mar. 2007.
21. M. Jeschke and R. Ewald. Large-Scale Design Space Exploration of SSA. In Proc. 6th International Conference on Computational Methods in Systems Biology (CMSB'08), pages 211--230, Oct. 2008.
22. K. Kira and L. A. Rendell. The Feature Selection Problem: Traditional Methods and a New Algorithm. In Proc. 10th National Conference on Artificial Intelligence (AAAI'92), pages 129--134, July 1992.
23. M. G. Lagoudakis, M. L. Littman, and R. E. Parr. Selecting the Right Algorithm. In Proc. 2001 AAAI Fall Symposium Series: Using Uncertainty within Computation (AAAI'01), Nov. 2001.
24. M. Lees, B. Logan, C. Dan, and G. K. Oguara, Ton andTheodoropoulos. Decision-Theoretic Throttling for Optimistic Simulationsof Multi-Agent Systems. In Proc. 9th Int'l Symp. on Distributed Simulation and Real Time Applications (DS-RT'05), pages 171--178, Oct. 2005.
25. H. Li and L. Petzold. Logarithmic Direct Method for Discrete Stochastic Simulation of Chemically Reacting Systems. Technical report, Department of Computer Science, University of California: Santa Barbara, 2006.
26. C. Maus, S. Rybacki, and A. M. Uhrmacher. Rule-based multi-level modeling of cell biological systems. BMC Systems Biology, 5(166), Oct. 2011.
27. P. K. McKinley, S. M. Sadjadi, E. P. Kasten, and B. H. C. Cheng. Composing Adaptive Software. Computer, 37(7):56--64, July 2004.
28. S. Meraji, C. Tropper, and W. Zang. A Multi-State Q-learning Approach for the Dynamic Load Balancingof Time Warp. In Proc. 24th Workshop on Principles of Advanced and Distributed Simulation (PADS'10), pages 1--8, May 2010.
29. D. M. Nicol and P. F. Reynolds Jr. Optimal Dynamic Remapping of Data Parallel Computations. IEEE Transactions on Computers, 39(2):206--219, Feb. 1990.
30. J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Transactions on Database Systems, 9(1):38--71, Mar. 1984.
31. A. C. Palaniswamy and P. A. Wilsey. Adaptive bounded time windows in an optimistically synchronized simulator. In Proc. 3rd Great Lakes Symposium on Design Automation of High Performance VLSI Systems, pages 114--118, 1993.
32. S. I. Reynolds. Decision boundary partitioning: Variable resolution model- free reinforcement learning. In Proc. 17th International Conference on Machine Learning (ICML-2000), pages 783--790, 2000.
33. S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2nd edition, 2002.
34. L. M. Sokol and B. K. Stucky. MTW: Eperimental Results for a Constrained Optimistic Scheduling Paradigm. In Distributed Simulation, volume 22, pages 169--173. SCS, Jan. 1990.
35. R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
36. J. Vermorel and M. Mohri. Multi-armed Bandit Algorithms and Empirical Evaluation. In Proc. 16th European conference on Machine Learning (ECML'05), pages 437--448, Oct. 2005.
37. R. Vitali, A. Pellegrini, and F. Quaglia. Autonomic Log/Restore for advanced optimistic simulation systems. In Proc. Int'l Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 319--327. IEEE CS, 2010.

Index Terms

• Computing methodologies

  • Machine learning

  • Modeling and simulation

    • Simulation types and techniques