Parallel programming with C++

Не зважаючи на швидкий ріст потужності комп’ютерів, задач, де стане в пригоді кожен такт процесора та кожен байт пам’яті стає більше. В наукових та інженерних обчислення, в AI та ML, в роботі із великим даними, потужності завжди мало. Не менш важливими є системи, де ресурси доводиться економити – мережі IoT, смартфони, та й загальне енергоспоживання датацентрів привертає увагу. Крім того, останні десятиліття потужність зростає завдяки масовому впровадженню паралельних обчислювачів – багатоядерних процесорів із величезними SIMD регістрами та своєрідних, глибоко паралельних, GPU – без CUDA чи OpenCL зараз важко уявити собі високопродуктивну систему. Щоб максимально ефективно використати наявні обчислювальні ресурси, потрібно розуміти, як влаштовані обчислювачі. Рівні абстракції дуже корисна річ, але всі абстракції протікають. Розуміння достатньо, щоб не робити відверто неефективних речей, програмуючи будь-якою мовою. Однак, значно більшого можна досягнути, отримавши безпосередній контроль над використанням ресурсів. В цьому сенсі, С++ – унікальна мова. Сучасний С++ дозволяє, з одного боку, писати високорівневий код, близький за простотою та виразністю до Python, однак, із малою платою за абстракції – не більшою, ніж в коді на С чи FORTRAN, з іншого – самим обирати,  наскільки заглиблюватися в подробиці, аж по врахування найдрібніших особливостей апаратної архітектури. Ще однією перевагою цієї мови є багатопарадигмовість. Є бажання «писати як на FORTRAN»? Без проблем. Надаєте перевагу ООП, функціональному стилю, узагальненому програмуванню, метапрограмуванню? Відповідні інструменти до ваших послуг. Зворотною стороною як потужності паралельних систем, так і гнучкості С++, є велика складність в освоєнні. Загадковий сленг, безліч можливих підходів, багато поганих книжок, пастки на кожному кроці. Все це робить вивчення та ефективне використання і паралельного програмування і С++ складним.   На цьому курсі ми будемо вчитися справлятися з цією складністю та  максимально використовувати наявні ресурси із мінімальними необхідними затратами сил та часу.

Теоретичні теми

1. Абстракції комп’ютерної системи: центральний процесор та сопроцесори, ієрархія пам’яті, засоби вводу-виводу
2. Представлення елементарних даних в пам’яті, відповідні типи даних С++ та інших мов програмування. Особливості роботи із машинними числами з рухомою комою.
3. Абстракції операційної системи: процеси та потоки; віртуалізація, особливості вводу-виводу.
4. Ієрархічна організація комп’ютерних систем. Роздільна компіляція, зв’язування (linking). Особливість С та С++ — невизначена поведінка як наслідок простору для оптимізації. Динамічні та статичні бібліотеки, раннє та пізнє зв’язування.
5. Модель машини та модель пам’яті С, адресний простір процесу в сучасних операційних системах. Поняття про ABI, угоди про виклики. Особливості ABI C++. Огляд системи команд (ISA) x86. Огляд інших підходів до ISA.
6. Мікроархітектура. Підсистема пам’яті: принципи та функціонування кешу, віртуальна пам’ять та TLB. Конвеєр процесора. Перевпорядкування та спекулятивне виконання команд.
7. Види паралелізму та класифікація Флінна. Оцінювання ефекту від застосування паралелізації. Закон Амдала та закон Густафсона.
8. Мультипроцесори: SMP, SMT. Когерентність кешів, моделі узгодженості пам’яті. UMA та NUMA-системи.
9. Паралельне та конкурентне програмування систем із спільною пам’яттю (shared memory systems). Стан гонитви, гонитви даних. Засоби синхронізації. Потокобезпечні та lock-free структури даних. Deadlock i Livelock. Executor-и та пули потоків. Асинхронні засоби, співпрограми, модель N:M.
10. Стандартні API C++, Python, Java . Важливі сторонні бібліотеки: TBB, Folly, Boost, Qt.
11. Створення паралельних програм. Методологія PCAM.
12. Засоби перевірки коректності програм: valgrind, concurrency visualizer, Intel parallel studio, санітайзери, статичні аналізатори – PVS-Studio та інші. Профайлери: Intel VTune, perf.

Практичні теми

 

Суть завдання	Призначення завдання
Робота із компілятором із командного рядка. Використання систем автоматичної побудови програм.	Знайомство із роздільною компіляцією, оптимізаціями компілятора та динамічним зв’язуванням.
Низькорівневе маніпулювання пам’яттю.	Навчання ручному керуванню ресурсами, такими як пам’ять чи відкриті файли. Практика використання RAII. Розуміння наслідків моделі пам’яті, що використовується сучасними комп’ютерами.
Використання сучасного С++: шаблонів, лямбда-функцій, auto і т.д. і т.п.	Вміння програмувати на С++ як на С++, а не як на ALGOR/Java/C/Go тощо. Практика використання функціонального та узагальненого програмування.
Знайомство із стандартною бібліотекою С++.	Боротьба із «велосипедобудуванням». Практика у виборі та комбінуванні засобів STL, вводу-виводу та інших частин стандартної бібліотеки.
Багатопоточне програмування.	Вивчення підходів до створення простих паралельних програм для багатопроцесорних (багатоядерних) систем – SMP-мультипроцесорів. Знайомство із синхронізацією. Практика у вимірюванні продуктивності.
Конвеєрна обробка, Map-Reduce	Знайомство із підходами до максимізації паралельності.
Побудова потокобезпечних структур даних.	Розуміння, як ці структури даних організовані та із якими обмеженнями стикають, допоможе їх правильно та ефективно використовувати.
Побудова розподілених систем із використанням MPI, Boost::MPI, Boost::asio.	Знайомство із програмуванням для систем із багатьох комп’ютерів – такі системи масштабуються помітно краще за SMP.

Вимоги до попередніх знань учасників курсу

Мінімальні вимоги: вміння  вільно програмувати будь якою мовою, знайомство із синтаксисом хоча б одної із мов: C, C++, Java, C#. Бажані: володіння базовим синтаксисом С++. Знайомство із об’єктно-орієнтованим програмуванням.