Distributing and Load Balancing Sparse Fluid Simulations
Distributing and Load Balancing Sparse Fluid Simulations
复制标题
DOI：
10.1111/cgf.13510
复制
发表时间：
2018-09
影响因子：
2.5
通讯作者：
Chinmayee Shah;David Hyde;Hang Qu;P. Levis
中科院分区：
文献类型：
--
作者：
Chinmayee Shah;David Hyde;Hang Qu;P. Levis
本文介绍了一种用于负载均衡稀疏流体模拟的通用算法和系统。由于计算量随模拟域和时间的变化而变化，有效地自动分布稀疏流体模拟具有挑战性。负载平衡的一个关键挑战是，最佳决策制定需要了解未来时间步长跨分区的流体分布，但是为任意模拟计算这种状态需要运行模拟本身。本文的关键观点是，可以通过并行运行推测性低分辨率模拟来预测未来的负载。我们在数学上阐述了多个时间步长的负载平衡问题，并提出了一个多项式时间算法来计算该问题的近似解。我们的实验结果表明，分布和推测性负载均衡在8个节点上的稀疏FLIP模拟将它们的速度提高了5.3倍到7.9倍，并且推测性负载均衡生成的分配执行在最优的20%以内。
This paper describes a general algorithm and a system for load balancing sparse fluid simulations. Automatically distributing sparse fluid simulations efficiently is challenging because the computational load varies across the simulation domain and time. A key challenge with load balancing is that optimal decision making requires knowing the fluid distribution across partitions for future time steps, but computing this state for an arbitrary simulation requires running the simulation itself. The key insight of this paper is that it is possible to predict future load by running a speculative low resolution simulation in parallel. We mathematically formulate the problem of load balancing over multiple time steps and present a polynomial time algorithm to compute an approximate solution to it. Our experimental results show that distributing and speculatively load balancing sparse FLIP simulations over 8 nodes speeds them up by 5.3× to 7.9×, and that speculative load balancing generates assignments that perform within 20% of optimal.