Multi-LevelLogicSynthesisIntroduction

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Multi-Level Logic Synthesis Introduction,Outline,Representation,Networks,Nodes,Technology Independent Optimization,Technology Dependent Optimization,1,Structured System,(combinational logic, memory, I/O),Combinational optimization,Sequential optimization,2,Two-Level (PLA) vs. Multi-Level,PLA,control logic,constrained layout,highly automatic,technology independent,multi-valued logic,slower?,input, output, state encoding,Multi-level,all logic,general,automatic,partially technology independent,coming,can be high speed,some results,3,Early Approaches to Multi-Level,Algorithmic Approach,continues along lines of ESPRESSO and two-level minimization,spectrum of speed/quality trade-off algorithms,encourages development of understanding and theory,4,Optimization Cost Criteria,The accepted optimization criteria for multi-level logic are 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,Wireability,while simultaneously satisfying upper or lower bound constraints placed on these physical quantities,5,Optimization Cost Criteria,6,Multi-Level is Natural for High Level Synthesis,Example,w=ab+ab,If,w,then,z=cd+ad,;,u=cd+ad+e(f+b),else,z=e(f+b),;,u=(cd+ad)e(f+b),A:,w=ab+ab,z=w(cd+ad )+we(f+b),u=w(cd+ad+e(f+b)+w(cd+ad)e(f+b),B:,w=ab+ab,t=cd+ad,s=e(f+b),z=wt+ws,u=w(t+s)+wts,7,Network Representation,In implementing multi-level logic our first aim is to establish a,structure,on which to develop a theory and algorithms,independent,of technology on which manipulations can be made, and,optimization,progress,can be,well estimated,.,This leads to,two,abstractions:,Boolean network,Factored forms,8,Network Representation,Boolean network:,directed acyclic graph (DAG),node logic function,representation,f,j,(x,y),node variable,y,j,:,y,j,= f,j,(x,y),edge,(i,j),if,f,j,depends explicitly on,y,i,Inputs,x = (x,1, x,2,x,n,),Outputs z,= (z,1, z,2,z,p,),External dont cares,d,1,(x), d,2,(x) , d,p,(x),9,Network Representation,Boolean,network,:,10,Node Representation,Some choices:,Merged view (technology and network merged),Separated view,technology dependent,technology independent,node representation,general node,generic node,discrete node,11,Node Representation,Separated, technology independent view,general node:,each node can be a representation of an,arbitrary,logic function,representation and implementation are the same,a theory is easier to develop since there are no arbitrary restrictions dependent on technology,SIS,uses this approach (includes all others as special cases, except for multiple output nodes),Choices of,function representation,for separated, technology independent view:,sum of products form,factored form,binary decision diagram,12,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,13,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,14,Factored Forms,Example:,(ad+bc)(c+d(e+ac)+(d+e)fg,Advantages,good representative of logic,complexity,f=ad+ae+bd+be+cd+cef=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 usually just,convert,into SOP before manipulation,15,Factored Forms,Note:,literal count,transistor count,area,(however, area also depends on wiring),16,Factored Forms,Definition 1:,f,is an,algebraic expression,if,f,is a set of cubes (SOP), such that no single cube contains another (minimal with respect to single cube containment),Example:,a+ab,is not an algebraic expression (factoring gives,a(1+b),),Definition 2:,the,product,of two expressions,f,and,g,is a set defined by,fg = cd | c,f,and,d,g,and,cd,0,Example:,(a+b)(c+d+a)=ac+ad+bc+bd+ab,Definition 3:,fg,is an,algebraic product,if,f,and,g,are algebraic expressions and have,disjoint,support (that is, they have no input variables in common),Example:,(a+b)(c+d)=ac+ad+bc+bd,is an algebraic product,17,Factored Forms,Definition 4:,a factored form can be defined recursively by the following rules. A factored form is either a product or sum where:,a product is either a single,literal,or,product,of factored forms,a sum is either a single,literal,or,sum,of factored forms,A factored form is a parenthesized algebraic expression.,In effect a factored form is a,product,of,sums,of,products ,or a sum of products of sums ,Any,logic,function,can be represented by a factored form, and,any,factored form is a representation of some logic function.,18,Factored Forma,Examples,of factored forms:,xyabca+bc(a+b)cd+e)(a+b)+e,(a+b)c,is not a factored form since,complementation is not allowed, except on literals,.,Three equivalent factored forms,(factored forms are not unique):,ab+c(a+b)bc+a(b+c)ac+b(a+c),19,Factored Forms,Definition 5:,The,factorization value,of an algebraic factorization,F=G,1,G,2,+R,is defined to be,fact_val(F,G,2,) = lits(F)-( lits(G,1,)+lits(G,2,)+lits(R) ),= (|G,1,|-1) lits(G,2,) + (|G,2,|-1) lits(G,1,),assuming G,1, G,2,and R are algebraic expressions. Where,|H|,is the number of,cubes,in the SOP form of,H,.,Example:,The algebraic expression,F = ae+af+ag+bce+bcf+bcg+bde+bdf+bdg,can be expressed in the form,F = (a+b(c+d)(e+f+g),which requires 7 literals, rather than 24.,If,G,1,=(a+bc+bd),and,G,2,=(e+f+g),then,R=,.,fact_val(F,G,2,) =,23+25=,16,.,The factored form above saves 17 literals, not 16. The extra literal comes from recursively applying the formula to the factored form of,G,1,.,20,Factored Forms,Factored forms are more,compact,representations of logic functions than the traditional sum of products form.,For example,(a+b)(c+d(e+f(g+h+i+j),when represented as a SOP form is,ac+ade+adfg+adfh+adfi+adfj+bc+bde+bdfg+ bdfh+bdfi+bdfj,Of course, every SOP is a factored form but it may not be a good factorization.,21,Factored Forms,When measured in terms of number of inputs, there are functions whose size is,exponential,in sum of products representation, but,polynomial,in factored form.,Example:,Achilles,heel,function,There are,n,literals in the factored form and,(n/2),2,n/2,literals in the SOP form.,Factored forms are useful in,estimating,area and delay in a multi-level synthesis and optimization system.,In many design styles (e.g. complex gate CMOS design) the implementation of a function corresponds directly to its factored form.,22,Factored Forms,Factored forms cam be graphically represented as labeled,trees, called factoring trees, in which each internal node including the root is labeled with either,+,or, and each leaf has a label of either a variable or its complement.,Example:,factoring tree of,(a+b)cd+e)(a+b)+e,23,Factored Forms,The,size,of a factored form,F,(denoted,(,F,) is the number of literals in the factored form.,Example:,(,a+b)ca) = 4,(,a+b+cd)(a+b) = 6,A factored form is,optimal,if no other factored form,(for that function),has less literals.,A factored form is,positive unate,in,x,if,x,appears in,F, but,x,does not. A factored form is,negative unate,in,x,if,x,appears in,F, but,x,does not.,F,is,unate,in,x,if it is either positive or negative unate in,x, otherwise,F,is,binate,in,x,.,Example:,(a+b)c+a,is positive unate in,c, negative unate in,b, and binate in,a,.,24,Cofactor of Factored Forms,The,cofactor,of a factored form,F, with respect a literal,x,1,(or,x,1,), is the factored form,F,x,1,= F,x,1,=1,(x),(or,F,x,1,=F,x,1,=0,(x),) obtained by,replacing all occurrences of,x,1,by,1, and,x,1,by,0,simplifying the factored form using the Boolean algebra identities,1y=y 1+y=1 0y=0 0+y=y,after constant propagation,(all constants are removed),part of the factored form may appear as,G + G,.,In,general,G,is another factored form, and the,G,s,may have different factored forms.,25,Cofactor of Factored Forms,The,cofactor of a factored form,F, with respect to a cube,c,is a factored form,F,C,obtained by successively cofactoring,F,with each literal in,c,.,Example:,F = (x+y+z)(xu+zy(v+u),and,c = vz,. Then,F,z,= (x+y)(xu+y(v+u),F,z v,= (x+y)(xu+y),26,Factored Forms,SOPs forms are used as the internal representation of logic functions in most multi-level logic optimization systems.,Advantages,good algorithms for manipulating them are available,Disadvantages,performance is unpredictable - they may accidentally generate a function whose SOP form is too large,factoring algorithms have to be used constantly to provide an estimate for the size of the Boolean network, and the time spent on factoring may become significant,Possible solution,avoid,SOP representation by using factored forms as the internal representation,this is not practical unless we know how to perform logic operations,directly,on factored forms without converting to SOP forms,extensions to factored forms of the most common logic operations have been partially provided, but,more research,is needed,27,Manipulation of Boolean Networks,Basic Techniques:,structural operations,(change topology),algebraic,Boolean,node simplification,(change node functions),dont cares,node minimization,28,End of lecture 8,29,Structural Operations,Restructuring Problem:,Given initial network, find,best,network.,Example:,f,1,= abcd+abce+abcd+abcd+ac+cdf+abcde+abcdf,f,2,= bdg+bdfg+bdg+bdeg,minimizing,f,1,= bcd+bce+bd+ac+cdf+abcde+abcdf,f,2,= bdg+dfg+bdg+deg,factoring,f,1,= c(b(d+e)+b(d+f)+a)+ac(bde+bdf),f,2,= g(d(b+f)+d(b+e),decompose,f,1,= c(x+a)+acx,f,2,= gx,x = d(b+f)+d(b+e),Two problems:,find good,common,subfunctions,effect the,division,30,Structural Operations,Basic Operations:,1. Decomposition,(single function),f = abc+abd+acd+bcd,f = xy+xyx = aby = c+d,2. Extraction,(multiple functions),f = (az+bz)cd+e g = (az+bz)e h = cde,f = xy+e g = xe h = ye x = az+bz y = cd,3. Factoring,(series-parallel decomposition),f = ac+ad+bc+bd+e,f = (a+b)(c+d)+e,31,Structural Operations,4. Substitution,g = a+bf = a+bc,f = g(a+b),5. Collapsing,(also called elimination),f = ga+gbg = c+d,f = ac+ad+bcdg = c+d,Note:,“division”,plays a key role in all of these,32,Factoring vs. Decomposition,Factoring,f=(e+g)(d(a+c)+abc)+b(a+c),Decomposition:,y(b+dx)+xby,Note,:,this is similar to BDD collapsing of common nodes and using negative pointers. But,not,canonical, so dont have perfect identification of common nodes.,tree,DAG,33,Value of a Node and Elimination,where,n,i,=,number of times literals,y,j,and,y,j,occur in factored form,f,i,l,j,=,number of literals in factored,f,j,with factoring,without factoring,value,=,(without factoring) - (with factoring),Can treat,y,j,and,y,j,the same since,( F,j,) =,( F,j, ),.,34,Literals before = 5+7+5 =17,Literals after = 9+15 =24,-,7,Value of a Node and Elimination,Difference after - before =,value,= 7,But we may,not,have the same value if we were to eliminate, simplify and then re-factor.,x,35,Value of a Node and Elimination,Note:,value of a node can change during,elimination,36,Extra Slides Beyond This Point,37,Node Representation,Merged view,(estimators are more accurate, but slower and more constrained):,each node is a valid “gate” chosen from a library of gates to be used in the final implementation),representation and implementation are the same,Separated view,(less accurate estimators, faster, more general - lends itself to theory),two representations allowed,technology independent, without any connection to the final implementation,technology dependent which only uses valid “gates” (in the cell library or meeting some criteria),in the separated, technology independent view, there are several choices,38,Node Representation,Separated, technology independent view,discrete node:,a node can be one of a small set of logic functions, such as AND, OR, NOT, DECODE, and ADD,multiple output nodes are also allowed,used mostly in rule based systems,complex blocks of logic can be manipulated as a single unit,theory for such networks is more difficult,Choices of function representation for separated, technology independent view:,sum of products form,factored form,binary decision diagram,39,Factored Forms,Sum of products forms are used as the internal representation of logic functions in most multi-level logic optimization systems.,Advantages,good algorithms for manipulating them are available,Disadvantages,performance is unpredictable - they may accidentally generate a function whose SOP form is too large,factoring algorithms have to be used constantly to provide an estimate for the size of the Boolean network, and the time spent on factoring may become significant,Possible solution,avoid SOP representation by using factored forms as the internal representation,this is not practical unless we know how to perform logic operations directly on factored forms without converting to SOP forms,extensions to factored forms of the most common logic operations have been partially provided, but more research is needed,40,Optimum Factored Forms,Definition 6:,Let,f,be a completely specified Boolean function, and,(f),is the minimum number of literals in any factored form of,f,.,Recall,(F),is the number of literals of a factored form,F,.,Definition 7:,Let,sup(f),be the true variable support of,f, i.e. the set of variables,f,depends on. Two functions,f,and,g,are,orthogonal,f g, if,sup(f),sup(g)=,.,41,Optimum Factored Forms,Lemma 1:,Let,f=g+h,such that,g h, then,(f)=(g)+(h),.,Proof:,Let,F,G,and,H,be the optimum factored forms of,f,g,and,h,. Since,G+H,is a factored form,(F)(G+H),.,Let,c,be a minterm, on,sup(g), of,g,. Since,g,and,h,have disjoint support, we have,f,c,=(g+h),c,=g,c,+h,c,=0+h,c,=h,c,=h,.,Similarly, if,d,is a minterm of,h,f,d,=g,.,Because,(h)=(f,c,)(F,c,),and,(g)=(f,d,)(F,d,),(h)+(g)(F,c,)+(F,d,),.,Let,m,(,n,) be the number of literals in,F,that are from,sup(g),(,sup(h),). When computing,F,c,(,F,d,), we replace all the literals from,sup(g),(,sup(h),) by the appropriate values and simplify the factored form by eliminating all the constants and possibly some literals from,sup(g),(,sup(h),) by using the Boolean identities. Hence,(F,c,)n,and,(F,d,),m,. Since,(F)=m+n,(F,c,)+(F,d,)m+n=(F),.,We have,(f)(g+h)(F,c,)+(F,d,)(F),(f)=(F).,42,Note, the previous result does not imply that,all,minimum literal factored forms of,f,are sums of the minimum literal factored forms of,g,and,h,.,Corollary 1:,Let,f=gh,such that,g h, then,(f)=(g)+(h).,Proof:,Let,F,denote the factored form obtained using DeMorgans law. Then,(F)=(F),and therefore,(f)=(f),. From the above lemma, we have,(f)=(f)=(g+h)=(g)+(h)=(g)+(h),.,Theorem 1:,Let such that,f,ij,f,kl,ij,or,kl, then,.,Proof:,Use induction on,m,and then,n, and lemma 1 and corollary 1.,Optimum Factored Forms,43,Optimum Factored Forms,Definition 8:,For an incompletely specified function,(f,d), if no optimum factored form of,(f,d),can contain variable,x, then,x,is said to be redundant.,Lemma 2:,If,F,covers,(f,d), then,F,c,covers (f,c,d,c,),for any cube,c.,Proof:,Easy induction on the number of variables in,c,.,Theorem 2:,Let,(f,d+e),be an incompletely specified function such that,sup(f+d),sup(e)=,.,Then, variables in,sup(e),are redundant, which implies,(f,d+e)=(f,d),.,Proof:,Let,F,be any optimum factored form of,(f,d+e),. Assume,e1, and let,c,be a minterm, on,sup(e), of,e,. By lemma 2,F,c,covers,(f,c,d,c,+e,c,),. But,f,c,=f,d,c,=d,and,e,c,=0,. So,F,c,also covers,(f,d),. Since,F,is optimum, and,(F,c,)(F), we must have,(f,c,)=(f), which implies that,sup(F),sup(c)=,sup(F),sup(e)=,. Thus,sup(e),variables are redundant.,44,Optimum Factored Forms,The above theorem can be interpreted by the figure. If,F,D,and,E,are represented as sum of products expressions, in a positional cube notation, and the matrix has the structure indicated in the figure, then the set of cubes in,E,can be removed from the don,t care set without affecting the final result.,45,Optimum Factored Forms,A natural question to ask at this point is, “is E unique?” If yes, how do we find it? The following theorem answers the questions.,Theorem 3:,Let,f,be a Boolean function, if there is a sum of product representation whose cube matrix has the structure as indicated in the figure, where the support of,A,and,B,are,X,and,Y,respectively, then no prime,p,contains variables from both,X,and,Y,.,Thus we just need to take the dont care set and get a prime representation for it. If it has the above structure, then,D,and,E,are displayed.,46,Optimum Factored Forms,Proof:,Let,p,be a prime of,f=A(x)+B(y),. Suppose,p,contains variables from both,X,and,Y,. Let,p=p,x,p,y,where,p,x,and,p,y,are parts of,p,containing only variables from,X,and,Y,respectively. Since,p,f, then,A,px,(x)+B,py,(y)1,If,A,px,(x)1,then,p,x,A,f,contradicting that,p,is prime. Hence,B,py,(y)1,. But this implies,p,y,B,f,contradicting that,p,is prime. Thus,p,must contain variables either entirely from,X,or entirely from,Y,.,47,Optimum Factored Forms,Not only does theorem 3 show the uniqueness of the partition (if we make all cubes prime), it also indicates a procedure for obtaining it.,Given an incompletely specified function,(F,D),:,expand all cubes of,F+D,to primes,build a cube matrix,M,partition,M,into blocks of disjoint supports,remove from,M,each block of the partition that is contained entirely in,D,.,48,