Мета курсу - вивчення: основних методів, алгоритмів, принципів побудови структур реалізації паралельних та розподілених обчислень, набуття початкових практичних навиків проектування таких засобів.
Результат вивчення – знання основних методів, алгоритмів і засобів паралельної та розподіленої обробки інформації, засобів програмування паралельних та розподілених обчислень та їх реалізації, складу апаратного та програмного забезпечення обчислювальних систем з засобами паралельної та розподіленої обробки і класів мов програмування високого рівня для них.
Основні питання:
Паралельні обчислення:
- вступ до курсу паралельних обчислень;
- методи оцінки продуктивності паралельних алгоритмів;
- мережі Петрі;
- розробка паралельного алгоритму;
- структури зв’язку між процесорами;
- основні класи паралельних комп’ютерів;
- схеми паралельних алгоритмів задач;
- мови паралельного програмування.
Розподілені обчислення:
- вступ до організації розподілених обчислень і розподілених систем;
- організація протоколів обміну в розподілених ситсемах;
2. Ортега Дж. Введение в параллельные і векторные методы решения линейных систем. М.:Мир, 1991.
3. Программирование на параллельных обчислювальних системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
4. Тройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
5. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
6. Векторизация программ: теория, методы, реализация: Пер. с англ. і нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
7. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
8. Вальковский В.А. Распараллеливание алгоритмов і програм. Структурный подход-М.:Радио і связь, 1989.
9. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных обчислювальних систем. – СПб: БХВ-Петербург, 2002.
10. Pacheco P.Parallel Programming With MPI (Доступні: зміст і приклади), див. www.parallel.ru).
11. Gropp W., Lusk E., Skjellum A. Using MPI (Книга доступна, див. www.parallel.ru).
12. Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.
Лекція №1
Питання
Паралелізм та розподілені обчислення
Області застосування і задачі паралельної обробки
Засоби для проведення паралельних обчислень
Рівні розпаралелення
Паралельні операції
Конвеєризація і паралелізм
Класифікація структур паралельної обробки
Основний сайт:www.parallel.ru
Паралелізм та розподіленість
Паралелізм – сукупність математичних, алгоритмічих, програмних і апаратних засобів, що забезпечують можливість пералельного виконання задачі.
Розподілені обчислення – сукупність протоколів обміну та незалежних апаратних засобів (комп’ютерів, серверів), що представляються користувачу єдиним обчислювачем, придатним для вирішення складної задачі
Області застосування і задачі паралельної обробки
Є коло обчислювальних задач, що вимагає більших обчислювальних ресурсів, ніж надає ПЕОМ. Для задач необхідно:
більша швидкодія;
· більший об’єм оперативної пам’яті;
· велике кількість інформації, що передається;
· обработка і зберігання великого об’єму інформації.
При наявності хоча б однієї з наведених вимог використання паралельної обробки оправдано.
Серед задач, що вирішуються на кафедрі ЕОМ під паралельну обробку найбільше підходять: розпізнавання і синтез мови, розпізнавання зображень (дисципліна: Проектування комп’ютерних засобів обробки сигнгалів та зображень, 5 курс).
Приклади:
Складні, багатовимірні задачі задачі, які необхідно розв’язати на протязі досить обмеженого часу, вимагають забезпечення великої швидкодії, наприклад - задачі прогнозу погоди. Область розв’язку (атмосфера) розбивається на окремі просторові зони, причому для розв’язку часових змін обчислень в кожній зоні повторюється багато разів. Якщо об’єм зони рівний 1 км3, то для моделювання 10 км шару атмосфери необхідно 5х108 таких зон. Припустимо, що обчислення в кожній зоні вимагає 200 операцій з плаваючою крапкою, тоді за один часовий крок необхідно виконати 1011 операцій з плаваючою крапкою. Для того, щоб провести розрахунок прогнозу погоди з передбачуванністю 10 днів з 10-ти хвилинним кроком в часу, ЕОМ продуктивністю 100 Mflops (108 операцій з плаваючою крапкою за секунду) необхідно 107 секунд чи понад 100 днів. Для того, щоб провести розрахунок за 10 хв, необхідна ЕОМ продуктивністю 1.7 Tflops (1.7X1012 операцій з плаваючою крапкою за секунду)
До категорії задач, що вимагають великого об’єму оперативної пам’яті, відносяться, наприклад, задачі гідро- і газодинаміки по розрахунку течій складної просторово-часової структури з врахуванням різних фізичних і хімічних процесів. Такі задачі є, як правило, багатвимірними, і розрахунок по кожному з напрямків хоча б для декількох точок вимагає оперативної пам’яті понад 10 Гбайт. В квантовій хімії неемпіричні розрахунки електронної структури молекул вимагають обчислювальних затрат, пропорційних N4 чи N5, де N умовно характеризує число молекул. Тому молекулярні системи вимужено досліджуються спрощено, з-за невистачання обчислювальних ресурсів.
Вимога забезпечення великої кількості інформації, що передаєтьсяхарактерна для задач гідро- і газодинаміки з змінюючими граничними умовами, коли обчислювальний алгоритм постійно вимагає підведення нової інформації; і задач економічної оптимізації, що описують поведінку системи, яка занурена в середовище з неперервно змінюючими властивостями, від яких залежить стан системи.
4. Проблема обробки і зберігання великого об’єму інформації характерна для задач астрономії, спектроскопії, біології, ядерної фізики.
Засоби для проведенняя паралельних обчислень
- апаратні
o засоби для проведення обчислень (обчислювальна техніка)
§ обчислювальна техніка, зібрана з стандартних комплектуючих
§ обчислювальна техніка, зібрана з спеціальних комплектуючих
o засоби візуалізації
o засоби для зберігання і обробки даних
· програмні
o програмні засоби загального призначення (операційнісистеми: стандартні бібліотеки, мови програмування, компілятори, профайлери, відлагоджувачі і т.п.)
o спеціальні програмні засоби: бібліотеки (PVM, MPI); засоби об’єднання ресурсів (Dynamite, Globus і ін.)