Optimización de
Software
66.20 Organización de Computadoras
Introducción

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.
¿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.
Tipos de Optimizaciones

Locales.
Aplican localmente a un procedimiento individual.
(a.k.a., “intraprocedurales”)

Globales.
Aplican globalmente a varios procedimientos.
(a.k.a., “interprocedurales”)
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).
Tipos de Optimizaciones

Locales.
Aplican localmente a un procedimiento
individual.
(a.k.a., “intraprocedurales”)

Globales.
Aplican globalmente a varios procedimientos.
(a.k.a., “interprocedurales”)
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…..
…no subestimar la posibilidad de cambiar el algoritmo.




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
RADIX-4 reduce en un 15%
el número de operaciones
Jerarquías de Memoria

Registros
de la CPU
Caché
(L1, L2 y L3)
Memoria
Principal
Memoria Secundaria
y Dispositivos de E/S
Capacidad y
Tiempo de acceso

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é.
Costo

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 la
Jerarquí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é.
BLOQUE
16
ELEMENTOS
X[0]
X[1]
X[2]
X[3]
X[0]
X[1]
X[2]
X[3]
X[4]
X[5]
X[6]
X[7]
X[4]
X[5]
X[6]
X[7]
X[8]
X[9]
X[10]
X[11]
X[8]
X[9]
X[10]
X[11]
X[12]
X[13]
X[14]
X[15]
X[12]
X[13]
X[14]
X[15]
4
PREFETCHs
MEMORIA
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 = Tiempo prefetch
TP
TI = Tiempo iteración
TI = 1/3 TP
Lectura Adelantada (cont.)

x[0] …
x[7]
Se debe generar un pipeline para que el bucle no deba
esperar.
x[8] …
x[15]
x[16] …
x[23]
x[24] … x[31]
x[32] … x[39]
Distancia
d=3
x[40] … x[47]
PROCESA
x[0] … x[7]
PROCESA
x[8] … x[15]
PROCESA
x[16] … x[23]
En general  d = TP / TI
PROCESA
x[24] … x[31]
…
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 bytes
Tamaño double: 8 bytes
Costo acumulación: 25 ciclos
Costo 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 Orden por columnas
(row-major order) (column-major order)
A(1,1)
A(1,1)
A(1,2)
A(2,1)
A(1,3)
A(3,1)
A(1,4)
A(4,1)
...
...
A(2,1)
A(1,2)
A(2,2)
A(2,2)
A(2,3)
A(3,2)
A(2,4)
A(4,2)
Intercambio de Bucles (cont.)



C/C++, Java, Pascal utilizan row-major order.
Fortran y versiones viejas de BASIC, utilizan columnmajor 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%
X
A
=
B
C
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é.
X
A
=
B
C
Operación en Bloques (cont.)
2WSA 2-KB (bloque de 32 bytes)
Optimización de Memoria #5:
Rellenado de Arreglos (padding)

...
Suma de matrices.
0x00000088
0x00000084
A
0
1
B
2
3
0
0
1
1
C
2
3
0
0
+
1
1
0x00000080
2
3
0
=
C(0,2)
C(0,1)
C(0,0)
...
1
2
2
2
3
3
3
C
(64 bytes)
0x00000048
0x00000044
0x00000040
B(0,2)
B(0,1)
B(0,0)
B
(64 bytes)
...
0x00000008
0x00000004
0x00000000
A(0,2)
A(0,1)
A(0,0)
A
(64 bytes)
Rellenado de Arreglos (cont.)
A
0
1
B
2
3
0
0
1
1
C
2
3
0
0
+
1
1
2
3
0
=
1
2
2
2
3
3
3
0
THRASHING
1
2
3
4
5
6
7
Memoria caché DM
64 bytes
8 bytes por línea
Rellenado de Arreglos (cont.)
A
0
1
B
2
3
0
0
1
1
C
2
3
0
0
+
1
1
2
3
0
=
1
2
2
2
3
3
3
0
1
2
3
4
5
6
7
Memoria caché DM
64 bytes
8 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 lectura
(8 cada 8 lecturas)
Desaciertos de escritura en
la matriz (8 cada 8 escrituras)
Rellenado de Arreglos (cont.)
Con rellenado:
Rellenos
Desaciertos de lectura de
matrices A y B (1 cada 8 lecturas)
Desaciertos de escritura en la
matriz C (1 cada 8 escrituras)
Ejercitación: Padding
2-KB
64
bytes
32 líneas
...
0
0
1
Asumir que el primer elemento
de la matriz se almacena en la
dirección 0x00000000
2
3
4
1
...
...
2
…
...
255
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.)
…
p = &a;
…
No sería redundante, si p
fuese un “alias” de 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).
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
Descargar

El Simulador SPIM (segunda parte)