Cloud workload prediction based on workflow execution time discrepancies

Before diving into the details, we provide a few important definitions: trace fragment—used to provide a particular background workload –, past error—determines the previously collected execution time error values regarding the completed jobs \(j_1, ...j_k\)—finally, future error—defines the previously collected execution error evaluations of the jobs \(j_{k+1},... j_N\) that have not yet run in the current workflow instance (i.e., what was the level of error in the “future” that after a particular past error value was observed).

A trace fragment is a list of activities characterised by such runtime properties (e.g., start time, duration, performance, etc.) that are usable in simulators, their collection is denoted as fragment database in Fig. 2. Each fragment represents realistic workloads i.e., real-world system behaviour. Fragments are expected to last for the duration of the complete simulation of the workflow with all its jobs. The fragment duration is independent from the actual real life situation modelled—which stems from the actual \([j_k,t]\) job which triggered the prediction. In a worst case, fragments should last for the completely serial execution of the workflow: \(\sum _{i=1\dots k}r_{ob}(j_i)+\sum _{i=k+1\dots N}r_{ex}(j_i)\). Thus fragment durations vary from workflow-to-workflow. Apart from their duration, fragments are also characterised and identified by their starting timestamp, i.e., the time instance their first activity was logged, denoted as \(t \in T\) (where \(T\subset {\mathcal{T}}\)); later we will refer to particular fragments by their identifying starting timestamp (despite these fragments often-times contain thousands of activities). As a result, when the algorithm receives an identifying timestamp, it queries the trace database for all the activities that follow the first activity for the whole duration of the fragment. Note, that our algorithm uses the relative position of these timestamps. Therefore, when storing historic traces as fragments, they are stored so that their timestamps are consistent and continuous, this requires some displacement of their starting positions. This guarantees that we can vary the fragment boundaries (according to the workflow level fragment duration requirements) at will.

Arbitrary selection of fragment boundaries would result in millions of trace fragments. If we would simulate with every possible fragment, the analysis of a single situation would take days. However, as with any prediction, the longer time it takes the less valuable its results become (as the predicted future could turn past by then). Predictions typically are only allowed to run for a few minutes as a maximum, thus the entire simulation phase must not hinder the real execution for more than \({\mathfrak{T}}\). In the following, we survey the steps that are necessary to meet this requirement i.e., reducing the analysis time from days to \({\mathfrak{T}}\). The fragment database needs to be pre-filtered so only a few fragments (\(T_{filt}\subset T\)) are used in the analysis later on.

Although this is out of scope of the current article, pre-filtering can use approaches like pattern matching, runtime behaviour distance minimisation (e.g., by storing past workflow behaviour—for particular fragments—and by comparing to the current run to find a likely start timestamp), or even random selection. Filtering must take limited and almost negligible time. In our experiments, we assumed it below \({\mathfrak{T}}/1000\) (allowing most of the time to be dedicated to the simulation based analysis of the situation). As a result of filtering, the filtered fragment count must be reduced so that the time needed for subsequent simulations does not exceed the maximum time for predictions: \(|T_{filt}|<{\mathfrak{T}}/{\mathfrak{t_{sim}}}(W)\), where \({\mathfrak{t_{sim}}}\) is the mean execution time of W in the simulated cloud. Our only expectation that the pre-filtering happens only in memory and thus the fragment database is left intact. As a result, when we run the algorithm, it only sees a portion of the fragment database. On the other hand, future runs of the algorithm might get a different portion from the database depending on the future runtime situation.

Finally, we dive into the error definitions. Alongside fragments, several error values are stored in the fragment database, but unlike fragments, which are independent from workflows, these error values are stored in relation to a particular workflow and its past instances. Later, just like projected execution times, these stored error values are also used to steer the algorithm. First, in terms of past errors, we store the values from our previous partial execution time error functions, Eqs. 1–3. Past errors are stored for every possible k value for the particular workflow instance. We calculate future errors similarly to past errors. Our calculation uses the part of the workflow containing the jobs after \(j_k\): \(W^F(W,k):=\{\forall j_i\in W:i>k\wedge i\le N\}\), where \(W^F\in {\mathcal{W}}\). Thus, the future error function determines how a particular, previously executed workflow instance continued after a specific past error value:This function allows the evaluation and storage of the final workflow execution time error for those parts of the past workflow instances, which have not been executed in the current workflow execution.

