(Si je ne fais plus de news, c'est que la page admin est cassée).
Sinon, revenons à la version 0.7.5 qui est en cours de développement. Elle apporte son lot de nouveauté (petite extension ROOTOF - très naive, mais sympa : ROOTOF(4,-x^3+x^2+x-1,x)^15 = -15+30*ROOTOF(4,-1+x^2-x^3+x,x)-10*ROOTOF(4,-1+x^2-x^3+x,x)^3-12*ROOTOF(4,-1+x^2-x^3+x,x)^2, implanté de façon super naïve et pas du tout optimisée).
Mais la principale nouveauté est le support des thread dans le moteur de calcul symbolique.
Pour ce faire, je me suis inspiré de cilk plus (site: http://www.cilkplus.org/ ) pour faire mon interface ( http://en.wikipedia.org/wiki/Cilk_Plus )
Les contraintes que j'avais :
* pas de regression du temps de calcul en mode Single-Thread.
* simple à gérer : le code MT ne doit pas rendre le code moins lisible et le même code doit pouvoir fonctionner en mode ST ou en mode MT.
L'interface cilk plus répondait à ces conditions. Prenons l'exemple classique de Fibonacci:
int fib(int n)
{
if (n < 2)
return n;
int x = fib(n-1);
int y = fib(n-2);
return x + y;
}
en version parallélisée, cela donne :
int fib(int n)
{
if (n < 2)
return n;
int x = cilk_spawn fib(n-1);
int y = fib(n-2);
cilk_sync;
return x + y;
}
Juste deux mot clés (cilk_spawn et cilk_sync en plus) mais le code reste le même (exemple complet disponible à https://www.cilkplus.org/fibcpp )
Pour compiler, il faut utiliser GCC /clang /icc dernière version :
gcc fib.c -O3 -fcilkplus
On execute:
./a.out
./a.out: error while loading shared libraries: libcilkrts.so.5: cannot open shared object file: No such file or directory
Arg ! Ca ajoute une dépendance à un runtime
Une fois corrigé:
Fibonacci number #39 is 63245986. Calculated in 6.059 seconds using 2 workers.
Comme l'interface est simple, je me suis dit que ca serait un bon entrainement de voir comme faire avec pthread seulement (pas encore porter le for).
Bon, j'ai paumé le source de test... (je dois pouvoir facilement le refaire cependant), mais les résultats étaient sans appel. Ce test de code vite fait était 10 fois plus rapide que cilk !
[EDIT] Bon finalement, j'ai refait le source pour être crédible. Les résultats:
Fibonacci number #39 is 63245986. Calculated in 0.702 seconds using 2 workers.
Le code est cependant moins joli:
int fib(int n);
struct fib2_s {
int x, n;
};
static void subfunc_1 (void *data) {
struct fib2_s *f = data;
f->x = fib (f->n );
}
/* Compute Fibonacci number using thread systems. */
int fib(int n)
{
if (n < 2)
return n;
struct fib2_s f;
may_spawn_block_t b;
may_spawn_start(b);
f.n = n - 2;
may_spawn (b, subfunc_1, &f);
int y = fib (n-1);
may_spawn_sync(b);
return f.x + y;
}
M'enfin bon, un facteur 10... je ne sais pas comment est faite l'implémentation de cilk plus ans gcc 4.9, mais à mon avis, y'a un insecte qui traine !
Considérant en plus qu'il me faut contrôler les variables globales lors d'un nouveau thread, je suis donc parti sur mon interface qui me permet de contrôler les variables globales spécifiques au thread lors de la création d'un nouveau thread (c'est hallucinant qu'ils n'aient pas prévu une fonction de construction / destruction à enregistrer lors de la création / destruction d'un thread mais qu'ils aient ajouté un quickexit dans le standard C11 - fin disgression).
L'interface de MAYLIB pour les thread worker devient donc:
int may_kernel_worker(int nb_core,size_t stack_size); ==> Définit le nomber de worker (= thread additionel que MAYLIB utilisera "automatiquement" pour ces calculs) et la taille de la pile des objets algébriques pour chaque thread. Note: 1==> 1 thread, pas de worker. 0 ==> Auto detect number of core / Auto detect stack_size. void may_spawn_start(may_spawn_block_t block, may_mark_t mark); ==> Démarre et initialise un block // dont tous les calculs seront garbage collecté lors du prochain compactage impliquant mark. void may_spawn (may_spawn_block_t block, void (*func)(void *), void *data); ==>Exécute (potentiellement) la fonction func(data) dans le block // block (s'il y a un worker de libre), où l’exécute de lui même sinon. void may_spawn_sync(may_spawn_block_t block); ==> Attend que tous les worker aient finis.
(Je sais, ce n'est pas une interface complète et elle ne permet pas tout).
Comme c'est pas très user friendly (limite du C...), j'ai donc fait un pool de macros supplémentaire dont voici l'usage:
MAY_SPAWN_BLOCK(block);
MAY_SPAWN(block,(b,c,d), {
a = add(b,c);
a = add (a, d);
}, (a));
z = add(r, t);
MAY_SPAWN_SYNC(block);Ca rend la lecture plus simple en stockant le coeur de l'algorithme à coté des autres calculs (et accessoirement avec des bons define, de générer le code sans multi-thread directement dans le cœur de la fonction)
La seule macro complexe est MAY_SPAWN dont le prototype est :
MAY_SPAWN(block, (list of input), { core of computation }, (list of output) );
qui encapsule l'appel à may_spawn ci-dessus.
Elle a un inconvénient : elle génère une nested function (comme ont dit dans le milieu) qui n'est supporté que par GCC et ICC (clang ne le supporte pas) et utilise l'extension typeof.
Par contre, elle ne génère pas de trampoline (ce qui fait que la stack n'est pas marquée comme exécutable, donc pas de faille de sécurité) car toutes les variables locales sont recopiés dans une structure interne permettant de passer en paramètre les données à la fonction.
Vous me direz :
* les nested function, c'est mal, c'est pas standard. C'est un gnuisme. Oui, mais ne faisant pas de C++ (et les fonctions lambda), j'ai pas le choix si je ne veux pas détruire le flot de l'algorithme de calcul. Les fonctions lambda en C existent (point zerosquare inside) mais nécessitent de mettre tout le code dans une macro... Ca marche... mais c'est super chiant lorsque ton code a une erreur et qu'il te dit que c'est tout le temps à la ligne 10 (ligne de début de la fonction). J'ai limité la casse en faisant en sorte d'éviter le trampoline.
* Pourquoi te compliques tu la vie à éviter le trampoline si c'est pour quand même utiliser les nested function ? Parce que les trampoline, c'est leeeeennnnnnnt !
Si je reprend mon exemple de fibonnacci avec pthread, en le modifiant pour faire utiliser une nested function:
int fib(int n)
{
if (n < 2)
return n;
struct fib2_s f;
may_spawn_block_t b;
may_spawn_start(b);
f.n = n - 2;
#if 0
may_spawn (b, subfunc_1, &f);
#else
void subfunc_2 (void *data) {
f.x = fib(f.n);
}
may_spawn (b, subfunc_2, &f);
#endif
int y = fib (n-1);
may_spawn_sync(b);
return f.x + y;
}
j'obtiens:
Fibonacci number #39 is 63245986. Calculated in 21.206 seconds using 2 workers.
Et oui, faire un saut indirect récursif vers une fonction dont l'adresse change tout le temps est super couteux !
Donc, c'est bon j'ai décidé, et je pars implanter çà proprement dans MAYLIB... ce fut la galère
Il me reste à savoir comment gérer la pile algébrique de MAYLIB. Pour mes tests, j'ai modifié la fonction karatsuba de maylib:
MAY_SPAWN_BLOCK(block, mark);
MAY_SPAWN(block, (a,i,n), {
/* A(X_i) = A1(X_i^2)*X_i+A2(X_i^2) */
split (&a1, &a2, a, i);
/* (A1+A2)*(B1+B2) with j */
a1pa2 = add (a1, a2, n);
}, (a1, a2, a1pa2));
/* B(X_i) = B1(X_i^2)*X_i+B2(X_i^2) */
split (&b1, &b2, b, i);
/* B(X_i) = B1(X_i^2)*X_i+B2(X_i^2) */
b1pb2 = add (b1, b2, n);
MAY_SPAWN_SYNC(block);
MAY_SPAWN(block, (a1pa2, b1pb2, j, n), {
a1pa2fb1pb2 = karatsuba(a1pa2, b1pb2, j, n, mark);
}, (a1pa2fb1pb2));
MAY_SPAWN(block, (a1, b1, j, n), {
/* A1*B1 with j */
a1fb1 = karatsuba (a1, b1, j, n, mark);
}, (a1fb1));
/* A2*B2 with j */
a2fb2 = karatsuba (a2, b2, j, n, mark);
MAY_SPAWN_SYNC(block);
(Ok, ca rend le code un poil plus difficile à lire. Mais pas trop).
1) première version:
pour la première version, j'ai décidé de couper le restant de la pile algébrique en deux lors d'un spawn, et que chaque thread se la partage en deux (chaque thread à ainsi sa propre heap qu'il accède via une variable globale définit par l'attribut __thread). Tout est créée dans la même pile et tout se compacte à la fin d'un coup.
Le GC (Garbash Collector) est désactivé lors d'un block paralléle.
Simple, pas très élégant, ... et ne fonctionne pas du tout !
L’algorithme de divide & conquer épuise rapidement la pile de 10 Go (à chaque étape on perd la moitié du restant de la pile, ce qui fait que rapidement il ne reste rien).
On abandonne donc cette mauvaise idée.
2) seconde version.
Pour cette version, toutes les allocations se font au sein de la pile algébrique donc l'accès à plusieurs thread est autorisé. Afin d'optimiser les performances (et éviter le mutex !), j'ai utilisé le add atomic du C11 atomic_fetch_add (ou __sync_fetch_and_add pour les gnuismes). La pile est augmenté de facon atomique et chaque thread à son alloc qui va bien. Par contre, le free a été supprimé - seul un GC permet de récupérer les données - et le realloc modifié pour toujours réallouer de la mémoire.
Je suis arrivé à la faire fonctionner, mais elle a un défault : elle consomme 3x plus de mémoire qu'avant (et est bien plus lente) !