# Multijob Associated Task Scheduling for Cloud Computing Based on Task Duplication and Insertion

Authors: Lei Shi; Jing Xu; Lunfei Wang; Jie Chen; Zhifeng Jin; Tao Ouyang; Juan Xu; Yuqi Fan
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the emergence and development of various computer technologies, many jobs processed in cloud computing systems consist of multiple associated tasks which follow the constraint of execution order. The task of each job can be assigned to different nodes for execution, and the relevant data are transmitted between nodes to complete the job processing. The computing or communication capabilities of each node may be different due to processor heterogeneity, and hence, a task scheduling algorithm is of great significance for job processing performance. An efficient task scheduling algorithm can make full use of resources and improve the performance of job processing. The performance of existing research on associated task scheduling for multiple jobs needs to be improved. Therefore, this paper studies the problem of multijob associated task scheduling with the goal of minimizing the jobs’ makespan. This paper proposes a task Duplication and Insertion algorithm based on List Scheduling (DILS) which incorporates dynamic finish time prediction, task replication, and task insertion. The algorithm dynamically schedules tasks by predicting the completion time of tasks according to the scheduling of previously scheduled tasks, replicates tasks on different nodes, reduces transmission time, and inserts tasks into idle time slots to speed up task execution. Experimental results demonstrate that our algorithm can effectively reduce the jobs’ makespan.


---

## Body

## 1. Introduction

Due to the rapid development of cloud computing and cloud infrastructure, an increasing number of applications are migrating to the cloud. Because of the strong extensibility and need for cloud computing, many existing tasks need powerful computing power and computing resources. The core of cloud computing is to coordinate many computer resources together, such that users can obtain unlimited resources and process users’ jobs. A cloud platform is built on a variety of computing and network components to achieve the supply and distribution of various resources, and different components have great heterogeneity. Usually, users submit jobs to the cloud platform. The cloud platform divides jobs into multiple associated tasks and assigns them to different components for execution. Components need to communicate to exchange data and get the final result.The associated tasks of a job can usually be represented by a directed acyclic graph (DAG). Each node in the DAG represents a task, and the directed arc represents the sequence constraints between tasks [1, 2]. Only when the current node has completed can the tasks of the subsequent nodes be executed. The execution of the subsequent node may need the result of the predecessor node as the input, so there is data transmission between the nodes. Based on the need for job processing performance, there has been extensive research on associated task scheduling. The DAG-based task scheduling is widely used in DNA detection, image recognition, geological survey, climate prediction, and other practical applications [3]. A heuristic algorithm based on genetic algorithms and task duplication was proposed in [4]. A task duplication-based scheduling algorithm was introduced in [5]. The joint problem of task assignment and scheduling considering multidimensional task diversity was modeled as a reverse auction with task owners being auctioneers; four auction schemes were designed to satisfy different application requirements [6, 7]. The preference of participants for different perceptual tasks is also a key factor to be considered in the auction mechanism, because assigning the least favorite task will hinder participants from participating in future perceptual tasks. A concept of “mutual preference degree” was proposed to capture a participant’s preference, and a preference-based auction mechanism (PreAm) was designed to simultaneously guarantee individual rationality, budget feasibility, preference truthfulness, and price truthfulness [8]. A solution was proposed to detect and remove both short-term and long-term traffic redundancy through a two-layer redundancy elimination design [9]. A list-based scheduling algorithm called Predict Earliest Finish Time (PEFT) was proposed to introduce an optimistic cost table (OCT), which was used for task ranking and processor selection [10].The processor may have idle time slots during processing multiple jobs. If the idle time slots can be fully utilized, the processing time of jobs can be reduced and the performance of job processing can be enhanced. A simple task scheduling algorithm may not be able to make full use of idle resources, so a more refined task scheduling algorithm is needed. In this paper, we study the associated task scheduling algorithm to minimize the jobs’ makespan when the components of the cloud computing platform are heterogeneous.The main contributions of this paper are summarized as follows.(1)
Aiming at minimizing the jobs’ makespan, we model the associated task scheduling problem(2)
We propose a list scheduling algorithm based on task replication and task insertion (DILS), which combines dynamic completion time prediction, task replication, and task insertion. According to the previous task scheduling situation, the algorithm dynamically predicts the remaining completion time of tasks, replicates tasks on different nodes, reduces transmission time, and inserts tasks into idle time slots to accelerate task execution(3)
Experimental results demonstrate that our algorithm can effectively improve the performance of job processingThe remainder of this paper is organized as follows. Section2 summarizes the related work. Section 3 proposes the problem model of associated task scheduling. Section 4 describes the multijob task scheduling algorithm. Section 5 compares our algorithm with other algorithms. Finally, Section 6 summarizes the work of this paper.


## 2. Related Work

