Calcolo parallelo e sistemi

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria

Università degli Studi di Udine

Calcolo parallelo e sistemi

multiprocessore

Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono

Nota di Copyright

Aumento

dell'affidabilità (fault tolerance)

Aumento della velocità oltre i limiti della tecnologia corrente

Maggior potenza a minor

costo

Necessità di HW

speciale per algoritmi e tecniche di

programmazione particolari (AI)

Calcolo parallelo

• Aumenta la potenza di calcolo facendo uso di più CPU

• Può derivare da esigenze diverse:

Programmi per calcolo parallelo

• Esistono diverse strategie. In generale:

– i programmi vengono suddivisi in moduli che sono eseguiti concorrentemente e/o sequenzialmente su più processori

– i dati possono essere ripartiti tra i processori, e/o essere condivisi in una memoria comune

(arbitraggio)

– i moduli in esecuzione sui diversi processori

comunicano mediante messaggi per scambio di

dati e sincronizzazione dell'attività

Efficiency Ep = Sp/p <= 1 Rapporto tra lo speed-up effettivo

e il massimo teorico (p) Speed-up

Sp = T1/Tp ≥ 1 Aumento della velocità grazie

all'uso di p processori

Misure di efficienza

• T _p = numero di unità di tempo

necessarie per eseguire un dato calcolo

su p ≥ 1 processori

Esempi di calcolo parallelo

• Analizzeremo due semplici casi come esempio di applicazione delle formule di speed-up ed efficienza:

– calcolo di espressioni aritmetiche

– soluzione di sistema di equazioni lineari

Espressioni aritmetiche

a

+ a

+ a

+ a

+ a

+ a

+ a

+ a

+ +

+ +

+ +

+ Esecuzione sequenziale (macchina di Von Neumann)

p = 1

T

= 7

Esecuzione parallela

a

+ a

+ a

+ a

+ a

+ a

+ a

+ a

+ + + +

+ +

+

esecuzione contemporanea esecuzione

contemporanea

p = 4 T

= 3

S

= 7/3 = 2.3

E

= 2.3/4 = 0.58

j=i-m i-1

Sistemi di equazioni

• Definiamo uno schema di iterazione lineare di ordine m di un sistema di n equazioni:

x _i = 0 per i ≤ ⁰

x _i = ci + Σ ^a ij x _j per 1 ≤ ⁱ ≤ ⁿ

• In forma matriciale:

x = c + Ax dove

– x = (x ₁ ,...,x _n ) ^t c = (c ₁ ,...,c _n ) ^t

– A matrice dei coefficienti (triangolare):

– a = 0 per i ≤ j e per i - j > m

Esempio

x

= c

x

= c

+ a

x

x

= c

+ a

x

+ a

x

n = 3

m = n - 1 = 2

= +

x

x

x

x

x

x

c

c

c

0 a

a

0 0 a

0

0

0

Algoritmo parallelo

• n - 1 processori per n equazioni

• Ogni processore i inizializza il risultato dell'equazione con il termine costante c _i

• x ₁ è inizialmente noto (c ₁ )

0) j = 1 (contatore delle iterazioni)

1) broadcast di x

da parte del processore che ha terminato il calcolo

2) moltiplicazione per a

3) somma con il risultato parziale precedente 4) j = j+1

5) ripetere da 1)

Misure di speed-up ed efficienza

• Ad ogni iterazione vengono effettuate due

operazioni: una somma ed una moltiplicazione

• Su singolo processore:

T

= 2(1+2+...+(n-1)) = n(n-1)

• Su p = n-1 processori:

T

= 2(n-1)

• Perciò

S

= n(n-1) / 2(n-1) = n/2

E = S /p = n / 2(n-1) > 1/2

Possibilità di parallelizzare gli algoritmi

• Normalmente gli algoritmi possono essere

parallelizzati solo in parte, il resto va eseguito sequenzialmente (cfr. Amdahl)

• Tradeoff tra il numero di processori e il loro utilizzo effettivo a causa dei tempi di

comunicazione: al crescere del numero di processori cresce la quantità di dati da

scambiare, e quindi il tempo in cui in media

ciascun processore è in attesa di dati. Questo

riduce l'utilizzo dei processori stessi

Possibilità di parallelizzare gli algoritmi (segue)

• Il tipo di algoritmi è spesso radicalmente

differente tra macchine con alcune decine o

poche centinaia di processori e macchine a

parallelismo massiccio (decine di migliaia)

Legge di Amdahl

Speedup = (s + p) / (s + p/N)

= 1 / (s + p/N)

dove:

– s e p sono le percentuali di programma da eseguire sequenzialmente o

parallelizzabili, rispettivamente (s + p = 1)

– N è il numero di processori

Legge di Amdahl (N = 1024)

Classificazione in base al parallelismo

• Si considerano il numero di processori e la loro potenza:

– cluster

– macchine a parallelismo ridotto (anche macchine a parallelismo non strutturato, coarse-grain parallel computer)

– macchine a parallelismo massiccio (anche

macchine a parallelismo strutturato, fine-

grain parallel computer)

Classificazione dei calcolatori in base al tipo di parallelismo

(Michael J. Flynn)

• Considera le sequenze di istruzioni (instruction stream) e le sequenze di dati (data stream):

