Load balancing split tasks optimize fragment counts for many bins
Load Balancing with Item Fragmentation and More Bins than Items: Linear-Time and Exact
Data Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
Summary
This paper studies how to spread tasks of different sizes across many machines so each machine does almost the same amount of work. Tasks can be split into smaller pieces assigned to different machines, but the goal is to keep the number of pieces per machine low. The authors focus on situations where there are more machines than tasks and find a simple, fast way to perfectly balance the load with the minimal number of task pieces per machine. This work improves on previous methods and helps systems where work is repeatedly redistributed across many processors.
What this means in practice
- •For parallel computing teams: Optimally assign computational tasks to many cores in linear time, minimizing task splitting to reduce overhead and improve efficiency.
- •For distributed system operators: Rebalance workloads exactly across numerous machines to ensure near-equal load and minimal task fragmentation for better performance.
- •For cloud resource managers: Enable cloud platforms to allocate tasks to more virtual machines than jobs with minimal fragmentation, improving scaling and resource use.$Commercial implications: This allows cloud providers to sell efficient task scheduling services that reduce overhead and improve utilization in large-scale deployments.
Authors
Ben Bals, Tomáš Flouri, Kassian Kobert, Solon P. Pissis, Leen Stougie
Abstract
We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, ensuring that the loads of any two bins differ by at most one unit. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. This problem is NP-hard and there exists an $(\mathrm{OPT}+1)$-approximation algorithm that runs in $O(N \log N + B)$ time [Kobert et al., 2014]. The existing algorithm is employed by several widely used production codes for phylogenetic reconstruction. Here, we focus on the case $B \ge N$, that is, bins are at least as numerous as items. This setting arises pervasively in modern parallel and distributed systems, as well as in iterative algorithms that rebalance their workload at every step. In this context, bins are machines or machine cores, and items represent computational tasks (jobs). Our central contribution is a remarkably simple $O(N)$-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using $O(N)$ space. In particular, we prove that an optimum always exists in which every bin receives at most two fragments and provide a characterization of when one fragment per bin suffices. Our result strictly improves the $(\mathrm{OPT}+1)$-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time $(\mathrm{OPT}+1)$-approximation algorithm for the general setting, as it removes the dependency on the number $B$ of bins.