In cloud computing platforms, there are many cases of processing multijob tasks, and the scheduling problem of multijob tasks is important to improve the performance of job processing. Previous studies usually took the makespan and energy consumption as the optimization objectives. Related works can be divided into the following categories.The first category of the research investigates the scheduling strategy based on task priority. For example, a task scheduling algorithm based on the multipriority queue genetic algorithm (MPQGA) for heterogeneous computing systems was proposed [11]. In this paper, the authors used a genetic algorithm to assign priority to each task and used the heuristic method of the earliest completion time to complete the processor assignment; the authors also designed crossover, mutation, and fitness functions suitable for DAG scheduling. An algorithm was proposed to calculate the priority of each task to schedule tasks. The algorithm first processes the tasks with higher priority to satisfy the deadline [12]. A performance-effective task scheduling (PETS) algorithm was proposed to calculate the priority of each task based on task communication cost and average computation cost and then select the processor with the minimum earliest finishing time for each task [13].The second category of the research studies the scheduling strategy based on a genetic algorithm. A learner genetic algorithm (denoted by LAGA) was presented to address static scheduling for processors in homogeneous computing systems [14]; the authors proposed two learning criteria named the steepest ascent learning criterion and next ascent learning criterion where they use the concepts of penalty and reward for learning; the algorithm exploits an efficient search method for solving a scheduling problem, such that the speed of finding a schedule could be accelerated and the trapping in local optimal could be alleviated; the algorithm also takes into consideration the idle time reuse criterion during the scheduling process to reduce the makespan. A decentralized scheduling algorithm based on genetic algorithms for the problem of DAG scheduling was proposed [15]; the genetic algorithm presents an effective method for optimization and could consider multiple criteria in the optimization process.The third category of the research studies the scheduling strategy based on load balancing. A task scheduling mechanism was proposed based on two levels of load balance, which satisfies the dynamic task requirements of users and improves the utilization of resources [16]. A stochastic load balancing scheme was designed to provide a probabilistic guarantee against the resource overloading with virtual machine migration, while minimizing the total migration overhead [17].The fourth category of the research focuses on QoS or heterogeneity during scheduling. A complex scene was considered where multiple moving MDs share multiple heterogeneous MEC servers, and a problem named the minimum energy consumption problem in a deadline-aware MEC system was formulated [18]. A network model aimed at improving user experience by pushing the scheduling problem to the task layer was proposed [19]. A QoE requirement was designed to generalize the QoS requirements of a task, which is the ratio requirement. Following this design, a corresponding scheduling policy was proposed to capture QoE for each task and then reached an application-aware transmission allocation. The q-coverage MLAS problem was investigated, which can guarantee that the aggregated nodes are distributed evenly [20]; two algorithms were proposed by scheduling the communication tasks in the bottom-up and top-down manner, respectively; three algorithms were then proposed to ensure that the aggregation nodes are evenly distributed in the network with low delay; additionally, the method to extend the proposed algorithms for the BF-WSNs with multiple channels was also studied. Three allocation-aware task scheduling algorithms were proposed for a multicloud environment [21]; the algorithms are based on the traditional Min–Min and Max–Min algorithms and extended for multicloud environment; all the algorithms undergo three common phases, namely, matching, allocating, and scheduling, to fit them in the multicloud environment. A heuristic algorithm was presented for constructing streaming DAG which converts a large graph together to a DAG with the graph traversal algorithm, and then, a three-stage heterogeneous-aware cluster-scheduling algorithm was proposed to schedule the DAG to a heterogeneous cloud for parallel processing [22]; in the first stage, a parallel linear clustering algorithm was designed to cluster the DAG into a series of linear clusters with different granularities; in the second stage, a heterogeneous-aware load balancing algorithm was designed to map these clusters to different computing nodes in the cloud; in the last stage, a task sorting algorithm was designed to allocate the start time of these clusters as early as possible.The fifth category of the research investigates the scheduling strategy based on task insertion. A Heterogeneous Earliest Finish Time (HEFT) algorithm was proposed to select the task with the highest upward rank value each time, then assign the task to the processor, and make use of task insertion to speed up the completion of the task and minimize the earliest completion time of the task [23]. A heterogeneous scheduling algorithm was proposed [24]; the algorithm takes the improved quantity as the calculation weight and communication weight and adopts an input task repeated selection strategy and an optimization strategy of idle time slot task insertion to improve the efficiency of task scheduling.However, the existing works do not consider the scheduling problem in the case of multijob associated tasks. In this paper, we use DAGs to represent multijob associated tasks and then propose a task Duplication and Insertion algorithm based on List Scheduling (DILS), which can accelerate the execution of associated tasks to minimize the jobs’ makespan.


## 3. Associated Task Scheduling Model

