di  -  venerdì 14 maggio 2010

Nei precedenti articoli abbiamo visto come utilizzare una pipeline per aumentare l’efficienza di utilizzo dell’hardware e aumentare di conseguenza le prestazioni della macchina. Tuttavia, la semplice pipeline in-order soffre di una serie di limitazioni che non le permettono di sfruttare buona parte dell’Instruction-Level Parallelism (ILP) presente in un programma. Di conseguenza, le sue prestazioni non riescono a salire oltre un livello generalmente modesto, con un IPC (Instructions Per Clock) sempre minore di 1.

Il problema è che il listato assembly è una sovraspecifica del programma: l’ordine delle istruzioni specificato è condizione sufficiente ma non necessaria per ottenere il risultato voluto. Nella pipeline semplice le istruzioni vengono eseguite strettamente in ordine di programma, non potendo superarsi all’interno degli stadi, e questa è la causa del mancato sfruttamento dell’ILP.

Per risolvere il problema e aumentare ancora di più le prestazioni è necessario cambiare completamente paradigma: le istruzioni devono poter eseguire, all’interno della CPU, nell’ordine più veloce, indipendentemente dall’ordine specificato dal codice. La domanda naturalmente è: qual è questo “ordine più veloce”? Come lo si trova? Come lo si esegue?

Negli anni ’70 / ’80 queste domande alimentarono molta ricerca in ambito accademico, e produssero un paradigma di computazione chiamato dataflow architecture. L’idea base è di eseguire le istruzioni non in ordine di programma, ma in ordine di disponibilità degli operandi: appena un’istruzione ha tutti gli operandi disponibili, essa viene attivata ed eseguita. Questo è il limite ultimo raggiungibile di IPC: avendo a disposizione hardware illimitato, l’intero programma potrebbe essere analizzato ad ogni ciclo di clock, tutte le istruzioni pronte verrebbero eseguite, e il programma verrebbe completato nel minimo numero di cicli di clock possibile. Visto che tutte le dipendenze sono rispettate, il programma eseguirà correttamente e produrrà il risultato voluto, nonostante l’aggressivo rimescolamento delle istruzioni.

La conseguenza di questo paradigma è un’architettura insolita, molto diversa da quelle a cui siamo abituati. Innanzitutto non esiste un Program Counter, visto che le istruzioni non devono essere sequenziate in ordine di programma. Inoltre, la memoria non viene acceduta per indirizzo ma per tag unica: il compilatore assegna ad ogni operando e risultato una tag unica (che non si ripete per tutto il programma), e le istruzioni cercano i propri operandi tramite questa tag. Il cuore del sistema è quindi una Content-Addressable Memory (CAM) : ogni dato è in rappresentato in memoria come una coppia {tag, dato}, e per cercare una tag bisogna scorrere tutte le coppie fino a trovarla.

Per chiarire il concetto, consideriamo questa sequenza di operazioni

c11 <= a11 * b11 + a12 * b21 + a13 * b31

che potrebbe venire, ad esempio, dal prodotto tra due matrici. In pseudo assembly può essere tradotta come

r1 <= a11 * b11
r2 <= a12 * b21
r3 <= a13 * b31
c11 <= r1 + r2
c11 <= c11 + r3

In una pipeline semplice queste istruzioni verrebbero eseguite in ordine e, se la ALU avesse dei forwarding paths (come spiegato qui), verrebbero eseguite al ritmo di esattamente una istruzione per ciclo di clock. Tuttavia, è chiaro che si potrebbe fare meglio di così: le prime tre istruzioni sono indipendenti, e possono essere eseguite in qualsiasi ordine (quindi anche contemporaneamente). Il modo più semplice per rendersene conto è analizzare il grafo delle dipendenze tra le istruzioni:

L’altezza dell’albero è 3 (il ramo sinistro, composto da due somme e una moltiplicazione), e quindi, avendo a disposizione abbastanza hardware, sarebbe possibile eseguire quelle istruzioni in soli 3 cicli di clock. Ma come fare?

L’architettura dataflow risolve il problema riscrivendo il programma in memoria in questo modo (estremamente idealizzato):

La memoria non viene più acceduta per indirizzo, ma per tag, tramite una ricerca completa della tag. L’esecuzione procede in questo modo:

  • al primo ciclo di clock, le prime tre istruzioni sono segnate “attive” perchè tutti i loro operandi sono disponibili (supponiamo che fossero stati caricati in precedenza) e vengono eseguite in parallelo; i loro risultati, identificati dalle tag {1,2,3} vengono propagati all’intera memoria per essere “catturati” dalle istruzioni che hanno le stesse tag
  • al secondo ciclo di clock, l’istruzione 4 è pronta ad eseguire perchè ha catturato i valori associati alle tag {1,2} al ciclo precedente; esegue e propaga il suo risultato
  • al terzo ciclo di clock, l’ultima istruzione ha tutti i suoi operandi (prodotti nel primo e secondo ciclo), e può eseguire

In questo modo molto elegante è possibile eseguire sempre ogni programma nel minimo numero di cicli di clock possibile (cioè con lo IPC più alto possibile). Sfortunatamente, questo schema ideale mal si adatta alla realtà: non è possibile costruire una memoria di questo tipo che sia abbastanza grande da contenere tutto un programma (o una buona parte di esso) e abbastanza veloce da permettere buone prestazioni. In particolare, il parallelismo è a grana troppo fine (a livello di singole istruzioni) e il tempo di propagazione dei dati nella memoria è superiore al tempo di esecuzione delle istruzioni.

