Analisi Matematica I e II, teoria della probabilità. Capacità di programmazione inl linguaggio C/C++.

Il corso fornisce un'introduzione moderna alla progettazione, analisi ed implementazione di algoritmi sequenziali e paralleli. In particolare, il corso si basa su un approccio pragmatico alla programmazione parallela di algoritmi message-passing attraverso il linguaggio C e la libreria MPI.

Knowledge and understanding.

Gli studenti devono avere un solido background con un ampio spettro di conoscenze di base sugli algoritmi sequenziali e paralleli:

• gli studenti devono possedere gli strumenti cognitivi di base per pensare in modo analitico, creativo, critico e curioso, e possedere le capacità di astrazione e di risoluzione dei problemi necessarie per affrontare sistemi complessi;
• devono avere una solida conoscenza della progettazione e dell'implementazione di algoritmi efficienti sequenziali e paralleli;
• devono possedere gli strumenti per analizzare le risorse utilizzate dagli algoritmi;
• devono possedere un catalogo dei più noti ed efficienti algoritmi sequenziali e paralleli per problemi computazionali di base.
•  

Applying knowledge and understanding.

Al termine del corso lo studente dovrebbe essere in grado di:

• Descrivere e utilizzare le principali tecniche di progettazione di algoritmi sequenziali;
• Progettare, dimostrare la correttezza e analizzare la complessità computazionale di algoritmi sequenziali;
• Comprendere le differenze tra diversi algoritmi che risolvono lo stesso problema e riconoscere quale sia migliore in condizioni diverse;
• Descrivere e utilizzare gli algoritmi sequenziali di base;
• Descrivere e utilizzare le strutture dati di base; conoscere l'esistenza di strutture dati avanzate;
• Comprendere la differenza tra algoritmi sequenziali e paralleli;
• Progettare, implementare e analizzare algoritmi paralleli basati sul message-passing in C/C++ utilizzando la libreria MPI;
• Descrivere e utilizzare algoritmi paralleli di base.

Making judgements. Gli studenti sono guidati ad apprendere criticamente tutto ciò che viene loro spiegato in classe, a confrontare diversi approcci alla soluzione di problemi algoritmici e a identificare e proporre, in modo autonomo, la soluzione più efficienti.

Communication. È fondamentale che lo studente sia in grado di comunicare con un pubblico vario e composito, non culturalmente omogeneo, in modo chiaro, logico ed efficace, utilizzando gli strumenti metodologici acquisiti e le proprie conoscenze scientifiche e, in particolare, il lessico specialistico. Il corso promuove lo sviluppo delle seguenti abilità dello studente: capacità di esporre in termini precisi e formali un modello astratto di problemi concreti, individuandone le caratteristiche salienti e scartando quelle non essenziali; capacità di descrivere e analizzare una soluzione efficace per un dato problema.

Learning skills. Gli studenti devono acquisire la capacità critica di rapportarsi, con originalità e autonomia, alle problematiche tipiche degli algoritmi sequenziali e paralleli e, in generale, alle questioni culturali legate ad altri ambiti simili. Dovranno essere in grado di sviluppare e applicare autonomamente le conoscenze e i metodi appresi in vista di un eventuale proseguimento degli studi a livello superiore (dottorato) o nella più ampia prospettiva di auto-miglioramento culturale e professionale dell'apprendimento permanente. Pertanto, gli studenti devono essere in grado di passare a forme espositive diverse dai testi di partenza per memorizzare, riassumere per sé e per gli altri e diffondere le conoscenze scientifiche.

