- Docente: Alan Albert Bertossi
- Credits: 6
- SSD: INF/01
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Computer Science (cod. 8028)
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