pith. sign in

arxiv: 2606.19789 · v2 · pith:YY4WZWUMnew · submitted 2026-06-18 · 🧮 math.OC · stat.ME

Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

Shreehari Anand Bodas , Jan-Pieter Dorsman , Michel Mandjes , Liron Ravner This is my paper

Pith reviewed 2026-06-26 16:41 UTC · model grok-4.3

classification 🧮 math.OC stat.ME
keywords malleable jobscore allocationspeed-up functionsmaximum likelihood estimationMarkov decision processdynamic programmingresource allocationmulticore systems
0
0 comments X

The pith

An alternating estimation-and-control scheme learns core allocations that minimize mean response time for two classes of malleable jobs whose speed-up parameters are initially unknown.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an iterative framework that alternates between estimating unknown speed-up parameters of two observable job classes and solving the associated Markov decision process to update the allocation policy. Estimation uses a maximum likelihood approach based on state-dependent inter-departure times, with a proof of strong consistency when the allocation policy is held fixed. Two learning algorithms combine this estimation step with dynamic programming updates, and the resulting policies assign fractions of cores to each class while sharing capacity equally within a class. A sympathetic reader would care because the approach removes the need for prior knowledge of job behavior in multicore systems and still targets the long-run mean number of jobs in steady state.

Core claim

The central claim is that maximum likelihood estimation of the unknown speed-up parameters, based on observed state-dependent inter-departure times, is strongly consistent under a fixed allocation policy, and that two algorithms integrating this estimator with dynamic programming policy updates produce allocation rules that minimize the long-run mean number of jobs for malleable jobs from two observable classes.

What carries the argument

The iterative learning-and-control framework that alternates maximum likelihood estimation of speed-up parameters from inter-departure times with dynamic programming solutions of the Markov decision process for class-level core fractions.

If this is right

  • Under a fixed allocation policy the maximum likelihood estimator is strongly consistent.
  • The two proposed algorithms combine the estimation step with dynamic programming updates to adapt the policy over time.
  • Within each class cores are shared equally among active jobs while the MDP supplies the capacity split between classes.
  • The objective achieved is the long-run average number of jobs in the system under the learned policy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the consistency result holds only for fixed policies, the adaptive algorithms may require additional analysis to guarantee convergence when the policy itself changes with the estimates.
  • The framework could be tested on systems with more than two classes provided the estimation step remains identifiable.
  • Numerical experiments in the paper illustrate behavior but leave open whether the same estimator remains reliable under bursty arrivals or non-stationary workloads.

Load-bearing premise

Jobs belong to one of two observable classes, each with its own distinct speed-up function whose parameters remain constant and can be recovered from completion observations.

What would settle it

Run the system under a fixed allocation policy and check whether the maximum likelihood estimates of the speed-up parameters converge to their true values as the number of observed job completions grows.

Figures

Figures reproduced from arXiv: 2606.19789 by Jan-Pieter Dorsman, Liron Ravner, Michel Mandjes, Shreehari Anand Bodas.

