Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING

*

A

ZZZZ

095946 - ADVANCED ALGORITHMS AND PARALLEL PROGRAMMING

Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA

*

A

ZZZZ

095946 - 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 (map, reduce, scan, etc.), Partitioning (domain vs. functional decomposition), Communication (cost, latency, bandwidth, visibility, synchronization, etc.), Data Dependencies and Tools/languages such as OpenMP and MPI.

An innovative teaching activity (1 CFU), Blended Learning & Flipped Classroom, is planned for some of the topics covered by the course.

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 analyze 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 scales well or not;

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

Communication

Students will learn to:

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

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

Lifelong learning skills

Students will understand how a complex algorithm, possibly parallel, has to be analyzed, designed, and assessed.

They will play with real problems, understanding where pitfalls may come when you move from a theoretical formulation down to an actual implementation considering existing tools and 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.

Building a faster and better parallel program greatly impacts power consumption reduction. Improving application program efficiency and minimizing the energy intensity by choosing the right technology will affect energy consumption and carbon emissions.

Prerequisiti

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

Modalità di valutazione

The assessment of the students is organized according to the schedule provided by the School's Academic Calendar.

The evaluation is based on a written exam focused on:

- The solution of some problems based on the practical application of the course concepts and techniques;

- Open answers to some questions on the course concepts and techniques.

After each written test, the teacher can complement the assessment procedure with an oral examination.

Continuous assessment will be implemented through two intermediate tests: one as a mid-term test and one at the end of the semester. All students are admitted to the second test, regardless of the outcome of the first one. The achieved results will be valid till the end of the academic year or till a student ask to repeat the given part. Each intermediate test contributed to the final grade with 16 points. The exam is considered passed if, in both parts, the students get a grade not less than 7, and the sum of the two grades is greater or equal to 18. 30 cum laude is assigned if students get a sum of grades greater than 30.

If either the first or the second test has a grade less than 7 or the total is less than 18, the student has to take the written test on one of the following dates according to the schedule provided by the School's Academic Calendar. The student may use one of the valid partial results on the next exam dates. In this case, a customized written exam version will be provided to the student for the parts not yet valid.

Participation in innovative-learning classroom activities will be assessed and will contribute to the final evaluation grade. In particular, in case of valid grades, some questions of the written exam could be skipped.

Bibliografia

T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Editore: MIT Press, Cambridge; 3rd edition, Anno edizione: 2009, ISBN: 978-0262533058
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Editore: Cambridge University Press, Anno edizione: 1995, ISBN: 978-0521474658
Michael McCool, James Reinders, Arch Robison, Structured Parallel Programming: Patterns for Efficient Computation, Editore: Morgan Kaufmann, Anno edizione: 2012, ISBN: 0124159931 http://parallelbook.com/Peter Pacheco, An Introduction to Parallel Programming, Editore: Publisher: Morgan Kaufmann; 1 edition, Anno edizione: 2011, ISBN: 978-0123742605
parallel programming online materialhttps://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorialAdditional material is available on the WeBeep platform of Politecnico di Milano https://webeep.polimi.it/login/index.php Note:

access restricted to course participants

Software utilizzato

Nessun software richiesto

Forme didattiche

Tipo Forma Didattica

Ore di attività svolte in aula

(hh:mm)

Ore di studio autonome

(hh:mm)

Lezione

25:00

37:30

Esercitazione

20:00

30:00

Laboratorio Informatico

0:00

0:00

Laboratorio Sperimentale

0:00

0:00

Laboratorio Di Progetto

5:00

7:30

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