# Harvesting Wasted Resources in HPC Systems Using
Model Predictive Control

Mahmoud Abdo

<figure><img src="image_1.png" /></figure>

## To cite this version:

Mahmoud Abdo. Harvesting Wasted Resources in HPC Systems Using Model Predictive Control. Automatic. 2025. hal-05225925

HAL Id: hal-05225925

https://inria.hal.science/hal-05225925v1

Submitted on 27 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Internship report

Harvesting Wasted Resources in HPC Systems Using Model Predictive Control

Presented and defended on 30 June 2024

by

Mahmoud ABDO

In front of a jury composed of

Jury President: Dr. Christophe Prieur

Supervisors: Dr. Bogdan Robu, Dr. Sophie Cerf

Internship Tutor: Prof. Jean-Marc Thiriet
# Contents

<table><tr><td>1 Abstract</td><td>3</td></tr><tr><td>2 Introduction</td><td>3</td></tr><tr><td>3 Objective</td><td>4</td></tr><tr><td>4 Model Predictive Control</td><td>5</td></tr><tr><td>4.1 Overview of model predictive control</td><td>5</td></tr><tr><td>4.2 How MPC work</td><td>5</td></tr><tr><td>5 System description</td><td>7</td></tr><tr><td>6 Modeling and validation</td><td>8</td></tr><tr><td>6.1 BE jobs</td><td>8</td></tr><tr><td>6.1.1 Waiting Jobs Evolution</td><td>8</td></tr><tr><td>6.1.2 Running Jobs Evolution</td><td>9</td></tr><tr><td>6.1.3 Killing Jobs</td><td>9</td></tr><tr><td>6.2 HP jobs</td><td>9</td></tr><tr><td>6.3 Substituted Job Evolution Equations</td><td>10</td></tr><tr><td>6.4 State-Space Representation</td><td>10</td></tr><tr><td>7 Extended Kalman Filter Implementation</td><td>11</td></tr><tr><td>7.1 State Vector Definition</td><td>11</td></tr><tr><td>7.2 EKF Structure</td><td>12</td></tr><tr><td>7.3 Model Validation and Result Interpretation</td><td>13</td></tr><tr><td>7.4 Estimated Parameters</td><td>14</td></tr><tr><td>8 Control design</td><td>14</td></tr><tr><td>8.1 MPC without Disturbance</td><td>15</td></tr><tr><td>8.1.1 Reformulation as a Quadratic Programming Problem</td><td>15</td></tr><tr><td>8.1.2 Expressions for H and f</td><td>16</td></tr><tr><td>8.1.3 Quadratic Cost Reformulation</td><td>17</td></tr><tr><td>8.1.4 Constraints</td><td>19</td></tr><tr><td>8.2 MPC with Disturbance</td><td>19</td></tr><tr><td>8.2.1 Modified State-Space Model</td><td>19</td></tr><tr><td>8.2.2 Anticipation Constraint</td><td>19</td></tr><tr><td>8.2.3 Updated Optimization Problem</td><td>20</td></tr><tr><td>9 Implementation and Simulations</td><td>20</td></tr><tr><td>9.1 MPC without Disturbance</td><td>20</td></tr><tr><td>9.2 MPC with Disturbance (HP Jobs)</td><td>21</td></tr><tr><td>10 Comparison Between MPC and PI Controllers</td><td>23</td></tr><tr><td>10.1 Killed Jobs Comparison</td><td>23</td></tr><tr><td>10.2 Tracking the Reference with Anticipation</td><td>24</td></tr><tr><td>10.3 Discussion</td><td>24</td></tr></table>
11 Conclusion 25

References 26
# 1 Abstract

This report investigates the use of Model Predictive Control (MPC) to reduce wasted resources in high-performance computing (HPC) systems. Idle time when computing resources remain unused due to inefficient scheduling presents a major opportunity for optimization in HPC environments. The aim of this internship was to design an MPC-based approach that dynamically adjusts job scheduling strategies to better utilize available resources.

The report first provides a detailed overview of MPC principles, followed by the modeling of a simplified linear dynamical system that captures the core dynamics of job queues in HPC systems. The controller is initially tested under nominal conditions to establish baseline performance. Then, external disturbances such as high-priority job arrivals are introduced to assess robustness. To mitigate their impact, strategies including disturbance modeling and constraint tightening are explored.

# 2 Introduction

