Degré de parallélisme

**souviron34** · 27/02/2009, 10h33

Envoyé par Furikawari

Comme beaucoup de définition elle a un champ d'application. Effectivement tu peux l'appliquer à des cas où elle est inutile et dire qu'elle ne sert à rien. C'est très convaincant comme approche.

Je dis juste que quand quelqu'un pose une question comme celle-ci :

Envoyé par acacia

Comment fait-on pour calculer le dedré de parallélisme d'une application?

la demande est pratique, pas par rapport à une définition théorique qui ne peut pas s'appliquer.

Et que si il y a plusieurs "définitions" comme celle que tu dis utiliser, ou celle-ci :

Envoyé par acacia

En fait j'ai trouvé dans un cour que le degré du parallélisme est le nombre de processeurs s'exécutant en parallèle

Laquelle croire ???

et quand en plus aucune des deux n'est satisfaisante, mon esprit scientifique me dit simplement que ce n'est pas correct ni utile pour répondre à la question du PO.

Quant à ton Directeur de Thèse, je ne sais ni quel age il a ni quel parcours il a eu, mais je suis au moins aussi bien placé que lui, bien que non chercheur, pour apprécier l'informatique et ses concepts J'étais en thèse que tu n'étais même pas conçu, et peut-être lui non plus...

Maintenant, puisque Dieu a parlé sous la forme de ce que tu sais, je m'incline...

**Furikawari** · 27/02/2009, 10h47

Envoyé par souviron34

Je dis juste que quand quelqu'un pose une question comme celle-ci :

la demande est pratique, pas par rapport à une définition théorique qui ne peut pas s'appliquer.

Et que si il y a plusieurs "définitions" comme celle que tu dis utiliser, ou celle-ci :

Laquelle croire ???

et quand en plus aucune des deux n'est satisfaisante, mon esprit scientifique me dit simplement que ce n'est pas correct ni utile pour répondre à la question du PO.

Quant à ton Directeur de Thèse, je ne sais ni quel age il a ni quel parcours il a eu, mais je suis au moins aussi bien placé que lui, bien que non chercheur, pour apprécier l'informatique et ses concepts J'étais en thèse que tu n'étais même pas conçu, et peut-être lui non plus...

Maintenant, puisque Dieu a parlé sous la forme de ce que tu sais, je m'incline...

Bon moi aussi je réponds une dernière fois... Un petit apparté d'abord : c'est un peu saoûlant de te voir toujours vouloir avoir raison.

L'OP a posé une question sur un terme d'un domaine qui admet une définition précise dans ledit domaine. Que la définition te plaise ou non, c'est la définition admise point barre.

Je ne vois pas ce que l'âge a à voir là dedans, est-ce que la connaissance est l'apanage des plus âgés uniquement ?

Quand à la référence à mon directeur de thèse (thèse que j'ai bouclée moi aussi il y a un certain nombre d'années moi aussi), c'était juste une façon discrète de te faire remarquer que je connaissais "un petit peu" le domaine, malgré mon "jeune âge" (enfin tout est relatif...), ce qui semble être un critère important à tes yeux.

**souviron34** · 28/02/2009, 00h09

Je me permet simplement de douter de l'expression de cette définition..

Et peut-être que tu es plus au courant que moi de cette discipline, certainement, même, puisque je n'ai aucune connaissance théorique en informatique.. J'ai cependant été chercheur, et en astrophysique, les "définitions " et les "théories" se font et se défont...

Or doncques j'argue simplement du fait que cette définition ne me semble ni correcte (puisqu'elle amène très rapidement un contre-exemple pour lequel tu me parles de "champ d'application"), ni utile, car le "degré" que l'on pourrait en tirer ne donne aucune indication sur l'application qu'il est censé caractériser.

Je suis prêt à venir en discuter un jour si nous nous retrouvons dans la même ville

Peace, man

alex_pi · 01/03/2009, 11h07

Envoyé par souviron34

Quant à ton Directeur de Thèse, je ne sais ni quel age il a ni quel parcours il a eu, mais je suis au moins aussi bien placé que lui, bien que non chercheur, pour apprécier l'informatique et ses concepts J'étais en thèse que tu n'étais même pas conçu, et peut-être lui non plus...

Ah le bon vieil argument d'autorité... "Ca fait 30 ans que je code en C depuis ma thèse en physique et que je refuse de regarder le moindre autre langage, alors j'en sais plus que quiconque sur tous les domaines informatique."
Du souviron34 dans toute sa splendeur.

