Trumpas įvadas į vaizdo procesorių architektūrą
Šių dienų kompiuteriuose vaizdo procesorius (angl. „GPU“ – Graphics Processing Unit) yra būtinas komponentas. Jis gali būti integruotas į motininę plokštę arba prijungtas atskirai vaizdo plokštėje. Šis procesorius gali atlikti ypač daug operacijų per sekundę savo galingumu kelis kartus aplenkdamas net pačius naujausius bendrosios paskirties procesorius.
1. Grafikas[šaltinis nr. 4] rodo kiek apytiksliai milijardų operacijų su slankaus kablelio skaičiais per sekundę galėjo atlikti naujausi bendrosios paskirties procesoriai (žydra kreivė) ir vaizdo procesoriai (raudona kreivė) nuo 1998 iki 2006 metų.
Vaizdo procesoriaus pagrindinė užduotis yra manipuliuoti 3D ir 2D vaizdus, skaičiuoti erdvinių objektų pozicijas ir apšvietimą. Nuo apytiksliai 2000 metų nauji vaizdo procesoriai gali būti programuojami vadinamųjų šešėliavimo programų pagalba (angl. „Shaders“). Tai leido kurti dar realistiškesnę kompiuterinę grafiką ir įgyvendinti naujus apšvietimo skaičiavimo metodus. Taip pat naujos galimybės sudomino ir kitų sričių specialistus.
Norint išsiaiškinti, kodėl vaizdo procesorius yra žymiai greitesnis už pagrindinės paskirties procesorių, reikia suprasti kaip jame apdorojami duomenys. Kadangi šis straipsnis neapžvelgs visos architektūros detalių, norintiems apie tai sužinoti plačiau, patariu apsilankyti procesorių gamintojos NVIDIA programuotojų puslapyje [7].
Taigi, duomenų apdorojimą grubiai vaizduoja diagrama nr.2. Objektai trimačiame pasaulyje dažniausiai aprašomi trikampiais. Šių trikampių viršūnės apdorojamos vadinamosiose viršūnių programose (angl. „Vertex shader“). Toliau iš tų viršūnių susidarantys trikampiai paverčiami į taškus ir perduodami taškų programai (angl. „Pixel shader“). Po to šis apdorotas taškas išvedamas į ekraną arba išsaugojamas į atmintį ir vėl iš naujo panaudojamas skaičiuojant kitas viršūnes ir taškus. Naujos kartos vaizdo procesoriuose (palaikančiuose 10-tą Direct3D versiją) atsirado dar daugiau programuojamų konvejerio dalių, tačiau jos nėr svarbios šiai straipsnio temai.
2. Duomenų apdorojimo konvejeris vaizdo procesoriuje
Dėl šios konvejerio tipo architektūros, duomenis galima lengvai apdoroti lygiagrečiai. Kiekviena viršūnė nepriklauso nuo kitų apdorojamų viršūnių ir kiekvienas taškas nepriklauso nuo kitų taškų. Todėl naujausi vaizdo procesoriai (2007 m.) turi net iki 128 skaičiavimo elementų, galinčių vykdyti viršūnių ir taškų programas vienu metu. Kiekvienas skaičiavimo elementas veikia apytiksliai 1500 MHz dažniu. Dėl to jų visuma aplenkia visus bendrosios paskirties procesorius. Šią skaičiavimo elementų didėjimo tendenciją matome ir šiandienos bendrosios paskirties procesoriuose, kurie jau turi iki 4 branduolių. Tačiau norint panaudoti šią galią, reikia stipriai keisti programos vykdymo eigą, priversti programą skaičiavimus vykdyti lygiagrečiai.
Kas yra GPGPU?
GPGPU angliškai reiškia General-Purpose computation on GPUs. Verčiant pažodžiui, būtų Bendros Paskirties Skaičiavimai su GPU. Dėl galimybės programuoti vaizdo procesorius ir didelės jų galios jie sudomino įvairių sričių specialistus. Priversti procesorių dirbti galima pasinaudojant įvairiom bibliotekom. Dvi pagrindinės šiuo metų populiariausios yra Direct3D, kuri turi HLSL (angl. „High Level Shading Language“), ir OpenGL su GLSL (angl. „OpenGL Shading Language“). Taip pat šiais metais NVIDIA pristatė CUDA (angl. „Compute Unified Device Architecture“) programavimo įrankį, kuris leidžia programuoti vaizdo procesorius kalba, panašia į populiariąją C kalbą.
Duomenys vaizdo atmintyje laikomi tekstūrų arba atminties blokų (buferių), į kuriuos surašomos viršūnių erdvėje koordinatės, pavidalu. Tekstūra – tai vienmatis, dvimatis ar trimatis paveiksliukas. Tekstūroje galime laikyti duomenis, kurių reikės atlikti skaičiavimams, ir išvesti į ją skaičiavimo rezultatus.
Bitoninio rikiavimo algoritmas
Vienas iš vaizdo procesoriaus pritaikymo būtų gali būti didelio kiekio duomenų rikiavimas. Tai operacija, kuri dažnai atliekama realiose situacijose, pavyzdžiui, įrašų rikiavimas duomenų bazėse. Tai galima atlikti vadinamuoju bitoninio rikiavimo algoritmu. Jis vykdomas keliomis (tiksliau log(n), kur n – duomenų kiekis, log – dvejetainis logaritmas) pakopomis. Algoritmo vykdymo metu surikiuoti mažesni duomenų blokai jungiami į dvigubai didesnius blokus. Šį algoritmą su vienmačiu masyvu arba vienmate tekstūra vaizdžiai iliustruoja diagrama žemiau.
Ši diagrama vaizduoja bitoninio rikiavimo algoritmą su 8 skaičiais. Algoritmas vykdomas trimis pakopomis. Vienos pakopos rezultatas yra sekančios pakopos duomenys. Kiekvienoje pakopoje masyvas išdalinamas į jau surikiuotus blokus, pažymėtus raudonai ir žaliai. Gretimi blokai lyginami taip, kaip vaizduoja rodyklės. Mažesnis elementas perkeliamas į žalią regioną, o didesnis į raudoną.
Bitoninio rikiavimo algoritmas ypatingas tuo, kad duomenų palyginimus ir sukeitimus galima atlikti lygiagrečiai, iškart visam duomenų masyvui (tekstūrai). Taip vienu metu išnaudojami visi vaizdo procesoriaus skaičiavimo elementai. Čia pateikiamas tik vienmačio masyvo rikiavimo algoritmas, bet dažniausiai naudojami dvimačiai masyvai, nes vaizdo procesoriai labiau pritaikyti dirbti su dvimatėmis tekstūromis (paveikslėliais). Taip pat šis algoritmas nėra pats našiausias lygiagretus rikiavimo algoritmas. Norintys sužinoti apie gudresnius būdus rikiuoti duomenis pasinaudojant vaizdo procesoriumi ar bet kokiu kitu lygiagretaus skaičiavimo procesoriumi, gali apsilankyti gpgpu.org.
Lygiagretūs rikiavimo algoritmai, vykdomi vaizdo procesoriuje, greičiu konkuruoja su algoritmais, vykdomais bendrosios paskirties procesoriuose, pavyzdžiui, greitu rikiavimu (angl. „Quick sort“). Kaip teigiama straipsnyje apie GPU TeraSort algoritmą, pigūs vaizdo procesoriai rikiuoja duomenis taip pat greit kaip žymiai brangesni bendrosios paskirties procesoriai (lyginama tuomet kainavusi $265 NVIDIA 7800 GT vaizdo plokštė su $2200 kainavusiu 3,6 GHz Dual Xeon serveriu).
Pabaiga
Straipsnyje paminėtas duomenų rikiavimo algoritmas yra tik vienas iš lygiagrečių procesorių pritaikymo būdų. Bendrosios paskirties skaičiavimai pasinaudojant vaizdo procesoriumi yra dar gan nauja sritis ir panašu, jog ateityje bus atrasta dar daugiau metodų kaip panaudoti šiuos galingus lygiagretaus skaičiavimo procesorius.
Naudoti šaltiniai:
http://www.gpgpu.org/
http://en.wikipedia.org/wiki/GPU
http://en.wikipedia.org/wiki/CUDA
http://www.wired.com/gadgets/pcs/news/2006/11/72090
GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management
http://en.wikipedia.org/wiki/Bitonic_sorter
http://developer.nvidia.com/