Model Predictive Control is a powerful optimization strategy for feedback con- trol. It is widely used in industrial applications due to its ability to handle multi-input multi-output systems. The key concept behind MPC is the use of a model of the sys- tem to predict future behavior and optimize control actions accordingly. Predictive control represents an effective control design for handling both hard constraints and performance issues. The predictive control law is obtained by minimizing a mov- ing horizon performance index which explicitly takes into account input and state constraints. It is well known that the action of bounded disturbances can desta- bilize a predictive controller. To decrease the effect of disturbances, we use robust Model Predictive Control (MPC) techniques. These strategies aim to ensure that the system remains stable and performs well even in the presence of uncertainties and disturbances [1]. The advantage of MPC is that it is a multi-variable controller that controls the output simultaneously by taking into account all the interactions between system variables. Another strength of MPC is that it can handle constraints and also it is preview capability which is similar to feedforward control. In Model Predictive Control (MPC), a system model along with the current state (measured or estimated) is used to predict the future behavior of the system over a short period for a given control input sequence. This predicted behavior is evaluated using a cost function that depends on the predicted states and control sequence. An optimization algorithm is then employed to determine the control sequence that minimizes this cost function. The first control input from this optimized sequence is applied to the system, updating it to the next state. This process is repeated at each time step,
resulting in a receding horizon control scheme [2]. High-Performance Computing (HPC), refers to the use of advanced technology, methodologies, and applications to deliver the maximum computing capacity at any given moment in time. HPC makes use of highly powered digital computers called supercomputers, which are specifically designed to perform a wide range of computationally intense tasks or loads as quickly as possible. Running such applications on a supercomputer is referred to generically as supercomputing, and it is synonymous with HPC.[3]

In high-performance computing (HPC), several research has focused on optimizing the use of idle resources (periods when no jobs are submitted to the platform). A promising strategy involves leveraging by injecting small, flexible, independent, and interruptible jobs that have no strict time constraints.

## 3 Objective

The aim of this work is to describe how Model Predictive Control (MPC) might be used to improve the efficiency of job scheduling in high-performance computing (HPC) systems. The aim is particularly to reduce idle times and to make the system more responsive to unpredictable events, such as the arrival of high-priority jobs. To achieve this, the project involves building a model that reflects how jobs are submitted, executed, and sometimes interrupted in an HPC system. This model is then used to develop a predictive controller that is able to perform smart scheduling by forecasting what the system will do in the future.

Throughout the internship, the focus has been on:

* Developing a mathematical model that reflects the real dynamics of HPC job queues

* Incorporating the effect of disturbances, like high-priority job submissions, into the control strategy

* Designing an MPC controller that tries to use the available computing power as efficiently as possible, while avoiding job interruptions

* Testing the controller under different scenarios to check its robustness and effectiveness

* Comparing the MPC-based strategy to simpler control methods to highlight the benefits of predictive control in this context.
# 4 Model Predictive Control

## 4.1 Overview of model predictive control

The numerical implementation of Linear Model Predictive Control (LMPC) involves solving a quadratic programming problem where the objective is to minimize a quadratic cost function subject to linear constraints on states and controls [2]. Nominal Predictive Control (NPC) is designed to regulate linear discrete-time systems under ideal conditions, assuming no disturbances. Robust Predictive Control (RPC) extends NPC to handle unknown but bounded disturbances. The presence of disturbances can destabilize a nominal predictive controller. RPC introduces constraint restrictions to ensure feasibility and stability under disturbances [1]. The robust tube-based Model Predictive Control (MPC) framework is designed for constrained discrete-time time-varying systems with additive uncertainties. This approach ensures robustness by maintaining all possible trajectories of the uncertain system within a sequence of admissible regions called tubes. The method uses reachable sets calculated online, adapting to system dynamics and uncertainties. This adaptive control law reduces conservativeness and ensures constraint satisfaction and stability [4]. Yan et al. [5] considered discrete-time linear systems with input constraints, structured parameter uncertainties, and persistent disturbances. To ensure robust stability of constrained uncertain systems, they propose methods to compute robust positively invariant (RPI) sets for stabilizing predictive controllers. On the other hand, Bemporad et al. [6] developed an algorithm that explicitly determines the state feedback control law via multi-parametric quadratic programming (mp-QP). The explicit MPC solution is shown to be piecewise linear and continuous, reducing online computation to a simple linear function evaluation. This approach retains the stability and performance characteristics of MPC while extending its applicability to fast sampling and small-scale applications.

## 4.2 How MPC work

Imagine walking in a dark room. You sense your surroundings, predict the best path towards your goal, then take a single step forward. You repeat this process step by step, continually reassessing and adjusting your course. Similarly the Model Predictive Control process is like walking in a dark room. The core idea behind MPC is the receding horizon principle. At each time step, MPC solves an optimization problem over a finite future horizon, computes the optimal control inputs, and applies the first input to the system. The horizon then shifts forward, and the process is repeated. Key components of the MPC framework include:

1. **System Model:** The mathematical representation of the system's dynamics.
2. **Prediction Horizon:** The future time period over which predictions are made.

3. **Control Horizon:** The future time period over which control actions are optimized.

4. **Cost Function:** The objective function that MPC minimizes, typically involving terms for tracking error and control effort.

5. **Constraints:** Restrictions on states and control inputs to ensure safe and feasible operation. [7]

<figure><img src="image_3.png" /><figcaption>Figure 1: Basic scheme of model predictive control block diagram.</figcaption></figure>

