27 iunie 2011

Optimizari

Asa cum am relatat in postarea precedenta, algoritmul paralel implementat se dovedeste a fi foarte ineficient (cel putin la prima vedere).


Pentru a-l imbunatati, primii pasi vor fi sa:

  • - elimin recrearea contextului de fiecare data
  • - elimin recompilarea programului de fiecare data (+ 0.1-0.3 la fiecare apelare)
  • - incearc sa inlantuiesc mai multe seturi de kernel-uri in acelasi context (folosind event)
  • - evit daca pot interschimbarea haotica de date (e rau mai ales pe GPU)
  • - bitonic sort e un mod de a sorta datele foarte potrivit pentru arhitecturi paralele (inclusiv GPU-uri), sugestie in loc de bubble sort in kernel-uri
  • - incearc sa elimin/reduc acele loop-uri din kernel cumva (cu cat sunt mai multe branch-uri conditionale cu atat e mai rau)
  • - reduc alocarile/eliberarile de memorie, folosind eventual o memorie tampon prealocata.

Cod: se poate gasi aici: http://dl.dropbox.com/u/24465060/K_elem_v3.zip

Observatii: timpul de executie s-a imbunatatit considerabil doar urmand cateva dintre sugestii, desi sortarile in kernels au ramas bubble sort (= multe bucle, multe ramificatii, interschimbari haotice).

------------------------- Teste -----------------------------------------------


n = 2400
k = 2000

[1] GeForce 8600 GT (4 cu) = 0.50s
[2] GeForce 210 (2 cu) = 0.91s
[3] Cedar Radeon 5470 (2 cu) = 0.57s
[5] ATI RV730 (8 cu) = 0.69s

==================

n = 2000
k = 1282

[0] Intel(R) Core(TM)2 Duo CPU = 0.09s
[1] GeForce 8600 GT (4 cu) = 0.34s
[2] GeForce 210 (2 cu) = 0.65s
[3] Cedar Radeon 5470 (2 cu) = 0.54s
[4] Intel(R) Core(TM) i3 CPU = 0.13s
[5] ATI RV730 (8 cu) = 0.69s

==================

n = 1000
k = 333

[0] Intel(R) Core(TM)2 Duo CPU = 0.09s
[1] GeForce 8600 GT (4 cu) = 0.14s
[2] GeForce 210 (2 cu) = 0.32s
[3] Cedar Radeon 5470 (2 cu) = 0.56s
[4] Intel(R) Core(TM) i3 CPU = 0.13s
[5] ATI RV730 (8 cu) = 0.71s

==================

n = 443
k = 89

[0] Intel(R) Core(TM)2 Duo CPU = 0.10s
[1] GeForce 8600 GT (4 cu) = 0.14s
[2] GeForce 210 (2 cu) = 0.17s
[3] Cedar Radeon 5470 (2 cu) = 0.55s
[4] Intel(R) Core(TM) i3 CPU = 0.12s
[5] ATI RV730 (8 cu) = 0.67s

Concluzii:


  • nu este un algoritm care sa demonstreze eficienta calculului pe GPU comparativ cu calculul pe CPU – ceea ce intareste ideea ca DOAR anumite probleme pot fi executate mai rapid pe placa grafica si anume cele pe seturi mari de date cu aplicarea unor operatii repetitive (specific SIMD)
  • principale dezavantaje GPU: latenta mare de transfer a datelor din RAM catre VRAM (memoria placii grafice) si invers; aceasta poate fi acoperita prin executia rapida si repetata a unor task-uri
  • in cazul de fata, datorita memoriei locale limitate de pe GPU si a structurii algoritmului, valoarea lui n nu poate trece de un prag (aici, 2500) – posibil ca programul sa dea rezultate foarte bune in favoarea GPU pentru valori mult mai mari ale lui n
  • algoritmul a trebuit regandit de mai multe ori pentru a da rezultate cat mai bune atat pe CPU cat si pe GPU – programarea in OpenCL cere totusi cunoasterea arhitecturii platformelor

24 iunie 2011

Days 5+

Implementarea unui algoritm in OpenCL si analiza performantei (rapiditate, scalabilitate, etc... )
Am ales sa implementez "aflarea celui de-al K-lea element dintr-un vector" - variantele banala, recursiva & paralela .

