Systolic architectures for fuzzy processing and their simulation

Ma th w are&Sof tC om puti ng 3( 19 94)29 7-30 8 SystolicArc hitecture sfo rF uzzy Proces singan dt he ir Sim ulation LuisdeSal v ador 1 ,M arc osGarc   a 1 ,Juli oGuti  e rrez 1 ; 2 1 Lab oratori odeH ardw areyContro lA v anz ado Inst.N ac .d eT e cnic aAe roespacial.C tra. Ajalvi rkm .4. 28850T orre j ondeArdoz.Madrid.Espa~ na e-ma il:salvador [email protected] 2 Dept.Tecnolog  aF ot onic a.Uni v.P olit  ecni cadeMadrid Cam pusdeM on tegance do. 28 660M adrid Ab stract Thispaperdetails thestudyofsystolicarc hitecturesf orfuzzyrulesprocessingmadeattheHardw areandAdv ancedCon trolLaboratory-INT A . Thetheoreticalbasiso fthesearc hitecturesisdescribedandanalysed.Lik ewise,theresul tan tsc hematicsaresim ulatedusingahardw aredescriptio n languag e(VHDL)w ithstandardcellsf romES2.Thisgiv esusav eryaccurateassessmen to ftheirrealperf ormance.Int hisw ayw ecandetectthe inheren tsh ortcomingsinthisclassofsy stemsandw eout linesev eralw aysof overcomingthen. Keyw ords: F uzzy, F uzzyCon trol,Systolic,S im ulation,VH DL. 1In troduc ti on One of theel dso fresearchi nf uzzy logi cisthedev elopme nt of sp ecichardw are withw hi ch w eca no bta inal lt he adva ntagesofw orkingwi th this classo fm odels. Thereare, basicall y ,tw oarea so fresea rc hinf uzzyco n trol lers:anal ogdesi gnand di gita l des i gn. The l atte r bring so ut sol utions base d o n s ystol ic archi te ctur es. T o systoli ze a pro blem c o ns i stsindivi ding i ti n to iden tical elem en tary op e rati ons that can b e e xecu ted to ge ther synchrono us l yi npa ra ll el [ 1,2 ].W e can repr ese n t all t hese elem en tary op e ratio ns as a se tofhom ogene ous pro ce ssing units that in terc onnec t tog e ther gi ving an arr a yo f n dime nsio ns . D ependi ng on the desi gn of t hi s arra y, the inputs and outputs are m ade t hroug hallorasubsetofunit s whic harein thel imits of the arr a y. The theore tical basis o f s ystoli za tion of fuz zy infere nce pro ce ss i ng de ned b ysev e ral a utho rs [3, 4, 5,6 ]. The se base s have lead t o the design ofseve ral s ystolic archite ctur es for pro ce ss ing. Atthisstageitisconvenienttouse simulation to ols. The se to ols allow: 297 298 L.DeSal v ador, M. Garc  a&J.G uti  errez 1.-T hefo rm al izationofdesign sp eci ca ti ons,sothati tw il la l sof orm al izethe theo ryupontheyarebased. 2.- Thestudyandc hecki ng of thed esignsbef oretheirim plem en tatio n. 3.-Thetesti ngofsystem pe rf orm ancesoastoc hec kfailuresi ndesi gntheo ry . Thesi m ul ation to ol w eusei saVHDL1sim ula tor. Th eadequacyo fVHD Las aspecica tion ands i m ul atio nlang uageisjustiedb yi tso wndeni ti on[7,8 ,9, 10] . 2T he ore ti calB asis Int hissectionw epresen tthebasisofsy stol icprocessorsoff uzzyrul es.Bydefa ult, w econsiderthebasi so ffuzzylogicalreadykno wn[11 ,12 ]. T odev elo pa sy stol icarc hitecture,most authors[ 3,4 ,5, 6]fo ll o ws ev er alsteps, asdescri be db el o w: 1.Denitio nofasetofrule so fthem odeltobedev el oped. Theserulesareas fol lo ws: IF A 1 i s LBA 1 ;x a nd/or.. .. A n is LBA n ;x THEN B 1 is LBB 1 ;y a nd/ or B m is LBB m; y where n isthen um ber ofan teceden ts, LBA a;b the b -thl abelo fthe an teceden t v ari able A a , m then um berofco nse quen tsa nd LBB a;b the b -thl abelofthe co nsequen tv aria ble B a .T heycom pl ywi ththec ondi ti on f A x g\f B y g i s em pt y ,tha ti stosa y ,therulesystemi snot li nk ed.Thek eyw ords\and"an d \or"a re,respe cti v ely ,thenorm aa ndco -n orm aused[1 1,12 ]. 2.Modicatio noftherul eset,sothatea ch ofthemi n v o lv esonl yonecons equen t v ari able. Ther ul eswi llha v ethef orm : IF A 1 i s LBA 1 ;x a nd/or.... A n is LBA n ;x THE N B a i s LBB a;b 3.N orm al izatio nofthean tece de nt si detoeli m i na tethe\ or"o pe ratorsandto expandtherule,sothata llt he an teceden tv ari ableswi ll be includedthere. This, as we wi lldem onstra te late r, is ag reatm ista k efrom at heoret icalpoin t of view, g ivi ng a rule se t that i snoteq uiv alent to the initi al one . 4. Inc l udingi nonesetal l t he rules tha th ave the sam e conse quen tv ari able. From no won , the res t of the pro c ess is de sc ri bed i n one se t, p e rfo rm ing the sa meo perati ons for eac hdieren ts et. 5. Cre ati on of a \rule basis". Thisrul e basis is a m atri xthatc on tai ns all the inf orm ati on ab out c o nditio ns to be k ept b y t he an tec ede n ts in o rder tha t variable B a will have one re sult or othe r. The cr eation of the matrixis done in the following way: Systol icarchitec ture sf or fuzzyprocessing andt he ir si mul atio n 2 99 5.1. Thedi m ensi onwil lbet he numb ero fan teceden tspl us one( n +1 ) : 5.2 .Thelengthofeachd im en sio nwi llbethen um ber of label softhea ssociatedv ariabl e. 5.3 .Thepositi on ( x 1 ;x 2 ;: :: ;x n ;x n +1 )wi lltak eonthev al ue dependi ngon whethertherule IF A 1 i s LBA 1 ;x 1 and. .. A n is LBA n; x n THEN B x is LBB x;x n +1 belo ngstoth es et ofrulesornot.Itisa lso po ss ibl etoconsiderv a luesb et ween 0a nd1,toconside rthefuzzi cati ono fa ntec ed en tconjunctionortheinse rtion ofm odiers. Notepoin t5. 2,whi chsho wso neim po rta n tconceptualc hangein rel ationto othe rauthors[3 ,4, 5, 6],whocons i derthelengthofea chdi m ens i ona sthesize of theuniv erseo fdi scourseo ft he associ atedv ari able.Afters ev eralstudies un dertak eninthi sl aboratory, we ha v eseenthattheuseofo nl yt he n um ber of label sissu ci en tifatthe da ta en trystagew ein troduce onef uz zieruni t. This reducesthesi zeoftherule basi sb yt w oordersofm agni tude ,m aki ngit ea siertouse,andal sosubstantia llyreducesthen um berofop er ati onstobe exec uted,soincreasingtheperform anceofthedesig nedarc hitecture.Inthe w a ythatw edesignedthea rc hi tecture,thefuzzi eruni tdoesnotg enerate an ydela ywhic hm ig h tresulti nareducti onofprocesssp eed,sothattheg ain obtainedusi ngthi stechni queishigh. 6.Generatio no fi nputdatam atri x.Thism atr i xi sg enera tedasf oll o ws: 6.1 .T hedi m ensi onwil lbethen um bero fan teceden tv aria bles. 6.2 .Thelengthofe achd im ensio nwi llbethen umb er of label softhea ssociatedv ariabl e. 6.3 .Thep ositi on( x 1 ;x 2 ;: :: ;x n )wi llhav et he sm all estm em bershi pv al ue of datainputs to label s LBA 1 ;x 1 . .. LBA n ;x n . 7. Mu l tipl icationofbothm atrice stoobtai nthei nference re su l t.Thisstepi s th eo ne re a llysystol ize d, andi ti sp os si bl etodoi tin seve ralw ay s. 8. De f uz zicatio no fresul t. This ste p could b e p erf orm ed using a nyo fthe exi sti ng m etho ds . 2. 1Systol ization In our m odel , inste ad of m ultiplying t wom atrice s, as des cribed ea rl ier, w ereduce the rule b a si sm atr i xi no ne dim ension, g enera ting s ev eral m atri c es with th e informati on of onl yo ne l ab el o feac h conse quen tv ari abl e . In thisw ay, the re sult of the matrix multiplicationgives the memb e rship of the conse quentvariable to this lab e l. 300 L.DeSal v ador, M. Garc  a&J.G uti  errez Fi gure1 :Systol izatio ns chem e T oc om putethem ultipl icatio nwe wi lluseonem axm inunit,which wi llbe descr ibedl ater,requi ri ngasm any unitsasthen um berofl abel so fconsequen t v aria bles. Thedi agramthatdescri bes thebeha vi ourofthesystolic systemissho wnin Figure1. Thi sguresho w sthegeneral beha vi ourofthesystoli csystemdescribedabo v e. Insum m ary ,theseto fpossiblerul esisev alua tedsequential ly .Theresul tisinserted ina\m i nim um "unit (represen tedb y X )sim ultaneouslywi thabi naryv ecto r.This v ectorco m pli eswith rulesthatha v ea neectone achconsequen tlabel.Onceal l oftherulesa ree valuated,thev aluesobtai ne da re de f uzzied. 3A rc hi t ect ur e Thearchi tecture desc ribedi ntheprev ioussec tion is co m prisedofthreem ai nc om - po nen ts: 1. The fuz zier 2. The fuz zy i nfe renc e unit 3. The d efuzz i e r The s y s tem ,a tthi spoi nt, app e ar s as a pi peli ne of thr ee segm en ts . This m eans th at the r unni ng of thes e se g men ts i sful ly s ync hronise d: the maxi mum dela yin an yof the m de ter m ines t he p e rf ormance o f the s yste m . In t his c ase, syst em p erfomanc e is limited bytheint ermediate unit: the fuzz y infere nce unit. Systol icarchitec ture sf or fuzzyprocessing andt he ir si mul atio n 3 01 Figure2:Structurem ax-m ini nf erence 3. 1 F uzzi er Inthearc hitecturedev el op ed ,thefuzzi erhasbeeni m plem en tedb ym eansof m em oryba nk s:onem em oryf or eac han teceden tv a ri able.Thee n trypoi n ttothe m em oryl oca tedb yanan teceden tv ariabl eisanindexwhi chsg iv esthecorrespondencebet w eentheex ternaluniv ersev al ueandtheuniv erseo fdisco urse:av alueof 8bitsinauniv erseofd iscourseof256locations.Eac hen trypo in tref erenceso ne w ordoflengthequaltot hen um berofpo ssibl elabelsf orthean teceden t,m ulti plie d b ytheprecisi oninbi ts usedintheev alua tiono fthem em bershipf unctio n: En tryx:[ label1 ][ labe l2 ].. .[ la bel7] Int he si m ul ationofthisdesi gnw eu seupto7l abelswi ththreep re cisi onbi ts i nthem em bershipfunct ion.Inthi sw a y ,theshapeoft he m em bershi pf uncti onw e cancongureisfree, wi thoutan yconstrain ts.Hen ce,e achm em oryhasasm an y o utputsasla belsthath av eb eendenedintheuniv ers eo fd iscourse. 3. 2Infere nc eu nit Thefuzzyinfe renc eu nitdev el opedherei si na ccor da ncewithgui delines desc ri bed b yotherautho rs[ 3, 4,5 ,6] ,butw ithone exceptionthat isessen tiali nourarc hitecture . Thi sisthere pre se n ta tion of the rules m apasi nd i cate d i n se ctio n2. W e di vide the i nfer ence uni tin to three m ain pa rts : a. Sys tol ic arra y b. Mu l tipl ication of a nte ce den ts c. Rules m ap The sys tolic arr ayisformed byachainof\max-min" units, asshown inFigure 2. 302 L.DeSal v ador, M. Garc  a&J.G uti  errez Figure3:Max-m inuni tdetai l Eac h\m ax -m i n"uni tc orre sp o ndstoo neel em en tary op er ato rasdescribedin theprevi oussectio n,w iththefol lo wingopti m i zati on:w eca rryoutthem ini m um fromthelog icalproduct( l ogi calAND)ofa n tecedents. T hi spa rti scom m ontoal l \m a x-m i n"units.T heme mb ershi pf unctio nisencoded by threebitsbut,i slater decodieda t8bi ts(unary codication),whic hall o wst heev al ua tionofm axi m a andm i ni m ausi ng onlyo nel ev elo fgates(Fig ur e3)andsubsequen tl ythebuil ding ofhi ghspeedunits. Thean teceden tpro ductuni ti sm a deupo faseto fs hi ftregi sters.Thel engthof eac hshi ftregi steri sequa ltothem axi m umn um berofla belsthata nan tenceden t v aria blecon tai ns .T hisn um berofan teceden tsi ss etatsyn thesi stim e.Theoutput dim ensiono ftheshi ftregistersi sthe equaltothen um berofbi tsusedt oencodethe m em bership functi on.Ino urca se,i tis threebi tswide.Anauxi li ary coun terci rcui t m anage st he outputo fan teceden tlab els, andoptim izestheci rcuitp er fo m ance whenthen um berofa n teceden tsusedi nt he de ni ti onofthefuzzysyst em is l ess tha nthem axim umn um bero fan teceden ts av ai labl einthehardw aresyste m. Therul em ap is madeupofi n terlea v edmemory banks.Ea chm em o rybank co rres pondstoaconsequen tv aria bl ea ndal abelo fthesame co nseq uen t.Itm ust pr ovidet he m em bershi penc od ing ow (1's a nd0 'sdataow)a tt he same sp eed tha tthe\ma x-m i n"uni tsw ork.Theseunitsprocesssofastthatiti snec essaryto bu i ld a pip eli ne str ucture that sim ula tesam em ory with the re qui red la te ncy . 3.3 Defuzzi er The de f u zzier unit w orks at the sam e sp e ed that the inf erence hardw are syst em ge nerate s nal v alues . The m etho d use d to pr o ces s de fuzz i ed v alues i scen troid com putation. Thi suni ts c on ta ins: 1. P arall el m ultipl ier unit[ 1,2 ]. 2. B uilt-in-memory divider. Systol icarchitec ture sf or fuzzyprocessing andt he ir si mul atio n 3 03 Figure4:Systolic archi tecturesc hem e W ecanuseab ui lt-i n-m em orydi vidersincew eo nl yuseei gh tdieren tle v el s toencodethe m em bershi pv a lues.Thisprocedurea llo wsustodev el opasi m pl e a ndv eryfastd esig n.Moreo v er,thethrough-puto fthedefuzzierisequaltothe through-puto fthefuzzier. Thew holearc hitecturesc hem eo ft he systol icsystemi sdepicte di nFigure4. 4Si m ul ati on Bet w eenthedesig nspec icatio na ndi tsactuali m plementatio nthereex istsan essen tialste p: sim ula tionusi ngCADtoo ls.T he m a inprobl em sa nddisfunction hi ddeninthea rc hite ctureem ergeduri ngthis phase.Moreo v er,w ecanset the m osti m portan tp aram etersofperf om a ncesuch as :e stim atedti m etoproce ss, through-put, ands oo n. W eha v eem pl o y edaha rdw aredescri ptionl a nguage,VHDL 1 ,asasim ula tion to o l. Thi s approac h has m an yadv an tages : i t is a standard too l[7, 8] ,itperm its to de sign w ith m odul arit ycr iter i a, it i s able to syn the size o ver s tanda rd cel ls or FPGA' s and w e c an bui ld param etr i zable designs. This last featur e all owsus to dene m any param ete rs o ftheci rc ui ti n a exibl ew ay. In our c ase, th e s et of pa ra meters i s: 1. N um ber of an tec ede n ts. 2. N um ber of co ns eque n ts. 3. Lab e lsperante ced ent. 304 L.DeSal v ador, M. Garc  a&J.G uti  errez 4. Label sperconsequen t. 5.Maxi m umnumb er of l abel speran tecedent. Thel ibra ri esha v ebeendev elop ed in ourlaboratorywi ththeE S2 2 spec i cati ons for1 m ce l ls. Becausetheexec utiont i m eofthei nferenceunit depe ndso nthedeniti onof then um berofl abelsp er an teceden t,thecicuith as be enada ptedi nordertobe abletosettherigh tn um berofl abel speran teceden tu sed.Inthisw a ythebest perfom ancefo revery co ngurationo fthefuzzys yste misac hiev ed. Sim ul atio nw asperform edo v erac ircuit generatedwiththef ol lo wi ng param eter settings: 1.Four an teceden tswi tham axim um numb ero fsev enl abel s. 2.Sev en label sperco nsequen ts. 3. Univ erseofdisco ursewith 256sam pl es. 4.T hreebitstoencodethem em ber shipfunction. 5.Upto8Kb ytesofm em ory. Thi sci rcuitwasprogram m edtoho ldf ouran teceden tsa ndthreela belsper an teceden t.Thep erfom anceofthecircuitis thefol lo wing: 1.Theci rcuitcanberun wi thacloc kperi odof10ns. 2.Thewho lerulebasei se xecu tedino nl y81 0ns. 3.Thethrough-put of thesystemis1 .2MFLIPS 3 . 4.Therul eexec utio nf re quencyis100MHz. 5. The s tim ated s i li con area i s40-6 0mm 2 . 6. The am oun t of tim ene ce sary to program the r ul ebas e and f u zzier is 46 .4 ns . Thi sarc hitec ture there fo re p ro vide s v ery hi gh p e rfom ance inrela ti on to other de velo pm en ts, ev en non-systolicdesig ns [1 3,14 ,15 ], es p ec ial ly if w etak ein to acc o un t tha t this i s not the m axim um p er f omanc e of the s y stem . Moreo ver, this des i gn do es not nee d muchmemory, unlike early fuzz y pro c es sign syst olic archite ctur es . Finally, the silicon area is ins ide the b ounds of a s mall dice of silicon. Systol icarchitec ture sf or fuzzyprocessing andt he ir si mul atio n 3 05 5 IssuesthatAri sei nSysto li cD es i gns Indev elo pingthep re se nt archi tecturew eha v ed etec te dsom econceptualdi sf un cti onsandsev era lc ri ticalaspectsofthesi m ulation pr ocess.Thesei ssuesared escri bedinthefo ll owings ubsecti ons:theoreticali ss ues(them ostim portan to nes) a ndim pl em en ta tioni ss ues. 5. 1Theore ticalIssues Oneo ft headv an tageousc haracter isticso ffuzzysysto licarch itecturesi stheirpresumm ed theircapa bil it yofproc es singa llthepossi bl erul es of thefuzzysystem [ 3,4,5, 6] . Althoug ht hisaspectseem so b vio usf ors ev era la utho rs 4 ,thefo llo wi ngproblem a ri ses:  Consi deraco n trolsyste mw itht w oinputv aria bles[A, B] ando neo utput v aria ble[C] .  Imp osetheco nditio nofo nlyt w ol ab el sperv aria ble[ LBA 1 LBA 2 ] ,[ LBB 1 LBB 2 ],[ LBC 1 LBC 2 ] .  Assum eafuzzysystol icdesig n. Inthepresen tedcase,i tisnotpo ssibl etorepresen tinthefuzzysysto licsystem thefollo wingrul e: IF A i s LB A y THEN C is LB C y Becausetherules ystemisrepresen tedo rthogonall y ,them ostapro xi m aterule w ecanusei s: IF A i s LBA y and( B i s LBB 1 or B is LBB 2 )THEN C i s LBC y Althougbothsenten cesareequiv alen tincl ass ic (orcrisp)l ogi c,thisisno ts o i nfuzzylo gic.Ther easoni sthattherei snotac om plem en tarypropert yinfuzzy l ogi c[ 11] .Thism ea ns: u LBB 1 ( x )or u L BB 2 ( x )doesno tim ply 1 u LBB 1 ( x )a nd u LB B 2 ( x ) doesnoti m pl y0 Av erysim i lar resultoccursi narulewheret henega tionofa nan teceden t app ears . Our c o nc l us i on i s the fol lo wing: fuzz y s ystol ic sys tems, b o th the tr a di tio na l dev elopm en ts a nd the sys tem de pi c ted in this pa per, pro ce ss onl ya l im ited se t of rul es. T h ese rules ha veana ntec ede n t part m ade upofthe l ogi c pro duc t of som e lab e l of e v ery an tec ede n tde ne d in the fuz zy syst em . 5. 2 Imple mentati on Issues Among the c ritical issue s that arise in t he de sign and simulation of s ystolic syste ms atimplementation, we s tre ss the following: