Паралельні та розподілені обчислення
Спеціальність: Комп'ютерна інженерія
Код дисципліни: 6.123.00.O.038
Кількість кредитів: 4.00
Кафедра: Електронні обчислювальні машини
Лектор: Доцент Євгеній Ваврук
Семестр: 6 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей:
загальні компетентності:
– базові знання фундаментальних наук, в обсязі, необхідному для освоєння загально-професійних дисциплін;
– базові знання в галузі комп’ютерної інженерії (комп’ютерної логіки, теорії програмування) необхідні для освоєння професійно-орієнтованих дисциплін.
– здатність до аналізу та синтезу;
– здатність до застосування знань на практиці;
– здатність здійснювати пошук та аналізувати інформацію з різних джерел;
– здатність розв’язувати поставлені задачі та приймати відповідні рішення;
– креативність, здатність до системного мислення.
фахові компетентності:
– базові знання теоретичних основ шляхів розпаралелення задачі та проведення відповідних обчислень;
– знання сучасних методів та технологій паралельної обробки, паралельних мов програмування, архітектур паралельних обчислювальних систем та окремих вузлів, особливостей визначення параметрів та роботи розподілених систем;
– здатність застосовувати та інтегрувати знання і розуміння дисциплін інших інженерних галузей;
– здатність досліджувати проблему та визначати обмеження при проведенні обчислень.
Результати навчання: У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі результати навчання:
• знати основні поняття паралельних та розподілених обчислень;
• володіти термінологією, застосовною в даній сфері;
• розрізняти та оптимізувати підходи до побудови паралельних та розподілених алгоритмів;
• знати основні конструкції синхронізації паралельних та розподілених процесів;
• вміти застосувати паралельні алгоритми при вирішенні обчислювальних та технічних задач різного призначення;
• використовувати програмні середовища для розробки паралельних алгоритмів та відповідних вузлів;
• використовувати апаратні засоби паралельної обробки;
• вміти обчислювати основні характеристики вузлів паралельної обробки та співставляти і оптимізувати отримані результати з поставленою метою.
У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі програмні результати навчання:
ЗН1 Знати і розуміти наукові і математичні принципи, що лежать в основі функціонування комп’ютерних засобів, систем та мереж.
ЗН2. Знати основи професійно-орієнтованих дисциплін спеціальності в галузі комп’ютерної інженерії.
ЗН3.Мати поглиблені знання принаймні в одному з напрямків галузі комп’ютерної інженерії : комп’ютерні системи та мережі; системне програмування; спеціалізовані комп’ютерні системи.
ЗН7.Знати та розуміти вплив технічних рішень в суспільному, економічному, соціальному і екологічному контексті.
ЗН11.Знати правила експлуатації комп’ютерних систем та мереж.
УМ7.Уміти поєднувати теорію і практику, а також приймати рішення та виробляти стратегію діяльності для вирішення завдань спеціальності з урахуванням загальнолюдських цінностей, суспільних, державних та виробничих інтересів.
УМ9.Уміти оцінювати отримані результати та аргументовано захищати прийняті рішення.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Попередні навчальні дисципліни:
Вища математика
Дискретна математика
Основи алгоритмізації та програмування Ч.1, Ч.2
Супутні і наступні навчальні дисципліни:
Високопродуктивні обчислення
Глобальні інформаційні мережі
Програмні технології мобільних обчислень.
Короткий зміст навчальної програми: Дана дисципліна призначена для освоєння студентами основних принципів організації паралельних та розподілених обчислень, що використовуються при проектуванні та дослідженні різного типу систем та мереж. Для цього передбачається вивчення алгоритмів, мов програмування, структур паралельної обробки та засобів взаємодії між ними, здобуття теоретичних знань та практичних навиків, необхідних для виконання проектних робіт в галузі застосування паралельних алгоритмів та структур.
Викладення теоретичного матеріалу поділено на три логічні блоки: в першому розглядаються основні теоретичні поняття паралельних та розподілених обчислень, в другому – організація паралельних обчислень, в третьому – організація розподілених обчислень.
Для здобуття практичних навиків пропонується цикл лабораторних робіт, ознайомлення із платформою програмування МРІ та використання її можливостей для взаємодії між елементами систем та мереж.
Опис: 1. Предмет та задачі курсу. Зв’язок з іншими дисциплінами навчального плану. Коротка характеристика навчальної літератури. Основні поняття паралельних та розподілених обчислень. Паралельна та розподілена обробка інформації. Проблеми підвищення продуктивності і ефективності використання засобів обчислювальної техніки. Паралелізм, як фундаментальний засіб обчислень. Паралельна і розподілена обробка в системах реального часу. Види паралелізму. Основні поняття паралелізму та векторизації. Ступінь паралелізму алгоритму. Паралельні алгоритми. Формальна модель прискорення паралельного алгоритму. Ступінь векторизації алгоритму. Прискорення та погодженість векторного алгоритму. Класифікація структур паралельної обробки
2. Методи оцінки продуктивності паралельних алгоритмів і систем. Загальні зауваження стосовно оцінки продуктивності паралельних систем. Фактори, що необхідно враховувати при оцінці продуктивності. Методи оцінки продуктивності паралельних систем. Характеристики продуктивності паралельних алгоритмів. Порівняння MIMD i SIMD структур за продуктивністю
3. Розробка паралельного алгоритму. Паралелізм даних. Паралелізм задач. Етапи розробки паралельного алгоритму (декомпозиція, планування комунікацій, укрупнення, планування обчислень).
4. Структури зв’язку між вузлами паралельної системи. Теоретичні основи. Шинні мережі. Сітки з комутаторами. Структури, що забезпечують зв’язок типу «пункт-пункт». Методи комутацій
5. Основні класи сучасних паралельних комп’ютерів (Масивно-паралельні системи. Симетричні мультипроцесорні системи. Системи з неоднорідним доступом до пам’яті. Паралельні векторні процесори. Кластерні системи). Організація обчислень на цих структурах.
6. Схеми паралельних алгоритмів задач. Схеми алгоритмів задач. Алгоритми перемноження матриці на матрицю і їх реалізація на структурах типу: кільцева, 2D (решітка), 3D (куб)
7. Мови паралельного програмування. Класифікація мов і систем паралельного програмування. Особливості організації паралельної програми. Технології паралельного програмування Message Passing Interface (MPI). Операції обміну повідомленнями.
8. Концепції і проблеми паралельної обробки (процеси, дистанційний виклик, неявна паралельність). Проблеми асинхронної паралельності (несумісність даних, блокування, балансування завантаження). Проблеми синхронної паралельності.
9. Вступ до розподілених обчислень. Модель розподілених обчислень. Різниця між локальними та розподіленими обчисленнями. Технологічні тенденції та масштаби мережних розподілених обчислень
10.Теорія мережних розподілених обчислень. Теоретичні основи на яких базується теорія мережних розподілених обчислень. Візантійські відмови і проблема вибору лідера. Проблеми взаємного виключення, відмовостійкості, синхронності, причинних зв’язків і часу в МРО.
11. Балансування навантаження в розподілених системах. Причини появи незбалансованого навантаження. Статичне і динамічне балансування. Методологія практичного рішення задачі балансування. Алгоритми балансування: випадковий алгоритм, алгоритм, що базується на комунікаціях, алгоритм, що базується на обчисленні навантаження
12. Хвильові алгоритми розповсюдження інформації (кільцевий, деревоподібний, голосування, фазовий, Фінна). Поширення інформації зі зворотним зв’язком.
Методи та критерії оцінювання: Оцінювання здійснюється за результатами виконання у віртуальному навчальному середовищі університету лекційних та семестрового тесту, також за результатами лабораторних занять.
Критерії оцінювання результатів навчання: Максимальна кількість балів для оцінки поточного контролю (ПК) знань за семестр – 40 балів.
Екзаменаційний контроль проводиться в письмово-усній формі.
Максимальна кількість балів для оцінки екзаменаційного контролю – 60 балів.
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Є.Ваврук Організація паралельних та розподілених обчислень// Навчальний посібник до лекційного курсу з дисципліни “Паралельні та розподілені обчислення” для студентів базового напряму 6.050102 "Комп'ютерна інженерія” Вид-во Нац. ун-ту “Львівська політехніка”, 2015 р. 109
2. Є.Ваврук, О.Лашко Організація паралельних обчислень// Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915 - “Комп’ютерна інженерія” Вид-во Нац. ун-ту “Львівська політехніка”, 2007 р., 70
3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург
4.Є.Ваврук, О. Акимишин Паралельні алгоритми множення матриці на матрицю// Методичні вказівки до лабораторної роботи № 4 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915 "Комп'ютерна інженерія“
5.Є.Ваврук, О. Акимишин Технологія паралельного програмування засобами МРІ // Методичні вказівки до лабораторної роботи № 3 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915 "Комп'ютерна інженерія“
6.Є.Ваврук, О.Лашко Використання функціональної декомпозиції для розв’язання обчислювальних задач// Методичні вказівки до лабораторної роботи № 1 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915 "Комп'ютерна інженерія“ Вид-во Нац. ун-ту “Львівська політехніка”, 2010 р., 12с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).