УДК 004.75: 004.451.44

 

Olha Prila, PhD student

CNTU, Chernigiv, Ukraine

THE ALGORITHM OF JOB SCHEDULING IN GRID ENVIRONMENT BASED ON THE DYNAMIC PROGRAMMING METHOD

О.А. Пріла, аспірант

ЧНТУ, м. Чернігів, Україна

АЛГОРИТМ ПЛАНУВАННЯ ЗАВДАНЬ У ГРІД-СЕРЕДОВИЩІ НА БАЗІ МЕТОДУ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

О.А. Прелая, аспирант

ЧНТУ, г. Чернигов, Украина

АЛГОРИТМ ПЛАНИРОВАНИЯ ЗАДАЧ В ГРИД-СРЕДЕ НА БАЗЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

The problem of the effective usage of the grid environment for solving different types of computing tasks of large dimension is researched in the paper. We study the problem of optimal task scheduling at an affordable set of resources on the one hand and the equitable distribution of resources between the tasks that come into the input queue of a centralized workflow management system, on the other hand. Two stage strategy of task scheduling in grid environment that takes into account user-defined QoS requirements, structural features and execution dynamicity of the task is presented. The dynamic programming method application to the workflow scheduling problem is proposed in the paper and the effectiveness evaluation experimental results of the proposed decision are given.

Key words: grid, workflow, scheduling, quality of service.

Досліджується проблема ефективного використання грід-середовища для вирішення різних типів обчислювальних задач великої розмірності. Розглядається задача оптимального розміщення обчислювальних блоків завдання на доступній безлічі ресурсів з одного боку і справедливого розподілу ресурсів між завданнями, які надходять у вхідну чергу централізованої системи управління потоками завдань, з іншого боку. Представлена двоетапна стратегія планування завдань у грід-середовищі, що враховує встановлені користувачем вимоги до рівня QoS, структурні особливості та динаміку виконання завдання. Запропоновано застосування методу динамічного програмування до задачі планування в грід-середовищі і представлені результати експериментального дослідження ефективності запропонованого решення.

Ключові слова: грід, потік завдань, планування, якість обслуговування.

Исследуется проблема эффективного использования грид-среды для решения разных типов вычислительных задач большой размерности. Рассматривается задача оптимального размещения вычислительных блоков на доступном множестве ресурсов с одной стороны и справедливого распределения ресурсов между задачами, поступающими во входную очередь централизованной системы управления потоками задач, с другой стороны. Представлена двухэтапная стратегия планирования задач в грид-среде, учитывающая установленные пользователем требования к уровню QoS, структурные особенности и динамику выполнения задачи. Предложено применение метода динамического программирования к задаче планирования в грид-среде и представлены результаты экспериментального исследования эффективности предложенного решения.

Ключевые слова: грид, поток задач, планирование, качество обсуживания.

Introduction. Currently grid technologies are actively developed and applied for solving of complex high-dimensional problems such as economic and ecology prognosis, medical information processing and others. The problem of task adoption for effective execution in the grid environment is rather complex itself. Abstract features of using of the grid-infrastructure for different types of tasks’ execution based on their structural but not functional features can be determined.

The actively developing field in the grid-computing is the technology of workflow execution in grid-environment. The workflow represents the task as a sequence of subtasks with certain synchronization scheme. The presence of several parallel blocks in such tasks allows to execute them on different resources for more efficient problem solution. To provide such a solution several factors should be taken into account and the most important of them is the expenses for data exchange between utilized resources. Workflow scheduling is an NP-complete problem in general [1].

Another component that is very important for grid end-users is the ability of a grid system to provide its consumers with the required quality of service (QoS). It results in the need to allocate task on a set of resources which is most suitable for its execution depending on the QoS information provided by the resources. While for non-commercial community grids it is limited to estimate completion time (ECT), commercial utility grids can also operate with costs of calculations and some other parameters.

The paper is dedicated to the research of the aspects of scheduling different types of tasks in grid-environment. Another research problem is the strategy of the central queue of grid tasks processing according to their priorities and QoS requirements.

