EDA(CS286.5b)

1、EDA (CS286.5b)Day 15Logic Synthesis:Two-Level1TodayTwo-Level Logic OptimizationProblemDefinitionsBasic Algorithm: Quine-McCluskyImprovements2ProblemGiven: Expression in combinational logicFind: Minimum (cost) sum-of-products expressionEx.Y=a*b*c + a*b*/c + a*/b*cY=a*b + a*c3EDA UseMinimum size PAL,

2、PLA, Minimum number of gates for two-level implementationStarting point for multi-level optimization4ComplexitySet covering problemNP-hard5CostPLA/PAL - first ordernumber of product termsAbstract (mis)number of literalscost(y=a*b+a*/c )=4General (simple, multi-level)cost(product-term)e.g. nand2=4, n

3、and3=5,nand4=66Terminology (1)Literals - a, /a, b, /b, . Qualified, single inputsMinterms - full set of literals covering one input casein y=a*b+a*ca*b*ca*/b*c7Terminology (2)Cube:product covering one or more mintermsY=a*b+a*ccubes:a*b*c abca*b aba*c ac8Terminology (3)Cover: set of cubes sum product

4、sabc, a/bc, ab/cab,ac9Truth TableAlso represent functiona b c y0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1a b c y1 0 1 11 1 0 11 1 1 1Specify on-set only10Cube/Logic SpecificationCanonical order for variablesUse 0,1,- to indicate input appearance in cube0 - inverted abc 1111 - not inver

5、ted a/bc 101- - not present ac 1-1a b c y1 0 1 11 1 0 11 1 1 11 - 1 11 1 - 11 0 1 11 1 0 11 1 1 11 - 1 1 1 -11In GeneralThree sets:on-set (must be set to one by cover)off-set (must be set to zero by cover)dont care set (can be zero or one)Dont Cares allow freedom in covering (reduce cost)arise from

6、cases where value doesnt mattere.g. outputs in non-existent FSM state data bus value when not driving bus12Multiple Outputsa b y x0 0 1 10 1 0 01 0 0 01 1 0 1a b y x o0 0 1 - 10 0 - 1 10 1 0 - 10 1 - 0 11 0 0 - 11 0 - 0 11 1 0 - 11 1 - 1 1Truth Table:Convert to single-output problemOn-set for result

7、001-00-1010 -01- 0100 -10- 0110 -11- 113Multiple OutputsCan reduce to single output casewrite equations on inputs and each outputwith onset for relation being trueafter cover remove literals associated with outputs14Prime ImplicantsImplicant - cube in on-set (not entirely in dont-case set)Prime Impl

8、icant - implicant, not contained in any other cubefor y=a*b+a*ca*b is a prime implicanta*b*c is not a prime implicant (contained in ab, ac)I.e. largest cube still in on-set (on+dc-sets)15Prime ImplicantsMinimum cover will be made up of primesless products if cover moreless literals in prime than con

9、tained cubesNecessary but not sufficient that minimum cover be primesy=ab+ac+b/cy=ac+b/cNumber of PIs can be exponential in input sizemore than minterms, even!16Essential Prime ImplicantsPrime Implicant which contains a minterm not covered by any other PIEssential PI must occur in any covery=ab+ac+b

10、/cab 11- 110 111 ac 1-1 101 111 * essential (only 101)b/c -10 110 010 * essential (only 010)17Computing PrimesStart with minterms for on-set and dc-setmerge pairs (distance one apart)for each pair merged, mark source cubes as coveredrepeat merging for resulting cube setuntil no more merging possible

11、retain all unmarked cubes which arent entirely in dc-set18Compute Prime Example 0 0000 5 0101 7 0111 8 1000 9 100110 101011 101114 111015 1111 19Compute Prime Example 0 0000 5 0101 7 0111 8 1000 9 100110 101011 101114 111015 1111 0, 8 -000 5, 7 01-1 7,15 -111 8, 9 100- 8,10 10-0 9,11 10-110,11 101-1

