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

Riepilogo Tecnico: Hermes

Definizione del Problema

Le richieste di carico a latenza elevata che non trovano corrispondenza nella gerarchia di cache on-chip e accedono alla memoria principale off-chip rimangono un collo di bottiglia primario per i moderni processori out-of-order (OOO) ad alte prestazioni. Queste richieste spesso bloccano il processore interrompendo il completamento delle istruzioni (instruction retirement) dal Reorder Buffer (ROB).

Gli autori identificano due tendenze critiche nelle attuali progettazioni di processori che limitano le prestazioni nonostante le ottimizzazioni esistenti:

1. Copertura Limitata dei Prefetcher: Anche i prefetcher hardware all'avanguardia (ad esempio, Pythia) possono predire solo circa la metà delle richieste di carico off-chip attraverso una vasta gamma di carichi di lavoro. I restanti carichi imprevedibili continuano a causare significativi arresti (stalls).
2. Aumento della Latenza della Cache On-Chip: Man mano che le cache on-chip crescono in dimensione e complessità per ospitare footprint di dati più ampi, la latenza necessaria per attraversare la gerarchia della cache on-chip (L1, L2, LLC) per determinare che una richiesta è un miss è aumentata significativamente. Una frazione sostanziale della latenza totale di un carico off-chip è spesa semplicemente per accedere alla gerarchia on-chip per confermare il miss, piuttosto che attendere la risposta dalla memoria principale.

Metodologia

Il documento propone Hermes, una tecnica progettata per accelerare le richieste di carico off-chip rimuovendo la latenza di accesso alla cache on-chip dal loro percorso critico.

Meccanismo Core

Hermes opera sul principio del fetching off-chip speculativo:

1. Predizione: Per ogni richiesta di carico, un predittore determina se la richiesta è probabile che fallisca nella gerarchia on-chip e vada off-chip.
2. Fetch Speculativo: Se un carico è predetto come destinato all'off-chip, Hermes emette una richiesta speculativa (una "richiesta Hermes") direttamente al controller della memoria principale non appena l'indirizzo fisico viene generato.
3. Esecuzione Concorrente: Questa richiesta speculativa procede concorrentemente con la normale richiesta di carico, che attraversa ancora la standard gerarchia della cache on-chip.
4. Occultamento della Latenza: Se la predizione è corretta, il carico regolare eventualmente fallisce nella Last-Level Cache (LLC) e attende il completamento della richiesta speculativa in corso. Ciò occulta efficacemente la latenza di attraversamento della cache on-chip sotto l'ombra della latenza della memoria principale.
5. Coerenza: Se la predizione è errata (il carico trova effettivamente un hit nella cache), la richiesta speculativa viene scartata e nessun dato viene inserito nella cache, garantendo che la coerenza della cache sia mantenata senza meccanismi di recupero complessi.

POPET: Il Predittore

Per abilitare Hermes, gli autori introducono POPET (Perceptron-based Off-chip load Prediction Technique), un predittore leggero che impara a identificare i carichi off-chip utilizzando molteplici caratteristiche del programma.

• Algoritmo: POPET utilizza un modello di apprendimento a perceptron hashato. Aggrega i pesi da varie caratteristiche del programma per effettuare una classificazione binaria (off-chip vs on-chip).
• Caratteristiche: Il predittore utilizza una combinazione di caratteristiche che includono:
  • XOR del Program Counter (PC) e dell'offset della cache line.
  • XOR del PC e dell'offset dei byte.
  • PC più un indizio "first access" (tracciando i recenti tocchi di pagina).
  • Offset della cache line più "first access".
  • Una cronologia degli ultimi quattro PC di carico.
• Addestramento: POPET è addestrato online utilizzando l'esito effettivo delle richieste di carico (se sono andate off-chip) per aggiornare i pesi delle caratteristiche.
• Overhead: POPET richiede solo 4 KB di memoria per core (3,2 KB per le tabelle dei pesi e 0,8 KB per i metadati della Load Queue), evitando gli overhead di metadati impraticabili degli approcci precedenti basati sul tracciamento degli indirizzi.

Contributi Chiave

