Analyse paralleler Algorithmen

In der Informatik die Analyse parallel Algorithmen ist der Prozess des Findens des Rechenkomplexität von parallel ausgeführte Algorithmen - Zeit, Speicher oder andere Ressourcen, die zur Ausführung erforderlich sind. In vieler Hinsicht, Analyse paralleler Algorithmen ist ähnlich wie die Analyse von sequentiellen Algorithmen, ist aber im Allgemeinen mehr involviert, weil man über das Verhalten mehrerer kooperierender Ausführungsfäden bereiten muss. Eines der Hauptziele der parallelen Analyse ist es zu verstehen, wie sich ein paralleler Algorithmus nutzt (Geschwindigkeit, Platz usw.) durch die Anzahl der Prozessoren.

Hintergrund

Ein sogenannter Arbeitszeit (WT) (manchmal als Work-Tiefe oder Arbeitspanen) wurde ursprünglich von Shiloach und Vishkin eingeführt [1] zur Konzeption und Beschreibung paralleler Algorithmen. Im WT -Framework wird ein paralleler Algorithmus zunächst in Bezug auf parallele Runden beschrieben. Für jede Runde sind die zu ausgeführten Operationen charakterisiert, aber mehrere Probleme können unterdrückt werden. Beispielsweise muss die Anzahl der Operationen in jeder Runde nicht klar sein, Prozessoren müssen nicht erwähnt werden, und alle Informationen, die bei der Zuweisung von Prozessoren zu Jobs helfen können, müssen nicht berücksichtigt werden. Zweitens werden die unterdrückten Informationen bereitgestellt. Die Einbeziehung der unterdrückten Informationen wird durch den Beweis eines Planungssatzes aufgrund von Brent geleitet.[2] das später in diesem Artikel erläutert wird. Das WT -Framework ist nützlich, da es zwar die anfängliche Beschreibung eines parallelen Algorithmus erheblich vereinfachen kann. Die durch diese anfänglichen Beschreibung unterdrückten Details ist oft nicht sehr schwierig. Zum Beispiel wurde das WT -Framework als grundlegender Präsentationsrahmen in den Büchern der parallelen Algorithmen angewendet (für die Parallele Zufallszugriffsmaschine Kinderwagenmodell)[3] und, [4] sowie in den Klassennotizen.[5] In der folgenden Übersicht wird erläutert, wie das WT -Framework zur Analyse allgemeinerer paralleler Algorithmen verwendet werden kann, selbst wenn ihre Beschreibung im WT -Framework nicht verfügbar ist.

Definitionen

Angenommen, Berechnungen werden auf einer Maschine ausgeführt, die hat p Prozessoren. Lassen Tp Bezeichnen Sie die Zeit, die zwischen dem Beginn der Berechnung und ihrem Ende abläuft. Analyse der Berechnungen Laufzeit Konzentriert sich auf die folgenden Vorstellungen:

  • Das Arbeit einer Berechnung von durchgeführt von p Prozessoren sind die Gesamtzahl der primitiven Operationen, die die Prozessoren ausführen.[6] Wenn Sie die Kommunikationsaufwand von der Synchronisierung der Prozessoren ignorieren, entspricht dies der Zeit, die für die Ausführung der Berechnung eines einzelnen Prozessors verwendet wird, bezeichnet T1.
  • Das Tiefe oder Spanne ist die Länge der längsten Reihe von Operationen, die nacheinander durchgeführt werden müssen Datenabhängigkeiten (das kritischer Weg). Die Tiefe kann auch die genannt werden Kritische Pfadlänge der Berechnung.[7] Das Minimieren der Tiefe/Spannweite ist wichtig für die Gestaltung paralleler Algorithmen, da die Tiefe/Spannweite die kürzester Ausführungszeit bestimmt.[8] Alternativ kann die Spanne als die Zeit definiert werden T∞ Verbrückte Computing mit einer idealisierten Maschine mit unendlicher Anzahl von Prozessoren.[9]
  • Das kosten der Berechnung ist die Menge ptp. Dies drückt die Gesamtzeit aus, die alle Prozessoren sowohl beim Computer als auch im Warten aufgewendet haben.[6]

Aus den Definitionen von Arbeit, Spannweite und Kosten folgen mehrere nützliche Ergebnisse:

  • Arbeitsrecht. Die Kosten sind immer zumindest die Arbeit: ptp ≥ T1. Dies folgt aus der Tatsache, dass p Prozessoren können höchstens abschneiden p parallele Operationen.[6][9]
  • Spalte Gesetz. Eine endliche Nummer p von Prozessoren kann eine unendliche Zahl nicht übertreffen, so dass das so Tp ≥ T∞.[9]