Figure 1
Figure 1. Figure 1: presents the plots corresponding to Examples 2.1 and 2.2. (a) s(z; p) versus z for Example 2.1 (b) s(z; p) versus z for Example 2.2 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Departure epochs of class-1 (blue) and class-2 (red) jobs on a single timeline. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Inter-departure time of class-i jobs decomposed into sub-intervals with constant state. Following Equation (3.1), the departure rate δ (i) j,k of class-i jobs during interval k = 1, . . . , N (i) j + 1 is δ (i) j,k =    n (i) j,k µ si  φ (i) j,k; pi  , n (i) j,k > 0, 0, n (i) j,k = 0. where the per-job allocation ratio, which is the number of cores allocated per job, during interval k = 1, . . . , N (… view at source ↗
Figure 4
Figure 4. Figure 4: Visualizations for Example 1 speed-up parameters [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Visualizations for Example 2 find that this assumption is quite restrictive, and strong consistency is observed also when the policy changes during the data generation process. Leveraging this observation, in this section, we describe an alternative to Algorithm 1b, which leads to faster convergence when the speed-up parameter does not change with time. Algorithm 1b Alternative learning algorithm 1: Given:… view at source ↗
Figure 6
Figure 6. Figure 6: A demonstration of the algorithm tracking a changing speed-up parameter. [PITH_FULL_IMAGE:figures/full_fig_p022_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Visualizations for Example 3 6 Conclusion In this paper, spurred in part by emerging applications such as the training of machine learning models, we studied the problem of dynamic resource allocation in a computing system with malleable jobs whose 22 [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Visualizations for Example 4 speed-up characteristics are not fully known a priori and may vary over time. Jobs belong to one of two observable classes, each characterized by an unknown degree of parallelizability. The objective is to learn a core-allocation policy that minimizes the long-run average sojourn time. To address this problem, we developed an iterative learning-and-control framework that combin… view at source ↗
read the original abstract

We study dynamic resource allocation in a multicore computing system with a fixed number of processing cores and a stream of malleable jobs. Each job may adjust its level of parallelism during execution, allowing adaptive redistribution of resources across concurrently active jobs. Jobs belong to one of two observable classes, each characterized by a distinct speed-up function with unknown parameters. The objective is to learn a core-allocation policy that minimizes the long-run mean number of jobs in the system, equivalently the mean response time in steady state. \noindent To address this uncertainty, we develop an iterative learning-and-control framework. The system alternates between estimating the unknown speed-up parameters from observed job completions and solving the associated Markov decision process (MDP) to update the allocation policy. Within each job class, cores are shared equally among active jobs; the fraction of capacity assigned to each class is obtained from the MDP formulation of \cite{berg2017}, evaluated at the current parameter estimates. We construct a maximum likelihood estimator based on state-dependent inter-departure times and prove its strong consistency under a fixed allocation policy. We further propose two learning algorithms that combine this estimation step with dynamic programming-based policy updates, and illustrate their through numerical experiments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper studies dynamic core allocation for a stream of malleable jobs belonging to two observable classes with unknown speed-up parameters in a fixed-core multicore system. The goal is to minimize long-run mean number of jobs (equivalently mean response time) via an iterative learning-and-control scheme that alternates maximum-likelihood estimation of the speed-up parameters from state-dependent inter-departure times with dynamic-programming solution of the associated MDP (following the formulation of Berg et al. 2017) to update class-level capacity fractions. Strong consistency of the MLE is proven under a fixed allocation policy; two algorithms combining the estimator with policy updates are proposed and illustrated numerically.

Significance. If the consistency result extends to the adaptive closed-loop setting and the combined scheme converges to the optimal policy, the work would supply a concrete, implementable method for online resource allocation under parametric uncertainty, directly extending an existing MDP model to the learning case. The explicit construction of an MLE from inter-departure observations and the fixed-policy consistency proof are concrete strengths.

major comments (2)
  1. [Abstract] Abstract (third paragraph): strong consistency of the MLE is established only under a fixed allocation policy, yet the two proposed learning algorithms alternate this estimator with MDP policy updates that alter the allocation (and therefore the observation process) based on current estimates. No argument is supplied showing that consistency survives the closed-loop dependence or that the iterates converge to the optimal policy; this directly undermines the claim that the algorithms solve the original learning-and-control problem.
  2. [Abstract] Abstract (second paragraph) and description of the algorithms: the MDP is solved at each iteration using current parameter estimates, but no derivation details, error bounds, or convergence analysis for the combined estimation-control loop are provided; without these the numerical experiments cannot be used to support the central claim.
minor comments (1)
  1. [Abstract] Abstract, final sentence: the phrase 'illustrate their through numerical experiments' appears to contain a typographical omission ('their performance').

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying key limitations in the theoretical scope of our results. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (third paragraph): strong consistency of the MLE is established only under a fixed allocation policy, yet the two proposed learning algorithms alternate this estimator with MDP policy updates that alter the allocation (and therefore the observation process) based on current estimates. No argument is supplied showing that consistency survives the closed-loop dependence or that the iterates converge to the optimal policy; this directly undermines the claim that the algorithms solve the original learning-and-control problem.

    Authors: We agree that the strong consistency proof applies exclusively to a fixed allocation policy, as stated in the manuscript. The two proposed algorithms are adaptive and no argument or proof is given that consistency or convergence to optimality holds under the closed-loop dependence induced by policy updates. This is a genuine limitation. In revision we will update the abstract and introduction to state explicitly that consistency holds only for fixed policies, describe the algorithms as iterative practical schemes whose behavior is illustrated numerically, and add a discussion noting the lack of closed-loop analysis as an open question. revision: yes

  2. Referee: [Abstract] Abstract (second paragraph) and description of the algorithms: the MDP is solved at each iteration using current parameter estimates, but no derivation details, error bounds, or convergence analysis for the combined estimation-control loop are provided; without these the numerical experiments cannot be used to support the central claim.

    Authors: The MDP is solved via standard dynamic programming (value or policy iteration) applied to the current parameter estimates, following the exact formulation of Berg et al. (2017); derivation details are therefore referenced rather than repeated. We acknowledge that the manuscript supplies neither error bounds nor any convergence analysis for the joint estimation-control iteration, and that the numerical experiments therefore serve only as illustration. In revision we will expand the algorithm descriptions with implementation specifics and add an explicit statement that theoretical convergence guarantees for the combined loop are not provided. revision: yes

Circularity Check

0 steps flagged

No circularity: MLE consistency restricted to fixed policy; adaptive loop uses external observations

full rationale

The paper constructs an MLE from observed state-dependent inter-departure times and explicitly proves strong consistency only under a fixed allocation policy. The two learning algorithms alternate this estimator with MDP policy updates (sourced from external citation berg2017), but the text makes no claim that consistency extends to the closed-loop adaptive case and does not redefine any performance metric in terms of the estimator itself. Data originate from the real system rather than being fitted to the final objective, so no self-definitional, fitted-input-called-prediction, or self-citation-load-bearing reduction occurs. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on the existence of exactly two observable job classes with distinct but parametric speed-up functions whose parameters can be recovered from inter-departure times, plus standard MDP theory and MLE consistency under a fixed policy; no new entities are postulated.

free parameters (1)
  • speed-up function parameters
    Unknown parameters of the two speed-up functions are estimated from data rather than chosen by hand, but they remain the quantities the policy depends on.
axioms (2)
  • standard math Standard results on strong consistency of maximum likelihood estimators under a fixed policy
    Invoked when stating the MLE is strongly consistent (abstract).
  • domain assumption The MDP formulation of berg2017 yields the optimal class-level allocation when parameters are known
    Used to obtain the fraction of capacity assigned to each class once estimates are available.

pith-pipeline@v0.9.1-grok · 5758 in / 1557 out tokens · 26424 ms · 2026-06-26T16:41:10.935202+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 8 canonical work pages · 1 internal anchor

  1. [1]

    Validity of the single processor approach to achieving large scale computing capabilities

    Amdahl, G. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the April 18–20, 1967 Spring Joint Computer Conference, 1967

    1967

  2. [2]

    Generic uniform convergence.Econometric Theory8(2) (1992), 241–257

    Andrews, D. Generic uniform convergence.Econometric Theory8(2) (1992), 241–257

    1992

  3. [3]

    Jacinto, A

    Antunes, N., G. Jacinto, A. Pacheco, and C. Wichelhaus. Estimation of the traffic intensity in a piecewise- stationary Mt/Gt/1 queue with probing.ACM SIGMETRICS Performance Evaluation Review44(2) (2016), 3–5

    2016

  4. [4]

    Armero, C. and M. Bayarri. Bayesian prediction in M/M/1 queues.Queueing Systems15(1–4) (1994), 401– 417

    1994

  5. [5]

    Nazarathy, and P

    Asanjarani, A., Y. Nazarathy, and P. Taylor. A survey of parameter and state estimation in queues.Queueing Systems97(1) (2021), 39–80

    2021

  6. [6]

    Bhat, and J

    Basawa, I., U. Bhat, and J. Zhou. Parameter estimation using partial information with applications to queueing and related models.Statistics & Probability Letters78(12) (2008), 1375–1383

    2008

  7. [7]

    Dorsman, and M

    Berg, B., J. Dorsman, and M. Harchol-Balter. Towards optimality in parallel scheduling.Proceedings of the ACM on Measurement and Analysis of Computing Systems1(2) (2017), 1–30

    2017

  8. [8]

    Vesilo, and M

    Berg, B., R. Vesilo, and M. Harchol-Balter. heSRPT: Parallel scheduling to minimize mean slowdown.Per- formance Evaluation146 (2020), 102147

    2020

  9. [9]

    PhD thesis, Carnegie Mellon University, 2022

    Berg, B.A Principled Approach to Parallel Job Scheduling. PhD thesis, Carnegie Mellon University, 2022

    2022

  10. [10]

    Moseley, W

    Berg, B., B. Moseley, W. Wang, and M. Harchol-Balter. Asymptotically optimal scheduling of multiple parallelizable job classes.arXiv preprint arXiv:2404.00346, 2024

    work page arXiv 2024

  11. [11]

    Mandjes, and L

    Bodas, S., M. Mandjes, and L. Ravner. Statistical inference for a service system with non-stationary arrivals and unobserved balking.arXiv preprint arXiv:2311.16884, 2023

    work page arXiv 2023

  12. [12]

    Cao, Y., H. Sun, D. Qian, and W. Wu. Scalable hierarchical scheduling for malleable parallel jobs on multiprocessor-based systems.arXiv preprint arXiv:1412.4213, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  13. [13]

    Georgiou, O

    Cera, M., Y. Georgiou, O. Richard, N. Maillard, and P. Navaux. Supporting malleability in parallel architec- tures with dynamic CPUSETs mapping and dynamic MPI. InProceedings of the International Conference on Distributed Computing and Networking, Springer, 2010

    2010

  14. [14]

    Chauhan, N., N. Kaur, K. Saini, S. Verma, A. Alabdulatif, R. Khurma, M. Garcia-Arenas, and P. Castillo. A systematic literature review on task allocation and performance management techniques in cloud data centers.arXiv preprint arXiv:2402.13135, 2024

    work page arXiv 2024

  15. [15]

    Kella, and G

    Chen, H., O. Kella, and G. Weiss. Fluid approximations for a processor-sharing queue.Queueing Systems 27(1–2) (1997), 99–125

    1997

  16. [16]

    Cirne, W. and F. Berman. A model for moldable supercomputer jobs. InProceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS), 2001

    2001

  17. [17]

    Cirne, W. and F. Berman. Using moldability to improve the performance of supercomputer jobs.Journal of Parallel and Distributed Computing62(10) (2002), 1571–1601

    2002

  18. [18]

    Zhang, Y

    Lian, J., X. Zhang, Y. Shao, Z. Pu, Q. Xiang, Y. Li, and B. Cui. ContTune: Continuous tuning by conservative Bayesian optimization for distributed stream data processing systems.arXiv preprint arXiv:2309.12239, 2023

    work page arXiv 2023

  19. [19]

    Delimitrou, C. and C. Kozyrakis. Quasar: Resource-efficient and QoS-aware cluster management.ACM SIGPLAN Notices49(4) (2014), 127–144

    2014

  20. [20]

    Scheduling in the dark.Theoretical Computer Science235(1) (2000), 109–141

    Edmonds, J. Scheduling in the dark.Theoretical Computer Science235(1) (2000), 109–141. 24

    2000

  21. [21]

    Wehrstedt, L

    Fernandez, J., L. Wehrstedt, L. Shamis, M. Elhoushi, K. Saladi, Y. Bisk, E. Strubell, and J. Kahn. Hardware scaling trends and diminishing returns in large-scale distributed training.arXiv preprint arXiv:2411.13055, 2024

    work page arXiv 2024

  22. [22]

    Carvalho, and C

    Gonzalez, N., T. Carvalho, and C. Miers. Cloud resource management: Towards efficient execution of large- scale scientific applications and workflows on complex infrastructures.Journal of Cloud Computing6(1) (2017), 13

    2017

  23. [23]

    Gupta, A., B. Acun, O. Sarood, and L. Kal´ e. Towards realizing the potential of malleable jobs. InProceedings of the 21st International Conference on High Performance Computing (HiPC), 2014

    2014

  24. [24]

    Open problems in queueing theory inspired by datacenter computing.Queueing Systems 97(1) (2021), 3–37

    Harchol-Balter, M. Open problems in queueing theory inspired by datacenter computing.Queueing Systems 97(1) (2021), 3–37

    2021

  25. [25]

    Hill, M. and M. Marty. Amdahl’s law in the multicore era.Computer41 (2008), 33–38

    2008

  26. [26]

    Huang, Y

    Huang, K., T. Huang, Y. Tung, and P. Shih. Effective processor allocation for moldable jobs with application speedup model. InAdvances in Intelligent Systems and Applications – Volume 2, Smart Innovation, Systems and Technologies, vol. 21. Springer, 2013, 563–572

    2013

  27. [27]

    Ravner, and M

    Inoue, Y., L. Ravner, and M. Mandjes. Estimating customer impatience in a service system with unobserved balking.Stochastic Systems13(2) (2023), 181–210

    2023

  28. [28]

    The queue inference engine: Deducing queue statistics from transactional data.Management Science36(5) (1990), 586–601

    Larson, R. The queue inference engine: Deducing queue statistics from transactional data.Management Science36(5) (1990), 586–601

    1990

  29. [29]

    Li, Z., B. Berg, A. Mukhopadhyay, and M. Harchol-Balter. How to rent GPUs on a budget. InProceedings of the 20th European Performance Engineering Workshop (EPEW), Lecture Notes in Computer Science, vol. 15454. Springer, Cham, 2024

    2024

  30. [30]

    Harchol-Balter, and B

    Li, Z., M. Harchol-Balter, and B. Berg. Mean field optimal core allocation across malleable jobs.arXiv preprint arXiv:2602.01411, 2026

    work page arXiv 2026

  31. [31]

    Li, Z., C. Zhu, A. Mukhopadhyay, M. Harchol-Balter, and B. Berg. BOA Constrictor: Squeezing performance out of GPUs in the cloud via budget-optimal allocation.arXiv preprint arXiv:2602.01404, 2026

    work page arXiv 2026

  32. [32]

    Lym, S., D. Lee, M. O’Connor, N. Chatterjee, and M. Erez. DeLTA: GPU performance model for deep learning applications with in-depth memory system traffic analysis. InProceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), IEEE, 2019, 293–303

    2019

  33. [33]

    Reinders, and A

    McCool, M., J. Reinders, and A. Robison.Structured Parallel Programming: Patterns for Efficient Compu- tation. Morgan Kaufmann, 2015

    2015

  34. [34]

    John Wiley & Sons, 1994

    Puterman, M.Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994

    1994

  35. [35]

    Podorojnyi, D. and L. Ravner. Estimation of service value parameters for a queue with unobserved balking. Queueing Systems110(2) (2026), Article 27

    2026

  36. [36]

    Taimre, and P

    Ross, J., T. Taimre, and P. Pollett. Estimation for queues from queue length data.Queueing Systems55(2) (2007), 131–138

    2007

  37. [37]

    Shi, J. and J. Lu. Performance models of data parallel DAG workflows for large-scale data analytics.Dis- tributed and Parallel Databases41(3) (2023), 299–329

    2023

  38. [38]

    Fluid models for multiserver queues with abandonments.Operations Research54(1) (2006), 37–54

    Whitt, W. Fluid models for multiserver queues with abandonments.Operations Research54(1) (2006), 37–54

    2006

  39. [39]

    Fitting birth-and-death queueing models to data.Statistics & Probability Letters82(5) (2012), 998–1004

    Whitt, W. Fitting birth-and-death queueing models to data.Statistics & Probability Letters82(5) (2012), 998–1004

    2012

  40. [40]

    Dai, and B

    Zhang, J., J. Dai, and B. Zwart. Law of large number limits of limited processor-sharing queues.Mathematics of Operations Research34(4) (2009), 937–970. 25

    2009

  41. [41]

    Dai, and I

    Zhao, S., X. Dai, and I. Bate. DAG scheduling and analysis on multi-core systems by modelling parallelism and dependency.IEEE Transactions on Parallel and Distributed Systems33(12) (2022), 4019–4038

    2022

  42. [42]

    datacenterdynamics.com/en/news/nvidia-h100-gpus-now-available-on-aws-as-amazons-cloud-scales-to-20000-gpu-clusters/

    Data Center Dynamics (2023).Nvidia H100 GPUs now available on AWS.https://www. datacenterdynamics.com/en/news/nvidia-h100-gpus-now-available-on-aws-as-amazons-cloud-scales-to-20000-gpu-clusters/. Accessed: June 1, 2026

    2023

  43. [43]

    Accessed: January 11, 2026

    McKinsey.The cost of compute: A$7 trillion race to scale data centers.https:// www.mckinsey.com/industries/technology-media-and-telecommunications/our-insights/ the-cost-of-compute-a-7-trillion-dollar-race-to-scale-data-centers/. Accessed: January 11, 2026

    2026

  44. [44]

    Accessed January 11, 2026

    Microsoft.Inside the world’s most powerful AI datacenter.https://blogs.microsoft.com/blog/2025/09/ 18/inside-the-worlds-most-powerful-ai-datacenter/. Accessed January 11, 2026

    2025

  45. [45]

    Google Cloud turbocharges its AI hypercomputer stack with next-gen TPUs and bigger GPU clusters

    SiliconAngle. Google Cloud turbocharges its AI hypercomputer stack with next-gen TPUs and bigger GPU clusters. October 30, 2024. Available at:https://siliconangle.com/2024/10/30/ google-cloud-turbocharges-ai-hypercomputer-stack-next-gen-tpus-bigger-gpu-clusters/. Accessed: June 1, 2026. 26

    2024