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

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

Problem Statement
This paper addresses the dynamic resource allocation problem in multicore computing systems handling a stream of "malleable" jobs. Unlike "moldable" jobs, where the number of allocated cores is fixed upon arrival, malleable jobs allow for the dynamic redistribution of processing capacity during execution. The system consists of a fixed number of identical cores ($c$) and two observable job classes. Each job class is characterized by a distinct, unknown speed-up function $s(z; p)$, where $z$ is the allocated capacity and $p$ is an unknown parameter governing the degree of parallelizability.

The objective is to minimize the long-run mean number of jobs in the system (equivalently, the mean response time in steady state). A fundamental trade-off exists: allocating more cores accelerates job completion, but due to diminishing returns (e.g., Amdahl's Law), the marginal gain decreases as more cores are assigned. While optimal policies for such systems are known when speed-up parameters are fixed and known (specifically, the EQUI policy for equal sharing within classes and an optimal fraction between classes derived via Markov Decision Processes), this paper tackles the scenario where the parameters $p_1$ and $p_2$ are unknown and must be learned from operational data. This gap is motivated by modern applications like large-scale machine learning training on cloud GPUs, where speed-up characteristics may vary due to evolving workloads or hardware upgrades, rendering static assumptions unrealistic.

Methodology
The authors propose an iterative learning-and-control framework that alternates between parameter estimation and policy optimization.

1. System Model:

   • Jobs arrive via a Poisson process with rate $\lambda$. Service requirements are exponentially distributed with rate $\mu$.
   • Jobs belong to Class 1 (probability $\alpha$) or Class 2 (probability $1-\alpha$).
   • The speed-up function $s(z; p)$ is linear for $z \le 1$ and concave/non-decreasing for $z > 1$. Two specific models are considered: Amdahl's Law and a power-law model ($s(z; p) = \max\{z, 1\}^p$).
   • The allocation policy $\pi$ determines the fraction of cores assigned to Class 1 jobs based on the current system state $(n^{(1)}, n^{(2)})$. Within each class, cores are shared equally (EQUI policy).

2. Parameter Estimation (Maximum Likelihood):

   • The core of the learning mechanism is a Maximum Likelihood Estimator (MLE) based on state-dependent inter-departure times.
   • The departure process for each class is modeled as a state-dependent Poisson process. The instantaneous departure rate $\delta^{(i)}$ depends on the number of jobs $n^{(i)}$, the allocated cores $c^{(i)}$, and the unknown parameter $p_i$.
   • The likelihood function is constructed by decomposing inter-departure intervals into sub-intervals where the system state (and thus the departure rate) remains constant. The log-likelihood is derived explicitly as a function of the observed departure times and the sequence of system states.
   • The authors prove that under a fixed allocation policy, these MLEs are strongly consistent (converge almost surely to the true parameters) as the number of observed departures increases. This proof relies on the regenerative structure of the queueing system and the Lipschitz continuity of the speed-up function with respect to $p$.

3. Policy Optimization (MDP):

   • Once parameters are estimated, the optimal allocation policy is computed by solving the Bellman optimality equation for a Markov Decision Process (MDP).
   • The state space is defined by the number of jobs in each class. The action space is the fraction of cores allocated to Class 1.
   • The cost function is the total number of jobs in the system. The MDP is solved using value iteration after uniformizing the continuous-time process into a discrete-time equivalent.

4. Learning Algorithms:
   The paper proposes two specific algorithms implementing this loop:

   • Algorithm 1a: Uses only data collected during the most recent observation window (defined by a fixed number of departures $N_k$) to update estimates. This allows for adaptability to non-stationary environments where parameters might change over time.
   • Algorithm 1b: Uses all accumulated data since time $t=0$ to update estimates. While this typically yields faster convergence and higher accuracy in stationary settings, it is less adaptable to changing parameters.

Key Contributions

• Extension of Malleable Job Models: The paper extends classical malleable-job core allocation models by introducing a learning mechanism for unknown speed-up parameters, moving beyond the assumption of a priori knowledge.
• Statistical Inference in Queueing Systems: It develops a specific MLE procedure for estimating parallelization characteristics using state-dependent inter-departure times, proving strong consistency under fixed policies.
• Integrated Learning Framework: It proposes and analyzes two iterative algorithms (1a and 1b) that combine statistical estimation with dynamic programming-based policy updates.
• Numerical Validation: Through extensive numerical experiments, the paper demonstrates that the proposed methods achieve accurate parameter estimates and near-optimal system performance after relatively short observation periods. It also highlights a "quasi-identifiability" issue where estimating parameters for jobs with low parallelizability (low $p$) is more difficult than for highly parallelizable jobs.

Results

• Convergence: Numerical experiments confirm that the estimators converge to the true parameters. Algorithm 1b generally converges faster than 1a in stationary settings due to the use of the full data history.
• Adaptability: In a non-stationary experiment where speed-up parameters change at specific time points, Algorithm 1a successfully tracks the evolving parameters and adjusts the allocation policy accordingly, demonstrating its utility in dynamic environments.
• Performance: The learned policies achieve mean response times close to the theoretical optimum that would be achieved if the true parameters were known from the start.
• Asymmetry in Estimation: The results indicate that estimating the parameter for the class with lower parallelizability (smaller $p$) is inherently more challenging and slower to converge than for the class with higher parallelizability, due to the weaker sensitivity of the speed-up function to core allocation changes in that regime.

Significance
The paper claims significance by addressing a critical gap in the literature: the assumption that speed-up functions are known and static. By providing a framework to learn these parameters online, the work offers a practical solution for modern, dynamic computing environments (such as cloud-based AI training) where resource efficiency is paramount but system characteristics are uncertain. The authors note that while the framework extends naturally to more than two job classes, the computational complexity of solving the associated Bellman equations increases significantly, highlighting a trade-off between model expressiveness and tractability. The work lays the groundwork for future research into non-stationary settings, general service-time distributions, and scalable approximation methods for high-dimensional systems.