5. Real-time Task Scheduling in Homogeneous Multiprocessor
5.2 Soft Real-time Task Scheduling Problem with Communication Time
5.2.2 GA Approach combined with SA
The solution algorithm is based on Genetic Algorithm (GA). Several new techniques are proposed in the encoding and decoding algorithm of genetic string and the genetic operations are introduced for discussion. They are explained in the following subsections.
1) Encoding and Decoding
A chromosome Vk, k=1,2,…,popSize, represents one of all the possible mappings of all the tasks into the processors. Where popSize is the total number of chromosomes in a generation.
A chromosome Vk is partitioned into two parts u(·), v(·). u(·) means scheduling order and v(·) means allocation information. The length of each part is the total number of tasks. The scheduling order part should be a topological order with respect to the given task graph that satisfies precedence relationship. The allocation information part denote the processor to which task is allocated.
Encoding procedure for sr-TSP is composed of two strategies: strategy I for u(·) and strategy II for v(·). Procedures will be written as follows:
procedure 5.6: Encoding Strategy I for sr-TSP input: task graph data set
output: u(·) begin
l←1, w←φ ; while (T ≠ φ)
w ← w ∪arg{τi |pre*(τi ) = φ , ∀i };
T ← T- {τi}, i∈w;
while (w ≠ φ)
j ← random(w);
u(l) ← j ; l ← l+1;
w ← w – {j };
pre*(τi ) ← pre*(τi ) – {τj}, ∀i;
end end
output u(·);
end
The procedure of strategy I generate u(·) as satisfying precedence relationship between tasks. Figure 5.18 represents the example of encoding strategy I procedure.
φ φ
7 2 5 4 1 6 3 j
φ {7}
{τ7}
φ {τ7}
{2}
{τ7} {2,5}
{τ7} {2,4,5}
{τ2,τ4,τ5,τ7} φ
{τ2,τ4,τ5,τ7} {1}
{τ2,τ4,τ5,τ7} {1,6}
{τ2,τ4,τ5,τ7} {1,3,6}
{τ1,τ2,τ3,τ4,τ5,τ6,τ7} φ
T w
φ φ
7 2 5 4 1 6 3 j
φ {7}
{τ7}
φ {τ7}
{2}
{τ7} {2,5}
{τ7} {2,4,5}
{τ2,τ4,τ5,τ7} φ
{τ2,τ4,τ5,τ7} {1}
{τ2,τ4,τ5,τ7} {1,6}
{τ2,τ4,τ5,τ7} {1,3,6}
{τ1,τ2,τ3,τ4,τ5,τ6,τ7} φ
T w
trace table
chromosome V
7 6 5 4 3 2 1 l
7 2 5 4 1 6 3 task no.u(·)
7 6 5 4 3 2 1 l
7 2 5 4 1 6 3 task no.u(·)
data set
-7 7 -4,5
-2 suc(τi)
32 7 5
-6 25
21 5 10
23 4 10
-3 10
17 2 10
-1 5
di ci i
-7 7 -4,5
-2 suc(τi)
32 7 5
-6 25
21 5 10
23 4 10
-3 10
17 2 10
-1 5
di ci i
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
communication time task graph
τ1 τ2
τ3 τ4
τ5 τ6 τ7
(5,-) (10,-) (25,-)
(10,17) (10,23) (5,32) (10,21)
2 3
1
1 2
Figure 5.18 Example of encoding strategy I procedure procedure 5.7: Encoding Strategy II for sr-TSP
input: task graph data set, u(·), ,
1 if , subgraph
1 if , ) 1 (
⎩⎨
⎧
=
≤
<
= −
k
popSize k
k
M M α, β
output: v(·), Mk
begin
l←1, tm ← 0, ∀m, idle ← 0;
while (l ≤ N)
m ← random[1, M];
i ← u(l);
if (tm < tiE) then tiS ← tiE;
idle ← idle + (tiS - tm);
end
else tiS ← tm;
if ( (di is not defined && tiS >tiL) || tiS > di) then if (idle/ci<α) then
M ← M +1;
m ← M;
idle ← idle + tiE; tm ← tiE + ci; end
else
idle ←max{0, (idle -ci)} ; end
else
tm ← tiS+ci; v(l) ← m;
l ← l+1;
end
idle ← idle + ∑(max{ tm }- tm);
end
while (idle/∑M X max{tm}> β) M ← M -1;
idle ← idle- idle/∑M X max{tm};
end
output v(·), Mk; end
In encoding strategy II procedure, the total number of processors is not fixed. Before generating v(·), the total number of processors M is defined and after generating v(·), M influence to v(·) of next chromosome. The M is changed during generating v(·). So, the M of output is different to the M of input. Where α, β is boundary constant to decide increasing the number of processor and decreasing the number of processor respectively.
Figure 5.19 represents the example of encoding strategy II procedure with task graph in Figure 5.18. In Figure 5.19, we can see that the number of processors is changed.
chromosome V
1 3 3 1 3 2 1 v(·)
7 6 5 4 3 2 1 l
7 2 5 4 1 6 3 u(·)
1 3 3 1 3 2 1 v(·)
7 6 5 4 3 2 1 l
7 2 5 4 1 6 3 u(·) trace table
7 0 6 0 0 0 0 0 idle
3 3 3 3 3 2 2 2 M
0 15
10 1 1 3
0.6 Idle/ci
32 27 7 1 7
11 5 2 3 6
21 11 5 3 5
20 10 4 1 4
5 0 1 3 3
25 0 6 2 2
10 0 3 1 1
tiF tiS i m i
7 0 6 0 0 0 0 0 idle
3 3 3 3 3 2 2 2 M
0 15
10 1 1 3
0.6 Idle/ci
32 27 7 1 7
11 5 2 3 6
21 11 5 3 5
20 10 4 1 4
5 0 1 3 3
25 0 6 2 2
10 0 3 1 1
tiF tiS i m i
M=|subgraph|=2 α= 0.2, β= 0.4
total idle time idle= 25 idle/∑M max{tm}= 25/96 < 0.4 M= 3
×
Gantt chart
data set
-7 7 -4,5
-2 suc(τi)
32 5 7
-6 25
21 10 5
23 10 4
-3 10
17 10 2
-5 1
di ci i
-7 7 -4,5
-2 suc(τi)
32 5 7
-6 25
21 10 5
23 10 4
-3 10
17 10 2
-5 1
di ci i
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
communication time
0 5 10 11 20 21 25 27 32 p1
task graph
τ1 τ2
τ3 τ4
τ5 τ6 τ7 (5,-) (10,-) (25,-)
(10,17) (10,23) (5,32) (10,21)
2 3
1
1 2
p2 p3
Figure 5.19 Example of encoding strategy II procedure Decoding procedure is will be written as follows:
procedure 5.8: Decoding for sr-TSP
input: task graph data set, chromosome u(·), v(·)
output: schedule set S, the total number of processor used f1, total tardiness of tasks f2 begin
l←1, tm ← 0, ∀m, idlem ← φ, ∀m, f1← 0, f2 ← 0, S ← φ;
while (l ≤ N) i ← u(l);
m← v(l);
if (tm =0) then f1 ← f1 +1;
IS*, IF* ← find {IS,IF|(IS,IF)∈idlem , IS ≤di};
if (IS* is exist && tm >tiL) then insert(i);
else start(i);
add_idle();
f2 ← f2+max{0,(tiS+ci-di )} ; S ← S ∪ {(i, m: tiS – tiF)};
l ← l+1;
end
output S, f1, f2 ; end
where insert(i) means to insert τi at idle time if τi is computable in idle time, start(i) means to assign τi to maximum finish time of all assigned task to pm , add_idle() means to add idle time to idle time list if idle time is occurred. IS means the start time of idle duration, IF means the end time of idle duration, idlem means the list of idle time and tm means the maximum finish time of all assigned task to pm.
The values of two objective f1 and f2 are calculated through the procedure of decoding.
Figure 5.20 represents the example of decoding procedure with chromosome in Figure 5.18 and Figure 5.19.
4 3
2 1
=
= f f chromosome
32 11 21 20 5 25 10 tiF
27 1 7 7
5 3 2 6
11 3 5 5
10 1 4 4
0 3 1 3
0 2 6 2
0 1 3 1
tiS v(l) i u(l)
32 11 21 20 5 25 10 tiF
27 1 7 7
5 3 2 6
11 3 5 5
10 1 4 4
0 3 1 3
0 2 6 2
0 1 3 1
tiS v(l) i u(l) trace table
S={ (3, 1:0-10), (6, 2:0-25), (1, 3:0-5), (4, 1:10-20 ), (5,3:11-21),(2, 3:5-11), (7, 1:27-32 )}
7 6 5 4 3 2 1 l
1 3 3 1 3 2 1 processor no.v(·)
7 2 5 4 1 6 3 task no.u(·)
7 6 5 4 3 2 1 l
1 3 3 1 3 2 1 processor no.v(·)
7 2 5 4 1 6 3 task no.u(·)
Gantt chart
-7 7 -4,5
-2 suc(τi)
32 5 7
-25 6
21 10 5
23 10 4
-10 3
17 10 2
-5 1
di ci i
-7 7 -4,5
-2 suc(τi)
32 5 7
-25 6
21 10 5
23 10 4
-10 3
17 10 2
-5 1
di ci i
data set
schedule S={(i,m:tiS,tiF)}
i: task number m: processor number tiS: start time of ith task tiF: finish time of ith task task graph
τ1 τ2
τ3 τ4
τ5 τ6 τ7 (5,-) (10,-) (25,-)
(10,17) (10,23) (5,32) (10,21)
2 3
1
1 2
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
2 7 6
1 7 5
1 5 3
3 4 3
2 2 1
gij j i
communication time
0 5 10 11 20 21 25 27 32 p1
tartdiness p2
p3
Figure 5.20 Example of decoding procedure
2) Evolution Function and Selection
We combine Adaptive Weight Approach (AWA) (Gen and Cheng, 2000) that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point.
The evaluation function is designed as follows:
∑
=−
=
=
2
1 max min
) ( 1
) ( / 1 ) (
q q q
k q k k
f f
V f V F V
eval
(5.16)
For selection, the commonly strategy called roulette wheel selection (Monnier, Beauvais and Deplanche, 1998; Gen and Cheng, 1997) has been used.
3) GA operators
We use one-cut crossover. This operator creates two new chromosomes (the proto-offspring) by mating two chromosomes (the parent). The one-cut crossover procedure will be written as follows:
procedure 5.9: One-cut Crossover
input: parent chromosomes u1(·), v1(·), u2(·) , v2(·)
output: proto-offspring chromosomes u1(·)’, v1(·)’, u2(·)’, v2(·)’ begin
r ← random[1,N];
u1(·)’ ← u1(·);
v1(·)’ ← v1[1:r] // v2[r+1:N] ; u2(·)’ ← u2(·);
v2(·)’ ← v2[1:r] // v1[r+1:N] ;
output offspring chromosomes u1(·)’, v1(·)’, u2(·)’, v2(·)’;
end
where u’(·), v’(·) are proto-offspring chromosome. Figure 5.21 represents the example of one-cut crossover procedure.
1 1 3 1 2 1 3
7 6 5 4 1 2 3
1 1 3 1 2 1 3
7 6 5 4 1 2 parent 1 3
3 3 1 1 2 1 3
7 6 5 4 1 2 3
3 3 1 1 2 1 3
7 6 5 4 1 2 3 parent 2
r
1 5
3 4
3 1
3 2 1
7 6
3 2 1
1 5
3 4
3 1
3 2 1
7 6
3 2 1
proto-offspring 1
1 1 3 1 3 2 1
7 4 5 6 3 2 1
1 1 3 1 3 2 1
7 4 5 6 3 2 proto-offspring 2 1
Figure 5.21 Example of one-cut crossover
For another GA operator, mutation, we use the classical one-bit altering mutation (Jackson and Rouskas, 2003).
4) Improving of convergence by the probability of SA
The convergence speed to local optimum of the GA can be improved by adopting the probability of simulated annealing (SA) (Kim, Hayashi and Nara, 1997; Kirkpatrick, Gelatt and Vecchi, 1983). Even though the fitness function value of newly produced strings is lower than those of current strings, the newly produced ones are fully accepted in early stages of searching process.
However, in later stages, a string with lower fitness function value is seldom accepted. The procedure of improved GA by the probability of SA will be written as follows:
procedure 5.10: Improving of GA by the probability of SA
input: parent chromosome V, proto-offspring chromosomes V, temperature T, cooling rate of SA ρ
output: offspring chromosomes V’’
begin
r ← random[0,1];
∆E ← eval(V’)-eval(V);
if ( ∆E >0 || r <Exp(∆E/T) ) V’’ ← V’;
else
V’’ ← V;
T ← T xρ;
output offspring chromosomes V’’
end
In this procedure, V and V’ are mean parent chromosome and proto-offspring chromosome.
V’’ means offspring chromosome which produced by this procedure. The T means the temperature and the ρ means the cooling rate of SA.
5) Reproduction and Population Replacement
During reproduction and replacement steps, proto-offspring chromosomes are created by mating, with probability pC, pairs of parents selected in the current population. And then chromosomes are mutated with probability pM, randomly using one of the mutation operators (Gen and Cheng, 2000). The offspring chromosomes are produced by the probability of SA.
Then new population is built through evaluating chromosomes and selecting.
This iterative evolution process is stopped as soon as one solution is found. However, we limit the number of offspring produced to maxGen, in order to avoid prohibitive calculation time, and to ensure that the GA will stop when treating an infeasible problem. Consequently, our proposed hybrid multiobjective Genetic Algorithm (h-moGA) obeys to the following algorithm:
procedure 5.11: sr-TSP by h-moGA input: task graph data set
output: best schedule set S begin
t ←0;
initialize P(t) by encoding strategy I and strategy II;
evaluate f1, f2 of P(t) by decoding routine;
create Pareto E(P);
fitness eval(P) by AWA;
while (not termination condition) do
crossover P(t) to yield C’(t) by one-cut crossover;
mutation P(t) to yield C’(t) by altering mutation;
improving of GA by the probability of SA;
evaluate f1, f2 by C(t) by decoding routine;
update Pareto E(P, C);
fitness eval(P, C) by AWA;
select P(t +1) from P(t) and C(t);
t ← t +1;
end
output best schedule set S;
end