5. Real-time Task Scheduling in Homogeneous Multiprocessor
5.2 Soft Real-time Task Scheduling Problem with Communication Time
5.2.3 Validation
1
8
3
4
7
5
6
10
2
9
Figure 5.22 Task graph with 10 tasks
For generality of numerical test, Table 5.12, 5.13, 5.14 and 5.15 are data set generated by exponential distribution and normal distribution of task graph in Figure 5.22 respectively.
Table 5.12 Data set of task graph with 10 tasks (exponential distribution)
i suc(τi) ci di i suc(τi) ci di
1 8 5 13 6 9 2 24
2 6 3 17 7 - 2 13
3 4,5 3 12 8 - 3 18
4 6,7,8 2 12 9 10 5 27
5 6,10 12 27 10 - 1 29
Table 5.13 Communication time of 10 tasks (exponential distribution)
i j gij i j gij
1 8 5 4 8 1
2 6 2 5 6 2
3 4 7 5 10 7
3 5 9 6 9 1
4 6 6 9 10 3
4 7 3
Table 5.14 Data set of task graph with 10 tasks (normal distribution)
i suc(τi) ci di i suc(τi) ci di
1 8 5 19 6 9 2 37
2 6 6 9 7 - 3 44
3 4,5 11 18 8 - 4 30
4 6,7,8 10 37 9 10 6 37
5 6,10 10 38 10 - 11 58
Table 5.15 Communication time of 10 tasks (normal distribution)
i j gij i j gij
1 8 7 4 8 7
2 6 6 5 6 6
3 4 7 5 10 5
3 5 6 6 9 4
4 6 2 9 10 6
4 7 5
Table 5.16 and 5.17 shows the comparisons of results by three different scheduling algorithms. In the case of data set based on exponential distribution (Table 5.16), there is no tardiness inclusively. The computing time of proposed h-moGA is a little bit longer than those of the other two algorithms. However, the number of used processors is fewer (3 processors) than those of the Oh-Wu’s algorithms (4 processors). The average utilization of processors by h-moGA is more desirable than those of the others.
The results based on normal distribution (Table 5.17), there are no tardiness inclusively. The computing time of proposed h-moGA is about 12% longer than that of other two algorithms.
However, the number of used processors is also fewer (4 processors) than those of Oh-Wu’s algorithm (5 processors). The average utilization of processors by h-moGA is most desirable one.
Table 5.16 Computation results 3 algorithms based on data set in Table 5.9 and 5.10 without tardiness (exponential)
terms Oh-Wu’s Algorithm moGA h-moGA
# of processors M 4 3 3
Makespan 29 27 28
Computing time (msec) 13 14 19 Average utilization of processors 0.487179 0.550725 0.578571
Table 5.17 Computation results 3 algorithms based on data set in Table 5.11 and 5.12 without tardiness (normal)
terms Oh-Wu’ Algorithm moGA h-moGA
# of processors M 5 4 4
Makespan 47 42 42
Computing times (msec) 35 36 41 Average utilization of processors 0.495152 0.519683 0.525556
Figure 5.23 and 5.24 represent the Pareto solution of three algorithms. In these Figure, the Pareto solution curve by proposed h-moGA is closer to ideal point than that of Oh-Wu’
algorithms. The coordinate of ideal point is total number of processors is 1 (f1=1) and total tardiness is 0 (f2=0).
0 5 10 15 20 25 30 35
0 1 2 3 4 5
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.23 Pareto solution in 10 tasks based on exponential distribution
0 10 20 30 40 50 60 70 80
0 1 2 3 4 5 6
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.24 Pareto solution in 10 tasks based on normal distribution
Table 5.18 shows the numerical data of the best solution in Figure 5.23 and 5.24.
Table 5.18 Numerical data of the best solution in Figure 5.23 and 5.24 10 tasks (exponential) 10 tasks (normal) objective
function Oh-Wu’s
algorithm moGA h-moGA Oh-Wu’s
algorithm moGA h-moGA
f1 2 2 2 3 3 3
f2 19 8 8 45 20 12
However, in these cases, it is not unreasonable that the result of h-moGA is better than that of moGA. The distinction between h-moGA and moGA is not appeared because the total number of tasks is very small.
2) Example 2
In this example, we use a task graph with 50 tasks. Figure 5.25 represents the task graph of 50 tasks case.
26
36 10
7
25 50 31
42
34 11
18 13
29 16
8
35
20 22 9
1
21 5 12
27
3 23 24
38 46
37 45 49
6 39
30
41
47 14
32 15
44 4
19 17
40
43 28
33 48
2
Figure 5.25 Task graph with 50 tasks
The data sets are omitted. Table 5.19 and 5.20 shows the comparisons of results by three different scheduling algorithms. In the case of data set based on exponential distribution (Table 5.19), there is no tardiness inclusively. The computing time of proposed h-moGA is a little bit longer than those of the other two. However, the number of used processors is fewer than those of the other two algorithms. The average utilization of processors by h-moGA is most desirable than those of the others. The results based on normal distribution (Table 5.20) also show same results in Table 5.19.
Table 5.19 Computation results 3 algorithms for 50 tasks without tardiness (exponential)
terms Oh-Wu’s Algorithm moGA h-moGA
# of processors M 35 32 26
Makespan 35 37 41
Computing times (msec) 118 122 191
Average utilization of processors 0.368339 0.412281 0.573981
Table 5.20 Computation results 3 algorithms for 50 tasks without tardiness (normal)
terms Oh-Wu’s Algorithm moGA h-moGA
# of processors M 32 28 26
Makespan 43 49 51
Computing times (msec) 120 129 198
Average utilization of processors 0.450904 0.474185 0.515035
Figure 5.26 and 5.27 represent the Pareto solution of proposed h-moGA and that of other two algorithms. In these Figures, the Pareto solution curve by proposed h-moGA is closer to ideal point than that of other two algorithms.
0 50 100 150 200 250 300
0 10 20 30 40
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.26 Pareto solution in 50 tasks based on exponential distribution
0 50 100 150 200 250 300 350 400 450 500
0 5 10 15 20 25 30 35
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.27 Pareto solution in 50 tasks based on normal distribution
Table 5.21 shows the numerical data of the best solution in Figure 5.26 and 5.27.
Table 5.21 Numerical data of the best solution in Figure 5.26 and 5.27 50 tasks (exponential) 50 tasks (normal) objective
function Oh-Wu’s
algorithm moGA h-moGA Oh-Wu’s
algorithm moGA h-moGA
f1 13 12 11 11 7 7
f2 110 106 92 243 233 209
3) Example 3
In this example, we use a task graph with 100 tasks. Task graph and data sets are omitted.
Table 5.22 and 5.23 shows the comparisons of results by three different scheduling algorithms.
In the case of data set based on exponential distribution (Table 5.22), there is no tardiness inclusively. The computing time of proposed h-moGA is a little bit longer than those of the other two. However, the number of used processors is fewer than those of the other two algorithms.
The average utilization of processors by h-moGA is most desirable than those of the others. The results based on normal distribution (Table 5.23) also show same results in Table 5.22.
Table 5.22 Computation results 3 algorithms for 100 tasks without tardiness (exponential)
terms Oh-Wu’s Algorithm moGA h-moGA
# of processors M 36 34 31
Makespan 157 163 168
CPU times (msec) 497 511 818
Average utilization of processors 0.417582 0.433392 0.497352 Table 5.23 Computation results 3 algorithms for 100 tasks without tardiness (normal)
terms Oh-Wu’s Algorithm moGA h-moGA
# of processors M 36 32 30
Makespan 193 198 209
CPU times (msec) 498 517 820
Average utilization of processors 0.433363 0.487823 0.527490
Figure 5.28 and 5.29 represent the Pareto solution of proposed h-moGA and those of other two algorithms. In these Figures, the Pareto solution curve by proposed h-moGA is closer to ideal point than that of other two algorithms.
0 100 200 300 400 500 600 700
0 10 20 30 40
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.28 Pareto solution in 100 tasks based on exponential distribution
0 200 400 600 800 1000 1200
0 10 20 30 40
total number of processors
total tardiness
Oh-Wu's algorithm moGA h-moGA
Figure 5.29 Pareto solution in 100 tasks based on normal distribution
Table 5.24 shows the numerical data of the best solution in Figure 5.28 and 5.29.
Table 5.24 Numerical data of the best solution in Figure 5.26 and 5.27 100 tasks (exponential) 100 tasks (normal) objective
function Oh-Wu’s
algorithm moGA h-moGA Oh-Wu’s
algorithm moGA h-moGA
f1 9 10 12 7 8 6
f2 318 253 211 809 588 554