Information Technology Reference
In-Depth Information
ASAP_Algorithm(
G
(
V,E
))
1. for
v
i
∈
V
do
2. if Pred
vi
= Øthen
3.
F
i
= 0;
4.
V
=
V
- {
v
i
}
;
5. while
V
≠ Ødo
6. for
v
i
∈
V
do
7.
if all nodes scheduled(Pred
vi
, F
)then
8.
F
i
= MAX(Pred
vi
,
F
);
9.
V
=
V
- {
v
i
}
;
10. return (
F
)
Figure 5.4
An overview of the ASAP algorithm.
ALAP_Algorithm(
G
(
V
,
E
),
T
)
1. for
v
i
∈
V
do
2. if Succ
vi
= Øthen
3.
L
i
=
T
;
4.
V
=
V
- {
v
i
};
5. while
V
≠ Ødo
6. for
v
i
∈
V
do
7. if all nodes scheduled(Succ
vi
,
L)then
8. L
i
= MIN(Succ
vi
, L);
9.
V
=
V
- {
v
i
};
10. return (L)
Figure 5.5
An overview of the ALAP algorithm.
In Figure 5.5, we illustrate the ALAP scheduling algorithm according to
Gajski et al. [7], where it assigns an ALAP label
L
i
to each node
v
i
of STFG,
thereby scheduling the starting execution of
v
i
into the latest possible state.
In lines 1-4, all nodes are initialized and the function Succ
vi
determines all
nodes, which are immediate successors of the node
v
i
. The vector
L
contains
the latest starting execution times for all nodes. In lines 5-9, all the resid-
ual nodes, which have successor nodes, will be assigned starting times for
execution. In line 7, the function all-nodes-scheduled returns true if all the
nodes in set Succ
vi
are scheduled. In line 8, the function MIN determines the
node with the longest execution value (finishing execution time—starting
execution time) from the set of predecessor nodes for
v
i
.