Example 1.
An example of an associated task scheduling problem is shown in Figure1. The job consists of four tasks, task set Tk=t1k,t2k,t3k,t4k and directed arc set ei,jk∣tik,tjk∈Tk. The weight ctik,tjk of directed arc ei,jk is the time required for data transmission from the server where task tik is running to the server where task tjk will run. The weight of the link from task to server is the execution time required for the task to run on the server.Figure 1
Architecture of the associated tasks and processor.Assume that the job set with different priorities to be processed isJ=J1,⋯,Jk,⋯, where Jk is the kth DAG-based job with multiple associated tasks. The tuple Jk=<Tk,Ek> represents the job Jk, where Tk represents the task set of Jk and Ek is the directed arc set ei,jk∣tik,tjk∈Tk between tasks. Each directed arc represents the execution order constraint of two tasks. For example, ei,jk means that the task tjk cannot be executed until the task tik is executed; that is, tik is the preceding task of tjk, tjk is the successive task of tik, and tik and tjk are the ith and jth tasks in job Jk, respectively. The directed arc also indicates that the execution of the subsequent task needs the result of the antecedent task execution. The weight ctik,tjk of directed arc ei,jk is the time required for data to be transferred from the server where task tik is running to the server running tjk. When two tasks connected by a directed arc run on the same server, weight ctik,tjk=0; that is, the communication within the same server is negligible.A DAG-based job is shown in Figure2. In the DAG, task set Tk=t1k,⋯,tik,⋯,t10k contains 10 tasks and directed arc set ei,jk∣tik,tjk∈Tk includes 15 directed arcs. For example, the directed arc from node t2k to node t8k indicates that t2k is the preceding task of task t8k, and the weight of this directed arc represents the communication time between the server running task t2k and the server running task t8k when two tasks are running on different servers.Figure 2
DAG-based job example.Due to the heterogeneity of servers, the execution time of the same task may be different on different servers.P=p1,⋯,ps⋯ represents the set of servers that will run the tasks. We use an execution time matrix Wk=Tk×P to list all possible mapping between the task tik and the server ps. Each element wtik,ps in the matrix Wk represents the time required for the task tik to run on the server ps. The execution time matrix Wk of DAG is shown in Table 1. The server set P=p1,p2,p3 contains 3 servers, and the element of mapping task t2k and server p2 indicates that the execution time of task t2k on server p2 is 18.Definition 2.
In DAG-based jobJk, ingress task tink is the task without any preceding tasks, and egress task toutk is the task without any successive tasks.Table 1
Execution time matrix example.
p1p2p3t1k222136t2k221818t3k322743t4k7104t5k292735t6k261724t7k142530t8k292336t9k15218t10k131633For the DAG-based job shown in Figure2, the ingress task and egress task are tasks t1k and t10k, respectively. If a job includes more than one ingress task, we add a virtual task node with zero computation cost as the virtual ingress task and add a directed arc from the virtual ingress task to each of the original ingress task nodes with zero weight.Definition 3.
ESTtik,ps,the earliest start time (EST) that task tik can be executed on server ps, is defined via Equation (1), where EATps is the earliest time that server ps is available, pretik is the set of the preceding tasks of task tik, and AFTtjk is the actual finish time of task tjk:
(1)ESTtik,ps=maxEATps,maxtjk∈pretikAFTtjk+ctjk,tik,∀tik∈Tk,∀ps∈P.Definition 4.
EFTtik,ps,the earliest finish time (EFT) that server ps can complete the execution of task tik, is calculated via
(2)EFTtik,ps=ESTtik,ps+wtik,ps,∀tik∈T,∀ps∈P.Definition 5.
For job setJ in which the jobs have different priorities, the makespan of job set J, ΓJ, is the completion time of all the jobs and can be calculated via
(3)ΓJ=maxJk∈JAFTtoutk.Given job setJ, the DAG of each job, server set P, and the execution time of each job on each server, we need to schedule the jobs in J on the servers in P, so as to minimize ΓJ, i.e., the makespan of job set J. The detailed notations are listed in Table 2.Table 2
Table of notations.
NotationDescriptionJkThekth DAG-based job with multiple associated tasks.TkThe task set ofJk.EkThe directed arc setei,jk∣tik,tjk∈Tk between tasks.PThe set of servers.tikTheith task of Jk.ei,jkThe directed arc oftik and tjk.c(tik,tjk)The transmission time required for data.psThe server that will run the tasks.wtik,psThe time required for the tasktik to run on the server ps.tinkThe task without any preceding tasks.toutkThe task without any successive tasks.pretikThe set of the preceding tasks of tasktik.suctikThe set of the successive tasks of tasktik.MThe number of servers.


## 4. Multijob Task Scheduling Algorithm

The single-job associated task scheduling problem with the aim of minimizing the makespan is an NP-hard problem [25]. Therefore, the multijob associated task scheduling problem is also an NP-hard problem [26].In this section, a task Duplication and Insertion based on List Scheduling (DILS) algorithm is proposed, which incorporates dynamic finish time prediction, task replication, and task insertion. The algorithm dynamically predicts the remaining execution time of each task according to the scheduling of scheduled tasks. Then, the algorithm schedules the tasks according to the latest time remaining on the server, which can minimize the remaining time. After each task is scheduled, the algorithm can advance the start time of the task by adopting task replication and task insertion. The remaining execution time of each reserved task is updated when the task is scheduled. The algorithm DILS shown in Algorithm1 consists of five parts: calculation of task remaining time, selection of tasks to be scheduled, server allocation of tasks to be scheduled, task replication, and task insertion.Algorithm 1: Algorithm DILS.
Input: Server set P, job set J with each job’s DAG, and execution time matricesOutput: Makespan of the jobs1:for each job JK∈Jdo2:  Calculate the predicted remaining time of each task via Eq. (6) and create the Prediction of Remaining Time (PRT) table;3:   Create an empty ready task list and add the ingress task to the list;4:while ready task list is not empty do5:for each task tik in ready task list do6:      Compute the average path length of tasktik via Eq. (8);7:end for8:      Select the task with the maximum average path length with Eq. (9);9:      Assign the server leading to the minimum estimated path length via Eq.(10) to the task;10:      Task duplication and task insertion;11:      Update the ready task list;12:end while13:end for14:return the completion time of the last scheduled task.


