Istruzioni di caricamento globalmente invisibili

Alcune delle istruzioni di caricamento possono non essere mai visibili a livello globale a causa del caricamento del carico di magazzino? Per dirla in altro modo, se un’istruzione di caricamento ottiene il suo valore dal buffer di archivio, non deve mai leggere dalla cache.
Come è generalmente affermato che un carico è globalmente visibile quando legge dalla cache L1D, quelli che non leggono dalla L1D dovrebbero renderlo globalmente invisibile.

Il concetto di visibilità globale per i carichi è complicato, perché un carico non modifica lo stato globale della memoria e altri thread non possono osservarlo direttamente .

Ma una volta che la polvere si è stabilizzata dopo un’esecuzione speculativa o fuori ordine, possiamo dire quale valore ha il carico se il thread lo memorizza da qualche parte, o rami basati su di esso. Questo comportamento osservabile del thread è ciò che è importante. (Oppure potremmo osservarlo con un debugger, e / o solo ragionare su quali valori potrebbe vedere un carico, se un esperimento è difficile.)


Almeno su CPU fortemente ordinate come x86, tutte le CPU possono essere d’accordo su un ordine totale di negozi che diventano globalmente visibili , aggiornando la singola memoria coerente + cache + memoria costante. Su x86, non è consentito il riordino del Store Store, questo TSO (ordine totale del negozio) concorda con l’ordine dei programmi di ciascun thread. (Cioè l’ordine totale è un interleaving di ordine di programma da ogni thread). SPARC TSO è anche questo fortemente ordinato.

(Per gli archivi che ignorano la cache, la visibilità globale si verifica quando vengono scaricati da buffer non coerenti di combinazione di scrittura in DRAM.)

Su un ISA debolmente ordinato, i thread A e B potrebbero non essere d’accordo sull’ordine dei negozi X e Y fatto dai thread C e D, anche se i thread di lettura utilizzano acquisisci-carichi per assicurarsi che i propri carichi non vengano riordinati. cioè potrebbe non esserci un ordine globale di negozi, per non parlare del fatto che non è lo stesso dell’ordine del programma.

IBM POWER ISA è così debole, così come il modello di memoria C ++ 11 (le due scritture atomiche in diverse posizioni in diversi thread saranno sempre viste nello stesso ordine da altri thread? ). Ciò sembrerebbe in conflitto con il modello dei negozi che diventano globalmente visibili quando eseguono il commit dal buffer del negozio alla cache L1d. Ma @BeeOnRope dice nei commenti che la cache è davvero coerente e consente di recuperare la coerenza sequenziale con ostacoli. Questi effetti di ordine multiplo si verificano solo a causa di SMT (più CPU logiche su una CPU fisica) che causano un riordinamento locale extra-strano.

(Un ansible meccanismo consentirebbe ad altri thread logici di eseguire lo snoop di archivi non speculativi dal buffer di archivio anche prima che si impegnino su L1d, mantenendo solo gli archivi non ancora ritirati privati ​​su un thread logico. Ciò potrebbe ridurre leggermente la latenza inter-thread. non può farlo perché spezzerebbe il robusto modello di memoria: Intel HT partiziona staticamente il buffer del negozio quando due thread sono attivi su un core, ma come i commenti di @BeeOnRope, un modello astratto di ciò che è permesso è un approccio migliore per ragionamento sulla correttezza: solo perché non si può pensare a un meccanismo HW per causare un riordino non significa che non possa accadere ) .

Gli ISA debolmente ordinati che non sono così deboli come POWER continuano a riordinare il buffer del negozio locale di ciascun core, se non vengono utilizzate barriere o depositi di rilascio. Su molte CPU esiste un ordine globale per tutti i negozi, ma non è un interleaving dell’ordine del programma. Le CPU OoO devono tenere traccia dell’ordine di memoria in modo che un singolo thread non abbia bisogno di barriere per vedere i propri negozi in ordine, ma consentire ai negozi di eseguire il commit dal buffer del negozio a L1d dall’ordine del programma potrebbe sicuramente migliorare il throughput (specialmente se ci sono più negozi in attesa della stessa linea, ma l’ordine del programma eliminerebbe la linea da una cache associativa tra ciascun negozio, ad esempio un modello di accesso all’istogramma cattivo.)


