1Copyright © 2000 K. Keutzer1Two-LevelLogic MinimizationProf. Srinivas DevadasMITProf. Kurt KeutzerProf. Richard NewtonUniversity of CaliforniaBerkeley, CA22Physical Design: Overall FlowRead NetlistInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingInputPlacementRoutingOutputCompaction/clean-upRouting RegionOrderingDetailed RoutingCost EstimationRoutingImprovementWrite Layout DatabaseFloorplanningFloorplanning2Copyright © 2000 K. Keutzer3Schematic Entry EraGiven:• Gate-level schematic entry editor• Gate-level simulator (we haven’t talked about this)• Gate level static-timing analyzer• Netlist Æ Layout flow• We can (and did) build large-scale integrated (35,000 gate) circuits• EDA vendors provided front-end tools and ASIC vendor (e.g. LSI Logic) provided back-end flow• But … It may be much more natural, and productive, to describe complex control logic by Boolean equations than by a schematic netlist of gates4For example: traffic light controllerSensorSensorFarmroadFarmroadHighwayHighway3Copyright © 2000 K. Keutzer5As a State transition diagramHighway-yellow010001STISTI/Restart001100Farmroad-greenLTI SenLTI+Sen/RestartFarmroad-yellow001010STISTI/RestartHighway-green100001LTI+SenLTI Sen/Restart Initialize/Restart6Boolean Logic Equations()BCFRRBACFRYBACFRGBCHWRBACHWYBACHWGSTIASenBALTISenARestartSTIAKJKLTISenLTISenAJBBAA=•=•==•=•=•+••+••=•===++••=4Copyright © 2000 K. Keutzer7Synthesize Logic to Implement equationsBFlip-flopsCombinationalLogicinputsoutputs8Physically Implement: AND-OR and NOR-NOR PLAsI1I2O1O2I1I2O1O2Logic increases with the number of product terms5Copyright © 2000 K. Keutzer9Early “Synthesis” FlowFSMSynthesisFSM logicSOP logicoptimizationPLAphysicaldesignlayoutHighway-yellow010001STISTI/Restar t001100Farm road -greenLTI SenLTI+Sen/RestartFarmroad-yellow001010STISTI/Rest artHighway-green100001LTI+SenLTI Sen/Restart Initialize/Rest artF1 = B + D + A C + A CI1I2O1O210Key Technology: SOP Logic MinimizationCan realize an arbitrary logic function in sum-of-products or two-level formF1 = A B + A B D + A B C D+ A B C D + A B + A B DF1 = B + D + A C + A COf great interest to find a minimum sum-of-products representation6Copyright © 2000 K. Keutzer11Definitions - 1Basic definitions:Let B = {0, 1} and Y = {0, 1, 2}Input variables: X1, X2…XnOutput variables: Y1, Y2…YmA logic function ff (or Boolean function, switching function) in n inputs and m outputs is the mapff: BnYmdon’t care – aka “X”12Definitions - 2If b ∈ Bnis mapped to a 2 then function is incompletely specified, else completely specifiedOFF-SETiBn, the set of all input valuesfor which ffi(x) = 0DC-SETiBn, the set of all input valuesfor which ffi(x) = 2⊆⊆For each output we define:ON-SETiBn, the set of all inputvalues for which ffi(x) = 1⊆7Copyright © 2000 K. Keutzer13The Boolean n-Cube, Bn14LiteralsGreen – ON-setRed – OFF-set8Copyright © 2000 K. Keutzer15Boolean Formulas16Example Boolean FunctionEXAMPLE: Truth table form of an incompletely specified functionff: B3Y2Y1: ON-SET1 = {000, 001, 100, 101, 110}OFF-SET1= {010, 011}DC-SET1= {111}X1 X2X3Y1Y20 0 0 1 10 0 1 1 00 1 0 0 10 1 1 0 11 0 0 1 01 0 1 1 21 1 0 1 11 1 1 2 19Copyright © 2000 K. Keutzer17Cube RepresentationF1 = A B + A B D + A B C D+ A B C D + A B + A B DF1 = B + D + A C + A Cminimum representation0 0 - - 10 1 - 1 10 1 0 0 11 1 1 0 11 0 - - 11 1 - 1 1-0 -- 1---1 10 - 0 - 11 - 1 - 1InputsOutputs18Operations on Logic Functions(1) Complement: f finterchange ON and OFF-SETS(2) Product (or intersection or logical AND)h = f • g or h = f ∩ g(3) Sum (or union or logical OR):h = f + g or h = f ∪ g(4) Difference h = f - g = f ∩ g10Copyright © 2000 K. Keutzer19Prime ImplicantsA cube p is an implicant of f if it does not intersect the OFF-SET of fpfON∪ fDC(or p ∩ fOFF= 0)A prime implicant of f is an implicant p such that(1) No other implicant q is such that q ⊃ pin the sense that q covers all vertices of p(2) fDC⊃ pA minterm is a fully specified implicante.g., 011, 111 (not 01-)⊆20Examples of Implicants/PrimesX1 X2X3Y10 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 2 000, 00- are implicants, but not primes ( -0- )1-1 0-011Copyright © 2000 K. Keutzer21Prime and Irredundant CoversA cover is a set of cubes C such thatC ⊇ fONandC fON∪ fDCAll of the ON-set is covered by CC is contained in the ON-set and Don’t Care SetA prime cover is a cover whose cubes are all primeimplicantsAn irredundant cover is a cover C such that removing any cube from C results in a set of cubes that no longer covers the function⊆22Minimum coversA minimum cover is a cover of minimum cardinalityTheorem: A minimum cover can always be found by restricting the search to prime and irredundant covers.Given any minimum cover C(a) if redundant, not minimum(b) if any cube q is not prime, replace qwith prime p ⊃ q and it is a minimum prime cover12Copyright © 2000 K. Keutzer23Example CoversX1 X2X3Y10 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 2 0 0 -1 0 - is a cover. Is it prime?1 1 - Is it irredundant?What is a minimum prime and irredundant cover for the function?24Example CoversX1 X2X3Y10 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 2 0 0 -1 0 - is a cover. Is it prime?1 1 - Is it irredundant?-0 -1 1 - is a cover. Is it prime?Is it irredundant?Is it minimum?What is a minimum prime and irredundant cover for the function?13Copyright © 2000 K. Keutzer25The Quine - McCluskey MethodStep 1: List all minterms in ON-SET and DC-SETStep 2: Use a prescribed sequence of steps to find all the primeimplicants of the functionStep 3: Construct the prime implicanttableStep 4: Find a minimum set of primeimplicants that cover all theminterms26Example05789101114150000010101111000100110101011111011110,85,77,158,98,109,1110,1110,1411,1514,15-000 E01-1 D-111 C100-10-010-1101-1-101-11111-8,9,10,11 10-- B10,11,14,15 1-1- AA B C D E are prime implicants14Copyright © 2000 K. Keutzer27Prime Implicant