1VLSI CAD Flow: Logic Synthesis, Placement and Routing6.375 Lecture 5Guest Lecture by Srini Devadas2RTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibrary/modulegeneratorsphysicaldesignlayoutmanualdesignabsq01dclkabsq01dclk3Two-Level 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 representation– Solved problem even for functions with 100’s of inputs (variants of Quine-McCluskey)4Two-Level versus Multilevel2-Level:6 product terms which cannot be shared.24 transistors in static CMOSMulti-level:Note that B + C is a common term in f1 and f2K = B + C 3 Levels20 transistors in static CMOSnot counting invertersf1=AB+AC+ADf2=AB+AC+AEf1=ΑΚ+ADf2=AK+AE5Technologies“Closed book”: gate-arraystandard-cell“Open book”: CMOS Domino,complex gate static CMOSLOGIC EQUATIONSTECHNOLOGY-INDEPENDENTOPTIMIZATIONFactoringCommonality ExtractionLIBRARYTECH-DEPENDENT OPTIMIZATION(MAPPING, TIMING)OPTIMIZED LOGIC NETWORK6Tech.-Independent OptimizationInvolves:Minimizing two-level logic functions.Finding common subexpressions.Substituting one expression into another.Factoring single functions.Factored versus Disjunctive formssum-of-products or disjunctive formfactored formmulti-level or complex gatef=ac+ad+bc+bd+aef=a+b()c+d()+ae7OptimizationsFactor FExtract common expressionF=f1=AB+AC+AD+AE+ABC D Ef2=AB+AC+AD+AF+ABC DF⎧⎨⎩F=f1=AB+C+D+E()+ABCDEf2=AB+C+D+F()+ABC DF⎧⎨⎩G=g1=B+C+Df1=Ag1+E()+AE g1f2=Ag1+F()+AF g1⎧⎨⎩⎪8What Does “Best” Mean?Transistor count AREANumber of circuits POWERNumber of levels DELAY(Speed)Need quick estimators of area, delay and powerwhich are also accurate9Algebraic vs. Boolean MethodsAlgebraic techniques view equations as polynomials and attempt to factor equations or “divide” themDo not exploit Boolean identities e.g., a a = 0In algebraic substitution (or division) if a function f = f(a, b, c) is divided by g = g(a, b), a and bwill notappear in f / gAlgebraic division: O(n log n) timeBoolean division: 2-level minimization required10Algebraic factorization proceduresBoolean factorization producesAlgebraic substitution of l into r failsBoolean substitutionComparisonf=ab+ac+ba+bc+ca+cbf=ab+c()+ab+c()+bc+cbf=a+b+c()a+b+c()l=bf+bf()a+e()+aeb f+bf()r=bf+bf()a+e()+ae bf+bf()r=ael+el()+ael+el()l=aer+er()+aer+er()11Given a function f to be strong divided by gAdd an extra input to f corresponding to g, namely G and obtain function h as followsMinimize h using two-level minimizerStrong (or Boolean) DivisionhON=fON−hDChDC=Gg+Gg12Strong Division Examplef=abc+abc +abc +a b cg=ab+ab1xxxx11xxxx10001111000 011110bcGaMinimization gives h = G c + G cFunction hhDC= G (a b + a b) + G (a b + a b)hON= fON−hDC13Weak (or Algebraic) DivisionDefinition: support of f as sup( f ) = { set of all variables v that occur in f as v or v }Example: f = A B + Csup( f ) = { A, B, C }Definition: we say that f is orthogonal to g,f ⊥ g, if sup( f ) ∩ sup( g ) =φExample: f = A + B g = C + D∴ f ⊥ g since { A, B } ∩ { C, D } =φ14Weak Division - 2We say that g divides f weakly if there exist h, rsuch that f = gh + r where h ≠φand g ⊥ hExample: f = ab + ac + dg = b + cf = a(b + c) + d h = a r = dWe say that g divides f evenly if r =φThe quotient f / g is the largest h such thatf = gh + r i.e., f = ( f / g )g + r15Weak Division Examplef = abc + abde + abh + bcdg = c + de + hTheorem: f / g = f / c ∩ f / de ∩ f / hf / c = ab + bdf / de = abf / h = abf / g = (ab + bd) ∩ ab ∩ ab = abf = ab(c + de + h) + bcdTime complexity: O( | f | | g | )16How to Find Good Divisors?$64K questionStrong division: Use existing nodes in the multilevel network to simplify other nodesWeak division: Generate good algebraic divisors using algorithms based on “kernels” of an algebraic expression17Tech.-Dependent OptimizationArea, delay and power dissipation cost functionsOPTIMIZED LOGIC EQUATIONSTECHNOLOGY MAPPINGGATENETLISTLIBRARYTIMINGCONSTRAINTS18“Closed Book” TechnologiesA standard cell technology or library is typically restricted to a few tens of gatese.g., MSU library: 31 cellsGates may be NAND, NOR, NOT, AOIs.AAACABAB+CBCA19Mapping via DAG CoveringRepresent network in canonical form⇒ subject DAGRepresent each library gate with canonical forms for the logic function⇒ primitive DAGsEach primitive DAG has a costGoal: Find a minimum cost covering of the subject DAG by the primitive DAGsCanonical form: 2-input NAND gates and inverters20Sample LibraryINVERTER 2NAND2 3NAND3 4NAND4 521Sample Library - 2AOI21 4AOI22 522Trivial Coveringsubject DAG7 NAND2 = 215 INV = 103123Covering #12 INV = 42 NAND2 = 61 NAND3 = 41 NAND4 = 51924Covering #21 INV = 21 NAND2 = 32 NAND3 = 81 AOI21 = 41725Sound Algorithmic approachNP-hard optimization problemTree covering heuristic: If subject and primitive DAGs are trees, efficient algorithm can find optimum cover in linear time⇒ dynamic programming formulationDAG Coveringmultiple fanout26Partitioning a Graph27Resulting TreesBreak at multiple fanout points28Dynamic ProgrammingPrinciple of optimality: Optimal cover for a tree consists of a match at the root of the tree plus the optimal cover for the sub-trees starting at each input of the matchxyzpBest cover forthis match usesbest covers forx, y, zBest cover forthis match usesbest covers forp, z29Optimum Tree CoveringNAND23AOI214 + 3 = 7INV11 + 2 = 13NAND22 + 6 + 3 = 11NAND23 + 3 = 6NAND23INV2RTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibrary/modulegeneratorsphysicaldesignlayoutmanualdesignabsq01dclkabsq01dclkPhysical Design: Overall Conceptual FlowRead NetlistInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingInputPlacementRoutingOutputCompaction/clean-upRouting RegionOrderingDetailed RoutingCost EstimationRoutingImprovementWrite Layout DatabaseFloorplanningFloorplanning3Kurt KeutzerResults of PlacementA bad placementA good placementA. KahngWhat’s good about a good placement?What’s bad about a bad placement?4Kurt KeutzerResults of PlacementBad placement causes routing congestion resulting in:• Increases in circuit area (cost) and wiring• Longer wires Æ more capacitancez Longer delayz Higher dynamic power dissipationGood placement•Circuit area
View Full Document