Parallele Computerwissenschaft ist eine Form der Berechnung, in der viele Berechnungen gleichzeitig ausgeführt werden, auf dem Grundsatz funktionierend, dass große Probleme häufig in kleinere geteilt werden können, die dann gleichzeitig ("in der Parallele") gelöst werden. Es gibt mehrere verschiedene Formen der parallelen Computerwissenschaft: Bit-Niveau, Instruktionsniveau, Daten und Aufgabe-Parallelismus. Parallelismus ist viele Jahre lang hauptsächlich in der Hochleistungscomputerwissenschaft verwendet worden, aber das Interesse daran ist kürzlich wegen der physischen Einschränkungen gewachsen, die Frequenzschuppen verhindern. Weil Macht-Verbrauch (und heizen folglich Generation), durch Computer eine Sorge in den letzten Jahren geworden ist, ist parallele Computerwissenschaft das dominierende Paradigma in der Computerarchitektur hauptsächlich in der Form von Mehrkernverarbeitern geworden.

Parallele Computer können gemäß dem Niveau grob klassifiziert werden, an dem die Hardware Parallelismus, mit dem Mehrkern und den Mehrverarbeiter-Computern unterstützt, die vielfache in einer Prozession gehende Elemente innerhalb einer einzelnen Maschine haben, während Trauben, MPPs und Bratrost vielfache Computer verwenden, um an derselben Aufgabe zu arbeiten. Parallele Spezialcomputerarchitekturen werden manchmal neben traditionellen Verarbeitern verwendet, um spezifische Aufgaben zu beschleunigen.

Parallele Computerprogramme sind schwieriger zu schreiben als folgende, weil Parallelität mehrere neue Klassen von potenziellen Softwareprogrammfehlern einführt, von denen laufen, sind Bedingungen am üblichsten. Kommunikation und Synchronisation zwischen den verschiedenen Teilaufgaben sind normalerweise einige der größten Hindernisse für das Bekommen guter paralleler Programm-Leistung.

Die maximale mögliche Beschleunigung eines Programms infolge

parallelization

wird als das Gesetz von Amdahl beobachtet.

Hintergrund

Traditionell ist Computersoftware für die Serienberechnung geschrieben worden. Um ein Problem zu beheben, wird ein Algorithmus gebaut und als ein Serienstrom von Instruktionen durchgeführt. Diese Instruktionen werden auf einer in einer Prozession gehenden Haupteinheit auf einem Computer durchgeführt. Nur eine Instruktion kann auf einmal durchführen — nachdem diese Instruktion beendet wird, wird das folgende durchgeführt.

Parallele Computerwissenschaft verwendet andererseits vielfache in einer Prozession gehende Elemente gleichzeitig, um ein Problem zu beheben. Das wird durch das Brechen des Problems in unabhängige Teile vollbracht, so dass jedes in einer Prozession gehende Element seinen Teil des Algorithmus gleichzeitig mit anderen durchführen kann. Die in einer Prozession gehenden Elemente können verschieden sein und Mittel wie ein einzelner Computer mit vielfachen Verarbeitern, mehrere vernetzte Computer, Spezialhardware oder jede Kombination des obengenannten einschließen.

Frequenzschuppen war der dominierende Grund für Verbesserungen in der Computerleistung von der Mitte der 1980er Jahre bis 2004. Die Durchlaufzeit eines Programms ist der Zahl von Instruktionen gleich, die mit der durchschnittlichen Zeit pro Instruktion multipliziert sind. Das Aufrechterhalten etwas anderen Unveränderlichen, die Erhöhung der Uhr-Frequenz vermindern die durchschnittliche Zeit, die man braucht, um eine Instruktion durchzuführen. Eine Zunahme in der Frequenz nimmt so ab Durchlaufzeit für alle rechnen - gebundene Programme.

Jedoch wird der Macht-Verbrauch durch einen Span durch die Gleichung P = C &times gegeben; V × F, wo P Macht ist, ist C die Kapazität, die pro Uhr-Zyklus wird schaltet (proportional zur Zahl von Transistoren, deren sich Eingänge ändern), V ist Stromspannung, und F ist die Verarbeiter-Frequenz (Zyklen pro Sekunde). Zunahmen in der Frequenz vergrößern den Betrag der in einem Verarbeiter verwendeten Macht. Die Erhöhung des Verarbeiter-Macht-Verbrauchs geführt schließlich nach der Annullierung im Mai 2004 von Intel seiner Verarbeiter von Tejas und Jayhawk, die allgemein als das Ende der Frequenz zitiert wird, die als das dominierende Computerarchitektur-Paradigma klettert.

Das Gesetz von Moore ist die empirische Beobachtung, dass sich die Transistor-Dichte in einem Mikroprozessor alle 18 bis 24 Monate verdoppelt. Trotz Macht-Verbrauchsprobleme und wiederholter Vorhersagen seines Endes ist das Gesetz von Moore noch tatsächlich. Mit dem Ende des Frequenzschuppens können diese zusätzlichen Transistoren (die für das Frequenzschuppen nicht mehr verwendet werden) verwendet werden, um Extrahardware für die parallele Computerwissenschaft hinzuzufügen.

Das Gesetz von Amdahl und das Gesetz von Gustafson

Optimal würde die Beschleunigung von parallelization geradlinig sein — Verdoppelung der Zahl von in einer Prozession gehenden Elementen sollte die Durchlaufzeit und Verdoppelung davon halbieren ein zweites Mal sollte wieder die Durchlaufzeit halbieren. Jedoch erreichen sehr wenige parallele Algorithmen optimale Beschleunigung. Die meisten von ihnen haben eine nah-geradlinige Beschleunigung für kleine Anzahlen von in einer Prozession gehenden Elementen, die in einen unveränderlichen Wert für die große Anzahl von in einer Prozession gehenden Elementen flach wird.

Die potenzielle Beschleunigung eines Algorithmus auf einer parallelen Rechenplattform wird durch das Gesetz von Amdahl gegeben, das ursprünglich von Gene Amdahl in den 1960er Jahren formuliert ist. Es stellt fest, dass ein kleiner Teil des Programms, das parallelized nicht sein kann, die gesamte von parallelization verfügbare Beschleunigung beschränken wird. Ein Programm, das ein großes mathematisches oder Technikproblem behebt, wird normalerweise aus mehreren parallelizable Teilen und mehreren non-parallelizable (folgende) Teile bestehen. Wenn der Bruchteil der Laufzeit ist, gibt ein folgendes Programm für non-parallelizable Teile, dann aus

