MASTER IN SISTEMI EMBEDDED PER L’INTERNET · 2016. 1. 22. · MASTER IN SISTEMI EMBEDDED PER...

MASTER IN SISTEMI EMBEDDED PER L’INTERNET OF THINGS

Architetture di Calcolo Avanzate per Sistemi Embedded

Docente: Francesca Palumbo

UNISS - Università degli Studi di Sassari

PolComIng – Gruppo di Ingegneria

dell’Informazione


INFO GENERALI

• Corso da 24 ore prevalentemente lezioni frontali.

• Valutazione Finale

• Come contattarmi:

– [email protected]

– [email protected] .it

• Materiale di supporto:

– Le slides utilizzate a disposizione sono disponibili su

http://people.unica.it/francescapalumbo/didattica/materiale-didattico/


OBIETTIVI E PROGRAMMA

• Studio delle caratteristiche, potenzialità e limitazione delle architetture avanzate per sistemi embedded.

• Programma

– Incremento delle prestazioni nei moderni sistemi di calcolo

– Strutture di memoria e modelli di programmazione in architetture parallele

– Sistemi di interconnessione

– Sistemi a bassa dissipazione di potenza: metodologie di progettazione e supporto architetturale


Incremento delle prestazioni nei moderni sistemi di calcolo: • Tipi di parallelismo e classificazioni • Limiti e costi dell’approccio parallelo • Instruction Level Parallelism:

Il pipelining delle istruzioni Processori superscalari Processori VLIW

• Thread Level Parallelism: Multi-Threading, Chip Multi-Processors e Massively Parallel


SCALING TECNOLOGICO E PERFORMANCE

• Uno dei vincoli principali nella progettazione di sistemi embedded è, da sempre, l’incremento delle performance: – Il trend che ha portato alla crescita delle frequenze di

funzionamento per le tecnologie CMOS dovrà, prima o poi, arrestarsi al raggiungimento dei limiti fisici di tale tecnologia.

– Per minimizzare i tempi di esecuzione di un codice su un processore è necessario percorrere altre strade

– More than Moore: nuove possibili strade (e.g. materiali alternativi al silicio).

– More Moore: si continua a seguire la legge di Moore (ogni due anni raddoppia il numero di gate), con approcci architetturali diversi.


IL CALCOLO SEQUENZIALE

• Di base un processore è una macchina sequenziale, il software è sempre stato scritto per la sua esecuzione seriale:

tN t3 t2 t1

PROBLEMA

istruzioni

Programmazione +Compilazione+

Assembly

esecuzione

Core

– Un problema è suddiviso in una serie discreta di istruzioni

– Le istruzioni vengono eseguite in sequenza

– L’esecuzione è assegnata ad un singolo processore

– Il processore esegue una istruzione alla volta


INCREMENTARE LE PERFORMANCE • Nel tempo le performance delle architetture a singolo

processore sono crollate, principalmente perché la frequenza di funzionamento non può essere spinta all’infinito:

– power wall: maggiore è la frequenza di funzionamento di un sistema maggiore è la potenza che esso dissipa (P ∝ f)

– memory wall: problemi computazionali complessi richiedono una disponibilità di memoria fisica elevata

• SOLUZIONE: Adattare l’architettura del processore alle esigenze di parallelismo che l’applicazione presenta, al fine di minimizzare il tempo di esecuzione totale (speed up), svolgendo più task contemporaneamente, o di risolvere un problema più grande (scale up), grazie ad una maggiore potenza di calcolo.

– Il calcolo parallelo è più adatto a modellare, simulare e comprendere la complessità dei fenomeni del mondo reale.


IL CALCOLO PARALLELO

• Nel calcolo parallelo più risorse computazionali vengono usate in maniera simultanea per risolvere un dato problema:

PROBLEMA – Un problema è suddiviso in parti distinte risolvibili contemporaneamente

– Ogni parte suddivisa in una serie di istruzioni

