Методи та технології розподілених та паралельних обчислень

Анотація навчальної дисципліни

Мета вивчення дисципліни 
Формування комплексу знань, вмінь в галузі використання паралельних обчислювальних систем для вирішення складних прикладних задач, оволодіння концепціями сучасного програмування в рамках парадигм паралельного та розподіленого програмування.

Практичне значення та використання отриманих знань 
Вивчення основних термінів і понять, математичного апарата й моделей паралельних обчислень; опанування теоретичних і практичних основ виявлення паралелізму, розпаралелювання алгоритмів, перетворення послідовних програм у паралельні, організації паралельних обчислювальних процесів; здатність використовувати сучасні методи і мови програмування для оволодіння концепціями паралельних та розподілених обчислень; вивчення методів і язикових механізмів конструювання паралельних програм; 
вивчення паралельних чисельних алгоритмів для рішення типових завдань обчислювальної математики; здатність створювати програмне забезпечення для паралельних та розподілених обчислень.

Основні результати навчання
ПРН02 Оцінювати і вибирати ефективні методи і моделі розроблення, впровадження, супроводу програмного забезпечення та управління відповідними процесами на всіх етапах життєвого циклу.
ПРН03 Будувати і досліджувати моделі інформаційних процесів у прикладній області.
ПРН06 Розробляти і оцінювати стратегії проєктування програмних засобів; обґрунтовувати, аналізувати і оцінювати варіанти проєктних рішень з точки зору якості кінцевого програмного продукту, ресурсних обмежень та інших факторів.
ПРН07Аналізувати, оцінювати і застосовувати на системному рівні сучасні програмні та апаратні платформи для розв’язання складних задач інженерії програмного забезпечення.
ПРН08 Розробляти і модифікувати архітектуру програмного забезпечення для реалізації вимог замовника.
ПРН09 Обґрунтовано вибирати парадигми і мови програмування для розроблення програмного забезпечення; застосовувати на практиці сучасні засоби розроблення програмного забезпечення.
ПРН10 Модифікувати існуючі та розробляти нові алгоритмічні рішення детального проєктування програмного забезпечення.
ПРН13 Конфігурувати програмне забезпечення, керувати його змінами та розробленням програмної документації на всіх етапах життєвого циклу.
ПРН15 Здійснювати реінжиніринг програмного забезпечення відповідно до вимог замовника..

Тематика та види навчальних занять
1 тиждень
Лекція 1. Послідовні та паралельні обчислення. Поняття про паралельні обчислення. Стимули розвитку паралельних обчислень. Загальна термінологія паралельних обчислень. Класифікація багатопроцесорних систем за організацією доступу до пам'яті. Ступінь паралелізму алгоритму. Напрямки, де необхідна паралелізація
Лабораторне заняття1. Характеристики систем функціональних пристроїв.

2 тиждень
Лекція 2. Моделі паралельного програмування. Рівні розпаралелювання. Паралельні операції. Паралелізм даних. Паралелізм задач. Різновиди паралелізму.
Практичне заняття1. Способи обробки даних в обчислювальних системах.

3 тиждень
Лекція 3. Види паралелізму в архітектурі комп’ютера. Способи паралельної обробки. Поняття паралельної, векторної та конвеєрної обробки даних.    
Лабораторне заняття 2. Ефективність паралельної системи. 

4 тиждень
Лекція 4. Класифікація паралельних комп’ютерів і систем. Класифікація Флінна. MISD,MIMD,SISD,SIMD – архітектури. Класифікація Хокні.  
Практичне заняття 2. Основні характеристики OpenMP. 

5 тиждень
Лекція 5. Класифікація Фенга, Скілікорна, Хендлера, Джонсона, Базу, Крішнамарфі, Дункана.
Лабораторне заняття 3. Граф алгоритму та концепції паралелізму. 

6 тиждень
Лекція 6. Продуктивність паралельних алгоритмів. Балансування навантаження. Характеристики продуктивності паралельних алгоритмів. Метрики паралельних обчислень
Практичне заняття 3. Потокова модель Java.

7 тиждень
Лекція 7. Етапи розробки паралельного алгоритму. Формальна модель прискорення алгоритму. Закон Амдала.
Лабораторне заняття 4. Написання програми з використанням технології OpenMP.

8 тиждень
Лекція 8. Основи паралельного програмування. Основні поняття паралельного програмування. Нотація паралельних операторів та процесів. Парадигми паралельного програмування..
Практичне заняття 4. Отримання/передача повідомлень між окремими процесами (MPI).
Модульна контрольна робота 1. 

9 тиждень
Лекція 9. Паралельне програмування з застосуванням інтерфейсу передачі повідомлень MPI. Загальні функції MPI. 
Лабораторне заняття 5. Паралельні обчислення з використанням багатопотокового програмування.

