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

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

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

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

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

 

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

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

Прості операції над векторами, наприклад складання двох векторів, можуть бути виконані безпосередньо синхронно i паралельно. У цьому випадку можна кожному елементу вектора підпорядкувати один процесор. При складніших операціях, таких як формування Bcix часткових сум, побудова ефективного паралельного алгоритму є не зовсім очевидною справою. Далі розрізняються одномісцеві (монадні) та двомісцеві (діадні) операції 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,і) "Заміна місць компонент вектора"

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

Приклад: (і,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)

3‑>(4,5,6,7)

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

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

 

Покажемо застосування цих операцій на простому прикладі: йдеться про обчислення скалярного добутку двох векторів. Цей результат можна одержати простим послідовним застосуванням базових операцій є) (тут - по-компонентне множення двох векторів) i в) - (редукція одного вектора в один скаляр (тут - за допомогою складання).

Приклад: Скалярний добуток

((1,2,3),(4,2,1))®(4,4,3)® 11