Sortie de la version 4.9 du compilateur GCC

Posté par  (site web personnel) . Édité par Davy Defaud, BAud, Sébastien Koechlin, barmic, khivapia, Nÿco, Storm, Sylvestre Ledru, Florent Zara, palm123 et Xavier Teyssier. Modéré par Xavier Teyssier. Licence CC By‑SA.
Étiquettes :
64
24
avr.
2014
GNU

La nouvelle version majeure du compilateur GCC du projet GNU vient de sortir. Écrit à l’origine par Richard Stallman, le logiciel GCC (GNU Compiler Collection) est le compilateur de référence du monde du logiciel libre. Il accepte des codes source écrits en C, C++, Objective-C, Fortran, Java, Go et Ada, et fonctionne sur une multitude d’architectures.

logo GCC

Dans la suite de la dépêche, vous pourrez découvrir les nouveautés et les optimisations mises en œuvre dans cette version 4.9 de GCC.

Sommaire

Optimisations générales

Ubsan

UndefinedBehaviorSanitizer est un projet initialement développé pour LLVM et qui fait son apparition dans GCC. Il rejoint ainsi ThreadSanitizer et AddressSanitizer qui sont entrés dans GCC 4.8.
Contrairement à valgrind qui lance le programme dans une machine virtuelle, il s’agit comme pour tous les Sanitizers d’instrumenter le code binaire généré. UndefinedBehaviorSanitizer détecte les erreurs qui donnent lieu à un comportement indéfini à l’exécution.
Il s’agit, par exemple, des divisions par zéro, des erreurs de cast de type non aligné, de valeurs en dehors des bornes représentables par le type (énumérations ou flottants).

Cette option s'active avec -fsanitize=undefined et elle est disponible pour les langages C et C++.

Protection de la pile

Les problèmes de débordement de pile sont un problème récurrent dans les programmes, en particulier avec le langage C qui alloue dans le même espace mémoire les variables locales à une fonction, la sauvegarde des registres et la pile d’exécution contenant toutes les adresses de retour.

Une personne mal intentionnée (ou un chercheur en sécurité) peut parfois fournir plus de données que le programme n’est prévu pour en traiter, et cela entraîne un écrasement des autres données. En visant soigneusement, on s’arrange alors pour écraser l’adresse de retour avec une valeur soigneusement calculée pour exécuter des commandes non prévues. Le processeur, à la fin de la fonction, pensant revenir à la fonction appelante, va exécuter du code écrit par l’attaquant, qui n’a rien à voir avec le programme d’origine.

L’idée de base pour se protéger de ce genre de chose est de déposer une valeur secrète juste avant l’adresse de retour, cette valeur est appelée « canari » à l’image des oiseaux utilisés par les mineurs pour détecter les nappes de gaz. Lorsque la fonction se termine, cette valeur est contrôlée. S’il y a eu débordement, la valeur du « canari » est écrasée, elle ne correspond plus et le programme est arrêté avant d’utiliser l’adresse de retour corrompue.

GCC dispose déjà de deux fonctions permettant de mettre un tel mécanisme en place.

L’option -fstack-protector-all, comme son suffixe l’indique, provoque l’ajout d’un canari pour tous les appels de fonction. Cet ajout est coûteux, car il y a plus d’instructions à exécuter, le code est plus long et va diminuer l’efficacité des différents caches.

L’option -fstack-protector provoque l’ajout d’un canari sur toutes les fonctions qui contiennent une variable locale de type chaîne de caractères prévue pour 8 octets ou plus (valeur paramétrable avec l’option --param=ssp-buffer-size=n). Cette option est nettement moins coûteuse, mais laisse pas mal de trous.

