DDT: a research tool for automatic data distribution in HPF

DDT: A Resea ch Tool o Au oma ic Da a Dis ibu ion in High Pe o mance Fo an EDUARD AYGUADE, JORDI GARCIA, MERC:E GIRONES, M. LUZ GRANDE, AND JESUS LABARTA Compu e A chi ec u e Depa men , Poly echnic Uni e si y o ' Ca alunya, c . G an Capi a s/num, Modul D6, 08034 -Ba celona, Spain ABSTRACT This a icle desc ibes he main ea u es and implemen a ion o ou au oma ic da a dis ibu ion esea ch ool. The ool (DDT) accep s p og ams w i en in Fo an 77 and gene a es High Pe o mance Fo an (HPF) di ec i es o map a ays on o he memo ies o he p ocesso s and pa allelize loops, and execu able s a emen s o emap hese a ays. DDT wo ks by iden i ying a se o compu a ional phases (p ocedu es and loops). The algo i hm builds a sea ch space o candida e solu ions o hese phases which is explo ed looking o he combina ion ha minimizes he o e all cos ; his cos includes da a mo emen cos and compu a ion cos . The mo emen cos e lec s he cos o accessing emo e da a du ing he execu ion o a phase and he emapping cos s ha ha e o be paid in o de o execu e he phase wi h he selec ed mapping. The compu a ion cos includes he cos o execu ing a phase in pa allel acco ding o he selec ed mapping and he owne compu es ule. The ool suppo s in e p ocedu al analysis and uses con ol low in o ma ion o iden i y how phases a e sequenced du ing he execu ion o he applica ion. © 1997 John Wiley & Sons, Inc. INTRODUCTION Da a dis ibu ion is mw o he opics o cu <>n IT- s<>a ch in pa allelizing en i onmen ~ o nonuni o m memo y an: •ss (: l 1! L ) massiY > pa alld p oc >sso s (MPP). In hes<> sys ems. each p o<Tsso has di ec au >ss o i s local (o dos >) memo and indi ec access o h<> emo e memo ies o o he p ocesso s h ough he in <> Tonnec ion ne wo k. The cos o acc<>ssing a local m<>mon loca ion can lw mo e han on<> o dn o magni J<le as e han h<> cos o acc >ssing a emo e men1o y loca ion. In h<>s<> sys ems. h<> choice o a good da a dis ibu ion can d ama ically a ec pe o mance lw :aus ' o he nonuni onni y o he nwmo y sys em. H•·c•·i"·d I:" I '19:; H<·yis.·d F.-ln:ll: 1 'I<J(J © 1 <)()'7 I" John iln lx So b. Inc. Sci.-n i ic l' o~ ammin~. 'ol. (J. pp. Tl-'J.-1 ( 1'N?) ( :( :(: 1 OSIJ-CJ:2+ /'1'7 /01 OOT~-~~ Se e al es >a che s ha ' a ge ed h >i esea ch p - o s o his opic. Fo ins ance, he C ys al con1pile and language p ojec [1]. he impl >men a ion o PAH- ADIC. 1 [2] on op o Pa a ase-2 and i s con inua ion 011 lw PTHA II mmpiln [:3] a IB. 1. he amP o k o he au oma ic de e mina ion o a ay mappin~s p >s 'n >d in [4. 5]. o he au oma ic da a-mapping s a egy [ 6 J o usc in he D-p og amming eu i on- mcn !' IIT 'n ly unde d > clopmen a Hice l :ni · si y a c •xampl >s o p oj >c s iu his a 'a. O he g oups ha e a ~ ' NI hei e o h o he > >c i c compila ion o p og ams con aining he s wci ica ion o he da a mapping. such as he YFCS sys em [7] o lw Vienna Fo an language [8]. lw Fo an-D compile [9] and language [1 OJ. o he cn cu conmu• ical co npil > s (xi IPF [11 ]. PGHPF [12]) o High Pe o manc ~ Fo - an (HPF) [UJ. Au oma ic da a dis ibu ion maps a ays in o w physically dis ihu >d mnno ies o he p ocesso s ac- co ding o he a ay access pa e ns and pa a li > I 'x.ccu- ion o ope a ions wi hin compu a ionally in 'nsi c 74 Cl'ADI~ ET ; L. phase~. This mapping nm lw ~i he s a ic o dynamic. In a s a ic mapping. he layon o he a ays dews no chang ' du ing he execu ion o he p og am; in a dynamic mapping. ~mapping op > a ions a e pe - o med in onl ' o change lw layou o a ays in di e en compu a ional phas 's. los s a ic da a dis ibu ion me hods [ L 2. - . 1 " . 1.)] pe o m h ' joh in wo main independen s eps: alignmen and dis ibu ion. Th~ alignmen s 'p iPs o ela e h ' dimensions o h ' a a s used in a block o nHl ' wi h he dinwnsions o ano he a a called lw empla e (in e dim 'nsional alignm 'n ). and o each aligned dinwnsion. o ind lw app op ia e shi he w ' 'n hei elemen s ( in adimensional alig111nell ). A good aligm wn willminimizP lw o e head o in P - p m-csso da a mm·cmen . The main di e ences lw ween he p e ious me hods is he kind o s uc n ' selec ed o n·p 's~n he p ob- l >m, and lw way used o onnula e and sol > i . Fo he al igm wn s ep .. Li and Cheu [ 1] d > inp and usc he Co nponm A ini y C aph (CAC) o ep esen align11wn p den·n<: 's. and i usPs a h 'u is ic algo- i hm o solw i . Cup a [2] also uses he CAC .. bu w >igh ed wi h da a mo e11wn cos s. To do his. a de aul dis ibu ion has o lw assumed. This p oposal is mo e accu a ' hau he p e ious one ,,·hen w~igh ing he edges o he CAG, hu lw sol e is bas 'd on he same heu is ic algo i hm. holey [ 14]us >s he p e e - em:e g aph de ined by [ 1 ()] in he anwwo k o ~illgl~ ins uc ion nml iplc-da a (SIMD) nachin 's. This !Taph i wlud >s alignmen p e e ences o p ~sc e pa - allcli~lll.. bu he Psoln ion hen lw g aph is in con- llic is also based on heu i~ ics. Schc llc e al. [4] de ine he alignmen dis ilm ion g aph ~hP P nodes n•p Tsen p og am ope a ions and edg >s "o mec de i- ni ions o a ay objec s o h 'i uses in i es~ ope a ions. Edges a e w 'igh cd wi h lw numlw o da a i ems com nunica ~d along lw edge. The alignnwn is ound using a g > ·dy algo i hm as a heu is ic o de enni w he minim un cos .. and applying g aph con ac ion op > a ionb o >duce he complexi y o lw p oblem. K ·Imedy and K eme [ 1;)] design a amP HJ k o he used i11side a da a layou assi~ an ool o HPF. l i~ bas >d on he CAC. and hey sol ' he alignmen pmb- l 'm using a 0-1 iu ·ge p og amming nHHl 'L hus a oidin; lw usc o heu is ics. Onn· lw align nen has been decid >d. he dis ibu- ion ~ ep d 'cide~ which dimension(s) o IIH' e npla P a c dis ibu ed and he uu nLw o p ocesso s assign 'd o each o hem .. good dis ibu ion maxi nizPs lw po en ial pa allelism o he cod • and o e s he possi- bili y o u lw educing da a lllO TnH'Il hy snializ- ing. This goal could b~ i ially ~a is i >d by assigning a da um o each JJJ"Oc 'sso . whi ·l1 maximize~ pa all >l- is n. Li and Chcu [ 17] ma ch he aligned e e ence pa e ns wi h a p ede ined sP o da a mme nen ou- ines. Each ou ine has an a chi ec u e-dependen cos pa ame e ized in ~ ms o he Jlll nbe o p ocesso s in ol ed in h ' da a mo ion and h~ amoun o da a being mo ~d. The cos unc ion o all he pa e ns is minimized hy selec ing he app op ia e dis ibn ion s a egy. Gup a [2] decides he dinwnsious o dis ib- u e (maximum 1 nJ dimensions). assuming a de au I mnnlw o p ocesso s in Pach one and minimizing h~ o al da a mo em~n plus compu a ion im '. When mo e han m e dim 'nsion is dis ihu ' L he decides he numbe o p ocesso s o assign o 'ach dimension by gene a ing all possible cmnbina ions. Wholey [ 14] uses a hill climbing sea ch m~ hod hich ini ially as- signs all a ay demen s o on~ p ocesso and 's inw ~s lw cos . Then i doubl > he munl_)(' o p o ·esso s and chooses he dinwnsion o assign he n 'w cmes. un il all a ailabl ' p ocesso s a ' n ilized o he o al cos is no u he n·duc >d. In la ge p oblems whe e di e Pn compu a ional!) in ensi e phas 's occu .. emapping ac ions be ween phases can inc ease he d ici~ncy o he solu ion. In his case. a good solu ion is indqwwkn ly ound o each phas ' .. and ealigmn 'n and/o edis ibu ion s a enwn s a e inse ed wh ' T m·ccssa y. Da a 'map- ping is also one o h ' opics in his suhj >c a ea o cmT 'n esea ch. Some o he p oposals p esen ed in he li e a u e abou a ay ~mapping [:'i. 13-20] a > ~umm:uized in he es o his sec ion. The D-Sys em. cu en ly unde d • 'lopmcn a Hice Lni ·e si y, conside s he p o i abili y o dynamic da a n~1napping by explo ing a s ~a ch space o eason- ahl ' alignnH·n a11d dis ibu ion spacPs [18]. In hei wo k. each phas.o has a se o candida e mapping sch ·mes. Selec ing a mapping schenw o each phase in he en i e p og am is dow· by n·p 'sen ing he p ob- l 'm wi h he da a layou g aph. Each possible mapping o a phase is >p esen ed wi h a nod ·. Edges lw ween O nodes in di e en phas 's n~p esen he n· napping ha has o lw ca i >d ou o execu e each phase ,,-i h h ~ co esponding mapping. : od ·s and edges ha e weigh s >p >s ·n ing lw on• al cos o 'Xecu ing a phase wi h mapping and emapping cos s. espec- i ely. in nms o execu ion inw. The p oblc n is ansla ed in o a 0-1 in ege p ogn11nmiug p oblem sui able o lw sol ed by a s a '-o - lw-a g >JH' al- pu pose in PgP p og annning sol e . Tlw FC:S sys em [1 )] conside s lw p old · n in he anwwo k o a da a dis ibu ion ool o Fo an <)() sou ce cod •o. ln his scO]H'. a ay-s~ n ax assignmen s a 'lll 'll s and ~liE HE masks a e 'Xamim·d o de e - mine candida • da a mappings. phase is basically a DO-loop c m aining a ay-syn ax a~sig n1wn ,; a e- men s o WT JERE masks in i s body. Ins ead o lookinp: o lw op imal solu ion. i uses a l e('-exhaus i e algo- i hm wi h some heu is ics o p une he sea ch spac '. A con lic able s o ing he con lic s lw w 'en he map- pings o he a ays om OTi ' phase o lw o he is he basis o he n·mapping algo i hm. This able de e - mim~s which edis ilm ion op ions a e wo h consid- ' ing a '11Ch ansi ion. F om his in o ma ion. a ee showing all lw di e en al e na i es o emapping is buil . Th > aim is o de e mine he pa h in he eP wi h lH~ lowes COb I. The u 11 emapping ee can easily g ow o in ac ahiP p opo ions. Cha e je > el a!. [;)]usc a di ide-awl-conque ap- p oach o he dynamic mapping p oblem. T wy ini- ially assign a s a ic mapping alid o all he nodes and lwn ecn si Piy di id > h >m in o egions which an~ assigned di > 'nl mappings. Two egions a e me ged wh >n dw cos o lw dynamic mapping is wo se han h > s a ic mapping, aking compu a ion. da a mo Pnwnl. and >mapping cos s in o accoun . Pal- e mo and Ba w jcc [20] also usc a di idc-and-cmi<pu:' app oach in which he p og am is n·cll si >ly decom- posed in o a hie a chy o nmdida P phases. Then. ak- in!-( in o a<:<'mm h ' cos o emapping bel een he di e en phases. he scq wncc o phases and ph b<' ansi ions wi h lw lowPs cos is sPIPc ><l. The usc [2] o assign mappings 10 hP phases gene a ed. Th > Da a Dis ibu ion Tool (DDT) is a esea ch ool designed o gene a e ho h s a ic ami dynamic solu- ions. Since i is a esea ch ool. i can use edmiqu >s ha may lw oo CO! l£H a ionall~ expensi e o lw in- cluded in a inal compile ; howe e . his allows ns o explo e a ich se o solu ions. The s a ic modu! · is based on he CAG hu Px ended wi h som ' in o ma ion ega ding pa allelism. W <'haw also modi ied he o i!-(i- nalalgo i hmsin [1. l'?] oimp o c he(IUali yo he mappings gene a ed [21]. The cu n·n e sion o he s a ic module g ~Jw a es bo h in e - and in adimensio- nal alignmen s and BLOCK and CYCLiC dis ibu ions. The dynamic llHH!ul > explo es a ich sci o cmnbina- lions: i is no ('xhaus i c hanks o mechanisms in- cluded o cu dm n hc sea ch space [22]. Tlw dynamic analysis is in e p uccd al and conside s con ol low o ck cnnine ·he e he cmappin!-( ac ions ha P o lw 1w onned (be W(' ~n ('0111pu a ional phas >s o ac oss p on~du P hounda i(~s). Tlw >s o h • a idP is o ganized as ollO S. In lw JH'XI sec ion "(' gi e an O T in o he hole da a- mapping p ocess in DDT. Sec ion :~ de ails how he s a ic solu ions an· ound. Sec ion-+ d >snilws ll ' al!-(o- i hm ·hich inds dynamic solu ions and inse b e- mapping ac ions i hey a c ound p oJi ahle. Sec ions :) and () desc ibe he nlcnsions o he p e ious algo- i hm o handle con ol Jim, and in c p ocedu al anal- DDT: A RESEARCH TOOL 75 yses. espec i ely. In S >c ion 7 we p ese11 h ' main esul s om a se o expe imen s o es he alidi y and quali y o he solu ions gene a >d by DDT. Finally. Sec ion 8 gi es sonw concluding ema ks. 2 AN OVERVIEW OF THE DATA DISTRIBUTION PROCESS IN DDT Om esea ch ool (DDT) analyzes Fo an 77 code and anno a es i wi h a s ' o HPF di ec i es and execll abiP s a em >n s ha speci y ( 1) !10 ~ a nays a e align >d o a se o l >mpla e a ays and how he dimen- sions o hese empla es a ' dis ilm ed among p oces- so s: (2) he sP o >alignmen and edis ibu ion s a Pnwn s i h ' solu ion ound is dynamic:, ami (:3) he pa alleliza ion s a egies o he loops ha access dis ibu ed a aYs. These decisions a ' done so ha hP amoun o en olc accesses is Pduc :d as much as possible .. whil > maximizill!-( he pa alldism achie ed. Th > cx (' nal shell o DDT is he in c p ocedmal analysis module: his module is based on he call g aph o he Pn i e p og am. ln a bo om-up pass o e he call g aph. each p occdun~ is analyzNi when all he p ocedu es called by i haY ' al eady been p ocessed. " o in· ha Fo an 77 docs no allow Pcu sion. so 110 cycl >s can he ound in he call g aph. F om he analysis o a p ocedu e. a se o candida e mappings a e gene a ed o i and s o ed in he DDT in e p oce- du al da abase. Fo each p ocedu e. DDT can gene a e wo di P - enl kiJH!s o solu ions: s a ic and d namic. S a ic solu- iom de ine an ini ial mapping o each a ay. and i does no change du ing he execu ion o he whole p ocedu e. In a dynamic solu ion. w s a emen s in lw miginal sou ce code a e g ouped in o a ('ollcc ion o phases: each one nwy ha e di e en mappings o he a ays a ' ' 'SSPd so emapping ope a ions migh be nP ·essa y o ex >cule each phase "·i h i s mappi !-(. i o ice ha s a ic solu ions a e a pa icula case o dynamic solu ions wlw e no emapping ope a ions a c needed. A phase is ei he he ou Pnnosl loop in a nes wiJOs • con ol a iable is used o subsc ip au a ay o a call o a p ocedun·. I lw phase is a loop w-; . he candida e n appin !s o i a e ob ained by pe o ming an analysis o P ' 'IH'P paiiPn s wi hin he 1ws . I h(· phase is a calL he candida e n appings a ' impo ed on lw DDT in e p ocedu al da abase. The con ml low mod- ule guides lw g<'JH' a ion o all possibiP sPqm·nces o phas 's o •ach p ocedu e. DDT is a ge ed o !-( 'IIP ic J l . L a chi ec un's wi h local and emo1 ' ac<Tsscs. Each p ocesso has i s own nemon· hie a d Y and can access he nwmo iPs in . . 76 AYGU,DJ;: ET AL. o he JH'occsso s h ough he in e connec ion ne wo k. Da a mo em ll cos s a e es ima ed as he numlw o emo e accesses mul iplied by he emo e access ime. Gi en a pa alleliza ion s a egy. compu a ion cos s a e 'S ima ed om a p o ile o lw seq wn ial execu ion on a wo ks a1ion based on he same p oe >sso and wi h he same memo y hie a chy han lw pa allel machine. P o iling lw s quw ial 'Xeeu ion o he o iginal Fo an 77 p og am is equi Pd in onle o ob ain some p obl 'm-speei ie pa ame e s. such as a ay sizes. he numbe o i e a ions o he loops and bei execu- iml ime.. and lw p ohabili ies o he di e en b anches in condi ional s a emen s. The e exis s a con- igu a ion ile ha allows he use o speci y sonH' machine-speci ic pa ame e s (numbe o p ocesso s. o e head o pa allel h ead c ea ion. local and emo e memo y access cos s, and so on) and es ic s he kind o solu ions explo eci by DDT (numbe o dis ibu ed dimensions .. s a ic o dynamic solu ions, numbe o eandida > mappings o he phases and p ocedu es. and so on). All cos es ima ions in DDT a e dmw nu- me ically assuming he abo e-men ioned p oblem and machine-speci ic pa ame e s. 2. 1 An Example: Al e na e Di ec ion Implici ln his S 'c ion we in oduce he Al ema ing Di ec ion Implici (ADI) in eg a ion ke nel o show he main ea u es o he DDT in ap occdu al da a- 'mapping HHHiule. The sou ce code o ADI de ines a ! Yo- dimensional da a space o size 256 in each dimension: i ha~ a sequenee o loops ha ini ializes lw da a space ollowPd hy an i e a i e loop ha pe o 111s he eompu a iom. In each i e a ion o his loop. o wa d and backwa d sweeps alon ows and col- lUnns a e done in sequence. In his example. and o simpli ~i y .. DDT only onside s mw-dimensional dis ibu ions:. we ha e also se he eon ign a ion ile ;;o ha llw o e head due o pa all 'l Pxecu ion is ze o. emo e aceess!'s ake 1 J.LS pe by e. and he pa allel machine has 16 p occs,;o s. The sou ce eode is shown in Figu e 1 o comple e- ness. DDT iden i ies nine plias<~s in his p og am. Each phase co esponds o one o he nes ed loops (labeled mm 1 o 9) in Fi~u e 1. Fo each phase. DDT es i- ma es he da a mo emen and he execu ion cos s o di e en da a-mappi11g and loop pa all '!iza ion al e - ua i e;;. Fo inslance. while analyzing phase 4. he wo possihle mapping" shm n in Table 1 a e aken in o accoun .ln his case, DDT sugges s a pe ec alignnwnl o all he a ays used in he phase and wo possibl · dis ilm ions: (BLOCK, *) and(*. RU)CK). Fo he i s ime, DDT also sugges s o pa allelizP he ou e p og am adi double p ecision x(256,256) double p ecision a(256,256), b(256,256J do 1 i 1, 256 a{i, 1) = 0.0 b{i, 1) = 3,0 x(i, 1) = 4.0 con inue do 2 j do 2 "" 1, 10 C AD1 backwa d sweeps along ows = 2' 256 ;:: 1~ 256 j} = x{i, j} - x(i, j 1) "' j} = b(i, j} - ali, j) "' a{i, 256 ) I b(i, 256 } Phase 1 Phase 2 Phase 3 Phase 4 b(L j 1) j - 1} Phase 5 = 255 , L -l Phase 6 i = 1' 256 x(i, j) = (x(i, j} - a(i, i + 1) * :x:{i, j- 1)) I b(i, j) 6 con inue C ADl o wa d & backwa d sweeps along columns do 7 j "' 1, 256 do 7 =- 2, 256 j) - x{i, j) ~ x{i j) "'b{i, j) - a(i, a(i, j) I bl256 , j) con i::1ue Phase 7 b{i - 1, :i) - 1, j) Phase 8 do 9 j = 1, 256 Phase 9 do9i=255 -1 x(i, j) "' j) - a(i + 1, j) * x{i + 1, j)) 1 b(i, j) 9 con inue 10 con inue end FIGURE 1 Son ce eode o ADl. i loop sinee he e an~ no da a dependencies p e en ing he loop om unning in pa alleL Fo he S<'eond al > - na i ~. he depe!Hlence in he second dimension o a a 'S band : · o ces DDT o sequ ,n ialize he execu- ion o he j loop. Fo each al e na i e. an es ima e o he da a mo enwn cos s is pe o med by ma ching e en·nee pall ems wi hin he phase wi h a p ede ined se o da a mo emen pa e ns. The compu alion ime o a phase wi h a pa alleliza ion s a egy is es ima ed om he p o ile o a se juen ial execu ion. Fo in- ;; ance. he 'S ima ion o phase <-± concludes ha h ee shi -like da a mo emen pa e n~ appea due o w accesses o a ays . and b when he second dimension is dis ibu ed (each shi mo cnwu in- Ynl es a ·olumn o an a Tay. i.e .. :2;)6 elclllell s o 2.048 by e). The p o ile o his phase epo s a sequen ial execu ion ime o o.:3S292:J s. which is he cos o Solu ion 2. Howe e . he compu a ion cos o his phase wi h Solu ion 1 is es ima ed as 1 I 1 () o his s ~quen ial execu ion ime plus he o e head due o pa allel h ead c ea ion (ze o in hi;:; example). The i s ow in Table 2 shows he da a mo 'men and compu a ion ime::; es ima ed o pha;,;e <-± o he wo solu ions e alua ed by DDT. F om he analysis o he di e en possible map- pings o a phase. n SPI o hem a e ~dec 'd as candi- da e 111appings ( his selec ion is done based on cos DDT: A RESEARCH TOOL 77 Table 1. A ay Mapping Al e na i es and Associa ed Loop Pa alleliza ion S a egies Analyzed by DDT o Phase 4 in ADI A ay 1apping Loop Pa alleliza ion Solu ion 1 CHPF$ TE 1PLATE a gc (256, 2;)6) CHPF$ ALIGN WITH a ge ::x. :L b CHPF$ DISTRIBCTE a ge (BLOCK, *) CIIPFS INDEPENDENT DO 4 i = L256 DO 4 j = 1.256 Solu ion 2 CHPF$ TEMPLATE a ge (2.S6, 256) CHPF$ ALIGN WITH a ge ::x, a. b CHPF$ DISTRIBUTE a ge (*, BLOCK) DO 4 i = 1.256 DO 4 j = 1.256 c i e ia). Once hey a e selec ed, an algo i hm o check he compa ibili y o phases is used; we say ha wo phases a e compa ibl > when hey ha e p e e ences o he same da a mappings so no emapping is equi ed when sequencing om one phase o he o he . Fo ins ance, conside he sequence {4, 5, 6} o phases. F om he sou ce code in Figu e L one can see ha hese h ee phases ha e he same p e e ed mapping (BLOCK,*) and loop pa alleliza ion s a egy (execu e he i loop in pa all >l). Simila ly, on > can conclude ha he p e e ed mapping o each phase in he sequence {7, 8 .. 9} o phases is(*. BLOCK) and he pa alleliza- ion o he j loop. Table 2 shows he cos s o he candida e mappings o all he phases wi hin he i e a- i e loop do i e . Table 2 shows ha he a o i e solu ion o phases {4, S. 6} and {7. 8, 9} is no he same. The e o e, hey a e no compa ible in hei mapping and pa alleliza- ion s a egies. Th ee main al e na i es a e e alua ed by he in ap ocedu al algo i hm: 1. Assign Solu ion 1 o all he phases. In his case he cos pe i e a ion is 0.5479-H and he >s i- na ed cos o he ou e i e a i e loop .5.47944. 2. Assign Solu ion 2 o all he phases. In his case he cos pe i e a ion is O.S7:'i59 and he es i- ma ed cos o he ou e i e a i e loop 5.7559. 3. As~ign h > p e e ed solu ion o each phase. Tn his case he compu a ion ime is 0.061886 and we ha e o emap he a ays be wcen in ompa i- bl > phases. In pa icula , a ays a, b, and x will be emapped om ow o column dis ibu ion be o e he execu ion o phase 7, which has an app oxima ed cos o (2.56 * 256)/16 = 4,096 a ay clemen s each (o 32,768 by e each). This emapping ac ion is pe o med 10 imes du ing he execu ion o he i e a i e loop. Due o he same loop, phase 4 is execu ed again a e exe- cu ing phase 9. So we ha e o conside he com- pa ibili y be ween hese wo phases and he pos- ~ible emapping cos s i hei mappings a e no compa ible. In pa icula , a ays a, b, and x ha e o be emapped om column o ow dis i- bu ion be o e he execu ion o pha~e 4 wi h he same es ima ed cos . This emapping ac ion is pe o med nine imes ( ~ince he las i e a ion o he i e a i e loop o ces he >xecu ion o >xi i ). The o al cos o he sequence o phases wi hin he i e a i e loop is es ima ed as: (10*0.064886) + (10*3*0.0:32768) + (9 * 3 * 0.0:32768) = 2.5166:36. In his >xmnple, he cos o he dynamic al e na i e is lowe hm1 he cos s o he wo s a ic al e na i es. In Sec ion 7. W ~ analyze and e alua e he alidi y o he di e en solu ions when changing a chi >c u al pa ame e s such as da a mo emen and hc numbe o p ocesso s. Table 2. Da a Mo emen and Compu a ion Cos s (in seconds) o Phases 4 h ough 9 in ADI o Two Candida e Solu ions Phase ;J (J 7 8 9 M o em Pn 0 0 0 0.0061- - 0 0.0040% Solu ion 1 Compu a ion 0.022058 0.000212 0.01109;) 0 .. '32- S(J:=i 0.002261 0.177;)13 Solu ion 2 Mo emen Compu a ion 0.0061 +± 0.332£)25 0 0.0():3:391 0. 00- O% 0.177-)Ll 0 0.020285 0 0.000 1- 1 0 0.01109:) 3 DATA DISTRIBUTION FOR A PHASE The basic compila ion s cps o a compu a ional pha~e an~ dc~c ibed wx . Fi s o all. a weigh ed g aph called he Dimension Alignmen C aph (DAC) is cons uc cd om he anal sis o hc a ay e >n•nces in lw sou ce . . p og am and i eco ds p e > >nc >s o alignmen . The DAC is simila o he CAC hu i indudcs p e e enccs o aligm wn based on pa alleliza ion in addi ion o da a lllOY 'IIH~n . Tlwn, an a ay alignmen phase ol- lows. In hi~ ~ <>p. all dimensions o he a ays in lw p og am a e cla ed o each o he by ( 1) mapping each a ay dimcnsion in o a dimension o a empla e a ay (in enlimensio11al alignmen ) and (:Z) applying an o se be ween 1 hem (in adimensional aligmncn ). Da a mo emen equi emen s o hose nonaligned e e >nc >s and loop pa alleliza ion s a egies a e ana- lyz<>d in o de o deci<k he dimensions o he empla <> o dis ibu e .. he numlw o JH·oc >s~o s alloca cd. and he kind o dis ibu ion applicd o hem. 3. 1 Re e ence Pa e ns and he DAG Tlw DAG is a 'wigh ed undi ec ed g aph buil om he analysis o a ay e e ence pa <> ns in loop s a e- menh. In his sec ion we e in how > e ence pa e ns a c de ined and anal z >d o de ec a ini Y. and how . . he DAC is buil om his anal ~is. Re e ence Pa e n Analysis and DAG Building The analysis o e e ence pa e ns is pe on wd wi hin lw scop<' o ws ed loops. A e e e11ce pa e n is de- ined in .. II, ..... i,) ~ !J(j, .. . .. . , · .. .. j,). wlw c /1 is an a ay ha appea s in lw le -hand sid > (!hs) o an a~signmen s a emen loca <·d insid > he loop and B i~ an a ay in lw igh -hand sid > ( hs) o he same assignmen s a emcn . l he assignmen is unde con ol o condi ional s a emen s. hen all lw a ays in hc cxp <>ssions ha e ·alna e he condi ions an· nmsiden·d as i hey we > in he hs o lw assign- lll 'II s a enwn . , n a ini y cla ion can appea be n'<'n o dinwn- sions o he da a a ays in a e e ence pa • n. Dinwn- sio l R, 1 is said o lw a inc wi h dinwnsion A1 ,( deno ed ("1 1 ,. R,)) i j, 1 and i1, a e linea unc ions o lw ~a me loop con ol a iable. F om he analysis o e e enc ' pa e ns. lw D" C is lmil . "od >~ o he DAC cpn·,;en dinwnsions o da a a ays and edges <>p cscn a ini y ela ion~ lw- ween a ay dimensions ob ained by exam1111ng e oss- > e cnce pa c n~ (pa e ns in which he s and lhs a ays a e di e en ). Sel - e e ence pa e ns a e no consid > ed in he DAC building s ep. 1 odes in he DAC a e g ouped in columns; each column con ains hose nodes ep esen ing dimensions om lw same da a a ay. An edg<> (4 1 ,. B,) in he D C sho ·s a p e >n·nce o alignmen o di wnsions AI, and n,l. Acco ding o [1]. edges in lw DAC a e weigh ed in wo ways. On he one hand (and o sol e lw in >nli- mensional alignmen p oblem) .. each edg<> is Tigh ed depending on whe lw i is compe ing o mmcom pe ing wi h ano he edge ( e i i is compc ing and 1 i no ). Tw~o edges a e said o be compe ing i he~ a c gene - a >d by he same e e ence pa e n and a e incid ·n on he sanw node. A DAC so <lelined nay con ain mul ipl > edges be w~een a pai o node~ since he e migh he se e al <> >n·nce pa · ns in ol ing o da a a ays: each se o mul iple >dg •s caJI he cplac >d wi h a singl > >dge hose w~eigh is he sum o lwi wighh. On lw o he hand (and o soh-e lw in adimensional aligmncn p oblem). each edge is weigh <·d wi h he o se be ween he wo subsc ip s in he a ay dinwn- sions innJl >d. ln l1i~ case" mul iple edges a > no mc ged in o a single edge lwca use each 011e may s o e in o ma ion aho a di e cn shi p e e ence. P e e - Pnces o s ide alignnwn a P no econl •d in h > DAG in lw <·nncn e sion o he DDT. DDT abo pe o m~ a se o wdl-knmn1 op i niza- ions such as cxp ession subs i u ion. subsc ip subs i- u ion. and imluc ion a iable de ec ion. In [2] he au ho s e alua e he e ec i eness o hese op imiza- ions in e ms o amoun o ll 'W e e ence pa e ns analyzed and a ini y cla ion~ oh ai wd. They also analyz<> he complexi y o he DAC in eal code~ 111 e ms o numlw o node~. edges. and o sc s . 3.2 Including Pa alleliza ion Cons ain s in he DAG Loop pa alldiza ion 1s no independen o lw way a ays in he phase a e aligned and di~ ihu ed. I would he in e es ing o ha e a d >a ela ionship be- w·<>en loop le cls in a ph as<> ha is pa allel ized and dimensions o a ays ha a c aligned and dis ibu ed: his nm cas<' he applica ion o I e ow w compu es ule and o a mo e > 1eien gene a ion o pa allel code. Fo each loop in a phase eligible o pa alld execu ion (acco ding o dqwndcnce analysi:;). a se o edg 's link- ing dimensions o a ay~ (in w lhs o a~sigm wn s a <>men s) ~uhsc ip cd by i s loop con ol a iable a > added in lw D" C. : "o e ha hese <'dges a c di e - PHI han he indqH·nd >nC<' an ip c cn·nce edgPs de- lined in [16]. Tlwy cha ac e ize po en ially pa alleli- 1 c ==;== FIGLRE 2 DAG o plHN' 4 in Dl including a ini y all(! pa all 'liza ion edg 's. zahl ' dimensions o a ays (in bo h sid >s o he assignmen s a emen s) i he subsc ip is no a scala . In o DAC. lw edge'i eco d p e <:> 'nccs o alignnwn o w dimensions ha a ' accessed by a loop eligible o be pa alldizcd. Fo ins ance .. conside phase -l in he ADI p og am in Figm<:> 1. I he alignmen and dis ibu ion o a ays x and b we e he ollowing: !HPF$ TEMPLATE a ge (256, 256) !HPF$ ALIGN x(i,j) WITH a ge (i,j) !HPF$ ALIGN b(i,j) WITH a ge (j,i) !HPF$ DISTRIBUTE a ge (BLOCK,*) hen he e would no he an easy pa alldiza ion s a - egy o he loop nes . Acco ding o he owne compu es ul '. w lhs o he i s assignmen s a enwn suggc~h a pa allcliza ion o lw i loop bile he s •cond one sugges s a pa alleliza ion o he j loop. I he ule is b ok >n in one o he wo s a emen s. addi ional da a mon• ncn a ises. Figu e 2 shows he DAC o phas ' 1: in ADT. No ice ha in addi ion o he edgeb ha show a !lni y lw w 'Pn dinwm;ions in a ay <:> <:> <:>nces ( hin edg<:>s (. 1• a1 ). (.1·". a'!.)· (a 1• b1 ). (a". h"). (: 1• b1 ). and (. ". b")). a ww edge be we<:>n (.1· 1• b1) is added. This edge lws a w 'igh big <:>nongh o ensu e ha lw D. C pa i ioning algo- i hm desc ibed in lw n 'x sec ion will align all he nodes linked by i . 3.3 DAG Pa i ioning and A ay Alignmen Two p obl<:>ms a c aced wlwn sol ing he a ay align- IIH'Ji s Pp. Fi s . l1e in <:> dimensional aligm wn p ob- l<·m ies o de ide l10w a ay dimensions a e aligned in o he dimensions o a common empla e a ay. This c npla e has dimensionali y <:>qnal o he la g<:>s di- IIWJJsionali y o ' all he a ays analyzed. Each dimen- sion o each a ay is aligned i l1 a dimension o he ·mpla c. S<:>nmd. he in adinwnsional alig nnen p oblem ies o decide how all he a ay dimensions aligned in o a dil!H'nsion o lw empla e a c shi <:>d DDT: A RESEARCH TOOL 79 'ach o he . Al hough hi!-i includes o se and s ide aligm wn s and e lec ions (s ide -1). only o se alignmen s ha 'e be<:>n implemell <:>d in he CliiT<:>n Yc - sion o DDT. ln e dimensional Alignmen Ci en a DAG G. he in enlimensional alignmen p ob- lem can be b a ed as ollows [ 1 J: Le n be he ma. imum nwnbe ~( nodes in a column <d' G. Pa i ion he node se ~~l G in o 11 di.~join subse s T1 ••••• I 11 • !l'i h he es ic ion ha no u·o nudes belon :ing· o he sanu' da a a a.1· a e allo!l'ed o be in he san e subse . :-.Jodcs in he same subse co espond o dimension' o be aligned. As a consequence. we wan o pa i ion lw DAG so as o minimize lw o al weigh o edges ha a c be ween nodes in di <:> Pn subs<:> s. The p obl >m .c; a cd abow is : P-comple e and [1 J p opose a lwn is ic algo i hm (g eedy) o soh·e i . In his algo i hm. a single da a a ay is amlo uly dwscn a 'ach s ep o alignmen wi h he e npla > (which is chosen among he da a a ays ha haY<:> maximum dimensionali y). The algo i hm appli<:>d o a g aph G is d >sc ilwd below: C, = Choose_Templa e_Column(G); while (no _emp y(G)) { Cx = Pick_Up_Column(G); G, = Fo m_Bipa i e_G aph(C , C,, G); M Op imal_Alignmen (G 2 ); G = Reduce_G aph(M, C,, C"G); In >ach i e a ion o he abo <:> loop. he aligmnPn be Ten h ' da a a ay co T<:>spmHI ing o column C,. and he da a a ay COIT 'SJHHHling o lw >mpla e col- umn C, is decided. The main s eps o he heu is ic a c d<:>sc ibed below: 1. Fom _/Jzjm i e_G (qJ! . a g aph(;" <·omposcd o he nodes in he wo cohunns C, and C, is buil . An edge is placed be ween wo nodes in he bipa i e g aph G'!. i he e is a pa h IH' w<·en lw wo o iginal nodes in lw DAC. Tlw weigh o he edge is he s un o all edges ha compose he pa h.l scyc al pa hs appea . lwn lw Tigh is s • o he sum o all he edg<:>s ha co nJHN' he pa b. 2. Op il la/_A/ignmell . Fo <:>ach bipa i P g aph G2. align dimensions o C, wi h dinwnsions o C, so ha he o al weigh o <:>dg >s no aligned is lllllllllllllll. 80 A YGUADE ET AL. (a) (c) • • (b) (d) FIGURE 3 ~lin-cu s. Sum in Fo m_Bipa i e _G aph. :~. Reduce J) aph. Me ges column C, in o C,, e- places mul iple edges be ween wo nodes wi h a single edge whose weigh is he sum o hei weigh s, and (l •le es all sel cycles. ln ou implemen a ion, se e al op imiza ions in he lwn is ic ha e been done in o de o ob ain be e alignmen s. They a e desc ibed below: 4. In Fonn_B jw i '_G aph. he weigh o an cdge be wcen wo nodes is se o he min-cu ins ead o he sum o he weigh o all edges ha com- pose he pa hs. Wi h min-cu , he weigh is se o hc minimum sum o edge weigh s in G ha we had o elimina e o isola e he wo nodes. This ep esen s he minimal cos o no aligning lw wo nodes. Fo ins ance. conside he DAG shown in Figu e 3a (i co esponds o p ocedu e THED2 om he ETSPACK lib a y). Figu e 3b shows a s ep o Fom _Ripa i >_Gmph when a pa h bc wcen T2 (o C,) and Z1 (o C, in he s ep) is looked o . ln his case, he e a e wo pa hs: T2, D1• Z1 and T2• TJ1 .. E1. Z1. The bipa - i e g aphs ob ained using he o iginal [ 1] and he min-cu p oposals a e shown in Figu es :k ami 3d. >spec i ely. Op i w/_Alignmen would align (7'1, Z2) and (T 2, Z1) in Figme 3c (wi h six an:s o communica e) and (T1, Z1) and (TJ.. Z2) in Figmc 3d (wi h one a c o communica e). The solu ion ob ained wi h min-cu is be e han he o he solu ion and be e e lec s he ac ual da a mo >m ~n equi emen s. !1. Pick_{ /JJ'olumn chooses a column C, among all he columns in Gas he column ha is mo e c i ical in he alignmen p ocess ins ead o an a bi a y column. To decide how c i ical a col- umn is. we inspec edges be ween he empla e and each column in G. Fo ins ance, conside he same example in Figu e :3. Once Op ima/_ Alignmen and Reduce_G aph ha e been done, he g aph shown in Figu e 4a is ob ained. I we pick up column D, he di e ence be ween he wo possible alignmen s ((7'1. D1 ) o (7~, D1)) in he numbe o communica io11s is 1. On he con a y, i we pick up column E, he di e ence is 2. So in his case, i is mo e c i ical o i s sol e he alignmen o a ay E a he han a ay D. Figu es 4b and 4c show he di e ence. The algo i hm used o decide ha he nex column is ou lined below: o each Cx in G { G2 = Fo m_Di ec _Bipa i e(C,, c •. G); di (x) = Wo sLAlignmen (G,) - Bes _Alignmen (G 2 ); c. Find_Maximum(di ); Func ion Fo m_Di ec _Bipa i P e u ns he bipa i e g aph be ween wo columns in a g aph ha esul s om di ec edges. Func ions Res _Alignmen and Wo s _A ignmPn e u n o a bipa i e g aph he o al weigh o nonaligned edges wi h he bes and wo s possible alignmen s. The use o min-cu inc >ases he execu ion ime o he algo i hm wi h espec o he sum al e na i e. Howe e . he use o a heu is ic o choose he nex column dec eases he execu ion ime o he min-cu solu ion because a each s ep, he complexi y o he emainina a a1)h is lowe and he algo i hm p oceeds bb as e . In [21] he au ho s e alua e he use ulness o hese op imiza ions o ien ed owa d imp o ing he ou pu o he DAG pa i ioning algo i hm. In adimensional Alignmen The algo i hm we p opose o ind shi s among aligncd dimensions is desc ibed nex . Fo each dime11sion o he empla e, a di ec ed g aph G, is c ea >d. ~od >s in his g aph co espond o a ay dimensions ha a e 2 Dl ~:1 Tl 7 Dl 4 • T2 (a) T2 (b) T2 (c) FIGURE 4 Heu is ic o choose a IH'W column in dw g aph o alignmen . (a) ln e mPdialP g aph. (h) Bipa i e g aph wid domain E. ((')Bipa i e g aph wi h domain D. aligned wi h a dimension o he empla e. Edges in G, a e he subsc o edges in he DAC bc een he nodes aligned. In his g aph, edges a c weigh ed wi h he o se lw we >n hc wo subsc ip s in he associa ed de Tnce pa > n. The algo i hm impl >men ed is: o each dimension i o empla e { G, = Ob ain_Di ec ed_G aph(G, i); Ma k_Templa e_Node(Gxl; while (noLalLma ked (Gxl l{ N = Pick_Up_Node (Gxl; S = Find_Shi (G" N); Gx = Apply _Re iming ( G" N, S) ; Ma k_Node (G" N); This algo i hm is basically he same han he one p oposed in [23] o solw he s a emen alignmen p oblem in o de o educe synch oniza ion cos s in a sha ed memo y execu ion model. The main s eps o he aigo i Inn a e dcsc ihed helm : 1. Pick_ jJ_c 'ode. T e u ns an unma ked node o G, co lllec ed wi h a ma ked node o G,. I such a node is no ound. hen an unma ked node is andmnl sclec ed. 2. Fin(L)h[ i. This unc ion e u ns he o se S (wi h cspec o he empla e) ha hm; o be applied o he node" ' cu en ly analyzed. This alm· is ob ained om he o se o all he edges lw wee11 node ;V and any ma ked node o G,. I se c al edges he Ten nod > ,y and w empla e nod · appea . he one ha is q)('a ed mo e imes is selec ed. I se e al edges a e candida es. hen he one wi h minimum alue is chosen. V ' ha 'e obse ed ha selec ing a alue di e en han ze o when ze o is one o he candida cs leads o poo solu io11s. . ). App(J·_He iminp:. The idea o e imi11g as de- sc ibed in [24] is applied in his unc ion. Tlw o s ' 8 ob ained in hc p e ious s ep is suh- ac ·d o all incoming a cs in o 11ode N. and added o all ou going a cs om node Y. A h ' e11d o he algo i hm .. each node in G, has an associa ed shi wi h espec o he empla e node. I G, is acyclic. a pe ec in adimensional align- I!Wn esul s. In his cas ~. all he edges a e aligned and no da a mo emen is needed. I cycl 's a e p esen in C,, hen some >dges may no he aligned and he e o e. da a mo 'e nen may be equi ed o hem. DDT: A RESEARCH TOOL 81 Table :3. Communica ion Hou ines and Thei Ma ehing wi h Re e ence Pa e ns Rou ine [,o al _/ lemul") ·_A cess Cop}· Shi One_ oA/1 /1/l_ oJJne 41/_((i_.' /1 Pa e n i,l = .1~1 cons (i") A cons (;;,) cons (i1, ~ j,,) CO/IS (J;,) CUI/S (i 1 ,) i,, #.i ' 3.4 Communica ion Analysis Once da a a ays a e aligned. each e e ence pa e n ha is no aligned (in e - o in aeomponen align- men ) a e he p e ious phase ep esen s da a mo e- men ha has o be ca ied ou . In his phase. a ma ch- ing o e e ence pa e ns o a p ede in >d se o da a mmcmen ou ines is done. In he cmTen impbnen a ion. DDT conside s sim- pl · da a mo e1nen ou ines ( ou ines ha pe o m da a mo emen in a single dimension o he empla e). I he e e >nC ' pa e n equi es da a mo >men in mo e han onc dimension. hen he e e ence pa e n is decompo.~ed in o subpa e ns and each subpa > n ma ched wi h a single da a mo emen ou im~ ( cach one pe o ming da a mo 'IIH'll in a single dimcnsion o he a ays). Fo each e e ence pa e n (o subpa e n i denun- posed). he da a mo emen ou ine ha pe o ms he da a mo emen wi h les~ cos is chosen. Table 3 shows he s · o da a mo emen ou in 's conside ed In DDT and ib ma ching "~i h e e ence pa e ns. In his able. p is he dimension whne da a mm· ·men akes place and i1, and j" a e he subsc iph in he dimension p o he e e ence pa e n. Func ion cons (P.lp) e u ns ue i e. p con ains cons an s only. The ma ching be ween da a mo emen ou ines and n· , TJHT pa e ns is pe o med in o de o ob ain an es ima ion o he oye head due o emo e acccsses . Each da a mon·men ou ine has an es ima cd cos . This cos is dependen on he a chi ec u e o he sys- em. he size o he block o da a o be ans e ed. and he numbe o p ocesso ,; in ol ed in he da a moyemen . The size o he block R is es ima ed hY DDT as ollows: , dim, . H =.')X IT ---y- X pos( , ~ 1) #p ' I S ep es 'n s he numlw o elemen s moYed in he dimension p whe e he da a mm- nH·n akes place. S, is he numbe o p ocesso s alloca ed o dimeusion i 88 AYGliADE ET AL. p og am shallow call ini al Phase 1 call calcl Phase 2 call calc2 Phase 3 i (ncycle .le. 1} hen call calc3z Phase 4 else call calc3 endi end (a) Phase 5 (b) FIGURE 7 (a) Ou line o he main p og am in he SPEC swm256 benchma k. (b) Con ol low g aph. in a ian . As a esul , a single mapping o phase 4 is selec ed acco ding o he p e iously ixed mappings o phases 1, 2, and :~. 61NTERPROCEDURAL DATA DISTRIBUTION The main aspec s conside ed in he in e p ocedu al da a dis ibu ion analysis pe o med by DDT a e de- sc ibed in his sec ion. The algo i hms used bo h o s a ic da a dis ibu- ion o dynamic edis ibu ion in he case o in e p o- cedu al analysis a e basically he same as hose used o he in ap ocedu al case. The de ini ion o phase is ex ended o conside some p ocedu e calls as phases, besides he loops as desc ibed in Sec ion· 4. l he p ocedu e call is ou side a loop which is conside ed a phase i sel , hen he p ocedu e is conside ed a phase. O he wise, some in o ma ion ob ained om he p e i- ous analysis o he called p ocedu e is used o es ima e he e ec s o he mapping o his p ocedu e while deciding he mapping o he phase. The analysis is based on he call g aph in which nmks ep esen p ocedu es and edges ep esen call si es. This g aph con ains ep esen a ions o he onnal and ac ual pa ame e s and hei dimensions associa ed wi h each p ocedu e and call si e. I is a e sed b DDT o decide he o de in which p ocedu es will be analyzed. The app oach ha has been conside ed is a bo om-up a e sal o he call g aph: Those p ocedu es ha a e deepe in he call g aph a e analyzed i s . This bo om-up a e sal ensu es ha when a call o a p ocedu e is ound hen i has al eady been analyzed, and he e o e he in o ma ion o ha p ocedu e is al eady in he in e p ocedu al DDT da abase. When a mapping speci ied o a dummy a gumen o global a iable di e s om i s ac ual a gumen o global a iable, liPF equi es implici da a edis- ibu ion and/ o ealignmen . Addi ionally. upon e- u n o he calle p og am, he o iginal mapping mus be ees ablished. So wo possible emappings o each a gumen and global a iable should be conside ed. O he p og amming models based on HPF, such as he one o e ed by FORGE [11], allow you o lea e an ou pu mapping di e en han he inpu one. In his case, he in o ma ion s o ed in he in e nal DDT da abase a e deciding he mapping o he p ocedu e will be i s ini ial and inal mapping (in addi ion o he ealignmen ac ions pe o med inside i and i s execu ion cos wi h he selec ed s a egy). No ice ha his la e model is a gene aliza- ion o he de ini ion o HPF. DDT ac ually suppo s bo h al e na i es. A p ocedu e may ha e se e al candida > mappings s o ed in he in e p ocedu al da abase. l di e en mappings a e p e e ed in di e en in oca ions o he same p ocedu e, hen p ocedu e cloning is applied in o de o ge1w a e e sions o he same p ocedu e wi h di e en mapping and pa alleliza ion al e na- i es. 6. 1 The P ocedu e Call is a Phase A p ocedu e call is conside ed a phase when i is no placed inside a loop agged as a phase. The emapping algo i hm used in his case is mainly he one desc ibed in Sec ion 4.1. Howe e , unc ion Ge w a eJJocaL Mappings eads he in e nal DDT da abase in o de o ob ain he di e en candida e mappings o he called p ocedu e, ins ead o compu ing hem om sc a ch. Phases due o p ocedu e calls ha e candida e map- pings composed o an ini ial and a inal mapping. In his case, he cos o emapping will he de e mined by he mapping di e ences be ween he ac ual global mapping and he co esponding ini ial mapping o he phase. Howe e . a e he exeeu ion o he phase, he global mapping will be upda ed wi h he inal mapping. This means ha when gene a ing di e en pe mu a ions o he local mapping in o de o es ima e di e en ealignmen op ions, bo h he ini ial and he inal mappings should be pe mu ed. This analysis could be ex apola ed and used o analyze any kind o phase (loop and call), assuming ha he local mapping o a loop has he same ini ial and inal mappings, whe eas he call has i s co e- sponding ini ial and inal mappings. The nex example is used o illus a e he aspec s desc ibed abo e. Assume ha some phases o a p oce- du e ha e been analyzed, and ha a his poin he global mapping GA1 1 con ains he ollowing in o - ma ion: A 1/i(- ) 2n(- J Ul!,: R 1/1(- ) 2/1(-l) c 1/i(-!J 2/1(- ) D 1/i(- ) 2n(- J This means ha in he global mapping GM,. all a ays u~ed lw o ' ha phase a e pe ec ly aligned. and hei i s and second dimensions a c dis ibu ed wi h ou p ocesso s assigned o each on '. Assume also ha he nex phas ' o be analyzed is a p occdu ' call whose local mappings in L!H,+ (ob ained om he in e p oce- du al da abase) a e he ollowing: A 1/1(- ) 2/i(- ) Ini ial LM,+ : R 2/i(- ) 1/1(- ) c 2/i(- ) 1/1(- ) E 2/i(- ) 1/1(- ) A 1/i(- l 2/i(- ) Final LM,+ : n 1/i(-!J 2/i(- ) c 1/i(-!J •) ~!i(-!J E 1/1(- ) 2/1(- ) Vhen analyzing his phase .. a ays used in his phase mus be agged acco ding o he dis ibu ion di e - ences be ween h ' global mapping and lw ini ial local mapping. 'e can see ha a ay E is new .. so i will be included in he global mapping wi h i s desi 'd dis ibu ion (no e ha i will also be included in he ini ial mapping o his p ocedu e). A ays 11. B. and Ca e candida es o be ealigned. Two di e en al e - na i es should be nmsid ' cd: o keep a ay A as i is and ealign a ays Band C:. o o keep a ays Band C as hey a e in he global mapping and ealign a ay A. ln o de o upda e he global mapping GM,+ 1• lw inal local mapping is h ' one ha mus be ak 'n in o conside a ion. This nwans ha i he i s al e na i e is selec ed. a ay A is hp as i is in he global mapping awl nei he he ini ial local mapping no he inal one is ansp be l So he global mapping will emain: A 1 /1(- ) 2/1(- ) n 1/1(- ) ') ~11(- l c 1/1(- ) 2/1(- ) [) 1 /1(- ) 2n(- ) E 1/1(- ) 2/i(- ) DDT: A RESEARCH TOOT, 89 Bu i dw second al e na i ' is scl 'c ed. hen a ays B and Ca e kep as hey a e in he global mapping so bo h he ini ial and he inal local mappings a e ansposed. In his case he global mapping will be: A ') ~/1(- ) 1/1(- ) n ') ......,H(- ) 1/1(- ) c 2/1(- ) ] /1(- ) j) ] /1(- ) 2/1(- ) E ') ~/1(- ) l l,.- ) 1 o e ha lw mapping o all a ays ( 'xcep o TJ) in GJ ,+ 1 in his las al e na i e is di P Tn ( ansposPd) om hei mapping in GJJ,. and appa en ly only a ay A has been ealigned. A en ion mus be paid o he local mappings o phas ' p,+1• The di e ence be ween he iui iallocalmapping and he inal one m >ans ha . a leas , a ays R. C. and/) ha e been >aligned inbide l1e pnlc 'dn e. and hus hei cos has al eady he >n assnnu•d wi hin he cos o 'X 'Cn ing he p ocedn c. l he i s al e na iw is selec ed, hen a ays Band C a e ealign 'd lw o e he p ocedu e eall aud inside i as welL so he G/ /,+ 1 emains unchanged wi h >sp 'c o GJ!,. A his poin i is no possible o say which al e na i e is he bes because i dqwnds on he phases no y ' analyzed. so he analysis mus con inue wi h he wo al e na i es. 6.2 The P ocedu e Call is Inside a Phase When he H'OC 'du e call is placed inside a loop which is agged as a phase. heu he call is no conside ed a phase. ln his UlS ' .. he ini ial and inal mappings assigned o he p ocedu e may a ec he choice o lw candida e mappings o he phase. When a call s a emen is ound, DDT impo s om he in P p occ- du al DDT da abase all he in o ma ion associa ed o each possible mndida e mapping o he called p o- cedu e. Dn ing he aligumen s ep, when a call s a emen is ound, DDT impo s om h ' co esponding ile in he in e p ocedu al DDT da abase he in o ma ion ega ding ALlGJ di ec i es o he global a iables and he ac ual pa ame e s. This in o ma ion is in- cluded in he DAG o he phase as addi ional cdg 's. ln ac . his is an app oxima ion o he p obl 'nL A mo e accu a e model should ha e o weigh hese ne ' edges wi h i s co esponding ealignmen cos . Du ing he dis ibu ion s ep. and o eac:h eall o a p ocedu e. he global a iables and he ac ual pa ame- e s mus lw emapped (i necessa y) be o e and a e 90 AYGUADE ET AL. lis iles S a ic e alua ion epo s Dynamic e alua ion epo s FIGURE 8 Main componen s o ou au oma ic oa a dis i- bu ion pla o m: DDT. xHPF compile . ano simula o om APR Inc. h > call. The mapping ha minimizes h > o > all cos including emapping is selec ed among he candi- da e ones. 7 EXPERIMENTAL RESULTS The main componen s o h > da a dis ibu ion cn i- onm >n we a e using and de eloping a P shown in Figu > ii. Ou esea ch ool (DDT) is impl >men ed on op o Pa a Scope [2;)] and assmnes s >quen ial p o- g ams V i en in Fo an 77 as inpu . DDT pa ses ll ' inpu emi > and anno a es i wi h a se o iiPF di ec i es and >xecu able s a >men s. The xHPF compile om Applied Pa allel ResPa ch [11 J is us >d o compile he p og am gene a ed by DDT and o gene a P a single-p og am mul iple-da a (SPMD) node p og am using PVM3 communica ion p imi i es [26 J. The xHPF execu ion model allows us o simula e he execu ion o he ins um >n Pd code gene a ed by xHPF on a singl > wo ks a ion. This si w- la ed execu ion is used o p > o n compa isons o he pe o mance o di e >n da a dis ibu ion s a egies and o alida e ou p oposals. We haw analyzed h Pe p og ams: ADI (shown in Fig. 1 and analyzed in Sec ion 2), ou ine RHS om h > APPBT. APPLlj, and APPSP NAS benchma ks, and swm2S6 om lw xiiPF benchma ks sP . * V e will see o he examples how changes in some a chi >c u al pa anl ' e s. such as numbe o p oces- so s and emo e access ime, lead o changes in he solu ion gPne a ed by DDT. The ool is use ul o he cha ac e iza ion o p og ams as well as lw s udy o he e ec s o hese a chi ec u al pa ame e s. * AYailable by anonnnous p a p.in o mall.o g in di ec o y l'nan s/ ap i/Bcnch. 7.1 Al e na e Di ec ion Implici ADI In his sec ion we u lw analyze ADT and co npa T he pe onna H"P p >dic ed by DDT agains h > pe o - nH!Il " ' ob ained when simula ing he execu ion o he m >ssage-passing code gene a ed by xHPF. Tn addi ion. we also show w use ulness o he ool o p edic he pe o mance o di e en mapping s a egies when changing a chi ec u al pa ame > s. Figu e 9 shows lw p edic ed and he measu >d speedups o he p og am o di e en numlw s o p ocesso s ( anging om 1 o :32) o wo possible solu ions: Th > s a ic solu ion whe e all a ays a e col- umn dis ibu >d (adi2 in all plo labels) and he dy- namic solu ion (a diD in all plo labels) as shown in Sec ion 2. Fo his plo we conside ed a emo e acc >ss ime o 1 p.,s. Ve can d aw he ollowing conclusions: 1. Tlw p edic ion pe o nwd by DDT (solid lines) is e y clos > o he ac ual speedup ( dash >d lines). Tn he dynamic solu ion we ha > no iced a s111all di e Pnce due o he es ima ion o edis ibu ion cos s. The model ha we conside o es ima e hese cos s (see Sec ion '1.3) is no e y accu a e and o e es ima es he numbe o da a cle- men s mo ed. 2. The speedup o he s a ic solu ion g ows om one ( o one p ocesso ) o wo ( o machine con- igu a ions wi h a la g > numbe o p ocesso s). This is due o lw ac ha abou one hal o he p og am is execu ed in a synch onized way wi h an Pxecu ion im > close o he sequen ial exPcu- ion ime. 3. The speedup o he dynamic solu ion is lowe han one o con igu a ions wi h less han ou p ocesso s bu hen g ows wi h an e iciency dos > o ou . This is due o he ac ha emap- 16 Numbe o p ocesso s 32 ~ adiD (p edic ed) ·+- adiD(measu ed) ~ adi2 (p edic ed) • K- adi2 (measu ed) FIGUH.E 9 ADI- spe 'dup s. numbe o p ocesso s o he s a ic and dynamic solu ions. Compa ison o he p e- dic ed and measun·d speedup ( emo e ac~!'ss ime= 1 p.,s). DDT: A RESEARCH TOO/, 91 Table 5. B eakdown o he To al Execu ion Time o ADI (Remo e Aeee8s Tim!' = 1 .LS) S a ic Solu ion Nm LP ocs lo emen Compu a ion () 10.S1S 0.1024 7.909 0.1024 6.606 8 0.10:2-i S.<JSS 0.10:24 5.629 0.102-i S.- 67 ping cos s an~ n~ y la ge when a small numbe o p ocesso s a e a ailable and ha all phases in he p og am a e execu ed in pa allel. 4. Wi h his emo e access ime, DDT chooses he s a ic solu ion o less han eigh p ocesso s and he dynamic solu ion when eigh o mo e p oces- so s a e a ailable. To u he compa e he dynamic and s a ic solu- ions. Table:) shows he b eakdown o he p edic ed execu ion ime in compu a ion and da a mo emen imes. No ice ha o he s a ic solu ion, he da a mo emen o e head is cons an (i is due o shi s whe e he numbe o el >men s mo ed is independen o he numbe o p ocesso s). Howe e , in he dynamic solu ion he edis ibu ion o e heads dec ease wi h he numbe o p ocesso s in ol ed in he da a mo emen . Figun· 10 shows he p edic ed speedup when he emo e access ime changes o he s a ic and dynamic solu ions. The aim o his g aph is o show he in luence o emo e access la encies in hese solu ions. In his 15 o~~~~~~~~~~ -~~~~~~~~~ 0.001 0.01 0.1 10 100 1000 Remo e access ime (mic osecs) FIGURE 10 AD I- p edic ed speedup s. emo e access ime o he s a ic and dynamic solu ions. 6.. adiD; D, adiZ. D namic Solu ion To al Jo emen Compu a ion To al 10.;")1- 0 10.680 10.b80 B.011 1- . 9'±2 ;) .• ")- O 20.282 (J.70<J 7.-+71 2.670 10.11-1 6.038 :3.733 1.T3S :1.070 !i.T-12 1.867 0.66 7 2.S:3S S.S(J<J 0.9TJ (J.:F2 1.:372 plo we assume ha he numbe o p ocesso s is H>. The ollowing conclusions a > d awn: 1. Fo e y lm,, access la encies, he speedup ends o be in 16 in he ch'namic solu ion ami 2 in he s a ic solu ion. 2. The s a ic solu ion is less sensi i e o he memo y la enc han he d namic solu ion. This is dw· . . o he ac ha he olume o da a ans e ed in he s a ic solu ion is small while in he dn a nic solu ion i is la ge. Fo la ge la encies. any gain due o pa allel execu ion is o se by he da a mo emen o e head. :3. Fo his numbe o p ocesso s. DDT chooses he dynamic solu ion when he emo e access ime is less han;) p.,s and he s a ic solu ion o he wise. 7.2 hs Rou ine om NAS and swm256 Benchma k In his sec ion we anaiYz > he beha io o he solu ion sugges >d by DDT o he o he wo benchma ks: he hs ou ine om 'IJAS and he swm2S(J p og am. Fo each o hem we compa e he pe o mance p edic ed by DDT agains he JW o mance ob ained in he simu- la ed execu ion. X" e assume ha he emo e access ime is 1 p.,s and ha he sys em has om one o eigh p ocesso s. Figu e 11a shows he beha io o hs. ln his case DDT sugges s a dynamic solu ion whe e h ee a ays ha e o be emapped. The dynamic solu ion implies ha he ou e loop in each phase uns in pa allel. In his case he p edic ion is dose o h > ac ual pe o - mance because DDT pe o ms an accu a e es ima ion o bo h da a mo emen and pa allel compu a ion imes. Figu e 11 b shows he beha io o swm2:)6. ln his case DDT sugges s a s a ic solu ion whe e all he a ays a e dis ibu ed by columns. This s a ic solu ion implies ha almos all he loops un in pa allel. The main 92 AYGFAD ~ ET AL. 2 4 Numbe o p ocesso s (a) 04-----------~------------.------------- 4 Numbe o p ocesso s (b) FIGL'RE 11 Pn·dic Pd and measu Pd spe >dup s. uumlw o 1n·ocPswn; o (a) hs-chnamic solu ion . .l. hs (p c- dic >d); D. hs (measu >d). (h) swm2S6-s a ic solu ion .. assuming mo · access ime= lms . .l. shallow (p edic Pd): D. shallow (mcasu >d). p og am in swm2;)6 indudPs an i Ta i e loop and condi ional s a emen s ha alida P he cmT 'C beha - io and es ima ions o he con ol llow module in DDT. o ic ' a small di e ence lw ween he p edic ed and measu ed S wedups. Tll ' di e ence is due o an o e es- ima ion o he da a mo enl 'n o e h 'ad: o ge a be e es ima ion, we ha ' o imp o ' he nodulc~ ha de ec s 'dundan da a mo ion ei lw wi hin a phase o he wPPn phases. 8 CONCLUSIONS AND REMARKS In his a icle wP ha e p escn 'd he key modules in ou au oma ic DDT. DDT gene a es bo h s a ic and dynamic HPF da a dis ibu ions o a giwn Fo an 77 ou i l ' and o a whole applica ion wi h in ' p oce- du al analysis. In he s a ic solu ions, ll ' mapping (alignmen and dis ibu ion) o each a ay in he p o- g am does no chang ' du ing he exPcu ion. The s a ic module is based on he CAC bu is ex PIHl 'd wi h some in o ma ion ega ding pa allelism. We ha e also nwcli iPd he o igiual algo i hms in [1. 17] o imp ow hP quali y o he mappings ge w a ed [21 J. Dnuunic solu ions inelud > exPcu able s a pmen s in he sou ce code ha change he mapping o speci ic a ays when n 'cessa y lw ween compu a ional phasPs. DDT pe o ms a cos analysis o p o i abili y in o de o include lwm. This analysis o p o i abili y is bas 'd on he ollowing s eps: 1. D ' ec ion o phases o compu a ionally in ensi ' po ions o code. which mainly co espond o nes 'd loops and calls o p oc 'du es. Remapping is only allowed be w ' 'n phases. 2. Gene a ion o candida e mappings o he p e- iously de ec ed phases all(! es ima ion o hei cos (including da a mo 'men and expcu ion ime cos s). :1. Analysis o compa ibili y among phases .. selec- ion o mappings o hem. and emapping ac- ions o lw pe o m 'd be we >n consecu i e phases. This selec ion is done by analyzing he cos in Pnns o da a noyenu•n due o 'dis i- hu ion and i s bene i s in he cos o succes- si e phas 's. Con ol low in o ma ion is us >d o iden i y sequencing o phases. The algo i hm explo Ps a ich sP o combi- na ions al hough i is no Pxhaus i '. I includ >s nwch- anisms o cu down he sea ch spac '. DDT is a esea ch ool ·hich is cu en ly us 'd in ou g oup o suppo di e pn 'sea ch aspec s. Since i is a esea ch ooL i can use echniques ha may be oo compu a ionally expensi e o be included in a inal compil ' ; how 'Y 'L his allows us o 'xplo e a ich sP o solu ions. We ha e endua 'd he quali y o he solu ions gen- en 'd by DDT by compa ing p edic ed pe o mance agains he ae ual pe o mance when he pa allel p o- g am is >xecu ed. Ve ha e also shown he use ulness o he ool o he cha ac e iza ion o he p og ams as well as he s udy o he e ec s o a chi ec u al pa a n ' P s. Ve ha e shown how he p 'die ed speed- ups a P close o he ac ual ones oh ai wd when he p og am is execu ed. DDT also accep s HPF di 'c i Ps in he sou c ' Fo an 77 p og am: in his case DDT is use ul as a suppo ool o he dewlopc o HPF codes in es ima ing he e ec o use -selec ed da a mappings and pa alleliza ion s a egies m he inal pe o mance o he pa allel p og am. We a e cu en ly po ing his echnology o gene a P d icien code o hie a chical global sha ed memo y a chi ec u es. In hese a chi ec u es a numbe o cen- al p ocessing uni s can simul aneously access da a anywhe e in he sys em. Howe e , he nonuni o mi y o he memo y accesses is s ill an impo an issue o conside and may equi e a higlu~ p og amming e o in o de o achie e pe o mance; ying o access hose ll' Pls in he hie a chy close o he p ocesso will in- c ease execu ion e iciency. The echnology de eloped o s udy he p o i abili y o dynamic da a emapping can be used o ack he mo emen o da a du ing p og am execu ion and hus pa allelize loops acco d- ingly, so ha he access o da a is done locally as much as possible. ACKNOWLEDGMENTS This wo k has lJPen pa ially suppo ed by CONVEX Com- pu e Co po a ion. COI YEX Supe compu e s S.A.E. CEPBA (Eu opean Cen e o Pa allelism o Ba celona). and by he . linis o Educa ion o Spain unde con ac TIC- 429/<JS. We hank Miguel Hu~ue om COI VEX SupP - compu e S.A.E, Robe 1e zge om CO~VEX Compu e Co po a ion. and he anonymous e iewe s o hei con- s uc i e commen s. WP also hank .Io di To es o his help in he implemen a ion o he in e p ocedu al d i e . REFERENCES [1] J. Li and M. Chen. ··Index Domain alignmen : Min- imizin~ cos o c oss- e e encing be ween dis ibu ed a ays.·· p esen ed a F on ie s90: 3 d Sy np. on he F on ie s o Massi ely Pa alld Compu a ion, College Pa k. MD. 1990. [2] M. Gup a, '·Au oma ic da a pa i ioning on dis ibu ed memo y mul icompu e s.·· PhD hesis, Cen e o Reli- able and High-Pe o mance Compu ing. Uni e si y o Tllinois a U bana-Champaign. 1992. [3] M. Gup a. S . . 1idki . E. Schonbe g, P. Sweeney. K. Y. Wang, and K. Bu ke. ''PTRAJV II- A compile o high pe o mance o an .. ·· in H . .T. Sips. Ed .. P oceed- ings o }w 4 h Wo kshop on Compu e s o Pa allel Compu e s. The Ne he lands: Del Uni e si y o TPch- nology. pp. 4 79-49.3. 1993. [ 4 J T. .l. Sche le , R. Sch eibe . 1. R. Gilbe , and S. Cha - e jee. '·Aligning pa allel a ays o educe communica- ion."" p esen ed a he F on ie s95: The 5 h Symp. on he F on ie s o Massi ely Pa allel Compu a ion, McLean. VA. 1995. [5] S. Cha e jee, J. R. Gilbe , R. Sch eibe . and T. J. She le . "A ay dis ibu ion in da a-pa allel p o- DDT: A RESEARCH TOOL 93 ~ ams.'" in K. Pingali e a!.. Eds .. P oceedings o lw 7 h Wo kshop on Languages and Compile s o Pa al- lel Compu ing. Lec u e J' o es in Compu e Science, ol. 892. :'-lew Yo k: Sp inge -Ve lag. pp. 76-91, 1994. [6 J ll. K eme . J. Mello -Cnnmney .. K. Kennedy. and A. Ca le. ''Au oma ic da a layou o dis ibu ed-memo y machines in he D p og amming en i omnPn .. '· p e- sen ed a he 1s ln . Wo kshop on Au oma ic Dis ib- u ed Memo y Pa alleliza ion. Au oma ic Da a Dis i- bu ion and Au oma ic Pa allel Pe o mance P edic ion .. Saa b uecken, Ge many. 199:3. [7] B. Chapman. T. Fah inge . and H. Zima. ·'Au oma ic suppo o da a dis ibu ion on dis ibu ed memo y mul ip ocesso sys ems. in ll. Bane jee e a!.. Eds., P oceedings o he 6 h Wo kshop on Languaws and Compile s o Pa allel Compu ing. Lec u e 1 o es in Compu e Science. ol. 768. 'lew Yo k: Sp inge -Ve - lag. pp. 184-199. 199:). [8] B. Chapman .. P. Meh o a. and H. Zima. ""P og am- ming in Vienna Fo an."" Sci. P ug. ol. 1.. pp. 31- :10 .. 1992. [9] S. Ili anandani. K. Kennedy. and C. Tseng. ""Compil- ing Fo an-D o 1 UMD dis ibu ed-memo y ma- chines." Commun. ACM. ol. 35. pp. 66-80. Aug. 1992. [10] G. Fox .. S. Hi anandani. K. Kennedy. C. Koelbel, ll. K eme .. C. Tseng. and M. Wu. "Fo an D language speci ica ion.·· Depa men o Compu e Science. Rice Cni e si y. Hous on. TX .. Tech. Rep. CRPC TR 90- 141.. Dec. 1990. [ 11 J AppliPd Pa allel Resea ch .. . hp e sion 2. o. [ ~se 's Guide. Place ille, CA: APR, 1995. [12] The Po land G oup. PGllPF -R(1e enee 1Hanual. Po land. OR: Po land G oup. 1994. [13] C. H. Koelbel. D. B. Lo eman .. R. S. Sch eibe . G. L. S eele. and M. E. Zosel. The high Pe o mance Fo an Handbook. ! umbe 1-2 in Scien i ic and Enginee ing Compu a ion Se ies. Camb idge, MA: MTT P ess. 1994. [ 14 J S. Wholey. '·Au oma ic da a mapping o dis ibu ed- memo y pa allel compu e s. in P oc. o. he ACM In . Con on Supe compu ing. pp. 25-:1:1. 1992. [1SJ K. Kennedy and li. K eme .. '·'Au oma ic da a layou o high pe o mance Fo an. Cen e o Resea ch on Pa allel Compu a ion, Rice Uni e si y. Hous on. TX. Tech. Rep. CRPC-TR9449B-S, Dec. 1994. [16 J K. Knobe, J.D. Lukas. and G. L. S eel , ''Da a op imi- za ion: Alloca ion o a ays o educe communica ion on SIMD machines.""]. Pa allel Dis ib. Compu .. ol. 8, pp. 102-118. Feb. 1990. [17] .T. Li and M. Chen. "Compiling eommuniea ion-d i- cien p og ams o massi ely pa allel machines.·· /£.'£'£' T ans. Pa allel Dis ib. Sys ems, ol. 2. pp. 361-375. July 1991. [18] R. Bixby. K. Kennedy. and U. K eme , ""Au oma ic da a layou using 0-1 in ege p og amming. ·• in P oc. o he In . Con on Pa allel A chi ec u es and Compi- la ion 1 >ehniques, pp. 111-122. 1994. 94 A YCliADE F:T AL. [ 19] P. C ooks and H. I I. Pe o . An au oma ic da a dis i- bu ion 1-!ene a o o dis ibu ed memo y l 111 lD ma- chines.·· in H . .T. Sips. Ed ... P o . o he 4 h In . IT in-k- shop 011 Compile s o Pa allel Compu e s. The Ne he lands: Del llniw si y o Technology. pp. :3:~ ++. 1 <)<);)_ [20] D. J. Pale mo and P. Bane jee, ··Au oma ic selec ion o dynamic pa i ioning schemes o dis ibu ed-menw y mul ico npu e s.·· in C.-H. Huang e aL Eds .. P oc. ! " lw S h Annual T o kshop on Languages and Com- pile s o Pa allel Compu ing. Lec u e 'io es in Com- pu e Science, ol. 103::1. New Yo k: Sp inge -Ve lag. pp. :~92-40(>. 1995. [21] E. Ayguade .. J. Ga cia. M. Gi on >s .. .1. Laba a . .1. To - n·s. and M. Vale o. ··De ec ing and using a ini y in an au oma ic da a dis ibu ion ool.'· in P oceedings o he i h Annual Wo kshop on T"nnp;uages and Gm - pile s o Pa allel Compu ing. K. Pingali P a!.. Eds. Lec u e No es in Compu e Science ol. 892. New Yo k: Sp inge -YP lag. 1994 .. pp. 61-7S. [22] E. Ayguade. J. Ga cia. M. Ci oni·s. M. L. G ande .. and .T. I .aba a. '·Da a Pdis ilm ion in an au oma ic da a dis ibu ion ool. in P oceedings o he ~ h An11ual Wo kshop on Lanp;uuges and Compile s j(J Pa allel Compu ing. Lec u e : o es in Compu e Science. ol. 10::1:1. : ew Yo k: Sp inge - V P lag. pp. 407 --±21. 1 <J<JS. [2:)] .T. Pei . ··P og am pa i ioning and synch oniza ion onmul ip ocpsso sys emS:" PhD hesis, l lniw si y o Illinois a l1 bana -Champaign. 1 <)86. [2-± J C. LPise son .. F. Rose. and J. Saxe .. '·Op imizing syn- ch onous cin:ui by e imin~.· · p esPn !'d a hP :) d Cal ech Con e ence on VLST. CA. 198:3. [25] K. Kennedy. K. , icKinle . and C-W. Tseng. ··Jn e - ac i ' pa allel p o~ amming using hP Pa aScope Pdi- o .·· Cen e o Resea ch on Pa allel Compu a ion .. Rice l'ni e si y. Hous on. TX .. Tech. Rep. CRPC- TR 90096, Oc . 1990. [2l>] A. Gucis . A.lkguelin. J. Donga a. V. Jiang. R. : 1an- chek. and . SundP am. ··PY: I:-Iuse · s guide and e - P ence numual.'" Oak Ridge 1 a ional Labo a o y. Tech. RPp. OB'iL/Tl 1-12187 . . 1ay 199:3. Submi you manusc ip s a h p://www.hindawi.com Compu e Games Technology In e na ional Jou nal o Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Dis ibu ed Senso Ne wo ks In e na ional Jou nal o Ad ances in Fuzzy Sys ems Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 In e na ional Jou nal o Recon igu able Compu ing Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Applied Compu a ional In elligence and So Compu ing Ad ances in A i icial In elligence Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Ad ances in So wa e Enginee ing Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Elec ical and Compu e Enginee ing Jou nal o Jou nal o Compu e Ne wo ks and Communica ions Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Ad ances in Mul imedia In e na ional Jou nal o Biomedical Imaging Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 A i icial Neu al Sys ems Ad ances in Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Robo ics Jou nal o Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Compu a ional In elligence and Neu oscience Indus ial Enginee ing Jou nal o Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Modelling & Simula ion in Enginee ing Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 The Scien i ic Wo ld Jou nal Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014 Human-Compu e In e ac ion Ad ances in Compu e Enginee ing Ad ances in Hindawi Publishing Co po a ion h p://www.hindawi.com Volume 2014