2h: Introduction to the course, structure of the lessons, hardware evolution and the urgency of parallel/distributed computing dictated by parallel hw (multicore CPUs, GPUs, clusters).
Assignment: look at top500.org and green500.org and try to figure out evolution of parallel machines through the “statistics” graphs in the lists.
2h: Examples of parallel execution of different kind of real life tasks:
translating a book
counting the euros in pockets of people in a room
assembling an object out of pieces p1, …, pn to be assembled in order
How the tasks may be executed by a single person and by number of cooperating persons.
Different way of executing tasks in parallel.
Effect of “slow” persons recruited to execute a task.
Figuring out general principles out of this: patterns, mechanisms, overheads, …
Assignment (1): single Jacobi iteration (as in the blackboard PDF). Create randomly generated matrix A and vectors B and X and run a single iteration of the Jacobi method verifying that the code is properly vectorized and measuring the increase in speed due to vectorization (optimization of the sequential code in general)
Assignment (2): consider a large matrix (4-8K rows/columns at least) and measure the improvement w.r.t. non optimized sequential computation of a single Jacobi iteration
when only vectorization is used
when the problem is parallelized using C++11 threads (only)
when you use threads (coarse grain parallelisation) and vectorization (fine grain parallelisation)
2h: Introduction to parallel patterns/skeletons
using OpenMP to implement parallel for (example of simple data parallel pattern) (Summary of 4.0, Old Tutorial slides). OpenMP is available in g++ and in icc by specifying the flag -fopenmp.
using GrPPI as high level programming model for skeletons (needs c++14)
implement a divide and conquer computation using c++ threads. The computation should look for a word in a text. Recursively divide the text up to the point you either get something of the a given length (parameter), and in this case you look for the string sequentially. Return an integer value counting the occurrences of the string. (sub assignment: consider programming the solution in such a way the code for the divide and conquer strategy may be used to program another divide and conquer application)
data parallel patterns (map, reduce, google map reduce, stencil, stencil-reduce)
implementation of pattern frameworks (supporting composition)
try to write a FF pipeline (with core patterns) that implements the Sieve of Eratostene: one stage emits the stream of integers and stage i filters out all the numbers multiple of i. The last stage prints the results. Try generating 20 integers and using k<20 filter stages.
by David Del Rio Astorga: 1h
Introduction to GrPPI (slides sent as PDF to the course mailing list).
methodology to develop parallel code with structured programming