logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
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 (263) MUSIC AND ACOUSTIC ENGINEERING*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

Obiettivi dell'insegnamento

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.


Risultati di apprendimento attesi

Knowledge and understanding

Students will learn how to:

- develop advanced algorithms by analyzing their complexity and by exploiting randomized approaches,  randomized based data structures, dynamic programming, amortized analysis, competitive analysis, and approximate programming;

- design and analyzed a parallel algorithm by exploiting parallel patterns, tools, and languages for parallel programming.

Applying knowledge and understanding

Given specific problems, students will be able to:

- understand complex problem descriptions;

- design algorithms and analyze their complexity;

- design and implement parallel algorithms;

- profile and fine-tune the performance of complex programs.

- understand where the pitfall and issues may come in (parallel) programming.

Making judgments

Given a relatively complex problem, students will be able to:

- define the relevant data sets required to judge the quality of the proposed solution;

- understand if the obtained performance is in line with the expected complexity;

- understand if the proposed solution scale well or not;

- understand where previous approaches are relevant or not for a given problem.

Communication

Students will learn to:

- present their work discussing pros and cons of the proposed solution.

- present critically the existing state of the art showing where it could be improved or where it is inconsistent; 

Lifelong learning skills

Students will understand how a complex algorithm, possibly parallel, have to be analyzed, designed and assessed. They will play with real problems understanding where pitfall may come when you move from a theoretic formulation down to a real implementation taking into account existing tools and real architectures.


Argomenti trattati

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.


Prerequisiti

Students are required to have some basic knowledge about data structures and computational complexity.


Modalità di valutazione

The final evaluation is based on a written exam.

It is possible to partially skip the written exam with a programming project on the advance algorithm part or on the parallel programming part but not on both.

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

The following text provides a detailed overview of the elements that will be considered in the various assessment activities.

Written exam

Description of the existing solutions. Questions on the design of parallel and non-parallel applications. Numerical exercises assessing the complexity and the performance of complex algorithms possibly parallel. (Dublin descriptor 1,2,3,4,5)

Oral presentation of the programming project (optional)

Assessment of the presentation of the programming project developed as part of course activities developed by students either individually or in groups. (Dublin descriptor 1,2,3,4,5)


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


Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
20:00
30:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

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.5 / 1.6.5
Area Servizi ICT
11/08/2020