processeur double coeur

Fabien LE LEZ a écrit :

On Thu, 19 Jun 2008 00:53:47 -0700 (PDT), James Kanze
<james.kanze@gmail.com>:

Et voilà le problème dans le C et le C++. Le fait que les
tableaux deviennent très vite des pointeurs, et que le
compilateur ne peut paralleliser que s'il peut établir que les
tableaux (designés par des pointeurs) ne se recouvrent pas.

N'est-il pas envisageable de remplacer vector<> et compagnie par une
classe qui aurait les bonnes propriétés ? Ça peut être une classe
propriétaire, adaptée à un compilo, et que le compilo reconnaît.

Ca ne serait pas le role de std::valarray, comme le suggere Ivan ?
C'est une vraie question, je n'ai jamais utilisé cette classe.

Specialement pour Gaby, puisqu'il connait bien le sujet : est-ce
qu'il y a un traitement particulier de g++ vis-a-vis de std::valarray ?

James Kanze a écrit :

Mais c'est exactement ce genre de calcul vectorisé qui se prête
le mieux à la parallelisation. Les machines vectorielles,
précisement, travaillaient souvent en parallel, et beaucoup de
la recherche dans la parallelisation automatique s'est fait sur
elles, à l'époque. (Recherche du travail de Ken Kennedy, de Rice
University, si ça t'intéresse. J'ai lu plusieurs papiers de lui
sur le sujet fin des années 1980.)

Les machines vectorielles sont une sorte de machine parallèle (je dis
"une sorte de" car il y a eu des débats sans fin sur ce sujet, à mon
avis complètement stériles). Il faut voir que le travail du compilateur
était très simplifié à la fois par le type de parallélisme de ces
machines (type SIMD pour les connaisseurs), et par le travail de
réécriture que les développeurs ont été amenés à faire pour présenter
les boucles comme il fallait au compilateur. De plus les compilateurs
parallélisants étaient presque tous FORTRAN car le FORTRAN 77 n'a pas
l'allocation dynamique et il est bien plus facile de tracer les données
quand il n'y a pas de pointeur.

Pour revenir au fil initial de la discussion qui concernaient la
parallélisation sur les multicores, on se trouve actuellement dans une
situation bien différente. Les architectures processeurs ont été
complètement changées (apparition du RISC, généralisation des
hiérarchies mémoire avec plusieurs niveau de cache, parallélisme type
MIMD, etc.), la technologie hardware a éliminé le TTL et l'ECL pour le
CMOS (n'oublions pas que les mémoires des proc. vectoriels étaient
synchrones avec le CPU !), le marché des processeurs est tiré par les
jeux pas par le calcul intensif (donc disparition des architectures
coûteuses mais performantes), etc.
Bref les architectures sont devenues tellement complexes (par rapport au
vectoriel) qu'aucun humain ni aucun outil ne sait les exploiter. Regarde
Intel ! Il concoivent le processeur (IA64) et le compilo (ICC), et il a
fallu attendre la version 10 de ICC pour commencer à avoir des
performances raisonnables... en séquentiel.

Je pense que ton papier de la fin des années 80 n'est vraisemblablement
plus à jour et que les techniques qui étaient valables à cette époque
sont certainement obsolètes.

A condition que les new aient lieu pas trop loin de la boucle à
optimiser.

Pas forcément. L'argument que j'ai entendu, justement, disait
qu'on n'avait pas besoin de quelque chose de particulier dans le
langage, parce que dans le cas de quelque chose comme
std::vector, le compilateur était capable de reconnaître que la
mémoire utilisée par chaque vecteur ne se recouvrait pas.

Comment fait-il pour voir ce qui se passe dans les éléments du std::vector ?
Si je crée un tableau du type :
class MaClasse { void * data_; /* je gère la mémoire moi-même */ ... };
std::vector< Maclasse > tab;
Comment peut-il savoir si MaClasse est multithread safe ?

Mais les codes numériques allouent généralement les données en
bloc au début, à la lecture des fichiers d'entrée, ce qui fait
qu'au bout de quelques fonctions, le compilateur est largué ne
serait-ce que par la pile d'appel qui devient gigantesque à
traiter.

