next up previous contents index
Next: La scalabilité de Up: Scalabilté Previous: La scalabilité d'architecture

La scalabilité d'application

 

La scalabilité d'application décrit les relations entre les performances d'une machine parallèle et la taille du problème considéré.

L'analyse de scalabilité doit se faire pour une architecture donnée et pour une application donnée. En principe, ces deux éléments sont indissociables. La question à laquelle on veut répondre est la suivante: quelles sont les lois d'échelle qui régissent les performances d'une architecture parallèle pour une application donnée. Les quantités qui interviennent dans cette analyse de scalabilité sont nombreuses. On citera les principales:

On pourrait définir formellement la scalabilité comme suit:

L'architecture X est scalable pour l'application Y si le speedup obtenu sur une machine de taille p est égale à p, quelque soit n la taille de l'application.

Comme le montrent les exemples du paragraphe gif cette définition est trop exigente et pratiquement aucune machine ne serait scalable. On préfère donc un définition plus nuancée.

La scalabilité s'exprime à travers la notion d'efficacité  E qui est le rapport entre le speedup obtenu pour une application de taille n et le nombre de processeurs p utilisé

 

est le temps d'exécution du meilleur algorithme séquentiel résolvant le problème et est le temps de l'algorithme parallèle considéré. L'efficacité indique quelle fraction des performances potentielles on obtient d'une application parallèle.

Une efficacité de 1 correspond a un speedup de p, ce qui est évidemment idéal. En géneral, ce n'est pas le cas, mais la question est ici de savoir s'il est possible d'agrandir suffisament la taille n du problème afin que sur p processeurs, l'efficacité soit acceptable. En effet, de la loi de Gustafson , on s'attend à ce que, pour p donné, plus n est grand, plus l'efficacité est bonne.

Pour donner un sens quantitatif à cette notion, on exprime la relation gif sous la forme

La fonction F est appelé la fonction d'isoefficacité  qui décrit comment la taille du problème doit augmenter pour avoir un efficacité donnée E avec p processeur. Ceci dépend évidemment de l'algorithme parallèle choisi et des possibilités offertes par l'architecture consiérée. Il peut y avoir une autre fonction d'isoefficacité si l'on change d'algorithme ou de machine. La scalabilité est définie comme suit:

Un algorithme est scalable sur une architecture donnée si la fonction d'isoefficacité existe.

Pour mieux comprendre cette définition, reprenons les exemples du paragraphe gif. Dans le cas de la solution de l'équation de Laplace, on avait obtenu un speedup

est le nombre total de points de grille. Ce speedup implique une efficacité

Clairement, si n est assez grand, l'efficacité peut être rendue aussi proche de 1 que désiré. L'isoefficacité est obtenue en extrayant n de la relation ci-dessus

Pour un nombre de processeurs p donné, on peut donc adapter la taille du problème n pour avoir une efficacité E choisie. La fonction d'isoefficacité ci-dessus indique que la taille du problème doit croître linéairement avec p. Plus l'efficacité exigée est grande, plus le coefficient devant p augmente. Mais ce résultat implique avant tout que la fonction d'isoefficacité soit linéaire en p, donc que le problème soit parfaitement scalable sur un ensemble de processeurs organisés selon une grille tri-dimensionnelle.

Par contre, dans le problème à N-corps décrit au paragraphe gif, les choses se passent moins bien. Le speedup vaut (n est le nombre de corps en interaction et p=M le nombre de processeurs)

d'où une efficacité

Le point crucial est qu'ici, l'efficacité ne dépend plus de la taille n du problème. Par conséquent, il n'est pas possible d'exprimer n en fonction de p. La fonction d'isoefficacité n'existe pas et le problème n'est pas scalable sur un anneau de processeurs. Cela n'empêche toutefois pas de paralléliser l'application car si T>>C, on aura de toute façon un gain de temps intéressant. Par contre, on n'obtiendra pas une efficacité optimale au niveau algorithmique.

Dans ces deux exemples, on voit que l'architecture joue un rôle important dans la discussion car l'expression du speedup dépend du modèle d'architecture utilisé pour définir l'algorithme parallèle.

Entre les deux extrêmes que nous venons de voir (isoefficacité linéaire et non définie), il existe toute une gamme de possibilités. L'application est plus ou moins bien scalable selon la dépendance de la fonction d'isoefficacité F. On peut parler de



next up previous contents index
Next: La scalabilité de Up: Scalabilté Previous: La scalabilité d'architecture



CHOPARD Bastien
Fri Dec 1 14:37:08 MET 1995