Per questi motivi le architetture dataflow pure sono rimaste esercizi accademici senza applicazioni commerciali. Ma i concetti principali sono confluiti nelle architetture Out-Of-Order, cuore di tutti i moderni processori ad alte prestazioni, di cui mi occuperò nei prossimi articoli.

11 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    Emanuele Rampichini
     scrive: 

    Conoscevo il paradigma data flow (visto in erlang e Oz in un corso universitario) ma non immaginavo che qualcuno potesse pensare di portarlo pari pari sulle CPU. :D
    Fatto sta che un paradigma così semplice toglie di mezzo tutti i problemi di sincronizzazione gestiti con semafori vari, una vera manna dal cielo per la scrittura di applicazioni fortemente parallelizzate.

    Piccola domanda… la lazy evaluation è stata mai presa in considerazione a livello di architettura della CPU?

  • # 2
    TheKaneB
     scrive: 

    “Ma i concetti principali sono confluiti nelle architetture Out-Of-Order, cuore di tutti i moderni processori ad alte prestazioni, di cui mi occuperò nei prossimi articoli.”

    nooooooo!!! non puoi lasciarci così a metà :D mi stavo “intrippando” nella lettura dell’articolo, ci sono rimasto di sasso…

  • # 3
    Pleg (Autore del post)
     scrive: 

    @ Emanuele

    Il dataflow e’ stato il Santo Graal dell’architettura delle CPU per gli anni ’70/’80, altroche’ :) c’e’ voluto parecchio per capire come farlo funzionare davvero, pero’. E anche come implementarlo, non a caso le prime CPU OOO mainstream (Pentium Pro, K5) sono arrivate 15 anni dopo!

    Per la lazy evaluation: non mi pare ci sia niente del genere, e mi risulta anche difficile pensarlo. Una volta che il codice arriva alla CPU, quello e’ e quello va eseguito. Anzi, direi che si fa l’opposto: la speculazione dei salti, il prefetching eccetera sono tutte tecniche che ti fanno fare PIU’ lavoro di quello strettamente necessario… invece di aspettare a vedere se qualcosa serve (“lazy”) si esegue qualcosa che potrebbe non servire, perche’ in media (se lo fai bene) aumenta le prestazioni (a scapito dell’energia, naturalmente).

  • # 4
    Pleg (Autore del post)
     scrive: 

    @ TheKaneB

    Sorry :)
    Questo piu’ che un articolo e’ in effetti un’anticipazione, ma mi serviva buttar giu’ quel paio di concetti base senza i quali risulta difficile capire da dove vengono fuori i processori OOO.

    Comunque, solo per sfiorare in superficie l’architettura di un processore moderno penso che mi ci vorra’ una dozzina di articoli, quindi… stay tuned! Arriveranno pian pianino nei prossimi mesi :)

  • # 5
    D
     scrive: 

    Mi sfugge forse il punto più importante: chi gestisce questo dataflow ? Il programmatore, il compilatore o l’hardware della cpu stessa ?

  • # 6
    homero
     scrive: 

    argomento molto interessante purtroppo limitato dal punto di vista teorico, il futuro di questo lo aveva tracciato intel con l’architettura itanium in cui si dava al compilatore la possibilità di gestire il flusso dati e volendo anche il programmatore poteva con un po’ di archibugi metterci lo zampino, a differenza delle architetture superscalari con pentium in cui tutto era gestito a livello hardware e il programmatore aveva pochissime(per non dire nulle) possibilità di gestire il tutto…
    quale è il futuro di tutto questo?
    bene il futuro credo che sia per il momento ancora itanium(il processore meno sfruttato della storia recente) in cui esistono metodi di gestione del dataflow superiori alle architetture desktop/server attuali in quanto su itanium il software puo’ gestire il modo in cui predeterminare la richiesta di dati e quindi ridurre al minimo gli accessi alla memoria che è il vantaggi principale dell’out of order dataflow
    vorrei non si confondesse il parallelismo degli algoritmi con il parallelismo citato nell’articolo delle istruzioni hardware in quanto sono due cose molto diverse…

  • # 7
    Pleg (Autore del post)
     scrive: 

    @ D

    In questo caso, stavo parlando del solo processore. Il compilatore puo’ aiutare (in alcuni casi, il compilatore puo’ fare molto), ma qui mi interessava solo mostrare come sia possibile riordinare aggressivamente le varie istruzioni all’interno della CPU in modo da eseguirle piu’ in fretta ottenendo lo stesso risultato.

    Nei processori che abbiamo a casa, il lavoro viene fatto completamente dal processore: e’ invisibile al programmatore, e in questo modo riesci a mantenere la compatibilita’ col codice precedente (e’ sempre il solito mantra :)

  • # 8
    D
     scrive: 

    Più avanti avremo una lista che raccoglierà tutte le operazioni aggressive che deve portare avanti un processore

  • # 9
    D
     scrive: 

    dimenticato il “?”

  • # 10
    Pleg (Autore del post)
     scrive: 

    @ D

    Si’, dovrei riuscirci :)

  • # 11
    banryu
     scrive: 

    Complimenti, interessantissimo articolo digeribile senza sforzi anche da chi è un profano del \basso livello\.
    Lettura godibilissima, ora mi butto sulle precedenti, in attesa della prossima!

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.