Paralleles Rechnen - Parallel computing

Parallel Computing ist eine Berechnungsart, bei der viele Berechnungen oder Prozesse gleichzeitig ausgeführt werden. Große Probleme lassen sich oft in kleinere aufteilen, die dann gleichzeitig gelöst werden können. Es gibt verschiedene Formen des parallelen Rechnens: Bit- , Befehls- , Daten- und Aufgabenparallelität . Parallelität wird seit langem im Hochleistungsrechnen eingesetzt , hat jedoch aufgrund der physikalischen Beschränkungen, die eine Frequenzskalierung verhindern, ein breiteres Interesse gefunden . Da der Stromverbrauch (und folglich die Wärmeerzeugung) von Computern in den letzten Jahren zu einem Problem geworden ist, ist paralleles Rechnen zum vorherrschenden Paradigma in der Computerarchitektur geworden , hauptsächlich in Form von Mehrkernprozessoren .

Parallel Computing ist eng mit Concurrent Computing verwandt – sie werden häufig zusammen verwendet und oft verschmolzen, obwohl die beiden unterschiedlich sind: Parallelität ohne Parallelität (wie Parallelität auf Bitebene ) und Parallelität ohne Parallelität (wie Multitasking) möglich durch Timesharing auf einer Single-Core-CPU). Beim parallelen Rechnen wird eine Rechenaufgabe typischerweise in mehrere, oft viele, sehr ähnliche Teilaufgaben zerlegt, die unabhängig voneinander bearbeitet werden können und deren Ergebnisse anschließend nach Abschluss kombiniert werden. Im Gegensatz dazu adressieren die verschiedenen Prozesse beim Concurrent Computing häufig nicht verwandte Aufgaben; wenn dies der Fall ist, wie es beim verteilten Rechnen typisch ist , können die einzelnen Aufgaben unterschiedlicher Natur sein und erfordern während der Ausführung oft eine gewisse Kommunikation zwischen den Prozessen .

Parallele Computer können grob nach der Ebene klassifiziert werden, auf der die Hardware Parallelität unterstützt, wobei Multi-Core- und Multi-Prozessor- Computer mehrere Verarbeitungselemente innerhalb einer einzigen Maschine aufweisen, während Cluster , MPPs und Grids mehrere Computer verwenden, um auf demselben zu arbeiten Aufgabe. Neben traditionellen Prozessoren werden manchmal spezialisierte parallele Computerarchitekturen verwendet, um bestimmte Aufgaben zu beschleunigen.

In einigen Fällen ist Parallelität für den Programmierer transparent, wie bei Parallelität auf Bit- oder Befehlsebene, aber explizit parallele Algorithmen , insbesondere solche, die Parallelität verwenden, sind schwieriger zu schreiben als sequentielle , da Parallelität mehrere neue Potenzialklassen einführt Softwarefehler , von denen Race-Conditions die häufigsten sind. Kommunikation und Synchronisation zwischen den verschiedenen Teilaufgaben sind typischerweise einige der größten Hindernisse für eine optimale parallele Programmleistung.

Eine theoretische Obergrenze für die Beschleunigung eines einzelnen Programms als Ergebnis der Parallelisierung wird durch das Gesetz von Amdahl gegeben .

Hintergrund

Traditionell wurde Computersoftware für serielle Berechnungen geschrieben . Um ein Problem zu lösen, wird ein Algorithmus konstruiert und als serieller Befehlsstrom implementiert. Diese Anweisungen werden auf einer zentralen Verarbeitungseinheit auf einem Computer ausgeführt. Es kann immer nur eine Anweisung gleichzeitig ausgeführt werden – nachdem diese Anweisung beendet ist, wird die nächste ausgeführt.

Paralleles Rechnen verwendet andererseits mehrere Verarbeitungselemente gleichzeitig, um ein Problem zu lösen. Dies wird erreicht, indem das Problem in unabhängige Teile zerlegt wird, so dass jedes Verarbeitungselement seinen Teil des Algorithmus gleichzeitig mit den anderen ausführen kann. Die Verarbeitungselemente können vielfältig sein und Ressourcen wie einen einzelnen Computer mit mehreren Prozessoren, mehrere vernetzte Computer, spezialisierte Hardware oder eine beliebige Kombination der oben genannten umfassen. Historisch wurde paralleles Rechnen für das wissenschaftliche Rechnen und die Simulation wissenschaftlicher Probleme insbesondere in den Natur- und Ingenieurwissenschaften wie der Meteorologie verwendet . Dies führte zum Design paralleler Hard- und Software sowie High Performance Computing .

Die Frequenzskalierung war von Mitte der 1980er Jahre bis 2004 der dominierende Grund für die Verbesserung der Computerleistung . Die Laufzeit eines Programms entspricht der Anzahl der Befehle multipliziert mit der durchschnittlichen Zeit pro Befehl. Wenn alles andere konstant gehalten wird, verringert das Erhöhen der Taktfrequenz die durchschnittliche Zeit, die zum Ausführen eines Befehls benötigt wird. Eine Erhöhung der Frequenz verringert somit die Laufzeit aller rechengebundenen Programme. Die Leistungsaufnahme P eines Chips ist jedoch durch die Gleichung P = C × V 2 × F gegeben , wobei C die Kapazität ist, die pro Taktzyklus geschaltet wird (proportional zur Anzahl der Transistoren, deren Eingänge sich ändern), V die Spannung ist und F ist die Prozessorfrequenz (Zyklen pro Sekunde). Frequenzerhöhungen erhöhen den Stromverbrauch eines Prozessors. Der zunehmende Stromverbrauch der Prozessoren führte schließlich dazu, dass Intel am 8. Mai 2004 seine Tejas- und Jayhawk- Prozessoren abschaffte , was allgemein als das Ende der Frequenzskalierung als vorherrschendes Computerarchitektur-Paradigma bezeichnet wird.

Mit dem Problem des Stromverbrauches und eine Überhitzung des Haupt umgeht Zentraleinheit (CPU oder Prozessor) Hersteller begannen zu produzieren energieeffiziente Prozessoren mit mehreren Kernen. Der Kern ist die Recheneinheit des Prozessors und bei Mehrkernprozessoren ist jeder Kern unabhängig und kann gleichzeitig auf denselben Speicher zugreifen. Multi-Core-Prozessoren haben paralleles Computing auf Desktop-Computer gebracht . Somit ist die Parallelisierung serieller Programme zu einer Mainstream-Programmieraufgabe geworden. Im Jahr 2012 wurden Quad-Core-Prozessoren zum Standard für Desktop-Computer , während Server über 10- und 12-Core-Prozessoren verfügen. Aus dem Mooreschen Gesetz lässt sich vorhersagen, dass sich die Anzahl der Kerne pro Prozessor alle 18–24 Monate verdoppeln wird. Dies könnte bedeuten, dass ein typischer Prozessor nach 2020 über Dutzende oder Hunderte von Kernen verfügen wird.

Ein Betriebssystem kann dafür sorgen, dass auf den verfügbaren Kernen unterschiedliche Aufgaben und Anwenderprogramme parallel laufen. Damit ein serielles Softwareprogramm die Mehrkernarchitektur jedoch voll ausnutzen kann, muss der Programmierer den Code neu strukturieren und parallelisieren. Eine Beschleunigung der Laufzeit von Anwendungssoftware wird nicht mehr durch Frequenzskalierung erreicht, sondern Programmierer müssen ihren Softwarecode parallelisieren, um die zunehmende Rechenleistung von Multicore-Architekturen zu nutzen.

Das Gesetz von Amdahl und das Gesetz von Gustafson

Eine grafische Darstellung des Amdahlschen Gesetzes . Die Beschleunigung eines Programms durch die Parallelisierung wird dadurch begrenzt, wie viel des Programms parallelisiert werden kann. Wenn beispielsweise 90 % des Programms parallelisiert werden können, beträgt die theoretische maximale Geschwindigkeit bei Verwendung von Parallel Computing das 10-fache, unabhängig davon, wie viele Prozessoren verwendet werden.
Angenommen, eine Aufgabe hat zwei unabhängige Teile, A und B . Teil B nimmt ungefähr 25 % der Zeit der gesamten Berechnung in Anspruch. Wenn man sehr hart arbeitet, kann man diesen Teil vielleicht fünfmal schneller machen, aber dies reduziert die Zeit für die gesamte Berechnung nur ein wenig. Im Gegensatz dazu muss möglicherweise weniger Arbeit verrichtet werden, um Teil A doppelt so schnell zu machen. Dadurch wird die Berechnung viel schneller als durch Optimieren von Teil B , obwohl die Beschleunigung von Teil B im Verhältnis größer ist (5-mal gegenüber 2-mal).

Optimalerweise wäre die Beschleunigung durch die Parallelisierung linear – eine Verdoppelung der Anzahl der Verarbeitungselemente sollte die Laufzeit halbieren, eine zweite Verdoppelung sollte die Laufzeit erneut halbieren. Allerdings erreichen nur sehr wenige parallele Algorithmen eine optimale Beschleunigung. Die meisten von ihnen haben eine nahezu lineare Beschleunigung für eine kleine Anzahl von Verarbeitungselementen, die bei einer großen Anzahl von Verarbeitungselementen auf einen konstanten Wert abflacht.

Die potenzielle Beschleunigung eines Algorithmus auf einer parallelen Rechenplattform ist durch das Amdahl-Gesetz gegeben

wo

  • S Latenzzeit ist das Potential Speedup in Latenz der Ausführung der gesamten Aufgabe;
  • s ist die Beschleunigung der Latenzzeit der Ausführung des parallelisierbaren Teils der Aufgabe;
  • p ist der Prozentsatz der Ausführungszeit der gesamten Task bezogen auf den parallelisierbaren Teil der Task vor der Parallelisierung .

Da die S- Latenz < 1/(1 – p ) ist , zeigt dies, dass ein kleiner Teil des Programms, der nicht parallelisiert werden kann, die durch die Parallelisierung verfügbare Gesamtgeschwindigkeit begrenzt. Ein Programm, das ein großes mathematisches oder technisches Problem löst, besteht typischerweise aus mehreren parallelisierbaren Teilen und mehreren nicht parallelisierbaren (seriellen) Teilen. Wenn der nicht parallelisierbare Teil eines Programms 10 % der Laufzeit ausmacht ( p = 0,9), können wir nicht mehr als eine 10-fache Geschwindigkeit erreichen, unabhängig davon, wie viele Prozessoren hinzugefügt werden. Dies setzt der Nützlichkeit des Hinzufügens weiterer paralleler Ausführungseinheiten eine Obergrenze. „Wenn eine Aufgabe aufgrund sequenzieller Beschränkungen nicht aufgeteilt werden kann, hat der Mehraufwand keine Auswirkungen auf den Zeitplan. Die Geburt eines Kindes dauert neun Monate, egal wie viele Frauen zugewiesen werden.“

Eine grafische Darstellung des Gustafsonschen Gesetzes

Das Gesetz von Amdahl gilt nur für Fälle, in denen die Problemgröße festgelegt ist. In der Praxis werden mit zunehmender Verfügbarkeit von Rechenressourcen diese eher für größere Probleme (größere Datensätze) verwendet, und die Zeit, die im parallelisierbaren Teil verbracht wird, wächst oft viel schneller als die inhärent serielle Arbeit. In diesem Fall gibt das Gesetz von Gustafson eine weniger pessimistische und realistischere Einschätzung der parallelen Leistung:

Sowohl das Gesetz von Amdahl als auch das Gesetz von Gustafson gehen davon aus, dass die Laufzeit des seriellen Teils des Programms unabhängig von der Anzahl der Prozessoren ist. Das Gesetz von Amdahl geht davon aus, dass das gesamte Problem eine feste Größe hat, so dass die Gesamtmenge der parallel zu erledigenden Arbeit auch unabhängig von der Anzahl der Prozessoren ist , während das Gesetz von Gustafson annimmt, dass die Gesamtmenge der parallel zu erledigenden Arbeit linear mit die Anzahl der Prozessoren .

Abhängigkeiten

Das Verständnis von Datenabhängigkeiten ist bei der Implementierung paralleler Algorithmen von grundlegender Bedeutung . Kein Programm kann schneller ausgeführt werden als die längste Kette abhängiger Berechnungen (bekannt als der kritische Pfad ), da Berechnungen, die von vorherigen Berechnungen in der Kette abhängen, der Reihe nach ausgeführt werden müssen. Die meisten Algorithmen bestehen jedoch nicht nur aus einer langen Kette abhängiger Berechnungen; es gibt in der Regel Möglichkeiten, unabhängige Berechnungen parallel durchzuführen.

Seien P i und P j zwei Programmsegmente. Bernsteins Bedingungen beschreiben, wann die beiden unabhängig sind und parallel ausgeführt werden können. Für P i seien I i alle Eingangsvariablen und O i die Ausgangsvariablen, und ebenso für P j . P i und P j sind unabhängig, wenn sie

Eine Verletzung der ersten Bedingung führt eine Flussabhängigkeit ein, die dem ersten Segment entspricht, das ein Ergebnis erzeugt, das von dem zweiten Segment verwendet wird. Die zweite Bedingung stellt eine Anti-Abhängigkeit dar, wenn das zweite Segment eine Variable erzeugt, die vom ersten Segment benötigt wird. Die dritte und letzte Bedingung stellt eine Ausgabeabhängigkeit dar: Wenn zwei Segmente an dieselbe Stelle schreiben, kommt das Ergebnis aus dem logisch zuletzt ausgeführten Segment.

Betrachten Sie die folgenden Funktionen, die verschiedene Arten von Abhängigkeiten demonstrieren:

1: function Dep(a, b)
2: c := a * b
3: d := 3 * c
4: end function

