VLSI & Adv Digital Dsgn
VLSI & Adv Digital Dsgn ECE 3060
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 0 page Class Notes was uploaded by Cassidy Effertz on Monday November 2, 2015. The Class Notes belongs to ECE 3060 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/233907/ece-3060-georgia-institute-of-technology-main-campus in ELECTRICAL AND COMPUTER ENGINEERING at Georgia Institute of Technology - Main Campus.
Reviews for VLSI & Adv Digital Dsgn
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
ECE 3060 VLSI and Advanced Digital Design Lecture 12 ComputerAided Heuristic Twolevel Logic Minimization ComputerAided Heuristic Two level Logic Minimization Heuristic logic minimization Principles Operators on logic covers Espresso Heuristic minimization 0 Provide irredundant covers with reasonably small cardinality 0 Fast and applicable to many functions 0 Avoid bottlenecks of exact minimization Prime generation and storage Covering Heuristic minimization principles 0 Local minimum cover given initial cover make it prime make it irredundant Iterative improvement improve on cardinality by modifying the implicants Heuristic minimization operators Expand make implicants prime remove covered implicants Reduce reduce size of each implicant while preserving cover Reshape modify implicant pairs enlarge one implicant enabling the reduction of another Irredundant make cover irredundant on set 0000 0010 0100 0110 1000 1010 0101 0111 1001 1011 1101 1 1 1 1 1 1 1 1 1 1 1 Example prime implicants OO gtxlt00 01 10 101 gtquot101 yAyAyAyAyAyA 5 Lgtww ll MIMI MilNIH Jquot l a wng Example Expansion Expand 0000 to or 00 drop 0100 0010 0110 from the cover Expand 1000 to B gt 00 drop 1010 from the cover Expand 0101 to y 01 lt drop 0111 from the cover Expand 1001 to 5 10 lt drop 1011 from the cover Expand 1101 to a 101 Cover is ocBy5e EzigggzaA All 1 Example reduction Reduce OO to nothing Reduce B gt ltOgt ltO to E 000 Reduce e 101 to 1101 Cover is y5 IHIIHWMMWIIHHmum En i M E y mm m l u quotVan sx Example reshape 39 Reshape 95 to B 0 Where 101 39 COVGI iS BM Example second expansion Expand 101 t0 5 10 lt Expand 1101 to Q gt 101 r mm Summary of Example Expansion Cover ocBy58 prime redundant minimal wrto single cube containment Reduction oc eliminated B OO reduced to E 000 8 101 reduced t0 1101 Cover y5 Reshape 5 reshaped to 3 where 101 Second expansion cover Bay sag prime irredundant minimal Expand naive implementation For each implicant for each non literal care literal raise it to don 2 care if possible remove all covered implicants 0 Problems check validity of expansion 2 ways non intersection of expanded implicant with OFFset requires complementation of ONset expanded implicant covered by union of ONset and DCset 0 can be reduced to recursive tautology check order of expansions Heuristics 0 First expand cubes which are unlikely to be covered by other cubes Selection choose implicants with least number of literals in common with other implicants Example f a b c d ab cd a b c d choose ab cd 0 Choose expansions to cover the largest number of minterms possible gt prime implicant Reduce Example Expanded cover Select 0c cannot be reduced and still cover the ON set Select 3 reduced to B 001 Reduced cover 0c 1 B 001 Irredundant Cover Relatively essential set Er implicants covering some minterms 0f the function not covered by other implicants Totally redundant set Rt implicants covered by the relatively essentials Partially redundant set Rp remaining implieants Irredundant cover goal and example Goal nd a subset of Rp that together with Er covers the function Example 3 28 lll e 10 Er 0L 8 Rt RP B9 5 Example continued 0 Covering relations B is covered by oc y y is covered by 3 5 5 is covered by y 8 0 Minimum cover y U Er Espresso Algorithm Compute the complement Extract essentials Iterate expand irredundant reduce Cost functions cover cardinality 01 weighed sum of cube and literal count 02 Espressomw Espresso algorlthm R complementF U D F expandF R F irredundantF D E essentia1sF D F F E D D U E repeat 02 costF repeat 01 F reduceF D F expandF R F irredundantF D until F 2 01 F lastgaspF D R until costF 2 02 FFUE DDE F makesparseF D R ECE 3060 VLSI and Advanced Digital Design Lecture 16 Technology MappingLibrary Binding Outline Modeling and problem analysis Rulebased systems for library binding Algorithms for library binding structural coveringmatching boolean coveringmatching Concurrent minimization and binding Technology MappingLibrary Binding 0 Given an unbound logic network already minimized and a set of library cells transform into an interconnection of instances of library cells various design goals optimize area under delay constraints optimize delay under area constraints optimize power under delay constraints 0 Method used for redesigning circuits in different technologies Library models 0 Combinational elements singleoutput functions eg AND OR AOI compound cells eg adders encoders Sequential elements registers counters 0 Miscellaneous threestate drivers Maj or Approaches Rulebased systems mimic designer activity handle all types of cells 0 Heuristic algorithms In general restricted to singleoutput combinational cells 0 Most tools use a combination of both rule based and heuristic algorithms e g replace adders in design with adders in library rulebased use heuristic algorithms for random logic Rulebased library binding 0 Binding by stepwise transformations 0 Database set if patterns associated with best implementation 0 Rules select subnetwork to be mapped handle highfanout problems buffering etc Example Algorithms for library binding 0 Mainly for singleoutput combinational cells 0 Fast and ef cient quality comparable to rulebased systems 0 Library descriptionupdate is simple each cell modeled by its function or equivalent pattern Problem analysis 0 To do library binding technology mapping we need to solve two subproblems Matching a cell matches a subnetwork if their terminal behaviors are the same inputvariable assignment problem Covering a cover of an unbound network is a partition into subnetworks which can be replaced by library cells Assumptions 0 Network granularity is ne decomposition into base functions 2input AND OR NAND NOR Trivial binding replacement of each vertex by base cell Example wxy xbc Example Library 0051 3 c zxd 13 AND2 4 N b u m1 v10R2 m2 V2AND2 m3 v3AND2 m4 v1 v20A21 m5 v1 v30A21 Example 0 Vertex covering cover V12m1 m4 m5 cover V22 m2 m4 cover V32 m3 m5 0 Note that match m2 requires m1 match m3 requires m1 0 This problem is intractable Heuristic algorithms Strategy apply two preprocessing steps before covering decomposition and partitioning Decomposition cast network and library in standard form decompose into base functions example NANDZ and INV Partitioning break network into cones transform network from multipleinput multipleoutput to many mutipleinput singleoutput subnetworks Covering cover each subnetwork by library cells Decomposition EN daial lm 1 oning t i IGG 433 Part Covering Structural matching and covering 0 Expression patterns represented by dags 0 Identify pattern dags in network subgraph isomorphism Simpli cation use tree patterns Example 3 30 oo 0 900000 o 90 Treebased matching Network partitioned and decomposed NOR2 or NAND INV generic base functions each cone is called a subject tree Library represented by trees possibly more than one tree per library cell 0 Can solve library binding problem with pattern recognition simple binary tree match Disclaimer lecture notes based on originals by Giovanni De Micheli Simple library l1V MN MW NANDZ I1N1v ANm I1N1v I1N111V Nom I1N211 V N1I1 V N2I1v 0R2 w 3 a b c gw I1N1N1V I1N1N2v I1N2HV I1N1l1 V I1N2N1V I1N2N2v I1N1N1V I1N1N2V I1N2N1V I1N2N2v t3 1 13932 Tree covering Dynamic programming visit subject tree from the bottom up from the input variables up 0 At each vertex attempt to match locally rooted subtree all library cells 0 Optimum solution e g to minimize area for the subtree Example SUBJ ECTTREE PATTERN TREES r t1 12 t3 t4 5 t T O O u 0 0 cost 2 cost 3 cost 4 cost 5 INV NAND AND OR Example Mlkh HQ l1 I M CHI WM Wit I1 quotWQ MIMI DI HIE MIl4l M dlolr l M5II Tree covering labeling 0 For all vertices in the subject tree the covering algorithm determines matches between locally rooted subtrees and pattern trees 0 Three possible conditions for any vertex and a given pattern tree the cell tree and the rooted subtree are isomorphic the vertex is labeled with the cell cost the cell tree is isomorphic to a subtree with leaves L the vertex is labeled with the cell cost plus the labels of the vertices L there is no match cannot happen when the base functions are in the library Example of labeling 0 Goal minimum area cover 0 Area costs INV2 NAND2z3 AND2z4 A0121 6 0 Best Choice found A0121 fed by a NANDZ gate Example Ne EWOVk SUbJ39eCt graph Vertex Match Gate Cosi x t2 NAND2bc 3 y H NVa 2 2 f2 NAND2xd 2 3 6 W 1392 NAND2V 3 3 2 11 0 quot WWW 332213 r3 Anna 2342 12 65 A0I21xda 3 6 IE Minimum delay cover Dynamic programming approach 0 Cost related to gate delay Delay modeling constant gate delay straightforward load dependent delay constant load dependent term load fanout unknown for most libraries values of input capacitance are nite and small therefore can use binning techniques where we label each vertex with all possible load values Minimum delay cover constant delays 0 Same labeling rules as the minimum area case 0 If the cell pattern tree and the rooted subtree are isomorphic the vertex is labeled with the cell delay 0 If the cell tree is isomorphic to a subtree With leaves L each leaf already labeled the vertex is labeled with the cell cost plus the maximum of the labels of L Example Inputs are all ready at time 0 except for d which arrives at time 6 Constant delays INV2 NAND2z4 AND2z5 AOIlelO Compute label for each vertex from the bottom up labels t are dataready times tx4 ty2tZ4tw2 Best Choice ANDZ two NANDZ and INV Example Ne EWOI k 3U biect graph Vertex Match Gate Cost x 12 NAND2bc 4 y 11 IMVa 2 2 t2 NAND2xd 6 4 10 w 2 NANDZvz 10 4 14 0 quot WWW 142 16 t3 ANDZyz 10 5 El 63 A0I21xda 10616 Minimum delay cover load dependent delays 0 Model assume a nite set of load values 0 Dynamic programming approach compute an array of solutions for each possible load for each input to a matching cell the best match for any load is selected 0 Optimum solution when all possible loads are considered Example Input dataready times are 0 except for rd 6 Loaddependent delays load at output INV1 E NAND223E AND224E A0121 29E Loads for use with l INV1NAND21AND21A01211 If output load is also 1 the we nd the same solution as before Example Input dataready times are 0 except for rd 6 Add super inverter to library larger area less delay Loaddependent delays INV 1 2 NAND223E AND24 A012129 SINV1O5 Loads INV1NAND21AND21A01211 SINV2 Assume output load is l same solution as before Assume output load is 5 solution uses SINV cell ECE 3060 VLSI and Advanced Digital Design Lecture 15 MultipleLevel Logic Minimization Outline Multilevel Circuit representations Minimization methods goals area delay power algorithms algebraic boolean rulebased methods Examples of transformations Boolean and algebraic models Disclaimer lecture notes based on originals by Giovanni De Micheli Motivation Multiple level networks Semicustom libraries Advantages of gates versus macros PLA more exible better performance 0 might want to minimize certain paths Applicable to a variety of designs Circuit modeling Logic network interconnection of logic functions hybrid structuralbehavioral model Bound mapped gates interconnection of logic gates structural model Example of a bound network ZEEX c q y lt 9 6 6 Q Q Q Logic equations of example adbcbde cqc c dbdcdae V NKltgtlt ltCHUJWFQU CHM Example of network Example circuit output function a dbdc dac a39b39ccdc acadbcbdc abc N ltgtlt Network optimization Minimize area power estimate subject to delay constraints Minimize maximum delay subject to area power constraints Maximize testability Minimize power Estimation Area number of literals in MOS literals poly strips number of functions gates Delay number of stages most often used metric re ned gate delay models sensitizable paths paths for which there are conditions under which a signal propagates through the path Problem analysis Multiplelevel optimization is hard Exact methods exponential complexity impractical die on reasonably sized networks Approximate heuristic methods algorithms which explore part of exact soln space rulebased methods replacement of subcircuits by other subcircuits Strategies for minimization Improve Circuits step by step circuit transformations Preserve network behavior Methods differ in types of transformations selection and order of transformations Example elimination Eliminate one function from the network Perform variable substitution Example srUrpa gtspa39b39 Example elimination Example decomposition Break one function into smaller ones Introduce new vertices in the network Example Va39dbdc39dae39 gtja39bc39 vjdae39 Example decomposition vidae E Example extraction Find a common subexpression of two or more expressions Extract subexpression as new function Introduce new vertex in the network Example pcede tacadbcbde p0d t0dab gtkcd pketkakbe Example extraction tkakbe EI uq 6qc qc y El Example simpli cation Simplify a local function Example uq39cqc39qc gtuqc Example simpli cation 2 9 AA 391 x Example subsitution Simplify a local function by using an additional input that was not previously in the function s support set Example t ka kb e gt t kq e because q a b Example substitution tkakbe EI uq 6qc qc y El Example outcome sequence of transformations jabd kcd qab skeaU tkqe uqc vjdae I vjdae EI skea b 2I Ikqe 1I uqc IEI Minimization approaches Algorithmic approach de ne an algorithm for each transformation type algorithm is an operator on the network Rulebased approach ruledata base set of pattern pairs pattern replacement driven by rules Algorithmic approach Each operator has wellde ned properties heuristic methods still used weak optimality properties Sequence of operators de ned by scripts based on experience Example elimination algorithm Set a threshold k usually 0 k corresponds to the maximum area or power or delay increase allowed Examine all expressions Eliminate expressions if the increase in literals does not exceed the threshold goal reduce the number of logic expressions Example elimination algorithm ELIMINATE GVE k repeat vx selected vertex with value lt k if vx empty vertex return replace x by fx in the network Example MIS SIS rugged script sweep eliminate l simplify m noeomp eliminate l sweep eliminate 5 simplfy m noeomp resub a fX resub a sweep eliminate l sweep fullsimplify m noeomp Algebraic Division f quotient fdividend fdivisor When gtllt fdividend fdivisor fquotient fremainder fdivisor fquotient O the literals 0f fdivisor are disjoint from the literals Of fquotient Note if fremamder 0 then fdivisor is called a is said to factor f factor and fd quotient iVisor De nitions Cubefree expression cannot be factored by a cube implicant Kernel of an expression cubefree quotient of the expression divided by a cube the cube used for division is called a co kernel Kernel set K09 of an expression set of kernels Example facebcedeg Divide f by a Get 6 Not cube free Divide f by I Get 6 Not cube free Divided f by 6 Get aebe Not cube free Divide f by 6 Get ab Cube free Kernel Divide f by d Get 6 Not cube free Divide f by 6 Get acbcd Cube free Kernel Divide f by g Get 1 Not cube free Expression f is a kernel of itself because cube free K09 ab acbcd acebcedeg Example yad bd cdege The literals are a b c d e g Try all combinations of literals There eXists a recursive function for calculating kernels very fast we won39t cover this recursive function Example use kernel computation to implement extraction y adbdcdege Steps I calculate Kx 2 calculate Ky 3 calculate Kz 4 if there are some kernels in common perform extraction with largest kernel largest of cubes break tie by choosing largest of literals Boolean and algebraic methods Boolean methods exploit properties of logic functions use don39t care conditions complex at times Algebraic methods View functions as polynomials eXploit properties of polynomial algebra simpler faster but weaker Example Boolean substitution habcdeqacd gt h a bq e becauseabqeabacdea bed e Algebraic substitution t ka kb e gt t kq e because q a b