1. Algoritmi Algoritmi e Calcolo Parallelo Prof. Pier Luca Lanzi

2. Riferimenti 2 Bertossi Alan A., Montresor Alberto. Algoritmi e strutture di dati (seconda edizione), CittStudi 2010 Stanley B. Lippman, Barbara E. Moo, Josee Lajoie C++ Primer, 5th Edition Addison-Wesley Prof. Pier Luca Lanzi

3. http://www.youtube.com/watch?v=06Nf_YVoowQ http://www.youtube.com/watch?v=06Nf_YVoowQ Prof. Pier Luca Lanzi

4. Come si cucina il tiramis? Quanto tempo si impiega per prepararlo per due persone? Quanto tempo per dieci persone? Quanto tempo per preparalo per cento persone? Prof. Pier Luca Lanzi

5. Se un amico vi aiutasse, come cambierebbe la procedura? Sareste pi rapidi se due amici vi aiutassero? E se cento amici vi aiutassero? Prof. Pier Luca Lanzi

6. Calcolo del Cammino Minimo 6 Come si calcola il cammino minimo fra due punti? Quanto tempo vi serve per calcolarlo? Avere pi persone aiuterebbe? Prof. Pier Luca Lanzi

7. Cos un Algoritmo? 7 Sequenza finita di passi, definiti con precisione, che portano alla realizzazione di un compito La sequenza di passi deve essere finita e deve portare ad un risultato Le istruzioni devono essere eseguibili materialmente e devono essere espresse in modo non ambiguo Un algoritmo deve essere comprensibile al suo esecutore, corretto, ed efficiente Forniscono descrizione astratta di un metodo (procedimento) per giungere alla soluzione di un dato problema Prof. Pier Luca Lanzi

8. Un po di storia 8 Al-Khwrizm, astronomo e matematico Persiano, nell825 scrive il trattato On Calculation with Hindu Numerals Tradotto in latino nel XII secolo, come Algoritmi de numero Indorum Algoritmi era la traduzione del nome dellautore (Al-Khwrizm) ma il termine stato frainteso come il plurare Latino algorismus Nel 1240, il termine usato in nel manuale Carmen de Algorismo di Alexandre de Villedieu. Francobollo emesso il 6 Settembre 1983 dallUnione Sovietica per commemorare il compleanno di Al-Khwrizm's (780850), fonte http://www.wikipedia.org Prof. Pier Luca Lanzi

9. Un Po' di Storia 9 Papiro di Ahmes (algoritmo per la moltiplicazione) Algoritmi di tipo numerico furono studiati da matematici babilonesi ed indiani Algoritmi in uso fino a tempi recenti furono studiati dai matematici greci pi di 2000 anni fa Algoritmo di Euclide per il Massimo Comune Divisore Algoritmi geometrici (calcolo di tangenti, sezioni di angoli, ...) Prof. Pier Luca Lanzi

10. qual lobiettivo del corso? imparare i principi generali algoritmi, strutture dati, calcolo parallelo impararli a utilizzare ora C++, programmazione a oggetti, MPI, OpenMP, CUDA Prof. Pier Luca Lanzi

11. Quali sono gli obiettivi del corso? 11 Analisi di algoritmi noti per il design di algoritmi nuovi Analisi degli algoritmi? Performance (velocit) Utilizzo delle risorse (memoria e comunicazione) Ci sono molti altri aspetti (non trattati qui): Correttezza, robustezza, mantenibilit Modularit, sicurezza, facilit duso Prof. Pier Luca Lanzi

12. Perch ci interessa la performance? La performance spesso determina il confine tra quello che possibile e quello che non possibile fare Lanalisi degli algoritmi ci aiuta a capire il concetto di scalabilit Prof. Pier Luca Lanzi

13. Esempio: N-body simulation & FFT Simulare le interazioni gravitazionali fra N corpi con un algoritmo brute-force richiede un tempo dellordine di N2 Lalgoritmo di Barnes-Hut richiede un tempo dellordine di NlogN Lalgoritmo brufe-force per la trasformata di Fourier discreta richiede un tempo dellordine N2 La versione FFT, NlogN Prof. Pier Luca Lanzi 13

14. Che Cosa si Intende per Scalabilit? Prof. Lanzi corre i 100m in 12s Prof. Pier Luca Lanzi 14 In quanto corre la maratona?

15. Esempio: Ricerca Sequenziale Dato un elenco contenente n oggetti, cercare se un oggetto x presente Lelenco non ordinato x? 15 x? x? x? x? x! Caso migliore? Quello che cerco il primo Caso peggiore? Ho n elementi e quello che cerco lultimo Caso medio? Circa n/2 Prof. Pier Luca Lanzi

