Programación de Sistemas. Unidad VII.
UNIDAD 7. OPTIMIZACIÓN.
7.1 TIPOS DE OPTIMIZACIÓN.
• La optimización va a depender del lenguaje de programación y es
directamente proporcional al tiempo de compilación; es decir, entre más
optimización mayor tiempo de compilación.
• Las optimizaciones pueden realizarse de diferentes formas. Las
optimizaciones se realizan con base al alcance ofrecido por el
compilador de programación y es directamente proporcional al tiempo
de compilación; es decir, entre más optimización mayor tiempo de
compilación.
• Como el tiempo de optimización es gran consumidor de tiempo (dado
que tiene que recorrer todo el árbol de posibles soluciones para el
proceso de optimización) la optimización se deja hasta la fase de prueba
final.
• Algunos editores ofrecen una versión de depuración y otra de entrega o
final
• La optimización es un proceso que tiende a minimizar o maximizar
alguna variable de rendimiento, generalmente tiempo, espacio,
procesador, etc.
• Desafortunadamente no existen optimizadores que hagan un programa
más rápido y que ocupe menor espacio.
• La optimización se realiza reestructurando el código de tal forma que el
nuevo código generado tenga mayores beneficios. La mayoría de los
compiladores tienen una optimización baja, se necesita de compiladores
especiales para realmente optimizar el código.
Objetivo: Mejorar código objeto final, preservando significado del programa.
Velocidad de ejecución
Factores a optimizar tamaño del programa
Necesidades de memoria
Se sigue una aproximación conservadora
No se aplican todas las posibles optimizaciones, solo las “seguras”
Clasificación de las optimizaciones
1. En función de la dependencia de la arquitectura.
1
Programación de Sistemas. Unidad VII.
• Dependientes de la máquina: aprovechan características especificas de la
maquina objetivo.
Asignación de registros, uso de modos de direccionamiento.
Uso instrucciones especiales (IDIOMS).
Relleno de pipelines, predicción de saltos, aprovechamiento
estrategias de memoria cache, etc.
• Independientes de la máquina: aplicables en cualquier tipo de maquina
objetivo
Ejecución en tiempo de compilación
Eliminación de redundancias
Cambios de orden de ejecución, etc.
2. En función del ámbito de aplicación.
• Optimizaciones locales: aplicadas dentro de un Bloque básico.
Solo estudian las instrucciones de bloque básico actual.
• Optimizaciones globales: aplicadas a más de un bloque básico.
Consideran contenido y flujo de datos entre todos o parte de los
bloques básicos.
Necesidad de recoger información sobre los B.B. y sus
interrelaciones.
Algoritmos de análisis global de flujo de datos
Sobre código fuente (programador/preprocesador)
Posibilidades de optimización: Durante la generación de código objeto
Sobre código intermedio
7.1.1 Locales
La optimización local se realiza sobre módulos de programa. En la mayoría de
las ocasiones a través de funciones, métodos, procedimientos, clases, etc.
La característica de las optimizaciones locales es que solo se ven reflejados en
dichas secciones.
La optimización local sirve cuando un bloque de programa o sección es crítico
por ejemplo: la E/S, la concurrencia, la rapidez y la confiabilidad de un conjunto
de instrucciones.
Como el espacio de soluciones es más pequeño la optimización local es más
rápida. Ejemplos:
2
Programación de Sistemas. Unidad VII.
1. Pre calcular expresiones constantes (con constantes o variables cuyo valor
no cambia).
i=2+3 i=5
j=4 j=4
f = j + 2.5 f = 6.5
2. Reutilización de expresiones comunes
a=b+c a=b+c
d=a–d d=a–d
e=b+c e=a
f=a–d f=d
3. Propagación de copias
• Ante instrucciones f = a, sustituir todos los usos de f por a
a = 3+i
f = a a=3+i
b = f+c b=a+c
d = a+m d=a+m
m= f+d m=a+d
4. Eliminación redundancias en acceso matrices
• Localizar expresiones comunes en cálculo direcciones de matrices.
Código Fuente:
A: array [1..4, 1..6, 1..8] of integer
A[i, j ,5 ] := A[i, j, 6] + A[i, j, 4]
Sin optimización:
direc(A[i, j, 5]) = direc(A[1, 1, 1]) + (i - 1)*6*8 + (j - 1)*8 + (5 - 1)
direc(A[i, j, 6]) = direc(A[1, 1, 1]) + (i - 1)*6*8 + (j - 1)*8 + (6 - 1)
direc(A[i, j, 4]) = direc(A[1, 1, 1]) + (i - 1)*6*8 + (j - 1)*8 + (4 - 1)
Con optimización:
k := direc(A[1, 1, 1]) + (i - 1)*6*8 + (j - 1)*8
direc(A[i, j, 5]) = k + 4
direc(A[i, j, 6]) = k + 5
direc(A[i, j, 4]) = k + 3
5. Transformaciones algebraicas:
Aplicar propiedades matemáticas para simplificar expresiones
A) Eliminar secuencias nulas.
3
Programación de Sistemas. Unidad VII.
x+0 x
1*x x
X/1 x
…
B) Reducción de potencia
o Remplazar una operación por otra equivalente menos costosa
x² x*x
2*x x + x (suma); x<<1 (desplazamiento por la
izquierda)
4*x, 8*x,… x << 2, x << 3,…
X/2 x >> 2
C) Reacondicionamiento de operadores
o Cambiar orden de evaluación aplicando propiedades
conmutativas, asociativas y distributivas.
A := B*C(D + E) ≡ A := (D + E)* B*C
MOV B,R0
MOV C,R0 MOV D,R0
MOV R0,t1 ADD E,R0
MOV D, R0 MUL B,R0 5 instrucciones
ADD E,R0 MUL C,R0 0 temporales
MUL t1,R0 MOV R0,A
MOV R0,A
7.1.2 Bucles.
• Los ciclos son una de las partes más esenciales en el rendimiento de un
programa dado que realizan acciones repetitivas, y si dichas acciones
están mal realizada, el problema se hace N veces más grandes.
• La mayoría de las optimizaciones sobre ciclos tratan de encontrar
elementos que no deben repetirse en un ciclo.
Ciclos
while (a == b)
{int c = a; c = 5;…;}
En este caso es mejor pasar el int c=a; fuera del ciclo de ser posible.
Ciclos
• El problema de la optimización en ciclos y en general radica es muy
difícil saber el uso exacto de algunas instrucciones. Así que no todo
código de proceso puede ser optimizado.
• Otro uso de la optimización puede ser el mejoramiento de consultas en
SQL o en aplicaciones remotas (sockets, E/S, etc.).
Optimización de Ciclos
4
Programación de Sistemas. Unidad VII.
Idea: Centrar la optimización en partes más usadas, no en todo el
programa.
Optimizar ciclos internos
Mejoras factorización de expresiones invariantes
Reducción de intensidad y eliminación de variables de inducción
Factorización de expresiones invariantes
Expresiones Invariantes de ciclo: expresiones cuyo valor es constante
durante toda la ejecución del ciclo.
Incluyen constantes y/o variables no modificadas en el cuerpo del ciclo.
Idea: Mover expresiones Invariantes desde el cuerpo hasta la cabeza del
ciclo.
Al sacarlas del ciclo, pueden quedar dentro de otro ciclo externo
repetir proceso.
Ejemplos:
While ( i<= ( limite*2 - 1 ) ) do { tmp1 = limite*2 -
1;
… while ( i<=
tmp1 ) {
} …
}
A: array [ 1…900, 1…900, 1.900] of integer
for i:=1 to 900 do for
i:= 1 to 900 do
for i:=1 to 900 do for j:=1 to 900 do
tmp3:= dir(A[i]);
for j:=1 to 900 do tmp1 := i*j; for
j:= 1 to 900 do
for k:=1 to 900 do tmp2 := dir (A[i][j])
tmp1 := i*j;
A [i] [j] [k] := i*j*k; for k := 1 to 900 do
tmp2 := dir (tmp3[j]);
end for tmp2[k] := tmp1*k; for
k:= 1 to 900 do
end for end for
tmp2[k] := tmp1*k;
5
Programación de Sistemas. Unidad VII.
end for end for
end for
end for
end for
end for
i, j y a [i][j] son A[i] es constante
constantes en el bucle de k en el bucle de j
• En C.I. aparecerán mas invariantes al incluir el cálculo de
desplazamientos en arreglos basados en el tamaño de los datos
(int 4, float 8,…)
7.1.3 Globales
• En algunas casos es mejor mantener variables globales para
agilizar los procesos (el proceso de declarar variables y eliminarlas
toma su tiempo) pero consume más memoria.
• Algunas optimizaciones incluyen utilizar como variables registros
del CPU, utilizar instrucciones en ensamblador.
Optimizaciones Globales
Optimizaciones entre Bloques Básicos
Optimizaciones típicas:
Identificación de expresiones comunes entre bloques
→ afecta a la asignación de registros entre B.B.
Optimización de llamadas a procedimientos
Optimización de bucles
Optimización de Llamadas a Procedimientos
Llamadas a procedimientos son muy costosas
Cambios del ámbito de referencias
Gestión de Registros de Activación
Paso de parámetros + asignación de datos locales
Mejoras
1. Optimizar manejo de Registro de Activación
Minimizar copia de parámetros y números de registros a salvar
Uso almacenamiento estático si no hay llamadas recursivas
2. Expansión en línea.
Idea: Eliminar llamadas a procedimientos, “copiando” el cuerpo del
procedimiento en el lugar donde es llamado
6
Programación de Sistemas. Unidad VII.
Evita sobrecarga asociada con las llamadas a procedimientos
Permite optimizaciones adicionales
→ el código llamado pasa a ser parte del código que lo llama
Limitaciones
Aumenta uso de memoria → útil en los procedimientos pequeños y
llamados desde pocos lugares
→ Si se llama en un único lugar (es frecuente) , no supone coste de
espacio adicional
No aplicable en procedimientos recursivos
Ejemplos:
Directiva inline en C++ y Java
En C puede simularse con macros #define
7.1.4 De Mirilla.-
La optimización de mirilla trata de estructurar de manera eficiente el
flujo del programa, sable todo en instrucciones de bifurcación como son
las decisiones, ciclos y saltos de rutinas.
La idea es tener los saltos lo más cerca de las llamadas, siendo el salto
más pequeño posible.
Idea Básica
Se recorre el código buscando combinaciones de instrucciones que
puedan ser remplazadas por otras equivalentes más eficientes.
Se utiliza una ventana de n instrucciones y un conjunto de patrones de
transformación (patrón, secuencias reemplazan).
Si las instrucciones de la venta encajan con algún patrón se reemplazan
por la secuencia de reemplazamiento asociada.
Las nuevas instrucciones son reconsideradas para las futuras
optimizaciones.
Ejemplo:
Eliminación de cargas innecesarias
MOV Ri, X MOV Ri, Rj
MOV X, Rj
Reducción de potencia
Eliminación de cadenas de saltos
if C goto L1 if C goto L2
L1: goto L2
7
Programación de Sistemas. Unidad VII.
if C goto L1 if not C goto FIN
goto FIN
L1: … L1: …
… FIN:
FIN:
7.2 COSTOS.-
Los costos son el factor más importante a la hora de optimizar ya que en
ocasiones la mejora obtenida puede verse no reflejada en el programa
final pero si ser perjudicial para el equipo de desarrollo.
La optimización de una pequeña mejora tal vez tenga una pequeña
ganancia en tiempo o en espacio pero sale muy costosa en tiempo en
ganancia.
Pero en cambio si esa optimización se hace por ejemplo en un ciclo, la
mejora obtenida puede ser N veces mayor por lo cual el costo se
minimizara y es benéfico la mejora.
7.2.1 Costos de Ejecución.-
Los costos de ejecución son aquellos que vienen implícitos al ejecutar el
programa.
En algunas programas se tiene un mínimo para ejecutar el programa por
lo que el espacio y la velocidad del microprocesador son elementos que
se deben optimizar para tener un mercado potencial más amplio,
Las aplicaciones multimedia como los videojuegos tienen un costo de
ejecución alto por lo cual la optimización de su desempeño es crítico, la
gran mayoría de las veces requieren de procesadores rápidos (ejemplo
tarjetas de video) o de mucha memoria.
Otro tipo de aplicaciones que deben optimizarse son las aplicaciones
para dispositivos móviles.
Los dispositivos móviles tienen recursos más limitados que un dispositivo
de cómputo convencional razón por la cual, el mejor eso de memoria y
otros recursos de hardware tiene mayor rendimiento.
En algunos casos es preferible tener la lógica del negocio más fuerte que
en otros dispositivos y hacer uso de arquitecturas descentralizadas como
cliente/servidor o P2P.
7.2.2 Criterios para mejorar código.-
8
Programación de Sistemas. Unidad VII.
La mejor manera de optimizar el código es hacer ver a los
programadores que optimicen su código desde el inicio, el problema
radia en el costo podría ser muy grande ya que tendría que codificar
mas y/o hacer su código mas legible.
Los criterios de optimización siempre están definidos por el compilador.
Muchos de estos criterios pueden modificarse con directivas del
compilador desde el código móvil y código para dispositivos móviles.
7.2.3 Herramientas para el Análisis del Flujo de Datos.-
Existen algunas herramientas que permiten el análisis de flujo de datos,
entre ellas tenemos los depuradores y desambladores.
La optimización al igual que la programación es un arte y no se ha
podido sistematizar del todo.
FIN DE LA UNIDAD VII.
