<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Estimating the job's pending time on a High-Performance Computing cluster through a hierarchical data-driven methodology</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Fabio Carfí</string-name>
          <email>fabio.carfi@polito.it</email>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Vladi Massimo Nosenzo</string-name>
          <email>vladi.nosenzo@cnhind.com</email>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Data-driven methodology, HPC cluster, Hierarchical Classifica-</string-name>
          <xref ref-type="aff" rid="aff2">2</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Enrica Capitelli</string-name>
          <email>enrica.capitelli@external.cnhind.com</email>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Tania Cerquitelli</string-name>
          <email>tania.cerquitelli@polito.it</email>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>CNH Industrial</institution>
          ,
          <addr-line>Turin</addr-line>
          ,
          <country country="IT">Italy</country>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>Department of Control and Computer Engineering</institution>
          ,
          <addr-line>Politecnico di Torino, Turin</addr-line>
          ,
          <country country="IT">Italy</country>
        </aff>
        <aff id="aff2">
          <label>2</label>
          <institution>tion Approach</institution>
        </aff>
      </contrib-group>
      <abstract>
        <p />
      </abstract>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>Nowadays, manufacturing industries have to shorten the time
to market to satisfy customers’ needs and survive in globally
competitive contexts. For these reasons, all the steps required
to create new products need to be optimized as much as
possible to minimize the overall execution time. Technologies like
CAD (Computer-Aided Design) and CAE (Computer-Aided
Engineering) are useful in this process. At the same time, Finite
Element Methods are fundamental because they allow
performing simulations, not only of mechanical components but also of
an entire manufacturing process. Doing so, there is the
possibility to avoid errors which would entail the need to carry out
further operations and, therefore, increase execution time during
the product’s creation. In the context of heavy simulations
performed on High-Performance Computing (HPC) architectures, it
is challenging to estimate each job’s pending time, i.e., the time
between the job submission and the job execution starting time.
This information could support the optimization of the resource
requests, drastically reducing the waiting times needed to obtain
the simulations’ results. This paper presents an innovative and
hierarchical data-driven methodology to estimate the discretized
value of pending time, i.e., estimating the range time that a job
will have to wait before the necessary hardware resources are
supplied for its execution. A large set of experiments have been
performed on a real dataset collected in an Italian industrial
context to assess the proposed approach’s efectiveness in correctly
and accurately predict the pending time’s discretized value. This
work is a preliminary step towards implementing a scheduling
system based on machine learning techniques.</p>
    </sec>
    <sec id="sec-2">
      <title>INTRODUCTION</title>
      <p>
        Nowadays, manufacturing industries make extensive usage of
physical HPC clusters[
        <xref ref-type="bibr" rid="ref8">8</xref>
        ] or online data centers to execute a huge
amount of simulations for mechanical components or entire
manufacturing processes. In this way, it is possible to slightly reduce
incoming errors related to the final product, trying to shorten
the time needed for its creation. The problem is that these
simulations request lots of resources that are often not immediately
available, increasing the time needed to start the job execution
and, consequently, obtaining the final results. The waiting time,
but also the execution time, can also be afected by hardware,
software, node, and many other types of failures that can occur,
wasting cluster resources [11, 24]. Generally, many simulations
are needed for a single product and, for this reason, there is the
necessity to overcome these problems. The topic is significant in
the real context of software applications development in the
industrial field. This requires eficient and innovative solutions that
can benefit from data analytic and machine learning techniques.
Some research studies have addressed this research issues.
The available data to be analyzed are characterized by a strong
class imbalance (both in the categorical and continuous context)
because most of the submitted jobs have limited waiting times,
while only a limited part of them request high waiting times. The
estimation of these times is challenging because it is influenced
by diferent factors (like, for example, the computation type, the
parameters used to run the simulations, the available resources’
usage, and many others) not known a priori.
      </p>
      <p>First, we consider a set of features describing the job
submission’s context. Some of them were available within the database
provided (like the amount of resources requested to run the job,
the software to use, and the submit, start and end times available
for each job). We will refer to them as the accounting data. In
contrast, other attributes related to the HPC cluster context (like
the number of jobs in the queue and the number of running jobs
at the submit time) have been identified using a feature selection
process, detailed in Section 3.2, to which we will refer to as
context data. It is also essential to notice that developing an efective
data-driven methodology would create a strong impact in using
HPC’s hardware resources, whose optimization would
significantly reduce software testing costs. The implemented solution
belongs to the hierarchical classification and it is composed by
three classification levels, each one characterized by thresholds
(for the definition of the local class of prediction) and training
records that depends on the results of the previous level.
The paper is organized as follows. Section 2 illustrates the related
work concerning the optimization of resources allocation in the
HPC context. In Section 3 a brief description of the data is given,
discussing the cleaning and feature engineering operations used
to build the dataset, avoiding as many outliers as possible, and
also depicting the solution implemented, describing all the main
parts that compose it and the most important features provided.
Section 4 discusses the experiments executed during the
implementation process. In fact, the proposed methodology has been
validated on a real-data set collected in the context of a CNH
(an American-Italian UK-headquartered multinational
corporation) HPC cluster, proving the efectiveness and accuracy of the
methodology in making correct predictions. Finally, in Section 5,
we conclude the paper by proposing some future improvements
of the proposed data-driven methodology towards implementing
a scheduling system based on machine learning techniques.
2</p>
    </sec>
    <sec id="sec-3">
      <title>RELATED WORK</title>
      <p>Some studies have addressed fundamental aspects for the
