Hermes: Accelerating Long-Latency Load Requests via Perceptron-Based Off-Chip Load Prediction

Technisches Resümee: Hermes

Problemstellung

Latenzintensive Ladeanfragen, die die On-Chip-Cache-Hierarchie verfehlen und auf den Off-Chip-Hauptspeicher zugreifen, bleiben ein primärer Flaschenhals für moderne Hochleistungs-Out-of-Order (OOO)-Prozessoren. Diese Anfragen blockieren oft den Prozessorkern, indem sie das Abschluss der Instruktionen (Retirement) aus dem Reorder Buffer (ROB) verhindern.

Die Autoren identifizieren zwei kritische Trends in aktuellen Prozessordesigns, die die Leistung trotz bestehender Optimierungen einschränken:

1. Begrenzte Prefetcher-Abdeckung: Selbst hochmoderne Hardware-Prefetcher (z. B. Pythia) können nur etwa die Hälfte der Off-Chip-Ladeanfragen über eine breite Palette von Workloads hinweg vorhersagen. Die verbleibenden unvorhersehbaren Ladevorgänge verursachen weiterhin signifikante Stalls.
2. Steigende On-Chip-Cache-Latenz: Da On-Chip-Caches in Größe und Komplexität zunehmen, um größere Datenfootprints unterzubringen, hat die Latenz, die erforderlich ist, um die On-Chip-Cache-Hierarchie (L1, L2, LLC) zu durchlaufen, um festzustellen, dass eine Anfrage ein Miss ist, erheblich zugenommen. Ein beträchtlicher Teil der Gesamtlatenz eines Off-Chip-Loads wird allein für den Zugriff auf die On-Chip-Hierarchie aufgewendet, um den Miss zu bestätigen, anstatt auf die Antwort des Hauptspeichers zu warten.

Methodik

Das Paper schlägt Hermes vor, eine Technik, die darauf ausgelegt ist, Off-Chip-Ladeanfragen zu beschleunigen, indem sie die On-Chip-Cache-Zugriffslatenz aus deren kritischem Pfad entfernt.

Kernmechanismus

Hermes operiert nach dem Prinzip des spekulativen Off-Chip-Fetchings:

1. Vorhersage: Für jede Ladeanfrage bestimmt ein Prädiktor, ob die Anfrage wahrscheinlich die On-Chip-Hierarchie verfehlen und Off-Chip gehen wird.
2. Spekulativer Fetch: Wenn eine Ladeanfrage als Off-Chip vorhergesagt wird, gibt Hermes eine spekulative Anfrage (eine „Hermes-Anfrage“) direkt an den Main-Memory-Controller aus, sobald die physikalische Adresse generiert wurde.
3. Konkurrente Ausführung: Diese spekulative Anfrage läuft parallel zur regulären Ladeanfrage ab, welche weiterhin die standardmäßige On-Chip-Cache-Hierarchie durchläuft.
4. Latenzverdeckung: Wenn die Vorhersage korrekt ist, verfehlt die reguläre Ladung schließlich den Last-Level-Cache (LLC) und wartet auf den laufenden spekulativen Prozess. Dies verdeckt effektiv die On-Chip-Cache-Traversierungslatenz im Schatten der Main-Memory-Latenz.
5. Kohärenz: Wenn die Vorhersage inkorrekt ist (die Ladung tatsächlich im Cache trifft), wird die spekulative Anfrage verworfen und es werden keine Daten in den Cache gefüllt, wodurch die Cache-Kohärenz ohne komplexe Rekonstruktionsmechanismen gewährleistet bleibt.

POPET: Der Prädiktor

Um Hermes zu ermöglichen, führen die Autoren POPET (Perceptron-based Off-chip load Prediction Technique) ein, einen leichtgewichtigen Prädiktor, der lernt, Off-Chip-Loads mithilfe mehrerer Programmfunktionen zu identifizieren.

• Algorithmus: POPET nutzt ein gehashtes Perzeptron-Lernmodell. Es aggregiert Gewichte aus verschiedenen Programmfunktionen, um eine binäre Klassifizierung (Off-Chip vs. On-Chip) vorzunehmen.
• Features: Der Prädiktor verwendet eine Kombination aus Features, darunter:
  • XOR aus Program Counter (PC) und Cache-Line-Offset.
  • XOR aus PC und Byte-Offset.
  • PC plus ein „First Access“-Hinweis (Verfolgung rezenter Page-Touches).
  • Cache-Line-Offset plus „First Access“.
  • Eine Historie der letzten vier Load-PCs.
• Training: POPET wird Online mittels der tatsächlichen Ergebnisse von Ladeanfragen (ob diese Off-Chip gingen) trainiert, um die Feature-Gewichte zu aktualisieren.
• Overhead: POPET benötigt lediglich 4 KB Speicher pro Kern (3,2 KB für Gewichtstabellen und 0,8 KB für Load-Queue-Metadaten), wodurch die unpraktikablen Metadaten-Overheads vorangegangener Ansätze zur Adressverfolgung vermieden werden.

Wichtige Beiträge