16. Codifica in C++ 16 bool linear_find(std::vector v, int x) { int i; for (i=0; i

17. Ricerca Binaria di un Elemento 17 Supponiamo ora che lelenco sia ordinato alfabeticamente Esempio: lelenco del telefono o un dizionario Rossi? A B C ... N ... ... Caso migliore? Quello che cerco il primo Caso peggiore? Caso medio? Prof. Pier Luca Lanzi ... Z

18. Codifica in C++ 18 bool binary_find(std::vector v, int x) { int l = -1; int r = v.size(); // l, r are the search // bounds while (l+1 != r) { // Stop when l, r meet int i = (l+r)/2; // Check middle if (x < v[i]) r = i; // Left half if (x == v[i]) return true; // Found it if (x > v[i]) l = i; // Right half } return false; // Search value not in array } // http://ideone.com/fBTUs // http://ideone.com/e3bXr Prof. Pier Luca Lanzi

19. quale dei due algoritmi ha prestazioni migliori? quali sono le ipotesi di lavoro alla base dei due algoritmi? Prof. Pier Luca Lanzi

20. perch studiare gli algoritmi da un punto di vista teorico? Prof. Pier Luca Lanzi

21. VignettaLuca Computers and Intractability di Garey and Johnson Prof. Pier da Lanzi

22. VignettaLuca Computers and Intractability di Garey and Johnson Prof. Pier da Lanzi

23. VignettaLuca Computers and Intractability di Garey and Johnson Prof. Pier da Lanzi

24. La ricerca binaria sempre pi efficiente? Prof. Pier Luca Lanzi

25. Gli algoritmi lavorano su dati che vengono organizzati secondo una certa struttura Se la struttura efficiente allora gli algoritmi sono pi efficienti Ogni struttura dati ha costi/benefici Raramente c una soluzione che va bene in tutte le situazioni Prof. Pier Luca Lanzi

26. Limitazioni del Calcolo Sequenziale 26 Ci sono diverse ragioni che limitano la costruzione di calcolatori sequenziali sempre pi veloci Velocit di trasmissione La velocit di un calcolatore sequenziale dipende dalla velocit di trasferimento dei dati Il limite la velocit della luce (30 cm/nanosecondo) e i limiti del rame (9 cm/nanosecondo). Velocit superiori richiedono maggiore vicinanza fra le unit che processano linformazione Limiti della miniaturizzazione Limitazioni economiche Prof. Pier Luca Lanzi

27. Prestazione degli (uni)Processori Prof. Pier Luca Lanzi 27

28. Calcolo Parallelo Abbiamo a disposizione pi esecutori, possiamo sfruttarli per risolvere problemi molto complessi, velocemente? Due possibili approcci Prof. Pier Luca Lanzi

29. (1) diversi esecutori, lavorano su diverse istanze dello stesso problema (2) il problema complesso viene suddiviso in sottoproblemi pi semplici diversi esecutori lavorano simultaneamente sui sottoproblemi (in parallelo) identificare i sottoproblemi, coordinare gli esecutori Prof. Pier Luca Lanzi

30. Calcolo Parallelo 30 Pi processori (risolvono i sottoproblemi) La rete (collega i processori/risolutori dei sottoproblemi) Ambiente per creare e gestire processi paralleli Sistema Operativo Paradigma di programmazione parallela (Message Passing, Data Parallel, ecc.) Un algoritmo parallelizzabile e l implementazione parallela (la scomposizione del problema in sottoproblemi) Prof. Pier Luca Lanzi

31. Programmazione Parallela 31 Decomposizione di un algoritmo in sottoproblemi o dei suoi dati in parti Distribuzione dei sottoproblemi ai processori che li risolvono contemporaneamente (in parallelo) Coordinamento del lavoro e comunicazione fra i processori Considerazioni Quale architettura usiamo? Quale tipo di comunicazione usiamo? Inizialmente, vedremo il parallelismo in maniera astratta successivamente vedremo uno dei paradigmi di programmazione parallela Prof. Pier Luca Lanzi

32. Perch ci Interessa il Calcolo Parallelo? Simulazione e Modellistica Maggiore potenza di calcolo, maggiore laccuratezza Problemi con grandi quantit di dati Elaborazione immagini/segnali Rendering Data Mining WWW Grand Challenge Modelli climatici Fluidodinamica Genoma umano Prof. Pier Luca Lanzi 32

33. Obiettivo del Corso studio, analisi, sviluppo di algoritmi sequenziali e paralleli e loro implementazione Come risolvere un problema? Quanto costa una soluzione? Si pu fare di meglio? Prof. Pier Luca Lanzi

34. Sequenziale vs Parallelo Se avessi pi di un esecutore, potrei risolvere problemi pi grandi? Avere pi esecutori, richiede spesso un ripensamento dellalgoritmo Trade-off fra complessit di design e guadagno di performance Prof. Pier Luca Lanzi