Threads – seconda parte

Oggi cercherò di mostrarvi come fanno i thread a lavorare insieme alla risoluzione di uno stesso problema. Farò un esempio stupidissimo: come contare il numero di elementi diversi da 0 in una matrice di interi molto grande.

Variabili locali e globali

Supponiamo di avere una matrice di 10.000 x 10.000 numeri interi. In tutto sono quindi ben 100.000.000  numeri. Ognuno degli elementi può essere 0 o 1, e vorremmo contare quanti sono in tutto gli elementi pari a 1. Se volessi farlo in maniera sequenziale, dovrei scrivere qualcosa del genere:

int array[DIM][DIM];   // matriciona da analizzare

int conta_array()
{
    int count = 0;
    for (int i=0; i<DIM; i++)
        for (int j=0; j<DIM; j++)
            if (array[i][j] != 0) count++;
    return count;
}

La funzione conta_array() esegue due cicli for uno dentro l’altro: la variabile locale i scorre le righe, mentre la variabile j scorre le colonne; la variabile count serve da accumulatore e viene incrementata solo se l’elemento array[i][j] è diverso da 0.

Notate che la funzione legge direttamente i dati dalla variabile array[][] che è una variabile globale. Essa può essere acceduta da tutte le funzioni del programma che la vedono, ovvero che sono dichiarate dopo array[][]. Una variabile globale rimane in memoria per tutta la durata del programma. In questo caso, la funzione conta_array() si limita a leggere array[][] senza modificarla, ma non è detto che sia sempre così: altre funzioni potrebbero sovrascrivere la variabile.

La variabile count, invece, è una variabile locale, perché è definita all’interno della funzione, e può essere utilizzata in maniera esclusiva e privata solo dalla funzione stessa. Nel momento in cui la funzione ha terminato di eseguire, il contenuto di count viene restituito (istruzione return count), e la variabile count viene distrutta; verrà ricreata la prossima volta che la funzione conta_array() viene invocata.

In altre parole, le variabili locali servono alla funzione per fare i propri calcoli interni e non possono essere accedute dall’esterno della funzione. La funzione può prendere i dati che gli servono a fare i calcoli dai parametri o dalle variabili globali. I risultati possono essere messi in altre variabili globali, oppure restituite attraverso l’istruzione return, oppure attravero i parametri di uscita (ovvero definiti tramite puntatori, come avveniva con l’oggetto Param dell’esempio della volta scorsa).

Parallelizzare!

Contare gli elementi di un array è una di quelle cose che si parallelizza benissimo. Faremo così: ci denifiamo un certo numero di thread; poi partizioniamo la matrice in tanti pezzi, uno per ogni thread, poi li lasciamo contare ognuno sulla propria partizione; infine, sommiamo i risultati parziali. Ecco il codice, più sotto lo spieghiamo.

#include <pthread.h>
#include <cstdlib>
#include <iostream>
#include "time_utils.hpp"

using namespace std;

#ifndef DIM
#define DIM 10000
#endif

int nt;                // numero dei thread
int array[DIM][DIM];   // matriciona da analizzare
int *res;              // qui ci vanno i risultati parziali

// restituisce la differenza (a-b) in microsecondi
long timespec_sub_us(struct timespec *a, struct timespec *b)
{
    long ret = 0;
    ret = (a->tv_sec - b->tv_sec) * 1000000;
    ret += (a->tv_nsec - b->tv_nsec) / 1000;
    return ret;
}

// il thread che fa il lavoro, sommando le righe:
// i=off, off+nt, off+2*nt, ...,
void *cth(void *arg)
{
    int off = (*(int *)arg);   // offset iniziale, tra 0 e nt-1
    int count = 0;             // somma parziale
    cout << "Thread con offset " << off << endl;
    for (int i=off; i<DIM; i+=nt)
        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

    cout << "Thread: somma parziale: " << count << endl;
    res[off] = count;
    return 0;
}

int main(int argc, char *argv[])
{
    if (argc < 2) {
        cout << "Uso: " << argv[0] << " <nthreads>" << endl;
        exit(-1);
    }

    nt = atoi(argv[1]);
    if (nt < 1) {
        cout << "Il numero di thread deve essere maggiore o uguale a 1"
             << endl;
        exit(-1);
    }

    // crea gli array in memoria
    pthread_t *tid = new pthread_t[nt];
    int *offset = new int[nt];
    res = new int[nt];

    cout << "Inizializzazione della matrice " << endl;
    for (int i = 0; i<DIM; i++)
        for (int j=0; j<DIM; j++) array[i][j] = rand() % 2;
    for (int i=0; i<nt; i++) res[i] = 0;

    cout << "Fine inizializzazione, creazione thread" << endl;

    // prende il tempo
    struct timespec start, stop;
    clock_gettime(CLOCK_REALTIME, &start);

    // crea nt thread concorrenti
    for (int i=0; i<nt; i++) {
        offset[i] = i;
        pthread_create(&tid[i], 0, cth, &offset[i]);
    }

    // aspetta la terminazione dei thread
    for (int i=0; i<nt; i++)
        pthread_join(tid[i], 0);

    int sum = 0;
    // integra i risultati
    for (int i=0; i<nt; i++) sum += res[i];

    // prende il tempo
    clock_gettime(CLOCK_REALTIME, &stop);
    long ut = timespec_sub_us(&stop, &start);

    cout << "Numero totale di non-zeri: " << sum << endl;
    cout << "Tempo necessario: " << ut << endl;
}

