1. Algoritmi Algoritmi e Calcolo ParalleloProf. Pier Luca Lanzi

2. Riferimenti2Bertossi Alan A., Montresor Alberto. Algoritmi e strutture di dati (seconda edizione), CittStudi 2010Stanley B. Lippman, Barbara E. Moo, Josee Lajoie C++ Primer, 5th Edition Addison-WesleyProf. Pier Luca Lanzi 3. http://www.youtube.com/watch?v=06Nf_YVoowQhttp://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 Minimo6Come 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? 7Sequenza 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 8Al-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 9Papiro 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, CUDAProf. Pier Luca Lanzi 11. Quali sono gli obiettivi del corso? 11Analisi 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 scalabilitProf. 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 Lanzi13 14. Che Cosa si Intende per Scalabilit?Prof. Lanzi corre i 100m in 12sProf. Pier Luca Lanzi14In quanto corre la maratona? 15. Esempio: Ricerca SequenzialeDato un elenco contenente n oggetti, cercare se un oggetto x presente Lelenco non ordinatox? 15x?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++16bool linear_find(std::vector v, int x) { int i; for (i=0; i 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 situazioniProf. Pier Luca Lanzi 26. Limitazioni del Calcolo Sequenziale26Ci 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 miniaturizzazioneLimitazioni economicheProf. Pier Luca Lanzi 27. Prestazione degli (uni)ProcessoriProf. Pier Luca Lanzi27 28. Calcolo Parallelo Abbiamo a disposizione pi esecutori, possiamo sfruttarli per risolvere problemi molto complessi, velocemente? Due possibili approcciProf. 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 esecutoriProf. Pier Luca Lanzi 30. Calcolo Parallelo30Pi 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 31Decomposizione 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 parallelaProf. 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 Lanzi32 33. Obiettivo del Corso studio, analisi, sviluppo di algoritmi sequenziali e paralleli e loro implementazioneCome risolvere un problema? Quanto costa una soluzione?Si pu fare di meglio?Prof. Pier Luca Lanzi 34. Sequenziale vs ParalleloSe 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 performanceProf. Pier Luca Lanzi