Loading AI tools
tipo di parallelismo Da Wikipedia, l'enciclopedia libera
L'Instruction level parallelism (ILP, lett. "parallelismo a livello di istruzione") esiste quando delle istruzioni di un programma sono indipendenti e quindi possono essere eseguite in calcolo parallelo.
La ricerca di codice parallelo a livello di istruzioni è una priorità nei moderni microprocessori che sono dotati di molte unità di calcolo e usualmente seguono una struttura a pipeline quindi l'individuazione e lo sfruttamento delle istruzioni eseguibili in parallelo permette di utilizzare le unità funzionali dei processori innalzandone le prestazioni.
Consideriamo il seguente frammento di pseudocodice:
1) h = a + b 2) f = c + d 3) g = h * f
L'istruzione 1 e l'istruzione 2 possono essere eseguite in parallelo dato che richiedono dei dati (a, b, c, d) che non sono utilizzate da altre istruzioni e quindi sono libere. Invece l'istruzione 3 per venire eseguita deve attendere il completamento delle prime due istruzioni dato che i dati h e f dipendono dall'esecuzione delle prime due istruzioni. Supponendo di avere delle unità di calcolo (ALU) indipendenti quindi si possono eseguire le istruzioni 1 e 2 in parallelo mentre la 3 deve attendere le altre due. Supponendo di avere unità che eseguono le operazioni in un ciclo di clock eseguendo le operazioni in parallelo si può completare il codice in due cicli di clock mentre un'esecuzione seriale del codice richiederebbe tre cicli di clock. Con questa modifica l'ILP diventa 3/2 dato che si eseguono tre istruzioni in due cicli di clock.
Fin dagli albori dell'informatica i progettisti hanno cercato di eseguire alcune operazioni in parallelo al fine di ottenere un incremento delle prestazioni dei sistemi di elaborazione. Già lo Z3, il primo computer digitale era in grado di eseguire alcune parti delle elaborazioni in parallelo al fine di migliorare le sue prestazioni. Le principali innovazioni legate all'ILP sono state:[1]
Il massimo numero di istruzioni eseguibili in parallelo viene limitato da tre problemi (in inglese definiti alee); il numero di unità funzionali, le dipendenze sui dati e le dipendenze sul controllo.
Nello specifico:
Per aumentare il livello di parallelismo nei microprocessori esistono in sostanza due strategie.
I processori moderni per ottenere le massime prestazioni tendono ad utilizzare le due tecniche in contemporanea, adottano pipeline più lunghe del minimo necessario (10/15 stadi) ed eseguono più istruzioni in parallelo.
L'analisi del codice alla ricerca di ILP può essere suddiviso in due grandi categorie, l'ILP statico e l'ILP dinamico.
Nell'ILP statico il processore riceve le operazioni già suddivise in blocchi di istruzioni indipendenti eseguibili in parallelo, il processore deve unicamente eseguire le istruzioni dato che l'analisi del codice è già stata effettuata dal compilatore che ha già individuato ed evidenziato le parti eseguibili in parallelo. Questo approccio permette di realizzare processori semplici e veloci ma ha lo svantaggio che i programmi vengono compilati appositamente per un singolo tipo di processore e modifiche all'architettura interna del processore possono produrre notevoli riduzioni di prestazioni e in casi estremi anche errori di esecuzione. I processori very long instruction word seguono questa filosofia.
Invece nell'ILP dinamico il compilatore non analizza il codice alla ricerca di istruzioni parallelizzabili dato che questo compito viene svolto dal processore che durante l'esecuzione dinamicamente decide quali istruzioni sono eseguibili in parallelo. Questo permette di non legare il codice all'architettura di un singolo processore ma ha lo svantaggio di rendere il microprocessore molto più complesso e potenzialmente più lento. Il processore ha pochi nanosecondi per decidere se esistono delle istruzioni parallelizzabili e per decidere come organizzarle mentre un compilatore può fare un'analisi approfondita del codice avendo molto più tempo del microprocessore.
I microprocessori per computer implementano l'ILP dinamico sebbene molti possano utilizzare anche alcune tecniche di ILP statico per incrementare le prestazioni.
Durante l'esecuzione il processore per individuare le istruzioni parallelizzabili può utilizzare molte tecniche, le principali sono:
Tutti i processori moderni utilizzano le pipeline, le pipeline quando si trovano in presenza di alee sui dati o sul flusso di controllo devono introdurre degli stalli (detti anche bolle) per permettere la risoluzione delle alee. Le alee possono essere ridotte riorganizzando le istruzioni opportunamente, per esempio nel seguente codice:
1) h = a + b 2) f = h - d 3) g = w + 100
la seconda istruzione dipende dal risultato della prima istruzione mentre la terza istruzione è indipendente dalle altre. Eseguendo le istruzioni all'interno di una pipeline a 5 stadi si avrebbe uno stallo (o due dipende da come viene implementata la pipeline) tra la prima e la seconda istruzione. Riorganizzando le istruzioni ed inviando alla pipeline la prima istruzione, poi la terza istruzione (indipendente dalle altre) e infine la seconda istruzione si ottiene un'esecuzione senza stalli. Questa modalità di esecuzione viene detta out-of-order dato che le istruzioni vengono eseguite e completate fuori ordine rispetto al codice sviluppato dal programmatore.
I microprocessori includono quasi sempre una qualche tipologia di unità di predizione delle diramazioni, questa unità tiene traccia delle istruzioni di salto e se incontra delle istruzioni di salto analizzano la storia passata delle istruzioni cerca di prevedere se il salto verrà eseguito o no. La predizione delle diramazioni permette di caricare in anticipo le istruzioni successive al salto e nel caso di corretta predizione del salto il processore non deve bloccare o svuotare la pipeline.
Alcuni processori implementano inoltre una qualche forma di esecuzione speculativa. Supponendo che un salto condizionato dipenda da dei dati non ancora elaborati alcuni processori basandosi sulla storia passata dell'istruzione di salto i processori possono fare una previsione sul risultato del salto (speculano sul possibile risultato) e caricare le istruzioni conseguiti la previsione. Questa tipologia di esecuzione richiede molti transistor per essere implementata perché oltre all'unita di speculazione bisogna tener traccia delle istruzioni in esecuzioni che dipendono dalla speculazione e in caso di errata previsione queste istruzioni vanno eliminate e i loro effetti sui dati annullati.
Alcune alee dipendono dal fatto che più istruzioni utilizzano gli stessi registri o le stesse locazioni di memoria per esempio per scriverci i risultati dell'elaborazione. Per esempio:
1) h = a + b 2) h = c - d
L'istruzione 1 e 2 sono dal punto di vista dei dati indipendenti ma non possono essere scambiate dato che entrambi scrivono i risultati in h, invertendo le istruzioni alla fine dell'elaborazione si troverebbe il valore calcolato da a+b e non c-d ottenendo un'esecuzione errata del programma. Questa non è una vera alee dei dati dato che in realtà le due istruzioni non sono realmente limitate dai dati ma sono limitate dai registri nei quali salvare i dati. Il microprocessori possono allora implementare la rinominazione dei registri, in sostanza introducono dei registri utilizzati per salvare dei dati temporanei in modo da poter eseguire le istruzioni in modo indipendente dato che alla fine dell'esecuzione sarà l'unità di rinominazione a salvare nei registi i dati corretti. Nell'esempio sopra il codice diverrebbe:
1) h = a + b 2) k = c - d
La seconda istruzione salva i dati nel registro temporaneo k e quindi le due istruzioni possono essere eseguite in parallelo tanto alla fine l'unità di rinominazione provvederà a memorizzare il dato contenuto in k nel registro h mantenendo la coerenza logica del programma. Lo scheduling dinamico della pipeline e la rinominazione dei registri permette di eliminare la maggior parte delle alee riducendo significativamente gli stalli nelle pipeline. L'utilizzo di queste tecniche viene governato dall'algoritmo di Tomasulo o da sue varianti più moderne e efficienti.
Spesso i programmi sono formati da gruppi di istruzioni che vengono eseguite più volte in sequenza. Utilizzando le unità di scheduling dinamico della pipeline e di rinominazione dei registri i processori possono eseguire alcune istruzioni dei vari cicli in parallelo e possono eliminare alcuni salti condizionati, per esempio il codice:
1) a = 0 2) FOR a< 2 3) k = k - d 4) a = a + 1 // fine FOR
dopo lo srotolamento del loop ottengo:
1) a = 0 2) k = k - d 3) a = a + 1 4) k = k - d 5) a = a + 1
Senza srotolamento il processore dovrebbe eseguire 8 istruzioni (1 2 3 4 2 3 4 2), delle quali tre sono salti condizionati (l'istruzione 2), dopo lo srotolamento ottengo 5 istruzioni, i salti sono stati eliminati e le istruzioni possono essere eseguite dalla pipeline senza stalli.
ILP statico a differenza dell'ILP dinamico viene eseguito durante la fase di compilazione del codice, il compilatore analizza il codice rilevando le istruzioni parallelizzabili e le segnala in modo che durante l'esecuzione il processore sappia già quali istruzioni sono parallelizzabili e come vadano eseguite. L'ILP statico è particolarmente utilizzato dai processori embedded che per questioni di costo e di consumi non possono implementare i complessi metodi di analisi richiesti dall'ILP dinamico. Comunque l'ILP statico viene utilizzato in qualche modalità anche dai processori ad alte prestazioni e la famiglia di processori Itanium è basata su questa filosofia.
ILP statico come l'ILP dinamico cerca di massimizzare le prestazioni e per far questo cerca di utilizzare al massimo le pipeline minimizzando gli stalli, questo viene ottenuto riorganizzando le istruzioni in un modo simile a quanto fa l'ILP dinamico. Il compilatore per poter produrre del codice efficiente deve conoscere nel dettaglio le caratteristiche del processore; deve conoscere dettagli come la lunghezza delle pipeline, la loro organizzazione, i tempi di esecuzione, ecc. Due processori con identico set di istruzioni (ISA) ma con diversa microarchitettura eseguendo lo stesso codice con ottimizzazioni statiche possono fornire prestazioni molto diverse. Un cambio di microarchitettura può richiedere una ricompilazione del codice per poter sfruttare le reale prestazioni del microprocessore, cosa non necessaria con l'ILP dinamica.
L'ILP statico utilizza molte tecniche di analisi e di ottimizzazioni comuni a l'ILP dinamico ma non dovendo eseguire le ottimizzazioni in tempo reale le analisi possono essere molto più approfondite e quindi le prestazioni migliori. Per esempio nel caso della tecnica di srotolamento dei loop il compilatore analizzando il codice può riconoscere i loop e ottimizzandolo. Per esempio supponendo di avere del codice del tipo:
1) i = 0 2) FOR i <1000 3) x[i]=x[i]+s 4) i = i + 1 //fine FOR
Il compilatore riconoscendo il codice potrebbe notare che il loop viene eseguito mille volte e dato che la parte critica è il salto condizionato (istruzione 2) potrebbe scrivere:
1) i = 0 2) FOR i <1000 3) x[i]=x[i]+s 4) i = i + 1 5) x[i]=x[i]+s 6) i = i + 1 //fine FOR
Questo loop viene eseguito solo 500 volte dato che dentro un singolo loop sono state inserite le istruzioni che precedentemente venivano eseguite in due loop. Il procedimento può essere iterato includendo altre istruzioni e quindi riducendo anche il numero di salti da eseguire, che sono delle istruzioni che dal punto di vista del programma non producono risultati utili dato che non influenzano direttamente i dati ma solo il flusso del programma. Il codice generato dallo srotolamento del loop può essere migliorato eseguendo una ridenominazione dei registri e una riorganizzazione delle istruzioni che migliora le prestazioni. Per esempio il codice iniziale eseguito su un processore MIPS senza nessuna ottimizzazione richiede 10 cicli di clock per ogni loop, applicando le varie ottimizzazioni si ottiene un'esecuzione in 3.5 cicli di clock per ogni loop. Il compilatore quando applica queste tecniche deve tenere conto anche dei problemi che queste portano. Lo srotolamento del loop aumenta la dimensione del codice e quindi la possibilità di non trovare i dati in cache. Inoltre un eccessivo uso della ridenominazione dei registri può terminare i registri temporanei costringendo il processore a utilizzare la lenta memoria di sistema per salvare i registri non usati.
L'ILP statico ovviamente cerca di sfruttare la presenza di più unità di calcolo, nell'esempio del loop supponendo di avere un processore con due pipeline indipendenti si potrebbe ridurre il tempo di esecuzione da 3.5 cicli di clock per loop a 2.5 cicli di clock per loop. I processori che utilizzano l'ILP statico utilizzano generalmente meglio le pipeline, dato che il compilatore può analizzare il codice in profondità e può cercare l'organizzazione migliore delle istruzioni in modo da massimizzare l'utilizzo della pipeline. Spesso questi compilatori raggruppano le istruzioni in pacchetti che una volta ricevuto dal processore vengono semplicemente inviate alle pipeline, il processore non deve controllare alee o altro dato che tutto è stato analizzato dal compilatore e gli eventuali problemi sono già stati risolti, questi processori sono detti processori very long instruction word (VLIW).
Nei processori VLIW il compilatore esegue tutte le ottimizzazioni mentre il processore non fa altro che ricevere le istruzioni ed eseguirle quindi un processore VLIW è molto più semplice di un processore con ILP dinamico di pari velocità. Dipendendo in modo totale dal compilatore per le prestazioni i compilatori utilizzano tecniche di analisi avanzate del codice per individuare il parallelismo instrinseco. Le principali sono:
Il compilatore cerca di prevedere il risultato dei salti (branch) tramite analisi statistiche del codice in modo da mantenere le pipeline sempre cariche. Queste tecniche ricalcano quelle applicate dai processori con ILP dinamico ma in questo caso forniscono mediamente prestazioni inferiori a quelle fornite da microprocessori con unità di predizione delle diramazioni allo stato dell'arte dato che il microprocessore è in grado di adeguarsi all'esecuzione dinamica del programma mentre il compilatore può solo stimare statisticamente come il programma si comporterà durante l'esecuzione.
Questa tecniche cerca di individuare il parallelismo tra iterazioni successive del loop nel caso di loop con cicli non indipendenti.
Con questa tecnica si decide di non srotolare i loop ma di aggiungervi all'interno delle istruzioni indipendenti in modo da evitare lo stallo durante l'esecuzione.
Questa tecnica analizza il codice alla ricerca di istruzioni indipendenti, l'esplorazione prosegue anche se il compilatore trova delle istruzioni condizionate (come salti o cicli).
Le tecniche di analisi del codice funzionano bene quando si riesce a prevedere con un elevato margine di accuratezza il comportamento dei salti condizionati. I salti condizionati sono molto frequenti nel codice (mediamente ogni 7 -10 istruzioni si ha un salto) e possono deprimere le prestazioni delle architetture a pipeline in modo rilevante. Le tecniche di analisi statistiche funzionano bene nel caso di istruzioni di salto che si ripetono in modo regolare (per esempio nei cicli) mentre negli altri casi i salti sono difficilmente predicibili. Per limitare l'impatto di questi salti si possono utilizzare lei istruzioni predicative (o condizionate). Le istruzioni predicative convertono una dipendenza dal controllo in una dipendenza sui dati eliminando in alcuni casi dei salti condizionati difficilmente predicibili. Le istruzioni predicative sono delle normali istruzioni che però vengono eseguite se una certa condizione è vera (o falsa a seconda dei casi). L'esempio più semplice (e comune) è la move condizionata. Questa istruzione copia il valore di un registro in un altro registro se la condizione associata è vera. Per esempio il codice
if (A == 0) H = J
verrebbe tradotto senza istruzioni condizionate come:
1) Se A = 0 → salta a 2) altrimenti → 3) 2) H = J
Con le istruzioni condizionate invece ottengo
1) A = 0, allora H = J
Il nuovo codice utilizza una sola istruzione quindi è più compatto e inoltre elimina un salto, invece di un'istruzione di salto e di una move ho solo una move condizionata che dipende unicamente dai dati, quindi ho eliminato l'istruzione di salto, che essendo singola e non legata a una qualche logica è difficile da prevedere. Questa strategia più essere estesa includendo praticamente tutte le istruzioni del processore, i processori Itaniuim per esempio possiedono istruzioni predicati che possono sostituire tutte le istruzioni classiche (il processore è del tipo full predication). Comunque la maggior parte dei processori si limita alle move predicative dato che negli altri casi l'utilizzo di istruzioni predicative aumenta la dimensione del processore senza necessariamente incrementare le prestazioni dello stesso. Comunque le move predicative sono talmente utili che anche molti processori che implementano sofisticate tecniche di ILP dinamico utilizzano anche le move condizionate per migliorare le prestazioni.
Un ulteriore metodo per migliorare le prestazioni è il caricamento speculativo, il compilatore analizzando il codice potrebbe individuare delle istruzioni o dei dati che probabilmente verranno richiesti e quindi porre delle load speculative. Queste load caricano i dati o le istruzioni prima della loro effettiva richiesta eliminando o comunque limitando i tempi di caricamento dalla memoria. Ovviamente possono sorgere dei problemi se i dati caricati fossero modificati prima del loro reale utilizzo. In caso di scrittura il processore controlla se le celle scritte sono state caricate in modo speculativo e in tal caso le elimina in modo da evitare incoerenze di esecuzione.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.