Tecniche di ottimizzazione
Tecniche per ridurre lo spazio
Un altro aspetto rilevante nell'ottimizzazione delle prestazioni dei programmi è ridurre la quantità di memoria utilizzata. Questo ha di riflesso un impatto positivo anche sul tempo di esecuzione, permettendo di sfruttare meglio le memorie cache.
Rappresentazioni sparse
Una prima tecnica che vedremo sono le rappresentazioni sparse, in cui si evita di rappresentare informazioni ridondati. Un esempio tipico sono le
matrici sparse, ampiamente diffuse nell'ambito del calcolo scientifico, in cui la maggior parte delle celle sono poste a zero.
Esempio. Consideriamo la seguente matrice 4x4:
Deprecated: Function split() is deprecated in /home/demetres/public_html/didattica/ae/actions/table.php on line 26
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/safehtml.php on line 308
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 159
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 161
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 162
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 163
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 165
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 166
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 167
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 243
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 250
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 259
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 266
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 273
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 280
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 467
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 469
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 471
| 0 |
1 |
3 |
0 |
| 0 |
0 |
0 |
0 |
| 0 |
6 |
0 |
0 |
| 5 |
0 |
1 |
3 |
Notiamo che la matrice ha 4x4=16 celle, di cui solo 6 sono poste a un valore diverso da zero. Sarebbe desiderabile una rappresentazione della matrice in cui si occupa spazio solo per le celle non zero. Mostriamo ora una rappresentazione che, data una matrice nxn con k celle diverse da zero, usa spazio O(n+k).
La rappresentazione si basa su tre array:
- val, di dimensione k, che rappresenta i valori non zero che si incontrano scorrendo la matrice per righe. Nel nostro esempio si ha: val = [1, 3, 6, 5, 1, 3].
- col, di dimensione k, tale che col[i] specifica la colonna della matrice che contiene il valore val[i]. Nel nostro esempio si ha: col = [1, 2, 1, 0, 2, 3].
- row, di dimensione n+1, tale che [row[i], row[i+1]-1] sia l'intervallo degli indici di val che contengono i valori sulla riga i-esima della matrice. Nel nostro esempio si ha: row = [0, 2, 2, 3, 6]. Si noti che la riga di indice 1 ha tutti gli elementi a zero e quindi non ci sono elementi tra row[1]=2 e row[2]-1=1.
Un oggetto matrice sparsa può essere rappresentato in C come segue:
typedef struct {
int n, k;
int* row; // array di dimensione n+1
int* col; // array di dimensione k
double* val; // array di dimensione k
} sparse_matrix;
Esempio. Mostriamo ora come usare la rappresentazione sparsa per calcolare un prodotto matrice-vettore della forma y=Ax, dove x e y sono due vettori colonna di dimensione n e A è una matrice nxn. Questo esempio illustra il principio per cui "il miglior modo per velocizzare un calcolo è non calcolare affatto". Nel nostro caso, non calcoleremo prodotti di elementi che coinvolgono fattori pari a zero della matrice. La seguente funzione calcola il prodotto matrice-vettore Ax e lo pone in y:
void sparse_mat_vec_prod
(sparse_matrix* A,
double* x,
double* y
) {
int i, q;
for (i=
0; i<A->n; i++
) {
y
[i
] =
0;
for (q=A->row
[i
]; q<A->row
[i
+1]; q++
)
y
[i
] += A->val
[q
] * x
[A->col
[q
]];
}
}
Packing e codifica
Un'altra tecnica per ridurre lo spazio consiste nel cercare di usare i bit disponibili in modo ottimale. Una tecnica molto usata è il
bit stealing, che consiste nel "rubare" dei bit da oggetti esistenti in cui non tutti i bit sono realmente utili. Ad esempio, è possibile sfruttare il fatto che i puntatori restituiti da
malloc su macchine a 64 bit puntano a indirizzi di oggetti allineati a multipli di (almeno) 8 byte, e pertanto i tre bit meno significativi dei un puntatore sono certamente sempre posti a zero. E' quindi possibile sfruttare questi bit "liberi" per memorizzare informazioni aggiuntive.
Esempio. Consideriamo ad esempio il problema di mantenere una lista collegata semplice contenente in ciascun nodo un campo info di tipo long e un flag booleano, oltre al puntatore al prossimo nodo della lista:
typedef struct node {
long info;
char flag;
struct node* next;
} node;
Si noti che
sizeof(node) è pari a 8+8+8=24 byte (8 per info + 1 per flag + 7 di padding + 8 per next). Usando il bit stealing possiamo "rubare" il bit meno significativo di
next per rappresentare il flag booleano. Assumendo che
sizeof(long) == sizeof(void*), e cioè un
long abbia la stessa dimensione di un puntatore, possiamo riscrivere la struttura come segue:
typedef struct node {
long info;
long flag_next;
} node;
dove
flag_next è una rappresentazione compatta dei campi
flag e del puntatore
next della rappresentazione originaria. Si noti che ora la struttura occupa 16 byte, senza alcun padding.
Abbiamo ottenuto un risparmio di oltre il 30% sullo spazio!
Per accedere ai campi "logici" dell'oggetto, è possibile usare delle funzioni o delle macro. Ad esempio, le seguenti funzioni fungono da "setter" e "getter" per i campi logici flag e next:
int get_flag(node* p) {
return p->flag_next & 1;
}
node* get_next(node* p) {
return (node*)(p->flag_next & ~1)
}
void set_flag(node* p, char b) { // precondizione: b = 0 oppure b = 1
p->flag_next = (long)get_next(p) | b;
}
void set_next(node* p, node* n) { // precondizione: n è un indirizzo pari
p->flag_next = get_flag(p) | (long)(n);
}
Si noti che in C l'operatore binario
& effettua l'AND bit a bit dei suoi operandi, mentre l'operatore unario
~ calcola il complemento a 1 del suo operando (inverte tutti i suoi bit).
In alternativa, possiamo usare macro, che effettuano l'inlining esplicitamente:
#define get_flag(p) ((p)->flag_next & 1)
#define get_next(p) ((node*)((p)->flag_next & ~1))
#define set_flag(p,b) ((p)->flag_next = (long)get_next(p) | (b))
#define set_next(p,n) ((p)->flag_next = get_flag(p) | (long)(n))
dove
p è un puntatore di tipo
node*. Usando funzioni o macro, scriveremo ad esempio
set_next(p,q); invece di
p->next = q;.
Ordinamento dei campi di una struct
Poiché in C i campi di una struttura sono allineati a multipli della loro dimensione e appaiono in memoria nello stesso ordine in cui sono dichiarati, in alcuni casi è possibile ridurre lo spazio semplicemente riordinandoli in modo da minimizzare lo spazio usato nel padding. Questo tipo di ottimizzazione deve essere necessariamente effettuato dal programmatore.
Esempio. La struttura:
struct S {
char a;
long b;
char c;
long d;
char e;
};
occupa 40 byte (1 per a + 7 di padding + 8 per b + 1 per c + 7 di padding + 1 per e + 7 di padding), di cui 19 di payload (spazio effettivamente in uso per i campi della struttura) e 21 di padding. Riordinando i campi come segue:
struct S {
long b;
long d;
char a;
char c;
char e;
};
lo spazio si riduce a soli 24 byte (8 per b + 8 per d + 1 per a + 1 per c + 1 per e + 5 di padding), di cui 5 di padding.
La riduzione di spazio dovuta a un semplice riordino dei campi è del 40%!
Tecniche per sfruttare il parallelismo
Vettorizzazione
La vettorizzazione è una tecnica che consente di effettuare in parallelo la stessa operazione su tutti gli elementi di un vettore. Viene realizzata mediante architetture SIMD (single-instruction multiple-data). I processori x86 sono muniti di unità SIMD che consentono il calcolo vettorizzato. In particolare:
- MMX∞, introdotto da Intel nel 1997 nella serie di processori Pentium
- 3DNow!∞ introdotto da AMD nel 1998 con il processore AMD K6-2
- SSE∞ (Streaming SIMD Extensions), introdotto da Intel nel 1999 con il Pentium III. Estensioni successive dell'SSE hanno portato al SSE2, SSE3, SSSE3, and SSE4.
- AVX∞ (Advanced Vector Extensions), che estende ulteriormente l'SSE, introdotto da Intel nel 2008 e supportato a partire dal 2011 nei processori Intel Sandy Bridge e AMD Bulldozer.
L'estensione SSE del set x86 prevede 8 registri a 128 bit dedicati, chiamati
xmm0-
xmm7. I processori a 64 bit forniscono ulteriori 8 registri a 128 bit (
xmm8-
xmm15). L'AVX estende i 16 registri SSE portandoli a 256 bit e chiamandoli
ymm0–
ymm15, di cui i 128 bit meno significativi sono ancora accessibili mediante i nomi
xmm0-
xmm15.
Vi sono decine di nuove istruzioni vettoriali che estendono il set di istruzioni x86, che possono essere usate nei programmi come se fossero chiamate a funzioni mediante gli
intrinsics∞, cioè particolari costrutti che il compilatore riconosce e mappa direttamente su codice assembly.
Vediamo un esempio di uso degli intrinsics, assumendo di avere un processore equipaggiato con estensione SSE4.1. Si consultino le guide
Intel∞ e
MSDN∞ per ulteriori informazioni sull'uso degli instrinsics.
Esempio. Somma vettoriale di 4 interi a 32 bit:
#include <stdio.h>
#include <smmintrin.h>
void sum
(int a
[4],
int b
[4],
int c
[4]) {
__m128i ap, bp, cp;
// variabili di tipo __m128i vengono mappate su registri SSE a 128 bit
ap = *
(__m128i*
)a;
// copia i 16 byte all'indirizzo a in una variabile SSE
bp = *
(__m128i*
)b;
// copia i 16 byte all'indirizzo b in una variabile SSE
cp = _mm_add_epi32
(ap,bp
);
// calcola la somma vettoriale di ap e bp, ciascuno contenente 4 interi a 32 bit e scrive il vettore risultante in cp
*
(__m128i*
)c = cp;
// copia i 16 byte della variabile SSE cp all'indirizzo b
}
int main
() {
int a
[4] =
{ 1,
2,
3,
4 };
int b
[4] =
{ 10,
20,
30,
40 };
int c
[4];
sum
(a, b, c
);
printf("%d %d %d %d\n", c
[0], c
[1], c
[2], c
[3]);
return 0;
}
Per compilare il programma, usare la riga di comando
gcc includendo l'opzione
-msse4.1:
$ gcc sum.c -O2 -msse4.1 -o sum
Si noti che la funzione
sum viene tradotta da
gcc in modo molto compatto come segue:
_sum: # rdi <-> a, rsi <-> b, rdx <-> c
movdqa (%rdi), %xmm0 # copia i 16 byte all'indirizzo rdi nel registro xmm0
paddd (%rsi), %xmm0 # effettua la somma vettoriale dei 4 interi a 32 bit all'indirizzo rsi e di quelli in xmm0 e mette il risultato in xmm0
movdqa %xmm0, (%rdx) # copia i 16 byte del registro xmm0 all'indirizzo rdx
ret
Caso di studio: prodotto di matrici
Versione base, con loop i, j, k:
void mat_mul_ijk(int** a, int** b, int** c, unsigned n) {
long i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
c[i][j] = 0;
for (k = 0; k < n; k++)
c[i][j] += a[i][k]*b[k][j];
}
}
Versione base, con loop i, j, k e variabile accumulatore nel ciclo interno:
void mat_mul_ijk_sum(int** a, int** b, int** c, unsigned n) {
long i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
int sum = 0;
for (k = 0; k < n; k++)
sum += a[i][k]*b[k][j];
c[i][j] = sum;
}
}
Versione con trasposizione di matrice:
static _mat_transpose(int** m, unsigned n);
void mat_mul_ijk_trans(int** a, int** b, int** c, unsigned n) {
long i, j, k;
_mat_transpose(b, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
int sum = 0;
for (k = 0; k < n; k++)
sum += a[i][k]*b[j][k];
c[i][j] = sum;
}
_mat_transpose(b, n);
}
static _mat_transpose(int** m, unsigned n) {
long i, j;
for (i = 0; i<n; i++)
for (j = i+1; j<n; j++) {
int temp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = temp;
}
}
Versione con ciclo i, k, j:
void mat_mul_ikj(int** a, int** b, int** c, unsigned n) {
long 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++) {
int aik = a[i][k];
for (j = 0; j < n; j++)
c[i][j] += aik * b[k][j];
}
}
Versione con ciclo i, k, j e vettorizzazione SSE:
void mat_mul_ikj_sse(int** a, int** b, int** c, unsigned n) {
long 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++) {
int aik = a[i][k];
for (j = 0; j < n-3; j+=4) {
__m128i ap = _mm_set_epi32(aik,aik,aik,aik);
__m128i bp = *((__m128i*)&b[k][j]);
__m128i cp = *((__m128i*)&c[i][j]);
bp = _mm_mullo_epi32(ap,bp);
cp = _mm_add_epi32(cp,bp);
*((__m128i*)&c[i][j]) = cp;
}
for (; j<n; j++) c[i][j] += a[i][k]*b[k][j];
}
}
Versione con ciclo i, j, k, trasposizione e vettorizzazione SSE:
static void mat_mul_ijk_trans_sse(int** a, int** b, int** c, unsigned n) {
long i, j, k;
_mat_transpose(b, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
__m128i sump = _mm_set_epi32(0,0,0,0);
for (k = 0; k < n-3; k+=4) {
__m128i ap = *((__m128i*)&a[i][k]);
__m128i bp = *((__m128i*)&b[j][k]);
bp = _mm_mullo_epi32(ap,bp);
sump = _mm_add_epi32(sump,bp);
}
int sum = 0;
for (; k<n; k++) sum += a[i][k]*b[j][k];
c[i][j] = sum+((int*)&sump)[0]+
((int*)&sump)[1]+
((int*)&sump)[2]+
((int*)&sump)[3];
}
_mat_transpose(b, n);
}
Versione con ciclo i, k, j, vettorizzazione SSE e 2 thread:
typedef struct {
int **a, **b, **c;
unsigned n;
long from, to;
} _data_pack;
static void* _pthread_func(void* p) {
// unpack parameters
_data_pack* d = (_data_pack*)p;
int **a = d->a, **b = d->b, **c = d->c;
unsigned n = d->n;
long i, j, k;
for (i = d->from; i < d->to; i++)
for (j = 0; j < n; j++) c[i][j] = 0;
for (i = d->from; i < d->to; i++)
for (k = 0; k < n; k++) {
int aik = a[i][k];
for (j = 0; j < n-3; j+=4) {
__m128i ap = _mm_set_epi32(aik,aik,aik,aik);
__m128i bp = *((__m128i*)&b[k][j]);
__m128i cp = *((__m128i*)&c[i][j]);
bp = _mm_mullo_epi32(ap,bp);
cp = _mm_add_epi32(cp,bp);
*((__m128i*)&c[i][j]) = cp;
}
for (; j<n; j++) c[i][j] += a[i][k]*b[k][j];
}
return NULL;
}
void mat_mul_ikj_sse_2thread(int** a, int** b, int** c, unsigned n) {
pthread_t t1, t2;
int res1, res2;
_data_pack dp1 = { a, b, c, n, 0, n/2 };
_data_pack dp2 = { a, b, c, n, n/2, n };
res1 = pthread_create(&t1, NULL, _pthread_func, (void*)&dp1);
res2 = pthread_create(&t2, NULL, _pthread_func, (void*)&dp2);
assert(res1 == 0 && res2 == 0);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
}
e con 4 thread:
void mat_mul_ikj_sse_4thread(int** a, int** b, int** c, unsigned n) {
pthread_t t1, t2, t3, t4;
int res1, res2, res3, res4;
_data_pack dp1 = { a, b, c, n, 0, n/4 };
_data_pack dp2 = { a, b, c, n, n/4, n/2 };
_data_pack dp3 = { a, b, c, n, n/2, 3*n/4 };
_data_pack dp4 = { a, b, c, n, 3*n/4, n };
res1 = pthread_create(&t1, NULL, _pthread_func, (void*)&dp1);
res2 = pthread_create(&t2, NULL, _pthread_func, (void*)&dp2);
res3 = pthread_create(&t3, NULL, _pthread_func, (void*)&dp3);
res4 = pthread_create(&t4, NULL, _pthread_func, (void*)&dp4);
assert(res1 == 0 && res2 == 0 && res3 == 0 && res4 == 0);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
pthread_join(t3, NULL);
pthread_join(t4, NULL);
}
Analisi delle prestazioni dei programmi
Principio di Pareto
Il principio di Pareto stabilisce che l'80% degli effetti è da imputare al 20% delle cause. Questa osservazione si riscontra in diversi contesti, fra cui:
- l'80% del territorio italiano è di proprietà del 20% della popolazione (Pareto)
- l'82.7% del reddito mondiale è concentrato sul 20% dei più ricchi (Human Development Report)
- l'80% degli introiti di un'azienda proviene dal 20% dei clienti
- l'80% dei crash di un programma si risolvono correggendo il 20% dei bug (Microsoft)
- l'80% del tempo di esecuzione di programma è speso nel 20% del codice
Quest'ultima osservazione implica che il processo di ottimizzazione delle prestazioni di un programma deve focalizzarsi su quel 20% che conta.
Legge di Amdahl
La legge di Amdahl stabilisce lo
speedup totale che è possibile ottenere ottimizzando una singola porzione di un programma. La legge è dovuta al pioniere dell'informatica
Gene Amdahl∞. La legge permette di rispondere a domande del tipo: "se dimezzassimo il tempo di esecuzione di una porzione di codice responsabile del 50% del tempo totale di esecuzione in un programma, di quanto ridurremmo il tempo totale stesso?". Nella sua forma più generale, la legge di Amdahl può essere espressa come segue.
Sia T il tempo totale di esecuzione di un programma e sia a la frazione di tempo richiesta da una sua porzione X, con a in [0,1]. Inoltre, sia T' il tempo totale di esecuzione del programma dopo aver ridotto di un fattore k il tempo richiesto dalla porzione X. Lo speedup totale del programma dovuta all'ottimizzazione è:
T/T' = 1/(a/k+1-a)
Dimostrazione: Partiamo dall'identità: T=aT+(1-a)T, dove aT è il tempo richiesto da X. Riducendo aT di un fattore k, otteniamo il tempo T'=aT/k+(1-a)T. Il rapporto T/T' è pertanto T/T'=T/[aT/k+(1-a)T]=1/(a/k+1-a).
Si noti che, per k che tende all'infinito, T/T'=1/(1-a) è il massimo speedup che si può ottenere agendo su una porzione del codice responsabile di una frazione a del tempo totale di esecuzione di un programma.
Esempio: per a=0.4 e k=2 stiamo dimezzando il tempo richiesto da una parte X del programma responsabile del 40% del tempo totale. Lo speedup complessivo che otteniamo è: T/T'=1/(0.4/2+1-0.4)=1/(0.2+0.6)=1/0.8=1.25x. Se anche portassimo a zero il tempo richiesto dalla porzione X, agendo solo su X lo speedup non potrebbe superare T/T'=1/(1-a)=1/0.6<1.67.
Profiling delle prestazioni: uso del tool gprof
Esempio visto a lezione.
#include <string.h>
#include <stdlib.h>
#define M 1000000000
#define N 10000
void init(int *v, int n) {
memset(v, n*sizeof(int), 255);
}
void A(int *v, int n) {
int i = 0;
for (i=0; i<n; i++) v[i] >>= 1; // shift a destra di 1 di v[i] = divisione per due di v[i]
}
void B(int *v, int n) {
int i = 0;
for (i=0; i<n; i++) v[i] /= 2; // divisione per due di v[i]
}
int main() {
int* v = malloc(N*sizeof(int)), i;
init(v, N);
for (i=0; i<M/N; i++) {
A(v, N);
B(v, N);
}
free(v);
return 0;
}