LInstruction level parallelism (ILP, ) 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.
Storia 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: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.
1940 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.brevetto US 2,636,672 Il trasferimento dei dati era effettuato in modo asincrono.(appendice A of Bashe, Johnson, Palmer, and Pugh, 1986) [cf. Harvard Mark II]
1950 Gene Amdahl (1950) nella sua tesi descrive una pipeline a quattro stadi (caricamento istruzione, caricamento dati, esecuzione, salvataggio risultati). 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, distribuito 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. 1956 IBM propone fino a sei istruzioni eseguite per ciclo di clock in un nuovo decodificatore delle istruzioni per l'IBM 7030 Stretch.
1960 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.Very high-speed computing systems Proceedings of the IEEE Volume 54, Issue 12, Dec. 1966 Page(s):1901 - 1909 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 Articolo del 1970 sulla decodifica multipla di istruzioni da parte del 7094 scritto da Tjaden e Flynn.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 Elbrus 1 "implementazione superscalare" (1973-1978). Brevetto Burroughs 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", 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.Overlapped Operation with Microprogramming IEEE: Transactions on Computers Volume C-27, Issue 3, March 1978 Page(s):270 - 275 CDC Flexible Processor (1979) - VLIW.datapath reminiscent of Elliott 152/153]
1980 Brevetto ottobre 1981 James H. Pomerene (IBM), "Machine for multiple instruction execution", 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.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 Progetto di Jim Smith sull'architettura DAE (1982) - Astronautics ZS-1.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 Progetto ELI-512 del 1983 di Josh Fisher sull'architettura VLIW, il progetto sfrutta la trace scheduling sviluppata da Fisher.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 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.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 Articolo di Hwa C. Torng nel 1986 sul dispatch stack a più unità.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 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) superscalare 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 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 2001, presentazione dei processori Intel Itanium basati su architettura EPIC. Giugno 2003 Articolo di K. Sankaralingam, R. Nagarajan, H. Liu, J. Huh, C.K. Kim D. Burger, S.W. Keckler, e C.R. Moore sull'instruction set Explicit Data Graph Execution e correlata architettura dal titolo "Exploiting ILP, DLP, and TLP Using Polymorphism in the TRIPS Architecture".30th Annual International Symposium on Computer Architecture (ISCA), pp. 422-433 2005 Presentazione dell'architettura TRIPS basata sull'Explicit Data Graph Execution.
Grado di parallelismo 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 Per aumentare il livello di parallelismo nei microprocessori esistono in sostanza due strategie.