GUIDA CPU: Ambiente di Esecuzione Hardware

[DispatchCode]

CPU: Ambiente di Esecuzione Hardware

Interamente a cura di Marco C. (DispatchCode)​

Prefazione

---

Ho pensato di scrivere questo piccolo articolo in quanto in rete non mi è sembrato molto diffuso, ed alcune informazioni le si riescono ad avere ma in modo non proprio lineare (ovvero si passa da un link all'altro mettendo insieme poi tutto il materiale, e forse si riesce ad avere un quadro quasi completo).


Introduzione

---

Il seguente articolo ha come scopo chiarire alcuni concetti sul funzionamento del processore, in particolare mostrerà in quale modo vengono eseguite le istruzioni, le fasi che vengono attraversate ed il numero di fasi coinvolte in una pipeline.
Precisamente porremo la nostra attenzione su IA-32, della Intel Corporation. Nel corso degli anni però si sono affermate altre aziende, e più precisamente AMD, che produce processori IA-32 compatibili. Una piccola chicca, la riporterei ora. Il codice compatibile con NetBurst è praticamente compatibile con AMD (ed Intel, ovviamente), ma vi sono alcune feature particolari che non sono supportate da entrambi i processori; è il caso di 3DNow! di AMD. I processori Intel non supportano questo set di istruzioni, al contrario però, AMD supporta il set SSE di Intel (in pratica i set sono in competizione).

L'analisi continuerà affrontando (brevemente) i seguenti argomenti:

• Intel NetBurst
• µops (Micro-Ops)
• Pipelines
• Branch Prediction
  • Eliminare il Branch Prediction

Intel NetBurst

---

Intel NetBurst è una microarchitettura, ormai nemmeno più recente, ma comoda da analizzare (chissà che non scriverò articoli sulle più recenti anche). La microarchitettura del Pentium 4, e capire in che modo opera, ci permetterà di comprendere meglio le ottimizzazioni sul codice del software scritto poi dai programmatori. Intel ormai rilascia una nuova architettura ogni 2 anni circa.


µops (Micro-Ops)

---

Si tratta semplicemente del microcodice. I processori IA-32 infatti usano il microcodice per implementare le istruzioni più complesse. Il microcode è salvato all'interno di una ROM; ogni istruzione ha quindi il corrispondente microcode. Dato che l'accesso continuo alla ROM produrrebbe dei rallentamenti, vi è una cache apposita che memorizza le istruzioni a cui la CPU accede più spesso.


Pipelines

---

Questa era presente già nei vecchi processori. Grazie alla pipelines il processore è in grado di eseguire più istruzioni parallelamente. In pratica è simile ad una catena di montaggio, ed ogni fase si occupa di una differente operazioni.
Nel caso di NetBurst vi sono 3 fasi principali:

• Front End: si occupa della decodifica delle istruzioni e produrre sequenze di micro-ops che rappresentano ogni istruzione. Vengono poi passate ad un componente chiamato Out of Order Core.
• Out of Order Core: ricevute le sequenze di microcodice dal Front End e le riordina basandosi sulla disponibilità delle risorse del processore.
• Retirement Section: il compito principale è assicurarsi che le istruzioni vengano eseguite nell'ordine originale.

Per quanto riguarda l'esecuzione delle operazioni, vi sono 4 porte (da 0 a 3), ognuna con la propria pipeline.

Porta 0

E' suddivisa in due parti: Double Speed ALU e Floating Point Move. La prima si occupa delle seguenti operazioni: ADD/SUB, operazioni logiche, blocchi condizionali (branches), Store Data Operation. La seconda si occupa invece delle seguenti operazioni: Floating Point Moves, Floating Point Stores, Floating Point Exchange


Porta 1

E' suddivisa in tre parti: Double Speed ALU, Integer Unit e Floating Point Execute. La prima si occupa delle seguenti operazioni: ADD/SUB La seconda si occupa delle seguenti operazioni: Shift e Rotazioni e Operazioni La terza si occupa invece delle seguenti: Addizione, Moltiplicazione e Divisione in virgola mobile (Floating Point), Altre operazioni ed MMX


Porta 2

Svolge un solo compito: Memory Loads. Si occupa solo della seguente operazione: Lettura dalla memoria


Porta 3

Svolge un solo compito: Memory Writes. E si occupa della seguente operazione: Address Store Operations. Si occupa praticamente della scrittura dell'indirizzo di memoria sul bus, ma non invia dati.


Particolare considerazione la meritano certamente la Porta 0 e la 1, in quanto hanno entrambe una Double Speed ALU che come dice già il nome stesso permette di eseguire le operazioni al doppio della velocità; possono essere eseguite ad esempio 4 addizioni (o sottrazioni), due per ogni ALU. Notiamo però che i floating point non hanno questo beneficio, quindi possiamo dedurre che la gestione dei numeri con la virgola sia più lenta rispetto ai numeri interi.


Branch Prediction

---

Come detto sopra, grazie alla pipeline è possibile svolgere più compiti simultaneamente (che riguardano stadi differenti). Ad esempio è possibile eseguire un operazione e nello stesso tempo caricare le istruzioni successive, così da essere già pronte all'esecuzione.
Questo permette di capire poichè è meglio evitare un uso inappropriato di if all'interno del codice di un software. Immaginate la classica situazione: il processore effettua dei calcoli e si trova ora in prossimità di un salto condizionale (sia esso un for, un while o un if, che di fatto costringono a valutare la condizione). In questo caso che si fa? Il processore caricherà l'interno dell'if (for, while) oppure ciò che viene dopo? La risposta a queste domande è: dipende dal tipo di condizione che ci si trova davanti. Il processore effettua una preedizione in base alla condizione che si trova a dover elaborare; la strategia è semplice: i backward branches (i loops, come while e for) vengono assunti come sempre true, mentre i forward branches vengono assunti come sempre falsi. Il motivo è semplice: nel caso dei loop si incorre in una predizione errata (ovvero riempire la pipeline con istruzioni che non verranno eseguite, in quanto l'esito della condizione è diverso da quanto si ipotizzava) solamente all'ultima iterazione. Ma quando la predizione è errata, che accade? La pipeline deve essere completamente svuotata, e devono essere così caricate le istruzioni corrette. In questo si ha un notevole spreco di tempo (espresso in cicli ci clock). Per facilitare il riconoscimento di una condizione già esaminata, viene utilizzato un BTB che è in pratica un buffer (Branc Trace Buffer) in cui vengono memorizzati gli esiti delle ultime condizioni eseguite. Di conseguenza, se viene individuato un elemento in questo buffer, viene usato questo per predire il comportamento.


