Multicore Systems

Lecturer:

Tutor:

Supervisor:

Department of Computer Systems

Synopsis:

Students understand architecture of systems based on multicore processors with multiple threads per core, structure and usage of cache hierarchy with shared last level. They learn parallel algorithm classification, parallel programming technics, simulation and monitoring tools for measurement and optimization of parallel algorithms. After this course, students can design MTMD programs (Multiple Threads Multiple Data), measure and analyze latency and throughput of parallel algorithms and optimize them for contemporary multicore systems.

Requirements:

-1. project ? rating of 20 points

-2. project ? rating of 60 points 60 bodů

-conclusion test ? rating of 20 points

Syllabus of lectures:

1.Multiprocessor systems, multicore processors, multithreaded processor cores. Hierarchy of caches in multicore processor, cache coherency protocols.

2.Synchronization primitives and data consistency in multiprocessor systems, memory models.

3.Parallel programming patterns for MTMD model, parallel data structures and algorithms and their behavior and optimization on multicore systems with multiple cache layers (cache conscious programming).

4.Methods of parallel algorithms measurement and optimization.

5.Parallel methods properties: deadlock-free, starvation-free, lock-free, wait-free.

6.Operating system impact on parallel program performance and its elimination. Critical path and its optimization.

Syllabus of tutorials:

1.Tutorial: Measurement of Intel cache hierarchy base properties.

2.Tutorial: Simulation of simple parallel algorithms.

3.Project assignment: measurement, simulation, evaluation and optimization of parallel algorithms.

4.Consultation.

5.Consultation. The 1st project checkpoint.

6.Consultation.

7.The 1st project results.

8.Consultation.

9.Consultation. The 2nd project checkpoint.

10.Consultation.

11.Consultation.

12.Final test. The 2nd project results.

13.The 2nd project results.

Study Objective:

Study materials:

1.Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming.

2.Rauber, Thomas and Rünger, Gudula: Parallel Programming Models, Springer, 2010

3.David A. Patterson, John L. Hennessy: Computer Organization and Design: The Hardware/Software Interface, Fourth Edition

4.Ricardo Bianchini, Enrique V. Carrera and Leonidas Kontothanassis: Evaluating the Effect of Coherence Protocols on the Performance of Parallel Programming Constructs, 1998

5.Ricardo Bianchini, Leonidas Kontothanassis: Algorithms for Categorizing Multiprocessor Communication Under Invalidate and Update-Based Coherence Protocols, 1995

6.Bryan R. Buck,Jeffrey K. Hollingsworth: Using Hardware Performance Monitors to Isolate Memory Bottlenecks, 2000

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: