This page is under construction...
Pareto Algebra is an algebraic method to
compositionally specify and compute trade-offs in multi-dimensional optimization
Figure 1: Pareto points
A configuration describes a possible choice (for instance of a potential
system realization) by a number of values of different optimization criteria.
These so-called quantities have a partial order relation associated with them to
indicate which values are better than others.
The well-known Pareto optimality criterion specifies that one configuration
dominates the other when it is at least as good in all of the criteria and also
strictly better in at least one of them. In that case, the former configuration
is always preferred over the latter one, independent of how the various optimization criteria are weighed.
Such configurations are called Pareto points (see Figure 1).
Pareto Algebra is an algebra on sets of configurations, targeted to manipulate such sets for computation of optimal
The algebra can be used for design-time (deployment-time) design space exploration, but also
for run-time resource or Quality-of-Service management. An example of the latter is given below.
As an example of application of the Pareto Algebra and Calculator we look at an
application from the Betsy project.
An MPEG-4 video stream is played from a media center device over a wireless connection to a handheld device.
The optimisation criteria that matter to the end-user are the following.
- Quality of the video. Although an objective measure of preceived quality is difficult to give. Signal-to-noise ratio,
frame rate and frame size of the video contribute to the quality in a higher is better fashion. For the example we represent a combination of
these aspects as a single number, but any other model of quality could be fit in, including considering the three
aspects as individual, independent optimization criteria.
- Energy consumption by the hand held, or battery lifetime of the hand held. Depending on the settings,
the hand held may use less or more energy for decoding and rendering the video. The user prefers the device
to run out of energy as late as possible.
- Latency of the transmission. Long latency makes the play back slow to respond to commands from the user
and hence should be minimized.
All of the above criteria cannot be optimized independently. There is a trade-off. High quality video requires
more processing and hence more energy. Energy savings are possible at the expense of additional latency.
Figure 2: Wireless video streaming scenario
Figure 3: Configuring an application-platform mapping
Figure 4: Quality vs. bit rate of an MPEG-4 stream
The parameters that can be changed on the MPEG-4 encoder, that determine the bit rate and the quality, considered in this example, are the
frame rate, the frame size and the bit rate through control of the quantization parameter. We consider eight combinations of parameters, listed in Table 1.
|parameter settings||bit rate ||quality|
|s1 (QCIF, 15 fps)||64||38.0|
|s2 (QCIF, 15 fps)||384||45.0|
|s3 (QCIF, 30 fps)||64||41.0|
|s4 (QCIF, 30 fps)||384||48.0|
|s5 (CIF, 15 fps)||64||46.5|
|s6 (CIF, 15 fps)||384||52.5|
|s7 (CIF, 30 fps)||64||48.5|
Table 1: MPEG-4 encoder parameter settings
|s8 (CIF, 30 fps)||384||56.0|
The xml specification of the encoder profile can be seen here.
Bursty transmission of data allows for pauses in transmission during which the transceiver can be turned off. This can save energy over lower bandwidth
transmission. At the expense of in particular additional latency and additional memory requirements for buffering, energy can thus be saved. The bit rate that needs to be supported by the transmission
depends on teh encode parameter settings.
Figure 5: Trade-offs in wireless transmission
Figure 5 shows a trade-off between bit rate, buffer capacity and power. The four dots represent four alternative configurations
considered for configuration of the example setup.
The xml specification of the transmission profile can be seen here.
Decoder on Hand Held Platform
At the end of the delivery chain, the stream is decoded and rendered on the hand
held device. The parameter settings of the MPEG-4 encoded stream have their impact
on the amount of processing that needs to be done on the device. Only a limited
amount of processing is available and through voltage scaling (3 discrete available levels), the available processing
power can be traded for energy consumption. In the example, separate models of the
platform processor and the decoder application are combined to obtain a model of
the hand held device (decoding + rendering). This results in the following table.
Table 2: Configurations of the hand held
|MPEG-4 parameter settings||processor power consumption (W)|
An xml description of the model of the hand held device can be found here.
Pareto algebra allows one to compositionally compute the end-to-end trade-offs of the delivery chain from the models of the components.
The models of the decoder software and the processor platform have already been combined to determine the power consumption of the differen MPEG-4 stream parameters.
Additionally, all components should assume the same MPEG-4 parameter settings and the transmission should support the bit rate needed by the MPEG-4 stream.
Energy consumption of the wireless transmission and the decoding and rendering are added up.
Parameters that were relevant to compute the composition, but that are not relevant to the end user can be abstracted and the result is a set of configurations that are potentially interesting to the end-user.
Finally, the user should decide about her or his preferences between a high quality, low latency or long battery lifetime solution.
An xml description of the model of the end-to-end video delivery system can be found here.
Table 3: Pareto points of the MPEG-4 delivery chain
|Configuration #||Latency (s)||Buffer capacity (bits)||Quality||Total power consumption (W)|
- M.C.W. Geilen, T. Basten, B.D. Theelen, R.H.J.M. Otten. An
Algebra of Pareto Points. Fundamenta Informaticae. x(y):xxx-yyy,
200x. To appear. (Special issue with best papers of ACSD 2005.)
(abstract / pdf)
© IOS Press.
- M.C.W. Geilen, T. Basten. A Calculator
for Pareto Points. In Design, Automation and Test in Europe,
DATE 2007, Proceedings, pages xyz-xyz. Nice, France, 16-20 April,
2007. IEEE Computer Society Press, Los Alamitos, CA, USA, 2007.
Erratum: In Algorithm 1, implementing the producer-consumer
operation, line 11, "add all..." should be preceded
by: "if j>=0 then".
- H. Shojaei, T. Basten, M.C.W. Geilen, P. Stanley-Marbell.
SPaC: A Symbolic Pareto Calculator. In
Hardware-Software Codesign and System Synthesis, International
Conference, CODES+ISSS 2008, Proceedings, pages xyz-xyz. Atlanta,
Georgia, USA, 19-24 October, 2008. ACM, 2008. (abstract
- R. Hoes, T. Basten, C.-K. Tham, M.C.W. Geilen, H. Corporaal.
Quality-of-Service Trade-off Analysis
for Wireless Sensor Networks.
Performance Evaluation. x(y):xxx-yyy, 200x. To appear. (Special
issue with best papers of MSWiM 2007.) (abstract
/ pdf) © Elsevier.
- M.C.W. Geilen, T. Basten, B.D. Theelen, R.H.J.M. Otten. An
Algebra of Pareto Points. In J. Desel and Y. Watanabe,
editors Application of Concurrency to System Design, 5th International
Conference, ACSD 2005, Proceedings, pages 88-97. St Malo, France,
6-9 June 2005. IEEE Computer Society Press, Los Alamitos, CA,
USA, 2005. (abstract
/ pdf) © IEEE. (see
journal version Fund. Inf. above).
This work is supported by the European Commission through the IST-004042 project
Betsy and the IST-216224