Perché XCHG reg, reg 3 istruzioni micro-op sulle moderne architetture Intel?

Sto eseguendo la micro-ottimizzazione su una parte critica dal punto di vista delle prestazioni del mio codice e ho trovato la sequenza di istruzioni (nella syntax AT & T):

add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx 

Ho pensato che finalmente avevo un caso d’uso per xchg che mi permettesse di radere un’istruzione e scrivere:

 add %rbx, %rax xchg %rax, %rdx 

Tuttavia, con il mio dimay ho trovato dalle tabelle di istruzioni di Agner Fog, che xchg è xchg 3 micro-op con una latenza di 2 cicli su Sandy Bridge, Ivy Bridge, Broadwell, Haswell e persino Skylake. 3 intere micro-operazioni e 2 cicli di latenza! Le 3 micro-operazioni eliminano la mia cadenza 4-1-1-1 e la latenza di 2 cicli lo rende peggiore dell’originale nel migliore dei casi poiché le ultime 2 istruzioni dell’originale potrebbero essere eseguite in parallelo.

Ora … ho capito che la CPU potrebbe rompere le istruzioni in micro-op che sono equivalenti a:

 mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx 

dove tmp è un registro interno anonimo e suppongo che le ultime due micro-op possano essere eseguite in parallelo, quindi la latenza è di 2 cicli.

Dato che la registrazione del registro si verifica su queste micro-architetture, tuttavia, non ha senso per me che ciò avvenga in questo modo. Perché il rinominatore del registro non dovrebbe sostituire le etichette? In teoria, questo avrebbe una latenza di solo 1 ciclo (possibilmente 0?) E potrebbe essere rappresentato come una singola micro-operazione, quindi sarebbe molto più economico.

Supportare xchg efficiente non è banale, e presumibilmente non vale la complessità aggiuntiva che richiederebbe in varie parti della CPU. La microarchitettura di una vera CPU è molto più complicata del modello mentale che è ansible utilizzare ottimizzando il software per questo. Ad esempio, l’esecuzione speculativa rende tutto più complicato, perché deve essere in grado di tornare al punto in cui si è verificata un’eccezione.

Rendere efficiente fxch era importante per le prestazioni di x87 perché la natura dello stack di x87 lo rende difficile (o alternative come fld st(2) ). Il codice FP generato dal compilatore (per gli obiettivi senza supporto SSE) usa fxch una quantità significativa di fxch . Sembra che il fxch veloce fxch stato fatto perché era importante, non perché è facile. Intel Haswell ha persino abbandonato il supporto per fxch single- fxch . È ancora a latenza zero, ma decodifica su 2 uops su HSW e versioni successive (da 1 a P5 e PPro a IvyBridge).

xchg è solitamente facile da evitare. Nella maggior parte dei casi, puoi semplicemente srotolare un ciclo, quindi è ok che lo stesso valore sia ora in un registro diverso. ad es. Fibonacci con add rax, rdx / add rdx, rax invece di add rax, rdx / xchg rax, rdx . Generalmente i compilatori non usano xchg reg,reg e di solito asm scritto a mano no. (Questo problema di pollo / uovo è piuttosto simile al fatto che il loop è lento ( perché l’istruzione di loop è lenta? Non è ansible che Intel l’abbia implementata in modo efficiente? ). loop sarebbe stato molto utile per i cicli adc su Core2 / Nehalem dove un adc + dec/jnz ciclo dec/jnz causa bancarelle a bandierine parziali.)

Poiché xchg è ancora lento nelle precedenti CPU, i compilatori non inizieranno a usarlo con -mtune=generic per diversi anni. A differenza di fxch o mov -elimination, una modifica del design per supportare xchg veloce non aiuterebbe la CPU a eseguire più velocemente il codice più esistente , e consentirebbe solo guadagni di prestazioni rispetto al progetto corrente in rari casi in cui è in realtà un’ottimizzazione dello spioncino.


I registri interi sono complicati da elementi di registro parziale, a differenza di x87

