Introduction
Related work
Input data
Cybershake scientific workflow
Tasks | Size of tasks | Time |
---|---|---|
Task 3 | 62,69,51,663 | 39.06 |
Task 5 | 69,47,76,323 | 38.49 |
Task 7 | 58,57,63,637 | 36.27 |
Task 9 | 53,68,97,326 | 32.29 |
Task 11 | 67,05,35,542 | 62.25 |
Task 14 | 40,67,28,38,798 | 96.91 |
Task 16 | 45,23,96,996 | 45.60 |
Task 18 | 50,27,64,231 | 28.67 |
Task 20 | 62,41,88,532 | 24.56 |
Task 22 | 42,65,77,006 | 31.05 |
Task 24 | 51,58,32,878 | 54.87 |
Task 26 | 68,14,99,417 | 23.99 |
Task 28 | 44,14,51,516 | 26.46 |
Epigenomics scientific workflow
Proposed system
Proposed methodology
Analytic hierarchy process
Numerical rating | Judgment preference |
---|---|
9 | Extremely preferred |
8 | Very strongly to extremely preferred |
7 | Very strongly preferred to preferred |
6 | Strongly to very strongly |
5 | Strongly preferred |
4 | Moderately to strongly preferred |
3 | Moderately preferred |
2 | Equally to moderately preferred |
1 | Equally preferred |
Task | Task 3 | Task 5 | Task 7 | Task 9 | Task 11 | Task 14 | Task 16 | Task 18 |
---|---|---|---|---|---|---|---|---|
Task 3 | 1 | 2 | 3 | 4 | 1/7 | 1/6 | 1/9 | 6 |
Task 5 | 1/2 | 1 | 3 | 4 | 1/5 | 1/6 | 1/3 | 6 |
Task 7 | 1/3 | 1/2 | 1 | 4 | 1/6 | 1/7 | 1/4 | 6 |
Task 9 | 1/4 | 1/7 | 1/2 | 1 | 1/7 | 1/8 | 1/5 | 6 |
Task 11 | 2 | 2 | 2 | 4 | 1 | 1/2 | 3 | 6 |
Task 14 | 3 | 3 | 3 | 4 | 2 | 1 | 2 | 6 |
Task 16 | 2 | 2 | 3 | 4 | 1/3 | 1/4 | 1 | 6 |
Task 18 | 1/5 | 1/5 | 1/4 | 1/3 | 1/8 | 1/9 | 1/6 | 1 |
Task 20 | 1/4 | 1/4 | 1/4 | 1/3 | 1/7 | 1/8 | 1/5 | 1/2 |
Task 22 | 1/4 | 1/4 | 1/3 | 1/2 | 1/7 | 1/8 | 1/5 | 6 |
Task 24 | 3 | 3 | 3 | 4 | 1/2 | 1/3 | 2 | 6 |
Task 26 | 1/5 | 1/5 | 1/5 | 1/4 | 1/8 | 1/9 | 1/6 | 1/3 |
Task 28 | 1/5 | 1/5 | 1/4 | 1/3 | 1/8 | 1/9 | 1/6 | 1/2 |
Sum | 791/60 | 46/3 | 1195/60 | 365/12 | 601/112 | 183/56 | 3229/360 | 338/6 |
Task | Task 20 | Task 22 | Task 24 | Task 26 | Task 28 |
---|---|---|---|---|---|
Task 3 | 8 | 5 | 1/8 | 9 | 7 |
Task 5 | 8 | 5 | 1/4 | 9 | 7 |
Task 7 | 8 | 5 | 1/5 | 9 | 7 |
Task 9 | 8 | 5 | 1/6 | 9 | 7 |
Task 11 | 8 | 5 | 3 | 9 | 7 |
Task 14 | 8 | 5 | 2 | 9 | 7 |
Task 16 | 8 | 5 | 1/2 | 9 | 7 |
Task 18 | 8 | 1/2 | 1/7 | 9 | 7 |
Task 20 | 1 | 1/3 | 1/6 | 9 | 1/2 |
Task 22 | 8 | 1 | 1/6 | 9 | 7 |
Task 24 | 8 | 5 | 1 | 9 | 7 |
Task 26 | 1/2 | 1/4 | 1/7 | 1 | 1/3 |
Task 28 | 8 | 1/3 | 1/7 | 9 | 1 |
Sum | 179/2 | 509/121 | 2161/280 | 109 | 431/6 |
Tasks | 3 | 5 | 7 | 9 | 11 | 14 | 16 | 18 |
---|---|---|---|---|---|---|---|---|
3 | 60/791 | 6/46 | 35/239 | 48/365 | 16/601 | 28/549 | 40/3229 | 9/84 |
5 | 30/791 | 3/46 | 35/239 | 48/365 | 112/300 | 28/549 | 120/3229 | 9/84 |
7 | 20/791 | 3/92 | 60/119 | 48/365 | 56/1803 | 8/183 | 90/3229 | 9/84 |
9 | 15/791 | 1/46 | 6/239 | 12/365 | 16/601 | 7/183 | 70/3229 | 9/84 |
11 | 120/791 | 6/46 | 24/239 | 48/365 | 112/601 | 28/183 | 1080/3229 | 9/84 |
14 | 180/791 | 9/46 | 35/239 | 48/365 | 224/601 | 56/183 | 720/3229 | 9/84 |
16 | 120/791 | 6/46 | 35/239 | 49/365 | 112/1803 | 14/183 | 360/3229 | 9/84 |
18 | 12/791 | 3/230 | 3/239 | 4/365 | 14/601 | 56/1647 | 60/3229 | 6/338 |
20 | 15/791 | 3/184 | 3/239 | 4/365 | 16/601 | 7/183 | 72/3229 | 3/338 |
22 | 15/791 | 3/184 | 4/239 | 6/365 | 16/601 | 7/183 | 72/3229 | 9/84 |
24 | 180/791 | 9/46 | 35/239 | 48/365 | 56/601 | 56/549 | 720/3229 | 9/84 |
26 | 12/791 | 3/230 | 12/119 | 3/365 | 14/601 | 56/1647 | 60/3229 | 1/168 |
28 | 12/791 | 3/230 | 3/239 | 4/365 | 14/601 | 56/1647 | 60/3229 | 3/338 |
Sum | 1 | 0.96 | 0.9723 | 1 | 1.0576 | 0.9817 | 1.09 | 1.005 |
Tasks | 20 | 22 | 24 | 26 | 28 |
---|---|---|---|---|---|
3 | 16/179 | 60/509 | 35/2161 | 9/109 | 42/431 |
5 | 16/179 | 60/509 | 70/2161 | 9/109 | 42/431 |
7 | 16/179 | 60/509 | 65/2161 | 9/109 | 42/431 |
9 | 16/179 | 60/509 | 140/6483 | 9/109 | 42/431 |
11 | 16/179 | 60/509 | 840/2161 | 9/109 | 42/431 |
14 | 16/179 | 60/509 | 560/2161 | 9/109 | 42/431 |
16 | 16/179 | 60/509 | 140/2161 | 9/109 | 42/431 |
18 | 16/179 | 16/509 | 40/2161 | 9/109 | 42/431 |
20 | 2/179 | 4/509 | 140/6483 | 9/109 | 3/43 |
22 | 16/179 | 12/509 | 140/6483 | 9/109 | 42/431 |
24 | 16/179 | 60/509 | 280/2161 | 9/109 | 42/431 |
26 | 1/179 | 3/509 | 40/2161 | 1/109 | 2/43 |
28 | 16/179 | 4/509 | 40/2161 | 9/109 | 6/43 |
Sum | 1 | 1.066 | 1.034 | 1 | 1.351 |
3 | 5 | 7 | 9 | 11 | 14 | 16 | 18 | |
---|---|---|---|---|---|---|---|---|
Task 3 | 0.075 | 0.086 | 0.146 | 0.131 | 0.026 | 0.051 | 0.012 | 0.107 |
Task 5 | 0.037 | 0.086 | 0.146 | 0.131 | 0.037 | 0.051 | 0.037 | 0.107 |
Task 7 | 0.025 | 0.032 | 0.050 | 0.131 | 0.031 | 0.043 | 0.027 | 0.107 |
Task 9 | 0.018 | 0.021 | 0.025 | 0.032 | 0.026 | 0.038 | 0.021 | 0.107 |
Task 11 | 0.151 | 0.130 | 0.100 | 0.131 | 0.186 | 0.153 | 0.334 | 0.107 |
Task 14 | 0.227 | 0.195 | 0.146 | 0.131 | 0.372 | 0.306 | 0.222 | 0.107 |
Task 16 | 0.151 | 0.021 | 0.146 | 0.131 | 0.062 | 0.076 | 0.111 | 0.107 |
Task 18 | 0.015 | 0.013 | 0.012 | 0.010 | 0.023 | 0.034 | 0.018 | 0.017 |
Task 20 | 0.018 | 0.016 | 0.012 | 0.010 | 0.026 | 0.038 | 0.022 | 0.008 |
Task 22 | 0.018 | 0.016 | 0.016 | 0.016 | 0.026 | 0.038 | 0.022 | 0.107 |
Task 24 | 0.227 | 0.195 | 0.146 | 0.131 | 0.093 | 0.102 | 0.222 | 0.107 |
Task 26 | 0.015 | 0.013 | 0.010 | 0.008 | 0.023 | 0.034 | 0.018 | 0.005 |
Task 28 | 0.015 | 0.013 | 0.012 | 0.010 | 0.023 | 0.034 | 0.018 | 0.008 |
Sum | 1 | 0.96 | 0.972 | 1 | 1.057 | 0.981 | 1.09 | 1.005 |
20 | 22 | 24 | 26 | 28 | Average of I and II | |
---|---|---|---|---|---|---|
Task 3 | 0.089 | 0.117 | 0.016 | 0.082 | 0.097 | 0.079 |
Task 5 | 0.089 | 0.117 | 0.032 | 0.082 | 0.097 | 0.116 |
Task 7 | 0.089 | 0.117 | 0.026 | 0.082 | 0.097 | 0.065 |
Task 9 | 0.089 | 0.117 | 0.021 | 0.082 | 0.097 | 0.053 |
Task 11 | 0.089 | 0.117 | 0.388 | 0.082 | 0.097 | 0.158 |
Task 14 | 0.089 | 0.117 | 0.259 | 0.082 | 0.097 | 0.180 |
Task 16 | 0.089 | 0.117 | 0.064 | 0.082 | 0.097 | 0.096 |
Task 18 | 0.089 | 0.011 | 0.018 | 0.082 | 0.097 | 0.033 |
Task 20 | 0.011 | 0.007 | 0.021 | 0.082 | 0.069 | 0.026 |
Task 22 | 0.089 | 0.023 | 0.021 | 0.082 | 0.097 | 0.055 |
Task 24 | 0.089 | 0.117 | 0.129 | 0.082 | 0.097 | 0.133 |
Task 26 | 0.005 | 0.005 | 0.018 | 0.009 | 0.046 | 0.016 |
Task 28 | 0.089 | 0.007 | 0.018 | 0.082 | 0.139 | 0.036 |
Sum | 1 | 1.066 | 1.034 | 1 | 1.351 | 1.046 |
Rank | Before AHP | After AHP |
---|---|---|
1 | Task 5 | Task 26 |
2 | Task 3 | Task 20 |
3 | Task 9 | Task 18 |
4 | Task 7 | Task 28 |
5 | Task 20 | Task 09 |
6 | Task 22 | Task 22 |
7 | Task 11 | Task 07 |
8 | Task 24 | Task 03 |
9 | Task 16 | Task 16 |
10 | Task 26 | Task 05 |
11 | Task 14 | Task 24 |
12 | Task 28 | Task 11 |
13 | Task 18 | Task 14 |
BATS+ BAR system
Bipartite graph
After allocating the tasks, the constructed bipartite is updated if any task remain to be processed
Preemption of the task
-
Given the ranking of the tasks, they are allocated to the VMs using a bipartite graph, but the issue is now one oftime,
-
Suppose ‘P1’-‘VM1’ has complete ‘t1’, or VMn-1 has completed at time ∑ Pn-1. However, one VM is stillrunning with high-priority tasks, and its processing time is also greater.
-
Therefore, we preempt the task per the following methodology. Before preempting, we should check the status of the VM (i.e. whether it is free or busy).
-
V(t) denotes the expected value of the minimum remaining time needed to finish all of the jobs given the set
-
V*(t) denotes the time quantity t = {t1,--------, tn}
-
V* denotes the expected value of the remaining completion time when no task has yet been completed i.e., all tasks are in the running state.
-
λtn denotes the experimentally distributed time required for task tn
-
λtm denotes the experimentally distributed time required for task tm.
-
Ctn denotes the time at which the first VM has finish its task execution
-
Ctm denotes the last task completed by another VM
-
D denotes the difference between the completion of the first task and that of the last task i.e., in Eq. 10
Divide-and-conquer methodology
Evaluation of the proposed heuristic approach
Experimental setup
Sr. No. | Characteristic | Value |
---|---|---|
1 | Number of data center | 1 |
2 | Number of hosts | 1 |
3 | Number of processing units | 4 |
4 | Processing capacity | 9600 mips |
5 | Storage capacity | 11 TB |
6 | Total amount of RAM | 40 GB |
Sr. No. | Characteristic | Value |
---|---|---|
1 | Allocation policy | BATS +BAR |
2 | Architecture | X86 |
3 | Operating system | Linux |
4 | Hypervisor | Xen |
5 | Upper threshold | 0.8 |
6 | Lower threshold | 0.2 GB |
7 | VM migration | Enabled |
8 | Monitoring interval | 180 |
Sr. No. | Characteristic | Value |
---|---|---|
1 | RAM | 40,000 MB |
2 | Bandwidth | 10,00,000 |
3 | Operating System | Linux |
4 | Hypervisor | Xen |
5 | Upper threshold | 0.8 |
6 | Lower Threshold | 0.2 GB |
7 | VM Migration | Enabled |
8 | Monitoring Interval | 180 |
Sr. No. | Information | Contains |
---|---|---|
1 | User | 1 |
2 | Cloudlets sent per minutes | 50 |
3 | Avg. length of cloudlet | 50,000 |
4 | Avg. cloudlet file size | 500 bytes |
5 | Avg. cloudlet output size | 500 bytes |
Sr. No. | Information | Contains |
---|---|---|
1 | Number of VMs | 20 |
2 | Avg. image size | 1000 bytes |
3 | Avg. RAM | 512 MB |
4 | Avg. bandwidth | 1,000,000 Mbps |
5 | Procedure element | 1 |
6 | Priority | 1 |
7 | Hypervisor | Xen |
8 | Scheduling policy | Dynamic workload |
Results and discussion
Evaluation of turnaround time
Tasks | BATS with 20 VM | IDEA with 20 VM | Heuristic approach with 20 VM |
---|---|---|---|
Task 3 | 3599.29 | 3666.27 | 2832.94 |
Task 5 | 3599.29 | 3666.27 | 2914.42 |
Task 7 | 3599.29 | 3666.27 | 2913.87 |
Task 9 | 3599.29 | 3666.27 | 2911.75 |
Task 11 | 3599.29 | 3666.27 | 2907.67 |
Task 14 | 3599.29 | 3666.27 | 2772.11 |
Task 16 | 3599.29 | 3666.27 | 2857.89 |
Task 18 | 3599.29 | 3666.27 | 2855.97 |
Task 20 | 3599.29 | 3666.27 | 2833.36 |
Task 22 | 3599.29 | 3666.27 | 2834.72 |
Task 24 | 3599.29 | 3666.27 | 2841.49 |
Task 26 | 3599.29 | 3666.27 | 2832.86 |
Task 28 | 3599.29 | 3666.27 | 2833.96 |
BATS with 20 VMs | IDEA with 20 VMs | Heuristic approach with 20 VMs |
---|---|---|
3738 | 3895 | 2033.72 |
Evaluation of response time
Tasks | BATS with 20 VMs | IDEA with 20 VMs | Heuristic approach with 20 VMs |
---|---|---|---|
Task 3 | 5.1 | 5.3 | 2.83 |
Task 5 | 5.1 | 5.3 | 2.91 |
Task 7 | 5.1 | 5.3 | 2.9 |
Task 9 | 5.1 | 5.3 | 2.91 |
Task 11 | 5.1 | 5.3 | 2.90 |
Task 14 | 5.1 | 5.3 | 2.77 |
Task 16 | 5.1 | 5.3 | 2.85 |
Task 18 | 5.1 | 5.3 | 2.85 |
Task 20 | 5.1 | 5.3 | 2.83 |
Task 22 | 5.1 | 5.3 | 2.83 |
Task 24 | 5.1 | 5.3 | 2.84 |
Task 26 | 5.1 | 5.3 | 2.83 |
Task 28 | 5.1 | 5.3 | 2.83 |
BATS with 20 VMs | IDEA with 20 VMs | Heuristic approach with 20 VMs |
---|---|---|
4.8 | 5.2 | 3.7 |