optimización de softwarematerias.fi.uba.ar/6620/clases/clase7.pdf · según el lenguaje, un...

Optimización de Software

66.20 Organización de Computadoras

� Optimizar la performance significa:� Minimizar el tiempo de ejecución.� Minimizar los requerimientos de memoria.� Minimizar el consumo de energía.

� Se buscan optimizaciones:� Conservadoras (no alteran la lógica del programa).� Que no empeoren otros casos.

Introducción

¿Quién optimiza?

� El usuario (programador), conociendo los detalles de la arquitectura de base.

� El compilador, con diferentes niveles de agresividad(-O0, -O1, -O2, etc.).

Ambos están limitados a ciertas optimizaciones.

Tiempos de Ejecución

� Interesan para determinar si una optimización puede ser factible.

� Algunos lenguajes poseen herramientas elementales (e.g., función clock() de ANSI C).

� Algunos procesadores brindan facilidades para medir tiempos.

� Existen herramientas para este fin (profilers).

Herramientas de Profiling

� Un profiler es una herramienta para análisis de performance.

� Mide la ejecución de un programa y recoge información estadística.

� Reporta la duración y frecuencia de llamada a rutinas.

� Una de las técnicas más usadas es la instrumentación

de código (estática o dinámica).

� Algunos de los más usados: Gprof, Valgrind y JProbe.

� Locales.Aplican localmente a un procedimiento individual.(a.k.a., “intraprocedurales”)

� Globales.Aplican globalmente a varios procedimientos.(a.k.a., “interprocedurales”)

Tipos de Optimizaciones

Optimizaciones Locales

� Asignación de registros.

� Eliminación de código inalcanzable y código muerto.

� Plegado y propagación de constantes.

� Reducción del costo de operaciones.

� Optimización de bucles.

Optimización Local #1:Asignación de Registros

� Implica determinar qué variables deberían estar en registros en cada instante de la ejecución.

� Los registros de CPU son un recurso escaso.

� Se busca minimizar el tráfico entre los registros y la memoria (spilling).

� Optimización de bajo nivel (poco puede hacer el programador).

Asignación de Registros (cont.)

� Lenguajes C/C++ ofrecen el modificador register

� “Aconseja” al compilador mantener una determinada variable en un registro del procesador.

� El compilador podría ignorarlo.

Asignación de Registros (cont.)

Optimización Local #2:Eliminación de Código …

� A las instrucciones que nunca se ejecutan se las denomina código inalcanzable.

� A las instrucciones que no producen efectos en el resultado, se las denomina código muerto.

� Generan código de máquina que ocupa espacio en la memoria caché de instrucciones.

Código muerto

Código inalcanzable

Optimización Local #3:Plegado y Propagación de Ctes.� Plegado de constantes (constant folding): evaluación de

expresiones con múltiples constantes.

� Propagación de constantes (constant propagation): reemplazo de una variable por una constante.

Sin optimizar

Optimizado

Optimización Local #4:Reducción del Costo de Op.� Reemplazar multiplicación o división entera por

operaciones de desplazamiento.

� Reemplazar la multiplicación por una constante pequeña por sumas.

Optimización Local #5:Optimización de Bucles� Optimización de la variable de control.

� Cuando el cómputo es lineal respecto a la variable de inducción.

Optimización de Bucles (cont.)

� Extracción de estructuras condicionales.

� Los branches reducen la performance porque interfieren el pipeline.

� Aplicable por el programador.

Optimización de Bucles (cont.)

� Pelado de bucles (loop peeling).

� Se extrae el manejo de condiciones de borde.

� Aplicable por el programador (ya que es compleja).

Optimización de Bucles (cont.)

� Desenrollado de bucles.

� Alivia el costo relacionado al control del bucle.

� Facilita la aplicación de otros tipos de optimizaciones.

No desenrollado

Desenrollado en un factor

de 10

Optimización de Bucles (cont.)

� Promoción de código invariante.

� Código invariante es aquel que no cambia entre iteraciones del bucle que lo contiene.

Código invariante

Optimización de Bucles (cont.)

� Fusión de bucles.

� Los bucles deben tener el mismo espacio de iteraciones.

� Aplicable por el programador (ya que es compleja).

� Locales.Aplican localmente a un procedimiento

individual.

(a.k.a., “intraprocedurales”)

� Globales.Aplican globalmente a varios procedimientos.

(a.k.a., “interprocedurales”)

Tipos de Optimizaciones

Optimización Global #1:Expansión en Línea (inlining)� Reemplaza la llamada por el cuerpo de la rutina.

