Розподілені обчислення

Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмна інженерія

Викладач: доцент Верес Максим Миколайович (лекції, лабораторні заняття)

Викладається: в 6-му семетрі бакалаврату.
Загальний обсяг: 68 год, з яких:
  • Лекції – 34 год.
  • Лабораторні роботи – 34 год.

Мета та завдання дисципліни

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

Предмет дисципліни

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

Вимоги до знань та вмінь

Для вивчення курсу Розподілені обчислення студент повинен прослухати наступні курси:
  • Основи програмування,
  • Програмування,
  • Теорія алгоритмів та математична логіка,
  • Алгоритми та складність,
  • Основи об'єктно-орієнтованого програмування,
  • Об'єктно-орієнтоване програмування.
В результаті вивчення навчальної дисципліни студент повинен
знати:
  • відомості про методи побудови паралельних алгоритмів обчислення в:
    • багатопотокових системах,
    • розподілених системах,
    • системах синхроних паралельних розрахунків;
та вміти:
  • проектувати та розробляти паралельні програми на багатоядерних та багатопроцесорних комп'ютерах.

Програма курсу

Змістовий модуль 1:

Тема 1: Введення в розподілені розрахунки.
  • Основи та історія виникнення комп'ютерних мереж, Інтернет.
  • Архітектури мережі.
  • Модель протоколів ISO та її відображення в TCP/IP.
Тема 2: Модель, спеціалізації розподілених розрахунків.
  • Стилі паралельного програмування.
  • Три класи задач:
    • багатопотокові системи,
    • розподілені системи,
    • системи синхронних паралельних розрахунків.
Тема 3: П'ять головних парадигм паралельного програмування.
  • Ітеративний паралелізм (множення матриць).
  • Рекурсивний паралелізм (адаптивна квадратура).
  • "Виробники та споживачи" (конвейери) – канали ОС Unix.
  • "Клієнт-сервер" – файлові системи.
  • Взаємодіючи рівні (розподілене множення матриць), передача повідомлень:
    • "керівник-робітник",
    • конвеєр.
Тема 4: Програмування з роздільними змінними.
  • Мультипроцесорні системи(SMP).
  • Проблеми при створенні багатопоточних програм.
Тема 5: Процеси та синхронізація
  • Програмна реалізація синхронізованої багато поточності.
Тема 6: Критичні секції. Семафори, розподілення ресурсів планування. Монітори.
  • Блокування та бар'єри.
  • Критичні секції.
  • Бар'єрна синхронізація.
  • Семафори, розподілення ресурсів планування.
  • Монітори, методи синхронізації.
Тема 7: Розподілене програмування.
  • Особливості програмування під архітектуру з розподіленою пам'яттю.
Тема 8: Віддалений виклик процедур, рандеву.
  • Програмні підходи для програмування взаємодії клієнт-сервер.
Тема 9: Моделі взаємодії процесів.
  • Поєднання схем взаємодії процесів:
    • виробник-споживач,
    • клієнт-сервер
    • взаємодіючи рівні.
Модульна контрольна робота 1

Змістовий модуль 2:

Тема 10: Мета та задачі паралельної обробки даних.
  • Типові області використання паралельної обробки даних.
Тема 11: Моделі обчислень та методи аналізу ефективності.
  • Прискорення та Ефективність.
  • Закон Амдала та наслідки.
  • Розрахунок реального прискорення паралельного підходу перед лінійним.
Тема 12: Принципи розробки паралельних методів.
  • Моделювання паралельних програм.
  • Методика розробки паралельних алгоритмів.
  • Етапи розробки:
    • розділення обчислень,
    • виділення інформаційних залежностей,
    • маштабування,
    • розподілення обчислень між процесами.
Тема 13: Технологія розробки для багатоядерних та багатопроцесорних систем (стандарт передачи повідомлень MPI та OpenMP).
  • Загальна характеристика стандарту MPI.
  • Режими передачі даних.
  • Загальна характеристика стандарту OpenMP.
  • Створення паралельних блоків.
  • Розподіл обчислювального навантаження між потоками.
  • Робота з даними.
  • Синхронізація.
  • Порівняльна характеристика підходів паралельного програмування для систем з розподіленою і роздільною пам'яттю.
Тема 14: Паралельні алгоритми розв'язку задач. Матричні операції.
  • Матрично-векторне множення, множення матриць, розв'язок систем лінійних рівнянь.
Тема 15: Паралельні алгоритми розв'язку задач. Системи лінійних рівнянь.
  • Паралельні алгоритми:
    • метод Гауса,
    • метод спряжених градієнтів.
Тема 16: Паралельні алгоритми розв'язку задач. Методи сортування.
  • Паралельне сортування.
  • Порівняння ефективності паралельно сортування в залежності від кількості обчислювальних вузлів.
Тема 17: Паралельні алгоритми розв'язку задач. Розв'язок диференційних рівнянь.
  • Паралельний розв'язок диференційних рівнянь.
  • Ефективність паралельного розв'язку диференційних рівнянь.
Модульна контрольна робота 2

Рекомендована література

Основна:

  1. Воеводин В.В., Воеводин Вл.В. Паралельные вычисления. – Санкт-Петербург, – 2004.
  2. Грегори Р. Эндрюс. Основы Многопоточного, параллельного и распределенного программирования. – Москва-Санкт-Петеррбург-Киев, – 2003.
  3. Немнюгин С., Стесик О. Паралельное програмирование для многопроцессорных вычислительных систем. – Санкт-Петербург, – 2002.
  4. Миллер Р. Последовательные и паралельные алгоритмы. – Москва, – 2006.
  5. mcsharp.net

Додаткова:

  1. Макс К. Гофф. Сетевые распределенные вычисления: достижения и проблемы. – Москва, – 2005.
  2. parallel.ru
  3. dtf.ru
  4. intel.com
  5. openmp.org
  6. mpi-forum.org