PAR · Tema 2

Mesurar el paral·lelisme

Com es quantifica el paral·lelisme d'un programa i què el limita. Construiràs grafs de dependències, aplicaràs la llei d'Amdahl i veuràs l'efecte dels overheads, la granularitat i el cost de moure dades.

Descarrega el dossier en PDF

Capítols

2.1
Construcció d'un Task Dependence Graph (TDG)Esborrany
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}$.
Llegit
2.2
Fracció paral·lelitzable i llei d'AmdahlEsborrany
Separes el temps en part seqüencial i part paral·lelitzable. La fracció $\varphi$ et diu quina part del codi es pot beneficiar del paral·lelisme, i la llei d'Amdahl, fins on pot arribar el guany.
Llegit
2.3
EscalabilitatEsborrany
L'escalabilitat mesura si el programa continua millorant quan hi afegeixes recursos. Distingiràs la strong scalability (mida fixa) de la weak scalability (mida proporcional a $P$) i veuràs la llei de Gustafson.
Llegit
2.4
OverheadsEsborrany
Paral·lelitzar mai és perfecte: crear i gestionar tasques, esperar dependències, protegir dades compartides i el desbalanceig de càrrega afegeixen temps. Són els overheads.
Llegit
2.5
GranularitatEsborrany
Un cop saps què pots paral·lelitzar, has de decidir en quantes tasques ho divideixes. Tasques grans donen desbalanceig; tasques petites donen overheads. Cal trobar el punt mig.
Llegit
2.6
Memòria distribuïda i cost de compartir dadesEsborrany
Encara que els threads comparteixin espai d'adreces, les dades no sempre són locals al processador. Moure-les té un cost, i aquí el modelaràs amb $t_s + m \cdot t_w$.
Llegit
2.7
ConsolidacióEsborrany
Repàs del tema 2: què has de saber fer i calcular per mesurar el paral·lelisme d'un programa.
Llegit