Embed Size (px)
Citation preview
Optimización de Software (segunda parte)66.20 Organización de Computadoras
Tipos de Optimizaciones
Intraprocedurales (locales).Aplican a procedimientos individuales.
Interprocedurales (globales).Aplican a varios procedimientos simultáneamente.
Cambio de algoritmos.Utilizar algoritmos con mejor orden de complejidad.
De la Jerarquía de Memoria.Consideran la jerarquía de memoria de base.
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é.
Registrosde la CPU
Caché(L1, L2 y L3)
MemoriaPrincipal
Memoria Secundariay Dispositivos de E/S
Cos
to
Cap
acid
ad y
Tie
mpo
de
acce
so
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. Transformación de bucles. Rellenado de arreglos (array padding). Reducción de solapamiento (aliasing).
Lectura Adelantada (prefetching)
Especula con los accesos futuros a datos e instrucciones. Se implementa a nivel de hardware y, en algunas
arquitecturas, puede controlarse desde el software. Útil en estructuras repetitivas (bucles). Suficiente un prefetch por bloque de la caché.
X[0] X[1] X[2] X[3]
X[4] X[5] X[6] X[7]
X[8] X[9] X[10] X[11]
X[12] X[13] X[14] X[15]
X[0] X[1] X[2] X[3]
X[4] X[5] X[6] X[7]
X[8] X[9] X[10] X[11]
X[12] X[13] X[14] X[15]
16ELEMENTOS
4PREFETCHs
MEMORIACACHÉ
BLOQUE
Lectura Adelantada (prefetching)(cont.) El lenguaje ANSI C permite aplicarlo a datos. Compilar de la siguiente manera:
gcc -march=pentium4 ejemplo01.c -o ejemplo01
Lectura Adelantada (prefetching)(cont.) Si el prefetch se hace
cerca del instante de uso, podría ser demasiado tarde.
Conviene aplicarlo con mayor anticipación.
Es necesario desenrollar el bucle.
¿FACTOR DE DESENROLLADO?
Lectura Adelantada (prefetching)(cont.) ¿Con cuánta anticipación debe leerse (prefetch) un
bloque desde memoria principal a caché? Deberá considerarse:
Cuántos ciclos insume el prefetch para traer el bloque a la caché. Cuántos ciclos insume una iteración del bucle.
Por ejemplo:
TP
TI = 1/3 TP
TP = Tiempo prefetch
TI = Tiempo iteración
Lectura Adelantada (prefetching)(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
Reemplazo de Elementos de Arreglos por Escalares Pocos compiladores intentan mantener los elementos de
un arreglo en registros, entre iteraciones sucesivas.
Reemplazo de Elementos de Arreglos por Escalares (cont.) Reemplazar el elemento de una arreglo por una variable
temporal, para que pueda mantenerse en un registro.
Transformación de Bucles
Fusión / Fisión. Desenrollado. Intercambio. Operación en bloques.
Transformación de Bucles(cont.) Intercambio. 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)
Transformación 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.
A(1,1)
A(1,2)
A(1,3)
A(1,4)
A(2,1)
A(2,2)
A(2,3)
A(2,4)
...
A(1,1)
A(2,1)
A(3,1)
A(4,1)
A(1,2)
A(2,2)
A(3,2)
A(4,2)
...
Orden por filas(row-major order)
Orden por columnas(column-major order)
Transformación de Bucles(cont.) En lenguajes como ANSI C y Pascal se utiliza el
esquema row-major order. Lenguajes como Fortran, utilizan column-major order. Por lo tanto, deben intercambiarse los bucles, de ser
necesario:
Transformación de Bucles(cont.) Operación en bloques. Permite decrementar la cantidad de desaciertos
(misses) en bucles anidados. Mejora la localidad temporal (mantiene en la caché,
datos que se usarán en el corto plazo).
Transformación de Bucles(cont.) Ejemplo: multiplicación de matrices. Elevada cantidad de accesos conflictivos a la caché.
X =
A B C
Transformación de Bucles(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
Rellenado de Arreglos(array padding) Suma de matrices.
+ =
A B C 0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
A(0,0)
A(0,1)
A(0,2)
...
B(0,0)
B(0,1)
B(0,2)
...
0x00000000
0x00000004
0x00000008
0x00000040
0x00000044
C(0,0)
C(0,1)
C(0,2)
0x00000048
0x00000080
0x00000084
0x00000088
...
A(64 bytes)
B(64 bytes)
C(64 bytes)
Rellenado de Arreglos(array padding) (cont.)
Memoria caché DM64 bytes8 bytes por línea
+ =
A B C 0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
0
1
2
3
4
5
6
7
THRASHING
Rellenado de Arreglos(array padding) (cont.)
Memoria caché DM64 bytes8 bytes por línea
+ =
A B C 0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
0 1 2 3
0
1
2
3
0
1
2
3
4
5
6
7
Rellenado de Arreglos(array padding) (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.
Reducción de Solapamiento (aliasing) 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 (aliasing) (cont.)
No sería redundante, si p fuese 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).
Intraprocedurales (locales).Aplican a procedimientos individuales.
Interprocedurales (globales).Aplican a varios procedimientos simultáneamente.
Cambio de algoritmos.Utilizar algoritmos con mejor orden de complejidad.
De la Jerarquía de Memoria.Consideran la jerarquía de memoria de base.
Tipos de Optimizaciones
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.
La Herramienta Gprof
Site: http://www.cs.utah.edu/dept/old/texinfo/as/gprof_toc.html
Soporta los lenguages C/C++ y Fortran. Integrado a la biblioteca GNU Binutils. Aplica la técnica de instrumentación estática de código. Compilar con la opción –pg
gcc -Wall -ansi -pedantic -pg prog.c -o prog
La Herramienta Valgrind
Site: http://valgrind.org/ (última versión: 3.1.1)
Soporta cualquier lenguaje compilado. Público y de código abierto, para ambientes Linux-x86,
Linux-AMD64 y Linux-PPC32. Aplica la técnica de instrumentación dinámica de código. Ejecutar de la siguiente manera:
valgrind --tool=memcheck prog
La Herramienta JProbe
Site: http://www.quest.com/jprobe/ Lenguaje Java. Comercial (aunque existe una versión freeware sin
soporte). Independiente de la plataforma. Aplica la técnica de instrumentación dinámica de código
(dentro de la JVM, a nivel de bytecode). Dispone de una interfaz gráfica.
Ejercicio #1: Padding en P4
Memoria caché L1 en el Pentium 4.
... ... ... ...
32 líneas
64bytes
2-KB
0 1 2 … 255
0
1
2
3
4
Optimizar aplicando padding.
Ejercicio #2: 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
