Speedup
# Speedup

En arquitectura de computadores, speedup (aceleración en castellano) es un proceso realizado para mejorar el rendimiento de un sistema que procesa un problema determinado. Más técnicamente, es la mejora en la velocidad de ejecución de una tarea ejecutada en dos arquitecturas similares con diferentes recursos. La noción de speedup fue establecida por la ley de Amdahl, que estaba dirigida particularmente a la computación paralela. Sin embargo, la speedup se puede usar más generalmente para mostrar el efecto en el rendimiento después de cualquier mejora en los recursos.

## Definiciones

La speedup se puede definir para dos diferentes tipos de cantidades: latencia y throughput.

La latencia de una arquitectura es el recíproco de la velocidad de ejecución de una tarea:

    $L={\frac {1}{v}}={\frac {T}{W}},$

donde

* v es la velocidad de ejecución de la tarea;
* T es el tiempo de ejecución de la tarea;
* W es la carga de trabajo de la tarea.

La throughput de una arquitectura es la tasa de ejecución de una tarea:

    $Q=\rho vA={\frac {\rho AW}{T}}={\frac {\rho A}{L}},$

donde

* ρ es la densidad de ejecución (es decir, el número de fases en una arquitectura segmentada);
* A es la capacidad de ejecución (es decir, el número de procesadores en una arquitectura paralela).

La latencia se mide habitualmente en segundos por unidad de carga de ejecución, y la throughput se mide habitualmente en unidades de carga de ejecución por segundo. Otra unidad de throughput son las instrucciones por ciclo (IPC), y su recíproco, los ciclos por instrucción (CPI), es otra unidad de latencia.

La speedup es un número sin dimensión y está definido de manera diferente para cada tipo de cantidad de manera que sea una métrica consistente.

### Speedup en latencia

La speedup en latencia está definida por la siguiente fórmula:

    $S_{\text{latencia}}={\frac {L_{1}}{L_{2}}}={\frac {T_{1}W_{2}}{T_{2}W_{1}}},$

donde

* $S_{latencia}$ es la speedup en latencia de la arquitectura 2 respecto a la arquitectura 1;
* $L_1$ es la latencia de la arquitectura 1;
* $L_2$ es la latencia de la arquitectura 2.

La speedup en latencia se puede predecir con la ley de Amdahl o la ley de Gustafson.

### Speedup en throughput

La speedup en throughput está definida por la siguiente fórmula:

    $S_{\text{throughput}}={\frac {Q_{2}}{Q_{1}}}={\frac {\rho _{2}A_{2}T_{1}W_{2}}{\rho _{1}A_{1}T_{2}W_{1}}}={\frac {\rho _{2}A_{2}}{\rho _{1}A_{1}}}S_{\text{latencia}},$

donde

* $S_{throughput}$ es la speedup en throughput de la arquitectura 2 respecto a la arquitectura 1;
* $Q_1$ es la throughput de la arquitectura 1;
* $Q_2$ es la throughput de la arquitectura 2.

## Ejemplos

### Usando tiempos de ejecución

Estamos probando la efectividad de un predictor de saltos en la ejecución de un programa. Primero, ejecutamos el programa con el predictor de saltos estándar en el procesador, lo que consigue un tiempo de ejecución de 2,25 segundos. A continuación, ejecutamos el programa con nuestro predictor de saltos modificado (y esperamos mejorado) en el mismo procesador, lo que produce un tiempo de ejecución de 1,50 segundos. En ambos casos la carga de ejecución es la misma. Usando nuestra fórmula de speedup, sabemos que

    $S_{\text{latencia}}={\frac {L_{\text{antigua}}}{L_{\text{nueva}}}}={\frac {2,25~\mathrm {s} }{1,50~\mathrm {s} }}=1,5.$

Nuestro nuevo predictor de saltos ha conseguido una speedup de 1,5x sobre el original.

### Usando ciclos por instrucción e instrucciones por ciclo

También podemos medir la speedup en ciclos por instrucción (CPI), que es una medida de latencia. Primero, ejecutamos el programa con el predictor de saltos estándar, lo que nos da un CPI de 3. A continuación, ejecutamos el programa con nuestro predictor de saltos modificado, lo que consigue un CPI de 2. En ambos casos la carga de ejecución es la misma y ambas arquitecturas no son segmentadas ni paralelas. Usando la fórmula de la speedup

    $S_{\text{latencia}}={\frac {L_{\text{antigua}}}{L_{\text{nueva}}}}={\frac {3~{\text{CPI}}}{2~{\text{CPI}}}}=1,5.$

También podemos medir la speedup en instrucciones por ciclo (IPC), que es una medida de throughput y el inverso del CPI. Usando la fórmula de speedup nos da

    $S_{\text{throughput}}={\frac {Q_{\text{nuevo}}}{Q_{\text{antiguo}}}}={\frac {0,5~{\text{IPC}}}{0,33~{\text{IPC}}}}=1,5.$

Vemos que obtenemos el mismo speedup de 1,5x, aunque usamos diferentes cantidades.

## Speedup lineal y super-lineal

Sea S la speedup de ejecución de una tarea y s la speedup de ejecución de la parte de la tarea que se beneficia de la mejora de los recursos de una arquitectura. La speedup lineal o ideal se obtiene cuando S = s. Cuando se ejecuta una tarea con speedup lineal, doblar la speedup local duplica la speedup global. Dado que esto es ideal, está considerado muy buena escalabilidad.

La eficiencia es una métrica de la utilización de los recursos del sistema mejorado definida como

    $\eta ={\frac {S}{s}}.$

Su valor está típicamente entre 0 y 1. Los programas con speedup lineal y los programas que se ejecutan en un único procesador tienen una eficiencia de 1, mientras que muchos programas difíciles de paralelizar tienen eficiencias como 1/ln(s) que se aproximan a 0 a medida que aumenta el número de procesadores A = s.

En algunas ocasiones se puede producir un speedup superior a A cuando se usan A procesadores en computación paralela, lo que es llamado speedup super-lineal. La speedup super-lineal rara vez ocurre y a menudo confunde a los principiantes, que creen que la máxima speedup teórica cuando se usan A procesadores debería ser A.

Una razón posible para la speedup super-lineal en cálculos de bajo nivel es el efecto caché producido por las diferentes jerarquías de memoria de un computador moderno: en computación paralela, no solo cambia el número de procesadores, sino también el tamaño de las cachés de los procesadores. Con un mayor tamaño acumulado de caché, más parte o casi todo el conjunto de trabajo puede estar en las cachés y el tiempo de acceso a memoria se reduce espectacularmente, lo que causa el speedup adicional al producido por el cómputo real.

Ocurre una situación análoga cuando se manipulan grandes conjuntos de datos, como los datos genómicos procesados por el programa BLAST: la RAM acumulada de todos los nodos del clúster permite que el conjunto de datos se mueva del disco a la RAM, reduciendo así espectacularmente el tiempo necesitado por programas como mpiBLAST para acceder a ellos.

También se producen speedups super-lineales cuando se realiza backtracking en paralelo: una excepción en un hilo puede causar que varios otros hilos retrocedan antes de que alcancen la excepción. También se pueden producir speedups super-lineales en implementaciones paralelas de ramificación y poda para optimización: el procesamiento de un nodo por un procesador puede afectar el trabajo que otros procesadores tienen que hacer para los otros nodos.

