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).
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...
Non.... ça renverrait au nombre de processeurs....
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..
8O
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.
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:
1
2 for ( i = 0 ; i < 10000 ; i++ ) tache(i) = ...
Comment trouves-tu le nombre de tâches ???Code:
1
2
3
4 for ( i = 0 ; i < 10000 ; i=i+NPCUS ) for ( j = 0 ; j < NCPUS ; j++ tache(i,j) = ... ; }
Le degré de parallélisme est indépendant du nombre de processeurs.
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..
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..
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..
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.