Ci sono 4 dimensioni di operando di xchg , 3 delle quali usano lo stesso codice operativo con i prefissi REX o operando-size. ( xchg r8,r8 è un opcode separato , quindi è probabilmente più semplice far decodificare i decodificatori in modo diverso dagli altri). I decoder devono già riconoscere xchg con un operando di memoria come speciale, a causa del prefisso di lock implicito, ma è probabilmente meno la complessità del decodificatore (transistor-count + power) se il reg-reg si decodifica tutti allo stesso numero di uops per diversi dimensioni dell’operando.

Rendere decodificabili alcuni moduli r,r in un singolo Uop sarebbe ancora più complesso, perché le istruzioni single-uop devono essere gestite dai decodificatori “semplici” e dal decodificatore complesso. Quindi dovrebbero essere tutti in grado di analizzare xchg e decidere se si trattava di un singolo modulo uop o multi-uop.


Le CPU AMD e Intel si comportano in modo simile dal punto di vista del programmatore, ma ci sono molti segnali che l’implementazione interna è molto diversa. Ad esempio, l’ eliminazione di Intel process funziona solo una parte del tempo, limitata da qualche tipo di risorse di microarchitettura , ma le CPU AMD che eseguono l’eliminazione del movimento lo fanno il 100% delle volte (ad es. Bulldozer per la corsia bassa di reg di vettori).

Vedi il manuale di ottimizzazione di Intel, Esempio 3-25. Sequenza di riordino per migliorare l’efficacia delle istruzioni MOV a latenza zero , dove discutono di sovrascrivere subito il risultato di zero-latenza-movzx per liberare prima la risorsa interna. (Ho provato gli esempi su Haswell e Skylake, e ho scoperto che l’eliminazione del movimento in effetti ha funzionato molto più del tempo quando lo facevo, ma che in realtà era leggermente più lento nei cicli totali, invece che più veloce. il vantaggio su IvyBridge, che probabilmente ha i colli di bottiglia sulle sue 3 porte ALU, ma HSW / SKL ha solo il collo di bottiglia sui conflitti di risorse nelle catene di dep e non sembra essere disturbato dalla necessità di una porta ALU per più delle istruzioni movzx .)

Non so esattamente cosa debba essere tracciato in una tabella di dimensioni limitate (?) Per l’eliminazione del movimento. Probabilmente è legato alla necessità di liberare le voci dei file di registro il più presto ansible quando non sono più necessarie, perché i limiti delle dimensioni dei file del registro fisico piuttosto che della dimensione ROB possono essere il collo di bottiglia per le dimensioni della finestra fuori ordine . Scambiare gli indici potrebbe renderlo più difficile.

xor -zeroing viene eliminato il 100% delle volte con la famiglia Intel Sandybridge ; si presume che ciò funzioni rinominando un registro di zero fisico e questo registro non deve mai essere liberato.

Se xchg usasse lo stesso meccanismo che fa l’eliminazione dei movimenti, potrebbe anche funzionare solo una volta. Dovrebbe essere decodificato su un numero sufficiente di uops da utilizzare nei casi in cui non viene gestito in caso di rinomina . (Oppure la fase di rilascio / rinominazione dovrebbe inserire dei bui extra quando un xchg impiega più di 1 uop, come succede quando si un-laminano gli uops micro-fusi con modalità di indirizzamento indicizzate che non possono rimanere micro-fuse nel ROB , o quando si inseriscono gli uop di unione per flag o registri parziali high-8, ma questa è una complicazione significativa che varrebbe la pena fare solo se xchg fosse xchg comune e importante.)

Si noti che xchg r32,r32 deve estendere a zero entrambi i risultati a 64 bit, quindi non può essere un semplice scambio di voci RAT (Register Alias ​​Table). Sarebbe più come troncare entrambi i registri sul posto. E nota che le CPU Intel non eliminano mai la mov same,same . Ha già bisogno di supportare mov r32,r32 e movzx r32, r8 senza porta di esecuzione, quindi presumibilmente ha alcuni bit che indicano che rax = al o qualcosa del genere. (E sì, Intel HSW / SKL lo fa , non solo Ivybridge, nonostante ciò che dice la guida del microarch di Agner.)

