Abstract
Already for more than a decade, consumer electronic devices have been available for
entertainment, educational, or telecommunication tasks based on multimedia streaming
applications, i.e., applications that process streams of audio and video samples in digital form.
Multimedia capabilities are expected to become more and more commonplace in portable
devices. This leads to challenges with respect to cost efficiency and quality. This thesis
contributes models and analysis techniques for improving the cost efficiency, and therefore also
the quality, of multimedia devices.
Portable consumer electronic devices should feature flexible functionality on the one hand
and low power consumption on the other hand. Those two requirements are conflicting.
Therefore, we focus on a class of hardware that represents a good trade-off between those two
requirements, namely on domain-specific multiprocessor systems-on-chip (MP-SoC). Our
research work contributes to dynamic (i.e., run-time) optimization of MP-SoC system metrics.
The central question in this area is how to ensure that real-time constraints are satisfied and the
metric of interest such as perceived multimedia quality or power consumption is optimized. In
these cases, we speak of quality-of-service (QoS) and power management, respectively.
In this thesis, we pursue real-time constraint satisfaction that is guaranteed by the system by
construction and proven mainly based on analytical reasoning. That approach is often taken in
real-time systems to ensure reliable performance. Therefore the performance analysis has to be
conservative, i.e. it has to use pessimistic assumptions on the unknown conditions that can
negatively influence the system performance. We adopt this hypothesis as the foundation of this
work. Therefore, the subject of this thesis is the analysis of guaranteed performance for
multimedia applications running on multiprocessors.
It is very important to note that our conservative approach is essentially different from
considering only the worst-case state of the system. Unlike the worst-case approach, our
approach is dynamic, i.e. it makes use of run-time characteristics of the input data and the
environment of the application.
The main purpose of our performance analysis method is to guide the run-time optimization.
Typically, a resource or quality manager predicts the execution time, i.e., the time it takes the
system to process a certain number of input data samples. When the execution times get smaller,
due to dependency of the execution time on the input data, the manager can switch the control
parameter for the metric of interest such that the metric improves but the system gets slower. For
power optimization, that means switching to a low-power mode. If execution times grow, the
manager can set parameters so that the system gets faster. For QoS management, for example,
the application can be switched to a different quality mode with some degradation in perceived
quality. The real-time constraints are then never violated and the metrics of interest are kept as
good as possible.
Unfortunately, maintaining system metrics such as power and quality at the optimal level
contradicts with our main requirement, i.e., providing performance guarantees, because for this
one has to give up some quality or power consumption. Therefore, the performance analysis
approach developed in this thesis is not only conservative, but also accurate, so that the
optimization of the metric of interest does not suffer too much from conservativity. This is not
trivial to realize when two factors are combined: parallel execution on multiple processors and
dynamic variation of the data-dependent execution delays. We achieve the goal of conservative
and accurate performance estimation for an important class of multiprocessor platforms and
multimedia applications. Our performance analysis technique is realizable in practice in QoS or
power management setups.
We consider a generic MP-SoC platform that runs a dynamic set of applications, each
application possibly using multiple processors. We assume that the applications are independent,
although it is possible to relax this requirement in the future. To support real-time constraints, we
require that the platform can provide guaranteed computation, communication and memory
budgets for applications. Following important trends in system-on-chip communication, we
support both global buses and networks-on-chip.
We represent every application as a homogeneous synchronous dataflow (HSDF) graph,
where the application tasks are modeled as graph nodes, called actors. We allow dynamic datadependent
actor execution delays, which makes HSDF graphs very useful to express modern
streaming applications. Our reason to consider HSDF graphs is that they provide a good basic
foundation for analytical performance estimation.
In this setup, this thesis provides three major contributions:
1. Given an application mapped to an MP-SoC platform, given the performance guarantees
for the individual computation units (the processors) and the communication unit (the
network-on-chip), and given constant actor execution delays, we derive the throughput
and the execution time of the system as a whole.
2. Given a mapped application and platform performance guarantees as in the previous
item, we extend our approach for constant actor execution delays to dynamic datadependent
actor delays.
3. We propose a global implementation trajectory that starts from the application
specification and goes through design-time and run-time phases. It uses an extension of
the HSDF model of computation to reflect the design decisions made along the
trajectory. We present our model and trajectory not only to put the first two
contributions into the right context, but also to present our vision on different parts of
the trajectory, to make a complete and consistent story.
Our first contribution uses the idea of so-called IPC (inter-processor communication) graphs
known from the literature, whereby a single model of computation (i.e., HSDF graphs) are used
to model not only the computation units, but also the communication unit (the global bus or the
network-on-chip) and the FIFO (first-in-first-out) buffers that form a ‘glue’ between the
computation and communication units. We were the first to propose HSDF graph structures for
modeling bounded FIFO buffers and guaranteed throughput network connections for the
network-on-chip communication in MP-SoCs. As a result, our HSDF models enable the
formalization of the on-chip FIFO buffer capacity minimization problem under a throughput
constraint as a graph-theoretic problem. Using HSDF graphs to formalize that problem helps to
find the performance bottlenecks in a given solution to this problem and to improve this solution.
To demonstrate this, we use the JPEG decoder application case study. Also, we show that,
assuming constant – worst-case for the given JPEG image – actor delays, we can predict
execution times of JPEG decoding on two processors with an accuracy of 21%.
Our second contribution is based on an extension of the scenario approach. This approach is
based on the observation that the dynamic behavior of an application is typically composed of a
limited number of sub-behaviors, i.e., scenarios, that have similar resource requirements, i.e.,
similar actor execution delays in the context of this thesis. The previous work on scenarios treats
only single-processor applications or multiprocessor applications that do not exploit all the
flexibility of the HSDF model of computation. We develop new scenario-based techniques in the
context of HSDF graphs, to derive the timing overlap between different scenarios, which is very
important to achieve good accuracy for general HSDF graphs executing on multiprocessors. We
exploit this idea in an application case study – the MPEG-4 arbitrarily-shaped video decoder, and
demonstrate execution time prediction with an average accuracy of 11%. To the best of our
knowledge, for the given setup, no other existing performance technique can provide a
comparable accuracy and at the same time performance guarantees.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 3 Nov 2008 |
Place of Publication | Eindhoven |
Publisher | |
Print ISBNs | 978-90-386-1418-2 |
DOIs | |
Publication status | Published - 2008 |