Paral·lelisme de Dades
| Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
| S'ha proposat fusionar aquest article a «Computació paral·lela». (Vegeu la discussió, pendent de concretar). Data: 2018 |
El paral·lelisme de dades és un mètode de paral·lelització el qual en lloc de dependre del procés o de la concurrència de la tasca, està relacionat tant amb el flux com amb l'estructura de la informació. Distribueix les dades en diferents nodes i aquests operen sobre aquestes dades en paral·lel.[1] Una analogia podria ser una fàbrica d'automòbils en la que dues línies de muntatge produiran dues vegades més de vehicles... Pot ser aplicat sobre dades com vectors o matrius que, essent grans o amb gran càrrega de còmput, facilitin poder-se distribuir entre diferents nodes. Així s'assoleix un millor temps d'execució. En paraules més tradicionals, podríem equiparar el concepte del paral·lelisme de dades com a Divideix i Venceràs.
L'objectiu principal del paral·lelisme de dades és escalar el rendiment del processament en funció de la capacitat de descompondre el conjunt de dades en fluxos de processament simultanis, tot realitzant el mateix conjunt d'operacions. Sempre que no hi hagi dependències, un vector de N elements pot ser dividit equitativament en Y processadors definits per a accelerar-ne el temps final d'execució. Per exemple, si volem sumar tots els elements d'un vector de 100 posicions i disposem de 4 processadors, podem utilitzar el paral·lelisme de dades per a balancejar la càrrega de treball en 25 posicions de l'array per a cada processador. D'aquesta manera haurem aconseguit disminuir la mida de les dades a realitzar-hi operacions de 100 a 25.
Contrasta amb paral·lelisme de tasques com un altre mètode de paral·lelisme.[2]
Definició modifica
En un sistema multiprocessador executant un sol tipus d'instrucció (SIMD), el paral·lelisme de dades és assolit quan cada processador realitza la mateixa tasca en diferents fragments de les dades particionades. Depenent de les arquitectures o bé en diferents situacions, un procés pot controlar operacions en diferents fragments de dades o bé tenir control a nivell d'operació però executar el mateix codi.
Un clar exemple és el que trobem a la imatge superior, on N és la mida de les dades i Op l'operació a realitzar en cada una d'elles.
Història modifica
Fins al 1960, tots els càlculs es feien seqüencialment, però el creixement de la grandària mitja de les dades a tractar va portar a explorar nous horitzons més enllà del càlcul ordenat lineal. El concepte de la computació paral·lela doncs, neix el 1960 amb el desenvolupament de la màquina de Solomon, la qual fou dissenyada per a treballar amb grans vectors orientats a càlculs matemàtics. Va ser llavors quan es va començar a adaptar el concepte de la computació paral·lela, que aconseguia millorar els temps d'execució dividint i balancejant la potència de còmput en diferents nuclis. En aquest punt es va requerir l'ús dels originalment anomenats Array Processors.[3] Aquests processadors disposaven d'una arquitectura totalment orientada al processament de vectors i matrius. D'aquesta manera incloïen un nombre elevant de processadors treballant simultàniament, cadascun tractant un element del vector. Aquest mètode va permetre aplicar una operació en paral·lel en múltiples elements, cosa que òbviament donava millors resultats de temps d'execució respecte el tractament de vectors seqüencialment.
Els Array Processors han evolucionat fins a les actualment anomenades GPU (Graphic Processing Unit), les quals tenen un funcionament semblant a l'hora d'interactuar elements per separat amb una sola instrucció, però han escalat enormement en la potència i nombre de nuclis, els quals ja no són processadors com a definició.
Diferències entre paral·lelisme de dades i de tasques modifica
El paral·lelisme de dades és una forma d'execució paral·lela d'una aplicació en diversos processadors. Es centra en distribuir dades a través de diferents nodes en l'entorn d'execució paral·lela i permetre subcompliments simultanis d'aquestes dades distribuïdes a través dels diferents nodes computacionals. Normalment, s'aconsegueix en mode SIMD (Single Instruction, Multiple Data) i pot tenir un controlador únic que controli les operacions de dades paral·leles o múltiples fils que funcionen de la mateixa manera en els nodes de còmput individuals (SPMD).
En canvi, el paral·lelisme de les tasques se centra a distribuir fils d'execució paral·lels a través de nodes de computació paral·lels. Aquests fils poden executar el mateix o diferents fils. Aquests fils intercanvien missatges mitjançant memòria compartida o missatges de comunicació explícits, segons l'algorisme paral·lel. En el cas més general, cadascun dels fils d'un sistema de tasques paral·leles pot realitzar tasques completament diferents però coordinar-se per resoldre un problema específic. En el cas més simplista, tots els fils poden executar el mateix programa i diferenciar-se segons el seu node-id per realitzar qualsevol variació en la tasca-responsabilitat. Els algorismes de tasques paral·leles més habituals segueixen el model Màster-Treballador, on hi ha un únic mestre i diversos treballadors. El mestre distribueix el càlcul a diferents treballadors segons les regles de programació i altres estratègies d'assignació de tasques.
MapReduce es troba dins de la categoria d'arquitectures SPMD del paral·lelisme de dades.
| Paral·lelisme de dades | Paral·lelisme de tasques |
|---|---|
| Mateixa operació és executada sobre diferents fragments de dades | Diferents operacions son executades sobre les mateixes dades o bé diferents fragments de dades |
| Computació síncrona | Computació asíncrona |
| El nivell de paral·lelisme depèn de la mida de les dades d'entrada | El nivell de paral·lelisme depèn del nombre de tasques independents a realitzar |
| Dissenyat per a optimitzar el balanceig de càrrega de treball en arquitectures multiprocessador | El balanceig de càrrega depèn de molts altres factors com ara bé els algoritmes de scheduling o del HW existent |
GPU modifica
Les GPU, tal com s'ha anomenat anteriorment, són un clar exemple de com aprofitar el paral·lelisme de dades per a minimitzar el temps d'execució d'una funció concreta. Són utilitzades en gran part per al tractament i generació d'imatges tal com indica el seu nom (Graphic Processing Unit). Si per generar una imatge en un processador haguéssim de tractar cada píxel de manera seqüencial, l'esforç i el temps que trigaríem seria massa gran, d'aquesta manera les GPU i juntament amb el paral·lelisme de dades són els que han permès que es tractin les imatges en ordinadors en grans velocitats. Això és el que ha permès que s'hagin arribat a crear videojocs amb uns gràfics tant semblants als que percebem a la vida real.
En un sistema multiprocessador que executa un únic conjunt d'instruccions (SIMD), s'aconsegueix paral·lelisme de dades quan cada processador realitza la mateixa tasca, en diferents porcions de les dades totals. En algunes ocasions, un sol fil d'execució controla les operacions de totes les porcions de les dades. En d'altres, diferents fils controlen l'operació, però alhora executen el mateix codi. Un exemple d'això seria la multiplicació de matrius y l'afegit de manera seqüencial; com es presenta a l'exemple.
Aplicacions modifica
El paral·lelisme de dades troba les seves aplicacions en una gran varietat de camps des de la física, química, biologia, ciències dels materials o processament de senyals. En general, la ciència adopta el paral·lelisme de dades per a simular models els quals, sense l'existència del paral·lelisme en seria inviable la simulació. Si tractem cada molècula per separat en un model de simulació en un processador seqüencial, no podrem assolir ni molt menys els mateixos resultats que utilitzant paral·lelisme de dades. Ja que tractant cada molècula independentment ens acostarem més al resultat que tindríem en un estat real.
Fora dels camps de la ciència, el paral·lelisme de dades pren força en el processament gràfic tal com hem vist en l'anterior apartat amb l'exemple de les GPU. Tenint els seus punts forts en codificació de vídeo i imatges, processament gràfic o comunicacions sense fils.
Algorismes Paral·lels: Cannon's Algorithm modifica
Aquest tipus d'algorisme paral·lel és molt freqüent en aplicacions que requereixen una operació de transposició d'àlgebra lineal o algun tipus de multiplicació de matrius.
L'algorisme de Cannon és un algorisme de multiplicació matricial per al paral·lelisme de memòria distribuïda dissenyat per a matrius denses i que depèn en gran manera de l'encaminament de permutació.
Llei d'Amdahl modifica
S'utilitza per trobar la màxima millora esperada del sistema total quan solament part del sistema és millorada. Sovint s'utilitza un càlcul paral·lel per predir la màxima acceleració teòrica utilitzant múltiples processadors.
Llei de Gustafson modifica
Estableix que qualsevol problema suficientment gran pot ser eficientment paral·lelitzat, donant el speedup teòric en la latència de l'execució d'un programa que pot esperar-se d'un sistema on els seus recursos han millorat. Està molt lligada a la Llei d'Amdahl.
Exemple: Càlcul del nombre PI modifica
Estratègia utilitzada
- Es divideix el bucle en parts iguals.
- Cada tasca realitza de forma independent el seu treball.
- S'utilitza un model SPMD (Single Program Multiple Data).
- Una tasca actua com a mestre per recopilar resultats i calcular el valor de PI.
Tenint en compte el mètode Monte Carlo d'aproximació de la PI el pseudocodi seria:
npoints = 10000
circle_count = 0
p = number of tasks
num = npoints/p
find out if I am MASTER or WORKER
do j = 1,num
generate 2 random numbers between 0 and 1
xcoordinate = random1
ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do
if I am MASTER
receive from WORKERS their circle_counts
compute PI (use MASTER and WORKER calculations)
else if I am WORKER
send to MASTER circle_count
endif
Eines per al paral·lelisme de dades modifica
El paral·lelisme de dades pot o no ser transparent cap al programador. Hi ha llenguatges i compiladors que poden paral·lelitzar algunes operacions, però si el programador vol tenir el control de les seccions paral·leles ha d'utilitzar certes eines sobre els llenguatges. A continuació es llisten algunes de les diferents eines que permeten especificar un paral·lelisme a nivell de dades, malgrat algunes d'elles permetin també el paral·lelisme a nivell de tasques.
CilkPlus
ArBB
Referències modifica
| Aquest article té bibliografia, però no se sap quina referència verifica cada part. Podeu millorar aquest article assignant cadascuna d'aquestes obres a frases o paràgrafs concrets. |
- ↑ Hillis, W. Daniel; Steele, Guy L. «Data Parallel Algorithms» (en anglès). Communications of the ACM, 1986.
- ↑ Błażewicz, Jacek; Ecker, Klaus; Plateau, Brigitte; Trystram, Denis «Handbook on Parallel and Distributed Processing» (en anglès). Springer-Verlag Berlin Heidelberg, 2000.
- ↑ Blelloch, Guy E «Vector Models for Data-Parallel Computing» (en anglès). MIT Press, 1990.