Mesurar el paral·lelisme · 2.6

Memòria distribuïda i cost de compartir dades

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

Conceptes clau

$t_{exe} = t_{comput} + t_{transferencies}$
Accés local i accés remot
Model $t_{acces} = t_s + m \cdot t_w$
Simplificacions del model

En un mateix procés, tots els threads comparteixen el mateix espai d’adreces (memòria compartida). Tot i això, a nivell de maquinari cada processador $P_i$ té la seva pròpia memòria/caches i les dades no sempre són locals al nucli on s’executa el thread. Quan cal accedir a dades que no estan disponibles localment, s’han de transferir i això té un cost.

t_{\text{exe}} = t_{\text{comput}} + t_{\text{transferències}}

Model simplificat: considerem un model senzill on cada processador $P_i$ té la seva pròpia memòria i tots estan interconnectats mitjançant una xarxa d’interconnexió:

Accés local: els processadors accedeixen a dades locals (a la seva pròpia memòria) amb instruccions normals de load/store. En aquest model idealitzat, aquests accessos locals tenen cost 0.
Accés remot: si un processador necessita dades que estan a la memòria d’un altre, utilitza un model de message passing: el processador demana les dades i l’altre processador les serveix.

En aquesta assignatura assumirem un temps d’accés remot que seguirà un model lineal:

t_{\text{accés}} = t_s + m \cdot t_w

$t_s$ és el cost fix de preparar la comunicació (startup).
$m \cdot t_w$ és el cost de transferència (enviar $m$ bytes amb cost temporal $t_w$ per byte).

Simplificacions del model: per fer un model més tractable, també assumirem que:

a) En un instant, un processador $P_i$ només pot fer un accés remot a un altre $P_j$ .

b) En un instant, un processador $P_i$ només pot servir un accés remot d’un altre $P_k$ .

c) Ambdues accions poden passar simultàniament: $P_i \to P_j$ i $P_i \leftarrow P_k$ .

(a) Incorrecte: P3 no pot fer dos accessos simultanis. (b) Incorrecte: P3 no pot estar servint dues peticions al mateix instant. (c) Correcte: P2 pot accedir a P3 i alhora estar servint P1. (figura al dossier, p. 14)

Aquestes hipòtesis no descriuen tots els detalls del maquinari real, però són suficients per raonar sobre com el cost de compartir dades i la sincronització poden limitar l’escalabilitat.