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 [1] is available on github:
https://github.com/TUE-EE-ES/ParetoCalculator
The GPL licensed symbolic Pareto Calculator [3] is available on github:
https://github.com/TUE-EE-ES/ParetoAlgebraLib
Selected Related Publications
-
![[DOI]](https://computationalmodeling.info/wp/wp-content/plugins/papercite/img/external.png)
M. Geilen and T. Basten, “A calculator for pareto points,” in 2007 design, automation test in europe conference exhibition, 2007, pp. 1-6.
[Bibtex]@InProceedings{GB07, author = {Geilen, Marc and Basten, Twan}, booktitle = {2007 Design, Automation Test in Europe Conference Exhibition}, title = {A Calculator for Pareto Points}, year = {2007}, pages = {1-6}, doi = {10.1109/DATE.2007.364605}, } - H. Shojaei, T. Basten, M. Geilen, and P. Stanley-Marbell, “Spac: a symbolic pareto calculator,” in Proceedings of the 6th ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2008, p. 179–184.
[Bibtex]@InProceedings{SBGS08, author = {Shojaei, Hamid and Basten, Twan and Geilen, Marc and Stanley-Marbell, Phillip}, booktitle = {Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis}, title = {SPaC: A Symbolic Pareto Calculator}, year = {2008}, address = {New York, NY, USA}, pages = {179–184}, publisher = {Association for Computing Machinery}, 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.}, doi = {10.1145/1450135.1450176}, isbn = {9781605584706}, keywords = {pareto algeba, binay decision diagram, embedded systems}, location = {Atlanta, GA, USA}, numpages = {6}, url = {https://doi.org/10.1145/1450135.1450176}, }
References
[1] M. Geilen and T. Basten, “A calculator for pareto points,” in 2007 design, automation test in europe conference exhibition, 2007, pp. 1-6.
[Bibtex]
M. Geilen and T. Basten, “A calculator for pareto points,” in 2007 design, automation test in europe conference exhibition, 2007, pp. 1-6. [Bibtex]
@InProceedings{GB07,
author = {Geilen, Marc and Basten, Twan},
booktitle = {2007 Design, Automation Test in Europe Conference Exhibition},
title = {A Calculator for Pareto Points},
year = {2007},
pages = {1-6},
doi = {10.1109/DATE.2007.364605},
}[2] M. Geilen, T. Basten, B. Theelen, and R. Otten, “An algebra of pareto points,” Fundam. inf., vol. 78, iss. 1, p. 35–74, 2007.
[Bibtex]
[Bibtex]
@Article{GBTO07,
author = {Geilen, Marc and Basten, Twan and Theelen, Bart and Otten, Ralph},
journal = {Fundam. Inf.},
title = {An Algebra of Pareto Points},
year = {2007},
issn = {0169-2968},
month = {jan},
number = {1},
pages = {35–74},
volume = {78},
address = {NLD},
issue_date = {January 2007},
numpages = {40},
publisher = {IOS Press},
url = {https://dl.acm.org/doi/10.5555/2366476.2366479},
}[3] H. Shojaei, T. Basten, M. Geilen, and P. Stanley-Marbell, “Spac: a symbolic pareto calculator,” in Proceedings of the 6th ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2008, p. 179–184.
[Bibtex]
H. Shojaei, T. Basten, M. Geilen, and P. Stanley-Marbell, “Spac: a symbolic pareto calculator,” in Proceedings of the 6th ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2008, p. 179–184. [Bibtex]
@InProceedings{SBGS08,
author = {Shojaei, Hamid and Basten, Twan and Geilen, Marc and Stanley-Marbell, Phillip},
booktitle = {Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},
title = {SPaC: A Symbolic Pareto Calculator},
year = {2008},
address = {New York, NY, USA},
pages = {179–184},
publisher = {Association for Computing Machinery},
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.},
doi = {10.1145/1450135.1450176},
isbn = {9781605584706},
keywords = {pareto algeba, binay decision diagram, embedded systems},
location = {Atlanta, GA, USA},
numpages = {6},
url = {https://doi.org/10.1145/1450135.1450176},
}