FlipVector

FlipVector è un programma C il cui obiettivo è mostrare diversi aspetti nell’utilizzo e gestione dei thread.

In questo programma vengono creati molteplici thread che manipolano un array condiviso. Nello specifico, ciascun thread inverte ripetutamente la posizione di ciascuna entry nell’array, la cui dimensione è un numero pari. A seguire, la funzione stress_test implementa tale operazione:

void* stress_test(void *arg){
    long my_ops = 0;
    int i = 0;
    pthread_barrier_wait(&ptbarrier);

    while(!stop){
        acquire();
        for(i=0;i<ARRAY_LEN/2;i++){
            shared[i] ^= shared[ARRAY_LEN-1-i];
            shared[ARRAY_LEN-1-i] ^= shared[i];
            shared[i] ^= shared[ARRAY_LEN-1-i];
        }
        release();
        my_ops+=1;
    }

    __sync_fetch_and_add(&ops, my_ops);
    return NULL;
}

Question

Come è possibile modificare il ciclo interno per gestire array di taglia generica?

Observation

L’operatore ^ implementa la semantica di eXclusive OR (XOR) bit a bit. La relativa tabella di verità è la seguente:

X	Y	X^Y
0	0	0
0	1	1
1	0	1
1	1	0

In altre parole se i due bit di input sono uguali l’output è pari a 0. Viceversa se sono diversi l’output è pari ad 1. Di conseguenza, x^x=0.

Question

Come è stato utilizzato lo XOR per implementare lo scambio del contenuto di due variabili?

Essendo l’array condiviso, la sincronizzazione è necessaria al fine di manipolare correttamente l’array. Le funzioni acquire e release assolvono a questo scopo, utilizzando primitive di lock nella loro implementazione.

Il programma misura le perfomance dell’applicazione in termini di sezioni critiche eseguite. Per assicurarsi che ciascun thread lavori con la massima concorrenza, questi aspettano che tutti i thread raggiungono la medesima riga di codice, prima di cominciare a manipolare l’array. Questo è ottenuto grazie alla primitiva di sincronizzazione pthread_barrier_wait, che blocca un thread fintanto che N thread non invocano la medesima funzione sul medesimo oggetto inizializzato a N.

Observation

Una barriera può esser vista come un particolare semaforo che:

• può assumere valori negativi

• inizializzato a -N

• l’operazione di wait incrementa il contatore di 1 unità

  • se il semaforo è negativo il thread rimane bloccato in attesa

  • se il semaforo assume valore pari a 0, tutti i thread in attesa vengono sbloccati e il valore resettato a -N

Prima di terminare ciascun thread utilizza una RMW per incrementare un contatore globale ops del numero di operazioni complessivamente eseguite dai thread. A tal scopo si è utilizzata la funzione __sync_fetch_and_add.

Warning

Le operazioni builtin __sync di gcc sono semplici da utilizzare, ma deprecate. La versione di riferimento è __atomic builtin, che tuttavia tengono conto anche del modello di memoria secondo lo standard C++11. Per ulteriori dettagli consultare AtomicSync.

Question

Come è possibile implementare l’accumulo del numero di operazioni globalmente eseguite senza utilizzare istruzioni RMW?

Ciascun thread termina non appena la variabile stop assume valore pari a true.

Il test viene ripetuto con molteplici configurazioni, ossia al variare dei thread e del tipo di lock. Il tutto è coordinato dal main thread secondo lo schema che segue.

for(i=1;i<=MAX_THREADS;i<<=1)
{
    for(lock_type=0; lock_type<num_locks;lock_type++){
        ...
        ...
        pthread_barrier_init(&ptbarrier, NULL, i);

        for(j=0;j<i;j++)    pthread_create(ptids +j, NULL, stress_test, NULL);
        sleep(SECONDS);
        __sync_bool_compare_and_swap(&stop, 0, 1);

        for(j=0;j<i;j++)    pthread_join(ptids[j],  NULL);

        pthread_barrier_destroy(&ptbarrier);
    }
}

Observation

L’operatore << è l’operatore di shift a sinistra. Considerando una variabile unsigned x a 8 bit con valore 4 la sua rappresentazione binaria è 0000 0100. L’istruzione x << 1 indica l’operazione di shift a sinistra di una posizione della variabile x, il cui risultato è pari a 0000 1000, ossia x assume il valore 8. L’operatore >> è l’operatore di shift a destra.

Question

• Quali operazioni matematiche possono essere implementate tramite gli operatori << e >>?

• Quante iterazioni esegue il seguente ciclo for(i=1;i<=MAX_THREADS;i<<=1)?

Per ciascun test, il main thread:

• inizializza la barriera

• crea i thread

• va in sleep per SECONDS secondi

• setta la variabile stop ad 1 con un’istruzione atomica

• attende la terminazione di ciascun thread

• distrugge la barriera

La variabile lock_type è una variabile globale utilizzata all’interno di acquire e release per selezionare l’implementazione di lock da utilizzare.

Question

• Perché la barriera viene distrutta ad ogni fine iterazione e inizializzata ad inizio iterazione?

• Quale altra istruzione RMW poteva essere usata al posto della compare&swap?

Il test misura e stampa il numero di operazioni effettuate in concorrenza da tutti i thread in un intervallo di tempo predefinito. Inoltre, prima di eseguire il suddetto ciclo, il main thread:

• inizializza le primitive di lock della libreria pthread

  pthread_spin_init(&ptspin,  PTHREAD_PROCESS_PRIVATE);
  pthread_mutex_init(&ptmutex, NULL);
  

