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 Sung Lim in Fall. Since its upload, it has received 9 views. For similar materials see /class/233855/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
Chapter 2 Binary Decision Diagrams A Binary Decision Diagram BDD is a way to represent a logic function Using a BDD to represent boolean logic turns out to be fairly ef cient even for a wide range of large hundreds of inputs logic functions BDDs are applicable to many other domains such as set and relation representation formal veri cation simulatiom nite system analysis etc 21 De nitions A Directed Acyclic Graph DAG G has a vertex set V and an edge set E each edge 61 E E is directed meaning 6 has a head and a tail and nally no cycles exist in G Li B A rooted DAG tree is simply a DAG where one of the vertices has only outgoing edges and is labeled as the root Now a BDD is a tree or rooted DAG where each vertex in the DAG denotes a binary decision Furthermore we distinguish between non leaf vertices each of which has a boolean variable associated with the vertex and leaf vertices each of which has a boolean value associated with the leaf vertex either a 0 or a 139 An Ordered Binary Decision Diagram OBDD is a tree rooted DAG which has been levelized so that each level corresponds to a variable See class lecture notes for BDD and OBDD examples Of course in order to manipulate large BDDs we need a non graphical representation suitable for implementation in a computer program More speci cally we need to describe a data structure for BDD representation 14 To start a BDD is a DAG which can be represented straightforwardly with a linked list More speci cally each non leaf vertex has a pointer indewo to the variable associated with that vertex Furthermore each non leaf vertex links to two children and highw If when evaluating the BDD the boolean variable pointed to by indewo evaluates to a 039 then the BDD is evaluated by following the link to child loo3900 instead if the boolean variable pointed to by indewo evaluates to a 139 then the BDD is evaluated by following the link to child higldo Finally each leaf vertex has a value 0 or 139 In order to consider a representation for an OBDD we need rst to clarify some details with the boolean variables We assume that the 7 input variables to the BDD are x 13702 vwn Now for each vertex Uh we assume that instead evaluates to a number corresponding to the variable 20 associated with that vertex For example for vertex 3903 if the boolean variable pointed to by i71d6lt 3gt is 705 then i71d6lt 3gt 5 Finally for the case of an OBDD the requirement that the BDD be levelized can be translated into the following requirement For each vertex the following two conditions hold 1 inde u lt indewaoww and 2 inde u lt indew zighw These two conditions ensure that the OBDD has a consistent order of boolean variables down any path from the root 22 BDD Properties Each OBDD with root de nes a function f The function f is de ned by the following three rules 0 If is a leaf vertex with value 139 then f 1 o If is a leaf vertex with value 0 then f 0 o If is not a leaf vertex and indescw i then f Li flow 1 fmgfdv Note that a given function f may have many OBDDs which correspond to f in other words OBDDs are not unique Also note that the size number of 15 vertices of an OBDD depends in some cases quite strongly on the variable order 221 Cofactor and Boolean Expansion Suppose we are given a single output boolean function f 14 x2 x1 70 9041 We de ne the cofactor of f with respect to w to be the boolean function 1 de ned by setting the varilable w to be a 1 and then evaluating f In notation f1 fx1x2x11x1xn We next de ne the cofactor of f with respect to 8 to be the boolean function ff de ned by setting the varilable w to be a 0 and then evaluating f In notation ff 2 fw1w2w10w1wn With these de nitions at hand let us de ne Boole 5 theorem also know as the Shannon suspension fw1w2w1ww1 nwn ILquot ff 90 12 EXAMPLE see lecture notes 222 Reduced Ordered Binary Decision Diagrams You may notice in the examples that some OBDDs can be reduced by making sure that there are no redundant subtrees This insight can be formalized the result is known as a Reduced Ordered Binary Decision Diagram ROBDD Formally an ROBDD is de ned as follows An ROBDD is an OBDD which meets the following two criteria 1 No vertex exists which has low higld u 2 No pair of vertices u exists such that the subgraph with root u is isomorphic to the subgraph with root It turns out that an OBDD can be transformed to an ROBDD in time polynomial with respect to the number of vertices In other words there exists a constant k such the for any OBDD with any number of vertices m the OBDD can be transformed via an algorithm to an ROBDD in no more than mk steps While this is good news it is unfortunately true that the number of vertices m may be an exponential of the number of input variables it eg it could be the case that m 2 Fortunately there exist well studied algorithms for automatically con structing an ROBDD given a boolean function 1 For examples of such algorithms please reference advanced textbooks DeMicheli Hachtel 16 ECE 3060 VLSI and Advanced Digital Design Lecture 11 Binary Decision Diagrams Outline Binary Decision Diagrams BDDs Ordered OBDDs and Reduced Ordered ROBDDs Tautology check Containment check ECE 3060 Lecture 11 2 History Efficient representation of logic functions 0 Proposed by Lee and Akers Popularized by Bryant canonical form Used for Boolean manipulation Applicable to other domains 0 Set and relation representation 0 Formal verification Simulation finitesystem analysis ECE 3060 Lecture 11 3 Definitions Directed Acyclic Graph DAG vertex set V edge set E each edge has a head and tail gt a direction 0 no cycles exist in GVE Binary Decision Diagram BDD tree or rooted DAG where each vertex denotes a binary decision 0 Example F abc 0691 0 GD 1 Q cf G o 5 2 if 43 index2 a ECE 3060 Lecture 11 4 Definition of OBDD Ordered Binary Decision Diagram OBDD the tree or rooted DAG can be levelized so that each level corresponds to a variable Implementation each nonleaf vertex v has 0 a pointer indexv to a variable 0 two children lowv and highv Each leaf vertex v has a value 0 or 1 Ordering indexv lt indexlowv indexv lt indexhighv ECE 3060 Lecture 11 5 Properties of an OBDD Each OBDD with root v defines a function fquot o if v is aleafwith valuev 1 then fV 1 o if v is a leafwith valuev 0 then fV 0 o if v is nota leaf and indeXv i then fV 1 f1 WVxi fhighV OBDDs are not unique therefore a function may have many OBDDs The size of an OBDD depends on the variable order ECE 3060 Lecture 11 6 Cofactor and Boolean expansion Function fx1x2 xl xn Definition cofactor of fwith respect to xi fxi x27 on 1 Definition cofactor of f with respect to fx17 x2 0 xn Theorem Letf 8 8 Then fx1x2 xl xn Ef xlfxi ECE 3060 Lecture 11 7 Example 0 Function f abbcac Cofactors fa bcandfgl 90 Expansion f Zzfglafa Zzbcabc ECE 3060 Lecture 11 8 ROBDDs Reduced Ordered Binary Decision Diagrams have no redundant subtrees no vertex with lowv highv no pair uv with isomorphic subgraphs rooted in u and v Reduction can be achieved in time polynomial with respect to the number of vertices However the number of vertices may be exponential in the number of input variables ROBDDs can be such by construction An ROBDD is a canonical form Example OBDD c on slide 4 ECE 3060 Lecture 11 9 Features Canonical form allows us to verify logic equivalence in constant time 0 check for tautology and perform logic operations in time proportional to the graph size Drawback ROBDD graph size depends heavily on variable order ROBDD size bounds Multiplier exponential size Adders exponential to linear size Sparse logic 0 good heuristics exist to keep size small ECE 3060 Lecture 11 10 Tabular representation of ROBDDs Represent multirooted graphs multipleoutput functions multiplelevel logic forms Unique table 0 one row per vertex identifier key variable left child right child E CE 3060 Lecture 1 I I I Example Unique Table Key Identi er ariahle Left Child Right Child 6 d 1 4 5 a 4 3 4 b 1 2 3 c 1 2 ECE 3060 Lecture 11 12 Tautology Checking Check if a function is always TRUE Recursive method expand about a variable appearing both complemented in an implicant and uncomplemented in another implicant if all cofactors are TRUE then the function is a tautology if any cofactor is not a tautology ie not TRUE then the function is not a tautology A function is a tautology iff all of it s cofactors are tau tologies A function is a tautology iff all of the leaves of it s BDD are TRUE This can be accomplished by traversing the BDD E CE 3060 Lecture 11 13 Containment Checking Theorem A cover F contains an implicant 0c iff FOC is a tautology Consequence containment can be verified by comput ing the cofactor and checking if it is a tautology In general how do we compute a cofactor E CE 3060 Lecture 11 14 Cofactor Computation An arbitrary cofactor of F can be computed from a BDD of F Suppose we have an ROBDD for F and we wish to compute Fa where or H xi l39e 0c First we note that Fx x Fx so we compute the 139 j i x cofactor with respect to a product of literals by consid ering the literals one at a time Consider the cofactor wrt xi For each node at index 2 trim the BDD by removing the edge associated with 371 and move the edge associated with x1 to the parent E CE 3060 Lecture 11 15 Example Consider F abc abc a13130 Construct an ROBDD for F Is a contained in F Is 9 contained in F Is 5 contained in F ECE 3060 Lecture 11 16 Other Uses of BDDs Further uses of BDDs Can efficiently calculate complement fx1x2 xl xn xiffixlfxi Can efficiently calculate union intersection Equivalence checking E CE 3060 Lecture 11 1 7 ECE 3060 VLSI and Advanced Digital Design Lecture 13 Datapathl ALUs and Adders Datapath Floorplan registers AL U W control nus access signals sigan 0 Busses run through cells 0 Pitch is matched 0 Vdd and Gnd are run horizontally 15653060 mmLz Example Chip Floorplan 15653060 DmapthJ Transmission Gate Mux 5 51 so Note Two tgates in series do not need the internal connection between pfet and nfet E CE 3060 DatapathI 4 Function Block 4x1 multiplexor can implement any function of two variables Simply place the truth table for F on the inputs of the mux The operands A and B will select the correct value of the function E CE 3060 DatapathI 5 Adder Cells SUM A G B G C CAB AB 5AB AB CARRY AB AC BC AB CA B Above equations may be implemented as complex gates These equations may be manipulated to yield SUM ABC A B CCARRY E CE 3060 DatapathI 6 Adder Layout ggwwwwwwywwwgww a ECE 3060 Datapath1 7 Transmission Gate Full Adder 0 Truth Table A 0 0 0 0 1 1 1 1 0 When A993 0SUM Cand Cany When Aeg 1SUM Eand Cany B 0 0 1 1 0 0 1 1 C HOHoHowo 0 HOOHOHH Sum Carry 0 HHHoHoo Ezrry 0 Using the GT XOR this full adder uses 1ST 15653060 mama Transmission Gate Adder ECE 3060 Carry Lookahead Ripple carry delays may be unacceptable for wider n bit adders Cout Cm VVUVUUUU J Delay is proportional to n There are many many schemes for speeding up the calculation of carry bits Traditional CLA designs are based upon calculating the carry bits in parallel this takes 0logn time because the fanin to the CLA function is 0n Other designs are based on speeding up the ripple E CE 3060 DatapathI I 0 Carry Propagate and Generate o A carry out Cl1 is generated from bit position i when both Al and BI are 1 Le GI A131 0 A carry in is propagated to the carry out at bit position iwhen either Al or BI is 1 if both are 1 GI will cover eg Pl AZ 131 gm m r 7 1 complex gate 5139 0 Thus the carryout Cl1 GZPZCZ 15653060 W141