Acceleratori hardware del calcolo ad alte prestazioni

Collana di seminari per la valorizzazione dei Risultati della Ricerca del CRS4

Acceleratori hardware del calcolo ad alte prestazioni

Comparazione della performance

di un algoritmo di ottimizzazione matematica

su piattaforme FPGA, GPGPU e x86_64

[email protected]


Perché hpc e architetture complesse?

Il calcolo deve rispondere ad esigenze sempre più ardue …

Un esempio:

• Un tipico dato di input della sismica a riflessione

Premessa

1km

3 km

Top salt surface, color map is related to the depth

1km

3 km


1km

3 km

1km1km

3 km3 km


2D

100 MB

Anni ’90

3D

Quasi un TB6 ordini di grandezza in più!

Oggi


Perché hpc e architetture complesse?

Un altro esempio:

Premessa


Di cosa NON parleremo

• Quale architettura è meglio delle altre in termini di possibili prestazioni medie o di picco a seconda del campo di applicazione oppure in termini di consumo a parità di velocità di calcolo per operazioni più o meno complesse

• Di calcolo numerico e metodi più rapidi per trovare i minimi o i massimi di una funzione pluridimensionale, non lineare, non regolare ecc.

• Di linguaggi di programmazione che siano per la programmazione strutturata o orientata agli oggetti oppure linguaggi specifici quali Cuda o OpenCL, VHDL o Verilog

Premessa


I due concetti che vorremmo sottolineare …

Premessa

Rispettare la legge di Moore è sempre più difficile• «Le prestazioni dei processori, e il numero di transistor ad esso relativo,

raddoppiano ogni 18 mesi».

• Ma il raggiungimento dei limiti fisici per la riduzione delle dimensioni dei transistor è ormai raggiunto

Le esigenze di calcolo crescono• la soluzione non può essere più computer o computer più grandi

• Si richiede troppo in termini di consumi e infrastrutture

La soluzione è tornare al semplice



Premessa

La soluzione è tornare al semplice



Premessa



Computation

Computation

MaxelerOs

Premessa



Premessa

• Spostare la gestione del dato dall’hardware al software

• Ad esempio:• avvicinare il dato all’unità di calcolo

• decidere la sequenza delle operazioni

• L’infrastruttura è a carico del programmatore

• FPGA o le GPGPU sono coprocessori

• Necessitano di essere inseriti in una macchina completa

• Non possono sostituire le CPU

• Elevate prestazioni di picco con minori consumi e costi

La soluzione è farsi aiutare da

hardware semplice ma efficiente

La soluzione è



Non c’è un’infrastruttura per l’HPC migliore delle altre, ma ènecessaria una valutazione globale del problema:

• Costi dell’hardware, Consumi e spese di mantenimento

• Possibilità di portare il problema nell’architettura specifica

• Complessità del problema da affrontare e costi di sviluppo

• Quantità di dati da elaborare

• Precisione necessaria per risolvere il problema

• Velocità d’elaborazione

• Mantenimento dell’applicazione nel tempo

• Frequenza dei possibili crash del sistema nel suo complesso

Valutare il problema globalmente, hardware compreso

Premessa



Premessatre

• Cercare di avere una visione globale dei problemi

• Non si può essere specializzati in tutto (ma in qualcosa si!)

• Sapere chi può affrontare e risolvere argomenti specifici

• Lavoro d’equipe (che non vuol dire nessuna responsabilità …)

• Facilità nell’inserire nuove persone, conoscenze

• Cercare le collaborazioni necessarie

• sapere cosa cercare e cosa offrire


Imaging and Numerical Geophysics

• Gruppo di ricerca di 8 persone con differente back-ground • 4 fisici: Ernesto Bonomi, Antonio Cristini, Guido Satta e Zeno Heilmann (geofisico)

• 4 ingegneri: Claudio Gallo, Giuliana Siddi, Daniela Theis, Gianluigi Caddeo

• 1 informatico: Omar Shiaratura

• Lavora nel campo della sismica a riflessione in collaborazione con l’industria petrolifera da circa 17 anni

• Capacità di autofinanziamento di più del 120%

• Inserito nel settore: Energy and Environment diretto daErnesto Bonomi con diversi interscambi interni

• Diverse le collaborazioni ancora attive con:• Importanti società di hardware e software

– Nvidia – AMD – Maxeler – …

• I più importanti dipartimenti universitari di geofisica

– Karlsruhe – Imperial College London – Università di Pisa

Chi siamo


Sommario


Contesto: cos’è la sismica a riflessione

Common Reflection Surface Stack o CRS-stack

CRS: metodo Data-Driven

Parallelizzazione

L’applicazione CRS in tre diverse architetture

Una slide sui progetti futuri


Cosa è un giacimento di gas e petrolio

• Non è un lago di petrolio e gas.

