En informàtica, un model de programació paral·lela és una abstracció de l'arquitectura informàtica paral·lela, amb la qual cosa és convenient expressar algorismes i la seva composició en programes. El valor d'un model de programació pot ser jutjat per la seva generalitat, es pot expressar una sèrie de problemes diferents per a una varietat de arquitectures diferents, i el seu rendiment, amb quina eficiència poden executar-se.Skillicorn, David B., "Models for practical parallel computation", International Journal of Parallel Programming, 20.2 133–158 (1991), La implementació d'un model de programació paral·lel pot prendre la forma d'una biblioteca invocada a partir d'un llenguatge seqüencial, com a extensió a un llenguatge existent o com un llenguatge completament nou.
Per entendre la diferència que hi ha entre els models de programació seqüencial i paral·lel, en farem una breu descripció de cadascun:
Computació sèrie: Es diu que un programa s'executa de forma seqüencial quan tenim un problema que es descompon en instruccions discretes, on aquestes instruccions s'executen una rere l'altra. Aquestes instruccions s'executen en un sol processador el qual solament pot executar una instrucció en qualsevol moment. Computació paral·lela: Es diu que un programa s'executa de forma paral·lela quan utilitza de forma simultània múltiples recursos per a resoldre un problema. Per aconseguier-ho, el problema s'hha de dividir en parts discretes que es poden resoldre simultàniament. Cada part del problema es descompon en una sèrie d'instruccions on aquestes instruccions s'executen de forma simultània en diferents processadors. Per a que un programa s'executi correctament de forma paral·lela, s'utilitzen també mecanismes de control i de coordinació.
És important que hi hagi un consentiment entre cada un dels models de programació, ja que permet que el software desenvolupat pugui executar-se en diferents arquitectures. Per arquitectures de programació seqüencial es puguin utilitzar el model de Von Neumann, ja que proporcionin un pont eficaç entre hardware i software, el que significa que llenguatges d'alt nivell poden compilar-se eficientment i es poden implementar de manera eficient en el hardware.Leslie G. Valiant, "A bridging model for parallel computation", Communications of the ACM, Volume 33, Issue 8, August, 1990, pages 103–111.
Conceptes i terminologia Els models de programació paral·lels estan estretament relacionats amb els models de computació. Un model de computació paral·lela és una abstracció que s'utilitza per analitzar el cost dels processos computacionals, però no necessàriament ha de ser pràctica, ja que es pot implementar de manera eficaç en hardware i / o programari. Un model de programació, en canvi, implica específicament les consideracions pràctiques de la implementació de maquinari i programari.Skillicorn, David B., and Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys, 30.2 123–169 (1998),
Arquitectura Von Neumann miniatura|Arquitectura de Von Neumann. Anomenada pel matemàtic hongarès John Von Neumann, que va escriure per primera vegada els requisits generals d'un ordinador electrònic en els seus articles de l'any 1945.
El disseny de la seva arquitectura consisteix en:
Una unitat de control Una unitat aritmeticològica Una unitat de memòria principal Registres Entrades/sortides
L'arquitectura de Von Neumann es basa en el concepte d'un ordinador amb un programa emmagatzemat, on les dades d'instruccions i les dades del programa s'emmagatzemen a la mateixa memòria. Aquest disseny encara s'utilitza en la majoria d'ordinadors que es produeixen actualment.
La unitat de control obté les instruccions / dades de la memòria, descodifica les instruccions i, a continuació, coordina les operacions per aconseguir la tasca programada. La unitat aritmètica realitza operacions aritmètiques bàsiques i l'entrada / sortida és la interfície perquè un humà hi pugui interactuar.
En aquest cas les computadores paral·leles segueixen aquest disseny bàsic, però multiplicant les unitats. L'arquitectura bàsica i fonamental segueix sent la mateixa.
Taxonomia de Flynn La taxonomia de Flynn és una classificació de les arquitectures de computadors, proposada per Michael J. Flynn l'any 1972.
La taxonomia de Flynn distingeix les arquitectures informàtiques segons com es poden classificar al llarg de dues dimensions independents: el flux d'instruccions i el flux de dades. Cadascuna d'aquestes dimensions solament admet dos estats possibles: simple o múltiple.
A continuació trobem les quatre possibles classificacions d'acord amb Flynn:
SISD (Single Instruction Single Data): Tenim un computador en sèrie (no paral·lela) on la CPU actua sobre un flux d'instruccions durant qualsevol cicle de rellotge. Durant qualsevol cicle de rellotge, només fa servir un flux de dades com a entrada. D'aquesta arquitectura en podem determinar l'execució. SIMD (Single Instruction Multiple Data): Tenim un computador paral·lel on totes les unitats de processament executen la mateixa instrucció però cada unitat de processament pot funcionar amb dades diferents. També se'n pot determinar l'execució. MISD (Multiple Instruction Single Data): Tenim un computador paral·lel on cada unitat de processament opera amb les dades de forma independent mitjançant instruccions diferents, en aquest cas, un únic flux de dades es submnistra a les diverses unitats de processament. MIMD (Multiple Instruction Multiple Data): Computador paral·lel on cada processador pot estar executant un flux d'instruccions diferent i cada processador pot estar treballant amb un flux de dades diferent. L'execució pot ser síncrona o asíncrona, determinista o no determinista.
A part de la classificació de Flynn, podem trobar altres tipus de classificacions .
Terminologia general En el món de la computació paral·lela trobem un argot propi, a continuació es detallaran alguns termes utilitzats associats a la computació paral·lela: Node: Terme comú per als elements computacionals que formen una màquina paral·lela de memòria distribuïda. Cada node té la seva pròpia memòria i almenys un processador; és a dir, un node pot ser un uniprocessador o algun tipus de multiprocessador. CPU/Processador/Nucli: La definició varia, depenent de qui parleu. En el passat, una CPU (Central Processing Unit) era un component d'execució singular per a una computadora. A continuació, es van incorporar múltiples CPUs a un node. Llavors, les CPU individuals es van subdividir en múltiples "nuclis", cadascun dels quals era una unitat d'execució única. Les CPU amb múltiples nuclis es denominen de vegades "sockets": dependents del proveïdor. El resultat és un node amb múltiples CPU, que conté cadascun de nuclis múltiples. Tasca: Aquest terme pot tenir diversos significats, depenent del context. La fem servir per a significar una seqüència d'operacions que juntes constitueixen una part lògica d'un algorisme o programa. SMP (Symmetric Multiprocessor): Un ordinador de memòria compartida en el qual cada processador és funcionalment idèntic i té accés a "temps igual" a cada adreça de memòria. En altres paraules, les adreces de memòria i els serveis del sistema operatiu estan igualment disponibles per a cada processador. Memòria compartida: Terme que s'aplica tant al maquinari com al programari que indica la presència d'una regió de memòria que es comparteix entre els components del sistema. Per als entorns de programació, el terme significa que la memòria es comparteix entre processos o fils. Aplicat al maquinari, significa que la característica arquitectònica que uneix processadors és la memòria compartida. Memòria distribuïda: Un sistema informàtic que construeix un espai d'adreça compartit entre diversos UE des de subsistemes de memòria física diferents i distribuïts sobre el sistema. Pot haver-hi suport operatiu i de sistemes operatius per al sistema de memòria compartida distribuïda, o la memòria compartida es pot implementar completament en un programari com a capa de middleware independent. Comunicacions: Les tasques paral·leles normalment necessiten intercanviar dades. Hi ha diverses maneres d'aconseguir aquest intercanvi, com ara a través d'un bus de memòria compartida o a través d'una xarxa, però l'esdeveniment real de l'intercanvi de dades s'anomena comunament comunicació, independentment del mètode utilitzat. Sincronització: Aplicar restriccions a l'ordenació d'esdeveniments que es produeixen en diferents UE (Unitats d'Execució). Això s'utilitza principalment per assegurar-se que els recursos compartits per un conjunt de UE s'utilitzin de forma determinada per a una correcte funcionament del programa, independentment de com estan programades les UE. Granularitat: En computació paral·lela, la granularitat és una mesura qualitativa de la relació entre la computació i la comunicació. Gruixuda: es fan quantitats relativament grans de treballs computacionals entre esdeveniments de comunicació. Fina: es realitzen quantitats relativament petites de treballs computacionals entre esdeveniments de comunicació. Speedup: Acceleració observada d'un codi paral·lelitzat, definit com:
On Temps Serie es el temps d'execució amb el programa seqüencial i el Temps Paral·lel és el temps d'execució amb el programa executant-se en paral·lel. Un dels indicadors més simples i més utilitzats per al rendiment del programa paral·lel.
Overhead: El temps necessari per coordinar les tasques paral·leles, en lloc de fer feines útils. Els costos paral·lels poden incloure factors com ara: Temps d'inici de tasques Sincronitzacions Comunicacions de dades Sobrecàrrega de programari imposada per llengües paral·leles, biblioteques, sistema operatiu, etc. Temps de finalització de tasques Paral·lelisme massiu: Es refereix al maquinari que comprèn un sistema paral·lel donat, que té molts elements de processament. El significat de "molts" continua augmentant, però actualment, les computadores paral·leles més grans estan constituïdes per elements de processament que se centren en milers i milions. Escalabillitat: Es refereix a la capacitat d'un sistema paral·lel (maquinari i / o programari) de demostrar un augment proporcional en acceleració paral·lela amb l'addició de més recursos. Els factors que contribueixen a l'escalabilitat inclouen: Maquinari: especialment amplades de banda de memòria-cpu i propietats de comunicació de xarxa Algorisme d'aplicació Característiques de l'aplicació a executar.
Límits i costos de la programació paral·lela Llei d'Amdahl miniatura|419x419px|Gràfic de speedups que s'obtenen en funció de la porció del codi paral·lelitzable i del nombre de processadors. La llei d'Amdahl estableix que l'acceleració potencial del programa es defineix per la fracció de codi (P) que es pot paral·lelitzar:
Si cap dels codis es pot paral·lelitzar, P=0 i la acceleració val 1 (no s'accelera).
Si tot el codi es pot paral·lelitzar, P=1, la velocitat resultant serà infinita (teòricament).
Si, per exemple, el codi es pot paral·lelitzar al 50%, la velocitat màxima serà de 2.
Introduint el nombre de processadors que executen la part paral·lela del programa, la relació es pot modelar per:
On P és la fracció paral·lela del programa, N el nombre de processadors i S la fracció sèrie del programa.
Com es pot veure en el gràfic de speedups, hi ha uns límits d'escalabilitat dels algoritmes, una frase d'Amdahl coneguda és la següent: podeu passar tota la vida aconseguint que el 95% del vostre codi sigui paral·lel i no aconseguir mai una velocitat superior a 20x, per més processadors que poseu. http://helper.ipam.ucla.edu/publications/bdctut/bdctut_15562.pdf
Escalabilitat https://www.cs.uky.edu/~jzhang/CS621/chapter7.pdf Existeixen dos tipus d'escalat en funció del temps que empren per arribar a la solució, l'escalat fort i el feble.