Banala -- sortarea vectorului si afisarea celui de-al K-lea element
Recursiva -- aflarea elementului, fara a sorta vectorul
Paralela -- se bazeaza pe varianta recursiva, cu paralelizarea unuia dintre pasi

Observatii:
- varianta banala tinde sa mearga mai bine decat cea recursiva pentru valori mari ale lui n (overhead la crearea stivelor pt varianta recursiva)
- aparent, varianta paralela merge de... numai paralela nu este . Se pare ca overhead-ul de creare a contextelor este imens... [in curand] optimizari.

19 iunie 2011

Days 3, 4

In Day 3, s-a discutat structura generala a unui program openCL si s-au prezentat cateva exemple.
Pe scurt, o sursa se compune dintr-un program C/C++, un program de kernel plus alte surse auxiliare, biblioteci, etc.

Un program in OpenCL are 3 parti:
* initializari - aici se specifica platforma, device-ul, se creeaza contextul, queues (cozile), (+ se fac verificari)
* executia kernel-urilor
* finalizare

De initializari si finalizare se ocupa codul in C/C++, iar de treaba propriu-zisa se ocupa fisierele de kernel. Compilarea este doar a programelor C/C++, iar fisierul binar rezultat va fi cel care executa fisierul de kernel (daca doar acesta se modifica, nu trebuie recompilat totul).

/////////////////////////////////////////////////////

Un exemplu "simplu" cu filtre de imagini si unul "complex" cu histogram equalisation puteti gasi aici: http://dl.dropbox.com/u/24465060/image_processing_geo.zip

18 iunie 2011

OpenCL Programming

Cateva idei din cartea "OpenCL Programming" de la FixStars:

* arhitecturi hardware care folosesc mai multe procesoare pentru implinirea unei singure sarcini:
- Grid computing - o combinatie de resurse din mai multe domenii administrative care realizeaza un singur task
- MPP = Massively Parallel Processor - "arhitectura super computer"
- Cluster server system - retea de calculatoare cu scop general
- SMP = Symmetric Multiprocessing system - un numar de 2^n procesoare identice conectate
- Multi-core processor - un chip cu mai multe nuclee de calcul

* Flynn
- pana in 2004 - SISD
- SIMD - instructiunea este difuzata la mai multe unitati de calcul - procesare vectoriala.
Recent, mai multe microprocesoare suporta instructiuni SIMD: SSE pe Intel CPU, si SPE pe un Cell BE.
- MISD - mai putine exemple, sistemele tolerante la defecte intra in categorie
- MIMD - clustere, sistem SMP

* Acceleratori:
GPU, Cell Broadband Engine - core-uri simple, care nu ocupa mult spatiu pe chip, deci pot fi incorporate mai multe
ex. GPU: Nvidia GPU chip (Tesla T10) = 30 de seturi de Streaming Processors (a cate 8 core-uri fiecare), in total 240 core-uri pe un chip
GPU-urile sunt superioare CPU-urilor pentru ca pot realiza intre 100 GFLOPS-1 TFLOPS, pe cand CPU-urile sunt limitate la 10 GFLOPS (giga floating operations per second)

OpenCL = framework pt scrierea de aplicatii in sisteme eterogene / hibride
"open computing language"

Implementarea unui program paralel:
* folosind apelurile de sistem ale SO : Posix threads
* folosind un framework: MPI pentru cluster servers, OpenMP pentru SMP, NUMA (sistemele cu memorie partajata), API-uri de paralelizare in Boost C++.
OpenMP - suportat de cele mai importante compilatoare: gcc, Intel C, Microsoft C
* prin compilare automata: Intel C/C++ , prin specificarea unor parametri de paralelizare in linia de comanda. Desi este mai comod asa, cu cat codul devine mai complex performanta are de suferit, compilatorul nestiind sa paralelizeze corespunzator.

OpenCL - pentru sisteme eterogene, dar si omogene (multi core: un core pentru control, restul pentru executii)
- scopul: un singur limbaj pentru a programa atat pe CPU-uri cat si pe GPU-uri, Cell BE, DSP-uri, .....

* Comparatie CUDA-Cell-lumea embedded
CPU = "host" - rol de management si control ---- "Host program"
GPU = "device" - rol de procesare data parallel -- "Kernel"
Kernelul trebuie scris in limbaj CUDA (extensie a lui C)
CUDA este asemanator cu Cell BE, CPU-ul fiind analog PPE, GPU-urile analoage SPU-urilor.
In domeniul embedded systems, modelul este asemanator: CPU dirijeaza DSP-urile (care au o functie primitiva - "digital signal processing")