Algorithm 1 (also depicted functionally in Fig. 3 and structurally as phases II–III in Fig. 2) aims at finding a timestamp so that the future estimated error is minimal, while past error prediction for this timestamp is the closest to the actual past error (i.e., the estimated and actual “past errors are aligned”). The algorithm is based on the assumption that if past workloads are similar (similarity measured by their error functions) then future workloads would be similar, too.

In detail, line 1 picks randomly one of the fragments identified by the timestamp in the filtered set \(T_{filt}\) and stores in \(t_{init}\). This will be the assumed initial location of the fragment that best approximates the background load. Later, in line 17, this \(t_{init}\) will be kept updated so it gives a fragment that better approximates the background load. The primary search window—\({\mathfrak{R}}\) of line 5 also shown between the dashed lines of the lower chart in Fig. 3 represents a set of timestamps within a S / 2 radius from the assumed start of the fragment specified by \(t_{init}\). The algorithm uses set \(T_{list}\) to store timestamps for the approximate trace fragments as well as to count the iterations (used after line 15).

A simulator is used to calculate observed execution times \(r_{ob}'\) for the jobs in the simulated infrastructure (see line 9). This is expressed with \(sim(W,R_{ex},i,t)\) thus, each simulation receives the workflow to be simulated, the set of execution time expectations (\(R_{ex}\)) that specify the original enactment plan, the identifier of the job (\(1 \le i \le N\)) we are interested in and the timestamp of the trace fragment (\(t\in T\)) to be used in the simulation as background load to the workflow, respectively. With these parameters the simulator is expected to run all the activities in the trace fragment identified by t in parallel to a simulated workflow instance. Note: the simulation is done only once for the complete workflow for a given infrastructure and a given fragment, later this function simply looks up the past simulated \(r_{ob}'\) values.

