Parallel Lives

Structures et Algorithmes Parallèles

Jouons avec quelques notions de base…

Matthieu Arzel & Serge Guelton

Prérequis: <pthread.h>

#include <pthread.h>

void* task(void* arg) {
    ...
}
...

pthread_t thread
int value;
pthread_create(&thread, NULL, task, &value);

void* ret;
pthread_join(thread, &ret);

Boucle sans état

for(int i = 0; i < n; ++i)
    task();
  1. Pas de partage de donnée
  2. Partage implicite ?

map : Boucle avec état indépendants

for(int i = 0; i < n; ++i)
    task(i);
  1. Données indépendantes
  2. Partage implicite ?

Boucle avec état partagé [r]

const struct state s;
for(int i = 0; i < n; ++i)
    task(&s, i);
  1. Données indépendantes
  2. Partage explicite

Boucle avec état partagé [rw]

struct state s;
for(int i = 0; i < n; ++i)
    task(&s, i);
  1. Données indépendantes
  2. Partage explicite
  3. Besoin de syncronisation

Ordonnancement

  1. Quand priviliger quelle stratégie ?
  2. Ajout / Suppression de thread ?
  3. Ratio calcul / ordonnancement

Attaquons l'exercice

Examinez le fichier parallel_for.c.

> gcc -O2 parallel_for.c -o parallel_for
> parallel_for 10
elapsed time: 487.425000 ms

Attaquons l'exercice

Parallélisez à l'aide de <pthread.h> et

  1. Mesurez le temps de création d'un thread
  2. Paritionnement statique bien dimensionné
  3. (Paritionnement dynamique)

Accumulation

int acc = 0;
for(int i = 0; i < n; ++i)
    acc += i * i;
  1. Atomicité de la réduction
  2. Associativité de la réduction ?

Reduction

int acc = 0;
for(int i = 0; i < n; ++i)
    acc = reduce(acc, i * i);
  1. Atomicité de la réduction
  2. Associativité de la réduction ?

Map-Reduce

int acc = 0;
for(int i = 0; i < n; ++i)
    acc = reduce(acc, task(i));
  1. Atomicité de la réduction
  2. Associativité de la réduction ?

Attaquons l'exercice

Inspectez le programme reduce.c (C11 !)

> gcc reduce.c -o reduce
> ./reduce 100000 2
elapsed time: 4.300000 ms
result: 5000050000
  1. Vérifiez le résultat théorique
  2. Tracez une courbe d'accélération
  3. Améliorez le programme

Producteur - Consommateur

struct stack work;
void produce() {
    while(true)
       stack_push(&work, random());
}

void consume() {
    while(true)
       task(stack_pop(&work));
}

Comment garantire l'atomicité des opérations ?

Attaquons l'exercice

Examinez le fichier consumer_worker.c.

> gcc -O2 consumer_worker.c -o consumer_worker
> ./consumer_worker | head -n 10
pushed: 0
read: 0
pushed: 1
read: 1
pushed: 2
read: 2
pushed: 3
read: 3
pushed: 4
read: 3

Attaquons l'exercice

Rendre la structure de donnée thread-safe à l'aide de

puis à l'aide <stdatomic.h> et

1