improvement of resources allocation. In fact, the scientific literature
has focused on two main problems: (i) the job failure prediction
and (ii) the implementation of scheduling algorithms based on
machine learning techniques.</p>
      <p>
        The first approach aims to predict how a specific job will end
its execution, estimating if an error will occur or the results
will be returned. The implemented algorithms try to stop those
jobs whose termination status is predicted as a failure [9, 11, 12],
independently of its type. The study of unsuccessful jobs and
tasks execution can improve the performance and the energy
saving of an entire HPC cluster [10, 19], but request lots of data to
be used to define a pattern between the attributes and the target
variable. The most significant variables can be available from the
start, saved in diferent databases, or extracted from the available
data with some feature engineering processes. Anyway, it is
important to notice how parsing and transformation operations
[
        <xref ref-type="bibr" rid="ref6">6</xref>
        ] are extremely useful to obtain better prediction results. Some
failures are not so easy to predict because they are rare, meaning
that they occur fewer times than the other, but can anyway
produce lots of waste of energy and resources [14]. For example,
Liu et al. [11] implemented a system for the failure prediction
composed of two main algorithms: the first one is a job clustering
algorithm used to measure the correlation among jobs with a
various number of tasks. In contrast, the second one is a multitask
learning algorithm used to get similar information from diferent
correlated jobs. In this paper, however, we do not address this
problem because the data available are not suficient to achieve
reliable results.
      </p>
      <p>A parallel research approach has been devoted to studying how
a scheduler can optimize the available resources. Jassas et al. [9]
also suggested, after the analysis of finished and failed jobs
behavior, the development of scheduling algorithms to improve the
reliability and availability of cloud applications. In large-scale
HPC, a waiting queue is needed when the system is highly
employed, whereas the number of resources cannot be unlimited.
With their studies, Nurmi et al. [15] have confirmed that, despite
the prediction eficiency of a resources scheduler, the
performance is also afected by the job’s waiting time that increase
when there are limited resources.</p>
      <p>Among the open issues in the research field of industrial software
development, the design of a data-driven HPC cluster scheduler
to optimize the resources allocation is challenging. To this aim,
this paper proposes a data-driven methodology for estimating
a job’s pending time by combining other techniques available
in the state-of-the-art appropriately. Like Park [16], we study,
design, and develop a data-driven model to improve the scheduler
performance by analyzing the jobs log file. Unlike Park, we derive
a prediction model estimating the uncertain time of the submitted
job.
3</p>
    </sec>
    <sec id="sec-4">
      <title>THE PROPOSED METHODOLOGY</title>
      <p>Here we present our data-driven methodology to derive a
predictive model that estimates the pending time of submitted jobs. The
proposed methodology follows the KDD (Knowledge Discovery
from Database) main steps [23], starting from the analysis of the
available data up to the deployment of a model able to predict
the time interval of the target variable with good performance.</p>
      <p>Among all the variables within the accounting data table, the
attributes concerning the number of requested resources, like
the number of CPUs requested or the software to use for the
job execution, were highlighted as useful, along with the times
related to the execution itself (submit, start and end of the job),
while many others were discarded, due to a low utility for the
model learning process (like in the case of the user identifier)
or the high presence of missing values. On the other hand, the
majority of the context attributes were selected for this prediction
problem. The cardinality of accounting and context data is about
25 thousand records, after the cleaning process.</p>
      <p>Given the dificulty of the problem, a specific analysis of the
available data was made so that the prediction categories could be
defined. Based on the results of the data exploration step and the
discussion with the domain experts, the classes of interest were
defined as follows: negligible or not (identified by a 60-seconds
threshold), greater or less than one hour, or other sub-ranges of
the last step. Through these three levels, it is possible to support
the user in deciding whether or not to submit the job at that
specific moment.
3.2</p>
    </sec>
    <sec id="sec-5">
      <title>Data preparation and exploration</title>
      <p>Some cleaning operations were necessary to remove possible
errors within the accounting data. The cleaning process involved:
1) the elimination of all those records that have not started their
execution (run time equal to 0), indicating the presence of
hardware problems that invalidate the execution of the job, 2) the
deletion of variables that do not provide any useful information
such as the alphanumeric identifier of the user that submitted it,
3) the removal of all the duplicate jobs present inside the dataset,
as well as 4) the deletion of those records characterized by
ambiguous attribute values that cannot be inferred or computed.
Besides, we search for a status variable associated with each
job, found inside PBS (Portable Batch System, the simulations
manager) raw files, reporting possible software problems during
the submission of the job and all those records with a value that
difers from 0 were deleted. Carrying out the cleaning operations,
the data available went from 105 thousand records to just over 25
thousand, minimizing the possibility of prediction errors caused
by external conditions.</p>
      <p>The above-mentioned dataset does not contain any reference to
the status of the HPC cluster at the submission time, data that
would be extremely useful for predicting the waiting time of a
job. For this reason, using the information regarding both queue
on which the job is launched and the submit, start, and end times
associated with its execution, a feature engineering process has
been carried out to extrapolate the attributes that allow
characterizing the HPC context at the submit time of each available
record. Almost all the available data were used, applying only a
selection of the data cleaning operations previously analyzed, as
jobs that cannot be useful for the prediction process hold anyway
the resources of the HPC cluster and therefore conditioned the
times of other jobs submitted later. After the entire extraction
process, we selected only the records with the information
related to those jobs that were not afected by the accounting data’s
cleaning operations. With this feature engineering process, we
have extracted, for each tuple, the number of jobs that, at the
submission time, were waiting for the necessary resources, the
number of those that, instead, was in execution, the total waiting
and execution time up to that moment, the number of cores and
nodes available at the submission time.</p>
      <p>The data preparation is a semi-supervised process that has been
executed manually, step by step. As usual, the pre-processing
is a custom pipeline requiring a strong interaction with the
domain experts to continually assess the selected data’s quality and
remove noisy data. It includes diferent steps deeply dependent
on the key aspects of available data and the feedback given by
domain experts to assess each cleaning step’s correctness and the
quality of the obtained results. The proposed strategy strongly
depends on available data, and it is not easy to generalize the
procedure to be used in a diferent setting.</p>
      <p>Finally, after obtaining the necessary information, exploratory
analyses were carried out on both accounting and context data
to extract as much knowledge as possible to use for the
prediction algorithm. We studied mainly the distribution of variables,
through tests such as Shapiro-Wilk [20] and graphical
visualizations like bar charts or box plots [13], and also the type of
relationship between the variables, using correlation matrices,
generated with the Spearman correlation coeficient [ 22], and
tests such as  2(Chi-squared) and 2(Eta-squared). More
specifically, we studied the distribution of the target variable for the
accounting data through some clustering operations that have
highlighted the high presence of values in the low part of the
range. About the correlation matrix of the context data, reported
in Figure 2, we looked at the cells containing values greater than
0.85 or lower than −0.85 because, in this case, only one of the two
attributes should be considered, being the two highly statistically
related. Besides, the distribution analysis has been deepened
for accounting data, also performing descriptive analysis and
clustering operations.
Here we discuss the distribution of the target variable, by means
of diferent statistical methods (see Figure 3, 4 and 5), and explain
the decision taken to define the prediction classes.</p>
      <p>Figure 3 shows the frequency of pending time value of every job
available in the real dataset, highlighting for each classification
level, represented in Figure 3a, 3b and 3c, the thresholds applied.
It is important to notice that as levels increase, the classification
is more specific and ranges are more limited. The x-axis have a
logarithmic scale to represent all the data available, while the
yaxis have a linear scale in which the absolute frequencies of each
value are reported. The higher frequencies are observed for values
less than 60 seconds, noting that around this value, the curve
tends to flatten on frequencies close to 0. This because, for values
higher than this threshold, as also shown by the graph in Figure 4,
there is a low number of jobs compared to those belonging to the
ifrst prediction class. On the other side, for values greater than 60
seconds the variability of the attribute increases, as shown by the
low frequencies displayed in Figure 3. The records’ distribution
in the diferent classes shows, in fact, a clear imbalance between
class 0 and the others, being the first class cardinality eight or
more times higher than the other classes. However, this can be
considered acceptable in a real context since, for times less than
a minute, the wait can be considered negligible, highlighting a
good CNH HPC cluster sizing.</p>
      <p>Figure 5 shows the distribution of the target variable for each
specific prediction class. From this representation a highlighted
aspect is the presence of outliers within the clusters at the
extremes, which means that boxplots are crushed on the lowest
values of the graph. On the other hand, for the other clusters,
one information that can be derived is that most of the values
belonging to each cluster tend to concentrate around the median.
From the analysis of the boxplots, in addition to the dispersion
of the data around the median, it is also clear that there is a
higher medium-low values frequency within the clusters, which
explain the downward displacement of the box. This confirms
the existence of a positive asymmetry, as already highlighted by
the bar chart shown in Figure 4.</p>
      <p>It is possible to say, that each one of the three classification levels
of the implemented system has a specific objective:
• The first level’s objective is to identify those jobs that have
a negligible waiting time.
• The second level points to provide feedback to the user,
giving him the ability to decide whether to wait to submit
the job, considering that the threshold is an hour.
• The third manages more critical situations, specializing
the results obtained by the second level.</p>
      <p>
        The choice of thresholds’ values for each classification level is
experimentally-driven, meaning that it is based entirely on the
results of experiments previously conducted, the results of which
are discussed in Section 4. The identification of the classes to be
predicted, in terms of ranges for each of them, for the first level
has been defined with a data-driven approach. An iterative
process based on classification was used, with several classes ranging
from 20 to 2. The search ended in correspondence with the best
results, identified by a binary classification with a 60-seconds
threshold. This one admits distinguishing between negligible
times and the most significative ones firstly. In fact, with a time
less than 60 seconds, every time can be considered as acceptable.
The values obtained by all the experiments (see Section 4) are
reported in Table 5, 6, 7 and 8. From the evaluation of the
models, which results are reported in Table 1, we decided to use the
MLP (Multi-level Perceptron) [
        <xref ref-type="bibr" rid="ref7">7</xref>
        ] for the prediction of the first
classification level.
      </p>
      <p>Considering that the results for class 0 are extremely meaningful,
with a 94% of correct predictions, we decided to apply the other
levels only to class 1. Considering the low data availability (about
six thousand records, i.e., the ones correctly classified in the first
step), we decided to perform another binary classification. The
classes thresholds have been set after performing diferent
experiment to find a good trade-of between the prediction reliability
and the number of associated records for each specific class. After
ifnding a compromise by using a 3, 600-seconds threshold, we
studied the behaviour of all the algorithms, obtaining the results
reported in Table 2, which highlight the suitability of the MLP as
classifier of the second level.</p>
      <p>
        We decided to apply a further classification to both of the second
level classes for the third level. For the first one, whose range
goes from 60 to 3, 600 seconds, considering that the range is quite
narrow, we opted for a binary classification with a 900-seconds
threshold, thus creating classes 1.0.0 and 1.0.1, suficient to give
users fairly precise feedback. To decide which model was the
most accurate in the assignment of records belonging to class 1.0,
an evaluation of the algorithms has been carried out, obtaining
the values shown in Table 3, from which we derived that the
Decision Tree [
        <xref ref-type="bibr" rid="ref3">3</xref>
        ] was the one that better fits the situation. For
the classification applied, instead, for the class 1.1 of the second
level, considering that the range is wide (from 3, 600 seconds up to
a few days of waiting), a binary classification was not the proper
approach. From the multi-class experiments previously executed
(discussed in Section 4.2), we noted that the one with higher
results was a 3-class classification, which shows also a great
improvement compared to the other experiments (taking into
account the results reported in Table 6). In this context, the 7,
200and 10, 800-seconds thresholds adopted to create classes 1.1.0,
1.1.1 and 1.1.2 were defined to meet some conditions: 1) do not
compromise too much the performance and 2) obtaining classes
to return meaningful feedback to the users. After identifying
these fundamental characteristics, we examined all the selected
algorithms and, from the results obtained and reported in Table
3, it was possible to highlight that the Decision Tree was the one
that better fits the situation.
3.4
      </p>
    </sec>
    <sec id="sec-6">
      <title>Data modeling</title>
      <p>The solution found is part of the category known as hierarchical
classification [ 21] (a specific case of ensemble learning [ 17]) in
which more algorithms are used to predict the belonging class.
In fact, the system created, whose schema is shown in Figure 6,
is composed of several prediction levels in which the algorithms’
training depends on the class predicted in the previous level.
Only correctly classified records are reused for the algorithm’s
training in later levels, resulting in a physiological decrease of
records each time you move to a following level.</p>
      <p>The algorithms that make up the system are the MLP and the
Decision Tree. The first one belongs to Neural Networks. The final
model comprises several interconnected layers, each composed
of many neurons, where each connection has a weight associated.
These algorithms’ learning process is based on the adaptation of
the weights to minimize the diference between the real value
and the predicted one. These are good algorithms for real-time
predictions but are characterized by a high initialization time. On
the other hand, Decision Trees are non-parametric algorithms
able to predict the target variable value through simple conditions
inferred from the data. The final model is made up of nodes
(specific variables), branches (possible values of the variables),
and leaves (final class of prediction). This algorithm is easy to
visualize and understand why a specific value is returned but is
low-generalizable. Even a small variation of a variable value is
enough to change the final result completely.</p>
      <p>In Figure 6 we try to schematize the operation of the
hierarchical process with which the best results have been obtained. In
essence, all the steps that the system performs to assign the most
appropriate class are depicted, given the input variables provided.
As it is possible to see in Figure 6, we refer to the first level ranges
as Class 0 and 1, to the second level as Class 1.0 and 1.1 and to
the third level as Class 1.0.0, 1.0.1, 1.1.0, 1.1.1 and 1.1.2.
3.5</p>
    </sec>
    <sec id="sec-7">
      <title>Model characterization</title>
      <p>It is important to note that all the algorithms that make up the
hierarchical model must be interpretable so that, starting from
specific input values, it is clear the process for which a certain
value is returned. This is implicit for the Decision Trees used in
the third level. They are algorithms that can be interpreted by
definition, giving the possibility to draw the entire rules’ tree.
Instead, in the case of the two MLPs used for the classification
(a) First classification level
(b) Second classification level
(c) Third classification level
of the first and second level, being these considered as black
box algorithms, it was necessary an intermediate step of
interpretability with the use of Decision Trees: the latter is provided
with the input variables of each MLP, while as target variable the
predictions made by the MLP are used. This process is outlined
in Figure 7.
Using these tests, the results obtained are extremely accurate
since the Decision Tree employed for the first level explains the
MLP to 99%, while the one used in the second level to 93%.
3.6</p>
    </sec>
    <sec id="sec-8">
      <title>Data prediction</title>
      <p>Every time a new job arrives, the first level MLP is used to classify
the record. If the classification result is 0, the prediction system
stops, meaning that this job will wait at most 60 seconds before
entering in execution. Diferently, if the result of the classification
is 1, the system passes to the second level of the system, that will
perform a binary classification again with an MLP classifier, and
then to the third one, depending on the class predicted in the
second level, to better understand the range to which the real
pending time belongs. In fact, if the result of the second level is 0,
in the third level is performed a binary classification, while, if the
result is 1 will be performed a 3-class classification, in both cases
using a Decision Tree classifier. The diferent approach adopted
for the two third-level predictions derives from the diference
between the classes 1.0 and 1.1 (the first from one minute to one
hour, while the second ranges from more than one hour to a few
days of waiting), even if the number of training records is quite
the same.
3.7</p>
    </sec>
    <sec id="sec-9">
      <title>Model evaluation</title>
      <p>For the evaluation of every algorithm used in all the performed