ist die maximale Beschleunigung mit parallelization des Programms. Wenn der folgende Teil eines Programms für 10 % der Durchlaufzeit verantwortlich ist, können wir nicht mehr als 10&times kommen; Beschleunigung, unabhängig davon, wie viele Verarbeiter hinzugefügt werden. Das stellt eine obere Grenze auf die Nützlichkeit des Hinzufügens mehr paralleler Ausführungseinheiten. "Wenn eine Aufgabe wegen folgender Einschränkungen nicht verteilt werden kann, hat die Anwendung von mehr Anstrengung keine Wirkung auf die Liste. Das Lager eines Kindes nimmt neun Monate, egal wie viele Frauen zugeteilt werden."

Das Gesetz von Gustafson ist ein anderes Gesetz in der Computerwissenschaft, die nah mit dem Gesetz von Amdahl verbunden ist. Es stellt fest, dass die Beschleunigung mit Verarbeitern ist

Das Gesetz von Amdahl nimmt eine feste Problem-Größe an, und dass die Laufzeit der folgenden Abteilung des Programms der Zahl von Verarbeitern unabhängig ist, wohingegen das Gesetz von Gustafson diese Annahmen nicht macht.

Abhängigkeiten

Das Verstehen von Datenabhängigkeiten ist im Einführen paralleler Algorithmen grundsätzlich. Kein Programm kann schneller laufen als die längste Kette von abhängigen Berechnungen (bekannt als der kritische Pfad), da Berechnungen, die von vorherigen Berechnungen in der Kette abhängen, in der Ordnung durchgeführt werden müssen. Jedoch bestehen die meisten Algorithmen aus gerade einer langen Kette von abhängigen Berechnungen nicht; es gibt gewöhnlich Gelegenheiten, unabhängige Berechnungen in der Parallele durchzuführen.

Lassen Sie P und P zwei Programm-Bruchstücke sein. Die Bedingungen von Bernstein beschreiben, wenn die zwei unabhängig sind und in der Parallele durchgeführt werden können. Für P, lassen Sie mich alle Eingangsvariablen und O die Produktionsvariablen, und ebenfalls für P sein. P und P sind unabhängig, wenn sie befriedigen

Die Übertretung der ersten Bedingung führt eine Fluss-Abhängigkeit entsprechend der ersten Behauptung ein, die ein durch die zweite Behauptung verwendetes Ergebnis erzeugt. Die zweite Bedingung vertritt eine Antiabhängigkeit, wenn die zweite Behauptung (P) eine durch den ersten Ausdruck (P) erforderliche Variable überschreiben würde. Die dritte und endgültige Bedingung vertritt eine Produktionsabhängigkeit: Wenn zwei Behauptungen derselben Position schreiben, muss das Endresultat aus der logisch letzten durchgeführten Behauptung kommen.

Denken Sie die folgenden Funktionen, die mehrere Arten von Abhängigkeiten demonstrieren:

1: fungieren Sie Abfahrt (a, b)

2: c: = a · b

3: d: = 3 · c

4: beenden Sie Funktion

Operation 3 in der Abfahrt (a, b) kann vorher (oder sogar in der Parallele mit) Operation 2, weil Operation 3 Gebrauch ein Ergebnis von Operation 2 nicht durchgeführt werden. Es verletzt Bedingung 1, und führt so eine Fluss-Abhängigkeit ein.

1: fungieren Sie NoDep (a, b)

2: c: = a · b

3: d: = 3 · b

4: e: = a+b

5: beenden Sie Funktion

In diesem Beispiel gibt es keine Abhängigkeiten zwischen den Instruktionen, so können sie alle in der Parallele geführt werden.

Die Bedingungen von Bernstein erlauben Gedächtnis nicht, zwischen verschiedenen Prozessen geteilt zu werden. Dafür ist ein Mittel, eine Einrichtung zwischen Zugängen geltend zu machen, wie Semaphore, Barrieren oder eine andere Synchronisationsmethode notwendig.

Rasse-Bedingungen, gegenseitiger Ausschluss, Synchronisation und parallele Verlangsamung

Teilaufgaben in einem parallelen Programm werden häufig Fäden genannt. Kleinere, leichte Versionen von Gebrauch von Architekturen eines parallelen Computers von als Fasern bekannten Fäden, während andere größere als Prozesse bekannte Versionen verwenden. Jedoch, "Fäden" wird allgemein als ein Oberbegriff für Teilaufgaben akzeptiert. Fäden werden häufig eine Variable aktualisieren müssen, die zwischen ihnen geteilt wird. Die Instruktionen zwischen den zwei Programmen können in jeder Ordnung durchgeschossen werden. Denken Sie zum Beispiel das folgende Programm:

Wenn Instruktion 1B zwischen 1A und 3A durchgeführt wird, oder wenn Instruktion 1A zwischen 1B und 3B durchgeführt wird, wird das Programm falsche Daten erzeugen. Das ist als eine Rasse-Bedingung bekannt. Der Programmierer muss ein Schloss verwenden, um gegenseitigen Ausschluss zur Verfügung zu stellen. Ein Schloss ist eine Programmiersprache-Konstruktion, die einem Faden erlaubt, Kontrolle einer Variable zu nehmen und andere Fäden davon abzuhalten, es zu lesen oder zu schreiben, bis diese Variable aufgeschlossen wird. Der Faden, der das Schloss hält, ist frei, seine kritische Abteilung durchzuführen (die Abteilung eines Programms, das exklusiven Zugang zu einer Variable verlangt), und die Daten aufzuschließen, wenn es beendet wird. Deshalb, um richtige Programm-Ausführung zu versichern, kann das obengenannte Programm umgeschrieben werden, um Schlösser zu verwenden:

Ein Faden wird Variable V erfolgreich schließen, während der andere Faden — unfähig ausgesperrt wird weiterzugehen, bis V wieder aufgeschlossen wird. Das versichert richtige Ausführung des Programms. Schlösser, während notwendig, um richtige Programm-Ausführung zu sichern, können ein Programm außerordentlich verlangsamen.

Die Blockierung vielfacher Variablen mit Nichtatomschlössern führt die Möglichkeit des toten Programm-Punktes ein. Ein Atomschloss schließt vielfache Variablen plötzlich. Wenn es sie alle nicht schließen kann, schließt es keinen von ihnen. Wenn zwei Fäden jedes Bedürfnis, dieselben zwei Variablen mit Nichtatomschlössern zu schließen, es möglich ist, dass ein Faden einen von ihnen schließen wird und der zweite Faden die zweite Variable schließen wird. In solch einem Fall kann kein Faden vollenden, und Ergebnisse festfahren.

Viele parallele Programme verlangen, dass ihre Teilaufgaben in der Gleichzeitigkeit handeln. Das verlangt den Gebrauch einer Barriere. Barrieren werden normalerweise mit einem Softwareschloss durchgeführt. Eine Klasse von Algorithmen, bekannt als ohne Schlösser und wartet - freie Algorithmen, zusammen vermeidet den Gebrauch von Schlössern und Barrieren. Jedoch ist diese Annäherung allgemein schwierig durchzuführen und verlangt richtig entworfene Datenstrukturen.

Nicht der ganze parallelization läuft auf Beschleunigung hinaus. Allgemein, weil eine Aufgabe in immer mehr Fäden aufgeteilt wird, geben jene Fäden einen ständig steigenden Teil ihrer Zeit aus, mit einander kommunizierend. Schließlich herrschen die Gemeinkosten von der Kommunikation vor die Zeit hat das Beheben des Problems, und weiter parallelization ausgegeben (d. h. das Arbeitspensum noch mehr Fäden spaltend), vergrößert aber nicht vermindert die Zeitdauer, die erforderlich ist fertig zu sein. Das ist als parallele Verlangsamung bekannt.

Feinkörniger, grobkörniger und peinlicher Parallelismus

Anwendungen werden häufig gemäß klassifiziert, wie oft ihre Teilaufgaben gleichzeitig sein oder mit einander kommunizieren müssen. Eine Anwendung stellt feinkörnigen Parallelismus aus, wenn seine Teilaufgaben oft pro Sekunde kommunizieren müssen; es stellt grobkörnigen Parallelismus aus, wenn sie oft pro Sekunde nicht kommunizieren, und es peinlich parallel ist, wenn sie selten oder nie kommunizieren müssen. Peinlich parallele Anwendungen werden als das leichteste zu parallelize betrachtet.

Konsistenz-Modelle

Parallele Programmiersprachen und parallele Computer müssen ein Konsistenz-Modell (auch bekannt als ein Speichermodell) haben. Das Konsistenz-Modell definiert Regeln dafür, wie Operationen auf dem Computergedächtnis vorkommen, und wie Ergebnisse erzeugt werden.

Eines der ersten Konsistenz-Modelle war das folgende Konsistenz-Modell von Leslie Lamport. Folgende Konsistenz ist das Eigentum eines parallelen Programms, dass seine parallele Ausführung dieselben Ergebnisse wie ein folgendes Programm erzeugt. Spezifisch entspricht ein Programm folgend, wenn "... die Ergebnisse einer Ausführung dasselbe sind, als ob die Operationen aller Verarbeiter in einer folgenden Ordnung durchgeführt wurden, und die Operationen jedes individuellen Verarbeiters in dieser Folge in der durch sein Programm angegebenen Ordnung erscheinen".

Software transactional Gedächtnis ist ein allgemeiner Typ des Konsistenz-Modells. Software transactional Gedächtnis leiht von der Datenbanktheorie das Konzept von Atomtransaktionen und wendet sie auf Speicherzugänge an.

Mathematisch können diese Modelle auf mehrere Weisen vertreten werden. Netze von Petri, die 1962 von Carl Adam Petri Doktorthese eingeführt wurden, waren ein früher Versuch, die Regeln von Konsistenz-Modellen zu kodifizieren. Theorie von Dataflow, die später auf diese und Architekturen von Dataflow gebaut ist, wurde geschaffen, um die Ideen von der dataflow Theorie physisch durchzuführen. Der Anfang gegen Ende der 1970er Jahre, wurden die Prozess-Rechnungen wie Rechnung von Kommunizierenden Systemen und das Kommunizieren Folgender Prozesse entwickelt, um das algebraische Denken über aus aufeinander wirkenden Bestandteilen zusammengesetzte Systeme zu erlauben. Neuere Hinzufügungen zur Prozess-Rechnungsfamilie, solcher als π-calculus, haben die Fähigkeit hinzugefügt, um über dynamische Topologien vernünftig zu urteilen. Logik wie der TLA von Lamport +, und mathematische Modelle wie Spuren und Schauspieler-Ereignis-Diagramme, ist auch entwickelt worden, um das Verhalten von gleichzeitigen Systemen zu beschreiben.

Die Taxonomie von Flynn

Michael J. Flynn hat eines der frühsten Klassifikationssysteme für die Parallele (und folgend) Computer und Programme geschaffen, die jetzt als die Taxonomie von Flynn bekannt sind. Flynn hat Programme und Computer dadurch klassifiziert, ob sie das Verwenden eines einzelnen Satzes oder vielfacher Sätze von Instruktionen bedienten, ob jene Instruktionen eine Single oder vielfache Sätze von Daten verwendeten.

Die Klassifikation der einzelnen Instruktion einzelnen Daten (SISD) ist zu einem völlig folgenden Programm gleichwertig. Die Klassifikation der einzelnen Instruktion vielfachen Daten (SIMD) ist dem Tun derselben Operation wiederholt über eine große Datei analog. Das wird in Signalverarbeitungsanwendungen allgemein getan. Vielfache Instruktion einzelne Daten (MISD) ist eine selten verwendete Klassifikation. Während Computerarchitekturen, um sich damit zu befassen (wie Systolic-Reihe), wenige Anwendungen ausgedacht wurden, die diese verwirklichte Klasse passen. Programme der vielfachen Instruktion vielfachen Daten (MIMD) sind bei weitem der allgemeinste Typ von parallelen Programmen.

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

