REVIEW 4 major objections 6 minor 37 references
Exploring Dynamic Load Balancing Algorithms for Block-Structured Mesh-and-Particle Simulations in AMReX
T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Painter's partition beats AMReX's load-balancing SFC in most tests.
desk verdict A genuinely useful, honest empirical comparison of load-balancing variants for AMReX, but the 'use painter's everywhere' recommendation outruns the evidence because communication cost is never measured. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the painter's partition algorithm applied to the SFC-ordered weight list: a binary search over candidate target weights, from the largest single box weight to the total weight, with a greedy feasibility check that asks whether the ordered list can be split into the available number of processors without any segment exceeding the target. This replaces AMReX's percentage-tracking heuristic, which cuts at the average and leaves the final box to the next rank, producing avoidable imbalance. The other mechanism is the Knapsack assignment, which repeatedly puts the largest remaining box on the lightest rank, and the combination algorithm that runs SFC once to assign boxes to nodes for geometric locality and then Knapsack within each node for balance.
What would settle it
Run the painter's and percentage-tracking SFC algorithms on a real AMReX mesh-and-particle application across, say, 64 to 512 ranks and compare end-to-end runtime per load-balance cycle including box redistribution; if the painter's method's higher efficiency does not produce equal or lower total wall-clock time, the paper's central performance claim fails. Alternatively, sample a workload with heavily skewed weights and show painter's efficiency falls below SFC, which would refute the 'wherever possible' recommendation.
Extended reading notes
Core claim
The central discovery is a direct algorithmic comparison: replacing the percentage-tracking bisection in AMReX's Morton SFC partitioner with a binary-search painter's partition that finds the optimal contiguous split of the SFC-ordered box list, and using Knapsack's largest-first assignment, yields near-perfect load-balance efficiency across 1 to 512 ranks at 4, 8, and 16 boxes per rank. On normally distributed weights with standard deviation 250, the painter's and Knapsack methods stay near perfect efficiency while the original SFC lags; at standard deviations 4523 and 25231 all algorithms converge toward similar efficiency, and the original SFC remains stable between about 0.8 and 0.95. The paper therefore claims painter's partitioning should be used wherever possible, and that SFC+Knapsack combination algorithms equal or slightly beat their SFC-only counterparts, while cautioning that the Knapsack step's effect on SFC's communication benefit remains unknown.
Load-bearing premise
The comparisons assume that randomly generated normally distributed box weights with standard deviations of 250, 4523, and 25231 capture real AMReX workloads, and that load-balance efficiency alone, without communication cost, is the right metric for judging an algorithm.
Editorial extensions
If this is right
- AMReX and similar block-structured frameworks can adopt painter's partition as a drop-in improvement to SFC partitioning and expect equal or better load-balance efficiency at essentially the same runtime, since all approximation algorithms finish in under a second.
- For workloads with low weight variance, Knapsack and painter's-based algorithms should be evaluated first; they approach perfect balance where percentage-tracking SFC leaves measurable inefficiency.
- SFC+Knapsack combination algorithms are viable candidates for production use and consistently reach at least the efficiency of their SFC-only counterparts.
- Brute-force load balancing remains impractical in situ beyond tiny problems, but remains useful as an offline tool to score approximation algorithms.
Reading between the lines
- A natural next test is to measure end-to-end wall-clock time on a real AMReX application, not just balance efficiency; if the additional communication from Knapsack's locality-destroying reassignments offsets the balance gain, the painter's advantage could disappear in practice, and the paper itself flags this as unknown.
- The convergence of all algorithms as weight spread grows suggests that for strongly skewed or time-varying workloads the ranking could invert, making the stable percentage-tracking SFC the safer default in those regimes.
- The painter's binary-search partitioning is not tied to Morton curves, so applying it to Hilbert or other locality-preserving orderings could combine the efficiency gain with the communication properties of those curves.
- The brute-force solver's permutation-symmetry reduction points toward a branch-and-bound or meet-in-the-middle variant that could certify approximation gaps of the fast algorithms on larger test instances.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper empirically compares dynamic load-balancing algorithms for AMReX-style block-structured mesh-and-particle simulations: a brute-force solver, AMReX's Knapsack and Morton space-filling curve (SFC) algorithms, a painter's-partition-based SFC algorithm, and a combined Knapsack+SFC algorithm organized by hardware nodes. Weight distributions are synthetic normals with three standard deviations, and the comparison uses load-balance efficiency (Eq. 1) and serial time-to-solution on up to 512 ranks. The reported results show that Knapsack and the painter's-based algorithms achieve near-perfect efficiency at low weight variance, that all approximation algorithms complete in under a second, and that the brute-force solver is practical only for very small problems. The paper recommends painter's partitioning and the combined algorithms for production consideration and provides a reproducibility artifact.
Significance. If the efficiency comparisons hold, the paper is a useful screening study: it identifies a simple, low-cost improvement to AMReX's SFC bisection and provides a reproducible artifact with 250 repeated runs per configuration, statistical shading, and honest acknowledgment of the unmeasured communication effects. The paper is less convincing as a basis for the strong prescriptive recommendations in Sections 4.2 and 5, because the metric used (load-balance efficiency) is not the quantity AMReX's SFC is designed to optimize (communication locality), and the workload model is limited to synthetic normal distributions. The main value is as an algorithm-selection starting point, not as a demonstrated end-to-end win for production simulations.
major comments (4)
- [§4.2, §5] The recommendation that painter's partitioning 'should be used wherever possible' (§4.2) and that combination algorithms 'should be evaluated for potential use in production-scale simulations' (§5) is based entirely on load-balance efficiency as defined by Eq. (1). The paper itself states in §2.3 that SFC's value is reducing communication costs via locality, and concedes in §4.2 that 'whether the effect of the knapsack step on SFC's communication improvement effects remains unknown.' Because a distribution with higher epsilon can increase halo-exchange volume or redistribution cost, the prescriptive recommendation outruns the measured evidence. Please either measure end-to-end runtime or communication volume in an AMReX application, or explicitly limit the conclusions to efficiency-only comparisons.
- [§3, §5] The workload model consists exclusively of normal distributions with mean 100000 and three standard deviations, justified in §3 as 'a realistic distribution' without supporting evidence. Real AMReX workloads can have skewed or time-varying weight distributions, and the paper's own high-standard-deviation results show the efficiency ranking compresses. The unqualified conclusion in §5 that 'combination algorithms outperform their single-algorithm counterparts' is not supported at medium and large standard deviations, where the text reports a 'collapse towards the SFC efficiencies' (§4.2). Please add skewed or application-derived weight distributions, or restrict the conclusions to the tested normal cases.
- [§2.5, Algorithm 2] Algorithm 2 cannot be implemented as written: final_map is never assigned, max_weight_across_ranks is initialized to 0 but never updated after the per-node Knapsack calls, local_boxes and knapsack_res are computed but unused, and the returned efficiency divides by max_w_across_ranks, which remains 0. The surrounding prose describes updating the maximum rank weight, but the pseudocode lacks that step. Please correct the pseudocode so that the combined algorithm's result and efficiency computation are reproducible from the paper alone.
- [§4.2, last paragraph] The statement that 'all of the painter's algorithms maintain at least a slight lead over the SFC algorithms for the entire range of differences' is immediately qualified by 'The only exception appears at the largest standard deviation,' which is internally inconsistent. Figure 5b also shows substantial overlap in the shaded standard-deviation bands. Please clarify whether the claimed lead holds across all tested distributions or only at small standard deviation, and reconcile the wording with the plotted uncertainty.
minor comments (6)
- [§2.1, Eq. (2)] Equation (2) counts the number of distribution maps checked by the first-half optimization, not the number of distinct unlabeled-rank partitions; the text calls these 'combinations,' which is potentially misleading. Please clarify the distinction.
- [Algorithm 1] The pseudocode renders 'h ← sum(weights)' and 'l ← max(weights)' with what appear to be stray minus signs ('ℎ←−𝑠𝑢𝑚'); please fix the typesetting so the assignments are unambiguous.
- [§3] The sentence 'This study uses randomly generated a distributions of weights' contains a typo and should read 'randomly generated distributions of weights.'
- [Figure 3b] Only the small-standard-deviation timing plot is shown; since the text claims the medium and high standard deviation results are 'extremely similar,' please include the maximum relative difference or show those plots in the appendix to support the claim.
- [§4.1] The sentence 'This corresponds to load balancing problems of 4 ranks and 3 boxes per rank or 2 ranks and 14 boxes per rank' is ambiguous because the two cases have very different numbers of combinations (4^12/2 versus 2^28/2). Please specify which combination count corresponds to which case.
- [References [10], [13]] The painter's partition problem is cited to informal online tutorials; consider also citing a standard algorithms textbook or a peer-reviewed treatment of the binary-search formulation.
Circularity Check
No significant circularity: the efficiency comparisons are measured against independently defined algorithms and inputs, with no fitted parameter or self-citation chain that forces the reported conclusions.
full rationale
The paper's central comparison is an empirical benchmark of load-balancing algorithms on synthetic weight distributions. The efficiency metric (Eq. 1) is defined directly from the weights and assigned loads, and each algorithm's output is measured against that metric rather than being constructed to equal it. The painter's partition algorithm is a standard binary-search procedure on the sorted SFC list; its reported advantage over AMReX's percentage-tracking SFC is an observed outcome, not an equivalence by definition. The combination algorithm is likewise an explicit composition of SFC followed by Knapsack, and its efficiency is computed from the resulting distribution map. No parameter is fitted to the test data and then renamed as a prediction. The only self-citations are to prior AMReX development and production-use papers (e.g., references [36, 37] and [12]), and these are used as background or as evidence that SFC has been successful in practice, not as a theorem that forces the present conclusions. The paper itself flags the main limitation: Section 4.2 states that 'whether the effect of the knapsack step on SFC's communication improvement effects remains unknown and can only be verified by testing on real applications,' and Section 6 lists communication performance testing as future work. That limitation weakens the practical recommendation but does not make the derivation circular. The brute-force section is a timing study, and its use as an evaluation tool is stated rather than used to define the efficiencies of the approximate algorithms. Overall, the reasoning is self-contained with respect to the claims it actually establishes: relative load-balance efficiency on the tested synthetic distributions.
Assumptions & free parameters
free parameters (8)
- normal_mean =
100000
- small_std =
250
- medium_std =
4523
- large_std =
25231
- boxes_per_rank =
4, 8, 16
- rank_limit =
512 ranks
- ranks_per_node_in_combination =
4
- brute_force_time_threshold =
20 seconds
assumptions (6)
- standard math The multiway number partitioning problem is NP-hard, so approximation algorithms are required.
- standard math The painter's binary search returns the optimal cut for a 1D contiguous partition.
- domain assumption Synthetic normal distributions are representative of real AMReX workload weights.
- domain assumption Load-balance efficiency (max load) is a sufficient proxy for simulation performance when comparing these algorithms.
- domain assumption Extracted AMReX algorithms run standalone capture the behavior of the in-situ versions.
- domain assumption The artificial 256^3 BoxArray domain provides a valid geometry for SFC ordering.
Cite this review
Pith. "Pith review of Exploring Dynamic Load Balancing Algorithms for Block-Structured Mesh-and-Particle Simulations in AMReX." pith.science (2026). https://pith.science/paper/6VFPAPPT
@misc{pith2026250515122,
author = {Pith},
title = {Pith review of: Exploring Dynamic Load Balancing Algorithms for Block-Structured Mesh-and-Particle Simulations in AMReX},
year = {2026},
howpublished = {\url{https://pith.science/paper/6VFPAPPT}},
note = {Machine review of arXiv:2505.15122}
}
read the original abstract
Load balancing is critical for successful large-scale high-performance computing (HPC) simulations. With modern supercomputers increasing in complexity and variability, dynamic load balancing is becoming more critical to use computational resources efficiently. In this study, performed during a summer collaboration at Lawrence Berkeley National Laboratory, we investigate various standard dynamic load-balancing algorithms. This includes the time evaluation of a brute-force solve for application in algorithmic evaluation, as well as quality and time evaluations of the Knapsack algorithm, an SFC algorithm, and two novel algorithms: a painter's partition-based SFC algorithm and a combination Knapsack+SFC methodology-based on hardware topology. The results suggest Knapsack and painter's partition-based algorithms should be among the first algorithms evaluated by HPC codes for cases with limited weight deviation and will perform at least slightly better than AMReX's percentage-tracking partitioning strategy across most simulations, although effects diminish as weight variety increases.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
A Abed Abud, Babak Abi, Roberto Acciarri, Mario A Acero, Márcio Rostirolla Adames, George Adamov, Mark Adamowski, David Adams, Marco Adinolfi, Cris Adriano, et al. 2023. Highly-parallelized simulation of a pixelated LArTPC on a GPU. Journal of instrumentation 18, 04 (2023), P04034
work page 2023
-
[2]
Yalçın Akçay, Haijun Li, and Susan H Xu. 2007. Greedy algorithm for the general multidimensional knapsack problem. Annals of operations research 150 (2007), 17–29
work page 2007
-
[3]
Karthik Balaguru, Wenwei Xu, Chuan-Chieh Chang, L Ruby Leung, David R Judi, Samson M Hagos, Michael F Wehner, James P Kossin, and Mingfang Ting. 2023. Increased US coastal hurricane risk under climate change. Science advances 9, 14 (2023), eadf0259
work page 2023
-
[4]
Sree Bhargavi Balija, Amitash Nanda, and Debashis Sahoo. 2024. Building communication efficient asynchronous peer-to-peer federated llms with blockchain. In Proceedings of the AAAI Symposium Series , Vol. 3. 288–292
work page 2024
-
[5]
Greg Breinholt and Christoph Schierz. 1998. Algorithm 781: Generating Hilbert’s space-filling curve by recursion.ACM Transactions on Mathematical Software (TOMS) 24, 2 (1998), 184–189
work page 1998
-
[6]
Ronak Buch. 2023. Vector load balancing for high-performance parallel applications . Ph. D. Dissertation. University of Illinois at Urbana-Champaign
work page 2023
-
[7]
James M Calvin and Joseph Y-T Leung. 2003. Average-case analysis of a greedy algorithm for the 0/1 knapsack problem. Operations Research Letters 31, 3 (2003), 202–210
work page 2003
-
[8]
Sunil Chopra and Mendu R Rao. 1993. The partition problem. Mathematical programming 59, 1 (1993), 87–115
work page 1993
Show all 37 references
-
[9]
David Clarke, Alexey Lastovetsky, and Vladimir Rychkov. 2011. Dynamic load balancing of parallel computational iterative routines on highly heterogeneous HPC platforms. Parallel Processing Letters 21, 02 (2011), 195–217
2011
-
[10]
Apna College. 2024. Painter’s Partition Problem | DSA Placement Series - Binary Search | Lecture 22. Retrieved December from https://www. youtube.com/watch?v=srsFN5OHBgw Manuscript submitted to ACM 12 Nanda, Chowdhury, Ross, Gott
2024
-
[11]
Kyla de Villa, Felipe González-Cataldo, and Burkhard Militzer. 2023. Double superionicity in icy compounds at planetary interior conditions. Nature Communications 14, 1 (2023), 7580
2023
-
[12]
Luca Fedeli, Axel Huebl, France Boillod-Cerneux, Thomas Clark, Kevin Gott, Conrad Hillairet, Stephan Jaure, Adrien Leblanc, Rémi Lehe, Andrew Myers, et al. 2022. Pushing the frontier in the design of laser-based electron accelerators with groundbreaking mesh-refined particle-i...
2022
-
[13]
GeeksforGeeks.org. 2024. The Painter’s Parition Problem - GeeksforGeeks. Retrieved December 10, 2024 from https://www.geeksforgeeks.org/ painters-partition-problem/
2024
-
[14]
Harshitha Menon Gopalakrishnan Menon. 2016. Adaptive load balancing for HPC applications . Ph. D. Dissertation. University of Illinois at Urbana-Champaign
2016
-
[15]
Daniel C Hackett, Dimitra A Pefkou, and Phiala E Shanahan. 2024. Gravitational form factors of the proton from lattice QCD. Physical Review Letters 132, 25 (2024), 251904
2024
-
[16]
Dorit S Hochba. 1997. Approximation algorithms for NP-hard problems. ACM Sigact News 28, 2 (1997), 40–52
1997
-
[17]
Thomas Ilsche, Sebastian Schrader, and Robert Schöne. 2024. Optimizing Idle Power of HPC Systems: Practical Insights and Methods. In 2024 IEEE International Conference on Cluster Computing Workshops (CLUSTER Workshops) . IEEE, 19–25
2024
-
[18]
Thomas Jakobs, Oliver Klöckner, and Gudula Rünger. 2024. Parallelization with load balancing of the weather scheme WSM7 for heterogeneous CPU-GPU platforms. The Journal of Supercomputing (2024), 1–21
2024
-
[19]
Haoqiang Jin, Dennis Jespersen, Piyush Mehrotra, Rupak Biswas, Lei Huang, and Barbara Chapman. 2011. High performance computing using MPI and OpenMP on multi-core parallel systems. Parallel Comput. 37, 9 (2011), 562–575
2011
-
[20]
Richard E Korf. 1998. A complete anytime algorithm for number partitioning. Artificial Intelligence 106, 2 (1998), 181–203
1998
-
[21]
Richard Earl Korf. 2009. Multi-way number partitioning. In Twenty-first international joint conference on artificial intelligence
2009
-
[22]
Hui Liu, Kun Wang, Bo Yang, Min Yang, Ruijian He, Lihua Shen, He Zhong, and Zhangxin Chen. 2017. Load Balancing using Hilbert Space-filling Curves for Parallel Reservoir Simulations. arXiv:1708.01365 [cs.DC] https://arxiv.org/abs/1708.01365
2017 arXiv
-
[23]
Daniele Micale, Mauro Bracconi, and Matteo Maestri. 2024. Increasing Computational Efficiency of CFD Simulations of Reactive Flows at Catalyst Surfaces through Dynamic Load Balancing. ACS Engineering Au (2024)
2024
-
[24]
Amitash Nanda, Sree Bhargavi Balija, and Debashis Sahoo. 2024. CPTQuant–A Novel Mixed Precision Post-Training Quantization Techniques for Large Language Models. arXiv preprint arXiv:2412.03599 (2024)
2024 arXiv
-
[25]
NERSC. 2025. Architecture - NERSC Documentation. Retrieved February from https://docs.nersc.gov/systems/perlmutter/architecture/
2025
-
[26]
NERSC. 2025. NERSC’s Summer Internships. Retrieved February from https://www.nersc.gov/about/work-at-nersc/internships/
2025
-
[27]
Hung H Nguyen, Vyacheslav S Bryantsev, and Claudio J Margulis. 2023. Are High-Temperature Molten Salts Reactive with Excess Electrons? Case of ZnCl2. The Journal of Physical Chemistry B 127, 42 (2023), 9155–9164
2023
-
[28]
Georgios A Pavlopoulos, Fotis A Baltoumas, Sirui Liu, Oguz Selvitopi, Antonio Pedro Camargo, Stephen Nayfach, Ariful Azad, Simon Roux, Lee Call, Natalia N Ivanova, et al. 2023. Unraveling the functional dark matter through global metagenomics. Nature 622, 7983 (2023), 594–602
2023
-
[29]
Omer Rathore, Alastair Basden, Nicholas Chancellor, and Halim Kusumaatmaja. 2024. Load Balancing For High Performance Computing Using Quantum Annealing. arXiv preprint arXiv:2403.05278 (2024)
2024 arXiv
-
[30]
Michael E Rowan, Kevin N Gott, Jack Deslippe, Axel Huebl, Maxence Thévenet, Remi Lehe, and Jean-Luc Vay. 2021. In-situ assessment of device-side compute work for dynamic load balancing in a GPU-accelerated PIC code. InProceedings of the Platform for Advanced Scientific Computi...
2021
-
[31]
Florian Schornbaum and Ulrich Rüde. 2018. Extreme-Scale Block-Structured Adaptive Mesh Refinement. SIAM Journal on Scientific Computing 40, 3 (2018), C358–C387. doi:10.1137/17M1128411 arXiv:https://doi.org/10.1137/17M1128411
2018 doi
-
[32]
TakeUForward.com. 2024. Painter’s Partition Problem - Tutorial. Retrieved December 10, 2024 from https://takeuforward.org/arrays/painters- partition-problem/
2024
-
[33]
Ahmad Tarraf, Martin Schreiber, Alberto Cascajo, Jean-Baptiste Besnard, Marc-André Vef, Dominik Huber, Sonja Happ, André Brinkmann, David E Singh, Hans-Christian Hoppe, et al. 2024. Malleability in Modern HPC Systems: Current Experiences, Challenges, and Future Opportunities. ...
2024
-
[34]
Wikipedia contributors. 2024. Uniform-machines scheduling — Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title= Uniform-machines_scheduling&oldid=1235219876 [Online; accessed 9-February-2025]
2024
-
[35]
Justyna Zawalska, Minh Chung, Katarzyna Rycerz, Laura Schulz, Martin Schulz, and Dieter Kranzlmüller. 2024. Leveraging Hybrid Classical-Quantum Methods for Efficient Load Rebalancing in HPC. In SC24-W: Workshops of the International Conference for High Performance Computing, N...
2024
-
[36]
Weiqun Zhang, Ann Almgren, Vince Beckner, John Bell, Johannes Blaschke, Cy Chan, Marcus Day, Brian Friesen, Kevin Gott, Daniel Graves, Max Katz, Andrew Myers, Tan Nguyen, Andrew Nonaka, Michele Rosso, Samuel Williams, and Michael Zingale. 2019. AMReX: a framework for block-str...
2019 doi
-
[37]
Weiqun Zhang, Andrew Myers, Kevin Gott, Ann Almgren, and John Bell. 2021. AMReX: Block-structured adaptive mesh refinement for multiphysics applications. The International Journal of High Performance Computing Applications 35, 6 (2021), 508–526. Manuscript submitted to ACM Exp...
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.