The Pareto Calculator

The Pareto Calculator ^[1] is a software implementation of the Pareto Algebra ^[2]. It defines the individual aspects, ‘quantities’ and their ordering in terms of better or worse. In Pareto Algebra, objectives can, but do not have to be, numerical and they can use arbitrary partial orders, i.e., some values may be incomparable. The calculator further allows so-called configuration spaces to be built from quantities. They define what properties configurations have. It then implements all the operators of the algebra to realize calculations of possible configurations, and in particular the computation of Pareto optimal configurations.

The tool is developed in C++ and consists of a core library of all the relevant operations, and a simple GUI that allows calculations to be performed interactively, or as described by an xml based input file.

A symbolic computation of some of the operators of the algebra is implemented in a different tool ^[3]. It uses Binary Decision Diagrams (BDDs) to represent sets of configuration symbolically, which may give a speedup in some cases.

File Format

Definitions of components and calculations can be specified in an xml format. The following is an example.

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="../xml/paretospec.xslt"?>
<pareto_specification xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="uri:pareto" xsi:schemaLocation="uri:pareto http://www.es.ele.tue.nl/~mgeilen/paretoalgebra/xml/paretospec.xsd ">
  <name>Case-Study, An Algebra of Pareto Points, Fundamenta Informaticae</name>
  <description>
    Model of a video stream delivered from a server via a wireless connection to a
    hand-held device. The case-study is described in the paper "An Algebra of Pareto Points", in Fundamenta Informaticae, vol. 78, no. 1, pp. 35-74, 2007
  </description>
  <quantity_definitions>
    <quantity_definition name="MPEGQuality" type="real"></quantity_definition>
    <quantity_definition name="MPEGBitRate"  type="real"></quantity_definition>
    <quantity_definition name="MPEGParams" type="unordered">
      <values>
        <value>mp_s1</value>
        <value>mp_s2</value>
        <value>mp_s3</value>
        <value>mp_s4</value>
        <value>mp_s5</value>
        <value>mp_s6</value>
        <value>mp_s7</value>
        <value>mp_s8</value>
      </values>
    </quantity_definition>
    <quantity_definition name="TransmBitRate_Inv"  type="real"></quantity_definition>
    <quantity_definition name="TransmLatency" type="real"></quantity_definition>
    <quantity_definition name="TransmBufferCapacity" type="real"></quantity_definition>
    <quantity_definition name="TransmPower" type="real"></quantity_definition>
    <quantity_definition name="DecoderCompEffort" type="real"></quantity_definition>
    <quantity_definition name="DecoderLatency" type="real"></quantity_definition>
    <quantity_definition name="ProcessorCompEffort_Inv" type="real"></quantity_definition>
    <quantity_definition name="ProcessorMode" type="unordered">
      <values>
        <value>pr_M1</value>
        <value>pr_M2</value>
        <value>pr_M3</value>
      </values>
    </quantity_definition>
    <quantity_definition name="ProcessorPower"  type="real"></quantity_definition>
  </quantity_definitions>
  <configuration_spaces>
    <space name="Encoder">
        <quantity name="MPEGParams" referBy="MPEGParams_Encoder"></quantity>
        <quantity name="MPEGQuality"></quantity>
        <quantity name="MPEGBitRate"></quantity>
    </space>
    <space name="Transmission">
        <quantity name="TransmBitRate_Inv"></quantity>
        <quantity name="TransmLatency"></quantity>
        <quantity name="TransmBufferCapacity"></quantity>
        <quantity name="TransmPower"></quantity>
    </space>
    <space name="Decoder">
        <quantity name="MPEGParams" referBy="MPEGParams_Decoder"></quantity>
        <quantity name="DecoderCompEffort"></quantity>
    </space>
    <space name="Processor">
        <quantity name="ProcessorCompEffort_Inv"></quantity>
        <quantity name="ProcessorMode"></quantity>
        <quantity name="ProcessorPower"></quantity>
    </space>
  </configuration_spaces>
  <configuration_sets>
    <configuration_set name="EncoderProfile" space_id="Encoder">
      <configurations>
        <configuration>
          <value>mp_s1</value>
          <value>-38</value>
          <value>64</value>
        </configuration>
        <configuration>
          <value>mp_s2</value>
          <value>-45</value>
          <value>384</value>
        </configuration>
        <configuration>
          <value>mp_s3</value>
          <value>-41</value>
          <value>64</value>
        </configuration>
        <configuration>
          <value>mp_s4</value>
          <value>-48</value>
          <value>384</value>
        </configuration>
        <configuration>
          <value>mp_s5</value>
          <value>-46.5</value>
          <value>64</value>
        </configuration>
        <configuration>
          <value>mp_s6</value>
          <value>-52.5</value>
          <value>384</value>
        </configuration>
        <configuration>
          <value>mp_s7</value>
          <value>-48.5</value>
          <value>64</value>
        </configuration>
        <configuration>
          <value>mp_s8</value>
          <value>-56</value>
          <value>384</value>
        </configuration>
      </configurations>
    </configuration_set>
    <configuration_set name="TransmissionProfile" space_id="Transmission">
      <configurations>
        <configuration>
          <value>0.01</value>
          <value>0.125</value>
          <value>12500</value>
          <value>0.07</value>
        </configuration>
        <configuration>
          <value>0.002</value>
          <value>0.025</value>
          <value>12500</value>
          <value>0.33</value>
        </configuration>
        <configuration>
          <value>0.002</value>
          <value>0.07</value>
          <value>35000</value>
          <value>0.22</value>
        </configuration>
        <configuration>
          <value>0.002</value>
          <value>0.16</value>
          <value>80000</value>
          <value>0.16</value>
        </configuration>
      </configurations>
    </configuration_set>
    <configuration_set name="DecoderProfile" space_id="Decoder">
      <configurations>
        <configuration>
          <value>mp_s1</value>
          <value>97</value>
        </configuration>
        <configuration>
          <value>mp_s2</value>
          <value>156</value>
        </configuration>
        <configuration>
          <value>mp_s3</value>
          <value>192</value>
        </configuration>
        <configuration>
          <value>mp_s4</value>
          <value>303</value>
        </configuration>
        <configuration>
          <value>mp_s5</value>
          <value>378</value>
        </configuration>
        <configuration>
          <value>mp_s6</value>
          <value>545</value>
        </configuration>
        <configuration>
          <value>mp_s7</value>
          <value>749</value>
        </configuration>
        <configuration>
          <value>mp_s8</value>
          <value>1100</value>
        </configuration>
      </configurations>
    </configuration_set>
    <configuration_set name="ProcessorProfile" space_id="Processor">
      <configurations>
        <configuration>
          <value>0.0025</value>
          <value>pr_M1</value>
          <value>2.8</value>
        </configuration>
        <configuration>
          <value>0.0050</value>
          <value>pr_M2</value>
          <value>1.6</value>
        </configuration>
        <configuration>
          <value>0.0100</value>
          <value>pr_M3</value>
          <value>0.9</value>
        </configuration>
      </configurations>
    </configuration_set>
  </configuration_sets>
  <calculation>
    <push name="ProcessorProfile"/>
    <push name="DecoderProfile"/>
    <product/>
    <prodcons>
      <producer_quant>ProcessorCompEffort_Inv</producer_quant>
      <consumer_quant>DecoderCompEffort</consumer_quant>
    </prodcons>
    <abstract>
      <quant>ProcessorCompEffort_Inv</quant>
      <quant>DecoderCompEffort</quant>
    </abstract>
    <hide>
      <quant>ProcessorMode</quant>
    </hide>
    <minimize/>
    <store name="Decoder-Processor-Profile"/>
    <push name="TransmissionProfile"/>
    <push name="EncoderProfile"/>
    <product/>
    <prodcons>
      <producer_quant>TransmBitRate_Inv</producer_quant>
      <consumer_quant>MPEGBitRate</consumer_quant>
    </prodcons>
    <abstract>
      <quant>TransmBitRate_Inv</quant>
      <quant>MPEGBitRate</quant>
    </abstract>
    <minimize/>
    <store name="Encoder-Transmission-Profile"/>
    <push name="Decoder-Processor-Profile"/>
    <push name="Encoder-Transmission-Profile"/>
    <join>
      <between quanta="MPEGParams_Encoder" quantb="MPEGParams_Decoder"/>
    </join>
    <hide>
      <quant>MPEGParams_Encoder</quant>
    </hide>
    <abstract>
      <quant>MPEGParams_Decoder</quant>
    </abstract>
    <minimize/>
    <aggregate>
      <quant>TransmPower</quant>
      <quant>ProcessorPower</quant>
      <name>TotalPower</name>
    </aggregate>
    <abstract>
      <quant>TransmPower</quant>
      <quant>ProcessorPower</quant>
    </abstract>
    <duplicate/>
    <store name="Final Profile"/>
    <duplicate/>
    <print/>
  </calculation>