� Reduce el costo en llamadas a procedimientos (sobre todo si son pequeños y de uso frecuente).

� Como contra, genera binarios grandes, lo cual puede perjudicar la localidad en la caché de instrucciones.

� En general, se hace a nivel de compilador.

Expansión en Línea (inlining)(cont.)� En ANSI C, utilizando la directiva __inline__ y

compilando con optimización nivel 1 (-O1).

Sin optimizar

Optimizado

¿Qué otra optimización está aplicando?

Regla de Oro…..

� Ganancias muy importantes.� No puede realizarlo el compilador.� Busca reducir el orden de complejidad.� En ocasiones, solo se reduce la cant. de operaciones.

Ejemplo: Ordenamiento RADIX.� RADIX-2 con complejidad 5 x N x log2 N

� RADIX-4 con complejidad 4.25 x N x log2 N

…no subestimar la posibilidad de cambiar el algoritmo.

RADIX-4 reduce en un 15% el número de operaciones

Jerarquías de Memoria

� La memoria incrementa su velocidad en un 10% a 20% anual.

� El procesador lo hace en un 50% anual.

� La brecha creciente la compensan las memorias caché.

Jerarquías de Memoria (cont.)

� Las memorias caché capturan la localidad espacial y temporal de datos e instrucciones.

� En algunos procesadores, están separadas (I-cache y D-cache).

� Organizaciones típicas:� Correspondencia Directa (Direct Mapped)

� Asociativa por Conjunto, de k vías (k-Way Set Associative).

� Completamente Asociativa (Fully Associative).

Jerarquías de Memoria (cont.)

� La organización de correspondencia directa sufre de thrashing.

� El esquema asociativo por conjunto lo reduce o elimina.

Optimizaciones de laJerarquía de Memoria� Lectura adelantada (prefetching) de datos e

instrucciones.� Reemplazo de elementos de arreglos por escalares.� Intercambio de bucles.� Operación en bloques.� Rellenado de arreglos (array padding).� Reducción de solapamiento (aliasing).

Optimización de Memoria #1:Lectura Adelantada (prefetching)� Especula con los accesos futuros a datos e instrucciones.� Se implementa a nivel de hardware y, en algunos casos,

puede controlarse desde el software.� Suficiente un prefetch por bloque de la caché.

Lectura Adelantada (cont.)

� Útil en bucles con patrones de acceso simples (aplicaciones científicas).

� En lenguaje C, es posible realizar una lectura adelantada mediante __builtin_prefetch(), si la arquitectura lo soporta.

Desde MIPS IV, se soporta prefetching mediante la

instrucción pref

Lectura Adelantada (cont.)

� ¿Con cuánta anticipación debe leerse un bloque desde memoria principal a caché?

� Si se hace cerca del instante de uso, podría ser tarde.� Conviene aplicarlo con mayor anticipación.� Deberá considerarse:

� Cuántos tiempo insume el prefetch.� Cuántos tiempo insume una iteración del bucle.

� Por ejemplo:

TP

TI = 1/3 TP

TP = Tiempo prefetch

TI = Tiempo iteración

Lectura Adelantada (cont.)

� Se debe generar un pipeline para que el bucle no deba esperar.

x[24] … x[31]

PROCESAx[0] … x[7]

PROCESAx[8] … x[15]

PROCESAx[16] … x[23]

PROCESAx[24] … x[31] …

x[32] … x[39]

x[40] … x[47]

x[16] …x[23]

x[8] …x[15]

x[0] …x[7]

Distancia d = 3

En general � d = TP / TIEn general � d = TP / TI

Lectura Adelantada (cont.)

Agregar una estructura condicional (if..else) o desenrollar el bucle, para no ejecutar el prefetch en todas las iteraciones.

FACTOR DE DESENROLLADO

IGUAL A LA CANT. DE ELEMENTOS POR BLOQUE DE CACHÉ

Ejercitación: Prefetching

� Optimizar utilizando lectura adelantada (prefetching).

� Determinar:� Factor de desenrollado del bucle.

� Distancia d.

DATOS:Línea caché: 32 bytesTamaño double: 8 bytesCosto acumulación: 25 ciclosCosto prefetch: 300 ciclos

Optimización de Memoria #2:Reemplazo de Elem. de Arreglos…� Pocos compiladores intentan mantener los elementos de

un arreglo en registros, entre iteraciones sucesivas.� Reemplazar el elemento de una arreglo por una variable

temporal, para que pueda mantenerse en un registro.

