Hardware Reference
In-Depth Information
To simplify the notation, the task index is omitted from task parameters whenever the
association with the related task is evident from the context. In the following, we
implicitly refer to a generic task
τ
i
, with maximum allowed NPR length
Q
i
=
Q
.As
shown in the previous sections,
Q
can be computed by the algorithm in Figure 8.12.
We say that an EPP selection is
feasible
if the length of each resulting NPR, including
the initial preemption overhead, does not exceed
Q
.
Figure 8.14 illustrates some of the defined parameters for a task with 6 basic blocks
and 3 NPRs. PPPs are represented by dots between consecutive basic blocks: black
dots are EPPs selected by the algorithm, while white dots are PPPs that are disabled.
Above the task code, the figure also reports the preemption costs
ξ
k
for each PPP,
although only the cost for the EPPs is accounted in the
q
j
of the corresponding NPR.
ξ
1
ξ
2
ξ
3
ξ
4
ξ
5
τ
i
δ
1
δ
2
δ
3
δ
4
δ
5
δ
6
b
1
b
2
b
3
b
4
b
5
b
6
q
1
q
2
q
3
Figure 8.14
Example of task with
6
BBs split into
3
NPRs. Preemption cost is reported
for each PPPs, but accounted only for the EPPs.
Using the notation introduced above, the non-preemptive WCET of
τ
i
can be ex-
pressed as follows:
N
i
C
NP
i
=
b
i,k
.
k
=1
The goal of the algorithm is to minimize the overall worst-case execution time
C
i
of each task
τ
i
, including the preemption overhead, by properly selecting the EPPs
among all the PPPs specified in the code by the programmer, without compromising
the schedulability of the task set. To compute the preemption overhead, we assume
that each EPP leads to a preemption, and that the cache is invalidated after each context
switch (note that EPP selection is optimal only under these assumptions). Therefore,
N
i
−
1
C
i
=
C
NP
+
selected(
i
,
k
)
·
ξ
i,k
i
k
=1
where
selected(
i
,
k
)
= 1 if the
k
-th PPP of
τ
i
is selected by the algorithm to be an
EPP, whereas
selected(
i
,
k
)
= 0, otherwise.
Search WWH ::
Custom Search