A p p u n ti d i C alcolatori E lettron ici - Siti Personali | Libero...

AAAppppppuuunnntttiii dddiii CCCaaalllcccooolllaaatttooorrriii EEEllleeettttttrrrooonnniiiccciii CCCaaapppiiitttooolllooo 777 ––– PPPrrroooccceeessssssooorrriii vvveeettttttooorrriiiaaallliii

Introduzione: perché i calcolatori vettoriali? ................................................................... 1 Pregi delle istruzioni vettoriali ..................................................................................... 2

Architettura di base dei calcolatori vettoriali: il DLXV ..................................................... 4 Istruzioni vettoriali del DLXV ..................................................................................... 6

Esempio: loop DAXPY .................................................................................................... 7 Transitorio di attivazione e frequenza di interazione delle istruzioni vettoriali ................... 9 Specifiche delle unità funzionali del DLXV..................................................................... 12

Unità di caricamento/memorizzazione ........................................................................ 12 Gestione dei banchi di memoria in un calcolatore vettoriale ......................................... 13

Problematiche realizzative: lunghezza e passo dei vettori ............................................... 16 Controllo della dimensione dei vettori ........................................................................ 16

Tecnica della riduzione a blocchi ............................................................................ 16 Passo dei vettori ....................................................................................................... 18

Prestazioni dei calcolatori vettoriali.............................................................................. 21 Tecniche di compilazione .............................................................................................. 22

Efficienza delle tecniche di vettorizzazione................................................................. 24

Introduzione: perché i calcolatori vettoriali?Introduzione: perché i calcolatori vettoriali? Nel capitolo precedente abbiamo studiato il pipelining, ossia una possibile tecnica

per migliorare le prestazioni di un calcolatore, dotato di singolo processore, sfruttando essenzialmente il parallelismo esistente tra le istruzioni da eseguire; abbiamo anche visto che le tecniche di schedulazione dinamica delle istruzioni, quelle di avvio di istruzioni multiple per ciclo di clock e, per ultime, le tecniche avanzate di pipelining consentono di raddoppiare le prestazioni del calcolatore rispetto ad una pipeline di tipo tradizionale (quella del DLX, per intenderci). Tuttavia, abbiamo anche osservato che esistono comunque dei limiti a tale miglioramento di prestazioni, dovuti a due fattori principali:

• il tempo del ciclo di clock: è possibile ridurre la durata del ciclo di clock

aumentando le dimensioni della pipeline (ad esempio arrivando fino ad 8 stadi al posto dei 5 tradizionali), ma proprio la maggiore dimensione della pipeline determina un aumento delle dipendenze tra gli stadi della pipeline stessa e tali dipendenze, introducendo necessariamente degli stalli, riducono il CPI. L’esito finale è che pipeline di grandi dimensioni finiscono col diminuire la velocità del processore anziché aumentarla, proprio perché aumenta il CPI e tale aumento compensa ampiamente la riduzione della durata del ciclo di clock;

• la frequenza di prelievo e decodifica delle istruzioni: tutti i calcolatori presentano un limite tecnologico, talvolta denominato collo di bottiglia di Flynn, al numero di istruzioni che possono essere prelevate e decodificate per ogni ciclo di clock; tale limite fa sì che, nella maggior parte delle

Appunti di “Calcolatori Elettronici” – Capitolo 7

Autore: Sandro Petrizzelli aggiornamento: 12 luglio 2001 2

macchine dotate di pipelining, non si riesca comunque ad avviare più di una istruzione per ciclo di clock (1).

Ci sono alcune applicazioni, tipicamente scientifiche ed ingegneristiche, in cui si

richiede una grande “potenza di calcolo”, per le quali quindi risultano particolarmente indicate le macchine pipelined ad alta velocità. Tali macchine sono spesso dotate di memorie cache, al fine di ridurre la latenza di lettura delle istruzioni in memoria: come vedremo nel prossimo capitolo, la memoria cache sfrutta i principi di località spaziale e temporale per conservare dinamicamente istruzioni e dati che hanno alta probabilità di essere richiamati a breve dalla CPU, in modo da sostituire gli accessi alla memoria principale (lenti) con quelli alla stessa cache (che sono molto più veloci). Tuttavia, questa ottimizzazione dell’architettura rischia di essere poco sfruttata proprio dalle applicazioni scientifiche di grandi dimensioni: infatti, spesso tali applicazioni richiedono l’accesso, in un dato istante, a voluminosi insiemi di dati significativi, i quali devono essere letti e scritti con frequenza elevata ed in modo scarsamente locale, contrastando così l’effetto della presenza della cache. In alcuni casi, si ottiene una netta diminuzione delle prestazioni della memoria cache e quindi dell’elaborazione in generale.

Un problema come quello appena citato potrebbe essere risolto facendo a meno della memoria cache e studiando più approfonditamente la distribuzione degli accessi alla memoria da parte delle applicazioni “incriminate”, al fine di ottimizzare il progetto sia delle unità di memoria sia anche dei compilatori. Tuttavia, una soluzione efficiente e più radicale risiede nell’uso dei cosiddetti calcolatori vettoriali: la caratteristica distintiva dei calcolatori vettoriale è quella di fornisce funzioni di alto livello che operano direttamente su vettori (cioè liste di numeri).

Consideriamo, per esempio, una operazione vettoriale tipica, come la somma di due vettori ad elementi reali (in virgola mobile), elemento per elemento:

Z = X + Y ↔ Z(1) = X(1)+Y(1)

Z(2) = X(2)+Y(2) ……

Supponendo ad esempio che entrambi i vettori abbiano 64 elementi, un

tradizionale processore scalare richiederebbe l’esecuzione di un loop (ciclo di istruzioni), in cui ogni iterazione provveda a sommare due elementi corrispondenti dei due vettori ed a memorizzare il risultato; dopo 64 iterazioni, l’operazione sarebbe completata (2). I calcolatori vettoriali mettono invece a disposizione, per una operazione di questo tipo, un’unica istruzione, che è appunto una istruzione vettoriale di somma tra vettori.

PPPrrreeegggiii dddeeelllllleee iiissstttrrruuuzzziiiooonnniii vvveeettttttooorrriiiaaallliii Le istruzioni vettoriali sono dotate di svariate importanti proprietà, che

contribuiscono a risolvere la maggior parte dei problemi che abbiamo citato prima:

• il calcolo di ogni risultato è indipendente dal calcolo dei risultati precedenti: ad esempio, quando sommiamo due vettori elemento per elemento, la somma degli elementi di indice i dei due vettori non dipende in alcun modo

1 Ricordiamo che “avviare” una istruzione significa farla “passare” dallo stadio ID allo stato EX, ossia dalla decodifica all’esecuzione vera e propria. 2 Il risultato di una operazione vettoriale è, per definizione, a sua volta un vettore.

Processori vettoriali

aggiornamento: 12 luglio 2001 Autore: Sandro Petrizzelli 3

dalle precedenti somme degli elementi di indice i-1,i-2,…. Questa proprietà consente l’uso di una pipeline di dimensioni molto grandi senza che nasca alcun conflitto di dati;

• una singola istruzione vettoriale specifica un volume elevato di lavoro, essendo generalmente equivalente ad un intero loop su una macchina scalare: ad esempio, sempre nel caso della somma di due vettori, l’istruzione vettoriale di somma equivale alle istruzioni (scalari) che costituiscono il loop per effettuare la somma dei singoli elementi uno dopo l’altro. Questa proprietà riduce, talvolta anche di molto, il numero di istruzioni prelevate dalla memoria (potremmo parlare di banda passante del flusso di istruzioni), attenuando quindi il problema del collo di bottiglia di Flynn precedentemente citato;

• le istruzioni vettoriali che accedono alla memoria presentano una distribuzione nota delle operazioni di accesso, il che consente di ottimizzare la realizzazione della memoria stessa: ad esempio, se gli elementi di un vettore sono memorizzati in celle adiacenti, è possibile ottenere un prelievo molto efficiente (che prevede l’accesso contemporaneo a tutti gli elementi del vettore, anziché uno per volta) con la tecnica dei banchi di memoria interallacciati (3), scegliendo il numero di banchi in modo proporzionato al numero di elementi del vettore nonché anche ai tempi di accesso, come vedremo più avanti;

• infine, dato che un intero loop di istruzioni scalari viene sostituito da una singola istruzione vettoriale, il cui comportamento è completamente predeterminato e noto a priori, non si verifica più il problema dei conflitti di controllo che invece, in un processore non vettoriale, verrebbe prodotto dalle diramazioni poste a conclusione dei loop (4).

L’insieme di queste proprietà fa in modo che le operazioni su vettori (a parità

ovviamente di elementi nei vettori stessi) vengano eseguite molto più velocemente dai processori vettoriali che non dalle analoghe sequenze di istruzioni per macchine scalari. Di conseguenza, i progettisti sono stimolati ad introdurre unità di calcolo di tipo vettoriale, a patto naturalmente che ci siano applicazioni in grado di sfruttarne le potenzialità con sufficiente frequenza.

