Parallel and Distributed Computing

From Computer Engineering Faculty

The development of this course has been initiated and supported by Intel's Multi-Core Curriculum Initiative. For details please visit http://www.intel.com/cd/software/university/asmo-na/eng/index.htm.

Lecturer: Volodymyr Obrizan (obrizan@kture.kharkov.ua).

Contents 1 Lectures 2 Labs 3 Schedule 4 Exam Questions 5 References 5.1 Synopsis 5.2 Books 5.3 Links 5.4 Video 5.5 MIT Open CourseWare

Lectures

1. Introduction, history, motivation. Download slides.
2. Basics of Parallel and Distributed Computers Architectures. Download slides.
3. Basics of Parallel Programming. Download slides.
4. Parallel Programming using OpenMP Library. Download slides.
5. Performance Analysis. Download slides.
6. Performance Analysis (cont.)
7. Windows Threads. Download slides.
8. Windows Threads (cont.)
9. Parallel Programming with MPI. Lecture notes on the site of University of Nizhny Novgorod: Go to the course.
10. Parallel Programming with MPI (cont.)
11. Parallel Methods for Matrix-Vector Multiplication. Lecture notes on the site of University of Nizhny Novgorod: Go to the course.
12. Parallel Methods for Matrix Multiplication. Lecture notes on the site of University of Nizhny Novgorod: Go to the course.
13. Introduction to Intel Threading Building Blocks Library. Download slides.
14. Introduction to Intel Threading Building Blocks Library (cont.)
15. Advanced Algorithms of Intel TBB. Download slides.
16. Advanced Algorithms of Intel TBB (cont.)
17. Intel TBB: Parallel Containers, Allocators, Synchronization.

Labs

Download source files.

1. Introduction to Intel VTune Performance Analyzer, Thread Checker, Thread Profiler, OpenMP. Download student manual.
2. Parallel programming using Windows Threads. Download student manual.
3. Distributed programming using MPI library. Download student manual.
4. Parallel programming using Intel Threading Building Block Library.

Schedule

The schedule is available on the University's web-site. Please look for the P&DC classes.

Exam Questions

1. Motivation for concurrency in software.
2. Parallel computing platforms.
3. Understanding performance. Amdahl’s Law. Speed-up. Efficiency. Scalability.
4. Task decomposition model. Real life and software examples.
5. Data decomposition model. Real life and software examples.
6. Data flow decomposition model (pipeline). Real life and software examples.
7. Basic parallel programming constructs.
8. Programming using Windows Threads.
9. Basic Windows API functions for multithreading.
10. OpenMP library. Motivation, application, benefits.
11. Basic OpenMP pragmas for parallel programming.
12. Reduction operations in OpenMP. Motivation, solution, examples.
13. Load balancing in OpenMP. Problem definition, pragmas, static and dynamic balancing.
14. Parallel programming errors: data races, deadlocks. How to identify. How to fix.
15. Performance problems: too many threads, excessive locking. How to identify. How to fix.
16. Intel VTune Performance Analyzer: sampling wizard.
17. Intel VTune Performance Analyzer: call-graph wizard.
18. Intel Thread Checker.
19. Intel Thread Profiler.
20. MPI: Basic concepts and definitions.
21. MPI: Basic point-to-point operations.
22. MPI: Basic collective operations.
23. Intel Threading Building Blocks library. Motivation, structure of the library.
24. Blocked_range class of Intel TBB.
25. Basic algorithm of Intel TBB: parallel_for.
26. Basic algorithm of Intel TBB: parallel_reduce.
27. Advanced algorithms of Intel TBB: parallel_while.
28. Advanced algorithms of Intel TBB: pipeline.
29. Concurrent containers of Intel TBB.
30. Comparison of three approaches: Windows Threads, OpenMP, Intel TBB. Advantages and disadvantages.

References

Synopsis

• http://www.software.unn.ac.ru/ccam/?doc=107 — Very good synopsis developed by University of Nizhny Novgorod, Russia.
• http://software.intel.com/en-us/articles/courseware-access/ — Parallel Programming Courseware.

Books

1. Multi-Core Programming, by Shameem Akhter and Jason Roberts. Copyright 2006 Intel Press. P. 336.
2. Intel Threading Building Blocks, by James Reinders. Copyright 2007 James Reinders, 978-0-596-51480-8. P.303.
3. Patterns for Parallel Programming, by Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill. Copyright 2005 by Pearson Education, Inc. P. 355.
4. Parallel Programming, by Barry Wiklinson and Michael Allen. Copyright 1999 by Pearson Education, Inc. P. 431.

Links

• http://www.intel.com/multi-core/ — Intel's Multi-Core technologies web-site.
• http://software.intel.com/ — Intel Sotware Network.
• http://www.threadingbuildingblocks.org — Intel Threading Building Blocks: sources download, news, examples, forum.
• http://intel.com/software/products/tbb — TBB on the Intel's web-site
• http://en.wikipedia.org/wiki/Intel_Threading_Building_Blocks — TBB on Wikipedia. Lots of useful links to academic papers.
• http://software.intel.com/en-us/articles/multi-threading-in-the-net-environment/ — multithreaded programming using .NET environment.

Video

• Multi-Core Curriculum for Academia

MIT Open CourseWare

Massachusetts Institute of Technology provides open courses on parallel and distributed programming:

• 18.337J / 6.338J Applied Parallel Computing (SMA 5505)
• 6.827 Multithreaded Parallelism: Languages and Compilers
• 6.895 Theory of Parallel Systems (SMA 5509)
• 6.896 Theory of Parallel Hardware (SMA 5511)
• 6.189 Multicore Programming Primer