PAL is an algorithm designed to quickly predict the Pareto-optimal solutions in a multi-objective design space. This is a particularly useful when measuring the target objectives given a design point is expensive, and therefore only a few samples of the design space should be drawn for measurement.

All our work on learning for optimization and autotuning.

The challenge of multi-objective design spaces is that rather than having a single optimal solution, several solutions may simultaneously optimize the target objective functions.

A concrete example in the domain of hardware design, are the design spaces generated by the Spiral DFT and sorting network hardware generators, when exploring the different settings provided by the tool. The user needs to choose between different candidate designs that perform the same task but that trade differently throughput and area. This challenge is aggravated by the fact that evaluating each design is extremely expensive, since complex synthesis processes must be executed. Thus, it is impractical and sometimes infeasible to evaluate every possible design in order to find the Pareto-optimal solutions that maximize throughput and minimize area at the same time.

Having drawn a few samples of the design space, PAL builds models using Gaussian processes to predict the objective functions for the rest of the space. Given these predictions and their corresponding uncertainties, PAL speculatively classifies designs as Pareto-optimal or not Pareto-optimal. Training samples are smartly selected until all points can be classified with the desired accuracy. This accuracy can be specified with the parameter epsilon. More details can be found in [1,2]. An illustrative example of an iteration of the PAL is shown below.

The implementation of PAL that is provided here is written in Matlab, and uses the GPML libraries written by Carl Edward Rasmussen and Chris Williams [3]. PAL can be used for any number of objective functions, however this implementation is limited to two objective functions.

In the plots below we show that different accuracy/training-cost tradeoffs can be obtained by varying the value of the parameter epsilon. Accuracy in predicting the Pareto front of a design space is measured using the logarithmic hypervolume error. The plots only show the errors obtained with the objective function 1.

The plots also show the effect of choosing epsilon on the termination of PAL. A larger epsilon causes PAL to stop earlier. Design spaces used are based on data sets obtained in [4], [5] and [6].

We compare the efficiency of PAL with that of the evolutionary algorithm ParEGO [7]. These results show that PAL in almost all cases significantly improves over ParEGO.

A detail explanation of these experiments can be found in [1].

- Marcela Zuluaga, Andreas Krause, Guillaume Sergent and Markus Püschel
**Active Learning for Multi-Objective Optimization**

to appear in Proc. International Conference on Machine Learning (ICML), 2013 - Marcela Zuluaga, Andreas Krause, Peter A. Milder and Markus Püschel
**"Smart" Design Space Sampling to Predict Pareto-Optimal Solutions**

Proc. Languages, Compilers, Tools and Theory for Embedded Systems (LCTES), pp. 119-128 , 2012

- Marcela Zuluaga, Peter A. Milder, and Markus Püschel

**Computer Generation of Streaming Sorting Networks**

Proc. Design Automation Conference (DAC), 2012 - Carl Edward Rasmussen and Christopher K. I. Williams

**Gaussian Processes for Machine Learning**

The MIT Press, 2006 - Oscar Almer, Nigel Topham, and Björn Franke

**Learning-Based Approach to the Automated Design of MPSoC Networks**

Proc. Architecture of Computing Systems (ARCS), 2011 - N. Siegmund, S. S. Kolesnikov, C. Kastner, S. Apel, D. Batoryx, M. Rosenmuller, and G. Saake

**Predicting Performance via Automated Feature-Interaction Detection**

Proc. Int'l Conference on Software Engineering (ICSE), 2012 - J. Knowles

**ParEGO: a Hybrid Algorithm with Online Landscape Approximation for Expensive Multiobjective Optimization Problems**

IEEE Trans. on Evolutionary Computation, 2006

Contact: Marcela Zuluaga <firstname.lastname@inf.ethz.ch>