P1a · Taller de cálculo de Speedup, Eficiencia y Escalabilidad
1. Propósito y competencia
Capacitar al estudiante en la medición empírica de tiempos de ejecución y en la formulación matemática de las métricas canónicas de rendimiento paralelo: **Ganancia de velocidad (
)
)
2. Fundamentación matemática
Dado un algoritmo ejecutado sobre una arquitectura paralela con 
unidades de procesamiento:
- **Tiempo secuencial (
):** Tiempo de ejecución del mejor algoritmo secuencial conocido sobre un único núcleo físico. - **Tiempo paralelo (
):** Tiempo transcurrido desde que se inicia la computación paralela hasta que el último procesador culmina su tarea. - **Speedup (
):** $$S_p = \frac{T_1}{T_p}$$ 
.
(caso general debido a sobrecargas de sincronización y partes secuenciales).
(ocurre comúnmente cuando el problema dividido cabe completamente en la suma de las memorias caché L2/L3 de los núcleos activos).- **Eficiencia (
):** Fracción del tiempo en que los procesadores realizan trabajo útil: $$E_p = \frac{S_p}{p} = \frac{T_1}{p \cdot T_p}$$ Expresada porcentualmente: 
.
3. Casos de estudio y actividades en laboratorio
Caso 1: Procesamiento de matrices densas
Se midieron los siguientes tiempos en segundos para un algoritmo de filtrado espacial sobre una imagen satelital multiespectral de 
píxeles:
Núcleos ( ) | Tiempo medido  (segundos) | Speedup calculado  | Eficiencia calculada  |
|---|---|---|---|
| 1 | 48.60 s | 1.00 x | 100.0 % |
| 2 | 25.10 s | ||
| 4 | 13.20 s | ||
| 8 | 7.80 s | ||
| 16 | 6.50 s |
- Completar la tabla calculando analíticamente
y 
. - Graficar la curva de Speedup experimental frente a la recta de Speedup ideal (
). - Identificar a partir de qué número de núcleos la eficiencia decae por debajo del
y justificar técnicamente la causa (saturación de ancho de banda de memoria o sobrecarga del planificador del sistema operativo).
Caso 2: Identificación de aceleración superlineal
Un algoritmo de búsqueda en grafos reporta 
en 1 núcleo y 
en 4 núcleos.
- Calcule
y 
. - Explique por qué este fenómeno no viola las leyes fundamentales de la física computacional, relacionándolo con la jerarquía de memoria caché del procesador Intel Core i7 del laboratorio.
4. Entregable
Documento breve en PDF con las tablas completadas, gráficas de 
vs 
, y análisis crítico de los resultados según los criterios de la