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.
Lesson period: First semester
(In case of multiple editions, please check the period, as it may vary)
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
Lectures and advanced seminars. The frequency of the course is strongly recommended.
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 in a presentation or a seminar on advanced topics agreed between teacher and student. During the seminar teacher will allow to appreciate the basic knowledge acquired in the course. The mark is expressed in thirtieths.