Hardware Reference
In-Depth Information
subject to the following QoS and resource constraints:
τ
max
,
c
α
[
τ
]
≤
∀
α
∈
A
(5.4)
≤
c
α
[
ρ
]
ρ
max
(5.5)
α
∈
A
where
ρ
max
is the maximum number of resources (or cores) in the system,
p
is
number of active applications and
A
is a set of all active applications.
According to [
38
], the previous problem is a Multi-dimension Multiple-choice
Knapsack Problem (MMKP) whose complexity resides in the NP-hard space with
respect to
p
,
N
α
and
ρ
max
. Moreover, depending on how tight
τ
max
constraints have
been set, there may not be
feasible
solutions
γ
. However, in our case of embedded
systems for multi-media domain, usually applications do not have
hard
real-time
constraints. Instead, we address the design of a
soft real-time system
in which
deadlines can be missed with the lowest penalty possible and/or the lowest proba-
bility. We manage this possibility by introducing a priority
ω
(
α
) measure to be used
by the run-time manager to relax some
τ
max
and reach a feasible solution.
In the following section we describe our proposed toolflow which consists of two
parts: one design-time analysis and other run-time heuristic.
5.4
Proposed Tool-Flow for RRM
This section describes our proposed tool-flow to solve Run-time Resource Manage-
ment (RRM) problem described above. Application of this tool-flow on a real-life
multimedia use case is described in Chap. 9. Our tool-flow solves RRM problem in
two steps:
1. A
design-time heuristic methodology
for reducing the average size
N
α
for each
α
.
2. A
run-time management layer
consisting of a filtering algorithm for each
C
α
and a greedy,
prioritized
heuristic for solving the MMKP.
5.4.1
Design-Time Heuristic Methodology
Our design-time methodology is shown in Fig.
5.1
. At design time, we identify an
ordered list
C
α
of operating points:
c
α
...
c
N
α
C
α
=
(5.6)
α
C
α
is generated at design-time by analyzing and exploring the impact of the architec-
ture run-time parameters on the QoS through an architecture simulator(s). Optimal
C
α
is derived from these design-time analysis by help of sophisticated optimization
Search WWH ::
Custom Search