Sappiamo che P6 e SnB avevano bit superiori a zero come questo, perché xor eax,eax prima di setz al evita uno stallo di registro parziale durante la lettura di eax. HSW / SKL non rinominano mai al separatamente, in primo luogo, solo ah . Potrebbe non essere una coincidenza che la ridenominazione a registro parziale (diversa da AH) sembra essere stata abbandonata nello stesso uarch che ha introdotto l’eliminazione del movimento (Ivybridge). Tuttavia, impostare quel bit per 2 registri contemporaneamente sarebbe un caso speciale che richiedeva un supporto speciale.

xchg r64,r64 potrebbe forse semplicemente scambiare le voci RAT, ma la decodifica che differisce dal caso r32 è un’altra complicazione. Potrebbe anche essere necessario triggersre l’unione di registro parziale per entrambi gli input, ma add r64,r64 deve farlo.

Si noti inoltre che un Intel uop (diverso da fxch ) produce sempre un solo risultato di registro (più flag). Non toccare i flag non “libera” uno slot di output; Ad esempio mulx r64,r64,r64 richiede ancora 2 uop per produrre 2 output interi su HSW / SKL, anche se tutto il “lavoro” viene eseguito nell’unità moltiplicatrice sulla porta 1, come con mul r64 che produce un risultato di flag .)

Anche se è semplice come “scambiare le voci RAT”, la creazione di un RAT che supporti la scrittura di più di una voce per uop è una complicazione . Cosa fare quando si rinomina 4 xchg uops in un singolo gruppo di numeri? Mi sembra che renderebbe la logica molto più complicata. Ricorda che questo deve essere costruito da porte logiche / transistor. Anche se dici “gestisci quel caso speciale con una trap al microcodice”, devi build l’intera pipeline per supportare la possibilità che quella fase della pipeline possa prendere quel tipo di eccezione.

Single-uop fxch richiede il supporto per lo scambio di voci RAT (o qualche altro meccanismo) nel FP RAT (fRAT), ma è un blocco separato di hardware dal RAT intero (iRAT). Tralasciando questa complicazione nell’iRAT sembra ragionevole anche se lo si ha nel fRAT (pre-Haswell).

Problema / rinominare la complessità è sicuramente un problema per il consumo di energia, però. Notare che Skylake ha ampliato gran parte del front-end (decodifica legacy e recupero della cache di uop), e la pensione, ma ha mantenuto il limite di 4 punti / ridenominazione. SKL ha anche aggiunto unità di esecuzione replicate su più porte nel back-end, quindi la larghezza di banda è un collo di bottiglia ancora più del tempo, specialmente nel codice con un mix di carichi, negozi e ALU.

Il RAT (o il file di registro intero, IDK) può anche avere porte di lettura limitate, dal momento che sembrano esserci alcuni colli di bottiglia front-end nell’emettere / ridenominare molti UOP a 3 input come add rax, [rcx+rdx] . Ho postato alcuni microbenchmarks ( questo e il post di follow-up) che mostrano che Skylake è più veloce di Haswell durante la lettura di molti registri, ad esempio con micro-fusione di modalità di indirizzamento indicizzate. O forse il collo di bottiglia era davvero un altro limite microarchitetturale.


