s
19 708 Pages

La loi d'Amdahl
Le programme d'un speedup en utilisant plusieurs processeurs dans 'calcul parallèle Elle est limitée par la fraction séquentielle du programme. Par exemple, si la moitié du programme est séquentielle, l'augmentation de la vitesse théorique maximale qui est obtenue à l'aide d'un système distribué serait 2 (1 / (0.5+ (1-0.5) / N)) lorsque N est grand

la La loi d'Amdahl, qui a pris le nom du concepteur dans ordinateur Gene Amdahl, Il est utilisé pour trouver l'amélioration maximale prévue dans l'architecture des ordinateurs ou un système informatique lorsque seules les parties du système sont améliorées. Dans sa forme la plus générale, il peut être exprimé sous la forme:

"L'amélioration qui peut être obtenu sur une certaine partie du système est limitée par la fraction du temps où cette activité a lieu"

qui peut encore être simplifié en règle de pratique:

« Plaider commun rapide » (Amarrez le cas le plus fréquent)

Par exemple: si vous allez pour un chemin de travail 10 minutes en voiture et à 40 minutes à pied, il n'a pas de sens d'acheter une voiture plus rapide.

La loi d'Amdahl est souvent utilisé dans 'calcul parallèle pour prédire l'accélération maximale théorique obtenue en utilisant plusieurs processeurs.

Dans le domaine des systèmes logiciels de loi d'Amdahl peut être interprété en termes plus techniques, mais en termes simples signifie qu'il est le 'algorithme de décider l'augmentation de la vitesse, et non le nombre de processeurs. Tôt ou tard, vous atteignez un point où il ne peut pas être plus paralléliser l'algorithme.

La loi d'Amdahl est une démonstration de la loi de la baisse des rendements: même si nous pouvions augmenter la vitesse d'une partie d'un pour cent de l'ordinateur ou plusieurs fois, si une telle partie ne concerne que 12% traitement global, l'accélération maximale il peut être un facteur .

La loi d'Amdahl
Supposons que le traitement comporte deux parties indépendantes, A et B. B prend environ 25% du temps de l'ensemble du calcul. Travailler très dur, vous pouvez faire cette partie cinq fois plus vite, mais cela réduit légèrement le temps du calcul entier. D'autre part, il peut faire moins de travail à faire partie A deux fois plus vite. Cela rendra le calcul beaucoup plus rapide que par l'optimisation de la partie B, même si B a été accéléré plus (5x par rapport à 2x).

Plus techniquement, la loi considère l'augmentation de la vitesse pouvant être obtenue par une amélioration à un calcul qui affecte une proportion de P de ce calcul, où l'amélioration réduit le temps de calcul d'un facteur S. (Par exemple, si une amélioration peut accélérer 30% du calcul, P Il sera 0,3; si l'amélioration double la vitesse de la partie modifiée, S sera 2.) La loi d'Amdahl déclare que l'augmentation de l'amélioration globale de la vitesse sera produit par

.

Pour voir comment arriver à cette formule, supposons que le temps d'exécution de l'ancien calcul est 1, dans une unité de temps donnée. Le temps d'exécution du nouveau calcul sera le temps nécessaire pour que la fraction non renforcée (qui est 1 - P) De plus le temps pris par la fraction améliorée. Le temps de prise de la partie du calcul amélioré est la partie de la durée d'exécution non encore améliorée divisé par le facteur d'accélération, à savoir P/S. La dernière augmentation de la vitesse est calculée en divisant l'ancien temps d'exécution pour la nouvelle exécution, ce qui entraîne dans la formule ci-dessus.

Voici un autre exemple. Nous avons une tâche décomposable dans les quatre parties suivantes: P1 = 0,11 soit 11%, P2 = 0,18 soit 18%, P3 = 0,23 ou 23%, P4 = 0,48 soit 48%, ayant une somme de 100% . Ensuite, nous n'améliorons pas P1 donc, S1 = 1 soit 100%, d'accélérer P2 par un facteur de 5, donc S2 = 5 soit 500%, d'accélérer P3 par un facteur de 20, alors S3 = 20-à-dire 2000%, et d'accélérer P4 par un facteur 1,6, de sorte S4 = 1,6-dire 160%. En utilisant la formule , nous constatons que le temps d'exécution est à-dire un peu moins de la moitié du temps d'exécution originale que nous savons être 1. Par conséquent, l'accélération globale est , -à-dire, en utilisant la formule , un peu plus de deux fois la vitesse d'origine. Remarquez comment les 20x et 5x accélération ne pas un grand effet sur l'accélération et le temps total de la course, étant donné que plus de la moitié de la tâche n'est accélérée par un facteur de 1,6 ou est accélérée du tout.

parallélisme

Dans le cas particulier du parallélisme, la loi d'Amdahl déclare que si fa est la fraction d'un calcul qui est parallélisable (ie qui peut bénéficier de parallélisme), et (1 - fa) Est la fraction qui ne peut pas être parallélisés, l'augmentation de la vitesse maximale qui peut être obtenue à l'aide N processeurs est

.

A l'extrême, dans le but de N à l'infini, l'accélération tend vers 1 /(1-F). Dans la pratique, le rapport performance / prix baisse rapidement avec l'augmentation N, depuis fa/N devient plus petit que (1-F).

Par exemple, si (1-F) est seulement de 10%, la vitesse de calcul peut être multipliée par dix au maximum, quelle que soit la valeur de N. Pour cette raison, calcul parallèle ou il est utile que pour un petit nombre de processeurs ou des problèmes avec des valeurs très faibles (1-F). Une grande partie de la recherche sur l'informatique parallèle est de tenter de réduire (1-F) à la plus petite valeur possible.

D'autres projets

  • Il contribue à Wikimedia Commons Wikimedia Commons: Il contient des images ou d'autres fichiers La loi d'Amdahl