experiments, subsequently reported in Section 4, we employed
two diferent strategies: (i) for the regression experiments (see
Section 4.2) we used the -fold cross validation, (ii) while for the
classification ones we used the stratified -fold cross validation.
Both these strategies can obtain reliable estimates of the
algorithms’ performance when they work with unseen data, finding
an acceptable bias-variance trade-of [ 18]. These techniques are
used to assure the robustness of the models’ results. This section
also defines how and when we used them, giving details on the
-parameter used in the diferent experiment types and the final
solution implemented.</p>
      <p>The -fold cross validation is a well-known state-of-the-art
strategy widely used in the machine learning and data mining
community to estimate the performance of supervised algorithms,
assessing the validity of the experiments’ results. It is composed
by some simple steps:
1) Split the dataset into  disjoined groups (subsets)
2) For each subset:
• Take the group as test set
• Take the remaining  − 1 groups as training set
• Fit a model on the training set and evaluate it on the
test set
• Retain the evaluation and discard the model
3) The model performance is estimate as the average of the
 experiments executed
The stratified -fold is a particular case of the -fold cross
validation, which retains, in each group, the same label distribution of
the entire dataset.</p>
      <p>By using these two strategies we can ensure that the presented
results, reported in Section 4, are robustly evaluated, minimizing
the possibility of occurring errors.</p>
      <p>The  value is selected considering the cardinality and the type
of the available data, but, generally, 10 is a good standard value.
For the regression experiments we used a -fold cross validation
with  = 10 and also with  = 20 to evaluate the models, while
for the classification ones we adopted a stratified -fold cross
validation with  = 20 for the majority of them. For the
hierarchical experiments, we used both  = 20 and  = 30, considering
the variability of the attributes and the data cardinality for each
classification level. Because of that, in the proposed solution,
analysed in Section 3.4, we used a stratified -fold with  = 20
for the first two levels, while for the last one we applied this
strategy using  = 30.</p>
    </sec>
    <sec id="sec-10">
      <title>4 PRELIMINARY EXPERIMENTAL</title>
    </sec>
    <sec id="sec-11">
      <title>VALIDATION</title>
      <p>Here we discuss the experimental results performed to address
two precise objectives:
1) Evaluating the performance of the diferent selected
algorithms for the implementation of the proposed solution
levels (see Section 4.1)
2) The experimental comparison of the proposed solution
with respect to the state-of-the-art techniques (see Section
4.2)</p>
    </sec>
    <sec id="sec-12">
      <title>4.1 Performance evaluation</title>
      <p>
        Here we discuss the performance evaluation of the proposed
methodology. The first prediction level with a 60-seconds
threshold has been defined as two classes, whose cardinalities are 17, 472
records (jobs) for the first one and the remaining 7, 967 for the
second one. From the evaluation of all the selected algorithms,
using a stratified 20-fold cross-validation [23], we obtained the
results reported in Table 1. Looking at these results, the most
accurate algorithms are the KNN (k-Nearest Neighbors) [
        <xref ref-type="bibr" rid="ref1">1</xref>
        ] and
the MLP. Considering the high initialization time for both
algorithms, the MLP allows a faster prediction in real-time, even for
very complex networks. For this reason, it was chosen for the
ifrst classification level.
      </p>
      <p>To train the second prediction level, we used only the records that
in the first level were correctly classified as belonging to class 1.
In this case, we used a binary classification with a threshold set to
3, 600 seconds. Re-evaluating the algorithms with a stratified
20fold cross-validation, the results, shown in Table 2, were obtained.
From these values, it is evident that the MLP is the algorithm
with the best performance values among all, the reason why it
was chosen as a classifier for the second level.</p>
      <p>
        Considering the results of the MLP, the algorithm that best fits
the situation, 4, 238 records have been used for the training of the
third level that are equivalent to those correctly predicted both
as class 1.0 and as 1.1, respectively 2, 101 for the first one (about
46.5% belonging to class 1.0.0 and the remaining 53.5% to class
1.0.1) and the remaining 2, 137 for the second one (about 20%
belonging to class 1.1.0, 15.5% to class 1.1.1 and the remaining
64.5% to class 1.1.2). For the third classification applied to class
1.0, it was decided to perform a binary classification using a
900-seconds threshold, thus creating the two final classes, 1.0.0
and 1.0.1. To evaluate the algorithms in this situation, we used a
stratified 30-fold cross-validation, obtaining the results reported
in the second and third columns of the Table 3. From these values,
it is possible to notice that all algorithms predict better just one
of the two classes, all except the Decision Tree that predicts both
classes well and better than all the other models. Finally, for the
third level classification applied to class 1.1, it was decided to
perform a 3-class classification using 7, 200- and 10, 800-seconds
thresholds, thus creating classes 1.1.0, 1.1.1, and 1.1.2. To evaluate
the algorithms’ performance in the prediction of these 3 classes,
a stratified 30-fold cross-validation was performed, obtaining the
results reported in the last four columns of Table 3. From these
data, we firstly discarded the SVM (Support Vector Machine)
[
        <xref ref-type="bibr" rid="ref5">5</xref>
        ] and KNN algorithms, due to the null results in class 1.1.1.
