University of Illinois at Urbana Champaign Dept of Electrical and Computer Engineering ECE 120 Introduction to Computing Optimizing Logic Expressions We Can Use Logical Completeness to Express Functions Let the truth table to the right define the function F Recall that we can use the logical completeness construction to write F as a Boolean expression This row is And this is And this is AB C ABC ABC A B C F 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 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 What s the Best Way to Write Function F Your Answer Is Wrong Choose a Metric First So F AB C ABC ABC But we can also write F AB AC What about F A B C Which one is best A B C F 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 The answer depends on our choice of metric How do we measure good Common answers for circuit design OR area size cost performance speed OR power energy consumption OR complexity reliability 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 1 27 2018 1 We Use Heuristics for These Metrics An Area Heuristic for ECE120 In practice measuring exactly is expensive 50 100M for a full design and 2 5M just for trying something Instead we use heuristics which are ways of estimating a metric A good heuristic is reasonably accurate and monotonic relative to a real measurement so that bigger estimates mean bigger measurements Here s a heuristic for area Count literals A A B B C C then Add the number of operations not including complements for literals Why does it work Remember gate structures each input literal two transistors operators into operators two transistors So it gives an approximate transistor count But wires also take space ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 5 ECE 120 Introduction to Computing 2016 2017 Steven S Lumetta All rights reserved slide 6 A Delay Speed Heuristic for ECE120 A Graphical View May Make Counting Easier Here s a heuristic for delay speed Find the maximum number of gates between any input and any output Do not include complements for literals Why does it work Each gate takes time switch its output on off We call this time a gate delay So it gives an approximate delay between inputs changing and outputs changing F AB C ABC ABC Number of literals is 9 Delay on all paths is 2 Number of operators gates is 4 Ignore these inverters for now ECE 120 Introduction to Computing 2016 2017 Steven S Lumetta All rights reserved slide 7 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 8 1 27 2018 2 Let s Analyze the Second Form of F Let s Analyze the Third Form of F F AB AC Number of literals is 4 F A B C Number of literals is 3 Number of operators gates is 3 Delay on all paths is 2 Number of operators gates is 2 Delay on longest paths is 2 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 The Area Heuristic Favors F A B C All Forms Are Equivalent in Delay Let s calculate the area heuristic for our three forms of F So F A B C is the smallest design Form of F Lits Ops Area AB C ABC ABC AB AC A B C 9 4 3 4 3 2 13 7 5 All designs are the same for delay Form of F Lits Ops Area Delay AB C ABC ABC 9 AB AC A B C 4 3 2 13 7 5 4 3 2 2 2 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 11 ECE 120 Introduction to Computing 2016 2017 Steven S Lumetta All rights reserved slide 12 1 27 2018 3 We Have a Winner F A B C F A B C is best by both metrics But the answers are not always so simple Sometimes no solution is best by both metrics See Section 2 1 1 for a simple example Later in our class we will explore more space time tradeoffs in design In practice tradeoffs are commonplace Take a look at Section 2 1 6 for more What About Power and Complexity These two metrics are beyond our class scope You ll see power in ECE385 One heuristic for power uses the fact that current flows when a transistor switches on off and uses simulation to estimate the number of times that happens Complexity is hard to measure and is usually based on experience ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 13 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 14 1 27 2018 4