Paral·lelisme de tasques

Aquest article podria incomplir els criteris generals d'admissibilitat. Milloreu-lo amb referències que demostrin que es tracta d'un tema admissible o bé podria entrar en un procés d'esborrament o fusió. (2017)

El paral·lelisme de tasques (task parallelism) és un paradigma de programació que consisteix en l'execució de diverses funcions (tasques) del mateix o diferents conjunts de dades, sobre un sistema de computació paral·lela, per tal d'aprofitar el seu màxim de recursos disponibles simultàniament.^[1]

Paral·lelisme de tasques

En contrast amb el paral·lelisme de dades (data parallelism, aka SIMD),^[2] que té com a objectiu la distribució d'un conjunt de dades en diferents cores per a la seva respectiva execució, el paral·lelisme de tasques té com a nucli central l'òptima distribució de tasques (task scheduling)^[3] per tot el sistema, per tal que pugui ser executada de forma més eficient.

Paral·lelisme de dades

Funcionament

En un sistema multiprocessador, el paral·lelisme de tasques tracta d'utilitzar cadascun dels processadors per tal d'executar un thread o un procés sobre un mateix o diferents conjunts de dades. Aquesta assignació de tasques

als recursos disponibles s'anomena planificació (scheduling), habitualment utilitza expressions condicionals, i és de vital importància, ja que serà la que determini l'eficiència de la

nostra aplicació.

Principalment, podem diferenciar dos tipus de planificació:

- Estàtica: L'assignació del processador i l'ordre de les tasques es determinat durant la compilació del programa. Permet incloure les dependències i comunicacions de tasques emprades pel planificador.

- Dinàmica:^[4] L'assignació del processador i la qualificació de quan s'executarà una determinada tasca es controlada per l'operatiu. Molt pràctic per tasques independents, però s'ha de considerar el temps de planificació extra (overhead).

Podem representar aquesta paral·lelització mitjançant grafs acíclics dirigits (DAGs), anomenats grafs de tasques, on cada node representa el còmput d'una tasca i els enllaços els seus costos de comunicació. Aquest graf es generat durant la descomposició en subtasques i el seu corresponent anàlisis de dependències.

Un cop realitzats els passos anteriors, el pas final es l'assignació d'aquestes tasques als processadors disponibles del nostre sistema i la determinació del seu ordre d'execució. A partir d'ara l'anomenarem planificació (scheduling) i només pot donar-se a terme havent fet tots els passos posteriors, per tant tot el procés d'anàlisi mencionat anteriorment serà un pas crucial per a l'òptima execució paral·lela de la nostra aplicació.

Diferents descomposicions en subtasques ens portaran cap a unes determinades restriccions per dependències amb les seves respectives planificacions, cadascuna de diferent eficiencia. Resumint, llavors direm que els 3 principals camps per a una correcta paral·lelització són:

-Descomposició en subtasques

-Anàlisi de dependències

-Planificació

Descomposició en subtasques

Principalment, la tria d'aquesta descomposició es basa en el tipus de còmput, tècniques de programació i llenguatge emprat pel nostre programa. L'arquitectura del sistema on executarem la nostra aplicació i el corresponent paradigma de paral·lelització que farem servir també afectara la nostra descomposició.

Segons la descomposició que aconseguim del nostre programa podrem parlar de granularitat fina (fine-grain), quan aconseguim fer una descomposició en tasques molt petites, o bé granularitat gruixuda (coarse-grain) quan fem una descomposició en tasques més grans. Aquesta granularitat també pot ser entesa com la relació entre la transferència de dades per a un determinat cost computacional de cadascuna de les diferents tasques.

Les tècniques de descomposició més comuns són:

-Descomposició de dades (data descomposition)

-Descomposició recursiva (recursive descomposition)

-Descomposició explorativa (exploratory descomposition)

-Descomposició especulativa (Speculative descomposition)

Representacions en grafs

Com hem mencionat anteriorment, ens ajudem de grafs per a la representació de nombrosos problemes en l'àrea de computació paral·lela i entorns distribuïts (grafs de comunicacions de xarxes, grafs de tasques, comunicacions i dependències de programes..., etc).

