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 条
  • [21] Large-scale rigid body simulations
    Klaus Iglberger
    Ulrich Rüde
    Multibody System Dynamics, 2011, 25 : 81 - 95
  • [22] The technology of large-scale CFD simulations
    Gorobets A.V.
    Mathematical Models and Computer Simulations, 2016, 8 (6) : 660 - 670
  • [23] Fidelity in visualizing large-scale simulations
    Popescu, V
    Hoffmann, C
    COMPUTER-AIDED DESIGN, 2005, 37 (01) : 99 - 107
  • [24] Fast large-scale reionization simulations
    Thomas, Rajat M.
    Zaroubi, Saleem
    Ciardi, Benedetta
    Pawlik, Andreas H.
    Labropoulos, Panagiotis
    Jelic, Vibor
    Bernardi, Gianni
    Brentjens, Michiel A.
    de Bruyn, A. G.
    Harker, Geraint J. A.
    Koopmans, Leon V. E.
    Mellema, Garrelt
    Pandey, V. N.
    Schaye, Joop
    Yatawatta, Sarod
    MONTHLY NOTICES OF THE ROYAL ASTRONOMICAL SOCIETY, 2009, 393 (01) : 32 - 48
  • [25] Large-scale simulations of synthetic markets
    Gerardo-Giorda, Luca
    Germano, Guido
    Scalas, Enrico
    COMMUNICATIONS IN APPLIED AND INDUSTRIAL MATHEMATICS, 2015, 6 (02):
  • [26] Large-scale dark matter simulations
    Raul E. Angulo
    Oliver Hahn
    Living Reviews in Computational Astrophysics, 2022, 8 (1)
  • [27] Visualization of Large-Scale Neural Simulations
    Hernando, Juan B.
    Duelo, Carlos
    Martin, Vicente
    BRAIN-INSPIRED COMPUTING, 2014, 8603 : 184 - 197
  • [28] Temporal and spatial variability of large-scale dynamic brain networks in ASD
    Yin, Shunjie
    Sun, Shan
    Li, Jia
    Feng, Yu
    Zheng, Liqin
    Chen, Kai
    Ma, Jiwang
    Xu, Fen
    Yao, Dezhong
    Xu, Peng
    Liang, X. San
    Zhang, Tao
    EUROPEAN CHILD & ADOLESCENT PSYCHIATRY, 2025,
  • [29] Large-scale simulations on polymer melts
    Kreitmeier, S
    Wittkop, M
    Trautenberg, HL
    Holzl, T
    Goritz, D
    JOURNAL OF COMPUTATIONAL PHYSICS, 1997, 133 (01) : 181 - 185
  • [30] Efficient large-scale BGP simulations
    Dimitropoulos, Xenofontas A.
    Riley, George F.
    COMPUTER NETWORKS, 2006, 50 (12) : 2013 - 2027