1 Uvod
Moderni splošnonamenski mikroprocesorji imajo poleg
navadnega skalarnega nabora ukazov še t.i. nabor uka-
zov SIMD (Single Instruction Multiple Data) name-
njen izvajanju operacij nad kratkimi vektorji oz. pa-
kiranimi podatki. Čeprav izdelovalci mikroprocesorjev
14 Dobravec, Bulić
različno poimenujejo ta nabor ukazov (npr. Intel MMX/S-
SE/SSE2/SSE3, Motorola Altivec, SUN VIS), gre pri
vseh za tako rekoč enak nabor operacij, ki jih podpirajo
ti ukazi. S temi ukazi lahko izvedemo isto operacijo nad
več operandi hkrati. Operandi so praviloma 8-, 16-, 32-,
ali 64-bitni in so shranjeni v registrih SIMD dolžine 128
bitov. Aritmetično-logični ukazi iz nabora ukazov SIMD
ponavadi podpirajo preproste aritmetično-logične opera-
cije (seštevanje, odštevanje, množenje, logične operacije).
Npr. z enim samim ukazom SIMD za seštevanje tako
lahko seštejemo dva vektorja, ki vsebujeta 16 8-bitnih
komponent. Ukazi za prenos podatkov iz nabora ukazov
SIMD praviloma prenašajo istoležne pomnilniške besede
med pomnilnikom in registri SIMD v CPE in se od nava-
dnih ukazov load/store razlikujejo le v dolžini prenesene
besede. Nabor ukazov SIMD je predvsem namenjen hi-
trejšemu izvajanju nekaterih vektorskih in matričnih ope-
racij v digitalni obdelavi signalov, ki jih opišemo s pro-
gramskimi zankami (npr. množenje matrik in vektorjev,
mešanje slik, DCT, FIR filtri ipd.). Pohitritev izvajanja
naštetih operacij je posledica tega, da lahko z enim uka-
zom SIMD izvedemo isto operacijo nad več operandi ter
da je treba manjkrat zajeti ukaze. Povedano drugače, pro-
gramsko zanko, v kateri M-krat izvajamo isto operacijo,
razvijemo N-krat ter N ukazov nadomestimo z enim sa-
mim ukazom SIMD. V praksi se izkaže, da deli program-
ske kode, ki jih lahko zapišemo z ukazi SIMD pomenijo
manjši delež v aplikacijah, zato je v praksi tipična pohitri-
tev izvajanja programov s temi ukazi okrog 30 odstotna.
Danes je zaželjeno, da programe pišemo v visokih pro-
gramskih jezikih ter z uporabo t.i. vektorizirajočih pre-
vajalnikov dosežemo vektorizacijo zank z ukazi SIMD.
To pomeni, da morajo prevajalniki analizirati programske
zanke ter način dostopa do podatkov v njih. Prevajalniki
morajo predvsem ugotoviti, ali sta morebiten razvoj zanke
in zamenjava vrstnega reda izvajanja ukazov legalna. Od-
govor na vprašanje legalnosti neke transformacije zank
nam da t. i. analiza podatkovne odvisnosti.
Problem analize podatkovne odvisnosti v zankah, v kate-
rih uporabljamo linearne reference na polja, se prevede na
iskanje množice rešitev linearne enačbe z danimi omeji-
tvami za posamezne spremenljivke. Ta problem je ekvi-
valenten problemu celoštevilskega linearnega programi-
ranja in je torej NP-polen problem ([10]). Danes obstaja
veliko metod za iskanje celoštevilskih rešitev sistema po-
datkovne odvisnosti ([10]). Razvrstimo jih v dve skupini.
V prvi so t. i. približne, v drugi pa natančne metode.
Značilnost približnih testov je, da na dokaj preprost način
poskušajo dokazati neobstoj podatkovne odvisnosti. Če
jim to ne uspe, konservativno sklepajo, da odvisnost ob-
staja. Najpogosteje uporabljena približna testa sta test Ba-
nerjee in test GCD ([2], [11]). Odlikuje ju nizka računska
zahtevnost. Gre za konservativna testa, ki tedaj, ko ne mo-
reta dokazati neodvisnosti, prepovedujeta nadaljnjo para-
lelizacijo. Po drugi strani natančne metode poiščejo vse
rešitve linearne enačbe in ugotovijo, kdaj in med katerimi
iteracijami pride do podatkovne odvisnosti. V literaturi
so predstavljeni tudi številni natančni testi. Med njimi se
največ uporablja test Omega ([7]). V najslabšem primeru
je časovna zahtevnost tega testa eksponentna. Test zane-
sljivo ugotovi obstoj podatkovne odvisnosti.
V praksi se izkaže, da so približni testi izjemno
učinkoviti, zato se prevajalniki analize podatkovne od-
visnosti lotevajo hierarhično: najprej s približnimi testi
poskušajo pokazati, da podatkovna odvisnost v zankah
ne obstaja, in nato uporabijo natančne metode za analizo
zank, pri katerih približni testi niso dali pozitivnega rezul-
tata.
V nadaljevanju bomo videli, da tedaj, ko skušamo para-
lelizirati programske zanke z naborom ukazov SIMD, do-
volimo obstoj podatkovne odvisnosti med programskimi
stavki, ki se ne bodo izvedli vzporedno, tj. kadar je
razdalja med pomnilniškimi referencami dovolj velika.
To je v praksi pogosto, saj so registri SIMD relativno
kratki, zato obstoječi približni testi ne morejo dati zado-
voljivega odgovora. V tem članku predstavimo metodo,
s katero pri približnih testih dodamo določene omejitve.
Tako učinkovito filtriramo in ignoriramo podatkovne od-
visnosti, ki nam ne bodo preprečile paralelizacije z ukazi
SIMD.
2 Osnovni pojmi
V tem razdelku bomo podali nekaj dobro znanih poj-
mov, ki bodo bralcu olajšali branje članaka in razume-
vanje predstavljene metode.
Definicija: 1 (Ik, Ik). Naj bo p ∈ N in ∀k ∈ {1, . . . , p}
naj velja lk, uk ∈ Z tako, da lk < uk. Množico celih
števil med lk in uk imenujemo interval Ik = [lk . . . uk].
Kartezični produkt prvih k intervalov je
Ik = I1 × I2 × . . . × Ik. (1)
V nadaljevanju bomo p, k, uk, lk, Ik in I
k uporabljali, kot
je definirano v definiciji 1.
Definicija: 2 (p-gnezdena for zanka). p-gnezdena for
zanka je gnezdo p for zank, kot je prikazano spo-
daj:
1 for (i1=l1; i1<=u1; i1++) {
2 for (i2=l2; i2<=u2; i2++) {
3 ...
4 for (ip=lp; ip<=up; ip++) {
5 stavki;
6 }
7 ...
8 }
9 }
T. Dobravec, P. Bulić 15
Spremenljivka i ∈ Ip naj pomeni vrednosti vseh zančnih
indeksov (i1, i2, . . . , ip) v najbolj notranji zanki. Glavni
cilj metode, ki jo bomo predstavili v članku, je, da
identificiramo morebitne podatkovne odvisnosti med po-
mnilniškimi referencami v najbolj notranji zanki p-
gnezdene for zanke. Vsak dostop do elementov nekega
n-dimenzionalnega polja A, ki ga v visokih programskih
jezikih ponavadi označimo z A[t1][t2]...[tn], je v resnici
dostop do neke pomnilniške lokacije. Naslov pomnilniške
lokacije se izraža kot afina funkcija, ki je podana v nasle-
dnjem izreku.
Izrek: 1 Naj bo A n-dimenzionalno polje, kjer so meje
posameznih dimenzij Lj , Uj ∈ Z : Lj ≤ Uj za vse
1 ≤ j ≤ n in naj bo A0 naslov prvega elementa v polju.
Naslov elementa A[t1][t2]...[tn] izrazimo z afino funkcijo
f(t1, t2, . . . , tn) = A0 +
n
∑
j=1
Dj · tj , (2)
kjer je
Dj =







