Introduction
-
A novel resource allocation and scheduling technique, RM-DCWF, for handling an open stream of multi-stage jobs with SLAs. Two task scheduling policies are devised.
-
Two algorithms devised to decompose the end-to-end deadline of a multi-stage job to assign each task of the job a sub-deadline.
-
Insights gained into system behavior and performance from a rigorous simulation-based performance evaluation of RM-DCWF using a variety of system and workload parameters. The synthetic workloads used in the experiments are based on real scientific workflows described in the literature.
-
A comparison of the performance of the proposed technique with that of a conventional first-in-first-out (FIFO) scheduler as well as a technique from the literature [29] that has objectives similar to RM-DCWF is presented.
Related work
Resource management on distributed systems for processing workflows
Resource management techniques on distributed systems for processing MapReduce jobs
Comparison with related work
Problem description and resource management model
Deadline budgeting algorithm for workflows
setOpt
argument. The first approach (setOpt = 1
) is to calculate the execution time of job j when it executes at its maximum degree of parallelism on the set of resources R with m resources, while not considering any contention for resources (denoted SET
j
R
). Recall from the previous section, the definition of R, which is a set of resources that models the distributed system job j will execute on. The approach used by the algorithm for matchmaking and scheduling the tasks of job j onto the m resources and computing SET
j
R
is briefly described. The tasks of job j are allocated in non-increasing order of their execution times: the ready task with the highest required task execution time is allocated first; the task with the next highest execution time is considered next and so on. Tasks are considered ready when all of their parent tasks, as captured in the precedence graph that characterizes the workflow, have completed executing. A best-fit technique is used for allocating the tasks of the job to the resources. Each task of the job is allocated on that resource that can execute the task at its earliest possible time. Thus, the algorithm attempts to complete each task and the job at its earliest possible finish time. The second approach (setOpt = 2
) is to calculate the execution time of the job when it executes on R, while considering the current processing load of the resources (i.e., considering the other jobs already executing or scheduled on R) (denoted SET
j
R_PL
). This is accomplished by scheduling the job on the system’s resources to retrieve its expected completion time and then removing the job from the system. Next, the algorithm calculates the laxity of the job (L
j
) using Eq. 1 (line 2). Note that when L
j
is calculated using SET
j
equal to SET
j
R
, the laxity of the job is referred to as the sample laxity (SL) because the job execution time is calculated on R without considering the current processing load of the resources in R. When L
j
is calculated using SET
j
equal to SET
j
R_PL
, the laxity of the job is referred to as the true laxity (TL) because the job execution time is calculated on R while considering the current processing load of the resources in R. The final steps of the algorithm are to distribute the laxity of the job to each of its constituent tasks and to calculate a sub-deadline for each of the tasks (line 3) by invoking one of two algorithms devised: (1) the Proportional Distribution of Job Laxity (PD) Algorithm, which is described in Section "Proportional Distribution of Job Laxity Algorithm", and (2) the Even Distribution of Job Laxity (ED) Algorithm, which is discussed in Section "Even Distribution of Job Laxity Algorithm". The algorithm that is used depends on the supplied laxDistOpt input argument.
Proportional distribution of job laxity algorithm
setOpt
, to indicate how SET
j
is calculated. Recall from the discussion earlier that SET
j
can be calculated in one of two ways: setOpt = 1
corresponds to SET
j
R
and setOpt = 2
corresponds to SET
j
R_PL
. A walkthrough of the algorithm is provided next.Even distribution of job laxity algorithm
cumulativeLaxities
is used to store the cumulative laxity for each execution phase, where the key is the execution phase and the value is the cumulative laxity. The last phase of the algorithm (lines 9–17) uses the cumulative laxity values to calculate and assign a sub-deadline for each of job j’s tasks. The following operations are performed on each task t of job j. First, the execution phase of the task t is retrieved as shown in line 10. The cumulative laxity of the task is then retrieved from the cumulativeLaxities map using the value of the execution phase as the key (line 11). Next, the sub-deadline of the task is calculated using Eq. 2 and assigned to the task (lines 12–13). Similar to the PD algorithm, the ED algorithm invokes setParentTasksSubDeadlines()
if the task t has more than 1 parent task. After all the tasks of job j are processed the algorithm ends.RM-DCWF’s matchmaking and scheduling algorithm
Job mapping algorithm
mapJob()
presented in Algorithm 4 and (2) mapJobHelper()
described in Algorithm 5. Note that the variables shown in the algorithms that are underlined indicate that the variables are fields belonging to RM-DCWF instead of being local variables. A walkthrough of mapJob()
is provided first, followed by a description of mapJobHelper()
. The input required by mapJob() comprises the following: a job to map j, an integer setOpt
, an integer laxDistOpt
, and an integer tsp. Note that except for the argument tsp, which specifies the task scheduling policy, these are the same input arguments used by the DBW algorithm. The method returns true if the job j is scheduled to meet its deadline; otherwise, false is returned.mapJob()
is to invoke the DBW algorithm to decompose the end-to-end deadline of the job j and assign each of job j’s tasks a sub-deadline (line 1). Next, RM-DCWF’s rootJob
field is set to j (line 2). The rootJob
field stores the current job that is being mapped by RM-DCWF. The third step is to clear RM-DCWF’s prevRemapAttempts
list (line 3), which stores the various sets of jobs that a job remapping attempt has previously processed. RM-DCWF’s jobComparator
field, which specifies how jobs that need to be remapped are sorted, is then set to the Job Deadline Comparator (line 4) to sort jobs by non-decreasing order of their respective deadlines. A more detailed discussion of the purpose of these fields, which are used by the Job Remapping algorithm, is provided in the next section. In line 5, RM-DCWF’s taskSchedulingPolicy
field, which specifies how tasks are scheduled, is initialized. Two task scheduling policies are devised. TSP1 schedules tasks to execute at their earliest possible times, and TSP2 schedules tasks to execute at their latest possible times such that the tasks meet their respective sub-deadlines. The last step is to invoke Algorithm 5: mapJobHelper()
(line 6).
mapJobHelper()
, which performs the allocation and scheduling of job j onto the set of resources in the system, is provided next. The input required by mapJobHelper()
includes the following: a job j to map, a Boolean isRootJob
, which is set to true if this is the first time job j is being mapped; otherwise, it is set to false, and a Boolean checkDeadline
, which is set to true if the method should try to map job j to meet its deadline; otherwise, it is set to false and the method has to map job j on the system, but it does not have to schedule job j to meet its deadline. The mapJobHelper()
method starts by initializing the local variable isJobMapped
to true (line 1). Next, all of job j’s tasks that need to be mapped are sorted in non-increasing order of their respective execution times (line 2), where ties are broken in favour of the task with the earlier sub-deadline. If the tasks also have the same sub-deadline, the task with the smaller task id (a unique value) is placed ahead of the task with the larger id. The method then attempts to map each of job j’s tasks (lines 3–4) by performing the following operations for each task t in job j. First, the startTime variable is initialized by invoking the task t’s getEarliestStartTime()
method (line 5), which returns the time that task t can start to execute while considering any precedence relationships that t has. If getEarliestStartTime()
returns −1, it means that an earliest start time for task t cannot be determined as yet because not all of task t’s parent tasks have been scheduled. In this case, mapJobHelper()
stops processing task t for the moment and attempts to map the next task in job j (line 6). On the other hand, if startTime is not −1, the processing of task t continues. If RM-DCWF’s taskSchedulingPolicy
field is set to TSP2 (line 7), the expected start time of the task is updated and set as shown in line 8. The expected completion time of the task is then calculated using the expected start time of the task (line 9).mappedTasks
list (line 12), which stores all the tasks that have been successfully mapped for job j. On the other hand, if task t has an execution time greater than 0 (line 13), the method attempts to find a resource r in R that can execute t at its expected start time. If t cannot be scheduled to execute at its expected start time, the task is scheduled at the next best time depending on the value of the taskSchedulingPolicy
field (line 14). If taskSchedulingPolicy
is set to TSP1, the method schedules task t at its next earliest possible time. On the other hand, if taskSchedulingPolicy
is set to TSP2, the method schedules the task at its next latest possible time, while ensuring the task’s sub-deadline is satisfied.checkDeadline
is set to true (line 15), mapJobHelper()
attempts to remap job j and a set of jobs that may have caused j to miss its deadline by performing the following operations (lines 16–18). First, the removePartiallyMappedJob()
method is invoked to remove each of the tasks stored in the mappedTasks
list from the system (line 16). Algorithm 7: remapJob()
(described in more detail in the next section) is then invoked and the return value is saved in a variable called isJobMapped
(line 17). The next step (line 18) is then to go to line 27 to check the value of isJobMapped. If isJobMapped
is set to true, meaning the job has been successfully scheduled to meet its deadline, the mappedTasks
list is cleared, job j is added to RM-DCWF’s mappedJobs
list (line 28), and true is returned (line 29). Otherwise, isJobMapped is set to false, meaning job j cannot be scheduled to meet its deadline (line 30). This leads to mapJobHelper()
being re-invoked, but this time with the checkDeadline
argument set to false, which will map job j even if it misses its deadline (line 31). False is then returned (line 32) to indicate job j will not meet its deadline.
checkDeadline
is false), it means that task t can be scheduled to execute on resource r (line 20) and t is then added to the mappedTasks
list (line 21). The next task of job j is then processed by repeating lines 3–26. This sequence of operations continues until all of job j’s tasks are mapped on the system. After all of job j’s tasks have been mapped, lines 27–29 are executed (as described earlier), and then the method returns.Job remapping algorithm
remapJob()
presented in Algorithm 6 and (2) remapJobHelper()
outlined in Algorithm 7. A discussion of remapJob()
is provided first, followed by a discussion on remapJobHelper()
. The input arguments required by remapJob()
include a job j to remap and a Boolean isRootJob
. The isRootJob
argument is set to true if it is the first invocation of remapJob()
for attempting to remap job j in this iteration; otherwise, isRootJob
is set to false. If job j and the set of jobs that may have prevented job j from meeting its deadline are remapped and scheduled to meet their deadlines, the method returns true; otherwise, false is returned.
remapJob()
is to set RM-DCWF’s taskSchedulingPolicy
field to TSP1 so the tasks that are remapped are scheduled to execute at their earliest possible times (line 1). The second step is to invoke Algorithm 7: remapJobHelper()
(line 2). Recall from line 4 of Algorithm 4 ((mapJob()
) that the jobComparator
field, which specifies how the jobs that need to be remapped are sorted, is initially set to the Job Deadline Comparator. The Job Deadline Comparator sorts jobs in non-decreasing order of their respective deadlines with ties broken in favour of the job with the smaller laxity (i.e., tighter deadline). If remapJobHelper()
returns true, remapJob()
also returns true (line 3). On the other hand, if remapJobHelper()
returns false, remapJob()
continues by checking the supplied isRootJob
argument (line 4). If isRootJob
is false (line 5), meaning that this invocation of remapJob()
is not for the original attempt for mapping job j, the method returns false to stop this particular remapping attempt from continuing (line 5). Otherwise, the method continues and RM-DCWF’s jobComparator
field is changed to the Job Laxity Comparator (line 6) and remapJobHelper()
is invoked again to check if remapping the jobs in a different order can generate a schedule in which all the jobs to remap can meet their deadlines (line 7).remapJobHelper()
(shown in Algorithm 7) is provided next. The input arguments and output value returned by remapJobHelper()
are the same as those described for remapJob()
. The first step of the method is to retrieve a subset of the jobs already scheduled on the system that may have caused job j to miss its deadline and store these jobs in the jobsToRemap
list (line 1). This includes all the jobs in RM-DCWF’s mappedJobs
list that execute within the interval [s
j
, d
j
]. Next, the supplied job j is added to the jobsToRemap
list (line 2) and then the jobsToRemap
list is sorted using RM-DCWF’s jobComparator
(line 3). Since it is possible to have multiple (nested) invocations of remapJobHelper()
, lines 4–6 determine when an invocation of remapJobHelper()
(referred to as a remapping attempt) should be rejected. More specifically, before a remapping attempt is started, the method checks if RM-DCWF’s prevRemapAttempts
list, which stores the various sets of jobs that previous invocations of remapJobHelper()
have processed, contains the same jobs (in the same order) as the jobsToRemap
list (line 4). If this is true, the method returns false to stop the remapping attempt (line 5). On the other hand, if the remapping attempt is allowed to continue, the jobsToRemap
list is added to RM-DCWF’s prevRemapAttempts
list (line 7). Next, the method checks if the supplied argument isRootJob
is true (line 8), and if so, the current state of the system is saved to a set of variables (line 9). This involves saving the scheduled tasks of each resource in the system and making a copy of RM-DCWF’s mappedJobs
list. Furthermore, the scheduled start time and assigned resource for each task currently mapped on the system is saved. The reason for saving this information is because it may be changed during the job remapping attempt, and if the remapping attempt is not successful, the original state of the system has to be restored.jobsToRemap
from the system (line 11), which involves removing the jobs from RM-DCWF’s mappedJobs
list and removing each task of each job from its assigned resource’s scheduledTasks
list. This needs to be done so that the jobs in
jobsToRemap
can be remapped on the system. All the jobs in jobsToRemap
that have already missed their deadlines are then moved to a new list called lateJobs
(line 12) so that the jobs that have not missed their deadlines can be remapped first. The jobs in jobsToRemap
(line 13) are then remapped in the specific order as determined by the jobComparator
(recall line 3). This is accomplished by invoking Algorithm 5: mapJobHelper()
as shown in line 14. If mapJobHelper() returns true, the method maps the next job in jobsToRemap
. If at any point mapJobHelper()
returns false (line 14), it means that one of the jobs in jobsToRemap
cannot be scheduled to meet its deadline and the job remapping attempt has failed. The method then checks if isRootJob
is true (line 15), and if so, the state of the system that is saved in line 9 is restored (line 16). False is then returned to indicate that the remapping attempt has failed (line 18). On the other hand, if all the jobs in jobsToRemap
are successfully remapped to meet their deadlines, the next step is to perform mapping for the jobs in lateJobs
(i.e., the jobs that have missed their deadlines). This is accomplished by invoking mapJobHelper()
(Algorithm 5) with the checkDeadline
input argument set to false for each of the jobs in lateJobs
(line 21). Lastly, a value of true is returned by the method to indicate the remapping attempt is successful (line 22).
Time complexity analysis of the RM-DCWF matchmaking and scheduling algorithm
jobsToRemap
list. Such a modification will limit the number of jobs that can be added to the list, thus limiting the number of jobs that can be rescheduled at a given point in time.Performance evaluation of RM-DCWF
Experimental setup
-
Proportion of Late Jobs (P) = N/n where N is the number of late jobs in a simulation run and n is the total number of jobs processed during the simulation.
-
Average Job Turnaround Time (T). The turnaround time of a job j (tat j ) is CT j –s j where CT j is job j’s completion time and s j is j’s earliest start time, respectively. Thus, T= ∑ j ∈ J (tat j )/n.
-
Average Job Matchmaking and Scheduling Time (O) is the average processing time required by RM-DCWF to partition a job’s deadline among its tasks and matchmake and schedule a job. O = ∑ j ∈ J (o j )/n where o j is the processing time required for mapping job j on the system.
System and workload parameters for the factor-at-a-time experiments
Parameter | Values | Default Value |
---|---|---|
Workload
| ||
Type | {CyberShake, LIGO, Genome} | – |
Job arrival rate (job/s) | λCS = {1/18, 1/22, 1/30} λLG = {1/150, 1/180, 1/265} λGN = {1/1800, 1/2290, 1/3205} | λCS = 1/22 λLG = 1/180 λGN = 1/2290 |
Earliest start time of jobs, s
j
(sec) |
\( {s}_j=\left\{\begin{array}{c}{at}_j,\kern7.75em x=0\\ {}{at}_j+ DU\left(1,{s}_{max}\right)\kern0.75em x=1\end{array}\right. \)
where at
j
is the arrival time of job j, x ~ Bernoulli(0.5), and s
max
= {1, 5, 25} * 104
|
s
max
= 50,000 |
Job Deadline, d
j
(sec) |
\( {d}_j=\left\lceil {s}_j+{SET_j^R}^{\ast } em\right\rceil \) where
em ~ U(1, em
max
) and em
max
= {2, 5, 10} |
em
max
= 5 |
System
| ||
Number of Resources, m
|
m = {40, 50,60} |
m = 50 |
Resource Capacity |
c
r
= 2 | – |
Configuration of RM-DCWF
| ||
Laxity Distribution Algorithm | {PD, ED} |
–
|
Approach to calculate the job laxity | {SL, TL} | – |
Task Scheduling Policy | {TSP1, TSP2} | – |
Results of the factor-at-a-time experiments
-
PD-SL-TSP1 vs ED-SL-TSP2 for the CyberShake workload
-
PD-SL-TSP1 vs ED-SL-TSP1 for the LIGO workload
-
PD-SL-TSP1 vs ED-SL-TSP1 for the Genome workload
Effect of job arrival rate
λLG (jobs/s) | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
1/265 | 0.02 | 0.02 | 1346 | 1346 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±0.6 | ±0.6 | ±0.00 | ±0.00 | |
1/180 | 0.11 | 0.11 | 1466 | 1466 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±4.6 | ±4.6 | ±0.00 | ±0.00 | |
1/150 | 1.03 | 1.06 | 2005 | 2006 | 0.017 | 0.016 |
±0.12 | ±0.12 | ±29 | ±28 | ±0.001 | ±0.001 |
λGN (jobs/s) | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
1/3205 | 0.01 | 0.01 | 17,544 | 17,544 | 0.008 | 0.008 |
±0.00 | ±0.00 | ±927 | ±927 | ±0.000 | ±0.000 | |
1/2290 | 0.07 | 0.07 | 17,963 | 17,963 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±1007 | ±1007 | ±0.000 | ±0.000 | |
1/1800 | 1.43 | 1.40 | 52,312 | 52,472 | 0.048 | 0.051 |
±0.45 | ±0.44 | ±12,915 | ±13,003 | ±0.015 | ±0.016 |
Effect of earliest start time of jobs
smax (sec) | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
10,000 | 0.10 | 0.10 | 1450 | 1450 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±3.3 | ±3.3 | ±0.000 | ±0.000 | |
50,000 | 0.11 | 0.11 | 1466 | 1466 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±4.6 | ±4.6 | ±0.000 | ±0.000 | |
250,000 | 0.09 | 0.08 | 1441 | 1427 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±4.7 | ±4.1 | ±0.000 | ±0.000 |
smax (sec) | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
10,000 | 0.04 | 0.04 | 17,693 | 17,693 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±959 | ±959 | ±0.000 | ±0.000 | |
50,000 | 0.07 | 0.07 | 17,963 | 17,963 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±1007 | ±1007 | ±0.000 | ±0.000 | |
250,000 | 0.08 | 0.08 | 18,171 | 18,171 | 0.008 | 0.008 |
±0.01 | ±0.02 | ±1049 | ±1049 | ±0.000 | ±0.000 |
Effect of job deadlines
emmax
| P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-S-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
2 | 2.44 | 2.43 | 1458 | 1457 | 0.012 | 0.011 |
±0.14 | ±0.14 | ±4.4 | ±4.4 | ±0.000 | ±0.000 | |
5 | 0.11 | 0.11 | 1466 | 1466 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±4.6 | ±4.6 | ±0.000 | ±0.000 | |
10 | 0.04 | 0.04 | 1458 | 1463 | 0.009 | 0.008 |
±0.01 | ±0.01 | ±6.2 | ±4.6 | ±0.000 | ±0.000 |
emmax
| P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
2 | 0.49 | 0.49 | 17,933 | 17,933 | 0.009 | 0.009 |
±0.12 | ±0.12 | ±1001 | ±1001 | ±0.000 | ±0.000 | |
5 | 0.07 | 0.07 | 17,963 | 17,963 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±1007 | ±1007 | ±0.000 | ±0.000 | |
10 | 0.03 | 0.03 | 17,963 | 17,963 | 0.007 | 0.007 |
±0.01 | ±0.01 | ±1007 | ±1007 | ±0.000 | ±0.000 |
Effect of the number of resources
m | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
40 | 4.11 | 4.14 | 3210 | 3218 | 0.034 | 0.032 |
±0.27 | ±0.27 | ±125 | ±126 | ±0.003 | ±0.003 | |
50 | 0.11 | 0.11 | 1466 | 1466 | 0.009 | 0.009 |
±0.01 | ±0.01 | ±4.6 | ±4.6 | ±0.000 | ±0.000 | |
60 | 0.03 | 0.03 | 1360 | 1360 | 0.010 | 0.010 |
±0.01 | ±0.01 | ±1.1 | ±1.1 | ±0.000 | ±0.000 |
m | P (%) | T (sec) | O (sec) | |||
---|---|---|---|---|---|---|
PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | PD-SL-TSP1 | ED-SL-TSP1 | |
40 | 1.29 | 1.30 | 52,320 | 52,106 | 0.032 | 0.035 |
±0.40 | ±0.42 | ±13,743 | ±13,597 | ±0.011 | ±0.012 | |
50 | 0.07 | 0.07 | 17,963 | 17,963 | 0.008 | 0.008 |
±0.01 | ±0.01 | ±1007 | ±1007 | ±0.000 | ±0.000 | |
60 | 0.02 | 0.02 | 17,583 | 17,583 | 0.009 | 0.009 |
±0.00 | ±0.00 | ±935 | ±935 | ±0.000 | ±0.000 |
Investigation of using a small number of resources
Comparison with a first-in-first-out (FIFO) scheduler
Comparison with MCRP-RM
λ (jobs/s) | T (sec) | O (sec) | ||
---|---|---|---|---|
RM-DCWF | MRCP-RM | RM-DCWF | MRCP-RM | |
0.001 | 383 ± 2 | 383 ± 2 | 0.010 ± 0 | 0.018 ± 0 |
0.01 | 395 ± 2 | 394 ± 2 | 0.010 ± 0 | 0.043 ± 0 |
0.015 | 413 ± 2 | 417 ± 2 | 0.010 ± 0 | 0.074 ± 0 |
0.175 | 429 ± 2 | 435 ± 2.5 | 0.012 ± 0 | 0.10 ± 0 |
0.1875 | 444 ± 3 | 450 ± 3 | 0.013 ± 0 | 0.12 ± 0 |
0.02 | 465 ± 4 | 471 ± 3 | 0.012 ± 0 | 0.18 ± 0.01 |
0.02125 | 502 ± 6 | 508 ± 6 | 0.016 ± 0 | 0.25 ± 0.02 |
0.0225 | 564 ± 12 | 566 ± 10 | 0.019 ± 0 | 0.43 ± 0.04 |
0.025 | 1332 ± 76 | 1788 ± 118 | 0.110 ± 0 | 2.9 ± 0.48 |
Conclusions and future work
-
Effect of system and workload parameters: An increase in the job arrival rate, λ, or a decrease in the earliest start time of jobs, s j , or a decrease in the deadline of jobs, d j , or a decrease in the number of resources, m, tends to lead to an increase in the proportion of late jobs, P, due to the increased contention for resources.
-
RM-DCWF configuration using the Proportional Distribution of Job Laxity Algorithm (PD): Overall, it is observed that using Task Scheduling Policy 1 (TSP1) generates lower or similar values for the proportion of late jobs, P, average job turnaround time, T, and average job matchmaking and scheduling time, O, than those achieved with Task Scheduling Policy 2 (TSP2). Furthermore, the two approaches used to calculate the laxity of the job (Sample Laxity, SL and True Laxity, TL) achieve similar performance with the SL approach achieving a slightly smaller P in most cases. When using PD, the results of the experiments showed that the highest performing RM-DCWF configuration (in terms of P) for all three workloads experimented with is PD-SL-TSP1.
-
RM-DCWF configuration using the Even Distribution of Job Laxity Algorithm (ED): The results demonstrate that for the CyberShake workload using ED-SL-TSP2 achieves the lowest P in most cases. However, when using the LIGO and Genome workloads, the best performance in terms of P is achieved by ED-SL-TSP1. When using ED, the results of the experiments showed that the two approaches used to calculate the laxity of the jobs (SL and TL) achieve comparable performance.
-
PD-based configuration vs ED-based configuration: For the CyberShake workload, it is observed that overall ED-SL-TSP2 outperforms PD-SL-TSP1 in terms of P but it has a slightly higher T because TSP2 schedules tasks to execute at their latest possible times while meeting their respective sub-deadlines. In the case of the LIGO and Genome workloads, both PD-SL-TSP1 and ED-SL-TSP1 achieve similar values of P, T, and O. This can be attributed to TSP1 scheduling tasks to execute at their earliest possible times, regardless of their sub-deadlines.
-
Effectiveness of RM-DCWF: For the system and workload parameters experimented with in Section "Results of the Factor-at-a-Time Experiments", it is observed that RM-DCWF can achieve low values of P (on average 0.62%). Even when the contention for resources is high and jobs are more susceptible to miss their deadlines (e.g., when λ is high, or d j is small, or m is small), P is less than 5% and on average 2.2% for all the experiments conducted.
-
Efficiency of RM-DCWF: Over all the experiments described in Section "Results of the Factor-at-a-Time Experiments", RM-DCWF achieved low values of O (less than 0.05 s and on average 0.02 s). Furthermore, O/T, an indication of the matchmaking and scheduling overhead, is also very small (less than 0.01%) for all the experiments conducted.
-
Effect of using a small number of resources: When executing the CyberShake workload on a system with m = 20, which prevented some jobs from executing at their maximum degree of parallelism, it was observed that PD-SL-TSP1 outperforms ED-SL-TSP2 in terms of P. When there are a limited number of resources, better performance can be achieved if the system schedules jobs to complete executing as soon as possible to lower the contention for resources when other jobs arrive later on the system.
-
Comparison with the FIFO Scheduler: The results of experiments comparing RM-DCWF with a FIFO Scheduler demonstrated that RM-DCWF achieves a significantly lower P and a lower O compared to the FIFO Scheduler. However, as expected the FIFO Scheduler did achieve a lower T because it prioritizes executing jobs that have earlier arrival times and schedules each job to execute at its earliest possible time.
-
MapReduce Workload and Comparison with MRCP-RM: A summary of observations resulting from the performance evaluation to compare RM-DCWF and MRCP-RM when using a MapReduce workload is provided. At low-to-moderate contention for resources (e.g., λ ≤ 0.0175 jobs per sec), RM-DCWF and MRCP-RM achieve comparable performance in terms of P. When the contention for resources is moderately high (e.g., average resource utilization is approximately 0.8), for a λ of 0.02 jobs per sec, for example, MRCP-RM outperforms RM-DCWF. At very high contention for resources (e.g., λ ≥ 0.025 jobs per sec), RM-DCWF outperforms MRCP-RM. For all the values of λ experimented with, RM-DCWF achieves on average an O that is 85% lower compared to that achieved by MRCP-RM.
-
These observations indicate that MRCP-RM’s constraint programming-based resource management algorithm led to its superior performance over the heuristic-based RM-DCWF at medium system load, but because of its lower overhead RM-DCWF demonstrated higher scalability and superior performance at higher system loads.