Model de programació paral·lela

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. 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 d'ells:

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

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.

Arquitectura Von Neumann

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:

1. 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ó.
2. 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ó.
3. 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.
4. 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 Arxivat 2017-02-01 a Wayback Machine..

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:
  • ${TempsSerie \over TempsParallel}$
  • 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

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:

$acceleracio={\frac {1}{1-p}}$

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:

$speedup={\frac {1}{{\frac {p}{n}}+s}}$

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.

Escalabilitat

Existeixen dos tipus d'escalat en funció del temps que empren per arribar a la solució, l'escalat fort i el feble.

• Escalat fort: La mida total del problema es manté fixa a mesura que s'afegeixen més processadors. L'objectiu és executar la mateixa mida del problema més ràpidament. L'escala perfecta significa que el problema es resol en temps 1 / P (en comparació al temps d'execució sèrie)

• Escalat feble: La mida del problema per processador es manté fixa a mesura que s'afegeixen més processadors. La mida total del problema és proporcional al nombre de processadors utilitzats. L'objectiu és generar un problema més gran en el mateix temps L'escala perfecta significa que el problema Px s'executa al mateix temps que un sol processador.

L'escalabilitat d'un programa paral·lel és el resultat d'un conjunt de factors interrelacionats. Afegir més processadors rarament és la solució.

L'algorisme pot tenir límits d'escalabilitat. En algun moment pot ser que afegir recursos fa que es disminueixi el rendiment, problema comú a moltes aplicacions paral·leles.

Tipus d'arquitectures de memòria paral·lela

Quan parlem de memòria en arquitectures paral·leles, en podem distingir dos grups clarament:

Memòria compartida

Esquema de memòria compartida.

Característiques generals

En general tenen en comú la possibilitat que tots els processadors accedeixin a tota la memòria principal com un espai d'adreces globals. Els múltiples processadors poden funcionar de manera independent, però comparteixen els mateixos recursos de memòria. Els canvis en una ubicació de memòria efectuada per un processador són visibles per a tots els altres processadors. Històricament, les màquines de memòria compartida han estat classificades com a UMA i NUMA, basades en els temps d'accés a la memòria.

Uniform Memory Acces (UMA)

• El més representat avui per les màquines Symmetric Multiprocessor (SMP)
• Processadors idèntics.
• Temps d'accés i accés iguals a la memòria.
• De vegades anomenats també CC-UMA - Cau UMA coherent. Mitjançant la coherència de la memòria cau, si un processador actualitza una ubicació a la memòria compartida, tots els altres processadors veuen l'actualització. La coherència de la memòria caché es realitza a nivell hardware.

Non-Uniform Memory Access (NUMA)

• Sovint es fa mitjançant l'enllaç físic de dos o més SMP.

• Un SMP pot accedir directament a la memòria d'una altra SMP.
• No tots els processadors tenen el mateix temps d'accés a tots els records.
• L'accés a la memòria a través d'un enllaç és més lent.
• Si es manté la coherència de la memòria cau, també es pot denominar CC-NUMA - Cau Coherent NUMA.

Avantatges

• L'espai d'adreces global proporciona una perspectiva de programació fàcil a l'hora d'utilitzar la memòria.

• La compartició de dades entre tasques és ràpida i uniforme a causa de la proximitat de la memòria a la CPU

Inconvenients

• El desavantatge principal és la manca d'escalabilitat entre memòria i CPU. Si s'afegeixen més CPU pot augmentar geomètricament el trànsit de la ruta compartida de la memòria de la CPU i, per als sistemes coherents de memòria cau, augmentar geomètricament el trànsit associat a la gestió de memòria cau.
• Responsabilitat del programador per a controlar la sincronització que garanteixi l'accés "correcte" a la memòria global.

Memòria distribuïda

Esquema de memòria distribuïda.

Igual que els sistemes de memòria compartida, els sistemes de memòria distribuïda varien àmpliament, però comparteixen una característica comuna. Els sistemes de memòria distribuïda requereixen una xarxa de comunicació per connectar la memòria entre processadors. Els processadors tenen la seva pròpia memòria local, les adreces de memòria d'un processador no s'adrecen a un altre processador, de manera que no hi ha cap concepte d'espai d'adreça global a tots els processadors. Com que cada processador té la seva memòria local, funciona de manera independent. Els canvis que fa a la seva memòria local no tenen cap efecte sobre la memòria d'altres processadors. Per tant, el concepte de coherència de la memòria cau no s'aplica. Quan un processador necessita accés a les dades en un altre processador, normalment és la tasca del programador definir explícitament com i quan es comuniquen les dades. La sincronització entre tasques és igualment la responsabilitat del programador. El tipus de tecnologia de xarxa utilitzada per a la transferència de dades varia àmpliament, tot i que pot ser tan simple com Ethernet.