Dopo aver copiato il codice in un file, chiamiamolo matrice.cpp, e compiliamolo con:

g++ matrice.cpp -lpthread -lrt -o matrice

Infatti bisogna linkare la libreria real-time, che mi servirà per misurare il tempo. Vediamo come funziona il tutto, partendo dalla funzione cth().

  • Righe 27-39: qui ci sta il codice dei thread. Essi contano ognuno su delle righe diverse. Il primo thread avrà off = 0, e conterà le righe 0, nt, 2*nt, 3*nt, ecc, dove la variabile globale nt definisce il numero di thread nel programma (definita alla riga 12, e inizializzata alla riga 48). Il secondo avrà off=1 e conterà le righe 1, 1+nt, +2*nt, ecc. E così via per tutti i thread. Il conto parziale viene fatto su una variabile locale count. Poi, una volta finito di contare, il risultato viene copiato su un array globale chiamato res (definito alla riga 14, e inizializzato alla riga 58.
  • Righe 43-53: servono per leggere il numero di thread desiderati sulla linea di comando. Il programma esce con errore se non viene specificato alcun numero, oppure un numero minore di 1.
  • Righe 56-58: vengono creati gli array. In C/C++ non si possono dichiarare array di dimensione variabile, ma solo di dimensione fissa e conosciuta a tempo di compilazione. Poiché a tempo di compilazione non so quanto è nt, devo crearli dinamicamente qui.
  • Righe 60-63: inizializzo la matrice con numeri casuali, invocando la funzione rand(). Questo prende un po’ di tempo (circa un secondo).
  • Righe 68-69: prima di creare i thread, prendo il tempo attuale e lo memorizzo nella variabile start. Teoricamente questa funzione ha la precisione del nanosecondo, in pratica la precisione dipende dal sistema operativo, e difficilmente può essere più preciso di un microsecondo.
  • Righe 71-75: creo i thread concorrenti, passando a ognuno un diverso valore di offset, tra 0 e nt-1. Notare che tutti i thread eseguiranno lo stesso codice, quello della funzione cth(), ma ognuno di essi opererà su dati diversi. Ogni volta infatti che viene chiamata la funzione pthread_create(), viene creato un nuovo thread che esegue la funzione cth(). Questo thread avrà una sua copia privata delle variabili locali, in primis della variabile count. Se ad esempio nt vale 4, vengono creati 4 thread, ognuno con le sue variabili count e off private e differenti da quelle degli altri; inoltre, il primo avrà off=0, il secondo off=1, il terzo off=2 e il quarto off=3. Tutti questi thread però agiscono sulla stessa variabile globale array[][], proprio perché essendo globale, di tale variabile ne esiste una sola copia accessibile da tutti.
    Questo modello di memoria è molto importante, tenetelo sempre presente perché è la chiave per capire come funziona la programmazione parallela.
  • Righe 78-79: aspetto che tutti i thread terminino
  • Righe 81-83: sommo i risultati parziali
  • Righe 86-87: prendo il tempo e calcolo la differenza in microsecondi tramite la funzione timespec_sub_us() che ho scritto alle righe 16-23
  • Righe 89-90: stampo a video il risultato e il tempo che ci è voluto

Lanciando il comando ./matrice 1 sul mio PC si ottiene il seguente output:

Inizializzazione della matrice
Fine inizializzazione, creazione thread
Thread con offset 0
Thread: somma parziale: 50002613
Numero totale di non-zeri: 50002613
Tempo necessario: 1867326

In pratica, se lanciate il programma con un thread solo, è come se fosse tutto sequenziale, a meno di overhead di sistema operativo (eh, il mio laptop è un po’ lento, ma la batteria mi dura 8 ore).
Nella figura seguente viene mostrato un grafico del tempo che ci vuole su un quadcore (4 processori) al variare del numero di thread che vengono creati.

Come vedete, creare più di 4 thread su un quadcore non solo non porta vantaggi, ma addirittura può incrementare leggermente il tempo di calcolo totale.
Per oggi direi che può bastare così. La prossima volta vedremo un’interfaccia un po’ più semplice dei thread per fare le stesse cose.

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • fettiptEnaria  Il 15 febbraio 2012 alle 00:18

    Cosa molto divertente

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: