University of Illinois at Urbana Champaign Dept of Electrical and Computer Engineering ECE 120 Introduction to Computing Pareto Optimization What s Best When We Have Several Metrics As engineers you will rarely have the luxury of a single metric How does one choose between metrics Imagine the following You are working as an intern designing hardware to execute DNNs deep neural networks which may be useful in a variety of tasks ECE 120 Introduction to Computing 2016 2017 Steven S Lumetta All rights reserved slide 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 2 Example Compare Designs Based On Area and Delay Which Metric is More Important Building on your ECE120 knowledge you have two metrics Area which you have normalized from 1 to 100 Delay which you have also normalized from 1 to 100 In both metrics smaller is better For a design X A X is the area and D X is the delay Now imagine that you have two designs X and Y How do you choose between them Which is more important area or delay ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 3 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 4 3 4 2018 1 The Answer Depends on How the Design is Used One Option is to Combine Metrics Numerically The answer depends on the context in which your design is used datacenter laptop mobile phone car or other vehicle space probe children s toy How do you make a choice One option linearize Pick some weights actually one weight W is enough W is the relative importance of delay compared to area Then for each design X calculate M X A X W D X Choose the design with the smallest M X ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 5 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 6 Relative Importance is Not Easy to Choose in Practice Remember Dilbert Oxygen is Good But how do you pick W What if you need designs for ALL of those applications As an engineer you may not be in a position to know the right weights So what can you do if you don t know the relative importance of the metrics For two designs probably just report both to your manager What if you have created 10 000 designs Not by hand but by using parameters For example does your design provide hardware for 8 bit 16 bit 32 bit or 64 bit addition Do you report all 10 000 to your manager Probably not if you want a job offer But what can you do ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 7 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 8 3 4 2018 2 A Design that is Worse in All Metrics is Pareto Dominated Eliminate Designs that are Pareto Dominated by Others Pick two designs X and Y What if A X A Y AND D X D Y Remember that smaller is better for both area and delay In such a case do you need to report Y No X is better in both metrics We say that design Y is Pareto dominated by design X If there were N metrics Y must be worse than some X in ALL metrics to be Pareto dominated You can use the idea of Pareto domination to eliminate designs Any design that is Pareto dominated by any other design can be discarded Only designs that may be better in some context remain The remaining designs form a Pareto curve a Pareto surface for more than two metrics ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 9 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 10 A Graph Illustrates Pareto Dominance Small is Good A Pareto Curve after Discarding Dominated Points All Possible Designs Pareto Curve 100 90 80 70 60 50 40 30 20 10 0 dominated by point P P 100 90 80 70 60 50 40 30 20 10 0 P 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 11 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 12 3 4 2018 3 Use of Pareto Curves Surfaces is Common Want to Learn More about Optimization In many hardware design environments engineers run design space exploration tasks on computers of course Given a set of parameters for a design Generate hardware for each possible combination of parameters Then use Pareto dominance to trim the results down And show the engineer the Pareto surface of area delay and power consumption Take ECE490 some day Combines theory and practice optimization algorithms Implementations use of libraries to solve problems ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 13 ECE 120 Introduction to Computing 2017 Steven S Lumetta All rights reserved slide 14 3 4 2018 4