Multicore Systems

Course guarantor:

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. programming skills (assembler, C/C++ or C#),

2. OS Linux/Windows, networking,

3. BI-EIA, MI-PAP and MI-PAR are advantageous, but not strictly required.

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. Sponsors project assignment.

9.Consultation. The 2nd project checkpoint.

10.Consultation.

11.Consultation.

12.The 2nd project results.

13.The sponsors 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:

https://moodle-vyuka.cvut.cz/course/view.php?id=2024

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master branch Knowledge Engineering, in Czech, 2016-2017 (elective course)
• Master branch Computer Security, in Czech, 2016-2019 (elective course)
• Master branch Computer Systems and Networks, in Czech, 2016-2019 (elective course)
• Master branch Design and Programming of Embedded Systems, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Info. Systems and Management, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Software Engineering, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Web Engineering, in Czech, 2016-2019 (elective course)
• Master program Informatics, unspecified branch, in Czech, version 2016-2019 (elective course)
• Master branch System Programming, spec. System Programming, in Czech, 2016-2019 (elective course)
• Master branch System Programming, spec. Computer Science, in Czech, 2016-2017 (elective course)
• Master specialization Computer Science, in Czech, 2018-2019 (elective course)
• Master branch Knowledge Engineering, in Czech, 2018-2019 (elective course)