In diesem Beispiel kann Anweisung 3 nicht vor (oder sogar parallel zu) Anweisung 2 ausgeführt werden, da Anweisung 3 ein Ergebnis von Anweisung 2 verwendet. Sie verletzt Bedingung 1 und führt somit eine Flussabhängigkeit ein.

1: function NoDep(a, b)
2: c := a * b
3: d := 3 * b
4: e := a + b
5: end function

In diesem Beispiel gibt es keine Abhängigkeiten zwischen den Anweisungen, sodass sie alle parallel ausgeführt werden können.

Bernsteins Bedingungen erlauben keine gemeinsame Nutzung von Speicher zwischen verschiedenen Prozessen. Dazu sind einige Mittel erforderlich, um eine Ordnung zwischen den Zugriffen zu erzwingen, wie beispielsweise Semaphoren , Barrieren oder andere Synchronisationsverfahren .

Race Conditions, gegenseitiger Ausschluss, Synchronisation und parallele Verlangsamung

Teilaufgaben in einem parallelen Programm werden oft als Threads bezeichnet . Einige parallele Computerarchitekturen verwenden kleinere, leichtgewichtige Versionen von Threads, die als Fasern bekannt sind , während andere größere Versionen verwenden, die als Prozesse bekannt sind . "Threads" wird jedoch allgemein als Oberbegriff für Teilaufgaben akzeptiert. Threads benötigen häufig synchronisierten Zugriff auf ein Objekt oder eine andere Ressource , beispielsweise wenn sie eine Variable aktualisieren müssen , die von ihnen gemeinsam genutzt wird. Ohne Synchronisation können die Anweisungen zwischen den beiden Threads in beliebiger Reihenfolge verschachtelt werden. Betrachten Sie zum Beispiel das folgende Programm:

Gewinde A Gewinde B
1A: Variable V . lesen 1B: Variable V . lesen
2A: Addiere 1 zur Variablen V 2B: Addiere 1 zur Variablen V
3A: Zurückschreiben in Variable V 3B: Zurückschreiben in Variable V

Wenn der Befehl 1B zwischen 1A und 3A ausgeführt wird oder wenn der Befehl 1A zwischen 1B und 3B ausgeführt wird, erzeugt das Programm falsche Daten. Dies wird als Race Condition bezeichnet . Der Programmierer muss eine Sperre verwenden , um einen gegenseitigen Ausschluss zu ermöglichen . Eine Sperre ist ein Programmiersprachenkonstrukt, das es einem Thread ermöglicht, die Kontrolle über eine Variable zu übernehmen und andere Threads daran zu hindern, sie zu lesen oder zu schreiben, bis diese Variable entsperrt wird. Der Thread, der die Sperre hält, kann seinen kritischen Abschnitt (den Abschnitt eines Programms, der exklusiven Zugriff auf eine Variable erfordert) ausführen und die Daten entsperren, wenn er fertig ist. Um eine korrekte Programmausführung zu gewährleisten, kann das obige Programm daher umgeschrieben werden, um Sperren zu verwenden:

Gewinde A Gewinde B
1A: Variable V . sperren 1B: Variable V . sperren
2A: Variable V . lesen 2B: Variable V . lesen
3A: Addiere 1 zur Variablen V 3B: Addiere 1 zur Variablen V
4A: Zurückschreiben in Variable V 4B: Zurückschreiben in Variable V
5A: Variable V . freischalten 5B: Variable V . freischalten

Ein Thread wird die Variable V erfolgreich sperren, während der andere Thread gesperrt wird – er kann nicht fortfahren, bis V wieder entsperrt wird. Dies garantiert die korrekte Ausführung des Programms. Sperren können erforderlich sein, um eine korrekte Programmausführung sicherzustellen, wenn Threads den Zugriff auf Ressourcen serialisieren müssen, aber ihre Verwendung kann ein Programm stark verlangsamen und seine Zuverlässigkeit beeinträchtigen .

Das Sperren mehrerer Variablen mit nicht-atomaren Sperren führt zu der Möglichkeit eines Programm- Deadlocks . Eine atomare Sperre sperrt mehrere Variablen gleichzeitig. Wenn es nicht alle sperren kann, wird keines davon gesperrt. Wenn zwei Threads jeweils dieselben zwei Variablen mit nicht-atomaren Sperren sperren müssen, ist es möglich, dass ein Thread eine von ihnen sperrt und der zweite Thread die zweite Variable sperrt. In einem solchen Fall kann keiner der Threads abgeschlossen werden und es kommt zu einem Deadlock.

Viele parallele Programme erfordern, dass ihre Teilaufgaben synchron agieren . Dies erfordert den Einsatz einer Barriere . Barrieren werden typischerweise unter Verwendung eines Schlosses oder eines Semaphors implementiert . Eine Klasse von Algorithmen, die als sperrfreie und wartefreie Algorithmen bekannt sind , vermeidet insgesamt die Verwendung von Sperren und Barrieren. Dieser Ansatz ist jedoch im Allgemeinen schwierig zu implementieren und erfordert richtig entworfene Datenstrukturen.

Nicht jede Parallelisierung führt zu einer Beschleunigung. Da eine Aufgabe in immer mehr Threads aufgeteilt wird, verbringen diese Threads im Allgemeinen einen immer größeren Teil ihrer Zeit damit, miteinander zu kommunizieren oder aufeinander zu warten, um Zugriff auf Ressourcen zu erhalten. Sobald der Overhead aus Ressourcenkonflikten oder Kommunikation die Zeit dominiert, die für andere Berechnungen aufgewendet wird, erhöht eine weitere Parallelisierung (d. h. die Aufteilung der Arbeitslast auf noch mehr Threads) die zum Abschluss erforderliche Zeit, anstatt sie zu verringern. Dieses als parallele Verlangsamung bekannte Problem kann in einigen Fällen durch Softwareanalyse und Redesign verbessert werden.

Feinkörnige, grobkörnige und peinliche Parallelität

Anwendungen werden oft danach klassifiziert, wie oft ihre Teilaufgaben sich synchronisieren oder miteinander kommunizieren müssen. Eine Anwendung weist eine feinkörnige Parallelität auf, wenn ihre Teilaufgaben viele Male pro Sekunde kommunizieren müssen; es zeigt grobkörnige Parallelität, wenn sie nicht viele Male pro Sekunde kommunizieren, und es zeigt peinliche Parallelität, wenn sie selten oder nie kommunizieren müssen. Peinlich parallele Anwendungen gelten als am einfachsten zu parallelisieren.

Flynns Taxonomie

Michael J. Flynn schuf eines der frühesten Klassifizierungssysteme für parallele (und sequentielle) Computer und Programme, das heute als Flynns Taxonomie bekannt ist . Flynn klassifizierte Programme und Computer danach, ob sie mit einem einzelnen Satz oder mehreren Sätzen von Befehlen arbeiteten und ob diese Befehle einen einzelnen Satz oder mehrere Sätze von Daten verwendeten oder nicht.

