C++ & OpenMP

Molto spesso a causa del mio lavoro mi trovo a dover implementare particolare algoritmi euristici sviluppati dal gruppo di ricerca con cui lavoro. Altrettanto spesso queste euristiche devono essere confrontate con la controparte esaustiva (o a forza bruta) per poter stimare quali sono i reali vantaggi nell’utilizzo dell’euristica rispetto ad un approccio a forza bruta. Fondamentalmente si è interessati a confrontare il rapporto qualità della soluzione rispetto al tempo “risparmiato” al crescere della dimensione del problema. Recentemente mi è capitato di dover lavorare su un problema la cui dimensione cresceva esponenzialmente rispetto ai dati di ingresso: come è facile immaginare la ricerca di una soluzione esaustiva diventava impraticabile (considerando i tempi necessari per poterla ricavare) anche con relativamente pochi dati iniziali. Proprio per questo ho fatto una veloce ricerca per vedere se riuscivo a trovare una libreria che mi permettesse con poco sforzo di parallelizzare l’algoritmo esaustivo in modo da poter sfruttare gli otto thread paralleli (ripartiti su 4 processori) disponibili sul mio Intel core i7 Q720.

Sono stato fortunato due volte:

• prima fortuna: mi sono imbattuto in questa API: OpenMP (The OpenMP API specification for parallel programming);
• seconda fortuna: viene supportata sia da MS Visual C++ (dalla versione 2005) che da GCC… anche se sotto Visual C++ non è possibile utilizzare la versione più recente (la 3.0) ma solamente la (2.0).

OpenMP mi è sembrata subito una risposta interessante al mio problema iniziale e quindi ho deciso di provarla sul campo e ne sono rimasto piacevolmente soddisfatto. Non potendo riportare qui quello su cui sto lavorando (l’articolo non è ancora uscito) vi presenterò un esempio ad hoc e vedremo come “modificarlo” (operazione necessaria utilizzando la versione 2.0 di OpenMP) e analizzeremo i miglioramenti di prestazioni ottenuti.

Differenze tra la versione 2.0 e la 3.0

Tra la versione 2.0 e la versione 3.0 esistono molte differenze anche significative. Le principali sono elencate brevemente di seguito:

• è stato aggiunto il concetto di Task (inteso come: una specifica istanza di codice eseguibile e il suo ambiente di esecuzione) e le relative funzioni per gestirlo;
• dalla versione 3.0 OpenMP supporta l’accesso atomico alla memoria;
• l’algoritmo per decidere quanti thread utilizzare in una parallel region è stato migliorato;
• dalla versione 3.0 OpenMP supporta l’utilizzo delle variabili di tipo unsigned integer e dei random access iterator nei loop;

Per una più precisa analisi di quanto è cambiato, vi rimando alla sezione successiva, dove potrete trovare il link alle specifiche complete di OpenMP 3.0 😉

Il codice di prova

L’idea base di questo prova è quello di “simulare” una enumerazione a forza bruta di uno spazio delle soluzioni relativamente vasto per analizzare i benefici apportati dall’utilizzo di OpenMP. Affinché il compilatore non decida di eliminare di sua volontà parti di codice che in realtà “non fanno nulla” il ciclo di enumerazione è in realtà composto da 3 cicli nidificati di cui il secondo viene eseguito un numero casuale di volte.

Il codice è il seguente (STANDARD STL VERSION – SSV):

// macro per la gestione dei numeri casuali (solitamente definite in un header separato)
#define RND_DOUBLE_0_1()         ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) )
#define RND_T_RANGE(T, MIN, MAX) ( (T)( (MAX - MIN + 1)*( RND_DOUBLE_0_1() ) + MIN ) )

void creareTestVector(vector &V, const int &Num) {
     for(int i = 0; i < Num; ++i) {
         V.push_back( RND_T_RANGE(int, 1, 10) );
     }
}

void test(const size_t &ProblemDimension, double &DiffTimeCreation, double &NumOfOpsCreation, double &DiffTimeEvaluation, double &NumOfOpsEvaluation, double &Total) {
    vector V1;
    vector V2;

    // *A*
    creareTestVector(V1, ProblemDimension);
    creareTestVector(V2, ProblemDimension);
    // *B*

    // *C*
    const vector::const_iterator V1End = V1.end();
    const vector::const_iterator V2End = V2.end();
    for(vector::iterator i = V1.begin(); i != V1End; ++i) {
        for(int t = 0; t < *i; ++t) {
            for(vector::iterator j = V2.begin(); j != V2End; ++j) {
                Total += *j;
            }
        }
    }
    // *D*
}

