Паралелізм даних

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

Наприклад, є 2-процесорна система (CPU A і B) в паралельному середовищі, і ми хочемо, виконати завдання над даними d. Можна задати CPU A виконувати це завдання на одній частині даних d, і CPU B одночасно на іншій, тим самим знижуючи тривалість виконання. Ці дані можуть бути задані за допомогою умовних операторів, як описано нижче. Як конкретний приклад розглянемо додавання двох матриць. В паралельній реалізації даних, CPU A може додати всі елементи з верхньої половини матриць, в той час як CPU B буде додавати всі елементи з нижньої половини матриць. Оскільки два процесори працюють паралельно, робота над матрицями забере в 2 рази менше часу, ніж виконання цього завдання на одному процесорі. Паралелізм даних підкреслює розподіленої (розпаралелювати) характер даних, на відміну від обробки (паралелізм завдань).

Більшість реальних програм впасти десь на континуумі між паралелізму задач і паралелізму даних.

Програма нижче виражена псевдокодом-який виконує якусь довільну операцію, foo, над кожним елементом в масиві d-який ілюструє паралельність даних:[1 1]

if CPU = "a"
   lower_limit := 1
   upper_limit := round(d.length/2)
else if CPU = "b"
   lower_limit := round(d.length/2) + 1
   upper_limit := d.length

for i from lower_limit to upper_limit by 1
   foo(d[i])

Якщо у прикладі вище програма виконується на 2-процесорній системі середовище може виконати його наступним чином:

• У системі SPMD, обидва процесори будуть виконувати код.
• У паралельному середовищі, обидва будуть мати доступ до d.
• Механізм передбачує знаходження в місці де кожен процесор може створити свою копію lower_limit і upper_limit які є незалежними.
• Оператор if розмежовує роботу процесорів. CPU A буде зчитувати true в if; а CPU B буде зчитувати true в else if, таким чином вони мають свої власні значення lower_limit і upper_limit.
• Зараз, обидва процесори виконують foo(d[i]), але, оскільки кожен процесор має різні значення меж, вони працюють на різних частинах d одночасно, тим самим розподіляють завдання між собою. Очевидно, що вони будуть виконувати це швидше, ніж один процесор.

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

for i from cpuid to d.length by number_of_cpus
   foo(d[i])

Наприклад, на 2-процесорній системі CPU A (cpuid 1) буде працювати на непарних значеннях і CPU B (cpuid 2) працюватиме на парних значеннях.

• Паралелізм на рівні команд
• Типи паралельних обчислень

1. Деякі вхідні дані (наприклад d.length дорівнює 1 і round знаходиться близько нуля [це лише приклад, немає жодних вимог для якого типу округлення це використовувати]) призведе до lower_limit буде більше upper_limit, це призведе до негайного виходу (тобто відбудеться нульова ітерація).

• Hillis, W. Daniel and Steele, Guy L., Data Parallel Algorithms Communications of the ACM December 1986
• Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X