Паралелизам података

Паралелизам података је форма паралелне обраде која се врши преко више процесора у окружењима за паралелну обраду. Паралелна обрада се фокусира на дистрибуцију података на виже различитих чворова паралелне обраде. Паралелизам података је супротност паралелизму затадатака (енгл. task).

Опис

У мултипроцесорском систему извршавање једног сета инструкција (SIMD), паралелизам података се постиже када сваки процесор извршава исти задатак на различитим деловима дистрибуираних података. У неким ситуацијама, једна нит избршења контролише операције на свим деловима података. У другим ситуацијама, различите нити контролишу операцију али извршавају исти код.

На пример, разматрамо двопроцесорски систем (имамо процесоре А и Б) у паралелном окружењу, и желимо да урадимо задатак над неким податком d. Могуће је рећи процесору А да изврши тај задатак на једном делу d и процесору Б да одради други део у исто време, што би смањило време извршавања. Подаци могу бити додељени коришћењем условних исказа као што је описано испод. Као специфичан пример, размотримо додавање две матрице. У имплементацији паралелизма података, процесор А може да сабере све елементе из горње половине матрица, док процесор Б може да сабира све елементе доње половине матрица. Пошто два процесора раде паралелно, посао који се обавља ће се обавити дупло брже него када би корситили један процесор.

Паралелизам података наглашава дистрибуирану (паралелну) природу података, за разлику од паралелизма задатака. Већина реалних програмских грешака се догађају негде између паралелизма задатака и паралелизма података.

Пример

Програм, који је доле написан у псеудокоду, примењује неку произвољну операцију. Овде foo илиструје паралелизам података на сваком елементу низа d.^{[nb 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])

Ако се горенаведени пример изврши на двопроцесорском систему код ће се извршити следећим током:

у SPMD систему, оба процесора ће извршавати код.
У паралелном окружењу, оба процесора ће имати приступ d-у.
Претпоставља се да је механизам на месту при чему ће сваки процесор креирати сопствене копије lower_limit-а и upper_limit-а независних од других.
if нам служи да разликујемо процесоре. Процесор "a" ће читати ако је услов 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])

На пример, на двопроцесорском систему, процесор А (cpuid 1) ће вршити операције на непарним улазним подацима док ће процесор Б (cpuid 2) радити са парним улазним подацима.

JVM Пример

Сличан претходном примеру, паралелизам података је могуће имплементирати користећи Јава (Џава) виртуену машину (JVM), користећи Ateji PX, екстензију Јаве.

Код испод илуструје паралелизам података на JVM: Могуће је одредити број грана у паралелној композицији. Ово се користи ради извршавања || оператора^[1] на свим елементима низа или колекције:

[
   // инкрементира све елементе низа паралелно
|| (int i: N) array[i]++;
]

The equivalent sequential code would be:

[
   // инкрементира све елементе низа један за другим
   for(int i: N) array[i]++;
]

Квантификација може да уведе произвољан број итератора и филтера. Ево како би ажурирали горњи леви троугао матрице:

[
||(int i:N, int j:N, if i+j<N) matrix[i][j]++;
]

Види још

Белешке

^ Неки подаци које уносимо (нпр. када d.length дође до 1 и round заокружи на 0) могу довести да lower_limit буде већи од upper_limit. Претпоставља се да ће доћи до изласка из петље одмах када се ово догоди.

Референце

^ http://www.ateji.com/px/patterns.html#data Архивирано на сајту Wayback Machine (17. децембар 2013) Data Parallelism using Ateji PX, an extension of Java

Литература

Hillis, W. Daniel; Steele, Guy L. (1986). „Data parallel algorithms”. Communications of the ACM. 29 (12): 1170—1183. S2CID 2315965. doi:10.1145/7902.7903. Communications of the ACM December 1986
Blelloch, Guy E. (1990). Vector Models for Data-Parallel Computing. MIT Press. ISBN 978-0-262-02313-9.

[1] Неки подаци које уносимо (нпр. када d.length дође до 1 и round заокружи на 0) могу довести да lower_limit буде већи од upper_limit. Претпоставља се да ће доћи до изласка из петље одмах када се ово догоди.

[2] ttp://www.ateji.com/px/patterns.html#data Архивирано на сајту Wayback Machine (17. децембар 2013) Data Parallelism using Ateji PX, an extension of Java

[nb 1]

[1]