1 ; j = n
n
∏
k=j+1
(Uk − Lk + 1) ; 1 ≤ j ≤ (n − 1).
(3)
Dokaz najdemo v [11].
V nadaljevanju bomo zapis A(f(t1, t2, . . . , tn)) upora-
bljali za označevanje elementa A[t1][t2]...[tn]. Ponekod
bomo uporabili obe notaciji, odvisno od konteksta. V na-
daljevanju bomo predpostavljali, da so pri referenci na po-
lje A v najbolj notranji zanki vsi izrazi tj afine funkcije
zančnih indeksov i ∈ Ip, tj. referenca na polje A bo
A[z1(i)][z2(i)] . . . [zn(i)] (4)
kjer so z1, . . . zn : I
p 7→ Z afine funkcije.
Predstavljena metoda ugotavljanja podatkovne
odvisnosti bo, tako kot test Banerjee, temeljila na iska-
nju mejnih vrednosti celoštevilske afine funkcije. Mejne
vrednosti linearne celoštevilske funkcije podaja naslednji
izrek ([2], [11]):
Izrek: 2 Naj bo p ∈ N in ∀k ∈ {1, . . . , p} naj velja
lk, uk ∈ Z, tako da lk < uk. Minimum in maksimum
funkcije
g : Ip 7→ Z, g(i) =
p
∑
k=1
akik
sta
min(g(i)) =
p
∑
k=1
a
+
k
lk − a
−
k
uk,
max(g(i)) =
p
∑
k=1
a
+
k
uk − a
−
k
lk,
kjer je
r+ =
{
r r > 0
0 r ≤ 0
in r− =
{
0 r ≥ 0
−r r < 0
za vsako celo število r.
3 Problem odvisnosti podatkov
Potreben pogoj za paralelizacijo zanke (oziroma za za-
pis več zaporednih ukazov zanke z enim samim SIMD
ukazom) je neodvisnost referenc na podatke istega polja.
Ugotavljanje, ali se z dvema različnima referencama na
polja istega polja lahko sklicujemo na isti element, se ime-
nuje problem odvisnosti podatkov in je formalno definiran
z naslednjo definicijo.
Definicija: 3 (Problem odvisnosti
podatkov) Naj bosta A(f(z′
1
(i), z′
2
(i), . . . , z′n(i)))
in A(f(z′′
1
(i), z′′
2
(i), . . . , z′′n(i))) dve referenci na isto po-
lje A znotra p-gnezdene for zanke. Če obstajata dva
celoštevilska vektorja i′, i′′ ∈ Ip, ki zadoščata enačbi,
f(z′
1
(i′), z′
2
(i′), . . . , z′n(i
′)) =
f(z′′
1
(i′′), z′′
2
(i′′), . . . , z′′n(i
′′)),
(5)
potem pravimo, da sta referenci na polje A podatkovno
odvisni.
V tem delu bomo predpostavili, da sta za vse j ∈
{1, . . . n} funkciji z′j(i) in z
′′
j (i), uporabljeni v referen-
cah opazovanega polja A, afini funkciji svojih argumen-
tov. Upoštevajoč trditev (3), po kateri je tudi funkcija f
afina funkcija svojih argumentov, lahko enačbo (5) preo-
blikujemo v
a′
0
+ a′
1
i′
1
+ a′
2
i′
2
+ . . . + a′pi
′
p =
a′′
0
+ a′′
1
i′′
1
+ a′′
2
i′′
2
+ . . . + a′′pi
′′
p ,
(6)
kjer so
a′
0
, a′′
0
, a′
1
, a′′
1
, . . . , a′p, a
′′
p ∈ Z
izraženi iz celoštevilskih argumentov funkcij f in
z′
1
, z′′
1
, z′
2
, z′′
2
, . . . , z′n, z
′′
n.
4 Ugotavljanje podatkovne odvisnosti
V nadaljevanju se bomo osredotočili na p-gnezdeno
zanko in iskali podatkovno odvisnost referenc na dano po-
lje A. Predpostavili bomo, da so v polju A elementi istega
tipa in da se referenci na elemente tega polja v dveh zapo-
rednih iteracijah najbolj notranje zanke razlikujeta za 1 ali
-1 (enotski korak). Te predpostavke izvirajo iz dejstva, da
lahko tedaj, ko razpolagamo z registrom SIMD velikosti
16 Dobravec, Bulić
Vlb, z enim ukazom SIMD izvedemo operacijo nad Vl po-
datki dolžine b, le, če so ti podatki zaporedno shranjeni v
pomnilniku. Vprašanje, s katerim se bomo ukvarjali v na-
daljevanju članka, je, ali (oziroma, kdaj) lahko razvijemo
Vl korakov najbolj notranje zanke in jih zamenjamo z
enim samim ukazom SIMD. Predstavili bomo metodo, ki
analiziran podatkovno odvisnost referenc na dano polje in
odgovori na zgornje vprašanje – pritrdilno, kadar je tako
razvitje mogoče, in nikalno, kadar ni oziroma kadar zane-
sljivega odgovora ne poznamo. Naša metoda, ki upošteva
dejstvo, da je za paralelizacijo z ukazi SIMD odločilnega
pomena, da je razdalja med posameznimi referencami na
polje v najbolj notranji zanki večja ali kvečjemu enaka
velikosti registra SIMD Vl dopolnjuje znani test Banerjee,
ki o neodvisnosti podatkov presoja zgolj na podlagi ocene
intervala, znotraj katerega se lahko giblje preiskovana re-
ferenca. Test z omenjeno dopolnitvijo razširja uporabnost
in učinkovitost Banerjeevega testa za SIMD prevajalnike.
Pred predstavitvijo metode zapišimo še nekaj oznak in de-
finicij.
Naj bosta i
′
= (i
′
1
, i
′
2
, . . . i
′
p) ∈ I
p in i
′′
=
(i
′′
1
, i
′′
2
, . . . i
′′
p ) ∈ I
p. Če definiramo
ζ(i
′
, i
′′
) = a′′
0
+ a
′′
1
i
′′
1
+ . . . + a
′′
p−1i
′′
p−1
− a′
0
− a
′
1
i
′
1
− . . . − a
′
p−1i
′
p−1,
potem splošna enačba odvisnosti (6) postane
a
′
pi
′
p − a
′′
p i
′′
p = ζ(i
′
, i
′′
). (7)
Razdaljo d(i
′
, i
′′
) med referencami na elemente polja v
najbolj notranji zanki, ki je v [11] definirana kot
d(i
′
, i
′′
) = i
′′
p − i
′
p (8)
lahko izrazimo iz (7) kot
d(i
′
, i
′′
) = i
′′
p − i
′
p =
= (a
′
p − 1)i
′
p − (a
′′
p − 1)i
′′
p − ζ(i
′
, i
′′
).
(9)
Paralelizacijo Banerjee lahko izvedemo, če je razdalja
med posameznimi referencami večja ali kvečjemu enaka
velikosti registra SIMD Vl (t.j. številu podatkov, nad ka-
terimi bomo izvajali operacijo v enem ukazu SIMD) ozi-
roma kadar velja:
d(i
′
, i
′′
) ≤ 0 ali d(i
′
, i
′′
) ≥ Vl (10)
za vse (i
′
, i
′′
) ∈ Ip. Upoštevajoč dejstva, da se lahko
indeks najbolj notranje for zanke spreminja le za ±1 in
da smo se omejili na enotski korak (|a
′
p| = |a
′′
p | = 1),
lahko predstavimo izrek, na katerem temelji naša metoda
za ugotavljanje podatkovne odvisnosti.
Izrek: 3 Naj bo ζ : Ip × Ip 7→ Z afina funkcija s
celoštevilskimi koeficienti in naj bo problem odvisnosti
podatkov v najbolj notranji zanki p-gnezdene for zanke
z mejami lp ≤ i
′
p, i
′′
p ≤ up predstavljen z enačbo
a
′
pi
′
p − a
′′
p i
′′
p = ζ(i
′
, i
′′
). Če je |a
′
p| = |a
′′
p | = 1, potem je
razdalja med referencami d(i
′
, i
′′
) enaka
d(i
′
, i
′′
) = −a′′pζ(i
′
, i
′′
) − |a′p − a
′′
p |i
′
p. (11)
Dokaz: 1 Pokazali bomo, da je vrednost razdalje
d(i
′
, i
′′
), izračunane po definiciji (9)
d(i
′
, i
′′
) = (a
′
p − 1)i
′
p − (a
′′
p − 1)i
′′
p − ζ(i
′
, i
′′
).
in po formuli (11)
d(i
′
, i
′′
) = −a′′pζ(i
′
, i
′′
) − |a′p − a
′′
p |i
′
p,
ki jo predlaga izrek, enaka v vseh (štirih) primerih:
1. a′p = a
′′
p = 1
• po (9): d(i
′
, i
′′
) = (1 − 1)i′p − (1 − 1)i′′p −
ζ(i
′
, i
′′
) = −ζ(i
′
, i
′′
)
• po (11): d(i
′
, i
′′
) = −1ζ(i
′
, i
′′
) − |1 − 1|i′p =
−ζ(i
′
, i
′′
).
2. a′p = a
′′
p = −1
• po (9): d(i
′
, i
′′
) = −2i′p + 2i
′′
p − ζ(i
′
, i
′′
) =
2(i′′p −i
′
p)−ζ(i
′
, i
′′
) = 2d(i
′
, i
′′
)−ζ(i
′
, i
′′
) ⇒
d = ζ(i
′
, i
′′
)
• po (11): d(i
′
, i
′′
) = −(−1)ζ(i
′
, i
′′
) − | − 1 −
(−1)|i′p = ζ(i
′
, i
′′
).
3. a′p = 1, a
′′
p = −1
• po (9): d(i
′
, i
′′
) = (1− 1)i
′
p − (−1− 1)i
′′
p −
ζ(i
′
, i
′′
) = 2i
′′
p − ζ(i
′
, i
′′
). Po definiciji velja
ζ(i
′
, i
′′
) = a
′
pi
′
p − a
′′
p i
′′
p = i
′
p + i
′′
p
′′ , zato i′′p =
ζ(i
′
, i
′′
) − i′p in d(i
′
, i
′′
) = 2i′′p − ζ(i
′
, i
′′
) =
2ζ(i
′
, i
′′
) − 2i′p − ζ(i
′
, i
′′
) = ζ(i
′
, i
′′
) − 2i′p.
• po (11): d(i
′
, i
′′
) = −(−1)ζ(i
′
, i
′′
) − |1 −
(−1)|i′p = ζ(i
′
, i
′′
) − 2i′p.
4. a′p = −1, a
′′
p = 1
• po (9): d(i
′
, i
′′
) = (−1 − 1)i′p − (1 − 1)i
′′
p −
ζ(i
′
, i
′′
) = −2i′p − ζ(i
′
, i
′′
)
• po (11): d(i
′
, i
′′
) = −1ζ(i
′
, i
′′
)−|−1−1|i′p =
−2i′p − ζ(i
′
, i
′′
).
�
Izrek 3 predstavlja preprosto in poceni metodo za ugo-
tavljanje podatkovne odvisnosti za procesorje z ukazi
SIMD: najbolj notranjo zanko p-gnezdene for zanke
lahko razvijemo v zaporedje ukazov SIMD, če velja ena
od spodnjih neenakosti:
T. Dobravec, P. Bulić 17
max
i′,i′′∈Ip
−a′′pζ(i
′
, i
′′
) − |a′p − a
′′
p |i
′
p ≤ 0 (12)
ali
min
i′,i′′∈Ip
−a′′pζ(i
′
, i
′′
) − |a′p − a
′′
p |i
′
p ≥ Vl. (13)
Izrek 3 in neenačbi (12) ter (13) uporabimo v naslednjem
algoritmu:
Algoritem: 1 Algoritem vrne TRUE, kadar so reference
na elemente polja neodvisne, in FALSE, kadar podat-
kovna odvisnost morda obstaja.
1. s pomočjo izreka 1 zapiši afini funkciji potencialno
problematičnih (odvisnih) referenc na elemente po-
lja znotraj najbolj notranje zanke,
2. s pomočjo izreka 3 izrazi funkcijo d(i′, i′′),
3. s pomočjo izreka 2 poišči
m = mini′,i′′∈Ip d(i
′
, i
′′
)
in
M = maxi′,i′′∈Ip d(i
′
, i
′′
)
4. če ((M ≤ 0) ali (m ≥ Vl))
vrni TRUE;
sicer
vrni FALSE.
5 Tehnične podrobnosti algoritma
Naj bo A n-dimenzionalno polje z mejami za posamezno
dimenzijo Lj , Uj ∈ Z : Lj ≤ Uj za vse 1 ≤ j ≤ n
in naj A0 pomeni naslov prvega elementa tega polja.
Kot neposredna posledica izreka 1 lahko koeficiente Dj
izračunamo z
Dn=1;
for (i = n − 1; i >= 1; i −−)
Di = Di+1 ∗ (Ui+1 − Li+1 + 1);
(14)
Naj bosta A(f(z′
1
(i), z′
2
(i), . . . , z′n(i)))
in A(f(z′′
1
(i), z′′
2
(i), . . . , z′′n(i))) dve potencialno proble-
matični (odvisni) referenci na elementa polja A znotraj
p-gnezdene for zanke in naj bo
z′j(i
′) = z′j0 +
p
∑
r=1
z′jri
′
r
in
z′′j (i
′′) = z′′j0 +
p
∑
r=1
z′′jri
′′
r ,
za vse j = 1, 2, . . . n. Po izreku 1 je
f(z1(i
′), . . . , zn(i
′)) = A0 +
n
∑
j=1
Djz
′
j(i
′),
in zato
f(z1(i
′), . . . , zn(i
′)) =
= A0 +
n
∑
j=1
Dj(zj0 +
p
∑
r=1
z′jri
′
r) =
= A0 +
n
∑
j=1
Djz
′
j0 +
p
∑
r=1
(
n
∑
j=1
Djz
′
jr)i
′
r.
a′
0
= A0 +
n
∑
j=1
Djz
′
j0
a′r =
n
∑
j=1
Djz
′
jr za vse r = 1, . . . p
(15)
Podobno velja za a′′
0
in a′′r .
Afino funkcijo d(i
′
, i
′′
) zapišimo kot
d(i
′
, i
′′
) = d′
0
+
p
∑
r=1
d′ri
′
r + d
′′
0
+
p
∑
r=1
d′′r i
′′
r .
Po izreku (3) je d(i
′
, i
′′
) = −a′′pζ(i
′
, i
′′
)−|a′p−a
′′
p |i
′
p, zato
so skoraj vsi koeficienti d(i
′
, i
′′
) produkt ustreznega koe-
ficienta a′ (oziroma a′′) v ζ(i
′
, i
′′
) in a′′p (oziroma −a
′′
p).
Izjema sta le koeficient d′p, ki je enak −|a
′
p − a
′′
p |, in d
′′
p ,
ki je enak 0.
d′r = +a
′′
pa
′
r for all r = 0, . . . p − 1
d′p = −|a
′
p − a
′′
p |
d′′p = 0
d′′r = −a
′′
pa
′′
r for all r = 0, . . . p − 1
(16)
Na koncu uporabimo še izrek (2) in izračunamo naj-
manjšo (m) in največjo (M ) vrednost funkcije d(i
′
, i
′′
):
m = d′
0
+ d′′
0
+
p
∑
k=1
e
+
k
lk − e
−
k
uk
M = d′
0
+ d′′
0
+
p
∑
k=1
e
+
k
uk − e
−
k
lk,
(17)
pri čemer je ek okrajšava za d
′
k
+ d′′
k
.
6 Rezultati in sklep
V tem delu smo predstavili preprosto, a učinkovito me-
todo za ugotavljanje podatkovne neodvisnosti referenc na
elemente polja znotraj vgnezdene for zanke. Metoda se
lahko uporablja kot pripomoček za paralelizacijo kode na
procesorjih SIMD.
Znane metode za ugotavljanje neodvisnosti temeljijo na
iskanju celoštevilskih rešitev enačbe, ki opisuje problem
odvisnosti – če tako rešitev najdejo, metode predpostavijo
podatkovno odvisnost (čeprav ta morda ne obstaja). Tak
konservativen pristop je še posebno neučinkovit pri upo-
rabi na procesorjih SIMD, saj so registri SIMD relativno
kratki in omogočajo paralelizacijo marsikatere zanke, ka-
tere vektorizacija na tradicionalnih vektorskih procesorjih
ni mogoča.
Metodo smo testirali na knjižnici LAPACK (BLAS) in na
veliki množici sintetičnih testov. Skupno smo analizirali
nekaj več kot 3 × 108 zank z dostopom MIV (Multiple
Index Variable) [1] do dvo-dimenzionalnih polj. Testi so
pokazali, da predstavljena metoda odkrije med 1-2% več
podatkovno neodvisnih dostopov kot test Banerjee (višji
procent izboljšanja smo dosegli pri večjih poljih). Re-
zultati so primerljivi tudi z rezultati iz [8], kjer so ugo-
tovili, da test Omega odkrije le 5% več podatkovno ne-
odvisnih dostopov kot test Banerjee, vendar na račun bi-
stevno povečane računske zahtevnosti. Kljub tem, da je
časovna zahtevnost predlagane metode linearna, tj. enaka
kot pri Banerjeejevem testu, dosežemo nezanemarljivo iz-
boljšanje pri filtriranju podatkovnih odvisnosti, ki ne pre-
povedujejo vektorizacije SIMD.
Namesto iskanja celoštevilskih rešitev enačbe podatkovne
odvisnosti naša metoda temelji na določanju najmanjše
in največje razdalje med potencialno problematičnima
referencama znotraj iteracijskega prostora. Tak pristop
omogoča večjo natančnost, hkrati pa je metoda časovno
nezahtevna, saj izračuna le meje celoštevilske afine funk-
cije. Metoda je primerna za uporabo v analizatorju odvi-
snosti, ki je organiziran kot zaporedje testov z naraščajočo
zanesljivostjo, kot eden prvih, preprostih in poceni testov.
7 Literatura
[1] Allen R., Kennedy K. Optimizing Compilers for Modern
Architectures: A Dependence-based Approach. Morgan
Kaufmann Publishers Inc., 2001.
[2] Banerjee U. Dependence Analysis: A Book Series
on Loop Transformations for Restructuring Compilers.
Kluwer Academic Publishers, Dordrecht, 1997.
[3] Bik A.J.C., Girkar M., Grey P.M., Tian X.M. Automatic
Intra-Register Vectorization for the Intel (R) Architecture.
International Journal of Parallel Programming. Vol 30.,
No. 2, pp. 65-98. 2002.
[4] Huang T.C., Yang C.M. Data Dependence Analysis for
Array References. The Journal of Systems and Software.
No. 52, pp. 55-65, 2000.
[5] Krall A., Lelait S. Compilation Techniques for Multi-
media Processors. International Journal of Parallel Pro-
gramming. Vol. 28, No. 4, pp. 347-361, 2000.
[6] Muchnick S. Advanced Compiler Design & Implementa-
tion . Morgan Kauffman Publishers, 1997.
[7] Pough W. A Practical Algorithm for Exact Array Depen-
dence Analysis. Communications of the ACM. Vol. 35,
No. 8, pp. 102-114, 1992.
[8] Psarris K., Klappholz D., Kong X. An Experimental Eva-
luation of Data Dependence Analysis Techniques IEEE
Transactions on Parallel and Distributed Systems. Vol.
15, No. 3, pp. 196-213, March 2004.
[9] Sreraman N., Govindarajan R. A Vectorizing Compiler
for Multimedia Extensions. International Journal of Pa-
rallel Programming. Vol. 28, No. 4, pp. 363-400, 2000.
[10] Wolfe M.J., Tseng C.W. The Power Test for Data De-
pendence. IEEE Transactions on Parallel and Distributed
Systems. Vol. 3, No. 5, pp. 591-601, September 1992.
[11] Zima H.P., Chapman B.M. Supercompilers for Parallel
and Vector Computers. Addison-Wesley Publishing Com-
pany, 1990.
Patricio Bulić, diplomirani inženir elektrotehnike, je dokto-
riral leta 2004 na Fakulteti za računalništvo in informatiko v
Ljubljani, kjer je trenutno zaposlen. Je član Laboratorija za
računalniško arhitekturo. Njegovo raziskovalno delo obsega
računalniške arhitekture, paralelno procesiranje ter načrtovanje
digitalnih in vgrajenih sistemov.
Tomaž Dobravec, diplomiran matematik, je doktoriral leta
2004 na Fakulteti za računalništvo in informatiko v Ljubljani,
kjer je trenutno tudi zaposlen. Raziskovalno se v okviru Labo-
ratorija za algoritme in podatkovne strukture ukvarja z razvojem
in analizo algoritmov, največ pozornosti pa namenja omrežjem
s simetrično topologijo in zaščiti podatkov.
T. Dobravec, P. Bulić : Učinkovita metoda ugotavljanja podatkovne odvisnosti med stavki z zadostno razdaljo med pomnilniškimi referencami