12、0,14 1-1011,15 1-1114,15 111- 20Compute Prime Example 0 0000 5 0101 7 0111 8 1000 9 100110 101011 101114 111015 1111 0, 8 -000 5, 7 01-1 7,15 -111 8, 9 100- * 8,10 10-0 * 9,11 10-1 *10,11 101- *10,14 1-10 *11,15 1-11 *14,15 111- * 8, 9,10,11 10-10,11,14,15 1-1-/b/c/d/abdbcda/bac21Covering MatrixMint

13、erms x Prime Implicants /b/c/d /abd bcd a/b ac 0000 X0101 X0111 X X1000 X X1001 X1010 X X1011 X X1110 X1111 X X22Essential ReductionMust pick essential PIpick and eliminate row and column /b/c/d /abd bcd a/b ac 0000 X0101 X0111 X X1000 X X1001 X1010 X X1011 X X1110 X1111 X X23Dominators: ColumnIf a

14、column (PI) covers the same or strictly more than another column can remove dominated column B C D E F G H0101 X X0111 X X1000 X X1010 X X1110 X X1111 X X24Dominators: ColumnIf a column (PI) covers the same or strictly more than another columncan remove dominated column B C D E F G H0101 X X0111 X X

15、1000 X X1010 X X1110 X X1111 X XC dominates BG dominates H25Dominators: ColumnIf a column (PI) covers the same or strictly more than another columncan remove dominated column B C D E F G H0101 X X0111 X X1000 X X1010 X X1110 X X1111 X X C D E F G 0101 X0111 X X1000 X1010 X X1110 X X1111 X X26New Ess

16、entialsDominance reduction may yield new Essential PIs C D E F G 0101 X0111 X X1000 X1010 X X1110 X X1111 X X C D E F G 1110 X X1111 X XC,G now essentialE dominates D and FCover C,E,G27Dominators: RowIf a row has the same (or strictly more) Pis than another row, the larger row dominanteswe can remov

17、e the dominating row(NOTE OPPOSITE OF COLUMN CASE) C D E F G 0101 X0111 X X1000 X1010 X X1110 X X1111 X X0111 dominates 0101 remove 01111010 dominates 1000 remove 101028Cyclic CoreAfter applying reductionsessential column dominatorsrow dominatorsMay still have a non-trivial covering matrixHow do we

18、move forward from here?29Example A B C D E F G H0000 X X0001 X X0101 X X0111 X X1000 X X1010 X X1110 X X1111 X X30Cyclic CoreCannot select (e.g. essential) or exclude (e.g. dominated) a PI definitively.Make a guessA in coverA not in coverProceed from there31Example A B C D E F G H0000 X X0001 X X010

19、1 X X0111 X X1000 X X1010 X X1110 X X1111 X X B C D E F G H0101 X X0111 X X1000 X X1010 X X1110 X X1111 X XA in Cover:32Example A B C D E F G H0000 X X0001 X X0101 X X0111 X X1000 X X1010 X X1110 X X1111 X XA not in Cover: B C D E F G H0000 X0001 X0101 X X0111 X X1000 X X1010 X X1110 X X1111 X X33Ba

20、sic Two-Level MinimizationGenerate Prime ImplicantsReduce (essential, dominators)If not done,pick a cubebranch (back to reduce) on selected/notSave smallest34OptimizationSummarize Minterms (signature cubes)rows represent collection of minterms with same primesAvoid generating full set of PIspre-comb

21、ining dominators during generationBranch-and-bound pruningget lower bound on remaining cost of a cover by computing independent set of primes(not necessarily maximal, that would be NP-hard)35HeuristicDont backtrack when select prime for inclusion/exclusionpick cover large set of minterms/signaturesweight to select “hard” to cover signaturesGenerate reduced set of PisIterative improvement