1. Introduction
Recent advancements [
1-2
] in the field of parallel and distributed computing led to the
definition of the computing continuum [
3
] as the environment incorporating highly heterogeneous
systems with dynamic spatio-temporal organizational structures [
4
], varying in-nature workloads (Fig
1-a), complex control hierarchies [
5
], governing computational clusters with multiple scales of the
processing latencies, and diverse sets of the management policies [
6-7
]. The emergence of these
systems is the natural response to the ever-growing variability of computational demands. However,
architecting of the algorithms in such environments, e.g. task schedulers, I/O schedulers and resource
scalers, is affected by the high degree of uncertainty in relation to the future operational conditions and
suffers from tractability issues.
(a) (b)
Figure 1. Examples of networks studied in one of the last works [
8
]. (a) - directed acyclic graph of 60
tasks, rendered und library PSLIB. (b) is a network of 256 agents of the computational continuum with
a scale-free topology [
9
].
As the scale of the system grows and the workloads become more heterogeneous in the inner
structure and the arrival patterns, scheduling problem becomes exponentially harder, requiring
problem-specific heuristics. This paper contributes with the set of recommendations and brief analysis
for the existing scheduling algorithms. Due to the lack of space we address reader interested in
theoretical aspects and definition of the computing continuum to the works [
3,8
].
2. Scheduling Methods
Due to the NP-hardness [
11
], the large varieties of algorithms were proposed. We summarized
some of those in the Table 1. To begin with, one possible approach involves problem reformulation in
order to have a more flexible and less computationally demanding control structures [
7
].
Listscheduling methods (Tab.1 #1, 2) do not provide full knowledge on the workflow execution, by
effectively skipping scheduling phase, and replace it with the simplest possible ranking and matching
policies [
10
]. Such methods typically run very fast in polynomial time, however precision is the major
problem in this case. It is important to highlight, that those approaches are de-facto standard in the
case of the large-scale computational systems / workflows and maintain significant robustness with
low resource consumption. Further, non-stationary aspects (e.g. price, performance, reliability
prediction etc.) of the computational network are normally out of scope in this approach and can be
incorporated via various averaging techniques. More specifically, in case we have set of identified
ordinary differential equations or hybrid stochastic/difference equations, we can propagate dynamics
further in time, but use only averaged values in the ranking and matching phases. Interruptions are not
considered here, since schedule is not generated at all.
Generally speaking, we would call these approaches highly entropic, since here we are dealing
with coarse-grained processes. However there is still a very intriguing research question on how to
integrate simple HEFT-like ranking policies [
10
] and FCFS insertion-based polices with dynamics
propagation at different time-scales.
Another two methods, namely GQAP [
12
] and GAP [
13
] are based on the quadratic and linear
precedence relaxation in MIP3 formulation. Precedence constraints, prescribed by the directed acyclic
graph (DAG), are not reflected in the equations. These approaches can be effectively combined with
previous two and offer global picture, when performing matching of the tasks to the partitions of
machines. Again, applicability of these techniques significantly depends on the structure of the
optimization objectives, as quadratic and linear relaxations can inadequately model minimum
makespan problems with the workflow structure. It contrasts, for example, with cost optimization,
which can be independent of the task running times. Dynamic aspects and interruptions are not
considered, because schedule is not generated. One of the drawbacks here is that unbalanced
centralized optimization approach with conventional optimization packages CPLEX or SCIP becomes
impractical for large-scale systems, due to the large number of variables, delays and information
exchange volumes. It leads to huge computational and communication costs. An open question to
investigate is how to define static/dynamic relationships between these controllers and groups of
controlled agents. Therefore, several hybrid schemes have been proposed to solve large-scale
problems, allowing to divide a complex problem into several less complex subtasks. Distributed
hierarchical system management strategies are expected to allow sub-optimal performance of control
systems in large-scale environments, using the principles of locality while balancing the performance
of the whole system, thus enabling scalable infrastructures.
1 GQAP – Generalized Quadratic Assignment Problem
2 GAP – Generalized Assignment Problem
3 MIP – Mixed-Integer Programming
2P-SGS is a polynomial heuristic method in MRCPSP notation [
11
] which takes an
intermediate place as it allows to compute complete schedule in two phases. First phase prescribes
matching of the tasks to machines and second phase performs activity sequencing subject to the
precedence and resource constraints. Algorithm works for discrete execution times and normally
suitable for medium scales, as complexity of the SGS phase is , where n is the number of tasks and k is
the number of resource constraints. More information on that approach can be found in [
11
].
We call 2P-DYNA family of the exact algorithms based on the ODE formulation and optimal
control theory principles [
14-16
]. Interruptions can be considered here, however discretization
intervals must allow that. Non-stationary aspects (e.g. price, performance, reliability prediction etc.) of
the computational network can be modeled very well in this approach and can be incorporated also
with various averaging techniques. Both FDTO4 and FOTD5 formulations are possible, but each will
lead to the different family of methods, including solution of the TPBVP6 and MIP [
15, 16
]. The
general possible approach to optimization at the planning horizon is to implement it by solving the
MILP or MINLP problem (Tab. 1. #7) with appropriate direct, heuristic and metaheuristics methods.
Book [
17
] contains excellent review of the various mathematical models, including exact and heuristic
methods. Both methods #6 and #7 offer very high precision, but also pose extreme difficulty to solve.
Normally, attempt to find exact optimum within these techniques can be used in frames of Monte
Carlo supercomputing simulations of the complex multilayered computing continuum networks.