cudd.ps

主要进行大规模的电路综合

b(ariable)24 b(Orders)h(for)e(BDDs)f(and)i(ZDDs)46 b(.)f(.)g(.)g(.)g(.)
125 b(21)585 1476 y(3.16)51 b(Hooks)k(.)45 b(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(21)585 1589 y(3.17)51
b(The)23 b(SIS/VIS)f(Interf)o(ace)27 b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(22)794 1702 y(3.17.1)65 b(Using)24 b(the)f(CUDD)f(P)o(ackage)i(in)f
(SIS)h(.)45 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(22)585 1815 y(3.18)51 b(Writing)24 b(Decision)h(Diagrams)f(to)g(a)f
(File)57 b(.)45 b(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)125 b(23)585 1928 y(3.19)51 b(Sa)n(ving)24 b(and)g(Restoring)h
(BDDs)78 b(.)45 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)125 b(25)448 2132 y Fq(4)92 b(Pr)n(ogrammer')m
(s)25 b(Manual)1870 b(25)585 2245 y Fp(4.1)96 b(Compiling)24
b(and)g(Linking)53 b(.)45 b(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(25)585
2357 y(4.2)96 b(Reference)25 b(Counts)53 b(.)45 b(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)g(.)125 b(25)794 2470 y(4.2.1)110 b(NULL)21 b(Return)j(V)-10
b(alues)42 b(.)j(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)
h(.)f(.)g(.)g(.)g(.)125 b(26)794 2583 y(4.2.2)110 b Fo(Cudd)p
1286 2583 28 4 v 33 w(Recur)o(siveDer)m(ef)40 b Fp(vs.)23
b Fo(Cudd)p 2239 2583 V 34 w(Der)m(ef)45 b Fp(.)h(.)f(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)125 b(27)794 2696 y(4.2.3)110 b(When)23
b(Increasing)k(the)d(Reference)h(Count)f(is)f(Unnecessary)90
b(.)45 b(.)125 b(27)794 2809 y(4.2.4)110 b(Saturating)25
b(Increments)h(and)e(Decrements)91 b(.)45 b(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)125 b(27)585 2922 y(4.3)96 b(Complement)24 b(Arcs)37
b(.)45 b(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)
f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(28)585 3035
y(4.4)96 b(The)23 b(Cache)37 b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)g(.)125 b(28)794 3148 y(4.4.1)110 b(Cache)24
b(Sizing)64 b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)
h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(29)794
3261 y(4.4.2)110 b(Local)23 b(Caches)55 b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(30)585 3374 y(4.5)96 b(The)23 b(Unique)h(T)-7 b(able)47
b(.)e(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(30)585 3487
y(4.6)96 b(Allo)n(wing)24 b(Asynchronous)j(Reordering)64
b(.)45 b(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(31)585 3599 y(4.7)96 b(Deb)n(ugging)28 b(.)45 b(.)g(.)h(.)f(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)125 b(33)585 3712 y(4.8)96 b(Gathering)25
b(and)f(Interpreting)j(Statistics)64 b(.)45 b(.)g(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125 b(33)794 3825
y(4.8.1)110 b(Non)23 b(Modi\002able)i(P)o(arameters)89
b(.)45 b(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(34)794 3938 y(4.8.2)110 b(Modi\002able)24 b(P)o(arameters)64
b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)g(.)125 b(36)794 4051 y(4.8.3)110 b(Extended)25 b(Statistics)g(and)
f(Reporting)63 b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)
125 b(38)585 4164 y(4.9)96 b(Guidelines)25 b(for)f(Documentation)75
b(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)g(.)125 b(39)448 4368 y Fq(5)92 b(The)22 b(C++)g(Interface)2044
b(40)585 4481 y Fp(5.1)96 b(Compiling)24 b(and)g(Linking)53
b(.)45 b(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)125 b(40)585 4594 y(5.2)96 b(Basic)23
b(Manipulation)58 b(.)45 b(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)125
b(40)448 4797 y Fq(6)92 b(Ackno)o(wledgments)2050 b(40)1920
5225 y Fp(2)p eop
%%Page: 3 3
3 2 bop 585 573 a Fq(Refer)n(ences)2341 b(41)585 777
y(Index)2539 b(42)1920 5225 y Fp(3)p eop
%%Page: 4 4
4 3 bop 448 573 a Fr(1)120 b(Intr)n(oduction)448 780
y Fp(The)28 b(CUDD)d(package)30 b(pro)o(vides)g(functions)g(to)e
(manipulate)i(Binary)e(Decision)i(Diagrams)448 893 y(\(BDDs\))35
b([5,)f(3)q(],)j(Algebraic)g(Decision)g(Diagrams)e(\(ADDs\))g([1],)j
(and)d(Zero-suppressed)448 1006 y(Binary)f(Decision)g(Diagrams)g
(\(ZDDs\))e([12)q(].)56 b(BDDs)32 b(are)h(used)g(to)g(represent)j
(switching)448 1119 y(functions;)k(ADDs)31 b(are)i(used)g(to)f
(represent)j(function)g(from)d Fn(f)p Fp(0)p Fk(;)10
b Fp(1)p Fn(g)2678 1086 y Fi(n)2749 1119 y Fp(to)32 b(an)h(arbitrary)h
(set.)448 1231 y(ZDDs)20 b(represent)j(switching)g(functions)g(lik)o(e)
f(BDDs;)e(ho)n(we)n(v)o(er)l(,)i(the)o(y)g(are)f(much)g(more)g(ef)n
(\002-)448 1344 y(cient)27 b(than)f(BDDs)e(when)i(the)g(functions)i(to)
d(be)h(represented)j(are)c(characteristic)30 b(functions)448
1457 y(of)h(cube)g(sets,)i(or)d(in)h(general,)i(when)e(the)g(ON-set)f
(of)g(the)h(function)i(to)d(be)h(represented)i(is)448
1570 y(v)o(ery)24 b(sparse.)30 b(The)o(y)23 b(are)h(inferior)i(to)d
(BDDs)f(in)h(other)i(cases.)589 1683 y(The)30 b(package)h(pro)o(vides)h
(a)d(lar)n(ge)i(set)f(of)f(operations)k(on)c(BDDs,)h(ADDs,)f(and)h
(ZDDs,)448 1796 y(functions)d(to)d(con)l(v)o(ert)h(BDDs)e(into)h(ADDs)f
(or)g(ZDDs)g(and)h(vice)g(v)o(ersa,)h(and)f(a)g(lar)n(ge)h(assort-)448
1909 y(ment)f(of)f(v)n(ariable)j(reordering)g(methods.)589
2022 y(The)e(CUDD)d(package)k(can)f(be)g(used)g(in)g(three)g(w)o(ays:)
585 2190 y Fn(\017)46 b Fp(As)17 b(a)h(black)h(box.)28
b(In)18 b(this)h(case,)g(the)g(application)i(program)f(that)f(needs)g
(to)f(manipulate)676 2303 y(decision)25 b(diagrams)f(only)g(uses)g(the)
g(e)o(xported)h(functions)g(of)e(the)h(package.)30 b(The)23
b(rich)676 2416 y(set)g(of)h(functions)i(included)g(in)d(the)h(CUDD)d
(package)26 b(allo)n(ws)e(man)o(y)f(applications)k(to)676
2529 y(be)21 b(written)i(in)f(this)g(w)o(ay)-6 b(.)28
b(Section)23 b(3)e(describes)k(ho)n(w)c(to)h(use)g(the)g(e)o(xported)i
(functions)676 2642 y(of)g(the)h(package.)33 b(An)24
b(application)k(written)d(in)f(terms)h(of)f(the)h(e)o(xported)h
(functions)h(of)676 2755 y(the)f(package)j(needs)e(not)g(concern)i
(itself)e(with)f(the)h(details)h(of)f(v)n(ariable)h(reordering,)676
2868 y(which)23 b(may)h(tak)o(e)g(place)h(behind)g(the)f(scenes.)585
3047 y Fn(\017)46 b Fp(As)25 b(a)g(clear)i(box.)36 b(When)26
b(writing)g(a)g(sophisticated)j(application)g(based)e(on)f(decision)676
3160 y(diagrams,)35 b(ef)n(\002cienc)o(y)e(often)g(dictates)h(that)f
(some)f(functions)i(be)e(implemented)i(as)676 3273 y(direct)h(recursi)n
(v)o(e)h(manipulation)i(of)c(the)h(diagrams,)j(instead)e(of)f(being)g
(written)g(in)676 3386 y(terms)e(of)g(e)o(xisting)i(primiti)n(v)o(e)f
(functions.)60 b(Section)35 b(4)d(e)o(xplains)j(ho)n(w)e(to)g(add)h(ne)
n(w)676 3499 y(functions)j(to)f(the)f(CUDD)e(package.)66
b(It)35 b(also)h(details)h(ho)n(w)d(to)i(write)f(a)g(recursi)n(v)o(e)
676 3612 y(function)25 b(that)f(can)g(be)g(interrupted)i(by)e(dynamic)h
(v)n(ariable)g(reordering.)585 3792 y Fn(\017)46 b Fp(Through)21
b(an)f(interf)o(ace.)30 b(Object-oriented)23 b(languages)g(lik)o(e)e
(C++)e(and)h(Perl5)g(can)h(free)676 3905 y(the)k(programmer)h(from)f
(the)h(b)n(urden)h(of)e(memory)g(management.)35 b(A)24
b(C++)g(interf)o(ace)676 4018 y(is)k(included)i(in)e(the)h(distrib)n
(ution)j(of)c(CUDD.)d(It)j(automatically)k(frees)d(decision)h(di-)676
4131 y(agrams)g(that)f(are)h(no)f(longer)i(used)f(by)f(the)h
(application)i(and)e(o)o(v)o(erloads)h(operators.)676
4244 y(Almost)i(all)h(the)g(functionality)k(pro)o(vided)e(by)e(the)g
(CUDD)d(e)o(xported)36 b(functions)g(is)676 4356 y(a)n(v)n(ailable)d
(through)g(the)e(C++)f(interf)o(ace,)35 b(which)c(is)g(especially)j
(recommended)f(for)676 4469 y(f)o(ast)e(prototyping.)56
b(Section)32 b(5)f(e)o(xplains)j(ho)n(w)c(to)i(use)f(the)h(interf)o
(ace.)54 b(A)31 b(Perl5)g(in-)676 4582 y(terf)o(ace)38
b(also)g(e)o(xists)g(and)f(is)g(ditrib)n(uted)j(separately)-6
b(.)71 b(\(See)37 b(Section)h(2.2.\))69 b(Some)676 4695
y(applications)27 b(de\002ne)d(their)g(o)n(wn)f(interf)o(aces.)31
b(See)23 b(for)h(e)o(xample)g(Section)h(3.17.)448 4863
y(In)k(the)h(follo)n(wing,)i(the)d(reader)i(is)e(supposed)j(to)d(be)g
(f)o(amiliar)h(with)f(the)h(basic)g(ideas)g(about)448
4976 y(decision)c(diagrams,)f(as)e(found,)i(for)e(instance,)j(in)d([3)q
(].)1920 5225 y(4)p eop
%%Page: 5 5
5 4 bop 448 573 a Fr(2)120 b(Ho)o(w)29 b(to)h(Get)g(CUDD)448
783 y Fh(2.1)99 b(The)26 b(CUDD)f(P)o(ackage)448 957
y Fp(The)36 b(CUDD)e(package)39 b(is)d(a)n(v)n(ailable)j(via)d(anon)o
(ymous)j(FTP)34 b(from)i(vlsi.Colorado.EDU.)448 1070
y(A)29 b(compressed)j(tar)e(\002le)f(named)h Fg(cudd-2.3.1.tar.)o(gz)22
b Fp(can)31 b(be)e(found)i(in)f(directory)448 1183 y
Fg(pub)p Fp(.)d(Once)c(you)h(ha)n(v)o(e)h(this)f(\002le,)676
1371 y Fg(gzip)52 b(-dc)i(cudd-2.3.1.tar)o(.g)o(z)48
b(|)54 b(tar)g(xvf)f(-)448 1559 y Fp(will)27 b(create)g(directory)j
Fg(cudd-2.3.1)21 b Fp(and)27 b(its)g(subdirectories.)42
b(These)27 b(directories)j(con-)448 1671 y(tain)h(the)g(decision)i
(diagram)f(package,)i(a)c(fe)n(w)g(support)j(libraries,)h(and)d(a)f(to)
o(y)h(application)448 1784 y(based)23 b(on)f(the)h(decision)h(diagram)f
(package.)30 b(There)22 b(is)g(a)f(README)e(\002le)i(with)h
(instructions)448 1897 y(on)33 b(con\002guration)j(and)d(installation)j
(in)d Fg(cudd-2.3.1)p Fp(.)51 b(Y)-10 b(ou)32 b(can)i(use)f(a)f
(compiler)i(for)448 2010 y(either)25 b(ANSI)d(C)g(or)i(C++.)589
2123 y(Once)g(you)g(ha)n(v)o(e)g(made)g(the)g(libraries)h(and)f
(program,)h(you)f(can)g(type:)676 2311 y Fg(cd)53 b(nanotrav)676
2424 y(nanotrav)e(-p)i(1)h(-autodyn)d(-reordering)f(sifting)h(-trav)676
2537 y(mult32a.blif)448 2724 y Fp(This)19 b(will)f(run)h(a)f
(simple-minded)j(FSM)c(tra)n(v)o(ersal)k(program.)28
b(\(On)18 b(a)g(200)h(MHz)f(PentiumPro)448 2837 y(\(TM\),)27
b(it)g(tak)o(es)h(about)h(6)e(sec.\))41 b(The)27 b(output)h(produced)i
(by)e(the)f(program)i(can)f(be)f(check)o(ed)448 2950
y(against)22 b(the)f(contents)i(of)d Fg(cudd-2.3.1/nanot)o(ra)o(v/)o
(mu)o(lt)o(32a)o(.o)o(ut)o Fp(.)h(More)g(infor)n(-)448
3063 y(mation)e(on)f(the)h Fg(nanotrav)13 b Fp(program)20
b(can)e(be)g(found)h(in)f Fg(cudd-2.3.1/nanot)o(ra)o(v/)o(RE)o(ADM)o(E)
p Fp(.)589 3176 y(If)26 b(you)h(w)o(ant)f(to)g(be)g(noti\002ed)h(of)f
(ne)n(w)f(releases)j(of)e(the)h(CUDD)c(package,)29 b(send)e(a)e(mes-)
448 3289 y(sage)g(to)e Fg(Fabio@Colorado.)o(ED)o(U)p
Fp(.)448 3538 y Fh(2.2)99 b(CUDD)25 b(Friends)448 3712
y Fp(T)-7 b(w)o(o)18 b(CUDD)g(e)o(xtensions)k(are)e(a)n(v)n(ailable)h
(via)f(anon)o(ymous)i(FTP)17 b(from)i(vlsi.Colorado.EDU.)585
3900 y Fn(\017)46 b Fo(P)-7 b(erlDD)27 b Fp(is)i(an)f(object-oriented)
34 b(Perl5)29 b(interf)o(ace)i(to)d(CUDD.)f(It)h(is)h(or)n(ganized)i
(as)e(a)676 4013 y(standard)f(Perl)e(e)o(xtension)j(module.)39
b(The)26 b(Perl)g(interf)o(ace)j(is)d(at)h(a)f(some)n(what)h(higher)676
4126 y(le)n(v)o(el)c(than)i(the)e(C++)g(interf)o(ace,)j(b)n(ut)e(it)f
(is)h(not)g(as)f(complete.)585 4313 y Fn(\017)46 b Fo(DDcal)23
b Fp(is)h(a)g(graphic)h(BDD)e(calculator)j(based)f(on)f(CUDD,)e
(Perl-Tk,)i(and)g(dot.)31 b(\(See)676 4426 y(Section)24
b(3.18)g(for)g(information)i(on)d Fo(dot)p Fp(.\))448
4719 y Fr(3)120 b(User')l(s)28 b(Manual)448 4926 y Fp(This)c(section)h
(describes)h(the)e(use)g(of)f(the)h(CUDD)d(package)26
b(as)d(a)g(black)i(box.)1920 5225 y(5)p eop
%%Page: 6 6
6 5 bop 448 573 a Fh(3.1)99 b(Compiling)25 b(and)g(Linking)448
747 y Fp(T)-7 b(o)23 b(b)n(uild)i(an)e(application)k(that)d(uses)g(the)
g(CUDD)d(package,)26 b(you)e(should)h(add)448 935 y Fg(#include)51
b("util.h")448 1048 y(#include)g("cudd.h")448 1235 y
Fp(to)32 b(your)g(source)h(\002les,)g(and)g(should)g(link)f
Fg(libcudd.a)p Fp(,)d Fg(libmtr.a)p Fp(,)f Fg(libst.a)p
Fp(,)i(and)448 1348 y Fg(libutil.a)23 b Fp(to)28 b(your)h(e)o(x)o
(ecutable.)43 b(\(All)28 b(these)h(libraries)g(are)f(part)h(of)f(the)g
(distrib)n(ution.\))448 1461 y(Some)20 b(platforms)h(require)h
(speci\002c)e(compiler)i(and)e(link)o(er)h(\003ags.)28
b(Refer)20 b(to)g(the)g Fg(Makefile)448 1574 y Fp(in)k(the)g(top)f(le)n
(v)o(el)h(directory)i(of)e(the)f(distrib)n(ution.)448
1823 y Fh(3.2)99 b(Basic)25 b(Data)g(Structur)n(es)448
1997 y Fq(3.2.1)92 b(Nodes)448 2172 y Fp(BDDs,)24 b(ADDs,)h(and)h(ZDDs)
d(are)j(made)g(of)f(DdNode')-5 b(s.)35 b(A)25 b(DdNode)g(\(node)i(for)f
(short\))g(is)g(a)448 2285 y(structure)j(with)d(se)n(v)o(eral)i
(\002elds.)37 b(Those)27 b(that)g(are)f(of)h(interest)h(to)e(the)h
(application)j(that)d(uses)448 2398 y(the)e(CUDD)d(package)27
b(as)d(a)g(black)i(box)f(are)f(the)h(v)n(ariable)h(inde)o(x,)g(the)e
(reference)j(count,)f(and)448 2510 y(the)f(v)n(alue.)33
b(The)24 b(remaining)i(\002elds)f(are)f(pointers)j(that)e(connect)i
(nodes)e(among)g(themselv)o(es)448 2623 y(and)f(that)g(are)g(used)g(to)
g(implement)h(the)e(unique)j(table.)j(\(See)23 b(Section)i(3.2.2.\))589
2736 y(The)h Fo(inde)n(x)i Fp(\002eld)e(holds)h(the)g(name)f(of)g(the)h
(v)n(ariable)h(that)e(labels)i(the)e(node.)38 b(The)25
b(inde)o(x)448 2849 y(of)37 b(a)f(v)n(ariable)i(is)f(a)f(permanent)j
(attrib)n(ute)g(that)e(re\003ects)g(the)g(order)h(of)e(creation.)70
b(Inde)o(x)448 2962 y(0)26 b(corresponds)k(to)c(the)g(v)n(ariable)i
(created)g(\002rst.)36 b(On)25 b(a)h(machine)h(with)f(32-bit)h
(pointers,)i(the)448 3075 y(maximum)21 b(number)h(of)e(v)n(ariables)j
(is)d(the)h(lar)n(gest)i(v)n(alue)e(that)h(can)f(be)f(stored)j(in)d(an)
h(unsigned)448 3188 y(short)27 b(inte)o(ger)g(minus)f(1.)35
b(The)25 b(lar)n(gest)j(inde)o(x)f(is)e(reserv)o(ed)j(for)e(the)g
(constant)h(nodes.)37 b(When)448 3301 y(64-bit)24 b(pointers)g(are)e
(used,)h(the)f(maximum)g(number)h(of)f(v)n(ariables)i(is)e(the)g(lar)n
(gest)i(v)n(alue)f(that)448 3414 y(can)h(be)g(stored)h(in)e(an)h
(unsigned)i(inte)o(ger)e(minus)g(1.)589 3527 y(When)k(v)n(ariables)i
(are)e(reordered)i(to)e(reduce)h(the)f(size)g(of)f(the)h(decision)i