Il corso si propone di mettere gli studenti in grado di astrarre modelli e problemi algoritmici formali da problemi computazionali concreti e di progettare soluzioni algoritmiche efficienti per questi ultimi. A tal fine si utilizzerà il seguente metodo di insegnamento. Ogni problema computazionale sarà introdotto motivandolo con esempi concreti. La presentazione di ogni argomento sarà divisa in quattro parti: 1. Descrizione del problema computazionale concreto. 2. Modellazione del problema reale mediante un problema astratto. 3. Risoluzione del problema astratto attraverso un algoritmo ottenuto con l'applicazione delle tecniche generali di progettazione di algoritmi introdotte nel corso. 4. Analisi delle risorse utilizzate dall'algoritmo. Il corso consiste in lezioni frontali ed esercitazioni in aula. Ci saranno lezioni teoriche finalizzate all'apprendimento delle tecniche di base per la progettazione e l'analisi degli algoritmi, e una parte delle lezioni dedicata alle esercitazioni in cui si illustrerà, con dovizia di esempi, come le conoscenze teoriche acquisite possano essere utilizzate per risolvere problemi algoritmici di interesse pratico e implementare algoritmi paralleli in linguaggio C/C++ attraverso la libreria MPI.

L'esame consiste in una prova scritta.

Al fine di verificare la conoscenza e la comprensione della materia da parte dello studente, La prova scritta (2 ore) verte su:

- argomenti teorici relativi alla progettazione e all'analisi di algoritmi sequenziali e paralleli;

- performance di algoritmi paralleli.

La prova scritta è valutata su una scala da 18 a 30 punti e lode, ed è superata se il voto conseguito è almeno pari a 18.

Ricevimento Studenti

Su appuntamento; contattare il docente via e-mail o al termine degli incontri di classe.

Algoritmi Sequenziali

Introduzione agli algoritmi sequenziali. Tecniche di progettazione di algoritmi. Design ed analisi. Modello RAM. Decrease and conquer. Russian Peasant multiplication. Il problema dell'ordinamento. Insertion Sort. Analisi di Insertion Sort. Correttezza. Assertions. Invariants. Correttezza di Insertion Sort. Ordini di grandezza e notazioni asintotiche. Uso delle notazioni asintotiche. Classi di funzioni. Analisi del running time di un algoritmo usando le notazioni asintotiche. Determinare la complessità computazionale di un algoritmo. Divide and conquer. Merge Sort. Equazioni di ricorrenza. Recursion tree.

Risoluzione di equazioni di ricorrenza. Metodo di sostituzione. Albero di ricorsione. Master theorem e sue estensioni. Teoremi di Akra-Bazzi. Metodo di Iterazione. Cambio di variabile. Ricorrenze lineari di ordine costante con coefficienti costanti.

Divide and conquer. Merge Sort. Binary search. Interpolation search. Powering a number. Calcolo dell'ennesimo numero di Fibonacci. Algoritmo di Strassen per la moltiplicazione matriciale. Algoritmo di Karatsuba per la moltiplicazione di due numeri. Minimo e massimo simultanei tramite divide and conquer oppure mediante algoritmo iterativo. Majority element: divide and conquer algorithm. Algoritmo di Boyer and Moore.

The hiring problem. Analisi nel caso peggiore. Analisi probabilistica di un algoritmo deterministico (average-case analysis). Variabili aleatorie indicatrici. Media di una variabile aleatoria indicatrice. Algoritmi randomizzati. Caratteristiche e differenze di un algoritmo randomizzato rispetto ad un algoritmo deterministico. Algoritmi randomizzati Monte Carlo e Las Vegas. Esempio di analisi di un algoritmo randomizzato: expected e worst-case running time. Algoritmo randomizzato di Freivald (Monte Carlo Matrix Multiplication Checker) per matrici con entries a valere su un campo GF(2). Correttezza dell'algoritmo di Freivald. Aumento della probabilità che l'output sia corretto da una probabilità costante ad una esponenzialmente elevata. Generalizzazione per matrici con entries a valere su un campo GF(d).

QuickSort. Partizionamento. Analisi nel caso peggiore. Analisi nel caso medio. Considerazioni introduttive sulla complessita' dell'algoritmo nel caso medio. Un esempio di analisi nel caso medio errata. Disuguaglianza di Jensen. Analisi dettagliata del caso medio tramite variabili aleatorie indicatrici. Paranoid Quicksort. Analisi nel caso medio di Paranoid Quicksort.

Transform and Conquer: instance simplification, representation change, problem reduction. Heaps. Max-Heap e Min-Heap. Max-Heapify. Build-Max-Heap. HeapSort. Priority Queues.

