Mesurar el paral·lelisme · 2.1

Construcció d'un Task Dependence Graph (TDG)

Si representes les tasques com a nodes i les dependències de dades com a arestes, obtens un TDG. Amb el graf calcules $T_1$ , $T_\infty$ , el paral·lelisme ideal i el nombre mínim de processadors $P_{min}$ .

Conceptes clau

Nodes, arestes i temps de cada tasca
$T_P$ , $T_1$ i $T_\infty$
Camí crític
Paral·lelisme ideal $T_1 / T_\infty$
Processadors mínims $P_{min}$

Prova-hoGraf de dependències entre tasques

Clica una tasca per canviar-ne el cost. En corall, el camí crític.

treball T₁

camí crític T_∞

paral·lelisme T₁/T_∞

processadors (ASAP)

Execució ASAP: cada tasca comença quan han acabat totes les que necessita.

Quan representem les tasques del nostre programa com a nodes i les dependències de dades entre tasques com a arestes, obtenim un Task Dependence Graph (TDG).

Cada node representa una tasca.
Les tasques indiquen el temps d’execució. El temps de cada node ens ajudarà a detectar colls d’ampolla i a fer una millor repartició de la càrrega de treball.
Les arestes indiquen dependències de dades. Una tasca no pot començar fins que les tasques predecessores han acabat.
Cada CPU només pot executar una tasca alhora.

Exemple d’un TDG: A (4) precedeix B (3), C (3) i D (6), i totes tres precedeixen E (1). (figura al dossier, p. 9)

Un cop construït el TDG, el podem utilitzar per analitzar fàcilment l’estratègia de paral·lelització:

$T_P$ : temps d’execució si usem $P$ processadors (respectant dependències).
$T_1$ : temps d’execució seqüencial. Per calcular-lo sumem els temps d’execució de totes les tasques.
$T_\infty$ : temps d’execució mínim que podem aconseguir amb aquesta estratègia. Per calcular-lo mirarem la durada del camí crític del TDG.

Camí crític de l’exemple: A → D → E. (figura al dossier, p. 9)

Paral·lelisme ideal/màxim: $\dfrac{T_1}{T_\infty}$ . Major speedup que podem obtenir amb aquesta estratègia.

$P_{min}$ : és el nombre mínim de processadors necessaris per assolir el paral·lelisme ideal (és a dir, executar el programa en $T_\infty$ ).

Per trobar $P_{min}$ , distribueix les tasques en una línia de temps entre varis processadors:

Assigna el camí crític a un processador (fixa el temps mínim possible, $T_\infty$ ).
Reparteix la resta de tasques en altres processadors, respectant dependències i sense excedir $T_\infty$ .
Si no hi caben, incrementa $P$ i repeteix. Si en canvi pots compactar tasques i alliberar algun processador, decrementa $P$ .

Planificador de 3 processadors: P0 executa A, D i E; B i C comencen a P1 i P2, i C es pot moure a P1 just després de B. (figura al dossier, p. 9)

Quan totes les tasques caben dins $T_\infty$ , el valor de $P$ és $P_{min}$ .