Load-balancing spatially located computations using rectangular partitions

DOI10.1016/J.JPDC.2012.05.013zbMATH Open1248.68101OpenAlexW1982869108MaRDI QIDQ455987FDOQ455987

Authors Erik Saule, Erdeniz Ö. Baş, Ümit V. Çatalyürek 

Publication date 23 October 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.2566

zbMATH Keywords

heuristicsdynamic programmingload balancingoptimal algorithmsparticle-in-cellspatial partitioninghierarchical partitioningjagged partitioningmesh-based computationrectilinear partitioning

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14)

Abstract: Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoff.

Recommendations

• scientific article; zbMATH DE number 1215254
• Parallel load balancing for problems with good bisectors
• One-dimensional partitioning for heterogeneous systems: theory and practice
• Optimal equi-partition of rectangular domains for parallel computation
• Fast optimal load balancing algorithms for 1D partitioning

Cites work

• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• scientific article; zbMATH DE number 1405506 (Why is no real title available?)
• A New Approximation Algorithm for Multidimensional Rectangle Tiling
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
• Approximation algorithms for array partitioning problems
• Approximations for the general block distribution of a matrix
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Distributed processing of very large datasets with DataCutter
• Efficient partitioning of sequences
• Fast optimal load balancing algorithms for 1D partitioning
• Graph partitioning models for parallel computing
• Image-space decomposition algorithms for sort-first parallel volume rendering of unstructured grids
• Mapping a chain task to chained processors
• One-dimensional partitioning for heterogeneous systems: theory and practice

Cited in

(6)

• Improving unstructured mesh partitions for multiple criteria using mesh adjacencies
• The plasma simulation code: a modern particle-in-cell code with patch-based load-balancing
• One-dimensional partitioning for heterogeneous systems: theory and practice
• Auto-balancing algorithm for parallel SPH simulation of materials in extremes
• Fast optimal load balancing algorithms for 1D partitioning
• On Symmetric Rectilinear Partitioning

Describes a project that uses

Uses Software

• CHARM++
• DataCutter
• DAGuE

This page was built for publication: Load-balancing spatially located computations using rectangular partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q455987)