El graf de tasques és el model de graf emprat per a planificació. Mostra de forma clara i concisa quina es l'estructura i cost de tasques i comunicacions d'un determinat programa.

Graf com a model de programa à Segons un abstracte de la teoria de grafs, un programa consisteix en dos tipus d'activitat –computació i comunicació. El còmput està associat amb els vèrtexs del graf i la comunicació amb els seus lligams. Anomenem nodes als vèrtexs del graf amb els seus respectius lligams de comunicació, que tot junt conforma una tasca. Aquesta, pot representar des d'una instrucció/operació atòmica (indivisible) fins a threads, cicles, blocs..., etc. Cada instrucció d'una tasca és executada concurrentment (no hi ha paral·lelisme en l'execució d'una tasca), i a més, cada tasca està implicada en una sola activitat—còmput o comunicació.

Per a poder generar aquests grafs en els nostres ordinadors, principalment emprem dos tipus de representació de grafs:

-Representació mitjançant una llista d'adjacència

-Representació mitjançant matriu d'adjacència

I per poder recórrer aquests grafs, principalment s'utilitzen els següents algorismes (més elementals):

-Recorregut en amplada o BFS (Breadth First Search)

-Recorregut en profunditat o DFS (Depth First Search)

Planificació (scheduling)

Les propietats del nostre Sistema paral·lel són les següents:

- Sistema Dedicat: El sistema paral·lel està dedicat a l'execució del graf de tasques. No hi ha cap altra tasca en execució mentre el nostre sistema està ocupat amb l'execució del graf de tasques.

- Processador Dedicat: Un processador P del nostre sistema només pot executar una tasca alhora i l'execució no es preventiva.

- Comunicació local (comunicació entre tasques executades en un mateix node és negligible) no té cap cost.

- Subsistema de comunicació: la comunicació entre processadors es pot realitzar de forma simultània, no hi ha cap mena de contenció/limitació pels recursos de comunicació.

- Sistema completament connectat. Dins del sistema, un processador pot comunicar-se directament amb qualsevol altre.

Donades aquestes característiques (processadors idèntics, connectats en xarxa..., etc), direm que les arquitectures NUMA (non-unified Memory Access), o de pas de missatges són les més òptimes per a tal comesa. 

Exemple

El següent pseudocodi il·lustra un pralal·lelisme de tasques:

program:
...
if CPU="a" then
 do task "A"
else if CPU="b" then
 do task "B"
end if
...
end program

Característiques:

1. En un sistema SPMD (programa únic, dades múltiples), les dues CPU executaran el codi.
2. En un entorn paral·lel, tots dos tindran accés a les mateixes dades.
3. La clàusula "if" diferencia entre les CPU. Cada una tindran la seva pròpia tasca.
4. Ambdues CPU executen blocs de codi separats simultàniament, realitzant diferents tasques simultàniament.

Codi executat per la CPU "A":

program:
...
do task "A"
...
end program

Codi executat per la CPU "B":

program:
...
do task "B"
...
end program

Referències

1. Khaldi, D.; Jouvelot, P.; Ancourt, C.; Irigoin, F. «Task Parallelism and Data Distribution: An Overview of Explicit Parallel Programming Languages» (en anglès). Languages and Compilers for Parallel Computing. LCPC 2012. Lecture Notes in Computer Science, vol 7760, 2013, pàg. 174-189.
2. Błażewicz, Jacek; Ecker, Klaus; Plateau, Brigitte; Trystram, Denis «Handbook on Parallel and Distributed Processing» (en anglès). Springer-Verlag Berlin Heidelberg, 2000.
3. Sinnen, Oliver. «Task Scheduling for Parallel Systems» (en anglès). Wiley.
4. Drebes, Andi; Pop, Antoniu; Heydemann, Karine; Cohen, Albert; Drach, Nathalie «Scalable Task Parallelism for NUMA: A Uniform Abstraction for Coordinated Scheduling and Memory Management» (en anglès). Proceedings of the 2016 International Conference on Parallel Architectures and Compilation (ACM), 2016, pàg. 125-137.