Tornando per un momento alla prima proprietà tra quelle prima enunciate, si è detto che i calcolatori vettoriali organizzano in modo pipeline il flusso di esecuzione delle operazioni sui singoli elementi dei vettori: tali operazioni sono talvolta definite atomiche (o elementari), per indicare che non sono ulteriormente “scomponibili”. Bisogna inoltre specificare che il flusso di operazioni atomiche non include solo operazioni di tipo aritmetico (somma, prodotto e così via), ma anche accessi alla memoria (caricamento o memorizzazione di elementi) e calcolo di indirizzi.

Un’altra osservazione da fare è che molti calcolatori vettoriali, specialmente quelli destinati ad applicazioni particolarmente avanzate, permettono l’esecuzione contemporanea di più istruzioni vettoriali, realizzando il parallelismo tra operazioni atomiche agenti su elementi distinti. Ad ogni modo, in questo capitolo si concentreremo su calcolatori vettoriali che eseguono istruzioni vettoriali in modo pipeline, sfruttando cioè la sovrapposizione delle operazioni atomiche che compongono l’istruzione vettoriale complessiva.

3 Si veda in proposito il capitolo 8 4 Si veda in proposito il capitolo 6 e, in particolare, le tecniche di ottimizzazione dell’esecuzione dei loop su macchine dotate di pipelining.



Architettura di base dei calcolatori vettoriali: il DLXVArchitettura di base dei calcolatori vettoriali: il DLXV Un calcolatore vettoriale è solitamente composto da due unità di calcolo:

• una unità scalare di calcolo, identica a quella dei processori tradizionali (ad esempio il DLX visto nei capitoli precedenti, sempre con pipelining);

• una unità vettoriale di calcolo, a sua volta suddivisa in un certo numero di sottounità. Ciascuna di tali sottounità presenta una latenza di parecchi cicli di clock: questo consente di ridurre la durata del ciclo di clock e, al contempo, di eseguire, con forte grado di pipelining, operazioni di tipo vettoriale che richiedono tempi di esecuzioni elevati.

La maggior parte delle macchine vettoriali elaborano vettori i cui elementi possono

essere numeri reali in virgola mobile oppure numeri interi o anche valori logici. Noi ci concentreremo sui vettori di numeri reali in virgola mobile.

Si possono distinguere due tipi di architetture vettoriali:

• macchine vettoriali di tipo registro: tutte le operazioni vettoriali, tranne il caricamento e la memorizzazione dei vettori, coinvolgono solo registri (sono perciò assimilabili alle architetture load/store esaminate in precedenza);

• macchine vettoriali di tipo memoria-memoria: tutte le operazioni vettoriali sono da memoria a memoria.

In questa sede consideriamo solo le architetture vettoriali di tipo registro. In particolare, l’architettura vettoriale che useremo nei nostri discorsi, e che

chiameremo DLXV, è schematizzata nella figura seguente:

Memoria centrale

Unità vettoriale dicaricamento/memorizzazione

Registrivettoriali

Registriscalari

Somm./Sottr. in VM

Moltiplicatore in VM

Divisore in VM

Operazioni in AI

Operazioni logiche

Struttura di base dell’architettura vettoriale del DLXV. Questo calcolatore contiene una sottomacchine di tipo scalare che coincide con la macchine DLX vista nei capitoli precedenti. Tutte le unità funzionali sono tipo vettoriale. Nella figura sono mostrate le unità funzionali vettoriali che elaborano vettori a componenti interi e di tipo logico. Il motivo per cui queste unità funzionali sono incluse nel DLXV è che sono unità del tutto standard, presenti cioè nella

maggior parte delle macchine vettoriali più comuni.



Possiamo subito dire che, in questa architettura, si distingue una sottostruttura per le operazioni in aritmetica intera, coincidente con quella già vista per il DLX, cui si aggiunge una sottostruttura vettoriale che è semplicemente l’estensione naturale del DLX per le operazioni vettoriali.

In particolare, si individuano i seguenti componenti funzionali fondamentali:

• registri vettoriali: un registro vettoriale è semplicemente un intero banco di registri ordinari, di dimensioni prefissate, da usare per la memorizzazione di un vettore. Si suppone che il DLXV abbia 8 registri vettoriali, ognuno dei quali destinato ad accogliere vettori da 64 elementi a 64 bit (ad esempio numeri reali in virgola mobile in doppia precisione);

• unità funzionali vettoriali: si suppone che il DLXV abbia 5 unità funzionali vettoriali (sommatore/sottrattore in VM, moltiplicatore in VM, Divisore in VM, ALU per operazioni in aritmetica intera, ALU per operazioni logiche). Ciascuna di esse è dotata di pipelining di grado massimo ed è in grado di avviare una nuova operazione ad ogni ciclo di clock;

• alle unità vettoriali si affianca una unità di controllo per la rilevazione dei conflitti: questa è necessaria per rilevare sia i conflitti di accesso alle unità funzionali (conflitti strutturali) sia quelli per l’accesso ai registri (conflitti di dati);

• unità vettoriale di caricamento/memorizzazione: è l’unità funzionale che si occupa di caricare e memorizzare interi vettori da o verso la memoria. Le istruzioni vettoriali di caricamento e di memorizzazione del DLXV vengono eseguite con grado di pipelining completo, in modo che la banda passante del trasferimento (tra registri e memoria) raggiunga il valore di una parola per ciclo di clock (a regime, una volta cioè esaurito un tempo di start-up iniziale);

• registri scalari: tali registri vengono comunque inclusi nel DLXV in quanto esistono operazioni vettoriali che coinvolgono sia scalari sia vettori (ad esempio, la somma di uno scalare ad un vettore); di conseguenza, le unità funzionali vettoriali possono usare, come dati in ingresso, non solo i vettori provenienti dai registri vettoriali, ma anche gli scalari provenienti dai registri scalari. Questi ultimi possono tra l’altro essere usati anche per contenere indirizzi da passare all’unità vettoriale di caricamento/memorizzazione. Si suppone che i registri scalari siano 32 di tipo generale e 32 per la virgola mobile, per cui non sono altro che i registri di cui era dotato il DLX dei capitoli precedenti.

Riepilogando il tutto, il DLXV possiede:

• 8 registri vettoriali, da 64 bit ciascuno;

• 32 registri scalari di uso generale, da 32 bit ciascuno;

• 32 registri scalari per la virgola mobile, da 64 bit ciascuno;

• 5 unità funzionali vettoriali, di cui tre per la virgola mobile (moltiplicazione, divisione, somma), una per l’aritmetica intera (somma) ed una per le funzioni logiche;

• 1 unità vettoriale di caricamento/memorizzazione



IIIssstttrrruuuzzziiiooonnniii vvveeettttttooorrriiiaaallliii dddeeelll DDDLLLXXXVVV Le istruzioni vettoriali del DLXV hanno lo stesso nome delle corrispondenti

istruzioni scalari del DLX, con in più il suffisso “V”: ad esempio, l’istruzione ADDV è la somma vettoriale di due vettori a componenti reali in doppia precisione.

Le istruzioni vettoriali del DLXV agiscono su vettori a componenti reali in virgola mobile (in singola e doppia precisione), a componenti interi ed a componenti logici. Nella seguente tabella sono riportate, per brevità, solo le istruzioni in virgola mobile in doppia precisione:

Tipo Istruzione / Codice Operativo

Operandi

Significato dell’istruzione

Istruzioni di caricamento/memorizzazione registri LV V1,R1 Caricamento nel registro vettoriale V1 dalla memoria, a partire

dall’indirizzo contenuto in R1 LVI V1,(R1+V2) Caricamento nel registro vettoriale V1 dalla memoria, a partire

dall’indirizzo contenuto in R1+V2(i), dove V2 è un vettore di indici

SV R1,V1 Memorizzazione nel registro vettoriale V1 in memoria, a partire dall’indirizzo contenuto in R1

SVI (R1+V2),V1 Memorizzazione nel registro vettoriale V1 in memoria, a partire dall’indirizzo contenuto in R1+V2(i), dove V2 è un vettore di indici

LVWS V1,(R1+R2) Caricamento di V1 dall’indirizzo contenuto in R1 con sfasamento in R2, cioè R1+i×R2

SVWS (R1+R2),V1 Memorizzazione di V1 all’indirizzo contenuto in R1 con sfasamento in R2, cioè R1+i×R2

MOVI2S VLR,R1 Trasferimento del valore di R1 nel registro di dimensione dei vettori

MOVS2I R1,VLR Trasferimento del valore del registro di dimensione dei vettori in R1

MOVF2S VM,F0 Trasferimento del valore di F0 (5) nel registro di mascheratura dei vettori

MOVS2F F0,VM Trasferimento del valore del registro di mascheratura dei vettori in F0

Istruzioni aritmetiche vettoriali ADDV V1,V2,V3 Somma dei vettori V1 e V2 con risultato in V3 ADDSV V1,F0,V2 Somma del vettore V2 con lo scalare F0, con risultato in V1 SUBV V1,V2,V3 Sottrazione del vettore V3 da V2 con risultato in V1 SUBVS V1,V2,F0 Sottrazione dello scalare F0 dal vettore V2, con risultato in V1 SUBSV V1,F0,V2 Sottrazione del vettore V2 dallo scalare F0, con risultato in V1 MULTV V1,V2,V3 Moltiplicazione degli elementi del vettore V2 per quelli di V3, con

risultato in V1 MULTSV V1,F0,V2 Moltiplicazione dello scalare F0 per gli elementi del vettore V2,

con risultato in V1 DIVV V1,V2,V3 Divisione degli elementi del vettore V2 per quelli di V3, con

risultato in V1 DIVVS V1,V2,F0 Divisione degli elementi del vettore V2 per lo scalare F0, con

risultato in V1 DIVSV V1,F0,V2 Divisione dello scalare F0 per gli elementi di V2, con risultato in

V1 Istruzioni varie

CVI V1,R1 Creazione di un vettore di indirci, memorizzando 0,1×R1,2×R1,…,63×R1 nel registro vettoriale V1

S_V V1,V2 Confronto (EQ,NE,GT,LT,GE,LE), cioè uguaglianza, disuguaglianza, maggioranza stretta, minoranza stretta,

5 Ricordiamo che F0 è un registro in virgola mobile in singola precisione (quindi da 64 bit).



S_SV F0,V1 disuguaglianza, maggioranza stretta, minoranza stretta, maggioranza lata e minoranza lata, tra gli elementi di V1 e quelli di V2. Se il confronto ha esito positivo, si aggiorna ad 1 il bit corrispondente del vettore di bit, mentre altrimenti lo si aggiorna a 0. Il vettore di bit è memorizzato nel registro di mascheratura dei vettori (VM). L’istruzione S_SV esegue la stessa operazione, ma usando un unico valore scalare come primo operando, da confrontare con tutti gli elementi del vettore usato come secondo operando

POP R1,VM Conteggio dei bit di valore 1 nel registro di mascheratura dei vettori e memorizzazione del risultato nel registro R1

CVM Inizializzazione al valore 1 di tutti i bit del registro di mascheratura dei vettori

In questa tabella sono stati considerati due registri speciali, denominati VLR

(registro di dimensione del vettore) e VM (registro maschera), di cui parleremo più avanti.

Le caratteristiche delle varie istruzioni sono abbastanza semplici da comprendere; in particolare, si nota che le operazioni vettoriali possono essere applicate ad operandi “organizzati” in due modi distinti:

• alcune istruzioni prevedono operandi situati in coppie di registri vettoriali

(ad esempio ADDV);

• altre istruzioni prevedono un operando vettoriale (situato perciò in un registro vettoriale) ed uno scalare (situato in un registro scalare); in questi casi, il nome dell’istruzione riceve il suffisso “SV” (Scalar Vector): ad esempio, l’istruzione ADD-SV è la somma di un vettore in virgola mobile in doppia precisione con uno scalare in virgola mobile in doppia precisione. Naturalmente, questo tipo di istruzioni prevedono che l’operazione scalare (operazione atomica) che corrisponde all’operazione vettoriale venga iterata su tutti i componenti dell’operando di tipo vettore, mentre invece il secondo operando (quello scalare) rimane fisso in ogni iterazione.

Le istruzioni vettoriali producono sempre un risultato di natura vettoriale, che

viene memorizzato in uno dei registri vettoriali. I codici mnemonici LV ed SV denotano le istruzioni vettoriali di caricamento e di

memorizzazione: il primo operando è il registro vettoriale da caricare o da memorizzare, mentre il secondo operando è un registro scalare di uso generale,, contenente l’indirizzo iniziale del vettore in memoria. Si notano anche due particolari istruzioni, LVWS (caricamento con passo specificato) e SVWS (memorizzazione con passo specificato), di cui parleremo in seguito.

Esempio: loop DAXPYEsempio: loop DAXPY Per comprendere a pieno i concetti esposti fino ad ora sulle macchine vettoriali,

possiamo far riferimento ad un esempio concreto. Supponiamo perciò di dover eseguire la seguente operazione vettoriale:

Y = a × X + Y

dove naturalmente X ed Y sono due vettori (inizialmente residenti in memoria) ed a uno scalare (anch’esso inizialmente in memoria).



Si tratta del cosiddetto loop DAXPY (Double-precision A * X Plus Y) (6). Supponiamo che il numero di elementi dei vettori coinvolti eguagli esattamente il numero di elementi memorizzabili in ciascun registro vettoriale del DLXV: X ed Y sono dunque vettori ciascuno da 64 elementi reali in doppia precisione (7).

Se dovessimo eseguire quella operazione sul DLX tradizionale, avremmo un loop del tipo seguente (8):

LD F0,a ; caricamento dello scalare in F0 ADDI R4,Rx,#512 ; ultimo indirizzo da caricare Loop: LD F2,0(Rx) ; caricamento di X(i) MULTD F2,F0,F2 ; a×X(i) LD F4,0(Ry) ; caricamento di Y(i) ADDD F4,F2,F4 ; a×X(i)+Y(i) SD F4,0(Ry) ; memorizzazione in Y(i) ADDI Rx,Rx,#8 ; incremento dell’indice per X ADDI Ry,Ry,#8 ; incremento dell’indice per Y

SUB R20,R4,Rx ; calcolo dell’estremo superiore BNZ R20,Loop ; condizione di terminazione Questo codice utilizza evidentemente due registri, Rx ed Ry, come indici

rispettivamente di X ed Y e quindi assume che tali registri siano stati pre-caricati con gli indirizzi iniziali rispettivamente di X ed Y.

Se invece volessimo scrivere l’analogo codice per il DLXV, avremmo quanto segue: LD F0,a ; caricamento dello scalare in F0

LV V1,Rx ; caricamento del vettore X MULTV V2,F0,V1 ; prodotto scalare×vettore LV V3,Ry ; caricamento del vettore Y ADDV V4,V2,V3 ; somma vettoriale di a×X ed Y SV Ry,V4 ; memorizzazione di a×X+Y Notiamo subito l’importanza di effettuare la moltiplicazione (istruzione MULTV)

prima del caricamento del vettore Y (prima istruzione LV): questo consente di non avere conflitto di struttura tra le due istruzioni LV, che altrimenti (nel caso cioè fossero state consecutive) si sarebbero trovate a voler usare contemporaneamente il bus. Una simile ottimizzazione può essere a cura del programmatore data la semplicità del codice, ma, in casi più complessi, può essere affidata al compilatore.

Possiamo ora fare una serie di importanti confronti tra i due codici ottenuti, uno per il DLX e uno per il DLXV:

• la prima cosa che osserviamo è che le linee guida usate per la scrittura dei

loop sono (ovviamente) le stesse: per prima cosa si carica lo scalare (la prima istruzione è uguale per entrambi i loop); successivamente, si carica l’elemento del vettore X (nel caso scalare) oppure l’intero vettore X (nel caso vettoriale); si esegue poi il prodotto con lo scalare, dopodiché si esegue la somma con il corrispondente elemento di Y (nel caso scalare) o con l’intero Y (nel caso vettoriale); infine, si memorizza il risultato, dopodiché, nel caso scalare, è prevista una diramazione che controlli se il loop è terminato o deve proseguire con un’altra iterazione; tale diramazione è assente nel caso

6 Esiste anche l’analoga versione SAXPY, che coinvolge numeri reali in singola precisione 7 Quella sul numero di elementi dei vettori è una limitazione che più avanti impareremo ad eliminare. 8 Si riprendano, in proposito, le considerazioni fatte nel capitolo 6 circa l’operazione di somma di un vettore e di uno scalare



vettoriale, in quanto le operazioni compiute hanno già riguardato tutti gli elementi dei vettori coinvolti;

• la differenza maggiore tra le due soluzioni può essere individuata nel fatto che la macchina vettoriale riduce drasticamente il numero di istruzioni caricate dalla memoria: il DLXV, infatti, preleva solo le 6 istruzioni prima riportate, mentre invece si verifica facilmente che il DLX, a seguito delle 64 iterazioni, preleva 2+9×64=578 istruzioni. Chiaramente, questa differenza così netta è dovuta sia al fatto che ogni singola istruzione del DLXV lavora su dati formati da ben 64 elementi, sia anche dal fatto che il loop del DLX contiene quasi il doppio delle istruzioni rispetto al codice del DLXV;

• un’altra differenza è data dalle dipendenze tra le istruzioni: nel loop del DLX, ogni istruzione ADDD deve attendere l’istruzione MULTD (conflitto di dati su F2), così come ogni istruzione SD deve attendere l’istruzione ADDD (conflitto su F4); nel DLXV, invece, ogni istruzione vettoriale lavora su tutti gli elementi del vettore, in modo indipendente, per cui gli stalli nella pipeline del DLXV si verificano solo una volta per ogni operazione vettoriale anziché una volta per ogni elemento dei vettori. Nell’esempio, la frequenza di stallo della pipeline del DLX è dunque 64 volte maggiore di quella del DLXV. Questa considerazione mostra che, anche supponendo di riuscire ad eliminare gli stalli del DLX tramite la schedulazione dinamica e lo srotolamento del loop, comunque il valore di banda passante di istruzioni del DLXV non è assolutamente raggiungibile dal DLX.