Le compilateur voit que la fonction prend une référence à un
std::vector (ou quelque chose de semblable) en paramètre, et il
voit que toute la mémoire gérée par la classe a été allouée dans
la classe. Et donc est disjointe de la mémoire de toute autre
instance de la classe.

A la rigueur, je comprends que cela fonctionne pour les types de base,
mais comme écrit plus haut, j'ai des doutes sur les classes de
l'utilisateur.

Si en plus tu fais de la compilation en unités séparées (= une
fonction par fichier), le compilo ne peut plus suivre le lien
et l'analyse interprocédurale ne pourra se faire qu'au link au
mieux.

Ce qui est le cas habituel de nos jours, quand tu démandes de
l'optimisation. (Au moins, c'est le cas avec les versions
récentes de VC++, et de Sun CC. Comme d'habitude, g++ est en
retard, sans doute en partie à cause de sa dépendence sur des
outils externes, comme des éditeurs de liens du système hôte, et
son exigeance de portabilité.)

Je veux bien admettre que g++ est en retard par rapport à un compilo
vendeur.
Par contre, il a à mes yeux une qualité essentielle : il est Open
Source. Et quand on produit du code Open Source, c'est une condition
impérative. Mais ceci est un autre débat... ;-)

L'autre problème qui se pose alors est le volume de calcul
nécessaire (grainsize) pour que le parallélisme puisse être
efficace. Si ta boucle est trop petite (=pas beaucoup
d'instructions), tu seras peut-être parallèle, mais au final
tu ne gagneras rien voire tu perdas du temps à créer tes
threads et à les synchroniser.

C'est vrai si tu veux travailler au niveau Posix (ou de l'API
Windows). Au niveau hardware, il existe en général des
possibilités d'une synchronisation mois chère.

Ceci est vrai avec tous les threads quelle que soit
l'implémentation. Le problème est inhérent au parallélisme et
à la gestion de la dépendance entre les données (=je dois
attendre que la données D soit produite avant de pouvoir
l'utiliser).

Mais je ne vois pas ce que tu veux dire avec le niveau hardware.

Qu'il y a en général des instructions machines qui assure la
synchronisation entre la mémoire et ta CPU (flush du pipeline
d'écriture, purge du pipeline de lecture), et qu'il existe des
algorithmes qui permettent à se resynchroniser à assez peu de
frais si la mémoire est synchronisée.

Ces instructions machine sont pour moi le support hardware à la gestion
des threads. Il me semble que tu es obligé de passer par là pour assurer
la moindre primitive de synchronisation ou de création/destruction de
thread. Tu peux tenter d'écrire toi-même le code assembleur pour
réaliser la synchronisation mais je doute que tu fasses beaucoup mieux
que ce qui est proposé par les bibliothèques de threads. En plus ceci
est loin (très loin) d'être à la portée du programmeur lambda.
Dans le meilleur des cas, le coût de création/destruction d'un thread
est de l'ordre de 100-200 instructions, ce qui est très bon par rapport
au calcul que tu pourrais faire. La synchronisation avec un mutex par
exemple est bien plus coûteuse car elle implique à la fois une lecture
mémoire et une écriture mémoire. Là tu en prends directement pour 2*200
cycles CPU, sans parler des caches misses qui pourraient avoir lieu et
augmenter encore ce chiffre. Tu peux atteindre les 1000 cycles facilement.
Franchement, je ne connais personne qui développe une application en
écrivant directement les instructions machine pour gérer le
parallélisme. Le compilateur fait cela beaucoup mieux que nous, par
contre il faut l'aider énormément, comme d'autres l'ont fait pour la
vectorisation.

Ivan

Michel Decima a écrit :

Ca ne serait pas le role de std::valarray, comme le suggere Ivan ?

Rendons à César, etc., etc. C'est Falk qui a suggéré std::valarray.

C'est une vraie question, je n'ai jamais utilisé cette classe.

Itou

Ivan

On Fri, 20 Jun 2008 00:01:37 +0200, Ivan Dutka-Malen <none@nowhere>:

Je veux bien admettre que g++ est en retard par rapport à un compilo
vendeur.
Par contre, il a à mes yeux une qualité essentielle : il est Open
Source. Et quand on produit du code Open Source, c'est une condition
impérative.

Je ne suis pas sûr de comprendre ce que tu veux dire. De même qu'on
peut développer un code closed-source avec g++, j'ai vu pas mal de
code open-source incapable de compiler sur autre chose que VC++.

Ivan Dutka-Malen <none@nowhere> writes:

Je veux bien admettre que g++ est en retard par rapport à un compilo
vendeur. Par contre, il a à mes yeux une qualité essentielle : il
est Open Source. Et quand on produit du code Open Source, c'est une
condition impérative. Mais ceci est un autre débat... ;-)

Ceci est du code open source:

------------------------------------------------------------------------
/*
Copyright Pascal Bourguignon 2008
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version
2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public
License along with this program; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330,
Boston, MA 02111-1307 USA
*/
#include <iostream>
#include <string>
int main(void){
std::string h="Hello";
h+=" ";
h+="world";
h+="!";
std::cout<<h<<std::endl;
return(0);
}
------------------------------------------------------------------------


Absolument aucun compilateur, ni interpreteur n'a été utilisé pour
produire ce code.

Ou bien, peut être voudrais tu qu'on te fournisse aussi les sources de
mon cerveau en logiciel libre? Demande à Dieu!


--
__Pascal Bourguignon__

Pascal J. Bourguignon a écrit :

Ivan Dutka-Malen <none@nowhere> writes:

Je veux bien admettre que g++ est en retard par rapport à un compilo
vendeur. Par contre, il a à mes yeux une qualité essentielle : il
est Open Source. Et quand on produit du code Open Source, c'est une
condition impérative. Mais ceci est un autre débat... ;-)

