Reducir el costo de las operaciones

Reducir el costo de las operaciones en la teoría del compilador consiste en reemplazar las operaciones lentas, como la multiplicación y la división, por otras más rápidas, como la suma, la resta y el desplazamiento. Entonces, la división (multiplicación) por es equivalente a un desplazamiento de bits hacia la derecha (izquierda).

Existen algoritmos para convertir operaciones de multiplicación y división por un número entero arbitrario en una secuencia de operaciones más simples (sumas, restas y desplazamientos). Dicha optimización generalmente la realiza automáticamente el compilador y no requiere la intervención del programador.

Ejemplos

Multiplicación de enteros por 2:

{ antes de la optimización (3 ciclos en Core 2 Duo) } y := 2 * x ; {después de la optimización} y := x + x ; // 1 reloj en Core 2 Duo y := x shl 1 ; // 1 reloj en Core 2 Duo


Multiplicación de enteros por 3:

{ antes de la optimización (3 ciclos en Core 2 Duo) } y := 3 * x ; {después de la optimización} y := x + x + x ; // 2 relojes en Core 2 Duo y := x shl 1 + x ; // 2 relojes en Core 2 Duo y := x shl 2 - x ; // 2 relojes en Core 2 Duo


Multiplicación de enteros por 4:

{ antes de la optimización (3 ciclos en Core 2 Duo) } y := 4 * x ; { después de la optimización (1 ciclo en Core 2 Duo) } y := x shl 2 ;


Multiplicación de enteros por 5:

{ antes de la optimización (3 ciclos en Core 2 Duo) } y := 5 * x ; { después de la optimización (2 ciclos en Core 2 Duo) } y := x shl 2 + x ;


Multiplicación de enteros por 6:

{ antes de la optimización (3 ciclos en Core 2 Duo) } y := 6 * x ; { después de la optimización } y := ( x shl 2 - x ) shl 1 ; // 3 ciclos, implementación subóptima y := x shl 2 + x shl 1 ; // 2 ciclos, siempre que las operaciones de cambio caigan en diferentes actuadores y se realicen en paralelo

Se puede ver que no todos los factores pueden ser reemplazados efectivamente por operaciones más simples. Además, la decisión sobre dicho reemplazo debe tener en cuenta las características de microarquitectura del procesador (al menos la latencia de la ejecución de las operaciones) para las que se realiza dicha optimización (por ejemplo, las operaciones de cambio en el procesador Pentium 4 tardan mucho más ). que en otros procesadores, lo que debe tenerse en cuenta) [1] .

Notas al pie

  1. ↑ En muchos compiladores (por ejemplo, Intel C ++ Compiler ) es posible, usando opciones de línea de comandos, indicar al compilador el procesador en el que se planea ejecutar el programa

Literatura

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compiladores : Principios, Técnicas y Herramientas = Compiladores: Principios, Técnicas y Herramientas. — 2ª edición. - M. : "Williams", 2008. - 1184 p. - 1500 copias.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Reducción de la fuerza del operador, en Munchnik, Steven S. & Jones, Neil D., Análisis de flujo de programas: teoría y aplicaciones , Prentice-Hall, ISBN 978-0-13-729681- una 
  • Cocke, John & Kennedy, Ken (noviembre de 1977), Un algoritmo para la reducción de la fuerza del operador, Comunicaciones de la ACM Vol . 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (octubre de 1995), Reducción de fuerza del operador , Universidad de Rice , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Consultado el 22 de abril de 2010.