TransitoriTransitorio di attivazione e frequenza di interazione delle o di attivazione e frequenza di interazione delle istruzioni vettorialiistruzioni vettoriali

Consideriamo il loop DAXPY esaminato nel paragrafo precedente. Vogliamo calcolare il tempo richiesto dal DLXV per eseguire il programma.

Il punto di partenza consiste nel dire che il tempo di esecuzione di una qualsiasi operazione vettoriale è la somma di due componenti:

• il transitorio di attivazione è l’intervallo di tempo derivante dalla latenza,

dovuta al pipelining, delle operazioni vettoriali; esso è determinato essenzialmente dalla dimensione della pipeline dell’unità funzionale interessata. Ad esempio, una latenza di 10 cicli di clock significa sia che l’operazione richiede 10 cicli di clock sia anche che la pipeline è di dimensione 10 (9). In pratica, si tratta del tempo di start-up che abbiamo visto per la pipeline del DLX;

• la frequenza di interazione è l’intervallo di tempo per ogni risultato prodotto, una volta che l’esecuzione dell’istruzione vettoriale è andata a regime. Generalmente, si ha un risultato per ciclo di clock, anche se alcuni supercalcolatori sono dotati di istruzioni vettoriali che possono produrre due o anche più risultati per ciclo di clock.

9 Si tenga conto che, nei calcoli delle prestazioni delle operazioni vettoriali, si usano generalmente i cicli di clock come unità di misura e noi ci adeguiamo a questa prassi.



Quindi, l’intervallo di tempo T per completare una singola operazione vettoriale che agisce su vettori di dimensione n vale

T = Transitorio di attivazione + n ×× Frequenza di iterazione

Facciamo subito un esempio numerico. Supponiamo che il transitorio di

attivazione di una moltiplicazione vettoriale valga 10 cicli di clock. Supponiamo inoltre che, dopo l’attivazione, la frequenza di iterazione sia di 1 ciclo di clock. Per calcolare l’intervallo di tempo necessario al calcolo di un intero vettore da 64 elementi, ci basta scrivere che

T = 10 + 64×1 = 74 cicli di clock

Quindi, l’istruzione iniziale ha un transitorio iniziale di 10 cicli di clock, dopodiché

prende a “sfornare” un risultato scalare ad ogni ciclo di clock. Sono richiesti 74 cicli di clock per l’intero vettore. Se dividiamo per la dimensione del vettore, otteniamo il numero medio di cicli di clock per ogni singolo risultato (ossia per ogni elemento del vettore): 74/64=1.16 cicli di clock per risultato.

Sottolineiamo che, in base alle ipotesi fatte, quella appena calcolata è la massima prestazione ottenibile, ossia potremmo dire la prestazione ideale.

La relazione appena utilizzata nell’esempio mostra dunque una dipendenza lineare del tempo di esecuzione T dal transitorio di attivazione e dalla frequenza di iterazione. Tale relazione si può efficacemente riassumere in forma grafica:

Numero totaledei cicli di clockper un vettoredi 64 elementi

Costo di attivazioneper ciclo di clock

4 cicli di clockper risultato

2 cicli di clockper risultato

1 ciclo di clockper risultato

2 50

In questo diagramma viene riportato il tempo totale di esecuzione (espresso in cicli

di clock e calcolato per un vettore da 64 elementi, come nell’esempio) in funzione del transitorio di attivazione, riportato come variabile indipendente sull’asse x; in particolare, si considera un transitorio di attivazione variabile da 2 a 50 cicli di clock. Il diagramma evidenzia che l’effetto del transitorio di attivazione è molto maggiore nelle macchine vettoriali veloci rispetto a quelle lente:

• all’aumentare del tempo di attivazione da 2 a 50 cicli di clock, l’operazione

che viene eseguita con frequenza di iterazione pari ad 1 risultato (scalare) per ciclo di clock (linea più in basso) vede aumentare il suo tempo totale di esecuzione di un fattore pari al 75%; essa risente dunque molto del tempo di attivazione;



• con la stessa variazione del tempo di attivazione, l’operazione con frequenza di iterazione di un risultato ogni 4 cicli di clock (linea più in alto) vede invece aumentare il suo tempo di esecuzione di un fattore pari al 20%.

L’operazione più penalizzata risulta essere dunque quella più veloce, come è

ovvio che sia, in quanto per essa il tempo di attivazione assume un peso più rilevante rispetto ad una operazione molto più lenta.

Detto questo, dobbiamo chiederci quali fattori determinano il transitorio di attivazione e la frequenza di iterazione. A tal proposito, consideriamo dapprima le operazioni che non eseguono accessi a memoria, ossia le operazioni registro-registro:

• tali operazioni hanno un transitorio di attivazione necessariamente pari (in

termini di cicli di clock) alla dimensione della pipeline dell’unità funzionale vettoriale che deve eseguirle, proprio perché questo è il tempo richiesto per ottenere il primo risultato scalare (dopodiché si va a regime). Nell’esempio che abbiamo fatto prima, la dimensione della pipeline dell’unità funzionale coinvolta (il moltiplicatore in virgola mobile) era 10 e quindi il transitorio di attivazione era di 10 cicli di clock. In effetti, però, possono esistere anche altri fattori che influiscono sul transitorio di attivazione;

• per quanto riguarda, invece, la frequenza di iterazione, essa è determinata dalla frequenza con cui l’unità funzionale vettoriale coinvolta può accettare un nuovo operando. Evidentemente, se è dotata di pipelining in modo completo, potrà accettare un nuovo operando ad ogni ciclo di clock, determinando così una frequenza di iterazione di un risultato ad ogni ciclo di clock, così come nell’esempio che abbiamo fatto.

Si è detto dunque che il transitorio di attivazione di una operazione comprende

quanto meno la latenza totale dell’unità funzionale che esegue l’operazione stessa: nel caso di una moltiplicazione, ad esempio, si tratterà della latenza totale del moltiplicatore vettoriale in virgola mobile. Allora, se vogliamo ottenere, per una data operazione, una frequenza di iterazione di un risultato scalare per ogni ciclo di clock, dobbiamo fare in modo che la dimensione della pipeline soddisfi ad un requisito ben preciso: deve essere pari al numero di cicli di clock richiesti dall’operazione stessa. Ad esempio, se una operazione richiede 10 cicli di clock, dovrà essere eseguita su una pipeline di dimensione 10. In termini analitici, questa condizione si esprime nel modo seguente:

=

clock di ciclo del Tempo

calcolo di totaleTempo pipeline della Dimensione

A secondo membro sono state usate le cosiddette parentesi di Gauss, , che

denotano il minimo intero superiore all’argomento. Ad esempio, se quel rapporto valesse 9.2, il minimo intero superiore sarebbe 10.

In base a quella relazione, la dimensione della pipeline dipende dal tempo totale di calcolo (e quindi dalla complessità dell’operazione nonché dall’unità funzionale che la realizza) e dalla durata del periodo di clock. Negli odierni calcolatori, si trovano dimensioni delle pipeline delle unità funzionali variabili tra 2 e addirittura 20 stadi, con transitori di attivazione compresi tra 4 ed 8 cicli di clock.



Specifiche delle unità funzionali del DLXVSpecifiche delle unità funzionali del DLXV Nel caso del DLXV, si suppone che tutte le unità funzionali siano dotate di

pipelining in modo completo. In particolare, le dimensione delle pipeline sono:

• 6 cicli di clock per la somma in virgola mobile

• 7 cicli di clock per la moltiplicazione in virgola mobile. Se una operazione vettoriale dipende da un calcolo non ancora completato

(conflitto di dati), deve essere sospesa e si aggiungono 4 cicli di clock di penalizzazione: questo è infatti il tempo ritenuto necessario per scrivere e poi leggere gli operandi richiesti. Ad esempio, consideriamo due operazioni vettoriali consecutive, caratterizzate dal fatto che il primo risultato scalare della seconda dipende dall’ultimo risultato scalare della prima: in questo caso, il tempo di attivazione della seconda operazione è necessariamente pari al tempo di esecuzione della prima operazione.

In assenza di dipendenze di dati, sul DLXV (come su molti altri calcolatori vettoriali) è possibile avviare, senza alcuna penalizzazione o ritardo, operazioni vettoriali che facciano uso di unità funzionali distinte. Operazioni vettoriali indipendenti si possono anche sovrapporre in modo completo. Quindi, quando le operazioni sono distinte ed indipendenti, il DLXV le può sovrapporre, esattamente come il DLX fa con le operazioni scalari in aritmetica intera ed in virgola mobile.

Dato che il DLXV è dotato di pipelining in modo completo, la frequenza di iterazione di tutte le operazioni vettoriali è pari ad 1. Nonostante questo, non è possibile avviare una sequenza di operazioni vettoriali al ritmo di una per ciclo di clock, a causa proprio dei transitori di attivazione. Questa limitazione è sintetizzata dal concetto di frequenza sostenibile: essa si riferisce al tempo richiesto per il calcolo di un singolo risultato scalare nel contesto di operazioni vettoriali dipendenti. In pratica, un elemento scalare non viene immaginato come il risultato di un’unica operazione vettoriale, ma come il risultato di una successione di operazioni vettoriali tra loro dipendenti; di conseguenza, l’intervallo di tempo per il calcolo di un singolo elemento è pari alla somma degli intervalli di tempo richiesti da ciascuna operazione della sequenza per produrre un elemento.