Les ingénieurs de Google ont donc développé une troisième alternative appelée -fstack-protector-strong pour améliorer la couverture des canaris sans avoir à l’ajouter à toutes les fonctions d’un programme. Elle est déjà utilisée avec succès dans Chrome OS depuis au moins 10 mois. Par rapport à -fstack-protector, cette option protège également plusieurs autres situations à risque :

  • toutes les fonctions qui utilisent des variables locales contenant des tableaux (En C, tous les tableaux sont susceptibles de déborder par rapport à la taille allouée, les chaînes de caractères n’en sont qu’un cas particulier), y compris si le tableau est dans une structure ou une union ;
  • toutes les fonctions qui utilisent un pointeur vers une autre variable (l’adresse d’une autre variable) ;
  • et toutes les fonctions qui stockent des variables dans les registres.

La version 3.14 du noyau Linux a été également modifiée pour permettre de le compiler avec les différentes options (il n’y a pas d’option pour -fstack-protector-all) :

  • CONFIG_CC_STACKPROTECTOR_NONE n’utilise pas de canaris ;
  • CONFIG_CC_STACKPROTECTOR_REGULAR (anciennement CONFIG_CC_STACKPROTECTOR) pour -fstack-protector ;
  • CONFIG_CC_STACKPROTECTOR_STRONG pour -fstack-protector-strong.

Ingo Molnar a mesuré quelques valeurs par rapport à l’usage de ces options (ces valeurs ne sont pas absolues et dépendent bien évidemment de la configuration générale du noyau) :

  • -fstack-protector augmente la taille du noyau de 0,33 % et protège 2,81 % des fonctions ;
  • -fstack-protector-strong augmente la taille du noyau de 2,4 %, mais protège 20,5 % des fonctions.

Bien que cette méthode ne soit pas parfaite, elle bloque un nombre significatif de problèmes de sécurité dans les applications. Comme toutes ces méthodes, elle a le double désavantage de faire payer à tous les utilisateurs les éventuels bogues de sécurité des applications et de ne pas inciter à la correction de ces problèmes. On peut s’attendre à ce que dans le futur, un certain nombre de distributions soient compilées avec cette option.

Pour aller plus loin :

Améliorations LTO

La technique LTO (pour Link Time Optimization) qui a été introduite dans GCC 4.5 reçoit encore une fois son lot d’améliorations incrémentales.
Cette fonction LTO permet des passes d’optimisations supplémentaires lors de l’édition des liens, au prix d’un temps de compilation et d’une empreinte mémoire largement augmentés.

La version 4.9 de GCC vise à réduire ces coûts afin de permettre une utilisation plus aisée par les distributions. On note en particulier une réécriture de l’algorithme de « _type merging_ », un travail sur les méthodes virtuelles afin de les éliminer le plus tôt possible, un chargement du corps des fonctions à la demande et un déchargement le plus tôt possible.
Tout ces correctifs (et les nombreux autres non cités) constituent une importante amélioration globale de LTO et suppriment des goulets d’étranglements qui existaient dans les versions précédentes de GCC.

Selon les notes de version, l’occupation mémoire d’une compilation LTO de Firefox (avec les symboles de débogage) passe ainsi de 15 Gio à seulement 3,5 Gio. Le temps passé à faire l’édition des liens dégringole, quant à lui, de 1 700 secondes à 350 secondes.

Point important à noter, plusieurs correctifs ont été proposés à Linus afin d’intégrer la possibilité de compiler le noyau en mode LTO. Ces correctifs sont écrits par Andi Kleen et Michal Marek et ont été proposées pour le futur noyau 3.15.
Linus a jugé que ces correctifs étaient encore trop expérimentaux et a demandé des tests prouvant qu’une compilation LTO du noyau apportait vraiment des bénéfices :

So I think I’ll let this wait a bit longer, unless people start talking about the upsides.
How much smaller is the end result? How much faster is it? How much more beautiful is it? Does it make new cool things possible? Are those cool things really close on the horizon and really want this merged even though it’s not really quite ready yet?
So please: convince me.

