Bonsoir,
Comment fait-on pour calculer le dedré de parallélisme d'une application?
Merci
Version imprimable
Bonsoir,
Comment fait-on pour calculer le dedré de parallélisme d'une application?
Merci
degré ??
A priori une application est parallèle ou non.
Si c'est pour savoir si elle est parallélisable ou non, à ce compte là c'est un degré de parallélisation, pas de parallélisme...
Dans les 2 cas, si c'est pour savoir un "degré", il faut regarder le code et voir quelle partie est/n'est pas parallélisée(parallélisable), et faire le rapport entre ça et le reste... Soit en volume de code (pas très intéressant), soit en temps de calcul (le plus intéressant).
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 :(
bof ... :?
comme je disais, ça ne me semble pas correspondre à une définition admise communément..
si je suis ta définition :
la même appli s'exécutant sur 4 processeurs aurait un degré supérieur de parallélisme que si elle s'exécutait sur 2 ???? même si elle tourne à la même vitesse ??? c'est assez farfelu...
re-bof....
Il faut tenir compte ET du nombre de processeurs ET de la vitesse d'exécution, si c'est ce genre de mesure...
Je dirais si elle s'exécute 2 fois plus vite avec 4 processeurs qu'avec 2 (ou 4 fois plus vite qu'avec 1 seul), c'est qu'elle possède un degré 100% (à quelques chouias près) de parallélisme.
Si elle va aussi lentement avec 1, 2, ou 4 processeurs, c'est qu'elle a un degré 0 de parallélisme (ellle n'est pas parallélisée).
Oui, je comprends ce que vous voulez m'expliquer et je vois que la définition que j'ai trouvé n'est pas suffisante. :)Citation:
Envoyé par souviron34
Merci beaucoup
Je me permets de remonter ça pour préciser.
On parle de degré de parallélisme par rapport à un graphe de tâches. Ton application peut être découpée en tâches, ces tâches sont éventuellement contraintes les unes par rapport aux autres (par exemple A doit s'exécuter avant B).
Le degré de parallélisme est le nombre maximale de ces tâches que tu peux exécuter simultanément. Tu peux trouver ça par exemple en utilisant l'algo flot max/coupe min.
Non, c'est par rapport aux tâches (avec ou sans graphes. ça peut être une liste, ça peut ne pas être découpé du tout en "tâches"...), mais aussi au code et aux liens de telle partie avec telle autre partie, etc etc...Citation:
Envoyé par Furikawari
Non.... ça renverrait au nombre de processeurs....Citation:
Envoyé par Furikawari
C'est la proportion (%) qui peut être exécuté parallèllement... (comme je disais, si tu ne disposes que de 2 processeurs, un code parallélisé à 50% tournera n (1.25 ou 1.50 ou...) fois plus vite de toutes façons... Si tu disposes de 4 processeurs, il ne tournera pas à la même vitesse.. Et pourtant il a le même degré de parallélisme..
8OCitation:
Envoyé par Furikawari
Encore une fois, tu peux avoir 80% du code non parallélisable, mais qui ne prend que 0.2% du temps, alors que 20% du code, parallélisable, prendra 99.8% du temps....
Ecoute je t'ai donné la définition théorique de degré de parallélisme, je pourrais te donner en ref un excellent bouquin co-écrit par mon directeur de thèse sur le sujet...
Rmq : quand je dis nombre de tâches que tu peux exécuter simultanément, ça n'a rien à voir avec le nombre de processeur. Le mot processeur n'apparaît jamais dans mon post.
Citation:
Envoyé par Furikawari
oui, j'ai bien compris..
MAIS...
Admettons que l'on ait à faire une multiplication de 5 matrices... ou une boucle...
tu auras beau avoir parallélisé ton code, si tu n'as que 2 processeurs, tu ne pourras faire que 2 choses à la fois. Si tu en as 4, 4...
Donc détermines-moi le "nombre de tâches exécutables simultanément" ????
Si tu as parallélisé, tu auras :Code:
2
Comment trouves-tu le nombre de tâches ???Code:
2
3
4
Le degré de parallélisme est indépendant du nombre de processeurs.
je suis bien d'accord, par conséquent ce n'est PAS le nombre de tâches pouvant être faites simultanément.. :PCitation:
Envoyé par Furikawari
1- Ce n'est pas la taverne là, on évite de jouer sur les mots de façon inutile
2- C'est le nombre de tâches exécutables simultanément si tu considères avoir un nb de procs infini. Ca te va mieux comme ça ?
C'est une définition théorique sur le graphe des tâches, c'est tout.
Justement, on n'est pas sur la taverne. On est dans le forum algorithme, donc on est précis..Citation:
Envoyé par Furikawari
La question était :
ça n'a rien de théorique.... Surtout avec "un nb de procs infinis". Ta définition est inutilisable dans la vraie vie..Citation:
Envoyé par acacia
Donc, on a donné une solution réelle, non théorique.. C'est tout..
Dans le cadre du parallélisme ce terme a une définition précise qui est celle que j'ai donnée. Pas celle que tu aimerais lui donner.
donc, tu es en train de me dire que, si j'ai un programme qui :
- a 90% de son code non parallélisable (linéaire)
- a 10% de son code qui est une boucle de 1 à 10000
le degré de parallélisme est 10 000 ????
C'est absurde...
Tu le fais exprès dis moi ?
En maths y'a des définitions, en physique y'a des définitions... Et en informatique aussi ! Je viens d'en donner une, qu'elle te plaise ou non n'est pas le sujet du post.
non, je ne le fais pas exprès.. Ce qu'il y a , c'est qu'en maths ou en physique, les définitions sont non seulement théoriques, mais veulent dire quelque chose et sont utilisables dans la pratique..Citation:
Envoyé par Furikawari
Je t'ai posé une question...
J'attend la réponse..
Si c'est ce que tu dis, cela veut dire que donc le degré d'un programme tel que je mentionne est 10 000 ?
La réponse est oui.
alors c'est ce que je disais..
Cette "définition" est absurde car non utile...
Et tu peux bien montrer notre dialogue à ton directeur de thèse, je persiste et signe...
Vu qu'alors ce "degré de parallèllisme" est ainsi indépendant de la portion de code touchée, augmentons les % cités plus haut et prenons un cas réel :
Admettons que le programme que je mentionne plus haut fasse 1 million de lignes de code.. dont 99.999 % linéaire...
On aurait donc 999 990 lignes de code linéaire, où A->B->C etc..., plus une boucle sur 10 lignes qui pourrait être (éventuellment) parallélisée... avec un degré 10 000.
Et la mesure du degré de paralléllisme de l'application serait 10000 .... :aie:
Alors que si je prenais cette même application, modifiée, dont 999 990 lignes seraient parallélisables et parallélisées, et qu'il ne reste que 10 lignes linéaires, elle aurait le même degré de paralléllisme...
C'est tout simplement inutile comme mesure et comme définition, sans plus...
Alors je veux bien que cela soit la définition que vous utilisiez, mais elle ne veut rien dire...
par exemple :
- si l'on se base sur cette mesure pour prévoir le temps/charge de travail/budget pour la parallélliser, on se trompe de 99%..
- si l'on se base sur cette mesure pour savoir quel temps on gagnerait en passant de 1 à 8 processeurs, on se trompe totalement, si par exemple ce qui prend le plus de temps est la partie linéaire..
- si l'on se base sur cette mesure pour savoir la complexité, c'est faux également, puisque dans la partie linéaire on peut avoir un algo non paralléllisable de complexité bien supérieure...
Je ne peux pas voir l'utilité d'une telle "définition"...
Et moi je ne comprends pas ton acharnement sur une définition... Si ton code est aussi linéaire que le "cas réel" que tu sors de ton chapeau, tu en as tout simplement rien à foutre du degré de parallélisme.
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 :Citation:
Envoyé par Furikawari
la demande est pratique, pas par rapport à une définition théorique qui ne peut pas s'appliquer.Citation:
Envoyé par acacia
Et que si il y a plusieurs "définitions" comme celle que tu dis utiliser, ou celle-ci :
Laquelle croire ???Citation:
Envoyé par acacia
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.Citation:
Envoyé par souviron34
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.
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 :D
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."Citation:
Envoyé par souviron34
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..
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
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 ...Citation:
Envoyé par FR119492
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) :Citation:
Envoyé par alex_pi
- 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 :
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).Citation:
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'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.....
=rand(1,300) dans Word ;)Citation:
Envoyé par FR119492
8-)Citation:
Envoyé par Obsidian
Citation:
Envoyé par Furikawari
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".Citation:
Envoyé par alex_pi
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.
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 :
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à)Citation:
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
- An o[n3/z3] reduction procedure for determining the maximum degree of parallelism in parallel applications
Si c'était uniquement la définition donnée par Furikawari, il n'y aurait aucun problème....Citation:
The problem of determining the maximum degree of parallelism in the control flow of such applications is under consideration.
- Effects of Parallelism Degree on Run-Time Parallelization of Loops
Si il y en a des différents, c'est que la mesure n'est pas absolue....Citation:
In this paper, we present two parallelization techniques that exploit different degrees of parallelism for loops with dynamic cross-iteration dependences
- Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)
Ce n'est donc pas le maximum....Citation:
The key observations and differences are that the degree of parallelism (i.e. number of processors or cores) is bounded by O(log n),
- A heuristic approach for finding a solution to the constant-degreeparallelism alignment problem
Citation:
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
Pas la même défintion...Citation:
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.
- Dynamically adapting the degree of parallelism with reflexive programs
Encore une fois pas une mesure absolue...Citation:
The modularity of this approach and its application-independence permit a general use on parallel computers with a scalable degree of parallelism.
CQFD :D
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.Citation:
Envoyé par FR119492
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.
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... :)Citation:
Envoyé par alex_pi
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...
Merci beaucoup pour ces liens Souviron, ça m'aide baeucoup :)Citation:
Envoyé par souviron34
de rien :DCitation:
Envoyé par acacia
Google + "degree parallelism"
(+ un peu de temps libre)