UUUnnniiitttààà dddiii cccaaarrriiicccaaammmeeennntttooo///mmmeeemmmooorrriiizzzzzzaaazzziiiooonnneee Consideriamo ora le “prestazioni” dell’unità vettoriale di

caricamento/memorizzazione, facendo sempre riferimento al DLXV. Nel caso di un caricamento di un vettore dalla memoria in un registro vettoriale,

il transitorio di attivazione è il tempo richiesto per caricare la prima parola; successivamente, se la parte restante del vettore può essere fornita senza bisogno di alcuna sospensione, allora la frequenza di iterazione sarà pari alla frequenza con cui verranno prelevate e poste nel registro le nuove parole: ad esempio, se la memoria è progettata in modo da fornire una parola ad ogni ciclo di clock, la frequenza di iterazione è pari ad 1.

Nel caso del DLXV, si ipotizza che il transitorio di attivazione per una operazione vettoriale di caricamento sia di 12 cicli di clock: è un valore medio rispetto a quelli che si hanno sui calcolatori reali, ma segnaliamo che, in taluni di questi calcolatori, si arriva addirittura a 50 cicli di clock.



Se invece consideriamo una operazione vettoriale di memorizzazione (quindi da registro a memoria), in linea di massima non è presente il transitorio di attivazione, dato che le memorizzazioni non producono direttamente risultati. Al contrario, quando una istruzione deve attendere che una memorizzazione venga completata, può darsi che essa debba essere ritardata di un intervallo di tempo pari ad una frazione della latenza o addirittura a tutta la latenza della memorizzazione.

Riepilogando, la seguente tabella riassume le penalizzazioni dei transitori di attivazione delle operazioni vettoriali del DLXV:

Operazione vettoriale

Penalizzazione di avviamento

(cicli di clock) Somma vettoriale 6 Moltiplicazione vettoriale 7 Divisione vettoriale 20 Caricamento vettoriale 12 Memorizzazione vettoriale 0

A queste specifiche bisogna aggiungere, come detto in precedenza, che, quando

una istruzione vettoriale dipende da una istruzione vettoriale precedente che non è stata ancora completata, la penalizzazione del transitorio di attivazione va aumentata di 4 cicli di clock.

Restando alle operazioni di caricamento/memorizzazione vettoriale, per ottenere una frequenza di iterazione pari ad una parola caricata o memorizzata per ogni ciclo di clock, dobbiamo fare in modo che la memoria possa produrre una simile quantità di dati. Generalmente, questo lo si ottiene suddividendo la memoria in banchi (10): ogni banco è praticamente un piccola memoria separata, a cui si può fare riferimento in parallelo ad altri banchi.

GGGeeessstttiiiooonnneee dddeeeiii bbbaaannnccchhhiii dddiii mmmeeemmmooorrriiiaaa iiinnn uuunnn cccaaalllcccooolllaaatttooorrreee vvveeettttttooorrriiiaaallleee Esistono due possibili tecniche per gestire i banchi di memoria e ottenere una

frequenza di una parola trasmessa ad ogni ciclo di clock; per comprendere tali tecniche, consideriamo per semplicità una operazione di caricamento di un vettore dai banchi in un registro vettoriale della CPU:

• la prima tecnica consiste nel sincronizzare tutti i banchi e nell’usarli in

parallelo: una volta indirizzati i vari banchi (tramite il bus indirizzi), ognuno di essi memorizza il dato richiesto in un proprio buffer ed il contenuto dei vari buffer viene poi riversato in modo seriale (cioè un buffer per volta) sul bus dati, per il trasferimento nella CPU; mentre le parole vengono trasferite dai buffer sul bus, si procede subito ad indirizzare le parole successive, in modo che, al termine del primo trasferimento, siano già pronte le nuove parole da trasferire e così via fino al trasferimento di tutti i dati richiesti;

• la seconda possibile tecnica è quella di sfruttare lo sfasamento indipendente dei banchi: al primo accesso, il riferimento viene svolto in parallelo a tutti i banchi e le parole vengono trasferite una alla volta; solo quando un banco ha trasmesso la propria parola, esso può iniziare a

10 Si veda, in proposito, quanto diremo anche nel capitolo sulla memoria



ricercare la successiva (mentre invece, nella precedente tecnica, poteva ricercarla anche prima della trasmissione, data la presenza del buffer temporaneo). Perciò, le operazioni dei banchi si sfasano e mantengono lo sfasamento in tutte le operazioni successive.

M0 M1 M2 M3

Bus dati a 32 bit

Indirizzo

DECOD

CONT

clock

Indirizzo di memoria (generato dalla CPU)

n - m - 2 m 0 0

Schematizzazione di una memoria realizzata a banchi

Dato l’indirizzo di memoria generato dalla CPU, esiste un campo di m bit che individua univocamente un banco (11): tramite l’azione combinata di un contatore e di un decoder, viene di volta in volta selezionato un unico banco di memoria, al quale viene conferita la possibilità di accedere al bus, in lettura o in scrittura (12). Il contatore, infatti, viene incrementato di 1 ad ogni ciclo di clock e seleziona perciò il banco di volta in volta successivo. Il valore iniziale del contatore è quello corrispondente al banco contenente il primo elemento da trasferire. La prima parte dell’indirizzo di memoria, invece, individua una parola all’interno del blocco selezionato: essa è lunga n-m-2, dove n è la lunghezza complessiva dell’indirizzo (ad esempio 32 bit). Infine, gli ultimi due bit dell’indirizzo sono sempre a 0 se si ipotizza una memoria organizzata (nel suo complesso) a parole e con accessi sempre allineati.

In ogni caso, il vantaggio è che, a regime, ad ogni ciclo di clock possiamo trasferire

sul bus una parola, dato che essa è stata già selezionata. La prima tecnica (sincronizzazione degli accessi) richiede l’impiego di un numero

maggiore di registri, ma è dotata di un controllo senz’altro più semplice di quella che sfrutta lo sfasamento indipendente dei banchi.

Ipotizzando che ciascun banco di memoria abbia parole in doppia precisione (64 bit), esiste un vincolo fondamentale per mantenere una frequenza di iterazione di una parola per ciclo di clock, a prescindere dalla tecnica usata per realizzare i banchi: deve infatti sempre risultare

11 Se m’ è il numero di banchi, allora ovviamente m=log2m’. Ad esempio, per indirizzare m’=4 banchi servono m=2 bit. 12 In particolare, le linee che partono dal decoder sono tutte a 0 tranne quella che individua il banco selezionato. Tali linee sono dette di chip select, proprio perché selezionano (mettendo la sua uscita a bassa impedenza) un dato banco (situato su un proprio chip) per l’accesso al bus.



Numero di banchi di memoria ≥ Tempo di accesso ai banchi (in cicli di clock) Vediamo di dimostrare il perché di questa relazione. Consideriamo ad esempio l’operazione di caricamento di un vettore da 64 elementi

in doppia precisione. Indichiamo l’indirizzo del generico elemento del vettore con ki : esso sarà dato evidentemente da

ki = Indirizzo iniziale del vettore + (i-1) × d

dove d è la distanza tra elementi adiacenti del vettore. Per elementi in doppia precisione, memorizzati adiacenti in memoria, tale distanza è chiaramente pari alla loro dimensione, ossia 8 byte (64 bit) (13).

Gli indirizzi degli elementi del vettore cui accedere solo quelli che soddisfano alla seguente condizione:

ki mod (numero del banco) = 0 Esaminiamo allora il primo accesso a ciascun banco: dopo un intervallo di tempo

pari al tempo di accesso alla memoria (14), che nel DLXV è stato supposto pari a 12 cicli di clock, sarà stata prelevata una parola in doppia precisione da tutti i banchi di memoria e si potrà così cominciare ad inviare le parole ai registri vettoriali (15): tali parole vengono inviate, tramite il bus dati, una alla volta in modo seriale, iniziando dal banco con l’indirizzo inferiore (16). Se i banchi sono sincronizzati, in ciascuno di essi l’accesso successivo inizia immediatamente, in quanto la parola da trasferire è stata posta nell’apposito buffer; se invece i banchi sono sfasati, allora non vengono usati buffer e quindi ogni banco può avviare l’accesso successivo solo dopo che la parola selezionata è stata effettivamente trasmessa. In entrambi i casi, comunque, il generico banco inizia l’accesso successivo ad un indirizzo superiore rispetto a quello precedente, di una quantità pari a 8×N, dove N è il numero dei banchi.

A questo punto, dato che, per ipotesi, il tempo di accesso alla memoria, espresso in cicli di clock, è inferiore al numero di banchi e dato che le parole vengono trasmesse secondo un ordinamento di tipo “round-robin”, alla frequenza di una trasmissione per ciclo di clock, ogni banco termina l’accesso prima che il suo turno di trasmettere si ripresenti e questo garantisce che, quando il turno arriva, il dato da trasmettere sia già pronto. Questo dimostra dunque la validità della relazione prima citata.

