Synthesis of IDDQ-Testable Circuits: Integrating Built-in Current Sensors

SYNTHESIS OF IDDQ-TESTABLE CIRCUITS: INTEGRATING BUILT-IN CURRENT SENSORS H.-J. Wunde lichl, M. He zogl J. Figue as2, J.A. Ca asco2, and A. Calde 6n2 (1)Ins i u e o Compu e S uc u es, Uni e si y o Siegen, Hoelde lins . 3,57068 Siegen, Ge many (2)Depa men o Elec onics Enginee ing, Uni e si a Poli ecnica de Ca alunya, Diagonal 647, pl a. 9,08028 Ba celona, Spain Abs ac "On-Chip" IDDQ es ing by he inco po a ion o Buil - In Cu en (BIC) senso s has some ad an ages o e "o - chip" echniques. Howe e , he in eg a ion o senso s poses analog design p oblems which a e ha d o be sol- ed by a digi al designe . The au oma ic inco po a ion o he senso s using pa ame e ized BIC cells could be a p o- mising al e na i e. The wo k epo ed he e iden i ies pa i ioning c i e ia o guide he syn hesis o IDDQ- es able ci cui s. The ci cui mus be pa i ioned, such ha he de ec i e IDDQ is obse able, and he powe supply ol age pe u ba ion is wi hin speci ied limi s. In addi ion o hese cons ain s, also cos c i e ia a e consi- de ed: ci cui ex a delay, a ea o e head o he BIC sen- so s, connec i i y cos s o he es ci cui y, and he es applica ion ime. The pa ame e s a e es ima ed based on logical as well as elec ical le el in o ma ion o he a - ge cell lib a y o be used in he echnology mapping phase o he syn hesis p ocess. The esul ing cos unc- ion is op imized by an e olu ion-based algo i hm. When un o e la ge benchma k ci cui s ou me hod gi es signi ican ly supe io esul s o hose ob ained using simple and less comp ehensi e pa i ioning me hods. 1 In oduc ion The es me hodology based on he obse a ion o he quiescen cu en (IDDQ) complemen s logic ( ol- age) es ing in CMOS echnologies. The quiescen cu en consumed by he IC is a good indica o o he p esence o a la ge class o de ec s escaping logic es [l-61. On-chip Buil -In Cu en (BIC) senso s ha e been p oposed o o e come some o he p oblems encoun- e ed in o -chip IDDQ es ing: long es ing imes and low disc imina ion o small de ec i e cu en s. These This wo k has been pe o med wi hin he amewo k o he ESPRIT P ojec 7107 A chimedes p oblems can be sol ed by pa i ioning he Ci cui Unde Tes (CUT) in subci cui s, each p o ided wi h a BIC senso . In ecen yea s, di e en BIC senso s ha e been p oposed [7-111. Some BIC senso s (i.e. pn junc i- ons o bipola de ices) in oduce a ol age d op du ing ansien swi ching which can be unaccep able in some applica ions due o i s e ec s in delay and noise ma - gin educ ion. Fo hese applica ions he BIC senso s ha e o inco po a e a bypass elemen so ha he pe - u ba ion in he i ual g ound is below a ce ain maxi- mum. The class o BIC senso s conside ed in his pape is illus a ed in igu e 1. The BIC senso includes a sen- sing de ice, a bypass MOS swi ch and a de ec ion ci - cui y. A con ol signal C is applied o he ga e o he bypass MOS de ice. Du ing no mal ope a ion, C = 1, u ns he MOS on. Du ing es ing, i s C is se o 1 and a es pa e n is applied o he CUT. When he ansien iDD cu en has decayed, C is se o 0, u ning he MOS o , and he sensing de ice p oduces a ol age signal which is p ocessed by he de ec ion ci cui y o p oduce a PASSFAIL signal, depending on whe he he sensed IDDQ alls below/abo e a gi en h eshold alue IDDQ,~~. Se e al sensing de ices can be used [7- 121, each wi h i s ad an ages and disad an ages. This kind o es abili y enhancemen may cause ex a delay and a ea o e heads as well as a educ ion o he noise immuni y ma gins [8,9,12,13,15], and he objec i e o a sophis ica ed BIC senso placemen should be minimi- zing hese d awbacks. Im- es o la ge CUTS canno be done e ec i ely using a single BIC senso . One ob ious eason is he need o an app op ia e disc iminabili y. E ec i e es o de ec s in CMOS ypically equi es IDDQ, h = IPA and non de ec i e IDDQ cu en s o la ge ci cui s can be la ge han 1 PA. Also, he la ge pa asi ic capaci ance in oduced a he sensing node by he CUT and he sen- sing de ice ad e sely impac s es imes. These p o- blems can be alle ia ed by pa i ioning he CUT in o 573 1066-1409/95 $4.00 0 1995 IEEE g oups o ga es and in oducing a BIC senso o each L de ec ion i ual GND - ci cui y - g oup [12,13]. + PASS / FAIL pe io i y o his app oach o e a s aigh o wa d manual BIC senso placemen . "DD 4 Figu e 1: A chi ec u e o a BIC senso wi h a bypass de ice. Fine-g ain pa i ions yield high disc iminabili y and low es imes bu incu in high a ea o e head due o he ( eplica ed) de ec ion ci cui y, ex a ou ing caused by he in oduc ion o he i ual ail and ou ing among BIC senso s. Coa se-g ain pa i ions ha e smalle a ea o e heads bu gi e smalle disc imina- bili ies and longe es imes. In addi ion, he ,,shape" o he g oups can ha e a g ea in luence on he equi ed BIC senso a ea. This is illus a ed in igu e 2, which shows wo di e en pa i ions o a CUT wi h a wo-di- mensional a ay s uc u e in ol ing h ee cell ypes. Pa i ion 1 has an a e age maximum iDD in each g oup smalle han pa i ion 2 as he h ee cells C1, C2, C3 will no swi ch in pa allel; hus, using pa i ion 2, he swi ching de ices ha e o be g ea e o gua an ee he same limi s o he i ual ail pe u ba ion, and pa i ion 1 should be p e e ed. Finding good pa i ions o IDDQ es abili y is a complex p oblem whe e disc iminabili y be ween aul y and aul ee cu en , a ea o e head, delay deg ada ion and es applica ion ime ha e o be conside ed. In his pape we p opose an e olu i e op imiza ion me hod o minimizing a cos unc ion subjec o es ic ions. The cons ain s a e disc iminabili y and i ual ail pe u ba- ion. The cos unc ion is ob ained by weigh ing es ima- o s o he di e en cos s in ol ed in he ade-o . These es ima o s make an app op ia e ade-o be - ween accu acy and compu a ion complexi y and a e e alua ed using pa ame e ized elec ical le el in o ma- ion o he a ge echnology. The es o he pape is o ganized as ollows. Sec ion 2 s a es o mally he pa - i ioning p oblem and i s cons ain s. Sec ion 3 de- sc ibes he es ima o s used in he cos unc ion. Sec ion 4 su eys he e olu ion op imiza ion algo i hm. The ex- pe imen al esul s discussed in sec ion 5 show he su- Pa i ion 1 ; BIC-Senso a BIC-Senso I BIC-Senso I Pa i ion 2 Figu e 2: Two pa i ions illus a ing he impac o he g oup shape in BIC senso a ea. 2. P oblem s a emen and cons ain s. To se -up o mally he pa i ioning p oblem, he CUT is modelled by a di ec ed g aph C = (G, T), whe e G is he se o ga es and T includes he connec ions among he ga es. .4 pa i ion Il o G is a collec ion {MI, ..., Mk} o disjoin g oups o ga es (modules) co- e ing G (U;"=, M, = G). Each ga e is comple ely included in one g oup, hence no ansis o g oup is spli among g oups, a oiding po en ial la chup p oblems [11,14]. Le IDDQ,~~ be he minimum de ec i e IDDQ cu en which has o be de ec ed and le IDDQ,~,, be he maximum non-de ec i e cu en o module M, The disc iminabili y o M, is de ined as 'DDQ. h 2d. IDDQ.nd.1 4 (4 1 = Fo he easibili y o an IDDQ es , d > 1 is equi ed, 574 and a ypical alue is 10. This es ic ion can be ex- p essed by a cons ain e alua ion unc ion de ined on he se o all possible pa i ions P as : P -+ (0,l) wi h K V d(Mi) 2 d i=l (n) = 1 The o he a ge s conce ning speed and a ea can be desc ibed by a global cos unc ion C on each pa i- ion. I is de ined as C: P -+ R in e ms o he ela i e weigh s ai o he me ics ci: n i=l The pa ame e s de ined abo e allow es ablishing he global cos unc ion o op imiza ion in he design space Speed-A ea-Tes abili y acco ding o di e en p io i ies e lec ed on he alues o he weigh ac o s ai. Cons ain s and cos s lead o a pa i ioning p oblem as ollows: Pa i ioning P oblem PART-IDDQ : Find a pa i- ion ll* sa is ying he cons ain s (Il*) and a he same ime minimizing he global cos unc ion c(n*). In gene al, his p oblem is NP-ha d, and heu is ics o ind accep able solu ions a e p oposed. In addi ion, he p ecise e alua ion o he cons ain s and he cos unc ions a e elec ical le el p oblems which a e no sol able in accep able ime excep o e y small ci - cui s. In he nex sec ion, app oxima e es ima ing p o- cedu es a e p esen ed using he ga e le el desc ip ion o he CUT and he a ge cell lib a y. 3 Maximum cu en and cos es ima o s In his sec ion a se o es ima o s o he a iables necessa y o e alua e he cons ain s and cos s a logic le el a e p oposed. A a ge cell lib a y ully cha ac e- ized a elec ical le el is assumed a ailable. 3.1 A pe u ba ion o he Vi ual G ound (Vi ual VDD) is caused by he inco po a ion o he I~SQ (IDDQ) BIC senso s. This a ia ion o he powe supply ol age cau- ses a educ ion o he noise immuni y ma gins. In addi- ion, ci cui s wi h memo y elemen s may loose he memo ized in o ma ion. The wo s pe u ba ion occu s du ing swi ching when he cu en is maximal. A con- s ain pu on his ol age d opping is usual o choosing he size o he BIC senso s. The ol age d opping de- pends on he maximum ansien cu en D,,,,,j h ough module Mi and on he senso a ea. Fo each module Mi he maximum ansien cu en A ea o e head due o BIC sensing. is es ima ed by he maximum numbe o ga es o modules swi ching simul aneously. In o de o es ima e a alue a logic le el we assume ha all ga es loca ed a he same dep h on di e en pa hs, swi ch in a way ha hei maximum cu en s add. This is a pessimis ic assump ion as we do no conside pa hs possibly blocked. This simpli ies he p oblem, and only he possible pa hs o all ansi ions and he maximum simul anei y o ansi ions a e iden i ied. Fo each ga e gi all possible Li ansi ion pa hs and he imes o ansi ion .. a i al a e de e mined. In his way a se o in- ege s i, i,. . ., & , ..., 'pL, is compu ed indica ing he possible imes o ansi ions a he ga e gi o each pa h Pk, whe e k:= 1 ,..., Li. An uppe limi o max(iDD} o a g oup Mi o ga es is compu ed by 1 The es ima e o DD,mm,, is app oxima e and pessimis ic, bu is compu a ionally e icien enough o allow explo a ion o a la ge numbe o pa i ions in easonable amoun s o CPU ime. Le Rs,~ be he ON esis ance o he BIC senso o Mi, he maximum i ual ail pe u ba ion can be ap- p oxima ed by Rs,i * DD,m,,i. The maximum i ual ail pe u ba ion o each module is limi ed o a gi en p ede ined alue , yielding * Since he equi emen s o a e ypically e y s ingen (be ween l00mV and 300mV) he impac o he easible Rs,~ on he delay o he CUT ends o be small. Then, o simpli y he op imiza ion p oblem we ake: * .. I Rs,i = , l4iIK. The senso a ea cos es ima o is compu ed using an a ea model o he o m 4 +A, I Rs o each BIC senso , whe e he e m 4 accoun s o he de ec ion ci cui y and he e m AI I Rs accoun s o he sensing elemen and he bypass de ice. This gi es DD, max,i As all componen s o he objec i e unc ion should ha e simila ange and a ia ion o op imiza ion easons we ac ually compu e CI (II):= log(A) 515 3.2 Delay o e head due o BIC senso s. The delay o e head cos is compu ed as: whe e D is he delay o he ci cui wi hou BIC senso s and DBIC is he delay o he ci cui wi h BIC senso s. Bo h delays a e compu ed using a longes pa h algo- i hm. The ga e delays DBIc(g, ) ( hese delays a e ime g id unc ions) used o DBIC a e ob ained om he nominal ga e delays (wi hou BIC senso ) D(g) and deg ada ion ac o s 6(g, ) as The ga e delay deg ada ion ac o 6(g, ) is ob- ained using a second o de elec ical ne wo k model ha ing as pa ame e s Rs ( he BIC senso ON esi- s ance), Cs ( he pa asi ic capaci ance a he i ual ail node), Cg ( he equi alen capaci ance a he ou - pu o g), Rg (an a e age equi alen ON esis ance o he discha ging ne wo k o a ga e o he CUT), and n( ) ( he ac i i y-numbe o simul aneously swi ching ga es a ime ). Wi h hese assump ions he exp es- sion o he ga e delay deg ada ion becomes The in e connec ion cos s a e di ided in o cos s o linking he BIC senso s o he ga es wi hin each mo- dule, and he cos s o connec ing he BIC senso s o all modules by he es clock and es ou pu . The mo- dule in e connec ion cos s ake in o accoun he di i- cul y in sensing ga es placed in emo e loca ions. The sepa a ion pa ame e S(gj,gj) o wo ga es gj and gj is he minimum numbe o nodes a e sed when going om gj o gj in he undi ec ed g aph o he logic ci - cui . I S(gj,gj) exceeds a ce ain pa ame e say p, o i no pa h exis s be ween gj and gj, we se The sepa a ion pa ame e S(M) o a module M is de ined as he sum o he sepa a ion pa ame e s o all ga e pai s: S(gi,gj):= P. R; .Rj EM In ui i ely, he pa ame e dec eases i many nodes o S(M) a e connec ed, and i is minimum i M is a clique o he undi ec ed ci cui g aph. The o e all in e connec ion cos o a pa i ion El o K g oups o ga es Mk whe e k = 1,. . ., K can be es i- ma ed by: K S(n) = S(Mk >. k=l As a cos unc ion we use c3 (El): = log( S( n)). The calcula ion ime o his me ic g ows quad a- ically wi h he numbe o ga es o each pa i ion g oup Mk. Since, in p ac ice, he numbe o ga es o a pa - i ion g oup is ela i ely small he p oblem is no oo se e e. As also he senso s mus be in e connec ed by he es clock line and he es signal line we use ~,(n):= K. 3.4 Tes applica ion cos s. The es applica ion ime o a p ecompu ed es ec- o se o he global CUT is es ima ed. Since he p opo- sed pa i ioning app oach does no modi y he logic s uc u e, he es ec o se needed o achie e a ce - ain quali y goal, does no change. Howe e , he ime equi ed o each ec o may be signi ican ly di e en due o di e en IDDQ se ling imes o di e en pa i- ions. Fo he es applica ion ime we use we e DiIc is he sum o DBIc and a e m A(zi) ac- coun ing o he iDD decay ime and he sensing ime, es ima ed om SPICE le el simula ions as a unc ion o he BIC senso ime cons an ZS,~ = Rs,iCs,i ((2s.; is he pa asi ic capaci ance a he i ual ail o g oup Mi ). 4 Pa i ioning Algo i hm Looking o a pa i ion ha sa is ies condi ion (n) and minimizes he cos unc ion is a e y complex, NP- ha d op imizing p oblem, and i is impossible o e alua e he cos unc ion C(n) o all he pa i ions. Also e alua ing C(n) o a single pa i ion is a he complex as i a ies be ween O(n) and O(m;) whe e mi is he size o a module. Hence a heu is ic algo i hm is needed which e alua es jus a mode a e numbe o pa i ions bu is no caugh in a local minimum. A a ie y o algo i hms has been p oposed o such kind o p oblems ( o ce-d i- en, simula ed annealing, Mon e Ca lo, gene ic, e. g.), in his pape an e olu ion-based algo i hm is applied. 576 4.1 Sol ing combina o ial p oblems by e olu ion based algo i hms Fo con olling he op imiza ion s eps an e olu ion- based algo i hm is adap ed [17,18,19]. A single cycle o such an algo i hm consis s o h ee s eps epea ed su i- cien ly o en: ecombina ion, mu a ion, and selec ion. Recombina ion: A popula ion consis s o a numbe o indi iduals called pa en s which co espond o pa i- ions in ou case. These pa en s p oduce descendan s by ecombining hei a ibu es. In ou case i u ned ou ha his s ep should be simpli ied such ha jus one pa- en is su icien o a child, and ecombina ion is jus duplica ion. Mu a ion: The child pa i ions a e modi ied an- domly co esponding o ce ain ules. These ules en- su e ha he modi ied pa i ion is s ill in he neighbou - hood o he o iginal one. Selec ion: The indi iduals p oduced so a a e e alua ed. The bes o hem a e he pa en s in he nex cycle. The con e gence o his p ocedu e depends on he s a popula ion, and on he se o con ol pa ame e s used. 4.2 Adap a ion o PART-IDDQ The s a pa i ions a e de e mined by simpli ying he cos unc ion such ha jus cl(l7) (a ea o e head) and cz(Il) (delay o e head) a e conside ed. Fi s he app op ia e module size is es ima ed. This can be done by e alua ing cl(Il) and c,(Il) by a e age numbe s o he equi ed pa ame e s and by abs ac ion om s uc u al in o ma ion. Then ga es a e clus e ed o mo- dules as ollows: s a ing om a ga e close o a p ima y inpu ga e, chains a e o med owa ds a p ima y ou pu . The p ocess s ops i his pa h eaches a p ima y ou pu , o i he e is no ee ga e anymo e, o i he maximum module size is eached. Modules a e o med as long as he e a e ee ga es. Using di e en chains he equi ed numbe o s a pa i ions is cons uc ed. The e olu ion cycle is con olled by a se o pa a- me e s as p oposed in [ 18,193 : CL: Numbe o pa en s h: Numbe o child en pe pa en x: Numbe o Mon e Ca lo descendan s 0: Maximum li e ime m: Maximum numbe o ga es o be mo ed E: Va ia ion o m The e olu ion cycle s a s wi h p di e en s a pa - i ions Ill,. . . , Ilp . Child en a e gene a ed by copying each o he pa en indi iduals A imes, and by mu a- ion a e wa ds. The mu a ion scheme o each o he (p*A) de- scendan s is as ollows: A module Mi a om he pa - i ion I?:= {M:, ...,Mii} is selec ed, and he numbe mbpu,& y o i s bounda y ga es is de e mined. A ga e o Mi a is a bounda y ga e i i is di ec ly connec ed o a ga e ou side Mi a . As a uni o mly dis ibu ed andom a iable we selec he ac ual numbe mmo e E {I ,..., min{m,m~ounda y)) o ga es o be mo ed. The m,,,, ga es a e chosen andomly, and pu in o he a ge module hey a e connec ed wi h. I hey a e connec ed wi h se e al a ge modules a andom one is chosen. In addi ion o hese (p*A) mu a ed child en, (p *x) Mon e-Ca lo child en a e gene a ed. Again, each pa en indi idual is copied x imes. A andom numbe o ga es o a andom module AIs a is mo ed in o a andom module M a ee . The andom a ia ion o hese descendan s is highe compa ed wi h mu a ions, and hey educe he p obabili y o being caugh in a lo- cal minimum. I all ga es o M,,, a e mo ed, his module is dele ed. A e ga e mo ing, cos s a e ecom- pu ed jus o he modi ied modules, and he global cos s o he pa i ion a e upda ed. As no he en i e cos unc ion has o be ecompu ed, he pa i ions gene a ed his way can be e alua ed e y e icien ly. A e exchanging ga es, he s ep wid h o mu a ion m is ecompu ed o each descendan . The new m is subjec o no mal dis ibu ion wi h a iance E a ound he m o s ep be o e. This scheme esul s in (1 + A + x) * p pa i ions. Du ing selec ion, all pa en indi iduals olde han o gene a ions a e dele ed. Ou o he emaining ones, he p pa i ions wi h bes cos unc ions a e selec ed as pa en s o he nex cycle. i 4.3 Example The pa i ioning s eps a e illus a ed using he ISCAS85 benchma k ci cui C17 as an example [16]. Fi s s a pa i ions Ill,. . . , lIp ha e o be cons uc ed as desc ibed abo e, igu e 4 shows pa i ion Ill. The ecombina ion s ep c ea es pa i ion Il: by duplica ing Ill. Du ing mu a ion Ms a := (4,6) is selec ed an- domly, and he bounda y ga es Sboud:= {g4,&} a e de e mined. Randomly m,,,, = 1 and g4 as ga es o be mo ed a e chosen. Wi h M a ge = (2,3) he descendan is shown in igu e 4. Du ing he nex gene a ion he al- go i hm c ea es pa i ion Il:, M,,,: = (2,3,4) is selec- ed and he bounda y se becomes Sbound = {g2, g3, g4 1 . Then ga e g3 mo es o module (6) ( igu e 5). Fo he las s ep he algo i hm selec s module (3,6) o n:. Now bo h ga es g3, g4 mo e o hei speci ic des ina- ion-modules and module (3,6) becomes emp y. A e hese 3 gene a ions he pa i ion Il consis s o wo modules (1,3,5), (2,4,6) and is he op imum pa i ion o C17. 511 I5 I4 I3 I2 I1 02 03 I5 I4 I3 I2 I1 02 03 I5 I4 I3 I2 I1 02 03 Figu e 5: IIi = {(1,5)(2,4)(3,6)], II = {(1,3,5)(2,4,6)} 5 Expe imen al Resul s In his sec ion we p esen a s aigh o wa d me hod o s anda d pa i ioning, and we compa e he esul s o he me hods discussed so a . The p ocess o s anda d pa i ioning s a s wi h a ga e as nea o a p ima y inpu as possible. New ga es a e added un il a speci ied size o he module is gene- a ed, he module size can be de e mined elec ically as desc ibed in sec ion 3, in ou case we ake he num- be s ob ained by he e olu ion based algo i hm. The new ga e added is ha ga e whose pa h leng h o all he ga es al eady clus e ed gi es a minimum sum. I he e a e mul iple choices, a ga e o his se is selec ed such ha he pa h leng hs o all he ga es no ye clus e ed gi e a maximum sum. A pa i ion gene a ed his way con ains modules such ha hei ga es a e connec ed mos closely. 5.1 Pa i ioning he ISCASS5 Ci cui s As all componen s o he cos unc ion should ha e simila ange and a ia ion o op imiza ion easons and in o de o ob ain IDDQ- es able ci cui s wi h minimal a ea-o e head which s ill sa is y pe o mance equi e- men s, he ollowing weigh ac o s we e chosen: C(n) = 9 * c1 (n) + IO5 * c2 (n) + c,(n) + c4 (n) + 10 * c5 (n) The e olu ion-based algo i hm was applied o he ISCAS85 ci cui s using his cos unc ion un il he e- sul s con e ged o a s able alue. compu ing ime de- pends on he s a popula ion, and is no de e minis ic. Bu e en o he la ges ci cui con e gence was ob- ained wi hin a ew hou s on a Sun Spa c wo ks a ion. The esul s a e lis ed in able 1. A s anda d pa i ioning needs om 14.5% o 30.6% mo e ha dwa e o BIC senso s han he op imal pa i- ioning o he e olu ion based algo i hm, bu does no show any imp o emen in sys em pe o mance and es ci cui 11 C1908 1 C2670 I C3540 I C5315 I C6288 I C7522 #modules II 2 I 3 I 4 I 6 I 5 I 6 a ea o BIC senso s senso a ea o e head s anda d 1.08E+6 5.67E+5 2.79E+6 2.87E+6 9.19E+5 5.65E+6 8.27E+5 4.95E+5 2.27E+6 2.29E+6 7.30E+5 4.72E+6 o s an- 30.6% 14.5% 22.9% 25.3% 25.9% 19.7% e olu ion 5.95E-2 e olu ion 5.94E-2 Table 1 : Resul s o s anda d pa i ioning and e olu ion-based pa i ioning. 578 pe o mance. Delays and applica ion imes a e gi en as pe cen age how he inco po a ion o BIC senso s slows down pe o mance. The a ea o he BIC senso s is gi en in uni s whose ac ual size depends on echnology. As echnology mapping is no ca ied ou so a wi ing is no conside ed. Since bo h in case o he s anda d and he e olu ion-based app oach he numbe o modules is he same, he ac ual ou ing cos s a e no expec ed o di e signi ican ly. 6. Conclusions Pa i ioning c i e ia a e es ablished o guiding he au oma ed design o IDDQ- es able ci cui s. They a e exp essed by a mul i- a ge objec i e unc ion o be op- imized by an e olu ion-based algo i hm. Ci cui ex a delay, a ea o e head o he BIC senso s, connec i i y cos s o he es ci cui y, and he es applica ion ime a e conside ed as cos c i e ia. The pa ame e s a e es ima ed based on logical as well as elec ical le el in o ma ion o he a ge cell lib a y o be used in he echnology mapping phase o he syn hesis p ocess. Fo he benchma k ci cui s in es iga ed, he inal design is supe io o esul s o a s anda d pa i ioning. So a only esyn hesis o including BIC senso s has been conside- ed. Nex s ep is con olling he logic syn hesis p oce- du e such ha he p esen ed cos unc ion is conside ed a he ea ly beginning. 7. Glossa y BIC: CUT, C: n: gi: M: n:={Gi, ..., GK}: d: : P -+ (0,l): ai : CI : C: : Li : : ASj 6SlC : buil -in cu en senso ci cui unde es numbe o ga es o CUT ga e numbe i g oup o ga es (module) pa i ion, disjoin g oup o ga es disc iminabili y o aul y and aul - ee case cons ain s weigh ac o cos unc ion global cos unc ion maximum i ual g ound pe u ba ion ansi ion pa h ansi ion ime o pa h j a ea o BIC senso i delay wi h connec ed BIC senso delay wi hou BIC senso o ced sepa a ion pa ame e numbe o pa en s h: x: 0: m: E: Re e ences numbe o child en pe pa en numbe o Mon e Ca lo descendan s maximum li e ime maximum numbe o ga es o be mo ed a ia ion o m C. F. Hawkings and J. M. Soden,. ,,Elec ical cha ac e- is ics and es ing conside a ions o Ga e Oxide Sho in CMOS ICs," in P oc. IEEE In e na ional Tes Con e- ence, pp. 544-555, Washing on, No embe 1985 W. Maly, P. K. Nag and P. Nigh, ,,Tes ing o ien ed analysis o CMOS ICs wi h opens," in P oc. ACMLEEE In e na ional Con e ence on Compu e Aided Design, pp. 344-347, San a Cla a, No embe 1988 R. Rod iguez-Mon a ies, J.A. Segu a, V.H. Champac, J. Figue as and J.A. Rubio, ,,Cu en s. logic es ing o ga e oxid sho , loa ing ga e and b idging ailu es in CMOS," in P oc. In e na ional Tes Con e ence, pp. 510-519, Nash ille, Oc obe 1991 R.C. Ai ken, ,,A Compa ison o De ec Models b Faul Loca ion wi h IDDQ Measu emen s," in P oc. IEEE In e na ional Tes Con e ence, pp. 778-781, Bal imo e, Sep embe 1992 R.C. Ai ken, I Chiang, V. Johansen, and P.C. Maxwell ,,The E ec i eness o IDDQ, Func ional and Scan Tes : How Many Faul Co e ages Do We Need?," in P oc. IEEE In e na ional Tes Con e ence, pp. 168-177, Bal i - mo e, Sep embe 1992 0. S e n and H.-J. Wunde lich, ,,Simula ion Resul s o an E icien De ec Analysis P ocedu e," in P oc. IEEE In e na ional Tes Con e ence, Washing on 1994 W. Maly and P. Nigh, ,,Build-In Cu en Tes ing - A Feasibili y S udy," in P oc. IEEE In e na ional Con e- ence on Compu e Aided Design, pp. 340-343, San a Cla a, 1988 A Rubio, J. Figue as and J. Segu a, ,,Quiescen cu en senso ci cui s in digi al VLSI CMOS es ing," Elec o - nics Le e s, ol. 26, no. 15, pp. 1204-1206, 1990 R. Rius and J. Figue as, ,,P opo ional BIC Senso o Cu en Tes ing," Jou nal o Elec onic Tes ing, Theo y and Applica ions (JETTA), ol. 3, no. 4, pp. 387-396, Decembe 1992 W. Maly and P. Nigh, ,,Build-In Cu en Tes ing - A Feasibili y S udy," in P oc. IEEE In e na ional Con e- ence on Compu e Aided Design, pp. 340-343, San a Cla a, 1988 L.R. Ca ley, D.B.I. Fel ham, W. Maly and P.J. Nigh, ,,Cu en Sensing o Buil -In Tes ing o CMOS Ci - cui s," in P oc. IEEE In e na ional Con e ence on Com- pu e Design, pp. 454-457, New Yo k, Oc obe 1988 W. Maly and M. Pa y a, ,,Design o ICs Applying Buil -In Cu en Tes ing," Jou nal o Elec onic Tes ing, Theo y and Applica ions (JETTA), ol. 3, no. 4, pp. 397-406, Decembe 1992 Y.K. Malaiya, A.P. Jayasumana, C.Q. Tong and S.M. Menon, ,,Resolu ion enhancemen in IDDQ es ing o 579 la ge ICs," Technical epo (3-92-143, Dep . CS and EE, Colo ado S a e Uni e si y, Fo Collins, CO 80523,1988 K-J. Lee and A. B eue , ,,Design and Tes Rules o CMOS Ci cui s o acili a e IDDQ Tes ing o B idging Faul s," IEEE T ansac ion on Compu e -Aided Design, ol. 11, no. 5, pp. 659 - 670, May 1992 Y.K. Malaiya, A.P. Jayasumana and R. Rajsuman: A de ailed examina ion o b idging aul s. P oceedings IEEE In e na ional Con e ence on Compu e -Aided De - sign ICCAD, pages 78-81, San a Cla a, No embe 1986. F. B glez e al: Accele a ed ATPG and aul g ading ia es abili y analysis. P oceedings IEEE In e na ional [14] [15] [16] Symposium on Ci cui s and Sys ems, Kyo o 1985 Y. Saab and V. Rao: An E olu ion-Based App oach o Pa i ioning ASIC Sys ems. 26 h ACMIIEEE Design Au- oma ion Con e ence, pages 767-770, Las Vegas, June 1989. I. Rechenbe g: E olu ionss a egie - Op imie ung ech- nische Sys eme nach dem P inzip de biologischen E olu ion. F ommann-Holzboog Ve lag, S u ga 1972. H.P. Schwe el: Nume ische Op imie ung on Compu - e modellen mi els de E olu ionss a egie. Bi khause Ve lag, Basel und S u ga , 1977. [17] [ 181 [19] 580