PA

Parallel Algorithms

This curricular unit aims to develop skills in the analysis and design of algorithms with a high degree of parallelism, namely:

Characterize the basic parallelism patterns.
Analyze the complexity of parallel algorithms in various types of computing systems.
Design efficient parallel algorithms for scientific computing suitable for each architecture.
Identify the underlying parallel algorithms in scientific applications.

Complexity analysis of parallel algorithms
Basic parallelism patterns (map, reduce and scan) and their efficient implementation on various high-performance platforms (Clusters, GPUs)
Typical parallelism patterns: pipeline, farm, hearbeat and divide&conquer.
Analysis of existing parallel algorithms: sorting, operations on dense and sparse matrices, iterative solutions of systems of linear equations, N-body and graph algorithms (MST).
Generation of pseudo-random numbers and memory allocation.
Lock-free parallel algorithms.

Parallel Scientific Computation: A Structured Approach Using BSP, Rob H. Bisseling, Oxford University Press, 2020.
Structured Parallel Programming, Michael McCool, Arch Robison & James Reinders, 2012
Parallel Computing Architectures and APIs, Vivek Kale, Chapman and Hall/CRC, 2019
Programming Massively Parallel Processors, A Hands-on Approach, 3rd Ed., David Kirk & Wen-mei Hwu, Morgan Kaufmann, 2016