Parallel and distributed algorithms

A.Y. 2020/2021
Overall hours
Learning objectives
The aim of the course is introducing the main concepts and methods in parallel and distribuite algorithm design, together with performance evaluation and comparison with sequential algorithms.
Expected learning outcomes
The student should be able to tell parallel from distributed world, apply techniques and methods presented along the course aiming to design efficient parallel and distribuite algorithms. In addition, the student should be able to analyze required computational resources, in order to assess performance and correctness of algorithms.
Course syllabus and organization

Single session

Lesson period
First semester
Didactic methods:
Synchronous lectures (video-lectures) will be carried out using the Zoom platform, with full lecture recording. Lectures will then be made available to allow them to be used asynchronously for students not present in the classroom.
Il programma e il materiale di riferimento compresa la modalità di verifica dell'apprendimento non subiranno variazioni.
The program and the reference material including the learning verification method will not change.
Course syllabus
Parallel and distributed algorithms, motivations. Parallel and distributed architectures vs. von Neumann architecture. Computational resources within different paradigms.
Parallel and distributed architectures:
- Problems in parallel algorithms design: synthesis, analysis, universality
- Shared and distributed memory parallel architectures: communication in both realms
- Shared memory architectures. The PRAM (Parallel RAM) model
- PRAM as a SIMD vs. MIMD architecture
- PRAM models: EREW, CREW, CRCW (common, priority, ... )
- Computational resources: hardware and time complexity
- Comparisons with sequential algorithms: speed-up and efficiency
- Efficient paralle solution on PRAM of some fundamental problems
- Computing iterated binary associative operations. iterated sum: structure and analysis of a parallel solution
- Efficient parallel algorithms for: linear algebra, graph theory, optimization, ...
- Computing prefix iterated binary associative operations. prefix sum
- Structure and analysis of Kogge-Stone's algorithm (pointer doubling)
- Efficient parallel polynomial evaluation. Parallel search algorithms
- Sorting problems (ranking), efficient sequential solutions
- Efficient parallel sorting problems. Batcher's Bitonic sort, structure and analysis
- Eulerian circuit technique in parallel algorithm design
- Distributed memory parallel architectures, interconnection network and performance parameters: degree, diameter and bisection size
- Sorting networks and the 0-1 principle (Knuth)
- Linear arrays of processors, structure, functions and net parameters
- Solving on linear arrays of processors: sorting, max and shuffle
- Odd-even and merge-split sorting, structure and analysis
- Meshes of processors, structures, functions and net parameters
- Computing max on a mesh
- LS3 sorting algorithms, structure and analysis
Distributed architectures and algorithms:
- Distributed architecture modeling
- Entities and communication channels
- Computational resources, time and message complexity
- Structure and analysis of distributed algorithms for fundamental problems
- Broadcasting, lower bounds for distributed solutions
- The flooding algorithm
- Wake-up, the wflooding algorithm
- Traversing, the depth-first algorithm
- Spanning tree, the shout and depth-first algorithm
- Election, computability limitations and elextion by minimum
- Routing, gossiping algorithms
Prerequisites for admission
No prerequisite.
Teaching methods
Lectures and advanced seminars.
The frequency of the course is strongly recommended.
Teaching Resources
For Parallel algorithms there are a book note that can be download directly from the web site of the course Parallel and Distributed Algorithms.
For Distributed algorithms students are invited to follow the book: N. Santoro.
Design and Analysis of Distributed Algorithms. Wiley-Interscience, 2006.
Assessment methods and Criteria
The exam consists of a written paper of about three questions / exercises covering the topics of the course. The questions consist of: formal definitions, statements of theorems and algorithms of constructions/proofs. The exercises verify the understanding of the subject. The mark is expressed in thirtieths.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Educational website(s)
by appointment
Via Celoria, 18 - Room: 4011