Pipeline (Computing) - Pipeline (computing)

Beim Rechnen ist eine Pipeline , auch als Datenpipeline bekannt , ein Satz von Datenverarbeitungselementen , die in Reihe geschaltet sind, wobei die Ausgabe eines Elements die Eingabe des nächsten Elements ist. Die Elemente einer Pipeline werden häufig parallel oder zeitgesteuert ausgeführt. Zwischen den Elementen wird häufig eine gewisse Menge an Pufferspeicher eingefügt.

Computerbezogene Pipelines umfassen:

Einige Betriebssysteme bieten möglicherweise eine UNIX-ähnliche Syntax, um mehrere Programmläufe in einer Pipeline zu verknüpfen, implementieren diese jedoch als einfache serielle Ausführung und nicht als echtes Pipelining, indem sie warten, bis jedes Programm abgeschlossen ist, bevor sie mit dem nächsten beginnen.

Konzept und Motivation

Pipelining ist ein im Alltag weit verbreitetes Konzept. Beispielsweise wird am Fließband einer Autofabrik jede spezifische Aufgabe - wie das Installieren des Motors, das Installieren der Motorhaube und das Installieren der Räder - häufig von einem separaten Arbeitsplatz ausgeführt. Die Stationen erledigen ihre Aufgaben parallel, jeweils in einem anderen Auto. Sobald ein Auto eine Aufgabe ausgeführt hat, fährt es zur nächsten Station. Variationen in der Zeit, die zur Erledigung der Aufgaben benötigt wird, können durch "Puffern" (Halten eines oder mehrerer Autos in einem Raum zwischen den Stationen) und / oder durch "Abwürgen" (vorübergehendes Anhalten der vorgelagerten Stationen) berücksichtigt werden, bis die nächste Station verfügbar wird .

Angenommen, die Montage eines Autos erfordert drei Aufgaben, die jeweils 20, 10 und 15 Minuten dauern. Wenn dann alle drei Aufgaben von einer einzigen Station ausgeführt würden, würde das Werk alle 45 Minuten ein Auto ausgeben. Bei Verwendung einer Pipeline mit drei Stationen gab das Werk das erste Auto in 45 Minuten und dann alle 20 Minuten ein neues aus.

Wie dieses Beispiel zeigt, verringert Pipelining nicht die Latenz , dh die Gesamtzeit, die ein Element benötigt, um das gesamte System zu durchlaufen. Es erhöht jedoch den Durchsatz des Systems, dh die Rate, mit der neue Artikel nach dem ersten verarbeitet werden.

Entwurfsüberlegungen

Balancieren der Bühnen

Da der Durchsatz einer Pipeline nicht besser sein kann als der des langsamsten Elements, sollte der Designer versuchen, die Arbeit und die Ressourcen auf die Phasen aufzuteilen, damit alle die gleiche Zeit für die Erledigung ihrer Aufgaben benötigen. Wenn im obigen Beispiel für die Fahrzeugmontage die drei Aufgaben jeweils 15 Minuten statt 20, 10 und 15 Minuten dauerten, würde die Latenz immer noch 45 Minuten betragen, aber ein neues Fahrzeug würde dann alle 15 Minuten anstelle von 20 Minuten fertiggestellt.

Pufferung

Wenn im Idealfall alle Verarbeitungselemente synchronisiert sind und die gleiche Verarbeitungszeit benötigt, kann jedes Element von jedem Element in einem einzigen Taktzyklus empfangen werden, so wie es vom vorherigen Element freigegeben wurde . Auf diese Weise fließen die Gegenstände mit einer konstanten Geschwindigkeit durch die Rohrleitung, wie Wellen in einem Wasserkanal. In solchen "Wellenpipelines" ist neben dem für die Datenelemente erforderlichen Speicher keine Synchronisation oder Pufferung zwischen den Stufen erforderlich.

Im Allgemeinen ist eine Pufferung zwischen den Pipeline-Stufen erforderlich, wenn die Verarbeitungszeiten unregelmäßig sind oder wenn Elemente entlang der Pipeline erstellt oder zerstört werden können. In einer Grafikpipeline, die Dreiecke verarbeitet, die auf dem Bildschirm gerendert werden sollen, kann ein Element, das die Sichtbarkeit jedes Dreiecks überprüft, das Dreieck verwerfen, wenn es unsichtbar ist, oder zwei oder mehr dreieckige Teile des Elements ausgeben, wenn sie teilweise sind versteckt. Das Puffern ist auch erforderlich, um Unregelmäßigkeiten in den Raten auszugleichen, mit denen die Anwendung Elemente der ersten Stufe zuführt und die Ausgabe der letzten Stufe verbraucht.

