The paper addresses a relevant problem of predicting the runtime of jobs for executing problem-solving schemes of large-scale applications in a heterogeneous distributed computing environment. Such an environment includes nodes that have various hardware architectures, different system software, and diverse computational possibilities. We believe that increasing the accuracy in predicting the runtime of jobs can significantly improve the efficiency of problem-solving and rational use of resources in the heterogeneous environment. To this end, we propose new models that make it possible to take into account various estimations of the module runtime for all modules included in the problem-solving scheme. These models were developed using the special computational model of distributed applied software packages (large-scale scientific applications). In addition, we compare the prediction results (jobs runtime and their errors) using different estimations. Among them are the estimations obtained through the modules testing, user's estimations, and estimations based on computational history. These results were obtained in continuous integration, delivery, and deployment of applied and system software of a package for solving warehouse logistics problems. They show that the largest accuracy is achieved by the modules testing.
Todays, scientific applications focus on carrying out large-scale scientific experiments in a
heterogeneous distributed computing environment. They play a significant role in the process of
solving important practical problems based on mathematical modeling of complex systems under
study [
In distributed applied software packages, problem-solving is described by schemes that specify the
computing process in terms of the subject domain. We apply methods of the computation and
information planning in constructing such problem-solving schemes on the special computational
model [
To execute a problem-solving scheme in the heterogeneous distributed computing environment, a
computational job is generated. A job enters into the environment. The meta-scheduler selects an
proposed by the authors.
integration of applied software [
An improvement in the efficiency of problem-solving and rational use of resources depends a lot
on the ability to estimate jobs runtime. In this regard, we propose new models for predicting jobs
runtime in the environment. Unlike well-known similar models [
following two problems: When starting jobs in a heterogeneous distributed computing environment, it is necessary to solve the
Forming a rational configuration of heterogeneous resources of the environment,
Planning a suboptimal schedule of the job execution on the formed configuration of resources.
It's obvious that a qualitative solution to these problems for a large spectrum of practical scientific applications requires an estimation of the execution time of applied programs [7]. For example, such an estimation is used to cluster jobs in the allocation of resources to them [8]. Generally, job runtime estimates are implemented by the user or some runtime prediction procedure [9].
Most of traditional job management systems and many workflow management systems are based on the use of estimates for program execution time that are specified by the user. This is a simple and very flexible approach. However, the errors of such estimates are usually highly large in practice.
There are various methods for predicting program execution time [10]. Among them are static and dynamic methods of program analysis.
The use of methods and tools of static analysis of program code without real program execution in heterogeneous environments is characterized by high overheads to additional programming. Such overheads are owing to the need to simulate operating the processor of the target computing node for executing a large spectrum of programs written in various programming languages.
In practice, the method of frequency characteristics has proven itself well [11]. It is based on the use of special tools for dynamic analysis of programs [12, 13]. Algorithms based on the use of such analysis differ in the sets of studied software and hardware characteristics [14]. Each algorithm determines specific relations between these characteristics. In this regard, the method of profiling the program on some reference node is most applicable in practice [15]. Its results are then extrapolated relative to the characteristics of the target node. Within this method, the accuracy of estimating the program execution time largely depends on the selection of scaling coefficients for computation speedup. These coefficients are determined by the ratios of characteristics for the reference and target nodes. dynamic analysis.
However, our practical experience in applying continuous integration of applied software
represented in [
The computational model of the environment is determined by the structure
=< , , , , , , , , , >, where , , , , , , , and are, respectively, the sets of applied software packages, parameters, operations, program modules, problem-solving schemes, jobs, resources, and constraints to the job execution and resources use.
is the set of relations between the above-listed objects. The data structure
represents the computational history that reflects the functioning of modules from . If
necessary, a description of components of the model
can be found in details in [
Each operation ∈ is implemented by the module ∈ , where ∈ ̅1̅,̅̅̅̅, ∈ 1̅̅,̅̅̅̅̅, is the number of operations, and
is the number of modules. One module can implement several operations. Each operation has two subsets , ⊂ of parameters. The subset input parameters. Their values must be known in order to calculate values of parameters from
and
reflect the purpose and semantics of formal parameters of the module that implements the operation . Parameters are transferred between modules in the form of data files.
Schemes from represent problems-solving processes in packages. The scheme ∈ that performs operations from is an analogue of the tiered-parallel form of the algorithm graph. Within the computational model under consideration, a scheme is a connected subgraph of an oriented acyclic bipartite graph. Such a graph represents schematic knowledge about algorithms for studying a subject domain. The example of such a graph is represented in Figure 1. Operations and parameters are depicted on it by filled and unfilled circles. The problem-solving scheme represented by the graph includes 3 tiers. Tier 1 contains the operation 3. The second consists of the operations 4, 5, and 6. Finally, two operations 7 and 8 are placed on tier 3.
= { 1} (Figure 2). At the same time, 2 = { 7, 8, 9} and 2 = ∅.
Two special operations 1 and 2 are emphasized in the computational model. This allows us to maintain a commonality for computations planning when constructing problem-solving schemes using their formulations [16]. The operations 1 and 2 model the conditions of the problem. They respectively define a subset of parameters whose values are known, and a subset of the parameters whose values need to be calculated. Thus, the operation 1 defines the subsets 1 = ∅ and 1 The operation 2 determines the subsets 2 ≠ ∅ and 1 = ∅. In the above example, 1
≠ ∅. = ∅ and
The execution of a problem-solving scheme in the environment is specified by a computational job. A job includes a list of modules of a problem-solving scheme. In addition, it contains requirements to the environment that determine the computing resources needed to execute the listed modules. These requirements include the number of processors or cores, sizes of RAM and disk memory, execution time, etc.
z 1 f 3 z
2 z
3 z 4 f 4 f 5 f 6 z
5 z 6 z 9
Tier 3 f 7 f 8 z
7 z
8 f 1 z 1 ...
f 2 the problem-solving scheme precedes (does not precede) the operation and ∩ ≠ ∅ ( ∩ = ∅). The matrix
of dimension × reflects estimates of the data volumes transmitted between operations. The matrix element operation to the operation . The matrix ≥ 0 shows the amount of data transmitted by the
of dimension × provides information about the interconnect bandwidth between nodes where modules that implement scheme operations are launched. The matrix element
≥ 0 demonstrates the interconnect bandwidth between nodes, in which the modules implementing the operations and operate.
The estimate of the job runtime in the asynchronous mode based on data availability is defined (at a time when all the necessary data is ready to execute it), is the predictive estimate of the module runtime, is the number of scheme operations, The variables in the formulas (1) are interpreted as follows:
( ) is the estimate of the period elapsed from the beginning of the job execution to the completion of the operation ( ),
is the estimate of the wait time in a queue for the module that implements the operation mode is defined as follows: 0 < ( ) ≤ 1 is the coefficient of decrease in interconnect bandwidth between nodes, in which the modules implementing the operations and operate, at the time .
Let the matrix of dimension
× be a tiered-parallel form describing the scheme execution in the fork/join mode, and is the number of scheme tiers. The element = 1 means that the operation must be performed on the lth tier. The transition to operations of the (l+1)th tier is possible provided that all operations on the lth tier are completed. The estimate ′ of the job runtime in the fork/join ′ = ∑ =1 , = estimates adjusted based on the computational history. (1) (2) follows: defined as follows:
In the environment with virtualized resources, the estimate asynchronous mode is defined as follows:
are, respectively, estimates of the time it takes to launch and remove determined experimentally for virtual machines of various configurations. virtual machine with a module that implements the operation . The estimates and are For the same environment, the estimate ′ of the job runtime in the fork/join mode is defined as is the module runtime to failure.
′ = ∑ =1 , = ∀ ∈1̅̅,̅̅: =1( max
In the asynchronous mode with restarting modules, the estimate of the job runtime is defined as
The variables in the formula above are interpreted as follows: is the estimate of the time it takes for the detection and identification of a failure, is the estimate of the time it takes for the restart of a module that implements operation These variables are required in the case of a hardware-software failure. The estimates and are determined by the average execution time of such processes by a meta-monitoring system for different types of software and hardware failures.
At the same time, in the fork/join mode with restarting modules, the estimate ′ of the job runtime is defined as follows: ′ = ∑ =1 , = ∀ ∈̅1̅,̅̅: =1( max + + +
max where ′ is the user’s estimate of the module runtime.
The estimate ′ of the job runtime in the fork/join mode is defined as follows: ′ = ∑ =1 , = ∀ ∈̅1̅,̅̅: =1( max + ′ + ). asynchronous mode is defined as follows:
In the environment with virtualized resources, the estimate of the job runtime in the
In the asynchronous mode with restarting the modules, the estimate of the job runtime is
max ∀ ∈̅1̅,̅̅:
Meanwhile, the estimate ′
of the job runtime in the fork/join mode is defined as follows:
max
, ℎ) > 0 is calculated on the basis of the computational history. The function ℎ( , , ℎ
) calculates using the average or median values from the sample time of the execution of the module that implements the operation for the period ℎ.
of the job runtime in the fork/join mode is defined as follows: ′ = ∑ =1 , =
In the environment with virtualized resources, the estimate
of the job runtime in the fork/join mode is defined as
Finally, let us consider the use of estimates based on computational history. In the asynchronous mode, the estimate + ′′ + In the asynchronous mode with restarting modules, the estimate of the job runtime is defined
of the job runtime in the fork/join mode is defined as follows: ′
As an example, we consider the problem of improving the processes of loading and unloading of goods in a warehouse through their simulation. To solve this problem, a distributed applied software package has been developed using the Orlando Tools framework [17]. This package is a parameter sweep application [18]. Simulations models (modules) are created using a special toolkit [19].
The heterogeneous distributed computing environment, in which this package is applied, was created on the basis of the resources of the public access Irkutsk Supercomputer Center SB RAS [20]. We compare the prediction results (jobs runtime and their errors) using different estimations.
The experiments were carried out in the continuous integration process of package modules. Such integration includes the modification, version control, build, testing, delivery, and deployment of applied and system software on different nodes of the heterogeneous environment. The experiments 350000 280000 s , em210000 i t n u rb140000 o J 70000
0 8000 7000 were carried out on two different clusters: PC-cluster and HPC-cluster. The characteristics of both clusters are provided in [17]. Figure 3 and Figure 4 show the actual and predicted jobs runtime on the PC-cluster and HPC-cluster, respectively. The jobs runtime are shown for different data size that is determined by the number of problem parameter variants. This time was predicted using the three methods discussed above. Obviously, the most accurate prediction in both cases was formed on the basis of the modules testing.
Actual job runtime Predicted job runtime based on the module testing Predicted job runtime based on the computational history Predicted job runtime based by users
Figure 5 and Figure 6 demonstrate the runtime prediction errors obtained through the various methods for estimating the module runtime. The errors are shown in percentages relative to the actual job runtime on the PC-cluster and HPC-cluster, respectively.
Error of the prediction based on the modules testing Error of the prediction based on the user's estimation
Error of the prediction based on the computational history 31.73 31.73 61.57 121.98 246.73
Data size, MB
Figure 6. Runtime prediction error for the HPC-cluster.
These results show that the error in the job runtime predicted based on the module testing decreases with increasing the data size in the both cases. In the example, it does not exceed 10%. At the same time, a change of the runtime prediction errors obtained owing to user’s estimates or computational history can be non-monotonous. In practice, the job runtime predicted based on a user’s estimates is usually overstated. The use of computational history can slightly reduce such errors.
The rational allocation of resources in solving large problems in a heterogeneous distributed computing environment depends on the effectiveness of job maintenance schedules planned by LRMs. Usually, these schedules are based on estimates of program execution time.
In the paper, we propose new models for predicting the job runtime using a variety of estimates. Such job specifies the execution of a problem-solving scheme of a distributed applied software package (large-scale scientific application) in the environment. Within these models, we take into account job execution in modes of data readiness and fork/join, resource virtualization, and job restarts.
The practical significance of the study lies in improving the quality of planning computations and resource allocation in heterogeneous environments. Such an improvement is due to reducing the error in estimating the job runtime through the application of the proposed models.
The study is supported by the Russian Foundation of Basic Research, project no. 19-07-00097. The development of the heterogeneous distributed computing environment was supported in part by the Basic Research Program of SB RAS, project no. IV.38.1.1. Applied Software Packages Proc. of the 42th Int. Convention on information and communication technology, electronics and microelectronics (Riejka: IEEE) pp 1775–1780 [7] Voevodin V V 2007 The solution of large problems in distributed computational media.
Automat. Rem. Contr.+ 68(5) 773–786 [8] Pegasus WMS – Automate, recover, and debug scientific computations. Available at: https://pegasus.isi.edu/ (accessed: 02.03.2020) [9] da Silva R F, Juve G, Deelman E, Glatard T, Desprez F, Thain D, Tovar B and Livny M 2013 Toward fine-grained online taskcharac-teristics estimation in scientific workflows: Proc. of the 8thWorkshop on Workflows in Support of Large-Scale Science pp 58–67 [10] Wilhelm R et al. 2008 The worst-case execution-time problem – overview of methods and survey of tools ACM T. Embed. Comput. S. 7(3) 1–52 [11] Wang W, Wang W, Guan X, Zhang X and Yang L 2006 Profiling program behavior for anomaly intrusion detection based on the transition and frequency property of computer audit data Comput. Secur. 25(7) 539–550 [12] Intel® VTune™ Profiler (formerly Intel® VTune™ Amplifier). Available at: https://software.intel.com/en-us/vtune/ (accessed: 02.03.2020) [13] OProfile – A System Profiler for Linux. Available at: https://oprofile.sourceforge.io/news/ (accessed: 02.03.2020) [14] Adhianto L, Banerjee S, Fagan M, Krentel M, Marin G, Mellor‐Crummey J and Tallent N R 2010 HPCToolkit: Tools for performance analysis of optimized parallel programs Concurr.
Comp.-Pract. E. 22(6) 685–701 [15] Ivannikov V P, Gaisaryan S S, Avetisyan A I and Padaryan V A 2006 Estimation of dynamical characteristics of a parallel program on a model Program. Comput. Soft.+ 32(4) 203–214 [16] Novopashin A P and Oparin G A 2004 Boolean Modeling of Action Planning in Distributed
Computing Systems J. Comput. Sys. Sc. Int.+ 43(5) 763–766 [17] Tchernykh A, Feoktistov A, Gorsky S, Sidorov I, Kostromin R, Bychkov I, Basharina O, Alexandrov A and Rivera-Rodriguez R 2019 Orlando Tools: Development, Training, and Use of Scalable Applications in Heterogeneous Distributed Computing Environments Comm. Com. Inf. Sc. 979 265–279 [18] Bychkov I, Oparin G, Tchernykh A, Feoktistov A, Bogdanova V, Dyadkin Yu, Andrukhova V and Basharina O 2017 Simulation Modeling in Heterogeneous Distributed Computing Environments to Support Decisions Making in Warehouse Logistics Procedia Eng. 201 524–533 [19] Feoktistov A G, Kostromin R O, Fereferov E S, Tchernykh A, Basharina O Yu, Dmitriev V I and Kurzybova Ya V 2019 Toolkit for simulation modeling of queue systems in Grid Proc. of the 1st International Workshop on Information, Computation, and Control Systems for Distributed Environments (ICCS-DE) (CEUR-WS Proceedings) 2430 pp 51–59 [20] Public access center Irkutsk Supercomputer Center. Available at: http://hpc.icc.ru (accessed: 02.03.2020)