Eliminare il Branch Prediction

---

Come abbiamo visto nel precedente paragrafo, il Branch Prediction è causa di rallentamenti in quanto in caso di una predizione errata la pipeline deve essere svuotata e poi riempita nuovamente con le nuove istruzioni. Per comprendere una tecnica che permette di evitare questo problema, è necessario pensare a quando compiliamo un software. Il compilatore (sia esso GCC, Intel etc.) svolge diverse operazioni prima di restituire il codice oggetto; una di queste fasi viene svolta dal beck-end, e si occupa dell'ottimizzazione del codice scritto. Una delle fasi di ottimizzazione consiste nel rimpiazzare eventuali IF con operazioni matematiche che conducano al risultato senza bisogno di usare salti condizionati (if, while, for, a breve mostrerò un esempio). Nel caso dei cicli iterativi, a volte viene effettuato un "unrolling loops", cioè il loop viene "srotolato", letteralmente. Ovviamente il peso sarà superiore essendoci più istruzioni, ma in alcune circostanze può essere conveniente.


Uno sguardo in basso...

---

Prima di continuare, è necessario aver ben chiaro come funzionano i costrutti quali if, for e while a basso livello, usando Assembly.
Il linguaggio Assembly altro non è che una rappresentazione simbolica del codice macchina; questo significa che ogni istruzione ha una diretta corrispondente in codice macchina.

