optimizarea metodelor de sortare simd pentru gpu-uri nvidia

Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare

15.01.2010 Algoritmi paraleli şi distribuiţi – Prezentări Laborator 1

Optimizarea metodelor de sortare SIMD pentru GPU-uri NVIDIA

Vlad-Ştefan PETRE

331CB

[email protected]

http://twitter.com/vladpetre88

http://linkedin.com/in/vladpetre88


Background

• Algoritmii de sortare reprezintă cele mai importante cărămizi ale unui program. Sortarea eficientă a volumelor mari de date este o operaţie critică.

• Implementarea algoritmilor de sortare pentru CPU (central processing unit) este relativ facilă. Sortarea folosind GPU (graphics processing unit) nu mai este atât de facilă, deoarece procesorul grafic are o arhitectură cu un grad înalt de paralelism, de tip SIMD (single-instruction multiple-data).

• Implementarea unor algoritmi de sortare eficienţi pe GPU este importantă, deoarece procesorul grafic depăşeşte CPU atât în materie de memory-bound, cât şi în materie de compute-bound.



Fluxuri in GPU

• Spre deosebire de memoria CPU, memoria GPU are câteva restricţii şi este accesibilă prin intermediul unor abstractizări ale interfeţei de programare grafică.

• Aceste abstractizări reprezintă trei tipuri de fluxuri, fiecare cu setul său propriu de reguli.

• Cele trei tipuri de fluxuri vizibile programatorului sunt fluxurile vertex, fluxurile frame-buffer şi fluxurile texture.

• Un al 4-lea tip de flux este fluxul fragment. Acesta este produs şi consumat în totalitate în cadrul procesorului grafic.



Fluxuri in GPU (2)



Algoritmi de sortare

• Algoritmii de sortare se împart în două categorii: data-driven şi data-independent.

• În practică, cei mai rapizi algoritmi sunt cei de tip data-driven, ceea ce înseamnă că pasul care urmează a fi făcut de algoritm, depinde de valoarea cheii analizate în acel moment. Un exemplu de algoritm data-driven este quicksort. În cazul general, el are o complexitate O(n log(n)), iar în cazul cel mai nefavorabil O(n²), ceea ce îl face inacceptabil.

• Algoritmii data-independent nu prezintă asemenea discrepanţă. Ei vor urma mereu aceiaşi paşi, indiferent de cheia analizată. Aceasta rigiditate este exploatată pe arhitecturi paralele, cum este GPU, deoarece punctele cheie de comunicaţie sunt cunoscute în avans.



Odd-Even Transition Sort

• Este un algoritm data-independent uşor de implementat.

• În reţeaua de sortare de mai sus, fiecare coloană reprezintă o serie de comparaţii ce se execută în paralel (vectorul). Numim acest lucru, un pas al reţelei de sortare.



Odd-Even Transition Sort (2)

• Pe măsura ce se efectuează deplasarea către dreapta, cheile se sortează. Complexitatea algoritmului este O (n²), ceea ce înseamna că nu este optim.

• În GPU, randăm doi bufferi texture în modul double-buffer. La fiecare pas, desenăm un quad şi executăm un program fragment ce preia cheia la poziţia sa. Deoarece putem scrie numai un singur fragment la un moment dat, compararea a două chei presupune procesarea a două fragmente; efectuăm o comparaţie ‘<‘ pe primul şi una ‘>=‘ pe al doilea fragment.

• Ambele fragmente efectuează două preluări (fetch) de date (texture). Această abordare necesită un bandwidth dublu decât în cazul unei implementari CPU care preia datele o singură dată şi, în funcţie de rezultatul comparaţiei, face swap.



Odd-Even Merge Sort

• Ideea acestui algoritm este de a sorta toate cheile pare şi toate cheile impare separat şi apoi de a le combina. Fiecare asemenea pas este numit stadiu al algoritmului de sortare. Stadiile sunt apoi scalate şi repetate pentru toate puterile lui 2 până cand întregul vector este sortat.

• Pentru a sorta m chei ale unui stadiu, log(m) paşi sunt necesari. Pentru sortarea tuturor celor n chei, avem nevoie de log(n) stadii, rezultând astfel o complexitate a algoritmului de O(n log²(n)+log(n)) paşi. Deşi este mai mare decât complexitatea lui quicksort, este în continuare optim în cazul cel mai defavorabil. De aceea, acest algoritm este considerat a fi un algoritm optim. Sortând un milion de chei, durează 210 paşi, comparativ cu un milion de paşi cât ar dura la algoritmul anterior.



Odd-Even Merge Sort (2)

• Implementarea este asemănătoare cu cea a algoritmului precedent, ceea ce înseamnă că nu ne folosim de toate resursele GPU de care dispunem (unitatea vertex, unitatea rasterizer). De asemenea, avem în continuare nevoie de un număr dublu de preluări, comparativ cu o implementare CPU.



Bitonic Merge Sort

• În OEMS (odd-even merge sort), unele valori sunt comparate, în timp ce altele sunt doar copiate. Dorim să evităm această situaţie, deoarece ambele consumă acelaşi timp pentru a se executa. Deci trebuie să scăpăm de copii. Acest lucru va duce la o îmbunătăţire, deoarece actul care determină dacă elementele trebuie să fie comparate sau copiate, poate fi omis.

• Algoritmul BMS (bitonic merge sort) construieşte două subsecvenţe de chei, una ascendentă şi una descendentă, adică o secvenţă bitonică; iar apoi le combină. Acest lucru se repetă până când vom avea o singură secvenţă ascendentă.

• Complexitatea algoritmului este tot O(n log²(n) + log(n)), care, deşi nu este la fel de eficientă precum quicksort, nu prezintă un caz defavorabil.



Bitonic Merge Sort (2)

• Exemplu:



Maparea Bitonic Merge Sort pe GPU

• Principalul avantaj al utilizării acestui algoritm este posibilitatea acestuia de a se mapa eficient pe resursele puse la dispoziţie de GPU (gruparea cheilor, lucrul cu perechi index/cheie, folosirea procesoarelor vertex şi rasterizer, etc).




Analiza algoritmilor



Vă mulţumesc!

Întrebări ?

optimizarea metodelor de sortare simd pentru gpu-uri nvidia

Technology