Visualizza il feed RSS

Titolo provvisorio...

Lascia o Raddoppia (ricorsivamente)?

Valutazione: 3 voti, con una media del 5.00.
di pubblicato il 18-06-2011 alle 02:21 (4441 Visite)
Dietro esplicita richiesta di un giovane lettore, riprendo qui un argomento già trattato in un post di qualche tempo fa.

I vector processor, assieme ai Transputer, sono un'altra delle poche vere idee geniali che costellano la storia dell'informatica applicativa, e (naturalmente) non hanno avuto il successo meritato a livello di personal computing. In compenso i soliti raccattatutto del mainstream hanno "ereditato" numerose idee del vector processing, facendone la base di "novità" tecnologiche come MMX e XMM.

Eppure non occorrono particolari doti immaginative per comprendere le enormi potenzialità dei VP in accoppiata con i linguaggi vettoriali come APL, Q o J.

I vantaggi in termini architetturali sono forse meno intuitivi, ma egualmente enormi: ad esempio, l'accesso vettoriale alla memoria (totalmente implementata on-chip in talune architetture) implica la totale inutilità di ineleganti obbobbri nondeterministici come la cache !
Il ciclo di potenza, determinato dagli stadi che devono essere alimentati durante le singole fasi elaborative è altresì molto vantaggioso e ne fa un processore a bassissimo consumo energetico specifico. Non a caso, da anni i VP vengono applicati in sistemi embedded CPU-intensive, oltre al magico reame del supercomputing che da sempre costituisce la loro più naturale vocazione.

Come insito nell'onomastica, un processore vettoriale è un processore MIMD o più spesso SIMD progettato per essere in grado di operare su interi vettori, non già su singoli valori (scalari).

Per costruzione tali processori ammettono nella ISA operazioni aritmetiche solo tra elementi nella medesima posizione: quindi l'i-esimo elemento di un vettore operando dovrà di norma essere elaborato unicamente insieme all'i-esimo elemento di un secondo vettore, e così via, in stretta corrispondenza.

Questo vincolo semplifica in maniera formidabile la progettazione del processore a parallelismo massivo, configurandolo esattamente come una serie di "corsie" a fronte di un casello autostradale: ad ogni corsia corrisponde una posizione nel vettore-operando, e in definitiva il numero di lanes esprime la massima dimensione di un vettore trattabile parallelamente in una singola operazione.

Resta inteso che vettori di dimensione maggiore rispetto alla dotazione di lanes vengono comunque trattati segmentandoli.

Un buon punto di partenza per maggiori informazioni è l'appendice G dell'Hennessy-Patterson sull'architettura dei calcolatori ("Computer Architecture: a quantitative approach"). Il secondo autore, in particolare, ha contribuito con numerosi articoli scientifici al progresso del settore del vector processing.

Come per quasi ogni altra piattaforma, anche in questo caso i migliori risultati si ottengono impiegando algoritmi appositamente studiati o modificati per adattarsi alle caratteristiche di questi interessanti core.

Una delle tecniche più importanti per la ristrutturazione e il riadattamento ai vector processors di algoritmi classici consiste nel raddoppio ricorsivo (da cui, con ardito spicco di fantasia, il titolo di questa entry...).

Il raddoppio ricorsivo (recursion doubling o metodo fan-in, dall'elettronica) è una tecnica di tipo divide et impera per scomporre algebricamente un problema, rendendolo più trattabile vettorialmente.

Per non appesantire inutilmente l'articolo con elenchi di assiomi e dettagliate definizioni sulla notazione, nel seguito mi prendo la libertà di usare in modo alquanto libero e forse meno rigoroso, ma massimamente intuitivo, i simboli usualmente impiegati nella letteratura di questo settore, esplicitando la base dei logaritmi e ricordando di nuovo la più ovvia delle premesse, ossia che tutti i numeri che qui ci interessano sono interi non negativi, salvo diversa esplicita specificazione.

Il più basilare degli esempi riportati sui testi è l'arciclassico prodotto interno di due vettori reali, universalmente definito come segue - data la dimensione dei vettori stessi espressa dall'intero positivo arbitrario n > 1:

Formula LaTeX: (1)\ \ \ p\ =\ \sum_{i=0}^{n} x_i\cdot y_i

Supposto che n sia pari, si pone m = n/2 ed è elementare la riscrittura:

Formula LaTeX: (2)\ \ \ p\ =\ \sum_{i=0}^{m} x_i \cdot y_i \ + \sum_{j=m+1}^{n} x_j \cdot y_j

Si tratta, in questo caso, di calcolare separatamente due somme (parziali) di prodotti, unendole poi con una somma finale.

Si nota immediatamente che tali somme sono del tutto indipendenti l'una dall'altra, e possono quindi essere calcolate in modo disgiunto e nel medesimo momento. Questa condizione di intrinseco parallelismo matematico è la chiave per la comprensione dell'intera strategia.

Generalizzando, si tratta di iterare (caso per caso) un tale procedimento, secondo il numero di processori target, chiamiamolo P, e la dimensione dell'input, che chiamiamo n come sempre si usa in complessità computazionale.

Si deve notare che codesta scomposizione ha anche l'eccellente effetto collaterale di minimizzare gli errori di accumulo tipici del floating point, a causa della sostanziale indipendenza dei risultati che vengono poi ricombinati linearmente, con l'effetto globale di aumentare notevolmente la stabilità dei relativi algoritmi numerici.

Non è difficile valutare quantitativamente il guadagno prestazionale di un simile approccio. Assumiamo, per semplificare, di avere già pronti i prodotti membro a membro: tale tempo in realtà non è direttamente influenzato dal cambio di strategia algoritmica, dunque lo consideriamo costante, omettendolo dal calcolo dei rapporti.

Chiamiamo Formula LaTeX: t_S il tempo necessario per una operazione elementare di somma tra due addendi, a valle del calcolo dei prodotti: avendo n addendi, avremo n-1 addizioni e quindi, nella forma manualistica elementare, il calcolo del prodotto interno avrà ovviamente costo in tempo pari a:

Formula LaTeX: (3)\ \ \ (n -1)\ \cdot\ t_S

Spezzando il problema in due semisomme parallele, il tempo necessario va praticamente a dimezzarsi. Avremo infatti il tempo necessario ad effettuare circa la metà delle somme (meno una: i segni sono sempre uno in meno degli addendi... ), a cui si aggiunge il tempo necessario a movimentare i risultati parziali e sommarli.
Scriviamo nel modo più pedissequo la formula, per meglio memorizzarne la composizione, prima di semplificarla algebricamente.

Formula LaTeX: (4)\ \ \ \left(\frac{n}{2} -1\right)\cdot t_S + t_C + t_S \ =\ \frac{n}{2}\cdot t_S + t_C

dove la nuova costante con pedice C rappresenta appunto il costo delle operazioni di movimentazione delle due semisomme da registri e/o memoria.

Il rapporto tra questi due costi, espressi dalla (3) e dalla (4) rispettivamente, ci fornisce il valore dell'ottimizzazione:

Formula LaTeX: (5)\ \ \ G\ =\ \frac{(n -1) \cdot t_S}{\frac{n}{2} \cdot t_S + t_C}

Tale rapporto, in pratica, è molto vicino a 2.

Per generalizzare, supponendo di avere un numero di processori P pari alla dimensione n del problema (con n potenza intera del 2, di esponente k > 1):

Formula LaTeX: (6)\ \ \ G\ =\ \frac{(n -1) \cdot t_S}{k \cdot (t_S + t_C)}\ \ \ \text{per } n=2^k,\ k>1

A noi conviene, per semplificare ulteriormente la formuletta, esprimere il tempo Formula LaTeX: t_C in funzione del tempo di somma. Su talune architetture, uno dei due risulta per costruzione trascurabile rispetto all'altro.
Poniamo dunque

Formula LaTeX: \tau \ =\ \frac{t_C}{t_S}

e dividiamo numeratore e denominatore per la quantità Formula LaTeX: t_S - sicuramente non nulla, almeno con l'attuale tecnologia...

Possiamo così scrivere la nostra formuletta di speedup in funzione della dimensione del problema:

Formula LaTeX: (7)\ \ \ G \ =\ \frac{n -1}{(\tau +1) \cdot \log_2n}

Allo stesso modo, possiamo esprimerla in funzione del numero di processori:

Formula LaTeX: (8)\ \ \ G \ =\ \frac{P -1}{(\tau +1) \cdot \log_2P}

Asintoticamente, annullando i tempi di comunicazione e le latenze, è interessante notare che rimane:

Formula LaTeX: (9)\ \ \ \bar{G} \ =\ \frac{P -1}{\log_2P}\ <<\ P

Tale guadagno è inferiore anche a Formula LaTeX: log_2P, per valori di P maggiori di 2 e inferiori a 20 processori (o lanes). Il che ci introdurrebbe dritti dritti alla legge di Amdahl sui limiti del parallelismo, che oltre un certo valore introduce più inefficienze di quante possa eliminarne...

A questo punto, è solo opportuno rimarcare che il fattore di costo Formula LaTeX: t_C ha una notevole importanza, in quanto riassume globalmente tutti i costi introdotti con l'uso del raddoppio ricorsivo: salvataggi, riletture e altre inefficienze intrinseche.

Tale fattore quantifica il concetto che in questo genere di transazioni "si perde comunque qualcosa", di norma secondo la legge macroscopica e asintotica:

Formula LaTeX: \frac{N}{log_2 N}

Questo implica, in definitiva, che non serve aumentare a dismisura il numero di processori (o lanes) in parallelo, in quanto esiste un limite superato il quale i costi aggiuntivi (legati principalmente ai trasferimenti di memoria) superano i vantaggi introdotti dal parallelismo.
Ciò è generalmente noto come argomento o legge di Amdahl (il cui modello è inerentemente più raffinato, come sappiamo): il buon informatico, in questo caso specifico in veste di progettista di compilatori ottimizzanti per vector processor, saprà sempre incrociare un paio di formulette lineari per far calcolare al suo software il break-even point ottimale in relazione alle peculiarità dell'architettura, al numero di processori, registri e lanes, alla dimensione del problema.

La bitmap allegata speedup.png mostra l'andamento della funzione:

Formula LaTeX: y\ =\ \frac{x -1}{log_2x}\;\;\;\;\forall x \ge 2

Gli assi cartesiani usano qui scale diverse per fin troppo ovvi motivi di evidenziazione grafica delle pendenze in un intervallo piuttosto ristretto. A confronto, in verde, la bisettrice del primo (e terzo) quadrante e - in blu - il logaritmo al denominatore.

L'immagine è stata ottenuta con graph.

La bottom line è che, per i vector processors, esiste un limite pratico per i vantaggi ottenibili aumentando il numero di lanes, il che conduce a poter progettare core (e multicore, come in alcune recenti proposte) VP dimensionati in modo ottimale per la generalità delle applicazioni.

Lettura consigliata: Designing and building parallel programs, un valido ebook a cura di Ian Foster.

aggiornamento da 01-07-2014 a 13:08 di M.A.W. 1968

Categorie
Hardware , Tecnologia

Commenti

  1. L'avatar di feel
    Salve,
    veramente interessante articolo.
    Sarei grato se mi dasse delucidazioni di come l'accesso vettoriale alla memoria sia capace di rendere inutile tecniche come l'uso della cache.
    Grazie.
  2. L'avatar di M.A.W. 1968
    Dobbiamo ricordare che l'architettura vettoriale è la più tipica soluzione per il progetto e la realizzazione di supercalcolatori, a partire dai Cray. Dunque possiamo attenderci qualche "sorpresa" hardware rispetto all'architettura "povera" dei PC e server mainstream. Per non appesantire la presente risposta, mi limiterò solo ad accennare i concetti più intuitivi che conducono all'eliminazione della cache.

    In effetti, abbiamo già indicato due concetti estremamente importanti in un vector processor: l'operabilità strettamente vincolata a posizioni corrispondenti nei vettori-operando, che ovviamente implica la garanzia di nessuna interazione o dipendenza tra i dati di un medesimo vettore (a questo provvedono i layer software, sia a tempo di compilazione che a runtime); e il rapporto tra lanes e lunghezza del vettore-operando, che sovente comporta l'esecuzione iterativa di una medesima operazione su più dati memorizzati in locazioni strettamente sequenziali.

    Dunque, anche se non abbiamo ben presenti in mente architetture esotiche come quella dello Stardent Titan, con i suoi banchi di registri multipli (es. 8 registri da 64 lanes cadauno) e la memoria interleaved tipica dei supercalcolatori, possiamo però già intuire che un VP non ha alcun bisogno di effettuare un pipeline profondo delle istruzioni, ma solo dei dati. Questo approccio è mutuamente esclusivo col concetto stesso di data cache, naturalmente.

    In base a tali considerazioni, anche se effettivamente esistono schemi di caching per talune architetture di VP (queste sì davvero esotiche), l'approccio generale - condiviso anche da taluni processori ibridi scalari/vettoriali, o comunque capaci di emulare modalità vettoriali - è quello di usare per costruzione il bypass della cache, grazie a banchi di registri dedicati - una soluzione ampiamente in uso anche all'altro estremo del computing applicativo, ossia nei sistemi embedded.
  3. L'avatar di feel
    Operazioni di fetch e decode su una medesima istruzione in rapporto con la quantità di dati da elaborare sono drasticamente ridotte in VP, e in concomitanza con dati richiesti localmente "vicini" tra loro acceduti vettorialmente implica una totale inutilità della cache.
    Perfetto ora mi è tutto più chiaro. Grazie
  4. L'avatar di M.A.W. 1968
    Portando all'estremo il concetto, alcune tra le numerose varianti di VP sono organizzate in modo tale che sorgente e destinazione dati siano unicamente in memoria (si ricordi, tuttavia, che quasi sempre si parla di memorie on-chip in casi del genere).

    Motivi secondari di efficienza e ottimizzazione della implementazione conducono tuttavia quasi ogni progetto di VP concretamente realizzato a fare affidamento su uno o più banchi di registri, ciascuno con molteplicità pari al lanes factor: e ciò non si limita unicamente a codesti registri, che comunque hanno un ruolo primario nella modalità di accesso sequenziale sancita dalla teoria. Infatti, pensando proprio al semplice esempio al centro della presente entry, è altresì facile intuire l'opportunità di disporre anche di registri e/o accumulatori per risultati scalari (intermedi e finali).