Der Puffer zwischen zwei Stufen kann einfach ein Hardwareregister mit geeigneter Synchronisations- und Signalisierungslogik zwischen den beiden Stufen sein. Wenn eine Stufe A ein Datenelement im Register speichert, sendet sie ein "Daten verfügbar" -Signal an die nächste Stufe B. Sobald B diese Daten verwendet hat, antwortet sie mit einem "Daten empfangen" -Signal an A. Stufe A hält an und wartet für dieses Signal, bevor das nächste Datenelement im Register gespeichert wird. Stufe B wird angehalten und wartet auf das Signal "Daten verfügbar", wenn es bereit ist, das nächste Element zu verarbeiten, Stufe A es jedoch noch nicht bereitgestellt hat.

Wenn die Verarbeitungszeiten eines Elements variabel sind, muss die gesamte Pipeline häufig angehalten werden und darauf warten, dass dieses Element und alle vorherigen Elemente die Elemente in ihren Eingabepuffern verbrauchen. Die Häufigkeit solcher Pipeline-Stillstände kann verringert werden, indem Platz für mehr als ein Element im Eingabepuffer dieser Stufe bereitgestellt wird. Ein solcher Puffer mit mehreren Elementen wird normalerweise als First-In- und First-Out-Warteschlange implementiert . Die Upstream-Phase muss möglicherweise noch angehalten werden, wenn die Warteschlange voll ist, aber die Häufigkeit dieser Ereignisse nimmt ab, wenn mehr Puffersteckplätze bereitgestellt werden. Die Warteschlangentheorie kann die Anzahl der benötigten Pufferschlitze in Abhängigkeit von der Variabilität der Verarbeitungszeiten und der gewünschten Leistung bestimmen.

Nichtlineare Pipelines

Wenn eine Phase viel länger dauert (oder dauern kann) als die anderen und nicht beschleunigt werden kann, kann der Designer zwei oder mehr Verarbeitungselemente bereitstellen, um diese Aufgabe parallel auszuführen, mit einem einzelnen Eingabepuffer und einem einzelnen Ausgabepuffer. Wenn jedes Element die Verarbeitung seines aktuellen Datenelements abgeschlossen hat, liefert es es an den gemeinsamen Ausgabepuffer und entnimmt das nächste Datenelement aus dem gemeinsamen Eingabepuffer. Dieses Konzept der "nichtlinearen" oder "dynamischen" Pipeline wird durch Geschäfte oder Banken veranschaulicht, in denen zwei oder mehr Kassierer Kunden aus einer einzigen Warteschlange bedienen.

Abhängigkeiten zwischen Elementen

In einigen Anwendungen kann die Verarbeitung eines Elements Y durch eine Stufe A von den Ergebnissen oder dem Effekt der Verarbeitung eines vorherigen Elements X durch eine spätere Stufe B der Pipeline abhängen. In diesem Fall kann Stufe A Punkt Y nicht korrekt verarbeiten, bis Punkt X Stufe B abgeschlossen hat.

Diese Situation tritt sehr häufig in Anweisungspipelines auf. Angenommen, Y ist eine arithmetische Anweisung, die den Inhalt eines Registers liest, das durch eine frühere Anweisung X modifiziert werden sollte. Sei A die Stufe, die die Befehlsoperanden abruft , und B die Stufe, die das Ergebnis schreibt in das angegebene Register. Wenn Stufe A versucht, Befehl Y zu verarbeiten, bevor Befehl X Stufe B erreicht, kann das Register immer noch den alten Wert enthalten, und die Wirkung von Y wäre falsch.