Facciamo un esperimento mentale su dove provengono i dati di caricamento

Quanto sopra è ancora solo sulla visibilità del negozio, non sui carichi. possiamo spiegare il valore visto da ogni carico come letto dalla memoria / cache globale ad un certo punto (ignorando le regole di ordinamento del carico)?

Se è così, allora tutti i risultati del carico possono essere spiegati mettendo tutti i negozi e carichi di tutti i thread in un ordine combinato, leggendo e scrivendo uno stato globale coerente di memoria.

Si scopre che no, non possiamo, il buffer del negozio spezza questo : l’inoltro parziale da magazzino a carico ci dà un controesempio (su x86 per esempio). Un archivio ristretto seguito da un ampio carico può unire i dati dal buffer del negozio con i dati della cache L1d prima che l’archivio diventi visibile a livello globale. Realmente le CPU x86 lo fanno e abbiamo i veri esperimenti per provarlo.

Se si considera solo l’inoltro completo dello store, in cui il carico preleva i suoi dati da un solo archivio nel buffer del negozio, si potrebbe obiettare che il carico è ritardato dal buffer del negozio. vale a dire che il carico appare nell’ordine di carico totale globale subito dopo il negozio che rende questo valore globalmente visibile.

(Questo ordine di caricamento totale globale non è un tentativo di creare un modello di ordine di memoria alternativo, non ha modo di descrivere le regole di ordinamento del carico effettive di x86.)


L’inoltro parziale dello store espone il fatto che i dati di caricamento non provengono sempre dal dominio della cache coerente globale.

Se un negozio da un altro core modifica i byte circostanti, un carico a livello atomico potrebbe leggere un valore che non è mai esistito, e non esisterà mai, nello stato globale coerente.

Vedere la mia risposta su Can x86 riordinare un negozio ristretto con un carico più ampio che lo contiene completamente? e la risposta di Alex per la prova sperimentale che può avvenire un tale riordino, rendendo invalido lo schema di blocco proposto in tale domanda. Un negozio e poi un ricarico dallo stesso indirizzo non è una barriera di memoria StoreLoad .

Alcune persone (ad esempio Linus Torvalds) descrivono ciò dicendo che il buffer del negozio non è coerente . (Linus stava rispondendo a qualcun altro che aveva inventato autonomamente la stessa idea di blocco non valida).

Altre domande e risposte riguardanti il ​​buffer e la coerenza del negozio: come impostare bit di un vettore bit in modo efficiente in parallelo? . Puoi fare alcuni OR non atomici per impostare i bit, quindi tornare indietro e controllare gli aggiornamenti persi a causa di conflitti con altri thread. Ma hai bisogno di una barriera StoreLoad (es. Un lock or x86 lock or ) per assicurarti di non vedere i tuoi negozi quando ricarichi.


Un carico diventa globalmente visibile quando legge i suoi dati. Normalmente da L1d, ma il buffer di archivio o MMIO o memoria non memorizzabile sono altre possibili fonti.

Questa definizione concorda con i manuali x86 che dicono che i carichi non sono riordinati con altri carichi. cioè caricano (in ordine di programma) dalla vista della memoria del core locale.

Il carico stesso può diventare globalmente visibile indipendentemente dal fatto che qualsiasi altro thread possa mai caricare quel valore da quell’indirizzo.

Non sono sicuro che la visibilità globale sia un concetto interessante per le operazioni di caricamento ( richiesta di chiarimenti), ma se si vuole usarla per risolvere un argomento semantico, allora si dovrà dipendere dalle definizioni. Se, ad esempio, la definizione di visibilità globale per i carichi è nel momento in cui carica un valore dalla cache L1 e non ammette la possibilità di inoltro del negozio, la risposta è “non diventa mai visibile” o “il tuo la definizione è errata “.

In pratica, tuttavia, si può pensare ai carichi che ricevono il loro valore da un particolare negozio nel sistema. In questo modo, possiamo parlare di una visibilità globale per i negozi (e forse un ordine parziale o totale su questi negozi) e quindi discutere quali carichi possono ricevere il loro valore da quali negozi. In questo modo, la serie di valori ricevuti da vari carichi li colloca in un tipo di tempo globale (sebbene forse solo parzialmente ordinato se i negozi sono ordinati solo parzialmente).

