81668 - ALGORITMI PARALLELI

Learning outcomes

Knowing the main parallel computational models. Understanding and using the main methodologies for designing and analyzing efficient parallel, concurrent, and distributed algorithms.

Course contents

Parallel algorithms for bounded degree networks. Synchronous systems. Parallel computation thesis. Interconnection networks: mesh, hypercube, shuffle, butterfly, CCC. Prefix sums. Batcher's bitonic mergesort. Matrix moltiplication. Fast Fourier Transform. VLSI and reconfigurable mesh models. Concurrent algorithms. Concurrency, critical sections, mutual exclusion, synchronization primitives, deadlock. Distribuited algorithms. Computer networks Messages. Topologies: ring, star, tree, graph. Mutual exclusione in complete graphs. Leader election in rings. Gallager-Humblet-Spira's minimum spanning tree algorithm.

Readings/Bibliography

A.A. Bertossi, Algoritmi Paralleli: Sincroni, Concorrenti, Distribuiti. Pitagora Editrice, Bologna, 2009.

Teaching methods

The course is taught during the first semester, and it comprises lessons and lectures. First, theoretical foundations are presented. After base notions are introduced, the main parallel computer models and some basic computational problems are presented. Algorithms for solving such problems are designed, pointing out the design techniques and related performance depending on the parallel model used.

Assessment methods

The assessment consists in a final written examination, lasting 3 hours, during which no books, notes, calculatora and electronic devices are allowed. The written exam consists of 4 questions, some of which are exercises whose purpose is to check the practical ability to design parallel algorithms to solve computational problems, while others are open-answer questions whose objective is to verify that the expected theoretical knowledge has been acquired.

Teaching tools

Projector.

Office hours

See the website of Alan Albert Bertossi