CilkPlus

Un petit mot à propos de CilkPlus. À la base il s'agit d'un environnement de compilation construit sur une version modifiée de GCC (v2.95 je crois, ou peut-être v3.x), produite au MIT. Cilk v5 est un logiciel libre, téléchargeable sur le site du MIT. Il faut se souvenir qu'il a été proposé à une période « héroïque », où il n'y avait pas encore réellement de standard pour exprimer des programmes en parallèle pour machines à mémoire partagée (OpenMP a officiellement proposé son premier standard en 1997). Voici un petit exemple de code Cilk (pas CilkPlus), et son équivalent en C+OpenMP:

/* Version Cilk naïve du calcul des nombres de Fibonacci en parallèle */
cilk int fib (int n) {
 if (n >= 2) {
 int n1, n2;
 n1 = spawn fib(n-1);
 n2 = spawn fib(n-2);
 sync;
 n = n1+n2;
 }
 return n;
}
int main(int argc, char *argv[]) {
 int n,res;
 /* J'omets le code pour lire n sur l'entrée standard */
 res = spawn fib(n);
 sync;
 printf("fib(%d) = %d\n",n,res);
 return 0;
}

/* Version OpenMP naïve du calcul des nombres de Fibonacci en parallèle */
int fib(int n){
 if (n >= 2) {
 int n1, n2;
# pragma omp task shared(n1)
 {
 n1 = fib(n-1);
 }
# pragma omp task shared(n2)
 {
 n2 = fib(n-2);
 }
# pragma omp taskwait 
 n = n1 + n2;
 }
 return n;
}

Ces deux codes font la même chose, mais ce qui est intéressant, ce sont les garanties et innovations offertes par Cilk à l'époque¹ :

1. Cilk n'ajoute que trois mots-clé à C89 : cilk, spawn et sync
2. Cilk garantit que l'espace pris par les différentes tâches (pile, etc.) est directement proportionnel à celui du même code tournant en séquentiel, à un facteur multiplicatif près.
3. Cilk était le premier langage parallèle (à ma connaissance) qui reposait sur la notion de vol de tâche, et en faisait une propriété algorithmique. Le vol de tâche consiste à aller « piocher » dans la liste de tâches en attente des voisins une nouvelle tâche à effectuer lorsqu'on n'a rien à faire.
4. Cilk utilise une cactus stack au lieu d'une linear stack (la pile habituellement utilisée par les compilateurs). C'est grâce à elle que le vol de tâche est « aisé » pour le runtime de Cilk² .
5. Lorsqu'une fonction parallèle est invoquée, le père est placé dans la liste des tâches en attente, et la fonction fille commence à s'exécuter directement. Cette propriété permet de garantir que l'ordre d'évaluation des fonctions est complètement strict (fully strict dans le texte original). Ça veut aussi dire que si j'exécute un code Cilk sur un seul processeur, il exécutera les fonctions exactement dans l'ordre dans lequel elles seront invoquées, et donc le code s'exécutera comme un code C classique.

Concernant le fait que l'exécution d'un programme Cilk est borné en espace, voici un exemple :

fib(3):
 fib(2):
 fib(1)
 fib(0)
 somme
 fib(1)
 somme
somme

Si j'ai un seul processeur, tout sera exécuté « dans l'ordre ». Si j'ai deux processeurs, alors la séquence devient quelque chose de ce genre (P1 et P2 sont les processeurs de la machine)³ :

P2: rien à faire.
P1: depuis fib(3):
 spawn fib(2): fib(3) est placée dans la liste des tâches disponibles. On exécute fib(2)
P2: vol de tâche. P2 récupère fib(3)
P1: depuis fib(2): 
 spawn fib(1): fib(2) est placée dans la liste des tâches disponibles. On exécute fib(1)
P2: depuis fib(3):
 spawn fib(1): fib(3) est placée dans la liste des tâches disponibles. On exécute fib(1)
P1: fib(1) termine. Vol de tâche. P1 récupère fib(2).
 spawn fib(0): fib(2) est placée dans la liste des tâches disponibles. On exécute fib(0)
P2: fib(1) termine. Vol de tâche. P2 récupère fib(2).
 On attend que toutes les tâches générées reviennent.
P1: fib(0) termine. Vol de tâche. P1 récupère fib(3).
 On attend que toutes les tâches générées reviennent.
P2: fib(1) et fib(0) sont revenues. On peut effectuer la somme, et terminer.
P1: fib(2) et fib(1) sont revenues. On peut effectuer la somme, et terminer.
P2: rien à faire.

Ainsi, si les deux codes Cilk et OpenMP se ressemblent fortement, Cilk me garantit qu'il ne créera pas plus de tâches que le nombre de processeurs disponibles. Avec OpenMP et la majorité des environnements de programmation parallèle, si un ordre de création de tâche est effectué, alors celle-ci est crée, qu'on ait les ressources pour l'exécuter ou pas.

Dernière chose : Cilk est le langage qui avait été choisi pour écrire « Socrates », un logiciel d'IA pour jouer aux échecs, et a longtemps été dans le top 3 dans les années 90. C'est aussi le langage qui a au départ été utilisé pour écrire FFTW (The Fastest Fourier Transform in the West), une bibliothèque de calcul de transformées de Fourier parallèle, qui a la propriété rigolote d'être « cache-oblivious » (c'est-à-dire que les algos de FFTW vont naturellement faire « tenir » les données dans les caches). Leiserson est le prof derrière le projet Cilk. Il avait monté une boite pour vendre Cilk++ (une réimplémentation de Cilk en C++, mais qui utilise des mécanismes différents)