Blog

Memcpy veloce, un design di sistema

Memcpy veloce un design di sistema | itkovian

Quando lavoravo in Google, la profilazione a livello di flotta ha rivelato che il 25-35% di tutto il tempo della CPU veniva speso solo spostando i byte: memcpy, strcmp, copia tra i buffer dell’utente e del kernel nella rete e I/O del disco, copia nascosta su- scrivere in soft page fault, checksum, comprimere, decifrare, assemblare/disassemblare pacchetti e pagine HTML, ecc. Se lo spostamento dei dati fosse più veloce, si potrebbe fare più lavoro sugli stessi processori.

Esperimento mentale

Osserviamo qui un Gedankenexperiment: spostare 16 byte per ciclo, affrontando non solo il movimento della CPU, ma anche il design del sistema circostante. Proporremo cinque nuove istruzioni generali che sono fondamentali per raggiungere questo obiettivo.

Assumiamo una macchina di caricamento/archiviazione a quattro vie con processore multi-core di base con registri di numeri interi/indirizzi a 64 bit Rx, registri di dati a 128 bit (16 byte) Vx e una D-cache L1 che può eseguire due operazioni per ciclo, ogni lettura o scrittura di una parola di memoria allineata di 16 byte. Un design inferiore non può spostare 16 byte per ciclo. Questo design di base può essere mappato facilmente su molti chip attuali.

Non riesce

Le proposte per eseguire la copia nella DRAM falliscono qui perché è improbabile che i campi sorgente e dati siano allineati ed è improbabile che si trovino nello stesso chip di memoria. Falliscono anche se l’origine o la destinazione desiderata si trova da qualche parte nella gerarchia della cache, non nella DRAM. Le proposte per l’utilizzo di un motore DMA specializzato per il movimento falliscono per spostamenti brevi se quel motore ha una configurazione non banale e ha un’elaborazione di interrupt al completamento, e fallisce per spostamenti lunghi se più processori devono eliminare un blocco software per utilizzare il singolo motore, causando attende quando c’è contesa (poiché ci sarà un utilizzo del 25-35% per core).

La funzione standard memcpy(dest, src, len) non conosce l’uso successivo del campo dest, quindi non può fare di meglio che lasciarlo ovunque si trovi nella gerarchia della cache. Evitiamo quindi carichi e negozi non temporali, che presuppongono il mancato utilizzo di dest. (L’inquinamento della cache è affrontato in una sezione di seguito.)

Supporto alla cache

Per spostare 16 byte per ciclo, la D-cache L1 deve eseguire un caricamento allineato di 16 byte e un archivio di 16 byte per ciclo, mentre contemporaneamente esegue il riempimento e il writeback della riga della cache alla stessa velocità, circa 50 GB/sec per un 3,2 GHz nucleo del processore. I livelli inferiori di cache devono supportare più flussi di questo tipo, fino alla memoria principale.

Istruzione alla base

Per spostare 16 byte per ciclo sono necessarie almeno quattro istruzioni per ciclo: load, store, test-done e branch. In realtà c’è molto altro da fare, ma un modesto srotolamento del loop può far rientrare il resto in quattro istruzioni per ciclo, come vediamo di seguito.

Movimenti brevi

Suddividiamo la discussione in tre parti: spostamenti brevi ~10 byte, medi ~100 byte e lunghi ~1000+ byte. Gli spostamenti brevi sono comuni nell’assemblaggio/disassemblaggio di intestazioni di pacchetti e tag HTML, nello spostamento di singoli caratteri UTF-8 da 1 a 4 byte e nello spostamento di stringhe di byte di piccole dimensioni durante la compressione/decompressione. Le mosse medie sono comuni nella giustapposizione di paragrafi di testo o nella copia di blocchi di controllo di dimensioni modeste. Gli spostamenti lunghi sono comuni nel riempire la parte di payload dei pacchetti e nei trasferimenti di buffer di rete/disco.

Il codice di mossa breve standard verifica che len sia piccolo, diciamo < 16, e poi lo fa

while (len-- > 0) {*dest++ = *src++;}

compilando in qualcosa di simile

compare, sub, branch, loadbyte, add, storebyte, add

prendendo almeno due cicli per byte, o 32 cicli per 16 byte, lontano dal nostro obiettivo di 1 ciclo.

Introduciamo due nuove istruzioni per gestire rapidamente il caso di movimento breve. Chip che possono già eseguire caricamenti e archivi non allineati da 1/2/4/8/16 byte Già avere tutti i datapath per questi; necessitano solo di piccole modifiche alla logica di controllo.

Carica parziale
ldp  V1, R2, R3

Load e zero estendono 0..15 byte da 0(R2) a V1, lunghezza specificata da R3<3:0>. La lunghezza 0 non carica e non accetta trap.

Negozio Parziale
stp  V1, R2, R3

Memorizza 0..15 byte da V1 a 0(R2), lunghezza specificata da R3<3:0>. La lunghezza 0 non memorizza e non accetta trap.

