# [PERSON]: An HPC Job Scheduler Using Deep Reinforcement Learning and Remaining Time Prediction
## 3 RLSchert
### The Scheduler with Remaining Runtime Prediction Based on PPO  
Based on the five-tuple definition of RLSchert, we used the most advanced DRL algorithm, PPO, to train the scheduling policy. The scheduling policy is represented by a deep neural network, \(a_{t}\sim\tau_{\theta}(\cdot|s_{t})\). The policy predicts the action \(a_{t}\) based on the current simulator state \(s_{t}\). First, we describe the update rule of PPO. In each episode, a set of jobs arrive and are scheduled for execution. When all jobs are finished, the episode is complete. All data \((s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},\cdots)\) generated in the episode are used to update the policy network. To speed up policy training, we used parallel PPO [24], as shown in Figure 4.  
The parallel PPO runs multiple simulators to generate data and then trains the policy network. These processes run independently to generate samples that are saved in the experience memory (EM). The global policy network samples data from the EM and updates the policy parameters by PPO. Then, we synchronize the latest policy network with each subprocess network. Through parallel sampling, the speed of the samples' generation increases, and the correlation between samples reduces. The RLSchert with runtime prediction before the job runs has the same training process, but the reward function \(R\) and state transition \(P\) are different. Specifically, in the slowdown metric, the first part of reward function is \(\sum_{j\in RunningQueue}-1/Predictor(j)[0]\).  
Algorithm 1 shows the pseudocode of PPO. In the parameters of the algorithm, _batchsize_ is the number of data used at each policy update. _epochs_ represents the maximum training steps of RLSchert. _pop_epoch_ is the maximum training steps. _KLtarget_ represents  
Figure 4: The parallel PPO algorithm.  
the stop condition of the PPO update. \(\gamma\) is the discount factor. \(\eta\) is the learning rate, and \(E\) is the number of parallel simulators.  
```
0: batch size, epochs, ppo_epoch, KL target, \(\gamma\), \(\eta\), \(E\)
0: RLSchert \(\pi_{\theta}\)
1: initialize \(E\) parallel simulators
2: randomly generate an \(E\) job sequence to each simulator
3:for\(t=1\) to epochsdo
4:for\(e=1\) to \(E\)do
5: interact with simulator e with the latest policy \(\pi_{\theta}\)
6: put the trajectory \((s^{e}_{1},a^{e}_{1},r^{e}_{1},v^{e}_{1},p^{e}_{1},s^{e}_{2},a^{e}_{2},\cdots)\) into the EM
7: calculate the cumulative rewards \(R^{e}_{t}=\sum_{t^{\prime}\geq t}\gamma^{t^{\prime}-t}r^{e}_{t^{\prime}}\)
8: calculate the advantage function \(A^{e}_{t}=R^{e}_{t}-v^{e}_{t}\)
9:endfor
10:for\(i=1\) to ppo_epochsdo
11: sample a mini-batch of data from EM \((s_{t},a_{t},r_{t},v_{t},p_{t},R_{t},A_{t},s_{t+1})\)
12: update the parameters of policy network \(\Delta\theta\leftarrow\Delta\theta+\eta\
abla_{\theta}\frac{\
abla_{\theta} \pi_{\theta}(a_{t}|s_{t})}{p_{t}}A_{t}\)
13: calculate the KL value \(KL(\pi_{\theta}(a_{t}|s_{t})||p_{t})\)
14:if KL > 1.5 \(\times\) KL target then
15: break
16:endif
17:endfor
18:endfor
```  
**Algorithm 1** The RLSchert with remaining runtime prediction based on PPO.