Scalabilità Energetica di Algoritmi Paralleli su

Architetture Multicore

Gennaro Cordasco

Outline

• Motivazioni

• Scalabilità Computazionale vs Scalabilità Energetica

• Modelli Computazionali e Assunzioni

• Una metodologia per massimizzare l’efficienza energetica su architetture parallele

• Esempio: Shared Memory

• Altri esempi

Motivazioni

• Ridurre il consumo di energia nei Computer…• Problema abbastanza semplice da risolvere su

architetture single-core• Energia consumata cresce in maniera non lineare (cubica)

rispetto alla frequenza della CPU.• E = TX X3

• Piattaforme emergenti: Architetture multi-core– Il problema si fa complesso

• Dipendenza fra i task• Energia per la comunicazione • Quanti core?• Quale frequenza utilizzare per ogni core?

Algoritmo Parallelo

• Cosa significa progettare un algoritmo parallelo?

– Definire in che modo il lavoro è suddiviso ed assegnato ai client/core

– Definire in che modo i client interagiscono/si scambiano informazioni

Dipendenza fra i task

• In ogni computazione parallela, il job da eseguire viene suddiviso in tasks

• I tasks possono essere dipendenti l’uno dall’altro

• Il grafo delle dipendenze è un grafo diretto aciclico (DAG) che descrive tali dipendenze

Grado di Parallelismo e Critical path

Dato un DAG

• I task senza dipendenze (figli) sono detti source, quelli senza genitori sono detti target

• Il critical path è la più lunga path fra un nodo source e uno target

Energia richiesta per la comunicazione

• Al fine di realizzare un job, è necessario far comunicare i task:

– I costi di comunicazione di un algoritmo parallelo in generale non sono costanti ed in particolare dipendono da:• Dimensione dell’input N

• Numero di core utilizzati P

Quanti Core?

• Considerando E = TX X3, più core utilizziamo e meglio sfruttiamo l’energia:

– Possiamo ad esempio raddoppiare il numero di core e dimezzare la frequenza per ottenere lo stesso risultato nello stesso tempo e con minore energia

– Detto in un altro modo due core con una frequenza ridotta all’80% consumano la stessa energia di un solo core alla frequenza massima, ma producono una potenza computazionale maggiore di circa il 60%

• E la comunicazione/interazione?

Scalabilità Computazionale vs Scalabilità Energetica

• Scalabilità Computazionale:– Relazione fra le prestazioni e il numero di core

usati.

• Scalabilità Energetica:– Relazione fra Energia dissipata e numero di core

usati.

• Perché sono diverse:– E possibile mascherare i tempi di comunicazione …

ma non l’energia richiesta per la comunicazione.

La prestazione è l’inverso del tempo richiesto per eseguire un determinato algoritmo su un determinato input

Scalability Metrics

• Energy Scalability:– Fissate l’istanza di un problema ed il tempo massimo

di esecuzione, qual è il numero di core ottimale per minimizzare l’energia dissipata?

• Performance Scalability:– Fissate l’istanza di un problema e l’energia disponibile,

qual è il numero di core ottimale per massimizzare le prestazioni?

• Energy Efficient Scalability:– Fissata l’istanza di un problema, qual è il numero di

core ottimale per massimizzare il rapporto prestazioni/energia?

Modelli di computazione

• Message passing

• PEM (Parallel External Memory)• P cores

• 2 livelli di memoria

Assunzioni

• Tutti i core operano alla stessa frequenza

• E’ possibile scalare la frequenza su qualsiasi valore. L’accesso alla cache dipende dalla frequenza dei core

• L’accesso alla memoria centrale richiede tempo costante (è indipendente dalla frequenza)

Notazione

• X, frequenza di un core• Tbusy = (numero di cicli) 1/X, tempo speso da un

core per l’esecuzione di una computazione• Tactive, tempo di attività di un core• Em, energia richiesta per l’accesso alla memoria• F, frequenza massima di un core• Mc, numero di cicli eseguiti durante l’accesso alla

memoria (alla frequenza massima)• N, dimensione input• P, numero di cores• A, istanza di un algoritmo parallelo

Energy Model

• P = CL V2 f + IL V

• Edynamic = Ed Tbusy X3

• Eleakage = El Tactive X

Metodo (Energy Scalability)

• Step 1: Analizzare il grafo delle dipendenze al fine di individuare la critical path A

• Step 2: Decomporre A in tempo computazione, tempo di accesso alla memoria e tempo di sincronizzazione

• Step 3: Ridurre la frequenza dei core in modo che il tempo richiesto da A coincida con il tempo massimo di esecuzione.

Metodo (Energy Scalability)

• Step 4: Calcolare il numero di cicli richiesti per eseguire A