I chip che eseguono il caricamento/memorizzazione non allineati hanno già la logica per decidere se accedere a una o due parole della cache, hanno la logica per spostare due parole di memoria per allineare i byte con V1 e la logica per estendere zero i caricamenti di 1/2/4/8 byte. Le nuove istruzioni necessitano solo della logica di controllo per rilevare lo spostamento di dati pari a zero e della logica di controllo per l’estensione zero di carichi da 0 a 15 byte.

Usando queste istruzioni, memcpy con dest, src e len già nei registri diventa

memcpy:
    ldp V1, 0(src), len
    stp V1, 0(dest), len
    andnot len, 15
    bnz medium
    return

Le prime quattro istruzioni possono essere emesse in un singolo ciclo, spostando da 0 a 15 byte senza rami, vicino al nostro obiettivo. Se questa è la lunghezza totale, il ritorno richiede un secondo ciclo. (Questo è il tempismo migliore; errori di cache, previsioni errate dei rami e accessi alla memoria non allineati possono rallentare le cose in modo modesto.)

Mosse Medie

Dopo ldp/stp per 0..15 byte, la lunghezza rimanente è un multiplo diverso da zero di 16 byte. Per coprire gli spostamenti medi, incrementiamo src e dst per tenere conto della lunghezza variabile ldp/stp e quindi spostiamo in modo condizionale 16, 32, 64 e 128 byte.

medium:
    and  Rx, len, 15    ; length (mod 16)
    add  src, Rx        ; increment past the 0..15 bytes
    add  dest, Rx       ; increment past the 0..15 bytes

Sposta in modo condizionale 16 byte con il normale load/store a 16 byte e aggiorna src/dest; 2 cicli per 16 byte

    and  Rx, len, 0x10  ; does length have a 16 bit?
    bz   1f
    ld                  ; yes, move 16 bytes
    st                  ; yes, move 16 bytes
    add  src, src, 16   ; increment past the 16 bytes
    add  dest, dest, 16 ; increment past the 16 bytes
1:
    and  Rx, len, 0x20  ; does length have a 32 bit?
    ...

Lo stesso schema si ripete per i bit len ​​0x20/0x40/0x80 spostando 32/64/128 byte tramite più coppie ld/st tra bz e add. Questi pezzi raggiungono tutti i 16 byte per ciclo nel migliore dei casi.

Il codice breve più medio copre tutte le lunghezze fino a 255 byte. Concludiamo testando per len > 255

    andnot len, 255
    bnz long
    return


Movimenti lunghi

Se len è più di 255 byte, finiamo qui con un multiplo diverso da zero di 256 in len<63:8>. Per velocità, successivamente vogliamo un ciclo che esegua solo caricamenti allineati a 16 byte e archivi allineati a 16 byte e srotoliamo quel ciclo in modo modesto per adattare le quattro istruzioni generali attorno alle coppie caricamento/archiviazione. Il ciclo ha una parola src caricata in precedenza, carica una nuova parola src allineata ogni ciclo, sposta due parole per allinearsi con dest e memorizza la parola dest.

1685100695 885 Memcpy veloce un design di sistema | itkovian

Introduciamo una nuova istruzione di spostamento a doppia larghezza di 32 byte per gestire rapidamente l’allineamento. Questa è la stessa logica di spostamento già presente nel percorso di carico non allineato di un chip.

Doppio spostamento di byte
shrbd  V1, V2, R3

Sposta la coppia di registri V2V3 a destra di 0..15 byte, come specificato da R3<3:0>. Metti il ​​risultato in V1.

Lo spostamento lungo complessivo utilizza ldp/stp per far avanzare dest al successivo multiplo più alto di 16, sposta blocchi di 64 byte utilizzando load/shift/store più spazio per gli incrementi dei due puntatori, test e branch per iterazione, inserendosi in 4 cicli per 64 byte. 16 byte per ciclo esattamente!

Dopo aver spostato multipli di 64 byte negli indirizzi di destinazione allineati, rimarrà una coda di 0..63 byte da spostare. Usa il modello medio e poi quello corto per finire. Questo progetto complessivo si avvicina molto allo spostamento di 16 byte per ciclo su l’intera gamma di memcpy breve, medio e lungo. Ma non abbiamo ancora finito…

Precaricamento

Con la cache L3 a circa 40 cicli di distanza dalla CPU e la memoria principale a 200-250 cicli di distanza, il precaricamento diventa importante per gli spostamenti lunghi. Non possiamo fare molto per ottenere rapidamente i byte iniziali, ma possiamo precaricare i byte successivi.

Lo spostamento di 1 KB a 16 byte/ciclo richiede 64 cicli. Questo è un tempo sufficiente durante lo spostamento di 1 KB per precaricare il successivo 1 KB dalla cache L3. Allo stesso modo, lo spostamento di 4 KB richiede circa 256 cicli, tempo sufficiente per precaricare i successivi 4 KB dalla memoria principale. Ma i computer di oggi precaricano solo singole righe di cache, spesso 64 byte ciascuna.

