SPAWN: An Iterative, Potentials-Based, Dynamic Scheduling and Partitioning Tool

Many applications of physics modeling use regular meshes on whichcomputations of highly variable cost over time can occur. Distributing the un-derlying cells over manycore architectures is a critical load balancing step thatshould be performed the less frequently possible. Graph partitioning tools areknown to be very effective for such problems, but they exhibit scalability prob-lems as the number of cores and the number of cells increase. We introduce adynamic task scheduling and mesh partitioning approach inspired by physicalparticle interactions. Our method virtually moves cores over a 2D/3D meshof tasks and uses a Voronoi domain decomposition to balance workload. Dis-placements of cores are the result of force computations using a carefully cho-sen pair potential. We evaluate our method against graph partitioning toolsand existing task schedulers with a representative physical application, anddemonstrate the relevance of our approach.