### 4.1. Task Remaining Time Calculation

There is a weight for each task which is the total communication and computation time of all the subsequent tasks. A predicted remaining time (PRT) table maintains the weights of all the tasks, and each elementPRTtik,ps in the table PRT represents the predicted remaining time required for executing all the successive tasks of task tik (1≤i≤N), when it is allocated to server ps∈P. The weight of task tik is closely related to its successive tasks and the number of servers, and we let
(4)Ai,sk=maxtjk∈suctikMINpt∈pPRTtjk,pt+wtjk,pt+ctik,tjk,where suctik is the set of successive tasks of task tik, and let
(5)Bik=∑tjk∈suctik∑pt∈PPRTtjk,pt/MM,where M is the number of servers. Note that no matter which server runs the egress task, the weight of the exit task of each job is 0. That is, for any pt∈P, PRTtoutk,pt=0:
(6)PRTtik,ps=maxAi,sk,Bik,∀tik∈T,∀ps∈P.The weight of tasktik is calculated via Equation (6). In each DAG, starting from the egress task to the ingress task, algorithm DILS recursively calculates backwards the weight of each task on each server and obtains the PRT table.


### 4.2. Selection of the Task to Be Scheduled

When all the preceding tasks of tasktik are scheduled, we call the task tikready. We create a ready task list (RTL) to maintain all ready tasks. Initially, the ready task list contains only one node, ingress task tink, because only the ingress task of each DAG-based job is ready. We calculate the earliest start time (EST) of each task in the ready task list. The EST of the task tik on the server ps, tik on server ps, ESTtik,ps is calculated via Equation (1). The estimated path length (EPL) of the task tik assigned to the server ps is calculated via
(7)EPLtik,ps=ESTtik,ps+wtik,ps+PRTtik,ps,∀tik∈Tk,∀ps∈P.Since each task may be assigned to any serverps∈P, the average path length (APL) APLtik of task tik which is ready can be calculated with
(8)APLtik=∑ps∈PEPLtik,psM,∀tik∈Tk.Considering the difference in execution time of tasks on different paths, the tasktik which is ready and has the maximum average path length is selected as the task to be scheduled; that is,
(9)tik=argmaxtjk∈RTLAPLtjk.The selection of tasks is related to the EST of the task, and EST changes dynamically with the scheduling results of the previous tasks. Therefore, in the process of scheduling associated tasks, the selection of tasks to be scheduled will be changed dynamically.


### 4.3. Allocation of the Server for the Task to Be Scheduled

When the tasktik can get the minimum estimated path length on the server ps, we assign the to-be-scheduled task tik to server ps to reduce the makespan; that is,
(10)ps=argminpt∈PEPLtik,pt.For tasktik, if multiple servers can get the same minimum estimated path length, we randomly assign task tik to one of the servers. The actual start time of the task tik can be calculated by Equation (2). When the server of the task to be scheduled is assigned, some other tasks may be ready to be scheduled, so the ready task list needs to be updated.


### 4.4. Task Duplication

Task duplication obtains multiple copies of the tasktik and then assigns the task copies to different servers for execution, such that the direct successive tasks of task tik can be executed immediately after the execution of tik, instead of waiting for the data generated by task tik to be transmitted through the network. Task duplication works as follows.
(1)
Each tasktjk in pretik is assigned a time weight τjk, that is, the time required for the data generated by the preceding task of task tik to be transmitted to the processor ps where task tjk is to be executed(2)
All the preceding tasks inpretik are sorted in nonascending order according to the time weights(3)
Each of the preceding tasks inpretik is iterative processed. Schedule a copy of task tjk∈pretik to the earliest idle time slot (ITS) of server ps, if the following conditions are met: (I) τjk>EATps; that is, τjk is greater than the earliest available time of processor ps; (II) there is an idle time slot for the copy of tjk; and (III) task tik can start earlier by duplicating tjk


### 4.5. Task Insertion

Task insertion inserts a task into an idle time slot on a processor which is occupied by some tasks after the time slot. Task insertion works as follows.(1)
When tasktik is to be scheduled on server ps, we search all the idle time slots on server ps. When the idle time slot meets the following conditions: (I) ESTtik,ps, the earliest start time of task tik, is no earlier than the start time of the idle time slot; (II) EFTtik,ps, the earliest finish time of task tik on processor ps, is no later than the end time of the idle time slot; we select this idle time slot to insert task tik(2)
If more than one idle time slot satisfies the above conditions, we choose the idle time slot with the smallest difference between the length of the idle time slot and the execution time of tasktik


### 4.6. Time Complexity

Suppose the number of DAGs isK, the number of processors is M, and the number of task nodes in each DAG is N1, N2, …, NK, respectively. For the ith 1≤i≤k DAG, DILS requires the computation of a PRT table, which consumes OM×Ni2 time. The time complexity of calculating the earliest start time and estimated path length of the task on the processor is OM2×Ni2. By executing the insertion mechanism in OM×Ni2 and executing task replication in OM×Ni2, the time complexity of updating the task ready list is ONi2. Therefore, the time complexity of Algorithm 1 is OM2×N12+OM2×N22+⋯+OM2×Nk2=OM2×ΣikNi2. Algorithms HSIP [24] and PEFT [10] are also scheduling strategies based on task insertion, which deal with the case of a single DAG with the time complexity of ON2×M.


