Du caml, des threads (et du doute?)

Ces derniers temps je fais pas mal de Cuda.
J’ai écris un petit mandelbrot et en faisant quelques tests j’ai découvert quelques surprises…
Voici le code original de la fonction de calcul:

__global__ void mandelbrot(int* A, const int N, const int largeur, const int hauteur){
  int idx = blockDim.x * blockIdx.x + threadIdx.x;
 
  int y = idx / hauteur;
  int x = idx - (y * largeur);
 
  if (y < hauteur && x < largeur)
    {
      int cpt = 0;
      float x1 = 0.;
      float y1 = 0.;
 
      float x2 = 0.;
      float y2 = 0.;
      float a = 4. * x / largeur - 2.;
      float b = 4. * y / hauteur - 2.;
 
      float val = x1* x1 + y1 * y1;
 
      while (cpt < N && val <= 4.)
	{
          cpt ++;
          x2 = x1* x1 - y1 * y1 + a;
          y2 = 2. * x1 * y1 + b;
          x1 = x2;
 
          y1 = y2;
          val = x1* x1 + y1 * y1;
        }
 
      A[y*hauteur+x] = cpt;
 
    }

Ce calcul a lieu pour chaque pixel de l’image à générer. Cuda me permet de produire un grand nombre de threads (1 par pixel) qui vont s’exécuter en parallèle sur la carte graphique (plus ou moins nombreux à la fois et plus ou moins vite en fonction du GPU Nvidia utilisé).
Ce petit programme me permet de générer mon image beaucoup plus rapidement qu’en sequentiel (même sur un petit GPU).

Pour mes travaux futurs je vais avoir besoin de fonction Cuda plus complexes et surtout qui appellent d’autres fonctions. Pour voir l’impact sur les performances des appels de fonctions j’ai modifié le code de mandelbrot ainsi:

__global__ void mandelbrot2(int* A, const int N, const int largeur, const int hauteur){
  int idx = addi(multi(blockDim.x, blockIdx.x), threadIdx.x);
 
  int y = divi(idx, hauteur);
  int x = subi(idx, multf(y, largeur));
 
  if (andi(lti(y, hauteur), lti(x, largeur)))
    {
      int cpt = 0;
      float x1 = 0.;
      float y1 = 0.;
 
      float x2 = 0.;
      float y2 = 0.;
      float a = subf(multf(4., divf( x, largeur)) , 2.);
      float b = subf(multf(4., divf(y, hauteur)), 2.);
 
      float val = addf(multf(x1, x1), multf(y1, y1));
 
      while (andi(lti(cpt, N), leqf(val, 4.)))
        {
          cpt = addi(cpt, 1);
          x2 = addf(subf(multf(x1, x1), multf(y1, y1)), a);
          y2 = addf(multf(multf(2., x1), y1), b);
          x1 = x2;
          y1 = y2;
          val = addf(multf(x1, x1) , multf(y1, y1));
        }
 
      A[addi(multi(y,hauteur),x)] = cpt;
 
    }
}

avec

 __device__ float addf(float a, float b) {
  return a + b;
}
 __device__ int addi(int a, int b) {
  return a + b;
}
 
 __device__ float subf(float a, float b) {
  return a - b;
}
 __device__ int subi(int a, int b) {
  return a - b;
}
 
 __device__ float multf(float a, float b) {
  return a * b;
}
 __device__ int multi(int a, int b) {
  return a * b;
}
 
 __device__ float divf(float a, float b) {
  return a / b;
}
 __device__ int divi(int a, int b) {
  return a / b;
}
 
 __device__ int lti (int a, int b) {
  return a < b ;
}
 __device__ int ltf (float a, float b) {
  return a < b ;
}
 
 __device__ int leqi (int a, int b) {
  return a <= b ;
}
 __device__ int leqf (float a, float b) {
  return a <= b ;
}
 __device__ int andi(int a, int b) {
  return a && b;
}

Le mot clef __device__ indique que la fonction doit être compilé pour le GPU.

Comme vous le voyez rien de bien méchant dans tout cela.

La surprise est venue lors des benchs:

Pour info : en séquentiel, sur un core de Phenom II X6 @3.4GHz, le programme met 41.49s à générer l’image.

On constate donc que l’utilisation des fonctions dans mon petit calcul ne fait pas perdre en performance mais au contraire qu’il permet de gagner un peu. Evidemment ce n’est pas du aux appels de fonction en eux même ni aux fonctions en question mais à des questions d’optimisation lors de la compilation.
Étonnant non?

OCaml n’autorise pas le parallélisme, mais il existe tout de même le module Thread qui permet d’exprimer la concurrence.
Par exemple si j’écris le programme suivant :

let f s=
  while true do
    Printf.printf "%s\n" s;
  done
 
let _ =
  let t0 = Thread.create  f  "Salut"
  and t1 = Thread.create  f  "Coucou"
  in
    Thread.join t0;
    Thread.join t1

j’obtiens l’affichage suivant
Salut
Salut
Salut
Salut
Salut
Salut
Salut
Coucou
Coucou
Coucou
Coucou
Coucou
Salut
Salut
Salut
...


Bien que non exécutés en parallèle, les deux threads s’entrelacent bien.

Là où ça devient plus surprenant, c’est si l’on fait une boucle qui ne fait rien…
Par exemple cette fois-ci j’exécute le programme suivant :

let rec fib n =
  if n < 2 then 1   
    else fib (n - 2) + fib (n - 1) 
 
let a = ref 1 
 
let f ()=
   let tmp = (fib !a)
   in
     Printf.printf "%d\n" tmp;
     incr a;     
 
let _ =
  let t1 = Thread.create (fun _ ->; while true; do f (); done) ()
  and t2 = Thread.create (fun _ ->; while true; do (); done) ()
  in
    Thread.join t1;
    Thread.join t2

Le thread t1 calcule la suite de Fibonnaci tandis que le thread t2 ne fait rien…
Dans ce cas, le programme va boucler dès que le thread t2 prendra la main. En effet, en OCaml le thread courant (celui qui s’exécute) ne change que lors d’une allocation mémoire ou d’un appel à une primitive de synchronisation. Ici, le thread t2 n’alloue pas de mémoire et n’utilise pas de primitives de synchro… une fois qu’il a pris la main, on n’est donc plus en mesure de changer de thread courant.
Pour laisser t1 calculer sa suite, il faut donc modifier t2

• soit en ajoutant un peu d’allocations :

t2 = Thread.create (fun _ ->; while true; do alloc 10; done) ()

avec :

let alloc n=
  let rec gen x = if x=0 then [] else x::gen (x-1) in ignore (gen n)

• soit en utilisant une primitive de synchro :

t2 = Thread.create (fun _ ->; while true; do Thread.yield(); done) ()

Pensez-y si vous êtes amenés à écrire de longues boucles sans allocations…

PS: merci à ce site pour la fonction d’allocation (oui, je suis flemmard).

Comme on l’a vu, parallélisme et concurrence ne font pas bon ménage.

En effet quand on écrit un programme parallèle on cherche à minimiser la concurrence. Et ce, pour deux principales raisons :

Pour limiter la perte de performances due à l’accès aux données en concurrence (en effet, l’accès à une donnée protégée implique la perte du parallélisme).
Pour limiter les bugs… le partage de données entre plusieurs tâches peut entraîner des conflits (si la protection est mal réalisée). En effet pour augmenter les performances on est tenté de protéger le moins possible les variables partagées…

Plusieurs techniques existent pour limiter la concurrence, l’une des plus évidentes est de ne pas en écrire du tout.

Pour qualifier un programme de réentrant, il faut qu’il satisfasse plusieurs conditions (plus ou moins tirées de wikipedia) :

• il ne doit pas contenir de variables globales non constantes
• il ne doit pas renvoyer une adresse vers une variable globale non constante
• il ne doit modifier que les variables passées en argument (pas d’effet de bord)
• il ne doit pas utiliser de verrou sur l’accès aux variables
• il ne doit pas modifier son propre code
• il ne doit pas appeler de programmes ou fonctions non réentrantes

Ces contraintes assurent qu’il n’existe aucune donnée partagée au sein du programme entre différentes taches et qu’une tache ne pourra pas modifier les données utilisées par une autre tache.

Cette méthode permet donc d’écrire des programmes sans concurrence sur des données. Ils sont donc facilement parallélisable (dès lors que les taches sont indépendantes les unes des autres).

Cependant, elle a un coût :
Afin de ne pas partager les données on va rapidement devoir en faire des copies pour chaque tâche ce qui implique un coût en temps d’exécution et en espace mémoire utilisé, de la même manière on risque de devoir passer beaucoup d’arguments à nos fonctions afin de s’assurer de leur réentrance.
Il reste donc à nouveau important de diminuer au maximum les données (autrefois partagées) à copier.

Néanmoins, avec l’émergence de machines au nombre d’unités de calcul (par exemple les multicoeurs) de plus en plus grand, il devient important de réfléchir à la parallélisation de nos programmes. Même si celle-ci n’a pas lieu aujourd’hui, peut-être que l’on (ou quelqu’un d’autre) cherchera à paralléliser notre code. Il me semble donc important d’essayer dès la première écriture de maximiser la réentrance de nos programmes. Ils deviendront ainsi plus facilement parallélisables ou intégrables à d’autres programmes plus complexes.
En effet, si notre programme n’est pas facilement divisible en taches indépendantes, peut-être qu’il constituera un élément d’un programme plus large. Cette dernière remarque est encore plus importante pour les développeurs de bibliothèques. Assurer l’utilisateur final de la réentrance de la bibliothèque qu’il utilise c’est l’assurer de pouvoir l’intégrer plus facilement à son programme et de pouvoir s’il le souhaite l’utiliser en parallèle.

Parfois la réentrance est aussi la seule solution pour rendre un programme paraléllisable.
Prenons l’exemple des fonctions de comparaison d’OCaml (OCaml n’autorise pas le parallélisme et sa bibliothèque d’exécution n’est absolument pas réentrante (mais nous en reparlerons une autre fois)):
Celles-ci ne sont pas utilisables en parallèle. En effet, dans le cas d’éléments complexes, la comparaison se fait en profondeur et le résultat courant de la comparaison est stocké dans une variable globale. L’exécution en parallèle de comparaisons implique des accès concurrents à cette variable. On pourrait donc la protéger par un verrou d’exclusion mutuelle. Cela ne suffira pas, car si des tâches effectuent une comparaison en parallèle elles risquent d’entrelacer leur accès à cette variable entraînant un résultat faux pour chacune des comparaisons.
Il existe (au moins) deux solutions :

• empêcher les comparaisons parallèles (ce n’est pas ce que l’on veut)
• ne plus partager cette variable et donner à chaque tâche une variable équivalente (on rend donc les fonctions de comparaison réentrantes)

Ici, nous rendons les fonctions de comparaisons réentrante ce qui nous assure de pouvoir les exécuter en parallèle sans introduire d’erreur dans notre programme.

Souvent quand on discute programmation et que l’on aborde le sujet des multicoeurs, des threads, etc on emploie les termes « parallélisme » et « concurrence ».
Assez souvent ces termes semblent interchangeables.

Pourquoi? Car souvent on parle de programmes parallèles ET concurrents, cependant des différences existent entre ces deux concepts.
Et il n’est pas trivial de faire cette différence (c’est la deuxième version de cet article…)

Avant de discuter programmation essayons de prendre des exemples concrets (merci Philippe):

Téléphone : Si deux personnes A et B appellent une troisième personne C (en même temps): ils partagent l’accès à une ressource, le téléphone de C. Ils sont donc en concurrence sur cette ressource. A priori ces appels ne seront pas parallèles, car, le téléphone de C fera alterner les conversations (via signal d’appel etc).

Télévision : Sur une télévision on peut désormais (depuis un certain temps) recevoir plusieurs flux en même temps (via les fonctions Picture In Picture etc). Là, la réception des deux flux est effectuée en parallèle et en concurrence (la ressource « télévision » étant partagée).

En programmation :
Un programme peut être divisé en tâches. Si ces tâches partagent des ressources on parlera alors de concurrence. L’accès a ces ressources (si elles sont protégées) empêche le parallélisme. On cherchera donc à minimiser la concurrence pour augmenter le parallélisme. En effet, en parallélisant une tâche, on peut (mais ce n’est pas obligatoire) en accélérer l’exécution.
Par exemple l’addition des éléments de deux vecteurs A et B pourra se répartir en tâches additionnant les éléments de sous vecteurs de A et B.
Ainsi les additions (ne partageant aucune ressource) pourront se faire entièrement en parallèle.

Ces différences sont importantes quand on s’intéresse aux propriétés des langages de programmation et de leurs implantations respectives.
En effet, il n’est pas rare de trouver des langages de programmation permettant la concurrence mais pas le parallélisme. Par exemple, en OCaml (comme c’est bizarre) il est tout à fait possible d’exécuter des tâches concurrentes. Cependant l’exemple de l’addition des tableaux ne tirera pas parti d’une architecture multicoeur le langage ne permettant pas une réelle exécution des tâches en parallèle (nous reviendrons sur tout ça une autre fois).

PS: pour OCaml je fais souvent un amalgame entre le langage et ses propriétés et l’implantation du langage par l’Inria (compilateur, bibliothèque d’exécution etc) c’est pour une raison simple l’implantation du langage la plus utilisée est celle de l’Inria et c’est (sauf  précisions) toujours celle dont je parle.

Quand on me demande avec quel langage je travaille je cite rapidement OCaml, et pourtant si on regarde par-dessus mon épaule on ne voit (presque) que du C sur l’écran…
En effet, je travaille avec OCaml, mais surtout, sur OCaml.

Suivant les cas je fais des modifications sur des éléments du langage (compilateur, bibliothèque d’exécution) ou parfois des bibliothèques. Et il s’avère qu’une bonne partie de l’implantation du langage de l’Inria (celle que j’utilise) est écrite en C.

De même, les bibliothèques sur lesquelles je travaille sont, souvent, des bibliothèques de calcul, ou, visant à exploiter du materiel particulier, et je me retrouve très rapidement à travailler sur des binding OCaml/C.
Le schéma suivant montre (grosso-modo) la compilation d’un code OCaml.

Compilation en OCaml

On y voit qu’un fichier .ml est transformé par le compilateur en fichier .cmx et  qu’un fichier assembleur .S est généré.

De là, on va lier cet ensemble avec la bibliothèque d’exécution (runtime) d’OCaml (libasmrun.a) et avec des bibliothèques (otherlibs) si nécessaire.

Dans cet ensemble, il faut savoir qu’ocamlopt (le compilateur) est écrit en OCaml, que la runtime d’OCaml est principalement écrite en C (avec des bouts d’assembleur) et que les bibliothèques utilisées peuvent contenir de l’OCaml ou du C.

Mon travail portant le plus souvent sur les otherlibs, et la runtime…
il implique donc d’écrire (et de lire :/) principalement du C.

Voici un blog sur lequel je compte publier un peu de tout concernant l’informatique et le développement en particulier. Que ce soit lié à mes travaux, à des projets perso ou à ce qui me passera par l’esprit.
Ça risque de souvent parler de langages de prog (et plus particulièrement dOCaml mais vous risquez de lire davantage de C (j’expliquerai pourquoi une autre fois)) et un peu de parallélisme (sous différentes formes).
Le but ici c’est d’échanger alors évidemment c’est pour partager des idées, des découvertes etc de mon côté mais aussi pour recueillir vos commentaires (que ce soit sur une erreur (et j’en ferai), pour compléter un sujet ou donner un avis).