Questo codice ci permetterà di misurare le prestazioni tra i punti A-B e tra i punti C-D (quelli dove è presente il maggior carico di lavoro) e, successivamente, ci permetterà di confrontare i risultati ottenuti da questa versione “liscia” del codice quelli ottenuti utilizzando OpenMP. Le prestazioni saranno misurate in numero di operazioni per ms.

La versione rivista per OpenMP 2.0

Come già detto Visual C++ 2008  (ma anche 2010) supporta solo la versione 2.0 di OpenMP e questa versione non permette di utilizzare gli iteratori nei cicli, oltre a non permettere l’utilizzo del metodo push_back() della classe vector dentro ad un ciclo da ottimizzare (la versione 3.0 dovrebbe risolvere per certo almeno il primo problema). Questo comporta un piccolo lavoro di adattamento del codice prima presentato (STL ARRAY VERSION – SAV). Nel seguente codice sono state evidenziate le parti coinvolte nell’adattamento:

void creareTestVector(vector &V, const int &Num) {
    V.resize(Num);

    for(int i = 0; i < Num; ++i) {
        V[i] = RND_T_RANGE(int, 1, 10);
    }
}

void test(const size_t &ProblemDimension, double &DiffTimeCreation, double &NumOfOpsCreation, double &DiffTimeEvaluation, double &NumOfOpsEvaluation, double &Total) {
    vector V1;
    vector V2;

    creareTestVector(V1, ProblemDimension);
    creareTestVector(V2, ProblemDimension);

    const size_t V1End = V1.size();
    const size_t V2End = V2.size();
    for(int i = 0; i < V1End; ++i) {
        const int TEnd = V1[i];
        for(int t = 0; t < TEnd; ++t) {
            for(int j = 0; j <V2End; ++j) {
                Total += V2[j];
            }
        }
    }
}

Ora bisogna capire quali sono le parti di programma che si possono parallelizzare.

Solitamente i punti più promettenti sono i cicli e le parti di codice che non interagendo tra di loro possono essere eseguite in parallelo. Osservando il codice precedente si  nota subito, quindi, che i punti di interesse sono:

• il for della funzione creareTestVector alla riga 4;
• le due chiamate alla funzione creareTestVector (righe 13 e 14) all’interno della funzione test;
• il for più esterno della funzione test alla riga 18.

Da questa veloce analisi si ricava la seguente versione del codice (OpenMP VERSION – OMPV), in cui sono evidenziati i punti modificati:

void creareTestVector(vector &V, const int &Num) {
    V.resize(Num);

    #pragma omp parallel for
    for(int i = 0; i < Num; ++i) {
        V[i] = RND_T_RANGE(int, 1, 10);
    }
}

void test(const size_t &ProblemDimension, double &DiffTimeCreation, double &NumOfOpsCreation, double &DiffTimeEvaluation, double &NumOfOpsEvaluation, double &Total) {
    vector V1;
    vector V2;

    #pragma omp parallel sections
    {
        #pragma omp section
        creareTestVector(V1, ProblemDimension);

        #pragma omp section
        creareTestVector(V2, ProblemDimension);
    }

    const size_t V1End = V1.size();
    const size_t V2End = V2.size();

    double TmpTotal = 0.0;
    #pragma omp parallel for reduction (+:TmpTotal)
    for(int i = 0; i < V1End; ++i) {
        const int TEnd = V1[i];
        for(int t = 0; t < TEnd; ++t) {
            for(int j = 0; j <V2End; ++j) {
                TmpTotal += V2[j];
            }
        }
    }
    Total = TmpTotal;
}

Come è facile intuire alla riga 4 si è detto al compilatore che il for della riga successiva può essere parallelizzato senza particolari precauzioni. La modifica alle righe da 14 a 21, invece, asseriscono che le due chiamate alla funzione creareTestVector possono essere eseguite in parallelo anche qui senza particolari precauzioni.
Molto più interessante, invece, è la riga 27. Anche qui viene detto ad OpenMP che il for più esterno può essere parallelizzato, ma in questo caso bisogna prestare particolare attenzione alla variabile TmpTotal che è può essere modificata dai vari thread. Infatti, l’ultima parte del comando (reduction (+:TmpTotal)) istruisce OpenMP a creare una variabile locale ad ogni thread parallelo e alla fine di eseguire una riduzione di queste variabili locali nella variabile TmpTotal attraverso un’operazione di somma.

