Unformatted text preview:

1Copyright © 2000 K. Keutzer1Technology Dependent Logic OptimizationProf. Kurt KeutzerEECSUniversity of CaliforniaBerkeley, CAThanks to S. DevadasKurt Keutzer2RTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibraryphysicaldesignlayoutabsq01dclkabsq01dclkModuleGeneratorsManualDesign2Copyright © 2000 K. KeutzerKurt Keutzer3Logic OptimizationPerform a variety of transformations and optimizations– Structural graph transformations– Boolean transformations– Mapping into a physical librarysmaller, fasterless powerlogicoptimizationnetlistnetlistLibraryabsq01dclkabsq01dclkKurt Keutzer4Combinational Logic OptimizationInput: • Initial Boolean network• Timing characterization for the module• - input arrival times and drive factors• - output loading factors• Optimization goals• - output required times• Target library descriptionOutput:• Minimum-area net-list of library gates which meets timing constraintsA very difficult optimization problem !3Copyright © 2000 K. KeutzerKurt Keutzer5Modern Approach to Logic OptimizationDivide logic optimization into two subproblems:– • Technology-independent optimization• - determine overall logic structure• - estimate costs (mostly) independent of technology• - simplified cost modeling– • Technology-dependent optimization (technology mapping)• - binding onto the gates in the library• - detailed technology-specific cost modelOrchestration of various optimization/transformation techniques for each subproblemKurt Keutzer6Logic OptimizationlogicoptimizationnetlistnetlistLibrarytechindependenttechdependent2-levelLogic optmultilevelLogic optLibraryTimingConstraints4Copyright © 2000 K. KeutzerKurt Keutzer7“Closed Book” Technology LibraryA standard cell technology or library may contain many hundreds of cellsTypical cells are NAND, NOR, NOT, AOI (AND-or-Invert), OAI (Or-And-Invert) etc. AAACABAB+CBCAKurt Keutzer8LibraryContains for each cell:– Functional information: cell = a *b * c– Timing information: function of• input slew• intrinsic delay• output capacitancenon-linear models used in tabular approach– Physical footprint (area)– Power characteristicsWire-load models - function of– Block size– WiringLibrary5Copyright © 2000 K. KeutzerKurt Keutzer9Elements of a library - 1INVERTER 2NAND2 3NAND3 4NAND4 5Element/Area CostKurt Keutzer10Elements of a library - 2AOI21 4AOI22 5Element/Area Cost6Copyright © 2000 K. KeutzerKurt Keutzer11Reasonable LibraryInverter, BufferND2-ND4; NOR2-NOR4; AND2- AND4; AOI21 - AOI333; OAI21 - OAI333XOR, XNORMUX, Full AdderNeg-Edge Triggered D-Flip-FlopPos-Edge Triggered D-FFJ-K FFAbove with various clears, enables Scan versions of each of the aboveMost of the above in 6 different power sizes:– 1x, 2x, 4x, 6x, 8x, 16xKurt Keutzer12Input Circuit Netlist``subject DAG’’7Copyright © 2000 K. KeutzerKurt Keutzer13Problem statementinto the technology library (simple example below):Find an ``optimal’’ (in area, delay, power) mapping of a circuitKurt Keutzer14Is there a problem? Trivial Covering #1subject DAG7 NAND2 (3) = 215 INV (2) = 10Area cost 318Copyright © 2000 K. KeutzerKurt Keutzer15Covering #22 INV = 42 NAND2 = 61 NAND3 = 41 NAND4 = 5Area cost 19Kurt Keutzer16Covering #31 INV = 21 NAND2 = 32 NAND3 = 81 AOI21 = 4Area Cost 17Costs:31, 19, 17Yes, there’s a problem!9Copyright © 2000 K. KeutzerKurt Keutzer17History of the Problem - 1Technology mapping in 1986 was a big problem• Almost every design group (e.g. AT&T) had their own library – ASIC – 400 cells– Microprocessor/DSP – 200 base cells– Government – 200+ cells• Every group had their own approach to mapping– ``Do what you have to do!’’ – handcrafted mappers tied to particular libraries and optimization tools– ``Rule-based’’ systems – e.g. GE Socrates – very slow ``expert systems’’ that made no guarantee on final quality of resultKurt Keutzer18History of the Problem - 2Yes, there are two problems:– Technology mapping can significant affect the area, speed, and power dissipation of a circuit – There are over 200 different semiconductors each with multiple internal libraries – how to create a tool that can utilize a diverse set of libraries??10Copyright © 2000 K. KeutzerKurt Keutzer19A similar problem – code generationExample of code generation in compilers using tree-covering• Handles complex instruction sets  Handles complex libraries• Easily portable to other instruction sets  Easily portable to Kurt Keutzer20Problem Formulation: DAG CoveringRepresent input netlist in normal form⇒⇒⇒⇒ subject DAGRepresent each library gate with normal forms for the logic function⇒⇒⇒⇒ primitive DAGsEach primitive DAG has a costGoal: Find a minimum cost covering of the subject DAG by the primitive DAGsNormal form: 2-input NAND gates and invertersK. Keutzer, DAGON: Technology Binding and Local Optimization by DAG Matching, in Proceedings of the24th Design Automation Conference, 1987 and 25 Years of Design Automation11Copyright © 2000 K. KeutzerKurt Keutzer21Step 1: Extract Combinational LogicBFlip-flopsCombinationalLogicSince FF’s don’t need to be optimized with surrounding combinational logic we can partition them outinputsoutputsKurt Keutzer22Step 2: Normalize Circuit Netlist``subject DAG’’Reduce the netlist into ND2 gates12Copyright © 2000 K. KeutzerKurt Keutzer23Step 3a: Normalize libraryINVERTER 2NAND2 3NAND3 4NAND4 5Element/Area Cost Tree Representation (normal form)Kurt Keutzer24Step 3b: Normalize libraryAOI21 4AOI22 5Element/Area CostTree Representation (normal form)13Copyright © 2000 K. KeutzerKurt Keutzer25Sound Algorithmic approachNP-hard optimization problemTree covering heuristic: If subject and primitive DAGs are trees, efficient algorithm can find optimum cover ⇒⇒⇒⇒ dynamic programming formulationStep 4: DAG Coveringmultiple fanoutK. Keutzer, D. Richards, Computation Complexity of Logic Synthesis and Optimization, in Proceedings of theInternational Workshop on Logic Synthesis, 1989Kurt Keutzer26Solution formulation1) Partition input netlist into forest of trees2) Solve each tree optimally using tree covering3) Stitch trees back together14Copyright © 2000 K. KeutzerKurt Keutzer27Resulting TreesBreak at multiple fanout pointsKurt Keutzer28For each tree - Dynamic ProgrammingPrinciple of optimality: Optimal cover for a tree consists of a best match at the root of the


View Full Document
Download Technology Dependent Logic Optimization
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 Technology Dependent Logic Optimization 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 Technology Dependent Logic Optimization 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?