– Istruzioni di parti diverse vengono eseguite contemporaneamente su risorse diverse

– E’ necessario un meccanismo di controllo per coordinare la risoluzione del problema

Core

Core

Core


APPLICAZIONI PARALLELE

• Il calcolo parallelo storicamente è stato utilizzato per la modellazione e risoluzione di problemi fisico/ingegneristici complessi

– fenomeni atmosferici, terrestri o ambientali, simulazioni genetiche, analisi geologiche e sismologiche…

• Oggi le applicazioni commerciali stesse richiedono l'elaborazione di grandi quantità di dati in maniera sofisticata

– elaborazione di immagini diagnostiche, calcolo finanziario, grafica avanzata e realtà virtuale (applicate all’entertainment)


TIPI DI PARALLELISMO

PARALLELISMO

A LIVELLO DI ISTRUZIONE • Throughput

elevato • Scarsa scalabilità

A LIVELLO DI THREAD

• Sincronizzazione • Risoluzione delle interdipendenze

A LIVELLO DI DATI

• Fortemente application-specific


PARALLELISMO A LIVELLO DI ISTRUZIONE

• Instruction Level Parallelism (ILP)

• L’ILP prevede l’esecuzione parallela di due o più istruzioni su unità funzionali separate, omogenee (se eseguono istruzioni dello stesso tipo) o eterogenee (se eseguono istruzioni di tipo differente).

• E’ sfruttabile sia da microprocessori general purpose che application specific.

• Sfruttare il parallelismo a livello di istruzione garantisce un throughput più elevato ma non è molto scalabile:

– limitazioni dovute a problemi strutturali (e.g. accesso in memoria, hazard strutturali);

– limitazioni dovute alla difficoltà di parallelizzazione del codice (e.g. hazard sui dati e di controllo).


PARALLELISMO A LIVELLO DI DATI

• Data Level Parallelism (DLP)

• Il DLP prevede l’esecuzione parallela di una medesima istruzione in contemporanea su più di un dato.

• Un codice capace di sfruttare un tale tipo di parallelismo è ben lungi dall’essere un codice di tipo generico. Applicazioni che si prestano intrinsecamente allo sfruttamento del DLP sono ad esempio:

– calcolo vettoriale (e.g. prodotti scalare per vettore)

– processing di segnali audio-video (dove la medesima operazione viene eseguita su uno stream di dati)


PARALLELISMO A LIVELLO DI THREAD • Thread Level Parallelism (TLP) • Il TLP prevede l’esecuzione contemporanea di diversi blocchi di

istruzioni, definiti appunto thread. • Non bisogna confondere il TLP con il concetto di sistema multi-

threaded tipico dei sistemi operativi. – Il multi-threading prevede la gestione ed esecuzione di un codice su una

unica CPU, sulla quale però i thread non vengono eseguiti contemporaneamente ma alternativamente attraverso strategie di scheduling a divisione di tempo.

– ll TLP prevede l’esecuzione dei thread in contemporanea su unità di esecuzione differenti.

• E’ critica la sincronizzazione fra thread e la risoluzione delle interdipendenze tra di essi. – A potrebbe necessitare di un dato non ancora prodotto da B

(interdipendenza). – A potrebbe dover modificare un dato con una frequenza più elevata

rispetto a quella di B C e D che condividono lo stesso dato (sincronizzazione).


CLASSIFICAZIONE DI FLYNN

• Nel 1966 Michael J. Flynn propose una classificazione dei sistemi di calcolo basata, non sulle caratteristiche della architettura, ma sulla possibilità di gestire contemporaneamente diversi flussi di istruzioni e sulla possibilità di far lavorare contemporaneamente ciascuna istruzione su dati differenti.

• La sequenza di istruzioni eseguite dalla CPU forma il flusso delle istruzioni e gli operandi necessari/prodotti all’/dall’esecuzione il flusso dei dati.

CPU MEMORY

flusso delle istruzioni

flusso dei dati


CLASSIFICAZIONE DI FLYNN