Peut être que la définition donnée par Furikawari a plus pour but d'être appliqué à une partie intéressante du programme qu'à son ensemble.. Genre si on a un solveur 3-SAT dont on cherche le degré de parallélisme, effectivement, on va plus regarder la partie solveur que le parseur ou le pretty printer.

Ensuite tu dis "il y a deux définitions". Malheureusement, ce sont exactement les mêmes... Puisque "le nombre de processeur s'exécutant", si on ne veut pas que le degré de parallélisme d'un programme dépende de la machine, il faut supposer qu'il y a un nombre infini de processeurs et regarder combien son effectivement utilisés, ce qui fait que l'on recoupe celle de Furikawari.

M'enfin, comme d'habitude, tu vas dire que je fais partie de tout ces jeunes c*n prétentieux qui ne comprennent rien à la valeur de ton expérience..

**FR119492** · 01/03/2009, 12h09

Bonjour à tous.
Je trouve amusant de vous voir vous étriper pour de telles futilités (je n'ai pas écrit utilités). Pour ma part, l'informatique est une science expérimentale: si l'on veut mettre en compétition diverses méthodes, on les essaie et on chronomètre. Les notions plus ou moins fumeuses telles que complexité, parallélisme, etc. ne jouent qu'un rôle secondaire; ce qu'on attend de notre travail, c'est de l'efficacité.
Une autre approche assez efficace est la suivante: vous vous servez une bière bien fraiche, vous vous asseyez confortablement dans un fauteuil, vous fermez les yeux et vous regardez défiler les diverses méthodes en compétition.
Jean-Marc Blanc

**Obsidian** · 01/03/2009, 13h46

Envoyé par FR119492

Une autre approche assez efficace est la suivante: vous vous servez une bière bien fraiche, vous vous asseyez confortablement dans un fauteuil, vous fermez les yeux et vous regardez défiler les diverses méthodes en compétition.

C'est effectivement une méthode de recherche intéressante qui, à mon avis, n'est ni meilleure ni pire qu'une autre. Toutefois, pour être tout-à-fait impartial, il faudrait mesurer son efficacité en scientifique, en corrélant le nombre de bières par méthode trouvée, et en remplaçant la bière par d'autres substances telles que café, gin, vodka ...

**souviron34** · 01/03/2009, 13h57

Envoyé par alex_pi

Ensuite tu dis "il y a deux définitions". Malheureusement, ce sont exactement les mêmes... Puisque "le nombre de processeur s'exécutant", si on ne veut pas que le degré de parallélisme d'un programme dépende de la machine, il faut supposer qu'il y a un nombre infini de processeurs et regarder combien son effectivement utilisés, ce qui fait que l'on recoupe celle de Furikawari.

Non, je pense qu'il y a au moins 2 définitions (si je ne compte pas la "mienne"), dans ce thread (enfin, il me semble. Mais de toutes façons, peu importe, c'est la définition, et pas leur nombre, qui pose problème) :

le nombre de processeurs s'éxécutant : si je reprend mon exemple avec une boucle de 10 000, si j'ai une machine à 8 processeurs, le degré serait 8. Vu qu'avoir une machine à 10 000 processeurs est inenvisageable (en tous cas pour une utilisation "normale"). Si je reprend ce que tu dis, une évaluation d'un "degré de parallélisme" d'une application qui ne dépendrait pas de la machine est bien lié au pourcentage de temps que l'on gagnerait à utiliser y compris le "nombre théorique" de processeurs, non ?? Et dans ce cas il faut bien tenir compte de si ce nombre théorique (admettons que tu dises que ce soit la même définition que l'autre) accélerais l'application, non ?? Sinon à quoi cela sert-il ??
le nombre maximal de tâches piuvant être faites en parallèle : le degré est 10 000

Donc d'une part le "degré" n'est pas le même;

Secondo encore une fois qu'elle est l'utilité d'une telle mesure et d'une telle définition ?

Je pose sincèrement la question. Je n'en vois pas, car ça ne relie en rien ni la durée d'exécution, ni l'éventuel avantage à multiplier par 2 (ou 4 ou 8) le nombre de processeurs, ni le temps nécessaire ou l'intérêt pour paralléliser l'application, ni quoi que ce soit d'utile pour évaluer l'application ou même l'algorithme..

Quand tu cites :

Genre si on a un solveur 3-SAT dont on cherche le degré de parallélisme, effectivement, on va plus regarder la partie solveur que le parseur ou le pretty printer.

D'une part là on parle d'un algorithme et non d'une application (ce qui n'était pas le problème soulevé par le PO).