• È una formazione porosa (rocce) che li racchiude;

• Una depressione della crosta terrestre che sprofondandoha accumulato sedimenti e materiale organico

• La varietà è pressoché infinita:

• Strati piatti di roccia;

• Strati curvi verso il basso;

• Strati fratturati, dislocati e inclinati.

Sismica a riflessione


Alla ricerca del giacimento

• Finché non è trivellato un pozzo, è difficile confermare la presenza di risorse utilizzabili …

• Il costo di una trivellazione è stimato a:• 0,5-8 M$ per depositi “onshore”;

• 10-30 M$ per depositi in acque poco profonde;

• Oltre 100 M$ per depositi in acque profonde;

• Necessità di metodi per la previsione della presenza di giacimenti

• Tre fasi:• Studio della superficie terrestre per costruire un primo modello di sottosuolo

• Sondaggio del sottosuolo, principalmente con metodi acustici

• Misure da pozzo



Che cosa è la sismica a riflessione …

• Il principale strumento di prospezione dell’industria petrolifera;

• È utile anche in campo civile, ambientale e della ricerca geologica di base;

• Usa molti concetti matematici sia originali sia mutuati da altre branche della matematica applicata;

• L’elaborazione sismica richiede ingenti risorse di calcolo e di archiviazione dati;

• È un’attività che vale oltre 4 miliardi di dollari all’anno.



La sismica o ecografia del sottosuolo

È il metodo di esplorazione che utilizza i principi della sismologia per stimare le proprietà del sottosuolo a partire da onde sonore indotte, in seguito riflesse.

Registrando il tempo di volo dell’eco e la sua intensità, èpossibile stimare la profondità della superficie riflettente;



I dati sismici

• Una traccia sismica è la registrazione degli echi retro-propagati dalle discontinuitàdel sottosuolo

• Le esplorazioni sismiche producono enormi quantità di dati:• Ciascuna esplorazione prevede 103 / 105 shots

• Ogni shot comporta circa 100-200 ricevitori

• Ciascun ricevitore registra circa 1500 campioni

Si sfiora facilmente un TB di dato a singola precisioneSi sfiora facilmente un TB di dato a singola precisione



Processing dei dati sismici

• Correzione dell’ampiezza

• Operazioni di Filtraggio

• Deconvoluzione

• Analisi di velocità

• Stacking

• Migrazione



-5000

-4500

-4000

-3500

-3000

-2500

-2000

-1500

-1000

-500

0

0 2000 4000 6000 8000 10000 12000

V0=1400 m/s

V1=2000 m/s

V2=3400 m/s

( )hHKHhmHKHmmw TzyNIPzy

TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp

S GS=GS=Gm

Common Reflection Surface Stack


-5000

-4500

-4000

-3500

-3000

-2500

-2000

-1500

-1000

-500

0

0 2000 4000 6000 8000 10000 12000

V0=1400 m/s

V1=2000 m/s

V2=3400 m/s


TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp

S GS=GS=Gm


• È un esperimento virtuale nel qualesorgente e ricevitore coincidono (tracce zero-offset)

• È una raccolta del segnale riflesso nello stesso punto(o in un intorno molto vicino) del segnale zero-offset

• Come realizzarla?• Ipotizzando un modello di volo del segnale nel terreno

• Raccogliendo il segnale al tempo ipotizzato


La formula del TravelTime


TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp


0xSG

mSG

h −+=−=2

;2

Bortfeld R., (1989). Geometrical ray theory: Ray and traveltimes in seismic systems (second-orderapproximations of the traveltimes): Geophysics, 54, no.3, 342–349.

Cervený V. (2001). Seismic ray theory. Cambridge University Press.

Höcht, de Bazelaire E., Majer P., Hubral P. (1999). Seismicsand optics: hyperbolae and curvatures: J. of AppliedGeophysics no. 42, 261–281.

Höcht G., (2002). Traveltime approximations for 2D and 3D media and kinematic wavefield attributes, doctors’thesis. Universität Karlsruhe.



• 2 parameters ( emergence angle & azimuth )

• 3 Normal Wavefront parameters ( RNx; RNy ; αN )

• 3 NIP Wavefront parameters ( RNIPx; RNIPy ; αNIP )

8 parametri attraverso I quali possiamo ricuperare i segnali della traccia e ricostruire quello della traccia ZO


TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp




Quali parametri utilizzare per identificare i tempi di volo?

Possiamo chiederlo ai dati …

Come?

8 parametri attraverso I quali possiamo ricuperare i segnali della traccia e ricostruire quello della traccia ZO


TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp



Semblance

• Costituisce la funzione costo per una procedura di ottimizzazione sugli 8 parametri



TTzyNzy

TT ++

+=

0

0

2

00

2 22

v

t

vtthyp

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

0 ≤ S ≤ 1


Perché considerare tanti problemi distinti?

