# Log Analysis-Based Resource and Execution Time Improvement in HPC: A Case Study
## 3 Backfilling Algorithm  
Backfilling scheduling is a method of rearranging the order when a small job cannot be performed due to a relatively large predecessor job This aims to improve performance by placing small-scale jobs that can be executed first, while maintaining fairness. In order to apply this algorithm, the user must specify the size and execution time of the task.  
This algorithm can improve performance with fairness. In backfilling scheduling, the execution time and size of each job must be specified. In this work, we traced and analyzed the job logs executed by the scheduler. As a result, we identify the idle resources that have not been used for a certain period of time and perform an experiment to optimize resource utilization by applying a backfilling algorithm [28].  
The conservative backfilling algorithm is a basic version, and it adheres to the FCFS scheme, which is the basic principle of scheduling, and running first when a subordinate job satisfies a fragmented resource. In general, batch jobs submitted to the scheduler have attributes for required resources and execution time. The backfilling algorithm also has these two properties. For this mechanism, there are two data structures. The first is a list structure that stores jobs and execution time of the queue list and the second is the resource processor profile to be used.  
This algorithm requires no latency for prior jobs due to subordinate jobs but cannot guarantee the planned sequence of jobs if the preceding job is terminated earlier than the expected time. Therefore, there is a more advanced algorithm for this, which is called EASY (the Extensible Argonne Scheduling System) backfilling [28; 29]. However, the experiment in this study simulates the performance improvement through backfilling at a fixed time for a large-scale job and therefore excludes the case where the job ends before the expected time. Figure 5 and Algorithm 1 show the conservative backfilling algorithm and how it works, respectively.  
The 1 st priority queued job does not have enough resources to run, so it will be scheduled after the two running jobs (\(a\)) and (\(b\)) have ended. The 2 nd priority queued job finds the available resource point (\(t_{1}\)), as indicated by the dotted line in Figure 5. Then, from this point \(t_{1}\) to the end of the execution, it checks whether it is possible to free up resources. However, at \(t_{2}\), the 1 st priority queued job is waiting and the 2 nd priority queued job will delay it. The 2 nd priority queued job can potentially free up resources if only one predecessor is terminated. However, the execution time of this job delays the predecessor, so a new start point must be found. In other words, it is a mechanism that prevents future arrivals from delaying previous pending operations. Finally, the 3 rd priority queued job is backfilling because there is enough gap to do the job.  
```
data:Running job is \(j_{i}\),  Queued job \(Q_{j}(p,t)-Q_{j}(p)\) is required processors, \(Q_{j}(t)\) is required time  Total available resource of system is \(S\)  Total used resource at time \(t_{i}\) is \(P(t_{i})\) for queued job \(Q_{j}\in Q\)do  Sort by execution time(\(\forall\)) if\(S\)-\(P(t_{i})\geq Q_{j}\) (\(p\))then  if\(i_{i}-\mathfrak{t}_{i-1}>Q_{j}\) (\(t\))then  JobAllocation(); \(P(t_{i})\gets P(t_{i})+Q_{j}\) (\(p\)); // Resource update \(T_{i+1}\gets T_{i}+Q_{j}\) (\(t\)); // New time stamp insert  For time stamp index from \(T_{i+1}\) to \(T_{end}\)do  IncreaseIndex(\(T_{i+1}\)); endfor \(j\gets j+1\); else \(i\gets i+1\); next;  endif  else \(i\gets i+1\);  next;  endif  else \(i\gets i+1\); next; endif  endfor
```  
**Algorithm 1**Conservative backfilling