Investigating reallocation algorithms in computational grids and presenting an efficient algorithm

Master's Thesis in the field

Computer Engineering (Software)

Abstract

Torin computing networks (GRID) have provided a platform to use heterogeneous resources in different geographic locations to solve complex scientific, engineering and business problems. Scheduling operations play a key role in the performance of Grids. Due to the dynamics of resources and imprecise estimation of execution time. To support fault tolerance, increase resource efficiency and reduce task completion time, which is called rescheduling. In this thesis, two independent task scheduling algorithms and a task flow scheduling algorithm are presented, taking into account the dynamics of the environment, whose goals are to reduce execution time, increase resource efficiency, create load balance, and support fault tolerance. First

Introduction

1-1 Introduction

The term "grid" was proposed in the mid-1990s and grid computing infrastructure (grid computing) was proposed in the field of advanced science and engineering [1].  The main idea of ??grid environment is to share computing resources. Today, most people have more computing power on their computer systems than they need. Therefore, the discovery of geographically distributed computing resources and their use to solve applications that require high computing power and must be executed in a certain period of time at a certain cost are promoted. Such infrastructures are called computing grids, and have led to the popularity of a field called grid computing [1].

From the connection of computing resources such as personal computers, workstations, clusters, servers, supercomputers, etc., distributed in different geographical regions, Turin computing networks (grids) have emerged, which are used as a computing platform to solve large-scale problems in academia, research and industry [2].

One Allocation of resources to tasks is one of the main operations to ensure efficiency in Turin computing networks. Resource allocation operations should provide mechanisms to support fault tolerance, ensure the sure execution of tasks, increase resource efficiency, and reduce task completion times. Scheduling in the grid environment is a part of NP-complete problems due to the geographical distribution of resources and users, resource fluctuations, service quality requirements from applications and restrictions imposed by resource owners [3]. In scheduling independent tasks, the goal is to increase the performance of the entire system, and in scheduling tasks with dependencies, the goal is to reduce the execution time of tasks without violating their priority constraints. By reducing the execution time of tasks, it increases the productivity of resources, as a result, we will have an improvement in the performance of the entire system.

In the last decade, task scheduling (dependent and independent tasks) within the grid environment has attracted the attention of many researchers. Due to the dynamics of the grid environment, the scheduling operation must update its schedule regularly by checking the current state of the system. Update operations occur with the occurrence of an event in the grid due to imprecise estimation of execution time, addition or removal of resources. In fact, the main purpose of applying rescheduling is to increase the productivity of resources, to execute definitively and to reduce the time of completion of work, so that at first it is scheduled based on the current status of resources and tasks, and in the event of the occurrence of the above events, rescheduling is based on the available resources and the status of the remaining tasks. It has been done and it has been shown that the estimates provided by the user are not accurate enough in most cases. The reason for this issue can be seen as that in local resource management systems, when the estimated execution time of the work ends, the work is terminated (cancelled), so users generally estimate the execution time of the work more than the actual time in order to be sure of the complete completion of the work. In various studies, the effect of user estimates on system efficiency has been evaluated, and the results indicate that incorrect user estimates reduce system efficiency.In addition, in the article [4] presented in 2009, the authors showed that local resource management systems are not able to cope with and control a large volume of handovers. In the article [5] that was presented in 2009, the impact of work set variability on the local resource management system was investigated and the results showed that this variability causes worse scheduling decisions. Rescheduling pursues three basic goals: increasing the efficiency of the scheduler, reducing the execution time, and providing fault tolerance.

Scheduling in the grid environment due to dynamics consists of two stages. In the first stage, the scheduler is based on the current state of the resources, and the estimated execution time creates a mapping of tasks on the resources. In the second stage, with the occurrence of an event, the scheduler reschedules based on the tasks, resources, and dependencies between the tasks and produces a new mapping. 1-3 Objectives of the thesis Considering that the grid resources are non-specific and the imprecise estimates provided by users have a significant impact on the grid performance because the tasks that have data dependencies between them (the data generated by this task, need another task is to start) and if we cannot guarantee the definite execution of the work here (due to the failure of the resource) it is not possible to execute the advanced tasks. Also, these inaccurate estimates will reduce the efficiency of the grid. For this reason, there is a need to monitor the status of resources and tasks and apply new mapping (rescheduling) with the occurrence of an event in the grid (change in the status of resources or the execution time of the task). Completing the last task, increasing efficiency, certainty in the execution of tasks and creating load balance. In this thesis, we also try to provide a suitable scheduling algorithm with regard to these goals.

1-4 stages of completing the thesis

In order to complete the thesis, first the concepts of grid and the mechanism of scheduling and rescheduling (re-allocation) in the grid environment were examined and after evaluating the existing methods, the best method was selected and improved.

1-5 Thesis structure

In the second chapter, the basic concepts of timing and passing on previous researches are examined, and in the third chapter, the proposed algorithms are presented, and in the fourth chapter, the results of the evaluation and comparison of the proposed algorithm are given. Scheduling and review of past works

2-1 Introduction

In this chapter, we first describe the concepts and limitations that exist in the grid. Then we check the schedule and its types. Finally, we have an overview of the past works.

Torin computing networks (grid) is a new technology that allows remote access to various types of resources by using communication infrastructures and computer networks, as well as by connecting heterogeneous computing resources at different geographical distances [6]. Today, using this technology, very complex and large applications that require very high processing power and a huge amount of input data can be implemented in grid networks.

Grid computing networks have different divisions in terms of application, and they are: information grid, computing grid, etc. . . In each of them, the purpose and method of allocating resources to users is different. One of the main challenges in computing grids is the mapping of user requested tasks to resources according to scheduling policies. Scheduling is the act of assigning applications to computing resources in such a way that the requirements of applications such as: number of processors, execution time, etc.

The scheduling problem is one of the Np-complete problems [3] and most of the presented algorithms are heuristics. The concepts and limitations that exist in this direction are explained below.

Work: It is an application that requires different processing capabilities (such as the number of processors, memory, required time, etc.) and different limitations. which is usually indicated by specific job descriptions.