Architetture per il Architetture per il calcolo parallelo calcolo parallelo

(1)

Architetture per il Architetture per il

calcolo parallelo calcolo parallelo

Moreno Marzolla

Dip. di Informatica—Scienza e Ingegneria (DISI) Università di Bologna

http://www.moreno.marzolla.name/

(2)

Algoritmi Avanzati--modulo 2 2

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License (CC-BY-SA). To view a copy of this license, visit http://creativecommons.org/licenses/by- sa/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San

Francisco, California, 94105, USA.

(3)

Una architettura parallela astratta

● Come è gestito il parallelismo?

● Dove si trova fisicamente la memoria?

● Quale è la topologia della rete di comunicazione?

CPU CPU CPU CPU

Rete di interconnessione

Memoria Memoria Memoria

(4)

Perché studiamo le architetture parallele?

● Non esiste il “calcolatore parallelo tipico”: diversi produttori adottano architetture diverse

– Conseguentemente non esiste un singolo paradigma di programmazione parallela valido per tutte le architetture

● Il tipo di architettura parallela ha un enorme impatto sulle prestazioni dei programmi

● Sarebbe bello riuscire a descrivere algoritmi paralleli in modo generico e indipendente dall'architettura; questo faciliterebbe la portabilità

● La triste verità è che, In generale, è necessario

utilizzare algoritmi ad-hoc in base all'architettura del sistema su cui verranno implementati

(5)

Architettura di Von Neumann

e sue estensioni

(6)

Architettura di Von Neumann

Processore

(CPU) Memoria Sottosistema

di interfaccia (I/O)

Bus di sistema

(7)

Un po' più in dettaglio

ALU

R0 R1 Rn PC

PSW IR

Memoria Memoria

Bus _Controllo

Dati Indirizzi

Controllo

(8)

Ciclo Fetch-Decode-Execute

● Eseguito in continuazione dalla CPU

● Fetch

– Preleva dalla memoria l'istruzione da eseguire; l'istruzione viene prelevato dall'indirizzo di memoria che si trova in PC; il contenuto di tale cella di memoria viene posto in IR

● Decode

– Esamina l'istruzione che si trova memorizzata in IR per decidere cosa fare

● Execute

– Esegue l'istruzione memorizzata in IR, incluso il recupero dalla memoria degli eventuali parametri necessari ad

eseguirla, e deposito del risultato

(9)

● Ridurre la latenza degli accessi alla memoria

– Sfruttare i registri della CPU e le cache

● “Nascondere” la latenza degli accessi alla memoria

– Multithreading e context-switch durante gli accessi alla memoria

● Esecuzione di istruzioni in parallelo

– Pipelining

– Multiple issue

– Branch prediction

– Speculative execution

– SIMD multimedia extensions

Limitare i colli di bottiglia

dell'architettura di Von Neumann

(10)

Località e parallelismo

● Le memorie capienti sono lente, le memorie veloci hanno capienza limitata

● Le applicazioni dovrebbero fare il massimo uso di dati

“locali” per ottenere le migliori prestazioni

CPU L! Cache L2 Cache

L3 Cache

Memoria

(possibile) bus di interconnessione

(11)

Gerarchia di cache dell'architettura AMD Bulldozer

Fonte: http://en.wikipedia.org/wiki/Bulldozer_%28microarchitecture%29

(12)

Gerarchia di memoria CUDA

Block

Global Memory Constant Memory Texture Memory

Local Memory

Shared Memory Registers Registers

Thread Thread

Local Memory

Block

Local Memory

Shared Memory Registers Registers

Thread Thread

Local Memory

(13)

Instruction Level Parallelism (ILP)

● Aumenta le prestazioni del processore mediante più unità funzionali che operano contemporaneamente

– Pipelining: le unità funzionali sono organizzate in “fasi”, come una catena di montaggio

– Multiple issue: le unità funzionali possono essere utilizzate in qualsiasi ordine

● Static multiple issue: l'uso delle unità funzionali è stabilito a tempo di compilazione (esempio: Intel IA64)

● Dynamic multiple issue (superscalar): l'uso delle unità funzionali è deciso dal processore durante l'esecuzione del programma

(14)

Instruction Level Parallelism

IF ID EX MEM WB

IF Instruction Fetch ID Instruction Decode EX Execute

MEM Memory Access WB Write Back

Instruction Fetch and Decode Unit

Integer Integer Floating Point

Load Store

Commit Unit In-order commit In-order issue

Out of order execute

Floating Point

Pipelining

Multiple Issue

(15)

Speculation

● Per usare la tecnica di multiple issue, il processore deve individuare quali istruzioni possono essere

eseguite contemporaneamente

● Nella esecuzione speculativa il compilatore o il

processore ipotizzano l'esito di certe operazioni in corso (tipicamente, confronti) e in base a tale ipotesi decidono quale istruzione successiva eseguire

