|
This course deals with advanced topics in algorithm design and parallel programming.
The course is structured in two parts. The first part focuses on general methods and algorithms that are not usually covered by the course “Algoritmi e Principi dell’Informatica”, such as, randomization, amortization, approximation algorithms, string searching/matching, etc.
The second part deals with parallel programming: Automatic vs. Manual Parallelization, Parallelizing Compilers, Parallel Patterns, Partitioning (domain vs functional decomposition), Communication (cost, latency, bandwidth, visibility, synchronization, etc.), Data Dependencies and Tools/languages such as OpenMP, MPI and CUDA.
Detailed program:
Part I
Course Objectives and Introduction
Randomized algorithms: Las Vegas and Monte Carlo algorithms. Analyzing Randomized algorithms.
Hiring Problem and Generating Random Permutations.
Randomized Quicksort. Worst-case analysis. Average-case analysis.
Order Statistics, Randomized divide-and-conquer algorithm.
Primality test. Fast exponentiation. Secret key and cryptosystems.
Karger’s Min-Cut Algorithm. Faster version by Karger and Stein.
Randomized data structures: Skip Lists, Treaps.
Dynamic Programming: Memoization. Examples of Dynamic Programming: String Matching, BDDs, etc.
Amortized Analysis: Dynamic tables, Aggregate method, Accounting method and Potential method.
Approximate programming.
Competitive Analysis Self-organizing lists Move-to-front heuristic.
Part II
Design of Parallel Algorithms - Parallel Algorithms and Parallel Programming.
Introducing parallel patterns: Reduce, Split, Compact / Expand and Parallel Prefix Sum.
More on parallel patterns: Segmented Scan, Sort, Mapreduce, Kernel Fusion.
Tools and languages for parallel programming: Posix Threads, OpenMP, Message Passing Interface, CUDA.
Comparison of Parallel Programing Technologies.
Optimizing parallel performance.
A library for parallel programming: Thrust.
An introduction to parallel graph computation.
Examples of Parallel Algorithms.
|
Inglese