SISD: Single Instruction Stream - Single Data Stream

SIMD: Single Instruction Stream - Multiple Data Stream

MISD: Multiple Instruction Stream - Single Data Stream

MIMD: Multiple Instruction Stream - Multiple Data Stream

CU PU MM IS

IS DS

CU: control unit PU: processor unit MM: memory module IS: instruction stream DS: data stream

SISD

• È il modello classico di computer

• Le istruzioni sono eseguite sequenzialmente, ma possono sovrapporsi grazie al pipeline

• Possono essere presenti più unità funzionali,

tutte controllate da un'unica unità di controllo

SM: shared memory

PU

MM

IS

DS 1

CU IS PU

PU

. ..

MM

MM

. ..

DS 2

DS n

SM SIMD

• A questa classe appartengono gli array processor

• L'unità di controllo (CU) invia in broadcast le istruzioni alle unità di calcolo (PU)

• Ogni unità di calcolo esegue le istruzioni su

memoria Control Unit ALU

Registri

ALU Registri

ALU Registri

ALU Registri

Computer parallelo sincrono

Array processor

Memoria

Instruction fetch unit Instruction decode unit

Scalar fetch unit Scalar fetch unit

Processore scalare Processore vettoriale

Registri scalari Registri vettoriali

Pipeline scalare Pipeline vettoriale

Calcolatore vettoriale

Pipeline della medesima istruzione su diversi dati

CU

PU

MM

IS 1

IS 1 DS

CU

IS 2 PU

CU

IS n PU

. .. .

..

MM

. . . MM

^SM

IS 2

IS n

MISD

• Diverse sequenze di istruzioni applicate al medesimo insieme di dati.

• Architettura puramente ipotetica, non

esistono macchine MISD nella realtà.

CU

PU

IS 1

IS 1

CU

IS 2 PU

CU

IS ⁿ PU

. .. .

..

IS 2

IS n

MM

MM

MM

. ..

DS 1 SM DS ²

DS ⁿ

MIMD

• A questa classe appartengono i sistemi multiprocessore.

• Ogni processore esegue una distinta sequenza

di istruzioni su un distinto insieme di dati.

Memoria

control unit

multiply divide

CPU

compare shift

add

boolean instruction decoder

CPU singola con più unità aritmetiche

Pipeline di diverse istruzioni su diversi dati

main memory control

unit ALU registri

control unit ALU registri

CPU1 CPU2

Computer parallelo parzialmente asincrono

Multiprocessor (memoria comune)

bus o rete di comunicazione control

unit ALU registri memoria

locale

control unit ALU registri memoria

locale

control unit ALU registri memoria

locale

Computer parallelo asincrono

Multiprocessor (memoria locale)

Classificazione in base alla comunicazione tra i processori

• Memoria comune

• Bus

• Rete a topologia fissa, es. ipercubo, griglia, toro, ecc.

• Rete a topologia variabile, es. crossbar

switch

Comunicazione mediante rete a topologia fissa

P P

P P

P P P

array lineare

P P

P P

P

anello

P P

P P

P

stella P

P P

albero P

P P

P P

P P P

P P P

P P P

griglia

P P

P P

cubo

P P P

P P P

P P P

toro

Switch box 2x2 (2 ingressi, due uscite)

Switch box Switch box

straight exchange

upper broadcast lower broadcast

Comunicazione mediante rete a topologia variabile

• Elemento base di commutazione:

switch box

1 n ^x m

1 r ^x r 1

n 1

m ^x n

2 2

n+1

2n 2

r m

(r-1)n+1

rn r

Esempio di rete a 3 stadi

1 n n+1 2n

(r-1)n+1 rn

Comunicazione mediante rete a topologia variabile

.. . .. .

.. . .. .

.. .

.. .

.. .

.. .

.. .

.. .

.. .

.. .

.. .

.. .

.. . .. .

.. .

.. .

0 1 n = 1

00 01

10 11

n = 2 n = 4

Ipercubo

• Dimensione n:

– 2 ⁿ processori

– n canali di comunicazione in ciascun

processore

Comunicazioni in un ipercubo

0000

0001 0010

0011

0101 0111

1000

1101

1010 1111

1100 1110

1011 1001

Destination: 1101

Source: 0000

Data: 00101101

Messaggio per 1101:

1101 EXOR 0000= 1101 prima differenza:

dimensione 0

(primo bit da destra)

Comunicazioni in un ipercubo

0000

0001 0010

0011

0101 0111

1000

1101

1010 1111

1100 1110

1011 1001

Ricevuto messaggio con destinatario 1101

1101 EXOR 0001 = 1100 prima differenza:

dimensione 2

(terzo bit da destra)

Comunicazioni in un ipercubo

0000

0001 0010

0011

0101 0111

1000

1101

1010 1111

1100 1110

1011 1001

Ricevuto messaggio con destinatario 1101

1101 EXOR 0101 = 1000 prima differenza:

dimensione 3

(quarto bit da destra)

0000

0001 0010

0011

0101 0111

1000

1101

1010 1111

1100 1110

1011

0000 1001

1101

bit: 3 2 1 0

dim. 0

dim. 2

dim. 3

Comunicazioni in un ipercubo