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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Паралелізм даних є формою розпаралелювання обчислень на кількох процесорах в паралельно обчислювальних середовищах. Паралелізм даних фокусується на поширенні даних через різні паралельні обчислювальні вузли. Це є відмінність в паралелізмі завдань як ще одна форма паралелізму.

Опис[ред.ред. код]

У багатопроцесорній системі, що проводить один набір інструкцій (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, це призведе до негайного виходу (тобто відбудеться нульова ітерація).

Посилання[ред.ред. код]