</pareto_specification>

Schema Definition

The xml format is defined by the follow schema.

<?xml version="1.0"?>
<xs:schema targetNamespace="uri:pareto" xmlns="uri:pareto" xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified">
  <xs:simpleType name="quantitytype">
    <xs:restriction base="xs:string">
      <xs:enumeration value="real" />
      <xs:enumeration value="integer" />
      <xs:enumeration value="enumeration" />
      <xs:enumeration value="unordered" />
    </xs:restriction>
  </xs:simpleType>
  <xs:element name="pareto_specification">
    <xs:complexType>
      <xs:sequence>
        <xs:element name="name" type="xs:string" maxOccurs="1" minOccurs="0">
        </xs:element>
        <xs:element name="description" type="xs:string" maxOccurs="1" minOccurs="0">
        </xs:element>
        <xs:element name="quantity_definitions" minOccurs="0">
          <xs:complexType>
            <xs:sequence>
              <xs:element name="quantity_definition" minOccurs="0" maxOccurs="unbounded">
                <xs:complexType>
                  <xs:sequence minOccurs="0">
                    <xs:element name="values">
                      <xs:complexType>
                        <xs:sequence>
                          <xs:element name="value" maxOccurs="unbounded" />
                        </xs:sequence>
                      </xs:complexType>
                    </xs:element>
                  </xs:sequence>
                  <xs:attribute name="name" type="xs:string" use="required" />
                  <xs:attribute name="type" type="quantitytype" use="required" />
                </xs:complexType>
              </xs:element>
            </xs:sequence>
          </xs:complexType>
        </xs:element>
        <xs:element name="configuration_spaces" minOccurs="0">
          <xs:complexType>
            <xs:sequence>
              <xs:element name="space" maxOccurs="unbounded" minOccurs="0">
                <xs:complexType>
                  <xs:sequence>
                    <xs:element name="quantity" maxOccurs="unbounded">
                      <xs:complexType>
                        <xs:attribute name="name" type="xs:string" use="required" />
                        <xs:attribute name="referBy" type="xs:string" use="optional" />
                      </xs:complexType>
                    </xs:element>
                  </xs:sequence>
                  <xs:attribute name="name" type="xs:string" use="required" />
                </xs:complexType>
              </xs:element>
            </xs:sequence>
          </xs:complexType>
        </xs:element>
        <xs:element name="configuration_sets" minOccurs="0">
          <xs:complexType>
            <xs:sequence>
              <xs:element name="configuration_set" minOccurs="0" maxOccurs="unbounded">
                <xs:complexType>
                  <xs:sequence>
                    <xs:element name="configurations">
                      <xs:complexType>
                        <xs:sequence>
                          <xs:element name="configuration" maxOccurs="unbounded">
                            <xs:complexType>
                              <xs:sequence>
                                <xs:element name="value" maxOccurs="unbounded" />
                              </xs:sequence>
                            </xs:complexType>
                          </xs:element>
                        </xs:sequence>
                      </xs:complexType>
                    </xs:element>
                  </xs:sequence>
                  <xs:attribute name="name" type="xs:string" use="required" />
                  <xs:attribute name="space_id" type="xs:string" use="required" />
                </xs:complexType>
              </xs:element>
            </xs:sequence>
          </xs:complexType>
        </xs:element>
        <xs:element name="calculation" minOccurs="0">
          <xs:complexType>
            <xs:sequence>
              <xs:choice minOccurs="0" maxOccurs="unbounded">
                <xs:element name="join">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="between" maxOccurs="unbounded">
                        <xs:complexType>
                          <xs:attribute name="quanta" type="xs:string" />
                          <xs:attribute name="quantb" type="xs:string" />
                        </xs:complexType>
                      </xs:element>
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="join_eff">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="between" maxOccurs="unbounded">
                        <xs:complexType>
                          <xs:attribute name="quanta" type="xs:string" />
                          <xs:attribute name="quantb" type="xs:string" />
                        </xs:complexType>
                      </xs:element>
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="push">
                  <xs:complexType>
                    <xs:attribute name="name" type="xs:string" />
                  </xs:complexType>
                </xs:element>
                <xs:element name="minimize" />
                <xs:element name="minimize_eff" />
                <xs:element name="pop" />
                <xs:element name="duplicate" />
                <xs:element name="print" />
                <xs:element name="store">
                  <xs:complexType>
                    <xs:attribute name="name" type="xs:string" />
                  </xs:complexType>
                </xs:element>
                <xs:element name="abstract">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="quant" maxOccurs="unbounded" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="hide">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="quant" maxOccurs="unbounded" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="aggregate">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="quant" maxOccurs="unbounded" />
                      <xs:element name="name" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="product" />
                <xs:element name="prodcons">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="producer_quant" />
                      <xs:element name="consumer_quant" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="prodcons_eff">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="producer_quant" />
                      <xs:element name="consumer_quant" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
                <xs:element name="rename_quant">
                  <xs:complexType>
                    <xs:sequence>
                      <xs:element name="from" />
                      <xs:element name="to" />
                    </xs:sequence>
                  </xs:complexType>
                </xs:element>
              </xs:choice>
            </xs:sequence>
          </xs:complexType>
        </xs:element>
      </xs:sequence>
    </xs:complexType>
  </xs:element>
