research-article

Synchronisation for dynamic load balancing of decentralised conservative distributed simulation

Authors:

Quentin Bragard,

Anthony Ventresque,

Liam MurphyAuthors Info & Claims

SIGSIM PADS '14: Proceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

Pages 117 - 126

https://doi.org/10.1145/2601381.2601386

Published: 18 May 2014 Publication History

Abstract

Synchronisation mechanisms are essential in distributed simulation. Some systems rely on central units to control the simulation but central units are known to be bottlenecks. If we want to avoid using a central unit to optimise the simulation speed, we lose the capacity to act on the simulation at a global scale. Being able to act on the entire simulation is an important feature which allows to dynamically load-balance a distributed simulation. While some local partitioning algorithms exist, their lack of global view reduces their efficiency. Running a global partitioning algorithm without central unit requires a synchronisation of all logical processes (LPs) at the same step. The first algorithm requires the knowledge of some topological properties of the network while the second algorithm works without any requirement. The algorithms are detailed and compared against each other. An evaluation shows the benefits of using a global dynamic load-balancing for distributed simulations.

References

[1]

K. Arvind. Probabilistic clock synchronization in distributed systems. Parallel and Distributed Systems, IEEE Transactions on, 5(5): 474--487, May 1994.

Digital Library

[2]

J. W. Barrus, R. C. Waters, and D. B. Anderson. Locales and Beacons: Efficient and Precise Support For Large Multi-User Virtual Environments. In VRAIS, pages 204--213, 1996.

Digital Library

[3]

D. W. Bauer Jr., C. D. Carothers, and A. Holder. Scalable time warp on blue gene supercomputers. In PADS, pages 35--44, 2009.

Digital Library

[4]

B. Bollobás. Modern Graph Theory. Springer, Heidelberg, corrected edition, 1998.

[5]

Q. Bragard, A. Ventresque, and L. Murphy. dsumo: Towards a distributed sumo. In First SUMO conference, Berlin, Germany, 2013.

[6]

S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1-7):107--117, Apr. 1998.

Digital Library

[7]

R. Chen, X. Weng, B. He, and M. Yang. Large graph processing in the cloud. In SIGMOD, pages 1123--1126, 2010.

Digital Library

[8]

I. D. Couzin, J. Krause, N. R. Franks, and S. A. Levin. Effective leadership and decision-making in animal groups on the move. Nature, 433(7025):513--516, 2005.

[9]