The complex two stage strategy for tasks’ queue processing and task scheduling next is proposed in the paper.

The formalization of the task of scheduling different types of jobs in grid environment. One of the factors influencing the performance of the grid-network is planning efficiency. Taking into account the heterogeneity of grid-resources, as well as the structural features of tasks, the following factors should be understood under the scheduling efficiency:

1) equable load of all the grid computing elements;

2) the minimal tasks’ downtime in the run queue;

3) the minimal execution time of tasks on a dedicated set of resources, including the time required for data transfer between computing blocks.

The classification of the tasks which are calculated in the grid-environment according to the structural criterion has been suggested by the authors [2].

The execution effectiveness of the task represented by a single computing unit or a set of consistent, depends on the effectiveness of its program implementation, planning strategies of the low-level grid brokers and local scheduler.

If the task is represented by a set of similar tasks with different input data, scheduling optimization reduces to decomposition of the task according to the current options of grid-infrastructure.

The presence of parallel blocks in workflow tasks allows executing them on different resources for more efficient problem solution. To provide such a solution the expenses for data exchange between utilized resources should be taken into account.

The expenses for data exchange can be eliminated by clustering several blocks of workflow for the same resource. There is a concept of linear and nonlinear clustering [1], when serial or parallel blocks are grouped respectively. The optimization problem is reduced to finding the optimal solution between parallelization and clustering.

Workflow task is generally modeled by a precedence-constrained task graph, which is a directed acyclic graph with nodes representing the subtasks and the directed edges representing the execution dependencies between them as well as the amount of communication.

For effective workflow scheduling the following subtask parameters must be defined:

{ECT, Memory, {T}},

where ECT - estimated completion time;

Memory – memory requirements;

{T} – set of links to other modules (one-way communication between nodes).

For effective execution in the grid-environment the following limitations are imposed for the workflow structure.

1. Lack of loops and branches. These limits are determined by the task structure presentation in the form of an acyclic directed graph. However, the task structure having loops can be converted to DAG by adding an additional level. Branching can be handled at the level of metascheduler through the dynamic approach to planning.

2. High level of task granularity. The dimension of calculations should be much higher in relation to the dimension of the transmitted data [1]. In [3] the granularity problem is defined as follows:

, (1)_

where  – computational complexity of node ;

– dimensionality of the data being transferred between nodes and ;

 – the number of computing nodes of the task.

Grid-network structure can be presented as a complete directed graph where vertices define the resources, and the weight of arcs define bandwidth computer network. Each unit of the grid-net structure is characterized by the following compulsory parameters.

{CPU, Memory, Cost, {R1, R2}},

where CPU – computational power;

Memory – memory characteristics;

Cost – usage cost;

R1 – receive data network bandwidth;

R2 – data transmission network bandwidth.

The optimization task presupposes working out an optimal computing units arrangement on the available set of resources.

The traditional classification of jobs scheduling tasks is presented in [4] but it does not take into account the multicriterion characteristic of the objective function. However, besides the job performance time, the competitive criterion, computing cost, is significant for the commercial grid-environment. The task of workflow scheduling in the grid-environment is NP-complete problem in general.

At the middleware level grid does not provide full support for the tasks of different types. For instance, ARC Nordugrid (http://www.nordugrid.org/) and gLite (http://glite.cern.ch/), which are considered as main providers of grid middleware in EMI (http://www.eu-emi.eu/) and which are widely used by the Ukrainian national grid-infrastructure make use of the following formats of the grid-tasks specifications: JSDL [5], xRSL [6] and JDL [7]. Among the mentioned JDL-format is the only to introduce the notion of the task type (Job, DAG и Collection), which still has certain limitations – the determination of the periodic synchronization between the units and the data transmission volumes is impossible. JSDL and xRSL formats provide just means of determining the parameters of single tasks; the workflow tasks, as well as the relations between single tasks, is not supported.

Middleware grid brokers realize simplified scheduling strategies and do not allow workflow scheduling taking into consideration the tasks structure and QoS parameters. For instance, ARC Nordugrid broker realizes the following strategies of the available computing resources selection: RandomBroker, BenchmarkBroker, FastestQueueBroker, DataBroker [6]. The latter means that the mechanisms of complex grid-tasks scheduling are to be realized and arranged beyond the middleware grid level.

The structure of the metascheduler of the centralized workflow management system. An important component of the use of the grid-environment is to provide its consumers with the required level of quality of service (QoS).

In addition to finding the optimal schedule of workflow task on the set of available computing resources, the important aspects of the metascheduler are: a) the strategy of processing the input queue of tasks in accordance with their priorities; b) the choice of the scheduling algorithm according to the structural features of the task; c) dynamic control of task execution; d) accounting the dynamicity of grid-network as well as the level of quality of service of grid resources.