## 4.1. Task Remaining Time Calculation

There is a weight for each task which is the total communication and computation time of all the subsequent tasks. A predicted remaining time (PRT) table maintains the weights of all the tasks, and each elementPRTtik,ps in the table PRT represents the predicted remaining time required for executing all the successive tasks of task tik (1≤i≤N), when it is allocated to server ps∈P. The weight of task tik is closely related to its successive tasks and the number of servers, and we let
(4)Ai,sk=maxtjk∈suctikMINpt∈pPRTtjk,pt+wtjk,pt+ctik,tjk,where suctik is the set of successive tasks of task tik, and let
(5)Bik=∑tjk∈suctik∑pt∈PPRTtjk,pt/MM,where M is the number of servers. Note that no matter which server runs the egress task, the weight of the exit task of each job is 0. That is, for any pt∈P, PRTtoutk,pt=0:
(6)PRTtik,ps=maxAi,sk,Bik,∀tik∈T,∀ps∈P.The weight of tasktik is calculated via Equation (6). In each DAG, starting from the egress task to the ingress task, algorithm DILS recursively calculates backwards the weight of each task on each server and obtains the PRT table.


## 4.2. Selection of the Task to Be Scheduled

When all the preceding tasks of tasktik are scheduled, we call the task tikready. We create a ready task list (RTL) to maintain all ready tasks. Initially, the ready task list contains only one node, ingress task tink, because only the ingress task of each DAG-based job is ready. We calculate the earliest start time (EST) of each task in the ready task list. The EST of the task tik on the server ps, tik on server ps, ESTtik,ps is calculated via Equation (1). The estimated path length (EPL) of the task tik assigned to the server ps is calculated via
(7)EPLtik,ps=ESTtik,ps+wtik,ps+PRTtik,ps,∀tik∈Tk,∀ps∈P.Since each task may be assigned to any serverps∈P, the average path length (APL) APLtik of task tik which is ready can be calculated with
(8)APLtik=∑ps∈PEPLtik,psM,∀tik∈Tk.Considering the difference in execution time of tasks on different paths, the tasktik which is ready and has the maximum average path length is selected as the task to be scheduled; that is,
(9)tik=argmaxtjk∈RTLAPLtjk.The selection of tasks is related to the EST of the task, and EST changes dynamically with the scheduling results of the previous tasks. Therefore, in the process of scheduling associated tasks, the selection of tasks to be scheduled will be changed dynamically.


## 4.3. Allocation of the Server for the Task to Be Scheduled

When the tasktik can get the minimum estimated path length on the server ps, we assign the to-be-scheduled task tik to server ps to reduce the makespan; that is,
(10)ps=argminpt∈PEPLtik,pt.For tasktik, if multiple servers can get the same minimum estimated path length, we randomly assign task tik to one of the servers. The actual start time of the task tik can be calculated by Equation (2). When the server of the task to be scheduled is assigned, some other tasks may be ready to be scheduled, so the ready task list needs to be updated.


## 4.4. Task Duplication

Task duplication obtains multiple copies of the tasktik and then assigns the task copies to different servers for execution, such that the direct successive tasks of task tik can be executed immediately after the execution of tik, instead of waiting for the data generated by task tik to be transmitted through the network. Task duplication works as follows.
(1)
Each tasktjk in pretik is assigned a time weight τjk, that is, the time required for the data generated by the preceding task of task tik to be transmitted to the processor ps where task tjk is to be executed(2)
All the preceding tasks inpretik are sorted in nonascending order according to the time weights(3)
Each of the preceding tasks inpretik is iterative processed. Schedule a copy of task tjk∈pretik to the earliest idle time slot (ITS) of server ps, if the following conditions are met: (I) τjk>EATps; that is, τjk is greater than the earliest available time of processor ps; (II) there is an idle time slot for the copy of tjk; and (III) task tik can start earlier by duplicating tjk


## 4.5. Task Insertion

Task insertion inserts a task into an idle time slot on a processor which is occupied by some tasks after the time slot. Task insertion works as follows.(1)
When tasktik is to be scheduled on server ps, we search all the idle time slots on server ps. When the idle time slot meets the following conditions: (I) ESTtik,ps, the earliest start time of task tik, is no earlier than the start time of the idle time slot; (II) EFTtik,ps, the earliest finish time of task tik on processor ps, is no later than the end time of the idle time slot; we select this idle time slot to insert task tik(2)
If more than one idle time slot satisfies the above conditions, we choose the idle time slot with the smallest difference between the length of the idle time slot and the execution time of tasktik


## 4.6. Time Complexity

Suppose the number of DAGs isK, the number of processors is M, and the number of task nodes in each DAG is N1, N2, …, NK, respectively. For the ith 1≤i≤k DAG, DILS requires the computation of a PRT table, which consumes OM×Ni2 time. The time complexity of calculating the earliest start time and estimated path length of the task on the processor is OM2×Ni2. By executing the insertion mechanism in OM×Ni2 and executing task replication in OM×Ni2, the time complexity of updating the task ready list is ONi2. Therefore, the time complexity of Algorithm 1 is OM2×N12+OM2×N22+⋯+OM2×Nk2=OM2×ΣikNi2. Algorithms HSIP [24] and PEFT [10] are also scheduling strategies based on task insertion, which deal with the case of a single DAG with the time complexity of ON2×M.


## 5. Simulation

In this section, we compare the performance of the proposed algorithm DILS with two state-of-the-art algorithms PEFT [10] and HSIP [24]. For this purpose, we consider the effect of the number of DAG-based jobs and processors on the performance of the algorithms. We also investigate the influence of some important parameters on the performance of the algorithms.Example 7.
The scheduling results of the three algorithms for job setJs=<J1,J2> are illustrated in Figure 3, where DAGs of jobs J1 and J2 are the same as that described in Figure 2 and Table 1. The gray shadowed block represents the task to be copied by algorithms DILS and HSIP. In this example, we can see that algorithm DILS has better results than HSIP and PEFT.Figure 3
The example of scheduling result.


### 5.1. Simulation Setup

In this paper, we will evaluate the performance of the three algorithms in terms of the scheduling length ratio (SLR). SLR is the ratio of the scheduling length to the minimum scheduling length by ignoring the communication time, which can be calculated by(11)SLR=∑Jk∈Jmakespan∑Jk∈J∑tik∈CPMINminps∈Pwtik,ps,where CPMIN is the minimum length of the critical path in the DAG-based job after ignoring the communication time between tasks, while the critical path of a DAG-based job is the longest path from the ingress task to the egress task.In the simulations, we use DAG-based jobs randomly generated by a DAG generator and real-world DAG-based jobs. The DAG generator uses the same parameters as in [25, 27]. The DAG topology parameters are as follows:
(1)
DAG average calculation timecDAG¯: indicating the average execution time of the tasks in the DAG, which is randomly set during the simulation(2)
Communication calculation ratioCCR: the ratio of the average communication time and the average execution time; the larger the value, the more communication-intensive the DAG-based job; the smaller the value, the more computation-intensive the DAG-based job(3)
Heterogeneous parameterα: representing the task execution time range on different processors; the larger the value, the more heterogeneous the processorsWe select three classic DAG-based jobs from the real-world applications in the simulations.(1)
Gaussian Elimination: it is used in linear algebraic programming for solving linear equations as shown in Figure4(a). The number of nodes is N=β2+β−2/2 according to matrix parameter β(2)
Montage Workflow: it is applied to construct astronomical image mosaic. An example of Montage Workflow is shown in Figure4(b)(3)
Molecular Dynamics Code: it is an algorithm to implement the atomic and the molecular physical motion. An example of the Molecular Dynamics Code is depicted in Figure4(c)Figure 4
Real-world DAGs.
(a)
Gaussian Elimination(b)
Montage Workflow(c)
Molecular Dynamics


### 5.2. Performance of Algorithm DILS

Figure5 shows the effect of changing the number of DAG-based jobs on the performance of the makespan of the three algorithms. The number of servers is set to 4, DAG-based jobs are randomly generated by the DAG generator, and the parameters CCR and α are both set to 1. It can be seen from Figure 5 that the makespan increases with the increase of DAG-based jobs. In short, among the three algorithms, DILS achieves the best performance, followed by algorithm HSIP and algorithm PEFT. When there are 10 DAG-based jobs, the algorithm DILS improves the performance of algorithm HSIP and PEFT by 4.5% and 7.9%, respectively.Figure 5
The makespan with the different numbers of DAG-based jobs.Figure6 shows the effect of the number of DAG-based jobs on the three algorithms on the average SLR. The number of servers is set to 8, DAG-based jobs are randomly generated by the generator, and the parameters CCR and α are both set to 1. The average SLR generated by the three algorithms decreases with the increase of the number of DAG-based jobs, because more idle time slots are utilized. Among the three algorithms, DILS can get the minimum average SLR, because DILS makes full use of the idle time slots. When the number of DAG-based jobs increases from 2 to 10, the performance of algorithm DILS compared with algorithm HSIP and PEFT is improved from 16.3% to 17.6% and from 17.9% to 25.0%, respectively.Figure 6
The average SLR with the different numbers of DAG-based jobs.In Figure7, we show the impact of the number of DAG-based jobs on the average SLR for Gaussian Elimination jobs. The number of processors is 4, the parameter CCR is set to 1, and α is set as 0.1. As the number of DAG-based jobs increases, the increase of average SLR is small. The difference between the three algorithms is obvious. However, our algorithm outperforms the other two algorithms.Figure 7
Average SLR with different numbers of DAG-based jobs for Gaussian Elimination.Figure8 illustrates the average SLR of the three algorithm changes with the increasing number of processors for Gaussian Elimination jobs. With the increase in the number of processors, the average SLR of our algorithm decreases significantly. Obviously, compared with other algorithms, our algorithm achieves better performance.Figure 8
Average SLR with different numbers of processors for Gaussian Elimination.


### 5.3. Impact of Parameters