Typen des Parallelismus

Parallelismus des Bit-Niveaus

Vom Advent der Computerchip-Herstellungstechnologie der Größtintegration (VLSI) in den 1970er Jahren ungefähr bis 1986 wurde die Beschleunigung in der Computerarchitektur durch die Verdoppelung der Computerwortgröße — der Betrag der Information gesteuert, die der Verarbeiter pro Zyklus manipulieren kann. Die Erhöhung der Wortgröße vermindert die Anzahl von Instruktionen, die der Verarbeiter durchführen muss, um eine Operation auf Variablen durchzuführen, deren Größen größer sind als die Länge des Wortes. Zum Beispiel, wo ein 8-Bit-Verarbeiter zwei ganze 16-Bit-Zahlen hinzufügen muss, muss der Verarbeiter zuerst die 8 Bit der niedrigeren Ordnung von jeder ganzen Zahl mit der Standardhinzufügungsinstruktion hinzufügen, dann die 8 höherwertigen Bit mit einer add-carry Instruktion und dem tragen Bit von der niedrigeren Ordnungshinzufügung hinzuzufügen; so verlangt ein 8-Bit-Verarbeiter zwei Instruktionen, eine einzelne Operation zu vollenden, wo ein 16-Bit-Verarbeiter im Stande sein würde, die Operation mit einer einzelnen Instruktion zu vollenden.

Historisch wurden 4-Bit-Mikroprozessoren durch 8 Bit, dann 16 Bit, dann 32-Bit-Mikroprozessoren ersetzt. Diese Tendenz ist allgemein mit der Einführung von 32-Bit-Verarbeitern abgelaufen, die ein Standard in der Mehrzweckcomputerwissenschaft seit zwei Jahrzehnten gewesen ist. Erst als kürzlich (c. 2003-2004), mit dem Advent von x86-64 Architekturen, haben 64-Bit-Verarbeiter werden gewöhnlich.

Instruktionsniveau-Parallelismus

Ein Computerprogramm, ist hauptsächlich, ein Strom von durch einen Verarbeiter durchgeführten Instruktionen. Diese Instruktionen können wiederbestellt und in Gruppen verbunden werden, die dann in der Parallele hingerichtet werden, ohne das Ergebnis des Programms zu ändern. Das ist als Instruktionsniveau-Parallelismus bekannt. Fortschritte im Instruktionsniveau-Parallelismus haben Computerarchitektur von der Mitte der 1980er Jahre bis zur Mitte der 1990er Jahre beherrscht.

Moderne Verarbeiter haben Mehrstufeninstruktionsrohrleitungen. Jede Bühne in der Rohrleitung entspricht einer verschiedenen Handlung, die der Verarbeiter auf dieser Instruktion in dieser Bühne durchführt; ein Verarbeiter mit einer N-stage Rohrleitung kann bis zu N verschiedenen Instruktionen in verschiedenen Stufen der Vollziehung haben. Das kanonische Beispiel eines pipelined Verarbeiters ist ein RISC Verarbeiter mit fünf Stufen: Instruktionsabruf, decodieren Sie, führen Sie Speicherzugang durch und schreiben Sie zurück. Der Pentium 4 Verarbeiter hatte eine 35-stufige Rohrleitung.

Zusätzlich zum Instruktionsniveau-Parallelismus von pipelining können einige Verarbeiter mehr als eine Instruktion auf einmal ausgeben. Diese sind als Superskalarverarbeiter bekannt. Instruktionen können zusammen nur gruppiert werden, wenn es keine Datenabhängigkeit zwischen ihnen gibt. Scoreboarding und der Algorithmus von Tomasulo (der scoreboarding ähnlich ist, aber von der Register-Umbenennung Gebrauch macht), sind zwei der allgemeinsten Techniken, um in Unordnung Ausführung und Instruktionsniveau-Parallelismus durchzuführen.

Datenparallelismus

Datenparallelismus ist Programm-Schleifen innewohnender Parallelismus, der sich darauf konzentriert, die Daten über verschiedene in der Parallele zu bearbeitende Rechenknoten zu verteilen. "Schleifen von Parallelizing führen häufig ähnlich (nicht notwendigerweise identisch) Arbeitsfolgen oder Funktionen, die auf Elementen einer großen Datenstruktur durchführen werden." Viele wissenschaftliche und Technikanwendungen stellen Datenparallelismus aus.

Eine Schleife-getragene Abhängigkeit ist die Abhängigkeit einer Schleife-Wiederholung auf der Produktion von einer oder mehr vorherigen Wiederholungen. Schleife-getragene Abhängigkeiten verhindern den parallelization von Schleifen. Denken Sie zum Beispiel den folgenden Pseudocode, der die ersten paar Fibonacci-Zahlen schätzt:

1: PREV1: = 0

2: PREV2: = 1

4: tun Sie:

5: KÖTER: = PREV1 + PREV2

6: PREV1: = PREV2

7: PREV2: = KÖTER

