New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Partitioning of Spacially Located Computations with Rectangles

SpeakerErik Saule

Co-authorErdeniz Bas, Umit Catalyurek

In many distributed applications, the computations take place in a 2D or 3D space which is discretized into cells for parallelization purpose. At each iteration of the application, the state of each cell is updated using the state of neighbor cells in a stencil-like fashion. In applications such as particle-in-cell simulation and raycasting, the computation time required to update each cell may vary in function of well known parameters (such as the distribution of the particle in the field or the position of the objects in the scene). When distributing such applications on a parallel computer, the cells must be allocated to the processor meticulously by taking into account both the load balance between the processors and the communication time between two neighboring processors. Methods should also take into account the possible dynamic aspects of such systems. In this talk, we are proposing different algorithms to balance the load between the processors. Since the communication are induced by the locality of the operation, the communication cost are implicitely minimized by restricting our search to rectangular partitioning. We analyze existing algorithms and propose new types of decomposition. In addition to theoretical worst-case analysis, the performance of the algorithm are experimentally evaluated using real logs from a particle-in-cell simulator and sythetically generated instances.