Ceci est du code open source:

------------------------------------------------------------------------
/*
Copyright Pascal Bourguignon 2008
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version
2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public
License along with this program; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330,
Boston, MA 02111-1307 USA
*/
#include <iostream>
#include <string>
int main(void){
std::string h="Hello";
h+=" ";
h+="world";
h+="!";
std::cout<<h<<std::endl;
return(0);
}
------------------------------------------------------------------------


Absolument aucun compilateur, ni interpreteur n'a été utilisé pour
produire ce code.

Ou bien, peut être voudrais tu qu'on te fournisse aussi les sources de
mon cerveau en logiciel libre? Demande à Dieu!

Oui vous avez raison. J'ai écrit un peu vite (et tard). Je sais
pertinemment que la production de lignes de code open source n'a a
priori rien à voir avec le choix du compilateur.
Sauf si j'écris :
void f() __attribute__((unused))
{ /* empty */ }
car dans ce cas je fais appel à une fonctionnalité de g++ qui n'a pas la
même syntaxe que celle des autres compilos.
Tout ce que je voulais dire dans ma phrase mal écrite et imprécise c'est
que pour produire du code open source, il est vraiment important de
s'appuyer sur des outils open source (mais aussi de ne pas utiliser les
fonctionnalités qui leur sont spécifiques comme mon exemple le montre).
Voilà ! Loin de moi l'idée de lancer une discussion sur ce sujet off
topic : je ne renchéris pas plus.

Ivan

On Jun 20, 12:01 am, Ivan Dutka-Malen <none@nowhere> wrote:

James Kanze a écrit :

> Mais c'est exactement ce genre de calcul vectorisé qui se prête
> le mieux à la parallelisation. Les machines vectorielles,
> précisement, travaillaient souvent en parallel, et beaucoup de
> la recherche dans la parallelisation automatique s'est fait sur
> elles, à l'époque. (Recherche du travail de Ken Kennedy, de Rice
> University, si ça t'intéresse. J'ai lu plusieurs papiers de lui
> sur le sujet fin des années 1980.)

