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 editar

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:

 

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:

 

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 editar

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

 

donde

  • Slatencia es la speedup en latencia de la arquitectura 2 respecto a la arquitectura 1;
  • L1 es la latencia de la arquitectura 1;
  • L2 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 editar

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

 

donde

  • Sthroughput es la speedup en throughput de la arquitectura 2 respecto a la arquitectura 1;
  • Q1 es la throughput de la arquitectura 1;
  • Q2 es la throughput de la arquitectura 2.

Ejemplos editar

Usando tiempos de ejecución editar

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

 

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

Usando ciclos por instrucción e instrucciones por ciclo editar

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

 

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

 

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

Speedup lineal y super-lineal editar

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

 

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 editar

Referencias editar

  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.