Parallel Computing

Lectures:
- Introduction to parallel programming. Concurrency, pseudoparallelism, parallelism. Processes and threads. Extended instruction sets, SIMD instructions.
- Sequential vs. parallel programming. Typical parallel programming problems and their solutions: synchronization and mutual exclusion, deadlock (definition, properties, conditions, detection, elimination).
- Types of parallel platforms. Shared and distributed memory systems. Data and functional parallelism.
- Shared memory systems. The fork-join model and OpenMP. Parallel constructs at different levels of abstraction (promise, future, async, threadpooling, scheduling, load balancing).
- Distributed memory systems. Message Passing and Bulk Synchronous Parallel Models. Posix queues, sockets. MPI interface, basic MPI operations.
- Other options in distributed memory systems: bulk synchronous parallel and partitioned global address space models.
- Easy introduction to accelerator and coprocessor programming. Concept of offloading computations. GPGPU architecture (program organization, memory). Data and functional parallelism on the GPU. CUDA environment and CUDA-C language, support in other languages ​​(OpenMP).
- Methodology of parallel algorithm design. Task/channel model of parallel computing. Foster's design methodology (partitioning, communication, agglomeration, mapping) and its use.
- Design patterns in parallel programming. Finding competition (domain and data decomposition), algorithm structure, and implementation. Solving typical scenarios: independent tasks, replication and reduce, divide and conquer, pipeline.
- Representation and analysis of parallel algorithms (parallel random access machine, bulk synchronous parallel, informal work depth, etc.). Performance and efficiency of parallel algorithms.
- Data structures for parallel algorithms: stack, queue, pool, linked list, hash table, trees, priorities. Main differences from sequential versions. Algorithms for solving selected problems: prefix-sum, merging, search (orthogonal trees, sorting networks). Difference between sequential, naively parallel, and efficient parallel solutions.
- Data structures and algorithms for parallel search. 2-3 tree, pipelining. Parallel search, insertion, and deletion.
- Parallel algorithms and data structures for graph tasks. Graph traversals, shortest path search, connectivity, independent components, etc.

Seminars:
- Solving computationally demanding tasks with and without parallelism. The traveling salesman problem - from a trivially parallel solution (brute-force algorithm) to a solution using IPC (simple parallel version of the branch-and-bound algorithm).
- Data parallelism over big data. Data decomposition, data parallel access, vectorization. Parallel matrix operations and clustering.
- Parallel search.
- Parallel algorithms for graph problems, graphs, and nonlinear data structures. Parallel implementation of the iterative version of the PageRank algorithm.