Instruction level parallelism

Da Wikipedia, l'enciclopedia libera.

L'Instruction level parallelism (parallelismo a livello d'istruzione) è una misura delle istruzioni in un programma che possono essere eseguite in parallelo da un sistema di calcolo.

La ricerca di codice parallelo a livello di istruzioni è una priorità nei moderni microprocessori, questi 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.

Storia[modifica | modifica wikitesto]

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]

1940[modifica | modifica wikitesto]

  • Z3 (1941, brevetto 1949) - esecuzione parallela di alcune componenti delle istruzioni.
  • Z4 (1944, ricostruito nel 1949) caricamento di due istruzioni in parallelo se non vincolate, in modo da ridurre i tempi di accesso.
  • Bell Labs Model V (1946), due processori con un gestore che distribuiva le istruzioni base alle unità libere.
  • Nel 1946 Alan Turing propone la costruzione dell'Automatic Computing Engine, il sistema ha un formato delle istruzioni complesso con tempi di esecuzione dipendenti dagli operandi. Nel Pilot ACE l'inserimento dei dati in alcune specifiche locazioni di memoria produceva l'esecuzione di alcune operazioni come per esempio la loro somma.
  • IBM SSEC (1948), due istruzioni se non dipendenti venivano unite in una sola linea in modo da poterle far eseguire in parallelo al computer.[2] Il trasferimento dei dati era effettuato in modo asincrono.[3]

1950[modifica | modifica wikitesto]

  • Gene Amdahl (1950) nella sua tesi descrive una pipeline a quattro stadi (caricamento istruzione, caricamento dati, esecuzione, salvataggio risultati).[4]
  • Nel sistema Elliott 152 (1950) viene inserito un dispositivi in grado di eseguire fino a 4 istruzioni da 20 bit per ciclo di clock.
  • Nel computer Harvard Mark IV (1952) le moltiplicazioni e le divisioni possono essere eseguite in parallelo in modo concorrente con le altre istruzioni (le moltiplicazioni sono sei volte più lente delle altre istruzioni e le divisioni sono venti volte più lente delle altre istruzioni).
  • Un articolo di Wilker e Stinger (1953) suggerisce la possibilità di raccogliere istruzioni indipendenti in una sola macroistruzione da far caricare al computer.
  • Nel sistema Elliot 153 (1954), istruzione a 64 bit che specificano caricamenti multipli nei registri.
  • IBM 7030 Stretch (fine 1950, rilasciato nel 1961) supercomputer con capacità di pre-esecuzione, esecuzione speculativa e recupero degli errori di predizione dei salti.
  • Computer UNIVAC LARC (fine 1950) pipeline a quattro stadi.[5]
  • 1956 IBM propone fino a sei istruzioni eseguite per ciclo di clock in un nuovo decodificatore delle istruzioni per l'IBM 7030 Stretch.

1960[modifica | modifica wikitesto]

  • CDC 6600 (1964) processore scalare con esecuzione fuori ordine, dieci unità funzionali nella CPU. La CPU decodifica un'istruzione per ciclo di clock e la invia allo scoreboard che può avviare fino a tre istruzioni in contemporanea (limitazione dovuta alla presenza di registri a tripla porta). Fino a quattro istruzioni possono terminare per ciclo di clock. Individuazioni di condizioni di conflitto tra le istruzioni e risoluzione tramite stalli. Possibilità di implementare una rudimentale esecuzione multithreading.
  • 1966 Articolo sui sistemi di calcolo ad alta velocità di Flynn, questo porterà alla tassonomia di Flynn.[6]
  • IBM S/360 Model 9 (1967), pipeline scalare con esecuzione fuori ordine tramite l'algoritmo di Tomasulo nell'unità in virgola mobile.
  • IBM ACS (fine 1960) proposto un processore superscalare a 7 vie.
  • 1969 articolo sullo sviluppo di un primitivo sistema VLIW di Melliar-Smith.

1970[modifica | modifica wikitesto]

  • Articolo del 1970 sulla decodifica multipla di istruzioni da parte del 7094 scritto da Tjaden e Flynn.[7]
  • Elbrus 1 "implementazione superscalare" (1973-1978).
  • Brevetto Burroughs[8] ottobre 1971, "Mechanism to control the sequencing of partially instructions in a parallel data processing system", sulla gestione di sequenze di istruzioni parzialmente ordinate in sistemi paralleli.
  • Brevetto Culler (Culler-Harrison) (1973) "Data processor with parallel operations per instruction",[9] elaborazione di dati tramite istruzioni eseguite in parallelo.
  • Floating Point Systems produce FPS AP-120B (1975) / FPS-164 (1980) due coprocessori matematici con architettura simil VLIW.
  • Articolo del 1978 sulla gestione concorrente di bit di controllo da parte Lee Higbie. Alle istruzioni vengono aggiunti dei bit di controllo gestiti dal programma o dal compilatore.[10]
  • CDC Flexible Processor (1979) - VLIW.[11]

1980[modifica | modifica wikitesto]

  • Brevetto ottobre 1981 James H. Pomerene (IBM), "Machine for multiple instruction execution",[12] sulla realizzazione di sistemi che elaborano gruppi di istruzioni indipendenti contemporaneamente.
  • Progetto di Bob Rau sull'architettura VLIW (1981) - Polycyclic Architecture project al TRW/ESL.[13]
  • Progetto di Jim Smith sull'architettura DAE (1982) - Astronautics ZS-1.[14]
  • Progetto ELI-512 del 1983 di Josh Fisher sull'architettura VLIW, il progetto sfrutta la trace scheduling sviluppata da Fisher.[15]
  • Cydrome (1983-1988) - VLIW.
  • Multiflow (1984-1990) VLIW.
  • Nel 1985 Yale Patt analizza la possibilità di gestire le istruzioni VAX (CISC) dinamicamente al fine di incrementarne il parallelismo.[16]
  • Articolo di Hwa C. Torng nel 1986 sul dispatch stack a più unità.[17]
  • Culler-7 (1986) lavori sull'architettura DAE/LIW.
  • CHoPP (metà 1980) - sistema a nove vie.
  • Due vie IBM Cheetah e Panther (metà 1980, predecessori del quattro vie America e IBM RS/6000, basato sull'articolo del 1986 FJCC su i compilatori per macchine a due vie).
  • Bell Labs CRISP (1987) organizzazione dei salti nella cache dati.
  • Horizon, sistema sviluppato nel 1988 da Burton Smith con individuazione delle istruzioni indipendenti e loro esecuzione.
  • Stellar GS-1000 (1988) quattro vie multitreading, due istruzioni per ciclo.
  • Apollo DN10000 (1988) processore Apollo PRISM, due vie LIW.
  • Intel i860 (1988) due vie LIW.
  • Intel i960CA (1989) superscalare a tre vie.
  • IBM RS/6000 (1989) supercalare a quattro vie.
  • Hatfield Risc Processor (1989) VLIW con predicazione e con writeback, permette la trasmissione degli operandi tra gli stadi delle pipeline senza memorizzare i dati nei registri al fine di ridurre le scritture nei registri.

1990[modifica | modifica wikitesto]

  • National Semiconductor Swordfish (1990) processore superscalare a due istanze con disegno LIW e decodifica dei dati all'interno della cache istruzioni.
  • IBM ES/9000-900 (1990) implementazione superscalare con esecuzione fuori ordine dei mainframe IBM.
  • Metaflow Lightning/Thunder (1991/1995) semplice esecuzione fuori ordine progettata per processori SPARC.
  • Transmeta Processori VLIW con Code Morphing Software.

2000[modifica | modifica wikitesto]

Grado di parallelismo[modifica | modifica wikitesto]

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:

  • Numero di unità funzionali: Banalmente se il processore è dotato di quattro unità di calcolo questo non potrà eseguire più di quattro istruzioni in parallelo anche se nel codice fossero presenti più istruzioni eseguibili in parallelo.
  • Dipendenze sui dati: Il processore non può eseguire (o completare) un'istruzione se non ha tutti i dati, se alcuni dati devono essere ancora elaborati (come nell'esempio con l'istruzione 3) il processore non può mandare in esecuzione (o completare, dipende da come è costruita l'unità funzionale) l'istruzione.
  • Dipendenza dal controllo: Il codice che si trova dopo un salto condizionato non può essere eseguito se prima non si stabilisce il risultato del salto condizionato.

Livelli di parallelismo[modifica | modifica wikitesto]