Optimización de Memoria #3:Intercambio de Bucles� Según el lenguaje, un arreglo multidimensional podría

almacenarse en memoria, ordenado por filas o por columnas.

Orden por filas(row-major order)

Orden por columnas(column-major order)

Intercambio de Bucles (cont.)

� Se busca acceder al arreglo en pasos unitarios (unit stride).

� Esto permite aprovechar la localidad espacial en la memoria caché de datos.

Orden por filas(row-major order)

Orden por columnas(column-major order)

Intercambio de Bucles (cont.)

� C/C++, Java, Pascal utilizan row-major order.

� Fortran y versiones viejas de BASIC, utilizan column-

major order.

� Por lo tanto, deben intercambiarse los bucles, de ser necesario:

Intercambio de Bucles (cont.)

Usando row-major order:

Desaciertos de escritura en la matriz (1 cada 8 escrituras)

Intercambio de Bucles (cont.)

Usando column-major order:

Desaciertos de escritura en la matriz (8 cada 8 escrituras)

Optimización de Memoria #4:Operación en Bloques� Permite decrementar la cantidad de desaciertos de

capacidad cuando se opera con arreglos grandes.

� Mejora la localidad temporal (mantiene en la caché, datos que se usarán en el corto plazo).

Operación en Bloques (cont.)

� Ejemplo: multiplicación de matrices.

� Elevada cantidad de desaciertos.

� Para una caché 2WSA 2-KB con bloques de 32 bytes, multiplicar dos matrices de 64x64 enteros, produce una tasa de desaciertos del 11,3%

Operación en Bloques (cont.)

� Solución: operar en bloques pequeños.

� Se reducen los accesos conflictivos, ya que los bloques pequeños pueden ser mantenidos en la caché.

Operación en Bloques (cont.)

2WSA 2-KB (bloque de 32 bytes)

Optimización de Memoria #5:Rellenado de Arreglos (padding)� Suma de matrices.

A(64 bytes)

B(64 bytes)

C(64 bytes)

Rellenado de Arreglos (cont.)

Memoria caché DM64 bytes8 bytes por línea

THRASHING

Rellenado de Arreglos (cont.)

Memoria caché DM64 bytes8 bytes por línea

Rellenado de Arreglos (cont.)

� Se cambia la forma en que los arreglos son almacenados en memoria principal.

� Reduce los accesos conflictivos.

� Disminuye el thrashing y, por consiguiente, la cantidad de desaciertos.

� Como desventaja, utiliza mayor cantidad de memoria.

Rellenado de Arreglos (cont.)

Sin rellenado:

Desaciertos de escritura en la matriz (8 cada 8 escrituras)

Desaciertos de lectura (8 cada 8 lecturas)

Rellenado de Arreglos (cont.)

Con rellenado:

Desaciertos de escritura en la matriz C (1 cada 8 escrituras)

Desaciertos de lectura de matrices A y B (1 cada 8 lecturas)

Rellenos

Ejercitación: Padding

32 líneas

64bytes

2-KB

Asumir que el primer elemento de la matriz se almacena en la

dirección 0x00000000

Optimización de Memoria #6:Reducción de Solapamiento� Un dato en memoria puede ser accedido de diferentes

maneras.

� Es importantes disminuir el aliasing para lograr optimizaciones más agresivas.

¿Redundante?

Reducción de Solapamiento (cont.)

No sería redundante, si pfuese un “alias” de a.

…

p = &a;

…

El programador puede “prometerle” al compilador que no existen “alias”. Así, le permite realizar optimizaciones

más agresivas (como eliminación de código redundante).

El programador puede “prometerle” al compilador que no existen “alias”. Así, le permite realizar optimizaciones

más agresivas (como eliminación de código redundante).

Algo sobre Valgrind

� Herramienta para profiling y debugging.

� Site: http://valgrind.org/

� Soporta cualquier lenguaje compilado.

� Pública y de código abierto.

� Aplica la técnica de instrumentación dinámica de código.� Ejemplo de ejecución:

valgrind --tool=<tool> my_prog

Algo sobre Valgrind (cont.)

� Cachegrind es el módulo para simulación de memorias caché.

� Junto con la herramineta cg_annotate, es posible detectar el origen de los desaciertos en caché.

$ valgrind --tool=cachegrind --D1=2048,2,32 prueba

(genera un archivo cachegrind.out.<pid>)

$ cg_annotate --<pid> prueba.c

IMPORTANTE: no olvidar compilar prueba.c utilizando la opción -g para incluir información de debugging útil para Valgrind).

Optimización de Software

66.20 Organización de Computadoras