K. D. Devine, E. G. Boman, R. T. Heaphy, B. A. Hendrickson, J. D. Teresco, J. Faik, J. E. Flaherty, and L. G. Gervasio. New challenges in dynamic load balancing. Applied Numerical Mathematics, 52(2{3):133--152, 2005.

Digital Library

[10]

A. Ferscha and S. K. Tripathi. Parallel and distributed simulation of discrete event systems. 1998.

[11]

R. M. Fujimoto. Parallel and distributed simulation. In WSC, pages 122--131, 1999.

Digital Library

[12]

B. Hendrickson and K. Devine. Dynamic load balancing in computational mechanics. Computer Methods in Applied Mechanics and Engineering, 184(2{4): 485--500, 2000.

[13]

S. Iqbal and G. F. Carey. Performance analysis of dynamic load balancing algorithms with variable number of processors. Journal of Parallel and Distributed Computing, 65(8):934--948, 2005.

Digital Library

[14]

D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1--13, Jan. 1977.

Digital Library

[15]

N. T. Karonis, B. Toonen, and I. Foster. Mpich-g2: A grid-enabled implementation of the message passing interface. Journal of Parallel and Distributed Computing, 63(5):551--563, 2003.

Digital Library

[16]

G. Karypis and V. Kumar. Metis - unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report, 1995.

[17]

G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96--129, 1998.

Digital Library

[18]

B. Kirk, J. Peterson, R. Stogner, and G. Carey. libmesh: a c++ library for parallel adaptive mesh refinement/coarsening simulations. Engineering with Computers, 22(3-4):237--254, 2006.

Digital Library

[19]

S. Lin, X. Cheng, and J. Lv. Micro-synchronization in conservative parallel network simulation. In PADS, pages 195--202, 2008.

Digital Library

[20]

J. Liu and R. Rong. Hierarchical composite synchronization. In PADS, pages 3--12, July 2012.

Digital Library

[21]

Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Graphlab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence (UAI), 2010.

Digital Library

[22]

E. Lusk and K. Yelick. Languages for high-productivity computing: the darpa hpcs language project. Parallel Processing Letters, 17(01), 2007.

[23]

M. R. Macedonia, M. J. Zyda, D. R. Pratt, D. P. Brutzman, and P. T. Barham. Exploiting Reality with Multicast Groups: A Network Architecture for Large-scale Virtual Environments. In IEEE Virtual Reality Annual International Symposium, 1995.

Digital Library

[24]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: A system for large-scale graph processing. In SIGMOD, pages 135--146, 2010.

Digital Library

[25]

D. L. Mills. Internet time synchronization: the network time protocol. Communications, IEEE Transactions on, 39(10): 1482--1493, 1991.

[26]

A. Montresor and M. Jelasity. Peersim: A scalable p2p simulator. In Peer-to-Peer Computing, 2009. P2P '09. IEEE Ninth International Conference on, pages 99--100, 2009.

[27]

L. Nyland, J. Prins, R. Yun, J. Hermans, H.-C. Kum, and L. Wang. Modeling dynamic load balancing in molecular dynamics to achieve scalable parallel execution. In Solving Irregularly Structured Problems in Parallel, volume 1457, pages 356--365. 1998.

Digital Library

[28]

K. Perumalla. Parallel and distributed simulation: Traditional techniques and recent advances. In WSC, pages 84--95, 2006.

Digital Library

[29]

S. Plimpton, SteveAttaway, S. Attaway, B. Hendrickson, J. Swegle, C. Vaughan, and D. Gardner. Parallel transient dynamics simulations: Algorithms for contact detection and smoothed particle hydrodynamics. J. Par. Distrib. Computing, 50:50--1, 1998.

Digital Library

[30]

P. Ramanathan, K. Shin, and R. Butler. Fault-tolerant clock synchronization in distributed systems. Computer, 23(10):33--42, Oct 1990.

Digital Library

[31]

M. Snir, S. W. Otto, D. W. Walker, J. Dongarra, and S. Huss-Lederman. MPI: The Complete Reference. MIT Press, Cambridge, MA, USA, 1995.

Digital Library

[32]

A. Steed and R. Abou-Haidar. Partitioning Crowded Virtual Environments. In VRST, pages 7--14, 2003.

Digital Library

[33]

D. J. Van Hook, S. J. Rak, and J. O. Calvin. Approaches to Relevance Filtering. In Workshop on Standards for the Interoperability of Distributed Simulations, pages 26--30, 1994.

[34]

A. Ventresque, Q. Bragard, E. S. Liu, D. Nowak, L. Murphy, G. Theodoropoulos, and J. Q. Liu. Spartsim: A space partitioning guided by road network for distributed traffic simulations. In IEEE/ACM DS-RT, 2012.

Digital Library

[35]

X. Wang, S. Turner, M. Low, and B.-P. Gan. Optimistic synchronization in hla based distributed simulation. In PADS, pages 123--130, May 2004.

Digital Library

[36]

Y. Xu and G. Tan. An offline road network partitioning solution in distributed transportation simulation. In IEEE/ACM DR-ST, pages 210--217, Oct 2012.

Digital Library

[37]

T. Zou, G. Wang, M. V. Salles, D. Bindel, A. Demers, J. Gehrke, and W. White. Making time-stepped applications tick in the cloud. In 2Nd ACM Symposium on Cloud Computing, pages 20:1--20:14, 2011.

Digital Library

Cited By

Bragard QVentresque AMurphy L(2018)Self-Balancing Decentralized Distributed Platform for Urban Traffic SimulationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.260317118:5(1190-1197)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.1109/TITS.2016.2603171
Borges FGutierrez-Milla ASuppi RLuque E(2015)Strip Partitioning for Ant Colony Parallel and Distributed Discrete-event SimulationProcedia Computer Science10.1016/j.procs.2015.05.27251:C(483-492)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.procs.2015.05.272
Bragard QVentresque AMurphy LBuckley SMiller J(2014)Global dynamic load-balancing for decentralised distributed simulationProceedings of the 2014 Winter Simulation Conference10.5555/2693848.2694321(3797-3808)Online publication date: 7-Dec-2014
https://dl.acm.org/doi/10.5555/2693848.2694321
Show More Cited By

Index Terms

Synchronisation for dynamic load balancing of decentralised conservative distributed simulation
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Discrete-event simulation
      2. Massively parallel and high-performance simulations

Recommendations

Global Virtual Time and distributed synchronization
PADS '95: Proceedings of the ninth workshop on Parallel and distributed simulation
Global Virtual Time (GVT) is the fundamental synchronization concept in optimistic simulations. It is defined as the earliest time tag within the set of unprocessed pending events in distributed simulation. A number of techniques for determining GVT ...
Global dynamic load-balancing for decentralised distributed simulation
WSC '14: Proceedings of the 2014 Winter Simulation Conference

Distributed simulations require partitioning mechanisms to operate, and the best partitioning algorithms try to load-balance the partitions. Dynamic load-balancing, i.e. re-partitioning simulation environments at run-time, becomes essential when the ...
Global Virtual Time and distributed synchronization
Global Virtual Time (GVT) is the fundamental synchronization concept in optimistic simulations. It is defined as the earliest time tag within the set of unprocessed pending events in distributed simulation. A number of techniques for determining GVT ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSIM PADS '14: Proceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

May 2014

222 pages

ISBN:9781450327947

DOI:10.1145/2601381

General Chair:
John (Drew) A. Hamilton
Mississippi State University, USA
,
Program Chairs:
George F. Riley
Georgia Institute of Technology, USA
,
Richard M. Fujimoto
Georgia Institute of Technology, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 May 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Science Foundation Ireland

Conference

SIGSIM-PADS '14

Sponsor:

SIGSIM

SIGSIM-PADS '14: SIGSIM Principles of Advanced Discrete Simulation

May 18 - 21, 2014

Colorado, Denver, USA

Acceptance Rates

SIGSIM PADS '14 Paper Acceptance Rate 19 of 33 submissions, 58%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
168
Total Downloads

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

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bragard QVentresque AMurphy L(2018)Self-Balancing Decentralized Distributed Platform for Urban Traffic SimulationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.260317118:5(1190-1197)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.1109/TITS.2016.2603171
Borges FGutierrez-Milla ASuppi RLuque E(2015)Strip Partitioning for Ant Colony Parallel and Distributed Discrete-event SimulationProcedia Computer Science10.1016/j.procs.2015.05.27251:C(483-492)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.procs.2015.05.272
Bragard QVentresque AMurphy LBuckley SMiller J(2014)Global dynamic load-balancing for decentralised distributed simulationProceedings of the 2014 Winter Simulation Conference10.5555/2693848.2694321(3797-3808)Online publication date: 7-Dec-2014
https://dl.acm.org/doi/10.5555/2693848.2694321
Bragard QVentresque AMurphy L(2014)Global dynamic load-balancing for decentralised distributed simulationProceedings of the Winter Simulation Conference 201410.1109/WSC.2014.7020207(3797-3808)Online publication date: Dec-2014
https://doi.org/10.1109/WSC.2014.7020207
Hanai MSuzumura TVentresque AShudo K(2014)An Adaptive VM Provisioning Method for Large-Scale Agent-Based Traffic Simulations on the CloudProceedings of the 2014 IEEE 6th International Conference on Cloud Computing Technology and Science10.1109/CloudCom.2014.164(130-137)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1109/CloudCom.2014.164

View Options

Get Access

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