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 Cost Tree Representation (normal form)Kurt Keutzer10Elements of a library - 2AOI21 4AOI22 5Element/Area CostTree Representation (normal form)6Copyright © 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 Keutzer14History 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• Everybody had their own approach– ``Do what you have to do!’’ – handcrafted mappers tied to particular libraries and optimization tools– ``Rule-based’’ systems – e.g. GE Socrates – slow ``expert systems’’ that made no guarantee8Copyright © 2000 K. KeutzerKurt Keutzer15Reduce to Combinational OptimizationBFlip-flopsCombinationalLogicSince FF’s don’t need to be optimized with surrounding combinational logic we can partition them outinputsoutputsKurt Keutzer16Is there a problem? Trivial Coveringsubject DAG7 NAND2 (3) = 215 INV (2) = 10Area cost 319Copyright © 2000 K. KeutzerKurt Keutzer17Covering #12 INV = 42 NAND2 = 61 NAND3 = 41 NAND4 = 5Area cost 19Kurt Keutzer18Covering #21 INV = 21 NAND2 = 32 NAND3 = 81 AOI21 = 4Area Cost 1710Copyright © 2000 K. KeutzerKurt Keutzer19History 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??Kurt Keutzer20A similar problem – code generationExample of code generation in compilers using tree-covering11Copyright © 2000 K. KeutzerKurt Keutzer21Problem 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 AutomationKurt Keutzer22Sound Algorithmic approachNP-hard optimization problemTree covering heuristic: If subject and primitive DAGs are trees, efficient algorithm can find optimum cover ⇒ dynamic programming formulationDAG Coveringmultiple fanoutK. Keutzer, D. Richards, Computation Complexity of Logic Synthesis and Optimization, in Proceedings of theInternational Workshop on Logic Synthesis, 198912Copyright © 2000 K. KeutzerKurt Keutzer23Solution formulation1) Partition input netlist into forest of trees2) Solve each tree optimally using tree covering3) Stitch trees back togetherKurt Keutzer24Resulting TreesBreak at multiple fanout points13Copyright © 2000 K. KeutzerKurt Keutzer25For each tree - Dynamic ProgrammingPrinciple of optimality: Optimal cover for a tree consists of a best 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, zChoose leastcost tree-coverat rootK. Keutzer, DAGON: Technology Binding and Local Optimization by DAG Matching, in Proceedings of the24th Design Automation Conference, 1987Kurt Keutzer26Example of Optimal Tree CoveringNAND23AOI214 + 3 = 7INV11 + 2 = 13NAND22 + 6 + 3 = 11NAND23 + 3 = 6NAND23INV214Copyright © 2000 K. KeutzerKurt Keutzer27DAG covering in detail1) partition DAG into