Potremo ad esempio riformulare il problema• considerando il legame dei punti spazialmente vicini

• Risolvendo un sistema algebrico …

Ma

Parcellizzando riusciamo ad definire due livelli di parallelizzazione1. Lungo gli assi spaziali

2. Lungo l’asse temporale

Formulare il problema considerando l’hardware sottostante

Piccola digressione …



In un applicazione seriale

• Un ciclo esterno sulle tracce di output


I N P U T visto dall’alto O U T P U T

tx

y

Forte sovrapposizione del dato di input


In un applicazione seriale


Ciclo sulle tracce

Ciclo sui campioni

• Un ciclo esterno sulle tracce di output

• Per ogni traccia un ciclo sui campioni temporali

• Per ogni campione (t0): ottimizzazione sugli attributi

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

ottimizzazione


L’applicazione parallela

• Tante istanze dello stesso codice seriale che elaborano tracce differenti sono un’applicazione parallela

• Il calcolo procede in modo asincrono sul ciclo delle tracce

Parallelizzazione

Ciclo sui campioni

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i=1

M

∑k = − N

2

N2

∑

2

ottimizzazione

Ciclo sui campioni

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

ottimizzazione

Ciclo sui campioni

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i=1

M

∑k = − N

2

N2

∑

2

ottimizzazione


Secondo livello di parallelizzazione

Parallelizzazione

Ciclo sui campioni

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i=1

M

∑k = − N

2

N2

∑

2

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i=1

M

∑k = − N

2

N2

∑

2

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2

ottimizzazione

S (r x 0 , t 0 ) = 1

M

a i, t i + k

i=1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i=1

M

∑k = − N

2

N2

∑

2

ottimizzazione

• Eliminando il ciclo sui campioni (t0)• Creando una routine che calcoli contemporaneamente molte funzioni costo

• La Multi-Semblance costituisce il nuovo kernel del calcolo• L’ottimizzazione procede in modo sincrono sui t0

• È più facile renderla più efficiente rispetto a tante Semblance distinte

• È più facile realizzare un paradigma SIMD (Single Instruction, Multiple Data) a basso livello

• La logica dell’ottimizzazione sui parametri non viene toccata


Multi-Semblance

• L’applicazione costituisce un’infrastruttura attorno al nucleo

TravelTime e Multi-Semblance• Chiamato molteplici volte dall’ottimizzazione

• 95% del tempo di calcolo è usato dalle due routine

• Scrittura modulare: facile sostituzione con altre implementazioni

• Versioni attuali sono:(SpeedUp rispetto a un singolo core Intel Westmere a 2.66 GHz)

Parallelizzazione

SpeedUpCollaborazioneLinguaggiPiattaforma

100 x

60 x

110 x

2 x

Nvidia e committenteCudaNvidia Tesla/Fermi

OpenCL

Java (Maxeler compiler) e C++

Fortran e C

AMD e committenteAMD FireStream

MaxelerMaxeler FPGA

(Maxeler)Core Intel


Multi-Semblance

• L’applicazione costituisce un’infrastruttura attorno al nucleo

TravelTime e Multi-Semblance• Chiamate molteplici volte dall’ottimizzazione

• 95% del tempo di calcolo è usato dalle due routine

• Scrittura modulare: facile sostituzione con altre implementazioni

