Align and distribute-based linear loop transformations

1 Align and Dis ibu e-based Linea Loop T ans o ma ions* Jo di To es, Edua d Ayguadé, Jesús Laba a and Ma eo Vale o Depa amen d’A qui ec u a de Compu ado s, Uni e si a Poli ècnica de Ca alunya Campus No d, Mòdul D6, G an Capi à s/núm. 08071 - Ba celona, SPAIN Abs ac In his pape we gene alize he amewo k o linea loop ans o ma ions in he sense ha loop alignmen is conside ed as a new componen in he ans o ma ion p ocess. The aim is o ma ch he s uc u e o loop nes s wi h he da a dis ibu ion and alignmen in o de o elimina e non-local e e ences whene e possible when compiling a sequen ial p og am o a dis ibu ed memo y machine. The alignmen and dis ibu ion unc ions a e assumed o be use speci ied o au oma ically gene a ed by he compile . The ans o ma ion p ocess is modelled wi h non- singula ma ices and we use he ideas ecen ly p oposed in his ield o ind pa o he ans o ma ion ma ix and gene a e an e icien ans o med code. Howe e , addi ional aspec s ha e o be s udied when he alignmen and dis ibu ion unc ions a e conside ed, bo h in he ob aining o he ans o ma ion ma ix and in he gene a ion o code. 1 In oduc ion Loop ans o ma ions ha e been ecognized o be one o he mos impo an componen s o he pa allelizing and ec o izing echnology o cu en supe compu e s. The aim is o ans o m nes ed-loop s uc u es in he sou ce p og am in o seman ically equi alen e sions wi h mo e oppo uni ies o pa allelize hem [1, 2]. When dis ibu ed memo y machines a e conside ed o un scien i ic codes, da a decomposi ion is needed. Da a ha e o be decomposed in o pieces and dis ibu ed among all p ocesso s. Op imizing locali y is c ucial o his kind o a chi ec u es and o non-uni o m memo y a chi ec u es (NUMA) in gene al. As a consequence, i is impo an o access local da a whene e possible o a oid he access o emo e da a. When non-local e e ences a e necessa y, and in o de o amo ize hei emo e access, block ans e o da a and da a euse a e addi ional aspec s o be conside ed and op imized o imp o e he e iciency. The p og amming model o e ed by Fo an-D [3] and HPF [4] gi es he p og amme con ol o e how o align and dis ibu e da a s uc u es ac oss p ocesso s. The compile has o be able o assign wo k o p ocesso s ( he owne ship ule is he simples way o do his [5]) and es uc u e loop nes s wi h he aim o a oiding non-local accesses as much as possible, and when necessa y, op imize communica ion o ans e emo e da a [6]. The single-p og am mul iple-da a (SPMD) model [7] is used o gene a e code. Each p ocesso uns he same p og am bu accesses o di e en pa s o he da a. Resea ch in he pas yea s has ocussed a inding a ma ix heo y o p og am ans o ma ions To es, J. [e al.]. Align and dis ibu e-based linea loop ans o ma ions. A: Wo kshop on P og amming Languages and Compile s o Pa allel Compu ing. "Languages and Compile s o Pa allel Compu ing: 6 h In e na ional Wo kshop Po land, O egon, USA, Augus 12–14, 1993: p oceedings". Sp inge , 1993, p. 321-339. ISBN 978-3-540-57659-4. The inal au hen ica ed e sion is a ailable online a h ps://doi.o g/10.1007/3-540-57659-2_19. 2 o e eal p og am pa allelism [8, 9] o exploi da a locali y and block ans e s [10, 11]. F om he speci ica ion o he sou ce loop nes and he ans o ma ion ma ix, a a ge loop nes is gene a ed wi h mo e oppo uni ies o exploi pa allelism o o da a euse. This s ep has been sol ed when unimodula ma ices a e used [8, 9] and in gene al, when non-unimodula ma ices a e conside ed. The key poin in he solu ions p oposed in he las case is he use o he Fou ie -Mo zkin elimina ion me hod and he He mi e No mal Fo m decomposi ion [12, 13, 14]. In his pape we p opose o conside he se o s a emen s in he loop body as a new componen in he amewo k o non-singula ans o ma ions. This allows o conside loop alignmen [15, 16, 17] in a uni ied way wi h o he loop ans o ma ions. We assume ha da a alignmen and dis ibu ion is ei he use speci ied o au oma ically gene a ed by he compile . F om he eaching alignmen and dis ibu ion unc ions o each a ay, and a ay e e ences in he s a emen s, a di e en ans o ma ion o each s a emen o he loop is de i ed wi h he aim o educing he numbe o non-local accesses. In he scope o his pape we conside ha he same ans o ma ion ma ix is used o all he s a emen s and add a di e en alignmen componen o each o hem. The owne compu es ule is he basic mechanism o associa e loop i e a ions o p ocesso s. Some imes he owne compu es ule can be elaxed allowing p ocesso s o compu e alues o da a hey do no own. Once compu ed, hese alues ha e o be send o he owne s. Deciding he alignmen componen o a s a emen can be done by analyzing i s mul iple igh -hand side and he le -hand side e e ences o dis ibu ed a ays. In o de o educe he numbe o non-local accesses, he owne compu es ule can be b oken. Aspec s dealing wi h he assignmen o i e a ions o p ocesso s and gene a ion o synch oniza ion o communica ion ins uc ions ha ake ca e o dependences a e no conside ed in his pape . The es o he pape is o ganized as ollows. In sec ion 2 we p esen he e minology and assump ions used along his pape . In sec ion 3 we ou line some p e ious wo k on loop ans o ma ions, code gene a ion o hem and ob aining o he ans o ma ion ma ix when NUMA a chi ec u es a e conside ed. Sec ion 4 p esen s he alignmen componen in he ans o ma ion amewo k and code gene a ion. In sec ion 5 we discuss some ideas and p oblems o ob ain he alignmen componen ha is added o each s a emen . Finally, we conclude he pape and p esen some u u e wo k. 2 Te minology and Assump ions Th ough his pape we conside pe ec ly nes ed loops {L1, ..., Ln} whe e bounds o any loop Lk (1≤k≤n) a e a ine unc ions o indices o i s ou e loops L1, ..., Lk-1, ha is, The i e a ion space o his loop nes is de ined as and can be w i en ollowing he ma ix no a ion used in he li e a u e ikak 0, ≥ak 1, i1 ⋅... ak k 1–( ),ik 1– ⋅+ + + lk = ikbk 0, bk 1, i1 ⋅... bk k 1–( ),ik 1– ⋅+ + +≤uk = IS i1... in , ,( ) Zn ∈lkikuk ≤ ≤, 1kn≤ ≤{ , }= αI⋅ β≤ 3 whe e L is cons uc ed om he coe icien s ak,i (1≤k≤n, 1≤i≤k-1) o he loop indices in he lowe bound exp essions, U is cons uc ed om he coe icien s bk,i (1≤k≤n, 1≤i≤k-1) o he loop indices in he uppe bound exp essions, ID is he iden i y ma ix, and l and u a e cons uc ed om he independen coe icien s ak,0 and bk,0 (1≤k≤n) o he lowe and uppe bounds espec i ely. Fo example, o he loop nes in Figu e 1.a, he IS o he loop can be de ined by Figu e 1.b shows he aspec o he IS o his loop. Each poin ep esen s he execu ion o one i e a ion o he inne loop body. In he scope o his pape we conside dense i e a ion spaces, i.e., spaces whe e all poin s co espond o i e a ions o he loop. The loop body is composed o mul iple assignmen s a emen s {S1, ..., Sm} ha e e ence a ay a iables whose subsc ip s a e a ine unc ions o loop indices i1, ..., in. Le V be he se o s a emen s in he loop body. The S a emen pe I e a ion Space (SIS) o a loop nes is de ined as he ca esian p oduc Each poin in he SIS ep esen s he execu ion o an i e a ion o a s a emen o he loop body. Dependence ela ions be ween a pai o s a emen s Siand Sj (deno ed Si δ Sj) appea when he e is an execu ion o de ing be ween hem [18]. We do no dis inguish be ween di e en kinds o da a dependences because hey all impose o de ing cons ain s in he same way. When dependence ela ions a e uni o m (i.e., in a ian h ough he SIS), hey can be cha ac e ized by dis ance ec o s d=(d1, ..., dn) exp essing he numbe o i e a ions ha he dependence ex ends ac oss in each loop dimension. Dependences a e lexicog aphically posi i e, ha is, he leading non-ze o componen is always posi i e. A ays accessed du ing he execu ion o a loop a e conside ed o be aligned among hem and dis ibu ed ac oss p ocesso s. The alignmen and dis ibu ion o he a ays is assumed o be use speci ied o au oma ically gene a ed by he compile [19, 20]. In any case, we conside ha each a ay accessed in he loop is a ec ed by a se o eaching alignmen and dis ibu ion unc ions. These unc ions a e he s anda d suppo ed by cu en da a-pa i ioning languages such as Fo an-D. The ALIGN s a emen maps each a ay elemen on o an index domain o DECOMPOSITION. The DISTRIBUTE s a emen g oups elemen s o he decomposi ion and maps hem on o he pa allel machine. Alignmen can be ei he wi hin o be ween dimensions and include o se s. Each dimension is localized o dis ibu ed in a block, cyclic o block-cyclic manne . αL ID– ID U– = and βl– u = 1– 0 0 1– 1 0 0 1 i1 i2 ⋅ 1– 1– 10 8 ≤ SIS IS V×= 4 Figu e 1: Wo king example: (a) Sou ce loop nes and (b) o iginal IS. (c) Ta ge IS when a non-singula ans o ma ion ma ix T is used. (d) T ans o med loop nes ha scans he poin s in he ans o med IS skipping o e poin s ha do no ha e o be execu ed. 1 2 3 4 5 6 11 12 13 14 15 16 j1 j2 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 T1 2 1 0 = (b) (c) 7 8 9 10 DO i1=1, 10 DO i2=1, 8 (a) A[i1+2.i2, i1] = (A[i1+2.i2, i1], C[i1+1, i2], B[i1+2.i2-1, i1]) B[i1+2.i2, i1] = g(A[i1+2.i2+1, i1], B[i1+2.i2, i1]) ENDO ENDO 1 2 3 4 5 6 7 8 i2 1 2 3 4 5 6 i1 7 8 9 10 DISTRIBUTE E (CYCLIC, :) ALIGN B (i, j) WITH E (i+1, j-1) ALIGN A, C WITH E DO j1=3, 26 DO j2 = j1 + 2 .max (-8, (1-j1)/2), j1 + 2 .min (-1, (10-j1)/2), 2 A[ j1, j2] = (A[ j1, j2], C[ j2+1, ( j1- j2)/2], B[ j1-1, j2]) B[ j1, j2] = g(A[ j1+1, j2], B[ j1, j2]) ENDO ENDO DISTRIBUTE E (CYCLIC, :) ALIGN B (i, j) WITH E (i+1, j-1) ALIGN A, C WITH E (d) 5 The sequen ial code in Figu e 1.a shows he eaching alignmen and dis ibu ion unc ions o he a ays e e enced inside he loop. No ice ha jus one dimension is dis ibu ed, as speci ied by he : a ibu e in he DISTRIBUTE s a emen which deno es ha he dimension is assigned locally. In he example, i P is he numbe o p ocesso s, p ocesso p (p=1, 2, ..., P) owns ows p, p+P, p+2.P, ... o ma ices A and C and p-1, p+P-1, p+2.P-1, ... o ma ix B. 3 Linea Loop T ans o ma ions and Da a Access Ma ix A loop ans o ma ion is a mapping be ween wo i e a ion spaces (named o iginal and a ge IS). In his pape we conside linea ans o ma ions, which can be modelled using non-singula in ege ma ices. Unimodula ma ices (i.e., ma ices whose de e minan is ±1) a e a pa icula case and can be used o model some basic ans o ma ions such as pe mu a ions, skewing and e e sal [8, 9]. Non-unimodula ma ices can be used o model o he basic ans o ma ions such as scaling [12], bu in gene al, any linea ans o ma ion ep esen ed by a non-singula in ege ma ix can be iewed as a composi ion o hese ou basic ans o ma ions [12]. Le I be a poin o he o iginal IS, J a poin o he a ge IS and T he ans o ma ion ma ix. The ela ionship among hem is The a ge IS can be dense o spa se depending on he unimodula i y o he ans o ma ion ma ix. In ou model, he i s p ows o he ans o ma ion ma ix T de ine he spa ial componen o he ans o ma ion and he las n-p ows he empo al componen [21]. I e a ions in he ou e mos loops o he ans o med nes a e dis ibu ed among he p ocesso s while i e a ions he inne mos loops a e execu ed sequen ially wi hin each p ocesso . Le d be a dis ance ec o in he o iginal IS. Due o he ac ha T is a linea ans o ma ion, T.d is he ans o med dis ance ec o in he a ge IS. A ans o ma ion T is legal i o all dependence ela ions d in he loop. This means ha each ans o med dependence has o be lexicog aphically posi i e in he a ge IS. 3.1 Da a Access Ma ix A linea ans o ma ion has o be ound in o de o ma ch he s uc u e o he loop nes s in a p og am wi h he eaching da a decomposi ion unc ions. [11] p oposes a ep esen a ion o a ay subsc ip s named Da a Access Ma ix and i s use as s a ing poin o ob ain he ans o ma ion ma ix. The da a access ma ix A is a n.n ma ix such ha he p oduc yields a ec o o n subsc ip s om a ay e e ences in he loop. The subsc ip s and he o de hey appea in A co espond o an es ima e o hei ela i e impo ance. Fo ins ance, [11] p opose an heu is ic ha gi es mo e impo ance o subsc ip s in he dis ibu ed dimensions o he a ays and, among hem, o hose ha appea mo e imes. I a da a access ma ix A has o be used as a ans o ma ion ma ix, wo condi ions ha e o be imposed: • ma ix A mus be in e ible. • ma ix A mus be legal, ha is, i mus no iola e dependences in he loop. J T I⋅= T d 0>⋅ A I⋅ 6 When ma ix A is no in e ible, linea ly dependen ows ha e o be elimina ed yielding a basis ma ix. This basis ma ix has o be legal so addi ional ows mus be dele ed i hey iola e dependences. Once a legal basis ma ix is ob ained, i is padded o an in e ible ma ix by adding ows which a e independen o he ows in he basis ma ix and which do no iola e dependence cons ain s. The ans o ma ion ma ix ob ained using his app oach e ains as many ows o he o iginal da a access ma ix as possible. Figu e 1 shows he example ha is used as wo king example along he pape . Figu e 1.b shows he o iginal IS and Figu e 1.c shows he a ge IS when he ollowing non-singula ans o ma ion ma ix is used Di e en shades a e used in he poin s o help he eade o es ablish he ela ionship be ween poin s in he o iginal and ans o med IS. This ans o ma ion ma ix co esponds o he da a access ma ix o he a ay subsc ip s in he dis ibu ed a ay dimensions shown in Figu e 1.a. 3.2 Code Gene a ion Once a legal ans o ma ion T has been de ined, we ha e o gene a e a loop nes ha app op ia ely scans he poin s in he a ge IS. In o de o do ha , we ha e o: •gene a e he bounds o he a ge DO loops and he s ide o each loop index in o de o skip o e poin s o he a ge IS ha do no ha e o be execu ed. As we ha e seen, he o iginal loop nes is de ined by . The e o e, i a ans o ma ion ma ix T is applied, he a ge IS can be ob ained om he in e se ma ix T-1 Howe e , he bounds ob ained by di ec elimina ion om he abo e inequali y migh no ha e he s uc u e assumed a he beginning o he p e ious sec ion. • eplace he subsc ip s in he a ay e e ences ha appea in he loop body such ha hey a e a ine unc ions o he new loop indices (i.e., subs i u e I wi h T-1.J in all subsc ip unc ions). Some p e ious wo ks [8, 9] ha e add essed he p oblem o code gene a ion when unimodula ma ices a e used o ans o m he o iginal IS. [22] includes condi ional s a emen s in o de o deal wi h he spa seness ha is in oduced in he a ge IS when a non-unimodula ma ix is used. O he au ho s [12, 13, 14] ha e made p oposals o a oid hese condi ionals and, as a consequence, educe he o e head in oduced by hem. The key poin in all o hem is he use o he Fou ie -Mo zkin elimina ion me hod and he He mi e No mal Fo m decomposi ion [23] o ob ain he a ge loop nes . Figu e 2.a summa izes he p ocedu e when he sou ce IS is dense and he ans o ma ion ma ix is unimodula . Wi h hese condi ions, he a ge IS is also dense. I he ans o ma ion ma ix is non-unimodula , hen a spa se IS is ob ained. Figu e 2.b shows he p ocedu e applied o ob ain he a ge code. The basic idea, as p oposed in [12] is o decompose he ma ix T in o he p oduc o a lowe iangula ma ix H wi h posi i e diagonal elemen s (He mi e ma ix o T) and a unimodula ma ix U ( e lec ing column ans o ma ions pe o med on T o ob ain H) such ha T1 2 1 0 = αI⋅ β≤ αT1– J⋅ ⋅ β≤ T H U⋅= 7 Applying U o he o iginal IS, and using Fou ie -Mo zkin elimina ion, he bounds o a dense auxilia y IS a e ob ained. Because o he spa seness o he a ge IS, wo hings ha e o be done: adjus loop bounds and skip o e poin s ha do no ha e o be execu ed. Ma ix H is used o ob ain he bounds o he spa se a ge loop nes by di ec elimina ion. The diagonal elemen s o ma ix H a e he s ides o each loop index a iable in he a ge loop nes . Figu e 1.d shows how he o iginal loop nes shown in Figu e 1.a is ans o med applying he p ocedu e ou lined in his sec ion. Figu e 2: T ans o ming a dense IS using Fou ie -Mo zkin elimina ion. (a) When a unimodula ma ix T is used and (b) when a non-unimodula ma ix T is used. 4 The Alignmen Componen Be o e p esen ing he gene al amewo k we p esen he unde lying idea in ou wo king example. Assume ha i e a ions o he ou e mos loop in Figu e 1.d a e dis ibu ed among P p ocesso s in such a way ha p ocesso p (p=1, 2, ..., P) is in ol ed in he execu ion o an i e a ion j1 i (j1-1) mod P = (p-1). Wi h his assignmen , he accesses o ma ices A and B a e local in he execu ion o s a emen S1 bu non-local in he execu ion o s a emen S2. Fo ins ance and assuming P=4, p ocesso p=1 execu es i e a ions j1=5, 9, ..., 25 and accesses A(5, j2), A(9, j2), ..., A(25, j2) B(4, j2), B(8, j2), ..., B(24, j2) in he execu ion o S1 which a e s o ed in i s local memo y and accesses A(6, j2), A(10, j2), ..., A(26, j2) B(5, j2), B(9, j2), ..., B(25, j2) in he execu ion o S2 which a e s o ed in he local memo y o p ocesso p=2. In ac , o make local he accesses o ma ices A and B in s a emen S2, we would ha e had o dis ibu e i e a ions in such a way ha j1 mod P = (p-1). In o de o make local all he accesses o A and B, i is necessa y o align he execu ion o s a emen s S1 and S2, as shown below. F-M dense a ge ISdense o iginal IS legal unimodula T (a) (b) densedense unimodula U spa se He mi e No mal Fo m H o iginal IS auxilia y IS a ge IS (poin s skipped) elimina ion F-M elimina ion di ec elimina ion 8 Conside ha each s a emen in he loop is ep esen ed wi h a hype plane in he SIS and ha we apply a di e en ans o ma ion o each s a emen in such a way ha he esul ing a ge IS is he one shown in Figu e 3. Di e en shades a e used o iden i y he di e en hype planes. I p ocesso p execu es i e a ions j1so ha (j1-1) mod P = (p-1), hen all he accesses o ma ices A and B a e local. Fo ins ance, p ocesso p=1 execu es j1=5, 9, ..., 25 and accesses A(5, j2), A(9, j2), ..., A(25, j2) B(4, j2), B(8, j2), ..., B(24, j2) in he execu ion o bo h S1 and S2. Figu e 3: Ta ge SIS assuming ha each s a emen o he loop is ans o med wi h a di e en ans o ma ion. Due o he alignmen o he hype planes, mos o he i e a ions in he a ge loop execu e bo h s a emen s bu o he s jus execu e one o hem. The new bounds o he a ge loop nes ha e o be he union o he bounds o each s a emen . The body has o include he app op ia e condi ional s a emen s o ensu e ha each s a emen is execu ed wi hin i s bounds. In his sec ion we gene alize he amewo k o linea ans o ma ions o include loop alignmen . Some addi ional aspec s ha e o be conside ed in he gene a ion o he a ge loop nes , such as he gene a ion o condi ional gua ds o p ese e he seman ics o he o iginal loop nes and he op imiza ion o hese condi ional gua ds o educe as much as possible he execu ion o e head in oduced. 1 2 3 4 5 6 11 12 13 14 15 16 j1 j2 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 7 8 9 10 27 28 0 s a emen S2 s a emen S1 9 4.1 Bounds o each s a emen We can conside ha he SIS is he composi ion o se e al hype planes, one o each s a emen in he loop body. Conside ha he hype plane associa ed o a s a emen Si is ans o med using he ollowing ans o ma ion whe e Di is he displacemen applied o he Si hype plane. No ice ha all he s a emen s a e ans o med using he same ans o ma ion ma ix T. Le T=H.U be he decomposi ion o ma ix T in o a unimodula ma ix U and he He mi e uppe iangula ma ix H. The e o e, he ans o med IS o s a emen Si is being Ki he auxilia y IS o he s a emen Si The bounds o he auxilia y space o s a emen Si can be de i ed om he bounds o he o iginal IS and using U-1, he in e se ma ix o he unimodula ans o ma ion, So he bounds o he auxilia y IS o Si can be ob ained applying he Fou ie -Mo zkin elimina ion me hod o o mo e clea ly o whe e Using he ma ix H, we can ob ain he bounds o he a ge IS o each s a emen Si by di ec elimina ion. Fo ins ance, conside ha we ans o m each s a emen hype plane in he wo king example in he ollowing way: The decomposi ion o T in he He mi e No mal Fo m is gi en by JiT I Di +     ⋅= JiH U I Di +     ⋅ ⋅ H Ki ⋅= = KiU I Di +     ⋅= αI⋅ β≤ I U 1– Ki ⋅Di –= αU1– Ki ⋅ ⋅     αDi ⋅     –β≤ α' Ki ⋅ βi ≤ α'αU1– ⋅= and βiβ α Di ⋅+= J1T I⋅= J2T I 1– 1 +       ⋅= T1 2 1 0 = H 1 0 1 2 = U 1 2 0 1– = 16 Figu e 8: (a) O iginal loop nes . Two di e en op ions o he alignmen componen s: (b) D1=[0, 0] and D2=[-1, 1] and (c) D1=D2=[0, 0] . We ha e used some ideas ecen ly published in he li e a u e o gene a e code ha con ols he co ec execu ion o each s a emen in each i e a ion o he ans o med loop nes and body. In his case i is mo e di icul o gene a e code and we ha e shown how o educe he o e head due o condi ionals ha appea in he loop body [24]. We ha e p esen ed a simple me hod o ob ain he alignmen componen o each s a emen o he loop body. I is based on he analysis o cons an s in he se o subsc ip s ha make up he da a access ma ix (in he spa ial pa o he ans o ma ion) and he alignmen unc ions o he a ays subsc ip ed by hem. Da a euse has no been conside ed in he me hod we ha e p oposed. A mo e p ecise o mula ion o he p oblem o inding he alignmen componen s whe e da a euse is conside ed is pa o ou u u e wo k. DO i1=1, 10 DO i2=1, 8 (a) A[i1+2.i2, i1] = (A[i1+2.i2, i1], B[i1+2.i2-1, i1], C[i1+1, i2]) B[i1+2.i2, i1] = g(A[i1+2.i2+1, i1], B[i1+2.i2-1, i1], C[i1+1, i2]) ENDO ENDO DO j1=3, 26 DO j2 = j1 + 2 .max (-8, (1-j1)/2), j1 + 2 .min (-1, (10-j1)/2), 2 A[ j1, j2] = (A[ j1, j2], B[ j1-1, j2], C[ j2+1, ( j1- j2)/2]) B[ j1, j2] = g(A[ j1+1, j2], B[ j1-1, j2],C[ j2+1, ( j1- j2)/2] ) ENDO ENDO (b) DO j1=2, 28 DO j2 = lco e,uco e, 2 A[ j1, j2] = (A[ j1, j2], B[ j1-1, j2], C[ j2+1, ( j1- j2)/2] ) B[ j1-1, j2+1] = g(A[ j1, j2+1], B[ j1-2, j2+1], C[ j2+2, ( j1- j2-2)/2]) ENDO ENDO (c) ... ... DISTRIBUTE E (CYCLIC, :) ALIGN B (i, j) WITH E (i+1, j-1) ALIGN A, C WITH E 17 A possible ex ension o he wo k p esen ed in his pape is he use o a di e en ans o ma ion o each s a emen . F om a ay e e ences in each loop s a emen , a di e en da a access ma ix o ans o ma ion ma ix T and alignmen componen can be ob ained o inc ease locali y. The a ge loop nes ob ained wi h his app oach has he same s uc u e as he one we ha e p esen ed in his pape . In gene al, he ans o med dependence dis ances become non-uni o m and as a consequence, i is mo e di icul o gene a e he associa ed synch oniza ion/communica ion ins uc ions. The s udy o he legali y o all he ans o ma ion ma ices is mo e complex because o his non-uni o m cha ac e is ic o dependences in he a ge space. Acknowledgmen s This wo k has been suppo ed by he Minis y o Educa ion o Spain unde con ac TIC-880/92, by he ESPRIT Basic Resea ch Ac ion 6634 APPARC and by he CEPBA (Eu opean Cen e o Pa allelism o Ba celona). Re e ences [1] Polych onopoulos C., Pa allel P og amming and Compile s, Kluwe Academic Publishe s, 1988. [2] Wol e M., Op imizing Supe compile s o Supe compu e s, The MIT P ess, 1989. [3] Fox G. e al., Fo an-D Language Speci ica ion, Technical Repo TR90-140, Dep . o Compu e Science, Rice Uni e si y, e ised Janua y 1992. [4] Da id Lo eman (ed.), D a High Pe o mance Fo an Language Speci ica ion Ve sion 1.0, Technical Repo TR92-225, CRPC, Rice Uni e si y, Janua y 1993. [5] Callahan D. and Kennedy K., Compiling P og ams o Dis ibu ed-Memo y Mul ip ocesso s, Jou nal o Supe compu ing, ol. 2, no. 2, Oc obe 1988. [6] Hi anandani S., Kennedy K. and Tseng C., E alua ion o Compile Op imiza ions o Fo an D on MIMD Dis ibu ed-Memo y Machines, in P oceedings o he 1992 ACM In e na ional Con e ence on Supe compu ing, July 1992. [7] Ka p A.H., P og amming o Pa allelism, Compu e , ol. 20, no. 5, May 1987. [8] Bane jee U., Unimodula T ans o ma ions o Double Loops, chap e 10 o Ad ances in Languages and Compile s o Pa allel P ocessing, The MIT P ess, 1991. [9] Wol M.E. and Lam M.S., A Loop T ans o ma ion Theo y and an Algo i hm o Maximize Pa allelism, IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, ol. 2, no. 4, Oc obe 1991. [10] Wol M.E. and Lam M., A Da a Locali y Op imizing Algo i hm, in P oceedings o he ACM SIGPLAN Con e ence on P og amming Language Design and Implemen a ion, June 1991. [11] Li W. and Pingali K., Access No maliza ion: Loop Res uc u ing o NUMA Compile s, in P oceedings o he Fi h In . Con e ence on A chi ec u al Suppo o P og amming Languages and Ope a ing Sys ems, Oc obe 1992. [12] Li W. and Pingali K., A Singula Loop T ans o ma ion F amewo k Based on Non-Singula Ma ices, in P oceedings o he Fi h Wo kshop on Languages and Compile s o Pa allel Compu e s, Augus 1992. [13] Fe nández A., Sys ema ic T ans o ma ion o Sys olic Algo i hms o P og amming Dis ibu ed Memo y Mul ip ocesso s, Ph.D. Thesis, Depa men o Compu e A chi ec u e, Poly echnic Uni e si y o Ca alunya (Spain), No embe 1992. [14] Ramanujam J., Non-unimodula T ans o ma ions o Nes ed Loops, in P oceedings o he Supe compu ing’92, No embe 1992. [15] Padua D.A., Mul ip ocesso s: Discussions o some heo e ical and p ac ical p oblems, Technical Repo DCS UIUCDCS-R-79-990, Ph.D. disse a ion, Uni e si y o Illinois a U bana-Champaign, No embe 1979. 18 [16] Pei J-K., P og am Pa i ioning and Synch oniza ion on Mul ip ocesso Sys ems, Ph.D. Thesis, Uni e si y o Illinois a U bana-Champaign, 1986. [17] Allen R., Callahan D. and Kennedy K., Au oma ic Decomposi ion o Scien i ic P og ams o Pa allel Execu ion, in P oceedings o he 14 h ACM Symposium P inciples o P og amming Languages, Janua y 1987. [18] Bane jee U., Dependence Analysis o Supe compu ing, Kluwe Academic Publishe s, 1988. [19] Kennedy K. and K eme U., Au oma ic Da a Alignmen and Dis ibu ion o Loosely Synch onous P oblems in an In e ac i e P og amming En i onmen , Technical Repo TR91-155, Dep . o Compu e Science, Rice Uni e si y, Ap il 1991. [20] Li J., Compiling C ys al o Dis ibu ed-Memo y Machines, Ph.D. Thesis, Dep. o Compu e Science, Yale Uni e si y, Decembe 1991. [21] Moldo an D.I. and Fo es J.A.B., Pa i ioning and Mapping Algo i hms in o Fixed Size Sys olic A ays, IEEE T ansac ions on Compu e s, ol. 35, no.1, Janua y 1986. [22] Lu L. and Chen M., New Loop T ans o ma ion Techniques o Massi e Pa allelism, Resea ch Repo TR-833, Depa men o Compu e Science, Yale Uni e si y, Oc obe 1990. [23] Sch ij e A., Theo y o Linea and In ege P og amming, John Wiley and Sons, 1986. [24] Ayguadé E. and To es J., Pa i ioning he S a emen pe I e a ion Space Using Non-singula Ma ices, in P oceedings o he 1993 ACM In e na ional Con e ence on Supe compu ing, July 1993.