SINGOLO MULTIPLO

SIN

GO

LO

MU

LTIP

LO

SISD Single Instruction

and Single Data

SIMD Single Instruction

and Multiple Data

MISD Multiple

Instruction and Single Data

MIMD Multiple

Instruction and Multiple Data

single-core processori vettoriali

array sistolico multi-core

multi-computers

istruzioni

dati


SINGLE INSTRUCTION AND SINGLE DATA

• Non sfruttano alcuna forma di parallelismo e rientrano nel paradigma classico di esecuzione sequenziale delle istruzioni: ogni istruzione è caricata dalla memoria, decodificata, ed eseguita sui soli dati componenti il proprio set di operandi.

• Sono macchine costituite da una singolo core computazionale:

– Vecchie generazioni di computer e workstations

– Il MIPS nella versione sequenziale non-pipelined

ALU MEMORY Ds CONTROL

UNIT

Is

Is

Is = Ds = 1


SINGLE INSTRUCTION AND MULTIPLE DATA

• Calcolatori di questo tipo sono in grado di eseguire la medesima istruzione su un intero set o vettore di dati. Il tipo di parallelismo supportato è ovviamente il DLP.

• L’unità di controllo è centralizzata al fine di avere N unità (o processing elements, PEs) sincronizzate. La stessa istruzione memorizzata nel PC viene eseguita in parallelo su N dati.

PE_1 MEM_1 Ds_1 CONTROL

UNIT

Is

Is = 1 Ds = N

PE_N MEM_N

MEMORY

Ds_N


SINGLE INSTRUCTION AND MULTIPLE DATA

• La memoria dati può essere divisa in sotto-blocchi per generare flussi multipli di dati, come fosse una memoria distribuita.

• L’approccio funzionale, relativamente al singolo flusso, è come quello dei SISD. Ogni unità funzionale ha i propri registri di indirizzamento dedicati per poter accedere a dati diversi ed essere in grado di gestirli.

• Ogni PE deve completare la propria istruzione prima che si possa fare il fetch dalla memoria dell’istruzione successiva.


MULTIPLE INSTRUCTION AND SINGLE DATA

• Calcolatori di questo tipo sono in grado di eseguire istruzioni diverse sullo stesso dato.

• N unità di controllo gestiscono i diversi flussi i istruzioni eseguiti su N PEs separate. Queste ultime elaborano lo stesso dato prelevato da un’unica memoria condivisa.

PE_1 CONTROL UNIT_1

Is = N Ds = 1

PE_N

Ds

CONTROL UNIT_N

Is_1

Is_N

MEMORY Ds

Ds

Is_1

Is_N


MULTIPLE INSTRUCTION AND SINGLE DATA

• Esempi di architetture MISD

– Array sistolici: Il dato in ingresso fluisce attraverso una rete di processore cablati fra loro che combinano, elaborano, uniscono o riordinano il dati in ingresso in un risultato derivato. Altamente application-specific (e.g. convoluzione, correlazione, moltiplicazione di matrici…).

– Architetture Fault-tolerant: Viene sfruttata la ridondanza delle istruzioni per individuare e correggere tempestivamente gli eventuali errori.


MULTIPLE INSTRUCTION AND MULTIPLE DATA • Calcolatori di questo tipo sono composti da diverse unità

computazionali, le quali possono eseguire flussi di elaborazione diversi su set di dati diversi.

• N unità di controllo gestiscono i diversi flussi i istruzioni eseguiti su N PEs separate. Le quali elaborano N flussi di dati separati in maniera indipendente (non è necessario sincronizzare i task).

PE_1 CONTROL UNIT_1

Is = N Ds = N

PE_N

Ds

CONTROL UNIT_N

Is_1

Is_N

Is_1

Is_N

MEM_1 Ds_1

MEM_N

MEMORY

Ds_N


MULTIPLE INSTRUCTION AND MULTIPLE DATA

• Tutti i sistemi multiprocessore appartengono a questa categoria e possono essere omogenei o eterogenei.

• Intrinsecamente scalabili:

– progettati per essere venduto con un numero di PEs variabile,

– il software è tale da funzionare anche se il processore i-esimo di N smette di farlo.

• Si prestano naturalmente a sfruttare al meglio il TLP avendo a disposizione più unità computazionali sulle quali eseguire in parallelo il codice, ma ogni unità computazionale poi può sfruttare gli altri tipi di parallelismo per migliorare le sue prestazioni intrinseche.


MULTIPLE INSTRUCTION AND MULTIPLE DATA • Problematiche:

– condivisione dei dati (memoria condivisa vs memoria distribuita)

– coordinamento fra i diversi processori.

• Sfruttare il TLP implica un overhead di comunicazione e il dover scegliere opportunamente fra le infrastrutture di comunicazione esistenti in letteratura (e.g. shared bus, network on chip).

• Esempi: – super-computing centers e networked parallel computers

– Multi-Processor System on Chip (MPSoCs) e Massively Parallel Processor (MPPs)

• I singoli componenti di una architettura di tipo MIMD possono sfruttare forme di parallelismo diverse come ILP e DLP.


ARCHITETTURE DI CALCOLO ED ESECUZIONE

SINGOLO MULTIPLO

SIN

GO

LO

MU

LTIP

LO

istruzioni

dati


RIASSUMENDO…

PARALLELISMO

ILP • Pipelined processors

• Superscalari • VLIW

TLP • CMP • MPP

DLP

• Vector Processors

ARCHITETTURE DI CALCOLO

SISD processori

scalari, sequenziali,

non-pipelined

MIMD

CMP

SIMD

Vector Processors

MISD

Systolic Array


LEGGE DI AMDAHL

• Legge di Amdahl - il potenziale aumento di velocità del programma (speed up) è definito dalla frazione di codice (P) che può essere parallelizzato:

Pspeedup

1

1

– Nessuna porzione di codice parallelo

P = 0 => speed up = 1

– Tutto il codice parallelo P = 1 => speed up = ∞

– 50% del codice parallelo P = 0.5 => speed up = 2


LEGGE DI AMDAHL

• Dato N come il numero di processori in grado di eseguire la frazione parallela del codice e S quella sequenziale, si ha

SN

Pspeedup

1


COMPLESSITA’ E PORTABILITA’

• COMPLESSITA’:

– Le applicazioni parallele sono molto più complesse di quelle tradizionalmente seriali perché vanno gestiti più flussi di istruzioni e di dati.

– Il costo (in tempo del programmatore) è maggiore in tutte le fasi del flusso di progettazione dalla concezione al mantenimento, passando per programmazione, debug e ottimizzazione.

• PORTABILITA’:

– Le operazioni di standardizzazione della programmazione parallela negli ultimi anni (MPI, POSIX, OpenMP, …) hanno notevolmente ridotto il problema della portabilità dei programmi.

– Estensioni del codice vendor-specific rendono il codice poco portabile.

– Architetture hardware variabili influenzano la portabilità


RISORSE

• RISORSE:

– Ridurre il tempo totale di esecuzione di un codice implica un aumento oggettivo del tempo totale di esecuzione. Un codice parallelo che viene eseguito in 1 ora su 8 processori utilizza 8 ore di tempo di CPU.

– La quantità di memoria può essere maggiore per i codici paralleli che per quelli seriali:

• necessità di replicare i dati

• overhead associato alle librerie di gestione.

– Programmi brevi eseguiti in parallelo potrebbero risultare più onerosi che eseguiti in maniera seriale a causa dei costi associati

• alla configurazione dell'ambiente parallelo

• alla creazione dei task

• alla comunicazione fra task

• alla finalizzazione dei task


SCALING

• L'algoritmo non sempre è scalabile rispetto al numero di risorse. Non sempre l’aumento ulteriore di risorse, ed il relativo overhead di gestione, porta ad un miglioramento delle prestazioni complessive.

