Algoritimi Avanzati Algoritimi Avanzati modulo 2 modulo 2

(1)

Algoritimi Avanzati Algoritimi Avanzati

modulo 2 modulo 2

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)

Presentiamoci

● Moreno Marzolla

– moreno.marzolla@unibo.it

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

● Algoritmi Avanzati modulo 2

– 2 CFU (~ 20 ore di lezione)

– Aspetti pratici della programmazione parallela

– http://www.moreno.marzolla.name/teaching/AA2014/

● Orario

– Martedì ore 13:30—16:30, aula Magna Anatomia Comparata

– Mercoledì ore 13:30—15:30, stessa aula

● Ricevimento

(4)

Scopo del modulo

● Aspetti pratici della programmazione parallela

– Concetti di base

– Modelli di programmazione più diffusi

– Pattern di programmazione parallela

● Progettare e sviluppare (semplici) applicazioni parallele usando MPI e OpenMP

● Misurare le prestazioni di applicazioni parallele

(5)

Caveat

● Abbiamo poco tempo a disposizione, ci dovremo concentrare su poche cose

● Alcuni argomenti interessanti non potranno essere affrontati

– e.g., programmazione di GPU tramite CUDA/OpenCL...

– ...ma se la cosa vi interessa possiamo riparlarne per la tesi :-)

(6)

Testo adottato

● Peter S. Pacheco,

An Introduction to Parallel Programming, Morgan Kaufmann 2011, ISBN 9780123742605

(7)

Prerequisiti

● Conoscenze di

– Architetture dei calcolatori

– Sistemi operativi

– Reti di calcolatori (cenni)

● Linguaggio C

– Serve per il progetto

Brian W. Kernighan and Dennis M.

Ritchie, The C Programming Language, Second Edition Prentice Hall, Inc., 1988.

ISBN 0-13-110362-8 (paperback), 0-13- 110370-9 (hardback)

(8)

Programma del modulo

● Introduzione alle architetture parallele

● Pattern per la programmazione parallela

● Metriche per la valutazione delle prestazioni

● Programmazione di architetture a memoria condivisa in linguaggio C con OpenMP

● Programmazione di architetture a memoria distribuita in linguaggio C con MPI

(9)

Modalità d'esame

● Progetto di programmazione da svolgere individualmente, accompagnato da una breve relazione

– Verrà proposto un progetto differente prima di ogni sessione d'esami (invernale, estiva, autunnale)

● I progetti consegnati restano validi fino alla sessione d'esame di gennaio/febbraio 2016 (compresa)

● I progetti devono essere consegnati prima di sostenere l'esame del modulo 1

– Le date di consegna verranno comunicate più avanti

● Il voto finale del corso viene calcolato come

( voto_modulo_1 * 4 + voto_modulo_2 * 2 ) / 6

(10)

Valutazione del progetto

● Comprensibilità

● Correttezza

● Efficienza

● Qualità della relazione

(11)

Valutazione del progetto

● Comprensibilità

● Correttezza

● Efficienza

● Qualità della relazione

I have seen things you people wouldn't believe. Attack ships on fire off the shoulder of Orion. I watched c-beams glitter in the dark near the Tannhäuser Gate. All those moments will be lost in time, like tears in rain. Time to die...

– Blade Runner

(12)

Introduzione al calcolo parallelo

(13)

High Performance Computing

● Molte applicazioni hanno bisogno di elevata potenza di calcolo

– Meteorologia, fisica, ingegneria, animazione 3D, finanza...

● Perché?

– Per risolvere problemi più complessi

– Per risolvere gli stessi problemi in modo più accurato

– Per risolvere gli stessi problemi in minor tempo

– Per sfruttare al meglio le risorse disponibili

– ...

(14)

I bei tempi andati...

Source: Hennessy, Patterson, Computer Architecture: A Quantitative Approach Gordon E.

Moore (1929– )

(15)

I bei vecchi tempi...

● Il vecchio “contratto” tra progettisti HW e SW

– “Scrivete codice così come viene, tanto poi ci pensiamo noi progettisti HW a costruire processori veloci per farlo girare a velocità accettabile”

● Risultato

– Nessuno (sviluppatori di software, ma anche linguaggi di programmazione) si cura più di ottimizzare il codice

(16)

Lezione di fisica

● Transistor più piccoli = processore più veloce

● Processore più veloce

= maggiore energia consumata

● Maggiore energia

consumata = maggiore calore prodotto

● Maggiore calore

prodotto = processore non affidabile

Herb Sutter, The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Dr. Dobb's Journal, 30(3), March 2005,

http://www.gotw.ca/publications/concurrency-ddj.htm

(17)

Che succede oggi?

● Per fornire prestazioni sempre più elevate, gli sviluppatori HW fanno la cosa più naturale

– Creare processori con un numero elevato di core

(18)

Risultato

● La premessa

– Abbiamo chip multi-core non perché gli sviluppatori SW sappiano scrivere software parallelo, ma perché non è più possibile aumentare la frequenza di clock dei processori

● Il risultato