</xs:schema>

Style Sheet

For visualization of such specifications, there is a style sheet transformation that turns the xml file into an xhtml visualization.

https://www.es.ele.tue.nl/pareto/xml/paretospec.xslt

Links

The MIT licensed open source basic Pareto Calculator ^[4] is available on github:
https://github.com/TUE-EE-ES/ParetoCalculator

The GPL licensed symbolic Pareto Calculator ^[5] is available on github:
https://github.com/TUE-EE-ES/ParetoAlgebraLib

References

1. Marc Geilen and Twan Basten (2007): A Calculator for Pareto Points. In: 2007 Design, Automation Test in Europe Conference Exhibition, pp. 1-6, 2007.
2. Marc Geilen and Twan Basten and Bart Theelen and Ralph Otten (2007): An Algebra of Pareto Points. In: Fundam. Inf., vol. 78, no. 1, pp. 35–74, 2007, ISSN: 0169-2968.
3. Hamid Shojaei and Twan Basten and Marc Geilen and Phillip Stanley-Marbell (2008): SPaC: A Symbolic Pareto Calculator. In: Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, pp. 179–184, Association for Computing Machinery, Atlanta, GA, USA, 2008, ISBN: 9781605584706.
4. Marc Geilen and Twan Basten (2007): A Calculator for Pareto Points. In: 2007 Design, Automation Test in Europe Conference Exhibition, pp. 1-6, 2007.
5. Hamid Shojaei and Twan Basten and Marc Geilen and Phillip Stanley-Marbell (2008): SPaC: A Symbolic Pareto Calculator. In: Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, pp. 179–184, Association for Computing Machinery, Atlanta, GA, USA, 2008, ISBN: 9781605584706.