Below we consider the metascheduler implementation aspects which are an integral part of the centralized workflow management system. Lack of the centralized approach, which consists in the possible occurrence of bottleneck, is assumed to be eliminated through the scalable workflow management system architecture.

This paper introduces a two-stage strategy for task scheduling in grid environment. The first stage involves the processing of the input queue of tasks in accordance with their priorities and QoS requirements. The second phase involves task scheduling at the affordable set of resources taking into account the structural features of the task.

Below we consider the approaches to scheduling the workflow task on the set of available heterogeneous grid-resources as well as strategies for handling the input queue of tasks of different types accounting the dynamicity of their execution.

Dynamic programming method application to the problem of workflow scheduling. In [1; 8; 9] the classification and the results of the algorithms’ effectiveness and complexity evaluation are given.

The methods of search in the space of states and methods of mathematical programming can produce optimal solutions, but in general are characterized by high computational complexity of the algorithm. Heuristic approaches can give effective solutions in polynomial time, but in general these approaches do not provide the optimal solution, as the average, the worst and the best performance of these algorithms is unknown [1].

Clustering (DSC, CASS-II [10]) and replication (TDS, TANH [11]) approaches aimed at reducing the time required for data transfer between nodes by placing tasks that require the exchange of large amounts of data on a single resource or duplicate blocks, respectively [9]. The disadvantages of these approaches is the difficulty of accounting the heterogeneity of the subtasks, and the lack of opportunities to use several resources grid-network for parallel blocks task.

An important aspect of the use of commercial grid-environment is the need to optimize the mutually exclusive characteristics of resource cost and execution time taking into account the significance of the coefficients of each one. Most heuristic scheduling algorithms focus on improving one of the criteria. Today, the only workflow scheduling algorithm that solves the multiobjective optimization problem is the LOSS / GAIN algorithm [8]. Many of the existing scheduling algorithms impose some restrictions on the structure of the task and the structure of grid-network.

Dynamic programming method is one of the methods of mathematical programming, applied to the problem with optimal substructure. Optimal substructure problem assumes that the optimal solution of its constituent smaller subtasks can be used to solve the original problem [12].

The algorithm introduces the concept of levels in the structure of the work flow, which are determined by a variety of tasks that can be performed simultaneously at a certain stage of the task. For example, a workflow structure shown in Fig. 1 (a) may be allocated to the following levels: 1) {A1}; 2) {A2, A3, A4}; 3) {A5} and 1) {B1}; 2) {B2, B3, B4}; 3) {B5, B6}; 4) {B7} for the sctructure shown in Fig. 1 (b) respectively.

Optimal solution contains optimal solutions at every level, and, therefore, the task has the property of optimality [12].

The objective function of the algorithm can be determined by several parameters that have some weight. Accordingly, the objective function might look as follows:

(2)

where k₁, k₂ - user-defined coefficients of QoS parameters;

time – task execution time;

cost - the cost of computing resources usage.

(a) Example DAG A (b) Example DAG B

Fig. 1. Two example DAGs

The flowchart of the algorithm is shown in Fig. 2.

Fig. 2. The QoS-based scheduling algorithm flowchart

As it can be seen from the flowchart that at each level for each allocation variant the optimal solution is saved regarding the allocation cost as well as the cost of interaction with the blocks of the previous levels. Inefficient solutions for each location are discarded and will not be further considered. At the last step of the algorithm the global optimal solution is determined moving backward from the bottom up through the levels. It is recommended to store the allocation plans ordered by the value of the objective function, which can be used for dynamic rescheduling problem if necessary.