– L'hardware parallelo è ovunque

– Il software parallelo è raro

● La sfida

– Il software parallelo deve diventare diffuso (ed efficiente!) come l'hardware parallelo

(19)

Pian piano ci si arriva...

(20)

Il “Santo Graal”

● Da anni gli informatici tentano di sviluppare linguaggi di programmazione che “parallelizzano da soli”

– In casi particolari i risultati sono positivi

– In generale i risultati sono mediocri (quando va bene), o del tutto inesistenti (quando va male)

● Occorre quindi usare strumenti specifici e sviluppare algoritmi efficienti che traggano vantaggio dalle

caratteristiche specifiche dell'architettura parallela sottostante Qui entriamo in gioco noi

(21)

Nessuno pero' dice che sia facile...

Versione sequenziale (~49 righe di codice C++)

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

(22)

Fondamenti di Calcolo Parallelo 22

Nessuno pero' dice che sia facile...

Versione sequenziale (~49 righe di codice C++) Versione parallela (PPU+SPU) (~1000 righe di codice C/C++

15 fogli A4)

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

(23)

Esempio classico: somma

● Calcola la somma dei valori contenuti in un array A[0..n-1] di float

float seq_sum(float* A, int n) {

int i;

float sum = 0.0;

for (i=0; i<n; i++) sum += A[i];

return sum;

}

(24)

Somma parallela (schema)

● p << n core numerati come 0..p-1

● my_id è l'indice del core che esegue l'algoritmo

● Ciascun core calcola la somma degli

elementi di un sottovettore

● I core (tranne il master) inviano la somma parziale al core 0

...float my_sum = 0.0;

int i;

int my_id = …, my_start = …, my_end = …;

for ( i = my_start; i < my_end; i++ ) { my_sum += A[i];

}if ( my_id == 0 ) {

for ( i=1; i<p; i++ ) {

float v = receive from core i;

my_sum += v;

}printf(“The sum is %f\n”, my_sum);

} else {

send my_sum to core 0;

}

(25)

Somma parallela

Core 0

A[ ]

my_sum

Core 1 Core 2 Core 3 Core 4 Core 5 Core 6 Core 7

1 3 -2 7 -6 5 3 4

4

2

9

3

8

11

(26)

Problema

● Il master è il collo di bottiglia, perché riceve p - 1 messaggi e deve eseguire p - 1 somme

– Sbilanciamento del carico: nella seconda fase, l'operazione di somma dei parziali viene svolta solo dal master

● E' possibile calcolare la somma globale, partendo dai risultati parziali, in maniera più bilanciata?

(27)

Somma parallela

Core 0

A[ ]

my_sum

Core 1 Core 2 Core 3 Core 4 Core 5 Core 6 Core 7

1 3 -2 7 -6 5 3 4

5 -1 7

6

15 4

9

● In tutto si eseguono p – 1 somme tra risultati parziali; il master

(28)

Coordinazione

● I processori devono coordinare il loro lavoro

● Comunicazione

– Uno o più core inviano la propria somma parziale ad un altro core

● Bilanciamento del carico

– Dividere il lavoro tra i core in maniera uniforme

● Sincronizzazione

– Assicurarsi che il lavoro di ciascun core sia “allineato” a quello degli altri

(29)

Come scrivere applicazioni parallele?

● Task Parallelism

– Ciascun processore esegue un proprio thread (o processo) che opera sugli stessi dati o su dati diversi

– I thread possono eseguire lo stesso programma oppure, più frequentemente, programmi diversi

● Data Parallelism

– Si dividono i dati di input tra i vari core

– I core eseguono sostanzialmente lo stesso programma sui propri dati

(30)

Esempio

Task Parallel vs Data Parallel

● Supponiamo di raccogliere in un foglio di calcolo (spreadsheet) le temperature giornaliere misurate durante un anno (365 giorni) in una certa località

● La temperatura viene registrata una volta all'ora (24 misurazioni giornaliere)

● Vogliamo calcolare, per ogni giorno, la temperatura massima, minima e media

● Numero di core a disposizione: 3

(31)

Esempio

max min ave

0 1 2 3 22 23

Hour (0—23)

0 1 2

364

Days (0—364)

(32)

Approccio data parallel

max min ave

0 1 2 3 22 23

Hour (0—23)

0 1 2

364

Days (0—364)

Core 0

Core 1

Core 2

(33)

Approccio task parallel

max min ave

0 1 2 3 22 23

Hour (0—23)

0 1 2

364

Days (0—364) Core 0 Core 1 Core 2

(34)

Conclusioni

● Le leggi della fisica ci hanno condotto verso le architetture di calcolo parallele

● I programmi sequenziali generalmente non traggono vantaggio dalla presenza di più processori (core)

● La parallelizzazione automatica (quando funziona) non sempre produce la soluzione migliore

● Imparare a scrivere programmi paralleli richiede di imparare a coordinare i processori a disposizione

● I programmi paralleli sono solitamente molto

complessi e quindi richiedono tecniche adeguate di progettazione e sviluppo