Ottimizzazioni dell'indirizzamento indiretto del ciclo interno della CPU moderna

Question

Da http://www.boost.org/community/implementation_variations.html

"...È improbabile che differenze di codifica come la modifica di una classe da membri virtuali a non virtuali o la rimozione di un livello di riferimento indiretto facciano una differenza misurabile a meno che non si trovino in un ciclo interno.E anche in un ciclo interno, le moderne CPU spesso eseguono tali sequenze di codici concorrenti nello stesso numero di cicli di clock!"

Sto cercando di capire la parte "anche nel circuito interno".Nello specifico, quali meccanismi implementano le CPU per eseguire i due codici (virtuale vs non virtuale o un ulteriore livello di indiretto) entro lo stesso numero di cicli di clock?Conosco il pipelining e la memorizzazione nella cache delle istruzioni, ma come è possibile eseguire una chiamata virtuale entro lo stesso numero di cicli di clock di una chiamata non virtuale?Come si "perde" il riferimento indiretto?

Answer 1

Memorizzazione nella cache (ad es. memorizzazione nella cache della destinazione del ramo), unità di carico parallele (parte della pipeline, ma anche cose come "hit under miss" che non bloccano la pipeline), e esecuzione fuori ordine probabilmente contribuiranno a trasformare a load-load-branch in qualcosa che è più vicino a un fisso branch.Anche il ripiegamento/eliminazione delle istruzioni (qual è il termine corretto per questo?) nella fase di decodifica o di previsione dei rami della pipeline può contribuire.

Tutto ciò si basa su molte cose diverse, però:quanti diversi target di filiale ci sono (ad es.quanti diversi sovraccarichi virtuali potresti attivare), quante cose esegui il loop (la cache di destinazione del ramo è "calda"?che ne dici di icache/dcache?), come sono disposte in memoria le tabelle virtuali o le tabelle indirette (sono compatibili con la cache o ogni nuovo caricamento di vtable potrebbe eliminare un vecchio vtable?), la cache viene invalidata ripetutamente a causa di ping-pong multicore, ecc...

(Disclaimer:Sicuramente non sono un esperto qui e gran parte della mia conoscenza deriva dallo studio dei processori incorporati in ordine, quindi parte di questa è estrapolazione.Se avete correzioni, sentitevi liberi di commentare!)

Il modo corretto per determinare se sarà un problema per un programma specifico è ovviamente quello di profilare.Se puoi, fallo con l'aiuto dei contatori hardware: possono dirti molto su cosa sta succedendo nelle varie fasi della pipeline.

---

Modificare:

Come sottolinea Hans Passant in un commento sopra Ottimizzazioni dell'indirizzamento indiretto del ciclo interno della CPU moderna, la chiave per far sì che queste due cose richiedano la stessa quantità di tempo è la capacità di "ritirare" effettivamente più di un'istruzione per ciclo.L'eliminazione delle istruzioni può aiutare in questo, ma disegno superscalare è probabilmente più importante (hit under miss è un esempio molto piccolo e specifico, le unità di carico completamente ridondanti potrebbero essere migliori).

Prendiamo una situazione ideale e supponiamo che un ramo diretto sia solo un'istruzione:

branch dest

...e un ramo indiretto è tre (forse puoi ottenerlo in due, ma è maggiore di uno):

load vtable from this
load dest from vtable
branch dest

Ipotizziamo una situazione assolutamente perfetta:*questo e l'intero vtable si trovano nella cache L1, la cache L1 è abbastanza veloce da supportare il costo ammortizzato di un ciclo per istruzione per i due carichi.(Si può anche supporre che il processore abbia riordinato i carichi e li abbia mescolati con istruzioni precedenti per consentire il tempo di completarli prima del ramo;non importa per questo esempio.) Si supponga inoltre che la cache di destinazione del ramo sia attiva e che non vi siano costi di svuotamento della pipeline per il ramo e che l'istruzione del ramo si riduca a un singolo ciclo (ammortizzato).

IL minimo teorico il tempo per il primo esempio è quindi 1 ciclo (ammortizzato).

