МЕТОДИ І ТЕХНОЛОГІЇ ПАРАЛЕЛЬНОГО ПРОГРАМУВАННЯ - Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни
Рівень вищої освіти Другий (магістерський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційні системи та технології
Освітня програма Інтегровані інформаційні системи, Інформаційне забезпечення робототехнічних систем, Інформаційні управляючі системи та технології
Статус дисципліни Вибіркова
Форма навчання очна(денна)/заочна/дистанційна
Рік підготовки, семестр 1 курс, весняний семестр
Обсяг дисципліни 150 годин (денна: 36 годин – лекції, 18 годин – лабораторні, 96 години – СРС;
Семестровий контроль/ контрольні заходи Залік
Розклад занять http://rozklad.kpi.ua
Мова викладання Українська
Інформація про керівника курсу / викладачів

Лектор: д.ф.-м.н., проф. Дорошенко Анатолій Юхимович,

a-y-doroshenko@ukr.net ,

роб. +38(099)266-9311

Лабораторні: к.ф.-м.н., доц. Жереб Костянтин Анатолійович,

zhereb@gmail.com, моб. +38(095)874-2832

| | Розміщення курсу | https://campus.kpi.ua |

Програма навчальної дисципліни

Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання

Опис дисципліни. Навчальна дисципліна «Методи і технології паралельного програмування» належить до вибіркових дисциплін циклу професійної підготовки зі спеціальності 126 – Інформаційні системи та технології освітньої програми Інформаційні управляючі системи та технології. При вивченні дисципліни, студенти познайомляться з основними засадами мультипроцесорних систем, моделями високопродуктивних обчислень та технологіями паралельного програмування. На лабораторних заняттях студенти опанують засоби сучасних мов паралельного програмування та познайомляться з методи проектування ефективних паралельних програм. В курсі передбачений контроль якості отриманих знань у формі модульних контрольних робіт.

Навчальна дисципліна належить до циклу навчальних дисциплін загальної підготовки, дослідницький (науковий) компонент (за вибором студентів).

Предмет навчальної дисципліни: Предметом навчальної дисципліни є методи і технології паралельного програмування для високопродуктивних обчислень на мультипроцесорних системах.

Міждисциплінарні зв’язки. Навчальна дисципліна в структурно-логічній схемі програми підготовки фахівців освітнього ступеня «магістр» забезпечується всіма попередніми дисциплінами бакалаврату.

Мета навчальної дисципліни. Метою викладання дисципліни є залучення студентів до використання високопродуктивної обчислювальної техніки в науково-дослідній роботі та ознайомлення їх з методами розробки паралельних програм.

Основні завдання навчальної дисципліни

Знати:

  • характеристики архітектури мультипроцесорних систем;

  • парадигми паралельного програмування;

  • засоби програмування систем паралельних обчислень зі спільною та розподіленою пам’яттю;

  • критерії продуктивності паралельних алгоритмів;

  • методи розробки ефективних паралельних програм.

Уміти:

  • вибирати архітектуру мультипроцесорної системи для відповідного класу прикладних задач;

  • користуватись відповідними цільовій архітектурі засобами паралельного програмування;

  • розробляти паралельні алгоритми розв’язування прикладних задач;

  • оцінювати ефективність паралельних алгоритмів за вибраними критеріями.

Передумови та постумови дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

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

Постумови: після вивчення дисципліни студенти будуть готові самостійно розробляти паралельні алгоритми в наукових дослідженнях та зможуть користуватися сучасними інтерфейсами паралельного програмування.

Зміст навчальної дисципліни

Лекційні заняття

Тема 1. Вступ до дисципліни, основні поняття паралельних обчислень.

Тема 2. Структуризація паралелізму операцій в комп’ютерних системах

Тема 3. Характеристики архітектури мультипроцесорних систем.

Тема 4. Парадигми паралельного програмування.

Тема 5. Поняття критичної секції та взаємного виключення процесів.

Тема 6. Основні підходи до вирішення проблеми взаємного виключення процесів. Алгоритм Деккера.

Тема 7. . Засоби бінарних та загальних семафорів.

Тема 8. Засоби синхронізації критичних областей.

Тема 9. Синхронізація засобами моніторів

Тема 10. Префіксні команди Дійкстри.

Тема 11. Засоби програмування обмінів повідомленнями.

Тема 12. Засоби програмування віддаленого виклику.

Тема 13. Моделі RAM і PRAM для оцінки складності обчислень

Тема 14. Критерії продуктивності паралельних обчислень

Тема 15. Закон Амдала та принцип Брента.

Тема 16. Парадигми еволюціонуючих паралельних обчислень.

Тема 17. Методи розробки ефективних паралельних програм.

Тема 18. Сучасні технології паралельного програмування: МРІ та OpenMP.

Лабораторні заняття

1. Засоби створення та керування потоками в паралельних мультипоточних програмах.

2. Засоби взаємодії та синхронізації потоків в паралельних мультипоточних програмах.

3. Навчальний проект з паралельного мультипоточного програмування. Моделювання броунівського руху.

4. Засоби взаємодії процесів в паралельних програмах з розподіленою пам'яттю

5. Навчальний проект з паралельного розподіленого програмування. Система передачі повідомлень

Навчальні матеріали та ресурси

Основна література

  1. Ф.И. Андон, А.Е. Дорошенко, К.А. Жереб, Р.С. Шевченко, Е.А. Яценко, Методы алгебраического программирования. Формальные методы разработки параллельных программ. - Киев, "Наукова думка".-2017.- 440 с.

  2. Дорошенко А*.*Ю. Лекції з паралельних обчислювальних систем. Методичний посібник.− Київ: Видавничий дім «КМ Академія», 2003.−42 с.

  3. Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. - К.,"Наукова думка", 2000.- 177 с.

  4. А.Ю. Дорошенко, Г.С. Фінін, Г.О. Цейтлін, Алгеброалгоритмічні основи програмування. Об’єктна орієнтація і паралелізм., Київ, „Наукова думка”, 2004.-458 c.

  5. Немнюгин С.А. Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем.–СПб:БХВ-Петербург, 2002.–400 с.

  6. Дж.Вебер, Технология Java в подлиннике, BHV,СПб, 2000, 1104 с.

  7. http:/parallel.ru/

Допоміжна література

  1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.– СПб.: БХВ-Петербург, 2002.–608 с.

    1. Таненбаум,_M._ван_Стеен, Распределенные системы. – Питер, 2003.- 526 с.

  3. Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications (M. Parashar and X. Li, eds.).- Wiley, 2010.-543 p.

  4. Ajay D. Kshemkalyani, Mukesh Singhal. Distributed Computing Principles, Algorithms, and Systems.-Cambridge University Press, 2008.-736 p.

  5. Topics in Parallel and Distributed Computing (Sushil K Prasad, Anshul Gupta, Arnold L Rosenberg, Alan Sussman, Charles C Weems).-Elsevier, 2015.- 337 p.

  6. Large scale network-centric distributed systems (Hamid Sarbazi-Azad and Albert Y. Zomaya, eds.).-Wiley, 2014.-762 p.

  7. Cloud Computing: Principles and Paradigms (Rajkumar Buyya, James Broberg, and Andrzej Goscinski, eds).-Wiley, 2011.-642 p.

Навчальний контент

Методика опанування навчальної дисципліни (освітнього компонента)

Лекційні заняття

№ з/п Назва теми лекції та перелік основних питань
(перелік дидактичних засобів, посилання на літературу та завдання на СРС)		 Кількість ауд. годин
1

Тема 1. Вступ до дисципліни, основні поняття паралельних обчислень

Лекція 1. Вступ до дисципліни, основні поняття паралельних обчислень

Принципи класичної моделі послідовних обчислень фон Неймана та основні етапи розвитку мультипроцесорних систем [1,2].

Завдання на СРС. Ознайомлення з прикладами розробок паралельних мультипроцесорних систем.

Література: [1, Розд.1.], [5, Розд.1]

 2
2

Тема 2. . Структуризація паралелізму операцій в комп’ютерних системах Лекція 2. Структуризація паралелізму операцій в комп’ютерних системах.

Види і рівні паралелізму виконання операцій в обчислювальних системах. [1,2].

Завдання на СРС. Вивчення прикладів реалізації характеристик архітектури мультипроцесорних систем.

Література: [7], [2, Розд.1]

 2
3

Тема 3. Характеристики архітектури мультипроцесорних систем

Лекція 3. Характеристики архітектури мультипроцесорних систем

Кількість та якість процесорів (ядер) обчислювальної системи, види пам’яті, види зв’язку та режими управління в мультипроцесорних системах. Таксономія архітектур комп’ютерних систем паралельної дії за М. Флінном [1,2].

Завдання на СРС. Ознайомлення з відмінними від таксономії М.Флінна підходами до таксономії архітектур паралельних систем.

Література: [4, Розд. 4], [5]

 2
4

Тема 4. Парадигми паралельного програмування

Лекція 4. Парадигми паралельного програмування

Парадигми програмування паралелізму за даними, за управлінням та потокова парадигма [1-3].

Завдання на СРС. Вивчення засобів програмування паралелізму за даними.

Література: [1, Розд. 4], [5]

 2
5

Тема 5. Поняття критичної секції та взаємного виключення процесів

Лекція 5. Поняття критичної секції та взаємного виключення процесів.

Поняття критичної секції процесу та умови дотримання взаємного виключення процесів [1,2].

Завдання на СРС Ознайомлення з засобами паралельного програмування за керуванням.

Література: [2, Розд. 5.2], [1], [5]

 2
6

Тема 6. Основні підходи до вирішення проблеми взаємного виключення процесів. Алгоритм Деккера.

Лекція 6. Основні підходи до вирішення проблеми взаємного виключення процесів. Алгоритм Деккера [1,2].

Ідеї додаткових змінних для управління доступом до критичних секцій. Алгоритм Деккера для програмного вирішення проблеми взаємного виключення процесів. [1,2].

Завдання на СРС Вивчення засобів паралельного програмування за потоковою парадигмою.

Література: [2, Розд. 5.3], [1], [5]

 2
7

Тема 7. Засоби бінарних та загальних семафорів.

Лекція 7. Засоби бінарних та загальних семафорів

Техніка семафорів для вирішення проблеми взаємного виключення процесів. Бінарні та загальні семафори. [1,2].

Завдання на СРС. Ознайомлення з прикладами застосування техніки семафорів у різних мовах паралельного програмування.

Література: [1, Розд. 3], [5]

 2
8

Тема 8. Засоби синхронізації критичних областей.

Лекція 8. Засоби синхронізації критичних областей.

Недоліки техніки семафорів. Поняття засобу критичної області. Класична задача про філософів-обідників [1,2].

Завдання на СРС. Вивчення тупиків за ресурсами в паралельних програмах

Література: [1, Розд. 4], [5]

 2
9

Тема 9. Синхронізація засобами моніторів.

Лекція 9. Синхронізація засобами моніторів.

Структурність засобів синхронізації процесів. Поняття монітора та його застосування [1,2].

Завдання на СРС. Визначення синтаксису та семантики засобів синхронізації моніторів.

Література: [1, 2], [5]

 2
10

Тема 10. Префіксні команди Дійкстри.

Лекція 10. Префіксні команди Дійкстри.

Недетермінізм в паралельних програмах. Модель обчислень префіксних команд та її застосування [1,2].

Завдання на СРС. Застосування префіксних команд для вирішення синхронізаційних та координаційних задач.

Література: [1, 2].

 2
11

Тема 11. Засоби програмування обмінів повідомленнями.

Лекція 11. Засоби програмування обмінів повідомленнями.

Модель паралельних обчислень з розподіленою пам’яттю. Засоби обміну повідомленнями, приклади застосування [1, 2].

Завдання на СРС. Вивчення прикладів реалізації обміну повідомленнями у мовах паралельного програмування.

Література: [1, 2].

 2
12

Тема 12. Засоби програмування віддаленого виклику

Лекція 12. Засоби програмування віддаленого виклику

Розвиток засобів програмування віддаленого виклику процедур та архітектури клієнт-сервер [1,2].

Завдання на СРС. Вивчення прикладів реалізації віддаленого виклику процедур у мовах паралельного програмування.

Література: [1, 2].

 2
13

Тема 13. Моделі RAM і PRAM для оцінки складності обчислень

Лекція 13. Моделі RAM і PRAM для оцінки складності обчислень

Абстрактні моделі обчислювачів. Моделі RAM і PRAM для оцінки складності обчислень [1,2].

Завдання на СРС. Вивчення прикладів оцінки складності обчислень для обчислювальних задач.

Література: [1, 2].

 2
14

Тема 14. Критерії продуктивності паралельних обчислень

Лекція 14. Критерії продуктивності паралельних обчислень

Коефіцієнти прискорення та ефективності паралельних обчислень. Ціна паралельних обчислень [1, 2].

Завдання на СРС. Вивчення прикладів оцінки коефіцієнтів прискорення та ефективності паралелізму в обчислювальних задачах.

Література: [1, 2].

 2
15

Тема 15. Закон Амдала та принцип Брента

Лекція 15. Закон Амдала та принцип Брента [1, 2].

Фундаментальне обмеження для прискорення паралельних обчислень, закон Амдала. Паралельні обчислення на обмежених ресурсах, принцип Брента [1, 2].

Завдання на СРС. Дослідження оцінок продуктивності конкретних паралельних алгоритмів відносно критерію ціни мультипроцесорного прискорення.

Література: [1, 2].

 2
16

Тема 16. Парадигми еволюціонуючих паралельних обчислень

Лекція 16. Парадигми еволюціонуючих паралельних обчислень

Некласичні парадигми паралельних обчислень: з невизначеним обсягом вхідних даних, зі змінним обсягом обчислень та обмеженням на час виконання. [1, 5].

Завдання на СРС. Дослідження явища накопичення даних для суперлінійного прискорення.

Література: [1, 5].

 2
17

Тема 17. Методи розробки ефективних паралельних програм

Лекція 17. Методи розробки ефективних паралельних програм

Метод балансованого дерева та метод «розділяй і владарюй» [1, 5].

Завдання на СРС. Дослідження оцінок продуктивності конкретних паралельних алгоритмів відносно методів розробки ефективних паралельних програм.

Література: [1, 5].

 2
18

Тема 18. Сучасні технології паралельного програмування: МРІ та OpenMP.

Лекція 18. Сучасні технології паралельного програмування: МРІ та OpenMP.

Інтерфейси паралельного програмування для розподілених обчислень МРІ. Директиви OpenMP для паралельного програмування зі спільною пам’яттю [1, 5, 7].

Завдання на СРС. Вивчення прикладів оцінки програмування обчислювальних задач в технологіях паралельного програмування МРІ та OpenMP.

Література: [1, 5, 7].

 2
Всього 36

**
**

Лабораторні роботи (денна форма навчання)

№ Назва лабораторної роботи Кількість ауд. годин
1

Лабораторна робота 1. Засоби створення та керування потоками в паралельних мультипоточних програмах.

Реалізувати послідовну та паралельну мультипоточну обробку незалежних задач (наприклад, parameter sweep – вирішуються екземпляри однієї задачі для різних значень параметрів). Реалізувати приклади задач трьох типів:

  1. CPU-bound – складні обчислення з невеликим обсягом даних

  2. Memory-bound – робота з даними, що зберігаються в пам’яті

  3. IO-bound – робота з даними на диску.

Виміряти залежність часу виконання від кількості потоків.

Література: [4, Розділ 1], [5]

 2
2

Лабораторна робота 2. Засоби взаємодії та синхронізації потоків в паралельних мультипоточних програмах.

Реалізувати одне з наступних завдань, використовуючи засоби мультипоточного програмування:

  1. Задано функцію f:A→B, а також список значень типу A. Застосувати функцію до кожного елементу списку. Після цього знайти та повернути мінімальний елемент отриманого списку (відповідно до заданого критерію порівняння), а також його індекс.

  2. Задано список заданого типу, а також декілька функцій, які перетворюють цей список (наприклад, алгоритми сортування). Застосувати кожну з функцій до початкового списку (незалежно, а не послідовно). Потім порівняти результати роботи функцій, повернути таблицю попарних відмінностей (чи однакові результати, якщо ні – чи відрізняються довжини списків, якщо відрізняються елементи – індекс першої відмінності).

  3. Задано функції generate: Int→A, transform: A→B, merge: B×B→B. Згенерувати задану кількість елементів типу A з використанням функції generate, потім перетворити кожен з них до типу B з використанням функції transform, потім об’єднати їх в один елемент з використанням функції merge. Повернути цей елемент.

  4. Задано дві матриці заданого (чисельного) типу. Перемножити ці матриці, потім знайти мінімальний елемент отриманої матриці (відповідно до заданого критерію порівняння), повернути його значення та індекси в матриці.

  5. Задано дві функції f,g:A→B, а також список значень типу A. Застосувати ці функції до кожного елементу заданого списку. Потім побудувати список, який містить всі елементи, що входять до обох отриманих списків (за заданим критерієм порівняння), в порядку, що визначається застосуванням функції f.

Література: [1, Частина 2, Розділ 4]

 4
3

Лабораторна робота 3. Навчальний проект з паралельного мультипоточного програмування. Моделювання броунівського руху

Постановка завдання: Моделюється броунівський рух частинок (домішок) в одновимірному кристалі, що складається з N комірок. Переміщення кожної з K частинок моделюється незалежно, на окремому потоці. Рух частинок задається наступним правилом: в кожен момент часу (на кожній ітерації) частка переміщається або вправо (з ймовірністю p), або вліво (з ймовірністю 1-p). При досягненні межі кристала частка відбивається від неї (тобто не виходить за межі кристала). У початковий момент всі домішки знаходяться в першій (лівій) комірці кристала. Переміщення частинок відслідковуються в інтерфейсі (графічному або консольному).

Моделювання проводиться в двох режимах: з обмеженням за часом і за кількістю ітерацій. У першому режимі задається час виконання програми і затримка між ітераціями; програма виконується протягом заданого часу. У другому режимі кожна частинка робить заданий число переміщень (ітерацій); програма завершується, коли всі частинки здійснили всі переміщення. В цьому режимі затримки між ітераціями не передбачені; також не слід показувати поточний стан кристала для кожної ітерації – вивід проміжних станів не повинен уповільнювати обчислення.

Література: [4, Частина 2, Розділ 5]

 4
4

Лабораторна робота 4. Засоби взаємодії процесів в паралельних програмах з розподіленою пам'яттю.

Перенести завдання з лабораторних робіт №1 та №2 на модель з розподіленою пам’яттю (незалежні процеси, взаємодія через обмін повідомленнями). Порівняти час виконання мультипоточних та розподілених версій.

Література: [4, Частина 2, Розділ 5]. [5]

 2
5

Лабораторна робота 5. Навчальний проект з паралельного розподіленого програмування. Система передачі повідомлень.

Реалізувати мережеву програму для передачі повідомлень (аналог чату). Можлива функціональність для реалізації:

  • Передача текстових повідомлень

  • Базове форматування тексту

  • Передача файлів

  • Передача мультимедійних повідомлень (зображення, аудіо, відео, веб-посилання)

  • Передача індивідуальних повідомлень

  • Передача повідомлень усім учасникам (broadcast)

  • Групи учасників, передача повідомлень усім учасникам даної групи

  • Перелік учасників

  • Відслідковування учасників, які від’єднались через мережеві проблеми

  • Можливість передачі повідомлень учасникам, які зараз не в мережі

Не обов’язково реалізовувати всю описану функціональність, проте суттєва частина має бути реалізована. Можна також реалізувати додаткові можливості, що мають сенс для подібних програм.

Література: [5, Частина 2, Розділ 8]

 4
Всього 18

**
**

Самостійна робота студента

№ з/п

 Назва теми, що виноситься на самостійне опрацювання Кількість годин СРС
1 Ознайомлення з прикладами розробок паралельних мультипроцесорних систем. 4
2 Вивчення прикладів реалізації характеристик архітектури мультипроцесорних систем 4
3 Ознайомлення з відмінними від таксономії М.Флінна підходами до таксономії архітектур паралельних систем. 4
4 Вивчення засобів програмування паралелізму за даними. 6
5 Ознайомлення з засобами паралельного програмування за керуванням 6
6 Вивчення засобів паралельного програмування за потоковою парадигмою 6
7 Ознайомлення з прикладами застосування техніки семафорів у різних мовах паралельного програмування 6
8 Вивчення тупиків за ресурсами в паралельних програмах 6
9 Визначення синтаксису та семантики засобів синхронізації моніторів 6
10 Застосування префіксних команд для вирішення синхронізаційних та координаційних задач 6
11 Вивчення прикладів реалізації обміну повідомленнями у мовах паралельного програмування 5
12 Вивчення прикладів реалізації віддаленого виклику процедур у мовах паралельного програмування 5
13 Вивчення прикладів оцінки складності обчислень для обчислювальних задач. 5
14 Вивчення прикладів оцінки коефіцієнтів прискорення та ефективності паралелізму в обчислювальних задачах 5
15 Дослідження оцінок продуктивності конкретних паралельних алгоритмів відносно критерію ціни мультипроцесорного прискорення 5
16 Дослідження явища накопичення даних для суперлінійного прискорення 5
17 Дослідження оцінок продуктивності конкретних паралельних алгоритмів відносно методів розробки ефективних паралельних програм 6
18 . Вивчення прикладів оцінки програмування обчислювальних задач в технологіях паралельного програмування МРІ та OpenMP 6
Всього 96

Політика та контроль

Політика навчальної дисципліни (освітнього компонента)

Система вимог, які ставляться перед студентом:

  • відвідування лекційних та практичних занять є обов’язковою складовою вивчення матеріалу;

  • на лекції викладач користується власним презентаційним матеріалом; використовує гугл-диск для викладання матеріалу поточної лекції, додаткових ресурсів та інше; викладач відкриває доступ до певної директорії гугл-диска для скидання електронних презентацій студентів;

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

  • заохочувальні бали виставляються за: активну участь на лекціях; участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць; презентацій по одній із тем СРС дисципліни тощо. Кількість заохочуваних балів на більше 10;

  • штрафні бали виставляються за: невчасну здачу лабораторної роботи. Кількість штрафних балів на більше 10.

Види контролю та рейтингова система оцінювання результатів навчання (РСО)

Рейтинг студента денної форми навчання складається з балів, що він отримує за::

  1. виконання та захист 5 лабораторних робіт;

  2. виконання 2 модульних контрольних робіт (МКР);

  3. заохочувальні та штрафні бали.

  4. відповіді на питання екзаменаційного білета.

Рейтинг студента заочної форми навчання складається з балів, що він отримує за:

  1. виконання та захист лабораторних робіт;

  2. виконання модульної контрольної роботи;

  3. заохочувальні та штрафні бали.

  4. відповіді на питання залікового білета.

Система рейтингових балів та критерії оцінювання

Денна форма навчання:

Лабораторні роботи (всього максимум 35 балів):

«відмінно», повна відповідь на питання під час захисту (не менш ніж 90% потрібної інформації) та оформлений належним чином електронний протокол до лабораторної роботи – 4 бали;

«добре», достатньо повна відповідь на питання під час захисту (не менш ніж 75% потрібної інформації) та оформлений належним чином електронний протокол до лабораторної роботи – 3 бали;

«задовільно», неповна відповідь на питання під час захисту (не менш ніж 60% потрібної інформації), незначні помилки та оформлений належним чином електронний протокол до лабораторної роботи – 2 бали;

«незадовільно», незадовільна відповідь та/або не оформлений належним чином електронний протокол до лабораторної роботи – 0 балів.

За кожне заняття запізнення з поданням лабораторної роботи до захисту від встановленого терміну оцінка знижується на 1 бал.

Модульні контрольні роботи (всього максимум по 10 балів за кожну з двох):

«відмінно», повна відповідь (не менш ніж 90% потрібної інформації) – 10 балів;

«добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), або повна відповідь з незначними помилками – 6-8 балів;

«задовільно», неповна відповідь (але не менш ніж 60% потрібної інформації) та незначні помилки – 3-5 балів;

«незадовільно», незадовільна відповідь (неправильний розв’язок задачі), потребує обов’язкового повторного написання в кінці семестру – 0 балів.

Заохочувальні бали

– за виконання творчих робіт з кредитного модуля (наприклад, участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць тощо); за активну роботу на лекції (питання, доповнення, зауваження за темою лекції, коли лектор пропонує студентам задати свої питання) 1-2 бали, але в сумі не більше 10;

– презентації по СРС – від 1 до 5 балів.

Міжсесійна атестація

За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 24 бали (2 лабораторні, МКР-1). На першій атестації (8-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 14 балів.

За результатами 13 тижнів навчання максимально можлива кількість балів – 41 бал (3 лабораторних, МКР-2). На другій атестації (14-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 21 бал.

Максимальна сума вагових балів контрольних заходів протягом семестру складає:

RD = 5*rлаб+2*rмкр+ (rз - rш)=5*7+2*10+ (rз - rш)=55 + (rз - rш),

де rлаб – бал за лабораторну роботу (0…7);

rмкр – бал за написання МКР (0…10);

rз – заохочувальні бали за активну участь на лекціях, презентації, участь в олімпіадах, конкурсі роботи, наукові роботи за тематикою дисципліни (0…10);

rзш – штрафні бали (0…10).

Система оцінювання залікових питань (максимум 45 балів):

«відмінно», повна відповідь, не менше 90% потрібної інформації, що виконана згідно з вимогами до рівня «умінь», (повне, безпомилкове виконання завдання) – 19-22 бали;

«добре», достатньо повна відповідь, не менше 75% потрібної інформації, що виконана згідно з вимогами до рівня «умінь» або є незначні неточності (повне виконання завдання з незначними неточностями) – 16-18 балів;

«задовільно», неповна відповідь, не менше 60% потрібної інформації, що виконана згідно з вимогами до «стереотипного» рівня та деякі помилки (завдання виконане з певними недоліками) – 13-15 балів;

«незадовільно», відповідь не відповідає умовам до «задовільно» – 0-12 балів.

Сума стартових балів та балів за екзаменаційну контрольну роботу переводиться до екзаменаційної оцінки згідно з таблицею:

Таблиця 1. Переведення рейтингових балів до оцінок за університетською шкалою

Кількість балів Оцінка
100-95 Відмінно
94-85 Дуже добре
84-75 Добре
74-65 Задовільно
64-60 Достатньо
Менше 60 Незадовільно
нездача письмової роботи Не допущено

Додаткова інформація з дисципліни (освітнього компонента)

  • перелік теоретичних питань, які виносяться на семестровий контроль наведено в Додатку 1;

Робочу програму навчальної дисципліни (Силабус):

Складено професор, д.ф.-м.н., Дорошенко Анатолій Юхимович

Ухвалено кафедрою ІСТ (протокол № 1 від 30.08.2021 р.)

Погоджено Методичною комісією факультету (протокол № 1 від 30.08.2021 р.)

Додаток 1

Перелік теоретичних питань на залік

  1. Види і рівні паралелізму операцій в комп’ютерних системах.

  2. Характеристики архітектури мультипроцесорних систем.

  3. Таксономія архітектур мультипроцессорних систем за Флінном.

  4. Парадигми паралельного програмування за даними

  5. .Парадигми паралельного програмування за керуванням

  6. Потокова парадигми паралельного програмування

  7. Поняття критичної секції та взаємного виключення процесів.

  8. Підходи до програмного вирішення проблеми взаємного виключення процесів.

  9. Алгоритм Деккера для взаємного виключення процесів.

  10. Бінарні семафори та їх застосування.

  11. Загальні семафори та їх застосування.

  12. Задача про обмежений буфер

  13. Засоби синхронізації критичних областей.

  14. Проблема тупиків та засоби її розв’язання.

  15. Засоби синхронізації моніторів.

  16. Префіксні команди Дійкстри.

  17. Засоби програмування обмінів повідомленнями

  18. Засоби програмування віддаленого виклику

  19. Моделі RAM і PRAM для оцінки складності обчислень.

  20. Мультипроцесорне прискорення паралельних обчислень.

  21. Ефективність паралельних обчислень.

  22. Критерій ціни для продуктивності паралельних обчислень.

  23. Закон Амдала.

  24. Принцип Брента.

  25. Суперлінійне прискорення за парадигми накопичення даних.

  26. Суперлінійне прискорення за парадигми належного вибору набору даних.

  27. Суперлінійне прискорення за парадигми складної зворотної функції.

  28. Метод балансованого дерева.

  29. Метод "розподіляй та владарюй".

  30. Сучасні інтерфейси для паралельного програмування.

  31. Основні поняття стандарту МРІ та OpenMP.