8: während (KÖTER

Aufgabe-Parallelismus

Aufgabe-Parallelismus ist die Eigenschaft eines parallelen Programms, dass "völlig verschiedene Berechnungen entweder auf denselben oder auf verschiedenen Sätzen von Daten durchgeführt werden können". Das hebt sich vom Datenparallelismus ab, wo dieselbe Berechnung auf denselben oder verschiedenen Sätzen von Daten durchgeführt wird. Aufgabe-Parallelismus klettert mit der Größe eines Problems nicht gewöhnlich.

Hardware

Gedächtnis und Kommunikation

Das Hauptgedächtnis in einem parallelen Computer ist irgendein geteiltes Gedächtnis (geteilt zwischen allen in einer Prozession gehenden Elementen in einem einzelnen Adressraum) oder verteiltes Gedächtnis (in dem jedes in einer Prozession gehende Element seinen eigenen lokalen Adressraum hat). Verteiltes Gedächtnis bezieht sich auf die Tatsache, dass das Gedächtnis logisch verteilt wird, aber häufig andeutet, dass es ebenso physisch verteilt wird. Verteilte geteilte Speicher- und Speichervirtualisierung verbindet die zwei Annäherungen, wo das in einer Prozession gehende Element sein eigenes lokales Gedächtnis und Zugang zum Gedächtnis auf nichtlokalen Verarbeitern hat. Zugänge zum lokalen Gedächtnis sind normalerweise schneller als Zugänge zum nichtlokalen Gedächtnis.

Computerarchitekturen, in denen auf jedes Element des Hauptgedächtnisses mit der gleichen Latenz und Bandbreite zugegriffen werden kann, sind als Systeme von Uniform Memory Access (UMA) bekannt. Gewöhnlich kann das nur durch ein geteiltes Speichersystem erreicht werden, in dem das Gedächtnis nicht physisch verteilt wird. Ein System, das dieses Eigentum nicht hat, ist als eine Architektur von Non-Uniform Memory Access (NUMA) bekannt. Verteilte Speichersysteme haben ungleichförmigen Speicherzugang.

Computersysteme machen von geheimen Lagern — kleine, schnelle in der Nähe vom Verarbeiter gelegene Erinnerungen Gebrauch, die vorläufige Kopien von Speicherwerten (in der Nähe sowohl im physischen als auch in logischen Sinn) versorgen. Parallele Computersysteme haben Schwierigkeiten mit geheimen Lagern, die denselben Wert in mehr als einer Position mit der Möglichkeit der falschen Programm-Ausführung versorgen können. Diese Computer verlangen ein Kohärenz-System des geheimen Lagers, das versteckte Werte nachgeht und sie strategisch reinigt, so richtige Programm-Ausführung sichernd. Das Busschnüffeln ist eine vom grössten Teil der üblichen Methodik, um nachzugehen, von denen auf Werte zugegriffen wird (und so gereinigt werden sollte). Das Entwerfen großer Hochleistungskohärenz-Systeme des geheimen Lagers ist ein sehr schwieriges Problem in der Computerarchitektur. Infolgedessen klettern Computerarchitekturen des geteilten Gedächtnisses nicht, sowie verteilte Speichersysteme tun.

Verarbeiter-Verarbeiter und Kommunikation des Verarbeiter-Gedächtnisses können in der Hardware auf mehrere Weisen, einschließlich über den geteilten (entweder mehrgetragen oder gleichzeitig gesandt) Gedächtnis, ein Querbalken-Schalter, ein geteilter Bus oder ein Verbindungsnetz einer Myriade von Topologien einschließlich Sterns, Rings, Baums, Hyperwürfels, fetter Hyperwürfel (ein Hyperwürfel mit mehr als einem Verarbeiter an einem Knoten), oder N-Dimensional-Ineinandergreifen durchgeführt werden.

Parallele auf Verbindungsnetzen gestützte Computer müssen eine Art Routenplanung haben, um den Übergang von Nachrichten zwischen Knoten zu ermöglichen, die nicht direkt verbunden werden. Das Medium, das für die Kommunikation zwischen den Verarbeitern verwendet ist, wird wahrscheinlich in großen Mehrverarbeiter-Maschinen hierarchisch sein.

Klassen von parallelen Computern

Parallele Computer können gemäß dem Niveau grob klassifiziert werden, an dem die Hardware Parallelismus unterstützt. Diese Klassifikation ist der Entfernung zwischen grundlegenden Rechenknoten weit gehend analog. Diese sind nicht gegenseitig exklusiv; zum Beispiel sind Trauben von symmetrischen Mehrverarbeitern relativ üblich.

Mehrkerncomputerwissenschaft

Ein Mehrkernverarbeiter ist ein Verarbeiter, der vielfache Ausführungseinheiten ("Kerne") auf demselben Span einschließt. Diese Verarbeiter unterscheiden sich von Superskalarverarbeitern, die vielfache Instruktionen pro Zyklus von einem Instruktionsstrom (Faden) ausgeben können; im Gegensatz kann ein Mehrkernverarbeiter vielfache Instruktionen pro Zyklus von vielfachen Instruktionsströmen ausgeben. Jeder Kern in einem Mehrkernverarbeiter kann Superskalar ebenso — d. h. auf jedem Zyklus potenziell sein, jeder Kern kann vielfache Instruktionen von einem Instruktionsstrom ausgeben.

Gleichzeitige Nebenläufigkeit (von denen HyperThreading von Intel am besten bekannt ist) war eine frühe Form von pseudo-multicoreism. Ein zur gleichzeitigen Nebenläufigkeit fähiger Verarbeiter hat nur eine Ausführungseinheit ("Kern"), aber wenn diese Ausführungseinheit leer läuft (solcher als während eines geheimen Lagers Fräulein), verwendet es diese Ausführungseinheit, um einen zweiten Faden zu bearbeiten. Der Zellmikroprozessor von IBM, der für den Gebrauch in Sony PlayStation 3 entworfen ist, ist ein anderer prominenter Mehrkernverarbeiter.

Symmetrische Mehrverarbeitung

Ein symmetrischer Mehrverarbeiter (SMP) ist ein Computersystem mit vielfachen identischen Verarbeitern, die Gedächtnis teilen und über einen Bus in Verbindung stehen. Busstreit hält Busarchitekturen davon ab zu klettern. Infolgedessen umfassen SMPs allgemein mehr als 32 Verarbeiter nicht. "Wegen der kleinen Größe der Verarbeiter und der bedeutenden Verminderung der Voraussetzungen für die durch große geheime Lager erreichte Busbandbreite sind solche symmetrischen Mehrverarbeiter äußerst rentabel, vorausgesetzt, dass ein genügend Betrag der Speicherbandbreite besteht."

Verteilte Computerwissenschaft

Ein verteilter Computer (auch bekannt als ein verteilter Speichermehrverarbeiter) sind ein verteiltes Speichercomputersystem, in dem die in einer Prozession gehenden Elemente durch ein Netz verbunden werden. Verteilte Computer sind hoch ersteigbar.

Traube-Computerwissenschaft

Eine Traube ist eine Gruppe lose verbundener Computer, die nah zusammenarbeiten, so dass in etwas Hinsicht sie als ein einzelner Computer betrachtet werden können. Trauben werden aus vielfachen eigenständigen durch ein Netz verbundenen Maschinen zusammengesetzt. Während Maschinen in einer Traube nicht symmetrisch sein müssen, ist das Lastausgleichen schwieriger, wenn sie nicht sind. Der allgemeinste Typ der Traube ist die Traube von Beowulf, die eine Traube ist, die auf vielfachen identischen kommerziellen Standardcomputern durchgeführt ist, die mit einem TCP/IP Ethernet lokales Bereichsnetz verbunden sind. Technologie von Beowulf wurde von Thomas Sterling und Donald Becker ursprünglich entwickelt. Die große Mehrheit der TOP500 Supercomputer ist Trauben.

Massive parallele Verarbeitung

Ein massiv paralleler Verarbeiter (MPP) ist ein einzelner Computer mit vielen vernetzten Verarbeitern. MPPs haben viele derselben Eigenschaften wie Trauben, aber MPPs haben Verbindungsnetze spezialisiert (wohingegen Trauben Warenhardware verwenden, um zu vernetzen). MPPs neigen auch dazu, größer zu sein als Trauben, normalerweise "weit mehr" habend, als 100 Verarbeiter. In einem MPP, "enthält jede Zentraleinheit sein eigenes Gedächtnis und Kopie des Betriebssystems und Anwendung. Jedes Subsystem kommuniziert mit anderen über eine Hochleistungsverbindung."

Blauer Gene/L, der fünfte schnellste Supercomputer in der Welt gemäß dem Juni 2009 TOP500 Rangordnung, ist ein MPP.

Bratrost-Computerwissenschaft

Verteilte Computerwissenschaft ist die am meisten verteilte Form der parallelen Computerwissenschaft. Es macht von Computern Gebrauch, die über das Internet kommunizieren, um an einem gegebenen Problem zu arbeiten. Wegen der niedrigen Bandbreite und äußerst hohe im Internet verfügbare Latenz befasst sich verteilte Computerwissenschaft normalerweise nur mit peinlich parallelen Problemen. Viele verteilte Rechenanwendungen sind geschaffen worden, von denen SETI@home und Folding@home die am besten bekannten Beispiele sind.

Rechenanwendungen des grössten Teiles des Bratrostes verwenden middleware, Software, die zwischen dem Betriebssystem und der Anwendung sitzt, um Netzmittel zu führen und die Softwareschnittstelle zu standardisieren. Die allgemeinste verteilte Computerwissenschaft middleware ist der Berkeley Offene Infrastruktur für das Netz (BOINC) Rechnend. Häufig macht verteilte Rechensoftware von "Ersatzzyklen" Gebrauch, Berechnung zuweilen durchführend, wenn ein Computer leer läuft.

Parallele Spezialcomputer

Innerhalb der parallelen Computerwissenschaft, dort werden parallele Geräte spezialisiert, die Nische-Gebiete von Interesse bleiben. Während nicht bereichsspezifisch sie dazu neigen, auf nur einige Klassen von parallelen Problemen anwendbar zu sein.

Wiederkonfigurierbare Computerwissenschaft mit der feldprogrammierbaren Tor-Reihe

Wiederkonfigurierbare Computerwissenschaft ist der Gebrauch einer feldprogrammierbaren Tor-Reihe (FPGA) als ein Coprozessor zu einem Mehrzweckcomputer. Ein FPGA, ist hauptsächlich, ein Computerspan, der sich für eine gegebene Aufgabe neu verdrahten kann.

FPGAs kann mit Hardware-Beschreibungssprachen wie VHDL oder Verilog programmiert werden. Jedoch kann die Programmierung auf diesen Sprachen langweilig sein. Mehrere Verkäufer haben C in HDL Sprachen geschaffen, die versuchen, mit der Syntax und/oder Semantik der C Programmiersprache wettzueifern, mit der die meisten Programmierer vertraut sind. Die am besten bekannten C in HDL Sprachen sind Mitrion-C, Impuls C, ZEHNCENTSTÜCK-C und Handel-C. Spezifische Teilmengen von SystemC, der auf C ++ gestützt ist, können auch für diesen Zweck verwendet werden.

Die Entscheidung von AMD, seine Technologie von HyperTransport Drittverkäufern zu öffnen, ist die Ermöglichen-Technologie für die wiederkonfigurierbare Hochleistungscomputerwissenschaft geworden. Gemäß Michael R. D'Amour, Hauptbetriebsoffizier von DRC Computer Corporation, "als wir zuerst in AMD spazieren gegangen sind, haben sie uns 'die Steckdose stealers genannt.' Jetzt nennen sie uns ihre Partner."

Mehrzweckcomputerwissenschaft auf Grafikverarbeitungseinheiten (GPGPU)

Die Mehrzweckcomputerwissenschaft auf Grafikverarbeitungseinheiten (GPGPU) ist eine ziemlich neue Tendenz in der Computertechnikforschung. GPUs sind Coprozessoren, die für die Computergrafik-Verarbeitung schwer optimiert worden sind. Computergrafik-Verarbeitung ist ein Feld, das durch Datenparallele-Operationen — besonders geradlinige Algebra-Matrixoperationen beherrscht ist.

In den frühen Tagen haben GPGPU Programme den normalen Grafik-APIs verwendet, um Programme durchzuführen. Jedoch sind mehrere neue Programmiersprachen und Plattformen gebaut worden, um allgemeine Zweck-Berechnung auf GPUs sowohl mit Ausgabe-Programmierumgebungen von Nvidia als auch mit AMD mit CUDA und Strom SDK beziehungsweise zu tun. Andere GPU Programmiersprachen sind BrookGPU, PeakStream und RapidMind. Nvidia hat auch spezifische Produkte für die Berechnung in ihrer Reihe von Tesla veröffentlicht. Khronos Technologiekonsortium-Group hat die Spezifizierung von OpenCL veröffentlicht, die ein Fachwerk ist, um Programme zu schreiben, die über Plattformen durchführen, die aus Zentraleinheiten und GPUs bestehen. Apfel, Intel, unterstützen Nvidia und andere OpenCL.

Anwendungsspezifische einheitliche Stromkreise

Mehrere Annäherungen des anwendungsspezifischen einheitlichen Stromkreises (ASIC) sind ausgedacht worden, um sich mit parallelen Anwendungen zu befassen.

Weil ein ASIC (definitionsgemäß) zu einer gegebenen Anwendung spezifisch ist, kann er für diese Anwendung völlig optimiert werden. Infolgedessen, für eine gegebene Anwendung, neigt ein ASIC dazu, einen Mehrzweckcomputer zu überbieten. Jedoch werden ASICs durch das Röntgenstrahl-Steindruckverfahren geschaffen. Dieser Prozess verlangt eine Maske, die äußerst teuer sein kann. Eine einzelne Maske kann mehr als eine Million US-Dollar kosten. (Je kleiner die Transistoren für den Span verlangt haben, desto teurer die Maske sein wird.) Inzwischen neigen Leistungszunahmen in der Mehrzweckcomputerwissenschaft mit der Zeit (wie beschrieben, durch das Gesetz von Moore) dazu, diese Gewinne in nur einer oder zwei Span-Generationen wegzuwischen. Hohe anfängliche Kosten und die Tendenz, von Moore-Law-Driven Mehrzweckcomputerwissenschaft eingeholt zu werden, haben ASICs unausführbar für die meisten parallelen Rechenanwendungen gemacht. Jedoch sind einige gebaut worden. Ein Beispiel ist der Peta-Misserfolg RIKEN MDGRAPE-3 Maschine, die kundenspezifischen ASICs für die molekulare Dynamik-Simulation verwendet.

Vektor-Verarbeiter

Ein Vektor-Verarbeiter ist eine Zentraleinheit oder Computersystem, das dieselbe Instruktion auf großen Sätzen von Daten durchführen kann. "Vektor-Verarbeiter haben Operationen auf höchster Ebene, die an der geradlinigen Reihe von Zahlen oder Vektoren arbeiten. Eine Beispiel-Vektor-Operation ist = B × C, wo A, B, und C jeder 64-Elemente-Vektoren von 64-Bit-Schwimmpunkt-Zahlen sind." Sie sind nah mit der SIMD Klassifikation von Flynn verbunden.

Computer von Cray sind berühmt wegen ihrer Vektoren bearbeitenden Computer in den 1970er Jahren und 1980er Jahren geworden. Jedoch sind Vektor-Verarbeiter — sowohl als Zentraleinheiten als auch als volle Computersysteme — allgemein verschwunden. Moderne Verarbeiter-Befehlssätze schließen wirklich einige Vektor-Verarbeitungsinstruktionen, solcher als mit AltiVec und Streaming SIMD Extensions (SSE) ein.

Software

Parallele Programmiersprachen

, Bibliotheken, APIs und parallele Programmiermodelle (wie Algorithmische Skelette) sind geschaffen worden, um parallele Computer zu programmieren. Diese können allgemein in Klassen geteilt werden, die auf den Annahmen gestützt sind, die sie über die zu Grunde liegende Speicherarchitektur — geteiltes Gedächtnis, verteiltes Gedächtnis machen, oder verteiltes Gedächtnis geteilt haben. Geteilte Speicherprogrammiersprachen kommunizieren durch die Manipulierung von geteilten Speichervariablen. Verteiltes Gedächtnis verwendet Nachrichtenübergang. POSIX Fäden und OpenMP sind zwei des am weitesten verwendeten geteilten Gedächtnisses APIs, wohingegen Message Passing Interface (MPI) die am weitesten verwendete nachrichtenpassierende System-API ist. Ein in der Programmierung paralleler Programme verwendetes Konzept ist das zukünftige Konzept, wo ein Teil eines Programms verspricht, eine erforderliche Gegebenheit an einen anderen Teil eines Programms in einer zukünftigen Zeit zu liefern.

KAPPEN entreprise und Pathscale koordinieren auch ihre Anstrengung, HMPP (Hybride Mehrkernparallele-Programmierung) Direktiven zu machen, ein Offener Standard hat OpenHMPP angezeigt.

OpenHMPP Direktive-basiertes Programmiermodell bietet eine Syntax an, um Berechnung auf Hardware-Gaspedalen effizient abzuladen und Datenfluss zu/von dem Hardware-Gedächtnis zu optimieren. Direktiven von OpenHMPP beschreiben entfernten Verfahren-Anruf (RPC) auf einem Gaspedal-Gerät (z.B. GPU) oder mehr allgemein eine Reihe von Kernen. Die Direktiven kommentieren Codes von C oder Fortran, um zwei Sätze von Funktionalitäten zu beschreiben: Das Abladen von Verfahren (hat codelets angezeigt), auf ein entferntes Gerät und die Optimierung von Datenübertragungen zwischen der Zentraleinheit Hauptgedächtnis und dem Gaspedal-Gedächtnis.

Automatischer parallelization

Automatischer parallelization eines folgenden Programms durch einen Bearbeiter ist der heilige Gral der parallelen Computerwissenschaft. Trotz Jahrzehnte der Arbeit von Bearbeiter-Forschern hat automatischer parallelization nur beschränkten Erfolg gehabt.

Parallele Hauptströmungsprogrammiersprachen bleiben entweder ausführlich Parallele oder (am besten) teilweise implizit, in dem ein Programmierer die Bearbeiter-Direktiven für parallelization gibt. Einige völlig implizite parallele Programmiersprachen bestehen — SISAL, Parallel Haskell, und (für FPGAs) Mitrion-C.

Anwendung checkpointing

Je größer und komplizierter ein Computer ist, desto mehr, der schief gehen kann und kürzer die mittlere Zeit zwischen Misserfolgen. Anwendung checkpointing ist eine Technik, wodurch das Computersystem einen "Schnellschuss" der Anwendung — eine Aufzeichnung aller aktuellen Betriebsmittelzuweisungen und variabler Staaten nimmt, die mit einer Kernmüllkippe verwandt sind; diese Information kann verwendet werden, um das Programm wieder herzustellen, wenn der Computer scheitern sollte. Anwendung checkpointing bedeutet, dass das Programm von nur seinem letzten Kontrollpunkt aber nicht der Anfang wiederanfangen muss. Für eine Anwendung, die seit Monaten laufen kann, der kritisch ist. Anwendung checkpointing kann verwendet werden, um Prozess-Wanderung zu erleichtern.

Algorithmische Methoden

Da parallele Computer größer und schneller werden, wird es ausführbar, Probleme zu beheben, die vorher zu lange genommen haben, um zu laufen. Parallele Computerwissenschaft wird in einer breiten Reihe von Feldern, von bioinformatics (Protein-Falte und Folge-Analyse) zur Volkswirtschaft (mathematische Finanz) verwendet. Allgemeine Typen von in parallelen Rechenanwendungen gefundenen Problemen sind:

• Dichte geradlinige Algebra
• Spärliche geradlinige Algebra
• Geisterhafte Methoden (wie Cooley-Tukey schneller Fourier verwandeln sich)
• N-Körperprobleme (wie Barnes-Hütte-Simulation)
• Strukturierte Bratrost-Probleme (wie Methoden von Lattice Boltzmann)
• Unstrukturierte Bratrost-Probleme (solcher, wie gefunden, in der begrenzten Element-Analyse)
• Simulation von Monte Carlo
• Logik von Combinational (wie rohe Gewalt kryptografische Techniken)
• Graph-Traversal (wie das Sortieren von Algorithmen)
• Dynamische Programmierung
• Zweig und gebundene Methoden
• Grafische Modelle (wie das Ermitteln von verborgenen Modellen von Markov und Konstruieren von Netzen von Bayesian)
• Zustandsmaschinensimulation

Geschichte

Die Ursprünge des wahren (MIMD) Parallelismus gehen Federico Luigi, Conte Menabrea und seiner "Skizze des Analytischen durch Charles Babbage Erfundenen Motors" zurück. IBM hat die 704 1954 durch ein Projekt eingeführt, in dem Gene Amdahl einer der Hauptarchitekten war. Es ist der erste gewerblich verfügbare Computer geworden, um vollautomatische Schwimmpunkt-Arithmetik-Befehle zu verwenden.

Im April 1958 hat S. Gill (Ferranti) parallele Programmierung und das Bedürfnis danach besprochen, sich zu verzweigen und zu warten. Auch 1958 haben Forscher von IBM John Cocke und Daniel Slotnick den Gebrauch des Parallelismus in numerischen Berechnungen zum ersten Mal besprochen. Burroughs Corporation hat den D825 1962, einen Vier-Verarbeiter-Computer eingeführt, der auf bis zu 16 Speichermodule durch einen Querbalken-Schalter zugegriffen hat. 1967 haben Amdahl und Slotnick eine Debatte über die Durchführbarkeit der parallelen Verarbeitung an der amerikanischen Föderation der in einer Prozession gehenden Informationsgesellschaftskonferenz veröffentlicht. Es war während dieser Debatte, dass das Gesetz von Amdahl ins Leben gerufen wurde, um die Grenze der Beschleunigung wegen des Parallelismus zu definieren.

1969 hat US-Gesellschaft Honeywell sein erstes System von Multics, ein symmetrisches Mehrverarbeiter-System eingeführt, das dazu fähig ist, auf acht Verarbeiter in der Parallele zuzulaufen. C.mmp, ein Mehrverarbeiter-Projekt der 1970er Jahre an der Universität von Carnegie Mellon, war "unter den ersten Mehrverarbeitern mit mehr als einige Verarbeiter". "Der erste busverbundene Mehrverarbeiter mit herumschnüffelnden geheimen Lagern war die Synapse N+1 1984."

SIMD Parallele-Computer können zurück zu den 1970er Jahren verfolgt werden. Die Motivation hinter frühen SIMD Computern sollte die Tor-Verzögerung der Kontrolleinheit des Verarbeiters über vielfache Instruktionen amortisieren. 1964 hatte Slotnick vorgehabt, einen massiv parallelen Computer für den Lawrence Livermore Nationales Laboratorium zu bauen. Sein Design wurde von der US-Luftwaffe gefördert, die die frühste SIMD Parallele schätzende Anstrengung, ILLIAC IV war. Der Schlüssel zu seinem Design war ein ziemlich hoher Parallelismus mit bis zu 256 Verarbeitern, die der Maschine erlaubt haben, an großem datasets darin zu arbeiten, was später als Vektor-Verarbeitung bekannt wäre. Jedoch wurde ILLIAC IV "den am meisten berüchtigten von Supercomputern" genannt, weil das Projekt nur ein Viertel vollendet war, aber 11 Jahre genommen hat und fast viermal die ursprüngliche Schätzung gekostet hat. Als es schließlich bereit war, seine erste echte Anwendung 1976 zu führen, wurde es um vorhandene kommerzielle Supercomputer wie der Cray-1 überboten.

Siehe auch

• Liste von wichtigen Veröffentlichungen in der gleichzeitigen, parallelen und verteilten Computerwissenschaft
• Liste von verteilten Rechenkonferenzen
• Parallelität (Informatik)
• Gleichzeitige Computerwissenschaft
• Gleichzeitige Programmierung
• Addressable zufriedener Parallele-Verarbeiter
• Transputer

Weiterführende Literatur

• C. Rodríguez, M. Villagra und B. Barán, Bionetics2007, Seiten 66-69, 2007.

Links

• Lawrence Livermore nationales Laboratorium: Einführung, um Computerwissenschaft anzupassen
• Das Vergleichen programmability des Offenen Abgeordneten und pthreads
• Was macht Parallele, die hart programmiert?
• Das Entwerfen und das Gebäude paralleler Programme, durch Ian Foster
• Internetparallele, die Archiv schätzt
• Paralleles in einer Prozession gehendes Thema-Gebiet an IEEE Verteilte Computerwissenschaft Online-
• Parallele Rechenarbeiten freies Online-Buch
• Grenzen des Freien Superrechenonline-Buches, das Themen wie Algorithmen und Industrieanwendungen Behandelt
• Universales paralleles Rechenforschungszentrum
• Kurs in der Parallelen Programmierung an der Universität von Columbia (in der Kollaboration mit dem Projekt von IBM T.J Watson X10)
• Parallele und verteilter Grobner stützen Berechnung in JAS
• Kurs in der parallelen Computerwissenschaft auf die Universität von Wisconsin-Madison
• OpenHMPP, ein neuer Standard für Manycore