Per semplificare il meccanismo di indirizzamento, di solito viene scelto un numero di banchi che sia una potenza di 2. Ad esempio, supponiamo di voler prelevare un vettore di 64 elementi; supponiamo che il tempo di accesso alla memoria sia di 6 cicli di clock: in base alla relazione citata nel precedente paragrafo, deduciamo immediatamente che sono necessari almeno 6 banchi; tuttavia, avendo detto che è sempre opportuno avere un numero di banchi che sia una potenza di due, ne prendiamo 8.

13 Vedremo più avanti come cambiano le cose quando gli elementi di un vettore non sono memorizzati in celle adiacenti. 14 E’ il tempo che intercorre tra l’istante in cui la CPU pone l’indirizzo del dato richiesto sul bus degli indirizzi e l’istante in cui la prima parola richiesta viene collocata sul bus dei dati. 15 Si suppone che tutti gli accessi siano allineati 16 Serve dunque un tempo di 12+1+1+1=15 colpi di clock per ogni “ciclo” di accesso ai banchi.



Problematiche realizzative: lunghezza e passo dei vettoriProblematiche realizzative: lunghezza e passo dei vettori Nei programmi applicativi per processori vettoriali, si presentano di frequente

due problemi:

• in primo luogo, i vettori potrebbero non avere dimensione multipla di 64;

• in secondo luogo, gli elementi di uno stesso vettore potrebbero non essere memorizzati in celle adiacenti.

CCCooonnntttrrrooollllllooo dddeeellllllaaa dddiiimmmeeennnsssiiiooonnneee dddeeeiii vvveeettttttooorrriii Un calcolatore vettoriale come il DLXV (cioè di tipo registro) si adatta

perfettamente all’elaborazione di vettori la cui dimensione sia un multiplo del numero di elementi contenuti in ciascun registro vettoriale (=64). Tuttavia, non necessariamente tale dimensione è quella dei vettori usati nei programmi, il che rappresenta ovviamente un “problema” da affrontare in sede sia di progettazione sia di compilazione. Non solo, ma la lunghezza effettiva dei vettori usati nei programmi spesso non è nota al momento della compilazione.

Per renderci conto di questa problematica, consideriamo il seguente codice per l’esecuzione del ciclo DAXPY:

do label i = 1,n

label Y(i) = a * X(i) + Y(i) Questo ciclo (scritto in Fortran), ha una dimensione effettiva dei vettori legata al

valore n: tale valore potrebbe benissimo essere sconosciuto al momento della compilazione (ad esempio se è il risultato di precedenti elaborazioni, nell’ambito ovviamente dello stesso programma) oppure potrebbe essere un parametro del sottoprogramma che esegue quel ciclo, soggetto perciò a variazioni durante l’esecuzione.

Per gestire simili situazioni, nel DLXV si adotta la seguente soluzione: si considera un registro di dimensione dei vettori (VLR, Vector Length Register), nel quale viene sempre memorizzata la dimensione di ogni operazione vettoriale (inclusi i caricamenti e le memorizzazioni), ossia il numero di elementi scalari su cui tale operazione dovrà operare.

E’ ovvio, del resto, che il valore contenuto nel VLR non può mai superare la dimensione fisica dei registri vettoriali (detta MVL, ossia Maximum Vector Length), pari a 64 nel caso del DLXV: questo vincolo fa sì che il problema della dimensione variabile dei vettori sia risolto completamente quando tale dimensione risulta inferiore a 64, mentre invece resta insoluta la questione di dimensioni superiori a 64.

Tecnica della riduzione a blocchi Per affrontare le situazioni in cui i vettori sono di dimensione superiore al

parametro MVL, esistono varie possibilità. Una di queste è nota come tecnica di riduzione a blocchi. Si tratta di una soluzione software, nel senso che deve essere applicata al programma in sede di compilazione: consiste nel suddividere una singola operazione vettoriale in una sequenza di operazioni vettoriali che operano su



sottoblocchi del vettore originale, avanti tutti dimensione non superiore al parametro MVL.

Possiamo comprendere facilmente questa tecnica con un esempio, considerando nuovamente il ciclo DAXPY. A prescindere dal fatto che si conosca già a priori o meno la dimensione dei vettori coinvolti, la tecnica di riduzione e blocchi fa sì che il ciclo venga riscritto nel modo seguente (usiamo sempre il Fortran):

base = 1 VL = n mod MVL /* resto del vettore */ do Lab1 j = 0, (n/MVL) /* loop esterno */ do Lab2 i = base,base+VL-1 /* ciclo di dim. VL */ Y(i) = a*X(i)+Y(i) /* corpo */

Lab2 continue base = base + VL /* fine del sottoblocco */ VL = MVL /* reinizializzazione dimensione */ Lab1 continue

Analizziamo questo ciclo:

• la prima istruzione serve semplicemente ad inizializzare il valore dell’indice i, che serve a “puntare” i vari elementi dei vettori X ed Y;

• la seconda istruzione calcola il resto intero della divisione tra la dimensione n dei vettori coinvolti e la dimensione dei registri vettoriali (64 nel caso del DLXV): se l’esito dell’operazione è nullo, significa che n è un multiplo intero di 64, mentre invece, in caso contrario, significa che n=MVL××k+VL, dove k è un numero intero;

• la conoscenza di VL consente di suddividere il ciclo complessivo in due sottocicli: l’effetto del ciclo esterno (quello di indice j) è quello di suddividere il vettore complessivo in k sottoblocchi di dimensione pari a VML, tranne il primo sottoblocco, la cui dimensione è VL; ogni sottoblocco viene poi elaborato dal ciclo interno (quello di indice i).

La suddivisione del vettore in sottoblocchi è mostrata nella figura seguente:

0 1 2 ... k = n/MVL

Vettore originale

VLelementi

Una volta illustrata questa tecnica, cerchiamo di capirne il “costo”. Nei

precedenti paragrafi abbiamo visto che è possibile calcolare il costo del transitorio di attivazione in modo indipendente per ciascuna operazione. Nel caso in cui venga applicata la riduzione a blocchi, una parte non trascurabile del tempo di attivazione è data proprio dal costo della riduzione a blocchi, il che rende il calcolo del costo di attivazione più complesso.

Per semplicità, consideriamo allora il seguente ciclo:

do label i = 1,n label Y(i) = X(i)



Per ridurre a blocchi tale codice, si è visto che il compilatore genera due cicli annidati. Il loop interno contiene una sequenza di due operazioni vettoriali: la prima operazione è una LV (caricamento del vettore X); la seconda è invece una SV (memorizzazione del vettore Y). Ogni operazione atomica (che cioè agisce su singoli elementi scalari), in cui viene scomposta iterativamente l’operazione vettoriale originaria, richiederebbe 2 cicli di clock in assenza di penalizzazioni di attivazione, uno per il caricamento e l’altro per la memorizzazione. Nel caso del DLXV, il costo dell’attivazione dell’operazione di caricamento è di 12 cicli di clock per ogni vettore, cui si aggiunge una penalizzazione di 4 cicli di clock dovuto alla dipendenza della memorizzazione dal caricamento: si ha perciò un costo di attivazione totale di 16 cicli di clock (si tenga conto che si può trascurare la latenza della memorizzazione, la quale non ha conseguenze sul resto del programma).

PPPaaassssssooo dddeeeiii vvveeettttttooorrriii Il secondo problema da affrontare, per il trattamento dei vettori in un calcolatore

vettoriale, riguarda le tecniche di elaborazione di vettori i cui elementi non siano stati memorizzati in celle di memoria sequenziali. Ad esempio, supponiamo che il nostro processore vettoriale debba eseguire l’operazione vettoriale A=A+(B×C), dove tutti i vettori coinvolti hanno dimensione 100 e dove il simbolo “×” indica il prodotto righe per colonne; il corrisponde ciclo Fortran è fatto nel modo seguente:

do lab i=1,100

do lab j=1,100 A(i,j)=0,0

do lab k=1,100 lab A(i,j) = A(i,j)+B(i,k)*C(,k,j) Per poter eseguire un codice del genere, usando tra l’altro la tecnica di riduzione

a blocchi (dato che il numero di elementi è superiore alla capacità dei registri vettoriali, pari a 64), dobbiamo necessariamente esaminare la disposizione in memoria degli elementi delle matrici C e B.

Quando il compilatore alloca una matrice in memoria, lo fa secondo due passi: la linearizza e poi la dispone in memoria per righe oppure per colonne. In particolare:

• l’allocazione per righe è quella usata dalla maggior parte dei linguaggi di

programmazione: le righe vengono memorizzate in modo sequenziale, allocando cioè gli elementi B(i,j) e B(i,j+1) uno dopo l’altro in celle adiacenti:

....

Memorizzazione di una matrice per righe



• l’allocazione per colonne, invece, è usata in altri linguaggi, come ad esempio il Fortran: in questo caso sono le colonne ad essere memorizzate in modo sequenziale (partendo dal primo elemento e andando via via verso l’ultimo), allocando quindi gli elementi B(i,j) e B(i,+1,j) in celle adiacenti:

....

Memorizzazione di una matrice per colonne

Supponiamo che si scelga l’allocazione per colonne ed esaminiamo gli accessi a B e a C presenti nel loop interno del ciclo prima riportato:

• per quanto riguarda gli accessi agli elementi della matrice B, ogni iterazione

del loop accede ad elementi di colonne diverse (dato che varia l’indice k), per cui, data la memorizzazione per colonne, ad ogni iterazione si dovrà accedere ad elementi che sono separati, in memoria, da uno spazio pari ad una intera riga della matrice: supponendo che ogni elemento della matrice occupi 8 byte (numeri reali in doppia precisione) e le matrici siano tutte quadrate di dimensione 100, deduciamo che la suddetta distanza vale 8×100=800 byte;

• non ci sono invece “problemi” per la matrice C, dato che ad ogni iterazione si accede ad un elemento di una riga diversa e quindi la distanza tra due elementi da usare in successione è di 8 byte (i due elementi sono adiacenti).

La distanza in memoria tra due elementi che devono contribuire ad un medesimo

elemento di un altro vettore, o anche dello stesso vettore, prende il nome di passo (17): nell’esempio che abbiamo appena fatto, il passo per la matrice B è pari a 100 (ossia 100 parole, in questo caso doppie, per un totale di 800 byte), mentre quello per la matrice C è pari ad 1 (una parola doppia, ossia 8 byte).

Una volta che un qualsiasi vettore è stato caricato in un registro vettoriale, ovviamente viene trattato come se i suoi elementi fossero logicamente adiacenti. Così facendo, i calcolatori vettoriali sono in grado di gestire vettori di passo qualsiasi, detti passi non unitari quando sono diversi da 1, rendendo così molto più generali le operazioni vettoriali di caricamento e di memorizzazione. Ad esempio, se si potessero caricare tutte le righe della matrice B dell’esempio nei registri vettoriali, si potrebbe considerarle, dal punto di vista logico, come adiacenti.

Quest’ultimo discorso evidenzia l’utilità di poter parametrizzare le operazioni di caricamento e di memorizzazione in funzione sia degli indirizzi iniziali dei vettori sia anche del passo: in altre parole, ad una istruzione di caricamento (o di memorizzazione) devono essere forniti sia la dimensione del vettore (che però è

17 Si tenga conto che, in un calcolatore vettoriale, il calcolo di ciascun elemento del vettore risultante (ossia 100 iterazioni del loop interno del codice da cui siamo partiti) avviene in un colpo solo, da cui appunto il senso della definizione appena data.



implicita nel codice operativo), sia l’indirizzo iniziale sia anche il passo. Nel caso del DLXV, dove l’elemento di memoria minimo indirizzabile è il byte (come il DLX), il passo da indicare, per l’esempio precedente, varrebbe 800.

A queste considerazioni si aggiunga il fatto che il passo deve poter essere calcolato in modo dinamico, dato che la dimensione della matrice non è necessariamente nota al momento della compilazione e può variare, così come la dimensione dei vettori, tra esecuzioni distinte della stessa istruzione. E’ allora possibile memorizzare il valore del passo dei vettori, così come quello dell’indirizzo iniziale, in un apposito registro di uso generale, che poi sarà usato per tutta la durata dell’operazione vettoriale interessata; successivamente, esso potrà essere modificato per una nuova istruzione o per una nuova esecuzione della stessa istruzione. Il “trattamento” del passo dei vettori è affidato a due apposite istruzioni di caricamento e memorizzazione fornite dal DLXV:

• l’istruzione LVWS (Load Vector With Stride) serve a caricare un vettore con

un passo specificato;

• l’istruzione SVWS (Store Vector With Stride) serve a memorizzare un vettore con un passo specificato.

Naturalmente, se il passo è unitario, non è necessario specificarlo. A livello delle unità di memoria, potrebbero verificarsi delle complicazioni

derivanti dalla gestione di passi non unitari. Ad esempio, consideriamo una memoria suddivisa in banchi, secondo i criteri esposti in precedenza. Abbiamo visto che le operazioni vettoriali in memoria possono procedere alla massima velocità a patto che sia verificata la condizione

Numero di banchi di memoria ≥ Tempo di accesso ai banchi (in cicli di clock)

Tuttavia, se esistono passi non unitari, potrebbe capitare che venga richiesto

l’accesso ad uno stesso banco con frequenza più elevata di quella di ciclo di memoria, il che comporterebbe un conflitto di banco di memoria: in pratica, un simile conflitto si verifica quando si richiede un accesso ad un banco prima che questo abbia completato il trasferimento corrente.

Facciamo un esempio numerico. Supponiamo di avere a disposizione 16 banchi di memoria, con tempo di accesso ciascuno di 12 cicli di clock. Supponiamo inoltre di voler caricare un vettore di 64 elementi:

• come primo caso, consideriamo quello di passo unitario, per cui gli

elementi del vettore sono memorizzati in celle adiacenti: dato che il numero di banchi (16) è maggiore della latenza di caricamento (12), sappiamo già che il caricamento viene svolto alla massima velocità, corrispondente a 12+64=76 cicli di clock (corrispondente a 1.2 cicli di clock per elemento);

• un caso sicuramente più sfavorevole è quello in cui il passo è pari ad esempio a 32: infatti, in questa situazione ogni accesso alla memoria entra in conflitto con quello precedente, degradando così il tempo di accesso, che diventa di 12 cicli di clock per ogni elemento, per un tempo totale di 768 cicli di clock per il caricamento. Lo stesso risultato si otterrebbe anche con un passo pari a 16.

Se aumentiamo il numero di banchi, riusciamo del resto a diminuire la frequenza

degli stalli: ad esempio, con 64 banchi, un passo pari a 32 causa uno stallo ogni due accessi anziché uno per ogni accesso.



Prestazioni dei calcolatori vettorialiPrestazioni dei calcolatori vettoriali Vogliamo ora introdurre un semplice modello per la valutazione delle prestazioni

di un loop eseguito su un calcolatore vettoriale; in particolare, consideriamo un loop ridotto a blocchi, il che, come visto in precedenza, elimina la possibilità che il calcolatore debba elaborare vettori di dimensione maggiore di quella dei registri vettoriali a disposizione. Naturalmente, la riduzione a blocchi fa sì che il corpo del loop sia costituito da una sequenza di istruzioni vettoriali.

Sotto queste ipotesi, il tempo di esecuzione del loop è costituito da tre componenti:

• il tempo di elaborazione di un singolo elemento scalare, senza il transitorio

di attivazione. Indichiamo questo tempo con Telemento: quando il corpo del loop produce un unico risultato vettoriale, allora Telemento è appunto l’intervallo di tempo necessario per calcolare un singolo elemento scalare di tale risultato; se invece il loop produce più di un vettore in uscita, allora Telemento è propriamente l’intervallo di tempo necessario a calcolare un elemento di ciascuno dei vettori di uscita. Il valore di Telemento dipende solo dall’esecuzione delle istruzioni vettoriali;

• il sovraccarico imposto da ogni sottoblocco delle istruzioni vettoriali: questa componente è la somma del tempo Tloop richiesto dall’esecuzione delle operazioni scalari per la suddivisione in sottoblocchi dei vettori originali e del transitorio di attivazione Tattivazione di ciascun sottoblocco;

• infine, il sovraccarico derivante dal calcolo dell’indirizzo iniziale e dall’inizializzazione delle operazioni di controllo dei vettori. Tale tempo, che indichiamo con Tbase, viene imposto una sola volta per l’intera operazione vettoriale e deriva solo dai tempi di esecuzione delle operazioni scalari ad esso connesse.

La composizione di queste tre componenti da origine, per una sequenza di

operazioni vettoriali che agiscono su un vettore di dimensione n, al seguente tempo totale di esecuzione:

( ) elementoeattivazionloopbasen TnTTMVL

nTTE ⋅++⋅

+=

Il senso della formula è abbastanza intuitivo: a parte il tempo Tbase necessario

per l’inizializzazione, il sovraccarico Tloop+Tattivazione dovuto alla “gestione” dei singoli sottoblocchi è “pesato” dal numero di sottoblocchi, mentre invece il tempo Telemento necessario per il calcolo dei singoli elementi del vettore risultante (o dei vettori risultanti) è “pesato” dal numero di elementi da calcolare.

Dal punto di vista dei fattori che influenzano questi tempi, possiamo dire quanto segue:

• i tempi Tattivazione e Tloop dipendono sia dal compilatore sia dalla struttura

del calcolatore;

• Tattivazione, in particolare, dipende dal tempo di attivazione del caricamento dei vettori sorgente (12 cicli di clock per ogni vettore), da eventuali stalli (di 4 cicli di clock) dovuti a dipendenze tra istruzioni (ad esempio tra memorizzazioni e caricamenti oppure tra moltiplicazioni e memorizzazioni), dal tempo di attivazione delle operazioni da compiere (ad esempio 7 cicli di clock per la moltiplicazione);



• il tempo Telemento dipende invece primariamente dall’hardware;

• la sequenza di istruzioni vettoriali da compiere influisce su tutti e tre i tempi appena citati ed in particolar modo su Telemento;

• i valori di Tbase e Tloop dipendono naturalmente dalla struttura del loop. Al fine di compiere delle valutazioni sulle prestazioni del DLXV, si è scelto di

attribuire valori costanti a Tbase e Tloop, pari rispettivamente a 10 ed a 15. Si potrebbe anche pensare che il valore 15 per Tloop sia troppo basso; in effetti, però, si possono fare le seguenti due considerazioni: in primo luogo, il sovraccarico per ogni loop deriva dal calcolo dell’indirizzo iniziale del vettore, dall’aggiornamento del valore del passo, dall’incremento dei contatori e dall’esecuzione della diramazione a guardia del loop; tutte queste operazioni scalari richiedono un certo tempo, ma possono del resto essere parzialmente sovrapposte alle operazioni vettoriali, minimizzando così i sovraccarichi relativi.

Tecniche di cTecniche di compilazioneompilazione Per rendere efficiente l’uso di un calcolatore vettoriale, occorre disporre di un

compilatore che possa stabilire se un loop, o almeno parte di esso, è “vettorizzabile” e, in caso affermativo, che sia in grado di generare il codice adatto. Questo richiede fondamentalmente la capacità, da parte del compilatore, di individuare eventuali dipendenze tra gli operandi coinvolti nel loop.

Per cominciare con un discorso semplice, consideriamo per il momento solo le dipendenze che nascono quando un operando viene scritto in un punto del loop e deve poi essere letto in un punto successivo: si tratta evidentemente delle classiche dipendenze corrispondenti ai conflitti RAW ampiamente visti in precedenza. Facciamo un esempio semplice:

do Lab1 i=1,100

S1 A(i+1)=A(i)+B(i) S2 B(i+1)=B(i)+A(i+1) Lab1 continue In un ciclo come questo, sussistono ben tre tipi di dipendenze:

1. in corrispondenza di ogni iterazione del loop, una istruzione usa un valore calcolato dalla stessa istruzione nell’iterazione precedente: ad esempio, l’istruzione contrassegnata con S1 usa il valore A(i) nell’iterazione (i+1)-esima ed A(i) che era stato calcolato durante l’iterazione i-esima della stessa S1 come A(i+1); analogamente, S2 usa B(i) che era stato calcolato nell’iterazione precedente come B(i+1);

2. in corrispondenza di ogni iterazione del loop, una istruzione usa un valore calcolato da un’altra istruzione nell’iterazione precedente: nel nostro caso, l’istruzione S1 usa il valore B(i) nell’iterazione (i+1)-esima e B(i) che era stato calcolato durante l’iterazione i-esima della S2 come B(i+1);

3. infine, una istruzione usa un valore calcolato da un’altra istruzione nella stessa iterazione: nel nostro caso, si tratta ovviamente di S2 che usa A(+1), calcolato dall’istruzione S1.



Perché questo tipo di conflitti possono dare dei problemi in una macchina vettoriale? La risposa è la seguente: dato che le operazioni vettoriali sono eseguite in modo pipeline e che la latenza di ciascuna di esse può assumere un valore anche molto elevato, può succedere che una iterazione precedente non sia stata ancora completata prima che venga iniziata un’iterazione successiva; di conseguenza, i risultati che si sarebbero dovuti scrivere nell’iterazione precedente potrebbero non essere ancora stati aggiornati quando si comincia l’iterazione successiva: ad esempio, l’iterazione i-esima del loop visto prima potrebbe non essere ancora terminata quando comincia l’iterazione (i+1)-esima, nel qual caso A(i) e B(i) potrebbero non essere stati ancora calcolati, il che impedirebbe di calcolare A(i+1) e B(i+1). In generale, dunque, quando si verificano le condizioni di cui ai punti 1 e 2, la vettorizzazione del loop può dare origine ad un conflitto di tipo RAW, conflitto che la macchina vettoriale non è in grado di rilevare. Proprio per questa limitazione della macchina vettoriale, qualora il compilatore trovi una situazione del tipo appena descritto, deciderà immediatamente che il loop non è vettorizzabile e quindi non genererà alcun codice vettoriale.

Più semplice è invece la gestione della situazione 3 prima descritta: infatti, bastano i soliti dispositivi hardware visti anche per il DLX per rilevare il conflitto e prendere i necessari provvedimenti (ad esempio l’anticipazione). In questi casi, quindi, il compilatore dà per scontato che il processore sarà in grado di gestire la situazione e quindi procede a generare il codice vettoriale.

Le dipendenze di tipo 1 e 2, che comportano cioè l’uso di valori calcolati da iterazioni precedenti del loop, sono dette dipendenze di loop.

Vediamo ora con maggiore dettaglio quale deve essere il comportamento del compilatore. La prima cosa che esso deve verificare, dato un loop eventualmente da vettorizzare, è quella di determinare se esistono dipendenze di loop all’interno del corpo del loop stesso. Questa fase si effettua tramite un apposito algoritmo di analisi delle dipendenze ed è abbastanza complicata. In effetti, un caso abbastanza semplice è quello in cui il nome di un vettore compare solo in un unico membro di una istruzione di assegnamento. Ad esempio, si consideri la seguente variante del loop visto prima:

do Lab1 i=1,100

S1 A(i)=B(i)+C(i) S2 D(i)=A(i)*E(i+1) Lab1 continue In questo caso, se i vettori coinvolti sono tutti diversi tra loro, non esiste alcun

dipendenza di loop. Si manifesta tuttavia un problema sul vettore A, in quanto le due istruzioni richiedono entrambe l’accesso a tale vettore (dipendenza di tipo 3); il compilatore ha allora due soluzioni a disposizione:

• la soluzione più semplice è quella di memorizzare A e poi ricaricarlo, in

quanto le due operazioni avverrebbero in sequenza e non determinerebbero alcun problema;

• una soluzione invece più complicata è invece quella di fare in modo che il moltiplicatore coinvolto nella seconda istruzione acceda direttamente al registro vettoriale in cui è stato memorizzato il risultato della istruzione di somma: in questo caso, il processore rileverebbe il conflitto RAW e porrebbe in stallo l’istruzione di moltiplicazione, fino al momento in cui può disporre dell’operando sorgente corretto.



Una situazione diversa da quella appena descritta si verifica quando lo stesso vettore compare sia come operando sorgente sia come operando destinazione di una stessa istruzione, come accade ad esempio nel loop DAXPY visto in precedenza:

do label i = 1,n

Y(i) = a * X(i) + Y(i) label continue In questo caso, non c’è però dipendenza di loop, dato che l’assegnamento ad Y

non dipende da un valore di Y calcolato in una iterazione seguente. Le cose cambiano, invece, se il ciclo fosse del tipo seguente:

do label i = 1,n Y(i) = Y(i-1) + Y(i)

label continue In questo caso, il calcolo di Y(i) richiede l’uso di Y(i-1), calcolato nell’iterazione

precedente. Si può eventualmente ben evidenziare la dipendenza srotolando il loop: nell’iterazione j-sima, si usa il valore di Y(j-1), ma tale valore viene memorizzato durante l’iterazione (j-1)-esima, determinando così la dipendenza di loop.

In generale, ci sono situazioni in cui l’esistenza di una dipendenza di loop non può essere rilevata in fase di compilazione, così come ci sono casi in cui la dipendenza può essere rilevata ma tramite un costo computazionale, da parte del compilatore, molto elevato.

Segnaliamo inoltre che possono esistere, oltre ai conflitti RAW di cui abbiamo parlato poco fa, anche conflitti WAR (detti anche anti-dipendenze) e conflitti WAW (detti anche dipendenze di uscita): rispetto ai conflitti RAW, però, questi altri conflitti possono essere facilmente risolti semplicemente rinominando i registri allocati dal compilatore; si tratta infatti di conflitti non “di dati”, bensì “di nome”, quindi facilmente eliminabili.

EEEffffffiiiccciiieeennnzzzaaa dddeeelllllleee ttteeecccnnniiiccchhheee dddiii vvveeettttttooorrriiizzzzzzaaazzziiiooonnneee Sono principalmente due i fattori che influiscono sull’efficienza con cui viene

eseguito un programma in modo vettorizzata:

• il primo fattore è ovviamente la struttura del programma stesso: se il programma non presenta dipendenze di dati oppure la presenta ma è possibile risolverle, allora l’esecuzione sarà efficiente;

• il secondo fattore è la potenza del calcolatore: infatti, se è vero che nessun compilatore potrà mai vettorizzare un loop il cui corpo non presenti un qualche grado di parallelismo a livello delle istruzioni che lo compongono, è altrettanto vero che esistono profonde differenze, tra i vari compilatori, nella capacità di stabilire la vettorizzabilità dei loop.

Autore: Sandro Petrizzelli e-mail: [email protected]

sito personale: http://users.iol.it/sandry

Date post:	23-Feb-2019
Category:	Documents
Upload:	duongtu
View:	213 times
Download:	0 times

A p p u n ti d i C alcolatori E lettron ici - Siti Personali | Libero...

Documents