Università del Salento

Collegamenti ai contenuti della pagina:
unisalento-theme-il-contenuto-pagina
Il menu di navigazione
Motore di ricerca
Area Riservata
Accessibilità


testata phonebook


 



unisalento-theme-contenuto-della-pagina [Inizio pagina]

Massimo CAFARO

CORSI

PARALLEL ALGORITHMS
 

Corso di Laurea: Computer Engineering

 
SSD:   ING-INF/05
 
anno di corso:        II
periodo:       primo
crediti formativi:     9
 
 
Requisiti
 

Analisi I e II, Teoria della Probabilita’. Conoscenze pregresse del linguaggio di programmazione C.

 
Obiettivi del corso
 

Il corso fornisce una moderna introduzione alla progettazione, analisi ed implementazione di algoritmi sequenziali e paralleli. In particolare, il corso e’ basato su un approccio pratico alla programmazione parallela di algoritmi message-passing in linguaggio C con la libreria MPI.

 

Dopo aver seguito il corso, lo studente dovrebbe essere in grado di:

 

1)      descrivere ed utilizzare le principali tecniche di progettazione di algoritmi sequenziali;

2)      progettare, provare la correttezza, implementare ed analizzare la complessita’ computazionale di algoritmi sequenziali;

3)      comprendere le differenze tra algoritmi diversi che risolvono uno stesso problema e riconoscere quale algoritmo e’ il migliore rispetto a condizioni diverse;

4)      descrivere ed utilizzare algoritmi sequenziali di base;

5)      descrivere ed utilizzare strutture dati di base; conoscere l’esistenza di strutture dati avanzate;

6)      comprendere le differenze tra algoritmi sequenziali e paralleli;

7)      progettare, provare la correttezza, implementare ed analizzare la complessita’ computazionale di algoritmi paralleli basati su message-passing in C  utilizzando la libreria MPI;

8)      descrivere ed utilizzare algoritmi paralleli di base.
 
 
Modalita’ d’esame
 

L’esame e’ orale. Opzionalmente, allo studente puo’ essere assegnato un piccolo progetto. Duramte l’esame, allo studente viene chiesto di illustrare argomenti teorici per verificare la sua conoscenza e comprensione degli argomenti scelti. Allo studente puo’ essere chiesto di progettare un semplice algoritmo per verificare la sua capacita’ di identificare ed utilizzare le tecniche di progettazione piu’ appropriate. Alternativamente, allo studente puo’ essere chiesto di analizzare la complessita’ computazionale di un breve frammento di codice.

 
Sito Internet di riferimento
 
http://sara.unisalento.it/moodle/
 
 
 

Programma                     

 
Algoritmi sequenziali
 

Introduzione. Ordini di grandezza. Analisi di algoritmi. Decrease and conquer. Divide and conquer. Ricorrenze. (7 ore) Algoritmi randomizzati. (5 ore)  Transform and conquer. (2 ore)  Lower bound for sorting. Linear time sorting algorithms: Counting sort, Radix sort and Bucket sort. (3 ore) Order statistics. Selection in expected and worst case linear time. (2 ore) Programmazione dinamica. (4 ore) Algoritmi greedy. (3 ore) Complessita’ e calcolabilita’. NP-Completezza. (7 ore)

 
Algoritmi paralleli
 

1) Introduzione. Metodo scientifico moderno. Concorrenza e parallelismo. Equazioni di Bernstein. Evoluzione del supercalcolo. Calcolatori paralleli. Grafo delle dipendenze dei dati. Data parallelism. Functional Parallelism. Pipelining. Approcci per la programmazione di calcolatori paralleli. (2 ore)

 

2) Architetture parallele. Reti di interconnessione. Shared e switched media. Topologie di rete. 2D mesh. Binary tree. Hypertree. Fat tree. Butterfly. Ipercubo. Torus. Shuffle-exchange. Processor arrays. Multiprocessori centralizzati e distribuiti. Multicomputers asimmetrici e simmetrici. Clusters e reti di workstations. Tassonomia di Flinn. (5 ore)

 

3) Parallel algorithm design. Modello task-channel. Metodologia PCAM di Foster. Decomposizioni, tasks e grafo delle dipendenze dei tasks. Grain size di una decomposizione. Grado di concorrenza. Critical path length. Grafo delle interazioni dei tasks. Processi e mapping. Recursive decomposition, Data decomposition Exploratory decomposition, Speculative decomposition. Decomposizione di dati di input, intermedi e di output. Decomposizione ibride e gerarchiche. The Owner Computes Rule. Tasks static e dinamici. Comunicazione locale, globale, strutturata e non strutturata. Task interactions: read-only, read-write, one-way, two-way. Comunicazione static e dinamica, sincrona ed asincrona. Algoritmi red-black.  Divide and conquer. Agglomerazione. Effetto surface to volume. Communication/computation ratio. Replicare la computazione per eliminare comunicazioni. Mapping. NP-completeness del mapping. Mapping static e dinamico.     Mappings based on data partitioning. Mappings based on task graph partitioning. Hybrid mappings. Probabilistic mapping, cyclic and block-cyclic. Graph partitioning. Recursive bisection. Quad and Oct-trees. Space-filling curves. Scattered decomposition. Dynamic load-balancing. Centralized dynamic mapping, master-slave (manager-worker), chunck scheduling. Distributed dynamic mapping. Dynamic data driven mapping. Dynamic geometric decomposition: Adaptive Mesh Refinement (AMR). Esempi di progettazione di algoritmi paralleli: boundary value problem, reductions, n-body problem. Data input. (10 ore)

 
 

4) Message-Passing programming. Message-passing model. MPI. Circuit-SAT problem. Communicators. Point-to-point communications: vari tipi di send e receive. Collective communications: broadcast, reductions, scatter, gather, all-gather,  all-to-all. Benchmark. (2 ore)

 

5) Crivello di Eratostene: progettazione, analisi, implementazione e benchmark. (2 ore)

 

6) Algoritmo di Floyd all-pairs shortest path: progettazione, analisi, implementazione e benchmark. (2 ore)

 

7) Performance analysis. Tempo di esecuzione sequenziale e parallelo. Communication overhead. Overhead totale. Speedup ed efficienza. Speedup relativo, reale, assoluto, relae asintotico e relativo asintotico. Cost-normalized speedup. Numero ottimale di processori. Speedup superlineare. Legge di Amdahl-Ware. Legge di  Gustafson-Barsis. Metrica di Karp-Flatt. Legge di Lee (generalizzazione della legge di Amdahl-Ware). Metrica di isoefficienza (Grama, Gupta and Kumar). Funzione di scalabilita’ di Sun e Ni. Cost-optimality (work-efficiency). Cost-optimality ed isoefficienza. Grado di concorrenza ed isoefficienza. Impatto della non cost-optimality di un algoritmo parallelo. Minimum Parallel execution Time. Minimum Cost-Optimal Parallel Execution Time. (7 ore)

 

8) Moltiplicazione matrice-vettore. Algoritmo sequenziale. Rowwise block-striped decomposition. Columnwise block-striped decomposition. Checkerboard block decomposition. implementazione e benchmark. (3 ore)

 
 

9) Classificazione di documenti. Design. Manager-worker paradigm. Comunicazioni nonblocking. (2 ore)

 

10) Moltiplicazione di matrici. Algoritmo sequenziale iterativo row-oriented e ricorsivo block-oriented.  Rowwise block-striped  parallel algorithm. Algoritmo di Cannon. Algoritmo di Fox. Algoritmo DNS (dei tre indiani). (3 ore)

 
Esercitazioni. (21 ore)
 
Testi consigliati:
 

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

 

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

 
Materiale didattico 
 

Il materiale didattico è costituito dai libri di testo consigliati, e dal materiale messo a disposizione degli studenti  frequentanti durante il corso. Tale materiale e' reperibile presso il sito web di riferimento del corso, alla URL 

 
http://sara.unisalento.it/moodle/
 

accedendo al corso "Parallel Algorithms".

 
 
 
CORSO DI LAUREA MAGISTRALE IN MATEMATICA
Data Mining (6 CFU)
II semestre
Obiettivi del corso

Il corso fornisce una moderna introduzione al data mining, un insieme di tecniche, algoritmi e metodologie per scoprire la struttura, patterns e relazioni in insiemi di dati (tipicamente, quelli più grandi) e fare previsioni. Le applicazioni del data mining stanno già accadendo intorno a noi, e se ben fatte, possono a volte anche passare inosservate. Come funziona la ricerca sul web di Google? Come fa Shazam a riconoscere una canzone? Come fa Netflix a raccomandare film a ciascuno dei suoi utenti? I principi del data mining forniscono le risposte di base a queste e ad altre domande simili. Il data mining abbraccia i campi dell’informatica, dello statistical machine learning e dei database. Obiettivo del corso è mettere in grado gli studenti di esplorare, analizzare e sfruttare i dati disponibili al fine di trasformarli in informazioni quantitative e qualitative di valore ed interesse per una azienda, ad esempio ai fini di un processo di decision-making.

Risultati di apprendimento

Dopo aver seguito il corso, lo studente dovrebbe essere in grado di:

 

•        descrivere ed utilizzare le principali tecniche di data mining;

•        comprendere le differenze tra algoritmi diversi che risolvono uno stesso problema e riconoscere quale algoritmo è il migliore rispetto a condizioni diverse;

•        affrontare nuovi problemi di data mining scegliendo i metodi più appropriati e giustificando le proprie scelte;

•        affrontare nuovi problemi di data mining progettando appositi algoritmi e valutando i risultati;

•        spiegare i risultati ottenuti sperimentalmente anche a persone con un background teorico diverso da statistica e/o informatica.

Programma del corso        

Introduzione al corso. Map-Reduce. (2 ore) Mining data streams. Frequent Items. (6 ore)  Frequent Itemsets ed association rules.(4 ore)  Mining similar items e Locality-Sensitive Hashing. (2 ore)  Analisi di grafi. Link analysis e PageRank. (2 ore)  Clustering. (4 ore)  Recommendation systems. (4 ore)  Mining Social-Network Graphs. (4 ore)  Dimensionality reduction. (2 ore)  Classification. (6 ore) Esercitazioni. (6 ore).

Conoscenze preliminari 

Analisi Matematica. Probabilità e statistica. Algebra lineare. Programmazione ed analisi di algoritmi.

Modalità di verifica delle conoscenze acquisite

L’esame è orale. Durante l’esame, allo studente viene chiesto di illustrare argomenti teorici per verificare la sua conoscenza e comprensione degli argomenti scelti. 

Orario di ricevimento

Previo appuntamento da concordare via email o al termine delle lezioni.

Testi consigliati:
Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Disponibile gratuitamente online: http://www.mmds.org

 

Data Mining and Analysis

M. J. Zaki and W. Meira

Disponibile gratuitamente online: http://dataminingbook.info