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

1. Апаратні засоби:

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

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

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

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

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

2. Програмні засоби:

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

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

 

Рівні розпаралелювання

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

Таблиця 1.1 Рівні паралельності

Зернистість	Рівні	Об’єкт обробки	Приклад системи
Великоблокова	Програмний	Робота/Задача	Мультизадачна ОС
Процедурний	Процес	MIMD-система
Дрібноблокова	Рівень формул	Інструкція	SIMD-система
Біт-рівень	В межах інструкції	Машина фон Ноймана

Методи i конструктиви даного рівня обмежуються тільки цим рівнем i не можуть бути поширені на інші рівні.

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

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

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

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

На цьому рівні різні частини ("процеси") однієї і тієї ж програми виконуються паралельно; кількість операцій обміну даними між процесами повинна бути мінмальною.

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

Рівень формул (арифметичних виразів)

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

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

Біт – рівень

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

Паралельні операції

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

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

Одномісцеві операції

а). Скаляр –> скаляр Послідовне виконання

Приклад 9‑>3 "Корінь"

б). Скаляр ‑> вектор Розмноження числової величини

Приклад 9‑>(9,9,9,9) "Broadcast"

в). Вектор ‑> скаляр Редукція вектора в скаляр

Приклад (1,2,3,4)‑>10 "Складання"

(із припущенням, що довжина вектора не змінюється)

г-1) Локальна векторна покомпонентна операція.

Приклад: (1,4,9,16) ‑> (1,2,3,4) "Корінь"

г-2) Глобальна векторна операція з перестановками.

Приклад: (1,2,3,4) ‑> (2,4,3,1) "Заміна місць компонент вектора"

г-3) Глобальна векторна операція (часто складається з простих операцій)

Приклад: (1,2,3,4) ‑> (1,3,6,10) "Часткові суми"

Двомісцеві операції

д) (скаляр, скаляр)‑> вектор Послідовне виконання

Приклад: (1,2)‑>3 "Скалярне додавання"

е) (скаляр, вектор)‑>вектор Покомпонентне застосування операцій над скаляром i вектором

Приклад: (3,(1,2,3,4))‑>(4,5,6,7) "Додавання скаляра з вектором"

Операція виконується як послідовність операцій б) та є)

додавання векторів:

(3,3,3,3)

+

(1,2,3,4)

(4,5,6,7)

є ) (вектор, вектор) ‑> вектор Покомпонентне застосування операції над двома векторами

Приклад: ((1,2,3,4),(0,1,,3,2)) ‑> (1,3,6,6) "Додавання векторів"