Overheads

Paral·lelitzar un programa no és perfecte. Fins i tot si un codi és totalment paral·lelitzable, en executar-lo sobre $P$ processadors no obtindrem $T_1/P$:

$$T_P \neq \frac{T_1}{P} \qquad \Rightarrow \qquad T_P = \frac{T_1}{P} + T_{\text{overheads}}$$

Els overheads són costos addicionals que apareixen per coordinar l’execució en paral·lel.

• Gestió de threads i tasques: el simple fet de paral·lelitzar un programa implica crear i mantenir threads i gestionar tasques (encuar, planificar, repartir i sincronitzar…). Aquesta feina es fa en temps d’execució i consumeix temps de CPU, de manera que es dedica a fer gestions i no a càlcul útil del programa.
• Accés a recursos compartits: com hem vist abans, en paral·lelitzar poden aparèixer problemes de concurrència (secció 1.5). Per evitar-los, sovint cal protegir les dades compartides amb mecanismes de sincronització (secció 3.6), fent que un thread hagi d’esperar que un altre acabi d’utilitzar la dada, perdent temps de còmput.
• Load imbalance: sovint alguns processadors acaben les tasques que tenen assignades abans que d’altres. Quan volen continuar, poden quedar-se inactius perquè no hi ha cap tasca disponible: o bé perquè la resta de feina encara està en execució en altres CPUs, o bé perquè cal esperar que es resolguin dependències abans de poder iniciar la següent tasca.
• Altres pèrdues: jerarquia de memòria, replicació de càlculs, enviaments de dades, etc.

▣TDG amb A (4), B (3), C (3), D (6), E (1) i F (1), on B i C comparteixen un recurs, i la seva execució en tres processadors amb els trams de creació de threads, espera per dependències, accés exclusiu i idle. (figura al dossier, p. 12)

Podem veure diversos overheads que fan créixer $T_P$ respecte l’ideal:

• Gestió (groc): petits trams al crear cada thread i també abans de crear cada tasca.
• Espera per dependències (wait dep, rosa): al principi, P1 i P2 esperen fins que acaba A; més endavant, tornen a esperar fins que D es resol (dep resolta) per poder executar E i F.
• Accés a recurs compartit entre B i C (trams R): les barres de B i C apareixen fragmentades perquè alternen càlcul amb seccions d’accés exclusiu, i això fa que s’esperin quan el recurs és ocupat per l’altra tasca.
• Idleness (gris): després d’acabar C, P2 queda inactiu fins al final perquè no té cap tasca disponible a executar; és un exemple de temps perdut per desbalanceig de càrrega.