Figure9 illustrates the average SLR performance versus different matrix size parameter β for the Gaussian Elimination jobs when the number of servers is 2. It can be observed that the average SLR of the three algorithms increases with the increase of β. The jobs with a larger β consist of more tasks and hence require more computation and transfer time for all the associated tasks. The performance improvement of algorithm DILS on algorithms HSIP and PEFT is up to 11.9% and 12.1%, respectively.Figure 9
The average SLR with different matrix parameterβ.Figure10 describes the average SLR for Montage Workflow. Parameter α varies in 0.1,0.5,1,2, when the parameter CCR=1 and the numbers of DAG-based jobs and servers are set as 5 and 4, respectively. The performance of algorithm DILS compared with algorithms HSIP and PEFT is improved from 18.4% to 22.9% and from 20.1% to 22.4%, respectively. For Figure 11, the parameter CCR increases from 0.2 to 10, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 8, respectively. The average SLR increases with the increase of the parameter CCR, since the communication between tasks consumes more time as parameter CCR increases. It can be seen that the algorithm DILS always achieves the best performance among the three algorithms.Figure 10
Average SLR with differentα for Montage Workflow.Figure 11
Average SLR with different CCR for Montage Workflow.Figure12 depicts the impact of parameter α on the average SLR for Molecular Dynamics Code. The parameter CCR is equal to 1, and the numbers of DAG-based jobs and servers are set to 5 and 4, respectively. It can be seen that the average SLR of the three algorithms increases with the increase of heterogeneous parameter α. Algorithm DILS always obtains the smallest results.Figure 12
Average SLR with differentα for Molecular Dynamics Code.Figure13 shows the impact of CCR on average SLR for Molecular Dynamics Code, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 8, respectively. The performance of algorithm DILS compared with HSIP and PEFT is improved from 9.4% to 24.5% and from 10.6% to 36.7%, respectively.Figure 13
Average SLR with different CCR for Molecular Dynamics Code.Figure14 describes the average SLR for Gaussian Elimination with different parameter α varying in 0.1,0.5,1,2, when the parameter CCR=1 and the numbers of DAG-based jobs and servers are set as 5 and 16, respectively. In general, algorithm DILS always achieves the best performance among the three algorithms, and algorithm HSIP performs better than algorithm PEFT. With the heterogeneous parameter α increasing from 0.1 to 2, the average SLR of algorithm DILS is improved from 50% to 57.3% and from 50.2% to 53% compared with HSIP and PEFT, respectively.Figure 14
Average SLR with differentα for Gaussian Elimination.Figure15 illustrates the average SLR for Gaussian Elimination with different parameter CCR increasing from 0.2 to 10, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 16, respectively. Compared with the other two algorithms, the average SLR performance of DILS increases from 51.3% to 71.5% and from 50.7% to 75%, respectively.Figure 15
Average SLR with different CCR for Gaussian Elimination.


## 5.1. Simulation Setup

In this paper, we will evaluate the performance of the three algorithms in terms of the scheduling length ratio (SLR). SLR is the ratio of the scheduling length to the minimum scheduling length by ignoring the communication time, which can be calculated by(11)SLR=∑Jk∈Jmakespan∑Jk∈J∑tik∈CPMINminps∈Pwtik,ps,where CPMIN is the minimum length of the critical path in the DAG-based job after ignoring the communication time between tasks, while the critical path of a DAG-based job is the longest path from the ingress task to the egress task.In the simulations, we use DAG-based jobs randomly generated by a DAG generator and real-world DAG-based jobs. The DAG generator uses the same parameters as in [25, 27]. The DAG topology parameters are as follows:
(1)
DAG average calculation timecDAG¯: indicating the average execution time of the tasks in the DAG, which is randomly set during the simulation(2)
Communication calculation ratioCCR: the ratio of the average communication time and the average execution time; the larger the value, the more communication-intensive the DAG-based job; the smaller the value, the more computation-intensive the DAG-based job(3)
Heterogeneous parameterα: representing the task execution time range on different processors; the larger the value, the more heterogeneous the processorsWe select three classic DAG-based jobs from the real-world applications in the simulations.(1)
Gaussian Elimination: it is used in linear algebraic programming for solving linear equations as shown in Figure4(a). The number of nodes is N=β2+β−2/2 according to matrix parameter β(2)
Montage Workflow: it is applied to construct astronomical image mosaic. An example of Montage Workflow is shown in Figure4(b)(3)
Molecular Dynamics Code: it is an algorithm to implement the atomic and the molecular physical motion. An example of the Molecular Dynamics Code is depicted in Figure4(c)Figure 4
Real-world DAGs.
(a)
Gaussian Elimination(b)
Montage Workflow(c)
Molecular Dynamics


## 5.2. Performance of Algorithm DILS