I risultati

Per analizzare l’effettivo miglioramento derivante dall’utilizzo di OpenMP sono stati eseguiti una serie di esperimenti con diverse configurazioni, sia con la “classica” compilazione a 32bit (architettura x86) che con compilazione a 64bit (architettura IA-64t).

Per entrambe le architetture si sono analizzate le prestazioni del codice relativo alla versione STL con iteratori (SSV), alla versione che utilizza STL con accesso ad array (SAV) e infine con la versione OpenMP (OMPV); per quest’ultima relativamente con una parallelizzazione a 2, 4, 8 thread. Per ogni configurazione sono stati eseguiti dieci esperimenti e i grafici rappresentano la media dei singoli risultati.

x86 - Analisi Prestazioni

IA-64t - Analisi Prestazioni

I primi due grafici rappresentano l’analisi di prestazioni per le architetture x86 e IA-64t.

La serie di istogrammi sulla sinistra di ciascun grafico rappresentano le prestazioni della parte di inizializzazione delle strutture dati (i.e., le 2 chiamate alla funzione creareTestVector ). Se guardiamo il grafico per l’architettura x86, si nota come effettivamente le prestazioni raddoppino (da circa 20000 operazioni/ms a circa 40000 operazioni/ms); è interessante notare che nel caso OpenMP le prestazioni sono costanti indipendentemente dal numero di thread utilizzati. Per l’architettura IA-64t le considerazioni sono analoghe e le prestazioni anche (solo leggermente superiori); in questo caso è interessante notare come il non utilizzare la funzione push_back() della classe vector porti ad un aumento di prestazioni abbastanza ragguardevole (da circa 20000 operazioni/ms a circa 35000 operazioni/ms).

La serie di istogrammi sulla destra, invece, rappresentano le prestazioni della parte di “calcolo effettivo” dell’esperimento. Guardando entrambi i grafici ci si accorge immediatamente come l’utilizzo delle funzionalità di OpenMP porti ad un effettivo guadagno in termini di potenza pura di calcolo: nel caso dell’architettura x86 dalle circa 100000 operazioni/ms della versione SSV alle circa 950000 operazioni/ms nel caso dell’utilizzo di tutti gli 8 thread paralleli della CPU di riferimento. Un guadagno di 9.5 volte. Per l’architettura IA-64t si va da circa 210000 a circa 1050000 operazioni/ms: un guadagno di 5 volte. Molto interessante, anche il fatto, che nell’architettura x86 il fatto di non usare gli iteratori per accedere alla classe vector porti  quasi al raddoppio delle prestazioni.

x86 - Analisi Prestazioni con Ottimizzazioni VS 2008

IA-64t - Analisi Prestazioni con Ottimizzazioni VS 2008

Questo secondo gruppo di grafici, invece, sono una specie di omaggio 😉 Ho eseguito l’analisi di prestazioni utilizzando il profiler presente in Visual Studio 2008. Questo utile strumento funziona in due passi. Nel primo si crea una versione speciale del codice per eseguire l’analisi delle prestazioni del codice stesso. Il profiler memorizza per ogni funzione quante volte è stata chiamata, quanto tempo è stata speso per eseguirla sia in assoluto che rispetto al tempo d’esecuzione dell’intero programma, e altre informazioni ancora. Nel secondo passo, il compilatore utilizzando le informazioni raccolte precedentemente sceglie quali funzioni vanno ottimizzate e in che modo.

I risultati di queste ultime analisi sono stati molto interessanti e (cosa inaspettate) diametralmente opposti per le due architetture. Per l’architettura x86 il vantaggio si è visto soprattutto nel caso dell’utilizzo degli iteratori STL: prestazioni quasi raddoppiate. Per l’architettura IA-64t, il vantaggio si è visto, invece, per la versione che non utilizza gli iteratori: quasi 4 volte.

Su MSDN (Microsoft Developer Network) potete trovare una interessante guida (in inglese) su come si utilizza questo utile strumento con VS 2005 (che si applica anche alla versione 2008).

Conclusioni e bibliografia

• Sito ufficiale OpenMP (in inglese)
• OpenMP su Wikipedia (in inglese)
• OpenMP tutorial (in inglese)
• OpenMP con Visual C++ (in inglese)
• Specifiche complete di OpenMP 3.0 (in inglese)
• Reference card di OpenMP 3.0 (in inglese)
• Specifiche del profiler di VS2008 (in inglese)