Avantatges

• La memòria és escalable amb el nombre de processadors. Augmentar el nombre de processadors augmenta la mida de la memòria proporcionalment.
• Cada processador pot accedir ràpidament a la seva pròpia memòria sense interferències i sense que la sobrecàrrega hagi estat causada per intentar mantenir la coherència global de la memòria cau.
• Eficàcia econòmica: pot utilitzar productes bàsics, processadors independents i xarxes.

Inconvenients

• El programador és responsable de molts dels detalls relacionats amb la comunicació de dades entre processadors.
• Pot ser que sigui difícil mapar estructures de dades existents, basades en la memòria global, a aquesta organització de memòria.
• Temps d'accés de memòria no uniforme: les dades que resideixen en un node remot triguen més a accedir a les dades locals del node.

Models de programació paral·lels

Els models de programació paral·lels existeixen com a abstracció per sobre de les arquitectures de hardware i memòria. Encara que no sembli aparent, aquests models NO són específics d'un tipus particular d'arquitectura de màquina o de memòria. De fet, qualsevol d'aquests models pot (teòricament) ser implementat en qualsevol maquinari subjacent. Les característiques dels models de programació paral·lela es poden subdividir àmpliament. Es poden generalitzar, però, en dos fonamentals: la interacció de processos i els problemes de descomposició.

Interacció de procés

La interacció de procés fa referència als mecanismes pels quals processos paral·lels poden ser capaços de comunicar-se entre si. Les maneres més comunes d'interacció son la memòria i el pas de missatges compartits, tot i que també pot ser implícita.

Memòria compartida

Article Principal: Memòria compartida

La memòria compartida es un mitjà eficaç de compartir dades entre programes. Depenent del context, els programes poden ser executats en un processador únic o en diversos processadors. En aquest model, les tasques paral·leles comparteixen un espai de direccions global on escriuen i llegeixen de manera asíncrona. Això requereix de mecanismes de protecció, tal com l'ús de semàfors, monitors per controlar l'accés concurrent o panys. La memòria compartida pot ser utilitzada en sistemes de memòria distribuïda, però els temps de NUMA (accés no uniforme a memòria, Non-Uniform Memory Access) poden guanyar rellevància i afectar el rendiment. A vegades la memòria també és compartida entre diferents seccions del codi del mateix programa. Per exemple, un bucle for pot crear fils d'execució per a cada iteració que actualitza una variable en paral·lel.

Model de fils

En el model de fils de programació paral·lela, un sol procés "pesat" pot tenir múltiples fils "lleugers", que són camins d'execució concurrents.

Des de la perspectiva de la programació, les implementacions de fils inclouen:

• Una biblioteca de subrutines que es criden des del codi font paral·lel del programa.
• Un conjunt de directrius del compilador incorporades en codi font en sèrie o en paral·lel.

En ambdós casos, el programador és responsable de determinar el paral·lelisme (encara que els compiladors de vegades poden ajudar).

• Els esforços de normalització no relacionats han donat lloc a dues implementacions de fils molt diferents: fils de POSIX i OpenMP .
• Fils POSIX
  • Especificat per l'estàndard IEEE POSIX 1003.1c (1995). La seva implementació es realitza solament amb llenguatge C.
  • Forma part dels sistemes operatius Unix / Linux.
  • Estan basats en una llibreria anomenada POSIX.
  • Habitualment els fils s'anomenen Pthreads.
  • Paral·lelisme molt explícit; requereix una atenció significativa en el detall de programació.
• OpenMP
  • Estàndard de la indústria, definit conjuntament i avalat per un grup de principals proveïdors de hardware i programari informàtic, organitzacions i individus.
  • Basada en directives del compilador.
  • Portàtil / multiplataforma, incloent plataformes com Unix i Windows
  • Disponible en implementacions C / C ++ i Fortran
  • Pot ser molt fàcil i senzill d'utilitzar: proporciona "paral·lelisme incremental". Es pot començar amb el codi de sèrie.

Pas de missatges

Article Principal: Pas de missatges

El pas de missatges és un concepte de la informàtica que s'utilitza àmpliament a l'hora de dissenyar i implementar modernes aplicacions de software; és clau per alguns models de concurrència i la programació orientada a objectes. En un model de pas de missatges, les tasques paral·leles intercanvien dades a través del pas de missatges entre elles. Aquestes comunicacions poden ser síncrones o asíncrones. La formalització de la Comunicació de processos seqüencials (CSP) del pas de missatges fa servir canals de comunicació per a connectar processos, i va donar lloc a una serie de llenguatges importants, com el Joyce, Occam i l'Erlang.

Implementacions