Après divers échanges sur la LKML il s’avère que, pour l’instant, la fonction LTO de GCC n’apporte que peu de bénéfices en termes de performances sur un projet déjà extrêmement optimisé comme l’est le noyau. En revanche, on observe une réduction de la taille finale du noyau, ce qui intéresse les gens travaillant dans l’embarqué.
Andi Kleen ajoute également que les bancs d’essai utilisés sont peu sensibles aux performances du compilateur et qu’on sous‐estime généralement le gain apporté par LTO.

Langages

ISO C11

La prise en charge de la norme C11 s’améliore encore dans cette version 4.9 de GCC. On note en particulier l’arrivée des types _Atomic, _Generic ainsi que de _Thread_local.
Cette norme C11 est maintenant considérée comme aussi bien prise en charge que l’ancienne C99.

C++1y

On retrouve dans cette nouvelle mouture de GCC plusieurs nouveautés concernant la prise en charge de la future version de C++ (connue sous le nom de C++14).
Le récapitulatif est disponible sur cette page, mais on peut citer les polymorphic lambdas (N3649) ou encore la déduction automatique du type de retour d’une fonction (N3638).

Plus anecdotique, on peut maintenant séparer de longs nombres par un guillemet droit simple afin d’améliorer la lisibilité. On aura ainsi :

int j = 1'048'576'752'870;

au lieu de :

int j = 1048576752870;

OpenMP

GCC 4.9 apporte la prise en charge de la version 4.0 de l’interface de programmation OpenMP.
OpenMP 4.0 est sorti en fin d’année 2013 avec beaucoup de nouveautés, notamment en termes de prise en charge des accélérateurs ou des directives SIMD. La branche GOMP 4.0 de GCC, qui suivait l’évolution de la norme, a permis son inclusion rapide dans la branche principale de GCC.

Une nouvelle option -fopenmp-simd permet d’activer la prise en charge des directives SIMD d’OpenMP sans avoir à suivre les autres directives. Il est également possible de régler plus finement le modèle utilisé pour évaluer le coût de vectorisation des boucles de code. Il suffit de passer l’option -fsimd-cost-model= avec l’une des trois valeurs suivantes : unlimited, dynamic et cheap.

Rappelons que la prise en charge d’OpenMP est une des grandes différences qui distinguent encore GCC et LLVM/Clang, puisque LLVM ne propose aucune prise en charge d’OpenMP dans sa branche principale.

Architectures

AArch64

Avant la déferlante attendue des processeurs ARM 64 bits, on note que GCC 4.9 améliore encore sa couverture du jeu d’instructions ARMv8, avec la prise en charge des fonctions intrinsèques crypto et CRC, mais aussi l’amélioration des performances des intrinsèques de vectorisation SIMD.

La prise en charge de l’architecture AArch64 profite également de l’activation de la passe d’optimisation REE (Redundant Extension Elimination) ainsi que de du LRA (local register allocator).
Le réglage fin de la génération du code émis par GCC est amélioré pour les cœurs de processeur Cortex-A53 et Cortex-A57. Il est également possible d’indiquer au compilateur que l’on vise une architecture de type big.LITTLE via l’option -mcpu=cortex-a57.cortex-a53.

POWER8

Le titanesque et surpuissant POWER8 d’IBM est maintenant pris en charge par GCC 4.9, via l’option -mcpu=power8.
GCC a également été modifié afin de prendre en charge le module HTM (Hardware Transactional Memory) de ces nouveaux processeurs POWER8. C’est dans la bibliothèque libitm qu’a été ajouté un raccourci (fast path) qui profite à fond des circuits spécialisés présents dans le processeur.

Extension AVX512

Les futurs processeurs Intel Xeon Phi Knights Landing et les Intel Core de la génération Skylake ont beau n’être prévus que pour 2015 ou 2016, cette version 4.9 de GCC prend déjà en charge l’extension AVX-512 qui sera incluse dans leurs cœurs de calcul.
AVX-512 est une extension complexe puisqu’elle propose un cœur obligatoire (AVX-512 Foundation) et plusieurs options Conflict Detection Instructions, Exponential and Reciprocal Instructions, Prefetch Instructions) qui seront activées ou pas selon la gamme de processeur.