Lower bound per algoritmi di ordinamento per confronti. Ordinamento in tempo lineare. Counting sort. Radix sort. Bucket sort.

Statistiche d'ordine. Selezione in tempo atteso lineare. Selezione in tempo lineare nel caso peggiore.

Introduzione alla programmazione dinamica. Matrix Chain Multiply. Optimal substructure. Overlapping subproblems. Top-down divide and conquer approach with memoization. Bottom-up iterative approach. Longest Common Subsequence. Elementi fondamentali della programmazione dinamica. Knapsack problem. 0-1 and fractional knapsack. Algoritmo basato su programmazione dinamica per 0-1 knapsack. Algoritmi pseudo-polinomiali.

Strategia greedy. Greddy choice property. Activity selection problem. Algoritmo basato su programmazione dinamica per activity selection. Algoritmo greedy per activity selection. Confronto tra approccio greedy e programmazione dinamica. Algoritmo greedy applicato a Knapsack 0-1 e fractional knapsack. Minimum Spanning Tree. Algoritmo di Prim.

Paths in graphs. Shortest paths. Optimal substructure. Triangle inequality. Negative weight cycles. Single-source shortest paths. Dijkstra’s algorithm. Correctness and analysis. Unweighted graphs and breadth-first search. Correctness and analysis. Belmann-Ford algorithm. Correctness and analysis. Shortest paths in Directed Acyclic Graphs: topological sort and depth-first search. All-pairs shortest paths. Dynamic programming algorithm. Floyd-Warshall algorithm. Correctness and analysis. Transitive closure of a directed graph.

Flow networks. Capacity constraint. Flow conservation. Maximum flow problem. Cuts. Flow across a cut. Capacity of a cut.   Minimum cut. Characterization of flow value. Upper bound on the maximum flow value. Residual network. Residual capacities. Augmentation of a flow. Augmenting paths. Max-flow min-cut theorem. Ford-Fulkerson algorithm. Analysis. Pseudo-polinomiality of Ford-Fulkerson. Edmonds-Karp algorithm. Monotonicity lemma. Counting flow augmentations. Analysis of Edmonds-Karp.  

Maximum matching problem. Maximum and maximal matching. 2-approximation greedy algorithm for maximal matching. Approximation algorithms. Maximum matching on bipartite graphs.

Introduzione alla complessita' computazionale concreta. Presentazione informale delle classi di complessita' P, NP e NPC. Problemi astratti e concreti. Problemi decisionali. Codifica di un problema. Linguaggi formali. Caratterizzazione formale delle classi P, NP e NPC. Riduzioni in tempo polinomiale. Il problema P = NP e sue implicazioni. Problemi NP-Completi. Dimostrazioni di NP-Completeness. Circuit-SAT. SAT. 3-CNF-SAT. Clique. Vertex cover. Tipi di computazione: deterministica, randomizzata, nondeterministica. Computing models: RAM e Turing Machine. Nondeterminismo. Church-Turing thesis. Linguaggi decidibili, semidecidibili e indecidibili. Extended Church-Turing thesis. Sequential computing thesis. Upper bounds e lower bounds. Classi di complessita’ di base. Relazioni tra RAM e Turing Machine. Classi di complessita’ L, NL, P, NP, POLYLOGSPACE, PSPACE, EXP. Riduzioni e completezza. P-Completeness. Tesi del calcolo parallelo. Problemi altamente parallelizzabili. Classe Polylogspace. Classe NC. Problemi difficilmente parallelizzabili: i problemi P-Completi.

Algoritmi Paralleli

Introduction to parallel computing. Concurrency, parallelism and Bernstein's conditions. Data Parallelism, functional parallelism and pipeline. Data and functional parallelism example: a generic clustering algorithm. Architetture parallele. Message-Passing and shared memory. MPI and OpenMP.

Task-Channel model. Metodologia PCAM. Partitioning. Domain e functional decomposition. Comunicazione. Comunicazione locale e globale, strutturata e non strutturata. Agglomerazione. Granularity. Surface to volume effect. Communication/computation ratio. Mapping. Static and dynamic mapping decision tree. Case studies. Boundary value problem. Determinare il massimo. Reduction. The n-body problem. Gather. All-gather. Adding data input. Scatter. Message-Passing model. Libreria MPI.

