An error-controlled methodology for approximate hierarchical symbolic analysis

ISCAS 2000 - IEEE In e na ional Symposium on Ci cui s and Sys ems, May 28-31, 2000, Gene a, Swi ze land An E o -Con olled Me hodology o App oxima e Hie a chical Symbolic Analysis 0. Gue a, J.D. Rod iguez-Ga cia, E. Roca, F. V. Fe nindez and A. Rod iguez-Vizquez Ins i u o de Mic oelec hica de Se illa, Cen o Nacional de Mic oelec 6nica, Se illa, SPAIN Phone: +34 955056666, FAX: +34 955056686 E-mail: { gue a, jda id, eli, paco , angel} @imse.cnm.es Abs ac * Limi a ions o exis ing app oaches o symbolic analysis o la ge analog ci cui s a e discussed. To add ess hei solu ion, a new me hodology o hie a chical symbolic analysis is in oduced. 'lke combina ion o a hie a chical modeling echnique and app oxima- ion s a egies, comp ising ci cui educ ion, g aph-based symbolic solu ion o ci cui equa ions and ma ix-based e o con ol, p o- ides op imum esul s in e ms o speed and quali y o esul s. 1. In oduc ion Symbolic analyze s a e aimed o analyze ci cui s in which pa o all hei pa ame e s a e symbols. The gene a ed exp essions p o- ide he keys o unde s anding he in ica e mechanisms unde - nea h he ci cui ope a ion. I s applica ions o p o iding insigh in in e ac i e ci cui design, gene a ing beha io al models o lib a y cha ac e iza ion, gene a ing design equa ions o syn hesis o op i- miza ion asks, a e well-known [I]. A majo p oblem in he applica ion o hese echniques was he exponen ial g ow h o he complexi y o he symbolic exp essions wi h he ci cui s sizes. Di e en solu ions ha e been p oposed o pallia e his p oblem. On he one hand, Simpli ica ion Be o e (SBG) and Du ing (SDG) Gene a ion app oaches [2]-[4] ha e ex ended he analyzable ci - cui sizes and ha e made he symbolic exp essions in e p e able bu a e s ill insu icien o e y la ge ci cui s. Hie a chical analysis echniques cons i u e an al e na i e o ana- lyze e y la ge ci cui s al hough epo ed echniques do no inco - po a e app oxima ion capabili ies, making in e p e a ion and as e alua ion o he esul s a p oblem [5]-[7]. Recen ly, new echniques based on De e minan Decision Dia- g ams ha e been p oposed, which a e able o ep esen he exac ci cui beha io in a compac , al hough unin e p e able, o m 81 ,PI. The me hodology p esen ed in his pape is buil on he ideas in [IO] o o mula e and implemen a hie a chical analysis me hodol- ogy able o inco po a e he ci cui educ ion and dominan con i- bu ion s a egies con ained in SBG and SDG echniques. The pape is o ganized as ollows. Sec ion 2 e iews and compa es exis ing symbolic analysis echniques. Sec ion 3 desc ibes he hie - a chical modeling me hodology while Sec ion 4 in oduces he app oxima e analysis s a egy. Finally, Sec ion 5 p esen s expe i- men al esul s o assess he quali y o he me hodology. 2. Re iew o p e ious app oaches 2.1. App oxima e la analysis echniques The i s app oxima ion app oaches we e based on Simpli ica ion A e Gene a ion (SAG) echniques, ha p une he leas signi ican symbolic e ms once he exac exp ession has been compu ed. * This wo k has been suppo ed by he ESPRIT P ojec #21812 (AMA- DEUS) and he Spanish C.I.C.Y.T. unde con ac TIC97-0580. Al hough he in e p e abili y was g ea ly imp o ed, he ini ial gen- e a ion o he exac exp ession exhaus ed he compu e esou ces e en in case o medium size ci cui s [I]. To sol e bo h, he in e p e abili y and he excessi e consump ion o compu e esou ces, wo new ideas we e in oduced: SBG ech- niques, which simpli y he sys em o ci cui equa ions (a he ma ix o he g aph le el) be o e being sol ed; and SDG ech- niques, which calcula e di ec ly an app oxima ed solu ion o he sys em o ci cui equa ions, con aining ,only he dominan con ibu- ions [2]-[4]. 2.2. Hie a chical analysis echniques T adi ionally, a h ee s ep app oach has been used (see M.M. Has- soun's "Hie a chical Symbolic Analysis o La ge Analog Ci cui s" - Chap e 5 in [I] o a de ailed e iew): Di ision o he ci cui in subblocks (ci cui pa i ioning). Cha ac e iza ion o he lowes le el blocks in e ms o hei inpu s and ou pu s ( e minal block analysis). I e a i e cha ac e iza ion o blocks in e ms o hei inpu s and ou pu s by pe o ming ope a ions on he cha a e iza ions o he cons i uen subblocks (middle block analysis) Fo e minal and middle block analysis, h ee app oaches ha e been epo ed: Coa es lowg aph, Mason lowg aph and di ec ne - wo k me hods. The Coa es lowg aph me hod equi es o build he Coa es g aph, which is hen pa i ioned [5]. Pa i ioning de ined by he use is no possible. Besides, since he Coa es g aph does no co espond wi h ci cui nodes and b anches, pa i ioning in o ma ion canno be di ec ly mapped o he ci cui le el. Mason signal lowg aph echniques use educ ion echniques on Mason's g aphs o yield a desc ip ion o each block in e ms o i s inpu and ou pu nodes only [6]. Finally, a combina ion o he blocks is made applying he same educ ion echniques o ge a desc ip ion o he en i e ci cui . The di ec ne wo k me hod ope a es by educing he Modi ied Nodal Analysis (MNA) ma ix, ep esen ing each subci cui in o a Reduced ModiJied Nodal Analysis ma ix, which only depends on e minal nodes o he block. A e wa ds, a successi e ecombina- ion o such ma ices is pe o med o ob ain a educed ma ix ep- esen ing he en i e ci cui 271. 2.3. DDD-based analysis echniques The echnique is based on he ep esen a ion o he symbolic exp essions by means o De e minan Decision Diag ams, ha a e signed oo ed acyclic g aphs wi h wo e minal e ices. This ep- esen aion is buil om he ma ix ha models he ci cui , exploi - ing he spa si y and sha ing o p oduc e ms [8], he e o e i inds i s main ad an age in case o epe i i e opologies (like ladde - s uc u ed ne wo ks). 2.4. Compa a i e discussion Al hough he e is no a p ecise limi o he applicabili y o app oxima e Ra analysis echniques (i depends on he ci cui 0-7803-5482-6/99/$10.00 02000 IEEE 111-133 size, model complexi y, ci cui connec i i y, igh ness o e o speci ica ions), such bounda y exis s. Beyond, al e na i e me hods a e needed; in pa icula , hose exploi ing he inhe en hie a chy in he cons uc i e p ocess o la ge ci cui s. The hie a chical Coa es lowg aph me hod will no dese e con- side a ion due o i s inabili y o handle p e-pa i ioned ci cui s. Nei he he di ec ne wo k me hod, no he Mason lowg aph me hod inco po a e app oxima ion echniques. This exceedingly hampe s hei applica ion o la ge p ac ical ci cui s which is co - obo a ed by he ac ha epo ed expe imen al esul s use ex emely simple block models; i.e. il e s using ideal models o he opamps. DDD-based me hods ep esen ci cui beha io in a compac o m. Al hough, such compac s uc u e is unin e p e able and CPU-in ensi e o build, hei main ad an age is hei as nume ical e alua ion. When hey a e used o gene a e app oxima e (in e p e - able) symbolic exp essions [8] hey a e no compe i i e o exis ing SBG and SDG app oaches. They ha e also been applied o hie a - chical analysis in a simila ashion o he Di ec Ne wo k me hod and using DDDs o ep esen ma ix de e minan s [9]. Howe e , no e o -con olled app oxima ion o symbolic exp essions ex ac ed om such DDD has been epo ed. 3. Hie a chical modeling me hodology In ou me hodology, blocks a e pa i ioned (de ined by he use o au oma ically pe o med) in se e al hie a chical le els. This hie a - chical s uc u e can be ep esen ed as an in e ed ee, as he exam- ple in Fig. 1 shows. Figu e 1. Example o in e ed ee ep esen a ion. Lea nodes ( e minal blocks) a e modeled by he subs i u ion o cons i uen de ices by hei co esponding models. Non-lea nodes (middle blocks) a e modeled using a ( ans)admi ance desc ip ion as Fig. 2 illus a es o a h ee- e minal block. Concep ually, each ( ans)admi ance is a unc ion o he models a he immedia e hie - a chical le el. An analogous desc ip ion esul s when subblock ma ices a e com- bined in he Di ec Ne wo k app oach [7], bu such me hodology p e en s he applica ion o e o -con olled app oxima ion s a e- gies. Figu e 2. (T ans)admi ance desc ip ion o blocks. The me hodology p esen ed he ein gene a es app oxima ed exp es- sions o he needed ( ans)admi ances o each middle block as a unc ion o he ( ans)admi ances o he sub-blocks a he ollow- ing le el down he hie a chy (de ice models in case o eiminal blocks). 4. App oxima ion s a egy Ou app oxima e analysis me hodology ollows he low diag am in Fig. 3. I s a s om a hie a chical ci cui desc ip ion and in o - ma ion on he ne wo k unc ion o calcula e, magni udelphase e o cons ain s and equency in e als. Hie a chically-decomposed Ci cui In e nal Block Size Checking Pa i ion Figu e 3. Module s uc u e. The Ci cui Reduc ion module pe o ms node con ac ions and de ice emo als whose con ibu ion o he global ci cui beha io is negligible. The e o in oduced by hese ci cui ans o ma ions is ca e ully con olled by using algo i hms based on in e al analy- sis echniques o gua an ee ha e o speci ica ions a e no iola ed wi hin he speci ied equency ange [4]. Ci cui equa ions mus be sol ed o con ol magni ude/phase e o s. This is a nume ical p o- cess and is he e o e mo e e icien ly pe o med by using an A4NA ma ix o mula ion and spa se ma ix echniques o i s solu ion. This ci cui educ ion echnique is applied o he comple e la ci - cui , al hough he p ede ined pa i ions a e o mally kep , so ha hey can be ebuil when he educ ion p ocess is inished. Since e y e icien spa se ma ix echniques a e used in he e o e aJua- ion, no signi ican ad an age is gained om applying he educ ion echnique o he componen blocks sepa a ely. Mo eo e , a sepa a e applica ion o each block would equi e an e o p opaga ion mech- anism a his ea ly s age o he analysis p ocess. This necessa ily yields mo e conse a i e esul s (less educed ci cui s) and, come- quen ly, has a nega i e impac on he global pe o mance o he analysis me hodology. The e ec o he ci cui educ ion is no only he size educ ion o he e minal blocks bu also he elimina ion o many o he model- ing ( ans)admi ances o he middle blocks. A e he ci cui educ ion p ocess, he hie a chical s uc u e is econs uc ed and Block Checking s ep s a s. I a simpli ied block con ains a oo small numbe o de ices o in e nal nodes, analyzing i as an independen block becomes e y ine icien . Then, i is ad isable o join he block o i s bes neighbo o inco po a e i in o he immedia ely uppe hie a chical le el. On he con a y, e en a e he ci cui educ ion, some block may s ill con ain oo many nodes and de ices o an e icien symbolic exp ession gene a ion. In his case, an in e nal pa i ioning is p o ided which inds op imal blocks o he subsequen exp ession gene a ion module. The in e nal pa i ioning mechanism p o ides he solu ion o he case in which no p e-de ined blocks a e gi en. A e he ci cui 111- 134 educ ion s ep, he ci cui a hand is in e nally pa i ioned o gene - a e a numbe o blocks ha enables an op imal esul in e ms o compu a ional ime and exp ession complexi y. To p ese e use equi emen s, bo h p ocesses: in e connec ion and pa i ioning, can be con olled by he use . Once he hie a chical block s uc u e has been ebuil and checked, a ci cui whe e blocks a e modeled in e ms o he ( ans)admi - ances is buil up. Then, app op ia e analysis algo i hms gene a e app oxima e symbolic exp essions o each ( ans)admi ance o each block in he s uc u e as a unc ion o he componen de ices o ha block. Analogous analysis algo i hms a e applied o ob ain he desi ed ne wo k unc ion (de ined by he global inpu /ou pu signals o he ci cui ) in e ms o he ( ans)admi ances modeling he blocks a he uppe mos hie a chical le el. When symbolically analyzing a block, a se o ne wo k equa ions ( opological and cons i u i e ela ionships) has o be sol ed. Fo he app oxima e symbolic solu ion o a se o linea equa ions, g aph me hods ha e p o en o be supe io [4]. E icien echniques a ailable o la ci cui s (based on he wo-g aph me hod) can be used a each hie a chical le el, as e minal blocks a e la in e con- nec ions o basic ci cui elemen s, and he same happens in middle blocks once he componen subblocks a e eplaced by he co e- sponding ( ans)admi ances. The ope a ion o he e o -con olled e m gene a ion is shown in Fig. 4. Ini ially, a equency alue is chosen. Each elemen has i s admi ance as associa ed weigh . The weigh o each ( ans)admi ance is a complex numbe because i unc ionally depends on all he de ices composing such block. The con ibu ion o each ( ans)admi ance o he global ci cui beha io is hen nume ically e alua ed. This is e icien ly done using a hie a chical MNA o mula ion and spa se echniques o sol e he ma ices. The magni ude o hese con ibu ions indica es which e m gene a o mus become ac i e. The gene a ion p ocess con inues i e a i ely un il he e o c i e ion is me . Ob iously, his is gua an eed only a he selec ed equency sample. An algo i hm o maximum e o de ec ion, which elays in a obus nume ical e e ence gene a o and in e al analysis O iginal Ci cui No Gene a o Figu e 4. E o -con olled exp ession gene a ion echniques is used o de ec equency alues whe e he e o s a e exceeded [4]. Then, he p ocess is epea ed un il he e o c i e ia a e me in he equi ed equency ange. 5. Expe imen al esul s Two examples a e analyzed using he p oposed echnique. Each is . ep esen a i e o di e en applica ion scena ios: a ci cui com- posed o blocks ( oo la ge o be analyzed using la analysis algo- i hms) and a building block desc ibed a he ansis o le el. 5.1. A band-pass il e The i s example is a decision band-pass il e used in an FSK modem and shown in Fig. 5(a), whe e he OTA ansis o -le el schema ics in Fig. 5(c)-(d) and he ansis o model in Fig. 5(b) we e used. The magni ude/phase e o cons ain s a e ]AMag 5 1 dB , ]APhs( I5 deg ees in 10 Hz I 5 lO'Hz. 4 .. Figu e 5. (a) Band-pass il e ; (b) small-signal model; (c) biasing OTA; (d) OTA schema ics. P e iously exis ing hie a chical app oaches did no inco po a e app oxima ion s a egies and, he e o e, could analyze he ci cui in Fig. 5(a) only i e y simple mac omodels ins ead o ansis o - le el desc ip ions o he OTAs we e used. The small-signal expansion o he ci cui yields a ci cui model wi h 618 de ices and 45 nodes. A e he ci cui educ ion s ep, he expanded model con ains 67 de ices and 26 nodes, which means a la ge educ ion, bu no enough o la analysis algo i hms. Applying ou hie a chical app oach, he ollowing ans e unc ion is ob ained in 100 seconds o CPU ime: (1) aB9.bp.in . (aB8.lp.lp + C, . s) - aB7.bp.l~ aB8.lp.bp + aB8.lp.lp. C, . s + C, . C, . s2 T = whe e he ( ans)admi ances a e he ollowing app oxima e sym- bolic exp essions: (3) 111-135 (-gm I I g ~ 14g ~ (gds, + gds,) - gm ,2giii 13gm lBgd~~2 aB8.lp.bp= gin,lgin1,(g n12 + gds2 + gds,) (5) The e o be ween he magni ude and phase beha io p edic ed by eqs. (1)-(5) and he magni ude and phase beha io o he o iginal ci cui is shown in Fig. 6. 1.0 U 0.5 1 ? 1 o5 lo6 equency (HZ) io7 5.0 1 I -3 U 1 o4 1 o5 lo6 equency (HZ) io7 Figu e 6. Magni ude and phase e o s. 5.2. pa741 ampli ie Now, he p741 ope a ional ampli ie in Fig. 7 will be analyzed. The magni ude/phase e o cons ain s ‘a e (AMng( I 3 dB , (Apk l I 10 deg ees in 1 Hz I I 106Hz, o include he comple e gain-bandwid h p oduc o he ampli ie . Al hough he ne lis is inpu wi h a p ede ined pa i ioning, which is shown in Fig. 7, he in e nal pa i ion size checking de ec s ha he block s uc u e a e he ci cui educ ion s ep is no adequa e o be e icien ly handled. The e o e, i p o ides some pa i ioning sugges ions (joining Bias, SC-p o and Ou pu s ages o he uppe le el). Te m gene a ion yields, hen, he ollowing ol age gain: (6) uSec 17.9 . ulnp9.4 go,3B’ (ulnp9.9 + aSec9.9) - uSec9.17. uSecl7.9 H(s) = whe e he ( ans)admi ances o he blocks a e gm3 ’ g!n6 ’ (gml + s ’ CZI) alnp9.4 = - uInp9.9 = go4 gm5 . (g nl + gi 3) gg. 5’16. $‘I7 uSec9.9 = 911116. S“117 These esul s a e ob ained in 4.8 seconds o CPU ime. A la analysis ool wi h he same e o speci ica ions p o ides a ne wo k unc ion con aining 53 symbolic e ms. 6. Conclusions This pape has in oduced a me hodology o he inco po a ion o app oxima ion s a egies in o a hie a chical analysis echnique. On he one hand, his o e comes he p oblems o app oxima e la analysis echniques when add essing e y la ge ci cui s. On he o he , he inhe en hie a chy o la ge ci cui s is espec ed bu he in oduc ion o app oxima ion echniques makes he esul s mo e in e p e able and mo e e icien ly e alua ed han wi h con en ional hie a chical analysis echniques. Figu e 7. pa741 ope a ional ampli ie wi h explici block pa i ioning and small-signal model o ansis o s. 7. Re e ences F. V. Femindez, A. Rod iguez-Vizquez, J. L. Hue as and G. Gielen, Eds., Symbolic Analysis Techniques. Applica ions o Analog Design Au oma ion. Pisca away, NJ: IEEE P ess, 1998. P. Wambacq, F.V. Femindez, G. Gielen, W. Sansen and A. Rod iguez-Vizquez, ”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 J. Solid-S a e Ci cui s, ol. 30, No. 3, pp. 327- 330, Ma ch 1995. Q. Yu and C. Sechen, “A uni ied app oach o he app oxima ed symbolic analysis o la ge analog in eg a ed ci cui s” IEEE T ans. Ci cui s and Sys .-I, Vol. 43, No. 8, pp. 656-669, 1996. 0. Gue a, J.D. Rod iguez-Ga cia, E. Roca, F.V. Fe nlndez and A. Rod iguez-Vhquez, “A simpli ica ion be o e and du ing gene a ion me hodology o symbolic la ge-ci cui s analysis” P oc. IEEE Inc. Con$ Elec onics, Ci cui s andSys ems, Vol. 3, pp. 81-84, Lisbon, Sep embe 1998. J. A. S a zyk and A. Konczykowska, “Flowg aph analysi:s o la ge elec onic ne wo ks,” IEEE T ans. on Ci cui s and Sys ., M. M. Hassoun and K. S. McCa ille, “Symbolic analysis o la ge-scale ne wo ks using a hie a chical signal lowg aph app oach,” Analog In . Ci cui s and Signal P oc., ol. 3, pp. 3 1- 42, Kluwe , Bos on, 1993. M. M. Hassoun and P. M. Lin, “A hie a chical ne wo k app oach o symbolic analysis o la ge-scale ne wo ks,” IEEE T ans. on Ci cui s and Sys .4, ol. 42, No. 4, pp. 201-211, Ap il 1995. X.D. Tan and C.J.R. Shi, “In e p e able symbolic small-signal cha ac e iza ion o la ge analog ci cui s using de e minan decision diag ams“, P oc. o he Design Au oma ion Con$, pp. X.D. Tan and C.J.R. Shi, “Hie a chical symbolic analysis o la ge analog ci cui s wi h de e minan decision diag ams”, P oc. IEEE In . Symp. Ci cui s and Sys ems, pp. 3 18-32]. June 1998. ol. CAS-33, NO. 3, pp. 302-315, Ma ch 1986. 448-453, Ma ch 1999. [lo] 0. Gue a, J.D. Rod iguez-Ga cia and A. Rod iguez-V izquez, “T ue Hie a chical Symbolic Analysis o La ge-scale Analog In eg a ed Ci cui s” P oc. In . Wo kshop on Symbolic Me hods &Applica ions o Ci cui Design, pp. 164-167, Oc obe 1998. 111- 136