GCC 4.9 prend en charge toutes ces extensions (le code assembleur, les intrinsèques, l’autovectorisation) qui s’activent via différentes options (par exemple, -mavx512f pour AVX-512 Foundation).

En bref

  • La colorisation automatique des diagnostics émis par le compilateur est maintenant disponible. L’option -fdiagnostics-color=auto permet ainsi de visualiser plus facilement les alertes (warnings) ou les erreurs, ainsi que l’emplacement exact du problème.

  • GCC 4.9 prend maintenant en charge la version 1.2.1 du langage Go (il s’agit de la toute dernière version sortie le 3 mars 2014).

  • On trouve également dans GCC 4.9 la prise en charge de Cilk Plus, l’extension de C et C++ créée par Intel afin de faciliter l’écriture de code parallèle. L’utilisation se fait via l’option -fcilkplus et suit la version 1.2 de l’ABI Cilk Plus.

  • La bibliothèque d’exécution (runtime library) pour le langage C++ se nomme libstdc++. Elle a reçu diverses améliorations dans cette nouvelle version de GCC. Outre les nombreux changements liés à la prise en charge du futur C++14 (par exemple, std::exchange(), std::make_unique ou encore std::shared_lock), l’ajout le plus notable est la prise en charge de <regex> qui fait partie des nouveautés introduites par C++11.

  • De nouvelles options font leur apparition afin d’optimiser le code pour des processeurs récents ou à venir.
    On trouve ainsi -march=silvermont pour le nouveau cœur Atom avec exécution dans le désordre, -march=broadwell pour la déclinaison 14 nm de l’architecture Haswell, ou encore -march=bdver4 pour les futurs cœurs Excavator d’AMD.

Suivre le développement de GCC

Si vous voulez suivre le développement de GCC, sans nécessairement vous plonger dans le détail des commits ou des annonces sur les listes de diffusion, un bon moyen est de suivre le blog de Nick Clifton. Ce développeur GCC propose presque chaque mois une synthèse des nouveautés de la chaîne de compilation GNU.
Lire rétrospectivement les articles concernant GCC 4.9 permet de mieux mesurer tout le travail et les ajouts qui sont incorporés dans cette version :