Selected Related Publications

@inproceedings{SBGS08,

title = {SPaC: A Symbolic Pareto Calculator},

author = {Hamid Shojaei and Twan Basten and Marc Geilen and Phillip Stanley-Marbell},

url = {https://doi.org/10.1145/1450135.1450176},

doi = {10.1145/1450135.1450176},

isbn = {9781605584706},

year  = {2008},

date = {2008-01-01},

urldate = {2008-01-01},

booktitle = {Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},

pages = {179–184},

publisher = {Association for Computing Machinery},

address = {Atlanta, GA, USA},

series = {CODES+ISSS '08},

abstract = {The compositional computation of Pareto points in multi-dimensional optimization problems is an important means to efficiently explore the optimization space. This paper presents a symbolic Pareto calculator, SPaC, for the algebraic computation of multidimensional trade-offs. SPaC uses BDDs as a representation for solution sets and operations on them. The tool can be used in multi-criteria optimization and design-space exploration of embedded systems. The paper describes the design and implementation of Pareto algebra operations, and it shows that BDDs can be used effectively in Pareto optimization.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{GB07,

title = {A Calculator for Pareto Points},

author = {Marc Geilen and Twan Basten},

doi = {10.1109/DATE.2007.364605},

year  = {2007},

date = {2007-01-01},

urldate = {2007-01-01},

booktitle = {2007 Design, Automation Test in Europe Conference Exhibition},

pages = {1-6},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}