Die Single-Instruction-Single-Data (SISD)-Klassifikation entspricht einem vollständig sequentiellen Programm. Die Single-Instruction-Multiple-Data (SIMD)-Klassifizierung ist analog zum wiederholten Ausführen derselben Operation über einen großen Datensatz. Dies wird üblicherweise in Signalverarbeitungsanwendungen durchgeführt . Multiple-Instruction-Single-Data (MISD) ist eine selten verwendete Klassifikation. Während Computerarchitekturen entwickelt wurden, um damit umzugehen (wie systolische Arrays ), kamen nur wenige Anwendungen zustande, die in diese Klasse passten. Multiple-Instruction-Multiple-Data (MIMD)-Programme sind bei weitem die gebräuchlichste Art von parallelen Programmen.

Laut David A. Patterson und John L. Hennessy sind „einige Maschinen natürlich Hybriden dieser Kategorien, aber dieses klassische Modell hat überlebt, weil es einfach und leicht zu verstehen ist und eine gute erste Annäherung bietet. Es ist auch – vielleicht wegen seiner Verständlichkeit – das am weitesten verbreitete Schema."

Arten von Parallelität

Parallelität auf Bitebene

Taiwania 3 of Taiwan , ein paralleles Supercomputing-Gerät, das sich der COVID-19- Forschung angeschlossen hat.

Vom Aufkommen der Computerchip-Fertigungstechnologie mit sehr großer Integration (VLSI) in den 1970er Jahren bis etwa 1986 wurde die Geschwindigkeit der Computerarchitektur durch die Verdoppelung der Computerwortgröße – die Menge an Informationen, die der Prozessor pro Zyklus verarbeiten kann – vorangetrieben . Das Erhöhen der Wortgröße verringert die Anzahl der Befehle, die der Prozessor ausführen muss, um eine Operation an Variablen durchzuführen, deren Größen größer als die Länge des Wortes sind. Wenn ein 8-Bit- Prozessor beispielsweise zwei 16-Bit- Ganzzahlen addieren muss, muss der Prozessor zuerst die 8 niederwertigen Bits von jeder Ganzzahl mit dem Standard-Additionsbefehl addieren und dann die 8 höherwertigen Bits mit addieren mit -Übertragsbefehl und das Übertragsbit aus der Addition niedrigerer Ordnung; somit benötigt ein 8-Bit-Prozessor zwei Befehle, um eine einzelne Operation abzuschließen, während ein 16-Bit-Prozessor in der Lage wäre, die Operation mit einem einzigen Befehl abzuschließen.

In der Vergangenheit wurden 4-Bit- Mikroprozessoren durch 8-Bit-, dann 16-Bit- und dann 32-Bit-Mikroprozessoren ersetzt. Dieser Trend endete im Allgemeinen mit der Einführung von 32-Bit-Prozessoren, die seit zwei Jahrzehnten ein Standard im Allzweck-Computing sind. Erst Anfang der 2000er Jahre, mit dem Aufkommen von x86-64- Architekturen, wurden 64-Bit- Prozessoren alltäglich.

Parallelität auf Befehlsebene

Ein kanonischer Prozessor ohne Pipeline . Es dauert fünf Taktzyklen, um einen Befehl abzuschließen, und somit kann der Prozessor eine subskalare Leistung ausgeben ( IPC = 0,2 < 1 ).

Ein Computerprogramm ist im Wesentlichen ein Strom von Anweisungen, die von einem Prozessor ausgeführt werden. Ohne Parallelität auf Befehlsebene kann ein Prozessor nur weniger als einen Befehl pro Taktzyklus ausgeben ( IPC < 1 ). Diese Prozessoren werden als subskalare Prozessoren bezeichnet. Diese Befehle können neu geordnet und zu Gruppen zusammengefasst werden, die dann parallel ausgeführt werden, ohne das Ergebnis des Programms zu ändern. Dies wird als Parallelität auf Befehlsebene bezeichnet. Fortschritte in der Parallelität auf Befehlsebene dominierten die Computerarchitektur von Mitte der 1980er bis Mitte der 1990er Jahre.

Ein kanonischer fünfstufiger Pipeline- Prozessor. Im besten Fall dauert es einen Taktzyklus, um einen Befehl abzuschließen, und somit kann der Prozessor skalare Leistung ( IPC = 1 ) ausgeben .

Alle modernen Prozessoren haben mehrstufige Befehlspipelines . Jede Stufe in der Pipeline entspricht einer anderen Aktion, die der Prozessor an diesem Befehl in dieser Stufe ausführt; ein Prozessor mit einer N- Stufen-Pipeline kann bis zu N verschiedene Befehle in verschiedenen Fertigstellungsstufen haben und kann somit einen Befehl pro Taktzyklus ( IPC = 1 ) ausgeben . Diese Prozessoren werden als Skalarprozessoren bezeichnet . Das kanonische Beispiel eines Pipeline-Prozessors ist ein RISC- Prozessor mit fünf Stufen: Befehlsabruf (IF), Befehlsdecodierung (ID), Ausführen (EX), Speicherzugriff (MEM) und Zurückschreiben des Registers (WB). Der Pentium-4- Prozessor hatte eine 35-stufige Pipeline.

Ein kanonischer fünfstufiger Pipeline- Prozessor mit zwei Ausführungseinheiten. Im besten Fall dauert es einen Taktzyklus, um zwei Befehle auszuführen, und somit kann der Prozessor superskalare Leistung ausgeben ( IPC = 2 > 1 ).

Die meisten modernen Prozessoren haben auch mehrere Ausführungseinheiten . Sie kombinieren diese Funktion normalerweise mit Pipelining und können somit mehr als einen Befehl pro Taktzyklus ausgeben ( IPC > 1 ). Diese Prozessoren werden als Superskalarprozessoren bezeichnet . Superskalare Prozessoren unterscheiden sich von Mehrkernprozessoren dadurch, dass die mehreren Ausführungseinheiten keine ganzen Prozessoren (dh Verarbeitungseinheiten) sind. Anweisungen können nur gruppiert werden, wenn keine Datenabhängigkeit zwischen ihnen besteht. Scoreboarding und der Tomasulo-Algorithmus (der dem Scoreboarding ähnelt, aber die Registerumbenennung verwendet ) sind zwei der gebräuchlichsten Techniken zum Implementieren von Out-of-order-Execution und Parallelität auf Befehlsebene.

Aufgabenparallelität

Task-Parallelismus ist die Eigenschaft eines parallelen Programms, dass "völlig unterschiedliche Berechnungen entweder mit den gleichen oder unterschiedlichen Datensätzen durchgeführt werden können". Dies steht im Gegensatz zur Datenparallelität, bei der dieselbe Berechnung mit denselben oder unterschiedlichen Datensätzen durchgeführt wird. Die Aufgabenparallelität beinhaltet die Zerlegung einer Aufgabe in Unteraufgaben und die anschließende Zuweisung jeder Unteraufgabe an einen Prozessor zur Ausführung. Die Prozessoren würden dann diese Unteraufgaben gleichzeitig und oft kooperativ ausführen. Die Aufgabenparallelität skaliert normalerweise nicht mit der Größe eines Problems.