(16)

Speculation

z = x + y;

if ( z > 0 ) { w = x ; } else {

w = y ; }

● Se il processore ritiene che il confronto “z > 0” darà come risultato true, inizierà ad

eseguire “w = x” prima

ancora che l'espressione “z

> 0” sia stata valutata

● Se l'ipotesi si rivelasse sbagliata, dovrà

interrompere l'esecuzione di

“w = x” ed eseguire “w = y”

(17)

Nel mondo reale...

● Dalla documentazione di GCC

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

— Built-in Function: long __builtin_expect (long exp, long c)

You may use __builtin_expect to provide the compiler with branch

prediction information. In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform. However, there are

applications in which this data is hard to collect.

The return value is the value of exp, which should be an integral

expression. The semantics of the built-in are that it is expected that exp ==

c. For example:

if (__builtin_expect (x, 0)) foo ();

(18)

Branch Hint: Esempio

#include <stdlib.h>

int main( void ) { int A[1000000];

size_t i;

const size_t n = sizeof(A) / sizeof(A[0]);

for ( i=0; __builtin_expect( i<n, 1 ); i++ ) { A[i] = i;

}

return 0;

}

Evitate accuratamente queste micro-

ottimizzazioni, a meno che non sappiate esattamente cosa state facendo.

(19)

Hardware multithreading

● Consente al processore di eseguire istruzioni anche quando il task corrente è in stallo

– ad esempio, perché sta aspettando dati dalla memoria

● Fine-grained: il context-switch tra thread ha costo

pressoché nullo e puo' quindi avvenire istruzione per istruzione

– Richiede CPU con supporto specifico,e.g., Cray XMT

● Coarse-grained: il context-switch avviene solo per i thread bloccati per periodi più lunghi (es., su I/O)

– Context switch solitamente più oneroso, minore efficienza dell'utilizzo della CPU in presenza di stalli di breve durata

(20)

Hardware multithreading

● Simultaneous multithreading (SMT) è una variazione di fine-grained multithreading basato sul fatto che

diversi thread possono usare contemporaneamente unità funzionali diverse

● Nei sistemi SMT istruzioni di thread diversi possono contemporaneamente essere presenti in diverse

unita' funzionali Instruction Fetch and Decode Unit

Integer Integer Floating Point

Load Store

Commit Unit

Floating Point

(21)

HyperThreading

● Implementazione recente della tecnologia SMT da parte di Intel

● Ogni core fisico presente sul processore viene visto e gestito dal Sistema Operativo come due core logici distinti

● HT sfrutta l'architettura superscalare del processore (cioè il fatto che alcune unità—ad esclusione dell'unità principale di esecuzione—sono duplicate e possono operare in parallelo)

(22)

Architetture Parallele

(23)

Tassonomia di Flynn

SISD

Single Instruction Stream Single Data Stream

SIMD

Single Instruction Stream Multiple Data Streams

MISD

Multiple Instruction Streams Single Data Stream

MIMD

Multiple Instruction Streams Multiple Data Streams

Data Streams

Single Multiple

Instruction Streams MultipleSingle

Architettura di Von Neumann

(24)

SIMD

● I sistemi SIMD consentono di applicare la stessa

istruzione (tipicamente aritmetica/logica, e.g., somma, prodotto, …) a più dati contemporaneamente

(tipicamente, 4 oppure 8)

● Questo implica che la ALU debba essere replicata 4/8/... volte

LOAD A[0]

LOAD B[0]

C[0] = A[0] + B[0]

STORE C[0]

LOAD A[1]

LOAD B[1]

C[1] = A[1] + B[1]

STORE C[1]

LOAD A[2]

LOAD B[2]

C[2] = A[2] + B[2]

STORE C[2]

LOAD A[3]

LOAD B[3]

C[3] = A[3] + B[3]

STORE C[3]

Tempo

(25)

SSE (Streaming SIMD Extensions)

● Estensione al set di istruzioni x86

● 70 nuove istruzioni in grado di operare

prevalentemente su numeri floating point in precisione singola

● 8 nuovi registri a 128 bit (XMM0—XMM7)

– rappresentano 4 float a 32 bit in precisione singola

● SSE2 consente di rappresentare

– 2 double a 64 bit, oppure

– 2 interi a 64 bit, oppure

– 4 interi a 32 bit, oppure

– 8 short int a 16 bit, oppure

– 16 caratteri a 8 bit

XMM0

32 32 128 32 32

XMM1

(26)

SSE (Streaming SIMD Extensions)

X3 X2 X1 X0

Y3 Y2 Y1 Y0

X3 op Y3 X2 op Y2 X1 op Y1 X0 op Y0

32 32 32 32

op op op op

(27)

Esempio

__m128 a = _mm_set_ps( 1.0, 2.0, 3.0, 4.0 );

