Load-balancing spatially located computations using rectangular partitions

DOI10.1016/J.JPDC.2012.05.013zbMATH Open1248.68101arXiv1104.2566OpenAlexW1982869108MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)