Parallelität auf Superwortebene

Parallelität auf Superwortebene ist eine Vektorisierungstechnik , die auf Schleifenabrollen und grundlegender Blockvektorisierung basiert . Es unterscheidet sich von Schleifenvektorisierungsalgorithmen dadurch, dass es die Parallelität von Inline-Code ausnutzen kann , wie zum Beispiel das Manipulieren von Koordinaten, Farbkanälen oder von Hand abgerollten Schleifen.

Hardware

Gedächtnis und Kommunikation

Der Hauptspeicher in einem Parallelcomputer ist entweder ein gemeinsam genutzter Speicher (der von allen Verarbeitungselementen in einem einzigen Adressraum gemeinsam genutzt wird ) oder ein verteilter Speicher (in dem jedes Verarbeitungselement seinen eigenen lokalen Adressraum hat). Verteilter Speicher bezieht sich auf die Tatsache, dass der Speicher logisch verteilt ist, impliziert jedoch oft, dass er auch physisch verteilt ist. Verteilter gemeinsamer Speicher und Speichervirtualisierung kombinieren die beiden Ansätze, wobei das Verarbeitungselement seinen eigenen lokalen Speicher und Zugriff auf den Speicher auf nicht-lokalen Prozessoren hat. Zugriffe auf den lokalen Speicher sind typischerweise schneller als Zugriffe auf nicht-lokalen Speicher. Auf den Supercomputern kann verteilter gemeinsamer Speicherraum unter Verwendung des Programmiermodells wie PGAS implementiert werden . Dieses Modell ermöglicht es Prozessen auf einem Rechenknoten, transparent auf den Remote-Speicher eines anderen Rechenknotens zuzugreifen. Alle Rechenknoten werden auch an einem externen Shared - Memory - System über Hochgeschwindigkeits - Verbindungsstecker , wie beispielsweise verbunden Infiniband , dieses externe Shared - Memory - System ist bekannt als Burst - Puffer , die typischerweise aus Anordnungen von gebaut ist nicht flüchtiger Speicher physisch über mehrere I verteilt / O-Knoten.

Eine logische Ansicht einer NUMA-Architektur ( Non-Uniform Memory Access ). Prozessoren in einem Verzeichnis können mit geringerer Latenz auf den Speicher dieses Verzeichnisses zugreifen als auf den Speicher des anderen Verzeichnisses.

Computerarchitekturen, bei denen auf jedes Element des Hauptspeichers mit gleicher Latenz und Bandbreite zugegriffen werden kann, sind als einheitliche Speicherzugriffssysteme (UMA) bekannt. Dies kann typischerweise nur durch ein Shared-Memory- System erreicht werden, bei dem der Speicher nicht physikalisch verteilt ist. Ein System, das diese Eigenschaft nicht aufweist, wird als NUMA-Architektur ( Non-Uniform Memory Access ) bezeichnet. Verteilte Speichersysteme haben einen ungleichmäßigen Speicherzugriff.

Computersysteme verwenden Caches – kleine und schnelle Speicher, die sich in der Nähe des Prozessors befinden und temporäre Kopien von Speicherwerten speichern (in der Nähe sowohl im physikalischen als auch im logischen Sinne). Parallele Computersysteme haben Schwierigkeiten mit Caches, die denselben Wert an mehr als einem Ort speichern können, mit der Möglichkeit einer falschen Programmausführung. Diese Computer benötigen ein Cache-Kohärenzsystem , das zwischengespeicherte Werte verfolgt und sie strategisch löscht, um so eine korrekte Programmausführung sicherzustellen. Bus-Snooping ist eine der gebräuchlichsten Methoden, um zu verfolgen, auf welche Werte zugegriffen wird (und daher bereinigt werden sollte). Das Entwerfen großer Hochleistungs-Cache-Kohärenzsysteme ist ein sehr schwieriges Problem in der Computerarchitektur. Als Ergebnis skalieren Computerarchitekturen mit gemeinsam genutztem Speicher nicht so gut wie Systeme mit verteiltem Speicher.

Die Prozessor-Prozessor- und Prozessor-Speicher-Kommunikation kann in Hardware auf verschiedene Weise implementiert werden, einschließlich über einen gemeinsam genutzten (entweder mit mehreren Ports oder Multiplexen ) Speicher, einen Crossbar-Switch , einen gemeinsam genutzten Bus oder ein Verbindungsnetzwerk mit unzähligen Topologien, einschließlich Stern , Ring , Baum , Hypercube , Fat Hypercube (ein Hypercube mit mehr als einem Prozessor an einem Knoten) oder n-dimensionales Mesh .

Parallele Computer, die auf miteinander verbundenen Netzwerken basieren, müssen über eine Art Routing verfügen , um das Weiterleiten von Nachrichten zwischen Knoten zu ermöglichen, die nicht direkt verbunden sind. Das für die Kommunikation zwischen den Prozessoren verwendete Medium ist in großen Multiprozessormaschinen wahrscheinlich hierarchisch.

Klassen von Parallelrechnern

Parallele Computer können grob nach dem Niveau klassifiziert werden, auf dem die Hardware Parallelität unterstützt. Diese Klassifikation ist weitgehend analog zum Abstand zwischen Basisrechenknoten. Diese schließen sich nicht gegenseitig aus; zum Beispiel sind Cluster von symmetrischen Multiprozessoren relativ häufig.

Multi-Core-Computing

Ein Multi-Core-Prozessor ist ein Prozessor, der mehrere Verarbeitungseinheiten (genannt "Kerne") auf demselben Chip enthält. Dieser Prozessor unterscheidet sich von einem superskalaren Prozessor, der mehrere Ausführungseinheiten enthält und mehrere Befehle pro Taktzyklus aus einem Befehlsstrom (Thread) ausgeben kann; im Gegensatz dazu kann ein Mehrkernprozessor mehrere Befehle pro Taktzyklus aus mehreren Befehlsströmen ausgeben. Der Cell-Mikroprozessor von IBM , der für den Einsatz in der Sony PlayStation 3 entwickelt wurde , ist ein bekannter Multi-Core-Prozessor. Jeder Kern in einem Mehrkernprozessor kann potenziell auch superskalar sein, dh jeder Kern kann in jedem Taktzyklus mehrere Befehle von einem Thread ausgeben.

Simultaneous Multithreading (wovon Intels Hyper-Threading das bekannteste ist) war eine frühe Form des Pseudo-Multicoreismus. Ein zu gleichzeitigem Multithreading fähiger Prozessor enthält mehrere Ausführungseinheiten in derselben Verarbeitungseinheit – das heißt, er hat eine superskalare Architektur – und kann mehrere Befehle pro Taktzyklus von mehreren Threads ausgeben . Temporales Multithreading enthält andererseits eine einzelne Ausführungseinheit in derselben Verarbeitungseinheit und kann einen Befehl nach dem anderen von mehreren Threads ausgeben .

