Introduzione a SISD e Pipelining PDF

Introduzione Classificazione delle Architetture Classificazione in base al numero di istruzioni eseguibili ¤ Architetture CISC (Complex Instruction Set Computer) Il set di istruzioni è costituito da numerose istruzioni con formato a lunghezza variabile, ovvero comprende sia istru...

Introduzione Classificazione delle Architetture Classificazione in base al numero di istruzioni eseguibili ¤ Architetture CISC (Complex Instruction Set Computer) Il set di istruzioni è costituito da numerose istruzioni con formato a lunghezza variabile, ovvero comprende sia istruzioni semplici sia istruzioni complesse la cui esecuzione richiede l’utilizzo di una unità di controllo microprogrammata ¤ Architetture RISC (Reduced Instruction Set Computer) Il set di istruzioni è costituito da un ridotto numero di istruzioni con formato a lunghezza fissa, ovvero comprende solo istruzioni semplici , che possono essere eseguite velocemente mediante un’unità di controllo cablata Architetture CISC L’approccio CISC è stato introdotto per supportare meglio la programmazione ad alto livello l’uso dei linguaggi di alto livello origina un gap, ossia una notevole differenza tra le operazioni consentite dal linguaggio e quelle fornite dall’architettura del calcolatore Le architetture CISC sono caratterizzate da un ricco insieme di istruzioni macchina, simili ai comandi di alto livello compilatori meno complessi e codice eseguibile più compatto Architetture RISC Approccio RISC: livello di microprogrammazione assente Caratteristiche di un’architettura RISC Poche istruzioni macchina semplici Le istruzioni prevedono operandi nei registri Solo poche istruzioni (es. le istruzioni Load e Store) fanno riferimento alla memoria Molti registri generali disponibili Semplici modi di indirizzamento Semplici formati delle istruzioni Un’istruzione macchina è solitamente completata in un ciclo macchina Architetture CISC e RISC Architettura IA-32 (famiglia processori Intel fino al Pentium IV) è di tipo CISC ¤ Istruzioni macchina di lunghezza variabile ¤ Differenti formati d’istruzione difficili da decodificare velocemente ¤ Pochi registri, molte istruzioni fanno riferimento alla memoria Architettura IA-64 (nuova famiglia processori Intel a partire da ITANIUM) è di tipo RISC ¤ Istruzioni macchina di lunghezza fissa ¤ Formati d’istruzione facili da decodificare ¤ Molti registri (128 in ITANIUM 2), poche istruzioni che fanno riferimento alla memoria Classificazione di Flynn (1972) SISD (Single Instruction Single Data) Un singolo processore esegue un flusso di istruzioni per operare su un insieme di dati (modello di Von Neumann) SIMD (Single Instruction Multiple Data) Un’istruzione macchina è eseguita simultaneamente su più insiemi di dati MISD (Multiple Instruction Single Data) Più processori eseguono diverse sequenze di istruzioni su uno stesso insieme di dati Modello non realizzato commercialmente MIMD (Multiple Instruction Multiple Data) ¤ Più processori eseguono simultaneamente diverse sequenze di istruzioni su diversi insiemi di dati ¤ Multiprocessori ¤ Multicomputer Modello SISD È il modello di von Neumann, costituito da un unico processore in grado di eseguire una sola istruzione per volta su un dato di tipo scalare ¤ Una istruzione vettoriale è trasformata in una istruzione scalare ripetuta nel tempo (ciclo) L’elaborazione è strettamente sequenziale ¤ È possibile eseguire solo una istruzione dopo l’altra ¤ L’ordine di esecuzione è fissato dal programma Modello SISD Memoria CPU CU Periferica 1 Periferica 2 ALU BUS Modello SISD Limite architetturale del modello SISD ¤ singola connessione tra memoria e processore (collo di bottiglia) il processore può prelevare dalla memoria una istruzione per volta Tecniche per superare tale limite ¤ Allargamento del bus di dati ¤ Introduzione della memoria cache ¤ Parallelismo temporale (a livello di istruzione) Introduzione del Pipelining Stadi del ciclo d’istruzione S1 S3 S5 Fetch Fetch Write istruzione operandi back S2 S4 Decode Execute SISD con Pipelining L’esecuzione di una istruzione è divisa in più fasi dette stadi (fetch, decode, operand fetch, execute,…) Con la tecnica del pipelining si realizza una sovrapposizione temporale degli stadi di più istruzioni ¤ Ogni stadio è gestito da un’unità HW dedicata, per consentire l’esecuzione simultanea di più fasi di istruzioni diverse Fk Dk Ok Ek Fk+1 Dk+1 Ok+1 Ek+1 Fk+2 Dk+2 Ok+2 Ek+2 Fk+3 Dk+3 Ok+3 Ek+3 t SISD con Pipelining Pipeline a cinque stadi SISD con Pipelining Il modello SISD basato su pipelining: ¤ resta un modello seriale viene mantenuta la sequenza temporale tra le istruzioni e tra le varie fasi all’interno dell’istruzione opera in parallelo su più istruzioni che si trovano a successivi stadi di elaborazione in uno stesso istante le diverse unità elaborano in parallelo i diversi stadi delle istruzioni ¤ Il parallelismo è realizzato a livello di stadi del ciclo d’istruzione SISD con Pipelining Il vantaggio del pipelining non è quello di eseguire più velocemente una singola istruzione ¤ Il completamento di una singola istruzione richiede tanti cicli di clock quanti sono gli stadi della pipeline Il vantaggio del pipelining è quello di aumentare la frequenza di completamento delle istruzioni ¤ Aumenta il numero di istruzioni eseguite per secondo (Throughput ) SISD con Pipelining Latenza: numero di cicli necessari a completare una singola istruzione ¤ la latenza non cambia con l’introduzione della pipeline ¤ se la pipeline ha K stadi, la latenza è di K cicli di clock Throughput: frequenza di completamento delle istruzioni = (n. istruzioni completate/ciclo) ¤ il throughput aumenta con l’introduzione di pipeline ¤ tipicamente un processore con una pipeline ha un throughput di una istruzione completata per ciclo SISD senza pipeline: throughput=1/latenza SISD con pipeline: throughput>1/latenza SISD con Pipelining Due processori con la stessa frequenza di clock possono avere velocità di elaborazione diverse se uno utilizza il pipelining e l’altro no Una pipeline con K stadi può elaborare N istruzioni in un tempo pari a K+(N-1) cicli di clock ¤ K cicli sono necessari per completare l'esecuzione della prima istruzione ¤ N-1 cicli sono necessari per completare le rimanenti N-1 istruzioni SISD con Pipelining Il modello SISD senza pipeline elabora N istruzioni in un numero di cicli di clock pari a KN Il modello SISD con pipeline (nel caso ideale) elabora N istruzioni in un numero di cicli di clock pari a K+(N-1) Il guadagno massimo (speed-up) nella esecuzione di N istruzioni con pipeline a K stadi, rispetto alla esecuzione delle stesse N istruzioni senza pipeline è KN speed _ up = K + ( N − 1) Lo speed-up introdotto dalla pipeline si riferisce al caso ideale ¤ Sequenza lineare di istruzioni indipendenti SISD con Pipelining Nei casi reali vi sono diversi fattori che, limitando la potenzialità della pipeline: ¤ presenza di istruzioni di salto (branch hazard) il processore non è in grado di stabilire la successiva istruzione da prelevare finché l’istruzione di salto non è stata decodificata ¤ dipendenza tra istruzioni (data hazard) Es. conflitto RAW (Read After Write) si verifica quando un’istruzione deve operare sul risultato di un’altra istruzione SISD con Pipelining La presenza di istruzioni di salto condizionato blocca la pipeline perché impedisce il pre-fetching delle istruzioni Soluzioni ¤ Delayed branch: si anticipa comunque il fetch dell’istruzione successiva Se il salto non viene effettuato, non si blocca la pipeline Se il salto viene effettuato, l’istruzione già prelevata deve essere eliminata dalla pipeline ¤ Branch prediction: si prevede il salto in modo dinamico, cioè durante l’esecuzione del programma Si usa una Tabella della storia dei salti che memorizza la storia delle istruzioni di salto di uno specifico programma Ogni entry della tabella si riferisce ad una istruzione di salto e contiene: indirizzo della istruzione di salto, indirizzo dell’istruzione a cui saltare, un bit o N bit che indicano se l’ultima volta (o le ultime N volte) il salto è stato effettuato o meno SISD con Pipelining Un altro fattore che blocca la pipeline è la dipendenza tra le istruzioni (data hazard) Esempio (dipendenza RAW) C=A+B D=C-1 Necessità di inserire una logica di controllo nel processore per implementare complessi schemi di scheduling (riordino) delle istruzioni che riducano il più possibile le dipendenze ¤ HW più complesso ¤ Aumento dei consumi SISD con Pipelining - Limitazioni Non tutte le istruzioni necessitano di tutti gli stadi della pipeline ¤ L’esecuzione di istruzioni macchina complesse richiede tutti gli stadi della pipeline ¤ L’esecuzione di istruzioni macchina semplici (per es. quelle a zero operandi) non necessita di tutti gli stadi Per semplificare l’HW di gestione della pipeline, si assume che ogni istruzione richieda tutti gli stadi ¤ in presenza di istruzioni complesse, le istruzioni più semplici subiscono un rallentamento ¤ per questo motivo il modello con pipeline si applica meglio ad architetture RISC, dove la maggior parte delle istruzioni sono semplici