1Two-level Logic Optimization, Part 2ECE 474a/575aSusan Lysecky2of 14Exact Algorithm vs. Heuristics• Quine-McCluskey Calculated all prime implicants to derive the optimal solution(s) Petrick’s Method derives all covers to determine minimum cover set(s)  Number of prime implicants grow quickly -- solution space is huge! Finding the minimum cover set in a class of NP complete problems• Determining optimal solution is difficult• Move to heuristics Look at generating a quality solution quickly (not necessarily optimal)ECE 474a/575aSusan Lysecky3of 14Logic Optimization Techniques• Logic Optimization Techniques K-maps (Graphical) Quine-McCluskey (Exact Algorithm) Espresso (Heuristic)• Other Generalized Heuristics Branch-and-bound Simulated Annealing Dynamic Programming many more exists …zeECE 474a/575aSusan Lysecky4of 14Local Search• Don’t generating all prime implicants and minterms• Instead, ESPRESSO successively modify a given initial cover This technique is called a local searchalgorithm• Idea behind local search Search space or solution space - set of all possible values and cost associated with solution Start with an initial value Search all points in neighborhood for a feasible point whose cost is less than current• Different problems have different neighborhood definitions If one is found, start process overcost of a solutionpossible solutionsxF(x)ECE 474a/575aSusan Lysecky5of 14Local Search• Drawback of local searches is local optimality Solution is locally optimal if its neighborhood does not contain any solutions with a lower cost Locally optimal solution may not be the optimal solution• Modify local search so we don’t get stuck at the local minimumF(x)xlocal minimumglobal/absolute minimumECE 474a/575aSusan Lysecky6of 14Espresso• Espresso utilizes local search (keeping in mind local minimum problem)• Composed of three main operations EXPAND, REDUCE, IRREDUNDANT• Espresso Heuristic (in a nutshell) Apply Expand and Irredundant operators to optimize the current function specification Uses the reduce operator to get out of local minimum This is iterated till the solution convergesECE 474a/575aSusan Lysecky7of 14Espresso – Expand Operator• EXPAND Deleting one (or more) of its literals Check for validity010000 01 11 10000111Fbcaab010000 01 11 10000111Fbcaabc010000 01 11 10000111Fbcabc010000 01 11 10000111FbcaabcExpand abc by removing c (results in ab)Is it valid? Yes.Expand abc by removing c (results in ab)Is it valid? No.ECE 474a/575aSusan Lysecky8of 14Espresso – Expand Operator• Goal is to expand a non-prime implicants to prime with the least number of literals110100 01 11 1010010XFbcaa’b’c’Expand a’b’c’ by removing a’Is it valid? Yes.110100 01 11 1010010XFbcab’c’Expand b’c’ by removing b’Is it valid? Yes.110100 01 11 1010010XFbcac’c’ is an prime implicantECE 474a/575aSusan Lysecky9of 14Espresso – Reduce Operator• REDUCE Adding one or more literals Check for validity111100 01 11 10000111Fbcaa’b’111100 01 11 10000111Fbcaa’111100 01 11 10000111Fbcaa’c111100 01 11 10000111Fbcaa’Reduce a’ by adding b’ (results in a’b’)Is it valid? Yes.Reduce a’ by adding c (results in ac)Is it valid? Yes.ECE 474a/575aSusan Lysecky10 of 14Espresso – Reduce Operator• Goal is to decrease the size of implicants such that expansion may lead to a better solution Avoiding a local minimum011100 01 11 10110101Fyzxx’z x’yxy’ xz’Reduce x’y to x’yz’No implicant can be expandedIs it valid? Yes.011100 01 11 10110101Fyzxx’z x’yz’xy’ xz’Is it valid? Yes.Reduce xz’ to xyz’Is it valid? Yes.Expand x’yz’ to yz’011100 01 11 10110101Fyzxx’zxy’ yz’F = x’z + yz’ + xy’Reduction helped find a better solution!011100 01 11 10110101Fyzxx’z x’yz’xy’ xyz’ECE 474a/575aSusan Lysecky11 of 14Espresso – Irredundant Operator• IRREDUNDANT Implicant in a cover is redundant if all the minterms covered by it are contained in other implicants in the coveryz’ is redundantx’y and xz’ cover all minterms contained in yz’011100 01 11 10110101Fyzxx’zx’yxy’yz’xz’011100 01 11 10110101Fyzxx’zx’yxy’xz’ECE 474a/575aSusan Lysecky12 of 14Espresso – Irredundant Operator• Irredundant cover is not the same as minimal cover011100 01 11 10110101Fyzxx’zx’yxy’xz’011100 01 11 10110101Fyzxx’zxy’yz’irredundant coverirredundant coverminimal coverECE 474a/575aSusan Lysecky13 of 14Espresso – Additional Concerns• Additional concerns Validity check operations Which direction should the move make?• Methods outlined in the heuristic We will not cover these010000 01 11 10000111Fbcaab010000 01 11 10000111Fbcaabc010000 01 11 10000111Fbcabcwhich way should we expand?011100 01 11 10110101Fyzxx’zx’yxy’yz’xz’which implicant should we reduce?which literal should we add?ECE 474a/575aSusan Lysecky14 of 14Espressoespresso(F,D) {R = complement(F U D); F = expand(F,R); // initial expansionF = irredundant(F,D); // initial irredundant coverE = essentials(F,D); // detect essential prime implicantsF = F – E; // remove prime implicants from fD = D U E; // add essential prime implicants to Drepeat {φ1= |F |; F = reduce(F,D); F = expand(F,R); F = irredundant(F,D);} until (|F | ≥ φ1); F = F U E; D = D – E;RETURN F;}repeated application of REDUCE, EXPAND, IRREDUNDANT operations while cost keeps decreasingF is the on-set, D is the don’t care