Symmetrisches Multiprocessing

Ein symmetrischer Multiprozessor (SMP) ist ein Computersystem mit mehreren identischen Prozessoren, die sich den Speicher teilen und über einen Bus verbunden sind . Buskonflikte verhindern die Skalierung von Busarchitekturen. Als Ergebnis umfassen SMPs im Allgemeinen nicht mehr als 32 Prozessoren. Aufgrund der geringen Größe der Prozessoren und der durch große Caches erreichten deutlichen Reduzierung der Anforderungen an die Busbandbreite sind solche symmetrischen Multiprozessoren äußerst kostengünstig, sofern eine ausreichende Speicherbandbreite vorhanden ist.

Verteiltes Rechnen

Ein verteilter Computer (auch als Multiprozessor mit verteiltem Speicher bekannt) ist ein Computersystem mit verteiltem Speicher, in dem die Verarbeitungselemente durch ein Netzwerk verbunden sind. Verteilte Computer sind hoch skalierbar. Die Begriffe „ Concurrent Computing “, „Parallel Computing“ und „Distributed Computing“ haben viele Überschneidungen und es gibt keine klare Unterscheidung zwischen ihnen. Dasselbe System kann sowohl als "parallel" als auch als "verteilt" charakterisiert werden; die Prozessoren in einem typischen verteilten System laufen gleichzeitig parallel.

Cluster-Computing

Ein Cluster ist eine Gruppe von lose gekoppelten Computern, die eng zusammenarbeiten, sodass sie in gewisser Hinsicht als ein einzelner Computer betrachtet werden können. Cluster bestehen aus mehreren eigenständigen Maschinen, die über ein Netzwerk verbunden sind. Während Maschinen in einem Cluster nicht symmetrisch sein müssen, ist der Lastausgleich schwieriger, wenn dies nicht der Fall ist. Der gebräuchlichste Clustertyp ist der Beowulf-Cluster , bei dem es sich um einen Cluster handelt, der auf mehreren identischen handelsüblichen Computern implementiert ist, die mit einem lokalen TCP/IP- Ethernet- Netzwerk verbunden sind . Die Beowulf-Technologie wurde ursprünglich von Thomas Sterling und Donald Becker entwickelt . 87% aller Top500- Supercomputer sind Cluster. Die restlichen sind Massively Parallel Processors, die unten erläutert werden.

Da Grid-Computing-Systeme (unten beschrieben) peinlich parallele Probleme leicht handhaben können, sind moderne Cluster in der Regel für schwierigere Probleme ausgelegt – Probleme, bei denen Knoten häufiger Zwischenergebnisse miteinander teilen müssen. Dies erfordert eine hohe Bandbreite und vor allem ein Verbindungsnetz mit geringer Latenz . Viele historische und aktuelle Supercomputer verwenden maßgeschneiderte Hochleistungs-Netzwerkhardware, die speziell für Cluster-Computing entwickelt wurde, wie das Cray Gemini-Netzwerk. Ab 2014 verwenden die meisten aktuellen Supercomputer einige handelsübliche Standard-Netzwerkhardware, oft Myrinet , InfiniBand oder Gigabit Ethernet .

Massiv paralleles Rechnen
Ein Schrank von IBM ‚s Blue Gene / L massiv parallelen Supercomputer

Ein Massively Parallel Processor (MPP) ist ein einzelner Computer mit vielen vernetzten Prozessoren. MPPs haben viele der gleichen Eigenschaften wie Cluster, aber MPPs haben spezialisierte Verbindungsnetzwerke (während Cluster handelsübliche Hardware für die Vernetzung verwenden). MPPs neigen auch dazu, größer als Cluster zu sein und haben typischerweise "weit mehr" als 100 Prozessoren. In einem MPP "enthält jede CPU ihren eigenen Speicher und eine Kopie des Betriebssystems und der Anwendung. Jedes Subsystem kommuniziert mit den anderen über eine Hochgeschwindigkeitsverbindung."

IBM ‚s Blue Gene / L , der fünftschnellste Supercomputer der Welt nach dem Juni 2009 TOP500 - Ranking ist ein MPP.

Grid-Computing

Grid-Computing ist die am weitesten verbreitete Form des parallelen Rechnens. Es verwendet Computer, die über das Internet kommunizieren , um an einem bestimmten Problem zu arbeiten. Aufgrund der geringen Bandbreite und der extrem hohen Latenz, die im Internet verfügbar sind, beschäftigt sich verteiltes Rechnen normalerweise nur mit peinlichen Parallelproblemen . Es wurden viele verteilte Computeranwendungen erstellt, von denen SETI@home und Folding@home die bekanntesten Beispiele sind.

Die meisten Grid-Computing-Anwendungen verwenden Middleware (Software, die zwischen dem Betriebssystem und der Anwendung sitzt, um Netzwerkressourcen zu verwalten und die Softwareschnittstelle zu standardisieren). Die gängigste Middleware für verteilte Computer ist die Berkeley Open Infrastructure for Network Computing (BOINC). Häufig verwendet verteilte Computersoftware "Ersatzzyklen" und führt Berechnungen zu Zeiten durch, wenn ein Computer im Leerlauf ist.

Spezialisierte Parallelrechner

Beim Parallel Computing gibt es spezialisierte parallele Geräte, die nach wie vor Nischen von Interesse sind. Obwohl sie nicht domänenspezifisch sind , sind sie in der Regel nur auf wenige Klassen paralleler Probleme anwendbar.

Rekonfigurierbares Computing mit feldprogrammierbaren Gate-Arrays

Rekonfigurierbares Rechnen ist die Verwendung eines feldprogrammierbaren Gate-Arrays (FPGA) als Co-Prozessor für einen Allzweckcomputer. Ein FPGA ist im Wesentlichen ein Computerchip, der sich für eine bestimmte Aufgabe selbst neu verdrahten kann.

FPGAs können mit Hardwarebeschreibungssprachen wie VHDL oder Verilog programmiert werden . Die Programmierung in diesen Sprachen kann jedoch mühsam sein. Mehrere Anbieter haben C-zu-HDL- Sprachen entwickelt, die versuchen, die Syntax und Semantik der Programmiersprache C zu emulieren , mit der die meisten Programmierer vertraut sind. Die bekanntesten C-zu-HDL-Sprachen sind Mitrion-C , Impulse C , DIME-C und Handel-C . Dazu können auch bestimmte Teilmengen von SystemC auf Basis von C++ verwendet werden.

Die Entscheidung von AMD, seine HyperTransport- Technologie für Drittanbieter zu öffnen , ist zur Basistechnologie für hochleistungsfähiges rekonfigurierbares Computing geworden. Laut Michael R. D'Amour, Chief Operating Officer der DRC Computer Corporation , "als wir AMD zum ersten Mal betraten, nannten sie uns 'die Socket- Stealer'. Jetzt nennen sie uns ihre Partner."

Allzweck-Computing auf Grafikprozessoren (GPGPU)

