Паралельні та розподілені обчислення
Спеціальність: Комп'ютерна інженерія
Код дисципліни: 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-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).