Паралельні та розподілені обчислення
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 7.121.01.E.017
Кількість кредитів: 5.00
Кафедра: Програмне забезпечення
Лектор: Базилевич Р.П.
Семестр: 2 семестр
Форма навчання: денна
Завдання: ІНТ. Здатність ефективно розв’язувати спеціалізовані задачі та практичні проблеми інноваційного характеру під час професійної діяльності, пов’язаної зі всіма аспектами виробництва програмного забезпечення від початкових стадій створення специфікації до супроводу системи після здачі в експлуатацію.
ФКС1.2. Здатність продемонструвати знання основних принципів побудови паралельних та розподілених обчислювальних систем, а також засади проектування програмних систем для ефективної організації обчислювального процесу.
Результати навчання: РНС1.3. Вміти застосовувати методологію розпаралелювання алгоритмів та програм в професійній діяльності.
РНС1.4. Вміти використовувати методи оптимізації (лінійне, нелінійне, дискретне та інші види програмування) при проектуванні паралельних алгоритмів та програм.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Пререквізити: Теорія надійності програмних систем
Кореквізити: Виконання та захист магістерської кваліфікаційної роботи
Короткий зміст навчальної програми: В дисципліні розглядаються основні засади пришвидшення обчислень з використанням багатопроцесорних систем. Вивчається класифікація комп’ютерів та комп’ютерних систем за Флином. Розглядаються архітектура Фон-Неймана, багатокористувацькі та конвеєрні системи, векторні та матричні системи, розподілені комп’ютерні системи, їх можливості та обмеження; основні типи топології зв’язків для паралельних комп’ютерів: шини, кросбари, багаторівневі мережі, гіперкуби, деревисті та інші мережі; типи алгоритмів та можливості їх розпаралелювання; ефективність паралельних алгоритмів; пришвидшення; основні параметри паралельних обчислень; граф залежності даних та задач; розмір та глибина обчислень; міра паралелізму; рекурсивна декомпозиція; вхідних, проміжних та вихідних даних; пошукова та динамічна декомпозиції. Даються приклади розпаралелювання реальних складних задач.
Опис: Архітектура паралельних комп’ютерів. Основні принципи пришвидшення обчислень. Системи конвеєрного, векторного та матричного типів. Системи з розподіленою пам’яттю та обміном повідомлень. Мережі для паралельних комп’ютерів. Статичні та динамічні мережі. Топологія мереж. Принципи розпаралелювання обчислень. Умови Бернштейна незалежності процесів. Виявлення паралелізму в алгоритмах. Можливості та ефективність паралельних обчислень. Характеристики розпаралелювання. Розмір та глибина обчислень. Міра паралелізму. Граф залежності даних та задач. Пришвидшення, ефективність, мінімальне число процесорів. Чинники, що визначають ефективність обчислень. Закон Амдагла. Принципи проектування паралельних алгоритмів. Граф залежності проблем. Декомпозиція алгоритмів. Кластеризація задач. Міра паралелізму. Критичний шлях. Граф взаємодії задач. Схема покриття задач процесорами. Декомпозиція алгоритмів. Рекурсивна декомпозиція. Декомпозиція вхідних, проміжних та вихідних даних. Поточна, очікувана та гібридна декомпозиція. Статична та динамічна взаємодія підзадач. Техніки покриття. Мінімізація перестою процесорів. Статичне та динамічне покриття. Покриття на основі декомпозиції даних, задач та гібридне. Ієрархічне покриття. Розпаралелювання прикладних задач. Розпаралелювання алгоритмів сортування, графових, пошукових та інших.
Методи та критерії оцінювання: 1. Опрацювання наукових статей та їх презентація.
2. Участь в обговоренні матеріалів лекцій та статей.
3. Захист лабораторних робіт.
4. Екзаменаційний контроль (письмова компонента, усна компонента).
Критерії оцінювання результатів навчання: Поточний контроль: 50% (виступ з презентацією – 10%, лабораторні роботи – 30% (5 лабораторних робіт по 6% кожна), участь в дискусіях на заняттях 10%)
Екзаменаційний контроль: 50% (письмова компонента 40%, усна компонента 10%)
Максимальні оцінки за лабораторні роботи виставляються при вчасному та успішному виконанні та захисту робіт, який передбачає:
• пояснення коду,
• модифікацію коду (з метою підтвердження самостійності виконання роботи),
• відповіді на теоретичні запитання за темою роботи.
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Паралельні та розподілені обчислення: навчальний посібник для вищих закладів освіти / К.Т. Кузьма, О.В. Мельник. – Миколаїв: ФОП Швець В.М., 2020. – 172 с.
2. Жуков І.А., Корочкін О.В. Ж48 Паралельні та розподілені обчислення. Навч. посіб. –
К.: «Корнійчук» , 2005. – 226 с
3. H.Jordan, G.Alaghband. Fundamentals of parallel processing. Pearson Education, 2003.
4. Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar. Parallel Computing. Addison Wesley, 2003.
5. Edmund K. Burke Graham Kendall. Search methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. Springer, 2005.
6. Mark Harman. The current state and future of search based software engineering. Future of software engineering (FOSE’07). IEEE, 2007.
7. Christian Blum. Metaheuristic in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, vol. 35. № 3, September 2003, pp. 266 – 306.
8. Search methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. Edited by EDMUND K. BURKE GRAHAM KENDALL. Springer. 2005.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).