> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Programación paralela: rendimiento, speedup y diseño de algoritmos

> Qué estudia la programación paralela: tiempo de ejecución paralelo, speedup, eficiencia, leyes de Amdahl y Gustafson, escalabilidad y metodología de Foster para diseñar algoritmos paralelos.

Durante décadas, los programas iban más rápido sin hacer nada: cada nueva generación de procesadores tenía más frecuencia. Hacia 2005 eso se acabó, porque subir más la frecuencia calentaba demasiado los chips, y los fabricantes empezaron a poner **varios núcleos** en cada procesador. Desde entonces, para aprovechar un ordenador hay que **repartir el trabajo**. La programación paralela estudia cómo hacerlo y, sobre todo, cómo saber si ha merecido la pena.

## Las ideas clave del bloque

### Medir antes de paralelizar

El rendimiento de un algoritmo paralelo depende de la talla $n$ y del número de procesadores $p$. Se modela con su tiempo, $T(n,p) \cong T_{ar} + T_{co}$, suma del cálculo y las comunicaciones, y se compara con el secuencial mediante unos pocos parámetros:

| Parámetro | Fórmula |
| - | - |
| Speedup | $S = T(n) / T(n,p) \le p$ |
| Eficiencia | $E = S / p \in [0, 1]$ |
| Coste | $C = p\,T(n,p)$ |
| Sobrecarga | $T_0 = C - T(n)$ |

### Los límites: Amdahl y Gustafson

La parte que no se puede repartir pone un techo al speedup: con una fracción secuencial $\alpha$, nunca se pasa de $1/\alpha$ (**ley de Amdahl**). Si el problema crece con la máquina, en cambio, el speedup escalado crece casi linealmente (**ley de Gustafson**).

### Escalabilidad

Un algoritmo es escalable si, haciendo crecer el problema, mantiene la eficiencia al añadir procesadores. La **función de isoeficiencia** dice cuánto tiene que crecer: cuanto más despacio, mejor.

### Diseño: la metodología de Foster

Para diseñar un algoritmo paralelo se siguen cuatro pasos:

1. **Descomposición:** dividir el problema en tareas pequeñas (por datos o por funciones).
2. **Comunicaciones:** ver qué datos necesita cada tarea de las demás.
3. **Agrupación:** juntar tareas para reducir comunicaciones (relación superficie/volumen).
4. **Asignación:** repartir los grupos entre los procesadores, de forma estática o dinámica.

## Orden recomendado

<Steps>
  <Step title="Tiempo paralelo y parámetros relativos">
    $T_{ar}$, $T_{co}$, speedup, eficiencia, coste y sobrecarga con ejemplos sencillos.
  </Step>

  <Step title="Leyes de Amdahl y Gustafson">
    El techo de la parte secuencial y el escalado del problema.
  </Step>

  <Step title="Escalabilidad">
    Isoeficiencia y eficiencia escalada.
  </Step>

  <Step title="Diseño de algoritmos paralelos">
    Grafos de dependencias, pipeline y metodología de Foster.
  </Step>
</Steps>

## Temas de este bloque

<CardGroup cols={2}>
  <Card title="Ley de Amdahl" href="/programacion/paralela/ley-de-amdahl">
    Speedup y eficiencia de un programa paralelo explicados: tiempo paralelo, coste y sobrecarga, ley de Amdahl, ley de Gustafson-Barsis, rendimiento efectivo e isoeficiencia, con ejemplos resueltos.
  </Card>
</CardGroup>

## Simuladores de programación paralela en Simulab

<CardGroup cols={2}>
  <Card title="Ley de Amdahl" icon="flask" href="https://simulab.es/programacion/ley-de-amdahl">
    Speedup, eficiencia y sobrecarga según la fracción paralelizable y los procesadores.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.