Between the other three models, to decide which one was the
best for this step, we decided to take into account the average
of the results of the three classes, since all three have the same
importance, resulting in that the Decision Tree was also in this
case, the one with better predictions’ performance.
      </p>
    </sec>
    <sec id="sec-13">
      <title>4.2 Comparative analysis with state-of-the-art approaches</title>
      <p>We compared the solution with some kind of state-of-the-art
techniques to prove the efectiveness of the results obtained:
• Case 1: regression techniques.
• Case 2: single level classification techniques with balanced
classes.</p>
      <sec id="sec-13-1">
        <title>Polynomial Regressor KNN Regressor Decision Tree (depth=3) Decision Tree (depth=5)</title>
        <p>MLP Regressor</p>
      </sec>
      <sec id="sec-13-2">
        <title>Polynomial Regressor KNN Regressor Decision Tree (depth=3) Decision Tree (depth=5)</title>
        <p>MLP Regressor
• Case 3: single level classification techniques where the
classes were manually defined.
• Case 4: single level binary classifications with manually
defined thresholds.
• Case 5: single level binary classifications with thresholds
defined by summing ranges from Case 2 and Case 3
experiments.
• Case 6: hierarchical classification experiments with two
classification levels.
• Case 7: hierarchical classification experiment with three
classification levels.</p>
        <p>About the Case 1, the proposed solution has been initially
compared with a reference baseline given by regression algorithms’
usage, considering that the target variable is a numeric real value.
In fact, we executed some k-fold cross-validation experiments,
using firstly  = 10 and then  = 20, and also a Holdout. From the
results of the cross-validation experiments, reported in Table 4a
and 4b, we can see that there is an improvement of the max
accuracy, meaning that some folders are better to predict than others,
while the mean accuracy decrease, meaning that there are more
other folders with no acceptable results. Same as for the holdout,
which results, reported in Table 4c, are too low to be considered.
Established that this kind of algorithm does not achieve good
performance, we moved on to classification experiments.
The classification experiments can be grouped into two main
types: single level (Case 2, 3, 4 and 5), meaning that it is used
only one algorithm, and multi-level (Case 6 and 7), i.e., using
a hierarchical structure. We started with a single level where
the classes were defined in such a way as to have classes of the
same frequency. Unlikely, for Case 2, noticeable from the results
reported in the Table 5, independently of the number of classes,
the accuracy increases too slowly (looking the results from Table
5a to Table 5d), reason why this type of experiments was deemed
unsuccessful.</p>
        <p>For this reason, we moved to Case 3 experiments, manually
defining the classes to be predicted, depending on the feedback we
would return and on the information obtained from the previous
tests. Anyway, also from these results, reported in Table 6, we
can highlight that the F-measure increase too slowly, looking at
the results of Table 6a, 6b and 6c, while, for the last experiments,
the results represented in Table 6d show a clean improvement.
For this reason, only the information of the last experiment was
used for the creation of the ranges for the binary experiment that
made up the first level of the solution proposed with a 60-seconds
threshold.</p>
        <p>Considering the non-relevant results with multi-class
experiments, we passed to Case 4 experiments and we started to study
algorithms’ behaviour with binary classifications using, firstly,
three user-defined thresholds: 900, 1, 800, and 3, 600 seconds.
From the values obtained, reported in Table 7, it is possible to
see that as the threshold increase, the results of class 1 tend to
decrease, related to a decrease of the number of records
associated with that class, while the results of class 0 do not change
significantly.</p>
        <p>For this reason, we defined new thresholds belonging to Case 5
experiments: 24, 30 and 582 seconds. These have been defined by
the aggregation of ranges of multi-class experiments previously
executed, considering their specific confusion matrices. In this
case, we can notice an increase in both classes results, reported in
Table 8, increasing the threshold used. The 60-seconds threshold
used inside the solution proposed as the first prediction level,
discussed in Section 3.4, also belongs to this type of experiments.
We discuss now the multi-level experiments, starting with two
hierarchical experiments, the first with four and the second with
ifve classes, both with two predictive levels ( Case 6 experiments).
The schemas of these two structures are represented in Figure
8a and 8b. The results obtained, reported in the table 9a and 9b,
anyway, highlight a worsening of the F-measure values globally.
In fact, if we consider the range up to 900 seconds, we can see that
the mean F-measure of the classes in this range, for both these
two levels of hierarchical structures, is worse compared with the
solution discussed in Section 3.4. The only positive thing that can
(a) Schema of the classification experiment with 2 levels and 4
ifnal classes
(b) Schema of the classification experiment with 2 levels and 5
ifnal classes
be highlighted in the system shown in Figure 8b is the slightly
better result regarding the 3-class classification compared to the
proposed solution, however at the cost of a great worsening of
the performance in the preceding ranges. For these reasons, both
the experiments have been discarded.
Finally, we made a comparison with a hierarchical architecture
with three levels and six classes (Case 7 experiment), whose
schema is reported in Figure 9, based on the two levels
hierarchical experiments discussed previously. In fact, we added a third
level to better predict the time range from 3, 600 seconds onward.
The obtained performance is reported in Table 10, and they are
not so good since even the results of the 3-class classification are
worse than the solution proposed in section 3.4.</p>
      </sec>
    </sec>
    <sec id="sec-14">
      <title>5 CONCLUSION AND FUTURE RESEARCH</title>
    </sec>
    <sec id="sec-15">
      <title>DIRECTION</title>
      <p>This paper proposed a data-driven solution to predict, with good
