Prefetching
In der Computer Architektur bezeichnet Prefetching den Vorabruf (engl.: to prefetch) von Daten in den Zwischenspeicher (Cache), bevor der Prozessor diese Daten benötigt. Wenn der Prozessor die Daten verarbeiten will, sind sie bereits verfügbar und können in sehr kurzer Zeit bearbeitet werden. Würde die Daten nicht im Cache hinterlegt werden, müsste der Prozessor diese direkt von der Speicheradresse laden – entsprechend groß wären die Verzögerungszeiten (Latenzzeiten). Prefetching dient der Verkürzung der Zugriffsgeschwindigkeit und wird auf mehreren Leveln des Systems verwendet – zum Beispiel auch bei DDR Arbeitsspeichern oder Bootvorgängen von Betriebssystemen. Welche Daten in den Cache geladen werden, wird oft mithilfe eines sogenannten Branch Prediction Algorithm ermittelt.
Allgemeine Informationen zum Thema
Prozessoren führen ein Programm aus, indem sie Daten aus dem Speicher abrufen und die in den Daten hinterlegten Befehle ausführen. Üblicherweise ist die Arbeitsgeschwindigkeit des Prozessors – gemessen in Taktzyklen – jedoch schneller als die des Arbeitsspeichers. Ein Taktzyklus besteht in der Regel aus vier Phasen:[1]
- Daten werden geladen
- Daten werden dekodiert
- Daten werden ausgeführt
- Resultate werden geschrieben
Sehr häufig müssen weitere Daten eingeholt werden, damit das Programm fortfahren kann. An dieser Stelle kommen Prefetching-Mechanismen ins Spiel, um die Anzahl der Taktzyklen zu reduzieren. Der Prozessor arbeitet sequentiell: Das bedeutet, dass er einen Befehl nach dem anderen verarbeitet. Wenn er gerade mit einer Instruktion beschäftigt ist, kann er keine Daten für den darauffolgenden Befehl laden. Wenn der Prozessor die Daten dann abrufen würde, könnte er keine weiteren Instruktionen ausführen – die CPU würde sich sich in diesem Fall im Leerlauf befinden.
Damit der Prozessor seine Ressourcen so effektiv wie möglich einsetzen kann, werden solche Daten in den Cache geladen, die höchstwahrscheinlich als nächstes vom Prozessor benötigt werden. Somit verfügt die CPU vor dem Ausführen der nächsten Instruktion schon über die Speicherinhalte, die diese Instruktion erfordert. Generell gilt,
- dass Prefetching-Mechanismen sowohl Daten als auch Instruktionen abrufen können.
- dass die Anzahl der Taktzyklen durch Prefetching bis zu 30% reduziert werden kann.
- dass Prefetching in den Bereichen Hard- und Software sowie in Compilern zum Einsatz kommen kann.[2]
Funktionsweise
Die Berechnung, welche Daten oder Instruktionen als nächstes benötigt werden, erfolgt beim Hardware-Prefetching häufig via Algorithmus. Moderne Rechnerarchitekturen verwenden sogenannte Pipelines, um Aufgaben parallel zu verarbeiten.[3] Ist eine Pipeline mit einer Instruktion beschäftigt, kann eine weitere Pipeline zeitgleich Daten und weitere Instruktionen vorladen.
Beispielsweise arbeiten viele Programme mit Schleifen im Quellcode. Diese Schleifen enthalten Bedingungen, die der Prozessor erst noch überprüfen muss. Die Sprungvorhersage greift auf den Erfahrungswert zu, dass Schleifen stets Bedingungen enthalten und lädt vorab den Sprungbefehl und/ oder die Sprungzieladresse, um die dort hinterlegten Daten in einer parallelen Pipeline zu prefetchen. Ein Beispiel:[4]
for (int i = 0; i < vorbedingung; i++) {
// vorbedingung ist eine Variable, die vorher initialisiert wurde.
tueA();
}
tueB();
Wenn der Prozessor die Vorbedingung prüft, steht er vor der Frage, ob er die Instruktionen für „tueA“ im Cache behalten oder die Instruktionen für „tueB“ in den Cache laden soll. Er verwendet eine Heuristik, um vorherzusagen, welche Daten gerade im Zwischenspeicher gebraucht werden. Die Zuverlässigkeit der Vorhersage ist wesentlich davon abhängig, welche Heuristik implementiert worden ist. Meist erfolgt dies mithilfe eines speziellen Prefetcher-Moduls (Prefetch Input Que; PIQ). Die Ermittlung von wahrscheinlich benötigten Befehlen oder Daten wird auch als Branch Prediction (Sprungvorhersage) bezeichnet. Sie ist für die Verbesserung der Performance ein wesentlicher Faktor, denn die Vorhersagen von Instruktionen und Speicheradressen können auch falsch sein – auch wenn das vor dem Hntergrund moderner Branch Prediction Algorithmen nur bei etwa 2% der Fall ist.[5]
Praxisbezug
Wenn Prefetching mit der Branch Prediction verbunden ist, versucht der Prozessor vorherzusagen, welche Instruktionen und welche Daten zukünftig benötigt werden. Der Prozessor antizipiert das Ergebnis einer Berechnung zur Laufzeit des Computers und ruft die Daten oder Instruktionen ab, die der Algorithmus als relevant für die darauffolgende Berechnung erachtet. Dies können typische Befehlsfolgen oder Programmabläufe sein: Bei Bootvorgängen ist zum Beispiel klar, welche Programme für die Laufzeit des Systems notwendig sind. Die entsprechenden Instruktionen oder Daten werden in den Cache geladen und bei Bedarf vom Prozessor abgerufen, um den Bootvorgang zu beschleunigen: Der Rechner fährt schneller hoch, weil die Systemprogramme aufgrund der verfügbaren Daten schneller ausgeführt werden.
Es gibt jedoch verschiedene Arten der Branch Prediction. Die einfachste Variante arbeitet statisch, indem das Ergebnis eines Befehls vorhergesagt wird. Da mit diesem Ergebnis meist weitere Bedingungen einhergehen, kann der Prozessor abschätzen, welche Bedingungen als nächstes überprüft werden sollen. Komplexere Branch Prediction Algorithmen arbeiten dynamisch; und teilweise mit einer Branch Historie und einer Mustererkennung: Bereits ausgeführte Befehlszeilen oder Programme werden binär gespeichert und bei einem erneuten Aufruf kennt der Prozessor die Befehle oder Daten, auf die diese Befehle oder Programme rekurrieren. In den Bereichen Data Mining und Machine Learning werden mittlerweile auch Methoden verwendet, die auf neuronalen Netzen und künstlicher Intelligenz basieren.
Bedeutung für die Programmierung
Chiphersteller arbeiten ständig an Möglichkeiten, die Performance zu optimieren – Hardware Prefetching ist eine davon. Doch auch Programmierer können sich das Prefetching zunutze machen, indem sie „prefetching hints“ manuell in den Programmablauf einfügen. Dafür ist es notwendig, dass sie wissen, was, wann, wo und wie prefetched werden soll. Da Prefetching bestimmte Speicher-Ressourcen in Anspruch nimmt, ist es wichtig für den Programmablauf, dass die richtigen Daten an der richtigen Stelle abgerufen werden.[6]
Das Prinzip des Prefetching wird darüber hinaus auch bei Websites angewandt: Das sogenannte Link Prefetching kann Hyperlinks vorabrufen, wenn es wahrscheinlich ist, dass diese Links durch einen Nutzer angeklickt werden. In diesem Zusammenhang kommen allerdings keine komplizierten Algorithmen zum Einsatz, sondern allenfalls Webanalyse-Statistiken über das Nutzerverhalten oder die Surfhistorie. Auf Basis dieser Daten wird dann vom Webmaster entschieden, inwiefern es sinnvoll ist, Websites oder andere Ressourcen wie CSS-Datein und Medieninhalte zu prefetchen.
Einzelnachweise
- ↑ Rechnerarchitektur kreissl.info. Abgerufen am 26.10.2015
- ↑ Computer Architecture Lecture 24: Prefetching ece.cmu.edu. Abgerufen am 26.10.2015
- ↑ Pipelines, Prefetch und Branch Prediction bernd-leitenberger.de. Abgerufen am 26.10.2015
- ↑ Was ist Prefetching? hardwareluxx.de. Abgerufen am 26.10.2015
- ↑ Konflikte bei Verzweigungsbefehlen hs-augsburg.de. Abgerufen am 26.10.2015
- ↑ What programmers need to know about hardware prefetching? futurechips.org. Abgerufen am 26.10.2015
Weblinks