1997
IEEE
In ema ional Symposium
on
Ci cui s and Sys ems,
June
9-12,1997,
Hong
Kong
Compa ison
o
Ma oid In e sec ion Algo i hms o L,a g : Ci cui Analysis*
Ma iano Galin, F ancisco
V.
Fe nindez a id Angel Rod iguez-Vizquez
Dep . o Analog and Mixed-Signal In eg a ed Ci cui Design,
IMSE,-CNM
Edi . CICA, A da. Reina Me cedes s/n, 13-41012 Se illa,
SPAlN
Tel.: +34
5
4239923, FAX: +34
5
4231832, E-mail: paco @cnm
us.es
Abs ac
This pape p esen s wo app oaches
o
symbolic
analysis o la ge analog in eg a ed ci cui s ia simpli ica-
ion du ing he gene a ion o he symbolic exp essions.
Bo h echniques a e examined om he poin
o
iew o
ma oid heo y. Finally, a new app oach which combines
he posi i e ea u es o bo h app oaches is in oduced.
1.
In oduc ion
Symbolic analyze s a e CAD ools which calcu-
la e ne wo k unc ions o analog ci cui s, wi h he com-
plex equency
s
and he ci cui pa ame e s kep as
symbols. Those ne wo k unc ions a e ypically gi en as
a
cancella ion- ee sum o p oduc s:
2
N
2
M
(1)
,(x)
+. ,(.,
+. ,(.,
+...+s
gg(x)
+.gl
(x)
+s
g*(.)
+
...
+s
g,(x)
H(s,x)
=
T
in
which
x
={xl,
x2,
. .
.,
xe}
is he ec o o symbolic
pa ame e s, and and
gi
a e sums o p oduc s. Many
po en ial applica ions ha e been epo ed o symbolic
analyse s, mos o which can be ound
in
[I].
One
o
he majo d awbacks ha has p e en ed
symbolic analyze s om being widely accep ed by he
analog design communi y has been ha he size
o
he ci -
cui s ha hey can analyze is s ill much smalle han o
nume ical simula o s. This is due o he exponen ial
g ow h o he symbolic o mula complexi y wi h he ci -
cui size. This no only limi s he maximum analysable
ci cui size bu also makes mo e di icul o mula in e -
p e a ion and i s use in design au oma ion applica ions,
whe e exp essions should be he smalles possible o
inc eased e alua ion e iciency.
Expe ience wi h he applica ion o symbolic ana-
lyze s
o
eal analog in eg a ed ci cui s shows ha , usu-
ally, a e y small pa o he symbolic exp ession con ains
mos ele an in o ma ion.
So
he app oxima ion o sym-
bolic exp essions, de ined as he educ ion o o mula
complexi y while main aining he accu acy as high as
possible, has become
a
mus . The gene al opic o exp es-
sion simpli ica ion will be desc ibed in Sec ion 2.
*
This
wo k
has
been pe o med
in
he
amewo k
o
he
AMADEUS
P ojec
o
he ESPRIT
IV
P og am
o
he
CEC.
0-7803-3583-X/97
$10.00
01997
IEEE
1784
]Howe e , o mula app oxima ion a e hle com-
ple e exac exp ession has been gene a ed
only
eases
in e p e a ion and manipula ion bu ci cui size limi a-
ions emain.
A
majo b eak h ough has been p ioduced
wi h lhe in oduc ion
o
simpli ica ion du ing gene a ion
algo i hms [2],[3],[41. Sec iion
3
will explain hsow he
app oxima ion du ing genwa ion p oblem can be unde -
s ood in e ms o ma oids,
a
gene al ma hema ical he-
o y ha gua an ees ha i I he ma oid p oblem has a
solu ion, he pa icula p oblem a hand can
also
be
sol ed, and a leas as e icien ly as he ma oid p oblem.
2.
Symbolic exp ession app oxima ion
Con en ionally, epo ed symbolic analyze s ha e
inco po a ed he app oxima ion ea u e by i s ciilcula -
ing he exac ne wo k unc ion and hen simpli ying i as
a pos p ocessing s ep
[5],[6],[7].
Fo his eason
'we
will
call i
Simpli ica ion
A e Gene a ion
(SAG). I
is
based
on he elimina ion
o
he leas signi ican e ms o subex-
p essions while some e o c i e ion is sa is ied. Rela i e
signi icance is e alua ed based on nume ical es ima es o
he symbolic ci cui pa ame e s. Assume
T
h,
(x:l
=
h,,
(x)
+
h,,
(x)
+
.
.
.
+
h,,
(x)
=
c
h,,
(x)
(2)
/=
I
ep exn s ei he k(x) o
gk(x)
in
(1).
The
P
leas signi i-
can e ms in (2) a e elimina ed, one by one and begin-
ning wi h he smalles , while he sum o he eli nina ed
e ms keeps below
some
gi len h eshold,
P
T
(3)
whe e
xo
ep esen s he design poin o he ci cui pa am-
e e s and
ek
is a disc imina ion h eshold.
The p incipal d awback o SAG echniques is ha
simpli ica ion is pe o med al e he exac ne wo k unc-
ion has been gene a ed.
So
he exac exp ession, which
usually is no used any mo e a e he app oxiima ion,
limi s he analysable ci cui size o a ound
10
an,sis o s.
In o de o ex end
he
capabili ies o con en ional
symbolic analyze s, he new concep o
Simpl@ca ion
Du ing Gene a ion
(SDG) has ecen ly been p oposed.
SDG is based on he ollowing idea: e ms a e gene a ed
in s ic ly dec easing o de o magni ude, s a ing wi h
he la ges , o each powe o
s,
un il hey ep esen a
gi en ac ion o he o al magni ude o he coe icien .
SDG has wo main ad an ages. Fi s , he analysis
is as e , as no ime is was ed gene a ing e ms ha would
be neglec ed la e on. Second, i s smalle memo y needs
make possible ha much la ge ci cui s can be analyzed.
This is clea ly illus a ed in Fig. l(b), which shows he
compu a ion ime o app oxima ed exp essions wi h
E+
=
0.25
e sus he numbe o ci cui nodes
in
Fig. l(a).
I
can be seen ha he new SDG app oach is
o de s o magni ude as e han he con en ional one
o
ge he same app oxima ed exp ession. Mo eo e , he
maximum analysable ci cui size inc eases conside ably.
Ml*
2
...*n
1
o5
I
---
SAG app oach
SDG app oach
-
~
I
G
io4
I
'i;
102-
/
V
2
103:
/
/
SAG app oach
SDG app oach
---
1
o5
I
-
I
G
io4
I
'i;
102-
,/
/
V
2
103:
/
%---5
'
'io
'
'is'
' '
'io'
35
.
'
4d
(b)
Numbe
o
ladde s ages
Figu e
1:
(a)
Ladde ne wo k;
(b)
CPU
ime compa i.
son o he calcula ion
o
i s ol age gain.
2.1.
Te m gene a ion wi h he wo-g aph me hod
Te m gene a ion by he wo-g aph ee enume a-
ion me hod has been shown o be he mos e icien ech-
nique o implemen he SDG idea. The wo-g aph
me hod makes
use
o
a ol age g aph
G
and a cu en
g aph
GI,
bo h
easily
buil om he o iginal ne wo k
[8].
Fig.
2
illus a es he cons uc ion o bo h g aphs o a
simple ci cui . Each alid e m co esponds o he admi -
ance p oduc o e e y b anch in a spanning ee common
o bo h g aphs.
The e o e, he e m gene a ion p oblem o each
powe o
s
(say he k- h powe ) educes o he ollowing
g aph p oblem: enume a e all spanning ees common o
bo h, he ol age and he cu en g aph, in dec easing
o de o weigh and con aining
k
capaci ance b anches.
Repo ed echniques [2],[3],[4] s a ed om he
algo i hm in
[9]
o he enume a ion o spanning ees o
a one-colo ed g aph in dec easing o de o weigh . As he
alid e ms a e gi en by common spanning ees o ol -
Figu e
2:
Example ci cui and i s wo-g aph ep esen a ion
age and cu en g aphs, his algo i hm is applied o he
ol age g aph and o each gene a ed spanning ee
i
is
checked i i is also a spanning ee in he cu en g aph.
Bu ,
each spanning ee mus con ain exac ly
k
capaci-
o s. The e o e, he o iginal algo i hm o one-colo ed
g aphs had
o
be ex ended o wo-colo ed g aphs (con-
aining wo b anch ypes: capaci o s and conduc ances).
3.
The enume a ion p oblem in e ms
o
ma
aids
Ma oids a e ma hema ical abs ac ions which
o e a model o many ma hema ical s uc u es and com-
bina o ial p oblems. I ou p oblem can be exp essed
in
e ms o ma oids, hen, gene ally, be e algo i hms
imp o ing he unning ime (exploi ing special s uc u es
o hose ma oids) may be ound. Some gene al concep s
abou ma oids a e de ined nex .
3.1.
Ma oid p elimina ies
A
ma oid
M=(E,J)
is a s uc u e
in
which
E
is a
ini e se o
elemen s
and Jis a amily o subse s o
E,
which sa is y some axioms
[lo].
A
subse
I
in
3
is an
independen
se
o he ma oid
M=(E,J).
A maximal inde-
penden se is a
base
o he ma oid. A ma oid
M=(E,J)
is
said o be he
g aphic ma oid
o he g aph G i
E
is
he
se o a cs o G and a subse
I
E
is
in
gi and only i
I
is a cycle- ee
subse
o
a cs. In
a
connec ed g aph, a base
o i s g aphic ma oid co esponds o a spanning ee.
Finally, le
K
be a pa i ion ha sepa a es
E
in o
m
disjoin blocks
B1,
...,
Bm,
and le
di,
(i=l,
...,
m)
be
m
non-nega i e in ege s. Then,
M=(E, i
is
a
pa i ion
ma oid
i
J
is he amily o subse s
I
ha sa is y
InB.
Id.,i
=
1
,...,
m).
I
II
1
3.2.
Applica ion
o
ma oid heo y
o
ou p oblem
The ee enume a ion p oblem can be unde s ood
as a 3-ma oid in e sec ion p oblem. These h ee
ma oids a e:
1785
A g aphic ma oid de ined on he ol age g aph
G
Ano he g aphic ma oid de ined analogously on
Gp
*
A pa i ion ma oid de ined
so
ha each se o
b anches wi h
k
capaci o s is
a
base o he ma oid.
so
ha each spanning ee in
G,
is
a
base.
The ee enume a ion p oblem co esponds o he
enume a ion o bases common o he h ee ma oids
in
dec easing o de o weigh (g id a ea
in
Fig.
3).
Un o u-
na ely, he in e sec ion o h ee ma oids is conside ed o
be,
in
gene al,
a
NP-ha d p oblem
[I I].
Howe e , he e
a e polynomial ime algo i hms o he weigh ed in e -
sec ion o wo ma oids
[
12],[ 111. Repo ed symbolic
simula o s ha inco po a e
SDG
ha e sol ed he p ob-
lem by inding i s he in e sec ion o wo ma oids and
checking which elemen s o ha in e sec ion a e also
a
base
in
he hi d ma oid. Two di e en possibili ies
a ise:
Fi s in e sec ioning a g aphic ma oid and he pa i-
Fi s in e sec ioning he wo g aphic ma oids ( e i-
ion ma oid (ho izon ally-s iped a ea in Fig.
3).
cally-s iped a ea in Fig.
3).
du ion
space
Figu e 3: Illus a ing he 3-ma oid
in e sec ion
p oblem.
The i s one has been implemen ed
in
ADAGIO
[2],[3] and RAINIER [4]
as
i has been desc ibed
in
Sec-
ion 2.1. This me hod has he disad an age ha many
spanning ees o he ol age g aph may be gene a ed ha
a e no spanning ees in he cu en g aph and, hence, do
no lead o alid e ms. The a io o gene a ed alid e ms
o e he numbe o spanning ees in he ol age g aph
end o dec ease when he ci cui size inc eases, impos-
ing
a
limi o he maximum analysable ci cui size.
I
is
no easy o compa e he wo implemen a ions
o his app oach: ha in [2],[3], on he one hand, and ha
in
[4],
on he o he . This is mainly due o he di e en
e o c i e ia applied, and he ac ha he ool in [4] pe -
o ms
a
simpli ica ion be o e gene a ion p ocedu e
which signi ican ly educes he ci cui
size.
Fo illus a ion's sake, he ool
in
[3]
p o ides
a
simpli ied exp ession o he ol age gain o he olded-
cascode opamp
in
Fig. 4 in 54.7
s.
The gene a ion o a
symbolic exp ession o he pA741
's
ans e unc ion a
low equencies wi h
a
magni ude e o o
0.11%
(110
symbolic e ms) equi es
38
s.
An app oxima ed exp es-
sion (57 e ms) o he pA741 is p o ided in [4]
in
19
s.
Figu e
4:
:
Folded-cascode opamp.
1
0
The second app oach, ha
is,
in e sec ioning he
wo g aphic ma oids has been implemen ed
in
[13].
The e, common spanning ees o he ol age and cu en
g aphs, in dec easing o de o ee admi ance p oduc ,
a e di ec ly gene a ed using he algo i hm
in
[12].
So,
no
ime
is
was ed in gene a ing spanning ees
o
one o
hese g aphs which a e wa ds a e no spanning ees in
he o lhe g aph. Bu no con ol can be pe o med on he
b anch ype (conduc ance
o
capaci o ), and, hence,
capaci o admi ances ( he b anch weigh ) mus be e al-
ua ed a a ixed equency:
CUC.
This app oach app oxima es he ne wo k unc ion
o e
a
equency ange and conside s
a
se o sample e-
quencies wi hin his ange. The algo i hm
in
[
121 o gen-
e a ion o common spanning ees (wi hou any
cons ain in he numbe o capaci ance b anches) is
applied a each sample equency un il some gi en e o
c i e ion is me . Since he e: is
no
cons ain
in
he num-
be o capaci ance b anches, e ms a e gene a ed wi h
di e en powe s o
s.
A
g'ene a ed e m is kep in he
app oxima ed exp ession i i appea s o
a
leas one o
he sample equencies
in
he equency ange.
Bu his me hod has wo impo an d awbacks:
on
he one hand, mos e ms a e gene a ed a mo e han one
sample equency, and his means
a
loss
o
e iciency.
On
he o he hand, la ge e o s can occu a equencies di -
e en om hose
o
he se o sample equencies as
no
con ol is pe o med on he (exp ession accu acy be ween
wo sample equencies. Imp o ing he accu acy equi es
aking mo e sample equencies bu his
is
done a he
expense o addi ional compu a ion ime, g ea ly de e io-
a ing he e iciency
o
he me hod.
The same exp ession han [4] o he pA.741 has
been epo ed o be ob ained in
20
s.
p ac ically he same
han wi h he p e ious echinique [13]. Howe e , a mo e
accu a e exp ession (1185 , e ms) is ob ained in 57.7
s,
less han hal he ime needed wi h p e ious echnique.
Fo his example 4 sample equencies we e used.
1786
3.3.
A
3-ma oid in e sec ion algo i hm
The i s o he e iewed app oaches has
in
i s
e i-
ciency o la ge ci cui s i s main d awback. This is pa -
ially o e come
in
he second app oach bu
a
he cos o
uncon olled accu acy o he esul ing exp essions. The
new algo i hm in oduced in his sec ion combines he
posi i e ea u es o bo h app oaches by di ec ly add ess-
ing he in e sec ion
o
ou h ee pa icula ma oids.
The algo i hm
in
[12]
allows he gene a ion
o
spanning ees common
o
he ol age and cu en g aphs
in dec easing o de
o
weigh : om each common span-
ning ee ( he maximum weigh common spanning ee is
no di icul
o
ind), he nex one is ob ained by ca ying
ou he b anch exchanges indica ed by he bes
p imi i e
bo de pa h
(PBP) o he
bo de g aph
(BG), buil om
he spanning ee and bo h he ol age and cu en
g aphs. This bes p imi i e bo de pa h is mo e e i-
cien ly ound
in
he
condensed bo de g aph
(CBG),
which is easily de i ed om he bo de g aph
[
121.
This
algo i hm makes use o he lexicog aphic Floyd-Wa -
shall algo i hm o ind he bes PBP
in
ei he he
BG
o
he CBG.
Bu
his way,
in
bo h he cons uc ion o he
CBG and
in
he Floyd-Wa shall algo i hm, we ha e no
con ol on he ype o he b anches as i only looks a hei
weigh s,
so
i
is unde e mined he inal numbe o
b anches o each ype (capaci ance o conduc ance), and
hus i is no adequa e o ou needs.
In o de o sol e he p oblem o he con ol on he
b anch ypes, we pe o m ex ensi e modi ica ions in he
cons uc ion
o
he
CBG,
leading
o
he
Ex ended Con-
densed Bo de G aph
(ECBG).
In
he ECBG, each
b anch can ha e up o wo weigh s, ins ead
o
one weigh
as
i occu s
in
he con en ional CBG. These wo weigh s
co espond o he capaci ance and conduc ance nodes o
he BG ha sa is y he condi ion needed
o
ha e a co e-
sponding b anch in he CBG, wi h he highes weigh o
all he capaci ance/conduc ance nodes o he BG.
I
e lec s he ac ha a conduc ance/capaci ance b anch
can be exchanged by, ei he
a
conduc ance o a capaci-
ance b anch. Each b anch weigh has an associa ed
b anch ype, which co esponds o he numbe
o
induced
capaci ance b anch exchanges.
To ind he bes
PBP
in his ECBG an algo i hm,
called
Mul ile el Sho es Pa hs
(MSP), has been de el-
oped. The MSP algo i hm inds all sho es pa hs
be ween each pai o nodes
in
he ECBG. These pa hs
co espond o e e y possible ne numbe
o
capaci ance
b anch exchanges wi h espec o he common spanning
ee om which he BG was buil . This is done conside -
ing he combina ions o he di e en b anches be ween
nodes, and aking in o accoun also hei ypes. Thus, cal-
cula ion o he ollowing common spanning ee in he
same coe icien in
(1)
educes o aking he bes PBP
wi h ze o ne capaci ance b anch exchanges.
Conclusions
Two algo i hms o app oxima ion du ing gene a-
ion o he symbolic analysis
o
la ge analog in eg a ed
ci cui s ha e been e iewed. The i s
one
has in i s accu-
acy i s s onge ea u e, dec easing i s e iciency wi h
he ci cui size. The second gi es p io i y
o
he e i-
ciency bu wi h
a
high isk o la ge inaccu acies. This has
mo i a ed he in oduc ion o
a
new app oach which
o e comes p e ious d awbacks and cons i u es he i s
polynomial ime algo i hm o he h ee ma oid in e sec-
ion p oblem.
Re e ences
A. Rod iguez-Vazquez, F.V. Femandez, J.L. Hue as and
G.
Gielen,
Symbolic Anulysis Techniques and Applica ions
o
Anulog
Design
Au oma ion,
IEEE P ess, 1996.
F.V. Fe nindez, P. Wambacq,
G.
Gielen, A. Rod iguez-Vazquez
and W. Sansen. "Symbolic Analysis o La ge Analog In eg a ed
Ci cui s by App oxima ion Du ing Exp ession Gene a ion,"
P oc.
IEEE
ln .
Symp.
on Ci cui s
und
Sys ems,
pp.25-28, 1994.
P. Wambacq, F.V. Femandez,
G.
Gielen, W. Sansen and A.
Rod iguez-Vazquez, "E icien Symbolic Compu a ion
o
App oxima ed Small-Signal Cha ac e is ics
o
Analog In eg a ed
Ci cui s,"
IEEE
JSSC,
Vol. 30,
No.
3, pp, 327-330, Ma ch 1995.
Q.
Yu
and C. Sechen, "App oxima e Symbolic Analysis o La ge
Analog In eg a ed Ci cui s,"
P oc. IEEE In .
Co $
on
Compu e -
Aided Design,
pp.
664-611,
1994.
F.V. Fe nindez, A. Rod iguez-Vizquez and J.L. Hue as,
"In e ac i e AC Modeling and Cha ac e iza ion o Analog
Ci cui s ia Symbolic Analysis,"
Anulog In eg u ed Ci cui
und
Signal P ocessing,
Vol
1,
pp. 183-208, Kluwe , No . 1991
G.
Gielen, H. Walscha s and W. Sansen, "ISAAC: A Symbolic
Simula o o Analog In eg a ed Ci cui s,"
IEEE
Jou nul
o
Solid
S u e Ci cui s,
Vol.
24,
pp. 1587-1597, Dec. 1989.
G.
M. Wie zba
e
al.,
"Sspice
-
A
Symbolic SPICE P og am o
Linea Ac i e Ci cui s,"
P oc.
32nd
Midwe.F
Symp.
on
Ci cu s
und
Sys ems,
pp. 1197-1201, 1989.
P.M. Lin,
Symbolic
Ne wo k
Analysis.
Else ie , 199
I.
H.N. Gabow, "Two Algo i hms o Gene a ing Weigh ed
Spanning T ees in O de ",
SIAM
J.
o
Compu ing,
Vol.
6,
No.
I,
pp.
139-150,
Ma ch 1977.
[IO]
E.L. Lawle ,
Combinu o iul Op imizu ion: Ne wo ks
und
[
1
I]
C.H. Papadimi iou and
K.
S eigli z,
Combinu o iul
Op imizu ion: Algo i hms
und
Complexi y,
Englewood Cli s,
New Je sey. P en ice-Hall Inc.,
1982.
Mu oids.
Hol ,
Rineha and Wins on, 1976.
[I21 P.M. Came ini and H.W. Hamache , "In e sec ion
o
Two
Ma oids: (Condensed) Bo de G aph and Ranking",
SIAM
J.
DISC.
Mu h.,
Vol. 2, pp. 16-27, Feb.
1989.
[I31
Q.
Yu
and C. Sechen, "E icien App oxima ion o Symbolic
Ne wo k Func ions Using Ma oid In e sec ion Algo i hms,"
P oc.
IEEE
ISCAS,
pp. 2088-2091,
1995.
1787