10 тиждень
Лекція 10. Колективні взаємодії процесів. Групи та комунікатори в MPI.. Віртуальні топології, комунікатори й області зв'язку.  Функції пристроїв керування трафіком.
Практичне заняття 5. Отримання/передача повідомлень між окремими процесами (продовження)

11 тиждень
Лекція 11. Моделювання систем за допомогою мереж Петрі.
Лабораторне заняття 6. Обчислення числа π.

12 тиждень
Лекція 12. Структурний аналіз мереж Петрі. Граф покриваючих маркувань.
Практичне заняття 6. Найпростіші паралельні алгоритми.

13 тиждень
Лекція 13. Поняття розподілених обчислень та розподіленої системи. Основні причини зростання значимості розподілених систем. Вимоги до розподілених систем.
Лабораторне заняття 7. Множення двох матриць на основі топології «кільце».

14 тиждень
Лекція 14. Взаємодія в розподілених системах. Фізичний та логічний час. Синхронні та асинхронні розподілені системи. Упорядкування подій. Скалярний час Лемпорта.
Практичне заняття 7. Моделювання системи з використанням мереж Петрі.
Модульна контрольна робота 2.

15 тиждень.  
Лекція 15. Взаємодія в розподілених системах (продовження). Примітиви взаємодії. Синхронний та асинхронний обмін повідомленнями. Складнощі розробки розподілених систем.
Лабораторне заняття 8. Аналіз властивостей мереж за допомогою дерева покриваючих маркувань.

Самостійна робота складає 120 годин. Самостійна робота здобувача відбувається впродовж семестру та складається з підготовки до аудиторних занять, контрольних заходів, участь у дискусіях,виконання індивідуальних завдань. 

Консультації: здійснюються викладачем впродовж семестру згідно розкладу. 

Оцінювання результатів навчання

Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.
Модуль 1
Повне виконання контрольного завдання – максимально 5 балів.
Оцінка за виконання лабораторних робіт – максимально 20 балів за модуль.
Модульна контрольна робота – бездоганне виконання 25  балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання).
Модуль 2
Повне виконання контрольного завдання – максимально 5 балів.
Оцінка за виконання лабораторних робіт – максимально 20 балів за модуль.
Модульна контрольна робота – бездоганне виконання 25  балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання).

Посилання на рекомендовані джерела
1. Коцовський В. М. Теорія паралельних обчислень: навчальний посібник. Ужгород: ПП «АУТДОР-Шарк», 2021. 188 с.
2. Кузьма К.Т., Мельник О.В.  Паралельні та розподілені обчислення: навчальний посібник для вищих закладів освіти. – Миколаїв: ФОП Швець В.М., 2020. – 172 c.
3. Минайленко Р.М. Паралельні та розподілені обчислення: навч. посіб. ― Кропивницький: Видавець Лисенко В. Ф., 2021. ― 153 с.
4. Семеренко, В. П. Технології паралельних обчислень : навчальний. – Вінниця : ВНТУ, 2018. – 104 с.
5. OpenMP. Application Programming Interface Version 5.2 November 2021. URL: https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5-2.pdf

Методична література
1. Зіноватна, С.Л. Конспект лекцій з дисципліни «Методи та технології розподілених та паралельних обчислень» для студентів спеціальності 121 – Інженерія програмного забезпечення, – Одеса: 2022. - 70 с. 
2. Зіноватна, С.Л. Методичні вказівки до лабораторних робіт з дисципліни «Методи та технології розподілених та паралельних обчислень» для студентів спеціальності 121 «Інженерія програмного забезпечення». –  Одеса, 2022. – 23 с. 
3. Зіноватна, С.Л. Методичні вказівки до практичних занять з дисципліни «Методи та технології розподілених та паралельних обчислень» для студентів спеціальності 121 «Інженерія програмного забезпечення». –  Одеса, 2022. – 23 с. 

Додаткова література
1. Gebali, F. Algorithms and parallel computing. A John Wiley & Sons, Inc., Publication, 2011. 365 p. ISBN 978-0-470-90210-3 
2. Peterson J. Petri Net Theort and vodeling of systems. Library of Congress Cataloging in Publication Data. https://dl.icdst.org/pdfs/files3/2bf95f7fde49a09814231bbcbe592526.pdf
3. Rauber  T., Runger G. Parallel Programming For Multicore and Cluster Systems. Springer-Verlag Berlin Heidelberg, 2010. 463 p. DOI 10.1007/978-3-642-04818-0. ISBN 978-3-642-04817-3. https://doc.lagout.org/science/0_Computer%20Science/5_Parallel%20and%20D...