Repositorio Institucional de Documentos

Escuelade IngenieríayArquitectura Proyecto Fin de Carrera de Ingenier´ıa en Inform´atica Estudio Comparativo de Frameworks de Instrumentaci´on Din´amica de Ejecutables Juan Antonio Artal Lozano Director: Ricardo J. Rodr´ıguez Fern´andez Ponente: Jos´e Javier Merseguer Hern´aiz Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Abril de 2012 Curso 2011/2012 A mi mujer, Conchita. Those types are not ’abstract’; they are as real as int and float. Doug McIlroy Agradecimientos A mis padres, hermanos y abuela. A todos mis compa˜neros de promoci´on. A Ricardo y su paciencia conmigo. A Jos´e Merseguer. A mis compa˜neros de trabajo. GRACIAS. Estudio comparativo de frameworks de Instrumentaci´on Din´amica de Ejecutables RESUMEN La Instrumentaci´on Din´amica de Ejecutables (Dynamic Binary Instrumentation, DBI) es una t´ecnica muy potente que permite analizar el comportamiento, en tiempo de ejecuci´on, de cualquier aplicaci´on. DBI se puede usar, por ejemplo, para contar el n´umero de instrucciones que ejecuta o contar todas las transferencias (lectura y/o escritura) a memoria que realiza un determinado programa. DBI tiene diferentes usos seg´un sea el perfil de la persona que lo use. Por ejemplo, para un programador, DBI ayudar´a a identificar las partes cr´ıticas del c´odigo; para un desarrollador de un procesador nuevo, DBI simular´a esta nueva arquitectura; y para un programador de compiladores en una nueva arquitectura, DBI ayudar´a a la colocaci´on de las instrucciones para mejorar el paralelismo o c´omo preparar profile-guided optimizacions (PGO). Un framework de DBI es una plataforma software que incluye programas, librer´ıas, documentaci´on y una API para manipulaci´on de instrucciones en tiempo de ejecuci´on. Existen diferentes frameworks de DBI (p.e., Pin, Valgrind, DynamoRIO, Paradyn/Dyninst), que proporcionan APIs muy extensas para que cada ingeniero pueda desarrollar sus propias herramientas de an´alisis din´amico, llamadas herramientas DBA (Dynamic Binary Analysis). Las herramientas DBA permiten analizar, generar optimizaciones y monitorizar el comportamiento de programas. El objetivo de este PFC es realizar un estudio comparativo centrado a nivel de impacto en rendimiento (performance) de diferentes frameworks de DBI. Es decir, se comprobar´a el rendimiento de una aplicaci´on ejecutada de forma nativa, sin instrumentar, y se comparar´a con esta misma aplicaci´on instrumentada por herramientas programadas bajo diferentes frameworks de DBI. De esta forma se obtiene el impacto en rendimiento de cada uno de los frameworks. Para poder llevar a cabo este estudio, se han seleccionado un conjunto de aplicaciones para crear un benchmark, que nos dar´a informaci´on de rendimiento de cada framework de DBI. Adem´as, se pretende comparar cada framework de DBI atendiendo a las siguientes caracter´ısticas: plataformas y tipos de ejecutables que aceptan, necesidad de disponer del c´odigo fuente, API proporcionada, facilidad de programaci´on de herramientas DBA, licencia/coste y la posibilidad de vincular a un proceso en ejecuci´on. ii ´ Indice 1. Introducci´on 1 1.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Organizaci´on del documento . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conocimientos previos 5 2.1. Granularidad en DBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Origen de DBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Frameworks de DBI 9 3.1. Pin........................................ 10 3.2. Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3. DynamoRIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4. Similitudes y diferencias entre estos frameworks . . . . . . . . . . . . . . . 12 4. Trabajo relacionado 15 5. Creaci´on de benchmark 17 5.1. Alternativas estudiadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2. Definici´on de benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3. Descripci´on del benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.4. Herramientas para el benchmark . . . . . . . . . . . . . . . . . . . . . . . 21 5.5. Mediciones en el benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.5.1. Tiempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.5.2. Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6. Experimentos 23 6.1. Entorno de pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7. Conclusiones y trabajo futuro 29 A. Fases de Desarrollo 35 A.1. Diagrama de Gantt ............................... 35 iii Cap´ıtulo 1 Introducci´on El t´ermino de instrumentaci´on se refiere a la inserci´on de c´odigo adicional sobre un determinado software. Principalmente, hay dos tipos de instrumentaci´on: de c´odigo fuente, cuando el programador a˜nade l´ıneas de c´odigo antes de la compilaci´on; y de ejecutable, si hay otra aplicaci´on que modifica el programa una vez compilado. La instrumentaci´on permite incorporar al programa desarrollado c´odigo adicional para recoger informaci´on en tiempo de ejecuci´on, que principalmente tiene dos usos diferentes: para estudio de arquitecturas, donde se puede hacer modelado de cach´es y simulaci´on de instrucciones nuevas de procesadores; y para an´alisis de c´odigo, donde se puede generar informaci´on para an´alisis de rendimiento, p.e., para averiguar cu´ando, d´onde y por qu´e nuestro c´odigo tarda tanto en ejecutar cierta tarea. Hay diferentes tipos de instrumentaci´on, como la manual, en la que el programador a˜nade directamente las l´ıneas de c´odigo que le interesan; como por ejemplo, para calcular tiempos de ejecuci´on, contar eventos o llamadas a una interfaz de programaci´on de aplicaciones (API). Hay herramientas tipo automated source level que modifican el c´odigo fuente para a˜nadir instrumentaci´on de acuerdo a una determinada configuraci´on. Existen otros tipos de instrumentaci´on como la asistida por el compilador, que es a˜nadida en tiempo de compilaci´on, y binary translation, donde se modifica el software con llamadas a una API de instrumentaci´on para que la propia aplicaci´on genere informaci´on en tiempo de ejecuci´on, siendo esta aplicaci´on la que se instrumenta a s´ı misma. Finalmente, existe la instrumentaci´on din´amica de ejecutables (DBI), donde una aplicaci´on externa inserta c´odigo adicional en tiempo de ejecuci´on al ejecutable instrumentado. Este proyecto se centra en DBI porque es la opci´on m´as completa de todas y m´as moderna, permitiendo adem´as monitorizar y controlar una aplicaci´on mientras se ejecuta desde su inicio hasta el final. Sin embargo, una desventaja que tiene la instrumentaci´on al ser a˜nadida en tiempo de ejecuci´on es la sobrecarga tan elevada que conlleva su adici´on. Debido a esto, las aplicaciones instrumentadas tienen un rendimiento muy malo compar´andolas consigo mismas ejecut´andose de forma nativa, es decir, sin instrumentar. Esto es un factor determinante a la hora de trabajar con DBI. Para programar aplicaciones que soporten DBI se puede usar un framework de DBI. 1 Secci´on 1.1 1. Introducci´on ´ Este facilita una API para que se puedan desarrollar herramientas de an´alisis din´amico. Estas herramientas permiten instrumentar un software en el momento que el programador determine. En la actualidad existen diferentes frameworks de DBI, como Valgrind [NS07] o Pin [LCM+05], pero no hay suficiente informaci´on comparativa sobre ellos a nivel de rendimiento, ya que apenas hay trabajos que traten directamente el tema de rendimien- to, y a nivel de programaci´on no se ha encontrado nada que compare los frameworks de DBI. 1.1. Objetivo El objetivo de este PFC es realizar un estudio comparativo a nivel de impacto en rendimiento de diferentes frameworks de DBI, ya que una aplicaci´on instrumentada puede tardar en ejecutarse hasta 35 veces m´as lenta, como se ha comprobado con los resultados de este PFC. Se ejecutar´an diferentes tipos de aplicaciones seleccionadas para el estudio, mediante un benchmark propio, bajo diferentes instrumentaciones en diferentes frameworks de DBI. Posteriormente se analizar´an los resultados obtenidos. El procedimiento para obtener esos resultados ha sido el siguiente: Hacer un estudio de los frameworks disponibles, buscando cu´ales son los que se est´an usando en la actualidad. Seleccionar los frameworks interesantes para este estudio, indicando los criterios de selecci´on que se han utilizado. Compilaci´on e instalaci´on del framework a partir del c´odigo fuente, para comprobar que se dispone de todo el software necesario para despu´es desarrollar herramientas. Estudio de manuales, tutoriales y APIs de cada framework, para despu´es poder desarrollar herramientas DBA. B´usqueda de aplicaciones est´andar para generar un benchmark. ´ Este re´une un conjunto de programas en diferentes categor´ıas como: c´alculo entero, c´alculo real, E/S de ficheros y acceso a memoria. Probar herramientas DBA desarrolladas bajo el benchmark, de tal forma que permita obtener informaci´on sobre el rendimiento de estas. Finalmente el benchmark permite obtener los datos de sobrecarga en tiempo de las aplicaciones por la instrumentaci´on y los requisitos adicionales de memoria. 1.2. Motivaci´on La principal motivaci´on para la elecci´on de este PFC fue la oportunidad de profundizar en el aprendizaje y estudio de herramientas DBI actuales, ya que en las asignaturas de la 2 1. Introducci´on Secci´on 1.3 carrera no hab´ıa nada relacionado con ello. Entre las aplicaciones innovadoras de estas herramientas son las relacionadas con la seguridad como la comprobaci´on de fugas de memoria e ingenier´ıa inversa. Este Proyecto me ha ofrecido la oportunidad de explorar una interesante aplicaci´on: la evaluaci´on del rendimiento del los frameworks de DBI basada en la programaci´on de herramientas DBA y el estudio de sus APIs. 1.3. Organizaci´on del documento El presente documento est´a dividido en dos partes: la memoria, donde se explica el desarrollo del Proyecto; y los ap´endices, donde se ampl´ıa la informaci´on de ciertos puntos relevantes. El cap´ıtulo 2 define algunos conceptos previos que sirven de ayuda para comprender el resto del documento como qu´e es DBI, DBA, la granularidad en instrumentaci´on y c´omo fueron los inicios de la instrumentaci´on din´amica. El cap´ıtulo 3 introduce los frameworks de DBI, expone los criterios de selecci´on para la comparaci´on, sus caracter´ısticas, similitudes y diferencias entre ellos y algunos comentarios sobre sus APIs. El cap´ıtulo 4 recoge el trabajo relacionado con este proyecto. El proceso de creaci´on del benchmark y la selecci´on de software para las pruebas est´a en el cap´ıtulo 5. El cap´ıtulo 6 resume los experimentos realizados con el benchmark definido anteriormente. Adem´as, se muestran los gr´aficos m´as relevantes junto a un an´alisis cr´ıtico de los resultados. Finalmente, el cap´ıtulo 7 presenta las conclusiones de este trabajo y plantea posibles l´ıneas de trabajo futuro. Respecto a los ap´endices, el ap´endice A es donde se hace balance del esfuerzo temporal empleado en la realizaci´on del PFC. El ap´endice B re´une los problemas que han ido apareciendo. El ap´endice C describe las aplicaciones usadas en los benchmark con m´as detalle. El ap´endice D contiene las tablas con los resultados obtenidos de los experimentos y no incluidas en el cap´ıtulo 6 y finalmente, en el ap´endice E se presenta el c´odigo fuente de las aplicaciones DBA para el benchmark. 3 Cap´ıtulo 2 Conocimientos previos En este cap´ıtulo se definen algunos de los conceptos m´as importantes en los que se basa este proyecto y, en general, se explica el funcionamiento y uso de DBI. El principal uso de DBI es analizar el comportamiento de un ejecutable durante la ejecuci´on, de tal forma que permita mejorar el funcionamiento de ´este. En comparaci´on con el an´alisis est´atico, ofrece la ventaja de estudiar qu´e es lo que est´a ocurriendo en vez de lo que podr´ıa estar ocurriendo. El ´unico inconveniente es que no se ejecutan todos los posibles caminos, porque si una instrucci´on no se ejecuta, no se llega a instrumentar. DBI se puede utilizar de manera diferente dependiendo de qui´en lo vaya a utilizar, para un programador, DBI ayudar´a a identificar las partes cr´ıticas del c´odigo; para un desarrollador de un procesador nuevo, DBI simular´a esta nueva arquitectura; y para un programador de compiladores en una nueva arquitectura, DBI ayudar´a a la colocaci´on de las instrucciones para mejorar el paralelismo o c´omo preparar profile-guided optimizacions (PGO). En un framework de DBI hay dos componentes principales, el n´ucleo y las herramientas desarrolladas con ´el. El n´ucleo se encarga de enviar fragmentos de c´odigo a la herramienta, y ´esta se encarga de la inyecci´on de c´odigo. El n´ucleo es como un compilador just-in-time (JIT), donde la entrada al compilador es un ejecutable. Se intercepta la ejecuci´on de la primera instrucci´on del ejecutable y genera nuevo c´odigo, donde se transfiere el control de la secuencia generada. La secuencia de c´odigo generada es pr´acticamente id´entica a la original, pero el n´ucleo se asegura que se retorne el control cuando se salga de la secuencia. El c´odigo generado es guardado en memoria, por lo que puede ser reutilizado sin necesidad de regenerarlo cada vez que se ejecute. Una vez que se ha generado este c´odigo se le da la opci´on al usuario de inyectar su propio c´odigo, o sea instrumentarlo. Una herramienta habitualmente tiene la forma plug-in o librer´ıa, y su funci´on es a˜nadir c´odigo al obtenido previamente del n´ucleo, para ello tiene dos componentes b´asicos: Instrumentaci´on, se decide d´onde y qu´e c´odigo es insertado. An´alisis, se ejecuta el c´odigo a˜nadido en los puntos de inserci´on. 5 Secci´on 2.1 2. Conocimientos previos Cuando se desarrollan herramientas, es m´as importante afinar el c´odigo de an´alisis que el de instrumentaci´on. Esto es as´ı debido a que la parte de instrumentaci´on en una l´ınea del c´odigo se ejecuta una ´unica vez; sin embargo, el an´alisis, que es el c´odigo que se ha inyectado, se puede llegar a ejecutar m´ultiples veces. Todo el c´odigo inyectado al ejecutable original se ejecuta de forma transparente [BZA12] con los frameworks de DBI actuales, de tal forma que este c´odigo a˜nadido no pueda interferir en el comportamiento del ejecutable y se modifique el comportamiento original. El n´ucleo y la herramienta habitualmente controlan el programa desde el inicio, es decir, desde la primera instrucci´on a ejecutar. Para los ejecutables enlazados con librer´ıas din´amicas esto implica que la ejecuci´on del cargador din´amico y de las librer´ıas es visible y controlada. Tambi´en son visibles y controlados el c´odigo generado din´amicamente, pero el que se automodifica puede llegar a dar problemas en funci´on del framework de DBI, como en el caso del framework Valgrind [NS07]. Para que el funcionamiento sea correcto, tanto el n´ucleo como la herramienta tienen que estar trabajando en el mismo espacio de direcciones que el ejecutable. Es decir, tienen que estar todos en espacio de usuario, donde residen las aplicaciones; o bien en espacio del kernel, donde residen los m´odulos o drivers. 2.1. Granularidad en DBI Un ejecutable instrumentado por un framework de DBI se suele instrumentar instrucci´on a instrucci´on, pero en funci´on de la instrumentaci´on que se desee realizar y del framework se puede utilizar una granularidad diferente. Las posibles granularidades son: Instrucci´on, es la unidad m´ınima que se puede instrumentar. Son instrucciones en ensamblador de la arquitectura en la que se trabaje. Bloque b´asico, es una secuencia de instrucciones que finalizan con una instrucci´on de control de transferencia como un salto condicional (p.e., en ensamblador x86, JZ, salto si flag Z=1 )[Int86], incondicional (p.e., JMP, salto a una direcci´on), repeticiones (p.e., instrucciones que tengan el prefijo REP, repite la instrucci´on posterior varias veces), llamada o retorno a procedimiento (p.e., RET, retorno de procedimiento) entre otros. Aqu´ı se muestra un ejemplo de bloque b´asico consistente en tres instrucciones x86: una suma entre dos registros del procesador dejando el resultado en el primero de ellos (ADD), una comparaci´on entre un n´umero y un registro (CMP) y un salto condicional que comprueba si el resultado de la operaci´on previa es menor o igual (JLE). Como la ´ultima instrucci´on es de control de transferencia, tras la instrucci´on del salto, finaliza el bloque b´asico. comparac: add %ebx,%eax cpm $0x7f,%ebx jle comparac 6 2. Conocimientos previos Secci´on 2.2 Superbloque, es tambi´en una secuencia de instrucciones que tiene un punto de entrada, pero al contrario que los bloques b´asicos puede tener m´ultiples puntos de salida. Traza, es la uni´on de bloques b´asicos que se ejecutan uno detr´as de otro en secuencia, aunque en el ejecutable no est´en consecutivos. Rutina, corresponde a las funciones y procedimientos t´ıpicamente producidos por un compilador de un lenguaje de programaci´on por procedimientos como C. Imagen, que representa a todas las secciones de un ejecutable, que son las partes en las que se divide, como p.e., .init,.text o.fini para el formato de fichero ejecutable para windows. Hay que tener en cuenta que durante la ejecuci´on de un proceso puede haber m´as de un objeto imagen en funci´on de las librer´ıas din´amicas a las que acceda. 2.2. Origen de DBI Las primeras herramientas de instrumentaci´on hac´ıan dos tareas b´asicas: contar bloques b´asicos y la generaci´on de trazas de direcciones para modelado de cach´es. Entre otras, estaban las herramientas Pixie [SG92], Epoxie [Wal91] y QPT [LB94] que utilizaban el ejecutable ya compilado. Presentaban diferentes problemas, como que no se pod´ıa hacer otro tipo de instrumentaci´on y adem´as generaban trazas de datos y direcciones de manera ineficiente, ya que no se pod´ıa seleccionar entre qu´e puntos se quer´ıa generar informaci´on. Otro tipo de herramientas eran los simuladores, como Tango Lite [GH93], Proteus [BDCW91] o g88 [Bed90]. Proteus permit´ıa estudiar el comportamiento de un programa con diferentes arquitecturas de cach´es y un n´umero simulado de procesadores para poder comprobar la escalabilidad de un programa o algoritmo. El principal problema de los simuladores es la sobrecarga en tiempo que generan, esto es algo que se ha mantenido hasta las herramientas actuales. Adem´as, no eran completamente transparentes para el programa y modificaban el comportamiento del ejecutable. El primer framework de DBI, ATOM [SE94], apareci´o en 1993 y funcionaba ´unicamente para Tru64 Unix en procesadores Alpha. Prove´ıa una API mediante la cual se pod´ıan programar herramientas para analizar un ejecutable. Ofrec´ıa la instrumentaci´on de instrucciones, bloques b´asicos y rutinas; y se pod´ıan construir simuladores a nivel de cach´e e instrucciones. Sin embargo, la mayor desventaja es que se ten´ıa que modificar el c´odigo fuente y recompilarlo. El nuevo programa utilizaba las librer´ıas de ATOM y las instrucciones eran directamente ejecutadas bajo el procesador real, sin ning´un tipo de simulaci´on. 7 Cap´ıtulo 3 Frameworks de DBI Este cap´ıtulo muestra una introducci´on a los frameworks de DBI. Se resumen los que se pueden encontrar, despu´es se analizan los criterios de selecci´on y cu´ales han sido los seleccionados para hacer el estudio de rendimiento. Un framework de DBI ofrece un conjunto de APIs de manipulaci´on de instrucciones en tiempo de ejecuci´on para que se puedan hacer, de manera f´acil y r´apida, herramientas de instrumentaci´on. Los principales frameworks de DBI que se pueden encontrar son: Pin [LCM+05] (http://pintool.org) es un sistema de instrumentaci´on desarrollado para proveer facilidad de uso, portabilidad, transparencia e instrumentaci´on eficiente. Se programa en C/C++ y se cre´o a partir de ATOM [SE94]. Se crean herramientas DBA ligeras, esto significa que se a˜nade la instrumentaci´on y se ejecuta directamente en el procesador de la arquitectura. DynamoRIO [Bru04] (http://dynamorio.org), es un sistema de manipulaci´on de c´odigo en tiempo de ejecuci´on que soporta transformaciones de c´odigo en cualquier parte de un programa mientras se est´a ejecutando. Con su API se pueden programar herramientas para an´alisis de programas, profiling, instrumentaci´on, optimizaci´on y binary translation entre otros. Provee manipulaci´on de c´odigo eficiente, transparente y extensa en aplicaciones sin necesidad de recompilarlas. Las herramientas creadas son ligeras. Valgrind [NS07], (http://valgrind.org), es un framework de DBI desarrollado para crear herramientas DBA pesadas, esto es, convierte el binario a un lenguaje intermedio, y guarda el estado de todos los registros y memoria accedidos, as´ı como todas las operaciones de lectura y escritura, asignaciones y liberaciones de memoria. Para todo esto, usa una t´ecnica llamada shadow values. Es por eso que herramientas DBA ligeras programadas con Pin y DynamoRIO son m´as r´apidas, pero sin embargo, las pesadas son m´as dif´ıciles de hacer o imposibles con esos frameworks. DynInst (http://dyninst.org), ofrece un API para modificar aplicaciones en tiempo de ejecuci´on, con la capacidad de crear herramientas portables proporcio- 9 4. Trabajo relacionado rentes, un Pentium 4 para 32 bit con una cach´e de trazas, y un Intel Xeon Core 2 para 64 bit con una cach´e de instrucciones. Ambos con GNU/Linux kernel 2.6.9 (i686 para 32 bit, y x86 64 para 64 bit). El benchmark utilizado es SPEC CINT 2006. Aqu´ı obtienen que el slowdown de media de DynamoRIO es 1,22x y el de Pin es 1,45x. Para realizar las mediciones utilizan los contadores de rendimiento hardware con PAPI yperfex. Lo que se pretende analizar es el rendimiento de la cach´e de instrucciones o trazas y otras estructuras de la microarquitectura. En [WM08], Weaver et al. describen el uso de herramientas creadas por ellos con Valgrind, Qemu y la comparan con otra de Pin. ´ Estas son ejecutadas en 9 m´aquinas diferentes con arquitectura IA-32 con Linux. Se usan dos benchmark SPEC CINT 2000 y SPEC CINT 2006. Utilizan los contadores hardware de la CPU para obtener resultados mediante el interfaz perfmon2. Para la instrumentaci´on usan la cuenta de bloques b´asicos. Como conclusiones obtienen que el rendimiento de sus herramientas es similar a otras ya existentes. Siempre que se instrumenta existe una sobrecarga que hace que se ejecute m´as lento que de forma nativa, en [CKS+08], Chen et al. buscan m´etodos para hacer que se ejecute m´as r´apido en instrumentaci´on de grano fino, a nivel de instrucciones. Para esto se usa el benchmark CPU SPEC INT 2000, y las herramientas DBA Addrcheck, Memcheck, TaintCheck y Lockset. Primero son instrumentados con Pin para obtener los accesos a memoria y eventos relacionados con las direcciones. Despu´es, se ejecuta el benchmark instrumentado con las cuatro herramientas y obtiene un slowdown medio de 3,2x para Addrcheck, 3,3x para TaintCheck, 4,2x para Lockset y finalmente 7,8x para Memcheck que ha sido programado con Valgrind. Contribuci´on. Con mi trabajo aporto un benchmark espec´ıfico para la evaluaci´on de frameworks de DBI, ya que lo realmente importante en rendimiento es poder comprobar cu´anto tiempo m´as tarda una aplicaci´on en ser ejecutada cuando es instrumentada. Adem´as, se ofrecen dos m´etodos de instrumentaci´on: por instrucciones, donde se instrumenta el 100 % de las instrucciones ejecutadas; y por bloques b´asicos, de forma que se consiga una sobrecarga media. Adem´as muestra la cuenta tanto de bloques b´asicos como de instrucciones, que es un dato muy importante en la instrumentaci´on. Como dato final tambi´en se muestra el consumo de memoria, que no es proporcionado por ning´un otro benchmark. 16 Cap´ıtulo 5 Creaci´on de benchmark Este cap´ıtulo resume las alternativas estudiadas para confeccionar un benchmark adecuado para la evaluaci´on de rendimiento entre los diferentes frameworks. Finalmente, se presentan las caracter´ısticas y m´etodos usados en el benchmark creado. 5.1. Alternativas estudiadas La primera alternativa era utilizar un benchmark ya existente, por lo que se empez´o estudiando benchmarks comerciales. Los primeros estudiados fueron los de Futuremark [Fut10], como 3DMark y PCMark, y aunque ´estos son de uso libre, ten´ıan el problema de ser ´unicamente para Windows. Otro benchmark que se estudi´o fue SysMark 2012, que tambi´en es s´olo para Windows, de pago y sus aplicaciones entre otras son de Adobe, Microsoft y Google. Para otros sistemas operativos tambi´en estaba TPC, pero sus benchmarks son de Procesamiento de Transacciones En L´ınea (OnLine Transaction Processing, OLTP) en los que principalmente se eval´ua una base de datos. PARSEC [Bie11], era una muy buena opci´on porque es de uso libre y ofrece el c´odigo fuente de sus aplicaciones, pero es un benchmark centrado en paralelizaci´on pensado especialmente para m´aquinas multiprocesadoras. Finalmente, el que mejor se acercaba para comprobar el rendimiento de las herramientas programadas era CPU2006 v1.2 de SPEC [Cor06], con versiones para Windows y Linux. En este benchmark tienen una m´aquina de referencia, una Sun Ultra Enterprise 2 de 1997, y el resultado obtenido en el benchmark es normalizado con respecto a esta m´aquina. ´ Este se podr´ıa definir como el primero de los problemas, ya que lo que se quiere comparar es un ejecutable consigo mismo instrumentado. El segundo problema es que este benchmark no es un producto gratuito. Estos dos problemas motivaron la creaci´on de un benchmark propio que se presenta a continuaci´on. 5.2. Definici´on de benchmark Una definici´on de benchmark tiene que cumplir una serie de detalles [Cor06]. Habitualmente, los benchmarks realizan un conjunto de operaciones estrictamente definidas: 17 Secci´on 5.2 5. Creaci´on de benchmark una carga de trabajo, y devuelve alg´un tipo de resultados. una m´etrica, describiendo c´omo tienen que ser realizadas las pruebas. La carga de trabajo en este benchmark ser´a siempre la misma por cada ejecutable, y est´a preparado para que devuelva siempre el mismo resultado. Lo ´unico importante es que debe realizar uso intensivo de CPU. Las m´etricas de los benchmarks normalmente miden: velocidad: c´omo de r´apido se ha realizado la carga de trabajo. throughput/rendimiento: cu´antas unidades de carga de trabajo por unidad de tiempo se han completado. En este benchmark, para generar informaci´on interesante, los datos que se esperan obtener est´an relacionados con la velocidad y no con el throughput. Lo importante es el tiempo que le cuesta de m´as ejecutar una aplicaci´on. Adem´as se estudiar´an los requerimientos de memoria de ejecutar aplicaciones instrumentadas. Para la base de este benchmark se utilizar´an bastantes programas usados por CPU2006. Esto es posible ya que todo el c´odigo fuente de estas aplicaciones est´a disponible libremente. Adem´as, se aprovechar´a una parte de la metodolog´ıa, como repeticiones, intercalado y optimizaciones. En CPU2006, cada aplicaci´on usada se ejecuta con diferentes argumentos y optimizaciones. Al igual que en ese benchmark, cada aplicaci´on se ejecutar´a varias veces para obtener una media del tiempo de ejecuci´on. Aunque en CPU2000 se ejecutaba de forma consecutiva cada prueba, a partir de CPU2006 se ejecutan las pruebas intercaladas, de una forma m´as real, que es otra parte de la metodolog´ıa que se usar´a en este benchmark. Otras opciones m´as tomadas de CPU2006 son compilar con diferentes niveles de optimizaci´on los ejecutables. Los resultados de la comparativa se centran en tiempo de ejecuci´on, instrucciones ejecutadas y el uso de memoria. La medici´on se realizar´a varias veces por ejecutable, y con diferentes niveles de optimizaci´on. Primero se ejecutar´an sin instrumentar para conocer el tiempo que le cuesta realizar una tarea. Despu´es se instrumentar´a para conocer el tiempo de ejecuci´on, uso de memoria y datos relacionados con la instrumentaci´on. Adem´as, las instrumentaciones ser´an realizadas por diferentes frameworks, por lo que se podr´a observar cu´al realiza mejor la tarea de instrumentaci´on, el rendimiento en funci´on de las instrucciones o tiempo de ejecuci´on y qu´e niveles de optimizaci´on pueden ser mejores para instrumentar. Las aplicaciones seleccionadas para el benchmark son todas de uso intensivo de CPU, y se han dividido en cuatro grupos: c´alculo entero, c´alculo real, gran demanda de E/S y software de acceso a memoria. Las tablas 5.1-5.4 muestran un resumen de las aplicaciones seleccionadas. La primera columna indica el nombre m´as descriptivo de la aplicaci´on, despu´es la versi´on utilizada para el benchmark, el lenguaje de programaci´on en el que est´an desarrolladas, y el tipo de categor´ıa en que se engloban las aplicaciones. Finalmente, se indica si esa aplicaci´on ha sido utilizada en alg´un otro benchmark. En la Tabla 5.1 hay software en las que las opciones de c´alculo son de n´umeros enteros. Se utilizan ficheros de entrada diferentes a los de SPEC para reducir el tiempo 18 5. Creaci´on de benchmark Secci´on 5.2 Nombre Versi´on Lenguaje Tipo Origen bzip2 1.0.6 C Compresi´on SPEC CINT 2006 GNU go 3.8 C IA - Juegos SPEC CINT 2006 hmmer 3.0 C Gen´etica SPEC CINT 2006 h264ref 18.2 C Compresi´on video SPEC CINT 2006 libquantum 1.0.0 C F´ısica, computaci´on cu´antica SPEC CINT 2006 Tabla 5.1: Aplicaciones de c´alculo entero. de ejecuci´on, p.e., una ejecuci´on de bzip2 en este benchmark sin instrumentar dura 20 segundos, y en SPEC CINT 2006 son 848 segundos [NEC08] (42 veces menos). Nombre Versi´on Lenguaje Tipo Origen namd 2.8 C++ Biolog´ıa, simulaci´on de mol´eculas SPEC CFP 2006 povray 3.0 C Renderizaci´on SPEC CFP 2006 milc v6 C F´ısica, Cromodin´amica cu´antica SPEC CFP 2006 mlucas 2.8x C Num´erica, c´alculo de n´umeros primos SPEC CFP 2000 linpack 29.5.04 Fortran Num´erica, multiplicaci´on de matrices Linpack benchmark Tabla 5.2: Aplicaciones de c´alculo real. Para la categor´ıa de software de c´alculo real se ha seleccionado software que se puede ver en la Tabla 5.2. Una parte del software es usado en SPEC CFP 2006 y CFP 2000, pero se usan ficheros de entrada diferentes para reducir el tiempo de ejecuci´on. Tambi´en se utiliza linpack, una librer´ıa de resoluci´on de ecuaciones lineales. Nombre Versi´on Lenguaje Tipo Origen whirlpool 2aRev C Criptograf´ıa, Hash Propio ripemd 160 C Criptograf´ıa, Hash Propio aes 1 C Criptograf´ıa, cifrado Propio ffmpeg 0.10 C Conversi´on de formatos video/audio Phoronix Test Suite Tabla 5.3: Aplicaciones con gran demanda de entrada/salida. Para este benchmark se han a˜nadido m´as categor´ıas de las que aparecen en otros benchmarks, como p.e., aplicaciones que tambi´en tuvieran uso intensivo de CPU, pero no s´olo que trabaje en memoria, sino accediendo a disco leyendo un fichero de entrada 19 Secci´on 5.3 5. Creaci´on de benchmark y obteniendo uno de salida de igual tama˜no o superior. Este software se puede ver en la Tabla 5.3. Estas aplicaciones realizan c´alculo sobre enteros. Nombre Versi´on Lenguaje Tipo Origen memtester 4.0.5 C Comprobaci´on de memoria defectuosa Propio Tabla 5.4: Aplicaciones de acceso a memoria. Finalmente, se ha a˜nadido otra categor´ıa m´as donde el software accediera al subsistema de memoria, se ve en la Tabla 5.4. memtester es una aplicaci´on de uso intensivo de CPU en c´alculo entero. 5.3. Descripci´on del benchmark Por cada aplicaci´on que ha sido seleccionada para el benchmark se van a ejecutar un grupo de pruebas. Este grupo de pruebas se forma con el ejecutable de la aplicaci´on, pero con diferentes niveles de optimizaci´on (-O0, -O3), que despu´es ser´a ejecutado sin instrumentar e instrumentado con los diferentes frameworks de DBI. Adem´as se ejecutar´a 3 veces cada prueba, pero no seguidas, sino alternadas. Esto se hace de forma similar a SPEC CPU 2006, como se ha comentado en la secci´on 5.2 no ejecuta consecutivamente la misma aplicaci´on con las mismas opciones, sino que hay alternancia de ejecuci´on. Otra diferencia que hay con SPEC CPU 2006 es el fichero de entrada que se utiliza por cada aplicaci´on, debido al slowdown que aparece en la instrumentaci´on, se usan ficheros que ofrezcan menos carga de proceso. Esta diferencia puede observarse en el ap´endice D.16. Primero ser´an ejecutados sin instrumentaci´on y despu´es instrumentados. Se esperan obtener los siguientes datos: tiempo de ejecuci´on real y total en segundos tiempo de ejecuci´on en modo kernel en segundos tiempo de ejecuci´on en modo de usuario en segundos n´umero de veces que el proceso ha sido paginado a disco de memoria porcentaje de uso de la cpu uso de memoria durante la ejecuci´on n´umero de instrucciones/bloques b´asicos ejecutados Puede haber pruebas que ser´an repetidas o descartadas, en funci´on de si ha sido utilizado un tiempo de ejecuci´on excesivo o ha sido paginado muchas veces en comparaci´on con las otras pruebas. Esto es as´ı porque las aplicaciones est´an preparadas para que el resultado obtenido de ellas sea siempre el mismo, por lo que se espera que su ejecuci´on dure aproximadamente lo mismo. Para esto se utilizar´an intervalos de confianza. 20 5. Creaci´on de benchmark Secci´on 5.4 5.4. Herramientas para el benchmark En el benchmark se van a realizar dos herramientas con diferentes tipos de instrumentaci´on: A nivel de instrucci´on A nivel de bloque b´asico Con la primera herramienta, instrumentaci´on a nivel de instrucci´on, se quiere conseguir el m´aximo slowdown. Esto es as´ı porque en la parte de la instrumentaci´on, donde se decide en qu´e punto se inserta la instrumentaci´on, se instrumentan todas las instrucciones. De esta forma, por cada instrucci´on ejecutada, tambi´en se ejecutar´a el c´odigo a˜nadido, que es incrementar un contador. Al finalizar la ejecuci´on se devuelve el resultado del contador total de instrucciones ejecutadas. Esta herramienta se ha desarrollado con los tres frameworks de DBI: Pin, Valgrind y DynamoRIO. Con la segunda herramienta, instrumentaci´on a nivel de bloque b´asico, se quiere conseguir una sobrecarga media. En la mayor´ıa de art´ıculos que eval´uan frameworks de DBI como [PA06], [Sof07] y [WM08] utilizan este m´etodo. En la parte de instrumentaci´on, se instrumentan todos los bloques b´asicos. Por cada bloque b´asico ejecutado, se ejecutar´a el c´odigo a˜nadido, que es incrementar un contador. Al finalizar la ejecuci´on se muestra la suma del n´umero total de bloques b´asicos ejecutados. Esta herramienta se ha desarrollado tambi´en con los tres frameworks de DBI: Pin, Valgrind y DynamoRIO. 5.5. Mediciones en el benchmark En esta secci´on se van a describir los m´etodos que utiliza el benchmark para medir el tiempo de ejecuci´on y el consumo de memoria de una aplicaci´on instrumentada y sin instrumentar. 5.5.1. Tiempo Todas las pruebas se hacen con el comando /usr/bin/time, diferente de la variante integrada en la shell time, parte del int´erprete de comandos. Esta es una forma b´asica de medir el tiempo que tarda en ejecutarse un programa. Ofrece el tiempo real desde que inicia hasta que acaba y adem´as el tiempo que realmente se est´a ejecutando en la CPU, distinguiendo entre el c´odigo de usuario y sus llamadas al sistema. La mayor´ıa de la informaci´on ofrecida por /usr/bin/time est´a derivada de la llamada al sistema wait3 owait4, con lo que los datos obtenidos ser´an tan buenos como los que pueda ofrecer esta llamada. En los sistemas que no est´e disponible se usa la llamada times que ofrece mucha menos informaci´on. En el sistema donde se ejecutar´a el benchmark la llamada al sistema usada es wait4. 21 Secci´on 5.5 5. Creaci´on de benchmark 5.5.2. Memoria Para medir el consumo de memoria, el benchmark ejecuta un proceso en background despu´es de lanzar la aplicaci´on a evaluar. Este proceso se encarga de revisar en /proc/<pid de la aplicaci´on>/status el consumo en el campo VmPeak que contiene el pico de memoria utilizada. Para definir el intervalo en el que se consulta el consumo se usaron valores inferiores a 1 segundo, y se fue aumentando una vez que se pudo comprobar que en las aplicaciones no se incrementaba el consumo de memoria en el ´ultimo intervalo por encima del valor de pico. 22 Cap´ıtulo 6 Experimentos En este cap´ıtulo se resumen los experimentos realizados con el benchmark, comenzando por la definici´on del entorno de pruebas y mostrando los resultados con un an´alisis cr´ıtico. Se ha utilizado un equipo con procesador Intel Core 2 Duo T7300 a 2 Ghz, 2 GiB de memoria RAM, S.O. Fedora Core 14 con kernel 2.6.35.14-106.fc14.i686.PAE. Se le ha deshabilitado al equipo uno de los cores para evitar que ciertas aplicaciones lanzaran m´as de un proceso a la vez, y que el tiempo de CPU se encontrara en valores cercanos al 190 %. En las Tablas 6.1 y 6.2 se resume el hardware y software, respectivamente, utilizado para la realizaci´on del experimento. Nombre CPU Intel R CoreTM2 Duo CPU T7300 Caracter´ısticas 2.00 GHz, 667 MHz bus CPU(s) 2 cores, 1 desactivado. Cach´e primer nivel 32 KiB I + 32 KiB D por core Cach´e segundo nivel 4 MiB I+D Memoria RAM 2 GiB (2x1 GiB DDR2 SODIMM 667 Mhz) Disco Duro 120 GB HITACHI HTS54161 Tabla 6.1: Hardware utilizado en las pruebas. Sistema Operativo Fedora Core 14 32bit Compilador C gcc (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4) Compilador Fortran GNU Fortran 4.5.1 Sistema de ficheros ext4 Nivel sistema Run level 3 (multiusuario) Tabla 6.2: Software utilizado en las pruebas. Las versiones de los frameworks de DBI que se han utilizado han sido Pin v.2.10, 23 Secci´on 6.1 6. Experimentos Valgrind v.3.7.0 y DynamoRIO v.2.2.0-2. 6.1. Entorno de pruebas En los experimentos se quiere que el resto de procesos que est´an funcionando en la m´aquina afecten lo m´ınimo posible, por lo que para que se tengan los m´ınimos procesos funcionando se iniciar´a la m´aquina en nivel 3 (multiusuario con red). Una vez reiniciada la m´aquina en ese nivel no se tendr´a ning´un proceso relacionado con el gestor de escritorio o salvapantallas que pueda influir durante la ejecuci´on del benchmark. En este momento y conectado remotamente por ssh se inicia el benchmark. Mientras se ejecuta, se puede ver por el terminal el programa del benchmark que se est´a ejecutando, si lo hace sin instrumentar o con c´ual est´a instrumentado, el n´umero de repetici´on de la prueba y si es el benchmark de instrucciones o de bloques b´asicos. El benchmark genera un fichero de log y un fichero de valores delimitados por comas (csv) en el que se puede encontrar el tiempo real de ejecuci´on, el tiempo en modo kernel, el tiempo en modo de usuario, los fallos de p´agina, el porcentaje de CPU usado y la l´ınea de comando. Como datos adicionales se encuentran el consumo de memoria por proceso y el n´umero de instrucciones o de bloques b´asicos ejecutados por aplicaci´on instrumentada en el log. 6.2. Resultados Se ha visto previamente en [LCM+05] y [NS07] que la instrumentaci´on provoca una ralentizaci´on de la ejecuci´on del programa instrumentado. Aqu´ı, se va a observar la eficiencia de cada framework de DBI intentando inferir cu´al es el m´as adecuado seg´un sea el tipo de aplicaci´on que se va a instrumentar. La Figura 6.1 muestra los resultados de tiempo de ejecuci´on para la aplicaci´on h264ref, una aplicaci´on de conversi´on de audio y v´ıdeo. Como se ha dicho previamente, una de las caracter´ısticas de la instrumentaci´on es que provoca una ralentizaci´on de la ejecuci´on, y aqu´ı se comprueba. Es la prueba m´as lenta de todas una vez instrumentada. Bajo Valgrind llega a durar 2615 segundos en la versi´on sin optimizar del ejecutable, y 918 segundos en la optimizada, cuando sin instrumentar son 175 segundos sin optimizar y 52 segundos optimizada. Aunque en relaci´on al slowdown (la relaci´on entre el tiempo de ejecuci´on instrumentado y sin instrumentar), ´esta no es la peor aplicaci´on de todas: bajo Valgrind se obtiene 11,2x sin optimizar, y 17,43x optimizada. En la Figura 6.2 se muestra el slowdown de la aplicaci´on ffmpeg instrumentada por los tres frameworks en ambas optimizaciones en la instrumentaci´on por instrucciones. Esta es la aplicaci´on que mayor slowdown presenta. Como en la aplicaci´on anterior, h264ref, el mayor slowdown se tiene bajo la instrumentaci´on de Valgrind, que en sus versiones sin optimizar y optimizada tiene una ratio de 34,6x y 35,38x respectivamente. No s´olo lo m´as importante es que tarde m´as tiempo, sino el n´umero de veces que se puede llegar a ejecutar m´as lenta una aplicaci´on. Revisando el slowdown de todas las 24 6. Experimentos Secci´on 6.2 Sin instrumentar PIN Valgrind DynamoRIO 0 500 1000 1500 2000 2500 3000 Tiempo (s) −O0 −O3 Figura 6.1: Tiempo de ejecuci´on de la aplicaci´on h264ref con instrumentaci´on por instrucciones y optimizaciones. PIN Valgrind DynamoRIO 0 5 10 15 20 Slowdown −O0 −O3 Figura 6.2: Slowdown en el benchmark de ffmpeg con instrumentaci´on por instrucciones y optimizaciones. 25 BIBLIOGRAF´ IA BIBLIOGRAF´ IA [Int86] Intel. 80386 programmer’s reference manual. Intel Corporation, 1986. [Int12] Intel. Intel R VTuneTM Amplifier XE , 2012. [Jon08] M. Tim Jones. Anatomy of linux dynamic libraries. 2008. [LB94] James R. Larus and Thomas Ball. Rewriting executable files to measure program behavior. Softw. Pract. Exper., 24(2):197–218, February 1994. [LCM+05] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. SIGPLAN Not., 40(6):190–200, June 2005. [NEC08] NEC Corporation. SPEC R CINT2006 Result - Intel Core 2 Duo T7400. http://www.spec.org/cpu2006/results/res2008q2/cpu2006- 20080316-03692.html, 2008. [NS07] Nicholas Nethercote and Julian Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. SIGPLAN Not., 42(6):89–100, June 2007. [PA06] G.-R. Uh; R. Cohn; B. Yadavalli; R. Peri and R. Ayyagari. Analyzing dynamic binary instrumentation overhead. In Workshop on Binary Instrumentation and Applications, WBIA, 2006. [RAH08] Arkaitz Ruiz-Alvarez and Kim M. Hazelwood. Evaluating the impact of dynamic binary translation systems on hardware cache performance. In IISWC, pages 131–140, 2008. [SE94] Amitabh Srivastava and Alan Eustace. ATOM: a system for building customized program analysis tools. SIGPLAN Not., 29(6):196–205, June 1994. [SG92] Inc. Silicon Graphics. MIPS Assembly Language Programmer’s Guide. Silicon Graphics, Inc., 1992. [Sof07] A. Guha; J.D. Hiser; Naveen Kumar; J. Yang; M. Zhao; S. Zhou; B.R. Childers; J.W. Davidson; K. Hazelwood; M.L. Soffa. Virtual execution environments: Support and tools. In International Parallel and Distributed Processing Symposium (IPDPS 2007), Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, March 2007. [SSNB06] Swaroop Sridhar, Jonathan S. Shapiro, Eric Northup, and Prashanth P. Bungale. HDTrans: an open source, low-level dynamic instrumentation system. In Proceedings of the 2nd international conference on Virtual execution environments, VEE ’06, pages 175–185, New York, NY, USA, 2006. ACM. [Wal91] David W. Wall. Systems for late code modification. In WRL Research Report 91/5, pages 275–293. Springer-Verlag, 1991. 32 BIBLIOGRAF´ IA BIBLIOGRAF´ IA [WM08] Vincent M. Weaver and Sally A. McKee. Using dynamic binary instrumentation to generate multi-platform simpoints: methodology and accuracy. In Proceedings of the 3rd international conference on High performance embedded architectures and compilers, HiPEAC’08, pages 305–319, Berlin, Heidelberg, 2008. Springer-Verlag. 33 BIBLIOGRAF´ IA BIBLIOGRAF´ IA 34 Ap´endice A Fases de Desarrollo A.1. Diagrama de Gantt En este ap´endice se describe la distribuci´on temporal de cada una de las etapas de este proyecto. La figura A.1 muestra el Diagrama de Gantt donde se reflejan las diferentes tareas realizadas y la figura A.2 el tiempo dedicado a su desarrollo, que ha sido de 410 horas y se puede ver detallado en la Tabla A.1. Figura A.1: Diagrama de gantt. Primero se realiz´o una b´usqueda de informaci´on sobre DBI, ya que no se pose´ıan conocimientos previos. Se busc´o informaci´on sobre la instrumentaci´on y sus diferentes tipos, an´alisis est´atico, din´amico, DBI, frameworks de DBI y trabajos previos relacionados con rendimiento para frameworks de DBI. Una vez que se encontr´o informaci´on suficiente, se procedi´o a la selecci´on de frameworks de DBI, donde el procedimiento que se realizaba para cada uno era: descarga del c´odigo fuente del framework, compilaci´on, instalaci´on y prueba de funcionamiento. Una vez que se llegaba a este punto, se estudiaba el API y se proced´ıa a programar una herramienta b´asica. Se hizo un estudio sobre los benchmarks existentes y de c´omo se pod´ıan llegar a usar en el desarrollo de este PFC. Se comprob´o que no hab´ıa ninguno que encajara y se desarroll´o uno nuevo. 35 Secci´on A.1 A. Fases de Desarrollo Para la creaci´on de este benchmark primero se buscaron aplicaciones y se desarrollaron metodolog´ıas para la ejecuci´on de las aplicaciones de prueba. Se buscaron diferentes m´etodos para medir el tiempo de ejecuci´on de las aplicaciones y el consumo de memoria de estas. Una vez finalizado este proceso se realizaron las pruebas con el benchmark para obtener los resultados para este PFC. La memoria del proyecto se ha ido realizando poco a poco, desde el principio del proyecto. Se fue completando al final con los resultados y conclusiones de los experimientos realizados. Benchmarks Problema instrucciones Documentación memoria Trabajo con Frameworks Reuniones Busqueda información Reuniones Busqueda información Trabajo con Frameworks Problema instrucciones Benchmarks Documentación memoria Figura A.2: Horas dedicadas. Tareas Horas Reuniones 20 B´usqueda de informaci´on 75 Trabajo con frameworks 95 Problema contado de instrucciones 55 Estudio y creaci´on de benchmark 60 Documentaci´on memoria 105 Total 410 Tabla A.1: Horas dedicadas. 36 Ap´endice B Problemas encontrados En este cap´ıtulo se resumen las dificultades m´as destacables que han ido apareciendo durante la realizaci´on de este proyecto. B.1. Cuenta de instrucciones Al principio del estudio se hicieron pruebas para verificar el funcionamiento de los frameworks de DBI. La primera herramienta se dedicaba a contar instrucciones ejecutadas en Pin, Valgrind y DinamoRIO. Se esperaba que el resultado de las tres instrumentaciones fuera exactamente el mismo n´umero de instrucciones. Para esto se cre´o un programa en C que calculaba el factorial de un n´umero. Los resultados fueron que, para instrumentar el comando $ factorial >/dev/null, se obten´ıan 99094 instrucciones en Pin, 120014 en Valgrind y 10150 en DynamoRIO. Debido a esto, se hicieron pruebas con m´as ejecutables para ver si exist´ıa alg´un tipo de correlaci´on y los resultados son los que aparecen en la Tabla B.1. Son datos que no tienen ninguna relaci´on entre ellos, por lo que se procedi´o a estudiar paso a paso el funcionamiento de las herramientas programadas. Pin Valgrind DynamoRIO xfsinfo 269699 298295 25581 ls 443104 474249 103596 xeyes 875730 920633 223912 cat 219189 242386 63354 Tabla B.1: Instrucciones contadas por framework de DBI. El primer paso fue sacar las primeras instrucciones de la aplicaci´on instrumentada, junto con su traza, para ver que instrumenta y cuenta la herramienta, para despu´es compararlas con las que aparecen en un debugger. Para esto, primero se desensambl´o el ejecutable con $ objdump -d ./factorial y as´ı ver cu´ales son las instrucciones en 37 Secci´on B.1 B. Problemas encontrados ensamblador y sus direcciones. Aunque en Pin y Valgrind las primeras instrucciones coincid´ıan, en DynamoRIO no era as´ı. Buscando m´as informaci´on, se obtuvo que DynamoRIO no soporta early injection (no instrumenta desde la primera instrucci´on). Adem´as DynamoRIO necesita que el ejecutable est´e enlazado din´amicamente, y cambia el proceso de carga de la aplicaci´on: en vez de utilizar el loader del sistema utiliza uno privado y carga sus librer´ıas despu´es de las de la aplicaci´on. En Linux comienza la instrumentaci´on cuando DynamoRIO vuelve de la inicializaci´on de las librer´ıas din´amicas (exactamente cuando deja la direcci´on de retorno en la pila). Si el ejecutable no est´a enlazado din´amicamente, no puede cargar sus librer´ıas y no puede instrumentar. Debido a esta limitaci´on, en aplicaciones peque˜nas, el n´umero de instrucciones que instrumenta es de un orden de magnitud menor. En la versi´on para Windows s´ı soporta early injection. El segundo problema que apareci´o fue que en la traza de direcciones las instrucciones eran las mismas, pero cada vez que se ejecutaba, las direcciones eran diferentes. Esto es debido a que a partir de la versi´on 2.6 del kernel de Linux tiene activado por defecto y por motivos de seguridad Virtual Address Space Randomization. Se soluciona deshabilit´andolo con el siguiente comando: # echo 0 > /proc/sys/kernel/randomize_va_space En el momento que las direcciones eran las mismas, se estudi´o el proceso de carga de un ejecutable bajo GNU/Linux. Cuando se invoca un ejecutable, el kernel lo carga en memoria virtual del espacio de usuario, despu´es en la secci´on .interp busca c´ual es el cargador din´amico a utilizar (p.e., /lib/ld-linux.so.2) y lo inicializa, cargando despu´es todas las bibliotecas dependientes (p.e., libc), resuelve los s´ımbolos, y finalmente transfiere la ejecuci´on al ejecutable original para comenzar su ejecuci´on [Jon08]. Debido a esto, cada vez se instrumenta un ejecutable con la opci´on para dar la traza de las instrucciones, en vez de comenzar la ejecuci´on en la direcci´on de inicio (start address) que se obtiene con objdump comienza en otra previa. $ objdump -f factorial prx2: file format elf32-i386 architecture: i386, flags 0x00000112: EXEC_P, HAS_SYMS, D_PAGED start address 0x08048310 Para poder hacer una comparaci´on m´as sencilla, se decide compilar el programa de prueba sin enlazar din´amicamente. Adem´as, para tener m´as informaci´on de lo que se est´a ejecutando antes del inicio se compila con las librer´ıas est´andar de C est´aticas con informaci´on de depuraci´on (paquete glibc-debuginfo-2.13-2). Los par´ametros a utilizar en la compilaci´on son: Con informaci´on de depuraci´on del programa (-g) Uso de glibc con informaci´on de depuraci´on(-L/usr/lib/debug/usr/lib) 38 B. Problemas encontrados Secci´on B.1 En est´atico (-static) para que no incluya librer´ıas externas. Una vez realizada esta operaci´on sobre el ejecutable, cuando se instrumenta, las instrucciones ejecutadas bajo Pin son 14223 y bajo Valgrind 14572. Hay 349 instrucciones de diferencia que se va a averiguar qu´e hacen y por qu´e se ejecutan en uno y no en el otro. Siguiendo la traza de instrucciones, se comprueba que la diferencia de ´estas corresponde a que el valor de los vectores de entorno (envp) y de los vectores auxiliares (auxv) son diferentes en ambas ejecuciones. En envp aparecen variables de entorno diferentes que son a˜nadidas por los scripts de inicio de Pin y Valgrind, cada variable de entorno es evaluada individualmente en el proceso de carga del ejecutable, por lo que afecta el tener m´as o menos variables de entorno a las instrucciones ejecutadas. En auxv se encuentra la diferencia: en Pin se pasan valores para AT SYSINFO yAT SYSINFO EHDR, pero para Valgrind no, por lo que primeramente afecta al procesamiento del vector ya que son de tama˜no diferentes y despu´es en esos valores est´a el puntero al Virtual Dynamicallylinked Shared Objects (VDSO), que es la forma actual de hacer llamadas al sistema. En este m´etodo de llamadas al sistema se utilizan las instrucciones sysenter/sysexit y previamente se utilizaban interrupciones software con int 0x80. La primera conclusi´on que se obtiene es que con un ejecutable enlazado din´amicamente, el proceso que realiza el cargador din´amico, incluyendo la carga de librer´ıas, se realiza de forma diferente entre Pin y Valgrind. La segunda conclusi´on es que las variables de entorno afectan directamente al n´umero de instrucciones ejecutadas. Y la tercera conclusi´on y m´as importante de todas es que las llamadas al sistema son realizadas de forma diferente entre Pin y Valgrind. Por este motivo, nunca se ejecutar´a el mismo n´umero de instrucciones para el mismo programa instrumentado por diferentes frameworks. La ´unica forma que se ha encontrado para que se cuenten el mismo n´umero de instrucciones entre distintos frameworks ha sido program´andolo directamente en ensamblador. Compilando un programa que s´olo ten´ıa 12 instrucciones, el funcionamiento en Pin y Valgrind era correcto y contaban sin ning´un problema. Sin embargo, DynamoRIO no pod´ıa instrumentar este ejecutable en ensamblador porque no era un ejecutable enlazado din´amicamente. En aplicaciones con un n´umero alto de instrucciones puede llegar a haber muy poca diferencia, como se ha comprobado en este PFC y se puede ver en la Tabla B.2, que muestra el n´umero de instrucciones ejecutadas para las aplicaciones whirlpool y memtester optimizadas. Pin Valgrind DynamoRIO whirlpool -O3 74222379297 74222385145 74222287028 memtester -O3 241201530296 241201536828 241201371000 Tabla B.2: Instrucciones contadas para las aplicaciones whirlpool y memtester 39 Secci´on B.2 B. Problemas encontrados B.2. Fallo en ejecuci´on Durante la ejecuci´on del benchmark ha aparecido un fallo con la aplicaci´on mlucas. Como de todas las aplicaciones que hay en el benchmark se dispone del c´odigo fuente, a partir de los mensajes de salida del fallo y de todo el c´odigo que se encontraba a su alrededor, se ha podido hacer un peque˜no programa de prueba capaz de repetir el fallo. #include <stdio.h> int main(int argc, char **argv) { double RND_A,RND_B,prueba; prueba= 5.4321; RND_A = 3.0*0x4000000*0x2000000*0x800; RND_B =12.0*0x2000000*0x1000000*0x800; printf("INFO: using 80-bit-double form of rounding constant\n"); printf("prueba: %20.15f RND_A: %20.15f RND_B: %20.15f\n",prueba, RND_A, RND_B); if( ((prueba+RND_A)-RND_B) != 5.0 ) { printf("INFO:prueba=%20.15f, rnd(prueba)=%20.15f\n",prueba, (prueba+RND_A)-RND_B); printf("ERROR 30 in util.c\n"); return(1); } return 0; } Seg´un el programa original para hacer el redondeo de una variable usa la funci´on rnd(). Lo que hace esta funci´on es, a partir de un n´umero real sumar y restar dos constantes de redondeo, suma el valor RND Ay resta el valor RND B, ambos valores son iguales pero calculados de forma diferente. Y el comportamiento esperado es que el resultado final sea la parte entera del n´umero real a redondear. El n´umero que se va a redondear es 5.4321. El programa se comporta de esta manera sin instrumentar y bajo la instrumentaci´on de Pin y DynamoRIO. $ pruebafallo INFO: using 80-bit-double form of rounding constant prueba: 5.432100000000000 RND_A: 13835058055282163712.000000000000000 RND_B: 13835058055282163712.000000000000000 Sin embargo, bajo la ejecuci´on en Valgrind el resultado no es el esperado: $ valgrind pruebafallo ==2503== Memcheck, a memory error detector ==2503== Copyright (C) 2002-2011, and GNU GPL’d, by Julian Seward et al. 40 B. Problemas encontrados Secci´on B.2 ==2503== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info ==2503== Command: ./pruebafallo ==2503== INFO: using 80-bit-double form of rounding constant prueba: 5.432100000000000 RND_A: 13835058055282163712.000000000000000 RND_B: 13835058055282163712.000000000000000 INFO: prueba = 5.432100000000000, rnd(prueba) = 0.000000000000000 ERROR 30 in util.c La condici´on del IF ya no falla, no se ha hecho bien el redondeo. Por este motivo falla mlucas en la prueba inicial de comprobaci´on de funcionamiento y ya no sigue ejecut´andose. En el programa original los dos valores reales con los que se hac´ıa esta comprobaci´on eran 1 √2y 2 ×π, cuyas partes enteras son 1 y 6 respectivamente. Al ir a abrir un bug sobre este fallo, ´este ya estaba abierto, y reportado m´ultiples veces por diferentes usuarios. El problema es que Valgrind no puede trabajar con n´umeros de 80 bits en las arquitecturas x32 y x64. El bug se puede ver en https://bugs.kde.org/show_bug.cgi?id=197915 41 Secci´on C.12 C. Aplicaciones usadas en el benchmark la simulaci´on a realizar a su3 rmd Salida: Muestra por la salida est´andar el resultado de la simulaci´on. P´agina web: http://physics.indiana.edu/~sg/milc.html Autor: Steven Gottlieb et al. Usada en: SPEC CFP 2006 C.12. povray Versi´on: 3.0 Categor´ıa: Renderizaci´on Tipo de c´alculo realizado: Real Lenguaje de programaci´on: C Descripci´on: Es una herramienta que produce gr´aficos por ordenador de muy alta calidad. Utiliza el algoritmo de trazado de rayos para generar im´agenes tridimensionales. Entrada: Se usa uno de los ficheros de ejemplo que incluye povray: radio-patio.pov Salida: Se obtiene el fichero patio-radio.png con la imagen P´agina web: http://www.povray.org/ Autor: David Buck et al. Usada en: SPEC CFP 2006 C.13. mlucas Versi´on: 2.8x Categor´ıa: Num´erica, b´usqueda de n´umeros primos Tipo de c´alculo realizado: Real Lenguaje de programaci´on: C Descripci´on: Realiza la b´usqueda de n´umeros primos de Mersenne, que tienen la forma de Mp= 2p−1 utilizando el algoritmo de Lucas-Lehmer. Entrada: Se le indica el rango de exponentes para buscar n´umeros primos de Mersenne Salida: Muestra los n´umeros primos que se hayan encontrado. P´agina web: http://hogranch.com/mayer/README.html Autor: Ernst Mayer et al. Usada en: SPEC CFP 2000 C.14. namd Versi´on: 2.8 Categor´ıa: Biolog´ıa, simulaci´on de mol´eculas Tipo de c´alculo realizado: Real 48 C. Aplicaciones usadas en el benchmark Secci´on C.15 Lenguaje de programaci´on: C++ Descripci´on: Es un software de din´amica molecular paralela dise˜nado para simulaci´on de alto rendimiento de grandes sistemas biomoleculares. Entrada: Se utiliza un fichero de prueba, que ofrecen los autores de namd, que se llama tiny.namd preparado para un benchmark, ya que es la carga significativa para un ´unico procesador en una gran simulaci´on. Salida: Genera 3 ficheros tiny.coor,tiny.vel ytiny.xsc con los resultados de la simulaci´on. P´agina web: http://www.ks.uiuc.edu/Research/namd/ Autor: Jim Phillips et al. Usada en: SPEC CFP 2006 C.15. linpack Versi´on: 25.5.04 Categor´ıa: Num´erica, multiplicaci´on de matrices. Tipo de c´alculo realizado: Real Lenguaje de programaci´on: Fortran Descripci´on: Es una librer´ıa software que se usa para resolver sistemas de ecuaciones. A partir de aqu´ı naci´o el benchmark linpack, que resuelve sistemas de ecuaciones haciendo uso intensivo de operaciones en c´alculo real. Entrada: Se le indica el tama˜no de la matriz, 1500x1500. Salida: Ofrece informaci´on del tiempo que le ha costado realizar las operaciones. P´agina web: http://www.netlib.org/linpack/ Autor: Jack Dongarra et al. Usada en: Linpack benchmark 49 Ap´endice D Resultados del benchmark En este ap´endice se muestran los resultados de la ejecuci´on del benchmark en todas las aplicaciones. Por cada aplicaci´on se presenta una tabla dividida en tres partes: Ejecuciones nativas, sin instrumentar. Ejecuciones instrumentadas por instrucciones. Ejecuciones instrumentadas por bloques b´asicos. Por cada parte se presentan tres ejecuciones sin optimizar (-O0) y tres optimizadas (-O3), adem´as, en las instrumentadas se muestran para los tres frameworks. En todas las tablas se presenta el consumo de memoria de las aplicaciones y para las instrumentadas tambi´en se presenta el n´umero de instrucciones o bloques b´asicos ejecutados. Finalmente, en la secci´on D.16 se mostrar´a el tiempo total de ejecuci´on del benchmark y la comparaci´on en tiempo con SPEC. 51 Secci´on D.1 D. Resultados del benchmark D.1. bzip2 Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 20.6 20.51 20.58 15.03 15.06 15.03 Mem. (kiB) 9440 9440 9440 9432 9432 9432 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 277.58 273.7 273.67 185.71 185.36 185.58 Mem. (kiB) 45816 45816 45816 46524 46524 46524 Slowdown 13,45 13,33 13,27 12,32 12,29 12,32 Instrucc. 73656398144 73656398144 73656398144 48475694952 48475694952 48475694952 Valgrind Tiempo (s) 414.49 412.92 414.91 278.01 276.94 277.34 Mem. (kiB) 58328 58328 58328 58320 58320 58320 Slowdown 20,09 20,11 20,13 18,45 18,36 18,41 Instrucc. 73656441642 73656441646 73656441638 48475738454 48475738460 48475738454 DynamoRIO Tiempo (s) 174.64 174.7 174.7 153.26 153.44 153.22 Mem. (kiB) 142036 142036 142036 142028 142028 142028 Slowdown 8,46 8,50 8,47 10,15 10,16 10,16 Instrucc. 73637943900 73637943900 73637943900 48457240420 48457240420 48457240420 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 72,31 72,49 72,94 66,47 66,98 66,91 Mem. (kiB) 45952 45952 45952 46564 46564 46564 Slowdown 3,88 3,91 3,93 4,86 4,90 5,38 Bloques 7063386170 7063386170 7063386170 6488305984 6488305984 6488305984 Valgrind Tiempo (s) 109,47 110,02 109,99 104,88 104,57 104,55 Mem. (kiB) 54996 54996 54996 54988 54988 54988 Slowdown 5,88 5,94 5,93 7,67 7,65 8,40 Bloques 4472395968 4472395967 4472395967 3998502071 3998502072 3998502072 DynamoRIO Tiempo (s) 29,18 29,09 29,09 21,93 21,87 21,73 Mem. (kiB) 142036 142036 142036 142028 142028 142028 Slowdown 1,56 1,57 1,57 1,60 1,60 1,74 Bloques 2139535991 2139535991 2139535991 2609502570 2609502570 2382277616 52 D. Resultados del benchmark Secci´on D.2 D.2. GNU go Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 133,3 133,3 133,42 82,98 82,97 82,96 Mem. (kiB) 24120 24120 24116 24328 24332 24332 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 1118,01 1117,59 1116 732,8 732,44 729,12 Mem. (kiB) 69340 69356 69352 75380 75392 75380 Slowdown 8,39 8,39 8,37 8,85 8,84 8,80 Instrucc. 247750494248 247750666655 247750666655 153754482838 153754535528 153754683960 Valgrind Tiempo (s) 2168,5 2165,89 2162,98 1542,52 1544,43 1546,33 Mem. (kiB) 71288 71288 71288 71496 71496 71496 Slowdown 16,29 16,27 16,23 18,62 18,64 18,66 Instrucc. 247750711832 247752391901 247785718265 153746809732 153746892452 153770256115 DynamoRIO Tiempo (s) 1028,65 1027,37 1032,39 789,55 790,33 789 Mem. (kiB) 156544 156548 156544 156756 156756 156756 Slowdown 7,72 7,71 7,74 9,51 9,52 9,51 Instrucc. 247745640933 247782861334 247748101772 150904441919 150904369639 150904369639 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 419,82 419,94 419,79 337,57 337,19 337,56 Mem. (kiB) 66880 66900 66900 73112 73108 73108 Slowdown 3,48 3,48 3,48 4,49 4,49 4,49 Bloques 36090511045 36095502484 36095454987 32464100442 32464133005 32464163434 Valgrind Tiempo (s) 847,94 849,49 847,13 765,86 760,61 767,98 Mem. (kiB) 67956 67956 67956 68164 68164 68164 Slowdown 7,02 7,04 7,02 10,19 10,12 10,22 Bloques 31790795376 31790783660 31795085040 27064807604 27064795737 27064795727 DynamoRIO Tiempo (s) 199,54 200,21 199,81 144,59 144,66 144,46 Mem. (kiB) 156544 156548 156544 156752 156756 156752 Slowdown 1,65 1,65 1,65 1,92 1,92 1,92 Bloques 1655477351 1655477351 1650396069 3809286521 3805093463 3805095450 53 Secci´on D.3 D. Resultados del benchmark D.3. hmmer Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 20,33 20,34 20,34 4,47 4,47 4,52 Mem. (kiB) 20892 20912 20892 20912 20832 20780 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 202,42 202,28 202,58 70,54 70,68 70,61 Mem. (kiB) 63660 63624 63660 63696 63688 63684 Slowdown 9,71 9,88 9,90 15,24 15,24 15,15 Instrucc. 54297654013 54297720973 54297720440 16649566301 16649736886 16649643995 Valgrind Tiempo (s) 376,88 375,67 375,65 120,75 121,4 121,51 Mem. (kiB) 69892 70020 69896 69880 69960 69884 Slowdown 18,06 18,33 18,34 26,03 26,10 26,02 Instrucc. 54298001231 54297950064 54297734601 16649955696 16649786684 16649862949 DynamoRIO Tiempo (s) 72,47 72,53 72,51 51 50,91 51,07 Mem. (kiB) 153392 153260 153392 153252 153208 153248 Slowdown 3,48 3,55 3,54 10,98 10,93 10,92 Instrucc. 53478979044 49205120807 53353754824 15030755553 15131107542 15001172531 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 45,69 45,74 45,71 27,87 28,03 27,9 Mem. (kiB) 63064 63020 63020 63380 63348 63440 Slowdown 2,22 2,26 2,26 6,12 6,14 6,07 Bloques 2563838468 2563770093 2563756783 2167186708 2167136122 2167187211 Valgrind Tiempo (s) 160,47 159,82 159,71 63,5 63,65 63,7 Mem. (kiB) 66596 66608 66632 66548 66548 66640 Slowdown 7,71 7,82 7,81 13,75 13,79 13,70 Bloques 2398092822 2398029615 2398077405 1766363309 1766390390 1766397846 DynamoRIO Tiempo (s) 25,26 25,09 25,14 9,19 9,23 9,14 Mem. (kiB) 153312 153316 153304 153216 153204 153188 Slowdown 1,22 1,23 1,23 2,02 2,03 2,00 Bloques 2382277616 2382274878 2382282498 2144631367 2144645182 2144660538 54 D. Resultados del benchmark Secci´on D.4 D.4. libquantum Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 2,97 2,97 2,97 1,14 1,17 1,14 Mem. (kiB) 2712 2712 2712 2716 2716 2716 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 41,32 42,5 41,3 18,56 18,9 18,44 Mem. (kiB) 38964 38964 38964 39068 39068 39068 Slowdown 13,85 14,24 13,84 16,05 15,94 15,95 Instrucc. 9486298035 9486298035 9486298035 4172204824 4172204824 4172204824 Valgrind Tiempo (s) 52,24 52,29 52,56 25,82 25,8 25,21 Mem. (kiB) 59456 59456 59456 59460 59460 59460 Slowdown 17,46 17,48 17,57 22,16 21,60 21,64 Instrucc. 9486307171 9486307163 9486307159 4172213780 4172213780 4172213784 DynamoRIO Tiempo (s) 23,89 23,72 23,81 14,3 14,25 14,21 Mem. (kiB) 135136 135136 135136 135140 135140 135140 Slowdown 7,98 7,92 7,95 12,26 11,92 12,19 Instrucc. 9483103387 9483103387 9483103387 4169009342 4169009342 4169009342 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 45,69 45,74 45,71 27,87 28,03 27,9 Mem. (kiB) 63064 63020 63020 63380 63348 63440 Slowdown 2,22 2,26 2,26 6,12 6,14 6,07 Bloques 2563838468 2563770093 2563756783 2167186708 2167136122 2167187211 Valgrind Tiempo (s) 160,47 159,82 159,71 63,5 63,65 63,7 Mem. (kiB) 66596 66608 66632 66548 66548 66640 Slowdown 7,71 7,82 7,81 13,75 13,79 13,70 Bloques 2398092822 2398029615 2398077405 1766363309 1766390390 1766397846 DynamoRIO Tiempo (s) 25,26 25,09 25,14 9,19 9,23 9,14 Mem. (kiB) 153312 153316 153304 153216 153204 153188 Slowdown 1,22 1,23 1,23 2,02 2,03 2,00 Bloques 2382277616 2382274878 2382282498 2144631367 2144645182 2144660538 55 Secci´on D.5 D. Resultados del benchmark D.5. h264ref Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 175,56 175,51 175,52 52,2 52,23 52,23 Mem. (kiB) 22800 22800 22800 22924 22924 22924 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 1969,15 1976,8 1979,48 731,61 731,16 730,83 Mem. (kiB) 63640 63624 63640 66536 66368 66368 Slowdown 11,20 11,25 11,27 13,96 13,96 13,95 Instrucc. 468222306245 468222571081 468222609480 151093059135 151094273120 151092430740 Valgrind Tiempo (s) 2615,92 2613,49 2610,26 913,42 913,12 918,55 Mem. (kiB) 71628 71628 71628 71752 71752 71752 Slowdown 14,89 14,89 14,87 17,43 17,42 17,52 Instrucc. 468602886301 468602886398 468602886324 151469116709 151469116744 151469117073 DynamoRIO Tiempo (s) 1384,98 1379,37 1391,31 263,49 258,38 258,62 Mem. (kiB) 155224 155224 155224 155348 155348 155348 Slowdown 7,88 7,85 7,92 5,03 4,93 4,93 Instrucc. 468099926570 468100703832 468100510812 150796835198 150798200840 150798661928 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 399,97 399,48 397,53 142,96 142,73 143,14 Mem. (kiB) 62044 62076 62068 64324 64324 64324 Slowdown 2,50 2,51 2,49 3,02 3,02 3,03 Bloques 41664395913 41664395918 41664395932 10246885976 10246885990 10246885958 Valgrind Tiempo (s) 842,34 849,58 847,54 317,07 316,91 317,07 Mem. (kiB) 68296 68296 68296 68420 68420 68420 Slowdown 5,28 5,34 5,31 6,68 6,68 6,68 Bloques 31254620209 31254620206 31254620232 9761665724 9761665724 9761665716 DynamoRIO Tiempo (s) 321,68 315,51 319,49 59,37 59,33 58,61 Mem. (kiB) 155224 155224 155224 155348 155348 155348 Slowdown 2,01 1,98 2,00 1,25 1,25 1,24 Bloques 2590913223 2590913138 2590913183 760355482 760355502 760355525 56 D. Resultados del benchmark Secci´on D.6 D.6. ripemd Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 15,92 15,92 15,95 5,79 5,81 5,88 Mem. (kiB) 2012 2012 2012 2016 2016 2016 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 154,98 155,11 154,59 93,59 93,53 93,97 Mem. (kiB) 38608 38608 38608 38612 38612 38612 Slowdown 9,64 9,63 9,61 15,37 15,33 15,45 Instrucc. 41946768879 41946768879 41946768879 22330342413 22330342413 22330342413 Valgrind Tiempo (s) 393,34 392,59 388,46 209,88 210,94 211,39 Mem. (kiB) 58244 58244 58244 58248 58248 58248 Slowdown 24,43 24,35 24,10 34,42 34,50 34,73 Instrucc. 41947389200 41947389190 41947389190 22330962488 22330962492 22330962488 DynamoRIO Tiempo (s) 21,89 21,83 21,86 7,8 7,82 7,8 Mem. (kiB) 134604 134604 134604 134608 134608 134608 Slowdown 1,38 1,37 1,37 1,33 1,33 1,34 Instrucc. 41789987035 41789987035 41789987035 22173559980 22173559980 22173559980 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 19,73 19,75 19,8 10,14 10,15 11,12 Mem. (kiB) 38440 38440 38440 38444 38444 38444 Slowdown 1,33 1,39 1,39 1,92 1,92 2,10 Bloques 873132829 873132829 873132829 518737174 518737174 518737174 Valgrind Tiempo (s) 38,91 38,81 40,75 23,09 23,22 22,9 Mem. (kiB) 54912 54912 54912 54916 54916 54916 Slowdown 2,60 2,70 2,83 4,27 4,31 4,27 Bloques 810173395 810173395 810173396 446564696 446564696 446564697 DynamoRIO Tiempo (s) 14,85 14,85 15,83 5,72 5,61 5,68 Mem. (kiB) 134604 134604 134604 134608 134608 134608 Slowdown 0,99 1,03 1,10 1,06 1,06 1,07 Bloques 263197444 263197444 263197444 75864982 75864982 75864982 57 Secci´on D.13 D. Resultados del benchmark D.13. mlucas Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 35,05 34,87 35,03 14,6 14,65 14,62 Mem. (kiB) 10004 10004 10004 9340 9340 9340 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 307,11 309,24 307,2 199,01 199,2 199,01 Mem. (kiB) 49560 49560 49560 49648 49648 49648 Slowdown 8,78 8,88 8,78 13,64 13,61 13,62 Instrucc. 85256941803 85256941829 85256941799 53554796686 53554796681 53554796686 Valgrind Tiempo (s) ✗✗✗✗✗✗ Mem. (kiB) ✗✗✗✗✗✗ Slowdown ✗✗✗✗✗✗ Instrucc. ✗ ✗ ✗ ✗ ✗ ✗ DynamoRIO Tiempo (s) 45,12 45,07 45,02 22,5 22,48 22,58 Mem. (kiB) 142428 142428 142428 141764 141764 141764 Slowdown 1,29 1,29 1,29 1,54 1,53 1,54 Instrucc. 85256744807 85256744807 85256744807 53554599416 53554599416 53554599416 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 37,91 37,99 38 21,16 21,15 21,19 Mem. (kiB) 48244 48244 48244 48324 48324 48324 Slowdown 1,21 1,21 1,21 1,62 1,62 1,62 Bloques 1387505307 1387505303 1387505307 909951883 909951875 909951875 Valgrind Tiempo (s) ✗✗✗✗✗✗ Mem. (kiB) ✗✗✗✗✗✗ Slowdown ✗✗✗✗✗✗ Bloques ✗ ✗ ✗ ✗ ✗ ✗ DynamoRIO Tiempo (s) 32,48 32,48 32,48 14,39 14,42 14,4 Mem. (kiB) 142428 142428 142428 141764 141764 141764 Slowdown 1,03 1,03 1,03 1,09 1,09 1,09 Bloques 278148461 278148462 278148462 227746162 227746162 227746162 64 D. Resultados del benchmark Secci´on D.14 D.14. namd Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 14,95 15,06 15,04 7,12 7,1 7,11 Mem. (kiB) 19744 19744 19744 19208 19208 19208 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 155,66 156,39 155,38 87,18 87,14 87,21 Mem. (kiB) 66980 66992 66988 69096 69020 68628 Slowdown 10,49 10,47 10,41 12,37 12,34 12,40 Instrucc. 38252761764 38252801255 38252759804 19832746065 19832741407 19832743883 Valgrind Tiempo (s) 214,64 213,66 213,89 113,25 113,22 114,94 Mem. (kiB) 78660 78660 78660 74860 74860 74860 Slowdown 14,32 14,16 14,20 15,85 15,77 16,10 Instrucc. 38253097254 38253096968 38253096409 19833493146 19833491949 19833488839 DynamoRIO Tiempo (s) 34,43 34,43 34,51 19,43 19,44 19,44 Mem. (kiB) 152144 152144 152144 151608 151608 151608 Slowdown 2,30 2,29 2,29 2,72 2,71 2,73 Instrucc. 38250283476 38250318179 38250282771 19814092244 19814078844 19814080525 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 26,68 26,49 26,75 18,73 18,68 18,78 Mem. (kiB) 64552 63992 64540 66636 65696 65820 Slowdown 2,04 2,02 2,06 3,08 3,07 3,08 Bloques 971692620 971695374 971691998 549464758 549461424 549464261 Valgrind Tiempo (s) 65 65 65,15 44,12 44,24 44,12 Mem. (kiB) 75328 75328 75328 71528 71528 71528 Slowdown 4,75 4,73 4,79 6,81 6,84 6,83 Bloques 949810174 949810463 949810293 511693175 511691568 511692316 DynamoRIO Tiempo (s) 17,09 17,17 17,03 8,55 8,54 8,54 Mem. (kiB) 152144 152144 152144 151608 151608 151608 Slowdown 1,25 1,25 1,25 1,32 1,32 1,32 Bloques 540152965 540159401 540149109 344577457 344575920 344575061 65 Secci´on D.15 D. Resultados del benchmark D.15. linpack Sin optimizar Optimizado Ejec.1 Ejec.2 Ejec.3 Ejec.1 Ejec.2 Ejec.3 Ejecuci´on nativa Tiempo (s) 6,95 7,15 6,96 4,33 4,35 4,34 Mem. (kiB) 20692 20692 20692 20692 20692 20692 Instrumentaci´on a nivel de instrucciones Pin Tiempo (s) 66,54 66,07 66,28 22,04 22,02 22 Mem. (kiB) 57848 57448 57496 57496 57496 57496 Slowdown 9,59 9,22 9,52 5,13 5,09 5,09 Instrucc. 19647034175 19647034027 19647034197 6246035342 6246035106 6246035254 Valgrind Tiempo (s) 96,45 96,04 95,93 32,47 32,28 32,36 Mem. (kiB) 77956 77956 77956 77956 77956 77956 Slowdown 13,88 13,39 13,75 7,51 7,41 7,44 Instrucc. 19647045951 19647045432 19647045951 6246046953 6246046921 6246046849 DynamoRIO Tiempo (s) 19,83 19,8 19,8 8,6 8,6 8,6 Mem. (kiB) 153120 153120 153120 153120 153120 153120 Slowdown 2,85 2,76 2,84 1,99 1,97 1,98 Instrucc. 19646781826 19646781851 19646781804 6245779182 6245778866 6245779042 Instrumentaci´on a nivel de bloques b´asicos Pin Tiempo (s) 9,39 9,35 9,37 5,98 5,86 5,84 Mem. (kiB) 57400 57396 57400 57456 57456 57456 Slowdown 1,38 1,33 1,37 1,40 1,39 1,40 Bloques 615171369 615171418 615171345 330477783 330477785 330477792 Valgrind Tiempo (s) 28,86 28,26 28,85 18,05 18,03 18,14 Mem. (kiB) 73600 73600 73600 73600 73600 73600 Slowdown 4,15 3,95 4,15 4,11 4,15 4,22 Bloques 608174575 608174559 608174609 316652503 316652492 316652465 DynamoRIO Tiempo (s) 6,96 6,92 6,92 4,55 4,47 4,5 Mem. (kiB) 153120 153120 153120 153120 153120 153120 Slowdown 1,00 0,97 1,00 1,03 1,03 1,05 Bloques 609917486 609917509 609917517 325785898 325785905 325785922 66 D. Resultados del benchmark Secci´on D.16 D.16. Tiempo de ejecuci´on de los benchmarks En esta secci´on se va a hacer una comparaci´on entre el tiempo que hubiera durado la ejecuci´on del benchmark propio desarrollado para este PFC y el que hubiera durado SPEC 2006. Se comparar´an los resultados con un equipo similar [NEC08]. En el equipo similar, a la ejecuci´on de la parte de c´alculo entero (CINT) de SPEC le cuesta 13 horas y 59 minutos. En el benchmark propio la ejecuci´on de c´alculo entero sin instrumentar, dura 38 minutos y 40 segundos. Extrapolando el resultado de SPEC del equipo similar, con la media de instrumentaci´on en instrucciones (13.97x) por cada uno de los tres frameworks, la ejecuci´on de este hubiera durado 25 d´ıas. La duraci´on total del benchmark propio es de 32 horas y 20 minutos. 67 Ap´endice E C´odigo fuente aplicaciones usadas en el benchmark En el presente cap´ıtulo se muestra el c´odigo fuente de las herramientas creadas para instrumentar las aplicaciones en el benchmark. La primera herramienta es la que instrumenta por instrucciones y la segunda herramienta es la que instrumenta por bloques b´asicos. E.1. Instrumentaci´on por instrucciones E.1.1. Pin #include <stdio.h> #include "pin.H" #include <iostream> UINT64 icuenta = 0; VOID contar() { icuenta++; } VOID Instruction(INS ins, VOID *v) { INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)contar, IARG_END); } VOID Fini(INT32 code, VOID *v) { std::cerr << "Instrucciones: " << icuenta << endl; } int main(int argc, char * argv[]) 69 Secci´on E.1 E. C´odigo fuente aplicaciones usadas en el benchmark { PIN_Init(argc, argv); INS_AddInstrumentFunction(Instruction, 0); PIN_AddFiniFunction(Fini, 0); PIN_StartProgram(); return 0; } E.1.2. DynamoRIO #include "dr_api.h" #define DISPLAY_STRING(msg) dr_printf("%s\n", msg); #define DISPLAY_STRING_ERR(msg) dr_fprintf(STDERR,"%s\n", msg); #define NULL_TERMINATE(buf) buf[(sizeof(buf)/sizeof(buf[0])) - 1] = ’\0’ static uint64 icuenta=0; //Contador de instrucciones static void cuenta(void) { icuenta++; } //C´odigo a a~nadir static void event_exit(void); static dr_emit_flags_t event_basic_block(void *drcontext, void *tag, instrlist_t *bb, bool for_trace, bool translating); DR_EXPORT void dr_init(client_id_t id) { dr_register_exit_event(event_exit); dr_register_bb_event(event_basic_block); dr_log(NULL, LOG_ALL, 1, "Inicializando cliente ’icuenta’\n"); } static void event_exit(void) { char msg[512]; int len; len = dr_snprintf(msg, sizeof(msg)/sizeof(msg[0]), "Instrucciones: %llu \n", icuenta); DR_ASSERT(len > 0); NULL_TERMINATE(msg); DISPLAY_STRING_ERR(msg); } static dr_emit_flags_t 70 E. C´odigo fuente aplicaciones usadas en el benchmark Secci´on E.1 event_basic_block(void *drcontext, void *tag, instrlist_t *bb, bool for_trace, bool translating) { instr_t *instr; int i; // Se recorre el bloque b´asico y se instrumentan todas las instrucciones for (instr = instrlist_first(bb), num_instrs = 0; instr != NULL; instr = instr_get_next(instr)) { dr_insert_clean_call(drcontext, bb, instr), (void *)cuenta, false, 0 ); } return DR_EMIT_DEFAULT; } E.1.3. Valgrind #include "pub_tool_basics.h" #include "pub_tool_tooliface.h" #include "pub_tool_options.h" #include "pub_tool_libcbase.h" #include "pub_tool_libcassert.h" #include "pub_tool_machine.h" #include "pub_tool_libcprint.h" #include "pub_tool_debuginfo.h" static ULong icuenta = 0; static void contar(void) { icuenta++; } static void ic_post_clo_init(void) { } static IRSB* ic_instrument ( VgCallbackClosure* closure, IRSB* sbIn, VexGuestLayout* layout, VexGuestExtents* vge, IRType gWordTy, IRType hWordTy ) { IRDirty* di; Int i; IRSB* sbOut; sbOut = deepCopyIRSBExceptStmts(sbIn); 71 Secci´on E.1 E. C´odigo fuente aplicaciones usadas en el benchmark i = 0; while (i < sbIn->stmts_used && sbIn->stmts[i]->tag != Ist_IMark) { addStmtToIRSB( sbOut, sbIn->stmts[i] ); i++; } for (; i < sbIn->stmts_used; i++) { IRStmt* st = sbIn->stmts[i]; if (!st || st->tag == Ist_NoOp) continue; switch (st->tag) { case Ist_IMark: di = unsafeIRDirty_0_N( 0, "contar", VG_(fnptr_to_fnentry)( &contar ), mkIRExprVec_0() ); addStmtToIRSB( sbOut, IRStmt_Dirty(di) ); break; default: tl_assert(0); } } return sbOut; } static void ic_fini(Int exitcode) { VG_(umsg)("Instrucciones: %’llu\n", icuenta); VG_(umsg)("Exit code: %d\n", exitcode); } static void ic_pre_clo_init(void) { VG_(details_name) ("icuenta"); VG_(details_version) (NULL); VG_(details_description) ("Contador de instrucciones"); VG_(details_avg_translation_sizeB) ( 275 ); VG_(basic_tool_funcs) (ic_post_clo_init, ic_instrument, ic_fini); } 72 E. C´odigo fuente aplicaciones usadas en el benchmark Secci´on E.2 E.2. Instrumentaci´on por bloques b´asicos E.2.1. Pin #include <stdio.h> #include "pin.H" #include <iostream> static UINT64 bcuenta = 0; VOID contar() { bcuenta++; } VOID Trace(TRACE trace, VOID *v) { for (BBL bbl = TRACE_BblHead(trace); BBL_Valid(bbl); bbl = BBL_Next(bbl)) { BBL_InsertCall(bbl, IPOINT_BEFORE, (AFUNPTR)contar, IARG_END); } } VOID Fini(INT32 code, VOID *v) { std::cerr << "Bloques b´asicos: " << bcuenta << endl; } int main(int argc, char * argv[]) { PIN_Init(argc, argv); TRACE_AddInstrumentFunction(Trace, 0); PIN_AddFiniFunction(Fini, 0); PIN_StartProgram(); return 0; } E.2.2. DynamoRIO #include "dr_api.h" #define DISPLAY_STRING(msg) dr_printf("%s\n", msg); #define DISPLAY_STRING_ERR(msg) dr_fprintf(STDERR,"%s\n", msg); #define NULL_TERMINATE(buf) buf[(sizeof(buf)/sizeof(buf[0])) - 1] = ’\0’ static uint64 bcuenta=0; //Contador de bloques b´asicos 73