In questo modello, i carichi di solito ricevono il loro valore da qualche negozio visibile a livello globale, ma nel caso particolare di inoltro del negozio, il carico riceve il suo valore da un negozio che non è ancora visibile a livello globale ! In pratica, il negozio (o un negozio successivo che lo sovrascrive) diventerà (a) visibile a livello globale ad un certo punto, poiché viene scritto su L1 dal buffer del negozio o (b) viene scartato a causa di qualche evento, come un errore di speculazione, interruzione, eccezione, ecc. Nel caso in cui il negozio venga scartato, non dobbiamo preoccuparci: un carico prende il suo valore da un negozio precedente nell’ordine di programma, quindi quando un negozio viene scartato, tutto anche le istruzioni successive in ordine di programma vengono scartate, incluso il carico.

Nel caso in cui lo store associato alla fine diventi visibile a livello globale, si ha un interessante effetto del tipo time-travel: il carico sulla CPU locale ha potenzialmente visto lo store molto prima rispetto ad altri processori, e in particolare forse lo vede fuori servizio rispetto ad altri negozi sul sistema. Questo effetto è uno dei motivi per cui i sistemi con l’inoltro del magazzino di solito hanno associato il riordino – ad esempio, nel modello di memoria x86 forte, le riordinazioni consentite sono esattamente quelle causate dal buffering del negozio e dall’inoltro del negozio.

Permettetemi di espandere un po ‘la domanda e discutere l’aspetto della correttezza nell’implementare l’inoltro del carico di magazzino. (La seconda parte della risposta di Peter risponde direttamente alla domanda che penso).

L’inoltro del carico di magazzino modifica la latenza del carico, non la sua visibilità. A meno che non sia stato svuotato a causa di qualche errore, il negozio alla fine diventerà comunque visibile a livello globale. Senza l’inoltro del carico di magazzino, il carico deve attendere il ritiro di tutti i negozi in conflitto. Quindi il carico può recuperare i dati normalmente.

(La definizione esatta di un archivio in conflitto dipende dal modello di ordinamento della memoria di ISA. In x86, supponendo il tipo di memoria WB, che consente l’inoltro del carico di magazzino, qualsiasi archivio che si trova prima nell’ordine di programma e la cui posizione di memoria fisica di destinazione si sovrappone a quella del carico è un negozio in conflitto).

Anche se esiste un archivio concorrente in conflitto da un altro agente nel sistema, questo potrebbe effettivamente cambiare il valore caricato perché l’archivio esterno può avere effetto dopo l’archivio locale ma prima del carico locale. In genere, il buffer di archiviazione non si trova nel dominio di coerenza e pertanto l’inoltro del carico di memoria può ridurre la probabilità che qualcosa di simile accada. Ciò dipende dalle limitazioni dell’implementazione di forwarding del carico di magazzino; di solito non vi è alcuna garanzia che l’inoltro avverrà per un particolare carico e operazioni di magazzino.

L’inoltro del carico di magazzino può anche comportare ordini di memoria globali che non sarebbero stati possibili senza di esso. Ad esempio, nel modello forte di x86, è consentito il riordino del carico di magazzino e, insieme all’inoltro del carico di magazzino, può consentire a ciascun agente del sistema di visualizzare tutte le operazioni di memoria in ordini diversi.

In generale, si consideri un sistema di memoria condivisa con esattamente due agenti. Sia S1 (A, B) l’insieme di possibili ordini di memoria globale per le sequenze A e B con l’inoltro del carico di magazzino e sia S2 (A, B) l’insieme di possibili ordini di memoria globale per le sequenze A e B senza memorizzazione -loading di spedizione. Sia S1 (A, B) che S2 (A, B) sono sottoinsiemi dell’insieme di tutti gli ordini di memoria globali legali S3 (A, B). L’inoltro del carico di magazzino può rendere S1 (A, B) non un sottoinsieme di S2 (A, B). Ciò significa che se S2 (A, B) = S3 (A, B), l’inoltro del carico di magazzino sarebbe un ottimizzazione illegale.

L’inoltro del carico di magazzino può modificare la probabilità che ogni ordine di memoria globale si verifichi perché riduce la latenza del carico.