Next, we use one of the error functions of the workflow execution time as defined in Eqs. 1–3. As we have simulated results, we substitute the observed/expected execution time values in the calculation with their simulated counterparts. In the simulation, the expected execution times \(r_{ex}'\) are set as the real observed execution times \(r_{ob}\) (see line 8). To denote this change in the inputs to the error function, we use the notation of \(E'(W,t,k)\)—error of simulated execution time. This function shows how the simulated workload differs from the observed one. The evaluation of the \(E'\) function is depicted with \(\times\) marks at the bottom chart of Fig. 3.

Afterwards, lines 12–14 search through the past error values for each timestamp (using the same error function as we used for the evaluation of \(E'\)). With the help of function \(\phi : {\mathcal{T}} \rightarrow {\mathbb{R}}\):This function offers the difference between the simulated and real past error functions (Fig. 3 represents this with red projection lines between the chart of E and the \(\times\) marks of \(E'\)). The algorithm uses the \(\phi (x)\) function to find the best alignment between the simulated and real past error functions: we set \(t_{min}\) as the time instance in \({\mathfrak{R}}\) with the smallest difference between the two error functions. The alignment is searched over an arbitrary subset of the timestamps: \(T_{red}\)—the secondary search window. The algorithm selects a \(T_{red}\) with a cardinality of P in order to limit the time to search for \(t_{min}\). The arbitrary selection of \(T_{red}\) is used to properly represent the complete timestamp set of T.

After finding \(t_{min}\), we have a timestamp from the fragment database, for which the behaviour of the future error function is in question, this corresponds to the fragment selection in Fig. 2. Line 16 finds the timestamp that has the closest past and future error values in the range around \(t_{min}\) within radius S / 2—see also in the top right chart of Fig. 3. Note, this operation utilises our assumption that past and future errors are aligned (i.e., a trace fragment with small past error value is more likely to result in similarly small future error value). The timestamp with the future error value closest to the past error is used as \(t_{target}\) for the current iteration (i.e., our current estimate for the start timestamp of the approximate background load).

Finally, the iteration is repeated until the successive change in \(t_{target}\) is smaller than the precision \(\Pi\) or the iteration count reaches its maximum—I, represented as phase III in Fig. 2. Note, I is set so the maximum time spent on workload prediction (\({\mathfrak{T}}\)) is not violated. The algorithm then returns with the last iteration’s \(t_{target}\) value to represent the starting timestamp of the predicted trace fragment that most resembles the background load currently experienced on the cloud behind the workflow. This returned value (and the rest of the trace fragment following \(t_{target}\)) then could be reused by when utilizing the real life version of the simulated cloud. For example, the workflow enactor could use the knowledge of the future expected workload for the planning and execution phases of its autonomous control loop (phase IV in Fig. 2). Note, the precise details on the use of the predicted workload is out of the scope of this article.

The execution of the TCG workflow was simulated according to the description presented in Fig. 5. The description is split into three main sections, each starting with a PSSTART tag (see lines 1, 6 and 20, which correspond to the three main sections G–[T1/T2/T3–TC]–C of the TCG workflow shown in the top left corner of Fig. 4). This tag is used as a delimiter of parallel sections of the workflow, thus everything that reside in between two PSSTART lines should be simulated as if they were executed in parallel. Before the actual execution though, every PSSTART delimited section contains the definition of the kind of VM that should be utilized during the entire parallel section. The properties of these VMs are defined by the VMDEF entry (e.g., see lines 2 or 8) following PSSTART lines. Note, the definition of a VM is dependent on the simulator used, so below we list the defining details specific to DISSECT-CF:The real-life workflow was executed in the LPDS cloud (see the leftmost section of Fig. 4). Thus, we needed to model this cloud to match the simulated behaviour of the workflow to its real life counterpart ran in phase one. Therefore, the storage name \(iscsi-izabel\) in the workflow description (e.g., in line 2 of Fig. 5) refers to the particular storage used on LPDS cloud, just like the VMI image name tinker does.

Now, we are ready to describe the runtime behaviour of the workflow observed in phase one in a format easier to process by the simulation. This behaviour is denoted with the VMSEQ entries (e.g., see lines 4 or 10) that reside in each PSSTART delimited parallel section. VMSEQ entries are used to tell the simulator a new VM needs to be instantiated in the parallel section. Each VM requested by the VMSEQ entries will use the definition provided in the beginning of the parallel section. All VMs listed in the section are requested from the simulated LPDS cloud right before the workflow’s processing reaches the next PSSTART entry in the description. This guarantees they are requested and executed in parallel (note, despite requesting the VMs simultaneously from the cloud, their level of concurrency observed during the parallel section will depend on the actual load of the simulated LPDS cloud). The processing of the next parallel section, only starts after the termination of all previously created VMs.

In the VMSEQ entries, a VM’s activities before termination. There are two kinds of activities listed: network and compute. Network activities start with N and then followed by the number of bytes to be transferred between the DATA store and the VM (this is the store defined by the VMDEF entry at the beginning of the parallel section). Compute activities, on the other hand, start with the letter C and then they list the number of seconds till the CPUs of the VM are expected to be fully utilised by the activity. VM level activities are executed in the simulated VM in a sequence (i.e., one must complete before the next could start).

For example, line 12 of Fig. 5 defines how job executions are performed in a VM. First, we prepare the VM to run the tinker binaries by installing three software packages. This results in three transfers (49 KB, 186 KB and 326 KB files) and a task execution for 22 seconds. Next, we fetch the tinker package (4.4 MBs) and decompress it (in a half a second compute task). Then, we transfer the input files with the 2500 conformers and the required runtime parameters to use them (5.9 MBs and 1.5 KBs). Afterwards, we execute the T1, T2, T3 and TC jobs sequentially taking 35, 60, 32 minutes and 2 seconds, respectively. These values were gathered as the average execution times for the jobs while the real life workflows were running in the LPDS cloud. Finally, this 2 second activity concludes the VMs operations, therefore it is terminated.

The PSSTART entry in line 6 and the virtual machine executions, defined until line 16, represent a single execution of the parallel section of the TCG workflow. Because of repetitions, we have omitted the several VMSEQ entries from the parallel section, as well as several PSSTART entries representing further parallel sections of conformer analysis. On the other hand, the description offered for the simulator did contain all the 14 additional PSSTART entries which were omitted here for readability purposes.

To conclude, the description in Fig. 5 provides details for over 1800 network and computing activities to be done for a single execution of the TCG workflow. If we consider only those activities that are shown in the TCG workflow, we still have over 1200 computing activities remaining. These activities result in the creation and then destruction of 302 virtual machines in the simulated cloud. When calculating the error functions, we would need expected execution details for all these activities or VMs. The rest of the article will assume that the workflow enactor provides details about the computing activities directly relevant for the TCG workflow only (i.e., the jobs of G/Tx/C). Thus our N value was 1202. The partial workflow execution error functions could be evaluated for every job done in the simulated TCG. This, however, is barely offering any more insight than having an error evaluation at the end of each parallel section (i.e., when all VMs in the particular parallel section are complete). As a result, in the rest of the article, when we report k values, they are going to represent the amount of parallel sections complete and not how many actual activities were done so far. To transform between activity count and the reported k values one can apply the following formula:where 15 is the number of parallel sections, and 80 is the number of TCG activities per parallel section. Finally, the \(k_{real}\) is the value used in the actual execution time error formulas from Eqs. 1–3.

Although, the above description was presented with our TCG workflow, the tags and their attributes of the description were defined with more generic situations in mind. In general, our description could be applied to workflows and applications that have synchronisation barriers at the end of their parallel sections.

In order to simulate how the workflow instances of TCG would behave under various workload conditions, we needed a comprehensive workload database. We have evaluated previously published datasets: we looked for workload traces that were collected from scientific computing environments (as that is more likely to resemble the workloads behind TCG). We only considered those traces that have been collected over the timespan of more than 6 months (i.e., the length of our experiment with TCG on the LPDS cloud—as detailed in Sect. 5.1). We further filtered the candidate traces to only contain those which would not cause significant (i.e., months) overload or idle periods in the simulated LPDS cloud. This essentially left 4 traces (SharcNet, Grid5000, NorduGrid and AuverGrid) from the Grid Workloads Archive (GWA [9]), we will refer to the summary of these traces as \(T^{GWA}\subseteq T\). Note, it is irrelevant that the traces were recorded on grids—for our purposes the user behaviour, i.e., the variety of tasks, their arrival rate and duration are important. Fortunately, these characteristics are all independent from the actual type of infrastructure.

Trace fragments were created using GWA as follows: we started a fragment from every job entry in the trace. Then we identified the end of the fragment as follows. Each fragment was expected to last at least for the duration of the actual workflow instance. Unfortunately, the simulated LPDS cloud could cause distortions to the job execution durations (e.g., because of the different computing nodes or because of the temporary under/over-provisioning situations compared to the trace’s original collection infrastructure), making it hard to determine the exact length of a fragment without simulation. Thus, we have created fragments that included all jobs within 3 times the expected runtime of the workflow. As a result each of our fragments was within the following time range: \([t,t+3\sum _{0<i<N}r_{ex}(j_i)]\). All these fragments were loaded in the trace archive of Fig. 4 (see its middle section titled “simulated data generation”). All together, our database have contained more than 2 million trace fragments.

With the trace fragments in place, we had every input data ready to evaluate the \(r'_{ob}\) values under various workload situations (i.e., represented by the fragments). Thus, we have set out to create a large scale parametric study. For this study, we have accumulated as many virtual machines from various cloud infrastructures as many we could afford. In total, we have had 3 cloud infrastructures (SZTAKI cloud,² LPDS cloud, Amazon EC2³) involved which hosted 192 single core virtual machines with 4 GBs of memory and 5 GBs of hard disk storage (and the closest equivalent on EC2). We offered the trace archive to all of them as a network share. Each VM hosted DISSECT-CF v0.9.6 and was acting as a slave node for our parametric study. The master node (not shown in the figure), then instructed the slaves to process one trace at a time as follows⁴:The simulation of all trace fragments took less than 2 days. The mean simulation execution time for a fragment running on our cloud’s model is \({\mathfrak{t_{sim}}}(TCG)=756\,{\mathrm{ms}}\). We have stored the details about each simulation in relation to the particular trace fragment in our simulated job execution log database (see Fig. 4).

To conclude our simulated data generation phase, we populated our past and future error cache of Fig. 4. Later our algorithm used this to represent past workflow behaviour. We calculated the past and future error values with the help of all \(r'_{ob}\) we collected during the simulation phase. The error values were cached from all 3 error functions we defined in Eqs. 1–3 as well as from their future error counterparts from Eq. 4. This cached database allowed us to evaluate the algorithm’s assumptions and behaviour in the simulated environment as we discuss it in the next section.

To investigate our assumption on the relation of past and future error values, we have analysed the collected values in the error cache. In Fig. 6, we exemplify how the simulated past and future error values (using the \(E_{SQD}\) function) vary within a subset of the past/future error cache (which we collected in the previous phase of our evaluation). Here, each dot represents a single simulation run, while the error values were calculated after the twelfth parallel section—\(k=12\), see Fig. 5. To reduce the clutter in the figure, we present the simulation results using only a subset of the trace fragments that we have identified in the Nordugrid GWA trace (\(T^{GWA}_{nordu}\subset T\)). The items in the subset were selected so every 50\(^{th}\) Nordugrid related trace fragment is shown in the chart: \(\{t_i, t_{i+1}\}\in T^{GWA}_{nordu}\rightarrow \{t_j,t_{j+50}\}\in T\). Out of the selected fragments, only those are shown in the figure which resulted in relatively low error values. This allows us to better observe the relationship between past and future errors when both error values are low. For example, in case of Fig. 6, we have used the low error value limit of \(10^7\). Note, the range of this error function for all the simulated trace fragments was: \(\forall t \in T:1.5\times 10^6< E_{SQD}(W,12,t)< 4 \times 10^7\).

Based on the error cache, in this section, we investigated two assumptions that are both important for the algorithm’s success: (i) low past error values likely pair up with low future error values; and (ii) show that as we approach the end of the workflow, decreasing past error values would more likely pair up with decreasing future error values (i.e., as past error values converge towards the final worklfow execution error, future error values also approach a stable hypothetical final value). As a first step, we limited our analysis to fragments with past/future error values below a chosen low error value—\(\tau\)—threshold:The choice for \(\tau\) could ensure that this filtered set contains the trace fragments most likely to be found by Algorithm 1 lines 1–14. For the error function \(E_{SQD}\), we have identified the low error value limit as: \(\tau :=2\times 10^6\).

For our first assumption, we evaluated the likelihood that consecutive fragments with small past error values E(W, t, k) lead to small F(W, t, k) values. We consider two trace fragments (\(t_a, t_b\in T: (t_a<t_b)\)) consecutive when there are no other trace fragments with starting timestamps in between the starting timestamps of the consecutive ones: \(\not \exists t_c\in T:(t_c>t_a\wedge t_c<t_b)\). First, we prepared the subsets of \(T_{filt}^{exp}\), that hold more than 80 consecutive timestamps of the trace. The number of consecutive timestamps is calculated as \({\mathfrak{T}}/{\mathfrak{t_{sim}}}\) while assuming \({\mathfrak{T}}\) to be a minute to minimise the impact of the simulation on the complete prediction operation and its users (eg., a workflow enactor) from the autonomous control loop. Next, we observed that in these subsets the likelihood of having both minimal future and past error values was 65–86%. Finally, we also observed that the selection of a lower \(\tau\) value could notably decrease the simultaneous presence of below-threshold error values (suggesting that a too precise match for the past/future error leads to over fitting).

For our second assumption, we evaluated the error cache and we observed that the higher k is the more potential the prediction has. I.e., with increasing k the error values tend towards the low error values, while simultaneously their deviation also decrease. Videos of this behaviour can be seen in footnotes for the Sharcnet⁶ and AuverGrid⁷ traces. The recordings show how the past and future error functions of \(E_{SQD}\) converge towards the optimal values as a result of the increasing number of completed parallel sections of TCG—k.

To conclude, we have shown that our assumption on using past error values to indicate the tendency of future ones is well supported by our simulated error cache. In other words, if a trace shows similarity (in terms of an error function) to past workloads then the same trace can be used to estimate future workloads.

In the final phases of our evaluation, we first executed an extensive parametric study on the most important inputs of the algorithm. Table 1 shows all the parameters evaluated. In our parametric study, we have ran all input parameter combinations on resources utilizing the private OpenStack cloud of Liverpool John Moores University. We have used 5 VM instances with equivalent configurations as follows: (i) 20 GB disks, containing the execution logs and the error cache, (ii) 16 GB of memory to allow efficient handling of the cache, and (iii) an Intel Core i7 4790 processor. For each parameter combination, these VMs ran 500 approximations using our previously collected simulated job execution log database (this is depicted in Fig. 4 as the “Algorithm behaviour data collection” phase).

For each approximation run, we have randomly selected an approximation target: a golden fragment, which we denote as \(t_g\in T_G\), where \(T_G\subset T^{GWA}\) denotes the set of all randomly chosen golden fragments. We have retrieved the execution logs related to the golden fragment (i.e., the \(r_{ob}(j,t_g)\)). Then, we applied our algorithm to identify an approximate GWA trace fragment for this particular (golden) TCG workflow instance, given that the instance has progressed to job \(j_k\) (i.e., the algorithm did not receive the complete execution log, just the observed execution time values that occurred before job \(j_k\): \(r_{ob}(j_i,t_g):1\le i<k\)). The approximation resulted in a \(t_{target}\in T^{GWA}\) trace fragment start time from one of the GWA traces. Finally, we have analysed the relation of \(t_{target}\) and \(t_g\), as well as the execution time—d—of the approximation algorithm under the particular input parameter conditions.

To analyse the capabilities of the algorithm in terms of workload approximation, we first defined the metrics to quantify the accuracy. An ideal solution would be finding exactly the golden fragment however, this is neither feasible nor necessary (as real life traces for the background workload would not be comparable). The aim is to see the degree of similarity between the golden fragment and its approximation (identified by \(t_{target}\)). We have defined two fundamental metrics for the evaluation of our algorithm:Thus our second, error level, metrics are defined as:for past errors, andfor future errors. Note: when evaluating our above metrics, we used the same error function as the algorithm—e.g., \(E(W,t_g,i)\) could be in both cases \(E_{SQD}(W,t_g,i)\).

As we have done 500 approximations for each input parameter combination, we have calculated their overall average and median values (for the following metrics: \(E^*_{MAPE}, F^*_{MAPE}, MAPE_E, MAPE_F, d\)) to represent the accuracy and performance of the approximation with a particular input set. To put these aggregated values into context, we have evaluated them for a random trace selection approach as well (this served as a baseline for comparing the effectiveness of our technique). Here, for each member of the golden set (\(T_G\)), an arbitrary trace fragment from the whole trace database was selected as the member’s approximation: \(t_{target}^{RANDOM}\in T^{GWA}\). The calculated accuracy metrics of this approximation approach are shown in Table 2.

Figures 7 and 8 show the behaviour induced by the changes in the two most impacting parameters of the algorithm. In total, each figure represents results of over 500 thousand approximations. A plotted point averages the outcomes of all possible parameter configurations except the one that is fixed for the plot. Note, the apparent impact of a parameter is often reduced by averaging (e.g., the best parameter configurations for \(S=1000\) lead to \(E^*_{MAPE}\) values in the range of 28%, while the average shown in the figure is over 34%). Nevertheless, the major trends are still visible. Also, in all cases the approximations of our algorithm yield significantly better results than random selection. Not surprisingly, using the \(E^*_{MAPE}\) metric, we have the best results when the algorithm also uses our MAPE based workflow execution time error function (\(E_{MAPE}\)), while the time adjusted function (\(E_{TAlt-SQD}\)) performs poorly. The improvements over random selection range between 10 and 20% for the median of our execution time level metric. Based on the results, one can also conclude that the secondary search window size (shown in Fig. 8) is a more important factor (albeit not directly configurable from the algorithm’s inputs). Thus, this must be an exposed user configurable parameter in the future.

In general, the d duration of the approximation is negligible (in the range of 31–2114 ms, with a median of less than 200 ms) compared to our assumed 1 minute maximum time for prediction. This leaves enough time for the simulation needs of the algorithm and therefore ensures timely predictions. We have also observed that increasing any of the parameters obviously introduces more calculations, however they do not increase the accuracy in a uniform way. Increasing parameter I, the number of iterations increases accuracy in a minimal way. After investigation, we have concluded that the algorithm’s exit condition (see line 18 of Algorithm 1) is often fulfilled by its sub-condition on \(\Pi\)—which was a set constant in all algorithm executions. Increasing the number (P) of evaluations for \(\phi (x)\) often leads to slightly decreasing accuracy because a higher number of evaluations lead to local minimums.

The effects on accuracy are not conclusive, because the nature of cross-parameter averages shown in Figs. 7 and 8. To better understand the effects of particular parameters, we have filtered the top 5% most accurate parameter configurations. Figures 9, 10, 11 and 12 show the likelihood for a particular parameter value to be represented in the filtered list. The figures also analyse how the particular error functions benefit from the other input parameters of the algorithm. Note, the average d duration of the algorithm’s evaluation with the parameter combinations from the top 5% was 2333 ms.

These figures suggest, that selecting an I value between 8 and 32 could bring slight benefits in accuracy. With regards to S, we have seen that values over 500 are beneficial. Our parametric study evaluated for \(S=2000\) as well, but this increased S value did not bring significant enough improvements to compensate for the additional time spent on evaluating the algorithm (i.e., the d increased threefold for an average accuracy increase of less than 1%). Next, we have analysed the effect of the number of \(\phi (x)\) evaluations (P). As with our previous experiments, P have had an inconclusive effect on accuracy (which highlights that the algorithm would greatly benefit from techniques that avoid the traps of local minimums). In general, lower \(P<500\) values proved more accurate, especially values of 20–50 were strongly represented in the top 5%. Finally, we have concluded that the secondary search window size has the biggest impact on accuracy, which is to be set between 50 and 100 times the size of the primary search window S. We recommend the following values:

Based on the recommended input values, we have analysed how the past and future errors for each 500 \(t_g\in T_G\) correlated with the error values acquired for the corresponding \(t_{target}\) predicted fragments. To evaluate the level of correlation, we used the statistical indicator called coefficient of determination: \(R^2\). The results are shown in Table 3. The algorithm finds strongly correlating approximations for past errors, while future errors show weaker correlation patterns. The weakest correlation was observed for the \(E_{MAPE}\) error function, which shows that the function is too focused on the particular \(r_{ob}\) values. On the other hand, the error function of \(E_{TAlt-SQD}\) leads to the best future error predictions, we assume this performance is likely caused by the function’s stronger reliance on job order (and indirectly time). The best \(R^2\) results we have obtained are presented in Fig. 13. These were using slightly different input parameter values (namely \(S=500, P=50\)) than we recommended based on our statistical evaluation. Amongst our future work, we plan to investigate techniques that would allow the algorithm to auto tune its parameters to get better correlating past and future error predictions for particular workflows.