Aller plus loin

  • # IPoT

    Posté par  (site web personnel) . Évalué à 0.

    Maintenant on peut commencer à spéculer sur la prochaine release de GCC : 4.10 ou 5.0 ?

  • # Valgrind

    Posté par  . Évalué à 9.

    Contrairement à valgrind qui lance le programme dans une machine virtuelle

    Valgrind ne lance pas le programme dans une VM.
    Il désassemble l’exécutable, instrumente le code, le réassemble et l’exécute. Tout ça à la volée, d’où le fait qu’il y ai un ralentissement important en général.

    C’est très bien expliqué dans le papier Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation.

    • [^] # Re: Valgrind

      Posté par  . Évalué à 8.

      Il fait du tissage donc :)

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Articles sur LTO

    Posté par  . Évalué à 7.

    Le blog de Jan Hubička (dév GCC) a des articles détaillés sur GCC, notammement le LTO.

    (et une petite faute à corriger : "les éventuelles bugs")

  • # Une erreur belle comme un arc-en ciel avec des poneys

    Posté par  . Évalué à 1.

    La colorisation automatique des diagnostics émis par le compilateur est maintenant disponible. L'option -fdiagnostics-color=auto permet ainsi de visualiser plus facilement les warnings ou les erreurs ainsi que l'emplacement exact du problème.

    Ça fait le même boulot que colorgcc ?

  • # Coquilles

    Posté par  (site web personnel) . Évalué à 2.

    dans sans avoir à suivre les autres directives

    Le backend AArch64 profite également de l'activation de la passe d'optimisation

    Outre les nombreux changements liéS

    Sinon très bonne dépêche ; j'aurai bien aimé une petite explication pour REE (Redundant extension elimination) et LRA (local register allocator), ça m'avait l'air intéressant.

    • [^] # Re: Coquilles

      Posté par  (site web personnel) . Évalué à 10.

      Coquilles corrigées. Merci.

      • [^] # Re: Coquilles

        Posté par  (site web personnel) . Évalué à 4.

        Merci pour les liens.
        J'avoue n'avoir rien compris au PDF sur LRA, il m'a l'air destiné au gens connaissant bien le fonctionnement interne et les nomenclatures de GCC. Tant pis.

        En revanche le lien sur REE était sympa. Voici un résumé pour les lecteurs pressés :
        Dans certaines situations le compilateur génère des instructions inutiles (car le boulot a en fait déjà été fait), ou bien 2 instructions qui peuvent être fusionnées en une seule. C'est notamment le cas sur x86-64 lorsqu'une valeur 32bits est chargée dans un registre 64bits, et que le processeur étend implicitement cette valeur avec des 0 dans les 32 autres bits (d'où le nom "extension instructions"). Cette passe va donc éliminer les instructions inutiles ou bien fusionner 2 instructions. Le gain de performance est apparemment assez faible sur les processeurs avec ré-ordonnancement dynamique, mais peuvent aller jusqu'à 10% sur Atom par exemple.

  • # CilkPlus

    Posté par  . Évalué à 10.

    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'époque1:

    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 Cilk2.
    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)3:

    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)

    1. CilkPlus est un peu différent, et je connais moins bien, du coup je ne peux garantir qu'il a les mêmes bornes théoriques en temps et espace. ↩

    2. Je ne rentre pas dans les détails, mais disons que si on utilise une pile linéaire classique, cela pose de sérieux problèmes pour pouvoir voler les tâches. Cet article de Matteo Frigo, l'auteur de FFTW explique pourquoi. ↩

    3. Je sais, c'est un peu confusionnant… ↩

    • [^] # Re: CilkPlus

      Posté par  . Évalué à 8.

      J'oubliais le code du main pour OpenMP :

      int main(int argc, char *argv[]) {
   int n,res;
    /* J'omets le code pour lire n sur l'entrée standard */

#   pragma omp parallel
    {
#       pragma omp single 
        {
            res = fib(n);
        }
    }
    printf("fib(%d) = %d\n",n,res);

    return 0;
}

    • [^] # Re: CilkPlus

      Posté par  . Évalué à 5.

      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.

      Il me semblait que limiter le nombre de tâche au nombre de CPU était parfois très contreproductif. Du coup, Cilk serait fortement désavantager. Est-ce le cas ?

      « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

      • [^] # Re: CilkPlus

        Posté par  . Évalué à 8. Dernière modification le 24 avril 2014 à 21:49.

        Oui, il y a des limites avec le Cilk « classique ». Ce qui fait sa force (la notion de fully strict) est en partie sa faiblesse. Cela dit, si j'ai un code fortement récursif (comme le fib de mon exemple), je vais rapidement créer assez de boulot pour le système: chaque fonction appelante est suspendue pour laisser la fonction appelée s'exécuter, mais du coup peut être utilisée par un autre processeur pour continuer le code jusqu'au prochain sync. Donc là où avec OpenMP tu écrirais un truc du genre :

        #pragma omp for schedule(static, SEUIL) // SEUIL est le nombre d'itérations à filer par thread
