Optimiert für MS Internet Explorer mit 1024 X 768
| Inhalt | |||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Wer war Amdahl ? Gene Amdahl war in den 60 er Jahren ein Mitarbeiter von IBM. Er arbeitete als Computerentwickler und entwickelte dabei speziell starke Vektorrechner, die auf Grund von parallelisierter Abarbeitung von Befehlen, Gleitkommaberechnungen sehr schnell ausführen können sollten. Der Ursprung des Amdahl´schen Gesetzes Vor einigen Jahren, als Firmen immer mehr Daten verarbeiten schneller verarbeiten konnten, gingen sie daran immer kühnere Forschungsprojekte auszuarbeiten, so daß ebenfalls der Bedarf der Firmen an immer leistungsstärkeren Großrechnern stark anstieg. Wissentschaftler erhofften sich eine Beschleunigung langwieriger Berechnungen durch Multiprozessorsysteme. Die erhofften Beschleunigungsraten der Rechengiganten mit bis zu mehreren 1000 Prozessoren blieb aber aus. Mathematische Beweise ergaben die fehlerfreie arbeitsweise der Rechner. Wieso waren die Computer dann aber nicht so schnell wie erhofft ? Wie ensteht das Problem der geringen Leistungssteigerung ? Die Prozessoren sollen parallel ein Prblem bearbeiten. Damit eine Maschine mit n Prozessoren tatsächlich die n-fache Leistung eines einzelnen Prozessors erreicht, müssen immer alle n Prozessoren gleichzeitig arbeiten. In jedem Programm aber gibt es Programmteile, die sich nicht unbegrenzt aufteilen (parallelisieren) lassen. Wenn ein Programmteil nur zwei von n Prozessoren arbeiten läßt, ruhen sich die anderen n-2 Prozessoren aus. Das bedeutet, daß nicht die maximal zur Verfügung stehende Leistung aller n Prozessoren zur Verfügung steht. Dies mindert die gesamte Rechnerleistung drastisch. Kann ein Programmteil eventuell sogar nur einen Prozessor beschäftigen, dann nennt man es sequentiell, anderfalls parallel. Die Aussage des Amdahlschen Gesetzes
Ein einfaches Rechenbeispiel Sei die gesamte Rechenzeit eines Programmes auf einem Rechner gleich 1. Der Anteil der nicht parallelisierbaren Programmteile sei a. Nehmen wir an, a sei a=0.2 . Das soll aussagen, daß 20% eines Programmes nicht parallelisierbar ist. Dann ist (1-a) der Prozentsatz der parallelisierbaren Prgrammteile, die wir so zu 80% annehmen. Dann ergibt sich die Gesamtrechenzeit zu : t = a + (1-a) / n Jetzt testen wir vier Maschinen mit verschiedener Anzahl von Prozessoren auf ihre Laufzeiten hin :
Man erkennt ganz deutlich, daß die Rechenzeit mit steigender Zahl von Prozessoren gegen den Zeitwert 0.2 konvergiert. Und das ist auch klar, da 20% der Programmes sich ja nicht parallelisieren läßt, sprich: Diese 20% des Programms müssen sequentiell abgearbeitet werden. Gut, die Rechenzeit kann gut gegen kleine Werte gedrückt werden, aber wie schaut es jetzt mit der eigentlichen Leistung unserer vier Systeme aus ? Wir werden einfach die relativen Leistungen ermitteln, die uns in Form der Kehrwerte der Rechenzeiten gegeben sind. Sei P die Leistung, dann gilt: P = 1 / (a + (1-a) / n) Nehmen wir nun den Test unserer vier Systeme in Augenschein.
Fazit : # Die Leistung von Systemen steigt nicht parallel mit der Zahl der Prozessoren. # Die maximale Leistung eines Systems konvergiert gegen einen festen Beschleunigungsfaktor, der in unserem Beispiel so bei fünf liegen kann. Dazu eine Grafik Welches sind die Gründe des Verlustes an Leistungssteigerung mit steigender Prozessorzahl ? Mit steigender Zahl der Prozessoren steigt auch der Kommunikationsaufwand zwischen den Prozessoren gewaltig, so daß sie ab einer bestimmten Zahl mehr mit der Kommunikation beschäftigt sind, anstatt das Problem abzuarbeiten. Dies mindert die Leistung gewaltig. Man nennt dies auch einen Overhead in der Aufgabenverteilung. Ein Programm kann nicht vollkommen parallelisiert werden, so daß alle Prozessoren immer gleichzeitig mit arbeit beschäftigt sind. Kann man denn nichts für eine stärkere Ausbeute an Leistung tun, oder besitzt das Amdahl´sche Gesetz immer seine verheerende Aussage ? Doch! Man stelle sich vor, daß alle Prozessoren in einer Baumstruktur angeordnet sind. Dann verläuft die Aufgabenverteilung au alle Prozessoren nicht mehr linear ab, wire wir bis jetzt immer angenommen haben sondern parallel zur Höhe des Baumes, also logarithmisch. So kann man die Leistung des Gesamtsystems steigern. Amdahls Gesetz spielt aber unter Umständen auch nur eine kleine Rolle. Man stelle sich da das Knacken von Verschlüsselungen durch rohe Rechengewalt vor, bei dem man den Faktor a und die Kommunikationszeit im Prinzip gegen null drücken kann. Oder man stelle sich Amdahls Gesetz in einem Multitasking- oder Multiusersystem vor. Druch sequentielle Programmteile können sich arbeitslose Prozessoren in dieser Zeit anderen wichtigen Prozessen widmen. Folgerungen aus dem Amdahl´schen Gesetz Die mögliche Erhöhung der Prozessorzahl eines Systems führt nicht immer zu einer deutlichen Erhöhung der Leistung eines Systems und muß so im Vorherein geprüft (simuliert) werden. Mindestens die wesentlichen Teile eines Programmes (die am häufigsten genutzten Teile) müssen parallelisiert werden, um eine höhere Leistungs zu erziehlen. Mit der Prozessorzahl muß auch die Größe des Problems ansteigen, damit eine steigende parallelisierung dann auch mit steigender absoluter Leistung korrespondiert. Wesentlich für eine hohe Effiziens ist eine gleichmäßige Verteilung der Aufgaben auf die Prozessoren. Material c´t Magazin fuer Computertechnik Ausgabe 26/1998 http://www.uni-karlsruhe.de/~sp2/online-kurs/parallelrechner/node34.html http://www.uni-karlsruhe.de/~sp2/online-kurs/parallelrechner/info/node34.html http://www.uni-karlsruhe.de/~sp2/online-kurs/parallelrechner/info/node35.html http://www.cs.newcastle.edu.au/isaac/preparata.html http://www.cs.orst.edu/~pancake/papers/cse/amdahl.html http://www.npac.syr.edu/techreports/hypertext/sccs-550/node27.html http://csep1.phy.ornl.gov/pt/node30.html |
|||||||||||||||||||||||||||||||||||||||
Optimiert für MS Internet Explorer mit 1024 X 768
|
Wer war Amdahl ? Der Ursprung Das Problem Die Aussage Ein Rechenbeispiel Gründe Folgerungen Material |