XOR csere algoritmus

A számítógép-programozásban a kizáró VAGY csere ('XOR swap) egy olyan algoritmus, amely a kizáró vagy (XOR(wd)) bitműveletet használja két változó értékének felcserélésére anélkül, hogy az általában szükséges ideiglenes változót használná.

Az algoritmus elsősorban újdonság, és a kizáró vagy (exclusive OR, vagy XOR) művelet tulajdonságainak bemutatására szolgál. Néha programoptimalizálásként is emlegetik, de szinte nincs olyan eset, amikor a kizáró vagy művelettel végrehajtott csere előnyt biztosítana a standard, nyilvánvaló technikával szemben.

Az algoritmus

A hagyományos csere egy ideiglenes tárolási változó használatát igényli. Az XOR cserealgoritmus használatával azonban nincs szükség ideiglenes tárolásra. Az algoritmus a következő:^[1]^[2]

X := Y XOR X; // XOR műveletet alkalmaz az értékekre, és az eredményt X-ben tárolja
Y := X XOR Y; // XOR műveletet alkalmaz az értékekre, és az eredményt Y-ban tárolja
X := Y XOR X; // XOR műveletet alkalmaz az értékekre, és az eredményt X-ben tárolja

Mivel az XOR egy kommutatív művelet, az X XOR Y vagy az Y XOR X felcserélhetően használható az előző három sorban. Megjegyzendő, hogy egyes architektúrákon az XOR utasítás első operandusa meghatározza a művelet eredményének tárolási célhelyét, megakadályozva ezt a felcserélhetőséget. Az algoritmus jellemzően három gépi kódú utasításnak felel meg, amelyeket a következő táblázat három sorában található megfelelő pszeudokód és assembly utasítások képviselnek:

Pszeudokód	IBM System/370 assembly	x86 assembly	RISC-V assembly
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`	`xor x10, x11`
`Y := Y XOR X`	`XR R2,R1`	`xor ebx, eax`	`xor x11, x10`
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`	`xor x10, x11`

A fenti System/370 assembly kódmintában az R1 és R2 különálló regiszterek, és minden XR művelet az első argumentumban megnevezett regiszterben hagyja az eredményét. x86 assembly használatával az X és Y értékek az eax és ebx regiszterekben találhatók (rendre), az xor pedig a művelet eredményét az első regiszterbe helyezi. A RISC-V assemblyben az X és Y értékek az X10 és X11 regiszterekben találhatók, az xor pedig a művelet eredményét az első regiszterbe helyezi (ugyanúgy, mint az x86).

A pszeudokódban vagy a magas szintű nyelvi verzióban vagy implementációban azonban az algoritmus kudarcot vall, ha x és y ugyanazt a tárolási helyet használja, mivel az adott helyen tárolt értéket az első XOR utasítás lenullázza, majd nulla marad; nem „cserélődik önmagával”. Ez nem ugyanaz, mintha x és y értékei megegyeznének. A probléma csak akkor jelentkezik, ha x és y ugyanazt a tárolási helyet használja, ebben az esetben az értéküknek már eleve egyenlőnek kell lennie. Vagyis, ha x és y ugyanazt a tárolási helyet használja, akkor a sor:

X := X XOR Y

nullára állítja x-et (mivel x = y, tehát X XOR Y nulla), és y-t is nullára állítja (mivel ugyanazt a tárhelyet használja), aminek következtében x és y elveszítik eredeti értéküket.

A helyesség bizonyítása

Az $N$ hosszúságú bittömbök feletti XOR binér művelet(wd) a következő tulajdonságokkal rendelkezik (ahol $\oplus$ az XOR műveletet jelöli):^[a]

L1. Kommutativitás: $A\oplus B=B\oplus A$
L2. Asszociativitás: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
L3. Neutrális elem: Létezik egy 0 értékű (N hosszú) bitlánc, amelyre bármely $A$ esetén $A\oplus 0=A$
L4. Minden elem a saját inverze(wd): minden $A$ esetén $A\oplus A=0$ .^[3]

Tegyük fel, hogy két különböző regiszterünk van, R1 és R2, ahogy az az alábbi táblázatban látható, A és B kezdeti értékekkel. Az alábbi műveleteket sorban végrehajtjuk, és az eredményeket a fent felsorolt tulajdonságok felhasználásával redukáljuk.

Lépés	Művelet	1. regiszter	2. regiszter	Redukció
0	Kezdeti érték	$A$	$B$	—
1	`R1 := R1 XOR R2`	$A\oplus B$	$B$	—
2	`R2 := R1 XOR R2`	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)$ $=A\oplus 0$ $=A$	L2 L4 L3
3	`R1 := R1 XOR R2`	$(A\oplus B)\oplus A=(B\oplus A)\oplus A$ $=B\oplus (A\oplus A)$ $=B\oplus 0$ $=B$	$\ A$	L1 L2 L4 L3