• Step 5: Calcolare il numero di accessi alla memoria richiesti da A

• Step 6: Calcolare Tactive per ogni core (dipende

dalla frequenza calcolata allo step 3)

Metodo (Energy Scalability)

• Step 7: Calcolare l’energia dissipata in funzione dei dati calcolati agli step precedenti– Ecomp= Ed (numero di cicli) X2

– Emem = Em (numero di accessi alla memoria)

– Emes = Et (numero di messaggi scambiati)

– Eleak = El Tactive X

E= Ecomp+ Emem+ Emes+ Eleak

Metodo (Energy Scalability)

• Step 8: Risolvere l’equazione E= Ecomp+ Emem+ Emes+ Eleak

al fine di identificare il numero di core ottimale per minimizzare i consumi di energia

Esempio 1: sommare Nnumeri in parallelo

• Architettura PEM– Assumiamo N multiplo di P e P potenza di 2

Procedura:1. Ogni core ricopia N/P numeri (a blocchi di B) nella

propria cache 2. Ogni core computa la somma dei propri numeri3. La metà dei core in esecuzione scrive nella memoria il

risultato ottenuto e passa nello stato idle4. L’altra metà legge dalla memoria un valore e lo somma

al proprio5. Se il numero di core attivi è maggiore di 1 vai al passo 36. L’ultimo core scrive il risultato nella memoria e passa

nello stato idle

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 1: Critical Path ----

– Step 2: Analisi Critical Path

• Letture di memoria

N/(B P) + log P

• Sincronizzazioni

log P

• Step di computazione(N/P) – 1 + log P

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 3: Nuova Frequenza

…

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 4: Numero totale di cicli

(((N/ P) – 1) P + (P – 1))

= (N – 1)

è il numero di cicli per una

somma

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 5: Numero totale di accessi alla memoria

(N / B) + 2 (P – 1)

Esempio: sommane Nnumeri in parallelo

• Architettura PEM– Step 6: Calcolare Tactive

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 7:

Ecomp= Ed (N – 1) X2

Emem = Em ((N/B)+2(P – 1))

Emes = 0

Eleak = El Tactive X

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 8:

Fissiamo β=3, k=1000 e Mc=1000

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 8:

Esempio: sommane Nnumeri in parallelo

• Architettura PEM

– Step 8:

Esempio2: Message Passing

• N numeri – 4 nodi

N/4 additions

1 2 3 4

Communication period

1 2 3 4

Esempio2: Message Passing

• Architettura MEM

– Step 1: Critical Path ----

– Step 2: Analisi Critical Path

• messaggi

log P

• Step di computazione

(N/P) – 1 + log P

1 2 3 4

Esempio2: Message Passing

• Architettura MEMStep 3: Nuova Frequenza

cKPFT

PP

N

FX

log

log

'1

1 2 3 4

Esempio2: Message Passing

• Architettura MEMStep 4: Numero di messaggi

(M-1)

Step 5: Ecomm = Em (P - 1)

Ecomp = Ec (N - 1) X’2

Eidle = Eidle Tidle

Esempio2: Message Passing

Esempio2: Message Passing

k è il rapporto fra l’energia spesa per la comunicazione e quella per la computazione

Case Study: Naïve Quicksort

Ener

gy

No: of Cores

No Tradeoff: Single Core is good enough

Parallel Quicksort

• Data to be sorted is distributed across the cores (assume parallel I/O).

• A single pivot is broadcast to all cores.

• Each core partitions its own data

• Data is moved so that the lessers are at cores in one region, and greaters are in another.

• Recursively quicksort each region.

Parallel Quicksort Algorithm

LU Factorization

• Given an N x N matrix A, find a unit lower triangular matrix L and an upper triangular matrix U, such that A = L U

• Use the coarse-grain 1-D column parallel algorithm

Case Study : LU Factorization

Conclusioni

• Il problema c’è…

• Il problema è interessante…

• La soluzione? La metodologia attuale merita senza dubbio ulteriori sviluppi.

BINGO

Riferimenti

• "Towards Optimizing Energy Costs of Algorithms for Shared MemoryArchitectures"Vijay Anand Korthikanti and Gul Agha.To appear in ACM Symposium on Parallelism in Algorithms andArchitectures (SPAA), Santorini, Greece, 2010.

• "Energy-Performance Trade-off Analysis of Parallel Algorithms"Vijay Anand Korthikanti and Gul Agha.To appear in USENIX Workshop on Hot Topics in Parallelism (HotPar),Berkeley, California, USA, 2010.

• "Analysis of Parallel Algorithms for Energy Conservation inScalable Multi-core Architectures"Vijay Anand Korthikanti and Gul Agha.International Conference on Parallel Processing (ICPP), Vienna, Austria, 2009.