Esercizi di preparazione all'esame: programmazione parallela
Esercizio 1 (Somma array vettorizzata)
Riscrivere la funzione
sum nel seguente programma in modo da usare vettorizzazione SSE o AVX:
#include <stdio.h>
void sum(int a[8], int b[8], int c[8]) {
int i;
for (i=0; i<8; i++) c[i] = a[i] + b[i];
}
int main() {
int a[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
int b[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
int c[8];
sum(a, b, c);
printf("%d %d %d %d %d %d %d %d\n", c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7]);
return 0;
}
Includere la header
immintrin.h e usare
-mavx2 (per AVX2) o
-msse4.2 (per SSE 4.2) sulla riga di comando
gcc.
Esercizio 2 (Prodotto matrici ikj vettorizzato)
Scrivere una variante della seguente funzione C usando vettorizzazione SSE o AVX:
void matmul_ikj(const int** A, const int** B, int** C, size_t n) {
int i,j,k;
for (i=0; i<n; i++)
for (j=0; j<n; j++) C[i][j] = 0;
for (i=0; i<n; i++)
for (k=0; k<n; k++)
for (j=0; j<n; j++)
C[i][j] += A[i][k]*B[k][j];
}
E' possibile assumere che i puntatori in A, B, e C siano tutti allineati a multipli di 16 (ma non 32) byte. Confrontare sperimentalmente le prestazioni della versione non vettorizzata con quella vettorizzata usando il comando
time da shell.
Esercizio 3 (Filtri grafici vettorizzati)
Scrivere una funzione
void pixelize_vect(const unsigned char* A, unsigned char* B, size_t w, size_t h) che, data un'immagine A a toni di grigio rappresentata in formato row-major (cioè le righe appaiono consecutivamente in memoria), crea un'altra immagine B delle stesse dimensioni e con la stessa rappresentazione dove il pixel di coordinate (i,j) in B è ottenuto come massimo dei valori dei pixel di A nella finestra di dimensioni 5x5 centrata in (i,j), dove i è l'indice di riga e j quello di colonna. Escludere dal calcolo del massimo i pixel che escono dai bordi. Realizzare la funzione usando vettorizzazione SSE.
Si parta dalla seguente funzione che realizza l'operazione in modo sequenziale:
#define M(mat,i,j,rows) ((mat)[(i)*(w)+(j)])
#define MIN5 2
#define MAX5 3
void pixelize(const unsigned char* A, unsigned char* B, size_t w, size_t h){
int i, j, ii, jj;
for (i=0; i<h; i++)
for (j=0; j<w; j++) {
unsigned m = 0;
for (ii=i-MIN5; ii<i+MAX5; ii++)
for (jj=j-MIN5; jj<j+MAX5; jj++) {
if (ii<0 || ii>=h || jj<0 || jj>=w) continue;
unsigned v = M(A,ii,jj,w);
if (v>m) m=x;
}
M(B,i,j,w) = m;
}
}
Scaricare e completare il
pacchetto software. Usare
make per compilare e
make run per eseguire.
- Suggerimento: utilizzare gli intrinsic _mm_loadu_si128 per caricare dati da memoria a registro SSE, _mm_max_epu8 per calcolare il massimo di unsigned char e _mm_store_si128 per trasferire dati da registro SSE a memoria. Includere "smmintrin.h" e compilare con l'opzione -msse4.1.
Soluzione:
void pixelize_vect(const unsigned char* A, unsigned char* B, size_t w, size_t h){
int i, j, ii, jj;
for (i=0; i<h; i++)
for (j=0; j<w; j++) {
unsigned m = 0;
// use sequential version near the border
// j-MIN5+16 ensures there is room for loading 16 bytes,
// and not just 5 in the current window centered in (i,j)
if (j-MIN5 < 0 || j-MIN5+16 >= w || i-MIN5 <0 || i+MAX5 >= h)
for (ii=i-MIN5; ii<i+MAX5; ii++)
for (jj=j-MIN5; jj<j+MAX5; jj++) {
if (ii<0 || ii>=h || jj<0 || jj>=w) continue;
unsigned v = M(A,ii,jj,w);
if (v>m) m=v;
}
else {
__m128i a, max = { 0 };
unsigned char p[16] __attribute__((aligned(16)));
a = _mm_loadu_si128 ((__m128i const*)&M(A,i-MIN5, j-MIN5,w));
max = _mm_max_epu8 (max, a);
a = _mm_loadu_si128 ((__m128i const*)&M(A,i-MIN5+1,j-MIN5,w));
max = _mm_max_epu8 (max, a);
a = _mm_loadu_si128 ((__m128i const*)&M(A,i-MIN5+2,j-MIN5,w));
max = _mm_max_epu8 (max, a);
a = _mm_loadu_si128 ((__m128i const*)&M(A,i-MIN5+3,j-MIN5,w));
max = _mm_max_epu8 (max, a);
a = _mm_loadu_si128 ((__m128i const*)&M(A,i-MIN5+4,j-MIN5,w));
max = _mm_max_epu8 (max, a);
_mm_store_si128 ((__m128i*)p, max);
if (p[0]>m) m = p[0];
if (p[1]>m) m = p[1];
if (p[2]>m) m = p[2];
if (p[3]>m) m = p[3];
if (p[4]>m) m = p[4]; // ignore p[5] through p[15]
}
M(B,i,j,w) = m;
}
}
Esercizio 4 (Filtri grafici vettorizzati)
Migliorare ulteriormente la soluzione dell'esercizio 3 scrivendone una variante multi-core basata su
POSIX thread. La soluzione deve utilizzare simultaneamente vettorizzazione e multi-threading.
- Suggerimento: scomporre la matrice in blocchi processati in parallelo da thread diversi. Può essere utile scrivere prima una versione multi-thread senza vettorizzazione.
Esercizio 5 (Raddoppiamento di immagini in OpenCL)
Lo scopo dellesercizio è quella di scrivere un modulo C che, data in input una immagine a toni 256 di grigio di dimensione w×h, crei una nuova immagine allocata dinamicamente ottenuta da quella di input raddoppiandone altezza e larghezza. [
Testo esercizio |
Codice e soluzioni]