Lineáris algebrai értelmezés

Mivel az XOR értelmezhető bináris összeadásként, és egy bitpár értelmezhető vektorként egy kétdimenziós vektortérben a kételemű mező(wd) felett, az algoritmus lépései 2×2 mátrixokkal való szorzásként értelmezhetők a kételemű test(wd) felett. Az egyszerűség kedvéért kezdetben tegyük fel, hogy x és y egyaránt egyedi bitek, nem bitvektorok.

Például a lépés:

X := X XOR Y

amely implicit módon tartalmazza a következőt:

Y := Y

megfelel a $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ mátrixnak, mint

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end{pmatrix}}

.

A műveletek sorrendjét ezután a következőképpen fejezzük ki:

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

(bináris értékekkel dolgozik, tehát $1+1=0$ ), amely két sor (vagy oszlop) felcserélésének elemi mátrixát(wd) fejezi ki^[4] az egyik elem másikhoz való hozzáadásának transzvekcióival(wd) (nyírásaival^[5]).

Az X és Y nem egyetlen bit, hanem n hosszúságú bitvektorokra való általánosításhoz ezeket a 2×2 mátrixokat 2n×2n blokkmátrixokkal(wd) helyettesítjük, például $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$ ^[6]^[7]

Ezek a mátrixok értékekkel, nem pedig változókkal (tárolási helyekkel) működnek, ezért ez az értelmezés elvonatkoztat a tárolási hely kérdéseitől és attól a problémától, hogy mindkét változó ugyanazon a tárolási helyen van.

Példa kód

Egy C függvény, amely megvalósítja az XOR csere algoritmust:

void XorSwap(int *x, int *y) 
{
  if (x == y) return;
  *x ^= *y;
  *y ^= *x;
  *x ^= *y;
}

A kód először ellenőrzi, hogy a címek különbözőek-e, és egy védelmi záradék^[8] segítségével korán kilép a függvényből, ha egyenlőek. Ezen ellenőrzés nélkül, ha egyenlőek lennének, az algoritmus egy *x ^= *x hármast adna, ami nullát eredményezne.^[9]

Az XOR cserealgoritmus makróval is definiálható:

#define XORSWAP_UNSAFE(a, b)                                                   \
  ((a) ^= (b), (b) ^= (a),                                                     \
   (a) ^= (b)) /* Nem működik, ha a és b ugyanaz az objektum \
                  - ebben az esetben nullát (0) rendel az objektumhoz */
#define XORSWAP(a, b)                                                         \
  ((&(a) == &(b)) ? (a) /* Különböző értékek ellenőrzése */                    \
                  : XORSWAP_UNSAFE(a, b))

A gyakorlatban elkerülendő okok

A modern CPU-architektúrákon az XOR technika lassabb lehet, mint egy ideiglenes változó használata a cseréhez. Legalábbis a legújabb x86-os CPU-kon, mind az AMD, mind az Intel esetében, a regiszterek közötti mozgás rendszeresen nulla késleltetéssel jár. (Ezt MOV-eliminációnak nevezik.) Még ha nincs is elérhető architekturális regiszter, az XCHG utasítás legalább olyan gyors lesz, mint a három XOR együttvéve. Egy másik ok, hogy a modern CPU-k igyekeznek az utasításokat párhuzamosan végrehajtani utasításpipeline-okon(wd) keresztül.^[10] Az XOR technikában az egyes műveletek bemenetei az előző művelet eredményétől függenek, ezért szigorúan egymás után kell végrehajtani őket, ami érvényteleníti az utasításszintű párhuzamosság előnyeit.^[11]

