Análisis Y Comparación Entre Diferentes Metaheurísticas Para El

Transcript

“ANÁLISIS Y COMPARACIÓN ENTRE DIFERENTES METAHEURÍSTICAS PARA EL PROBLEMA DE INLINING DE FUNCIONES” Fernanda Kri Amar Departamento de Ingeniería Civil Informática Universidad de Santiago de Chile e-mail:[email protected], [email protected] Paz Caro Verdugo Departamento de Ingeniería Civil Informática Universidad de Santiago de Chile e-mail:[email protected] Resumen El problema inlining consiste en reemplazar las llamadas de funciones por una copia modificada del cuerpo de esta función. En este artículo se realiza un estudio comparativo entre cuatro metaheurísticas para resolver el problema de inlining de funciones. Las metaheurísticas utilizadas son un algoritmo genético secuencial y paralelo, simulated annealing y por último búsqueda tabú. En general las metaheurísticas han demostrado que resuelven bien los problemas NP-Completo y el problema de inlining corresponde a un problema de este tipo. Para realizar la comparación se incorporan las metaheurísticas al compilador GCC a fin de obtener resultados reales. Los resultados obtenidos muestran que no existe una diferencia significativa al resolver el problema de inlining para los benchmark utilizados. Palabras claves: compilación, metaheurísticas, problema inlining. Introducción El proceso de compilación [1] consiste en traducir un programa escrito en un lenguaje fuente a un programa equivalente escrito en un lenguaje comprensible por la máquina en la cual el programa será ejecutado. Para lograr esto, el compilador debe resolver una serie de problemas siendo, varios de ellos problemas NP – Completo, de entre los cuales está el problema de inlining el cual puede afectar a otros problemas de compilación. Cuando se escribe un programa la tendencia es tener todo el código en módulos, es decir, en funciones que llaman a otras funciones o procedimientos. Se hace esto para poder reutilizar el código, para tener un mayor entendimiento si se desea modificar o encontrar algún error existente en él. Los motivos son diversos pero si no se hiciera esto, un código extenso podría tornarse caótico cuando se desee hacer por ejemplo alguna revisión en él. Toda esta separación ayuda al programador pero no al compilador ni al tiempo de ejecución del programa. La otra cara de la moneda surge a nivel del compilador, cuando existe una llamada a una función, se busca el cuerpo de esa función implicando un consumo de tiempo porque se realizan muchos accesos a memoria. Se tendería a pensar en colocar todo el código en donde se hacen las llamadas para evitar el almacenamiento en el stack y con eso minimizar el tiempo. Esto no es conveniente hacer porque el código se volvería muy extenso, con esto solamente se lograría que aumente el tamaño del archivo objeto con lo que no alcanzaría en la memoria caché volviendo lento el archivo ejecutable. Por todo lo mencionado se requiere obtener un equilibrio, se debe seleccionar algunas de las funciones para ser reemplazadas y esta elección de ¿cuando y como? [2] es lo que se debe optimizar. Existe la necesidad de tener compiladores más eficientes para que generen códigos de mejor calidad y sí ayudar a minimizar el tiempo de ejecución para poder resolver problemas más complejos en tiempos que estén de acuerdo a la actualidad. Dado que las metaheurísticas funcionan bien para problemas NP-Completo y en los compiladores existen muchos de estos problemas como por ejemplo la asignación de registros, selección de instrucciones y el propio inlining de funciones. Este trabajo propone resolver el problema de inlining de funciones con un algoritmo genético secuencial y paralelo, simulated annealing y por último búsqueda tabú. Y posteriormente a todo esto realizar un estudio comparativo entre ellas. Compilación En esta sección se definen y explican los principales conceptos a utilizar en este trabajo y posteriormente un completo estado del arte con respecto al problema de inlining y la utilización de metaheurísticas en el área de compilación. Los compiladores surgieron aproximadamente en la década de los 50, precisamente en 1957 con el compilador Fortran por John Backus de IBM [3]. Los principios de los compiladores son desarrollados durante los años 60. Normalmente se identifican 2 partes en un compilador las cuales están compuestas de las fases del compilador y son front end y back end. Front end [4] realiza las siguientes funciones y en el orden presentado: analiza el código fuente, comprueba su validez, genera el árbol de derivación y completa los valores de la tabla de símbolos. Back end (es el mismo para todos los lenguajes pero específico para cada arquitectura) genera el código objeto utilizando lo realizado por el front end. Entre los problemas que el compilador debe resolver existen algunos de ellos que son obligatorios, es decir, es necesario resolverlos a fin de poder generar un código objeto, un ejemplo de estos problemas es la asignación de registros. Otros los cuales no son obligatorios corresponden a técnicas para optimizar el código generado de entre los cuales está el propio inlining de funciones. Algunos de estos problemas son verdaderamente complejos y pertenecen a la clase NP-Completo. Como la solución a estos tipos de problemas no está dentro de un rango de tiempo razonable en la actualidad se utilizan las metaheurísticas para entregar buenas soluciones y en un menor tiempo. Problema inlining El problema inlining [2] consiste en reemplazar las llamadas de funciones por una copia modificada del cuerpo de esta función. En la figura 1 se muestra una llamada a función llamada “función2” la cual es reemplazada por el cuerpo de la función con algunas modificaciones. La resolución de este problema permite influir en otros problemas existentes en compilación como la asignación de registros, propagación de constantes, eliminación de subexpresiones comunes y otros. void main() { int x; scanf(“%i”,x); x=x + función2(x); printf (“%i”,x) return; int función2(int j) { j=j*2; return(j); } Resultado void main() { int x; scanf(“%i”,x); x=x+(x*2); printf (“%i”,x) return; } } Figura 1 Reemplazo de una llamada a función. El problema de inlining de funciones fue uno de los problemas nombrados dentro del catálogo de optimizaciones de Allend y Cocke en 1972. Ha sido tratado por ejemplo para compiladores del lenguaje C [5], GCC [2], Jalapeño JVM (máquina virtual de java) para el cual se realizó un estudio empírico [6] y un estudio comparativo de tres heurísticas que resuelven el problema inlining [7]. Para este problema la parte más compleja es saber cuando decidir en reemplazar la llamada a función por el código de la función y cuando no, Serrano [2] entrega ciertas pautas a considerar para cuando se deba tomar esta decisión. Las reglas para el “¿cuándo?” están basadas por ejemplo en un umbral el cual no debe ser sobrepasado por el tamaño del cuerpo de una función (ayuda a mantener bajo control el crecimiento del código), otras incluyen el tamaño y prohibición a llamadas anidadas, también se realiza inlining en una llamada a función cuando disminuye el tamaño del código por otras optimizaciones, etc. Las reglas para el “¿cómo?” se basa si la función es recursiva o no. Serrano [2] en su artículo crea un algoritmo para decidir cuando realizar inlining. Otro punto a considerar para la solución de este problema es cuando las funciones son recursivas [8]. Appel [9] señala las distintas situaciones que existen cuando se hace inlining y entre ellas el cómo realizar inlining para una función recursiva. Al realizar en forma indiscriminada inlining se genera una nueva problemática que consiste en la explosión del código. También indica la existencia de heurísticas para resolver este problema como por ejemplo el expandir las llamadas a funciones de las cuales su cuerpo sea pequeño o funciones que son llamadas una sola vez o expandir las llamadas de aquellas funciones que son más frecuentemente ejecutadas. Existen estudios como el realizado con el compilador Fortran [10] para analizar los efectos del inlining en los otros problemas de compilación. En este artículo se describe también las razones por las cuales aumenta la velocidad del archivo ejecutable. Scheifler [11] realiza un análisis de la situación, de los efectos positivos y negativos. Posteriormente formula una solución la cual consiste en tener un conjunto de todas las llamadas, limitar a un tamaño máximo el código del programa y de los procedimientos en él, utilizando todas estas condiciones se debe encontrar una secuencia que minimice el tiempo de ejecución. Zhao y Amaral [12] describen 2 nuevas heurísticas con las cuales resuelven el problema utilizando ORC (Open Research Compiler). Para ORC se utilizaba un umbral de temperatura igual a 120 con el cual se decidía si se realizaba inlining o no. Este umbral se obtuvo mediante muchas pruebas con benchmark. El problema que presentaba era que favorecía a las aplicaciones grandes pero no a las pequeñas. El cambio más importante que introdujeron fue dividir el umbral en 3 tipos, para aplicaciones grandes de entre los cuales estaba GCC con 19.000 llamadas y 190.000 líneas de código, medio y pequeñas. Los umbrales de temperatura quedaron con los siguientes valores respectivamente 120, 50, 1. A esto se le llamó inlining adaptivo. Finalmente Báez [13], resuelve el problema utilizando un algoritmo genético para el compilador GCC, sus resultados no son concluyentes. Metaheurísticas Las metaheurísticas son algoritmos no determinísticos los cuales no aseguran entregar el óptimo pero si buenas soluciones. Algunas características de las metaheurísticas están en su independencia del problema, su capacidad para escapar de óptimos locales y así buscar en otras áreas de soluciones. Sirven para entregar soluciones a problemas muy complejos y generalmente con un alto grado de combinatoria para los cuales no existe una manera de encontrar el óptimo en un tiempo razonable. Dentro de las metaheurísticas existentes están los algoritmos genéticos [14], simulated annealing [14], búsqueda tabú [14]. La mayoría de las metaheurísticas nombradas están basadas en observaciones de la naturaleza. Generalmente se mezclan estos algoritmos formando metaheurísticas híbridas o se busca su paralelización como, por ejemplo, los algoritmos genéticos paralelos. Las metaheurísticas utilizadas en este trabajo son: algoritmo genético (AG) [14, 15, 16, 17], algoritmo genético paralelo (AGP) [14, 15, 18, 19, 20], simulated annealing (SA) [14, 21, 22] y por último el algoritmo de búsqueda tabú (TS) [14, 23, 24]. Los operadores tanto para AG y AGP son selección, cruzamiento y mutación. Para SA se debe definir la solución vecina y por último, para búsqueda tabú la lista tabú, filtros sucesivos, criterio de aspiración, diversificación e intensificación. El modelo de AGP utilizado es de concurrencia síncrona de redes. Su funcionamiento consiste en tener varios AG (esclavos) y uno central o maestro que está encargado de recibir los mejores que cada AG selecciona, elige el mejor de todos los recibidos y posteriormente entrega a cada AG el mejor de todos para que este forme parte de la población de la siguiente generación. Uso de metaheurísticas en compilación El uso de metaheurísticas en el área de compilación es escaso y lo existente resuelve problemas principalmente utilizando un algoritmo genético (AG). Uno de los problemas de compilación es el ordenamiento de instrucciones abordado por Beaty [25] utilizando un AG, no presenta resultados. Kenneth Williams et. at. [26] solucionan 5 problemas que no puede resolver la compilación en paralelo utilizando un algoritmo genético. Para esto crean un conjunto en el cual están codificadas ciertas transformaciones de loops. El AG secuencial utiliza la secuencia codificada en un programa y como resultado entrega una versión paralelisada de este. No presenta resultados, tan sólo realiza una comparación entre un compilador genético y un compilador tradicional. Nisbet [27] en 1998 utiliza un algoritmo genético para obtener una secuencia buena de los loop y el orden de las declaraciones para minimizar el tiempo de ejecución de un programa dado. Se prueban los resultados con otro compilador. Obtiene como resultado entre un 21 a 25% de mejora en los tiempos de los benchmark utilizados. En 1999 Nisbet [28] continua con su trabajo. Un trabajo no tan cercano en el sentido de resolver algún problema directamente de compilación es el de Keith D. Cooper et. at. [29] quienes disminuyen el tamaño del código generado por un compilador utilizando una combinación codificada de 10 problemas de optimización (constantes de propagación, eliminación de código muerto, asignación de registros y otros) insertos en él. Realizan diversas pruebas con distintos benchmark con el AG y otros sin el AG para hacer comparaciones de los resultados. Obtienen una secuencia la cual disminuye en un 40% el tamaño del código y también en muchos de los casos mejoran la velocidad en un 26%. Mark Stephenson et. at. [30] utilizan la programación genética para optimizar 2 heurísticas de compilación:“predication hyperblock formation” y la asignación de registros. Para ello realizaron diversas pruebas con distintos benckmark obteniendo como resultado para la heurística de hyperblock una mejora de un promedio de un 23% en la velocidad y para la asignación de registros para aplicaciones individuales una velocidad del 6% y para heurísticas de propósito general una mejora del 3%. También utilizando un AG secuencial Kri y Feeley [31] resolvieron el problema de la asignación de registros local. Manuel Báez [13] resuelve el problema de inlining utilizando el compilador GCC. En ACOVES (analysis of compiler options via evolutionary algorithm) [32], implementa un algoritmo genético para que decida cual de las opciones de optimización que posee el compilador GCC es más apropiada para cada programa. Cuando se compila un programa su archivo ejecutable queda más rápido dependiendo de que opción de optimización seleccionó el usuario. Solución propuesta Para resolver el problema es necesario definir una función de costo que permita determinar la calidad de la solución y una representación del problema con la cual se puedan codificar todas las posibles soluciones. Tanto la función de costo y la representación del problema son utilizadas por todas las metaheurísticas a fin de que se pueda realizar una comparación objetiva. Representación del problema Para representar el problema se utilizó una cadena binaria de largo n, donde n es el número de llamadas a funciones. Cada posición representa una llamada a función existente en el código exceptuando las llamadas recursivas. Al ser un problema binario significa: 0 no realiza inlining 1 realiza inlining Cada solución sólo contendrá un conjunto de 0 ó 1(figura 2), de acuerdo a la combinación que se forme se indicará a un compilador que llamada a función realizar inlining y a cual no. Después de esto, para evaluar los resultados de esa combinación se ejecuta el programa resultante. La combinatoria que se forma representa a todas las llamadas a funciones existentes en un código a las cuales si se les puede hacer inlining (excluyendo las llamadas recursivas), por este motivo el espacio de soluciones es todo el universo al no existir soluciones infactibles. ¾ ¾ #include void g() { f(); printf(“M2”); } void f() { printf(“M1”); } main Printf F() Printf G() (“M0”) (“M1”) - 0 1 0 1 F() 1 Printf Printf (“M1”) (“M2”) 0 0 int main() { printf(“M0”); f(); g(); return(0); } Figura 2 Representación binaria del problema inlining para un código. Función de evaluación Para poder discernir cual de las combinaciones encontradas es la mejor se utiliza el tiempo de ejecución del programa resultante para poder evaluar porque lo que se desea lograr es disminuir los tiempos. Todos estos algoritmos trabajarán para resolver el problema de inlining utilizando como función objetivo el tiempo. Se utiliza el tiempo porque es una de las maneras para poder discriminar cual código generado es mejor. Esto se debe a que en la actualidad las arquitecturas de los computadores son muy complejas, con el tiempo se le han ido agregando cada vez más funcionalidades con las cuales hace imposible analizar a simple vista 2 códigos assembler y poder decidir cual es mejor. La función de evaluación debe compilar el programa realizando el inlining indicado en el cromosoma, luego ejecuta el programa generado y mide su tiempo de ejecución. En la función de evaluación para obtener el tiempo se utiliza el comando time que pertenece al sistema Linux. Cuando se toma el tiempo, el comando time entrega 3 tiempos de los cuales son útiles los 2 últimos (tiempo de usuario y sistema), se suman los cuales juntos originan el tiempo final del proceso. Operadores Adicionalmente es necesario definir los operadores con los que trabaja cada metaheurística. Al ser un problema binario los operadores utilizados tanto para el algoritmo genético secuencial como para el algoritmo genético paralelo son los estándar como selección proporcional o ruleta, cruzamiento de un punto y mutación invirtiendo un bit de la solución. Para simulated annealing la solución vecina se obtiene mediante un número aleatorio el cual indica la cantidad de cambios a realizar para así generar un nuevo vecino. En búsqueda tabú se utilizan la lista tabú de un tamaño 7, los filtros sucesivos, el criterio de aspiración se utiliza cuando una solución tabú a superado la mejor solución del momento, intensificación y diversificación (se logra mediante la memoria basada en frecuencia). Resultados Se analizó aproximadamente 50 algoritmos para obtener el número de llamadas a funciones de entre los cuales 7 estaban en un rango considerable para analizar. El gran número descartado de benchmark refuerza la idea de Hennessy et. al. [33] quienes señalan que dentro de un benchmark aproximadamente el número de llamadas a funciones corresponde al 1% de las instrucciones, por ejemplo, algunos poseían 4 llamadas a funciones como es el caso del benchmark burbuja, insertion, c4 y heapsort entre otros. Esto significa que son 24 combinaciones, es decir, 16 combinaciones lo que no justifica para un proceso de estas características utilizar metaheurísticas porque al ser un número pequeño se puede calcular el óptimo en un tiempo reducido. Otra razón es porque algunos benchmarks eran recursivos con lo cual tenían el número de llamadas igual a cero, es el caso del benchmark de hanoi, y otros por el incumplimiento de las restricciones duras que impone el compilador GCC. Benchmark Función N° de N° líneas en C llamadas Big factorial Realiza la función factorial de un número 8 135 Complex Utiliza 2 números complejos y realiza diversas operaciones sobre 13 183 ellos. Flor Cálculo de flujo de redes. 25 340 Queens Resuelve el problema para N reinas. 14 850 Fulk Cálculo de flujo de redes. 44 379 Magic Crea cuadrados mágicos. Todas las filas y columnas suman lo mismo. 15 175 Metropolis Utiliza otro programa al cual toma su tiempo de ejecución 5 veces 10 72 para después entregar su promedio. Utiliza para su funcionamiento el benchmark de queens. TABLA 1 Características de los benchmark utilizados En la tabla 1 se muestran todos los benchmark que superaron todos los problemas mencionados anteriormente. Se indica su función, número de llamadas y número de líneas. Tam=4n C=70% Mut=0,005% N°G=20 N° generación 19 16 13 N° generación a) b) T°i=1.000 α=0,9 T°f=0,001 2,15 2,10 2,05 Sol. actual 2,00 1,95 Tamaño t=7 Tamaño fs=10 TS Flow 8,40 Valor f. o. [s] SA big factorial 8,20 8,00 Sol. actual 7,80 Sol. mejor 7,60 7,40 N° solución c) FIGURA 3 Gráficos con los parámetros seleccionados. N° solución d) 161 141 121 101 81 61 41 7,20 21 593 519 445 371 297 223 149 1 75 1,90 1 Valor f. o.[s] 10 promedio 1 19 16 13 10 7 4 mejor_g mejor 7 mejor 2,10 2,08 2,06 2,04 2,02 2,00 1,98 1,96 1,94 1,92 4 promedio Tam=4n C=70% Mut=0,005% N°G=20 AGP Big factorial Valor f. o. [s] 1,90 1,88 1,86 1,84 1,82 1,80 1,78 1 Valor f. o. [s] AG complex Los gráficos de la figura 3 corresponden a gráficos obtenidos con los parámetros seleccionados al término del proceso de parametrización. En los gráficos de la figuras 3 a) y b) el eje x corresponde al número de generaciones, y c) y d) la cantidad de soluciones de solución. El eje y corresponde (en todos los casos) al resultado de la función objetivo medida en segundos. Él gráfico de la figura 3a) muestra la convergencia del AG con el benchmark complex, la curva promedio significa que es el promedio de toda la población en una generación. La curva mejor corresponde a la mejor solución encontrada hasta ese momento y mejor_g es el mejor de cada generación. Para el AGP con el benchmark big factorial (figura 3 b)) es similar a la explicación anterior con la única diferencia que no posee la curva mejor_g. Para el gráfico de la figura 3 c) corresponde al SA con el benchmark big factorial trabaja con una única curva que es la solución actual. Por último para TS con el benchmark Flow (figura 3 d)) trabaja similar a SA con la diferencia que se agrega la curva mejor la cual significa que es la mejor solución encontrada hasta ese momento. Las metaheurísticas muestran una buena convergencia, sin embargo las ganancias obtenidas no son significativas. En la tabla 2 están todos los resultados obtenidos después de la parametrización, también están los resultados entregados por el compilador GCC y así realizar una comparación entre los resultados de las metaheurísticas con una heurística clásica como la utilizada por GCC para realizar inlining. Benchmark GCC [s] AG [s] AGP [s] TS [s] SA [s] Big factorial 2.06 1.98 1.98 1.98 1.98 Complex 2.07 1.83 1.83 1.83 1.83 Flow 8.03 7.57 7.55 7.65 7.67 Queens 18.12 18.06 18.02 17.96 18.08 Fulk 2.37 2.29 2.26 2.26 2.29 Magic 2.44 2.06 2.06 2.09 2.08 Metropolis 2.53 2.47 2.47 2.48 2.49 TABLA 2 Resultado de la evaluación de los distintos benchmark con todas las metaheurísticas y el compilador GCC. La metaheurística que obtuvo los mejores resultados es el AGP, de los 7 benchmark fue la única que encontró 6 valores mejores que sus compañeras siendo superada una sola vez por TS para el benchmark Queens. AG acompañó 4 veces con igual valor a AGP al encontrar la mejor solución y TS 3 veces y una vez superó a AGP. Los tiempos entregados por todas las metaheurísticas fueron mejores que los entregados por el compilador GCC. Entre los valores entregados en la tabla 1 no existe una diferencia significativa. Análisis resultados No existe una diferencia significativa en los resultados entregados en la tabla 4.4. Estos resultados se pueden deber a las siguientes situaciones: ¿Los benchmark pueden no ser apropiados? Los benchmarks utilizados se consideran representativos porque son comunes, es decir, son utilizados en el ambiente informático. Por ejemplo, el algoritmo de queens, es generalmente utilizado para el aprendizaje de novatos en la computación. Se descartaron algunos algoritmos de ordenamientos porque no poseían llamadas a funciones que cumplieran con las restricciones duras del compilador GCC como por ejemplo los algoritmos recursivos como hanoi y quicksort o simplemente tenían un nivel de combinatoria muy pobre. ¿ Las metaheurísticas no sirven para resolver problemas de compilación?. Esta situación no es probable porque las metaheurísticas han demostrado trabajar muy bien en los problemas Np-completo. Además existen trabajos en compilación los cuales utilizan metaheurísticas, principalmente AG con buenos resultados explicados en la sección del estado del arte. ¿Las metaheurísticas están mal parametrizadas?. Si bien se puede realizar un proceso más fino de parametrización, el aquí realizado es suficientemente exhaustivo para descartar esta opción. ¿No hay ganancia al realizar inlining?. Esta situación se ve reflejada en los gráficos de parametrización. ¾ ¾ ¾ ¾ Para analizar la veracidad o falsedad del último punto mencionado se implementó un algoritmo de fuerza bruta para resolver el problema de los benchmarks los cuales pueden entregar sus resultados en un tiempo razonable. En algunos casos la realización de todas las combinaciones tardaría 7,9 años aproximadamente (es para el benchmark de flow tomando en cuenta un tiempo promedio de 7.5 segundos con 25 llamadas) por este motivo se descartó esa opción. Para realizar todas las combinaciones se hizo un contador con valor inicial igual a 0 hasta 2n, n es el número de llamadas a funciones, valor que se tiene desde un principio, al llegar a este valor concluyen los procesos. Estos números se transforman a binarios para así tener la solución que era analizada por la función de evaluación. Benchmark Peor caso (segundos) Big factorial 2.07 Complex 1.94 Magic 2.13 Metropolis 2.55 TABLA 3 Resultado de los benchmark con fuerza bruta Mejor caso (segundos) 1.98 1.83 2.06 2.48 Diferencia porcentual 4.4% 5.7% 3.3% 2.8% Al realizar todas las combinaciones de los siguientes benchmark se obtienen los valores mejores y peores expuestos en la tabla 3. Estos resultados indican claramente que el trabajar en la optimización de inlining no influye mucho en la minimización de los tiempos para estos benchmark. En la tabla 2 el AG secuencial encontró el óptimo sin recorrer todo el espacio de soluciones. Esto no ocurre en el benchmark big factorial en donde se evalúan 640 soluciones de 256 combinaciones aunque en la generación número 3 ya se había encontrado el óptimo, es decir, después de evaluar 96 soluciones. En cambio con el benchmark complex se evaluan 1040 soluciones de 2600 combinaciones existentes dentro del espacio de soluciones, se encuentra el óptimo en la generación número 8 habiendo evaluado 416 soluciones. Conclusiones Se cumple el objetivo de comparar distintas metaheurísticas para un problema NP-completo, en este caso, para el problema de inlining de funciones en el área de compilación. Además es un aporte la utilización de las metaheurísticas en compilación, ámbito en donde es poco frecuente su utilización. No hay diferencias significativas entre los resultados entregados por las metaheurísticas. La metaheurística AGP obtuvo en casi todos los benchmark los mejores resultados exceptuando en el benchmark queens en el cual Ts obtuvo el mejor resultado. La metaheurística que sigue es el AG junto con TS, obtuvieron en 4 ocasiones los mejores resultados. Al ordenar las metaheurísticas por un orden de resultados de mejor a peor sería: AGP, AG - TS y por último SA. SA no entrega resultados muy alejados que sus compañeros por este motivo se indica al principio que no existen diferencias significativas. Las metaheurísticas al comparar sus resultados con los entregados por fuerza bruta para el benchmark Magic todas recorren un 3,7% del espacio de soluciones y tanto AG como AGP encuentran el óptimo en las 4 ocasiones. TS y SA, ambas encuentran el óptimo para 2 benchmarks y en las otras 2 están muy cerca con una diferencia ínfima. Para el benchmark Complex recorren un 12,7% del espacio de soluciones encontrando las 4 metaheurísticas el óptimo a diferencia del compilador GCC el cual nunca encuentra en ninguno de estos 4 benchmark el óptimo. La mayoría de los trabajos existentes sobre compilación con metaheurística son realizados con AG. De acuerdo a este trabajo se demuestra que entrega un mejor resultado que otras metaheurística aunque la diferencia no es sustancial. No hay diferencias significativas entre los resultados entregados por las metaheurísticas y el compilador GCC. Las 4 metaheurísticas entregaron mejores resultados comparándolos con los de la heurística del compilador GCC. No hay una gran diferencia entre los valores máximo y mínimo, esto se demostró realizado fuerza bruta para ciertos benchmarks. Muchos autores indicaban en sus artículos que el problema de inlining podía afectar tanto negativa como positivamente en otras optimizaciones existentes en los compiladores. Para los benchmark utilizados en este trabajo y el compilador GCC, este impacto no es importante en las otras optimizaciones porque se vería reflejado en los tiempos resultantes. Al hacer todas las combinaciones para alguno de los benchmark los resultados de diferencia entre el mejor y peor tiempo fueron muy pobres, esta diferencia no alcanza a ser ni de un segundo. Se puede deber que el impacto de inlining, o mejor dicho el intento de optimización de este problema no fuese significativo porque de acuerdo a [33] este problema se presenta en un 1% aproximadamente de las instrucciones en el código de los benchmark, lo que significa que su optimización no afectaría tanto. Quizás, se podrían obtener resultados más beneficiosos para códigos en que este número tenga un gran valor, o por lo menos superior a 44 número de llamadas (mayor valor con el que se realizó pruebas). Para trabajos futuros se podrían eliminar las restricciones duras del compilador GCC para analizar si se pueden obtener mejores resultados a los obtenidos en este trabajo. También utilizar más benchmark para tener resultados con una muestra más significativa aunque está claro que esta tarea sería larga porque en este trabajo de 50 benchmark sólo se pudieron utilizar 7. También se podría construir un compilador. Referencias Bibliográficas [1] A.V. Aho and J. D. Ullman. Compiladores Principios, técnicas y herramientas. Addison-Wesley,1990. [2] Manuel Serrano , Inline expansion: when and how?, Proceedings of the conference on Programming Languages, Implementation and Logic Programming., Shouthampton, September 1997. [3] Anónimo, Compiler, http://www.iridis.com/glivar/Compiler, fecha visitada: 01/12/2004 [4] Anónimo, Compilador, http://es.wikipedia.org/wiki/Compilador, fecha visitada: 01/12/2004 [5] Pohuap Chang, Scott Mahlke, William Chen y Wen-Meiw Hwu, Profile-guided Automatic Inline Expansion for C Programs, Center for Reliable and High-performance Computing, Coordinated Science Laboratory, University of Illinois, 1992. [6] Toshio Suganuma, Toshiaki Yasue, Toshio Nakatani, An Empirical Study of Method Inlining for a Java Just-InTime Compiler, Proceedings of the 2nd JavaTM Virtual Machine Research and Technology Symposium (JVM '02), 2002 [7] Matthew Arnold, Stephen Fink, Vivek Sarkar, Peter Sweeney, A comparative study of static and profile-based heuristics for inlining, Workshop on Dinamic and Adaptive Compilation and Optimization (DYNAMO ‘00), junio 2000. [8] Henry G. Baker, Inlining Semantics for Subroutines which are Recursive, ACM Sigplan Notices 27,12 (Dec. 1992), 39-46. [9] Andrew Appel, Modern compiler implementation in java, Cambridge University Press, 1998. [10] Keith D. Cooper, Mary W. Hall y Linda Torczon, An Experiment with Inline Substitution, Department of Computer Science, Rice University, Houston, Texas 77251-1892. [11] Robert W. Scheifler, An analysis of inline substitution for a structured programming language, volumen 20 número 9, Communications of the ACM 1977 [12] Peng Zhao y Nelson Amaral, To inline or not to inline? Enhanced inliing decisions, Departament of computing science University of Alberta, Edmonton, Canada, 2002. [13] Manuel Báez, Sustitución de llamadas a funciones usando algoritmos genéticos, Tesis de Ingeniería Civil Informática, Departamento de Ingeniería de Informática, Universidad de Santiago de Chile, 2004 [14] Adenso Díaz, Fred Glover, Hassan Ghaziri, J. González, Manuel Laguna, Pablo Moscato, Pablo Moscato, Fan Tseng, Optimización heurística y redes neuronales, Editorial Paraninfo, 1996. [15] Pedro Larrañaga, Iñaki Inza, Tema 2: Algoritmos genéticos, http://www.sc.ehu.es/isg, Fecha visitada: 08-252004 [16] Anónimo, Algoritmos genéticos, http://mit.ocw.universia.net/15.053/s02/pdf/s02-lec24.pdf, Fecha visitada: 01/07/2004 [17] David Beasley, David Bull, Ralph Martin, An overview of genetic algorithms: Part 1, fundamentals, University Computing,1993. [18] Mariusz Nowostawski, Riccardo Poli, Parallel genetic algorithm taxonomy, In Proceedings of the Third International Conference on Knowlege-basecl Intelligent Information Engineering Systems KES'99, pages 88-92. IEEE Computer Society,13 de mayo 1999. [19] Iván Mellado, Evaluación de modelos paralelos para algoritmos genéticos aplicados al problema de la mochila, Tesis de Ingeniería Civil Informática, Departamento de Ingeniería de Informática, Universidad de Santiago de Chile, 1998 [20] Eric Cantú-Paz, A survey of parallel genetic algorithms, Illigal Report N° 97003, mayo 1997. [21] S. Kirkpatrick, C. D. Gelatt y M. P. Vecchi, Optimization by Simulated annealing, Science , volumen 220, 1983. [22] Kathryn Dowsland, Belarmino Adenso Díaz, Diseño de heurísticas y fundamentos del recocido simulado, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial N°19 (2001), http://www.aepia.org/revista [23] Fred Glover, Manuel Laguna, Tabu search, Kluwer Academic Publishers, 2002 [24] Fred Glover, Belén Melián, Tabu search, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial N°19 (2003), http://aepia.dsic.upv.es/revista/ [25] Steven J. Beaty,Genetic algorithms and instruction scheduling, Departament of Mechanical engineering, Colorado State University, Fort Collins, Colorado,1991. [26] Kenneth P. Williams y Shirley A. Williams, Genetic compilers: A new technique for automatic parallelisation, In 2nd European School of Parallel Programming Environments (ESPPE'96) , 1996) [27] Andy Nisbet, GAPS: Genetic algorithm optimised parallelisation, Departament of Computer Science, University of Manchester, 1998. [28] Andrew Nisbet, John Gurd, Brian Warboys, Genetic algorithm optimised compilation of fortran for distributed memory architectures, 1999 [29] Keith D. Cooper, Philip J. Schielke y Devika Subramanian. Optimizing for reduced code space using genetic algorithms, Department of Computer Science, Rice Universitiy, Houston Texas, 1999 [30] Mark Stephenson, Una-May O’Reilly, Martin C. Martin and Saman Amarasinghe, Genetic programming appplied to compiler heuristic optimization, Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings [31] F. Kri , M. Feeley, Utilización de Métodos Metaheurísticos en Compilación: Una Experiencia Preliminar, IV Workshop on Advances & Trens in Artificial Intelligence for Problem Solving (ATAI 2003) [32] Scott R. Ladd, Acovea: Analysis of compiler options via evolutionary algorithm, http://www.coyotegulch.com/products/acovea/, fecha visitada: 24/04/2005 [33] J.L. Hennessy, D. A. Patterson, Computer architecture a quantitative approach. Segunda edición, Morgan Kaufman Publishers, 1996.