Les machines vectorielles sont une sorte de machine parallèle
(je dis "une sorte de" car il y a eu des débats sans fin sur
ce sujet, à mon avis complètement stériles). Il faut voir que
le travail du compilateur était très simplifié à la fois par
le type de parallélisme de ces machines (type SIMD pour les
connaisseurs), et par le travail de réécriture que les
développeurs ont été amenés à faire pour présenter les boucles
comme il fallait au compilateur. De plus les compilateurs
parallélisants étaient presque tous FORTRAN car le FORTRAN 77
n'a pas l'allocation dynamique et il est bien plus facile de
tracer les données quand il n'y a pas de pointeur.

Pour revenir au fil initial de la discussion qui concernaient
la parallélisation sur les multicores, on se trouve
actuellement dans une situation bien différente. Les
architectures processeurs ont été complètement changées
(apparition du RISC, généralisation des hiérarchies mémoire
avec plusieurs niveau de cache, parallélisme type MIMD, etc.),
la technologie hardware a éliminé le TTL et l'ECL pour le CMOS
(n'oublions pas que les mémoires des proc. vectoriels étaient
synchrones avec le CPU !), le marché des processeurs est tiré
par les jeux pas par le calcul intensif (donc disparition des
architectures coûteuses mais performantes), etc.

Jusque là, rien à dire.

Bref les architectures sont devenues tellement complexes (par
rapport au vectoriel) qu'aucun humain ni aucun outil ne sait
les exploiter. Regarde Intel ! Il concoivent le processeur
(IA64) et le compilo (ICC), et il a fallu attendre la version
10 de ICC pour commencer à avoir des performances
raisonnables... en séquentiel.

C'est certain qu'il y a des différences, surtout en ce qui
concerne la façon d'assurer la synchronisation. Mais ce sont les
différences par rapport au code qu'il faut générer quand on a
besoin de se résynchroniser. La logique qui détermine si la
parallelisation est possible reste la même, et c'est là la
partie la plus délicat.

Je pense que ton papier de la fin des années 80 n'est
vraisemblablement plus à jour et que les techniques qui
étaient valables à cette époque sont certainement obsolètes.

Pour ce qui concerne les façons de reconnaître quand la
parallelisation s'applique, je ne crois pas.

>> A condition que les new aient lieu pas trop loin de la
>> boucle à optimiser.

> Pas forcément. L'argument que j'ai entendu, justement,
> disait qu'on n'avait pas besoin de quelque chose de
> particulier dans le langage, parce que dans le cas de
> quelque chose comme std::vector, le compilateur était
> capable de reconnaître que la mémoire utilisée par chaque
> vecteur ne se recouvrait pas.

Comment fait-il pour voir ce qui se passe dans les éléments du
std::vector ?

Il regarde le code. Comment veux-tu qu'il le fasse ?

Si je crée un tableau du type :
class MaClasse { void * data_; /* je gère la mémoire moi-même */ ... };
std::vector< Maclasse > tab;
Comment peut-il savoir si MaClasse est multithread safe ?

D'abord, il y a peu de chances qu'il essaie à paralleliser les
opérations sur un tel vector -- la parallelisation concerne
surtout les vector des types de base : double, float et
éventuellement les types entiers. Mais au fond, je ne vois pas
trop où est le problème de base. Le compilateur voit bien
quelles fonctions tu appelles sur Maclasse ; il voit bien ce que
tu y fais ; et il voit bien s'il y est quelque chose qui
pourrait poser un problème. (Dans la doute, évidemment, il ne
parallelise pas.)

>> Mais les codes numériques allouent généralement les données en
>> bloc au début, à la lecture des fichiers d'entrée, ce qui fait
>> qu'au bout de quelques fonctions, le compilateur est largué ne
>> serait-ce que par la pile d'appel qui devient gigantesque à
>> traiter.

> Le compilateur voit que la fonction prend une référence à un
> std::vector (ou quelque chose de semblable) en paramètre, et il
> voit que toute la mémoire gérée par la classe a été allouée dans
> la classe. Et donc est disjointe de la mémoire de toute autre
> instance de la classe.

A la rigueur, je comprends que cela fonctionne pour les types
de base, mais comme écrit plus haut, j'ai des doutes sur les
classes de l'utilisateur.

C'est plus difficile, est moins utile. Mais je ne crois pas
qu'il soit complètement impossible.