Figure 1 illustrates a basic scheme of MPC. In a control problem, the objective of the controller is to determine the input to the plant so that the plant's output follows a specified reference. A Model Predictive Controller computes this input by predicting the future. It utilizes a model of the plant to predict its future output and employs an optimizer to ensure that these predictions align with the desired reference.

Figure 2 illustrates that at each sampling time *k*, the MPC controller uses the system model to predict future outputs based on the current state and a sequence of future control inputs. Only the first control input from the optimized sequence is applied to the system. The process then repeats at the next sampling time, incorporating new measurements and updating predictions [8].
<figure><img src="image_4.png" /><figcaption>Figure 2: Model predictive control strategy.</figcaption></figure>

# 5 System description

<figure><img src="image_5.png" /><figcaption>Figure 3: System architecture of the HPC system integrating CiGri with feedback-based regulation of BE jobs.</figcaption></figure>

Figure 3 represents an architecture of a computing platform managed by a centralized scheduler that is responsible for scheduling jobs to available resources in a data cluster. There are two types of jobs managed by the system: high-priority (HP) jobs, which must be scheduled with priority, and best-effort (BE) jobs, which are only scheduled when there are available resources[9].

The CiGri platform is responsible for injecting BE jobs into the system. The tap
lets a controlled number of BE jobs through at fixed intervals to prevent cluster saturation[10]. Injected BE jobs are passed on to the OAR scheduler, which is also in charge of HP jobs. The scheduler decides the order of job execution based on current platform availability and scheduling policies.

As shown in the figure, the OAR scheduler features two queues, one for HP jobs and one for waiting BE jobs. It then submits jobs to the cluster, where HP jobs and BE jobs run in parallel, provided there are free resources.

Feedback about the condition of the platform, i.e., job execution and available capacity, is sent back to CiGri. The feedback loop enables the controller to tune the submission rate of BE jobs dynamically based on actual system load.

A BE job can be in one of the following four states:

* Running: actually executing on a resource.

* Waiting: waiting in queue because of insufficient resources.

* Killed: the job was interrupted to free resources for an HP job; it will be resubmitted to the waiting queue for future execution.

* Completed: terminated execution successfully.

# 6 Modeling and validation

This section deals with modeling the dynamics of best-effort (BE) jobs, whose execution depends on the availability of idle resources, and high-priority (HP) jobs, which have priority and can preempt BE execution under contention. The model presented here captures the manner in which BE jobs evolve over time in different states waiting, running, or being forcibly terminated (killed). These evolutions are determined by scheduling decisions, resource constraints, and the arrival of HP jobs.

In contrast, HP jobs are submitted one at a time and must be executed with minimal delay and are therefore a key driver of system saturation and BE job mortality.

## 6.1 BE jobs

### 6.1.1 Waiting Jobs Evolution

The number of waiting jobs at step $W_{k+1}$ is equal to the number of waiting jobs at the previous step, plus the jobs that were killed and sent back to the queue, plus newly submitted jobs, minus the jobs that left the queue and started running:

$$W_{k+1} = W_k - N_k r_k + K_k + U_k \quad (1)$$

The parameter $N_k$ is interpreted as the fraction of running jobs launched by the scheduler that were taken from the waiting queue.
### 6.1.2 Running Jobs Evolution

The number of running jobs at step $r_{k+1}$ is equal to the number of running jobs at the previous step, plus the jobs that start running(from the waiting queue) minus the jobs that were killed and sent back to the queue, minus the jobs that finished at each time step:

$$r_{k+1} = r_k + M_k W_k - K_k - \left(\frac{\Delta t}{P} r_{\max}\right) \quad (2)$$

Where $\Delta t = 30s$ is the BE jobs submission sampling time,and $p$ is the processing time of BE jobs which has a theoretical value of = 60s, but this value varies between jobs in real implementation on the platform[10].

The parameter $M_k$ is interpreted as the fraction of waiting jobs selected by the scheduler to move into the running state.

### 6.1.3 Killing Jobs

The killing factor models the number of BE jobs that are forcibly removed from execution due to the arrival of high-priority jobs or system overload.

The killing factor is defined based on the difference between high-priority job demands and the idle system capacity:

$$K_k = d_{HP,k} - \text{idle resources} \quad (3)$$

where the idle resources at time step $k$ are given by:

$$\text{idle resources} = r_{\max} - r_k \quad (4)$$

Substituting this into the previous equation yields:

$$K_k = d_{HP,k} + r_k - r_{\max} \quad (5)$$

$r_{\max}$ is the total system capacity in terms of maximum simultaneously running jobs.

To ensure physical feasibility, the killing factor must always be non-negative. Therefore, we enforce the condition:

$$K_k \ge 0$$

## 6.2 HP jobs

The system is subject to disturbances due to the arrival and execution of HP jobs. The evolution of the number of resources occupied by HP jobs has the following dynamics and can be described as:

$$y^{\text{HP}}(k+1) = y^{\text{HP}}(k) + d(k) - c^{\text{HP}} \quad (6)$$
where $y^{\text{HP}}(k)$ represents the number of resources already occupied by HP jobs at iteration $k$, $d(k)$ represents the number of resources requested by newly submitted HP jobs at iteration $k$, and $c^{\text{HP}}$ represents the number of resources freed at iteration $k$ due to the completion of HP jobs.

## 6.3 Substituted Job Evolution Equations

By substituting the killing factor expression

$$K_k = d_{HP,k} + r_k - r_{\max}$$

into the previous evolution equations, we obtain simplified forms for the system dynamics without explicitly including $K_k$.

### Waiting Jobs

$$W_{k+1} = W_k + d_{HP,k} + (1 - N_k)r_k - r_{\max} + U_k \quad (7)$$

Since high-priority jobs are immediately executed upon arrival without waiting, we set $d_{HP,k} = 0$ in the waiting queue dynamics. Therefore, only the best-effort jobs and system capacity affect the waiting queue evolution.

$$W_{k+1} = W_k + (1 - N_k)r_k - r_{\max} + U_k \quad (8)$$

This expression captures the impact of high-priority job arrivals and system capacity on the waiting queue.

### Running Jobs

$$r_{k+1} = M_k W_k - d_{HP,k} + r_K \left(1 - \frac{\Delta t}{P}\right) \quad (9)$$

## 6.4 State-Space Representation

After substituting the expression for the killing factor $K_k$ into the waiting and running job equations, we obtain the following simplified discrete-time system dynamics:

$$W_{k+1} = W_k + (1 - N_k)r_k - r_{\max} + U_k \quad (10)$$

$$r_{k+1} = r_K \left(1 - \frac{\Delta t}{P}\right) + M_k W_k - d_{HP,k} \quad (11)$$

These equations describe the evolution of the number of waiting and running best-effort (BE) jobs over time, incorporating the influence of high-priority job arrivals, resource limitations, and job submission.
To express the system in a compact form, we define the state vector, control input, disturbance, and output as follows:

$$x_k = \begin{bmatrix} W_k \\ r_k \end{bmatrix}, \quad u_k = U_k, \quad d_k = d_{HP,k}, \quad y_k = C x_k$$

The discrete-time state-space equations are given by:

$$x_{k+1} = A_k x_k + B_k u_k + E_k d_k + f_k \quad (12)$$

$$y_k = C x_k \quad (13)$$

where the matrices are defined as:

$$A = \begin{bmatrix} 1 & 1 - N_k \\ M_k & \left(1 - \frac{\Delta t}{P}\right) \end{bmatrix}, \quad B = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \quad E = \begin{bmatrix} 0 \\ -1 \end{bmatrix},$$

$$f = \begin{bmatrix} -r_{\max} \\ 0 \end{bmatrix}, \quad C = \begin{bmatrix} 1 & 1 \end{bmatrix}$$

This representation captures the dynamic behavior of the system and models how the waiting and running BE jobs evolve in response to control actions and high-priority job arrivals.

# 7 Extended Kalman Filter Implementation

To estimate both the internal states and system parameters of the job scheduling system, an **Extended Kalman Filter (EKF)** was implemented. The EKF is particularly suited for this application because the system model is nonlinear, and the observations (waiting and running Best Effort jobs) are noisy. The filter enables recursive estimation of quantities that cannot be measured directly, such as the internal dynamics of the scheduler and its governing parameters[11].

## 7.1 State Vector Definition

The EKF operates on a Four-dimensional state vector defined as:

$$x_k = \begin{bmatrix} W_k \\ r_k \\ N_k \\ M_k \end{bmatrix}$$

where:
* $W_k$: number of waiting Best Effort (BE) jobs

* $r_k$: number of running BE jobs

* $N_k$: parameter controlling how running jobs reduce the waiting queue

* $M_k$: parameter determining how waiting jobs affect the running queue

## 7.2 EKF Structure

Because the model is nonlinear, a standard Kalman Filter is not applicable. Instead, the Extended Kalman Filter is used, which linearizes the system at each time step using the Jacobian matrix.

### Prediction Step

The predicted state is computed using the nonlinear model:

$$x_{k+1}^{\text{pred}} = f(x_k)$$

The Jacobian matrix of the dynamics, denoted $A_k = \frac{\partial f}{\partial x_k}$, is evaluated at the current estimate. The state covariance is propagated as:

$$P_{k+1}^{\text{pred}} = A_k P_k A_k^T + Q_k$$

where $Q_k$ is the process noise covariance matrix accounting for model uncertainty.

### Correction Step

When the next observation becomes available:

$$z_k = \begin{bmatrix} W_k^{\text{obs}} \\ r_k^{\text{obs}} \end{bmatrix}$$

The innovation (measurement residual) is computed as:

$$y_k = z_k - H x_{k+1}^{\text{pred}}$$

The observation matrix is defined as:

$$H = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}$$

The Kalman gain is computed as:

$$K_k = P_{k+1}^{\text{pred}} H^T (H P_{k+1}^{\text{pred}} H^T + R_k)^{-1}$$
The updated state and covariance are given by:

$$x_k = x_{k+1}^{\text{pred}} + K_k y_k \\ P_k = (I - K_k H) P_{k+1}^{\text{pred}}$$

where $R_k$ is the measurement noise covariance matrix, computed from the empirical variance of the observed data.

## 7.3 Model Validation and Result Interpretation

Figure 4 illustrates the comparison between the measured system behavior and the predictions generated by the Extended Kalman Filter (EKF). The plots confirm that the EKF accurately estimates the evolution of the system state over time.

* Figure 4(a) shows the input signal $u(k)$, which is the submitted Best Effort (BE) job load. It increases in discrete steps, allowing us to observe how the system responds to load variations.

* Figure 4(b) compares the actual and estimated number of waiting BE jobs $w^{BE}(k)$. The EKF model successfully captures the increase and eventual decay in the waiting queue, especially when the system approaches saturation.

* Figure 4(c) displays the total number of jobs in the system, defined as $y^{BE}(k) = w^{BE}(k)+r^{BE}(k)$. The prediction closely follows the measured signal, confirming the reliability of the state estimation.

* Figure 4(d) illustrates the evolution of running BE jobs $r^{BE}(k)$. The EKF is able to track both the growth phase and the saturation phase where the number of running jobs fluctuates around the maximum capacity.

These results show that the predicted trajectory remains close to the real system measurements despite model uncertainties, confirming both stability and fidelity of the filter.
<figure><img src="image_6.png" /><figcaption>Figure 4: Comparison between actual and EKF-estimated values of system input and states.</figcaption></figure>

## 7.4 Estimated Parameters

After running the Extended Kalman Filter over the observed data, the following parameters were estimated:

* $N = 1.9589$

* $M = 1.5500$

These parameter values were learned dynamically based on the evolution of the system and the submitted BE job patterns. They fall within the imposed stability bounds and confirm the EKF's ability to track not only system states but also hidden dynamics.

## 8 Control design

In this section, we introduce the control strategy used to regulate the submission of BE jobs on the HPC platform. The controller is based on a Model Predictive
Control (MPC). The main objective is to maximize the usage of idle resources while ensuring system constraints are satisfied with high probability. The control design is developed using the system dynamics identified earlier, incorporating both feedback regulation and probabilistic constraint handling.

## MPC Optimization Problem

**Cost Function to Minimize:**

$$J = \sum_{k=0}^{N} (\|x_k - x_{\text{ref}}\|_{Q}^{2} + \|u_k\|_{R}^{2})$$

Here, $x_k = \begin{bmatrix} W_k \\ r_k \end{bmatrix}$, $u_k = U_k$, $x_{\text{ref}} = \begin{bmatrix} 0 \\ r_{\text{ref}} \end{bmatrix}$

## Constraints

$$0 \le r_k \le r_{\max} \quad (\text{Running BE Jobs})$$

$$U_k \in [0, 32] \quad (\text{Submitted BE Jobs})$$

$$r_k + d_{HP,k} \le r_{\max} \quad (\text{Anticipation Constraint})$$

# 8.1 MPC without Disturbance

## 8.1.1 Reformulation as a Quadratic Programming Problem

The finite-horizon MPC problem aims to minimize a quadratic cost function over the control inputs $U = [u_0, u_1, \dots, u_{N-1}]^T$:

$$J(U) = \sum_{k=0}^{N-1} ((x_k - x_{\text{ref}})^T Q (x_k - x_{\text{ref}}) + u_k^T R u_k) + x_N^T P x_N,$$

where $Q$ and $R$ are positive definite weighting matrices for the states and inputs, respectively, and $P$ is the terminal cost.

To reformulate the above expression, we express $J(U)$ in the form:

$$\min_{U} \frac{1}{2} U^T H U + f^T U,$$

where $H$ is the Hessian matrix and $f$ is the gradient vector.
### 8.1.2 Expressions for H and f

The matrices can be derived as follows:

First of all, we write the state equation from the system in (12) in the following format (by iteration):

* For $k = 0$:

$$x_1 = Ax_0 + Bu_0$$

* For $k = 1$:

$$x_2 = Ax_1 + Bu_1 = A(Ax_0 + Bu_0) + Bu_1 = A^2x_0 + ABu_0 + Bu_1$$

* For $k = 2$:

$$x_3 = Ax_2 + Bu_2 = A(A^2x_0 + ABu_0 + Bu_1) + Bu_2 = A^3x_0 + A^2Bu_0 + ABu_1 + Bu_2$$

Continuing this pattern, we find a general formula for $x_{k+1}$:

$$x_{k+1} = A^{k+1}x_0 + \sum_{i=0}^{k} A^i Bu_{k-i}$$

Substituting $k = N - 1$, we get the expression for $x_N$:

$$x_N = A^N x_0 + \sum_{i=0}^{N-1} A^i B u_{N-1-i}$$

Thus, the stacked state vector from $x_1$ to $x_N$ can be written as:

