1Two-level Logic Optimization, Part 3ECE 474a/575aSusan Lysecky2of 23Logic 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 …ze• Very general algorithm – can be applied to a variety of problems• Based on the idea of a decision tree Varies in that it tries to visit only part of the treeECE 474a/575aSusan Lysecky3of 23Decision Trees• Decision tree Enumeration approach in which we have n decision variables, and list the 2npossible valueszeEssential prime implicants: w’yz’, x’y’z079156813(2,6)0-10(9, 13)10-1(8,9)-001(6,7)011-(13, 15)1-11(7, 15)-111Previous example – we derived a prime implicant chart and the corresponding essential prime implicants. How do we derive a minimum cover with the remaining prime implicants?ECE 474a/575aSusan Lysecky4of 23Decision TreesP2P1P4P3079156813(2,6) 0-10(9, 13) 10-1(8,9) -001(6,7) 011-(13, 15) 1-11(7, 15) -111Remove the essential prime implicants, they are already in the cover.Number the remaining prime implicants so it’s easier for us to read.Let’s start our decision tree. What are the decision to make?Should we include P1 in our cover?Should we include P2 in our cover?Should we include P3 in our cover?Should we include P4 in our cover?10P1P2P21010P3 P3 P3 P31010 1010P4 P4 P4 P4P4 P4 P4 P41010 10101010 1010ECE 474a/575aSusan Lysecky5of 23Decision Trees10P2P2P1P4 P4 P4 P4P4 P4 P4 P4P3 P3 P3 P310101010 10101010 10101010 1010The leaves are your possible solutionsCover = P1, P2, P3, P4Valid? yes, Cost = 4Cover = P1Valid? noCover = P2, P3, P4Valid? yes, Cost = 3Cover = P2, P3Valid? yes, Cost = 2Cover = P1, P4Valid? yes, Cost = 2Cover = P3, P4Valid? yes, Cost = 2Cover = noneValid? noECE 474a/575aSusan Lysecky6of 23Branch-and-bound Idea• Branch-and-bound Several optimal solutions may exist, we only need to find one Idea is that maybe we only have to visit part of the decision tree If we can estimate the low bound to a subtree, and that low bound is higher than the current minimum, we don’t need to look at that subtreec cb0101010c170555c130610 8costkilled subtreelow bound = 4current minimum = 301ba1ECE 474a/575aSusan Lysecky7of 23Generic Branch-and-bound PseudocodeBRANCH_AND_BOUND{Current_best= anythingCurrent_cost= infinityS= s0while( S≠ 0 ) do {Select an element in sSRemove sfrom SMake a branch based on syielding sequences {si, i=1, 2, …, m}for ( i=1 to m){Compute the lower bound of biof siif( bi>= Current_cost){Kill si}else{if( sicorresponds to a complete solution ){Current_best= siCurrent_cost= cost of si}else{Add sito set S}}}}}zeKeeps track to the best solution we came up with and it’s corresponding costWhile we have decisions to make, keep goingIf low bound less than current minimum, keep searching the subtreeChoose a decision, and make a branch corresponding to all possible values of the decisionIf lower bound higher than the minimum we’ve seen so far, ignore the subtreeIf low bound is less than the current minimum and it’s a solution – we found a new minimum solution!Calculate the lower bound on the subtreeECE 474a/575aSusan Lysecky8of 23Branch-and-bound – Example 1• Let’s look at the minimum cover problem againm1 m3m2 m4P1P3P6P2P5P4Current_best = anythingCurrent_cost = infinity1. Initialize current_best and current_cost variables10P12. Choose a decision (P1) and branch corresponding to all possible values of that decision (1 – include in cover, 0- don’t include in cover)lower bound b = ?3. Calculate lower bound on subtreeECE 474a/575aSusan Lysecky9of 23Branch-and-bound – Lower Bound Calculation• How do I calculate the lower bound of a subtree? Varies depending on your problem• Minimum cover problem lower bound = number of prime implicants included so far + MIS  Maximally Independent Set (MIS)• Equal to the number of independent rows in the table• Indicates the lowest possible number of prime implicants required to cover the remaining minterms We want worst case, so we pick the set with the highest number of prime implicants If no two independent rows, MIS = 2 (this is a theorem proved in your Hatchel book – thm 4.8.1)m1 m3m2 m4P1P3P6P2P5P4Rows are independent if no overlapping X’sMIS = 2{P1, P2}{P3, P4}{P5, P6}ECE 474a/575aSusan Lysecky10 of 23Branch-and-bound – Example 1b = 1 + 2 b = 3• Minimum cover problemm1 m3m2 m4P1P3P6P2P5P410P12. Choose a decision (P1) and branch corresponding to all possible values of that decision (1 – include in cover, 0- don’t include in cover)3. Calculate lower bound on subtree1. Initialize current_best and current_cost variablesCurrent_best = anythingCurrent_cost = infinitylower bound = number of prime implicants included so far + MISMIS = 2 because {P3, P4} or {P5, P6} are the largest independent setsP1 is no longer considered in calculating MIS because we’ve already made a decision to include/don’t include itECE 474a/575aSusan Lysecky11 of 23Branch-and-bound – Example 110P1b = 3m1 m3m2 m4P1P3P6P2P5P4Current_best = anythingCurrent_cost = infinity4. Is lower bound >= current_cost? No.5. Do we have a complete solution? No.6. Let’s look at another prime implicantECE 474a/575aSusan Lysecky12 of 23Branch-and-bound – Example 110P1b = 3m1 m3m2 m4P1P3P6P2P5P42. Calculate lower bound on subtree3. Is lower bound >= current_cost? No.1. Choose a decision variable and list the possible decision values10P2Current_best = anythingCurrent_cost = infinitycurrent_best = solutioncurrent_cost = cost of solutionCurrent_best = P1, P2Current_cost = 2We can keep looking until we’ve eliminated or explored all paths –but 2 is the optimal solution so we stop4. Do we have a complete solution? Yes.Solution : {P1, P2}Cost : 2b = 4P1, P2 are ignoredMIS = 2 because the largest set is {P3, P4} or {P5, P6}ECE 474a/575aSusan Lysecky13 of 23Branch-and-bound – Example 2• Let’s look at another minimum cover problem Yes, there are essential prime implicants in the table Normally we remove these first – I’ve left them there for illustrative purposesm1 m3m2 m4 m5 m6P1P2P3P43. Calculate lower bound on subtree4. Is lower bound >= current_cost? No.5. Do we have a complete solution? No.6. Let’s look at another prime implicant2. Choose a decision variable and list decision valuesP110MIS = 3, {P2, P3, P4}lower bound = 1 +