Dynamic Straggler Mitigation for Large-Scale Spatial Simulations

被引:0
|
作者
Bin Khunayn, Eman [1 ]
Xie, Hairuo [2 ]
Karunasekera, Shanika [2 ]
Ramamohanarao, Kotagiri [3 ]
机构
[1] King Abdulaziz City Sci & Technol KACST, Riyadh, Saudi Arabia
[2] Univ Melbourne, Melbourne, Australia
[3] Australian Acad Sci, Canberra, Australia
关键词
Spatial simulation; stragglers; BSP; load balancing; traffic simulation;
D O I
10.1145/3578933
中图分类号
TP7 [遥感技术];
学科分类号
081102 ; 0816 ; 081602 ; 083002 ; 1404 ;
摘要
Spatial simulations have been widely used to study real-world environments, such as transportation systems. Applications like prediction and analysis of transportation require the simulation to handle millions of objects while running faster than real time. Running such large-scale simulation requires high computational power, which can be provided through parallel distributed computing. Implementations of parallel distributed spatial simulations usually follow a bulk synchronous parallel (BSP) model to ensure the correctness of simulation. The processing in BSP is divided into iterations of computation and communication, running on multiple workers, followed by a global barrier synchronisation to ensure that all communications are concluded. Unfortunately, the BSP model is plagued by the straggler problem, where a delay in any worker slows down the entire simulation. Stragglers may occur for many reasons, including imbalanced workload distribution or communication and synchronisation delays. The straggler problem can become more severe with increasing parallelism and continuous change of workload distribution among workers. This article proposes methods to dynamically mitigate stragglers and tackle communication delays. The proposed strategies can rebalance the workload distribution during simulation. These methods employ the spatial properties of the simulated environments to combine a flexible synchronisation model with decentralised dynamic load balancing and on-demand resource allocation. All proposed methods are implemented and evaluated using a microscopic traffic simulator as an example of large-scale spatial simulations. We run traffic simulations for Melbourne, Beijing and New York with different straggler scenarios. Our methods significantly improve simulation performance compared to advanced methods such as global dynamic load balancing.
引用
收藏
页数:34
相关论文
共 50 条
  • [11] Large-scale dual AGN in large-scale cosmological hydrodynamical simulations
    Puerto-Sanchez, Clara
    Habouzit, Melanie
    Volonteri, Marta
    Ni, Yueying
    Foord, Adi
    Angles-Alcazar, Daniel
    Chen, Nianyi
    Guetzoyan, Paloma
    Dave, Romeel
    Di Matteo, Tiziana
    Dubois, Yohan
    Koss, Michael
    Rosas-Guevara, Yetli
    MONTHLY NOTICES OF THE ROYAL ASTRONOMICAL SOCIETY, 2025, 536 (03) : 3016 - 3040
  • [12] SPECTRAL MULTI-DOMAIN FOR LARGE-SCALE FLUID DYNAMIC SIMULATIONS
    STREETT, CL
    MACARAEG, MG
    APPLIED NUMERICAL MATHEMATICS, 1989, 6 (1-2) : 123 - 139
  • [13] Dynamic coupling of a finite element solver to large-scale atomistic simulations
    Veske, Mihkel
    Kyritsakis, Andreas
    Eimre, Kristjan
    Zadin, Vahur
    Aabloo, Alvo
    Djurabekova, Flyura
    JOURNAL OF COMPUTATIONAL PHYSICS, 2018, 367 : 279 - 294
  • [14] Gradient Coding with Dynamic Clustering for Straggler Mitigation
    Buyukates, Baturalp
    Ozfatura, Emre
    Ulukus, Sennur
    Gunduz, Deniz
    IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC 2021), 2021,
  • [15] Large-scale network simulations with GTNets
    Riley, GR
    PROCEEDINGS OF THE 2003 WINTER SIMULATION CONFERENCE, VOLS 1 AND 2, 2003, : 676 - 684
  • [16] Large-scale rigid body simulations
    Iglberger, Klaus
    Ruede, Ulrich
    MULTIBODY SYSTEM DYNAMICS, 2011, 25 (01) : 81 - 95
  • [17] Large-Scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints
    Capezzuto, Luca
    Tarapore, Danesh
    Ramchurn, Sarvapali D.
    MULTI-AGENT SYSTEMS, EUMAS 2021, 2021, 12802 : 108 - 125
  • [18] Design of large-scale parallel simulations
    Knepley, MG
    Sameh, AH
    Sarin, V
    PARALLEL COMPUTATIONAL FLUID DYNAMICS: TOWARDS TERAFLOPS, OPTIMIZATION, AND NOVEL FORMULATIONS, 2000, : 273 - 279
  • [19] LARGE-SCALE NATURAL VISION SIMULATIONS
    LOURENS, T
    PETKOV, N
    KRUIZINGA, P
    FUTURE GENERATION COMPUTER SYSTEMS, 1994, 10 (2-3) : 351 - 358
  • [20] Large-scale hybrid simulations of reconnection
    Krauss-Varban, D.
    Karimabadi, H.
    Numerical Modeling of Space Plasma Flows: Astronum-2006, 2006, 359 : 264 - 269