D'autre part, admettons que j'ai dans cette partie solveur une boucle de 1 à 10 000 ET, dans le parseur un algo linéaire, qui prend la majeure partie du temps.

A quoi cela peut-il bien me servir de savoir que mon degré est 10 000 dû à la partie solveur ????

Je vais au contraire me focaliser sur quelque chose qui n'apportera qu'un gain marginal, même si je mettais le nombre maximal de processeurs.....

**souviron34** · 01/03/2009, 14h00

Envoyé par FR119492

Une autre approche assez efficace est la suivante: vous vous servez une bière bien fraiche,

=rand(1,300) dans Word

Envoyé par Obsidian

il faudrait mesurer son efficacité en scientifique, en corrélant le nombre de bières par méthode trouvée, et en remplaçant la bière par d'autres substances telles que café, gin, vodka ...

**souviron34** · 01/03/2009, 14h10

Envoyé par Furikawari

Je ne vois pas ce que l'âge a à voir là dedans, est-ce que la connaissance est l'apanage des plus âgés uniquement ?
... c'était juste une façon discrète de te faire remarquer que je connaissais "un petit peu" le domaine, malgré mon "jeune âge" (enfin tout est relatif...), ce qui semble être un critère important à tes yeux.

Envoyé par alex_pi

Ah le bon vieil argument d'autorité...
...
Du souviron34 dans toute sa splendeur.
..
M'enfin, comme d'habitude, tu vas dire que je fais partie de tout ces jeunes c*n prétentieux qui ne comprennent rien à la valeur de ton expérience..

Je ne répond de cette manière que quand on m'assène une Vérité avec un grand V en me disant "de toutes façons c'est ce que j'ai appris et c'est forcément bon Et si vous critiquez c'est que vous êtes obtus".

Le bon sens existe aussi.

Et comme le dit Jean-Marc, on nous demande d'être efficace.

En quoi est-ce qu'une définition inutile est-elle à suivre ??

Ce que je soulève simplement (et si je réfère à l'age je répète que c'est parce que vos affirmations sont théoriques) c'est que d'une part nous ne faisons pas affaire avec la théorie mais la pratique, et d'autre part que si une définition ou une théorie s'avère avoir des failles, on en change, quand on a un minimum l'esprit scientifique. C'est tout.

Même Einstein et sa Relativité Générale sont battus en brêche depuis 15 ans. Alors en Théorie de l'Informatique, pourquoi cela ne serait pas le cas ???

PS: si j'étais un de vos profs et non un intervenant sur ce forum, vous ne me renverriez pas comme ça. Et je n'aurais donc pas à me justifier comme je le fais ici.

**souviron34** · 01/03/2009, 16h57

Bon..

Comme je commençais à en avoir marre de me faire taper dessus pour oser contredire la définition de Furikawari, j'ai fait moi-même une petite (mini) biblo sur le net..

Voici ce que je trouve, qui montre bien que la notion de "degré de parallèlisme" ainsi que la définition n'est pas "coulée dans le bronze"..

A Practical Approach to Parallel Computing

Page 2 :

1.2 Degree of parallelism :

For executing a program successfully, different numbers of processors must be required at different time periods. The total number of processors required to execute this program in each such time period is known as the degree of parallelism. An efficient parallel program has a high degree of parallelism

On ne parle donc là que du degré d'une période de temps, d'une partie du programme, et non de la totalité de l'application... Ce qui fait la dernière phrase.... (et mon argumentation depuis le début de ce débat-là)
An o[n3/z3] reduction procedure for determining the maximum degree of parallelism in parallel applications

The problem of determining the maximum degree of parallelism in the control flow of such applications is under consideration.

Si c'était uniquement la définition donnée par Furikawari, il n'y aurait aucun problème....
Effects of Parallelism Degree on Run-Time Parallelization of Loops

In this paper, we present two parallelization techniques that exploit different degrees of parallelism for loops with dynamic cross-iteration dependences

Si il y en a des différents, c'est que la mesure n'est pas absolue....
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)

The key observations and differences are that the degree of parallelism (i.e. number of processors or cores) is bounded by O(log n),

Ce n'est donc pas le maximum....
A heuristic approach for finding a solution to the constant-degreeparallelism alignment problem

