SPAWN: An Iterative, Potentials-Based, Dynamic Scheduling and Partitioning Tool
- PDF / 1,745,256 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 0 Downloads / 221 Views
SPAWN: An Iterative, Potentials-Based, Dynamic Scheduling and Partitioning Tool Jean-Charles Papin1 Raymond Namyst3
•
Christophe Denoual2 • Laurent Colombet2
•
Received: 27 February 2017 / Accepted: 5 September 2020 Ó Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Many applications of physics modeling use regular meshes on which computations of highly variable cost over time can occur. Distributing the underlying cells over manycore architectures is a critical load balancing step that should be performed the less frequently possible. Graph partitioning tools are known to be very effective for such problems, but they exhibit scalability problems as the number of cores and the number of cells increase. We introduce a dynamic task scheduling and mesh partitioning approach inspired by physical particle interactions. Our method virtually moves cores over a 2D/3D mesh of tasks and uses a Voronoi domain decomposition to balance workload. Displacements of cores are the result of force computations using a carefully chosen pair potential. We evaluate our method against graph partitioning tools and existing task schedulers with a representative physical application, and demonstrate the relevance of our approach. Keywords Simulation Dynamic load-balancing Graph partitioning Tasks Many-core Pair potential
1 Introduction Many physics simulation applications rely on large meshes where each cell contains a few elementary computing elements (e.g. particles, finite elements) and is linked to its neighboring cells. Figure 1 illustrates the concept of mesh and neighboring dependencies. The computing cost of each cell varies with the modeled material and & Jean-Charles Papin [email protected] 1
CMLA, ENS-Cachan, 61 Avenue du Pre´sident Wilson, Cachan 94235, France
2
CEA, DAM, DIF, Arpajon 91297, France
3
Universite´ de Bordeaux, 351 cours de la Libe´ration, Talence 33405, France
123
International Journal of Parallel Programming Fig. 1 2D Mesh example. The red cell has 8 direct neighbors, 16 2ndrank neighbors and 32 3rd rank neighbors. Every cell contains a set of elementary elements (atoms, finite elements or finite difference cells)
the applied action (e.g., shock wave or distortion). Thus, distributing cells among computing units must both preserve locality of neighbors and dynamically balance computing load. Mesh partitioning can either be achieved by using generic task scheduling or graph partitioning tools. Along with specific libraries [2, 12, 19] and languages extensions [14], many languages now integrate task support in their standard, such as C??11 with its future variables concept. Tasks are generally associated with a data set and can exchange data with other tasks, allowing to define affinity criteria for a given task. Therefore, a particular attention shall be paid to the place (i.e., the computing unit) where the task will be executed. The still increasing cores-on-chip number [7] forces applications to spawn a large number of tasks so as to prevent cor
Data Loading...
