Elektrotehniški vestnik 76(1-2): 13-18, 2009 Electrotechnical Review, Ljubljana, Slovenija
Ugotavljanje podatkovne odvisnosti za procesorje z naborom ukazov SIMD
Patricio Bulic, Tomaz Dobravec
Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Tržaška 25, 1000 Ljubljana, Slovenija
Povzetek. V tem članku predstavimo algoritem za ugotavljanje obstoja podatkovne odvisnosti pri vektorizaciji zank za CPE z naborom ukazov SIMD. Znano je, da lahko zaporedje ukazov, ki izvedejo enako operacijo nad sosednjimi operandi v pomnilniku, nadomestimo z enim samim ukazom SIMD, če med temi ukazi ni prave podatkovne odvisnosti, tj. odvisnosti tipa RAW. Vendar se izkaze, da lahko pravo podatkovno odvisnost ignoriramo, če je le razdalja med pomnilniskimi referencami, kijih beremo, in pomnilniškimi referencami, v katere pišemo, enaka ali vecja od dolzine registrov SIMD v CPE oz. od števila operandov, nad katerimi se naenkrat izvede operacija SIMD. Z ustrezno analizo linearnih izrazov, s katerimi naslavljamo pomnilniške lokacije, naš algoritem ugotavlja kolikšna je razdalja med pomnilniškimi referencami, ki nastopata v dveh potencialno podatkovno odvisnih ukazih. Na podlagi te razdalje predlagani postopek, ki temelji na preverjanju minimuma in maksimuma razdalje med odvisnima pomnilniškima referencama, daje zeleno luc za vektorizacijo zank med postopkom prevajanja. Predlagani postopek spada v skupino t.i. pribliznih algoritmov za ugotavljanje podatkovne odvisnosti, saj poskuša le dokazati, da odvisnosti ni. Izkaze se, daje predlagani postopek ucinkovitejši kot najpogosteje uporabljen priblizni Banerjeejev postopek in ga zato lahko nadomesti v hierarhicnem sistemu za ugotavljanje podatkovne odvisnosti.
Ključne besede: podatkovna odvisnost, multimedijske razširitve ISA, nabor ukazov SIMD, vektorizacija zank
Testing data dependency for microprocessors with a short SIMD instruction set
Extended abstract. In this paper we present an algorithm for the data-dependency problem related to microprocessors with a multimedia extension (i.e., including short SIMD instructions). Actually, there is a number of data-dependency tests proposed in literature (Banerjee test [2], GCD test [11], Omega test [7], Power test [10], etc.) which are all based on solving the linear dependence system. These tests would prohibit any vectoriza-tion if dependence exists even though this dependence would not be violeted after the vectorization. As an extension to the Baner-jee test, the presented method checks whether the vectorization affects any existing depenedence relation by checking the distance between two conflicting memory references. We assume a p-nested for loop. In short SIMD processing, we can process V data simultaneously and these data must be successively stored in the memory. All the data must be of the same bit length b and the SIMD registers must be Vl ■ b bits long. Thus, the problem of SIMD vectorization becomes a problem of whether we can unroll the innermost loop Vi times and substitute the simultaneous statements with a single SIMD statement that performs the same operation at a time, over Vl b-bits data in the (Vi ■ b)-bits SIMD register.
In this paper, we prove that the distance between the memory references in the innermost loop, which is defined as d(i , i ) =
the memory references in the innermost loop is greater than or equal to the number of data processed in the SIMD register (Vl),
' eip
—a'Z(i , i ) — |ap — a''|i' < 0
min —a'Z(i , i ) — la'p — a'|ip > Vj.
i' ,i''
As we compute only the bounds of an integer affine function, the presented method results in a greater accuracy and also in reduction of the time cost. This simple and efficient data-dependency testing method is suitable for the use in a dependence analyzer that is organized as a series of tests, progressively increasing in accuracy, as a one of the first used, simple and inexpensive tests.
Key words: data dependency, multimedia extensions, SIMD instructions, vectorizing compilers
1 Uvod
d(i , i ) = —a'Z(i , i ) — |ap — a'|i'p. SIMD vectorization can be performed iff the distance between
Prejet 24. september, 2008 Odobren 8. januar, 2009
Moderni splošnonamenski mikroprocesorji imajo poleg navadnega skalarnega nabora ukazov še t.i. nabor ukazov SIMD (Single Instruction Multiple Data) namenjen izvajanju operacij nad kratkimi vektorji oz. pakiranimi podatki. Ceprav izdelovalci mikroprocesorjev
i.e.

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, kijih podpirajo ti ukazi. S temi ukazi lahko izvedemo isto operacijo nad vec operandi hkrati. Operandi so praviloma 8-, 16-, 32-, ali 64-bitni in so shranjeni v registrih SIMD dolzine 128 bitov. Aritmeticno-logicni ukazi iz nabora ukazov SIMD ponavadi podpirajo preproste aritmeticno-logicne operacije (seštevanje, odštevanje, mnozenje, logicne operacije). Npr. z enim samim ukazom SIMD za seštevanje tako lahko sesštejemo dva vektorja, ki vsebujeta 16 8-bitnih komponent. Ukazi za prenos podatkov iz nabora ukazov SIMD praviloma prenašajo istolezne pomnilniške besede med pomnilnikom in registri SIMD v CPE in se od navadnih ukazov load/store razlikujejo le v dolzšini prenesene besede. Nabor ukazov SIMD je predvsem namenjen hitrejšemu izvajanju nekaterih vektorskih in matricnih operacij v digitalni obdelavi signalov, ki jih opisemo s programskimi zankami (npr. mnozenje matrik in vektorjev, mešanje slik, DCT, FIR filtri ipd.). Pohitritev izvajanja nasštetih operacij je posledica tega, da lahko z enim ukazom SIMD izvedemo isto operacijo nad vecš operandi ter daje treba manjkrat zajeti ukaze. Povedano drugace, programsko zanko, v kateri M-krat izvajamo isto operacijo, razvijemo N-krat ter N ukazov nadomestimo z enim samim ukazom SIMD. V praksi se izkazše, da deli programske kode, kijih lahko zapišemo z ukazi SIMD pomenijo manjsi delez v aplikacijah, zato je v praksi tipicna pohitritev izvajanja programov s temi ukazi okrog 30 odstotna.
Danes je zazšeljeno, da programe pisšemo v visokih programskih jezikih ter z uporabo t.i. vektorizirajocih prevajalnikov dosezšemo vektorizacijo zank z ukazi SIMD. To pomeni, da morajo prevajalniki analizirati programske zanke ter nacin dostopa do podatkov v njih. Prevajalniki morajo predvsem ugotoviti, ali sta morebiten razvoj zanke in zamenjava vrstnega reda izvajanja ukazov legalna. Odgovor na vprašanje legalnosti neke transformacije zank nam da t. i. analiza podatkovne odvisnosti.
Problem analize podatkovne odvisnosti v zankah, v katerih uporabljamo linearne reference na polja, se prevede na iskanje mnozice rešitev linearne enacbe z danimi omejitvami za posamezne spremenljivke. Ta problem je ekvivalenten problemu celosštevilskega linearnega programiranja in je torej NP-polen problem ([10]). Danes obstaja veliko metod za iskanje celosštevilskih resšitev sistema podatkovne odvisnosti ([10]). Razvrstimo jih v dve skupini. V prvi so t. i. približne, v drugi pa natančne metode. Znacilnost pribliznih testov je, da na dokaj preprost nacin poskušajo dokazati neobstoj podatkovne odvisnosti. (Če jim to ne uspe, konservativno sklepajo, da odvisnost obstaja. Najpogosteje uporabljena priblizna testa sta test Ba-nerjee in test GCD ([2], [11]). Odlikuje ju nizka racunska zahtevnost. Gre za konservativna testa, ki tedaj, ko ne moreta dokazati neodvisnosti, prepovedujeta nadaljnjo para-lelizacijo. Po drugi strani natancne metode poišcejo vse
resšitve linearne enacšbe in ugotovijo, kdaj in med katerimi iteracijami pride do podatkovne odvisnosti. V literaturi so predstavljeni tudi sštevilni natancšni testi. Med njimi se najvec uporablja test Omega ([7]). V najslabšem primeru je cšasovna zahtevnost tega testa eksponentna. Test zanesljivo ugotovi obstoj podatkovne odvisnosti.
V	praksi se izkazše, da so priblizšni testi izjemno ucšinkoviti, zato se prevajalniki analize podatkovne odvisnosti lotevajo hierarhicno: najprej s pribliznimi testi poskusšajo pokazati, da podatkovna odvisnost v zankah ne obstaja, in nato uporabijo natancšne metode za analizo zank, pri katerih priblizšni testi niso dali pozitivnega rezultata.
V	nadaljevanju bomo videli, da tedaj, ko skusšamo para-lelizirati programske zanke z naborom ukazov SIMD, dovolimo obstoj podatkovne odvisnosti med programskimi stavki, ki se ne bodo izvedli vzporedno, tj. kadar je razdalja med pomnilnisškimi referencami dovolj velika. To je v praksi pogosto, saj so registri SIMD relativno kratki, zato obstojecši priblizšni testi ne morejo dati zadovoljivega odgovora. V tem clanku predstavimo metodo, s katero pri pribliznih testih dodamo dolocene omejitve. Tako ucinkovito filtriramo in ignoriramo podatkovne odvisnosti, ki nam ne bodo preprecšile paralelizacije z ukazi SIMD.
2 Osnovni pojmi
V	tem razdelku bomo podali nekaj dobro znanih pojmov, ki bodo bralcu olajšali branje clanaka in razumevanje predstavljene metode.
Definicija: 1 (Ik, Ik). Naj bo p G N in Vk G {1,... ,p} naj velja lk,uk G 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 = 11 x I2 x ... X Ik
(1)
V nadaljevanju bomo p, k, uk, lk, Ik in Ik 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 spodaj:
Spremenljivka i G Ip naj pomeni vrednosti vseh zancnih indeksov (i1, i2,..., ip) v najbolj notranji zanki. Glavni cilj metode, ki jo bomo predstavili v clanku, 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 [t 1] [¿2 ] --. [tn], je v resnici dostop do neke pomnilniške lokacije. Naslov pomnilniške lokacije se izraza kot afina funkcija, kije podana v naslednjem izreku.
Izrek: 1 Naj bo A n-dimenzionalno polje, kjer so meje posameznih dimenzij L j, Uj G Z : L j < Uj za vse 1 < j < n in naj bo A0 naslov prvega elementa v polju. Naslov elementa A[t1][t2]... [tn] izrazimo z a fino funkcijo
f (ti,t2,...,tn) = Ao + J2 D j • tj,
j=i
(2)
kjerje
Dj
j=n
n (uk - Lk + 1)
k = j + 1
1 < j < (n - 1).
(3)
Dokaz najdemo v [11].
V nadaljevanju bomo zapis A(f (t1, t2,..., tn)) uporabljali za oznacevanje elementa A[t1][t2]...[tn]. Ponekod bomo uporabili obe notaciji, odvisno od konteksta. V nadaljevanju bomo predpostavljali, da so pri referenci na polje A v najbolj notranji zanki vsi izrazi tj afine funkcije zancnih indeksov i G Ip, tj. referenca na polje A bo
A[z1(i)][z2(i)] ... [zn(i)]
kjer so z1,... zn : Ip — Z afine funkcije.
(4)
Ip - z, g(i) = ]T
ak ik
k=1
sta
p
min(g(i)) = ^J a+lk - afc uk,
k=1
max(g(i)) = a+uk - afc lk,
k=1
kjerje
+
r r > 0	_	0 r > 0
in r = <
10 r < 0	I -r r < 0
za vsako celo število r.
3 Problem odvisnosti podatkov
Potreben pogoj za paralelizacijo zanke (oziroma za zapis vec zaporednih ukazov zanke z enim samim SIMD ukazom) je neodvisnost referenc na podatke istega polja. Ugotavljanje, ali se z dvema razlicnima referencama na polja istega polja lahko sklicujemo na isti element, se imenuje problem odvisnosti podatkovin je formalno definiran z naslednjo definicijo.
Definicija: 3 (Problem	odvisnosti
podatkov)	Naj bosta A(f (z1 (i), z2 (i),..., zn (i)))
in A(f (z" (i), z2'(i),..., zn(i))) dve referenci na isto polje A znotra p-gnezdene for zanke. Ce obstajata dva celoštevilska vektorja i', i'' G Ip, ki zadoščata enašbi,
f (z1 (i'), f (z1'(i"),
^2 (i'),
zn(i/)) = zn (i")),
(5)
potem pravimo, da sta referenci na polje A podatkovno odvisni.
V tem delu bomo predpostavili, da sta za vse j G {1,... n} funkciji zj(i) in zj'(i), uporabljeni v referencah opazovanega polja A, afini funkciji svojih argumentov. Upoštevajoc trditev (3), po kateri je tudi funkcija f afina funkcija svojih argumentov, lahko enacbo (5) preoblikujemo v
Predstavljena metoda ugotavljanja podatkovne odvisnosti bo, tako kot test Banerjee, temeljila na iskanju mejnih vrednosti celoštevilske afine funkcije. Mejne vrednosti linearne celosštevilske funkcije podaja naslednji izrek ([2], [11]):
Izrek: 2 Naj bo p G N in Vfc G {1,... ,p} naj velja lk, uk G Z, tako da lk < uk. Minimum in maksimum funkcije
+ +
1i1
1 i1
+ +
2i2
2 i2
+ +
+ +
aV
ap ip ,
(6)
kjer so
2<o, ao , a 1, a 1 , .. ., a p, a p G Z
izrazšeni iz celosštevilskih argumentov funkcij f in
z1, z1 , z2, z2 , . . . , zn, zn.
4 Ugotavljanje podatkovne odvisnosti
V nadaljevanju se bomo osredotocšili na p-gnezdeno zanko in iskali podatkovno odvisnost referenc na dano polje A. Predpostavili bomo, da so v polju A elementi istega tipa in da se referenci na elemente tega polja v dveh zaporednih 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
n
1
n
a
apip
o
a
o
g
Vb, z enim ukazom SIMD izvedemo operacijo nad V podatki dolžine b, le, Ce so ti podatki zaporedno shranjeni v pomnilniku. Vprašanje, s katerim se bomo ukvarjali v nadaljevanju Clanka, je, ali (oziroma, kdaj) lahko razvijemo Vi 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 mogoCe, in nikalno, kadar ni oziroma kadar zanesljivega odgovora ne poznamo. Naša metoda, ki upošteva dejstvo, da je za paralelizacijo z ukazi SIMD odlocšilnega pomena, da je razdalja med posameznimi referencami na polje v najbolj notranji zanki veCja ali kvečjemu enaka velikosti registra SIMD Vi dopolnjuje znani test Banerjee, ki o neodvisnosti podatkov presoja zgolj na podlagi ocene intervala, znotraj katerega se lahko giblje preiskovana referenca. Test z omenjeno dopolnitvijo razširja uporabnost in ucinkovitost Banerjeevega testa za SIMD prevajalnike. Pred predstavitvijo metode zapišimo še nekaj oznak in definicij.
Naj bosta i = (i1, i2,... ip) G Ip in i = (i1, i2 ,... ip) G Ip. Ce definiramo
z mejami lp < ip, ip < up predstavljen z enačbo
C (i', i" ) =
+ a1 i1 +
+ a.
,p-1ip-1
— an — a1i1 — ... — ap-1i
'p—1'p-1,
potem splošna enacba odvisnosti (6) postane
apip — apip = C(i , i ).
(7)
Razdaljo d(i , i ) med referencami na elemente polja v najbolj notranji zanki, kijev [11] definirana kot
d(i', i" ) = i"p — ip (8) lahko izrazimo iz (7) kot
d(i', i '')
= («p — 1)ip — (ap — 1)ip — C(i', O.
(9)
Paralelizacijo Banerjee lahko izvedemo, ce je razdalja med posameznimi referencami vecšja ali kvecšjemu enaka velikosti registra SIMD Vi (t.j. številu podatkov, nad katerimi bomo izvajali operacijo v enem ukazu SIMD) oziroma kadar velja:
d(i , i ) < 0 ali d(i , i ) > V
(10)
apip ap ip
C (i , i )• Ceje |ap| = |ap | = 1, potem je razdalja med referencami d(i , i ) enaka
d(i', i") = —apC (i', i") — |ap — ap'|ip. (11)
Dokaz: 1 Pokazali bomo, da je vrednost razdalje d(i , i ), izračunane po definiciji (9)
d(i', i) = («p — i)ip— («p' — i)ip— c (i', i).
in po formuli (11)
d(i', i ) = —a'"C(i', i ) — |ap — aP'|iP,
ki jo predlaga izrek, enaka v vseh (čtirih) primerih:
1 - Oip — Oip
1
po (9); d(i', i") = (1 — 1)i'p — (1 — 1)ip' —
C (i ', i ' ') = - C ( i ', i '')
po (11): d(i', i '') = — 1C(i ', i '') — |1 — 1|ip =
—C (i ', i '')-
za vse (i , i ) G Ip. Upoštevajoc dejstva, da se lahko indeks najbolj notranje for zanke spreminja le za ±1 in da smo se omejili na enotski korak (|ap| = |ap| = 1), lahko predstavimo izrek, na katerem temelji nasša metoda za ugotavljanje podatkovne odvisnosti.
Izrek: 3 Naj bo C : Ip x Ip ^ Z afina funkcija s celoštevllsklml koeficienti in naj bo problem odvisnosti podatkov v najbolj notranji zanki p-gnezdene for zanke
2.	ap = ap' = —1
•	po (9): d(i ', i ' ') = — 2ip + 2'' — C (i ', i ' ') =
2(ip' — ip)-C (i ', i ' ') = 2d(i ', i '') — C (i ', i '') ^ d = C(i ', i '')
•	po (11): d(i', i'') = —( — 1)C(i ', i'') — | — 1 —
( — 1)|ip = C (i', i")-
3.	ap = 1, ap' = — 1
•	po (9): d(i', i") = (1 — 1)ip — ( — 1 — 1)ip — C(i , i ) = 2ip C(i , i ). Po definiciji velja
C (i', i) = apip— «p ip = ip + v ^zato ip =
C (i ', i ' ' ) —ip in d(i ' ,i '') = 2ip' — ' (i ', i '') = 2C (i', i'')—2ip —C (i', i' ') = C (i ', i '') —2ip.
•	po (11): d(i' ,i '' ) = —( — 1)C(i',i'') — |1 —
( — 1)|ip = C (i', i")—2ip -
4.	ap = —1, ap = 1
•	po (9).• d(i', i'') = ( — 1 - 1)ip — (1 — 1)ip' —
C (i ', i ' ') = — 2ip — C (i ', i '')
•	po (11): d(i',i'') = — 1C(i', i'') — | — 1 —1|ip =
—2ip — C(i ', i '')-
Izrek 3 predstavlja preprosto in poceni metodo za ugotavljanje podatkovne odvisnosti za procesorje z ukazi SIMD: najbolj notranjo zanko p-gnezdene for zanke lahko razvijemo v zaporedje ukazov SIMD, ce velja ena od spodnjih neenakosti:
a
n
= ip ip =
max -a"Z(i, i) - K - a'P K < 0 (12)
i',i''eip
ali
min -aP Z (i , i ) - |aP - aP'|iP > V;. (13)
i',i''£/P ^	F	F F
Izrek 3 in neenacbi (12) ter (13) uporabimo v naslednjem algoritmu:
Algoritem: 1 Algoritem vrne TRUE, kadar so reference na elemente polja neodvisne, in FALSE, kadar podatkovna odvisnost morda obstaja.
1.	s pomočjo izreka 1 zapisi afini funkciji potencialno problematičnih (odvisnih) referenc na elemente polja znotraj najbolj notranje zanke,
2.	spomocjo izreka 3 izrazi funkcijo d(i', i''),
3.	s pomocjo izreka 2 poišči
m = mini',i"e/p d(i , i )
in
M = maxi',i»e/p d(i , i )
4.	ce ((M < 0) ali (m > Vi))
vrni TRUE; sicer
vrni FALSE.
T. Dobravec, P. Bulic 17 za vse j = 1, 2,... n. Po izreku 1 je
n
f (z!(i'),...,zn(i'))= Ao + £ Dj zj(i'),
j=1
in zato
f (Zi(i'), ... ,Zn(i')) =
n	p
= A0 + Dj (zj0 + «r) = j=1 r=l n	p n
= Ao +Dj zjo+Dj zjr )«r.
j = 1	r = 1 j=1
(15)
Podobno velja za a0' in ar'.
Afino funkcijo d(i , i ) zapišimo kot
p
d(i, i) = ¿o +dr«r+^0'+^ dr'«
r=1	r = 1
//
'r «r .
5 Tehnične podrobnosti algoritma
Naj bo A n-dimenzionalno polje z mejami za posamezno dimenzijo L j, Uj G Z : L j < Uj za vse 1 < j < n in naj A0 pomeni naslov prvega elementa tega polja. Kot neposredna posledica izreka 1 lahko koeficiente D j izracšunamo z
Dn=1;
for (i = n - 1; i >= 1; i--)
Di = Di+1 * (Ui+1 - Li+1 + 1);
Naj	bosta	A(f (z1(i), z£(i),..., <(i)))
in A(f (z1'(i), z^'(i),..., z'(i))) dve potencialno proble-maticšni (odvisni) referenci na elementa polja A znotraj p-gnezdene for zanke in naj bo
p
zj (i ' ) = zj 0 + 13 zj r «r
in
i/(• i/\ _ 11 . \ ' // ■//
zj (i ) = zj0 + 2-^ zjr «r ,
Po izreku (3) je d(i , i ) = -a^Z(i , i ) — |ap-ap|«p, zato so skoraj vsi koeficienti d(i , i ) produkt ustreznega koeficienta a ' (oziroma a '') v Z (i , i ) in ap (oziroma -ap). Izjema sta le koeficient dp, kije enak — |ap - ap|, in dp, ki je enak 0.
dr	= +a a — 1 ap ar	for all r	= 0, .	..p-	1
dp	= -|ap-	n 1 ap|			
dp	=0				
dr	= -a a — ap ar	for all r	= 0, .	..p-	1
(16)
Na koncu uporabimo se izrek (2) in izracunamo najmanjšo (m) in najvecjo (M) vrednost funkcije d(i , i ):
m = d0 + d0' + e+lk - ek uk
M = d0 + d0' + ^ e+uk - efc lk,
r=1
pri cemer je ek okrajšava za d'k + d'fc'.
p
6	Rezultati in sklep
V tem delu smo predstavili preprosto, a učinkovito metodo 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 - ce tako rešitev najdejo, metode predpostavijo podatkovno odvisnost (ceprav ta morda ne obstaja). Tak konservativen pristop je še posebno neucinkovit pri uporabi na procesorjih SIMD, saj so registri SIMD relativno kratki in omogocajo paralelizacijo marsikatere zanke, katere vektorizacija na tradicionalnih vektorskih procesorjih ni mogoca.
Metodo smo testirali na knjiznici LAPACK (BLAS) in na veliki mnozici sinteticnih testov. Skupno smo analizirali nekaj vec kot 3 x 108 zank z dostopom MIV (Multiple Index Variable) [1] do dvo-dimenzionalnih polj. Testiso pokazali, da predstavljena metoda odkrije med 1-2% vec podatkovno neodvisnih dostopov kot test Banerjee (višji procent izboljšanja smo dosegli pri vecjih poljih). Rezultati so primerljivi tudi z rezultati iz [8], kjer so ugotovili, da test Omega odkrije le 5% vec podatkovno neodvisnih dostopov kot test Banerjee, vendar na racun bi-stevno povecane racunske zahtevnosti. Kljub tem, daje casovna zahtevnost predlagane metode linearna, tj. enaka kot pri Banerjeejevem testu, dosezemo nezanemarljivo izboljšanje pri filtriranju podatkovnih odvisnosti, ki ne prepovedujejo vektorizacije SIMD.
Namesto iskanja celoštevilskih rešitev enacbe podatkovne odvisnosti naša metoda temelji na dolocanju najmanjše in najvecje razdalje med potencialno problematičnima referencama znotraj iteracijskega prostora. Tak pristop omogoca vecjo natancnost, hkrati paje metoda casovno nezahtevna, saj izracuna le meje celoštevilske afine funkcije. Metoda je primerna za uporabo v analizatorju odvisnosti, kije organiziran kot zaporedje testov z narašcajoco zanesljivostjo, kot eden prvih, preprostih in poceni testov.
7	Literatura
[1]	Allen R., Kennedy K. Optimizing Compilers for Modem 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 Multimedia Processors. International Journal of Parallel Programming. Vol. 28, No. 4, pp. 347-361, 2000.
[6]	Muchnick S. Advanced Compiler Design & Implementation . Morgan Kauffman Publishers, 1997.
[7]	Pough W. A Practical Algorithm for Exact Array Dependence Analysis. Communications of the ACM. Vol.35, No. 8, pp. 102-114, 1992.
[8]	Psarris K., Klappholz D., Kong X. An Experimental Evaluation 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 Parallel Programming. Vol. 28, No. 4, pp. 363-400, 2000.
[10]	Wolfe M.J., Tseng C.W. The Power Test for Data Dependence. 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 Company, 1990.
Patricio Bulic, diplomirani inZenir elektrotehnike, je doktoriral 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 racšunalnisške arhitekture, paralelno procesiranje ter nacšrtovanje digitalnih in vgrajenih sistemov.
Tomaž Dobravec, diplomiran matematik, je doktoriral leta 2004 na Fakulteti za racšunalnisštvo in informatiko v Ljubljani, kjer je trenutno tudi zaposlen. Raziskovalno se v okviru Laboratorija za algoritme in podatkovne strukture ukvarja z razvojem in analizo algoritmov, najvecš pozornosti pa namenja omrezšjem s simetricšno topologijo in zasšcšiti podatkov.