• L’hardware condiziona la scalabilità:

– banda complessiva verso cpu-memoria

– banda del sistema di interconnessione

– quantità di memoria totale disponibile

– velocità del processore


LINK E MATERIALE UTILE • https://computing.llnl.gov/tutorials/parallel_comp/

• http://www.lighterra.com/papers/modernmicroprocessors/

• “Struttura e progetto dei calcolatori” di David A. Patterson, John L. Hennessy


TEMPO MEDIO PER ISTRUZIONE

• Il tempo medio per istruzione (TMI) rappresenta l’intervallo di tempo medio necessario per l’esecuzione di una singola istruzione, ed è calcolabile come:

– CPI è il Clock Per Instruction: numero medio di cicli di clock necessari per eseguire un’istruzione

– CC è il Clock Cycle: durata di un colpo di clock

• Nelle architetture parallele l’obiettivo è migliorare il TMI

CCCPITMI

CCCPITMI 22

111 TMICCCPI

CCCPITMI


ANALISI DEL TMI

Microarchitettura a

singolo ciclo

CPI=1

CC elevato

CPI è ottimo ma CC è

condizionato dall’esecuzione della

istruzione più lenta (LOAD)

Microarchitettura

Multiciclo (5 cicli per

istruzione)

CPI=5

CC migliore

CPI è condizionato dal numero di

fasi in cui viene scomposta

l’esecuzione dell’istruzione ma il

CC è migliore perché


fase più lenta (nel caso migliore

1/5 del precedente)

Micoarchitettura

Pipelined

CPI≈1

CC ≈ precedente

CPI ≈1 perché si tende ad avere

un throughput di quasi una

istruzione per colpo di clock e il

CC come nel caso precedente è


fase più lenta


PIPELINING - ILP • Le unità funzionali di base, necessarie all’esecuzione di una

istruzione macchina, vengono organizzate in “stadi” (Fetch-Decode-Execute-Memory-WriteBack). Gli stadi sono utilizzati in sequenza al fine di completare una singola esecuzione. – Latenza di completamento = numero di stadi da attraversare

– Throughput => tende a 1.

• Obiettivo: migliorare le prestazioni sfruttando l’intrinseco parallelismo presente in un flusso di istruzioni sequenziale: – Sfruttamento dell’overlapping dell’esecuzione di istruzioni

differenti

– Problemi di interdipendenza fra i dati

– Problemi strutturali nella gestione di unità funzionali preposte a cose diverse e non utilizzabili in contemporanea.


lw $1,100($0)

lw $2,104($0)

add $3,$2,$1

sw $3,200($0)

ISTRUZ. FE. DEC. EXE. MEM. W.B.

Load 20 ps 5 ps 10 ps 20 ps 5 ps

Store 20 ps 5 ps 10 ps 20 ps --

Salto 20 ps 5 ps 10 ps -- --

Aritmetico -

Logica 20 ps 5 ps 10 ps -- 5 ps

PIPELINING - ESEMPIO

Latenza Effettiva: (2*60+40+55) ps = 215 ps


PIPELINING - PRESTAZIONI • La durata del colpo di clock in una microarchitettura

pipelined corrisponde più o meno alla latenza della fase più lunga, che determina il percorso critico del sistema.

• Il codice assembly visto in precedenza viene completato in 8 cicli, il che vuol dire che il tempo di esecuzione è 8*20ps=160ps; contro una latenza totale, calcolata snza tenere in considerazione l’overlapping ma solo la natura delle istruzioni, di 215ps.

• La latenza della singola istruzione è comunque paria 5.

• Incremento delle performance attraverso il pipelining delle istruzioni: – modifiche architetturali;

– trasparente al programmatore.


PIPELINING - LIMITAZIONI

• L’incremento potenziale delle prestazioni della microarchitettura corrisponde teoricamente al numero di stadi di pipelining introdotti

– La latenza reale ottenuta non è pari a 215ps/5=43 ps.

