Paralelizam podataka

Paralelizam podataka je forma paralelne obrade koja se vrši preko više procesora u okruženjima za paralelnu obradu. Paralelna obrada se fokusira na distribuciju podataka na viže različitih čvorova paralelne obrade. Paralelizam podataka je suprotnost paralelizmu zatadataka (engl. task).

Opis

U multiprocesorskom sistemu izvršavanje jednog seta instrukcija (SIMD), paralelizam podataka se postiže kada svaki procesor izvršava isti zadatak na različitim delovima distribuiranih podataka. U nekim situacijama, jedna nit izbršenja kontroliše operacije na svim delovima podataka. U drugim situacijama, različite niti kontrolišu operaciju ali izvršavaju isti kod.

Na primer, razmatramo dvoprocesorski sistem (imamo procesore A i B) u paralelnom okruženju, i želimo da uradimo zadatak nad nekim podatkom d. Moguće je reći procesoru A da izvrši taj zadatak na jednom delu d i procesoru B da odradi drugi deo u isto vreme, što bi smanjilo vreme izvršavanja. Podaci mogu biti dodeljeni korišćenjem uslovnih iskaza kao što je opisano ispod. Kao specifičan primer, razmotrimo dodavanje dve matrice. U implementaciji paralelizma podataka, procesor A može da sabere sve elemente iz gornje polovine matrica, dok procesor B može da sabira sve elemente donje polovine matrica. Pošto dva procesora rade paralelno, posao koji se obavlja će se obaviti duplo brže nego kada bi korsitili jedan procesor.

Paralelizam podataka naglašava distribuiranu (paralelnu) prirodu podataka, za razliku od paralelizma zadataka. Većina realnih programskih grešaka se događaju negde između paralelizma zadataka i paralelizma podataka.

Primer

Program, koji je dole napisan u pseudokodu, primenjuje neku proizvoljnu operaciju. Ovde foo ilistruje paralelizam podataka na svakom elementu niza d.

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])

Ako se gorenavedeni primer izvrši na dvoprocesorskom sistemu kod će se izvršiti sledećim tokom:

• u SPMD sistemu, oba procesora će izvršavati kod.
• U paralelnom okruženju, oba procesora će imati pristup d-u.
• Pretpostavlja se da je mehanizam na mestu pri čemu će svaki procesor kreirati sopstvene kopije lower_limit-a i upper_limit-a nezavisnih od drugih.
• if nam služi da razlikujemo procesore. Procesor "a" će čitati ako je uslov if provere tačan. U suprotnom će čitati drugi procesor. Zbog toga će svaki procesor imati sopstvene vrednosti za lower_limit i upper_limit.
• Sada, oba procesora izvešavaju foo(d[i]), ali pošto jedan procesor ima vrednosti različite od granica, oni će vršiti operacije na različitim delovima d-a u isto vreme, čime će deliti zadatke među sobom. Ovo će, očigledno, biti brže nego kada bi se izvršavalo na jednom procesoru.

Ovaj koncept može da se generalizuje na bilo koji broj procesora. Međutim, kada se poveća broj procesora, može biti korisno da se rekonstruiše program na sličan način (gde bi cpuid bio ceo broj između 1 i broja procesora, i gde bi se ponašao kao jedinstveni identifikator za svaki procesor):

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

Na primer, na dvoprocesorskom sistemu, procesor A (cpuid 1) će vršiti operacije na neparnim ulaznim podacima dok će procesor B (cpuid 2) raditi sa parnim ulaznim podacima.

JVM Primer

Sličan prethodnom primeru, paralelizam podataka je moguće implementirati koristeći Java (Džava) virtuenu mašinu (JVM), koristeći Ateji PX, ekstenziju Jave.

Kod ispod ilustruje paralelizam podataka na JVM: Moguće je odrediti broj grana u paralelnoj kompoziciji. Ovo se koristi radi izvršavanja || operatora na svim elementima niza ili kolekcije:

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

The equivalent sequential code would be:

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

Kvantifikacija može da uvede proizvoljan broj iteratora i filtera. Evo kako bi ažurirali gornji levi trougao matrice:

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

Vidi još

• Paralelizam na nivou bita
• Paralelizam na nivou naredbe

Literatura

• 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.