Figure5 shows the effect of changing the number of DAG-based jobs on the performance of the makespan of the three algorithms. The number of servers is set to 4, DAG-based jobs are randomly generated by the DAG generator, and the parameters CCR and α are both set to 1. It can be seen from Figure 5 that the makespan increases with the increase of DAG-based jobs. In short, among the three algorithms, DILS achieves the best performance, followed by algorithm HSIP and algorithm PEFT. When there are 10 DAG-based jobs, the algorithm DILS improves the performance of algorithm HSIP and PEFT by 4.5% and 7.9%, respectively.Figure 5
The makespan with the different numbers of DAG-based jobs.Figure6 shows the effect of the number of DAG-based jobs on the three algorithms on the average SLR. The number of servers is set to 8, DAG-based jobs are randomly generated by the generator, and the parameters CCR and α are both set to 1. The average SLR generated by the three algorithms decreases with the increase of the number of DAG-based jobs, because more idle time slots are utilized. Among the three algorithms, DILS can get the minimum average SLR, because DILS makes full use of the idle time slots. When the number of DAG-based jobs increases from 2 to 10, the performance of algorithm DILS compared with algorithm HSIP and PEFT is improved from 16.3% to 17.6% and from 17.9% to 25.0%, respectively.Figure 6
The average SLR with the different numbers of DAG-based jobs.In Figure7, we show the impact of the number of DAG-based jobs on the average SLR for Gaussian Elimination jobs. The number of processors is 4, the parameter CCR is set to 1, and α is set as 0.1. As the number of DAG-based jobs increases, the increase of average SLR is small. The difference between the three algorithms is obvious. However, our algorithm outperforms the other two algorithms.Figure 7
Average SLR with different numbers of DAG-based jobs for Gaussian Elimination.Figure8 illustrates the average SLR of the three algorithm changes with the increasing number of processors for Gaussian Elimination jobs. With the increase in the number of processors, the average SLR of our algorithm decreases significantly. Obviously, compared with other algorithms, our algorithm achieves better performance.Figure 8
Average SLR with different numbers of processors for Gaussian Elimination.


## 5.3. Impact of Parameters

Figure9 illustrates the average SLR performance versus different matrix size parameter β for the Gaussian Elimination jobs when the number of servers is 2. It can be observed that the average SLR of the three algorithms increases with the increase of β. The jobs with a larger β consist of more tasks and hence require more computation and transfer time for all the associated tasks. The performance improvement of algorithm DILS on algorithms HSIP and PEFT is up to 11.9% and 12.1%, respectively.Figure 9
The average SLR with different matrix parameterβ.Figure10 describes the average SLR for Montage Workflow. Parameter α varies in 0.1,0.5,1,2, when the parameter CCR=1 and the numbers of DAG-based jobs and servers are set as 5 and 4, respectively. The performance of algorithm DILS compared with algorithms HSIP and PEFT is improved from 18.4% to 22.9% and from 20.1% to 22.4%, respectively. For Figure 11, the parameter CCR increases from 0.2 to 10, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 8, respectively. The average SLR increases with the increase of the parameter CCR, since the communication between tasks consumes more time as parameter CCR increases. It can be seen that the algorithm DILS always achieves the best performance among the three algorithms.Figure 10
Average SLR with differentα for Montage Workflow.Figure 11
Average SLR with different CCR for Montage Workflow.Figure12 depicts the impact of parameter α on the average SLR for Molecular Dynamics Code. The parameter CCR is equal to 1, and the numbers of DAG-based jobs and servers are set to 5 and 4, respectively. It can be seen that the average SLR of the three algorithms increases with the increase of heterogeneous parameter α. Algorithm DILS always obtains the smallest results.Figure 12
Average SLR with differentα for Molecular Dynamics Code.Figure13 shows the impact of CCR on average SLR for Molecular Dynamics Code, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 8, respectively. The performance of algorithm DILS compared with HSIP and PEFT is improved from 9.4% to 24.5% and from 10.6% to 36.7%, respectively.Figure 13
Average SLR with different CCR for Molecular Dynamics Code.Figure14 describes the average SLR for Gaussian Elimination with different parameter α varying in 0.1,0.5,1,2, when the parameter CCR=1 and the numbers of DAG-based jobs and servers are set as 5 and 16, respectively. In general, algorithm DILS always achieves the best performance among the three algorithms, and algorithm HSIP performs better than algorithm PEFT. With the heterogeneous parameter α increasing from 0.1 to 2, the average SLR of algorithm DILS is improved from 50% to 57.3% and from 50.2% to 53% compared with HSIP and PEFT, respectively.Figure 14
Average SLR with differentα for Gaussian Elimination.Figure15 illustrates the average SLR for Gaussian Elimination with different parameter CCR increasing from 0.2 to 10, when α=1 and the numbers of DAG-based jobs and servers are set to 5 and 16, respectively. Compared with the other two algorithms, the average SLR performance of DILS increases from 51.3% to 71.5% and from 50.7% to 75%, respectively.Figure 15
Average SLR with different CCR for Gaussian Elimination.


## 6. Conclusion

Careful multijob task scheduling is the key to achieve efficient job processing. This paper studied the problem of associated task scheduling of multiple jobs with the aim of minimizing jobs’ makespan. We propose a task Duplication and Insertion algorithm based on List Scheduling (DILS). The algorithm combines dynamic prediction of task completion time, task replication, and task insertion. For multiple jobs, the expected completion time of their associated tasks is calculated to determine which task is scheduled and which processor to run the task. Some tasks are copied to different processors to reduce the transmission delay. There are many jobs to be processed, and hence, there may be idle time slots on the processor. Therefore, the tasks that meet the insertion conditions can be inserted into the idle time slots to speed up the execution of the jobs. Simulation results demonstrated that algorithm DILS achieved good performance.



---

*Source: 6631752-2021-04-28.xml*