Unter Verwendung dieser Definitionen und Gesetze können die folgenden Leistungsmaßnahmen angegeben werden:

  • Beschleunigen ist der Geschwindigkeitsgewinn, der durch parallele Ausführung im Vergleich zur sequentiellen Ausführung erzielt wird: Sp = T1 / Tp. Wenn die Beschleunigung ist Ω (n) Für Eingangsgröße n (Verwendung Big O Notation), die Beschleunigung ist linear, was in einfachen Berechnungsmodellen optimal ist, da das Arbeitsgesetz impliziert, dass dies impliziert T1 / Tp ≤ p (Superlinearer Geschwindigkeit kann in der Praxis aufgrund von auftreten Speicherhierarchie Auswirkungen). Die Situation T1 / Tp = p wird als perfekte lineare Geschwindigkeit bezeichnet.[9] Ein Algorithmus, der linearer Geschwindigkeit aufweist skalierbar.[6]
  • Effizienz ist die Beschleunigung pro Prozessor, Sp / p.[6]
  • Parallelität ist das Verhältnis T1 / T∞. Es stellt die maximal mögliche Beschleunigung für eine beliebige Anzahl von Prozessoren dar. Nach dem Gesetz über Spannwesen begrenzt die Parallelität die Beschleunigung: wenn p > T1 / T∞, dann:

.[9]

  • Das Schlaffheit ist T1 / (pt∞). Eine Lockerheit, die weniger als einer impliziert (nach dem Spannungsgesetz), dass perfekte lineare Beschleunigung unmöglich ist p Prozessoren.[9]

Ausführung einer begrenzten Anzahl von Prozessoren

Die Analyse paralleler Algorithmen wird normalerweise unter der Annahme durchgeführt, dass eine unbegrenzte Anzahl von Prozessoren verfügbar ist. Dies ist unrealistisch, aber kein Problem, da jede Berechnung, die parallel auf ausgeführt werden kann N Prozessoren können ausgeführt werden p < N Prozessoren, indem jeder Prozessor mehrere Arbeitseinheiten ausführen lässt. Ein Ergebnis genannt Brents Gesetz gibt an, dass man eine solche "Simulation" rechtzeitig ausführen kann Tp, begrenzt durch[10]

oder weniger genau,[6]

Eine alternative Aussage der Rechtsgrenzen Tp oben und unten nach

.

zeigen, dass die Spannweite (Tiefe) T∞ und die Arbeit T1 Zusammen bieten angemessene Grenzen für die Berechnungszeit.[2]

Verweise

  1. ^ Shiloach, Yossi; Vishkin, Uzi (1982). "Ein O(n2Protokolln) Parallel Max-Flow-Algorithmus ". Journal of Algorithmen. 3 (2): 128–146. doi:10.1016/0196-6774 (82) 90013-x.
  2. ^ a b Brent, Richard P. (1974-04-01). "Die parallele Bewertung allgemeiner arithmetischer Ausdrücke". Journal of the ACM. 21 (2): 201–206. Citeseerx 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.
  3. ^ Jaja, Joseph (1992). Eine Einführung in parallele Algorithmen. Addison-Wesley. ISBN 978-0-201-54856-3.
  4. ^ Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Praktische Kinderwagenprogrammierung. Wiley-Interscience. ISBN 978-0-471-35351-5.
  5. ^ Vishkin, Uzi (2009). Paralleles Denken: Einige grundlegende datenparallele Algorithmen und Techniken, 104 Seiten (PDF).Klassennotizen von Kursen zu parallelen Algorithmen, die seit 1992 an der University of Maryland, dem College Park, der Tel Aviv University und dem Technion unterrichtet wurden.
  6. ^ a b c d e f Casanova, Henri;Legrand, Arnaud;Robert, Yves (2008). Parallelalgorithmen. CRC Press. p. 10. Citeseerx 10.1.1.466.8142.
  7. ^ Blelloch, Guy (1996). "Parallelalgorithmen programmieren" (PDF). Kommunikation der ACM. 39 (3): 85–97. Citeseerx 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.
  8. ^ Michael McCool;James Reinders;Arch Robison (2013). Strukturierte parallele Programmierung: Muster für eine effiziente Berechnung. Elsevier. S. 4–5.
  9. ^ a b c d e f Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Einführung in Algorithmen (3. Aufl.).MIT Press und McGraw-Hill.S. 779–784. ISBN 0-262-03384-4.
  10. ^ Gustafson, John L. (2011)."Brent's Theorem". Enzyklopädie des parallelen Computers. S. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.