DOC PREVIEW
MIT 6 375 - Logic Synthesis, Placement and Routing

This preview shows page 1-2-3-4-5-33-34-35-36-66-67-68-69-70 out of 70 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 70 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 375 - Logic Synthesis, Placement and Routing

Documents in this Course
IP Lookup

IP Lookup

15 pages

Verilog 1

Verilog 1

19 pages

Verilog 2

Verilog 2

23 pages

Encoding

Encoding

21 pages

Quiz

Quiz

10 pages

IP Lookup

IP Lookup

30 pages

Load more
Download Logic Synthesis, Placement and Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logic Synthesis, Placement and Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logic Synthesis, Placement and Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?