• Overhead:

– Riempire e svuotare la pipe (nell’esempio la pipeline è a regime solo per 2 colpi di clock su 8)

– Stadi di pipeline non sono identici

– Hazard ed eccezioni: interdicono l’esecuzione della prossima istruzione nello slot assegnatogli. La pipeline viene stallata, per un numero di colpi di clock tale da risolvere la condizione critica.

agesNumberOfSt

nPipelinedtructionNoTimePerIns

SpeedUp

PipeDepthstructionsyclesPerInPipeStallC

SpeedUp

1

1


LINK E MATERIALE UTILE • Vedi Simple Pipelining in

http://euler.mat.uson.mx/~havillam/ca/CS323/index.html


PREMESSA

• Nelle architetture scalari e pipelined date diverse classi di istruzioni (e.g. accesso alla memoria, operazioni aritmetico/logiche in virgola fissa, …) è possibile distinguere diversi flussi di operazioni a latenza intrinseca diversa.

• Da qui l’evoluzione verso CPU in cui a ogni flusso corrisponde una diversa pipeline, a valle della lettura e decodifica delle istruzioni.

• Come nelle architetture pipelined aumento il throughput di picco, permangono le limitazioni dovute a dipendenze non risolte o salti non previsti correttamente.


REQUISITI

• Poter effettuare la lettura di più istruzioni simultaneamente, eventualmente sfruttando anche tecniche di branch prediction.

• Poter decodificare più istruzioni simultaneamente, effettuando un controllo che non esistano dipendenze fra le istruzioni lette e fra loro e quelle in esecuzione.

• Disporre di – metodi che consentano di lanciare (issuing) più istruzioni in

parallelo – più unità funzionali in parallelo – gerarchie di memoria capaci di rispondere contemporaneamente

a più riferimenti

• Disporre di un eventuale logica di riordino delle istruzioni (in-order commitment) per preservare la semantica originale del codice.


CARATTERISTICHE • L’identificazione del potenziale parallelismo e la conseguente

gestione dell’esecuzione delle istruzioni in parallelo non viene compiuta a tempo di compilazione (come nei processori VLIW) ma a tempo di esecuzione dall’unità di controllo.

• L’implementazione dell’ILP in queste architetture è completamente trasparente al programmatore.

• Nonostante la gestione dinamica del parallelismo il compilatore ha il compito di ristrutturare il codice (riordino delle istruzioni e register renaming) per sfruttare al meglio il parallelismo intrinseco del programma attraverso le unità funzionali parallele.

• E’ necessario disporre di una banda di memoria adeguata per istruzioni e dati per poter consentire l’esecuzione del programma alla velocità richiesta.


CRITICITA’ • Problema: di identificare (e ritrovare) uno stato preciso del

processore. – salvo lo stato della macchina in particolari punti di controllo

(checkpoints) in un history buffer, aggiornato durante l’esecuzione. Quando un’istruzione viene finalizzata si cancella la “storia” che non è più necessaria.

– separo lo stato fisico da quello logico; lo stato fisico si aggiorna non appena l’operazione viene completata, quello logico viene aggiornato solo in ordine sequenziale, post verifica speculazioni. Utilizzo un re-order buffer: per finalizzare un’istruzione, il suo risultato viene tolto dal re-order buffer e portato nel registro destinazione.

• Più le pipeline dedicate sono profonde e sbilanciate (in termini di latenza) più critico è il compito del compilatore e maggiori sono le esigenze di memorizzazione pre-committment.

• Come nelle architetture pipelined aumento il throughput di picco, ma sono soggetto a forti limiti dovuti a dipendenze non risolte o un salto non previsto correttamente.


LIMITAZIONI • Hazards sui dati

– le istruzioni della finestra di esecuzione sono analizzate per scoprire le dipendenze sui dati prima di iniziare la loro esecuzione

– ristrutturazione del codice da parte del compilatore