$$\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_N \end{bmatrix} = \begin{bmatrix} Ax_0 + Bu_0 \\ A^2x_0 + ABu_0 + Bu_1 \\ A^3x_0 + A^2Bu_0 + ABu_1 + Bu_2 \\ \vdots \\ A^N x_0 + \sum_{i=0}^{N-1} A^i B u_{N-1-i} \end{bmatrix}$$

We can express the vector $\mathbf{x}$ in compact form:

$$\mathbf{x} = A_{\text{stack}} x_0 + M_u U$$
where:

$$
A_{\text{stack}} = \begin{bmatrix} A \\ A^2 \\ A^3 \\ \vdots \\ A^N \end{bmatrix} \qquad M_u = \begin{bmatrix} B & 0 & 0 & \cdots & 0 \\ AB & B & 0 & \cdots & 0 \\ A^2 B & AB & B & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ A^{N-1} B & A^{N-2} B & A^{N-3} B & \cdots & B \end{bmatrix} \qquad U = \begin{bmatrix} u_0 \\ u_1 \\ u_2 \\ \vdots \\ u_{N-1} \end{bmatrix}
$$

8.1.3 Quadratic Cost Reformulation

Next, the quadratic cost function can be written in compact matrix form:

$$
J(U) = \mathbf{X}^T Q_{\text{block}} \mathbf{X} + U^T R_{\text{block}} U
$$

where:

$$
Q_{\text{block}} = \begin{bmatrix} Q & 0 & 0 & \cdots & 0 \\ 0 & Q & 0 & \cdots & 0 \\ 0 & 0 & Q & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & P \end{bmatrix} \quad R_{\text{block}} = \begin{bmatrix} R & 0 & \cdots & 0 \\ 0 & R & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & R \end{bmatrix}
$$

and:

$$
\mathbf{X} = \begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_N \end{bmatrix}
$$
Since:

$$ \mathbf{X} = A_{\text{stack}}x_0 + M_u U $$

substituting into the cost function:

$$ J(U) = (A_{\text{stack}}x_0 + M_u U)^T Q_{\text{block}} (A_{\text{stack}}x_0 + M_u U) + U^T R_{\text{block}} U + x_0^T Q x_0 $$

Expanding:

$$ J(U) = x_0^T Q x_0 + x_0^T A_{\text{stack}}^T Q_{\text{block}} A_{\text{stack}} x_0 + 2x_0^T A_{\text{stack}}^T Q_{\text{block}} M_u U + U^T (M_u^T Q_{\text{block}} M_u + R_{\text{block}}) U $$

Thus, the cost function is rewritten as:

$$ J(U) = \left( \text{constant} + \frac{1}{2} U^T H U + f^T U \right) $$

where:

- Constant term:

$$ x_0^T Q x_0 + x_0^T A_{\text{stack}}^T Q_{\text{block}} A_{\text{stack}} x_0 $$

- Quadratic term:

$$ H = 2 (M_u^T Q_{\text{block}} M_u + R_{\text{block}}) $$

- Linear term:

$$ f = 2 M_u^T Q_{\text{block}} A_{\text{stack}} x_0 $$

In an optimization context, the constant term is irrelevant because it does not affect the minimizer. Thus, the final cost function to minimize is:

$$ \min_{U} \frac{1}{2} U^T H U + f^T U $$
### 8.1.4 Constraints

Thus, the final optimization problem becomes:

$$ \min_{U} \frac{1}{2} U^T H U + f^T U $$

subject to the following constraints:

$$ 0 \le r_k \le r_{\max} \quad (\text{Running BE Jobs}) $$

$$ U_k \in [0, 32] \quad (\text{Submitted BE Jobs}) $$

## 8.2 MPC with Disturbance

In this subsection, we extend the previous MPC formulation by explicitly incorporating the effect of high-priority (HP) job arrivals as a disturbance into the system dynamics and constraints. The aim is to ensure that best-effort (BE) jobs are scheduled without violating the resource limitations imposed by the HP job load.

### 8.2.1 Modified State-Space Model

The presence of HP jobs affects the system by reducing the number of available resources for BE jobs. To capture this, we modify the discrete-time dynamics:

$$ x_{k+1} = Ax_k + Bu_k + Ed_k \quad (14) $$

where $d_k$ denotes the disturbance corresponding to the number of resources consumed by HP jobs at time step $k$, and $E$ is a disturbance mapping matrix that subtracts the HP impact from the running jobs.

### 8.2.2 Anticipation Constraint

To avoid early termination of BE jobs, the MPC formulation anticipates HP job arrivals by enforcing the constraint:

$$ r_k + d_k \le r_{\max} \quad (15) $$

This ensures that the sum of BE running jobs and HP disturbances does not exceed the maximum resource capacity.
### 8.2.3 Updated Optimization Problem

The modified optimization problem becomes:

$$ \min_{U} \frac{1}{2} U^T H U + f^T U \quad (16) $$

subject to:

$$ 0 \le r_k \le r_{\max} \quad (\text{Running BE Jobs}) $$

$$ U_k \in [0, 32] \quad (\text{Submitted BE Jobs}) $$

$$ r_k + d_k \le r_{\max} \quad (\text{Anticipation Constraint}) $$

The structure of $H$ and $f$ remains unchanged, but the matrices used to build the constraint set are adjusted to account for the predicted disturbance trajectory $d_k$ over the horizon. These disturbances are either known in advance or forecasted using a predictive model.

## 9 Implementation and Simulations

This section presents the implementation details and simulation results of the Model Predictive Control (MPC) framework for regulating the submission of best-effort (BE) jobs in a high-performance computing (HPC) system. The performance of the controller is analyzed under different scenarios, starting with a disturbance-free case.

### 9.1 MPC without Disturbance

In the first scenario, the MPC controller is applied to the system without considering any high-priority (HP) job interference. This allows us to evaluate the controller's ability to track the desired number of running BE jobs while respecting system constraints.

The simulation is carried out over a horizon of $N = 20$ steps, and the system parameters are initialized according to the validated model.

Figure 5 shows the simulation results. As observed:

- The control input $u_k$ (submitted BE jobs) rapidly increases and stabilizes to keep the number of running jobs at the reference level.

- The number of running jobs $r_k$ smoothly reaches the target value $r^* = 32$ without overshoot or oscillations.
This confirms that the MPC controller performs well under nominal conditions and efficiently utilizes the available system capacity.

<figure><img src="image_7.png" /><figcaption>Figure 5: MPC simulation results without disturbance.</figcaption></figure>

## 9.2 MPC with Disturbance (HP Jobs)

In this subsection, we evaluate the performance of the MPC controller in the presence of disturbances, representing high-priority (HP) jobs submitted directly to the cluster. The disturbance signal $d_k$ models the number of resources occupied by HP jobs over time. As a result, the number of available resources for best-effort (BE) jobs becomes time-varying.

The MPC controller anticipates future disturbances over the prediction horizon and adjusts the control input $u_k$ (submitted BE jobs) to avoid exceeding the maximum capacity $r_{max}$. The anticipation constraint:

$$r_k + d_{HP,k} \le r_{max}$$

is explicitly included in the optimization problem to ensure that the sum of running BE jobs and incoming HP jobs does not surpass the system's limit.

## Simulation Results:
Figure 6 presents the simulation results under variable HP job arrivals. We observe the following:

- The control input $u_k$ is adjusted dynamically to anticipate future HP job bursts, reducing BE job submissions accordingly.

- The number of running BE jobs $r_k$ is kept within acceptable bounds and closely follows the reference $r^*$ when the platform is not disturbed.

- The anticipation constraint is respected throughout the simulation, as $r_k + d_k \le r_{max}$ holds at all times.

<figure><img src="image_8.png" /><figcaption>Figure 6: MPC performance under disturbance.</figcaption></figure>

## Waiting and Killing Jobs Analysis:

Figure 7 shows the evolution of waiting BE jobs $W_k$ and killing jobs $K_k$ over time. These dynamics reflect the internal system pressure due to limited resources and the arrival of high-priority (HP) jobs.

- **Waiting BE Jobs $W_k$:** This curve shows how many BE jobs are waiting in the queue due to lack of available resources. The controller tries to minimize this number by adjusting the control input $u_k$, yet the number of waiting jobs still grows when job execution is slow or resources are monopolized by HP jobs.

- **Killing Jobs $K_k$:** Killing jobs represent the number of BE jobs that were preempted (interrupted) to free resources for HP job arrivals. Ideally, $K_k$ should remain as close to zero as possible. The controller achieves this by anticipating future disturbances and reducing BE job submissions in advance. Small peaks in $K_k$ indicate moments where anticipation was slightly delayed or the disturbance changed abruptly.
<figure><img src="image_9.png" /><figcaption>Figure 7: Evolution of waiting BE jobs $W_k$ and killing jobs $K_k$.</figcaption></figure>

The results show the MPC is capable of minimizing $K_k$ effectively, which is critical for avoiding resource wastage.

# 10 Comparison Between MPC and PI Controllers

To evaluate the performance of the proposed MPC controller, we compare it with a classical Proportional-Integral (PI) controller. The main evaluation criteria are:

- The number of killed jobs due to over-submission under high-priority job arrivals,

- The system's ability to anticipate disturbances and maintain running jobs close to the reference,

- The quality of resource utilization.

## 10.1 Killed Jobs Comparison

Figure 8 illustrates the number of killed jobs over time for both the MPC and PI controllers. As shown, the PI controller frequently violates the system capacity constraint, especially during and after disturbance events, which results in a significant number of killed jobs. In contrast, the MPC controller effectively anticipates disturbances and adapts its submission strategy, ensuring that the number of killed jobs remains almost zero throughout the simulation.
<figure><img src="image_10.png" /><figcaption>Figure 8: Killed BE Jobs under MPC vs. PI Control</figcaption></figure>

## 10.2 Tracking the Reference with Anticipation

Figure 9 compares the total running BE jobs combined with the disturbance (i.e., $r_k + d_k$) against the reference. The PI controller fails to anticipate the disturbance and hence overshoots the capacity limit during several periods. The MPC controller, however, tracks the reference accurately while respecting the anticipation constraint $r_k + d_k \le r_{max}$.

<figure><img src="image_11.png" /><figcaption>Figure 9: Comparison of $r_k + d_k$ under MPC and PI Controllers</figcaption></figure>

## 10.3 Discussion

The results confirm the advantages of MPC in resource-constrained environments with variable disturbances. Specifically:
- **Anticipation:** MPC adjusts its control inputs before the arrival of disturbances, minimizing overloads.

- **Efficiency:** Submission decisions are optimized to track the reference without violating constraints.

- **Robustness:** The system remains stable even under intense disturbance scenarios, unlike PI control.

These findings demonstrate that MPC is better suited for dynamic and constraint-sensitive systems such as HPC platforms, where job scheduling must adapt to both demand and external load in real time.

## 11 Conclusion

This internship focused on the use of Model Predictive Control (MPC) to enhance the efficiency of job scheduling in High-Performance Computing (HPC) systems. A simplified yet representative model of the job dynamics was developed to capture the interactions between Best Effort (BE) jobs and disturbances introduced by High Priority (HP) job arrivals. An Extended Kalman Filter (EKF) was implemented to estimate internal states and system parameters, improving model accuracy and adaptability. Based on this foundation, an MPC controller was designed to regulate BE job submissions while respecting system constraints and anticipating resource contention. Simulation results confirmed that the controller was able to maintain stable operation, reduce the number of killed jobs, and achieve efficient resource utilization, even under fluctuating workloads. Compared to a classical PI controller, the MPC approach demonstrated clear advantages in robustness and responsiveness. This experience provided valuable insights into the application of control theory in real-world computing environments and highlighted the potential of predictive strategies for intelligent resource management[12] [13].
References

[1] L. Chisci, J. Rossiter, and G. Zappa, “Systems with persistent disturbances: predictive control with restricted constraints,” *Automatica*, vol. 37, no. 7, pp. 1019–1028, 2001.

[2] M. T. Augustine, “Model predictive control using matlab,” *arXiv preprint arXiv:2309.00293*, 2023.

[3] T. Sterling, M. Brodowicz, and M. Anderson, *High performance computing: modern systems and practices*. Morgan Kaufmann, 2017.

[4] R. Gonzalez, M. Fiacchini, T. Alamo, J. L. Guzmán, and F. Rodríguez, “Online robust tube-based mpc for time-varying systems: A practical approach,” *International Journal of Control*, vol. 84, no. 6, pp. 1157–1170, 2011.

[5] W. Yang, G. Feng, and T. Zhang, “Robust model predictive control of uncertain linear systems with persistent disturbances and input constraints,” in *2013 European Control Conference (ECC)*, pp. 542–547, IEEE, 2013.

[6] A. Bemporad, M. Morari, V. Dua, and E. N. Pistikopoulos, “The explicit solution of model predictive control via multiparametric quadratic programming,” in *Proceedings of the 2000 American control conference. ACC (IEEE Cat. No. 00CH36334)*, vol. 2, pp. 872–876, IEEE, 2000.

[7] A. Afram and F. Janabi-Sharifi, “Theory and applications of hvac control systems—a review of model predictive control (mpc),” *Building and environment*, vol. 72, pp. 343–355, 2014.

[8] C. Bordons, F. Garcia-Torres, M. A. Ridao, C. Bordons, F. Garcia-Torres, and M. A. Ridao, “Model predictive control fundamentals,” *Model Predictive Control of Microgrids*, pp. 25–44, 2020.

[9] I. Hawila, S. Cerf, R. Bleuse, S. Perarnau, and E. Rutten, “Adaptive power control for sober high-performance computing,” in *2022 IEEE Conference on Control Technology and Applications (CCTA)*, pp. 403–410, IEEE, 2022.

[10] R. Pagano, S. Cerf, B. Robu, Q. Guilloteau, R. Bleuse, and É. Rutten, “Making control in high performance computing for overload avoidance adaptive in time and job size,” in *2024 IEEE Conference on Control Technology and Applications (CCTA)*, pp. 753–760, IEEE, 2024.

[11] G. A. Einicke and L. B. White, “Robust extended kalman filtering,” *IEEE transactions on signal processing*, vol. 47, no. 9, pp. 2596–2599, 2002.

[12] E. Weinan, J. Han, and J. Long, “Empowering optimal control with machine learning: A perspective from model predictive control,” *IFAC-PapersOnLine*, vol. 55, no. 30, pp. 121–126, 2022.
[13] M. Schwenzer, M. Ay, T. Bergs, and D. Abel, “Review on model predictive control: An engineering perspective,” *The International Journal of Advanced Manufacturing Technology*, vol. 117, no. 5, pp. 1327–1349, 2021.