Questo è codice macchina:

A1 3A D5 17 F4

Il corrispettivo in Assembly è:

mov eax, 0xF417D53A ; eax = 0xF417D53A

Da notare che il numero (F417D53A) è a 32bit, ed essendo un architettura little endian viene prima il byte meno significativo (quindi lo troveremo scritto al contrario, come nell'esempio in codice macchina). In pratica stiamo assegnando quel valore all'interno del registro eax.

A1 è l'opcode, cioè, il codice dell'operazione che vogliamo eseguire; in particolare si tratta di mov reg, mem (se effettuassimo l'assegnamento contrario, l'opcode cambierebbe).

Chiarito questo aspetto, possiamo proseguire. In Assembly un salto condizionale avviene usando uno mnemonico del tipo Jxx, dove al posto delle x ci sarà il tipo di salto più specifico. Alcuni esempi:

JE = Salta se uguale 
JG = Salta se è maggiore 
JL = Salta se è minore 
JNE = Salta se NON è uguale

e ve ne sono molti altri. Tutti questi sono salti condizionati, quindi come dice il nome stesso il salto avviene solo se il valore è maggiore, minore, uguale... Esiste un altro tipo di salto, quello incondizionato, indicato con JMP.

Prima di questi mnemonici vi è solitamente un istruzione che effettua il confronto; questa istruzione spesse volte è CMP. Questa istruzione, proprio come MOV vista più sopra (che sposta i dati da una sorgente ad una destinazione) ha una destinazione ed una sorgente.
Un esempio è:

; Forma: ;
 CMP dest, src 

CMP eax, 0

Il risultato prodotto da questa istruzione è una modifica al registro EFLAGS del processore, e riguarda i bit interessati (ciascun flags ha un significato ben preciso, ma non serve analizarlo in questa sede, in quanto non è una guida ad Assembly).
Opera nel seguente modo: sottrae la sorgente dalla destinazione, modifica il flag, ma non salva il risultato (non altera quindi la destinazione). Nel caso sopra esposto quindi vi sarà eax - 0. Ora sappiamo perchè le istruzioni mostrate sopra del tipo Jxx si chiamano "salti condizionati"; la condizione che determina il salto è data proprio dal flags (in base al suo valore).

Ora abbiamo gli elementi per analizzare un IF in Assembly. Vogliamo saltare ad un determinato indirizzo solo se EAX vale 0. Useremo quindi JE (salta se eax è uguale a 0, nel nostro caso).

cmp eax, ebx 
jle MinoreUguale 
mov eax, c1 
jmp Altro 
MinoreUguale:
mov eax, c2 
Altro:

Con sintassi C lo stesso codice può essere scritto come:

if(eax <= ebx) { 
  eax = c1; 
}  else  { 
  eax = c2; 
}

Oppure anche come:

eax = (eax <= ebx) ? c1 : c2;

Nel caso sopra rappresentato, cmp modifica quindi i flag, e JE verifica l'esito dell'operazione guardando il flag appropriato.
Ciò che accade dovrebbe essere chiaro facendo riferimento al codice in C scritto sotto: se EAX è minore o uguale a EBX, viene posto EAX uguale al valore c1, altrimenti viene posto uguale a c2. Il JMP è utile in quanto corrisponderebbe in C al termine del blocchi IF e ci evita quindi di entrare nell'ELSE.

Un while "ottimizzato" visto a basso livello, presenta prima un IF e poi il corpo del ciclo. Qui sotto vi è un esempio:

cmp eax, 0 
je SaltaLoop 
InizioLoop:
 ; istruzioni 
; ..... 

cmp ecx, 0 
jne SaltaLoop 
; altre istruzioni 

cmp eax, 0 
jne InizioLoop 
SaltaLoop: 
; .....

La forma che ho mostrato è volutamente molto generica e priva di significato (non esegue alcun controllo specifico), ma permette di capire la logica del while. Il primo JE salta all'etichetta chiamata SaltaLoop se EAX vale 0. Se ha un numero differente entra nel loop. Esegue altre istruzioni e poi verifica se ECX vale 0; in questo caso il salto avviene se è diverso. Vi sono poi altre istruzioni, ed un nuovo controllo su EAX. In questo caso il salto avviene se è diverso da 0, ed una volta effettuato il salto ci si ritrova di nuovo all'etichetta InizioLoop, e di conseguenza si ripete un nuovo ciclo.


A questo punto sappiamo come funzionano un IF ed un While ad un livello più basso. Il codice che presenta IF/ELSE in quel modo può essere riscritto evitando il branch prediction. E' possibile effettuare questa operazione usando l'istruzione SETCC oppure utilizzando CMOV ed eseguendo opportuni calcoli. Come prima, CC in questo caso viene sostituito dal tipo di istruzione necessario (SETL, SETNE, SETE, etc...); nel nostro caso utilizzeremo SETLE. Questa particolare istruzione permette di settare il registro passato come operando destinazione in base a "se è minore o uguale", di conseguenza, il valore settato da questa istruzione dipende dal valore assunto dal flag (quindi ci sarà prima il classico CMP).

Per comprendere meglio, analizziamo questa volta un source in MASM in ambiente Win32. Il seguente sorgente non è ottimizzato:

    include     c:\masm32\include\masm32rt.inc
     
     
    .data
    c1         dd      0    ; Costante che indica il fallimento del confronto (eax NON e' minore di ebx)
    c2         dd      1    ; In questo caso invece eax e' minore di ebx
     
    .data?
     
     
    .code
    start:
     
      call      main
      inkey
      invoke    ExitProcess,0
        
        
    main        proc
       mov      eax, 123
       mov      ebx, 124
      
       cmp      eax, ebx
       jle      MinoreUguale
       mov      eax, [c1]
       jmp      Altro
       MinoreUguale:
       mov      eax, [c2]
       Altro:
      
       print    str$(eax),13,10
      
       ret
      
    main        endp
     
    end         start

Il risultato restituito è 1. In effetti eax contiene un numero più piccolo di ebx, anche se di una sola unità.
Il seguente codice come è stato spiegato sopra effettua semplicemente un controllo del tipo if(eax <= ebx) {...} else {....}..

La prima versione ottimizzata utilizza setle, come già detto sopra; il main ora ha questo aspetto:

    main        proc
       mov      eax, 123
       mov      ebx, 124
      
       xor      ecx, ecx
       cmp      eax, ebx
       setle    cl
       sub      ecx, [c2]   ; c2 = 1
       and      ecx, [c3]   ; c3 = c1 - c2 = -1
       add      ecx, [c2]
      
      
       print    str$(ecx),13,10
      
       ret
      
    main        endp

c3 è dichiarata come c1-c2, quindi vale -1.

l seguente codice merita la nostra attenzione, in quanto non è proprio comprensibile ad un primo sguardo. Come detto precedentemente cmp modifica il flags registers; xor è il classico OR-Esclusivo ed applicato ad una stessa variabile azzera il valore (ergo ecx = 0 dopo l'esecuzione di quella istruzione).
Quella che ancora non conosciamo bene è setle. Il suo comportamente è molto semplice: se il flag ZF (Zero Flag) è settato a 1 OPPURE il Sign Flag NON è uguale all'Overflow Flag il byte passato come parametro (cl, nel nostro caso) viene settato a 1; diversamente viene settato a 0.
Qusti flags sono tutti quelli modificabili quando utilizziamo l'istruzione CMP, ed ovviamente la modifica avviene come conseguenza del risultato ottenuto da CMP (ricordo che cmp effettua una sottrazione senza memorizzare il risultato).

Da questo possiamo quindi dedurre che nel codice sopra riportato, essendoci gli stessi valori del precedente non ottimizzato, quel CMP produrrà esattamente gli stessi flags settati a 1 ed a 0. Ecco quindi che in CL viene memorizzato il valore 1, settato appunto da setle.

NOTA: per chi non conosce i registri del processore (eax, ebx, ecx,...).

---

Spoiler

ECX, EAX, EBX, EDX sono tutti registri generali del processore, usati liberamente dal programmatore (la CPU usa ad esempio ECX come contatore di un loop).
Questi registri sono tutti a 32bit, ma possono essere scomposti in più parti. I 16bit più alti non sono accessibili direttamente. Tuttavia se si deve operare su dati a 16bit si possono usare i più bassi, quelli ad esempio utilizzati in 8086. I registri diventano quindi CX, AX, BX, DX. Questi sono quindi a 16bit, e sono scomponibili in altre due parti, una che contiene i bit più alti ed una che contiene i bit più bassi. Si scompongono quindi in CH, CL; AH, AL; BH, BL; DH, DL.
Quindi nel codice sopra stiamo usando CL, ovvero i primi 8bit del registro ECX.

---

Continuando l'analisi vediamo l'istruzione sub che come si intuisce dal nome stesso indica una sottrazione tra il primo operando ed il secondo.
L'istruzione successiva è un AND a livello di bit (il classico & di C/C++, Java ed altri oppure l'and di Python). Questo restituisce 1 quando entrambi i bit sono settati a 1.
L'istruzione successiva, add, è un addizione.

Voglio soffermarmi ora sulla logica di queste istruzioni. Ciò che accade è in pratica questo: viene azzerato il registro ECX che conterrà poi il risultato finale; viene effettuato il confronto tra EAX ed EBX e successivamente viene settato a 1 il registro CL (in quanto EAX è minore di EBX). Successivamente viene sottratto il numero 1 dal registro ECX e viene effettuato un AND con la differenza tra c1 e c2, quindi -1. Questo setta il valore di ECX a 0, oppure a 1; dipende dal valore precedente, nel nostro caso conterrà 0. L'ultima istruzione somma il valore 1 al registro ECX, inserendo quindi il valore corretto.
Vista con i numeri in binario:

    EAX = 5  ; 00000000000000000000000000000101
    EBX = 10 ; 00000000000000000000000000001010
     
    ; setle cl
    CL  = 00000001  ; eax <= ebx
     
    ; sub   ecx, 1
    ECX - 1  = 00000000000000000000000000000001 - 1  = 00000000000000000000000000000001 - 1 = 00000000000000000000000000000000
     
    ; and   ecx, -1
    ECX & -1 = 00000000000000000000000000000000 & -1 = 00000000000000000000000000000000 & 11111111111111111111111111111111 = 00000000000000000000000000000000
     
    ; add   ecx, 1
    ECX + 1 = 00000000000000000000000000000001

Ho citato in precedenza CMOV, ma non ho riportato alcun esempio. Eccone quindi uno:

    include     c:\masm32\include\masm32rt.inc
     
    .data
     
    .data?
     
     
    .code
    start:
     
      call      main
      inkey
      invoke    ExitProcess,0
        
        
    main        proc
       mov      eax, 100
       mov      ebx, 50
      
       mov      ecx, ebx
       cmp      eax, ebx
       cmovle   ecx, eax
      
       print    str$(ecx),13,10
      
       ret
      
    main        endp
     
    end         start

L'istruzione CMOVcc effettua l'assegnamento solo se la condizione cc, che può assumere gli stessi valori di SETcc, ovvero le, ge, etc. è verificata.
Nel codice precedente viene quindi assegnato al registro ECX il valore di EBX; successivamente si utilizza il solito CMP per settare i flags, e l'istruzione CMOV per spostare (se EAX < EBX) il valore di EAX in ECX. Nel caso precedente l'istruzione non verrà eseguita in quanto EBX è minore di EAX, e l'output risultante è quindi 50, il valore di EBX.


Conclusione

---

L'articolo è giunto al termine. Spero sia stato un viaggio interessante seppur breve e non esaustivo (le informazioni sarebbero veramente molte). Se trovate errori o avete domande, scrivete qui sotto.

DispatchCode