The strategy of input queue of tasks processing. We have considered the issues of planning a separate task represented as a workflow at an affordable set of heterogeneous resources. In this section, we will discuss approaches to processing and scheduling of various types of tasks coming into a single input queue of workflow management system.

In [13] the following existing multiple workflow scheduling strategies are presented.

1. Scheduling and execution DAGs that are in the input queue one after another. The disadvantage of this approach is the ineffective grid resources utilization, inability to reflect the priorities and the required level of QoS.

2. Scheduling and execution of DAGs in accordance with the criterion of total estimated runtime. Processing order may be different: the priority for tasks with a minimum execution time or the maximum. Such approach does not solve the problem of effective resources utilization and QoS considering.

3. Combining multiple DAGs into a single DAG with a further usage of existing methods of single workflow task scheduling in a heterogeneous environment.

The following four main approaches of merging DAGs are determined.

1. Policy C1: Combining DAGs by adding a new entry and new exit “empty” nodes. The combining technique application for two DAGs shown in Fig. 1 is presented in Fig. 3.

 

Fig. 3. Common entry and common exit node technique

2. Policy C2: A composite graph is created in the same way as before, but the scheduling is made by the levels for independent parallel tasks (level-based ordering) (Fig. 4).

3. Policy C3: Scheduling and execution of different computational units of workflow tasks occur in the style of round-robin: if on the previous step the task of one workflow was planned and carried out, then on the next step it will be considered as the ready task of another workflow.

4. Policy C4: When combining DAGs into a single workflow structure the estimated execution time of workflow is taken into account and merging by introducing additional nodes occurs at the appropriate level (Fig. 5).

Fig. 4. Level based ordering Fig. 5. Ranking based composition technique

Two fairness policies of resources distribution based on calculating the delay of each workflow while choosing the next workflow for scheduling have been introduced in [13].

However the merging DAGs approaches and fairness policies can be applied only to the workflows with the same priorities.

In [14] a ServeOnTime strategy is proposed and its efficiency in comparison with the classical approach FCFS (first come first serve) is shown. The strategy is based on adding the new arrived workflow task to the exiting task of executing workflow. Such an approach ignores the QoS requirements, and underutilized resources associated with the occurrence of "gaps" (waiting for completion of the tasks of the previous level and data transfer). In [15] a GapSearchScheduling algorithm is presented. The algorithm is based on finding and filling such gaps by tasks, the execution time of which is less than the gap size.

In [16] the input queue deadline coordinator structure is presented. The deadline driven (DD) coordinator orders DAGs considering deadlines specified by users. DAG with earlier deadline is processed first. DAG priority is computed inversely to deadline value. The DD-coordinator should verify that the deadline is realistic. However, the solution is not complete. Deadline set by the user must be considered in relation to the estimated execution time and the arrival time of all tasks.

We suggest the following scheme of tasks priority evaluation:

(3)

where U_p – user task priority set by the policy of appropriate virtual organization;

t_in –arrival time of task queued for execution.

When sending a task to perform, the user can set the desired values for the following QoS parameters: restriction to the task time execution (deadline), cost limit of computing (maximal cost), as well as the significance of the coefficients of these parameters.

Taking into account the dynamicity of the grid environment structure, compliance with user-defined QoS-parameters can not be guaranteed, but finding the optimal solutions based on the established significance coefficients is guaranteed. Defining the actual values of QoS parameters is possible by the use of simulation model of task execution process.

Guaranteed compliance deadline is possible only for the tasks submitted with advanced reservation policy, and the preliminary assessment time regarding to the task execution time is set by the workflow management system administrator. In the case of low QoS level of available resources replication approach can be used in addition.

Internal xml task specification format has been developed. The format allows describing the tasks of different types, as well as to determine the volume of data transferred between the computational units of workflow task and periodic synchronization between the parallel blocks. When the task is sent to a specific computing resource the task format is converted to those required by the corresponding middleware.