[...]

>>>> L'autre problème qui se pose alors est le volume de calcul
>>>> nécessaire (grainsize) pour que le parallélisme puisse être
>>>> efficace. Si ta boucle est trop petite (=pas beaucoup
>>>> d'instructions), tu seras peut-être parallèle, mais au final
>>>> tu ne gagneras rien voire tu perdas du temps à créer tes
>>>> threads et à les synchroniser.

>>> C'est vrai si tu veux travailler au niveau Posix (ou de l'API
>>> Windows). Au niveau hardware, il existe en général des
>>> possibilités d'une synchronisation mois chère.

>> Ceci est vrai avec tous les threads quelle que soit
>> l'implémentation. Le problème est inhérent au parallélisme et
>> à la gestion de la dépendance entre les données (=je dois
>> attendre que la données D soit produite avant de pouvoir
>> l'utiliser).

>> Mais je ne vois pas ce que tu veux dire avec le niveau
>> hardware.

> Qu'il y a en général des instructions machines qui assure la
> synchronisation entre la mémoire et ta CPU (flush du pipeline
> d'écriture, purge du pipeline de lecture), et qu'il existe des
> algorithmes qui permettent à se resynchroniser à assez peu de
> frais si la mémoire est synchronisée.

Ces instructions machine sont pour moi le support hardware à
la gestion des threads. Il me semble que tu es obligé de
passer par là pour assurer la moindre primitive de
synchronisation ou de création/destruction de thread.

C'est ce que j'ai dit, non ?

La création des threads doit obligatoirement avoir lieu au
niveau du système d'exploitation : pthread_create ou son
équivalent sous Windows. Ensuite, en revanche, c'est bien
possible d'utiliser des instructions machine de plus bas niveau
pour synchroniser : ça a un coût, mais ce n'est pas forcément
excessif.

Tu peux tenter d'écrire toi-même le code assembleur pour
réaliser la synchronisation mais je doute que tu fasses
beaucoup mieux que ce qui est proposé par les bibliothèques de
threads.

Ça dépend de comment est impémenter la bibliothèque de thread,
mais il existe bien des algorithmes « non-blocant » pour
certaines opérations, qui donne une performance nettement plus
élevée dans la pratique que d'utiliser pthread_mutex_lock et al.

En plus ceci est loin (très loin) d'être à la portée du
programmeur lambda.

Ça, en revanche...

C'est encore un argument pour le laisser au compilateur:-).

Dans le meilleur des cas, le coût de création/destruction d'un thread
est de l'ordre de 100-200 instructions, ce qui est très bon par rapport
au calcul que tu pourrais faire. La synchronisation avec un mutex par
exemple est bien plus coûteuse car elle implique à la fois une lecture
mémoire et une écriture mémoire. Là tu en prends directement pour 2*200
cycles CPU, sans parler des caches misses qui pourraient avoir lieu et
augmenter encore ce chiffre. Tu peux atteindre les 1000 cycles facilement.
Franchement, je ne connais personne qui développe une application en
écrivant directement les instructions machine pour gérer le
parallélisme. Le compilateur fait cela beaucoup mieux que nous, par
contre il faut l'aider énormément, comme d'autres l'ont fait pour la
vectorisation.

Moi, je connais des gens qui écrivent du code « lock-free »,
pour diverses raisons. Dont la performance. De même, la
parallelisation peut apporter une amélioration importante dans
certains cas. Si tu as une boucle sans dépendences, qui
s'exécute une million de fois, repartir le traitement sur deux
processeurs va bien te gagner plus qu'il ne te coûte pour créer
le deuxième thread et synchroniser les résultats.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Jun 20, 4:24 pm, Ivan Dutka-Malen <none@nowhere> wrote:

Tout ce que je voulais dire dans ma phrase mal écrite et
imprécise c'est que pour produire du code open source, il est
vraiment important de s'appuyer sur des outils open source

Je ne vois pas le rapport. Quand on veut produire du code open
source, je crois le plus important, c'est de l'essayer avec
autant de compilateurs que possible, que ces compilateurs soient
open source ou non.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34