Pareto Algebra and the Pareto Calculator

Pareto Algebra

Pareto Algebra is an algebraic method to compositionally specify and compute trade-offs in multi-dimensional optimization problems.

Pareto Analysis

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

Pareto Algebra is an algebra on sets of configurations, targeted to manipulate such sets for computation of optimal configurations.

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.

Example

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

MPEG-4 Encoder

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.

The xml specification of the encoder profile can be seen here.

Wireless Transmission

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.

An xml description of the model of the hand held device can be found here.

End-to-end model

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.

Publications

• 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. (abstract / pdf) © IEEE.
  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 / pdf) © ACM.
• 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).

People involved

• Twan Basten
• Marc Geilen
• Rob Hoes
• Hamid Shojaei
• Phillip Stanley-Marbell
• Sander Stuijk
• Bart Theelen

Acknowledgements

This work is supported by the European Commission through the IST-004042 project Betsy and the IST-216224 project MNEMEE.