logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 095946 - ADVANCED ALGORITHMS AND PARALLEL PROGRAMMING
Docente Ferrandi Fabrizio
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (434) INGEGNERIA INFORMATICA* AZZZZ095946 - ADVANCED ALGORITHMS AND PARALLEL PROGRAMMING
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA* AZZZZ095946 - ADVANCED ALGORITHMS AND PARALLEL PROGRAMMING

Programma dettagliato e risultati di apprendimento attesi

This course deals with advanced topics in algorithm design and parallel programming.

The course is structured in two parts. The first part focuses on general methods and algorithms that are not usually covered by the course “Algoritmi e Principi dell’Informatica”, such as, randomization, amortization, approximation algorithms, string searching/matching, etc.

The second part deals with parallel programming: Automatic vs. Manual Parallelization, Parallelizing Compilers, Parallel Patterns, Partitioning (domain vs functional decomposition), Communication (cost, latency, bandwidth, visibility, synchronization, etc.), Data Dependencies and Tools/languages such as OpenMP, MPI and CUDA.

Detailed program:

Part I

Course Objectives and Introduction

Randomized algorithms: Las Vegas and Monte Carlo algorithms. Analyzing Randomized algorithms.

Hiring Problem and Generating Random Permutations.

Randomized Quicksort. Worst-case analysis. Average-case analysis.

Order Statistics, Randomized divide-and-conquer algorithm.

Primality test. Fast exponentiation. Secret key and cryptosystems.

Karger’s Min-Cut Algorithm. Faster version by Karger and Stein.

Randomized data structures: Skip Lists, Treaps.

Dynamic Programming: Memoization. Examples of Dynamic Programming: String Matching, BDDs, etc.

Amortized Analysis: Dynamic tables, Aggregate method, Accounting method and Potential method.

Approximate programming.

Competitive Analysis Self-organizing lists Move-to-front heuristic.

Part II

Design of Parallel Algorithms - Parallel Algorithms and Parallel Programming.

Introducing parallel patterns: Reduce, Split, Compact / Expand and Parallel Prefix Sum.

More on parallel patterns: Segmented Scan, Sort, Mapreduce, Kernel Fusion.

Tools and languages for parallel programming: Posix Threads, OpenMP, Message Passing Interface, CUDA.

Comparison of Parallel Programing Technologies.

Optimizing parallel performance.

A library for parallel programming: Thrust.

An introduction to parallel graph computation.

Examples of Parallel Algorithms.


Note Sulla Modalità di valutazione

Final evaluation is based on a written exam.

It is possible to integrate or to skip the written exam with either a programming project or a report on further readings.

The written exam is individual while the projects may be assigned up to two people.


Bibliografia
Risorsa bibliografica facoltativaT. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Editore: MIT Press, Cambridge; 3rd edition, Anno edizione: 2009, ISBN: 978-0262533058
Risorsa bibliografica facoltativaRajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Editore: Cambridge University Press, Anno edizione: 1995, ISBN: 978-0521474658
Risorsa bibliografica facoltativaPeter Pacheco, An Introduction to Parallel Programming, Editore: Publisher: Morgan Kaufmann; 1 edition, Anno edizione: 2011, ISBN: 978-0123742605
Risorsa bibliografica facoltativaDavid B. Kirk, Wen-mei W. Hwu, Programming Massively Parallel Processors: A Hands-on Approach, Editore: Morgan Kaufmann, Anno edizione: 2010 978-0123814722
Risorsa bibliografica facoltativaparallel programming online material https://computing.llnl.gov/tutorials/parallel_comp/ http://code.google.com/p/stanford-cs193g-sp2010/
Risorsa bibliografica facoltativaAdditional material is available on the Beep platform of Politecnico di Milano https://beep.metid.polimi.it
Note:

access restricted to course participants


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
30.0
esercitazione
20.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
19/11/2019