for (int i = 0; i < N; ++i) 
{
    do_something(i);
}

        … et en Cilk, on ferait plutôt un truc du genre :

        cilk void do_something(int lo, int hi)
{
    if (hi-lo < SEUIL) {
        serial_do_something(lo,hi); // le vrai travail est effectué ici
    } else {
        spawn do_something(lo,   hi/2);
        spawn do_something(hi/2, hi);
        sync;
    }
}

        L'approche diviser-pour-regner est inhérente à la programmation pour Cilk. Après, avec Cilk++

        Le gros « problème » de Cilk (et ses potes Cilk++ et CilkPlus) selon moi, c'est le fait qu'il nécessite de repenser un partie de ses algorithmes, là où avec OpenMP, on peut prendre du code déjà écrit séquentiellement, et « juste » rajouter un pragma au-dessus d'une boucle (en pratique si tu ne fais pas gaffe, tu vas sans doute avoir des perfs pourries, mais ça ne coûte en tout cas pas grand chose d'essayer pour voir, même si tu n'es pas un expert en optimisation de perfs).

        • [^] # Re: CilkPlus

          Posté par  (site web personnel) . Évalué à 2.

          Et niveau perf justement, pour le même genre d'algo, cela se situe ou entre cilk+, openMP, openMP simd et l’auto-vectorisation ? C'est juste des frontend différent ou est-ce que le code diffère complètement ? Est-ce qu'il y a un générateur plus mature qu'un autre ?

          "La première sécurité est la liberté"

          • [^] # Re: CilkPlus

            Posté par  . Évalué à 7.

            Pour le même genre d'algo c'est difficile à dire en fait. OpenMP définit les constructions paralleles, mais ne dit absolument rien à propos de l'ordonnancement (mis à part certaines grandes lignes pour l'ordonnancement des boucles parallèles). De l'autre cote, tu as Cilk qui décrit sous quelles conditions le vol de tache est effectué, le genre de structures de données utilisé pour stocker les piles de chaque thread dans le tas (cactus stack), le genre structures de données utilisé pour stocker les taches en attente (deque—double-ended queue), etc.

            Bref, certaines implémentations d'OpenMP vont faire du vol de tache, d'autres vont avoir une file d'attente unique et centralisée (beurk), mais surtout, OpenMP n'a aucune garantie à apporter pour ce qui est de l'utilisation des ressources. Si j’écris un truc du genre 

            void fork_bomb(int n) {
    printf("%d-th iteration\n");
    if (n > 0) {
#       pragma omp task
        {
            fork_bomb(n-1);
        }
#       pragma omp task
        {
            fork_bomb(n-1);
        }
#       pragma omp taskwait
    }
}

/* ou son equivalent Cilk */
cilk void fork_bomb(int n) {
    printf("%d-th iteration\n");
    if (n > 0) {
        spawn fork_bomb(n-1);
        spawn fork_bomb(n-1);
        sync;
    }
}

            … dans un cas je peux potentiellement avoir 2^n taches créées (même si le taskwait limite quand même pas mal) alors qu'avec Cilk j'ai la garantie d'une exécution bornée en terme d'espace mémoire.

            Par contre avec Cilk, tu es cense faire une synchro depuis la fonction appelante pour collecter les threads générés (ce qui garantit la propriété fully strict, qui nécessite qu'une tache fille se synchronise avec son parent direct), alors qu'OpenMP permet de faire a peu près tout, y compris du "strict-tout-court" (qui ne demande "que" d'avoir une tache qui se synchronise avec un ancêtre lorsqu'elle termine): tu peux créer une hiérarchie de taches, et ne demander à faire une synchro qu'avec une tache tout en haut de l'arbre de création.

            Concernant Cilk+, j'ai regardé de plus près : ils ont une notation "à la Fortran" pour les tableaux, genre

            int tab[MAX][MAX], a[MAX], b[MAX];
for (int i = 0; i < MAX; ++i) 
    tab[i] = 5;

// On peut raccourcir en ecrivant :

tab[0][:] = 5;

// On peut aussi faire des operations sur les tableaux : 
tab[:] = a[:] + b[:];

            Ca marche pour les vrais tableaux et les conteneurs types "vecteurs" (i.e., un truc dont les bornes sont connues).

            Apres, Cilk+ et TBB ou OpenMP ont des objectifs différents, et sont efficaces pour des classes problèmes différents, de ce que j'ai pige. Ça ne veut pas dire que tu ne peux pas faire une ch'tite multiplication de matrices efficacement en Cilk+, juste que faudra sans doute changer l'algo de partitionnement en blocs.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.