Nowadays, evaluating the performance of a vehicle before the production phase is challenging and important. In the automotive industry, many virtual simulations are needed to model the vehicle behavior in the best possible way. However, these simulations require a lot of time without the user knowing their runtime in advance. Knowing the required time in advance would allow the user to manage the simulations more efectively and choose the best strategy to use the available computational resources. For this reason, we present an innovative data-driven method to estimate in advance the execution time of simulations. Our approach integrates unsupervised techniques, such as constrained k-means clustering, with classification and regression algorithms based on tree structures. In this paper, we present an innovative and hierarchical data-driven method for estimating the execution time of jobs. Numerous experiments were conducted on a real dataset to verify the efectiveness of the proposed approach. The experimental results show that the proposed method is promising.
waiting time can lead to wasted cluster resources.
Since the number of analysis and simulations that must
Today, more and more manufacturing industries rely be performed for a single product is considerable, it is on either online data centers or physical HPC clusters important to find a method to avoid wasting cluster reto run a large variety of tasks to perform analyses and sources and increasing delays. This issue is relevant in simulations. These tasks, or jobs, range from simulating the context of software application development for the individual mechanical components to analyze entire man- industrial domain and we want to address it by relying ufacturing processes. In this way, it is possible to shorten on an innovative methodology based on data analysis the time to market of the final product while reducing the and machine learning techniques. In order to predict number of errors made during the process. However, the the execution time of jobs, we have taken into account execution of these jobs often requires resources that may not only the HPC resources required by the diferent not be immediately available, thus delaying the job exe- jobs, but also the settings of the diferent solvers, that cution and increasing the time needed to obtain the final are the various kind of software used for analysis and results. In this paper, we present a data-driven methodol- simulation. Each simulation is characterized by a series ogy for predicting the jobs’ execution time. We focus on of parameters (specific for each solver) that describe its predicting the execution time of simulations and analysis configuration. These parameters are inserted manually because it directly afects the waiting time of other jobs from the user in phase of submission of the job and are before they are submitted and the problem of unknown then extracted in automatic way from the server used for running the simulations. The proposed approach is based on a hierarchical classification model. Our methodology is based on three separated models. The first model does a preliminary binary classification and then it divides the data accordingly. The other two models classify the two diferent portions of data, one portion of data for each model. In this way we are able to classify the data into four diferent classes while reducing the complexity of the task from a multiclass problem to a binary one at each step.
The rest of the paper is divided as follows. Section 2 deals with the literature review related to HPC, from resource allocation to runtime prediction. Section 3 deals with the proposed methodology, while Section 4 presents our results so far. Finally, in Section 5, we discuss our methods and future steps to continue this research.
the waiting time is impacted by many factors, such as
HPC specifics. Technical specifics aside, one factor that
impacts the waiting time of every simulation is the
execution time of the job that are running on the HPC. Some
studies have focused on this approach, such as [
While we agree on the centrality of the execution time we have adopted a diferent strategy compared to the studies mentioned before. As a matter of fact we use pretty much the same toolbox, i.e. clustering for data preprocessing and classification and or regression to estimate the execution time, however, as far as we know, we diferentiate ourselves from previous work through the use of a hierarchical approach, which will be explained in detail in the following section.
There are several approaches and studies investigating how to improve HPC resource allocation. Research activities can be classified as: (i) predicting job failures, (ii) developing scheduling algorithms based on machine learning techniques, and (iii) using simulation execution time estimation to predict the waiting time of jobs that have yet to be submitted. 3. Data-driven methodology The first research strand’s goal is to estimate if a specific job will fail or complete its execution. The intent is to The building blocks of the proposed methodology, shown stop prematurely those jobs that are predicted by the in Figure 1, are as follows: i) data cleaning, ii) model algorithms as failures [8, 6, 9]. By learning which jobs building and iii) model evaluation. Each of these steps is are more likely to fail and stopping them the HPC is able adequately described in the related subsection. to improve its performance, while saving energy that After the data collection phase, the generated dataset would be wasted[12, 7]. However this type of approach contains a record for each submitted job. These jobs may requires a lot of data in order to identify a pattern be- have been executed by diferent solvers. Here with solver tween the attributes and the target variables. The most we mean the software used to run the simulation, each significant variables can be extracted in diferent ways, of which is characterized by diferent model variables. either through some feature engineering process or from Due to the diferent parameters that characterize each diferent databases. Even so, parsing and transformation solver, and due to very diferent execution times between operations have been proven very useful in order to im- solvers, we decided to consider only one solver at a time, prove the prediction results [5] are extremely useful to thus avoiding working with a dataset too sparse. obtain better prediction results. The issue here is related to the fact that some failures are rare, hence they are not easy to predict, but still consume a lot of resources [10].
For example, Liu et al. [8] integrated two algorithms in order to estimate whether a job fails or not. The first algorithm is a clustering one. It measures the correlation among jobs from diferent contexts. The other one is a multitask learning algorithm trained on correlated jobs. Since our data is not enough to achieve meaningful results in this paper we do not tackle this problem.
Another research approach focuses on the optimization Figure 1: Schema of the proposed methodology
of the available resources performed by a scheduler.
After analyzing the behavior of successful and failed jobs,
Jassas et al. [6] investigated scheduling algorithms
intended to optimize the reliability and availability of cloud 3.1. Data cleaning
applications. Since the number of resources cannot be Since the parameters characterizing each job are entered
unlimited, large-scale HPC exploit waiting queues. How- manually by the user during the job submission phase, it
ever it has been proved by Nurmi et al. [11] that regard- is essential to check the correctness of the available data
less of the performance of a resources scheduler one of before using them for subsequent analysis.
the main factor that impacts the prediction eficiency is The data cleaning phase started with a collaboration with
the amount of time that a job has to wait before being domain experts, who, thanks to their knowledge, helped
submitted. Following this idea, also authors in [
We compared the number of jobs labeled as outliers with each of the 3 approaches, and in subsequent experiments we tried to evaluate how the performance of a predictive model varies depending on the preprocessing used.
The task of our model is to predict the execution time of a simulation running on a HPC. Since the goal is to predict a time that is a continuous value, this could be tagged as a regression task. However, the experimental results obtained by treating this task as a regression one led to poor results. This behavior can be justified by the fact that the data collection phase is quite recent, so the available data at the moment are not numerous. For this reason, we decided to treat it like a classification problem; this was made possible by categorizing the available runtimes, dividing them into classes representing contiguous time intervals. After this categorization, a classification algorithm can then try to predict in which range of values the execution time of the analyzed job will fall. In other words we have a multiclass problem. However, due to the scarce amount of data in our possession, the performance of our initial model was not enough. Since the amount of data is limited it is dificult for a classification algorithm to make good predictions in a multiclass context. On the other hand we did not want to oversimplify the problem by reducing the number of classes considered. Thus by implementing a classification hierarchical approach we were able to improve the goodness of the predictions without sacrificing too much quality. The 3.2.1. Classification Approach Unlike a single level classification where the model is trained only once on all available data, in the hierarchical approach a binary tree structure is used, in which each node of the tree corresponds to a binary classification where a model predicts to which of the two classes the job belongs. The depth of the tree depends on the number of total classes that we want to obtain (each of which represents a temporal range of values). The hierarchical binary structure we used in this methodology has two levels of depth, to which correspond 3 predictive models (nodes) and 4 total classes (leaves). Solutions with diferent depths have also been tested experimentally, but the one with four classes has demonstrated to be the best compromise between good models’ performance and enough detailed classes. An example of how the structure looks is reported in Figure 2. In this way every classifier has to deal with a binary classification problem, but overall the classes considered are four.
tire structure are the three conditions that determine in which sub-branch the obtained prediction must go. To each of these conditions corresponds a subdivision of the dataset (or of a portion of it), in two classes that represent diferent time intervals of the execution time of the jobs.
The overall performance of the classification method is
greatly influenced by the identified thresholds, so it is
important to try to define them as best as possible. To do
this, two diferent approaches have been tested:
• balanced approach: in each division of the
identified hierarchical structure, the available data
is divided into two classes, each containing the
same number of jobs. This technique prevents
any unbalanced class problem, allowing the
predictive model to be trained on balanced classes;
• k-means approach: the classes to use for training a
predictive model in each node of the structure, are
chosen in an automatic way through a clustering Figure 3: Mixed Approach Structure
algorithm. In particular, the k-means algorithm
is used, with K=2. In addition, to prevent the
proposed solution from leading to an unbalanced- 3.3. Model Evaluation
classes problem, we used a constrained version of
the k-means algorithm, in which a minimum size For the evaluation of every algorithm used in all the
perfor each cluster can be specified. In particular, formed experiments, we exploited the Leave-One-Out
the constraint we used here is that each identified Cross Validation (LOOCV) technique. Even if it is a
comclass had to contain at least 40% of the total jobs. putationally expensive technique, LOOCV results in a
reliable and unbiased estimate of model performance.
3.2.2. Mixed Approach Moreover, this method turns out particularly useful when
the data available are limited, like in our case in which
Several regression algorithms (XGBoost [
The experiments presented here show the actual results obtained and that motivate us to rely on the hierarchical classification approach. Section 4.1 ofers insight on the data that we have used to train our models. Section 4.2 discusses the efectiveness of the proposed techniques to correctly identify outliers and how they impact the selectivity of the dataset cardinality. Section 4.3 shows the performance of classifier models, both normal and with the hierarchical structure. Section 4.4 presents the results obtained with diferent regression algorithms and the hierarchical mixed approach.
Our data was extracted from a PBS (Portable Batch System) server used to run simulations of various nature, from aerodynamics to virtual crash tests, related to the automotive context. Our data belong to two main categories, i.e. explicit and implicit jobs. The implicit methods use 4.2. Data Cleaning an algorithm "step by step", in which an appropriate con- In this preprocessing phase we tried to remove all the vergence criterion allows the analysis to continue or not, jobs having an anomalous execution time compared to reducing the time increment, depending on the accuracy the runtimes of the other jobs. To do this, 3 diferent of the results at the end of each step. Using the explicit methodologies were tested as discussed in Section 3.1, methods does not have problems of non-convergence, based on: i) interquartile range (IQR), 95th centile, 99th since in this case the time increment is defined at the centile. The percentage of jobs labeled as outliers by each beginning and remains constant during the calculation. of the three techniques, separately by solver, is shown in After the data collection phase, the dataset contains about Table 2. 6000 records, each of which represents a job submitted in the cluster. Jobs can be performed by five diferent Table 2 solvers, depending on the type of analysis to be run. A The number of outlier jobs for each solver summary of the solvers contained in our dataset is given in Table 1. Due to the diferent parameters that characterize each solver, and due to very diferent execution times between solvers, the analyses described below consider only one solver at a time.
As a demonstration of the diferences between the solvers, Figure 4 shows the kernel density estimate (KDE) plot for the execution times of an explicit solver (Adams) and an implicit solver (Optistruct). KDE represents the data using a continuous probability density curve and the x-axis in the figure show how the jobs belonging to the two solvers occupy very diferent ranges of execution times, with much greater times for the explicit solver.
Since we can not know in advance which of the 3 techniques will lead to greater benefits, in the following analysis we compared the results obtained with diferent preprocessing techniques, evaluating then the best of them. However, from Table 2 we can see that the IQR and 95th centile techniques show rather similar results (with an average diference of about 3%); instead the 99th centile technique often identifies a very low percentage of outliers compared to the other techniques. For this reason, in the following analyses we will consider only the IQR and the 99th centile techniques, comparing the results obtained with these two diferent approaches.
Table 3 contains the F-score values obtained using the 99th centile as preprocessing step and the k-means for thresholds identification, since it is the configuration with which the best results were obtained. For each solver, the first column of the table shows the results for the first classification level (where the first two classes are identified), while the second column contains the F-score values obtained in the second level of classification (classes 1 and 2 for the left sub-branch, classes 3 and 4 for the right sub-branch). To better illustrate our methodology, a focus on a specific solver is also represented in Figure 5, that shows the hierarchical approach specifically for the Nastran solver, indicating the relevance of the identified classes in a real context. The predictive model used in all the nodes is the XGBoost and on the figure are indicated the F-Score values for each prediction. Here, the implemented model is able to predict quite eficiently whether the execution time of an analyzed job will be less than 8 minutes, between 8 and 16 minutes, between 16 and 30 minutes, or greater than 30 minutes. For solvers with diferent characteristics obviously diferent thresholds will be obtained; however the results in the Table 3 indicate that, except for the Radioss solver (where the results obtained are below the average behavior), for all solvers we are able to predict quite accurately which class a job should belong to. baseline against which we want to compare our methodology. The table shows the results obtained with both the two preprocessing techniques (IQR vs 99th centile) and with both the strategies to define the subdivision in classes (k-means vs balanced approach). For reasons of space, each solver has been indicated in this table only by its initials (Ad, R, N, O, Ab); moreover, ’K-M’ stands for k-means, while ’Bal’ indicates the balanced approach. Comparing the f-score values obtained in the two methodology, it is evident how the hierarchical structure allows to obtain better performances than the baseline approach, whatever preprocessing technique is used.
guish two categories of jobs, the R2 values obtained in the second regression level are now higher than those obtained with the Nastran solver using the baseline approach. Moreover, the mean absolute error (MAE) values shown in Figure 6, indicates that the average error associated with jobs that last less than 16 minutes is just over one minute (69 seconds), therefore an acceptable error in our use-case. Regarding instead the mean absolute error associated with jobs that last longer than 16 minutes, this one turns out to be about 11 minutes, so a bit more impactful.
The error grows as execution times increase. So, for the considered solver, the better choice could be to adopt techniques of regression in order to estimate low execution times; and to use instead a classification approach in order to predict the classes to which the job will belong when it deals with longer execution times.
We have presented a classification hierarchical model which is able to address a multiclass problem by dividing its complexity among multiple prediction layers. In this way every classifier has to deal with a binary classification problem, instead of a multiple classification. Even if the amount of data in the considered use case is limited our approach has shown a promising performance also compared to single prediction level approaches. Especially in the classification context the hierarchical approach performs better than the normal approach. We have also tried some experiments in which more than one solver is taken into account. However, due to the fact that every solver takes into account a diferent set of variables the resulting dataset is very sparse. This issue combined with the limited amount of data leads to poor predictions with both the hierarchical approach and a single prediction level method. Once that the data in our possession has reached a higher numerosity, it will allow us to investigate whether or not our hierarchical approach can outperform more classical approaches in a more complex environment. A higher amount of data means that the impact of the diferent variables taken into account will be reduced. Currently we are still working on this project and we already have diferent improvements that we want to address. We will keep gathering more data that will allow us to build more stable and robust models. We also intend to further investigate the possibility of building a model that is able to make predictions on the whole set of solvers, instead of relying on a diferent model for every solver. Finally we intend to integrate our model inside the HPC structure in order to help it assess the pending time of newly submitted jobs. putacionais de Alto Desempenho, Belo Horizonte, Statistical Society Series B 73 (06 2011), 273–282. 72–83. https://doi.org/10.2307/41262671 [5] S. Ganguly, A. Consul, A. Khan, B. Bussone, J. [14] Hao Wang, Yi-Qin Dai, Jie Yu, and Yong Dong. 2021.
Richards, and A. Miguel. 2016. A Practical Approach Predicting running time of aerodynamic jobs in to Hard Disk Failure Prediction in Cloud Platforms: HPC system by combining supervised and unsuperBig Data Model for Failure Management in Datacen- vised learning method. Advances in Aerodynamics ters. In 2016 IEEE Second International Conference 3 (03 2021). https://doi.org/10.21203/rs.3.rs-360961/ on Big Data Computing Service and Applications v1 (BigDataService). 2016 IEEE Second International [15] Jiawei Yang, Susanto Rahardja, and Pasi Fränti. Conference on Big Data Computing Service and 2019. Outlier Detection: How to Threshold Outlier Applications, Oxford, United Kingdom, 105–116. Scores?. In Proceedings of the International Conferhttps://doi.org/10.1109/BigDataService.2016.10 ence on Artificial Intelligence, Information Processing [6] M. Jassas and Q. H. Mahmoud. 2018. Failure Anal- and Cloud Computing (AIIPCC ’19). Association for ysis and Characterization of Scheduling Jobs in Computing Machinery, New York, NY, USA, ArtiGoogle Cluster Trace. In IECON 2018 - 44th An- cle 37, 6 pages. https://doi.org/10.1145/3371425. nual Conference of the IEEE Industrial Electronics 3371427 Society. IECON 2018 - 44th Annual Conference of the IEEE Industrial Electronics Society, Omni Shoreham, United States, 3102–3107. https://doi.org/10.
1109/IECON.2018.8592822 [7] P. Li, B. Zhang, Y. Weng, and R. Rajagopal. 2017.
A Sparse Linear Model and Significance Test for Individual Consumption Prediction. IEEE Transactions on Power Systems 32, 6 (2017), 4489–4500.
https://doi.org/10.1109/TPWRS.2017.2679110 [8] Chunhong Liu, Liping Dai, Yi Lai, Guinbing Lai, and
Wentao Mao. 2020. Failure prediction of tasks in the cloud at an earlier stage: a solution based on domain information mining. Computing 102 (2020), 2001– 2023. https://doi.org/10.1007/s00607-020-00800-1 [9] C. Liu, J. Han, Y. Shang, C. Liu, B. Cheng, and
J. Chen. 2017. Predicting of Job Failure in Compute Cloud Based on Online Extreme Learning Machine: A Comparative Study. IEEE Access 5 (2017), 9359–9368. https://doi.org/10.1109/ACCESS.2017.
2706740 [10] J. M. Navarro, G. H. A. Parada, and J. C. Dueñas.
2014. System Failure Prediction through RareEvents Elastic-Net Logistic Regression. In 2014 2nd International Conference on Artificial Intelligence, Modelling and Simulation. IEEE, Madrid, Spain, 120– 125. https://doi.org/10.1109/AIMS.2014.19 [11] D. Nurmi, A. Mandal, J. Brevik, C. Koelbel, R. Wolski, and K. Kennedy. 2006. Evaluation of a Worklfow Scheduler Using Integrated Performance Modelling and Batch Queue Wait Time Prediction. In SC ’06: Proceedings of the 2006 ACM/IEEE Conference on Supercomputing. IEEE, Tampa, FL, USA, 29–29.
https://doi.org/10.1109/SC.2006.29 [12] A. Rosà, L. Y. Chen, and W. Binder. 2017. Failure
Analysis and Prediction for Big-Data Systems. IEEE Transactions on Services Computing 10, 6 (2017), 984– 998. https://doi.org/10.1109/TSC.2016.2543718 [13] Robert Tibshirani. 2011. Regression shrinkage selection via the LASSO. Journal of the Royal