Exerciții
Scrieți o implementare în virgulă fixă a generatorului Mandelbrot.
a.
Vă veți observa că performanța este inconsistentă între diferiți pixeli și diferite cadre. De ce se întâmplă acest lucru?
b.
Care este intensitatea aritmetică a corpului de buclă cel mai interior, în operații pe octet accesat din memorie? Care este limita de performanță corespunzătoare pentru procesorul ARM? Cum se compară aceasta cu performanța observată?
c.
Măsurați următorii parametri de performanță pentru corpul de buclă cel mai interior:
▪
instrucțiuni pe iterație
▪
instrucțiuni pe operație
▪
CPI
▪
cache miss rate
d.
Utilizați asamblarea în linie pentru a implementa corpul de buclă cel mai interior și măsurați impactul asupra performanței în raport cu metricile din partea c. Care este creșterea de viteză în comparație cu codul generat de compilator?
Paralelizați generatorul de seturi Mandelbrot utilizând OpenMP. Aplicați directiva parallel-for la bucla cea mai exterioară (rând).
a.
Măsurați numărul mediu de cicluri necesare pentru fiecare iterație a buclei celei mai interioare (pentru a evalua polinomul) pentru un fir și două fire pentru cadrul inițial. Folosiți aceste măsurători pentru a calcula creșterea vitezei, în termeni de pixeli pe secundă, a două fire față de un fir.
b.
Măsurați timpul de calcul al tuturor pixelilor din primul cadru atunci când se utilizează programarea dinamică în comparație cu programarea statică.
Ce face dificilă aplicarea operației SIMD pentru generatorul de seturi Mandelbrot? Care este cea mai eficientă metodă de aplicare a operației SIMD pentru generatorul de seturi Mandelbrot?
Măsurați debitul efectiv de scriere pentru Linux Framebuffer. Este acesta echivalent cu debitul de scriere pentru o matrice de memorie alocată din heap?
Calculați intensitatea aritmetică a programului de transformare a imaginii în operații pe pixel. Care este limita de performanță a acestuia având în vedere debitul efectiv de memorie al procesorului ARM? Cum se compară cu performanța dumneavoastră observată?
Utilizați OpenMP pentru a adăuga suport multicore la programul de transformare a imaginilor în virgulă fixă. Pentru a face acest lucru, aplicați pragma parallel for la bucla cea mai exterioară (rând).
Măsurați performanța sa pe un procesor ARM cu patru nuclee. Cum variază performanțele sale atunci când este executat cu unul, două, trei și patru fire?
Utilizați intrinseci pentru a adăuga suportul NEON SIMD la versiunea în virgulă fixă a programului de transformare a imaginilor. Utilizați operații cu patru căi pentru a calcula următoarele calcule pentru un grup de patru pixeli: localizarea pixelului sursă, extragerea fracțiunii și calculul ponderii. În ce măsură îmbunătățește acest lucru performanța?
Nu putem optimiza cu ușurință programul generator Mandelbrot folosind instrucțiuni SIMD, deoarece pixelii vecini pot necesita un număr diferit de evaluări ale polinomului și fiecare iterație a polinomului depinde de evaluarea anterioară. O abordare alternativă este de a implementa bucla în asamblare inline, de a o derula cu cel puțin patru și apoi de a utiliza pipelining-ul software pentru a îmbunătăți CPI-ul buclei. În acest caz, ar trebui să evităm ramurile condiționate în interiorul buclei derulate. Deoarece valorile c divergente vor continua să difere cu evaluările ulterioare, putem aștepta să verificăm condiția de ieșire din buclă după fiecare grup de patru iterații. Cu toate acestea, efectuarea unor evaluări polinomiale suplimentare după ce un Pc() diverge potențial în afara cercului cu raza 2 ne va cere să ținem cont de cerințele suplimentare de interval pentru formatul nostru în virgulă fixă. Recalculați cerințele de rază de acțiune în virgulă fixă pentru această optimizare și determinați în ce măsură acest lucru va reduce nivelul maxim de zoom.
Principalele avantaje ale virgulei fixe sunt reducerea latenței operațiilor și capacitatea de a evita conversiile de tip în anumite tipuri de coduri grafice. Capitolul 2 evidențiază un exemplu de program a cărui performanță este sensibilă la latența operațiilor, metoda lui Horner. Presupunând că putem tolera limitările de interval ale virgulă fixă în codul metodei lui Horner, conversia acestuia în virgulă fixă ar îmbunătăți performanța? Explicați-vă răspunsul.
Secțiunea 3.6.5 a prezentat două implementări diferite ale unei macro de preprocesor de adunare generalizată în virgulă fixă. Prima a fost generată de gcc în condiții de optimizare maximă, iar a doua a fost codificată manual folosind limbajul de asamblare inline. Ambele implementări au necesitat aproximativ același număr de instrucțiuni.
a.
Afirmați dependențele de date citite după scriere în ambele implementări. Presupunând că procesorul folosește o singură instrucțiune, în ordine de emitere, și presupunând că latența tuturor operațiilor aritmetice cu numere întregi este de patru cicluri, câte comparați numărul de cicluri de blocaj de date necesare pentru ambele implementări.
b.
Scrieți din nou versiunea de asamblare în linie a macroului de adunare în virgulă fixă pentru a programa instrucțiunile astfel încât instrucțiunile dependente să fie separate cât mai mult posibil. În ce măsură sunt reduse blocajele, presupunând latența dată în partea a?
c.
Scrieți un cod care să demonstreze modul în care toate cele trei implementări (generată de compilator, asamblare în linie și asamblare în linie programată) pot fi caracterizate din punct de vedere al performanței.
În această întrebare examinăm implementarea în asamblare inline a înmulțirii generalizate în virgulă fixă descrisă în secțiunea 3.6.6.
a.
Cum se compară, din punct de vedere al numărului de instrucțiuni și al performanței în timpul execuției, în comparație cu codul echivalent generat de compilator pentru:
res = ((((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2))) +(rp1>rp2? ((((long long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long long)op1 * (long long)op2) >> (rp2-1))&1)));
Asigură-te că folosești comutatoarele „-O3” și „-marm” atunci când compilezi cu gcc.
b.
Programați instrucțiunile din versiunea de asamblare în linie a macroului de multiplicare pentru a minimiza blocajele legate de dependența de date. Măsurați performanțele sale în raport cu versiunea dată în secțiunea 3.6.6.
c.
Pentru implementarea în asamblare inline, cât de mult se obține mai mult de-a lungul dacă se modifică astfel încât pozițiile punctului radix să fie fixe în loc de variabile ca în cod? Pentru această întrebare, utilizați atât numărul de instrucțiuni, cât și comportamentul real în timpul execuției.
Calcularea valorilor pixelilor pentru un set Mandelbrot necesită o funcție de conversie a numărului de iterații în canalele de culoare R, G și B. Setarea tuturor celor trei canale la aceeași valoare va genera o imagine gri, astfel încât panta fiecărei funcții a canalului de culoare trebuie să fie unică, iar oricare dintre pante este cea mai mare va determina nuanța imaginii.
După cum este descris în secțiunea 3.8.1, numărul de evaluări polinomiale poate depăși valoarea care depășește intervalul unui canal de culoare. Pentru a evita o potențială depășire, trebuie să utilizați aritmetica de saturație atunci când calculați valoarea fiecărui pixel. În acest fel, dacă valoarea calculată depășește valoarea maximă permisă, setați-o la valoarea maximă.
Scrieți o macro C care efectuează o multiplicare saturată fără semn pe 8 biți. Funcția va lua doi operanzi de 8 biți și va produce un produs de 8 biți setat la 255 dacă produsul depășește 255. Macroul nu trebuie să includă instrucțiuni de ramificare și să fie programat pentru dependențe de date.
Acest exercițiu va explora creșterea preciziei tipurilor de virgulă fixă pentru generatorul Mandelbrot la 64 de biți.
a.
Utilizând o rată de zoom de 1,5zoom, până la ce nivel poate fi mărit cadrul înainte de a depăși această precizie?
b.
Definiți un macro în C pentru adunarea a două (64,56) valori în virgulă fixă. Macroul poate efectua adunarea pe 128 de biți folosind patru adunări pe 32 de biți și poate folosi stegulețul de transport pentru a implementa transporturi de la fiecare grup de 32 de biți la următorul grup de 32 de biți cel mai semnificativ.
c.
Definiți un macro în C pentru înmulțirea a două (64,56) valori în virgulă fixă. Construiți această macro peste macroul de adunare pe 64 de biți din partea b.
După cum se arată în figura 3.6, o modalitate simplă de a efectua o înmulțire pe 64 de biți este de a efectua o serie de patru operații de înmulțire/schimbare/acumulare pe 32 de biți care produc fiecare un rezultat pe 64 de biți.
Figura 3.6. Un multiplicator pe 8 biți implementat cu multiplicatori pe 4 biți.
În figură, două valori pe 4 biți A și B care dețin valorile 1110 și 1410 sunt separate fiecare în două porțiuni superioare și inferioare pe 2 biți, numite A1, A0 și B1 și B0. Presupunând că produsele sunt pe 4 biți, produsul pe 8 biți este calculat ca (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Pentru a aplica acest lucru la o multiplicare pe 64 de biți, fiecare dintre cele două valori pe 64 de biți trebuie să fie reținută în două registre pe 32 de biți. Fiecare multiplicare generează un rezultat pe 64 de biți, ceea ce permite obținerea unui produs final pe 128 de biți.
d.
Utilizând aceste macroprograme, implementați un generator de seturi Mandelbrot pe 64 de biți și măsurați diferența de performanță rezultată.
e.
Implementați ambele macroprograme în limbajul de asamblare inline și măsurați creșterea vitezei de rezultat a generatorului Mandelbrot în comparație cu cea din partea d.
.