Allzweck-Computing auf Grafikprozessoren (GPGPU) ist ein relativ neuer Trend in der Computertechnikforschung. GPUs sind Co-Prozessoren, die stark für die Computergrafikverarbeitung optimiert wurden . Die Computergraphikverarbeitung ist ein Gebiet, das von parallelen Datenoperationen dominiert wird – insbesondere von linearen Algebra- Matrixoperationen .

In der Anfangszeit verwendeten GPGPU-Programme die normalen Grafik-APIs zum Ausführen von Programmen. Es wurden jedoch mehrere neue Programmiersprachen und Plattformen entwickelt, um allgemeine Berechnungen auf GPUs durchzuführen, wobei sowohl Nvidia als auch AMD Programmierumgebungen mit CUDA bzw. Stream SDK veröffentlichen. Andere GPU-Programmiersprachen sind BrookGPU , PeakStream und RapidMind . Nvidia hat in seiner Tesla-Serie auch spezielle Produkte für die Berechnung herausgebracht . Das Technologiekonsortium Khronos Group hat die OpenCL- Spezifikation veröffentlicht, die ein Framework zum Schreiben von Programmen ist, die plattformübergreifend aus CPUs und GPUs ausgeführt werden. AMD , Apple , Intel , Nvidia und andere unterstützen OpenCL .

Anwendungsspezifische integrierte Schaltkreise

Für den Umgang mit parallelen Anwendungen wurden mehrere anwendungsspezifische integrierte Schaltungs (ASIC)-Ansätze entwickelt.

Da ein ASIC (per Definition) spezifisch für eine gegebene Anwendung ist, kann er vollständig für diese Anwendung optimiert werden. Als Ergebnis neigt ein ASIC für eine gegebene Anwendung dazu, einen Allzweckcomputer zu übertreffen. ASICs werden jedoch durch UV-Photolithographie hergestellt . Dieses Verfahren erfordert einen Maskensatz, der extrem teuer sein kann. Ein Maskenset kann über eine Million US-Dollar kosten. (Je kleiner die für den Chip erforderlichen Transistoren sind, desto teurer wird die Maske.) In der Zwischenzeit tendieren Leistungssteigerungen im Allzweck-Computing (wie durch das Mooresche Gesetz beschrieben ) dazu, diese Gewinne in nur ein oder zwei Chipgenerationen zunichte zu machen . Hohe Anfangskosten und die Tendenz, durch das Moore's Law-getriebene Allzweck-Computing überholt zu werden, haben ASICs für die meisten parallelen Computing-Anwendungen undurchführbar gemacht. Einige wurden jedoch gebaut. Ein Beispiel ist die PFLOPS RIKEN MDGRAPE-3 Maschine, die kundenspezifische ASICs für die Molekulardynamiksimulation verwendet.

Vektorprozessoren
Der Cray-1 ist ein Vektorprozessor

Ein Vektorprozessor ist eine CPU oder ein Computersystem, das den gleichen Befehl an großen Datensätzen ausführen kann. Vektorprozessoren verfügen über Operationen auf hoher Ebene, die mit linearen Arrays von Zahlen oder Vektoren arbeiten. Eine beispielhafte Vektoroperation ist A = B × C , wobei A , B und C jeweils 64-Element-Vektoren von 64-Bit- Gleitkommazahlen sind. Sie sind eng mit der SIMD-Klassifikation von Flynn verwandt.

Cray- Computer wurden in den 1970er und 1980er Jahren für ihre vektorverarbeitenden Computer berühmt. Vektorprozessoren – sowohl als CPUs als auch als vollständige Computersysteme – sind jedoch im Allgemeinen verschwunden. Moderne Prozessor - Befehlssätze beinhalten einige Vektorverarbeitungsanweisungen, wie mit Freescale Semiconductor ‚s AltiVec und Intel ‘ s Streaming SIMD Extensions (SSE).

Software

Parallele Programmiersprachen

Parallele Programmiersprachen , Bibliotheken , APIs und parallele Programmiermodelle (wie algorithmische Skelette ) wurden für die Programmierung paralleler Computer erstellt. Diese können im Allgemeinen basierend auf den Annahmen, die sie über die zugrunde liegende Speicherarchitektur treffen, in Klassen unterteilt werden – gemeinsam genutzter Speicher, verteilter Speicher oder gemeinsam genutzter verteilter Speicher. Shared-Memory-Programmiersprachen kommunizieren, indem sie Shared-Memory-Variablen manipulieren. Verteilter Speicher verwendet Message Passing . POSIX Threads und OpenMP sind zwei der am weitesten verbreiteten Shared-Memory-APIs, während Message Passing Interface (MPI) die am häufigsten verwendete Message-Passing-System-API ist. Ein Konzept, das beim Programmieren paralleler Programme verwendet wird, ist das Zukunftskonzept , bei dem ein Teil eines Programms verspricht, zu einem späteren Zeitpunkt ein erforderliches Datum an einen anderen Teil eines Programms zu liefern.

CAPS entreprise und Pathscale koordinieren außerdem ihre Bemühungen, hybride Multi-Core Parallel Programming (HMPP)-Direktiven zu einem offenen Standard namens OpenHMPP zu machen . Das auf Direktiven basierende OpenHMPP-Programmiermodell bietet eine Syntax, um Berechnungen effizient auf Hardwarebeschleuniger auszulagern und die Datenbewegung zum/vom Hardwarespeicher zu optimieren. OpenHMPP-Direktiven beschreiben Remote Procedure Call (RPC) auf einem Beschleunigergerät (zB GPU) oder allgemeiner auf einem Satz von Kernen. Die Direktiven kommentieren C- oder Fortran- Codes, um zwei Gruppen von Funktionalitäten zu beschreiben: das Auslagern von Prozeduren (bezeichnet als Codelets) auf ein entferntes Gerät und die Optimierung der Datenübertragung zwischen dem CPU-Hauptspeicher und dem Beschleunigerspeicher.

Der Aufstieg von Consumer-GPUs hat zur Unterstützung von Compute-Kernels geführt , entweder in Grafik-APIs (als Compute-Shader bezeichnet ), in dedizierten APIs (wie OpenCL ) oder in anderen Spracherweiterungen.

Automatische Parallelisierung

Die automatische Parallelisierung eines sequentiellen Programms durch einen Compiler ist der "Heilige Gral" des parallelen Rechnens, insbesondere bei der oben erwähnten Grenze der Prozessorfrequenz. Trotz jahrzehntelanger Arbeit von Compilerforschern hatte die automatische Parallelisierung nur begrenzten Erfolg.

Mainstream-Parallelprogrammiersprachen bleiben entweder explizit parallel oder (bestenfalls) teilweise implizit , wobei ein Programmierer den Compiler- Direktiven für die Parallelisierung gibt. Es gibt einige vollständig implizite parallele Programmiersprachen – SISAL , Parallel Haskell , SequenceL , System C (für FPGAs ), Mitrion-C , VHDL und Verilog .

Anwendungs-Checkpointing

