Лекція №1 Паралельні та розподілені обчислення Мета курсу - вивчення: основних методів, алгоритмів, принципів побудови структур реалізації паралельних та розподілених обчислень, набуття початкових практичних навиків проектування таких засобів. Результат вивчення – знання основних методів, алгоритмів і засобів паралельної та розподіленої обробки інформації, засобів програмування паралельних та розподілених обчислень та їх реалізації, складу апаратного та програмного забезпечення обчислювальних систем з засобами паралельної та розподіленої обробки і класів мов програмування високого рівня для них. Основні питання: Паралельні обчислення: - вступ до курсу паралельних обчислень; методи оцінки продуктивності паралельних алгоритмів; мережі Петрі; - розробка паралельного алгоритму; - структури зв’язку між процесорами; - основні класи паралельних комп’ютерів; - схеми паралельних алгоритмів задач; мови паралельного програмування. Розподілені обчислення: - вступ до організації розподілених обчислень і розподілених систем; - організація протоколів обміну в розподілених ситсемах; - алгоритми маршрутизації; - розподілені обчислення в локальних мережах Оцінка знань: Лабораторні і практичні заняття РГР КР Залік Разом балів
40 10 20 30 100
Література Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002. Ортега Дж. Введение в параллельные і векторные методы решения линейных систем. М.:Мир, 1991. Программирование на параллельных обчислювальних системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991. Тройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991. Векторизация программ: теория, методы, реализация: Пер. с англ. і нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999 Вальковский В.А. Распараллеливание алгоритмов і програм. Структурный подход-М.:Радио і связь, 1989. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных обчислювальних систем. – СПб: БХВ-Петербург, 2002. Pacheco P. Parallel Programming With MPI (Доступні: зміст і приклади), див. www.parallel.ru). Gropp W., Lusk E., Skjellum A. Using MPI (Книга доступна, див. www.parallel.ru). Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 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 умовно характеризує число молекул. Тому молекулярні системи вимужено досліджуються спрощено, з-за невистачання обчислювальних ресурсів. Вимога забезпечення великої кількості інформації, що передається характерна для задач гідро- і газодинаміки з змінюючими граничними умовами, коли обчислювальний алгоритм постійно вимагає підведення нової інформації; і задач економічної оптимізації, що описують поведінку системи, яка занурена в середовище з неперервно змінюючими властивостями, від яких залежить стан системи. Проблема обробки і зберігання великого об’єму інформації характерна для задач астрономії, спектроскопії, біології, ядерної фізики. 3. Засоби для проведенняя паралельних обчислень - апаратні засоби для проведення обчислень (обчислювальна техніка) обчислювальна техніка, зібрана з стандартних комплектуючих обчислювальна техніка, зібрана з спеціальних комплектуючих засоби візуалізації засоби для зберігання і обробки даних програмні програмні засоби загального призначення (операційнісистеми: стандартні бібліотеки, мови програмування, компілятори, профайлери, відлагоджувачі і т.п.) спеціальні програмні засоби: бібліотеки (PVM, MPI); засоби об’єднання ресурсів (Dynamite, Globus і ін.)
4. Рівні розпаралелювання Класифікація паралельності за рівнями, що відрізняються показниками абстрактності розпаралелювання задач наведена в табл.1. Чим "глибше" рівень, в якому наступає паралельність, тим детальнішим, малоелементнішим буде розпаралелювання, що торкається елементів програми (інструкція, елементи інструкції тощо). Чим вище розміщено рівень абстракції, тим більші блоки має паралельність. Таблиця 1. Рівні паралельності Рівні Об’єкт обробки Приклад системи
Дрібноблоковий Біт-рівень В межах інструкції Машина фон Ноймана
Кожний рівень має повністю piзні аспекти паралельного оброблення. Методи i конструктиви даного рівня обмежуються тільки цим рівнем i не можуть бути поширені на інші рівні. Найбільший інтерес викликають рівень процедур (великоблокова, асинхронна паралельність) та рівень арифметичних виразів (малоелементна, детальна або масивна синхронна паралельність). Програмний рівень На цьому найвищому рівню одночасно ( або щонайменше розподілено за часом) виконуються комплектні програми (рис.1.). Машина, що виконує ці програми, не повинна бути паралельною ЕОМ, досить того, що в ній наявна багатозадачна операційна система (наприклад, реалізована як система розподілу часу). В цій системі кожному користувачеві відповідно до його пріоритету планувальник (Scheduler} виділяє відрізок часу різної тривалості. Користувач одержує ресурси центрального процесорного блоку тільки впродовж короткого часу, а потім стає в чергу на обслуговування. У тому випадку, коли в ЕОМ недостатня кількість процесорів для bcix користувачів (або процесів), що, як правило, найбільш імовірно, в системі моделюється паралельне обслуговування користувачів за допомогою "квазіпаралельних" процесів.
Часові інтервали
Рис. 1. Паралельність на програмному piвні. Рівень процедур На цьому piвні різні розділи однієї і тієї самої програми мають виконуватися паралельно. Ці розділи називаються "процесами" i відповідають приблизно послідовним процедурам. Проблеми поділяються на суттєво незалежні частини так, щоб по можливості рідше виконувати операції обміну даними між процесами, які потребують в