1. Identificazione delle Opportunità: Il documento evidenzia che una frazione significativa di carichi off-chip rimane imprevedibile per gli attuali prefetcher e che una quota crescente della latenza off-chip è consumata dal attraversamento della cache on-chip.
2. Tecnica Hermes: L'introduzione di un meccanismo che esegue il fetching speculativo di dati dalla memoria principale per i carichi off-chip predetti mentre accede concorrentemente alla gerarchia della cache, eliminando così la latenza on-chip dal percorso critico.
3. Predittore POPET: Il design di un nuovo predittore basato su perceptron a basso overhead che raggiunge un'alta accuratezza e copertura per la predizione di carichi off-chip senza richiedere grandi strutture di metadati o supporto dal sistema operativo.
4. Valutazione Esaustiva: Valutazione estesa su 110 carichi di lavoro single-core e 220 multi-core (SPEC CPU2006/2017, PARSEC, Ligra, CVP) e varie configurazioni di sistema (variando numero di core, larghezza di banda della memoria e prefetcher).
5. Open Source: Il rilascio del codice sorgente di Hermes, dei trace e degli script per riprodurre i risultati.

Risultati

La valutazione dimostra che Hermes fornisce miglioramenti costanti delle prestazioni rispetto ai baseline allo stato dell'arte:

• Accuratezza della Predizione: POPET raggiunge una media del 77,1% di accuratezza e del 74,3% di copertura per i carichi off-chip. Questo è significativamente superiore al precedente miglior predittore di accuratezza (HMP), che raggiungeva il 47% di accuratezza e il 22,3% di copertura.
• Guadagni di Prestazioni:
  • Single-Core: Hermes combinato con il prefetcher Pythia migliora le prestazioni in media del 5,4% (fino al 23,4%) rispetto a Pythia da solo.
  • Multi-Core (8-core): I miglioramenti sono mediamente del 5,1% (fino al 25,7%).
  • Bandwidth-Constrained: Nelle configurazioni con larghezza di banda limitata, Hermes migliora le prestazioni del 6,2% (fino al 32,2%) rispetto a Pythia, superando Pythia da solo in questi scenari grazie al minor overhead della larghezza di banda di memoria.
• Efficienza: Hermes comporta un modesto aumento dello 0,5% delle richieste alla memoria principale per ogni 1% di guadagno nelle prestazioni, mentre il prefetcher Pythia comporta un aumento del 2% delle richieste per lo stesso guadagno.
• Robustezza: Hermes migliora costantemente le prestazioni quando combinato con vari prefetcher ad alte prestazioni (Bingo, SPP, MLOP, SMS) e rimane efficace anche con stime pessimistiche della latenza dell'interconnessione on-chip (fino a 24 cicli).
• Potenza e Storage: Hermes aggiunge solo il 3,6% di overhead della potenza dinamica (rispetto all'8,7% di Pythia) e richiede solo 4 KB di storage per core, rispetto ai 25,5 KB di Pythia.

Significato e Rivendicazioni

Gli autori affermano che Hermes rappresenta un passo avanti significativo nel gestire gli accessi alla memoria a lunga latenza cambiando fondamentalmente il percorso critico dei carichi off-chip. A differenza dei prefetcher tradizionali che tentano di nascondere la latenza prelevando i dati prima che siano necessari, Hermes riduce la latenza del carico stesso bypassando la gerarchia on-chip per i miss predetti.

Il documento sottolinea che man mano che le cache on-chip continuano a crescere in dimensione e complessità, la penalità di latenza per attraversarle per confermare un miss aumenterà soltanto. Hermes affronta questa specifica tendenza disaccoppiando la decisione di prelevare dalla memoria principale dalla latenza della gerarchia della cache on-chip. Gli autori sostengono che l'osservazione chiave — ovvero che i carichi off-chip possono essere predetti con alta accuratezza utilizzando un apprendimento a perceptron leggero — apre la porta a future ottimizzazioni del sistema di memoria che riducano ulteriormente l'impatto delle richieste a lunga latenza.

Il lavoro è presentato come una soluzione pratica che non richiede supporto dal sistema operativo o uno storage di metadati impraticabile, rendendolo un candidato valido per l'adozione in processori commerciali. Gli autori concludono che Hermes fornisce un "miglioramento delle prestazioni significativo e costante" attraverso una vasta gamma di carichi di lavoro e configurazioni di sistema.