Il minimo teorico per il secondo esempio, eliminazione di istruzioni assenti o unità funzionali ridondanti o qualcosa che consentirà di ritirare più di un'istruzione per ciclo, è di 3 cicli (ci sono 3 istruzioni)!

Il caricamento indiretto sarà sempre più lento, perché ci sono più istruzioni, finché non si raggiunge qualcosa come un design superscalare che consente di ritirare più di un'istruzione per ciclo.

Una volta ottenuto questo, il minimo per entrambi gli esempi diventa qualcosa tra 0 e 1 cicli, ancora una volta, a condizione che tutto il resto sia l'ideale.Probabilmente è necessario avere circostanze più ideali affinché il secondo esempio raggiunga effettivamente quel minimo teorico rispetto al primo esempio, ma ora è possibile.

In alcuni dei casi che ti interessano, probabilmente non raggiungerai quel minimo per nessuno dei due esempi.O la cache di destinazione del ramo sarà fredda, oppure vtable non sarà nella cache dei dati, oppure la macchina non sarà in grado di riordinare le istruzioni per sfruttare appieno le unità funzionali ridondanti.

...qui entra in gioco la profilazione, che in genere è comunque una buona idea.

Voi Potere in primo luogo, è sufficiente sposare una leggera paranoia riguardo al virtuale.Vedere L'articolo di Noel Llopis sulla progettazione orientata ai dati, l'eccellente Insidie ​​delle diapositive di programmazione orientata agli oggetti, E Le presentazioni scontrose ma educative di Mike Acton.Ora sei improvvisamente passato a schemi di cui è probabile che la CPU sia già soddisfatta, se stai elaborando molti dati.

Le funzionalità linguistiche di alto livello come il virtuale sono solitamente un compromesso tra espressività e controllo.Onestamente penso, però, che semplicemente aumentando la tua consapevolezza di ciò che il virtuale sta effettivamente facendo (non aver paura di leggere la vista di disassemblaggio di tanto in tanto e sicuramente sbirciando i manuali dell'architettura della tua CPU), tenderai a usarlo quando ha senso e non quando non lo è, e un profiler può coprire il resto se necessario.

Le affermazioni valide per tutti su "non usare il virtuale" o "è improbabile che l'uso virtuale faccia una differenza misurabile" mi rendono scontroso.La realtà è solitamente più complicata e o ti troverai in una situazione in cui ti preoccupi abbastanza da profilarla o evitarla, oppure ti troverai in quell'altro 95% di cui probabilmente non vale la pena preoccuparsi se non per il possibile contenuto educativo.

Answer 2

Il pipelining è la via principale.

Si potrebbe prendere 20 cicli di clock per caricare un'istruzione, decodificarlo, eseguirla di azioni e caricare riferimenti alla memoria indiretti. Ma a causa della pipleline il processore può essere esecuzione parti di altre 19 istruzioni allo stesso tempo in diversi stadi della pipeline dando un erogato complessivo di 1 istruzione ogni ciclo di clock indipendentemente dal tempo impiegato effettivamente per alimentare tale istruzione attraverso la conduttura.

Answer 3

Che cosa succede, penso è che il processore ha una cache di speciale che contiene le posizioni e gli obiettivi di rami e salti indiretti. Se si verifica un salto indiretta a $ 12345678, e l'ultima volta che è stato riscontrato è andato per affrontare $ 12348765, il processore può iniziare esecuzione speculativa delle istruzioni all'indirizzo $ 12348765, anche prima che si risolva l'indirizzo della succursale. In molti casi, all'interno del ciclo interno di una funzione, un particolare salto indiretto sarà sempre saltare lo stesso indirizzo per tutta la durata del ciclo. La cache indiretta-salto può quindi evitare ramificazione sanzioni.

Answer 4

CPU moderni utilizzano una tecnica di branch prediction adattiva che può prevedere molti salti indiretti, come si ottiene con un'implementazione vtable di funzioni virtuali. Vedere http://en.wikipedia.org/wiki/Branch_prediction#Prediction_of_indirect_jumps

Answer 5

Se la CPU ha già l'indirizzo di memoria nella cache, quindi l'esecuzione di un'istruzione di carico è banale, se questo.