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

Інший вид паралельності виникає з аналізу математичних операцій над окремими елементами даних або над групами даних. Розрізняють скалярні дані, операції над якими виконуються послідовно, 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) "Додавання векторів"

Основні принципи паралелізму (розпаралелення)

Розпаралелити кожну задачу можна не єдиним способом. Тому доцільно розглянути алгоритми можливого розпаралелення типових задач незалежно від конкретної програмної і платформенної реалізації. В загальному випадку процедура розпаралелення розіб’ється на 3 етапи:

- розбиття задачі на незалежні під задачі;

- призначення конкретних процесорів для виконання кожної під задачі;

- збирання результатів роботи окремих процесорів.