This paper studies the problem of finding a computation mapping and data distributions that minimize the number of remote data accesses for a given degree of parallelism.
The degree of parallelism

In this paper, the degree of parallelism is introduced and investigated. The degree of parallelism is a natural descriptional complexity measure of Lindenmayer and Bharat systems. This concept quantifies the amount of non-redundant parallelism needed in the derivations of those systems.

Pas la même défintion...
Dynamically adapting the degree of parallelism with reflexive programs

The modularity of this approach and its application-independence permit a general use on parallel computers with a scalable degree of parallelism.

Encore une fois pas une mesure absolue...

CQFD

alex_pi · 01/03/2009, 16h58

Envoyé par FR119492

Je trouve amusant de vous voir vous étriper pour de telles futilités (je n'ai pas écrit utilités). Pour ma part, l'informatique est une science expérimentale: si l'on veut mettre en compétition diverses méthodes, on les essaie et on chronomètre. Les notions plus ou moins fumeuses telles que complexité, parallélisme, etc. ne jouent qu'un rôle secondaire

Ca veut dire quoi "l'informatique est une science expérimentale" ? C'est quoi "une science expérimentale" ? Personnellement, je n'en connais aucune. Si on prend la physique par exemple, il est généralement admis que Stephen Hawking est un des plus grand physicien des 50 dernières années. Il ne faut pas longtemps pour se rendre compte que ça ne doit pas être une "science expérimentale". Ce qui n'empêche pas qu'elle ait des composante expérimentale.

Toi tu vois l'informatique comme étant "programmer un ordinateur". C'est sans doute ton boulot et c'est une partie légitime de l'informatique. Mais on ne peut pas la résumer à ça ! Comme disait Dijkstra (je suis sûr que souviron appréciera), "Computer science is no more about computers than astronomy is about telescopes." (L'informatique n'est pas plus la science des ordinateurs que l'astronomie est celle des télescopes (traduction libre

))

Oui, il y a des gens qui s'intéresse au parallélisme d'un point de vue théorique. Ca peut te sembler inutile, mais il faut bien se rendre compte que c'est pourtant indispensable. En effet, le nombre de coeur sur les processeurs a de bonne chance d'être ce qui va le plus augmenter dans les années à venir (à la place de la fréquence d'horloge). Il va donc bien falloir qu'on trouve un meilleur modèle de programmation parallèle que les bon vieux threads et locks... Puisque l'expérience prouve que ça passe très mal à l'échelle.

Et certaines approches (marchera, marchera pas, effectivement, l'expérience le dira, mais le design nécessite de la théorie) consistent à détecter automatiquement les parties parallélisable. Il faut bien avoir une définition précises (même si elle contient un brin d'arbitraire) du degré de parallélisation, et pas juste pour se toucher la nouille (si vous me passez l'expression).

Il faut bien se rendre compte que si personne ne se posait de questions théoriques, on programmerait encore à la bande perforée ou aux loquets sur la face avant de la machine. Alors bon, peut être qu'à cause de ça, il y a moins de veritables, mais je persiste à penser que ça a pas mal apporté à l'informatique, même celle appliquée et expérimentale.

**souviron34** · 01/03/2009, 17h02

Envoyé par alex_pi

mais je persiste à penser que ça a pas mal apporté à l'informatique, même celle appliquée et expérimentale.

Ok, mais regarde mes liens ci-dessus, et tu verras qu'effectivement, d'une part c'est de la recherche, et d'autre part même les définitions ne sont pas aussi limpides que Fukirawari voulait bien le laisser entendre...

**souviron34** · 01/03/2009, 17h11

je rajouterais d'ailleurs que justement, ce dont tu parles pour "détecter automatiquement les parties parallélisables" rejoint les divers papiers cités, comme quoi c'est difficile, et la mesure n'est pas simple... Ce que je soutiens depuis le début de cet aparté... Car le PO (qui par ailleurs avait été satisfait de ma réponse ) demandait l'évaluation pour une application...

**acacia** · 02/03/2009, 00h20

Envoyé par souviron34

Bon..

Comme je commençais à en avoir marre de me faire taper dessus pour oser contredire la définition de Furikawari, j'ai fait moi-même une petite (mini) biblo sur le net..

Voici ce que je trouve, qui montre bien que la notion de "degré de parallèlisme" ainsi que la définition n'est pas "coulée dans le bronze"..