# EECS 219B Spring 2002 - University of Texas at Austin

Logic Synthesis Multi-Level Logic Synthesis Courtesy RK Brayton (UCB) and A Kuehlmann 1 Basic Model: Hardware Implementing Finite State Machines Y=(y1,y2,,yn) X=(x1,x2,,xn) S=(s1,s2,,sn)

D S=(s1,s2,,sn) M(X,Y,S,S0,,): X: Inputs Y: Outputs S: Current State S0: Initial State(s) : X S S (next state function) : X S Y (output function) Delay element: Clocked: synchronous

single-phase clock, multiple-phase clocks Unclocked: asynchronous 2 General Logic Structure Combinational optimization keep latches/registers at current positions, keep their function optimize combinational logic in between Sequential optimization change latch position/function 3 Optimization Criteria for Synthesis 1. 2.

3. 4. 5. 6. 7. The optimization criteria for multi-level logic is to minimize some function of: Area occupied by the logic gates and interconnect (approximated by literals = transistors in technology independent optimization) Critical path delay of the longest path through the logic Degree of testability of the circuit, measured in terms of the percentage of faults covered by a specified set of test vectors for an approximate fault model (e.g., single or multiple stuck-at faults) Power consumed by the logic gates Noise immunity Placeability, Wireability

Manufacturability while simultaneously satisfying upper or lower bound constraints placed on these physical quantities 4 Example: Area-Delay Trade-off 5 Two-Level (PLA) vs. Multi-Level E.g. Standard Cell Layout PLA Multi-level Logic control logic constrained layout

highly automatic technology independent multi-valued logic input, output, state encoding Very predictable all logic general (e.g. standard cell, regular blocks,..) automatic partially technology independent some ideas part of multi-level logic Very hard to predict 6 General Approaches to Synthesis PLA Synthesis: theory well understood

predictable results in a top-down flow Multi-Level Synthesis: optimization criteria very complex except niches, no general theory available greedy optimization approach incrementally improve along various dimensions of the criteria works on common design representation (circuit or network representation) attempt a change, accept if criteria improves, otherwise reject 7 Transformation-based Synthesis all modern synthesis systems are build that way set of transformations that change network representation work on uniform network representation script of scenario that can combine those transformations to a

overall greedy transformations differ in: the scope they are applied local scope versus global restructuring the domain they optimize combinational versus sequential timing versus area technology independent versus technology dependent the underlying algorithms they use BDD based, SAT based, structure based 8 Network Representation Boolean network: directed acyclic graph (DAG) node logic function representation fj(x,y) node variable yj: yj= fj(x,y)

edge (i,j) if fj depends explicitly on yi Inputs x = (x1, x2,,xn ) Outputs z = (z1, z2,,zp ) External dont cares d1(x), d2(x) ,, dp(x) 9 Typical Synthesis Scenario RTL to Network Transformation - read Verilog - control/data flow analysis Technology independent Optimizations - basic logic restructuring

- crude measures for goals Technology Mapping Technology Dependent Optimizations Test Preparation - use logic gates from target cell library - timing optimization - physically driven optimizations - improve testability - test logic insertion 10 Local versus Global Transformations

Local transformations optimize the function of one node of the network smaller area faster performance map to a particular set of cells Global transformations restructure the entire network merging nodes spitting nodes removing/changing connections between nodes Node representation: SOP, POS BDD

Factored forms keep size bounded to avoid blow-up of local transformations 11 Sum of Products (SOP) Example: abc+abd+bd+bef (sum of cubes) Advantages: easy to manipulate and minimize many algorithms available (e.g. AND, OR, TAUTOLOGY) two-level theory applies Disadvantages: Not representative of logic complexity. For example f=ad+ae+bd+be+cd+ce f=abc+de These differ in their implementation by an inverter. hence not easy to estimate logic; difficult to estimate progress during logic manipulation

12 Reduced Ordered BDDs like factored form, represents both function and complement like network of muxes, but restricted since controlled by primary input variables not really a good estimator for implementation complexity given an ordering, reduced BDD is canonical, hence a good replacement for truth tables for a good ordering, BDDs remain reasonably small for complicated functions (e.g. not multipliers) manipulations are well defined and efficient true support (dependency) is displayed 13

Factored Forms Example: (ad+bc)(c+d(e+ac))+(d+e)fg Advantages good representative of logic complexity f=ad+ae+bd+be+cd+ce f=abc+de f=(a+b+c) (d+e) in many designs (e.g. complex gate CMOS) the implementation of a function corresponds directly to its factored form good estimator of logic implementation complexity doesnt blow up easily Disadvantages not as many algorithms available for manipulation hence often just convert into SOP before manipulation 14

## Recently Viewed Presentations

• Specifications are subject to change without notice. Panasonic System NetworksPBX SE team . Document for Technical Training
• What are biomedical research methods? An integrated approach using chemical, mathematical and computer simulations, in vitro tests, whole animal models, and human epidemiological studies and clinical trials is currently the best approach to advance science, develop new products and drugs,...
• Engineering Hydrology (ECIV 4323) Instructors: Dr. Yunes Mogheir Dr. A-Majid Nassar CHAPTER FOUR Stream flow measurement Surface water hydrology deals with the movement of water a long earth's surface as a result of precipitation and snow melt Knowledge of quantity...
• Note that each packet contains a packet number, message number, and destination. * Identify the principal components of telecommunications networks and key networking technologies. Identify the different types of networks. Describe how the Internet and Internet technology work and how...
• Lorsque la source originale contient une faute, inclure la correction entre crochets. Ne pas utiliser « [sic] » à moins d'avoir une raison particulière de vouloir signaler l'erreur. Pour mettre l'accent sur une partie d'une citation, la mettre en italique...
• Splashing in the puddles, the thunderstorm cooled Jayanti's hot feet. Splashing in the puddles left by the thunderstorm, Jayanti cooled her hot feet. Splashing in the puddles left by the thunderstorm, the cool water refreshed Jayanti's hot feet. Splashing in...
• Operációs Rendszerek Gyakorlati jegyzet Összeállította: Rodek Lajos Szegedi Tudományegyetem Képfeldolgozás és Számítógépes Grafika Tanszék
• B. Pemeriksaan Fisik Nystagmus : adalah gerakan bola mata yang sifatnya involunter, bolak balik, ritmis, dengan frekuensi tertentu . Nystagmus merupakan bentuk reaksi dari reflex vestibulo oculer terhadap aksi tertentu .