• Hazards di controllo – Tecniche speculative: predizione sul risultato del salto, si legge in

modo speculativo l’istruzione che si prevede sarà eseguita dopo e di conseguenza un nuovo blocco di istruzioni entra a fare parte della finestra di esecuzione.

• Predizione corretta – tolgo l’etichetta di “speculazione” alle istruzioni lette e aggiorno lo stato della macchina

• Predizione sbagliata – devo “tornare indietro” garantendo che lo stato non sia modificato erroneamente.

• Hazard strutturali – Impongono vincoli architetturali

– Duplicazione risorse


RIASSUMENDO…

REQUISITI

1. ILP della applicazione Posso eseguire in parallelo più operazioni, se e

solo se queste ci sono e sono disgiunte

1. Ottimizzazioni a livello di compilazione

La gestione del parallelismo è dinamica, quindi non ne è responsabile il

compilatore, ma il compilatore deve mettermi a disposizione quanto più

parallelismo possibile

1. Supporto Hardware Devo poter leggere, decodificare ed eseguire

più istruzioni in parallelo

LIMITAZIONI

1. Hazard sui dati e.g. ADD r1, r2 (r1 := r1+r2);

MOVE r3,r1 (r3 := r1) La lettura e la decodifica della seconda

istruzione può avvenire in parallelo alla prima ma non la sua esecuzione

1. Hazard sul controllo Gestione delle speculazioni

1. Hazard strutturali La banda di lettura/scrittura dei dati deve

essere adeguata


APPROCCIO GENERALE – IL FLUSSO

• Il codice oggetto è statico, la sequenza di istruzioni eseguite invece rappresenta il flusso dinamico. Le istruzioni sono prelevate in ordine dalla memoria e l’esecuzione parallela è responsabilità del controllo.

• CPI inferiore all’unità – idealmente, se n è il numero di istruzioni che possono essere simultaneamente lette, decodificate ed eseguite, si raggiunge CPI =1/n;

• La banda della cache (= numero di istruzioni trasferite da cache a CPU in una sola operazione di lettura) deve essere n.


APPROCCIO GENERALE - GESTIONE • Il fetch può o meno includere la predizione dei salti.

• L’unità di controllo/decodifica crea uno schedule di esecuzione parallela che garantisce il soddisfacimento dei vincoli di dipendenza e disponibilità di risorse hardware. – risoluzione dipendenze artificiali tramite renaming

– riordinamento

• Nella finestra l’ordine non è più sequenziale, ma legato alle dipendenze vere e alle risorse hardware disponibili.

• Le istruzioni possono terminare in ordine diverso dal programma, causa parallelismo e/o diversa latenza delle varie unità funzionali – non posso aggiornare subito il register file e la memoria al termine di

una istruzione

– mantengo in memoria temporanea i risultati (accessibile da eventuali istruzioni dipendenti) fino alla fase di committing o flushing/retiring dell’istruzione.


FLUSSO DI ESECUZIONE

CARATTERISTICHE

1. Due uniche pipeline 2. Nessun supporto hardware

per la predizione dei salti 3. Nessuna duplicazione di

unità funzionali 4. Assenza di instruction

buffer


SCHEMA A BLOCCHI DELL’ARCHITETTURA

load/store => 5 stadi

aritmetico/logiche in virgola

fissa => 3 stadi

aritmetiche in virgola

mobile => 8 stadi

FINESTRA DI ESECUZIONE (ISSUE WINDOW)

Vengono aggiunti da 4 a 7 bit a ogni istruzione RISC (e.g. la classe di istruzione, le risorse richieste, il pre-calcolo dell’indirizzo obiettivo del salto)


FUNZIONAMENTO - LETTURA • Pre-decodifica: parte della decodifica viene spostata nella

fase di caricamento dalla RAM (o dalla cache di secondo livello) alla I-cache. Si distinguono alcune istruzioni (o classi di istruzioni) per adottare tecniche di speculazione intelligente per i salti.

