Оцінка ефективності паралельних обчислень. Загальні принципи побудови паралельних алгоритмів і програм

Основи паралельних алгоритмів

Паралелізм – сукупність математичних, алгоритмічих, програмних і апаратних засобів, що забезпечують можливість пералельного виконання задачі.

Розподілені обчислення – сукупність протоколів обміну та незалежних апаратних засобів (комп’ютерів, серверів), що представляються користувачу єдиним обчислювачем, придатним для вирішення складної задачі.

Є коло обчислювальних задач, що вимагає більших обчислювальних ресурсів, ніж надає ПЕОМ. Для вирішення цих задач необхідно:

• більша швидкодія;

• більший об’єм оперативної пам’яті;

• велике кількість інформації, що передається;

• обработка і зберігання великого об’єму інформації.

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

Серед задач, підпадаючих під паралельну обробку найбільше підходять: розпізнавання і синтез мови, розпізнавання зображень. А саме:

1. Складні, багатовимірні задачі, які необхідно розв’язати на протязі досить обмеженого часу, вимагають забезпечення великої швидкодії, наприклад – задачі прогнозу погоди. Область розв’язку (атмосфера) розбивається на окремі просторові зони, причому для розв’язку часових змін обчислень в кожній зоні повторюється багато разів. Якщо об’єм зони рівний 1 км3 , то для моделювання 10 км шару атмосфери необхідно 5х108 таких зон. Припустимо, що обчислення в кожній зоні вимагає 200 операцій з плаваючою крапкою, тоді за один часовий крок необхідно виконати 1011 операцій з плаваючою крапкою. Для того, щоб провести розрахунок прогнозу погоди з передбачуванністю 10 днів з 10-ти хвилинним кроком в часу, ЕОМ продуктивністю 100 Mflops (108 операцій з плаваючою крапкою за секунду) необхідно 107 секунд чи понад 100 днів. Для того, щоб провести розрахунок за 10 хв, необхідна ЕОМ продуктивністю 1.7 Tflops (1.7X1012 операцій з плаваючою крапкою за секунду);

2. До категорії задач, що вимагають великого об’єму оперативної пам’яті, відносяться, наприклад, задачі гідро- і газодинаміки по розрахунку течій складної просторово-часової структури з врахуванням різних фізичних і хімічних процесів. Такі задачі є, як правило, багатвимірними, і розрахунок по кожному з напрямків хоча б для декількох точок вимагає оперативної пам’яті понад 10 Гбайт. В квантовій хімії неемпіричні розрахунки електронної структури молекул вимагають обчислювальних затрат, пропорційних N4 чи N5 , де N умовно характеризує число молекул. Тому молекулярні системи вимужено досліджуються спрощено, через недостаток обчислювальних ресурсів;

3. Вимога забезпечення великої кількості інформації, що передається, характерна для задач гідро- і газодинаміки з змінними граничними умовами, коли обчислювальний алгоритм постійно вимагає введення нової інформації; і задач економічної оптимізації, що описують поведінку системи, яка занурена в середовище з неперервно змінними властивостями, від яких залежить стан системи;

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

Засоби для проведенняя паралельних обчислень бувають:

- апаратні:

• засоби для проведення обчислень (обчислювальна техніка);

• обчислювальна техніка, зібрана з стандартних комплектуючих;

• обчислювальна техніка, зібрана з спеціальних комплектуючих ;

• засоби візуалізації;

• засоби для зберігання і обробки даних;

- програмні:

• програмні засоби загального призначення (операційнісистеми: стандартні бібліотеки, мови програмування, компілятори, профайлери, відлагоджувачі і т.п.);

• спеціальні програмні засоби: бібліотеки (PVM, MPI); засоби об’єднання ресурсів (Dynamite, Globus і ін.).

Рівні розпаралелювання Класифікація паралельності за рівнями, що відрізняються показниками абстрактності розпаралелювання задач наведена в табл.  Чим "глибше" рівень, в якому наступає паралельність, тим детальнішим, малоелементнішим буде розпаралелювання, що торкається елементів програми (інструкція, елементи інструкції тощо). Чим вище розміщено рівень абстракції, тим більші блоки має паралельність.

Кожний рівень має повністю piзні аспекти паралельного оброблення. Методи i конструктиви даного рівня обмежуються тільки цим рівнем i не можуть бути поширені на інші рівні. Найбільший інтерес викликають рівень процедур (великоблокова, асинхронна паралельність) та рівень арифметичних виразів (малоелементна, детальна або масивна синхронна паралельність).

Програмний рівень

На цьому найвищому рівню одночасно (або щонайменше розподілено за часом) виконуються комплексні програми. Машина, що виконує ці програми, не повинна бути паралельною ЕОМ, досить того, що в ній наявна багатозадачна операційна система (наприклад, реалізована як система розподілу часу). В цій системі кожному користувачеві відповідно до його пріоритету планувальник (Scheduler) виділяє відрізок часу визначеної тривалості. Користувач одержує ресурси центрального процесорного блоку тільки впродовж короткого часу, а потім стає в чергу на обслуговування.

У тому випадку, коли в ЕОМ недостатня кількість процесорів для всіх користувачів (або процесів), що, як правило, найбільш імовірно, в системі моделюється паралельне обслуговування користувачів за допомогою "квазіпаралельних" процесів.

Рівень процедур

На цьому piвні різні розділи однієї і тієї самої програми мають виконуватися паралельно. Ці розділи називаються "процесами" i відповідають приблизно послідовним процедурам. Проблеми поділяються на суттєво незалежні частини так, щоб по можливості рідше виконувати операції обміну даними між процесами, які потребують відносно великих витрат часу. В різних галузях застосування стає ясно, що цей рівень паралельності ні в якому разі не обмежується розпаралелюванням послідовних програм. існує великий ряд проблем, які потребують паралельних структур цього типу навіть тоді, коли так само, як i на програмному piвні, у користувача є тільки один процесор.

Застосування (основне) – загальне паралельне оброблення інформації, де застосовується поділ вирішуваної проблеми на паралельні задачі – частини, які вирішуються багатьма процесорами з метою підвищення обчислювальної продуктивності.

Рівень арифметичних виразів

Арифметичні вирази виконуються паралельно покомпонентно, причому в суттєво простіших синхронних методах. Якщо, наприклад, йдеться про арифметичний вираз додавання матриць, то він синхронно розпаралелюється дуже просто тому, що кожному процесорові підпорядковується один елемент матриці.

При застосуванні n*n процесорних елементів можна одержати суму двох матриць порядку n*n за час виконання однієї операції складання (за винятком часу, потрібного на зчитування та запис даних). Цьому рівню притаманні засоби векторизації та так званої паралельності даних. Останнє поняття пов'язане з детальністю розпаралелювання, а саме – з його поширенням на оброблювані дані. Майже кожному елементу даних тут підпорядковується свій процесор, завдяки чому ті дані, що в машині фон Неймана були пасивними, перетворюються на “активні обчислювальні пристрої”.

Рівень двійкових розрядів

На цьому piвні відбувається паралельне виконання бітових операцій в межах одного слова. Паралельність на рівні бітів можна знайти в будь-якому працюючому мікропроцесорі. Наприклад, у 8-розрядному арифметико-логічному пристрої побітова обробка виконується паралельними апаратними засобами.