• Des d'una perspectiva de programació, les implementacions en transmissió de missatges solen incloure una biblioteca de subrutines. Les crides a aquestes subrutines s'incorporen al codi font. El programador és responsable de determinar tot el paral·lelisme.
• Històricament, des de la dècada dels vuitanta hi ha disponibles diverses biblioteques de transmissió de missatges. Aquestes implementacions difereixen substancialment les unes de les altres, cosa que dificultava que els programadors desenvolupessin aplicacions portàtils.
• El 1992 es va formar MPI amb l'objectiu principal d'establir una interfície estàndard per a la implementació de missatges.
• La primera part de la Message Passing Interface (MPI) es va publicar el 1994. La part 2 (MPI-2) es va publicar el 1996 i MPI-3 el 2012. Totes les especificacions MPI estan disponibles a la web de MPI.
• MPI és l'estàndard "de facto" a la indústria per a la transmissió de missatges, que substitueix pràcticament totes les altres implementacions de transmissió de missatges utilitzades anteriorment. Les implementacions MPI existeixen per a pràcticament totes les plataformes de computació paral·leles més utilitzades. No totes les implementacions inclouen tots els estàndards en MPI-1, MPI-2 o MPI-3.

Implícit

En un model implícit, cap interacció del procés es visible al programador, en canvi el compilador i/o temps d'execució es responsable de realitzar la mateixa. Això es més comú amb els llenguatges específics de domini en el que la concurrència d'un problema pot ser més prescrita, i amb els llenguatges de programació funcional perquè la acescència de efectes secundaris permet la independència de les funcions a executar en paral·lel. De manera que aquest tipus de paral·lelisme es difícil de manejar i els llenguatges funcionals com Haskell concurrent i ML concurrent aporten de gestió al paral·lelisme explicit.

Descomposició del problema

Un programa paral·lel està format per processos simultanis d'execució. La descomposició del problema es relaciona amb la forma en què es formulen els processos constitutius.

Paral·lelisme de tasques

Article Principal: Paral·lelisme de tasques

Un model de tasca paral·lela se centra en processos o en subprocessos d'execució. Aquests processos seran sovint de manera comparativa, el que fa èmfasi en la necessitat de la comunicació. El paral·lelisme de tasques és una forma natural d'expressar la comunicació de pas de missatges.

Paral·lelisme de dades

Article Principal: Paral·lelisme de Dades

Un model de dades paral·leles se centra en realitzar operacions en un conjunt de dades, normalment una matriu estructurada regularment. Un conjunt de tasques funcionarà en aquestes dades, però de forma independent en particions no seleccionades. A la taxonomia de Flynn, el paral·lelisme de dades sol ser classificat com a MIMD / SPMD o SIMD.

Paral·lelisme implícit

Igual que amb la interacció implícita del procés, un model implícit de paral·lelisme no revela res al programador, ja que el compilador, el temps d'execució o el maquinari és responsable. Per exemple, en els compiladors, la paral·lelització automàtica és el procés de convertir el codi seqüencial en codi paral·lel, i en l'arquitectura de la computadora, l'execució super escalar és un mecanisme pel qual el paral·lelisme de nivell d'instrucció s'explota per realitzar operacions en paral·lel.

Exemple de models de programació paral·lela

• Esquelets algorítmics
• Components
• Objectes distribuïts
• Invocació de mètode de manera remota

Nom	Classe d'iteració	Classe de descomposició	Implementacions d'exemple
Model d'Actors	Pas de missatges asíncron	Tasca	Llenguatge D, Erlang, Scala, SALSA
Paral·lelisme síncron al por major (bulk synchronous parallelism)	Memòria Compartida	Tasca	Apache Giraph, Apache Hama, BSPlib
Processos comunicants seqüencials	Pas de missatges síncron	Tasca	Ada, Occam, VerilogCSP, Go
Circuits	Pas de missatges	Tasca	Verilog, VHDL
Processament de fluxos (dataflow), Flux de treball (workflow)	Pas de missatges	Tasca	Lustre, TensorFlow, Apache Flink
Programació funcional	Implícit	Tasca	Haskell concurrent, ML concurrent
Màquina LogP	Pas de missatges síncron	No s'especifica
Màquina d'accés paral·lel aleatori	Memòria compartida	Dades	Cilk, CUDA, OpenMP, XMTC, creació de fils en bloc (threading building blocks)

Bibliografia addicional

• Blaise Barney. Introducció a la programació paral·lela (anglés). 
• Murray I. Cole.. Esquelets algorítmics: Gestió estructurada de la computació paral·lela (anglés). 
• «Programació paral·lela estructurada (anglés)». Sobre models de programació per computadors masivament paral·lels. IEEE Computer Society Press, 1993.
• Ian Foster. Dissenyant i construint programes paral·lels (anglés).