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.