Circuit-SAT: parallelizzazione tramite MPI. User-Defined Reductions. Derived datatypes. Benchmarking. How to install the MPI library on linux, macOS and Windows.

Crivello di Eratostene. Parallelizzazione. Allocazione a blocchi. Broadcast in MPI. Sieve performance enhancements. Eliminare i numeri pari, replicare il calcolo per eliminare le comunicazioni, riorganizzare i cicli per migliorare il cache hit rate. Analysis and benchmarking.

All-pairs shortest path problem. Dynamic 2-D arrays in C. Parallel algorithm design: Partitioning. Communication. Agglomeration e mapping. Rowwise e Columnwise block striped decompositions. Point-to-point communication in MPI. Block row matrix I/O. Analysis and benchmarking. Overlapping communication and computation.

Analisi delle prestazioni. Communication overhead. Total overhead. Work. Cost. Degree of concurrency. Maximum and average degree of concurrency. Critical Path Length, also known as span or depth. Parallelism. Work Law. Span Law. Brent's theorem. Execution time components. General speedup formula. Optimal number of processors. Super-linear speedup. Another definition of overhead, based on the speedup. Efficiency. Amdahl’s effect. Amdahl’s Law. Gustafson’ Law. Karp-Flatt metric. Isoefficiency Metric. Scalability. Strongly scalable and weakly scalable algorithms. Quasi-scalable algorithms and the scaling zone. Scalability function. Cost-Optimality (Work-Efficiency) and Isoefficiency. Scaling down dei processori. Impatto della mancanza di cost-optimality. Minimum Parallel execution Time. Minimum Cost-Optimal Parallel Execution Time.

Moltiplicazione matrice-vettore. Sequential algorithm and its complexity. Design, analysis, and implementation of parallel programs based on Rowwise block striped, and Columnwise block striped decompositions. Replication of vectors. All-gather. MPI_Allgatherv. All-to-all. MPI_Scatterv. MPI_Gatherv. MPI_Alltoallv. Moltiplicazione matrice-vettore: algoritmo basato su decomposizione checkerboard block. Design ed analisi. Creazione di communicators con topologia cartesiana in MPI. Creazione di communicators mediante MPI_Comm_split. Document classification. Parallel algorithm design. Manager-worker paradigm (master-slave). Creating communicators. Non-blocking communications. Additional MPI functions.

Moltiplicazione matriciale. Sequential algorithms: Iterative row-oriented and Recursive block-oriented. Parallel algorithms: Rowwise block striped decomposition and Cannon’s algorithm. DNS Algorithm. SUMMA algorithm. Fox's matrix multiplication algorithm.

Dense linear systems. Special matrices. Back substitution algorithm. Parallel row-oriented algorithm. Parallel column-oriented algorithm. Gaussian elimination algorithm. Avoiding numerical issues: partial pivoting. Parallel row-oriented algorithm MPI reduction operators MPI_MAXLOC and MPI_MINLOC. Parallel column-oriented algorithm. Pipelined row-oriented algorithm. Sparse linear systems. Jacobi and Gauss-Seidel methods. Conjugate Gradient Method. Parallel algorithm based on rowwise block striped decomposition.

Ordinary and partial differential equations. Examples of Phenomena Modeled by PDEs. Solving PDEs. Linear Second-order PDEs. Difference Quotients. Finite difference methods. Vibrating string problem. Discretization. Parallelization. Ghost cells. Analysis. Replication of computations done by neighbouring processes to reduce communications. Steady state heat distribution problem. Parallel algorithm based on rowwise block striped and checkerboard block decompositions. Analysis.

Sorting problem. Sequential Quicksort algorithm. Parallel Quicksort. Complexity and isoefficiency analysis. HyperQuicksort. Complexity and isoefficiency analysis. Parallel sorting by regular sampling. Complexity and isoefficiency analysis. 

Parallel Programming

Message-Passing programming using the MPI library.

Introduction to Algorithms. Fourth edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP (International Edition). Michael J. Quinn. McGraw-Hill