Aliasing

Az XOR csere a gyakorlatban az álnevezés^[12] miatt bonyolult. Ha megpróbáljuk egy adott hely tartalmát önmagával XOR-cserével felcserélni, az eredmény az, hogy a hely nullázódik, és az értéke elvész. Ezért az XOR-cserét nem szabad vakon használni magas szintű nyelvekben, ha az álnevezés lehetséges. Ez a probléma nem érvényes, ha a technikát assemblyben használják két regiszter tartalmának felcserélésére.

Hasonló problémák fordulnak elő a név szerinti hívással,^[13] mint például Jensen eszközében(wd), ahol az i és A[i] felcserélése egy ideiglenes változón keresztül helytelen eredményeket ad az argumentumok összefüggése miatt: a csere a temp = i; i = A[i]; A[i] = temp változón keresztül megváltoztatja az i értékét a második utasításban, ami aztán helytelen i értéket eredményez A[i] számára a harmadik utasításban.

Változatok

Az XOR csere algoritmus alapelve bármely, a fenti L1-L4 kritériumoknak megfelelő műveletre alkalmazható. Az XOR összeadással és kivonással való helyettesítése különféle, kissé eltérő, de nagyrészt egyenértékű megfogalmazásokat ad. Például:^[14]

void AddSwap( unsigned int* x, unsigned int* y )
{
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
}

Az XOR cserével ellentétben ez a variáció megköveteli, hogy az alapul szolgáló processzor vagy programozási nyelv olyan módszert használjon, mint a moduláris aritmetika vagy a bignum,^[15] hogy garantálja, hogy az X + Y kiszámítása ne okozzon hibát egészszám-túlcsordulás(wd) miatt.^[16] Ezért a gyakorlatban még ritkábban fordul elő, mint az XOR csere.

Azonban a fenti AddSwap implementációja a C programozási nyelvben mindig működik, még egész szám túlcsordulás esetén is, mivel a C szabvány szerint az előjel nélküli egész számok összeadása és kivonása a maradékosztály szabályait követi, azaz a $\mathbb {Z} /2^{s}\mathbb {Z}$ ciklikus csoportban történik, ahol $s$ az unsigned int bitjeinek száma. Valójában az algoritmus helyessége abból következik, hogy az $(x+y)-y=x$ és a $(x+y)-((x+y)-y)=y$ képletek bármely Abel-csoportban érvényesek. Ez általánosítja az XOR-csere algoritmus bizonyítását: az XOR az összeadás és a kivonás is az $(\mathbb {Z} /2\mathbb {Z} )^{s}$ Abel-csoportban (ami a $\mathbb {Z} /2\mathbb {Z}$ s példányának direkt összege(wd)). Ez nem érvényes a signed int típus esetén (ez az alapértelmezett az int típusnál). Az előjeles egészszám-túlcsordulás egy nem definiált viselkedés a C-ben, így a maradékosztály nem garantált a szabvány által, ami helytelen eredményekhez vezethet.

Az AddSwap műveletsorozata mátrixszorzással fejezhető ki a következőképpen:

{\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

Regiszterkiosztás alkalmazása

A dedikált swap utasítással nem rendelkező architektúrákon az XOR-swap algoritmus szükséges az optimális regiszterkiosztáshoz, mivel ez elkerüli az extra ideiglenes regisztert.^[17] Ez különösen fontos azoknál a fordítóprogramoknál, amelyek statikus egyszeres értékadási formát^[18] használnak a regiszterelosztáshoz; ezek a fordítók időnként olyan programokat hoznak létre, amelyeknek két regisztert kell cserélniük, amikor egyetlen szabad regiszter sincs. Az XOR csere algoritmus elkerüli egy extra regiszter lefoglalásának vagy a regiszterek főmemóriába való kibontásának szükségességét.^[19] Az összeadás/kivonás változat is használható ugyanerre a célra.^[20]

Ez a regiszterallokációs módszer különösen releváns a GPU shader(wd) fordítók számára.^[21] A modern GPU architektúrákon a változók kiszórása költséges a korlátozott memória-sávszélesség és a magas memóriakésleltetés miatt, míg a regiszterhasználat korlátozása javíthatja a teljesítményt a regiszterfájl(wd) dinamikus particionálása miatt. Ezért egyes GPU fordítók megkövetelik az XOR swap algoritmust.^[22]

Lásd még

Megjegyzések

↑ Az első három tulajdonság, valamint az egyes elemek inverzének létezése az Abel-csoport definícióját alkotja. Az utolsó tulajdonság az az állítás, hogy minden elem involúció(wd) (öninverz függvény), azaz másodrendű, ami nem igaz minden Abel-csoportra.

Jegyzetek

↑ The Magic of XOR. Cs.umd.edu. [2014. április 1-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. április 2.)
↑ Swapping Values with XOR. graphics.stanford.edu. (Hozzáférés: 2014. május 2.)
↑ A matematikában az inverz elem(wd) fogalma általánosítja a számok ellentétét ( $-x$ ) és reciprokát ( $1/x$ ).
↑ Az elemi mátrix(wd) egy négyzetes mátrix, amelyet az egységmátrixon végzett egyetlen elemi sorművelet alkalmazásával kapunk.
↑ A síkgeometriában a nyírási leképezés(wd) egy affin transzformáció, amely minden pontot egy rögzített irányban elmozdít egy adott, az adott iránnyal párhuzamos egyenestől való előjeles távolságával(wd) arányos mennyiséggel.
↑ Eves, Howard. Elementary Matrix Theory, reprint, New York: Dover, 37. o. (1980). ISBN 0-486-63946-0 „We shall find that it is sometimes convenient to subdivide a matrix into rectangular blocks of elements. This leads us to consider so-called partitioned, or block, matrices.”
↑ Dobrushkin, Vladimir: Partition Matrices. Linear Algebra with Mathematica . (Hozzáférés: 2024. március 24.)
↑ A guard(wd) egy logikai kifejezés, amelynek igaznak kell lennie az értékelése során, ha a program végrehajtásának folytatódnia kell a kérdéses ágban. A guard clause (védelmi záradék) korai kilépést biztosít egy szubrutinból, és egy gyakran használt eltérés a strukturált programozástól, eltávolítva egy szintet a beágyazásból és kisebb kódot eredményezve: az if guard { ... } helyére if not guard: return; ... kerül.
↑ Beck, Kent. Smalltalk Best Practice Patterns,, 178–179. o. (1997)
↑ A számítástechnikában az utasítás-pipelining egy olyan technika, amely egyetlen processzoron belüli utasításszintű párhuzamosságot valósít meg. A pipelining célja, hogy a processzor minden részét valamilyen utasítással lefoglalja azáltal, hogy a bejövő utasításokat egymást követő lépések sorozatára ("pipeline"(wd)) osztja, amelyeket különböző processzoregységek hajtanak végre, az utasítások különböző részeit párhuzamosan feldolgozva.
↑ 6.172 Performance Engineering of Software Systems, Lecture 2. MIT OpenCourseWare . Massachusetts Institute of Technology, 2010. [2015. január 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2015. január 27.)
↑ A számítástechnikában az aliasing olyan helyzetet ír le, amelyben a memóriában(wd) lévő adathelyhez a programban különböző szimbolikus neveken keresztül lehet hozzáférni. Így az adatok egyetlen névvel történő módosítása implicit módon módosítja az összes alias névhez tartozó értékeket, amire a programozó nem feltétlenül számít. Ennek eredményeként az aliasing különösen megnehezíti a programok megértését, elemzését és optimalizálását.
↑ A név szerinti hívás (call by name) egy kiértékelési stratégia, ahol a függvény argumentumai nem értékelődnek ki a függvény meghívása előtt, hanem közvetlenül a függvény törzsébe helyettesítődnek be, majd valahányszor megjelennek a függvényben, kiértékelődnek.
↑ Hacker's delight. Boston: Addison-Wesley, 39. o. (2003. május 8.). ISBN 0201914654
↑ A számítástudományban az tetszőleges precizitású aritmetika(wd), más néven bignum aritmetika azt jelenti, hogy a számításokat olyan számokon végzik, amelyek pontosságát potenciálisan csak a gazdarendszer rendelkezésre álló memóriája korlátozza.
↑ Egész szám túlcsordulás akkor fordul elő, amikor egy egész számokon végrehajtott aritmetikai művelet olyan numerikus értéket próbál létrehozni, amely kívül esik az adott számú számjeggyel ábrázolható tartományon – vagy magasabb, mint a maximális, vagy alacsonyabb, mint a minimálisan ábrázolható érték.
↑ A fordítóprogram optimalizálásában a regiszterallokáció(wd) az a folyamat, amelynek során lokális automatikus változókat(wd) és kifejezéseredményeket rendelünk hozzá korlátozott számú processzorregiszterhez.
↑ A statikus egyszeres értékadású forma (static single assignment form(wd), SSA) egyfajta köztes reprezentáció, ahol minden változóhoz pontosan egyszer rendelnek hozzá értéket.
↑ SSA Elimination after Register Allocation, Compiler Construction, Lecture Notes in Computer Science, 158–173. o.. DOI: 10.1007/978-3-642-00722-4_12 (2009. május 8.). ISBN 978-3-642-00721-7
↑ Register Allocation for Programs in SSA-Form, Compiler Construction, Lecture Notes in Computer Science, 247–262. o.. DOI: 10.1007/11688839_20 (2006. május 8.). ISBN 978-3-540-33050-9
↑ A shader(wd) egy számítógépes program, amely kiszámítja a megfelelő fény-, sötétség- és színszinteket egy 3D-s jelenet renderelésekor(wd) – ezt a folyamatot árnyékolásnak(wd) nevezik.
↑ SSA-based Register Allocation for GPU Architectures. (Hozzáférés: 2022. április 17.)

Fordítás

Ez a szócikk részben vagy egészben a XOR swap algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Informatikai portál • összefoglaló, színes tartalomajánló lap

[3] Az első három tulajdonság, valamint az egyes elemek inverzének létezése az Abel-csoport definícióját alkotja. Az utolsó tulajdonság az az állítás, hogy minden elem involúció(wd) (öninverz függvény), azaz másodrendű, ami nem igaz minden Abel-csoportra.

[1] The Magic of XOR. Cs.umd.edu. [2014. április 1-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. április 2.)

[2] Swapping Values with XOR. graphics.stanford.edu. (Hozzáférés: 2014. május 2.)

[4] A matematikában az inverz elem(wd) fogalma általánosítja a számok ellentétét ( $-x$ ) és reciprokát ( $1/x$ ).

[5] Az elemi mátrix(wd) egy négyzetes mátrix, amelyet az egységmátrixon végzett egyetlen elemi sorművelet alkalmazásával kapunk.

[6] A síkgeometriában a nyírási leképezés(wd) egy affin transzformáció, amely minden pontot egy rögzített irányban elmozdít egy adott, az adott iránnyal párhuzamos egyenestől való előjeles távolságával(wd) arányos mennyiséggel.

[7] Eves, Howard. Elementary Matrix Theory, reprint, New York: Dover, 37. o. (1980). ISBN 0-486-63946-0 „We shall find that it is sometimes convenient to subdivide a matrix into rectangular blocks of elements. This leads us to consider so-called partitioned, or block, matrices.”

[:8-8] Dobrushkin, Vladimir: Partition Matrices. Linear Algebra with Mathematica . (Hozzáférés: 2024. március 24.)

[9] A guard(wd) egy logikai kifejezés, amelynek igaznak kell lennie az értékelése során, ha a program végrehajtásának folytatódnia kell a kérdéses ágban. A guard clause (védelmi záradék) korai kilépést biztosít egy szubrutinból, és egy gyakran használt eltérés a strukturált programozástól, eltávolítva egy szintet a beágyazásból és kisebb kódot eredményezve: az if guard { ... } helyére if not guard: return; ... kerül.

[beck-10] Beck, Kent. Smalltalk Best Practice Patterns,, 178–179. o. (1997)

[11] A számítástechnikában az utasítás-pipelining egy olyan technika, amely egyetlen processzoron belüli utasításszintű párhuzamosságot valósít meg. A pipelining célja, hogy a processzor minden részét valamilyen utasítással lefoglalja azáltal, hogy a bejövő utasításokat egymást követő lépések sorozatára ("pipeline"(wd)) osztja, amelyeket különböző processzoregységek hajtanak végre, az utasítások különböző részeit párhuzamosan feldolgozva.

[12] 6.172 Performance Engineering of Software Systems, Lecture 2. MIT OpenCourseWare . Massachusetts Institute of Technology, 2010. [2015. január 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2015. január 27.)

[13] A számítástechnikában az aliasing olyan helyzetet ír le, amelyben a memóriában(wd) lévő adathelyhez a programban különböző szimbolikus neveken keresztül lehet hozzáférni. Így az adatok egyetlen névvel történő módosítása implicit módon módosítja az összes alias névhez tartozó értékeket, amire a programozó nem feltétlenül számít. Ennek eredményeként az aliasing különösen megnehezíti a programok megértését, elemzését és optimalizálását.

[14] A név szerinti hívás (call by name) egy kiértékelési stratégia, ahol a függvény argumentumai nem értékelődnek ki a függvény meghívása előtt, hanem közvetlenül a függvény törzsébe helyettesítődnek be, majd valahányszor megjelennek a függvényben, kiértékelődnek.

[15] Hacker's delight. Boston: Addison-Wesley, 39. o. (2003. május 8.). ISBN 0201914654

[16] A számítástudományban az tetszőleges precizitású aritmetika(wd), más néven bignum aritmetika azt jelenti, hogy a számításokat olyan számokon végzik, amelyek pontosságát potenciálisan csak a gazdarendszer rendelkezésre álló memóriája korlátozza.

[17] Egész szám túlcsordulás akkor fordul elő, amikor egy egész számokon végrehajtott aritmetikai művelet olyan numerikus értéket próbál létrehozni, amely kívül esik az adott számú számjeggyel ábrázolható tartományon – vagy magasabb, mint a maximális, vagy alacsonyabb, mint a minimálisan ábrázolható érték.

[18] A fordítóprogram optimalizálásában a regiszterallokáció(wd) az a folyamat, amelynek során lokális automatikus változókat(wd) és kifejezéseredményeket rendelünk hozzá korlátozott számú processzorregiszterhez.

[19] A statikus egyszeres értékadású forma (static single assignment form(wd), SSA) egyfajta köztes reprezentáció, ahol minden változóhoz pontosan egyszer rendelnek hozzá értéket.

[20] SSA Elimination after Register Allocation, Compiler Construction, Lecture Notes in Computer Science, 158–173. o.. DOI: 10.1007/978-3-642-00722-4_12 (2009. május 8.). ISBN 978-3-642-00721-7

[21] Register Allocation for Programs in SSA-Form, Compiler Construction, Lecture Notes in Computer Science, 247–262. o.. DOI: 10.1007/11688839_20 (2006. május 8.). ISBN 978-3-540-33050-9

[22] A shader(wd) egy számítógépes program, amely kiszámítja a megfelelő fény-, sötétség- és színszinteket egy 3D-s jelenet renderelésekor(wd) – ezt a folyamatot árnyékolásnak(wd) nevezik.

[23] SSA-based Register Allocation for GPU Architectures. (Hozzáférés: 2022. április 17.)

[1]

[2]

[a]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]