Speedup

En arquitectura de computadores, speedup 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.^[1]​

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

${\displaystyle 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:

${\displaystyle 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:^[2]​

${\displaystyle 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₁ es la latencia de la arquitectura 1;
• L₂ 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:^[3]​

${\displaystyle 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₁ es la throughput de la arquitectura 1;
• Q₂ 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

${\displaystyle 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

${\displaystyle 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

${\displaystyle 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

${\displaystyle \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.^[4]​

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.^[5]​

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.^[6]​ 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.^[7]​

Véase también

• Ley de Amdahl
• Ley de Gustafson
• Ley de Brooks
• Teorema del aumento de velocidad
• Escalabilidad

Referencias

1. Martin, Milo. «Performance and Benchmarking» (en inglés). Consultado el 10 de noviembre de 2017. 
2. Hennessy, John L.; David A., Patterson (2012). Computer Architecture: A Quantitive Approach (en inglés). Waltham, MA: Morgan Kaufmann. pp. 46–47. ISBN 978-0-12-383872-8. 
3. Baer, Jean-Loup (2010). Microprocessor Architecture: From Simple Pipelines to Chip Multiprocessors (en inglés). New York: Cambridge University Press. pp. 10. ISBN 978-0-521-76992-1. 
4. Benzi, John; Damodaran, M. (2007). «Parallel Three Dimensional Direct Simulation Monte Carlo for Simulating Micro Flows». Parallel Computational Fluid Dynamics 2007: Implementations and Experiences on Large Scale and Grid Computing. Parallel Computational Fluid Dynamics (en inglés). Springer. p. 95. Consultado el 10 de noviembre de 2017. 
5. Feng, Wu-chun. «Green Destiny + mpiBLAST = Bioinfomatics» (en inglés). Consultado el 10 de noviembre de 2017. 
6. Speckenmeyer, Ewald (2005). «Superlinear Speedup for Parallel Backtracking». Lecture Notes in Computer Science (en inglés) 297: 985-993. 
7. «Gurobi versus CPLEX benchmarks» (en inglés). Michael Trick's Operations Research Blog. Consultado el 10 de noviembre de 2017. 

•   Datos: Q1549489