Je ne pouvais pas paralléliser chacune des boucles vectorisées, car la parallélisation a un sur-coût trop important.
Attention à ne pas confondre architectures vectorielles et instructions SIMD (type SSE ou AltiVec). C'est vraiment pas pareil [1]. :-) Un processeur vectoriel des familles implémente une certaine forme de parallélisme de données (donc SIMD), mais fonctionne vraiment différemment d'une instruction SIMD. Mais ce n'est pas très important.
Dans ton exemple de boucle, les instructions SIMD que tu utilises permettent d'obtenir du parallélisme d'instruction (ILP). Il s'agit de parallélisme à grain fin, et oui dans ce cas, on va choisir les boucles les plus internes, car l'overhead (le surcoût) est minimal [2]. C'est aussi quelque chose de possible uniquement parce que tu as un jeu de données extrêmement régulier (mêmes bornes pour tous tes vecteurs, ou bien il est possible de s'arranger pour que la boucle ait les bonnes propriétés). Lorsque tu veux paralléliser un ensemble d'instructions par contre (et pas l'instruction elle-même), tu dois passer par des mécanismes à grain plus gros (pthread, tâche OpenMP, processus MPI, etc.). Et dès lors, oui, bien sûr, il y a un coût pour initialiser les constructions parallèles, l'initialisation de la liste des tâches de ton programme, etc. Que ce soit écrit avec des pthread_create() ou via une construction Cuda, je ne vois pas ce que ça change: ça reste du bête parallélisme de données. Il faudra donc avoir suffisamment de données à fournir à une des tâches créées pour cacher le coût de création de la tâche elle-même, mais je ne vois pas ce qu'il y a de nouveau là-dedans.
Du coup, tu as quand même titillé ma curiosité : quel langage as-tu utilisé pour paralléliser ta boucle ? S'il s'agit d'OpenMP, quel compilateur ? (Par exemple, l'implémentation d'Intel dans leur compilateur est notoirement meilleure que celle de gcc...) Et surtout, surtout, quelle était la taille de tes vecteurs ?
Quant à la vectorisation en règle générale, j'estime qu'un compilateur suffisamment évolué devrait savoir gérer les cas relativement simples sans passer par un humain (de la même manière qu'un bon compilateur C devrait savoir reconnaître for (i=0;i<N;++i) a[i] = 0; et remplacer le tout par un appel à memset(a,0,N*sizeof(type_de_a))). Le compilateur d'Intel le fait, gcc sait le faire dans une certaine mesure, si je ne me trompe pas le compilateur d'IBM le fait pour POWER, etc.
Ici c’est trivial, mais sur un algo. un poil complexe, je ne vois pas comment : par exemple le parcours d’un arbre, je vois bien comment le paralléliser en donnant un sous-arbre à chaque process, par contre je ne sais pas comment le vectoriser.
C'est vrai, mais je ne vois pas le rapport avec les GPU. En fait c'est même pire, les GPU sont notoirement mauvais pour traiter d'opérations sur les graphes en parallèle. Par contre, si tu as les bons outils (et là, je vais ressortir Cilk, que j'ai cité plus haut), tu utilises ... Cilk, qui est parfait pour ça (enfin dans certaines limites quand même), propose une approche divide-and-conquer de la parallélisation, et a même permis d'obtenir des programmes de d'IA pour échecs parmi les plus performants (ça commence à dater, mais Socrates a, à plusieurs reprises, fini dans le top 5 de grosses compèt' d'IA d'échecs vers la fin des années 90).
Cela dit, tu as raison de faire remarquer que le plus gros des applications gourmandes en ressources et tournant sur des gros calculateurs étaient en majorité des applications très régulières en termes structures de contrôle (if, while, etc.). D'où l'importance de trucs genre TOP500, avec comme seule métrique le nombre d'opérations flottantes par seconde (FLOPS).
Mais avec l'apparition des réseaux sociaux, etc., on s'aperçoit enfin dans les sphères du HPC que la métrique est peut-être un peu désuète (ou en tout cas incomplète). D'où la création fin 2010 du challenge Graph500 (patrick_g avait fait une news sur le sujet à l'époque). Ici la métrique est plutôt le nombre de nœuds traversés à la seconde si je me souviens bien, dans un parcours en largeur.
Donc si tu me dis que la parallélisation d'un programme dépend fortement des structures de données utilisées pour traiter un problème donné, je suis d'accord, mais je ne vois pas ce que ça change par rapport à la programmation séquentielle : en fait, si tu veux vraiment passer par une boucle for parallèle pour traverser une arbre par exemple, tu peux parfaitement recourir aux mêmes stratagèmes et algos utilisés pour parcourir un arbre de façon itérative et pas récursive. Il suffit d'utiliser une pile pour simuler les niveaux de récursion. Comme en plus il s'agit d'un arbre, tu sais que les nœuds ne peuvent pas être partagés (les données qu'ils contiennent par contre, c'est une autre histoire). Évidemment, un arbre n'est pas forcément équilibré, et dès lors on se retrouve avec un problème d'équilibrage de charge (mais là encore, Cilk avait fait fort et avait montré qu'ils pouvaient avoir un ordonnancement proche de l'optimal — mais, ironiquement, pas forcément le plus efficace).
Mais je digresse. Tout ça pour dire que je ne suis pas sûr de voir le rapport entre ce que je disais à propos des GPU (et surtout il faut faire bien attention : les GPU Nvidia n'ont rien à voir avec ceux d'AMD du point de vue architectural), et du fait qu'ils ne réinventaient pas vraiment grand chose pour quelqu'un qui a du bagage en prog parallèle, et ce que tu racontes à propos de la vectorisation — qui est vrai hein, c'est juste que j'appelle pas ça de la parallélisation au sens où la plupart des gens l'entendent. :)
[1] Même si par ailleurs, les instructions SIMD sont clairement inspirées par les machines vectorielles.
[2] Dans ce cas précis on peut carrément le considérer comme nul.
[^] # Re: Par pitie
Posté par lasher . En réponse au journal Du livre "Premiers cours de programmation en Scheme". Évalué à 3.
Attention à ne pas confondre architectures vectorielles et instructions SIMD (type SSE ou AltiVec). C'est vraiment pas pareil [1]. :-) Un processeur vectoriel des familles implémente une certaine forme de parallélisme de données (donc SIMD), mais fonctionne vraiment différemment d'une instruction SIMD. Mais ce n'est pas très important.
Dans ton exemple de boucle, les instructions SIMD que tu utilises permettent d'obtenir du parallélisme d'instruction (ILP). Il s'agit de parallélisme à grain fin, et oui dans ce cas, on va choisir les boucles les plus internes, car l'overhead (le surcoût) est minimal [2]. C'est aussi quelque chose de possible uniquement parce que tu as un jeu de données extrêmement régulier (mêmes bornes pour tous tes vecteurs, ou bien il est possible de s'arranger pour que la boucle ait les bonnes propriétés). Lorsque tu veux paralléliser un ensemble d'instructions par contre (et pas l'instruction elle-même), tu dois passer par des mécanismes à grain plus gros (pthread, tâche OpenMP, processus MPI, etc.). Et dès lors, oui, bien sûr, il y a un coût pour initialiser les constructions parallèles, l'initialisation de la liste des tâches de ton programme, etc. Que ce soit écrit avec des
pthread_create()ou via une construction Cuda, je ne vois pas ce que ça change: ça reste du bête parallélisme de données. Il faudra donc avoir suffisamment de données à fournir à une des tâches créées pour cacher le coût de création de la tâche elle-même, mais je ne vois pas ce qu'il y a de nouveau là-dedans.Du coup, tu as quand même titillé ma curiosité : quel langage as-tu utilisé pour paralléliser ta boucle ? S'il s'agit d'OpenMP, quel compilateur ? (Par exemple, l'implémentation d'Intel dans leur compilateur est notoirement meilleure que celle de gcc...) Et surtout, surtout, quelle était la taille de tes vecteurs ?
Quant à la vectorisation en règle générale, j'estime qu'un compilateur suffisamment évolué devrait savoir gérer les cas relativement simples sans passer par un humain (de la même manière qu'un bon compilateur C devrait savoir reconnaître
for (i=0;i<N;++i) a[i] = 0;et remplacer le tout par un appel àmemset(a,0,N*sizeof(type_de_a))). Le compilateur d'Intel le fait, gcc sait le faire dans une certaine mesure, si je ne me trompe pas le compilateur d'IBM le fait pour POWER, etc.C'est vrai, mais je ne vois pas le rapport avec les GPU. En fait c'est même pire, les GPU sont notoirement mauvais pour traiter d'opérations sur les graphes en parallèle. Par contre, si tu as les bons outils (et là, je vais ressortir Cilk, que j'ai cité plus haut), tu utilises ... Cilk, qui est parfait pour ça (enfin dans certaines limites quand même), propose une approche divide-and-conquer de la parallélisation, et a même permis d'obtenir des programmes de d'IA pour échecs parmi les plus performants (ça commence à dater, mais Socrates a, à plusieurs reprises, fini dans le top 5 de grosses compèt' d'IA d'échecs vers la fin des années 90).
Cela dit, tu as raison de faire remarquer que le plus gros des applications gourmandes en ressources et tournant sur des gros calculateurs étaient en majorité des applications très régulières en termes structures de contrôle (if, while, etc.). D'où l'importance de trucs genre TOP500, avec comme seule métrique le nombre d'opérations flottantes par seconde (FLOPS).
Mais avec l'apparition des réseaux sociaux, etc., on s'aperçoit enfin dans les sphères du HPC que la métrique est peut-être un peu désuète (ou en tout cas incomplète). D'où la création fin 2010 du challenge Graph500 (patrick_g avait fait une news sur le sujet à l'époque). Ici la métrique est plutôt le nombre de nœuds traversés à la seconde si je me souviens bien, dans un parcours en largeur.
Donc si tu me dis que la parallélisation d'un programme dépend fortement des structures de données utilisées pour traiter un problème donné, je suis d'accord, mais je ne vois pas ce que ça change par rapport à la programmation séquentielle : en fait, si tu veux vraiment passer par une boucle for parallèle pour traverser une arbre par exemple, tu peux parfaitement recourir aux mêmes stratagèmes et algos utilisés pour parcourir un arbre de façon itérative et pas récursive. Il suffit d'utiliser une pile pour simuler les niveaux de récursion. Comme en plus il s'agit d'un arbre, tu sais que les nœuds ne peuvent pas être partagés (les données qu'ils contiennent par contre, c'est une autre histoire). Évidemment, un arbre n'est pas forcément équilibré, et dès lors on se retrouve avec un problème d'équilibrage de charge (mais là encore, Cilk avait fait fort et avait montré qu'ils pouvaient avoir un ordonnancement proche de l'optimal — mais, ironiquement, pas forcément le plus efficace).
Mais je digresse. Tout ça pour dire que je ne suis pas sûr de voir le rapport entre ce que je disais à propos des GPU (et surtout il faut faire bien attention : les GPU Nvidia n'ont rien à voir avec ceux d'AMD du point de vue architectural), et du fait qu'ils ne réinventaient pas vraiment grand chose pour quelqu'un qui a du bagage en prog parallèle, et ce que tu racontes à propos de la vectorisation — qui est vrai hein, c'est juste que j'appelle pas ça de la parallélisation au sens où la plupart des gens l'entendent. :)
[1] Même si par ailleurs, les instructions SIMD sont clairement inspirées par les machines vectorielles.
[2] Dans ce cas précis on peut carrément le considérer comme nul.