Um solche Konflikte korrekt zu behandeln, muss die Pipeline mit zusätzlichen Schaltkreisen oder Logik ausgestattet sein, die sie erkennen und die entsprechenden Maßnahmen ergreifen. Zu den Strategien hierfür gehören:

  • Blockieren: Jede betroffene Phase, wie z. B. A, wird angehalten, bis die Abhängigkeit aufgelöst ist, dh bis die erforderlichen Informationen verfügbar sind und / oder der erforderliche Status erreicht wurde.
  • Neuanordnen von Elementen: Anstatt zu blockieren, kann Stufe A Element Y beiseite legen und nach einem nachfolgenden Element Z in seinem Eingabestream suchen, für das keine Abhängigkeiten mit einem früheren Element anstehen. In Anweisungspipelines wird diese Technik als Ausführung außerhalb der Reihenfolge bezeichnet .
  • Vermutung und Rückverfolgung: Ein wichtiges Beispiel für die Abhängigkeit von Element zu Element ist die Behandlung eines bedingten Verzweigungsbefehls X durch eine Befehlspipeline. Die erste Stufe A der Pipeline, die den nächsten auszuführenden Befehl Y abruft, kann ihre Aufgabe erst ausführen, wenn X seinen Operanden abgerufen und bestimmt hat, ob die Verzweigung genommen werden soll oder nicht. Dies kann viele Taktzyklen dauern, da der Operand von X wiederum von vorherigen Anweisungen abhängen kann, die Daten aus dem Hauptspeicher abrufen.
Anstatt anzuhalten, während auf das Beenden von X gewartet wird, kann Stufe A erraten, ob der Zweig genommen wird oder nicht, und den nächsten Befehl Y basierend auf dieser Vermutung abrufen. Wenn sich die Vermutung später als falsch herausstellt (hoffentlich selten), müsste das System zurückverfolgen und mit der richtigen Auswahl fortfahren. Alle Änderungen, die bis zu Stufe A und nachfolgenden Stufen auf der Grundlage dieser Vermutung am Zustand der Maschine vorgenommen wurden, müssten rückgängig gemacht werden, die Anweisungen nach X, die sich bereits in der Pipeline befinden, müssten gelöscht werden und Stufe A müsste mit neu gestartet werden der richtige Anweisungszeiger . Diese Verzweigungsvorhersagestrategie ist ein Sonderfall der spekulativen Ausführung .

Kosten und Nachteile

Ein Pipeline-System benötigt normalerweise mehr Ressourcen (Schaltungselemente, Verarbeitungseinheiten, Computerspeicher usw.) als eines, das jeweils einen Stapel ausführt, da seine Stufen diese Ressourcen nicht gemeinsam nutzen können und möglicherweise Pufferung und zusätzliche Synchronisationslogik zwischen dem System erforderlich sind Elemente.

Darüber hinaus kann die Übertragung von Elementen zwischen separaten Verarbeitungselementen die Latenz erhöhen, insbesondere bei langen Pipelines.

Die zusätzlichen Komplexitätskosten für das Pipelining können beträchtlich sein, wenn Abhängigkeiten zwischen der Verarbeitung verschiedener Elemente bestehen, insbesondere wenn eine Vermutungs- und Rückverfolgungsstrategie verwendet wird, um diese zu handhaben. In der Tat haben die Kosten für die Implementierung dieser Strategie für komplexe Befehlssätze einige radikale Vorschläge zur Vereinfachung der Computerarchitektur wie RISC und VLIW motiviert . Compiler wurden auch mit der Aufgabe belastet, die Maschinenanweisungen neu anzuordnen, um die Leistung von Anweisungspipelines zu verbessern.

Neue Technologien

Es ist richtig, dass in den letzten Jahren die Anforderungen an Anwendungen und die zugrunde liegende Hardware erheblich waren. Zum Beispiel ist das Erstellen von Pipelines mit Einzelknotenanwendungen, die die Daten zeilenweise durchlaufen, mit dem Volumen und der Vielfalt von Big Data nicht mehr möglich . Mit dem Aufkommen von Datenanalyse-Engines wie Hadoop oder neuerdings Apache Spark war es jedoch möglich, große Datenmengen auf mehrere Verarbeitungsknoten zu verteilen, sodass Anwendungen Effizienzhöhen erreichen konnten, die mehrere hundert Mal höher waren als bisher angenommen. Dies hat heute zur Folge, dass selbst ein PC mittlerer Ebene, der auf diese Weise verteilte Verarbeitung verwendet, den Aufbau und Betrieb von Big-Data-Pipelines übernehmen kann.


Siehe auch

Verweise

  1. ^ Data Pipeline Development Veröffentlicht von Dativa, abgerufen am 24. Mai 2018
  2. ^ O. Hauck; Sorin A. Huss; M. Garg. "Zweiphasige asynchrone Wellenpipelines und ihre Anwendung auf eine 2D-DCT" . semantischer Gelehrter . Abgerufen am 14. September 2019 .
  3. ^ Was ist eine Datenpipeline? Veröffentlicht von Data Pipelines, abgerufen am 11. März 2021

Literaturverzeichnis