Mit zunehmender Komplexität eines Computersystems nimmt die mittlere Zeit zwischen Ausfällen normalerweise ab. Application Checkpointing ist eine Technik, bei der das Computersystem einen "Schnappschuss" der Anwendung erstellt – eine Aufzeichnung aller aktuellen Ressourcenzuweisungen und Variablenzustände, ähnlich einem Core-Dump –; diese Informationen können verwendet werden, um das Programm wiederherzustellen, falls der Computer ausfallen sollte. Application Checkpointing bedeutet, dass das Programm nur an seinem letzten Prüfpunkt und nicht am Anfang neu gestartet werden muss. Obwohl Checkpointing in einer Vielzahl von Situationen Vorteile bietet, ist es besonders nützlich in hochparallelen Systemen mit einer großen Anzahl von Prozessoren, die im Hochleistungsrechnen verwendet werden .

Algorithmische Methoden

Da parallele Computer immer größer und schneller werden, sind wir jetzt in der Lage, Probleme zu lösen, deren Ausführung zuvor zu lange gedauert hat. So unterschiedliche Bereiche wie die Bioinformatik (für Proteinfaltung und Sequenzanalyse ) und die Wirtschaftswissenschaften (für die Finanzmathematik ) haben die Vorteile des parallelen Rechnens genutzt. Häufige Arten von Problemen bei Parallel-Computing-Anwendungen sind:

Fehlertoleranz

Paralleles Rechnen kann auch auf den Entwurf fehlertoleranter Computersysteme angewendet werden , insbesondere über Lockstep- Systeme, die dieselbe Operation parallel ausführen. Dies sorgt für Redundanz bei Ausfall einer Komponente und ermöglicht auch eine automatische Fehlererkennung und Fehlerkorrektur bei abweichenden Ergebnissen. Diese Methoden können verwendet werden, um Störungen durch einzelne Ereignisse zu vermeiden, die durch vorübergehende Fehler verursacht werden. Obwohl in eingebetteten oder spezialisierten Systemen möglicherweise zusätzliche Maßnahmen erforderlich sind, kann dieses Verfahren einen kostengünstigen Ansatz bieten, um eine n-modulare Redundanz in kommerziellen Standardsystemen zu erreichen.

Geschichte

ILLIAC IV , "der berüchtigtste aller Supercomputer"

Die Ursprünge des wahren (MIMD) Parallelismus gehen auf Luigi Federico Menabrea und sein Sketch of the Analytic Engine Invented by Charles Babbage zurück .

Im April 1958 diskutierte Stanley Gill (Ferranti) die parallele Programmierung und die Notwendigkeit von Verzweigungen und Wartezeiten. Ebenfalls 1958 diskutierten die IBM-Forscher John Cocke und Daniel Slotnick erstmals den Einsatz von Parallelität in numerischen Berechnungen. Die Burroughs Corporation stellte 1962 den D825 vor, einen Computer mit vier Prozessoren, der über einen Crossbar-Switch auf bis zu 16 Speichermodule zugreift . 1967 veröffentlichten Amdahl und Slotnick auf der Konferenz der American Federation of Information Processing Societies eine Debatte über die Durchführbarkeit der Parallelverarbeitung. Während dieser Debatte wurde das Gesetz von Amdahl geprägt, um die Grenze der Beschleunigung aufgrund von Parallelität zu definieren.

1969 stellte Honeywell sein erstes Multics- System vor, ein symmetrisches Multiprozessorsystem, das bis zu acht Prozessoren parallel betreiben kann. C.mmp , ein Multiprozessorprojekt an der Carnegie Mellon University in den 1970er Jahren, gehörte zu den ersten Multiprozessoren mit mehr als nur wenigen Prozessoren. Der erste busverbundene Multiprozessor mit Snooping-Caches war 1984 der Synapse N+1 .

SIMD-Parallelrechner lassen sich bis in die 1970er Jahre zurückverfolgen. Die Motivation hinter den frühen SIMD-Computern bestand darin, die Gate-Verzögerung der Steuereinheit des Prozessors über mehrere Befehle zu amortisieren . 1964 hatte Slotnick vorgeschlagen, einen massiv parallelen Computer für das Lawrence Livermore National Laboratory zu bauen . Sein Design wurde von der US Air Force finanziert , die die früheste SIMD-Parallel-Computing-Anstrengung, ILLIAC IV, war . Der Schlüssel zu seinem Design war eine ziemlich hohe Parallelität mit bis zu 256 Prozessoren, die es der Maschine ermöglichte, mit großen Datensätzen in der späteren Vektorverarbeitung zu arbeiten . ILLIAC IV wurde jedoch als "der berüchtigtste aller Supercomputer" bezeichnet, weil das Projekt nur zu einem Viertel abgeschlossen war, aber 11 Jahre dauerte und fast das Vierfache der ursprünglichen Schätzung kostete. Als es 1976 endlich bereit war, seine erste echte Anwendung auszuführen, wurde es von bestehenden kommerziellen Supercomputern wie dem Cray-1 übertroffen .

Biologisches Gehirn als massiv paralleler Computer

In den frühen 1970er Jahren am MIT Computer Science and Artificial Intelligence Laboratory , Marvin Minsky und Seymour Papert begann die Entwicklung Society of Mind Theorie, die das biologische Gehirn als Ansichten massiv parallele Computer . 1986 veröffentlichte Minsky The Society of Mind , die behauptet, dass „der Geist aus vielen kleinen Agenten gebildet wird, von denen jeder für sich selbst geistlos ist“. Die Theorie versucht zu erklären, wie das, was wir Intelligenz nennen, ein Produkt der Interaktion nicht intelligenter Teile sein könnte. Minsky sagt, dass die größte Quelle der Ideen zu der Theorie von seiner Arbeit kam, als er versuchte, eine Maschine zu entwickeln, die einen Roboterarm, eine Videokamera und einen Computer verwendet, um mit Kinderblöcken zu bauen.

Ähnliche Modelle (die das biologische Gehirn auch als massiv parallelen Computer betrachten, dh das Gehirn besteht aus einer Konstellation unabhängiger oder semi-unabhängiger Agenten) wurden auch beschrieben von:

Siehe auch

Verweise

Weiterlesen

  • Rodriguez, C.; Villagra, M.; Baran, B. (29. August 2008). „Asynchrone Teamalgorithmen für Boolesche Erfüllbarkeit“. Bio-inspirierte Modelle von Netzwerk-, Informations- und Computersystemen, 2007. Bionetics 2007. 2. : 66–69. doi : 10.1109/BIMNICS.2007.4610083 . S2CID  15185219 .
  • Sechin, A.; Paralleles Rechnen in der Photogrammetrie. GIM International. Nr. 1, 2016, S. 21–23.

Externe Links

Diesen Artikel anhören ( 54 Minuten )
Gesprochenes Wikipedia-Symbol
Diese Audiodatei wurde aus einer Überarbeitung dieses Artikels vom 21. August 2013 erstellt und spiegelt keine späteren Bearbeitungen wider. ( 2013-08-21 )