Introduciamo due istruzioni di prefetch.

Prelettura_lettura, Prelettura_scrittura

PRE_R  R2, R3

Prelettura dei dati per la lettura da 0(R2), lunghezza min(R3, 4096).

PRE_W  R2, R3

Prelettura dei dati per la scrittura da 0(R2), lunghezza min(R3, 4096).

Il limite superiore di 4 KB sulla lunghezza è importante. Impedisce di descrivere un prefetch di megabyte e garantisce che il prefetch non necessiti di più di due ricerche TLB per pagine da 4 KB o più grandi. È abbastanza grande da dare al codice il tempo di avviare i precaricamenti successivi secondo necessità, calibrando il precaricamento in base all’utilizzo dei dati.

L’implementazione desiderata di PRE_W esegue l’allocazione di linee di cache esclusive ma differisce riempiendoli con qualsiasi dato, eccetto possibilmente la prima e l’ultima riga della cache parziali. Se tale riga della cache viene completamente sovrascritta, la lettura non viene mai eseguita. Senza questa ottimizzazione, la larghezza di banda della memoria aumenta del 50%

Il lungo ciclo di spostamento può essere costruito come una coppia di cicli nidificati, quello interno emette preletture di lettura e scrittura e quindi sposta 4 KB alla volta.

Accesso alla riga DRAM

Le DRAM copiano internamente i bit da condensatori molto deboli in un buffer di riga e quindi servono i byte a un chip della CPU da lì. I buffer di riga sono in genere 1 KB. L’accesso ai byte da un buffer di riga già pieno è tre volte più veloce rispetto all’avvio da zero, circa 15 ns contro 45 ns. Questo non è cambiato molto in 40 anni.

Se un’implementazione riceve un indirizzo di prelettura e lunghezza alla logica del controller di memoria all’inizio di un lungo prefetch, il controller di memoria dispone di informazioni sufficienti per ottimizzare i recuperi del buffer di riga, anche in presenza di richieste di memoria concorrenti.

Inquinamento della cache

Lo spostamento rapido di molti kilobyte di dati attraverso le cache normalmente ha lo svantaggio di eliminare altri dati appartenenti ad altri programmi. L’isolamento della cache rimane un problema nella parte del data center del nostro settore.

È possibile prevenire l’inquinamento della cache assegnando alcuni bit di « proprietà » a ciascuna riga della cache recuperata e utilizzandola per tenere traccia di quante righe ciascuna CPU/ecc. possiede nella cache. Per una cache L1 in un chip con hyperthread, ogni CPU logica è un proprietario. In una cache condivisa tra molti core, ogni core fisico potrebbe essere un proprietario. Per evitare che il codice del kernel inquini i dati dell’utente durante gli spostamenti di massa del disco e della rete, il « kernel » potrebbe essere un proprietario a sé stante.

Dare ai proprietari a limite su quante righe di cache possono utilizzare consente a un’implementazione di cambiare le strategie di allocazione per i proprietari che hanno superato il loro limite, sostituendo preferenzialmente il loro Proprio righe o posizionando i loro nuovi riempimenti vicino alla fine di sostituzione di un elenco di sostituzione pseudo-LRU. Un limite libero è abbastanza buono da evitare di far morire di fame altri utenti.

Questo approccio è superiore a fisso modo di partizionamento di una cache associativa a N vie perché non lascia molte risorse bloccate.

Un approccio alternativo che non richiede ulteriori bit di proprietà consiste nel tenere traccia del tasso di riempimento di ciascun proprietario e essenzialmente limitare la velocità di ciascun proprietario. Quelli che superano il loro limite ottengono la strategia di allocazione alternativa.

Riepilogo

La nostra semplice ricerca « Sposta 16 byte per ciclo » per memcpy e simili rivela una serie sfumata di set di istruzioni e problemi di microarchitettura:

  • Fallimento: motori Copy-in-RAM e DMA
  • Sia il lato CPU che il lato memoria delle cache sono importanti
  • Load/Store Partial e Double-width-shift aiutano in modo significativo
  • Il precaricamento più lungo è importante
  • Consentire al controller di memoria di conoscere il prefetch lunghezza può essere 3 volte più veloce
  • Il controllo dell’inquinamento della cache è importante

Suggeriamo alcune nuove istruzioni e un po’ di gestione della cache che possono aiutare a raggiungere l’obiettivo.

Disclaimer: Questi post sono scritti da singoli contributori per condividere i propri pensieri sul blog Computer Architecture Today a beneficio della comunità. Qualsiasi punto di vista o opinione rappresentata in questo blog è personale, appartiene esclusivamente all’autore del blog e non rappresenta quelli di ACM SIGARCH o della sua organizzazione madre, ACM.

Hi, I’m Samuel