Problema: toate cele 3 situatii (CUDA, Cell, sistemele embedded) cer folosirea unui API diferit. Solutia propusa este OpenCL.

Software de OpenCL = {compilator OpenCL, biblioteca runtime OpenCL}
Procesoarele implicate trebuie sa suporte insa OpenCL (vezi placa video)
Avantaje OpenCL:
- API pentru paralelizare standard
- optimizare: operatii vectoriale SIMD, copiere asincrona de memorie folosind DMA, transfer de memorie intre procesoare. OpenCL nu va limita niciodata performanta (in cazul unor functii nesuportate, se va folosi API-ul specific al procesorului)

Platforme: Host + Device
- Host: mediul in care se afla programul care controleaza device-urile, de obicei CPU-ul + memoria aferenta
- Device: GPU, DSP, Cell BE, alte CPU-uri + memoriile aferente
Un GPU este descris astfel: Device (GPU) + unitate de calcul (SM=streaming processor) + element de procesare (SP=scalar processor)
Programul care ruleaza pe device = kernel.

API-urile oferite de OpenCL se incadreaza pt urmatoarele modele de programare paralela:
* data parallel - un singur kernel este executat simultan in unitatile de calcul sau elementele de procesare, cu seturi diferite de date
* task parallel - mai multe kernel-uri....

Daca pe fiecare unitate de calcul ruleaza un grup kernel-uri , grupul primeste un ID unic (Work group ID). Fiecare kernel din grup primeste si el un ID (Work item ID). Utilizatorul specifica numarul total de work items si numarul de work items care sa ruleze pe fiecare unitate de calcul.
ID-ul poate avea pana la 3 dimensiuni.

* Modelul de memorie, contine memorie:
- globala: poate fi citita de toti work items, fizic rezidua in memoria principala a device-ului
- constanta: idem cea globala, doar ca poate fi folosita mai eficient dar unitatile de calcul contin hardware ce suporta constant memory cache
- locala: poate fi citita de toti work items din work group-ul respectiv. Fizic este memoria partajata de pe fiecare unitate de calcul
- privata: accesata doar de un singur work item. Fizic, corespunde registrilor fiecarui element de procesare.

Host : poate manipula memoria globala, constanta si memoria proprie
Device : memoria sa este accesata exclusiv de catre kernel


Continuarea acestei carti arata modul de instalare , exemple de utilizare si alte detalii utile.

16 iunie 2011

Day 2

* GPGPU platforms (OpenCL, DirectCompute, CUDA, Stream)
GPGPU = general purpose GPU; GPU-urile sunt folosite pt scop general, atât pt calcule grafice cât și pt calcule normale (executate de CPU);
- OpenCL - producător Khronos - merge pe SO Linux, Windows, Mac
- CUDA ("compute unified device architecture") - producător Nvidia - merge pe Linux, Windows
- DirectCompute - producător Microsoft - merge doar pe Windows
- Stream - producător AMD


* My PC Amd X2 4000+, 4GB, GF210, GF8600
a) Use bios info to describe it.
b) Use CPUz & GPUz to describe it.
c) Compare GF210 vs 8600GT.
Why ?3dmark 2003. 3dmark 2006.


* SIMD vs SISD. CPU vs GPU.


* APU discutie. Prezentare APU Brazos, Zacate.
APU = un chip in care sunt incorporate CPU si GPU


* Discutie Liano.Prezentare Sandy Bridge vs Nehalem.


* Diferenta IGP onboard, on socket, on die.Intel Larrabee prezentare arhitectura.
Why ? Why not ?Exemple probleme SIMD. Discutie.


* Pre GPGPU era. Discutie.


* GPGPU meaning. Geforce 8800 architecture presentation.


* Geforce 8800 vs Geforce 7900 architecture.


* Limitations GPGPU. Nvidia Tesla. Amd Firestream.Nvidia Fermi.


* Nvidia CUDA. Amd Stream.OpenCL. DirectCompute.


* Examples GPGPU CUDA & DirectCompute.Discutie.


a) When GPGPU ? Limitations ?
b) Memory hierarchy importance GPGPU.
c) OpenCL vs DirectCompute vs Cuda. Discussion.

15 iunie 2011

Day 1

Aici incep o serie de articole cu noutati din activitatea de practica de anul acesta; anul trecut nu am facut acest lucru si mi-a parut rau, pentru ca unele lucruri s-au cam "uitat" si intotdeauna e bine sa scrii acolo ce faci, decat sa te bazezi doar pe memorie :) De asemenea, practica de anul acesta aduce cu sine concepte noi si intr-o oarecare masura transmise pe "cale orala" - un motiv in plus ca sa consemnez cate ceva... inca un lucru pe care l-am observat de cand am deschis acest blog a fost ca orice lucru pe care l-am postat a insemnat sa imi dau interesul mai mult (pentru el) decat o faceam in mod obisnuit.

-------------------------------------- //// --------------------------------------------

In primele 3 zile se vor dezvolta notiuni teoretice, urmand ca in urmatoarele 2 saptamani sa se faca aplicatii. Tema practicii: Workflow Heterogeneous Computing - calcul heterogen (pe CPU-uri si GPU-uri), OpenCL .

Meniul de astazi se poate gasi aici, iar eu le voi lua pe rand, in 2-3 cuvinte despre fiecare:


* Description CPU. Current CPU technologies.
CPU = central processing unit;
- roluri: citire, interpretare & executie de instructiuni (operatii aritmetice, logice si de I/E)
- parametri: nr.de nuclee, frecventa, GFlops (nr de giga-floating operations), diametru, nr. tranzistori, registri si dimensiunea lor, cache-uri: L1, L2, L3, FSB (front side bus), CPU socket;
- cresterea performantei prin scaderea diametrului & cresterea frecventei;
- de la frecvente mai mari de 4GHz/procesor, eficienta scade in primul rand prin consumul ridicat de putere (costuri mari) + zgomot mai mare
- tehnologii: multicore & hyper threading. Hyper threading: sistemul de operare vede un singur procesor hyper-threaded ca 2 CPU-uri logice separate, avantajul fiind o planificare mai eficienta, nucleul este tinut ocupat cat de mult posibil.


* SISD paradigm. Singlecore vs Multicore vs Manycore.
SISD = single instruction, single data; executie secventiala, un procesor ~ o instructiune ~ un singur flux de date
- singlecore: un sistem cu un singur nucleu
- multicore: mai multe nuclee independente pe acelasi soclu, un CPU dual core va executa mai repede decat un CPU hyper-threaded; un CPU multicore poate fi si hyper-threaded
- manycore: un procesor cu zeci, sute, sau mii de nuclee


* MMX & SSE & AVX brief intro. Architecture differences (Netburst vs Core).
MMX, SSE, AVX, x86_64, 3DNow - tipuri de instructiuni
- MMX = "multimedia extension"
- SSE = "streaming SIMD extensions" (replica lui Intel la 3DNow al lui AMD) = noi instructiuni pt DSP si procesare grafica
- AVX = "advanced vector extensions"


* Architecture evolution (K8; K10.5, Prescott; Ivy Bridge)


* Benchmarking. Examples SuperPi, SySandra, Lappack, PCMark.


* Performance discussion.


* Important factors in current CPU performance


* CPU frequency vs CPU core count.
Un CPU de frecventa 4 GHz poate fi inlocuit cu 2 nuclee de 2 GHz, performanta este aproape aceeasi (putin mai buna la un singur nucleu), insa consumul este mai favorabil in cazul a 2 nuclee.


* Utilities presented : CPU-Z.


a) When singlecore / multicore ? When many core ?
- singlecore: aplicatii banale (Notepad)
- multicore: aplicatii atat de calcul cat si de preluare date de la dispozitive I/E, un browser cu mai multe tab-uri, Skype-ul (?)
- manycore: calculatoarele de top


b) Memory hierarchy. Why L1? Why L2? Why L3? Problems.
Ierarhie: registri, L1, L2, L3, RAM, HDD, cloud.....
- L1: tip SRAM, mare viteza, dimensiune mica, datele, instructiunile separat + TLB
- L2: dimensiune mai mare decat L1
- L3: optional
Probleme: cache-miss-uri, politica de inlocuire?

c) Check with CPU-Z and describe an architecture.













- nu am hyper-threading :(
- nu am instructiuni de tip AVX
- core speed este ajustat in functie de necesitatile sistemului
- 3 nuclee inseamna de fapt 4, unul fiind dezactivat din fabricatie (costa putin nucleul propriu zis, ajustarea arhitecturii este costisitoare. Motivul: o gama mai variata de preturi)


* Description GPU. Comparison with CPU
GPU = graphical processing unit
Parametri pt o placa video: producator (Nvidia, ATI), frecventa procesor, dimensiune, tip si frecventa memorie, latime magistrala (bus width), bandwidth, etc.
- CPU-ul este pentru calcule generale, iar GPU este strict specializat pe calcule ce tin de grafica, paralelism masiv
- CPU are un set de instructiuni mai bogat
- un GPU poate fi asezat in 3 locuri: pe placa de baza, pe acelasi soclu cu CPU-ul sau integrat cu CPU-ul
- GPU-ul lucreaza cu datele din memoria proprie VRAM, daca datele lipsesc, CPU-ul este cel care ii trimite datele din RAM (transfer costisitor); GPU nu poate comanda (cere) ceea ce ii lipseste;
- GPU = stream processor, 1 stream = {vertex, pixel, geometrical} ; vertex ~ modelare, pixel ~ efecte;
- frecventele GPU sunt mai mici decat cele ale CPU, deci consuma mai putina putere


* Memory hierarchy CPU vs GPU
- GPU nu are cache-uri, poate avea memorie locala pentru fiecare unitate de calcul


* Types of GPU. Discrete (PCI, AGP, PCIe) & Integrated (IGP, APU)
Discrete:
- PCI = "peripheral component interconnect", pentru placi de retea, sunet, modem, porturi USB/seriale, controllers de disc, etc. Nu prea se mai foloseste pt placi video din cauza cresterii latimii de banda, se vor folosi AGP si PCI Express.
- AGP = "accelerated graphics port" - canal de viteza inalta pt conectarea unei placi video la placa de baza.
- PCIe = "PCI Express" (2004) - inlocuieste PCI si AGP;
Integrate:
- IGP = "integrated graphics processor" - sunt de dimensiune limitata, nu pot avea cooler, nu au aceeasi performanta ca placile video, nu pot fi upgradate, solutie buna pt laptop-uri.
- APU = "accelerated processing unit" - poate include GPU-uri, FPGA-uri, etc; rata de transfer intre CPU si GPU este imbunatatita, consum redus.


* GPU evolution. Pipeline vertex/pixel; stream units
Inainte existau core-uri GPU specializate pt calcule de modelare (vertex) sau de efecte (pixel), dezavantajul era ca atunci cand se efectuau calcule de modelare, core-urile specializate pe efecte stateau degeaba; prin stream units, toata lumea face ceva la un moment dat...


* SIMD paradigm. Nvidia architecture evolution ( 5 series; fermi/kepler)
Fermi = arhitectura CUDA de la Nvidia, prima arhitectura completa pt GPU computing, pt HPC (high performance computing)


* Amd architecture evolution ( 9 series ; evergreen/southern island)


* IGP evolution. Intel IGPs, Nvidia & Amd IGPs.


* Benchmarking. 3dmark 2005/2006/vantage.


* Forceware & Catalyst drivers. Differences.
Forceware - driverul de la Nvidia
Catalyst - driverul de la ATI
Un driver Forceware nu poate face ca o placa video ATI sa fie recunoscuta, nici invers.


* Presentation. MultiGPU configurations.


* SLI vs Crossfire vs Lucid. Scalability discussion.


* Utilities presented : GPU-Z


a) When CPU ? When GPU ?


b) Inspect a GPU with GPU-Z. Describe.




















- nu suporta OpenCL, Cuda, DirectCompute...
- bus width de 32 de biti limiteaza serios performanta (chiar daca bandwidth e de 3.2 GBps)
- bus interface este PCI (un pic deprecated)

c) APU GPU vs Discrete GPU ?
In cazul APU GPU (GPU integrat), latimea de banda cu memoria RAM trebuie sa fie suficient de mare cat sa nu tina pe loc GPU-ul care este mai rapid decat un CPU. GPU are nevoie de un flux de mare de date, cat mai rapid. O mare parte din intarzieri este eliminata deoarece datele vin direct din RAM si nu trec din RAM in North Bridge si de acolo in VRAM-ul placii video (cazul Discrete GPU).