1. Identifizierung von Chancen: Das Paper hebt hervor, dass ein signifikanter Anteil der Off-Chip-Loads für aktuelle Prefetcher unvorhersehbar bleibt und dass ein wachsender Teil der Off-Chip-Latenz durch die On-Chip-Cache-Traversierung konsumiert wird.
2. Hermes-Technik: Die Einführung eines Mechanismus, der spekulativ Daten aus dem Hauptspeicher für vorhergesagte Off-Chip-Loads abruft, während gleichzeitig auf die Cache-Hierarchie zugegriffen wird, wodurch die On-Chip-Latenz aus dem kritischen Pfad eliminiert wird.
3. POPET-Prädiktor: Das Design eines neuen, geringen Overheads aufweisenden Perzeptron-basierten Prädiktors, der eine hohe Genauigkeit und Abdeckung für die Off-Chip-Load-Vorhersage erreicht, ohne große Metadatenstrukturen oder OS-Unterstützung zu benötigen.
4. Umfassende Evaluierung: Umfangreiche Evaluierung über 110 Single-Core- und 220 Multi-Core-Workloads (SPEC CPU2006/2017, PARSEC, Ligra, CVP) sowie verschiedene Systemkonfigurationen (variierende Kernzahlen, Speicherbandbreite und Prefetcher).
5. Open Source: Die Veröffentlichung des Hermes-Quellcodes, der Traces und der Skripte zur Reproduktion der Ergebnisse.

Ergebnisse

Die Evaluierung zeigt, dass Hermes konsistente Leistungssteigerungen gegenüber State-of-the-Art-Baselines bietet:

• Vorhersagegenauigkeit: POPET erreicht eine durchschnittliche Genauigkeit von 77,1 % und eine Abdeckung von 74,3 % für Off-Chip-Loads. Dies ist signifikant höher als beim bisher besten Genauigkeits-Prädiktor (HMP), der 47 % Genauigkeit und 22,3 % Abdeckung erreichte.
• Leistungsgewinne:
  • Single-Core: Die Kombination von Hermes mit dem Pythia-Prefetcher verbessert die Leistung im Durchschnitt um 5,4 % (bis zu 23,4 %) gegenüber Pythia allein.
  • Multi-Core (8-Core): Die Verbesserungen liegen im Durchschnitt bei 5,1 % (bis zu 25,7 %).
  • Bandbreitenbeschränkt: In bandbreitenbeschränkten Konfigurationen verbessert Hermes die Leistung um 6,2 % (bis zu 32,2 %) gegenüber Pythia und übertrifft Pythia in diesen Szenarien aufgrund des geringeren Speicherbandbreiten-Overheads.
• Effizienz: Hermes verursacht lediglich einen moderaten Anstieg der Main-Memory-Anfragen von 0,5 % für jedes 1 % Leistungszuwachs, während der Pythia-Prefetcher für denselben Gewinn einen Anstieg der Anfragen um 2 % verursacht.
• Robustheit: Hermes verbessert die Leistung konsistent in Kombination mit verschiedenen Hochleistungs-Prefetchern (Bingo, SPP, MLOP, SMS) und bleibt selbst bei pessimistischen Schätzungen der On-Chip-Interconnect-Latenz (bis zu 24 Zyklen) effektiv.
• Leistung und Speicher: Hermes verursacht lediglich 3,6 % dynamischen Leistungs-Overhead (im Vergleich zu 8,7 % bei Pythia) und benötigt nur 4 KB Speicher pro Kern im Vergleich zu 25,5 KB bei Pythia.

Bedeutung und Behauptungen

Die Autoren behaupten, dass Hermes einen bedeutenden Schritt nach vorn bei der Handhabung von Latenzen bei Speicherzugriffen darstellt, indem es den kritischen Pfad von Off-Chip-Loads grundlegend verändert. Im Gegensatz zu traditionellen Prefatchern, die versuchen, die Latenz zu verbergen, indem sie Daten vor deren Bedarf abrufen, reduziert Hermes die Latenz des Loads selbst, indem es die On-Chip-Hierarchie für vorhergesagte Misses umgeht.

Das Paper betont, dass die On-Chip-Caches mit zunehmender Größe und Komplexität immer größer werden und die Latenzstrafe für das Durchlaufen dieser Caches, um einen Miss zu bestätigen, weiter steigen wird. Hermes adressiert diesen spezifischen Trend, indem es die Entscheidung zum Abruf aus dem Hauptspeicher von der Latenz der On-Chip-Cache-Hierarchie entkoppelt. Die Autoren postulieren, dass die zentrale Beobachtung – dass Off-Chip-Loads mit hoher Genauigkeit mittels leichtgewichtiger Perzeptron-Lernverfahren vorhergesagt werden können – die Tür für zukünftige Speicher-Systemoptimierungen öffnet, die den Einfluss von Latenz-intensiven Anfragen weiter reduzieren.

Die Arbeit wird als praktische Lösung präsentiert, die keine OS-Unterstützung oder unpraktikable Metadaten-Speicherung erfordert, was sie zu einem lebensfähigen Kandidaten für die Implementierung in kommerziellen Prozessoren macht. Die Autoren kommen zu dem Schluss, dass Hermes eine „signifikante und konsistente Leistungsverbesserung“ über eine breite Palette von Workloads und Systemkonfigurationen hinweg bietet.