(

Parallelizzazione

Cosa rende speciale calcolare tante

Semblance assieme rispetto a una per volta?


Utilizzo dei dati nella Multi-Semblance

Utilizzo dei dati con 1 campione Utilizzo dei dati con 4 campioni

Utilizzo dei dati con 16 campioni Utilizzo dei dati con 64 campioni

Parallelizzazione


Sfruttamento della cache della CPU

• Non calcola una Semblance alla volta

• Calcola assieme i termini parziali relativi alla singola traccia

CPU e Multi-Semblance

∑ +

+

−

+==

+==

+==−−−

2

,

)()()1(

,

)()()1(

2,

)()()1(

)(

)(

)(

222

...

......

...

......

...

kti

nsembnsemb

kti

nsembnsemb

Nti

nsembnsemb

nsembi

nsembikkk

nsembi

NNN

adenomdenomdenom

anumnumnum

anumnumnum

i = 1

S (r x 0 , t 0 ) = 1

M

a i,t i + k

i= 1

M

∑k = − N

2

N2

∑

a i, t i + k

2

i= 1

M

∑k = − N

2

N2

∑

2


Sfruttamento della cache della CPU

• Non calcola una Semblance alla volta

• Calcola assieme i termini parziali relativi alla singola traccia

• Una traccia occupa circa 12 KB e può risiedere per intero dentro la cache di primo livello delle moderne CPU

• Ciò permette di aumentare il rapporto tra “Cache hit e Cache miss ”fino a 100 volte

• Il meccanismo di caricamento del dato in cache è automatico

• Riduzione del tempo globale del calcolo del 50%:• Da 3 a 1,5 mesi il tempo di elaborazione di un dataset con 1.000 core

CPU e Multi-Semblance


Meccanismo di calcolo nel FPGA

• Algoritmo del calcolo uguale a quello visto per la CPU

• Non c’è un meccanismo di cache nel FPGA

• C’è un flusso continuo delle tracce nel FPGA

• calcola e conserva in memoria quanto serve

• Per ogni FPGA si hanno fino a:

• 6 pipe ovvero 6 flussi continui del dato a 180 MHz

• Le pipe lavorano in modo SIMD

• Tuning specifico per il codice

• Utilizzo della rappresentazione in virgola fissa

• Si ha una maggior precisione solo dove richiesto

Field Programmable Gate Array e Multi-Semblance


Meccanismo di calcolo nel FPGA


DR

AM

of P

CI c

ard PCIe

Parametri

Coord. delle tracce

TraveTimeTraveTime KernelKernel

MultiMulti--SemblanceSemblance KernelKernel

tt

FPGA

Ris

Ris . p

arzia

li. p

arzia

li

Riduzione del tempo globale e delle risorse necessarie

Da 3 mesi a 6 giorni, da 1.000 core in 167 nodi a 128 FPGA su 32 nodi

RiduzioneRiduzione deldel tempo globale tempo globale e dellee delle risorse necessarierisorse necessarie

Da 3 mesi a Da 3 mesi a 6 giorni6 giorni, da 1.000 core in 167 nodi, da 1.000 core in 167 nodi aa 128 FPGA su 32 nodi128 FPGA su 32 nodi


Un risultato con FPGA


CPU Coherency MAX2 Coherency


Meccanismo di calcolo nella GPGPU

• Algoritmo di calcolo “naturale”

• Ogni Semblance è assegnata a un Thread

• Il calcolo della funzione costo procede in modo asincrono

• L’hardware gestisce la schedulazione dei thread ai core “liberi”

• Si realizza un modello SIMD sui parametri del TravelTime

• (L’ottimizzazione procede in modo sincrono)

• Il calcolo viene velocizzato dai numerosi core

• fino a 512 sulle schede Nvidia Fermi

• Importanti differenze tra le due implementazioni in test:

GPGPU e Multi-Semblance

100 x

60 x

Nvidia e committenteCudaNvidia Tesla/Fermi

OpenCL AMD e committenteAMD FireStream


Confronto tra versione AMD e Nvidia

Versione AMD:

• Scritta in OpenCL• C’è un tempo di latenza iniziale dovuto alla compilazione del kernel

• Il TravelTime è calcolato “al volo” all’interno della Semblance• Coprire la lettura del dato con il tempo di calcolo

Versione Nvidia:

• Scritta in Cuda• Linguaggio, fino ad oggi, un po’ più maturo per HPC

• TravelTime vengono calcolati preventivamente

• Uso della memoria Texture per le interpolazioni• Interpolazioni hardware molto veloci, ma meno precise

• Dobbiamo ancora verificare se la precisione è sufficiente



Confronto tra versione AMD e Nvidia

Versione AMD:

• Scritta in OpenCL• C’è un tempo di latenza iniziale dovuto alla compilazione del kernel

• Il TravelTime è calcolato “al volo” all’interno della Semblance• Coprire la lettura del dato con il tempo di calcolo

Versione Nvidia:

• Scritta in Cuda• Linguaggio, fino ad oggi, un po’ più maturo per HPC

• TravelTime vengono calcolati preventivamente

• Uso della memoria Texture per le interpolazioni• Interpolazioni hardware molto veloci, ma meno precise

• Dobbiamo ancora verificare se la precisione è sufficiente



Da 3 mesi a 47 giorni, da 1.000 core in 167 nodi a 32 schede FireStream


Da 3 mesi a Da 3 mesi a 47 giorni47 giorni, da 1.000 core in 167 nodi, da 1.000 core in 167 nodi aa 32 schede 32 schede FireStreamFireStream


Da 3 mesi a 28 giorni, da 1.000 core in 167 nodi a 32 schede Fermi


Da 3 mesi a Da 3 mesi a 28 giorni28 giorni, da 1.000 core in 167 nodi, da 1.000 core in 167 nodi aa 32 schede Fermi32 schede Fermi


Progetti futuri

• Continuare a seguire lo sviluppo dell’hardware

• Modifica dell’ottimizzazione

• Meno performace, ma con una convergenza uniforme per ogni t0

• Estendere il porting su FPGA e GPGPU

• Altri modelli data-driven con più parametri da cercare

• Altri progetti



Domande?


Acceleratori hardware del calcolo ad alte prestazioni

Technology

Transcript of Acceleratori hardware del calcolo ad alte prestazioni