• Cache istruzioni: memoria piccola e veloce che contiene le istruzioni più recenti. Ad ogni ciclo un numero di istruzioni pari, nel caso migliore, a quelle eseguibili in parallelo vengono lette contemporaneamente.

• Hardware dedicato per il branch prediction: predizione dell’esito dei salti condizionali ed effettuare letture oltre l’istruzione di salto.

• Buffer istruzioni: rappresenta una riserva di istruzioni, la CPU può continuare il proprio lavoro anche quando la lettura delle istruzioni è bloccata (ad esempio, per un trasferimento da cache) o limitata.


FUNZIONAMENTO - DECODIFICA • Identificazione delle “vere” dipendenze (RAW) e risoluzione

delle “false” dipendenze (WAW e WAR). • Issue window: contiene le istruzioni lette e decodificate, ma

non ancora lanciate in esecuzione. Si occupa del dispatching verso le unità funzionali opportune.

• Reservation station (ove presenti): buffer per conservare operandi e operazione fino a che l’unità funzionale non è pronta per l’esecuzione. Disaccoppiamento della fase di issue e dal controllo delle vere dipendenze. – In assenza di reservation station ad ogni ciclo, le istruzioni nella

issue window vengono controllate rispetto alle interdipendenze con quelle nella finestra di esecuzione e quelle nella issue window stessa.

– Se sono presenti le reservation station le istruzioni decodificate vengono inviate alle direttamente alle reservation station che faranno i controlli.


FUNZIONAMENTO - DECODIFICA

• L’unità di smistamento invia ogni istruzione e i suoi operandi alla reservation station opportuna e inserisce un riferimento a tale istruzione nel re-order buffer interno alla “re-order and commit unit”.

– Il dispatching non viene effettuato se non c’è spazio nella reservation station e/o nel re-order buffer.

• Lo spazio per mantenere i risultati si esaurisce rapidamente:

– i processori hanno registri interni replicati (rename buffers) per memorizzare i risultati in attesa che l’unità di consegna dia il permesso per scrivere i registri effettivi.


FUNZIONAMENTO – ESECUZIONE E COMMITTMENT • Quando una unità funzionale è pronta a ricevere una nuova

istruzione la reservation station associata viene controllata al fine di trovare una istruzione eligibile. – Se ce ne è più di una disponibile si ricorre a politiche di

dispatching.

• Out of order execution: L’esecuzione non avviene nell’ordine originale ma in base alla disponibilità dei dati.

• I risultati delle istruzioni vengono scritti nella commit unit, in modo tale che le istruzioni vengano logicamente riordinate. – Necessità di una memoria temporanea per i risultati

dell’istruzione corrente (accessibile da eventuali istruzioni dipendenti) fino alla fase di commitment.

• Lo stato della CPU viene aggiornato (committment phase) in base all’ordine corretto delle istruzioni. Dall’esterno l’esecuzione appare in ordine.


SUPERSCALARI SUL MERCATO • Oggi, praticamente ogni processore è un superscalare. Ciò che è

altamente variabile è la dimensione della issue window.

• Il numero e il tipo di unità funzionali dipende dal mercato di riferimento. Alcuni processori dispongono di più unità floating point (e.g. i POWER di IBM), altri fondamentalmente lavorano prevalentemente con interi (e.g. Pentium Pro/II/III/M ). Altri ancora dedicano gran parte delle loro risorse alla gestione SIMD del parallelismo (e.g. PowerPC G4e).


LINK E MATERIALE UTILE • Vedi Superscalar Processors e Reorder Buffers & Register

Renaming in http://euler.mat.uson.mx/~havillam/ca/CS323/index.html

MASTER IN SISTEMI EMBEDDED PER L’INTERNET · 2016. 1. 22. · MASTER IN SISTEMI EMBEDDED PER...

Documents

Transcript of MASTER IN SISTEMI EMBEDDED PER L’INTERNET · 2016. 1. 22. · MASTER IN SISTEMI EMBEDDED PER...