There are static and dynamic approaches to task scheduling. Static approach assumes the availability of information about the current state of grid-network resources and task’s blocks execution sequence prior to computation. Dynamic approach takes into account the dynamic grid-network resources, as well as handles branching in the structure of the problem. However, this greatly complicates the planning process.

The paper introduces the use of a hybrid approach to planning, which is to use static methods for primary distribution, followed by the dynamic regulation of the primary distribution, taking into account the dynamics of the task and the state of network resources. Such a scheme is implemented at the level of the metascheduler through periodic survey of the state of the network resources, task’s units execution control and rescheduling tasks when needed.

The system is supposed to have the following task queues.

1. Single Block And Data Parallel Queue – contains the tasks of the first and the second type. In case of the resource failure, the task is resubmitted to the same queue with the highest priority.

2. Workflow Queue – contains workflow tasks.

3. Workflow Tasks Rescheduling Queue – contains computational units of different workflow tasks requiring rescheduling. Computing unit of any workflow is put into this queue if the resource that was scheduled for the unit failed.

Queue processing and tasks scheduling is made in the order of their priorities. Rescheduling is processed first, and the rescheduling task is assigned to a suitable free resource or the nearest "gap" in the schedule of resource employment.

If several tasks have the same priority, they are merged into a single DAG according to the combine policy C4.

Single DAG scheduling is made using the method presented in the previous section, with further drafting task’s schedule taking into account the synchronization between units and graphics of resources employment.

While scheduling the workflow if the amount of the free resources is less than the width of the DAG then the estimated execution time on the set of available resources is compared with the estimated execution time on the greatest possible variety of resources. If the difference in execution time is less than the waiting time of deallocation, the task is assigned to the available resources, or the task is waiting for the release of resources employed and the optimal schedule for its implementation since the liberation of resources is prepared.

Single blocks of tasks are assigned either to a suitable free resource, or to the nearest appropriate "gap" in the graph of the resource. "Gap" is considered appropriate if the estimated execution time of the task is less than gap size.

Scheduling algorithms effectiveness evaluation. The experiments were carried out only for the analysis of the effectiveness of the proposed single DAG scheduling method on the available set of resources. Effectiveness evaluation of the proposed strategy for processing the queue of tasks taking into account the dynamics of their implementation requires additional research.

To investigate the properties of scheduling algorithms the GridSim toolkit [17] was expanded by adding new entities required for modeling the processes of planning and execution of workflows in the grid-environment. The experiments were carried out for randomly generated workflow tasks of varying complexity.

The grid-environment experimental model was presented by four compute nodes with the following characteristics: CE1 = {10 mips, 100, 0, {100, 50}}; CE2 = {25 mips, 100, 0, {100, 20}}; CE3 = {35 mips, 100, 0, {80, 40}}; CE4 = {47 mips, 100, 0, {100, 30}}.

The effectiveness of a scheduling algorithm in the experiments was determined by: 1) the objective function value; 2) the computational complexity of the algorithm. In order to simplify the objective function was defined by task execution time, excluding the economic costs.

Table 5 shows the results of the experiments for the tasks of different complexity and the following scheduling algorithms: 1 - heuristic algorithm HEFT, 2 - scheduling algorithm based on dynamic programming method, 3 - random selection of the resource to perform the task of computing unit, ready to run, excluding the cost of accommodation.

Proposed algorithm showed a higher efficiency for the workflow runtime criterion. Scheduling time of the proposed method is higher than for other algorithms, but it is incomparably less the workflow runtime in the grid-environment that justifies the appropriateness of the proposed solution.

Table 5

Experimental results

Number of nodes	Number of links	Number of levels	Scheduling time, ms	Runtime, s	Algorithm	The ratio of the (number of nodes / number of links)
10	13	5	3	518,4	1	0,769231
25	34	7	9	6859,91	1	0,735294
50	72	9	30	7241,28	1	0,694444
10	13	5	5	408	2	0,769231
25	34	7	12	5833,44	2	0,735294
50	72	9	43	6167,76	2	0,694444
10	13	5