Per aumentare il livello di parallelismo nei microprocessori esistono in sostanza due strategie.

  • La prima prevede l'aumento degli stadi nella pipeline, ovvero la profondità della pipeline. Pipeline con più stadi possono eseguire, in teoria, più istruzioni in parallelo dato che hanno più possibilità di sovrapporre le istruzioni nei vari stadi della pipeline. Inoltre (e principalmente) molti stadi implicano che ogni stadio deve eseguire una frazione più semplice dell'istruzione e quindi può eseguirla più rapidamente, questo consente di innalzare la frequenza di funzionamento dei microprocessori. Per esempio alcuni modelli di Pentium 4 hanno più di 30 stadi nelle pipeline. Questa strategia ha dei limiti dato che per esempio le pipeline molto lunghe diventano molto inefficienti nel caso di salti e difatti la maggior parte dei microprocessori hanno un numero di stadi compresi tra 10 e 15.
  • La seconda strategia prevede l'utilizzo di più unità di esecuzione indipendenti che eseguano istruzioni in parallelo. Questa tecnica viene detta multiple issue e il suo svantaggio principale è una maggior complessità del processore difatti oltre alla presenza di più unità di calcolo il processore deve disporre di un bus interno ampio in modo di trasportare i dati tra le varie unità senza colli di bottiglia. Inoltre le singole unità funzionali come le cache devono poter rilasciare più dati in parallelo e gli stessi registri devono poter leggere e scrivere più dati in parallelo. Le architetture in grado di eseguire più istruzioni in parallelo sono dette superscalari, e l'analisi del parallelismo a livello di istruzione per questa tipologia di processori è ovviamente fondamentale.

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.

Tipologie di ILP[modifica | modifica wikitesto]

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.

ILP dinamico[modifica | modifica wikitesto]

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 dipendo 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 cha 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[modifica | modifica wikitesto]

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à quasi 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, etc. 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:

  • Static branch prediction:

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.

  • Loop Level Parallelism.

Questa tecniche cerca di individuare il parallelismo tra iterazioni successive del loop nel caso di loop con cicli non indipendenti.

  • Symbolic loop unrolling.

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.

  • Global code scheduling.

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).

  • Tecniche predicative

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 speculare e in tal caso le elimina in modo da evitare incoerenze di esecuzione.

Note[modifica | modifica wikitesto]

  1. ^ Linea del tempo basata sull'articolo Instruction- Level Parallel Processing: History , Overview and Perspective B. Ramakrishna Rau, Joseph A. Fisher Computer Systems Laboratory HPL-92-132 October, 1992 con integrazioni successive.
  2. ^ brevetto US 2,636,672
  3. ^ (appendice A of Bashe, Johnson, Palmer, and Pugh, 1986) [cf. Harvard Mark II]
  4. ^ (EN) Tesi di Gene Amdahl
  5. ^ (EN) Engineering Considerations of the LARC
  6. ^ Very high-speed computing systems Proceedings of the IEEE Volume 54, Issue 12, Dec. 1966 Page(s):1901 - 1909
  7. ^ Detection and Parallel Execution of Independent Instructions Tjaden, G.S.; Flynn, M.J.; Computers, IEEE Transactions on Volume C-19, Issue 10, Oct. 1970 Page(s):889 - 895
  8. ^ (EN) US 3,611,306
  9. ^ (EN) Brevetto US 3,771,141
  10. ^ Overlapped Operation with Microprogramming IEEE: Transactions on Computers Volume C-27, Issue 3, March 1978 Page(s):270 - 275
  11. ^ datapath reminiscent of Elliott 152/153]
  12. ^ US 4,295,193 1981
  13. ^ Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing International Symposium on Microarchitecture archive Proceedings of the 14th annual workshop on Microprogramming table of contents Chatham, Massachusetts, United States Pages: 183 - 198 anno: 1981 ISSN:1050-916X
  14. ^ Decoupled access/execute computer architectures International Symposium on Computer Architecture archive Proceedings of the 9th annual symposium on Computer Architecture table of contents Austin, Texas, United States Pages: 112 - 119 anno:1982 James E. Smith
  15. ^ Very Long Instruction Word architectures and the ELI-512 IEEE-CS : Computer Society, SIGARCH: ACM Special Interest Group on Computer Architecture Pages: 140 - 150 anno: 1983 ISBN:0-89791-101-6
  16. ^ Retrofitting the VAX-11/780 microarchitecture for IEEE floating point arithmetic—implementation issues, measurements, and analysis David B. Aspinwall, Yale N. Patt; IEEE Transactions on Computers archive Volume 34 , Issue 8 (August 1985) table of contents Pages: 692 - 708 Year of Publication: 1985 ISSN:0018-9340
  17. ^ An Instruction Issuing Approach to Enhancing Performance in Multiple Functional Unit Processors Acosta, R.D.; Kjelstrup, J.; Torng, H.C.; IEEE: Transactions on Computers Volume C-35, Issue 9, Sept. 1986 Page(s):815 - 828
  18. ^ 30th Annual International Symposium on Computer Architecture (ISCA), pp. 422-433
  19. ^ TRIPS, il calcolo a teraherz, Le Scienze, 27-4-2007. URL consultato il 16-10-2007.

Collegamenti esterni[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica