Accelerating Distributed Graphical Fluid Simulations with Micro‐partitioning

dc.contributor.authorQu, Hangen_US
dc.contributor.authorMashayekhi, Omiden_US
dc.contributor.authorShah, Chinmayeeen_US
dc.contributor.authorLevis, Philipen_US
dc.contributor.editorBenes, Bedrich and Hauser, Helwigen_US
dc.date.accessioned2020-05-22T12:24:43Z
dc.date.available2020-05-22T12:24:43Z
dc.date.issued2020
dc.description.abstractGraphical fluid simulations are CPU‐bound. Parallelizing simulations on hundreds of cores in the computing cloud would make them faster, but requires evenly balancing load across nodes. Good load balancing depends on manual decisions from experts, which are time‐consuming and error prone, or dynamic approaches that estimate and react to future load, which are non‐deterministic and hard to debug.This paper proposes Birdshot scheduling, an automatic and purely static load balancing algorithm whose performance is close to expert decisions and reactive algorithms without their difficulty or complexity. Birdshot scheduling's key insight is to leverage the high‐latency, high‐throughput, full bisection bandwidth of cloud computing nodes. Birdshot scheduling splits the simulation domain into many micro‐partitions and statically assigns them to nodes randomly. Analytical results show that randomly assigned micro‐partitions balance load with high probability. The high‐throughput network easily handles the increased data transfers from micro‐partitions, and full bisection bandwidth allows random placement with no performance penalty. Overlapping the communications and computations of different micro‐partitions masks latency.Experiments with particle‐level set, SPH, FLIP and explicit Eulerian methods show that Birdshot scheduling speeds up simulations by a factor of 2‐3, and can out‐perform reactive scheduling algorithms. Birdshot scheduling performs within 21% of state‐of‐the‐art dynamic methods that require running a second, parallel simulation. Unlike speculative algorithms, Birdshot scheduling is purely static: it requires no controller, runtime data collection, partition migration or support for these operations from the programmer.en_US
dc.description.number1
dc.description.sectionheadersArticles
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume39
dc.identifier.doi10.1111/cgf.13809
dc.identifier.issn1467-8659
dc.identifier.pages375-388
dc.identifier.urihttps://doi.org/10.1111/cgf.13809
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13809
dc.publisher© 2020 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltden_US
dc.subjectdistributed graphics
dc.subjecthardware
dc.subjectfluid modelling
dc.subjectanimation
dc.subject• Computing methodologies → Distributed computing methodologies; Distributed simulation; Computer graphics
dc.titleAccelerating Distributed Graphical Fluid Simulations with Micro‐partitioningen_US
Files
Collections