__m128 b = _mm_set_ps( 2.0, 4.0, 6.0, 8.0 );

__m128 ab = _mm_mul_ps( a, b );

1.0 2.0 3.0 4.0

2.0 4.0 6.0 8.0

2.0 8.0 18.0 32.0

a b

ab

_mm_mul_ps( a, b )

32 32 32 32

(28)

GPU

Chip GPU Fermi (fonte:

http://www.legitreviews.com/article/1100/1/)

● Le moderne GPU

(Graphics Processing Units) includono un elevato numero di

“core” che esibiscono caratteristiche simili a sistemi SIMD

(29)

CPU vs GPU

ALU ALU

ALU Control

Cache DRAM

ALU

DRAM

CPU GPU

● Le differenze sono evidenti se consideriamo come vengono utilizzati i transistor presenti sul chip

(30)

GPU core

● Un singolo core contiene una unità fetch/decode condivisa tra più ALU

– 8 ALU = ciascuna

istruzione può operare su 8 dati simultaneamente

● Ogni core mantiene più contesti di esecuzione ed è in grado di passare dall'uno all'altro a costo

~zero

– Fine-grained parallelism

ALU ALU ALU ALU ALU ALU ALU ALU

Ctx Ctx

Ctx Ctx Ctx Ctx

Fetch / Decode

Ctx Ctx Ctx

Ctx

(31)

GPU

● 12 stream di istruzioni x 8 ALU = 96 operazioni in parallelo

(32)

MIMD

● Nelle architetture MIMD sono presenti più unità di esecuzione che eseguono sequenze di istruzioni indipendenti

– Multiple Instruction Streams

● Ogni unità di esecuzione può operare su dati differenti dalle altre

– Multiple Data Streams

CALL F() z = 8 y = 1.7 z = x + y

a = 18 b = 9 if ( a>b ) c = 7

a = a - 1

w = 7 t = 13 k = G(w,t)

k = k + 1

Tempo

LOAD A[0]

LOAD B[0]

C[0] = A[0] + B[0]

STORE C[0]

(33)

Architetture MIMD

● Shared Memory

– Un insieme di processori che

condividono una memoria comune

– Ogni processore puo' accedere direttamente ad una qualsiasi locazione della memoria

● Distributed Memory

– Un insieme di sistemi autonomi connessi tramite una rete di comunicazione

– Nodi diversi devono comunicare tramite la rete per condividere dati

– Esempio più comune: cluster di PC connessi tramite ethernet, programmati usando MPI

Memoria

CPU CPU CPU

Interconnect

CPU

CPU Mem

Interconnect

(34)

Architetture ibride

● In pratica, i principali sistemi HPC presenti sul mercato sono basati su architetture ibride, in cui ogni nodo di calcolo è un sistema multiprocessore a memoria

condivisa, e più nodi sono collegati da una rete di interconnessione

CPU Mem

Interconnect CPU

CPU CPU GPU GPU

CPU Mem CPU

CPU CPU GPU GPU

CPU Mem CPU

CPU CPU GPU GPU

CPU Mem CPU

CPU CPU GPU GPU

(35)

Esempio shared memory

Intel core i7 AMD “Istanbul”

(36)

Esempio distributed memory IBM BlueGene / Q @ CINECA

Architecture 10 BGQ Frame Model

IBM-BG/Q

Processor Type

IBM PowerA2, 1.6 GHz Computing Cores

163840

Computing Nodes 10240

RAM

1GByte / core Internal Network 5D Torus

Disk Space

2PByte scratch space Peak Performance 2PFlop/s

(37)

(38)

(39)

www.top500.org

(40)

www.top500.org

(41)

SANDIA ASCI RED Data:

1996

Prestazioni di picco:

1.8Teraflops Ingombro:

150m²

Consumo energetico:

800.000 Watt

(42)

SANDIA ASCI RED Data:

1996

1.8Teraflops Ingombro:

150m²

Consumo energetico:

800.000 Watt Sony

PLAYSTATION 3 Data:

2006

>1.8Teraflops Ingombro:

0.08m² Consumo energetico:

<200 Watt

(43)

Dentro la PS3

Cell Broadband Engine

(44)

Conclusioni

● Memoria condivisa

● Vantaggi:

– In generale, più “facile” da programmare

– Vantaggioso per applicazioni che prevedono un accesso

“irregolare” ai dati (esempio, algoritmi di esplorazione di grafi)

● Svantaggi:

– Problemi di concorrenza/mutua esclusione

– Banda di memoria limitata

● Memoria distribuita

● Vantaggi:

– Accesso a potenze di calcolo molto elevate

– Vantaggioso per applicazioni che esibiscono forte località di accesso ai dati, con elevato rapporto computazione / comunicazione

● Svantaggi:

– Latenza della rete di comunicazione

– In generale, più complesso da programmare