• limita i core su cui i thread possono andare in esecuzione

  cpu_set_t my_set;
  CPU_ZERO(&my_set);
  for(i=0;i<CORES;i++)
      CPU_SET(i, &my_set);
  sched_setaffinity(0, sizeof(cpu_set_t), &my_set);
  

Warning

sched_affinity è una funzione non POSIX

Question

• Perché la set affinity viene utilizzata dal main thread?

• L’uso di set affinity garantisce che ciascun thread andrà in esecuzione sul medesimo core? Se sì, perché? Se no, come è possibile garantirlo?

Le funzioni di acquire e release

Le funzioni di acquire e release utilizzano una specifica implementazione di lock in funzione del valore assunto dalla variabile globale lock_type. Nello specifico supportano 5 implementazioni differenti di lock:

1. pthread spin lock (PT_TAS)

2. pthread mutex (PT_MUTEX)

3. test-and-set spin lock (TAS)

4. test-and-test-and-set spin lock (TTAS)

5. ticket spin lock (TICKET)

Nel caso di lock forniti dalla libreria pthread, acquire e release ridirezionano sulle rispettive funzioni di libreria.

void acquire(){
    ...
    if(lock_type == PT_TTAS) pthread_spin_lock(&ptspin);
    if(lock_type == PT_MUTEX)pthread_mutex_lock(&ptmutex);
}

void release(){
    ...
    if(lock_type == PT_TTAS)                    pthread_spin_unlock(&ptspin);
    if(lock_type == PT_MUTEX)                   pthread_mutex_unlock(&ptmutex);
}

Chiaramente, le variabili ptspin e ptmutex sono variabili globali.

Anche i lock TAS e TTAS sono delle variabili globali intere. Il valore 0 indica che il lock è libero e 1 indica che il lock è stato acquisito da un qualche thread.

volatile int lock = 0;

void acquire(){
    if(lock_type == TAS)
        while(__sync_lock_test_and_set(&lock,1));
    if(lock_type == TTAS){
        while(__sync_lock_test_and_set(&lock,1))
            while(lock);
    }
    ...
}

void release(){
    if(lock_type == TAS || lock_type == TTAS){  asm volatile ("":::"memory");   lock = 0;}
    ...
}

Observation

• la variabile lock è dichiarata volatile. Questo garantisce che il compilatore non attuerà alcune ottimizzazioni, garantendo che ogni accesso alla variabile lock verrà effettuato sempre in memoria. Ad esempio, il compilatore non potrà usare i registri general purpose come cache per la variabile.

• asm volatile ("":::"memory"); costituisce una barriera per il compilatore. Di conseguenza, quest’ultimo non può spostare istruzioni che seguono la barriera prima di quest’ultima e viceversa. asm indica al compilatore che si sta innestando all’interno di codice C del codice assembly. In questo caso, l’istruzione innestata "" è nulla. Siccome, il codice innestato è nullo, è necessario indicare al compilatore di non eliminare l’istruzione tramite il token volatile. Infine, l’ultimo parametro "memory" indica al compilatore che l’istruzione accede in modo impredicibile alla memoria, disabilitando ulteriori ottimizzazioni come il riordinamento delle operazioni di scrittura/lettura. Per approfondimenti sul tema consultare la documentazione di GCC riguardo gli extended-asm.

Note

Provare a dichiarare la variabile lock come int piuttosto che volatile int e vederne gli effetti quando si compila con il massimo livello di ottimizzazione (e.g. gcc -O3).

Infine, il ticket lock (TICKET) è implementato come una coppia di variabili globali lock e now di tipo volatile int, che indicano rispettivamente l’ultimo ticket servito e il ticket corrente.

volatile int lock = 0;
...
volatile int now = 0;

void acquire(){
    ...
    if(lock_type == TICKET){
        int myticket = __sync_fetch_and_add(&lock, 1);
        while(now != myticket);
    }
    ...
}

void release(){
    ...
    if(lock_type == TICKET){                    asm volatile ("":::"memory");   now = now+1;}
    ...
}

Question

L’algoritmo di ticket lock mostrato è corretto? Se sì, cercare di mostrare perché? Se no, mostrare un caso in cui l’algoritmo non garantisce mutua eclusione o progresso.

Risultati

In questa sezione vengono discussi i risultati ottenuti compilando con:

• MAX_THREADS = 32

• CORES = 4

• ARRAY_LEN = 256

• SECONDS = 5

• gcc -O3

Il sistema è equipaggiato con:

• CPU = Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

• CC = gcc 9.3.0

• LIBC = glibc 2.31

• LIBPTHREAD = NPTL 2.31

A seguire i risultati.

Le massime performance (numero di sezioni critiche eseguite) sono raggiunte da tutti i lock in assenza di concorrenza. Quando il numero di thread è maggiore di 1, le performance deteriorano a causa della contesa. Il degrado aumenta con thread count crescenti per gli spin lock (attesa attiva). L’uso ridotto di RMW nei TTAS giustifica le differenze con TAS. Il pthread mutex (PT-MUTEX) mantiene performance quasi inalterate in quanto riduce la contesa sulle risorse hardware (thread in attesa fuori dalla run queue). Non appena il numero di thread è maggiore del numero di core usabili, il ticket lock (spin+FIFO) ha un drastico crollo delle performance.

Question

Cosa giustifica il comportamento di TICKET?

Riferimenti

• pthread_barrier_init

• pthread_barrier_wait

• bitwise XOR

• __sync gcc builtin

• pthread_spin_init

• pthread_mutex_init

• sched_setaffinity

• CPU_SET

• shift

• extended-asm