accuracy, the interval in which a submitted job’s real waiting time
belongs. We preferred to address the problem as a classification
task due to the bad results obtained through regression-based
strategies (see Table 4). As reported in Section 4, the solution,
compared with other experiments, shows promising results,
although some classes’ performance needs to be improved. The
rather poor results associated with these classes are related to
the unbalanced available dataset, considering that, as it can be
seen from the graph in Figure 4, there is an uneven
distribution between classes. In fact, the records used to predict the last
ifve classes are about a third compared to those used to predict
only the first one. As classification levels increase, the number
of analysed jobs decreases while the variability of the pending
time increase, therefore the available data is not suficient to
accurately model all classes. The decrease of available jobs for
the training process is afected also by the misclassifications in
the previous levels. Moreover, the variables used to model the
multiple classification tasks did not perfectly model the problem
under analysis; thus, the problem appears to be under-modeled.
This means that the variables used to predict the categorical
waiting-time for each job are not suficient to describe the
problem optimally (the high variability of diferent classes in the case
of an unbalanced dataset). There is a lack of essential information
for the considered algorithms to improve the system’s
classification performance. In this regard, it was noted that little data
could describe the complexity of the job.</p>
      <p>
        This work is a preliminary step towards implementing a
scheduling system based on machine learning techniques on what we
are currently working on. Based on the discussed experimental
results, there is room for improvements in the proposed
datadriven methodology. More specifically, we are currently working
with HPC experts to define an extended set of attributes to model
the problem addressed in this paper, understand how to get them
and where, or create a new feature engineering step similar to the
one proposed in [
        <xref ref-type="bibr" rid="ref2">2</xref>
        ] to improve the system’s overall performance.
Furthermore, we are working to extend the current methodology:
(1) to predict other types of information (e.g., the number of CPUs
necessary for a job, the termination status of the job execution)
to enhance the HPC cluster performance and (2) to estimate the
model degradation over time [
        <xref ref-type="bibr" rid="ref4">4</xref>
        ].
at. https://www.mordorintelligence.com/industry-reports/
high-performance-computing-market
[9] M. Jassas and Q. H. Mahmoud. 2018. Failure Analysis and Characterization
of Scheduling Jobs in Google Cluster Trace. In IECON 2018 - 44th Annual
Conference of the IEEE Industrial Electronics Society. 3102–3107. https://doi.
org/10.1109/IECON.2018.8592822
[10] 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
[11] Chunhong Liu, Liping Dai, Yi Lai, Guinbing Lai, and Wentao Mao. 2020.
      </p>
      <p>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
[12] 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
[13] Robert McGill, John W Tukey, and Wayne A Larsen. 1978. Variations of box
plots. The American Statistician 32, 1 (1978), 12–16.
[14] J. M. Navarro, G. H. A. Parada, and J. C. Dueñas. 2014. System Failure Prediction
through Rare-Events Elastic-Net Logistic Regression. In 2014 2nd International
Conference on Artificial Intelligence, Modelling and Simulation . 120–125. https:
//doi.org/10.1109/AIMS.2014.19
[15] D. Nurmi, A. Mandal, J. Brevik, C. Koelbel, R. Wolski, and K. Kennedy. 2006.</p>
      <p>Evaluation of a Workflow Scheduler Using Integrated Performance Modelling
and Batch Queue Wait Time Prediction. In SC ’06: Proceedings of the 2006
ACM/IEEE Conference on Supercomputing. 29–29. https://doi.org/10.1109/SC.
2006.29
[16] J. W. Park. 2019. Queue Waiting Time Prediction for Large-scale
Highperformance Computing System. In 2019 International Conference on High
Performance Computing Simulation (HPCS). 850–855. https://doi.org/10.1109/
HPCS48598.2019.9188119
[17] R. Polikar. 2006. Ensemble Based Systems in Decision Making. IEEE Circuits
and Systems Magazine 6, 3 (2006), 21–45.
[18] Sebastian Raschka and Vahid Mirajalili. 2019. Python machine learning.
Number 1. Packt Publishing,.
[19] 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
[20] S. S. SHAPIRO and M. B. WILK. 1965. An analysis of variance test for normality
(complete samples)†. Biometrika 52, 3-4 (12 1965), 591–611. https://doi.
org/10.1093/biomet/52.3-4.591
arXiv:https://academic.oup.com/biomet/articlepdf/52/3-4/591/962907/52-3-4-591.pdf
[21] Carlos N. Jr. Silla and Ale xA. Freitas. 2011. A survey of hierarchical
classiifcation across diferent application domains. Data Mining and Knowledge
Discovery 22, 1-2 (2011), 31–72. https://doi.org/10.1007/s10618-010-0175-9
[22] C. Spearman. 1904. The Proof and Measurement of Association between Two</p>
      <p>Things. The American Journal of Psychology 15, 1 (1904), 72–101.
[23] Pang-Ning Tan, Michael Steinbach, Anuj Karpatne, and Vipin Kumar. 2018.</p>
      <p>Introduction to Data Mining (2nd Edition) (2nd ed.). Pearson.
[24] Q. Zhang, M. F. Zhani, R. Boutaba, and J. L. Hellerstein. 2014. Dynamic
Heterogeneity-Aware Resource Provisioning in the Cloud. IEEE Transactions
on Cloud Computing 2, 1 (2014), 14–28. https://doi.org/10.1109/TCC.2014.
2306427</p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          [1]
          <string-name>
            <given-names>N. S.</given-names>
            <surname>Altman</surname>
          </string-name>
          .
          <year>1992</year>
          .
          <article-title>An introduction to kernel and nearest-neighbor nonparametric regression</article-title>
          .
          <source>American Statistician</source>
          <volume>46</volume>
          ,
          <issue>3</issue>
          (Aug.
          <year>1992</year>
          ),
          <fpage>175</fpage>
          -
          <lpage>185</lpage>
          . https://doi.org/10.1080/00031305.
          <year>1992</year>
          .10475879
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          [2]
          <string-name>
            <given-names>Daniele</given-names>
            <surname>Apiletti</surname>
          </string-name>
          , Claudia Barberis, Tania Cerquitelli, Alberto Macii, Enrico Macii, Massimo Poncino, and
          <string-name>
            <given-names>Francesco</given-names>
            <surname>Ventura</surname>
          </string-name>
          .
          <year>2018</year>
          .
          <article-title>iSTEP, an Integrated Self-Tuning Engine for Predictive Maintenance in Industry 4.0</article-title>
          . In IEEE International Conference on Parallel &amp;
          <article-title>Distributed Processing with Applications</article-title>
          ,
          <source>Ubiquitous Computing &amp; Communications, Big Data &amp; Cloud Computing, Social Computing &amp; Networking</source>
          ,
          <string-name>
            <given-names>Sustainable</given-names>
            <surname>Computing</surname>
          </string-name>
          &amp; Communications, ISPA/IUCC/BDCloud/SocialCom/SustainCom 2018, Melbourne, Australia,
          <source>December 11-13</source>
          ,
          <year>2018</year>
          . IEEE,
          <fpage>924</fpage>
          -
          <lpage>931</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          [3]
          <string-name>
            <given-names>Leo</given-names>
            <surname>Breiman</surname>
          </string-name>
          .
          <year>2017</year>
          .
          <article-title>Classification and regression trees</article-title>
          .
          <source>Routledge (Milton Park</source>
          , Abingdon, Oxfordshire).
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          [4]
          <string-name>
            <given-names>Tania</given-names>
            <surname>Cerquitelli</surname>
          </string-name>
          , Stefano Proto, Francesco Ventura, Daniele Apiletti, and
          <string-name>
            <given-names>Elena</given-names>
            <surname>Baralis</surname>
          </string-name>
          .
          <year>2019</year>
          .
          <article-title>Towards a real-time unsupervised estimation of predictive model degradation</article-title>
          .
          <source>In Proceedings of the International Workshop on Real-Time Business Intelligence and Analytics</source>
          ,
          <string-name>
            <surname>BIRTE</surname>
          </string-name>
          <year>2019</year>
          , Los Angeles, CA, USA,
          <year>August 26</year>
          ,
          <year>2019</year>
          . ACM,
          <volume>5</volume>
          :
          <fpage>1</fpage>
          -
          <issue>5</issue>
          :
          <fpage>6</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          [5]
          <string-name>
            <given-names>Corinna</given-names>
            <surname>Cortes</surname>
          </string-name>
          and
          <string-name>
            <given-names>Vladimir</given-names>
            <surname>Vapnik</surname>
          </string-name>
          .
          <year>1995</year>
          .
          <article-title>Support-Vector Networks</article-title>
          .
          <source>Mach. Learn</source>
          .
          <volume>20</volume>
          ,
          <issue>3</issue>
          (Sept.
          <year>1995</year>
          ),
          <fpage>273</fpage>
          -
          <lpage>297</lpage>
          . https://doi.org/10.1023/A:1022627411411
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          [6]
          <string-name>
            <given-names>S.</given-names>
            <surname>Ganguly</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Consul</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Khan</surname>
          </string-name>
          ,
          <string-name>
            <given-names>B.</given-names>
            <surname>Bussone</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Richards</surname>
          </string-name>
          ,
          <article-title>and</article-title>
          <string-name>
            <given-names>A.</given-names>
            <surname>Miguel</surname>
          </string-name>
          .
          <year>2016</year>
          .
          <article-title>A Practical Approach to Hard Disk Failure Prediction in Cloud Platforms: Big Data Model for Failure Management in Datacenters</article-title>
          .
          <source>In 2016 IEEE Second International Conference on Big Data Computing Service and Applications (BigDataService)</source>
          .
          <fpage>105</fpage>
          -
          <lpage>116</lpage>
          . https://doi.org/10.1109/BigDataService.
          <year>2016</year>
          .10
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          [7]
          <string-name>
            <given-names>Trevor</given-names>
            <surname>Hastie</surname>
          </string-name>
          , Robert Tibshirani, and
          <string-name>
            <given-names>Jerome</given-names>
            <surname>Friedman</surname>
          </string-name>
          .
          <year>2009</year>
          .
          <article-title>The elements of statistical learning: data mining, inference and prediction (2 ed</article-title>
          .). Springer. http://www-stat.stanford.edu/~tibs/ElemStatLearn/
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          [8]
          <string-name>
            <given-names>Mordor</given-names>
            <surname>Intelligence</surname>
          </string-name>
          .
          <year>2020</year>
          .
          <article-title>High Performance Computing (HPC) Market, growth</article-title>
          , trends,
          <source>forecasts (2020 - 2025). Report posted</source>
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>