Repositorio Institucional de Documentos

Proyecto de Fin de Carrera Ingenier´ıa Inform´atica Curso 2013/2014 Caracterizaci´on de instrucciones en aplicaciones de cloud Alba Pedro Zapater Director: Dr. V´ıctor Vi˜ nals Y´ ufera Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Septiembre 2014 Dedicado a mis padres, por estar siempre ah´ı. Agradecimientos Sobre todo quiero agradecer a mi director, V´ıctor, todo lo que me ha ense˜nado, su paciencia, sus ´animos, su tiempo, su buen humor y toda la ayuda que me ha proporcionado durante este a˜no. Fue uno de mis mejores profesores en la carrera y sin duda ha sido el mejor director que podr´ıa haber tenido. Tambi´en le doy las gracias a Clemente Rodr´ıguez y a Pablo Ib´a˜nez por el tiempo que me han dedicado y por la gran ayuda que ha sido lo que me han ense˜nado. Adem´as, darle las gracias a Marta Ort´ın por estar siempre dispuesta a resolverme dudas y su rapidez para contestarme a los emails. Tambi´en a mis compa˜neros de carrera que me han sorprendido con grandes dosis de solidaridad y ayuda mutua frente a la competencia que mueve nuestro mundo . En especial a ´ Alvaro, Cintia, David y Juan, que han estado siempre para los buenos y los malos momentos y que sin su apoyo y amistad no hubiera sido posible llegar hasta aqu´ı. Para terminar, quiero agradecerles a mis padres por todo lo que me han dado, sin pedir nada a cambio, tan solo verme feliz. Y a todas las personas que siempre han cre´ıdo en mi, y de una forma u otra han hecho posible que yo est´e ahora escribiendo las ´ultimas lineas de mi proyecto de fin de carrera. v Resumen Las tendencias de mercado indican que el negocio de los procesadores para grandes centros de datos va a seguir creciendo, impulsado por la econom´ıa de la virtualizaci´on y la gran penetraci´on empresarial y social de las aplicaciones que residen en las nubes (cloud computing). Para dise˜nar un procesador de futuro adaptado a este mercado es necesario experimentar con una carga de trabajo apropiada. Por ello, en este proyecto nos hemos centrado en caracterizar el comportamiento de la cache de instrucciones para un sistema de cuatro procesadores, usando el conjunto de aplicaciones Cloudsuite 2.0 del laboratorio de investigaci´on Parsa, representativo del cloud computing. Hemos usado la plataforma de simulaci´on Simics, un simulador de sistema completo, trabajando con las cinco aplicaciones de Cloudsuite que est´an acompa˜nadas de checkpoints p´ublicos. Adem´as, se ha contribuido con un tutorial de Simics, acompa˜nado de material pr´actico, para facilitar y agilizar la fase de formaci´on de otros proyectos que tambi´en utilicen esta plataforma. Para realizar los experimentos deseados se han programado dos m´odulos de Simics de jerarqu´ıa de memoria basados en el m´odulo g-cache, que implementan dos algoritmos eficientes y espec´ıficos para registrar tasas de fallos y huellas de memoria. Un algoritmo obtiene resultados para m´ultiples caches en una sola simulaci´on y el otro est´a especializado en caches completamente asociativas. A partir de estos experimentos hemos analizado los benchmarks en cuanto a su tasa de fallos, en funci´on de su tama˜no y de su asociatividad, sugiriendo configuraciones pr´acticas de tama˜no y asociatividad para cada aplicaci´on. Tambi´en se ha examinado la huella de memoria de instrucciones a lo largo del tiempo, concluyendo que todas las aplicaciones tardan muchos segundos en entrar en r´egimen estacionario y que la aparici´on de varias fases complica la selecci´on de ventanas de simulaci´on. Y finalmente, se ha calculado el ancho de banda de instrucciones agregado para los cuatro procesadores simulados, concluyendo que la presi´on sobre el siguiente nivel puede ser bastante grande, y sugiriendo configuraciones de ese segundo nivel con capacidad para absorber las demandas del primero. Contenidos Agradecimientos V Resumen VII Contenidos IX Lista de Figuras XII Lista de Tablas XIV 1. Introducci´on 1 1.1. ContextodelProyecto ............................. 3 1.2. Objetivos .................................... 3 1.3. Organizaci´on de la Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Estado del Arte en simulaci´on y cargas de trabajo 5 2.1. Plataformas y estrategias de simulaci´on . . . . . . . . . . . . . . . . . . . 5 2.2. CargasdeTrabajo ............................... 6 3. CloudSuite 8 3.1. Caracter´ısticas de los Benchmarks . . . . . . . . . . . . . . . . . . . . . . 9 3.2. CloudsuiteenSimics.............................. 10 4. Metodolog´ıa 11 4.1. M´etricasUtilizadas............................... 11 4.2. Modelodelas3C................................ 12 4.2.1. Algoritmos de una sola pasada . . . . . . . . . . . . . . . . . . . . 15 4.3. M´oduloG-Cache ................................ 18 4.3.1. M´odulos en Simics . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3.2. G-cache ................................. 18 4.4. Experimentos.................................. 19 5. Resumen de Resultados 21 5.1. MpkiporCore ................................. 21 5.1.1. Streaming (Figura 5.1) . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1.2. Cassandra (Figura 5.2 ) . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1.3. Nutch (Figura 5.3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 ix Cap´ıtulo 1 Introducci´on Las tendencias de mercado indican que el negocio de los procesadores para grandes centros de datos va a seguir creciendo, impulsado por la econom´ıa de la virtualizaci´on y la gran penetraci´on empresarial y social de las aplicaciones que residen en las nubes (cloud computing). Para dise˜nar un procesador de futuro adaptado a este mercado es necesario experimentar con una carga de trabajo apropiada, pero en la actualidad apenas existen programas de prueba (benchmarks) de esta clase. Una excepci´on es la denominada CloudSuite 2.0, un conjunto de aplicaciones cliente/servidor seleccionadas recientemente por el laboratorio de investigaci´on Parsa de la EPFL en Suiza. Estas aplicaciones est´an pensadas para escalar en un centro de datos de forma horizontal (scale-out, es decir, con capacidad para aumentar el rendimiento a medida que se a˜naden mas computadores independientes) y se caracterizan por su paralelismo expl´ıcito y por manejar conjuntos de datos de tama˜no muy considerable. Las aplicaciones seleccionadas pretenden ser representativas del futuro del cloud computing: Data Analytics, Data Caching, Data Serving, Graph Analytics, Media Streaming, SW Testing, Web Search y Web Serving [EPF]. La experimentaci´on preliminar con estos programas de prueba, publicada en los congresos de arquitectura de computadores, ha revelado un uso intensivo y muy poco eficiente de la jerarqu´ıa de cache de instrucciones en chip [FAK+12]. Parece que no solo los conjuntos de datos son muy grandes, sino tambi´en el c´odigo que los manipula. Una memoria cache es una memoria RAM est´atica (SRAM), peque˜na y r´apida que contiene un subconjunto de las direcciones referenciadas por el procesador. Su funcionamiento es autom´atico, transparente al programador, y se basa en explotar la localidad temporal y espacial del acceso a memoria durante la ejecuci´on de los programas. En los chips actuales de altas prestaciones las memorias cache ocupan una parte sustancial del 1 Cap´ıtulo 1. Introducci´on 2 silicio, ya que la velocidad en la ejecuci´on de los programas depende en gran medida del rendimiento de las caches. Las memorias cache dentro del chip se organizan como una jerarqu´ıa multinivel, ver figura 1.1. El primer nivel de memoria cache est´a separado en datos e instrucciones para cada procesador; el resto de niveles, hasta dos m´as, suelen contener de forma mezclada datos e instrucciones. Un buen dise˜no de la jerarqu´ıa de memoria cache permite acceder poco a la memoria principal RAM din´amica (DRAM) situada fuera del chip, contribuyendo de forma cr´ıtica a la ejecuci´on eficiente de los programas. Figura 1.1: Ejemplo de chip multiprocesador contempor´aneo, con cuatro procesadores y tres niveles de memoria cache en chip (SRAM): los dos primeros privados de cada procesador, y el tercero compartido En este proyecto nos planteamos una caracterizaci´on por simulaci´on del comportamiento de las instrucciones en CloudSuite 2.0. Seguiremos una metodolog´ıa de experimentaci´on basada en Simics, un hipervisor de tipo 2 con capacidad de emulaci´on de sistema completo: m´aquinas cliente y servidor con sus perif´ericos, sistemas operativos hu´esped (Oracle Solaris 11) y procesadores SPARC v9. Simics no est´a pensado para desplegar m´aquinas virtuales orientadas a la consolidaci´on de servidores, sino al desarrollo y prueba de nuevos sistemas hardware y software. Esta orientaci´on permite en nuestro caso configurar un sistema multiprocesador, capturar la secuencia de direcciones de instrucciones e inyectarla a un simulador de memoria cache. Si bien este tipo de simulaci´on de sistema completo (aplicaci´on y sistema operativo) es realmente lenta, la precisi´on de las conclusiones experimentales es muy elevada. [Los resultados han sido...] Cap´ıtulo 1. Introducci´on 3 1.1. Contexto del Proyecto Este Proyecto Fin de Carrera se ha realizado con el soporte del grupo de investigaci´on en Arquitectura de Computadores de la Universidad de Zaragoza (gaZ) y ha sido financiado en parte por el proyecto TIN2010-21291-C02-01 (Gobierno de Espa˜na y Uni´on Europea) y por la dotaci´on anual recibida como grupo consolidado de investigaci´on en Arag´on (ref. T48). Adem´as, durante el curso 2013/2014 he disfrutado de una Beca de Colaboraci´on del Ministerio de Educaci´on destinada a la iniciaci´on a la investigaci´on. 1.2. Objetivos El objetivo de este Proyecto Fin de Carrera es analizar el comportamiento de las instrucciones en CloudSuite 2.0. Para ello se han realizado las siguientes tareas: 1. Instalaci´on y despliegue en cluster de los checkpoints necesarios para la simulaci´on con Simics. Un checkpoint es un registro del estado de los procesadores, memorias y dispositivos de E/S en un instante dado. 2. Programaci´on de un m´odulo muy ligero de simulaci´on de cache de instrucciones, que reduce la sobrecarga de las herramientas convencionales de simulaci´on de jerarqu´ıa de memoria (p.e. Multifacet GEMS Simulator de la U. de Wisconsin) 3. An´alisis de tasas de fallos y de huella de memoria de instrucciones a lo largo de tiempos de ejecuci´on significativos. 4. Conclusiones sobre comportamiento temporal a trav´es de una simulaci´on muestreada y sobre la efectividad de una jerarqu´ıa multinivel de instrucciones. Tras llevar a cabo estas tareas se han alcanzado todos los objetivos inicialmente planteados. El valor a˜nadido en este proyecto se concentra principalmente en los cap´ıtulos de resultados y conclusiones, d´onde se analizan los resultados obtenidos por simulaci´on. 1.3. Organizaci´on de la Memoria El resto del presente documento est´a organizado del siguiente modo: en el cap´ıtulo 2 se introduce el estado del arte en simulaci´on y cargas de trabajo; en el cap´ıtulo 3 se explica con mayor detalle la suite Cloudsuite; el cap´ıtulo 4 explica la metodolog´ıa utilizada para llevar a cabo los experimentos; en el cap´ıtulo 5 se presenta un resumen de los resultados Cap´ıtulo 1. Introducci´on 4 del proyecto y en el cap´ıtulo 6 se recogen las conclusiones y las posibles lineas abiertas. Se incluyen como anexos: A. Gesti´on del proyecto. Incluye la planificaci´on del tiempo durante el proyecto y el esfuerzo invertido en el mismo. B. Productividad en Simics. Se adjunta un tutorial de Simics que sirva de documentaci´on para futuros proyectos. C. M´odulo G-cache. Se amplia la informaci´on sobre el m´odulo de g-cache y los m´odulos programados para el proyecto. D. Simulaciones Cloudsuite. Se presenta d´onde y c´omo se han llevado a acabo las simulaciones de la CloudSuite. Cap´ıtulo 2 Estado del Arte en simulaci´on y cargas de trabajo La simulaci´on es una herramienta fundamental para dise˜nar nuevo hardware o mejorar el rendimiento de los programas. En este cap´ıtulo describimos brevemente la plataforma Simics y el papel de los programas de prueba en la simulaci´on de nuevas jerarqu´ıas de memoria. 2.1. Plataformas y estrategias de simulaci´on Simics de la empresa Virtutech (simplemente Simics a partir de ahora) es un simulador de sistema completo que podemos configurar para modelar multiprocesadores, sistemas empotrados, routers de telecomunicaciones, clusters o redes de esos elementos [MCE+02]. Es capaz de ejecutar sistemas operativos sin necesidad de que sean adaptados y simular aplicaciones realistas ofreciendo resultados precisos. Se trata de un hipervisor comercial de tipo 2, puede ejecutarse sobre m´ultiples procesadores y sistemas operativos, y el c´odigo no es libre. En la comunidad de experimentaci´on en arquitectura de computadores, Simics suele utilizarse conjuntamente con el entorno GEMS (General Execution-Driven Multiprocessor Simulator) [MSB+05], que fue creado en la Universidad de Wisconsin y proporciona m´odulos para el estudio de prestaciones en sistemas multiprocesador de memoria compartida con jerarqu´ıas complejas y coherentes de memorias cache. El componente principal de GEMS se llama Ruby, que simula las memorias cache, el protocolo de coherencia y la red de interconexi´on. Simics act´ua como un simulador funcional, es decir, simplemente se ocupa de ejecutar las instrucciones, y se comunica con el m´odulo Ruby de GEMS, que se encarga de gestionar los accesos a memoria, temporiz´andolos de forma adecuada. 5 Cap´ıtulo 2. Estado del arte 6 Un problema muy importante en la simulaci´on de multiprocesadores es el bajo rendimiento del simulador, y esto es especialmente cierto en Simics, que como ya hemos dicho es una m´aquina virtual de sistema completo. Seg´un el detalle temporal (precisi´on) de la simulaci´on, las aplicaciones se ejecutan entre 100 y 1000 veces m´as lentas que en la m´aquina real. En nuestro caso estamos interesados en muy largas simulaciones de fallos/aciertos, s´olo para la cache de instrucciones y no nos importa el detalle temporal. Por ello hemos escogido una soluci´on de menos sobrecarga, aunque conllevar´a la necesidad de un mayor esfuerzo de programaci´on. La soluci´on escogida ha sido el m´odulo g-cache (que explicaremos en el apartado 4.3), cuyo c´odigo fuente acompa˜na a la distribuci´on est´andar de Simics. 2.2. Cargas de Trabajo Se llama benchmark al programa de prueba que sirve para evaluar el rendimiento de un computador completo o de uno de sus subsistemas. [Bon07]. Un conjunto de benchmarks se denomina suite. Hist´oricamente los programas de prueba han evolucionado en complejidad, desde los primeros programas sint´eticos, pasando por peque˜nas rutinas intensivas en c´alculo o memoria, hasta los programas reales de la actualidad, representativos de un campo inform´atico determinado. La selecci´on de la carga de trabajo tiene una gran importancia, puesto que queremos obtener conclusiones que sirvan para el dise˜no de los computadores del futuro. Veamos algunas suites actuales: PARSEC 2.1: suite compilada por la universidad de Princeton (Princeton Application Repository for Shared-Memory Computers, 2009-10). Est´a compuesta por trece aplicaciones paralelas de memoria compartida (multithreaded applications). Ofrece aplicaciones paralelas t´ıpicas, por ejemplo de High-Performance Computing (HPC), pero tambi´en incluye otro tipo de aplicaciones paralelas emergentes (p.e. escritorio y servicio WEB). Recoge distintas dominios de aplicaci´on, como visi´on por computador, codificaci´on de v´ıdeo, an´alisis financiero, visualizaci´on de experimentos f´ısicos y proceso de imagenes.[BKSL08] SPEC CPU2006: suite compilada por la cooperativa SPEC en 2006 (Standard Performance Evaluation Corporation). Est´a pensada para medir el rendimiento del procesador, la jerarqu´ıa de memoria o el compilador, puesto que no tiene apenas operaciones de entrada/salida. Contiene dos suites de benchmarks, una intensiva en c´alculo entero (12 programas no paralelos) y otra en coma flotante (19 programas no paralelos). [CPU06] Cap´ıtulo 2. Estado del arte 7 SPECweb 2009: tambi´en de la cooperativa SPEC, busca evaluar el rendimiento de servidores WEB. Sus cargas de trabajo est´an pensadas para multiprocesadores de memoria compartida e incluyen aplicaciones de banca, comercio electr´onico o soporte Web.[web09] TPC-C: aplicaci´on patrocinada por la cooperativa Transaction Processing Council desde 1992. En la actualidad est´a en su versi´on cinco, y simula un entorno completo de usuarios realizando transacciones en directo (online) hacia una base de datos. Aunque no se limita a ninguna actividad en particular modela una empresa que debe gestionar, vender y/o distribuir un producto o servicio.[TC] Los anteriores benchmarks son un buen resumen de aplicaciones que se est´an ejecutando en los computadores actuales. Sin embargo, unos nuevo tipo de aplicaci´on est´a emergiendo con fuerza en los ´ultimos a˜nos: los servicios de la nube (cloud computing). Esta plataforma est´a dominando el suministro de servicios escalables online. Estos servicios se caracterizan por unos enormes working-sets, un alto grado de paralelismo y restricciones de tiempo real no estricto. Todo esto hace que estas aplicaciones denominadas scale-out tengan un comportamiento distinto a las aplicaciones tradicionales ya conocidas y que se recogen en los benchmarks anteriores. Por ello, para estimular la investigaci´on en el ´area de los centros de datos y la nube y ya que apenas existen benchmarks de esta clase, el laboratorio de investigaci´on Parsa de la EPFL en Suiza ha creado CloudSuite, un benchmark basado en servicios online del mundo real [FAK+12]. Esta es la carga de trabajo que hemos seleccionado para nuestro proyecto, por lo que explicamos sus caracter´ısticas con m´as detalle en el cap´ıtulo siguiente. Cap´ıtulo 3 CloudSuite Como ya hemos introducido en el cap´ıtulo anterior, la carga de trabajo que usamos en este trabajo es Cloudsuite 2.0, un conjunto de aplicaciones cliente/servidor del grupo de investigaci´on Parsa de la EPFL en Suiza. Estas aplicaciones est´an pensadas para escalar en un centro de datos de forma horizontal ( scale-out: a m´as servidores f´ısicos, m´as rendimiento) y se caracterizan por su paralelismo expl´ıcito y por manejar conjuntos de datos de tama˜no muy considerable. Aunque en su web podemos encontrar disponibles 8 aplicaciones para ejecutar en nativo [EPF], nosotros hemos trabajado solo con 5, aquellas acompa˜nadas de checkpoints p´ublicos para la simulaci´on en Simics. En la tabla 3.1 podemos ver las aplicaciones con una breve descripci´on: Aplicaci´on Descripci´on Data Analytics Esta aplicaci´on se basa en el paradigma map-reduce, que ha emergido como una aproximaci´on muy popular para los an´alisis de datos a gran escala. Se lanzan peticiones al cluster de procesadores que se simulan, que en primer lugar filtran y transforman la informaci´on (map) y despu´es unen los resultados (reduce). Data Serving Aplicaci´on de almacenamiento y servicio de datos basada en NoSQL (Not only SQL). Ha sido dise˜nada expl´ıcitamente para soportar aplicaciones web como Facebook, Google Earth y Google Finance, proporcionando almacenamiento escalable, con capacidad de adaptar r´apidamente el esquema de almacenamiento. Media Streaming Los servicios en streaming, tipo Youtube, usan enormes clusters de servidores que gradualmente empaquetan y transmiten ficheros multimedia cuyo tama˜no puede ir desde los megabytes hasta los gigabytes. Web Frontend Las aplicaciones que dan servicio al alojamiento de p´aginas web se caracterizan por su gran tolerancia a fallos y su escalabilidad din´amica. Web Search Aplicaci´on basada en un motor de b´usqueda, similar a Google, capaz de indexar terabytes de datos recogidos din´amicamente de fuentes online. Tabla 3.1: Aplicaciones CloudSuite 2.0 simuladas. 8 Cap´ıtulo 3. CloudSuite 9 3.1. Caracter´ısticas de los Benchmarks Todas estas aplicaciones tienen unas caracter´ısticas similares [FAK+12]: Operan con grandes conjuntos de datos que se reparten entre un gran n´umero de m´aquinas, t´ıpicamente en fragmentos residentes en las memorias principales de los servidores. Sirven grandes cantidades de peticiones completamente independientes que no comparten ning´un estado. Est´an dise˜nadas espec´ıficamente para una infraestructura de servidores t´ıpica de la nube, donde las conexiones y las m´aquinas no son del todo fiables. Usan conectividad entre m´aquinas solo para las tareas m´as importantes de coordinaci´on y administraci´on. En algunas aplicaciones de esta suite llegamos a simular hasta tres computadores completos conectados por red, como es el caso de Web Frontend, cuyo esquema est´a representado en la figura 3.1. Este benchmark consiste en tres componentes principales: el servidor web, la base de datos y un cliente, cada una es ejecutada en una m´aquina distinta y emulan los accesos del mundo real al servidor web. Todo este sistema simulado nos permite estudiar las instrucciones del servicio cr´ıtico: el servidor web que se ejecuta en una m´aquina multiprocesador, de cuatro procesadores en nuestro caso. Figura 3.1: Esquema Aplicaci´on Web Frontend. Cap´ıtulo 3. CloudSuite 10 3.2. Cloudsuite en Simics Como ya se ha apuntado, ´unicamente se disponen de forma p´ublica los checkpoints para Simics de las cinco aplicaciones de la tabla 3.1. Los checkpoints permiten empezar una simulaci´on en un punto de inter´es, sin necesidad de configurar todo de nuevo, arrancar la m´aquina, y saltar la fase de inicializaci´on. Un checkpoint almacena el contenido de los registros de los procesadores, de las MMUs, la imagen de la memoria principal, los contenidos de los discos y el estado de los perif´ericos (consola, conexiones de red, etc.). En nuestro caso un checkpoint consiste en varios ficheros que contienen la configuraci´on del sistema simulado (m´aquinas para los clientes, para la base de datos y para el servidor bajo an´alisis) en un estado estacionario de la ejecuci´on, saltando la fase de inicializaci´on del sistema que queremos analizar. Para desplegar los checkpoints en ATPS, nuestro cluster de experimentaci´on, ha sido necesario configurar las rutas que referencian a los diferentes ficheros de un checkpoint: datos de entrada de la aplicaci´on simulada, configuraci´on hardware de las m´aquinas, e imagen del estado hardware en el punto de inicio de la simulaci´on. Cap´ıtulo 4. Metodolog´ıa 17 Figura 4.7: Aciertos y fallos para una cache LRU con asociatividad 3 En la primera figura, la 4.6, se representa una cache de un solo bloque, y de un solo conjunto, as´ı que si inmediatamente no se referencia al mismo bloque, se produce un fallo. En el caso de que se produzca un acierto este siempre es a distancia 1, ya que la pila LRU del conjunto solo tiene un elemento. En el vector de la izquierda de la figura 4.8 podemos ver el resumen de los aciertos y fallos totales de la secuencia de referencias utilizada (ABCCDBAADA). Figura 4.8: Vector de aciertos acumulados para S=1 y S=3 Sin embargo la secuencia de estados en la figura 4.7 se complica, ya que corresponde a una cache de un solo conjunto, pero de asociatividad 3. Ahora aparecen aciertos a distancias 1, 2 y 3. Aqu´ı se aprecia lo que explic´abamos anteriormente, por ejemplo, el ´ultimo acierto se da a distancia 2 porque entre la ´ultima referencia al bloque A y la anterior referencia solo se ha referenciado al bloque D. O en el pen´ultimo acierto, que se da a distancia 3 porque entre la ´ultima vez que se referencia a D y la anterior s´olo se han Cap´ıtulo 4. Metodolog´ıa 18 referenciado dos bloques: el A y el B. En el vector de la derecha de la figura 4.8 recogemos el n´umero total de fallos y de aciertos, estos ´ultimos clasificados por distancias. Gracias a las figuras y a las tablas ahora podemos ver mejor porque los aciertos de asociatividad 1 de una cache est´an incluidos en los aciertos de una cache con el mismo n´umero de conjuntos pero mayor asociatividad. Los aciertos a distancia 1 del vector S=3 en 4.8 son los correspondientes a los aciertos de la cache de asociatividad 1 de la figura 4.6 para esa secuencia de referencias a bloques.Y llegamos a la conclusi´on de que no es necesario representar una cache de asociatividad 2 con 2 bloques, y un solo conjunto, para saber su n´umero de aciertos ya que la cache de asociatividad 2 incluir´a los de la 1 (2 aciertos) m´as los de distancia 2 del vector S=3 en 4.7 de la cache de asociatividad 3. Es decir, para la cache de un conjunto y asociatividad 2 el n´umero de aciertos ser´a 3, y por lo tanto el n´umero de fallos 7, ya que en total hay 10 referencias a bloques. Asumiendo reemplazo LRU, ¿c´omo concretar estas ideas en un algoritmo?. Una forma es gestionar un vector de aciertos que contabiliza cuantos aciertos se dan en cada distancia. El algoritmo en detalle puede consultarse en el anexo C.2.1. Con este algoritmo podemos obtener, por ejemplo, a partir de la simulaci´on de una cache de 16KB de asociatividad 4, los aciertos (y por lo tanto tambi´en los fallos) de una cache 8KB con asociatividad 2, y de una cache de 4KB con asociatividad 1. 4.3. M´odulo G-Cache 4.3.1. M´odulos en Simics Un m´odulo en Simics es un c´odigo ejecutable que se carga din´amicamente en la m´aquina virtual. Para tener un uso pr´actico debe interactuar con Simics, con otros m´odulos o con el usuario. Simics proporciona una API (application programming interface) para que los m´odulos puedan utilizar diversas funciones. La API soporta los conceptos de clase, objeto, interfaz y evento. Los m´odulos pueden programarse en DML (Device Modeling Language), Python o C/C++. En este proyecto hemos trabajado modificando un m´odulo ya definido por Simics, gcache, que se explica a continuaci´on. 4.3.2. G-cache Simics es una m´aquina virtual con capacidad de ejecuci´on funcional de sistema completo, tanto de aplicaciones como de sistema operativo. Por tanto no modela las cuestiones de Cap´ıtulo 4. Metodolog´ıa 19 implementaci´on transparentes al lenguaje m´aquina, como la jerarqu´ıa de caches. Sin embargo, incorpora a modo de ejemplo el m´odulo g-cache que permite modelar una jerarqu´ıa multinivel de caches para multiprocesador. G-cache trata las transacciones de memoria de forma simple: todas las operaciones necesarias (copy-back de bloques sucios de datos, fetch de instrucciones, etc.) se ejecutan en orden de programa y una sola vez. La cache devuelve la suma de los ciclos de parada para cada operaci´on. Hemos modificado este modulo para programar de forma eficiente nuestras caches de instrucciones. Las dos versiones programadas tienen la siguiente funcionalidad: Algoritmo para m´ultiples caches (algoritmo MC): Se aplica la idea del apartado 4.2.1 para recoger en una simulaci´on ´unica los fallos de varias asociatividades y tama˜nos. Algoritmo para caches completamente asociativas (algoritmo CCA): Ya que las caches completamente asociativas solo tienen un conjunto, los algoritmos tradicionales de reemplazo LRU es muy costoso de simular para caches grandes, por tener que recorrer toda la lista LRU una o varias veces cada vez que se produce un fallo. La mejora original que proponemos es utilizar una cache de correspondencia directa auxiliar, que permite capturar una gran parte de los aciertos, evitando tener que buscar el bloque en la cache simulada. Hemos medido una mejora media en velocidad de un 90,52 % gracias a esta mejora. En el Anexo C se describen en detalle los dos algoritmos. 4.4. Experimentos En este trabajo hemos lanzado 6 experimentos con el algoritmo MC, y 5 experimentos con el algoritmo CCA, por cada aplicaci´on. La gr´afica 4.9 muestra los seis primeros experimentos y a qu´e cache (asociatividad y tama˜no) corresponden los resultados obtenidos, cuatro caches distintas por cada experimento. As´ı que con seis ejecuciones hemos obtenido los datos de 24 caches distintas, suponiendo una muy importante mejora. El algoritmo CCA se ha ejecutado para las caches de 16KB, 32KB y 64KB, para las que ya disponemos resultados desde asociatividad 1 a 8, pudiendo as´ı completar el modelo de las 3Cs. El cuarto experimento con este algoritmo corresponde a la simulaci´on de una cache de 2048KB. Esta cache que al ser lo suficientemente grande nos permite contabilizar los fallos obligatorios. Cap´ıtulo 4. Metodolog´ıa 20 Figura 4.9: Experimentos lanzados con algoritmo MC. Cada uno de los experimentos anteriores supone 10 segundos (tiempo en m´aquina real) de cada aplicaci´on, recogiendo muestras cada 100ms, es decir se obtienen 100 muestras por cada experimento y aplicaci´on. Antes de cada muestra las caches y sus estad´ısticas se inicializan. Por ´ultimo, el quinto experimento con el algoritmo CCA corresponde a la obtenci´on de los fallos obligatorios a lo largo de los 10 segundos (tiempo en m´aquina real) sin inicializar las caches ni las estad´ısticas y recogiendo los datos cada 100ms . El experimento se ha lanzado con un tama˜no de 2048KB para todas las aplicaciones excepto para Classification y Cloudstone que ha sido de 4096KB y 8192KB,respectivamente. Cap´ıtulo 5 Resumen de Resultados En este capitulo se recogen los resultados de los experimentos realizados, siguiendo las m´etricas presentadas en el apartado 4.1. Los resultados se estructuran en tres apartados; el primero muestra las tasas de fallos promediadas para todos los cores en toda la duraci´on de las aplicaciones; el segundo presenta la huella de memoria, estudiando su evoluci´on temporal en intervalos de 100ms; el tercer apartado presenta el ancho de banda agregado que debe suministrar el siguiente nivel, tambi´en analizando intervalos de 100 ms. Al final de cada apartado se ofrecen unas conclusiones de comportamiento y, en su caso, de dise˜no. 5.1. Mpki por Core Las gr´aficas presentadas en esta secci´on (5.1 - 5.5) resumen el comportamiento de las caches de instrucciones en cuanto a su tasa de fallos expresada en mpki, en funci´on de su tama˜no y de su asociatividad, para un tama˜no de bloque de 64 bytes. Para cada tama˜no de cache y para cada core hemos calculado la media aritm´etica de todas las muestras temporales1. En estas gr´aficas observaremos la importancia relativa del tama˜no y la asociatividad en la tasa de fallos, as´ı como la posible diferencia de comportamiento entre cores. 1Estos datos, junto con los del siguiente apartado, permiten descomponer los fallos seg´un el modelo de las 3Cs. No se ha hecho as´ı porque la anomal´ıa de asociatividad aparece, y entonces la representaci´on pierde utilidad. 21 Cap´ıtulo 5. Resumen de Resultados 22 5.1.1. Streaming (Figura 5.1) Destaca la diferencia de comportamiento entre cores: el core 3 es menos sensible a la asociatividad y al tama˜no (rango total 35-20 mpki), mientras que los cores 1,2 y 4 tienen comportamientos casi id´enticos, presentando unas tasas altas para 16KB (45-50 mpki) y mucha sensibilidad a la asociatividad para 64 KB. En los dos grupos de cores aparece la anomal´ıa de asociatividad. Para el core 3, en 64 KB solo la correspondencia directa es peor que completamente asociativo. Para el resto de cores ocurre algo muy parecido, pero para 32 KB. Resaltemos esto: la mejor elecci´on de asociatividad se invierte por completo, seg´un el tama˜no y el core considerados, lo cual no es nada bueno desde el punto de vista de dise˜no. Escoger una asociatividad 4-8 para todos los cores y tama˜nos, podr´ıa ser un buen compromiso de dise˜no. En definitiva, estamos frente a una aplicaci´on cuya b´usqueda de instrucciones puede convertirse en el cuello de botella del procesador si el tama˜no de cache es insuficiente o la asociatividad no es la apropiada. Figura 5.1: Streaming: mpki de la cache de instrucciones en cada core vs. tama˜no y asociatividad. Tama˜no de bloque 64B. 5.1.2. Cassandra (Figura 5.2 ) En esta aplicaci´on basta con descartar dise˜nos de correspondencia directa para obtener un muy buen rendimiento (4-5 mpki), independientemente del tama˜no y del core considerado. En cuanto a comportamiento de cache, parece que esta aplicaci´on paralela Cap´ıtulo 5. Resumen de Resultados 23 usa el mismo c´odigo en los cuatro procesadores. No se observa ninguna anomal´ıa de asociatividad, y la sensibilidad de los fallos al tama˜no de cache es reducida. Figura 5.2: Cassandra: mpki de la cache de instrucciones en cada core vs. tama˜no y asociatividad. Tama˜no de bloque 64B. 5.1.3. Nutch (Figura 5.3) Buen aprovechamiento de la capacidad y de la asociatividad: al aumentar tama˜no de 16KB a 64 KB, nos movemos desde la franja 20-10 mpki a 5-1 mpki, para asociatividades entre 1 y CA, respectivamente. Todos los cores parecen ejecutar el mismo c´odigo. 5.1.4. Classification (Figura 5.4) Podemos apreciar una gran diferencia entre asociatividad 1 y el resto. Independientemente del tama˜no,a partir de asociatividad 4-8, la tasa de fallos es inapreciable.Todos los cores parecen ejecutar el mismo c´odigo. 5.1.5. Cloudstone (Figura 5.5) El core 2 presenta una tasa de fallos (20-15 mpki) superior al resto (15-20 mpki), que se comportan de forma similar. Independientemente de la asociatividad, todos los cores experimentan el mismo descenso de mpki al doblar el tama˜no, un 21 % aproximadamente. A partir de asociatividad 4 apenas se aprecia mejora. Cap´ıtulo 5. Resumen de Resultados 24 Figura 5.3: Nutch: mpki de la cache de instrucciones en cada core vs. tama˜no y asociatividad. Tama˜no de bloque 64B. Figura 5.4: Classification: mpki de la cache de instrucciones en cada core vs. tama˜no y asociatividad. Tama˜no de bloque 64B. Cap´ıtulo 5. Resumen de Resultados 25 5.1.6. Conclusiones En base al estudio de las tasas medias de fallos por core, podemos extraer la siguientes conclusiones para el conjunto de todas las aplicaciones: Dos aplicaciones, Streaming y Cloudstone, no facilitan un dise˜no homog´eneo de la cache de instrucciones, ya que un core se desmarca del comportamiento de los otros tres. Escoger descuidadamente una configuraci´on de tama˜no y asociatividad puede resultar en unas tasas de fallos excesivas para unos y en un dise˜no sobredimensionado para otros. La existencia de anomal´ıas de asociatividad complica a´un mas la decisi´on de dise˜no. El rango de tasa de fallos observado es grande, destacando Streaming, que puede llegar a los 50 mpki. Le sigue Cloudstone, presentando entre 20 y 10 mpki. A continuaci´on, Nutch puede llegar a fallar bastante con peque˜nos tama˜nos (2010 mpki), pero con suficiente capacidad y asociatividad apenas falla (5-1 mpki). Finalmente, Cassandra y Classification, con una asociatividad suficiente, apenas fallan (<4 mpki). A la vista de los experimentos realizados podemos derivar algunas pautas de dise˜no para la cache de instrucciones de primer nivel con tama˜no de bloque 64 Bytes: - Si el tiempo y la energ´ıa de acceso no quedan comprometidas2, el dise˜no mas razonable es un tama˜no de 64 KB con asociatividad 4-8. •La opci´on de 32 KB es mas barata y r´apida. Salvo para Streaming ser´ıa muy apropiada. Una asociatividad 4 ser´ıa suficiente. •En caso de optar por 16 KB, la mitad de las aplicaciones funcionar´ıan bien por debajo de su potencial (Streaming, Nutch y Cloudstone). En esta caso, una asociatividad 4 tambi´en ser´ıa suficiente. 5.2. Huella de Memoria La huella de memoria es el n´umero total de bloques diferentes que un programa visita cuando se ejecuta. En nuestro caso nos interesa la huella de instrucciones, medida con una granularidad de 64 bytes, el tama˜no de bloque de cache que vamos a utilizar en 2Tanto el tiempo como la energ´ıa de un acceso de cache crecen m´as o menos linealmente con el tama˜no y de forma marginal con la asociatividad. Un dise˜no comercial no s´olo considera la tasa de fallos, sino el tiempo medio de acceso y el posible impacto sobre el tiempo de acceso del procesador [HP06] Cap´ıtulo 5. Resumen de Resultados 26 Figura 5.5: Cloudstone: mpki de la cache de instrucciones en cada core vs. tama˜no y asociatividad. Tama˜no de bloque 64B. todo este cap´ıtulo. Por tanto la huella de instrucciones es equivalente al tama˜no efectivo del c´odigo que se ha ejecutado en cada aplicaci´on. Para observar la evoluci´on temporal, hemos medido en primer lugar la huella de recarga en intervalos de 100 ms. Para cada core, la huella de recarga mide el n´umero de bloques diferentes que se visitan en cada intervalo. Esta medida se ha realizado mediante una cache completamente asociativa lo suficientemente grande para que no haya fallos de conflicto ni de capacidad, solo fallos obligatorios, que son los correspondientes al n´umero de bloques diferentes referenciados. Al principio de cada intervalo se vac´ıa la cache. Puesto que cada cache tiene su propia din´amica, hemos optado por representar ´unicamente la mayor de las cuatro huellas de recarga3. En las figuras tambi´en se presentan los resultados para cada core de la huella acumulada, que se ha calculado sin perder memoria cada 100 ms. Por tanto la huella acumulada al final de los 10 s representa el n´umero total de bloques de instrucciones visitado por cada core. Hay que prestar especial atenci´on en las figuras ya que no todas est´an escaladas igual y no todos los ejes verticales comienzan en el valor cero. En este apartado nos interesa verificar si las aplicaciones est´an en r´egimen estacionario, como afirman los creadores de los checkpoints. En tal caso, podr´ıamos buscar fases de ejecuci´on que nos permitan simular en una ventana de tiempo mas reducida. Por otra 3En el cap´ıtulo de conclusiones y l´ıneas abiertas (Cap´ıtulo 6) se comenta un interesante trabajo futuro relacionado con las posibles similitudes o diferencias entre las huellas de recarga de los cuatro procesadores. Cap´ıtulo 5. Resumen de Resultados 33 Figura 5.13: Ancho de banda por asociatividad y tama˜no en Streaming. Cap´ıtulo 5. Resumen de Resultados 34 Figura 5.14: Ancho de banda por asociatividad y tama˜no en Cassandra. Cap´ıtulo 5. Resumen de Resultados 35 5.3.3. Nutch (Figura 5.15) Destaca la gran variabilidad temporal del ancho de banda, sobre todo para 16KB y 32KB. Al aumentar el tama˜no de la cache el rango del ancho de banda se reduce apreciablemente, aunque el escalado es variable (e.g. en media, el cociente entre BWin para S=1 y para CA, es del orden de 2, 1,7 y 6, para las caches de 16, 32 y 64 KB, respectivamente). La influencia del tama˜no de la cache sobre el filtrado de ruido y la disminuci´on de la componente continua sigue el patr´on general. 5.3.4. Classification (Figura 5.16) Salvo con una cache de correspondencia directa, esta aplicaci´on es la que menos presiona al siguiente nivel de memoria. Observamos una gran diferencia entre asociatividad 1 y el resto de asociatividades. Adem´as, al aumentar el tama˜no de la cache, la sensibilidad a la asociatividad es menor. La influencia del tama˜no de la cache sobre el filtrado de ruido y la disminuci´on de la componente continua sigue el patr´on general. 5.3.5. Cloudstone (Figura 5.17) Junto con la aplicaci´on Nutch, Cloudstone destaca por gran variabilidad temporal. Pero en este caso, apenas es apreciable el filtrado paso bajo que se observa en el resto de aplicaciones al aumentar el tama˜no de cache. Observamos que la diferencia absoluta entre las distintas asociatividades es casi constante, independientemente del tama˜no de la cache. 5.3.6. Conclusiones Con tan solo cuatro procesadores las aplicaciones estudiadas pueden ejercer una presi´on notable sobre el siguiente nivel de memoria cache. Si asumimos que la recarga de instrucciones se produce regularmente, sin r´afagas (lo cual no suele ser cierto), podemos calcular a partir de BWin el n´umero medio de ciclos entre las transacciones de 64 B, mediante la siguiente formula (procesadores de 2GHz): 119,2 BW in(GBps)·ciclos transaccion (5.2) Esto significa que un ancho de banda de 10 GBps, observado en mas de una aplicaci´on y configuraci´on, supone en media un acceso cada 12 ciclos, aproximadamente. Cap´ıtulo 5. Resumen de Resultados 36 Figura 5.15: Ancho de banda por asociatividad y tama˜no en Nutch. Cap´ıtulo 5. Resumen de Resultados 37 Figura 5.16: Ancho de banda por asociatividad y tama˜no en Classification. Cap´ıtulo 5. Resumen de Resultados 38 Figura 5.17: Ancho de banda por asociatividad y tama˜no en Cloudstone. Cap´ıtulo 5. Resumen de Resultados 39 En la actualidad, las latencias de las caches de segundo nivel est´an en ese orden de magnitud, lo cual hace pensar en la necesidad de un dise˜no espec´ıfico. Una posibilidad ser´ıa un siguiente nivel de memoria cache de instrucciones privado para cada core, que disminuir´ıa el tr´afico por cuatro, ver figura 5.18(a). Otra posibilidad ser´ıa un siguiente nivel multibanco para datos e instrucciones, que permita el servicio simult´aneo del tr´afico de datos (que no ha sido considerado en este trabajo) y soporte la presencia de r´afagas de fallos, cuya serializaci´on tambi´en comprometer´ıa las prestaciones, ver figura 5.18(b). Figura 5.18: Dos propuestas para mejorar el suministro de instrucciones desde el siguiente nivel.(a)Segundo nivel de cache de instrucciones privado para cada core.(b)Segundo nivel de cache compartido (datos + instrucciones) y multibanco. Una buena forma de entender como afecta el aumento de tama˜no y asociatividad consiste en observar la evoluci´on temporal del ancho de banda como si fuera una se˜nal, y considerar a la cache como un filtro paso bajo, que de acuerdo a su tama˜no y asociatividad, reduce progresivamente el nivel de la componente continua y su frecuencia de corte. Esta es una hip´otesis interesante, que deber´ıa ser contrastada de forma rigurosa, pero que excede del alcance de este trabajo. Desde el punto de vista de muestreo, es decir, de la posibilidad de extraer conclusiones v´alidas observando ´unicamente una parte peque˜na de toda la evoluci´on temporal, podemos dividir las aplicaciones en dos grupos. El primero est´a formado por Nutch y Cloudstone; su variabilidad es grande y no parece que pueda escogerse un trozo peque˜no representativo. El segundo est´a formado por Streaming, Cassandra y Classification; en estos casos, no parecen verse fases claras, pareciendo cualquier tramo similar y susceptible de ser representativo. Por supuesto estas reflexiones valen ´unicamente para experimentos encaminados a probar el siguiente nivel, carg´andolo con un tr´afico representativo. Cap´ıtulo 5. Resumen de Resultados 40 5.4. Comparaci´on con otras cargas de trabajo Seg´un los creadores de Cloudsuite una de sus principales caracter´ısticas es que sus benchmarks ejercen una fuerte presi´on contra la cache de instrucciones [FAK+12]. Para contrastar esta afirmaci´on vamos a comparar las tasas de fallos que hemos obtenido experimentalmente con los suyos y con otras fuentes disponibles. A continuaci´on presentamos un resumen de los trabajos que hemos consultado: Evaluating associativity in CPU caches. Este es el trabajo en el que Hill y Smith proponen el modelo de las 3Cs [HS89]. Adem´as, en ´el realizan un estudio para arquitecturas maduras de 32 bits, mediante simulaciones hechas con 28 trazas de computadores IBM 370 (sistema operativo MVS) y DEC VAX-11 (sistemas operativos VMS y ULTRIX). Los datos que reproducimos corresponden a unos promedios ajustados que sus autores denominan ”design target miss ratios”, pensados para caracterizar de forma tabular el comportamiento ”medio”de una cache y no tener que simular. En la figura 5.19 est´an recogidos los mpki para caches de instrucciones de tama˜no 16KB y 32KB y asociatividades desde 1 a 8, con tama˜no de bloque 64B. Filtering Directory Lookups in CMPs. En esta tesis Ana Bosque recoge la tasa de fallos para las aplicaciones de la suite SPLASH2, una suite usada para estudios cient´ıficos de m´aquinas paralelas con memoria compartida [LVIB11]. Las simulaciones se realizaron con SIMICS, con binarios compilados para SPARC v9 en Solaris 8, y corresponden a una cache de instrucciones de primer nivel de 16 KB, con tama˜no de bloque 32B y asociatividad 8. En la figura 5.19 se reproducen las tasas de fallos obtenidas para toda la secci´on paralela de cada benchmark. Memory System Behavior of Java-Based Middleware. En este trabajo, Karlsson, Moore, Hagersten y Wood usan dos benchmarcks: SPECjbb y ECperf [KMHW03]. Las simulaciones se realizaron con SIMICS, con binarios compilados para SPARC v9 en Solaris 8. SPECjbb est´a dise˜nado para medir la habilidad de un sistema para ejecutar aplicaciones Java en el lado del servidor. Esta aplicaci´on conecta a los clientes con la base de datos a trav´es de la l´ogica de negocio, pero para hacer el benchmark m´as portable y f´acil de usar, no usan una base de datos comercial, almacenando directamente las tablas en memoria como objetos de tipo ´arbol de Java. ECperf est´a dise˜nado para comprobar el rendimiento y la escalabilidad de un sistema de 3 niveles (cliente, servidor y base de datos), modelando un negocio online. Los benchmarks se simulan para distintos tama˜nos de cache, con asociatividad 4 y tama˜no de bloque 64B. Cap´ıtulo 5. Resumen de Resultados 41 Clearing the clouds. Este es el trabajo que motiva en parte nuestro estudio. En ´el, Ferdman et al. del laboratorio Parsa realizan un estudio de la Cloudsuite en un hardware real, bajo sistema operativo Linux y utilizando contadores de prestaciones. La m´aquina que aloja los benchmarks a monitorizar es un Dell PowerEdge M1000e, con dos procesadores Intel X5670 y 24GB de RAM en cada blade. Cada procesador Intel X5670 incluye seis cores agresivos con ejecuci´on fuera de orden, con una jerarqu´ıa de tres niveles de cache. El primer nivel es privado y separado para datos e instrucciones. El segundo tambi´en es privado, pero contiene datos e instrucciones. Finalmente, el tercer y ´ultimo nivel es compartido por los seis cores. La cache L1 de instrucciones real tiene tama˜no 32KB, asociatividad 4 y tama˜no de bloque 64B. Sus tasas de fallos recogen 180 segundos por cada carga de trabajo, una vez que se ha completado la fase de inicializaci´on de carga y se supone que el sistema ha entrado en un r´egimen estacionario[FAK+12]. Se supone que las tasas de fallos que reproducimos promedian el comportamiento de los 12 procesadores, aunque esto no est´a explicitado en su art´ıculo. Nuestro trabajo. Para comparar con un n´umero ´unico se ha calculado la mediana en cada benchmark de todas las muestras temporales para los cuatro procesadores. La informaci´on derivada de estos trabajos se ha resumido en la tabla de la figura 5.19. En la columna de la izquierda est´a la fuente. En la segunda columna presentamos las aplicaciones. En las siguientes columnas aparecen las tasas de fallos de instrucciones para diferentes tama˜nos y asociatividades, siempre que ha sido posible para tama˜no de bloque 64 B. En la ´ultima columna se hace referencia a la naturaleza de las instrucciones consideradas, ya sea de s´olo de usuario (u), o de sistema y usuario a la vez (u+s y u∪s). En la suite SPLASH2 ´unicamente se considera actividad de usuario, pero al tratarse de aplicaciones cient´ıficas, es conocido que suponen una carga de sistema despreciable. En el trabajo de referencia de Cloudsuite se desagrega la actividad de usuario y de sistema (u+s) [FAK+12], mientras que en el resto de trabajos no se dispone de ese detalle (u∪s). 5.4.1. Conclusiones Los datos recogidos son heterog´eneos y escasos, pero comparando nuestras tasas con las del resto de los autores, podemos extraer algunas conclusiones: Trabajo de Hill y Smith [HS89]. Si comparamos la media de nuestras aplicaciones con sus n´umeros, ambos resultados son muy similares. Si descartamos a Streaming y Classification por at´ıpicos (outliers), entonces nuestros resultados suponen tasas de fallos menores. Cap´ıtulo 5. Resumen de Resultados 42 Figura 5.19: Comparaci´on MPKI benchmarks. Tipo de actividad hace referencia a si los datos son de usuario (u) o de sistema (s) Tesis de Ana Bosque [LVIB11]. La media de estas aplicaciones ronda los 30 mpki, superior a nuestra media, pero destaca la gran influencia del at´ıpico Radiosity y el efecto, notable, de utilizar un tama˜no de bloque de 32 B. Si descartamos los at´ıpicos, la media de este trabajo queda por debajo de la nuestra, lo cual es razonable para cargas cient´ıficas. Trabajo de Karlsson et al. [KMHW03]. Muy comparable a nuestros resultados. Podr´ıamos colocarlos como propios y pasar´ıan desapercibidos. Trabajo de Ferdman et al. [FAK+12]. Esta comparaci´on tiene un gran inter´es, puesto que estamos hablando de las mismas aplicaciones. Sin embargo, en la confrontaci´on uno a uno, tan solo la aplicaci´on Nutch presenta tasas comparables. El resto de aplicaciones presenta tasas significativamente mayores en las ejecuciones reales del Parsa. ¿C´omo explicarlo?. No lo sabemos. Es cierto que hay dos factores diferenciales que juzgamos importantes, el tama˜no de la muestra y el sistema operativo. Nosotros simulamos 10 s y ellos ejecutan 180 s. Nuestro sistema operativo Ap´endice A. Carga y Desarrollo del Proyecto 49 Figura A.2: Distribuci´on del tiempo invertido en el proyecto. que por errores, u otras razones fueron descartados esta estimaci´on, como sucede en todos los trabajos de investigaci´on de arquitectura de computadores, podr´ıa hasta triplicarse. Estas horas de simulaci´on corresponden a 550 segundos de aplicaci´on real. Haciendo los c´alculos apropiados vemos que la m´aquina virtual funciona a una velocidad equivalente de 1’59 MIPS para el algoritmo MC (m´ultiples caches) y 1’17 MIPS para el algoritmo CCA (cache completamente asociativa). Dado que los procesador f´ısicos del cluster ATPS tiene una frecuencia de 3Ghz, y podemos suponer que sostienen un ritmo de 2 instrucciones/ciclo, lo cual corresponder´ıa a 6 GIPS, podemos apreciar un slowdown de 3770 y de 5128, respectivamente. A.4. Problemas encontrados El primer problema con el que nos encontramos es la falta de una documentaci´on para iniciarse en Simics y para resolver dudas que iban surgiendo en su uso, ya que el manual de uso del simulador resulta insuficiente. Uno de los problemas generales de los trabajos de simulaci´on en arquitectura es que estas son muy costosas en tiempo, algunas costaban varios d´ıas, as´ı que cualquier error en la simulaci´on conlleva retrasos considerables. Una punto d´ebil del algoritmo MC es que en caso de fallo el algoritmo recorre todo el conjunto (de 8 bloques), para mejorarlo podr´ıa proponerse el uso de un algoritmo que con poco coste nos dijera que un bloque no est´a en la cache. Una propuesta podr´ıa ser el uso de un filtro de Bloom [Blo70], una estructura de datos probabil´ıstica concebida Ap´endice A. Carga y Desarrollo del Proyecto 50 Tarea N´umero de horas Formaci´on 160 Estado del arte de Simuladores 71 Estado del arte de las cargas de trabajo 33 Herramientas para el an´alisis 56 Familiarizaci´on con el entorno de trabajo 119 Primeros usos de Simics 59 Iniciaci´on y configuraci´on CloudSuite 60 Programaci´on 120 Programaci´on m´odulos caches 90 Programaci´on Scripts 30 Caracterizaci´on CloudSuite 195 Dise˜no y ejecuci´on de experimentos 75 An´alisis de Resultados 120 Documentaci´on 105 Tutorial Simics 43 Memoria 62 Total 699 Tabla A.1: Horas dedicadas a cada tarea del Proyecto. por Burton Howard Bloom en 1970 que se usa para saber si un elemento forma parte de un conjunto. El test determina con seguridad si un elemento no est´a en el conjunto, o de forma insegura si lo est´a (o quiz´as no, es un falso positivo). Otro de los problemas encontrados para la realizaci´on del proyecto es que el cluster utilizado, ATPS, dej´o de funcionar dos veces: en diciembre y en agosto. Est´a ´ultima coincide con las tareas de mantenimiento de la universidad pero su restablecimiento se retras´o debido a problemas en Danae, otro cluster del que depende, administrado por el Dpto. de Inform´atica e Ingenier´ıa de Sistemas. Adem´as coincidi´o con la etapa de mayor intensidad de experimentos y algunos de ellos fueron interrumpidos y tuvieron que repetirse despu´es. Ap´endice B Productividad en Simics Uno de los objetivos de este proyecto era producir documentaci´on para posteriores proyectos, ya sean de grado, m´aster o investigaci´on que requieran Simics como plataforma de simulaci´on. Y de esta manera facilitar y agilizar la fase de formaci´on de estos proyectos. En este tutorial se guiar´a la ejecuci´on de Simics y sus principales funciones en el cluster ATPS del grupo Gaz de la Universidad de Zaragoza. El tutorial est´a basado y hace referencias al “Simics User Guide For Unix”. 51 GRUPO DE ARQUITECTURA DE COMPUTADORES DE LA UNIVERSIDAD DE ZARAGOZA Tutorial de Simics Este tutorial guiará a través de los primeros pasos para la ejecución de Simics y su configuración en el cluster ATPS del grupo Gaz de la Universidad de Zaragoza. 1. DIRECTORIOS DE TRABAJO Primero debemos crear un directorio de trabajo. Como estamos trabajando en ATPS para que el directorio de trabajo sea visible por los nodos debemos crearlo en: /export/home/iduser Siendo iduser vuestro nombre de usuario de atps, podemos crear una carpeta llamada common y crear alli el workspace, siendo su ruta: /export/home/iduser/common/workspace Para configurar este workspace debemos ejecutar workspace-setup que se encuentra en el directorio de instalación de Simics (/usr/local/pkg/simics-3.0.31/bin/workspace-setup en atps). Para trabajar más cómodamente podemos linkar esta carpeta commons en nuestro home usando el comando “ln -s”. Además del workspace necesitaremos tres directorios más: Checkpoints, Craffs y tmp, ya que los archivos que escribiremos allí van a ser bastante grandes se crearan en nuestra carpeta de export/scratch/users/iduser. El directorio scratch tiene gran capacidad pero no realiza copias de seguridad, así que tenemos que tener cuidado y encargarnos de realizarlas. 2. CONFIGURACIÓN ATPS Veámos ahora cómo hay que configurar ATPS para ejecutar Simics. Primero hay que modificar $HOME/.software y añadir la palabra “simics”. Además, en el .profile hay que indicar dónde buscar la licencia, escribimos: [email protected].unizar.es Para que estos cambios tengan efecto hay que salir y acceder de nuevo a atps. Si al ejecutar Simics la ventana que muestra la máquina target (máquina que estamos simulando) no se abriera, se puede probar modificando .profile. Para ello hay que comentar 1 las 5 líneas de código que aparecen tras el comentario #who i am (aparece la palabra DISPLAY en ellas, así que son fáciles de localizar). 3. INICIAR EL SIMULADOR Hay que tener instalado un sistema operativo en la máquina que emulamos. En este caso usaremos una máquina SPARC que ejecute Solaris. Los ficheros system-01.disk.craff, system-sol10.disk.craff, abisko-sol10.state y abisko-sol10.run.simics a los que se hace referencia a continuación se proporcionan en el DVD adjunto:“Ficheros Tutorial Simics”. Primero copiamos system-01.disk.craff y system-sol10.disk.craff en el directorio que habíamos creado para los craffs (/export/scratch/users/iduser/craffs) Los archivos .craff son copias de disco duro (no confundir con los checkpoints) y más adelante veremos que se pueden crear para reutilizar datos de una simulación y poder usarlos para crear checkpoints con otras configuraciones. Después copiamos abisko-sol10.state y abisko-sol10.run.simics en nuestro (..)/workspace/targets/serengenti Tenemos que modificar las tres líneas que contienen paths en abisko-sol10.state: Checkpoint_path apuntará a este mismo directorio ((..)/workspace/targets/serengenti) Los otros path tienen que apuntar a los craffs que hemos copiado antes, así que hay que escribir la ruta completa. Los parámetros para configurar la máquina se encuentran en abisko-sol10.run.simics, en este caso se han añadido los siguientes parámetros: $num_cpus=1 (1 procesador) $megs_per_cpu=1024 (1GB de memoria por procesador) $cpu_class = ultrasparc-iii-plus (máquina con un thread por cpu, ultrasparc-iv tiene dos threads) Finalmente ejecutamos: $ simics -stall -x abisko-sol10-run.simics Con este comando le estamos indicando que ejecute el script abisko-sol10-run.simics, “-stall” indica que queremos que las transacciones de memoria se envíen a la jerarquía de memoría que haya conectada y “-x” que el fichero de entrada que le pasamos es un script. Los comandos básicos de Simics son: c y ctrl+c, continuar la ejecución del target y detenerla, respectivamente. Para salir de Simics se usa q o exit. Antes de iniciar la simulación del target hay que indicarle a Simics dónde guardar los archivos temporales, si no tendremos problemas más adelante a la hora de copiar archivos en el target, guardar checkpoints y craffs. Para ello antes de darle a continuar (c) escribimos: prefs->swap-dir=/export/scratch/users/userid/tmp Depués introducimos c, y entonces el sistema operativo solaris se cargará. Estará listo cuando aparezca el prompt (#). Como hemos ido apuntando tenemos dos máquinas, la simulada (target) y la real (host). Es posible la comunicación y la transferencia de archivos, y gracias a los archivos de configuración proporcionados para acceder a los archivos almacenados en el host(atps) desde el target(sparc2 solaris) solo hay que ejecutar en el target: # mount /host Se habrá creado una carpeta host que enlazará con nuestra máquina, por ejemplo para llegar a nuestra home la ruta será /host/home/userid. 4. CREACIÓN DE CHECKPOINTS Los checkpoints nos permiten volver a un mismo punto después sin necesidad de arrancar la máquina de nuevo. Además, también se guarda el contenido del disco. En el punto que deseemos de ejecución, hacemos ctrl+c en el terminal del simulador y ejecutamos: simics>write-configuration ruta_check_point/micheckpoint.check Si queremos iniciar Simics desde ese checkpoint ejecutaremos: $simics -stall -c ruta_check_point/micheckpoint.check Podemos ver que usamos el flag “-c” cuando iniciamos Simics desde un checkpoint. Tambien se puede iniciar Simics y desde alli el checkpoint con: simics>read-configuration ruta_check_point/micheckpoint.check Hay que tener mucho cuidado al organizar los directorios en nuestra carpeta de checkpoints porque si cambiamos un checkpoint de lugar no funcionará y habrá que modificar los path de sus archivos. Otro aspecto a tener en cuenta sobre los checkpoints es que son incrementales. Es decir, si inicias el sistema desde un checkpoint (chk1) y en un punto creas otro checkpoint (chk2), para iniciar el sistema con chk2, chk1 será necesario. 5. COMANDOS ÚTILES Aquí tenemos algunos comandos que pueden resultarnos útiles en Simics. list-modules : Lista todos los módulos que pueden ser cargados en Simics, indicando los que ya lo están. run-command-file : para ejecutar scripts. Más adelante hablaremos de estos scripts, pueden tener código en Python y comandos de Simics. list-objects: lista todos los objetos así como información de su clase. output-file-start y output-file-stop : para guardar la salida de Simics (no del target) en un fichero. help : Comando de ayuda, si se ejecuta help y un objeto proporciona toda la información sobre ese objeto: sus atributos, sus comandos, su clase... print-time -all : Muestra para cada procesador el número de instrucción, de ciclo y el tiempo en segundos en el que se encuentra. Si queremos ver los ciclos de un procesador en concreto podemos ejecutar cpu0.print-time. 3 6. CREACIÓN DE CRAFFS Los Craffs son similares a los checkpoints pero permiten guardar solamente el estado persistente de una máquina, por ejemplo, los datos que permanecen cuando la máquina está apagada (CRAFF = Compressed Random Access File Format). Normalmente esto quiere decir las imagenes del disco, la memoria flash o el contenido NVRAM. De forma muy similar a los checkpoints se guardan y se cargan con los comandos “save-persistent-state path” y “load-persistent-state path” respectivamente. ¿Para que nos puede ser útil? Copiar grandes archivos desde el host hasta el target puede ser costoso en tiempo, para ello una vez copiados puede guardarse un checkpoint para volver al mismo punto. Sin embargo si cambiamos la configuración de la máquina, por ejemplo 2 cpus en vez de 1 cpu, tendríamos que volver a realizar la operación. En este caso Simics nos permite cargar el craff sobre la nueva configuración, como resultado los ficheros anteriores estarán ya cargados en el target. 7. CREACIÓN DE SCRIPTS Los scripts de Simics pueden llevar tanto comandos Simics como código Python. Las lineas de código Python deben ir precedidas del carácter , y si algún comando de Simics quiere ser invocado en Python hay que usar “@run_command”. Veamos algún ejemplo de código Python en Simics: simics>@print “This is a Python line” This is a Python line simics>@if SIM_number_processors() >1: ....... print “Wow, an MP system!” ....... else: ....... print “Only single pro :-(” ....... Wow, an MP system! simics>@run_command(“print-time”) processor steps cycles time [s] cpu0 27828281475 27828281475 371.044 El propósito de invocar un comando de Simics en Python es la potencia de este lenguaje, lo cual nos permitiría, por ejemplo, ejecutar un bucle con comandos de Simics. En el siguiente script podemos ver un ejemplo: prefs−>swap−dir=/export/scratch/users/iduser/tmp #Cargamos checkpoint read−configuration /export/scratch/users/iduser/checkpoints/mi_checkpoint @sizeKB=8 @numlines=(sizeKB*1024)/64 4 #configuracion caches #========================================== @cache = pre_conf_object ( ’cache ’ , ’g−cache ’ ) @cache. cpus = conf . cpu0 @cache. config_line_number = numlines @cache. config_line_size = 64 @cache. config_assoc = 8 @cache. config_virtual_index = 0 @cache. config_virtual_tag = 0 @cache. config_write_back = 0 @cache. config_write_allocate = 1 @cache. config_replacement_policy = ’ lru ’ @cache. penalty_read = 0 @cache. penalty_write = 0 @cache. penalty_read_next = 0 @cache. penalty_write_next = 0 #Add Configuration @SIM_add_configuration ([ cache ] , None) ; #============================================= #Timing Model @conf .cpu0_mem. timing_model= conf . cache #Ejecucion @time=0 @run_command( "cd /home/iduser/experimentos" ) @for x in range (0,100): f i l e =open( "muestra"+str( sizeKB)+"time"+str( time ) , ’a ’ ) time=time+10 f i l e . write ( "Numero i nicial de instrucciones : \n" ) f i l e . write ( str(conf .cpu0 . steps )) run_command( "c 200000000" ) f i l e . write ( "\nNumero final de instrucciones : \n" ) f i l e . write ( str(conf .cpu0 . steps )) f i l e . write ( "\ nEstadisticas instrucciones \n" ) f i l e . write ( "\nCpu0" ) f i l e . write ( "\nOperaciones de lectura : "+str(conf . cache . stat_data_read )) f i l e . write ( "\nFallos en operaciones de lectura : "+str(conf . cache . stat_inst_data_read_miss )) f i l e . close () run_command( "cache . reset−st at is ti cs " ) run_command( "cache . reset−cache−lines " ) exit Los dos primero comandos son de Simics, indicamos dónde guardar los archivos temporales y cargamos el checkpoint. A continuación ejecutamos dos instrucciones de Python, las cuales 5 modifican unas variables que nos permitirán configurar la simulación. En el siguiente conjunto de instrucciones configuramos un objeto llamado “cache” que se declara como objeto de la clase “g-cache”. Podemos ver como las variables pueden ser usadas para la configuración u otros objetos (cpu0 a través de conf.cpu0). Finalmente llamamos a la función SIM_add_configuration() que añade el objeto cache a la configuración de Simics. Esta función forma parte de la API de Simics que recoge todas las instrucciones que permiten la comunicación entre Simics y Python. Una vez que el objeto forma parte de la configuración de Simics lo conectamos con el espacio de memoria de la cpu0. En este punto la configuración de la memoria cache a terminado y procedemos a la ejecución, para guardar los resultados de nuestros experimentos en una carpeta determinada podemos usar el comando cd path como en linux. El ejecutarlo a través de Python en vez de como simplemente un comando Simics puede permitirnos cambiar la ruta a través de variables, por ejemplo. Y finalmente tenemos un bucle de 100 iteraciones que crea un fichero, escribe atributos de objetos de Simics en él, ejecuta la simulación por un número determinado de instrucciones. Tras ello escribe los atributos de estadísticas de lecturas de la cache, cierra el fichero y ejecuta los comandos de Simics que inicializan la cache y sus estadísticas. Al acabar el bucle se ejecuta exit para salir del simulador. Los scripts pueden ser ejecutados tanto desde el propio Simics: simics>run-command-file script Cómo al lanzar Simics: $ simics -stall -x script 8. SOBRE ESTE TUTORIAL Este tutorial fue parte del proyecto de fin de carrera “Caracterización de instrucciones en aplicaciones de cloud” presentado en Septiembre de 2014 por la alumna de Ingeniería Informática, Alba Pedro Zapater. El objetivo de la creación de este tutorial fue producir documentación para posteriores proyectos, ya fueran de grado, máster investigación que requieran Simics como plataforma de simulación. Y de esta manera facilitar y agilizar la fase de formación de estos proyectos. 6 Ap´endice C M´odulo G-Cache En este ap´endice vamos a ampliar la informaci´on sobre el m´odulo g-cache que ya present´abamos en el apartado 4.3 y sobre los algoritmos que hemos programado. C.1. M´as sobre G-cache Para el estudio tanto de g-cache como de la simulaci´on de caches en general se acudi´o al capitulo 18 del “Simics User Guide For Unix” y al c´odigo de g-cache que se encuentra dentro del directorio de instalaci´on de Simics en [simics]/src/extensions. G-cache nos permite simular desde una cache sencilla, definiendo su tama˜no de bloque, n´umero de bloques, asociatividad, pol´ıtica de reemplazo, si es copy-back, si es write-allocate y ciclos de penalizaci´on por escrituras y lecturas, hasta jerarqu´ıas m´as complicadas. Por ejemplo la de la figura C.1, en la que dos niveles de cache son simulados, y el primer nivel est´a dividido en cache de instrucciones y cache de datos. G-cache tambi´en permite tanto conectar una memoria cache a varias CPUs c´omo dise˜nar un sistema multiprocesador con un protocolo de coherencia MESI. G-cache nos proporciona adem´as las estad´ısticas sobre el n´umero total de transacciones, n´umero de lecturas, de escrituras, de instrucciones, n´umero de fallos en cada una de estas categor´ıas, n´umero de operaciones en copy-back, y n´umero de invalidaciones, y cambios de estado para el protocolo MESI. Podemos ilustrar g-cache a trav´es de sus diagramas de estado, para ello vamos a usar como ejemplo el sistema de la figura C.2. En ella podemos observar dos niveles de cache, con protocolo de coherencia MESI entre las caches de nivel 2. De este sistema podemos obtener cuatro diagramas de estados: Transiciones por eventos internos de las caches de nivel 2 (C.3), transiciones por eventos externos, correspondientes al protocolo MESI entre caches del nivel 2 (C.4), transiciones por eventos internos de las caches de nivel 1 (C.5) y por ´ultimo, transiciones por eventos externos, 58 Ap´endice C. G-Cache 65 Se ha observado una mejora en el tiempo de ejecuci´on de un 90,52 % al usar este algoritmo frente a usar el algoritmo original de LRU de g-cache que esta basado en una lista ´unica con marcas de tiempo. Ap´endice D Simulaciones CloudSuite En este Ap´endice vamos a presentar d´onde y c´omo se han llevado a acabo las simulaciones de la CloudSuite. D.1. Cluster ATPS Los experimentos han sido realizados en el cluster ATPS. El cluster ATPS es una infraestructura de computaci´on de altas prestaciones financiada por el grupo de Arquitectura de Computadores de la Universidad de Zaragoza (gaZ). ATPS se usa principalmente para simular modelos funcionales y temporales a nivel microarquitectura (procesadores, caches y redes de interconexi´on). ATPS es un cluster que se usa fundamentalmente en modo de productividad. Se lanzan m´ultiples experimentos (variaciones de un modelo con distintos par´ametros) que se ejecutan independientemente en las m´aquinas del cluster. El cluster consta de 6 chasis de dos tipos: •3 chasis 1U, cada uno con 2 nodos 2x Intel Xeon X5365 (4Cores, 3.00 GHz, 8 MB L2), en total 6 nodos, uno se dedica al front-end y los otros dedicados a computaci´on. En cada nodo hay pues un total de 8 cores compartiendo 16 GB RAM. •3 chasis 2U modelo Superserver SYS-6026TT-TRF, cada uno con 4 nodos 2xIntel Xeon X5650 (Westmere, 6 Cores, 2.67 GHz, 12 MB L3), en total 12 nodos, todos dedicados a computaci´on. En total en cada nodo hay 12 cores (24 threads) compartiendo 48 GB RAM. En la figura D.1 podemos ver el esquema de conexiones de red que permite simplificar la administraci´on de los distintos equipos, ya que todos los nodos est´an conectados al front-end a trav´es de la misma direcci´on IP. 66 Ap´endice D. Simulaciones CloudSuite 67 Figura D.1: Red de conexiones atps. D.2. Condor Condor es un sistema de gesti´on de carga para tareas de computaci´on intensivas que soporta un gestor de colas, con pol´ıticas de planificaci´on de ejecuci´on, esquema de prioridades, monitorizaci´on y gesti´on de recursos. Es decir, desde el front-end se lanzan los trabajos a trav´es de Condor que se encarga de distribuirlos en los nodos. A continuaci´on podemos ver un script muy sencillo para lanzar un trabajo, aunque Condor permite muchas m´as opciones de configuraci´on para necesidades m´as sofisticadas. # Example submit file for vanilla job Universe = vanilla Executable = hello_world .sh input = /dev/ null output = hello . out error = hello . error Queue Lo habitual es lanzar las tareas a los nodos de ATPS a trav´es de condor, sin embargo al compartir la m´aquina con un entorno de producci´on que limitaba los recursos que pod´ıamos utlizar, pasamos a programar shell scripts para lanzar manualmente los trabajos en el n´umero limitado de nodos que nos fueron asignados. D.3. Scripts En esta secci´on detallamos los scripts usados para las simulaciones a las que se hace referencia en el apartado 4.4. Ap´endice D. Simulaciones CloudSuite 68 D.3.1. Shell Scripts Un script por cada aplicaci´on. En el ejemplo ilustramos el lanzamiento de una simulaci´on de la aplicaci´on Cassandra. size =8 for ((i =0;i <6; i++) ) do oldsize = $size size=‘ expr $size \* 2‘ string =" s/ @sizeKB = $oldsize / @sizeKB = $size /" sed -i $string / home / albapz / common / workspacenodos / scripts / OptCassan4cpu echo $size ./ simics - stall -no - win -x / home / albapz / common / workspacenodos / scripts / OptCassan4cpu done El script anterior permite lanzar 6 ejecuciones de Simics a trav´es de un bucle. En cada iteraci´on con el comando “sed” se modifica el script de Simics “OptCassan4cpu”. Concretamente modifica la variable que define el tama˜no de la cache, doblando este valor en cada iteraci´on. Tras esto Simics ejecuta el script mencionado. Al lanzar Simics se le indica a trav´es del flag -no-win que desactive la apertura de ventanas externas (las del target o cualquier otra externa). D.3.2. Simics Scripts Los scripts de Simics pueden contener comandos de Simics y/o c´odigo Python (se indica con el s´ımbolo @al principio de la linea de c´odigo). Al lanzar Simics con el flag -x indicamos que tiene que ejecutar el script que se pasa como par´ametro. Veamos un ejemplo: prefs -> swap - dir =/ export / scratch / users / albapz / tmp # Cargamos checkpoint read - configuration / export / extra / data / trazas / parsa / cloudsuite / images / cassandra /4 cpu /4s -4 gb -2c -4 gb @sizeKB=8 @numlines =( sizeKB *1024) /64 # configuracion caches istc - disable @conf . server_cpu0 . instruction_fet ch_mode =" instruction - fetch - trace " @conf . server_cpu1 . instruction_fet ch_mode =" instruction - fetch - trace " @conf . server_cpu2 . instruction_fet ch_mode =" instruction - fetch - trace " @conf . server_cpu3 . instruction_fet ch_mode =" instruction - fetch - trace " @conf . client_cpu0 . instruction_fet ch_mode =" instruction - fetch - trace " @conf . client_cpu1 . instruction_fet ch_mode =" instruction - fetch - trace " #============================================= ## Transaction staller for memory #============================================= @staller0 = pre_conf_object (’ staller0 ’, ’trans - staller ’) Ap´endice D. Simulaciones CloudSuite 69 @staller0 . stall_time = 0 #================================================================ #============================================= ## L1 - Instruction Cache : L1 Inst0 @ic0 = pre_conf_object ( ’ic0 ’, ’g - cache ’) @ic0. cpus = conf . server_cpu0 @ic0. config_line_number = numlines @ic0.config_line_size = 64 @ic0.config_assoc = 8 @ic0.config_virtual_index = 0 @ic0. config_virtual_tag = 0 @ic0. config_write_back = 0 @ic0. config_write_allocate = 1 @ic0.config_replacement_policy = ’lruopt’ @ic0.penalty_read = 0 @ic0. penalty_write = 0 @ic0. penalty_read_next = 0 @ic0. penalty_write_next = 0 @ic0. timing_model = staller0 #============================================= ## ID splitter for L1 cache @id0 = pre_conf_object ( ’id0 ’, ’id - splitter ’) @id0. ibranch = ic0 @id0. dbranch = staller0 #============================================= ## L1 - Instruction Cache : L1 Inst1 @ic1 = pre_conf_object ( ’ic1 ’, ’g - cache ’) @ic1. cpus = conf . server_cpu1 @ic1. config_line_number = numlines @ic1.config_line_size = 64 @ic1.config_assoc = 8 @ic1.config_virtual_index = 0 @ic1. config_virtual_tag = 0 @ic1. config_write_back = 0 @ic1. config_write_allocate = 1 @ic1.config_replacement_policy = ’lruopt’ @ic1.penalty_read = 0 @ic1. penalty_write = 0 @ic1. penalty_read_next = 0 @ic1. penalty_write_next = 0 @ic1. timing_model = staller0 #============================================= ## ID splitter for L1 cache @id1 = pre_conf_object ( ’id1 ’, ’id - splitter ’) @id1. ibranch = ic1 @id1. dbranch = staller0 #===================================== # Add Conf igura tion @SIM_add_configuration ([ staller0 ,ic0 , id0 , ic1 , id1 ], None ); #============================================= # Timing Model Ap´endice D. Simulaciones CloudSuite 70 @conf . server_cpu0_mem . timing_model = conf .id0 @conf . server_cpu1_mem . timing_model = conf .id1 #Ejecucion @time =0 @run_command (" cd / home / albapz / common / workspacenodos / experimients / lruopt / cassan") @for x in range (0 ,100) : file = open (" cassanopt2cpus "+ str ( sizeKB )+" time "+ str ( time ) ,’a ’) time= time +10 file . write (" Numero inicial de instrucciones : \ n") file . write ( str (conf . server_cpu0 . steps ) ) run_command ("c 200000000 ") file . write ("\ nNumero final de instrucciones : \ n") file . write ( str (conf . server_cpu0 . steps ) ) file . write ("\ nEstadisticas instrucciones \ n") file . write ("\ nCpu0 ") file . write ("\ nInstruction Fetch transactions : " +str ( conf .ic0 . stat_inst_fetch )) file . write ("\ nInstruction Fetch misses : " +str ( conf . ic0 . stat_inst_fetch_miss)) file. write ("\ nVector Hits : "+ str( conf . ic0. lruopt_hits )) file . write ("\ nCpu1 ") file . write ("\ nInstruction Fetch transactions : " +str ( conf .ic1 . stat_inst_fetch )) file . write ("\ nInstruction Fetch misses : " +str ( conf . ic1 . stat_inst_fetch_miss)) file. write ("\ nVector Hits : "+ str( conf . ic1. lruopt_hits )) file . close () run_command (" ic0. reset - statistics ") run_command (" ic0 . reset - cache - lines " ) run_command (" ic1. reset - statistics ") run_command (" ic1 . reset - cache - lines " ) conf. ic0 . lruopt_hits =[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0] conf. ic1 . lruopt_hits =[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0] exit En este script podemos destacar: •El par´ametro -sizeKB indica el tama˜no de la cache a simular. Este par´ametro es el que se modifica desde el Shell Script. numlines indica el n´umero de bloques. •Simics usa internamente unas caches software (de datos y de instrucciones) para acelerar las simulaciones, a las que llama STC (Simulator Translation Cache) que evitan que todas las transacciones tengan que pasar por la jerarqu´ıa de memoria. Sin embargo en el caso de las instrucciones esto implica estad´ısticas incorrectas, por lo cual procedimos a su desactivaci´on con el comando istc-disable. Ap´endice D. Simulaciones CloudSuite 71 •Por defecto, y tambi´en para acelerar las simulaciones, Simics no env´ıa las b´usquedas de instrucciones a la jerarqu´ıa de memoria. Para evitar este comportamiento hay que cambiar el modo de simulaci´on de las cpus a instruction-fetch-trace •Staller representa el acceso a la memoria principal, sin embargo en este caso la penalizaci´on por acceso a memoria principal es 0. •Se configuran dos caches de instrucciones, una por cada procesador. En este caso la pol´ıtica de reemplazo lruopt corresponde al algoritmo MC descrito en el apartado C.2.1. •Se declara un ID Splitter para cada procesador; este objeto de Simics separa las transacciones de datos de las de instrucciones. •Todos los objetos declarados se a˜naden a la configuraci´on de Simics y se conecta cada ID Splitter al timing model de los procesadores cuyas caches de instrucciones queremos simular (los procesadores que ejecutan los servidores de inter´es en cada aplicaci´on). Al timing model puede conectarse un objeto para que tenga acceso a la transacci´on de memoria, antes de que ´esta se ejecute. En nuestro caso ese objeto es nuestra jerarqu´ıa de memoria. •Finalmente comienza la ejecuci´on de la simulaci´on, para ello un bucle en Python ejecuta 100 veces 200 millones de instrucciones (por cada procesador, ya que trabajan en paralelo) y tras cada ejecuci´on se escriben las estad´ısticas en un fichero, inicializando de nuevo tanto las estad´ısticas como las caches. La figura D.2, representa la jerarqu´ıa de memoria configurada en el script de ejemplo. Figura D.2: Jerarqu´ıa de cache configurada con el script. Bibliograf´ıa [BKSL08] Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. The parsec benchmark suite: Characterization and architectural implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, October 2008. http://parsec.cs.princeton.edu/ [Online; accessed 23-Agosto-2014]. [Blo70] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422–426, July 1970. [Bon07] Jan Lodewijk Bonebakker. Finding representative workloads for computer system design. Technical report, Sun Microsystems, Inc. Mountain View, CA, USA, 2007. [CGS99] David E. Culler, Anoop Gupta, and Jaswinder Pal Singh. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann Publishers Inc., 1999. [CPU06] SPEC CPU2006. https://www.spec.org/cpu2006/, 2006. [Online; accessed 23-Agosto-2014]. [EPF] PARSA EPFL. Cloudsuite official webpage. http://parsa.epfl. ch/cloudsuite/cloudsuite.html. [FAK+12] Michael Ferdman, Almutaz Adileh, Onur Kocberber, Stavros Volos, Djordje Jevdjic Mohammad Alisafaee, Cansu Kaynak, Adrian Daniel Popescu, Anastasia Ailamaki, and Babak Falsafi. Clearing the clouds. a study of emerging scale-out workloads on modern hardware. In 17th Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012), March 2012. [HP06] John L. Hennessy and David A. Patterson. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006. 72 Bibliograf´ıa 73 [HS89] M.D. Hill and A.J. Smith. Evaluating associativity in cpu caches. Computers, IEEE Transactions on, 38(12):1612–1630, Dec 1989. [KMHW03] Martin Karlsson, Kevin Moore, Erik Hagersten, and David Wood. Memory System Behavior of Java-Based Middleware. pages 217–228, Anaheim, California, USA, February 2003. [LVIB11] Jos´e Mar´ıa Llaber´ıa, V´ıctor Vi˜nals, Pablo Ib´a˜nez, and Ana Bosquel. Filtering directory lookups in CMPS. PhD thesis, Zaragoza, Universidad de Zaragoza, Zaragoza, Ago 2011. http://zaguan.unizar.es/record/6812?ln=es. [MCE+02] P.S. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, and B. Werner. Simics: A full system simulation platform. Computer, 35(2):50–58, Feb 2002. [MGST70] R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Syst. J., 9(2):78–117, June 1970. [MSB+05] Milo M. K. Martin, Daniel J. Sorin, Bradford M. Beckmann, Michael R. Marty, Min Xu, Alaa R. Alameldeen, Kevin E. Moore, Mark D. Hill, , and David A. Wood. Multifacet’s general executiondriven multiprocessor simulator (gems) toolset. SIGARCH Comput. Archit. News, 33:92–99, Nov 2005. [TC] TPC-C. http://www.tpc.org/tpcc/. [Online; accessed 23-Agosto2014]. [web09] SPEC web2009. http://www.spec.org/web2009/, 2009. [Online; accessed 23-Agosto-2014].