The paper presents an overview of modern methods for task scheduling in desktop grid systems, estimates of the quality of methods, including: the time of execution of all tasks, the level of resource utilization. Heuristic approach to task scheduling is considered, which allows ensuring high performance and reliability of such systems at the early stages of development. A comparative analysis of the results of computational experiments performed with the help of the GridSim high performance computing simulation tool for various desktop grid system configurations is carried out.
The desktop grid is a grid system that unites personal devices (personal computers, laptops, smartphones, etc.) using telecommunications networks and uses their idle computing resources for calculations. In the early 2000s, the desktop grid implied the unification of only personal computers. Today, the desktop grid is a heterogeneous system that combines not only various non-specialized computing devices, but also multiprocessor computing systems with a large amount of hardware and software heterogeneity. The idea of recycling idle resources of a large number of personal computers is extremely attractive. Such a solution, which requires almost no costs, has enormous potential. The technology of organization desktop grid has the following advantages: ease of deployment; low cost; high scalability (hundreds of thousands computing nodes); high potential peak performance; low financial cost of creation and maintenance. But there are also a number of features characteristic of such grid systems: high hardware and software heterogeneity; lack of information about the availability of nodes; low reliability of nodes. And the simultaneous provision of energy efficiency, safety, reliability and high performance is a pressing issue for modern grid systems. These goals conflict with each other and require increased attention to the problem of scheduling tasks at the desktop grid.
In papers [
The proposed approach to scheduling jobs – Sort-Median (SM). The main objective of the proposed heuristics is to reduce the overall execution time of all tasks and increase the level of utilization of the resources of the grid system. Let T={ti : i=1, 2, …, n} – a set of computing tasks in the desktop grid, with each task ti has a length lengthti in FLOP. Let H={hj : j=1, 2, …, m} – a set of computational nodes, with each node hj have performance powerhj in FLOPS. Then the schedule for performing the set of tasks T on the set of computing nodes H of the system is determined by the following expression: = { ∶ ∈ , ∈ }, where N is the set of numbers of computing tasks to be performed on the nodes of the grid system, according to schedule S, and M is the set of numbers of computational nodes to which these tasks will be assigned. We will also define a matrix in which we will store estimates for the completion of tasks (Completion Time, CT): where eij is the task execution time ti on the hj node, rj is the release time of the hj resource.
The description of this algorithm can be divided into the following steps: 1. CT matrix initialization — for each task, the execution time on each computing node is estimated; 2. bypassing a set of tasks is performed if it is not empty: 2.1. The CT matrix is sorted and the SCT (Sorted Completion Time) matrix contains the medians in rows (for each computational task) – this characteristic, unlike the average value, reflects how “expensive” the miscalculation of a particular task will cost, if it is not counted first; 2.2. assigns the task tk with the maximum median to the computation node hp with the minimum (1) (2) completion time; 2.3. the rp value is updated, as well as the column with the index p of the matrix CT; 2.4. removes the tk task sent for rendering from the set.
Unlike the previously proposed Min-Min or Min-Max algorithms, this algorithm allows you to get a comprehensive assessment when assigning tasks to a computational node, namely, to show the degree of efficiency of calculating a particular task in the first place.
To model distributed computing systems, a special class of software is used. Depending on the
method of reproducing the processes of functioning of distributed systems, these tools are divided into
two classes: emulators and simulators. Simulators include the following systems: OptorSim [
As part of the studies conducted on the basis of the GridSim software, an application was developed for modeling the operation of the grid system and testing the tasks scheduling algorithms. The following modeling scenarios were highlighted (Table 1), the main task of which is to evaluate the effectiveness of the proposed approach to scheduling in comparison with existing algorithms according to the above criteria and the behavior of the grid system at the early stages of its development, when the number of computing nodes is sufficiently small.
Number of computational nodes 10 50 100 tasks 1000 6000 15000
For a comparative analysis of the proposed scheduling algorithm with existing ones, we introduce two quality assessments: the level of utilization of the resources of the grid system (Grid Utilization, GU) and the total execution time (Makespan). Let the execution time of all tasks: Then the level of utilization of the resources of the grid system:
= max{ |∀ 1 ≤ ≤ }. = ×
∑ =1 .
(3) (4)
The proposed quality estimates were calculated for the following scheduling algorithms: MaxMin, Min-Min, RASA, Sort-Median. The diagram of the total task execution time (Figure 1) shows the advantage of the proposed Sort-Median heuristics for all grid modeling scenarios. (5) (6) (7) load among all the computational nodes of the system. Despite the fact that the Sort-Median algorithm has improved the performance of the grid system and increased the level of resource utilization, using it in the proposed form for scheduling tasks on a real grid system is unacceptable. This approach allows to take into account the variation in the performance of resources and the complexity of computing tasks, but does not take into account the possibility of failure of the computational nodes, as well as their return of erroneous results. These restrictions make it difficult to complete tasks on time, they require additional time spent on re-execution of tasks. Therefore, it is necessary to modify the Sort-Median algorithm to ensure the reliability of the calculations. Since the planning of tasks is considered at the early stages of the development of the grid system, when there are no statistics on the activity of computational nodes, reputational methods lose their relevance. The use of various prediction heuristics is also difficult, since it is difficult to estimate the number and reliability of computational nodes that can join or leave the system at any time. Therefore, premature scheduling of all tasks on all compute nodes is the wrong approach. It is advisable to use short-term planning: break up the set of all tasks into small subsets and make a decision about planning a specific subset of tasks after returning a certain percentage of correct results. This approach will allow assessing the state of computational nodes set at each scheduling iteration and make a decision on the assignment of tasks.
Let the size of each subset be equal to the number of nodes in the grid system, and each new iteration of short-term scheduling occurs when returning 35% of the valid results of the subset. It is proposed to calculate the delay for each node:
where aij is the actual time of execution of the task ti on the hj node, and q is the number of correctly calculated tasks by the hj node. Then we introduce two types of penalties for each node: for delay and for failure (failure or incorrect answer). The size of the penalty for failure for each computing node is determined by the expression:
∑ = =1(
− ), = ∑
=1 ,
= + ( + ), where g is the number of failures and incorrect answers for the hj node. Define the resulting matrix as a weighted sum:
The weighting factor w is the proportion of correct calculated results from all tasks. Accordingly, as the number of tasks not counted decreases, the importance of the above penalties increases during planning. The modified heuristics of the algorithm Sort-Median called PSM (Penalty Sort-Median). Let us determine the characteristics of scenarios with the presence of failures in the operation of the grid system for comparing the heuristics of Sort-Median and PSM. The simulated percentage of failover computing nodes will vary from 20 to 35. The results show a significant decrease in the total runtime of the script (about 60%) when using short-term planning and the PSM algorithm in comparison with the Sort-Median algorithm. The main disadvantage of this solution is a decrease in the level of utilization of resources due to an increase in their idle time.
An approach using Sort-Median heuristics for scheduling tasks in desktop grid is proposed. A comparative analysis of the algorithms showed the advantage of the proposed approach. Sort-Median utilizes more than 99% of the grid system's resources in all cases, and also improves the performance of the grid system by 3%. Penalty Sort-Median (PSM) heuristic was also proposed using short-term scheduling, which is important for desktop grids at the early stages of their development.
This work was supported by the Russian Foundation for Basic Research (grants No. 18-2903264, 18-57-06003).