Ma come funziona 1-uop fxch ? IDK come è stato fatto a Sandybridge / Ivybridge. Nelle CPU della famiglia P6 esiste fondamentalmente una tabella di remapping in più per supportare FXCH . Ciò potrebbe essere necessario solo perché P6 utilizza un file registro di ritiro con 1 voce per registro “logico”, anziché un file di registro fisico (PRF). Come dici tu, ti aspetteresti che sia più semplice quando anche i valori di registro “freddi” sono solo un puntatore a una voce PRF. (Fonte: brevetto US 5.499.352 : tabella alias del registro a virgola mobile FXCH e array di registri a virgola mobile di pensionamento (descrive l’uarch P6 di Intel).

Uno dei motivi principali per cui l’array rfRAT 802 è incluso nella presente logica fRAT dell’invenzione è un risultato diretto del modo in cui la presente invenzione implementa l’istruzione FXCH.

(Grazie a Andy Glew (@krazyglew) , non avevo pensato di cercare i brevetti per scoprire gli interni della CPU.) È piuttosto difficile, ma potrebbe fornire qualche informazione sulla contabilità necessaria per l’esecuzione speculativa.

Curiosità interessante: il brevetto descrive anche l’intero e afferma che ci sono alcuni registri logici “nascosti” che sono riservati per l’uso da parte del microcodice. (Intel 3-uop xchg quasi certamente usa uno di questi come temporaneo.)


Potremmo essere in grado di ottenere alcune informazioni dal guardare a ciò che AMD fa.

È interessante notare che AMD ha 2-uop xchg r,r in K10, Bulldozer-family, Bobcat / Jaguar e Ryzen. (Ma Jaguar xchg r8,r8 è di 3 uops, forse per supportare xchg ah,al un caso d’angolo senza uno speciale uop per scambiare il 16 basso di un singolo reg).

Presumibilmente entrambi i uops leggono i vecchi valori dei registri architettonici di input prima che il primo aggiorni il RAT. IDK esattamente come funziona, dal momento che non sono necessariamente emessi / rinominati nello stesso ciclo (ma sono almeno contigui nel stream di uop, quindi nel peggiore dei casi il secondo uop è il primo UOP nel ciclo successivo). Non ho idea se il 2-uop fxch Haswell fxch modo simile o se stia facendo qualcos’altro.

Ryzen è una nuova architettura progettata dopo che l’eliminazione del movimento è stata “inventata”, quindi presumibilmente ne traggono vantaggio laddove ansible. (La famiglia Bulldozer rinomina le mosse vettoriali (ma solo per la bassa corsia 128b dei vettori YMM), Ryzen è la prima architettura AMD a farlo anche per i xchg r32,r32 GP.) xchg r32,r32 e r64,r64 sono a latenza zero (rinominati) , ma ancora 2 uops ciascuno. ( r8 e r16 bisogno di un’unità di esecuzione, perché si fondono con il vecchio valore invece di estendere o copiare l’intero reg, ma sono ancora solo 2 uops).

Il fxch di fxch è 1 uop . AMD (come Intel) probabilmente non sta spendendo un sacco di transistor per rendere x87 veloce (ad esempio fmul è solo 1 per orologio e sulla stessa porta di fadd ), quindi presumibilmente sono stati in grado di farlo senza un sacco di supporto extra. Le loro istruzioni x87 micro-codificate (come fyl2x ) sono più veloci rispetto alle recenti CPU Intel , quindi forse a Intel importa ancora meno (almeno sull’istruzione x87 microcodificata).

Forse AMD avrebbe potuto rendere xchg r64,r64 un singolo uop, più facilmente di Intel. Forse anche xchg r32,r32 potrebbe essere single uop, dato che come Intel ha bisogno di supportare mov r32,r32 zero-extension senza porta di esecuzione, quindi forse potrebbe semplicemente impostare qualunque bit “superiore 32 azzerato” esistente per supportarlo. Ryzen non elimina movzx r32, r8 in movzx r32, r8 di rinomina, quindi presumibilmente c’è solo un bit upper32-zero, non bit per altre larghezze.


Cosa Intel potrebbe essere in grado di fare a buon mercato se volesse:

È ansible che Intel possa supportare 2-uop xchg r,r come fa Ryzen (zero latenza per le forms r32,r32 e r64,r64 o 1c per i r8,r8 e r16,r16 ) senza troppa complessità aggiuntiva in parti critiche del nucleo, come il problema / rinominare e fasi di pensionamento che gestiscono la Register Alias ​​Table (RAT). Ma forse no, se non possono avere 2 uops leggono il “vecchio” valore di un registro quando il primo uop lo scrive.

Stuff come xchg ah,al è sicuramente una complicazione in più, dal momento che le CPU Intel non rinominano più i registri parziali separatamente, tranne AH / BH / CH / DH .


latenza xchg in pratica sull’hardware corrente

La tua ipotesi su come potrebbe funzionare internamente è buona. Quasi certamente utilizza uno dei registri temporali interni (accessibile solo al microcodice). La tua ipotesi su come possono riordinare è troppo limitata, però. In effetti, una direzione ha latenza 2c e l’altra direzione ha latenza ~ 1c.

 00000000004000e0 <_start.loop>: 4000e0: 48 87 d1 xchg rcx,rdx # slow version 4000e3: 48 83 c1 01 add rcx,0x1 4000e7: 48 83 c1 01 add rcx,0x1 4000eb: 48 87 ca xchg rdx,rcx 4000ee: 48 83 c2 01 add rdx,0x1 4000f2: 48 83 c2 01 add rdx,0x1 4000f6: ff cd dec ebp 4000f8: 7f e6 jg 4000e0 <_start.loop> 

Questo ciclo viene eseguito in ~ 8,06 cicli per iterazione su Skylake. L’inversione degli operandi xchg la esegue in cicli ~ 6.23c per iterazione (misurata con perf stat su Linux). i segnalini uop emessi / eseguiti sono uguali, quindi non è avvenuta alcuna eliminazione. Sembra che la direzione dst <- src sia quella lenta, dal momento che mettere gli adduption su questa catena di dipendenze rende le cose più lente rispetto a quando si trovano nella catena di dipendenze dst -> src .

Se si desidera utilizzare il xchg reg,reg sul percorso critico (ragioni di dimensione del codice?), xchg reg,reg con la direzione dst -> src sul percorso critico, poiché si tratta solo della latenza 1c.


Altri argomenti secondari dai commenti e dalla domanda

Le 3 micro-operazioni lanciano la mia cadenza 4-1-1-1

I decodificatori della famiglia Sandybridge sono diversi da Core2 / Nehalem. Possono produrre fino a 4 uop totali, non 7, quindi i pattern sono 1-1-1-1 , 1-1-1-1 , 3-1 o 4 .

Inoltre, fai attenzione che se l'ultimo uop è uno che può effettuare il macro-fusibile, si bloccheranno su di esso fino al prossimo ciclo di decodifica nel caso in cui la prima istruzione nel blocco successivo sia un jcc . (Si tratta di una vincita quando il codice viene eseguito più volte dalla cache di UOP ogni volta che viene decodificato. E di solito è sempre 3 Uops per decodificare la velocità effettiva).

Skylake ha un decodificatore "semplice" in più, quindi può fare 1-1-1-1-1 fino a 4-1 , ma> 4 uops per una istruzione richiede ancora la ROM del microcodice. Skylake ha rinforzato anche la cache di uop e spesso può strozzare i 4 uops di dominio fuso per ogni problema di clock / rinominare il limite di throughput se il back-end (o il ramo mancante) non è un collo di bottiglia per primo.

Sto letteralmente cercando ~ 1% di dossi di velocità, quindi l'ottimizzazione delle mani ha funzionato sul codice di loop principale. Sfortunatamente questo è ~ 18kB di codice quindi non sto nemmeno cercando di considerare la cache di uop più.

Sembra un po 'pazzesco, a meno che non ti limiti principalmente all'ottimizzazione a livello asm nei loop più brevi all'interno del tuo ciclo principale. Tutti i loop interni all'interno del ciclo principale continueranno a essere eseguiti dalla cache di uop, e probabilmente questo dovrebbe essere il momento in cui trascorrerai la maggior parte del tempo a ottimizzare. I compilatori di solito fanno un lavoro abbastanza buono che non è pratico per un umano fare molto su larga scala. Prova a scrivere il tuo C o C ++ in modo tale che il compilatore possa fare un buon lavoro con esso, ovviamente, ma cercare piccole ottimizzazioni come questo oltre 18kB di codice sembra andare nella tana del rabbitmq.

Usa contatori perf come idq.dsb_uops e uops_issued.any per vedere quanti dei tuoi totali sono usciti dalla cache uop (DSB = Decode Stream Buffer o qualcosa del genere). Il manuale di ottimizzazione di Intel ha alcuni suggerimenti per altri contatori perf per cercare il codice che non si adatta alla cache di uop, come ad esempio DSB2MITE_SWITCHES.PENALTY_CYCLES . (MITE è il percorso legacy-decode). Cerca nel pdf per DSB per trovare alcuni posti in cui è menzionato.

I contatori Perf ti aiuteranno a trovare i punti con potenziali problemi, ad esempio le regioni con uops_issued.stall_cycles superiore alla media potrebbero trarre beneficio dalla ricerca di modi per esporre più ILP se ce ne sono, o dalla soluzione di un problema front-end o dalla riduzione di errori imprevedibili.


Come discusso nei commenti, un singolo UOP produce al massimo 1 risultato di registro

Per %rdx , con un mul %rbx , ottieni veramente %rdx e %rax tutto in una volta o il ROB ha tecnicamente accesso alla parte inferiore del risultato un ciclo prima della parte superiore? O è come se il "mul" uop entrasse nell'unità di moltiplicazione e quindi l'unità di moltiplicazione emettesse due uops direttamente nel ROB per scrivere il risultato alla fine?

Terminologia: il risultato della moltiplicazione non va nel ROB. Passa sulla rete di inoltro a qualsiasi altro utente che lo legge e va nel PRF.

L'istruzione mul %rbx decodifica a 2 uop nei decodificatori. Non hanno nemmeno bisogno di rilasciare nello stesso ciclo, figuriamoci eseguire nello stesso ciclo.

Tuttavia, le tabelle delle istruzioni di Agner Fog elencano solo un singolo numero di latenza. Risulta che 3 cicli è la latenza da entrambi gli ingressi a RAX. La latenza minima per RDX è 4c, in base al test InstlatX64 su Haswell e Skylake-X .

Da ciò, concludo che il secondo uop dipende dal primo ed esiste per scrivere la metà superiore del risultato in un registro architettonico. Il port1 uop produce un risultato di moltiplicazione completo di 128b.

Non so dove il risultato della metà risiede finché il p6 uop non lo legge. Forse c'è una sorta di coda interna tra l'unità di esecuzione multipla e l'hardware connesso alla porta 6. Pianificando il p6 uop con una dipendenza dal risultato di metà campo, ciò potrebbe fare in modo che i p6 uops derivino da più istruzioni mul in-flight per l'esecuzione nell'ordine corretto. Ma poi, invece di usare effettivamente quell'ingresso di metà basso fittizio, l'uop prenderebbe il risultato della metà superiore dell'output di coda in un'unità di esecuzione che è connessa alla porta 6 e la restituirà come risultato. ( Questo è puro lavoro di supposizione , ma penso che sia plausibile come una ansible implementazione interna.Vedi i commenti per alcune idee precedenti).

È interessante notare che, secondo le tabelle di istruzioni di Agner Fog , su Haswell i due uops per mul r64 vanno alle porte 1 e 6. mul r32 è 3 uops e gira su p1 + p0156. Agner non dice se questo è realmente 2p1 + p0156 o p1 + 2p0156 come fa per altri insns. (Tuttavia, egli afferma che mulx r32,r32,r32 gira su p1 + 2p056 (si noti che p056 non include p1).)

Ancora più stranamente, afferma che Skylake esegue mulx r64,r64,r64 su p1 p5 ma mul r64 su p1 p6 . Se questo è accurato e non un refuso (che è una possibilità), praticamente esclude la possibilità che l'extra-uop sia un moltiplicatore della metà superiore.