Extensiones de PRAM (APRAM, BSP, LogP…)

El PRAM clásico idealiza: procesadores sincronizados, memoria global con acceso $O(1)$, comunicación implícita. No representa $T_{comunicación}$, $T_{sincronización}$ ni $T_{latencia}$. Cada extensión relaja un supuesto:

Modelo	Supuesto que modifica	Extensión
APRAM (asíncrono)	sincronización global	procesadores a velocidades distintas; sincronizan solo en dependencias (wait(flag))
Phase PRAM	sincronización gratuita	fases: cómputo → barrera → cómputo…; $T_{sync}=S\cdot T_{barrier}$
LPRAM (memoria local)	acceso uniforme	$T_{local}<T_{global}$: jerarquía de memoria (cachés, NUMA, GPU)
BPRAM (bloques)	acceso palabra a palabra	transferencias de bloques de tamaño $b$: $T=\alpha+\beta b$, $\alpha\gg\beta$

BSP (Bulk Synchronous Parallel)

Supersteps: cómputo local → comunicación → barrera. Máquina $(p,g,L)$:

$$T_{superstep}=\underbrace{w}_{\text{cómputo}}+\underbrace{g\,h}_{\text{comunicación}}+\underbrace{L}_{\text{sincronización}}\qquad T_{BSP}=\sum_s w_s+g\sum_s h_s+S\,L$$

Reducción de $p$ valores: $\log_2p$ supersteps con $w=h=O(1)$ ⇒ $T_{red}=\log p\,(1+g+L)$ y

$$T_{BSP}=O\!\left(\frac np+g\log p+L\log p\right)$$

(en PRAM puro era solo $O(\log p)$: BSP hace explícito que cada nivel paga comunicación y sincronización). $BSP\approx$ Phase PRAM + localidad + comunicación + sincronización.

LogP

Ejecución asíncrona con costos explícitos: $L$ (latencia), $o$ (overhead de CPU al enviar/recibir), $g$ (gap mínimo entre envíos ⇒ ancho de banda), $P$ (procesadores).

$$T_{LogP}=O\!\left(\frac np+\log p\,(L+o+g)\right)$$

($n/p$ cómputo local, $o\log p$ overhead, $L\log p$ latencia, $g\log p$ ancho de banda.)

BSP y LogP en una línea de tiempo

BSP: supersteps (w + gh + L)LogP: reducción (L, o, g, P)

p = 4supersteps S = 3g (costo/palabra) = 2L (barrera) = 6desbalance = 50%🎲 Otra carga

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

fase 0/9

superstep 117+2·4+6 = 31

superstep 218+2·4+6 = 32

superstep 317+2·3+6 = 29

T_BSP92

$T_{superstep}=w+gh+L$ con $w=\max_i w_i$ y $h=\max_i h_i$ (h-relación). $T_{BSP}=\sum_s w_s+g\sum_s h_s+S\,L$. El proceso más lento marca el paso: sube el desbalance y mira crecer la zona roja.

En el examen…

Si preguntan «¿qué modelo usarías?»: asíncrono con dependencias ⇒ APRAM; fases con barreras (barrier() en el PRAM del arquetipo C) ⇒ Phase PRAM; transferencia por bloques ⇒ BPRAM; todo junto ⇒ BSP.

Error común

Confundir el $L$ de BSP (costo de sincronización/barrera) con el $L$ de LogP (latencia de un mensaje).

Niveles de paralelismo en hardware real

threads (SIMD/superescalar) → core (L1/L2) → procesador (L3) → nodo (memoria principal) → red de nodos → discos/Internet. Estrategia: modelos híbridos con pocos niveles bien definidos.

Ejercicio

Compara LogP y BSP: ¿qué parámetro separa LogP que BSP no separa explícitamente? Escribe el costo de una reducción en ambos.

Ver solución

LogP separa el overhead de CPU $o$ (tiempo en que el procesador está ocupado enviando/recibiendo) de la latencia $L$ y del gap $g$; BSP agrupa todo el costo de comunicación en $g\,h$ y la sincronización en $L$. Reducción: BSP $O(n/p+(g+L)\log p)$; LogP $O(n/p+(L+o+g)\log p)$.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. Modelo que introduce transferencias por bloques $\alpha+\beta b$:

a) APRAMb) LPRAMc) BPRAMd) LogP

2. En BSP, $L$ es…

a) latencia de un mensajeb) costo de sincronización globalc) número de procesadoresd) tamaño del bloque

3. Costo BSP de una reducción de $n$ datos:

a) $O(\log p)$b) $O(n/p+(g+L)\log p)$c) $O(n+gp)$d) $O(np)$

4. ¿Qué modelo reconoce que la memoria local es más barata que la global?

a) LPRAMb) Phase PRAMc) APRAMd) CRCW

Fuente ·estudio/04_PRAM.md §9 · U2.3-Diseño_en_paralelo-PRAM_02.pdf