Gestión de caché SDRAM en una jerarquía no volátil RRAM

Universidad de Valladolid Escuela de Ingeniería Informática TRABAJO FIN DE GRADO Grado en Ingeniería Informática (Mención Computación) Gestión de caché SDRAM en una jerarquía no volátil RRAM Autor: D. Adrián Lamela Pérez 2 4 Universidad de Valladolid Escuela de Ingeniería Informática TRABAJO FIN DE GRADO Grado en Ingeniería Informática (Mención Computación) Gestión de caché SDRAM en una jerarquía no volátil RRAM Autor: D. Adrián Lamela Pérez Tutor: D. Benjamín Sahelices Fernández 4 Índice general Agradecimientos 17 Abstract 19 Resumen 21 1. Introducción y objetivos 23 1.1. Planicación del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2. Contexto tecnológico 29 2.1. Memoriascaché..................................... 31 2.1.1. Principios de localidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.1.2. Organizaciónlógica............................... 33 2.1.3. Políticas de reemplazo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.1.4. Inclusión y exclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2. Visión general de las memorias DRAM . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.1. Celdas, arrays de memoria, bancos y ranks . . . . . . . . . . . . . . . . . . 38 2.2.2. Buses para comunicarse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.3. Pasos en una petición típica . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.4. Evolución de la arquitectura DRAM . . . . . . . . . . . . . . . . . . . . . 43 2.3. Organización de la memoria DRAM . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3.1. Módulosdememoria.............................. 47 2.3.2. Topologíahabitual ............................... 49 2.4. Protocolo básico de acceso a memoria DRAM . . . . . . . . . . . . . . . . . . . . 50 2.4.1. Comandosbásicos................................ 50 2.4.2. Interacciones entre comandos . . . . . . . . . . . . . . . . . . . . . . . . . 54 5 6 ÍNDICE GENERAL 2.5. Controlador de memoria DRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.5.1. Arquitectura del controlador de memoria DRAM . . . . . . . . . . . . . . 55 2.5.2. Políticas de manejo de buer de la . . . . . . . . . . . . . . . . . . . . . . 56 2.5.3. Esquema de traducción de direcciones de memoria . . . . . . . . . . . . . . 57 2.5.4. Optimización del rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . 60 3. Accesos a memoria fuera del chip 65 3.1. Intel R  Pin........................................ 67 3.1.1. Funcionamiento básico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.1.2. Pintools ..................................... 68 3.1.3. Observaciones sobre Pin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.1.4. Propósito para utilizar Pin . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.2. Fichero de traza y aplicaciones monitorizadas . . . . . . . . . . . . . . . . . . . . 70 4. Agrupamiento de aplicaciones 75 4.1. Agrupamiento en base a la localidad temporal . . . . . . . . . . . . . . . . . . . . 75 4.1.1. Agrupamiento de la distribución completa . . . . . . . . . . . . . . . . . . 77 4.1.2. Agrupamiento considerando un umbral de olvido . . . . . . . . . . . . . . 84 4.2. Perl de utilización de memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5. Mecanismo de prebúsqueda 97 5.1. Primera propuesta: modelo binomial . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.1.1. Fichero de localidad espacial . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.1.2. Violación de las suposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.2. Segunda propuesta: información inmediata anterior . . . . . . . . . . . . . . . . . 105 5.3. Tercera propuesta: modelo oculto de Markov . . . . . . . . . . . . . . . . . . . . . 107 5.3.1. Pasoiterativo.................................. 112 5.3.2. Pasoinicial ................................... 118 5.3.3. Procedimiento completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.4. Resultados del reconocimiento de patrones . . . . . . . . . . . . . . . . . . . . . . 123 5.5. Prebúsqueda....................................... 126 5.6. Resultados de la prebúsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 5.6.1. Caché SDRAM ideal con umbral de olvido . . . . . . . . . . . . . . . . . . 137 5.6.2. Caché SDRAM asociativa por conjuntos . . . . . . . . . . . . . . . . . . . 140 ÍNDICE GENERAL 7 Conclusiones 153 Anexos 156 A. Clustering localidad temporal para Ass1Tam32 159 B. Clustering localidad temporal para Ass8Tam16 165 C. Clustering localidad temporal para Ass8Tam32 171 D. Perl de memoria de las aplicaciones restantes 175 Referencias 187 8 ÍNDICE GENERAL Índice de tablas 3.1. Listado de aplicaciones a monitorizar. . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2. Comienzo del chero de traza .nvt para Firefox en el caso de 16MB de LLC y asociatividaddenivel1. ................................ 71 4.1. Ejemplo de las primeras líneas del chero de localidad temporal para el caso de Firefox, con una LLC de tamaño 16MB y asociatividad de nivel 1. . . . . . . . . . 76 4.2. Comienzo del chero de densidad para Firefox, con la conguración de asociatividad 1yLLCde16MB.................................... 93 5.1. Comienzo del chero de localidad espacial para la aplicación astar, con LLC de 16MByasociatividad1. ................................ 103 5.2. Correlaciones entre las variables X1 ij , X2 ij , Y1 ij y Y2 ij , para astar, LLC 16MB, asociatividad 1.............................................. 106 5.3. Resultados del reconocimiento de patrones para las veinte aplicaciones . . . . . . . 124 5.4. Comparación de la caché SDRAM con y sin prebúsqueda, suponiendo una SDRAM idealconumbraldeolvido............................... 139 5.5. Comparación de la caché SDRAM con y sin prebúsqueda, suponiendo una SDRAM conconguración16/4.................................. 142 5.6. Comparación de la caché SDRAM con y sin prebúsqueda, suponiendo una SDRAM conconguración64/8.................................. 144 D.1. Algunos resúmenes sobre el perl de utilización de memoria de las aplicaciones . . 178 9 16 ÍNDICE DE FIGURAS Agradecimientos Me gustaría dedicar unas palabras de agradecimiento a aquellas personas y entidades que me han brindado su apoyo a lo largo de la realización de este Trabajo de Fin de Grado. En primer lugar, al Grupo de Investigación Reconocido Caracterización de Materiales y Dispositivos Electrónicos de la Universidad de Valladolid, y especialmente a Benjamín Sahelices Ferna«dez y Helena Castán Lanaspa, por abrirme las puertas del GIR y permitir una colaboración en una tarea investigadora que ha sido (casi) siempre de lo más placentera. Gracias también a Helena por su enorme preocupación e interés por mi carrera académica, pues he podido aprovechar oportunidades importantes gracias a la información que me ha proporcionado desde el principio. A mi familia, con especial dedicatoria a mi madre, mi tía, y mi hermana. Mi madre, Beatriz, por apoyarme en esta etapa académica que llega a su n y por reforzar mi libertad tanto en mis elecciones académicas como personales. A mi hermana, Patricia, por llenar de alegría los días que no tenían tanta; me esforzaré por seguir siendo el referente por el que me tomas. A mi tía, Virginia, por ofrecerse a arreglar conmigo cualquier problema que se presentara, por enseñarme la mejor manera de buscar soluciones, y por ayudarme a comprender que mis límites estaban mucho más allá de lo que podía imaginar. Gracias a todos por ese toque de cariño que todo el mundo debería tener. A mis compañeros de clase y grandes amigos, Raúl e Irene. Habéis conseguido que el paso por la Universidad haya sido realmente divertido. Su cercanía, sincera amistad e inolvidables momentos han hecho que tanto el desarrollo de este TFG como toda la carrera haya sido de lo más llevadera, incluso en las épocas de exámenes. A Irene, por estar siempre dispuesta a prestar ayuda y compartir todo el material. A Raúl, por hacerme reír hasta en las clases más duras y enseñarme ese lado despreocupado tan necesario hoy en día. Os agradezco de corazón vuestro apoyo, y sabed que yo también estaré cuando me necesitéis. Sobre todo, a Manuel Jiménez. Gracias por tu paciencia, tu comprensión, tu apoyo incondicional y tu ayuda sea cual sea el momento en el que la pida. Te agradezco que hayas sido una fuente de inspiración tan valiosa y toda la energía que me has transmitido. No olvidaré todas aquellas ocasiones en las que te has preocupado más por mi bienestar que por el tuyo propio. También a Cristina Rueda Sabater, catedrática en el departamento de Estadística e Investigación Operativa. Sus ideas y correcciones sobre la parte más estadística de este trabajo han sido muy valiosas para mí. Gracias por dedicar una parte de tu tiempo en ello y en otros 17 18 ÍNDICE DE FIGURAS tantos consejos y opiniones. Por último, me gustaría dar las gracias a Benjamín Sahelices Fernández por acogerme bajo su tutela en este TFG, por el trato tan personal y amigable desde el comienzo, por la transparencia con la que habla y expone su punto de vista, por la ayuda y el tiempo dedicado cada vez que surgían dudas, por la alegría y pasión desprendida de esas reuniones semanales, y en denitva por todas las oportunidades que me han sido ofrecidas. Abstract The resistive switching phenomenon has been studied for many years, and it is a eld of greatest interest in technology and science. Memories based on this phenomenon, known as Resistive RAM or RRAM, are quite promising to replace Flash memories and classical SRAM and DRAM. Some of their advantages are their density, speed, power consumption, and durability. RRAM memories are non-volatile, which means no energy is needed to keep the information in a consistent state. Their density allows us to design one-terabyte capacity memories, and even more. The growing number of applications that demand large amounts of memory (for example, those related to Big Data ) serves as motivation in this invetigation. The main drawback is that RRAM technology is ten times slower than current DRAMs. If we consider a traditional DRAM memory, faster but smaller, as a cache of an RRAM, we could provide faster access without renouncing the advantages of these resistive memories. The main goal of this work is to provide an architecture where an SDRAM is congured as a cache over an RRAM. The system we shall design will also include a prefetching technique, that analyzes past memory access and tries to predict which lines will be used in the future, in order to shorten the global access time. Specically, the prefetching technique is divided into two phases. The rst one tries to pull apart memory zones attending their behavior, while the second one predicts the near-future of all these zones. In Chapter 2 we discuss how a cache works, as well as the basic organization and operations of conventional DRAMs. In Chapter 3 we present the data that we are going to use in the rest of the work and the software we use to collect this information. In Chapter 4 we will use clustering algorithms to group applications attending their behavior, measured in terms of temporal locality and algorithmic locality. Finally, in Chapter 5, the prefetching system will be presented, which is based on hidden Markov and linear models. 19 20 ÍNDICE DE FIGURAS Resumen Aunque el fenómeno de la conmutación resistiva es conocido desde hace bastante tiempo, es de gran interés en la actualidad, tanto en el campo cientíco como tecnológico. Unas memorias basadas en este fenómeno, conocidas como Resistive RAM o RRAM, son unas de las más prometedoras para sustituir tanto a las memorias no volátiles Flash como a las volátiles SRAM y DRAM. En gran parte se debe a las buenas características que poseen en términos de densidad, velocidad, consumo energético y durabilidad. Las memorias RRAM son no volátiles, por lo que no necesitan energía continua para mantener la información almacenada en un estado consistente, y pueden llegar a tener capacidad de terabytes. Poco a poco se están desarrollando aplicaciones más y más exigentes, especialmente con el auge del Big Data , que requerirán capacidades muy superiores a las que podemos encontrar hoy en día. El principal inconveniente en comparación con las memorias DRAM comercializadas actualmente es que son del orden de 10 veces más lentas. Parece buena idea considerar una memoria tradicional, más rápida pero más pequeña, como una caché sobre una RRAM más grande. Esto permitiría un aumento signicativo de la velocidad de acceso sin renunciar a las ventajas de las memorias resistivas. Lo mencionado establece el objetivo principal de este Trabajo Fin de Grado: determinar una pequeña arquitectura que permita congurar una memoria SDRAM sobre una memoria RRAM. El sistema que se pretende construir no sólo describirá la memoria SDRAM como caché de una RRAM, sino que el grueso del trabajo pasa por desarrollar una técnica de reconocimiento de patrones para predecir los accesos futuros y reducir el tiempo global del sistema. Concretamente, este sistema de prebúsqueda, aunque se detallará más adelante, pasa por distinguir patrones de comportamiento en los accesos, asociados con las zonas de memoria donde se producen, y examinar cada uno de ellos por separado. En el Capítulo 2 se abordan temas relacionados con la tecnología de las memorias, necesario para comprender correctamente el resto de la memoria. En el Capítulo 3 se encuentra una descripción sobre cómo se obtienen los datos necesarios para el diseño de esta prebúsqueda. En el Capítulo 4 se emplean técnicas de clustering para agrupar diferentes aplicaciones de las que se tienen datos en función de la localidad temporal y algorítmica. Finalmente, en el Capítulo 5 se desarrolla un procedimiento de reconocimiento de patrones y un sistema de prebúsqueda basado en un modelo oculto de Markov y diversos modelos lineales. 21 22 ÍNDICE DE FIGURAS Capítulo 1 Introducción y objetivos El presente Trabajo Fin de Grado es un trabajo de Investigación de la rama de Arquitectura de Computadores, realizado en colaboración con el Grupo de Investigación Reconocido Caracterización de Materiales y Dispositivos Electrónicos. Concretamente, se encuadra en una de las líneas de investigación más importantes de dicho GIR, dedicada a la caracterización de materiales para dispositivos de conmutación resistiva. Aunque el fenómeno de la conmutación resistiva es conocido desde hace bastante tiempo, es de gran interés en la actualidad, tanto en el campo cientíco como tecnológico. Unas memorias basadas en este fenómeno, conocidas como Resistive RAM o RRAM, son unas de las más prometedoras para sustituir tanto a las memorias no volátiles Flash como a las volátiles SRAM y DRAM. En gran parte se debe a las buenas características que poseen en términos de densidad, velocidad, consumo energético y durabilidad [1]. Los fenómenos de conmutación resistiva han sido principalmente observados en diversas estructuras metal-óxido-metal (MIM) y metal-óxido-semiconductor (MIS). La causa de este fenómeno es la creación de un nano-lamento conductor que conecta dos electrodos. Estos lamentos pueden romperse y formarse de nuevo mediante la aplicación de un potencial externo. Existen entonces dos diferentes estados resistivos (baja y alta resistencia), y el dispositivo puede permanecer en el mismo estado durante un largo período de tiempo. Esto motiva una de las características principales de las RRAM: la no volatilidad. Se plantean muchos interrogantes acerca del origen de los mecanismos de conducción y de la conmutación resistiva. Por consiguiente, antes de abordar el uso comercial de las RRAM, es necesario resolver algunos aspectos fundamentales, como la existencia de uctuaciones en los diferentes estados resistivos, responsables de la variabilidad entre ciclos y entre dispositivos. Existen en la literatura numerosos artículos sobre memorias resistivas que intentan dar respuesta a estos y otros muchos interrogantes. Desde hace algún tiempo se ha venido estudiando el incremento y decremento gradual de la resistencia en los dispositivos RRAM cuando se aplican señales adecuadas [3]. Las investigaciones más importantes pasan por la demostración de que estos dispositivos se pueden comportar exactamente como elementos de una memoria analógica y 23 24 CAPÍTULO 1. INTRODUCCIÓN Y OBJETIVOS estudios exhaustivos sobre el fenómeno de conmutación resistiva en diferentes materiales. Pocos investigadores han prestado atención a los cambios en la capacitancia durante la conmutación entre estados. Éstos y las variaciones en la admitancia proporcionan información importante para diferenciar los materiales más utilizados en la construcción de estos dispositivos. En [3] se presenta un análisis completo de los estados intermedios que pueden sufrir las memorias resistivas, en función de la admitancia. En [4] se estudian las diferentes formas de controlar la conductancia en estados intermedios de las RRAM. En [2] se presenta un estudio de las estructuras MIM y los cambios que sufren entre los dos estados en términos de la conductancia y susceptancia. Además de estos problemas que necesitan ser resueltos antes de producirse el salto a las memorias no volátiles, existe otro pequeño inconveniente. Aunque las RRAM tienen una mayor densidad de almacenamiento y puedan alcanzar tamaños mucho mayores que las actuales DRAM del mercado, son del orden de diez veces más lentas. Por ello, este trabajo de investigación se centra en cómo podemos combinar las memorias resistivas con otras memorias tradicionales, más pequeñas pero más rápidas, para acelerar el sistema de memoria en general. Las memorias RRAM pueden llegar a tener capacidad de terabytes. Poco a poco se están desarrollando aplicaciones más y más exigentes, especialmente con el auge del Big Data , que requerirán capacidades muy superiores a las que podemos encontrar hoy en día. Parece buena idea considerar una memoria tradicional, más rápida pero más pequeña, como una caché sobre una RRAM más grande. Esto permitiría conservar las grandes ventajas de las RRAM, como su gran capacidad y la no volatilidad, y simultáneamente aumentar las velocidades de acceso. Dada la capacidad de las RRAM, una memoria SDRAM de unos 16GB (un tamaño de lo más popular en los ordenadores personales de hoy en día) puede congurarse sobre una RRAM, e ir almacenando los accesos más frecuentes, de forma que no sea necesario esperar a que la RRAM proporcione la información. De la misma forma que los procesadores disponen de un sistema de caché sobre las memorias RAM, ésto permitiría un aumento signicativo de la velocidad de acceso sin renunciar a las ventajas de las memorias resistivas. La conguración de las memorias caché se aprovecha de dos fenómenos muy conocidos: la localidad temporal y la localidad espacial. Por un lado, la primera nos dice que, una vez accedida una porción de memoria, es muy probable acceder de nuevo a ella en un corto período de tiempo. Por ello, el almacenamiento de esta información en una caché más rápida permite el acceso a información repetida de forma eciente. Además, también existe la localidad espacial, que arma que la probabilidad de acceder a posiciones de memoria cercanas a corto plazo es muy alta. Ésta es bastante más complicada de analizar y medir que la anterior, puesto que no hay que prestar atención a lo que ocurre en la misma porción, sino a las zonas cercanas anteriores y posteriores a ella. El aprovechamiento de la localidad temporal pasa simplemente por el almacenamiento de la información en una caché de forma temporal, hasta que haya pasado suciente tiempo o abandone su posición en favor de otras porciones más recientes. La localidad espacial se puede aprovechar de varias formas. Por un lado, muchos sistemas no sólo traen una porción de memoria a la caché 25 cuando es requerida, sino que también actúa sobre las adyacentes. Otros sistemas más sosticados pasan por la implementación de un pequeño sistema de prebúsqueda que analiza los accesos a memoria e intenta predecir cuáles serán los siguientes. La gran mayoría de los sistemas de prebúsqueda recientes son algo básicos, priorizando la facilidad de implementación y cálculos sencillos [5]. Las cachés más utilizadas están en un nivel muy cercano al procesador, la demanda de información es extremadamente alta, y no pueden permitirse cálculos y técnicas complejas, puesto que el tiempo entre dos accesos es muy limitado. Sin embargo, esta situación no se asemeja a la jerarquía que se propone en este trabajo. Al trabajar al nivel de memorias RAM, muchos accesos quedan enmascarados por los aciertos en las cachés superiores, por lo que el examen del patrón de accesos es más complicado al disponer sólo de información parcial. Como ventaja se tiene que el tiempo disponible para procesar la información y llevar a cabo la prebúsqueda es mucho mayor. Por ello, podemos considerar técnicas más sosticadas que las actuales, con más cálculos y operaciones, a cambio de más precisión. Lo mencionado establece el objetivo principal de este Trabajo Fin de Grado: determinar una pequeña arquitectura que permita congurar una memoria SDRAM sobre una memoria RRAM. El sistema que se pretende construir no sólo describirá la memoria SDRAM como caché de una RRAM, sino que pasa por el diseño de un mecanismo de prebúsqueda para predecir los accesos futuros y reducir el tiempo global del sistema. Concretamente, este sistema de prebúsqueda, aunque se detallará más adelante, pasa por distinguir patrones de comportamiento en los accesos, asociados con las zonas de memoria donde se producen, y examinar cada uno de ellos por separado. En el Capítulo 2 se abordan temas relacionados con la tecnología de las memorias, necesaria para comprender correctamente el resto del trabajo. Existe una sección dedicada al estudio sobre la organización de las memorias caché. Aunque generalmente se piensa en una caché como aquella memoria muy rápida y cercana al procesador, la realidad es que una memoria caché es cualquier memoria que actúa sobre otra de mayor tamaño, almacenando la información más relevante, para evitar los accesos en la situada en el nivel inferior. Examinaremos, además de la organización lógica y los tipos de cachés que hay, cuáles son las políticas de reemplazo que determinan las porciones de memoria desechadas cuando ésta se encuentra llena. A continuación se proporciona una visión detallada de las memorias DRAM ( Dynamic Random Access Memory ), pasando por su organización lógica, el funcionamiento de las peticiones de acceso, los diferentes módulos de memorias DRAM existentes, la topología habitual, el protocolo de acceso y el controlador de memoria. En el Capítulo 3 se aborda la descripción de la obtención de los datos. En nuestro caso, utilizaremos una herramienta de Intel R  para monitorizar el comportamiento real de varias aplicaciones atendiendo a los accesos a memoria, llamada Intel R  Pin. Esto nos permitirá obtener un chero con información sobre las peticiones al sistema de memoria RAM, que contiene los datos sobre el momento en el que se ha producido dicha petición, la línea de memoria a la que hace referencia y el tipo de petición (lectura o escritura). Con ello podremos realizar diferentes simulaciones y probar el mecanismo de prebúsqueda sobre la arquitectura de memoria deseada. 32 CAPÍTULO 2. CONTEXTO TECNOLÓGICO Para cualquier caché, es necesario determinar las características en cuanto a tres dimensiones ortogonales: La organización de la caché: la estructura lógica que dene cómo se almacenan los datos. Las heurísticas de almacenamiento para decidir si se retiene o no un elemento en un determinado momento. Las heurísticas de consistencia que garanticen que los datos que se utilizan son los válidos en cada momento. Además, como se ha indicado anteriormente, lo normal es que haya varios niveles de memorias caché. En la gura 2.2 se muestra la jerarquía de memorias caché para la microarquitectura de Intel Nehalem, utilizada en la primera generación de los procesadores Intel Core i5 e i7 [8]. Puede comprobarse que se utiliza hasta una memoria caché de nivel 3 antes de llegar al nivel de la memoria principal. Figura 2.2: Organización de la caché de la microarquitectura de Intel Nehalem. 2.1.1. Principios de localidad Las memorias caché funcionan debido a los principios de localidad de referencia . Los procesos tienden a exhibir un comportamiento predecible en cuanto a los accesos a memoria, de lo cual podemos aprovecharnos para el diseño de las heurísticas de almacenamiento de información en una caché más pequeña que la memoria a la que sirve. Es conveniente destacar que los fenómenos de localidad no están garantizados; tan sólo son comportamientos que tienden a tener la mayoría de los procesos. Existen fundamentalmente tres principios de localidad: 2.1. MEMORIAS CACHÉ 33 Localidad temporal : es la tendencia de los programas a utilizar los mismos datos en períodos próximos de tiempo, lo que puede proporcionar una evidente heurística para la gestión de los datos de una memoria caché: almacenarlo por si es requerido en un futuro próximo. La única limitación es el tamaño de la memoria. Localidad espacial : es la tendencia de los programadores y compiladores a agrupar objetos relacionados en espacios de memoria consecutivos. Como consecuencia, parece conveniente agrupar los datos en bloques de caché , mayores que un único elemento, de manera que cuando se solicita un dato concreto, se eleva todo el bloque que lo contiene, consiguiendo que los elementos cercanos se consideren también. Localidad algorítmica : en muchos casos se tiene un comportamiento predecible que no se puede explicar con ninguno de los principios anteriores. Supongamos un programa que accede repetidamente a varias estructuras de datos de forma intercalada que se encuentran consecutivamente en memoria (por ejemplo, puede pensarse en dos vectores ordenados que se combinan en uno solo). El comportamiento del programa es predecible, pero no puede ser capturado con la localidad temporal (no se vuelve a acceder a la misma posición de memoria) ni tampoco enteramente con la espacial (pues se accede a los dos vectores intercaladamente). Esta localidad es típica en aplicaciones que realizan operaciones repetidas sobre grandes conjuntos de datos que se almacenan en estructuras dinámicas y no cambian en períodos cortos de tiempo (por ejemplo, el algoritmo Z-buer ). 2.1.2. Organización lógica La organización lógica dene cómo se almacenan los datos en una caché. Una caché almacena cadenas de datos que se llaman bloques de caché . Cada elemento es referenciado con una dirección de memoria que se puede dividir en dos zonas: el ID del bloque, y el desplazamiento dentro del bloque (gura 2.3). Como la caché sólo maneja bloques, los datos se mueven a este nivel. Figura 2.3: Dirección de memoria que se divide en ID de bloque y desplazamiento dentro del bloque. La caché está compuesta por varias entradas, donde cada una de ellas almacena la siguiente información: 34 CAPÍTULO 2. CONTEXTO TECNOLÓGICO La etiqueta de la caché. Puesto que una caché es mucho más pequeña que la memoria a la que sirve, se necesita algún mecanismo que permita identicar si un cierto elemento está o no almacenado en la caché. Para esto sirven las etiquetas: hacen referencia a un grupo de bloques e indica qué elemento se almacena en la entrada correspondiente. Bits de estado que, entre otras cosas, indican si la entrada está vacía o contiene datos inválidos o que deben sobreescribirse. Los datos . Dado que la caché tiene capacidad para almacenar más de un bloque, es necesario determinar en qué lugar se pueden encontrar los datos correspondientes a un ID de bloque. Para ello, se dene un conjunto como una lista de posibles entradas de caché, de manera que cada bloque está asociado a un único conjunto. Para asegurar esta condición, el número de conjunto se elige a partir de ciertos bits del ID de bloque, como se indica en la gura 2.4. Una vez que se ha determinado el número de conjunto para un cierto ID de bloque, los datos se almacenarán únicamente en la lista de entradas que se corresponden con ese conjunto. Nótese que sólo es necesario almacenar el campo etiqueta en la entrada de la caché para hacer referencia a un bloque. Figura 2.4: División de una dirección de memoria considerando las partes del ID del bloque En este contexto, surgen varias maneras de organizar una caché: Una memoria de mapeo directo está compuesta por tantos conjuntos como posibles bloques, de manera que cada bloque tiene un único conjunto que no comparte con otros bloques. Una memoria totalmente asociativa tiene un único conjunto, por lo que todos los bloques se encuadran en el mismo y no es posible conocer a priori si un bloque se encuentra en la caché a menos que se recorran todas las entradas. Una memoria asociativa por conjuntos tiene más de un conjunto, donde cada uno incorpora más de un bloque. De esta manera se tiene una idea de dónde se puede encontrar un bloque, sin recorrer todas las entradas posibles. En la gura 2.5 se puede encontrar una memoria caché de 512 KB asociativa por conjuntos de nivel 4: se pueden almacenar hasta 4 bloques de datos que pertenecen al mismo conjunto. Además es especialmente importante el problema de mantenimiento de la consistencia. Cuando se modica un dato cualquiera en la memoria caché hay dos formas de hacer permanente dicho cambio, lo que da lugar a las dos políticas de escritura que se describen a continuación. 2.1. MEMORIAS CACHÉ 35 Figura 2.5: Memoria caché L2 de 512 KB congurada como asociativa por conjuntos de nivel 4. La política write-through escribe inmediatamente en el nivel inferior la modicación realizada, para que esté disponible la versión actualizada para todos los procesos que lo soliciten. Esta solución pasa por un aumento del tiempo y coste (ancho de banda, consumo energético), al ser obligatorio realizar todas las escrituras en el nivel inferior. La política write-back almacena información en la entrada correspondiente de la caché (a través del dirty bit ) que indica que ese dato debe hacerse permanente en el nivel inferior, pero aún no se ha realizado el reemplazo. Esta política se aprovecha de los principios de localidad explicados anteriormente, puesto que si una aplicación ha escrito un cierto dato, es muy probable que vuelva a usarlo en un futuro cercano. En este caso, si se produce una reescritura posterior, no tendría sentido hacer dos escrituras en el nivel inferior cuando se puede realizar sólo una. La desventaja principal es que, si estamos hablando de un sistema multiprocesador, es posible que si cada uno mantiene una caché diferente, se pueda acceder a alguna versión obsoleta de la información al no hacerse persistente inmediatamente. 2.1.3. Políticas de reemplazo Las políticas de reemplazo de una caché proporcionan una heurística para desechar bloques en la caché en pos de otros nuevos. En una caché las entradas se van llenando progresivamente y, cuándo la memoria está llena, es necesario desechar una entrada para poder guardar otra nueva. Al desechar una entrada se puede hacer de dos formas: silenciosamente o con reemplazo. Si el bloque de caché ha sido modicado (esto es, el dirty bit está activado) y ese mismo bloque es el objetivo del algoritmo de reemplazo, es necesario escribir la nueva información en memoria principal. Si, contrariamente, no se ha modicado la información, basta con desechar la entrada sin más (es silenciosa). Una memoria caché con mapeo directo no necesita de un algoritmo para la selección de víctima. Cada bloque sólo puede ser ubicado en una posición, por lo que si la entrada está ocupada es necesario desechar lo que contiene. En una memoria totalmente asociativa las entradas se van llenando hasta que no se permitan más entradas, y es en este caso cuando hay que seleccionar una víctima de entre todas las entradas de la caché para ser sustituida por el nuevo bloque. 36 CAPÍTULO 2. CONTEXTO TECNOLÓGICO En una memoria asociativa por conjuntos, cada bloque de datos tiene una serie de entradas donde se puede ubicar. Un nuevo bloque se ubica en una entrada cualquiera del conjunto asociado, siempre que haya entradas libres. En caso de que todas estén ocupadas, el algoritmo para la política de reemplazo debe entrar en juego de nuevo. Hay muchos criterios para denir diferentes políticas de reemplazo. El más eciente sería aquel que descarta la información que no se va a necesitar más, o que más va a tardar en utilizarse. A este simple pero inalcanzable algoritmo se le conoce como el algoritmo óptimo de Bélády . Dado que es imposible conocer el futuro, es necesario buscar otras heurísticas basadas en alguna regla que funcionen bien en la práctica. Las más conocidas y utilizadas se listan a continuación [15]. First In First Out (FIFO) . Al utilizar este algoritmo la caché se comporta como una cola FIFO. Sin importar cuántas veces se ha utilizado, se desechará el bloque que lleve más tiempo en el conjunto correspondiente de la caché. Last In First Out (LIFO) . El comportamiento de la caché aquí es el contrario a la cola FIFO: se desechará el último bloque que ha sido traído en lugar del primero. Least recently used (LRU) . Se descarta la entrada que lleva más tiempo sin usarse. Para poder aplicar LRU se necesita mantener información sobre la última vez que se utilizó un bloque, y hacer una búsqueda en el momento del reemplazo para encontrar la más inactiva. Es más caro de implementar, aunque funciona muy bien en la práctica. Time aware least recently used (TLRU) . Es una variante del LRU para cachés que almacenan bloques con un tiempo de vida limitado, y que añade un concepto nuevo a cada entrada de la caché: TTU (Time To Use). El TTU para cada entrada dene el tiempo de vida que resta a esa entrada antes de ser desalojada obligatoriamente. El TLRU da prioridad para desalojar aquellas entradas con un TTU pequeño. Most recently used (MRU) . A diferencia del LRU, el algoritmo de reemplazo MRU desecha el último bloque usado. Aunque puede sonar contradictorio, Chou & DeWitt [19] mostraron que, cuando una estructura de datos es accedida repetidamente con un patrón de bucle secuencial, MRU es el mejor algoritmo de reemplazo. Funciona bien si la probabilidad de acceder a un elemento es mayor cuanto más antiguo sea. Random replacement (RR) . Como su nombre indica, la víctima se elige al azar de entre todas las posibles. Least frequently used (LFU) . Funciona de forma similar a LRU, aunque ahora, en lugar de almacenar el momento del último acceso, contamos cuántas veces ha sido accedido cada bloque. El elemento desechado es el que menos veces ha sido utilizado. 2.2. VISIÓN GENERAL DE LAS MEMORIAS DRAM 37 2.1.4. Inclusión y exclusión Ya hemos visto cómo la jerarquía de memoria establece una partición vertical sobre las diferentes memorias que existen en un sistema. Sin embargo, dentro de un mismo nivel, es posible hacer particiones horizontales. En el caso de tener una partición horizontal en un nivel de caché se denomina cache multi-lateral . Un ejemplo de partición horizontal es la organización de la memoria en bancos, de lo que hablaremos más en detalle en secciones posteriores. Otra posibilidad es incluir varias memorias complementarias en un mismo nivel, cada una con un propósito. Mientras que la partición vertical se utiliza para conseguir accesos más rápidos a memoria mediante los procedimientos descritos anteriormente, las particiones horizontales sirven para controlar la energía que se consume en un determinado nivel mediante la utilización de la partición más adecuada en cada caso. Los principios de inclusión y exclusión denen las relaciones existentes entre dos particiones cualesquiera de la jerarquía de memoria, independientemente de su posición vertical u horizontal. Por supuesto, son posibles esquemas híbridos a medio camino entre los dos. Una relación de inclusión garantiza que cualquier elemento en una cierta partición tiene una copia en otra. Puede que el lector piense que es una pérdida de tiempo y de recursos almacenar dos veces la misma información, pero recordar que acceder a un elemento en el primer nivel de la jerarquía es millones de veces más rápido que en el último debería hacerle cambiar de opinión. Una relación de este tipo además, garantiza que si se quiere sustituir una porción de memoria que se sabe se encuentra en niveles inferiores y que no ha sido modicada, basta con descartarla inmediatamente. Por otro lado, una relación de exclusión permite conocer con certeza que si un elemento se encuentra en una partición, no es posible que se encuentre en otra. El conocimiento de esta relación permite agilizar los procesos de control de la consistencia que subyacen en todos los sistemas. 2.2. Visión general de las memorias DRAM La memoria DRAM, por sus siglas en inglés ( Dynamic Random Access Memory ) es lo que se conoce como memoria principal. Todo programa, para ejecutarse, debe cargarse en memoria principal. La DRAM se conecta al procesador a través de un intermediario que se conoce como el controlador de memoria , de manera que el procesador no necesita conocer cómo se maneja el módulo de memoria concreto. Aunque hablaremos del mismo más adelante, sus funciones principales son las relacionadas con el manejo de la DRAM a bajo nivel y la más que probable compatibilidad con varios procesadores, como ocurre en prácticamente todas las arquitecturas modernas. La gura 2.6 muestra un ejemplo de las conexiones y responsabilidades del controlador de memoria. En este dibujo se muestra la CPU como un único chip en el que ya se incluyen las memorias caché correspondientes. La comunicación del procesador con la memoria se hace a través 38 CAPÍTULO 2. CONTEXTO TECNOLÓGICO de este controlador, también llamado puente norte ( North-Bridge ). Más abajo se encuentran los dispositivos de entrada y salida. En el dibujo, las conexiones SATA, USB y PCI se pueden utilizar para conectar módulos de memoria no volátiles que sirvan en el nivel más bajo de la jerarquía. Al controlador de entrada y salida se le conoce a veces como puente sur ( South-Bridge ). Figura 2.6: Esquema de organización del controlador de memoria y sus interacciones con distintos componentes [9]. 2.2.1. Celdas, arrays de memoria, bancos y ranks La DRAM es un tipo de memoria RAM que utiliza un par transistor-condensador para cada celda de almacenamiento que guarda un bit de información. La palabra dinámica hace referencia a la necesidad de refrescar continuamente la información del condensador (es decir, leer y volver a escribir el mismo bit), pues de no hacerse la información se perdería al cabo de un tiempo. Cada módulo DRAM contiene uno o varios arrays de memoria , que no son más que la organización en una matriz bidimensional de las celdas de memoria. Puesto que se organizan en las y columnas, cada celda de memoria se especica en un array de memoria mediante estos dos parámetros. El controlador de memoria es el que conoce como leer o escribir información en una posición dada. En la gura 2.7 se encuentra un ejemplo de un array de memoria de una DRAM con capacidad para 128KB de datos. Cada palabra (la) está compuesta por 512 bits (64 Bytes de datos). Además, cada celda de memoria está representada con un transistor y un condensador. Aunque en la gura no se encuentra explícitamente representado, es necesario una amplicación de la señal una vez leída la posición correspondiente. Esta estructura para las celdas de memoria ha sido la más utilizada y conocida (1T1C). Existen otras estructuras menos usadas, como la variante con tres transistores (3T1C), que tiene velocidades de lectura más altas. Son bastante más grandes que las celdas 1T1C, por lo que la 2.2. VISIÓN GENERAL DE LAS MEMORIAS DRAM 39 Figura 2.7: Organización bidimensional de un array de memoria en una DRAM [10]. mayoría de los dispositivos DRAM actuales están basados en 1T1C, priorizando la densidad sobre la velocidad. La investigación para el desarrollo de nuevas estructuras y tecnologías continúa en nuestros días. El acceso a una celda de memoria se produce mediante la activación del transistor correspondiente aplicando un determinado voltaje en la puerta de acceso. La aplicación de otro voltaje que procede, por ejemplo, de un bit que se quiere escribir en la celda, carga el condensador con la información. Sin embargo, la carga almacenada en el condensador se va perdiendo con el paso del tiempo (de ahí la necesidad de refrescarlo). Para asegurar que se mantienen los datos correctos, cada celda de memoria se debe leer y volver a escribir con la misma información a intervalos regulares de tiempo. Una celda normal puede almacenar la información correcta hasta algunos segundos. Sin embargo, es necesario garantizar que el bit representa información válida en todo momento, por lo que el tiempo habitual entre refrescos es de unos 32 o 64 milisegundos. Una forma de caracterizar un módulo DRAM es mediante el número de arrays de memoria que contiene, y cómo interaccionan entre sí: pueden actuar de forma totalmente independiente unos de otros, de la misma manera, o presentar un comportamiento por grupos. En todos los siguientes ejemplos, conviene imaginar la memoria DRAM con una tercera dimensión a partir de la gura 2.7, donde se superponen los distintos arrays de memoria. Si todos los arrays de memoria actúan de la misma forma, operan como una única unidad de memoria. Especicada una posición, se realiza la operación sobre todos los arrays de memoria existentes. Por ejemplo, si se tiene una DRAM con 8 arrays, realizar una operación 40 CAPÍTULO 2. CONTEXTO TECNOLÓGICO de lectura sobre una la y una columna lleva a la lectura de 8 bits. Si todos los arrays actúan independientemente, no basta con indicar la la y la columna, sino que también es necesario indicar cuál de todos los arrays se quiere tener en cuenta. Sobre el ejemplo anterior, equivaldría a especicar la la, columna y un número del 1 al 8 que haga referencia al array. Antes se tenía un ancho de banda de 8 bits por operación, pero ahora el ancho de banda es 1. Es posible que los arrays de memoria se agrupen por conjuntos, donde todos los arrays de un mismo conjunto operen como una única entidad, pero sean completamente independientes de los arrays de otro grupo. Si consideramos dos grupos sobre el ejemplo, tendríamos 4 arrays de memoria en cada grupo. La especicación de una operación necesita de la la, columna y el número de grupo (1 o 2), y tiene un ancho de banda de 4 bits. A cada uno de estos grupos se le conoce como banco . Cada banco de memoria es independiente y, salvo ciertas restricciones estructurales, se puede activar, precargar, leer o escribir al mismo tiempo que otros bancos. La utilización de varios bancos de memoria permite lograr anchos de banda mayores a partir de dispositivos más lentos, como hemos comprobado en el ejemplo. Los módulos de memorias DRAM se venden normalmente como DIMM ( dual in-line memory module , módulo de memoria con contactos duales). Como en general incluyen varias DRAM, cada una de ellas con una conguración de bancos potencialmente diferente, puede pensarse en bancos de DRAMs a nivel de DIMM. A esto se le conoce como rank , y cada uno de ellos se diseña para operar en exclusión mutua. Finalmente, un sistema se puede componer de distintos DIMMs, cada uno de ellos con uno o varios ranks. Cada rank es un conjunto de dispositivos DRAM que operan al unísono, aunque internamente cada DRAM puede tener una conguración de bancos de memoria. Cada uno de estos bancos está compuesto por un cierto número de arrays de memoria, y el ancho de banda de dicha DRAM es equivalente al número de arrays de cada banco. El mecanismo de ranks, bancos y arrays permite ampliar el ancho de banda con accesos paralelos a distintas celdas de memoria. En la gura 2.8 puede encontrarse un ejemplo de división de dos DIMMs, cada uno de ellos en dos ranks, donde cada rank tiene cuatro bancos. 2.2.2. Buses para comunicarse La comunicación entre el controlador de memoria y los DIMMs de un sistema tiene lugar a partir de buses que llevan la información, tanto para leer y escribir datos, como para indicar las operaciones que se quieren realizar. Los buses en un estilo de organización JEDEC se clasican por su función en cuatro grupos: Los buses de datos . 2.2. VISIÓN GENERAL DE LAS MEMORIAS DRAM 41 Figura 2.8: Organización de un par de DIMMs en ranks y bancos. Fuente: m5sim.org [11] Los buses de dirección . Los buses de control . Los buses de selección de chip . El bus de datos sirve para llevar la información que se quiere leer o escribir, y suele tener un ancho de banda suciente para llevar a cabo estas operaciones en un tiempo razonable (por ejemplo, 64 bits). El bus de dirección indica la posición como número de la y columna para una DRAM determinada, y es más ancho cuanto mayor sea el tamaño de la DRAM, lo suciente como para indexar la información. El bus de control tiene ciertos bits de información necesarios, como la señal de reloj. Por último, el bus de selección de chip es el que se encarga de seleccionar la DRAM correspondiente dentro de un rank determinado. Este bus debe seleccionar únicamente la o las DRAMs sobre la que se va a realizar la operación, por lo que debe ser tan ancho como el número de DRAMs del sistema. Aunque todas las DRAMs están conectadas al mismo bus de control y de direcciones, el bus de selección de chip evita que todas pongan una respuesta en el bus de datos (en caso de una petición de lectura, por ejemplo) activando sólamente el módulo deseado. 2.2.3. Pasos en una petición típica Consideremos una petición de lectura sobre un grupo de DIMMs en un sistema (por ejemplo, el mostrado en la gura 2.8). Los pasos que se siguen son los siguientes: 48 CAPÍTULO 2. CONTEXTO TECNOLÓGICO anchura de 36 bits que soportara comprobaciones de paridad. Fue a principios de los 90 cuando se sustituyeron por los módulos de 72 pines. Las SIMM de 72 pines, por contra, permitían una anchura de entre 32 y 36 bits en el bus de datos, además de las señales de control necesarias. El cambio fue motivado por las necesidades cada vez mayores de los ordenadores en cuanto a ancho de banda. 2.3.1.b. Dual In-Line Memory Module (DIMM) A nales de los 90 se produce una transición de las FPM DRAM a las SDRAM, lo que provoca que las SIMM de 72 pines cedan a favor de los módulos DIMM. Los DIMM son físicamente más grandes y proporcionan una interfaz para el bus de datos con anchura de 64 o 72 bits. A diferencia de las SIMM, los contactos de cada uno de los lados tienen diferentes características eléctricas. Las DIMM para los ordenadores personales suelen ser no registradas ( Unregistered DIMM o Unbuered DIMM ), y no tienen ningún registro entre la DRAM y el controlador de memoria del sistema. Esto hace que haya más carga eléctrica en el Controlador de Memoria y permite sistemas con menos módulos, en contraposición con los módulos que sí tienen este buer, más típicos de grandes servidores. 2.3.1.c. Registered Memory Module (RDIMM) A diferencia de los módulos UDIMM, para satisfacer las necesidades de memoria de servidores y estaciones de trabajo más grandes, se necesita un módulo que incluya un pequeño buer entre el DMC y los dispositivos DRAM. Tener un gran número de DRAMs tiende a sobrecargar los buses de datos y a dar problemas en la carga de la información. Los módulos que incluyen un registro que actúa de intermediario pueden solucionar este problema de sobrecarga, además de permitir una mayor exibilidad en la combinación de memorias de características o fabricantes diferentes. Un módulo RDIMM alivia la sobrecarga eléctrica provocada por un grán número de DRAMs a través de registros que almacenan temporalmente las direcciones y señales de control a nivel de interfaz del módulo. Concretamente, pueden reducir el número de cargas eléctricas que el controlador de memoria debe manejar directamente. La señal que se conecta con el sistema de memoria se divide en la parte que va desde el DMC a los bueres intermedios, y la que conecta estos registros con los dispositivos DRAM. Como punto negativo, el almacenamiento intermedio de las señales de control y direcciones de memoria en un buer introduce un paso más en la espera para servir la petición, por lo que inevitablemente la latencia de acceso se ve incrementada en todas las transacciones. Existe otro tipo de módulo, llamado Small Outline Dual In-line Memory Module (SO-DIMM) , que está diseñado y estandarizado explícitamente para ocupar poco espacio, siendo especialmente utilizado en pequeños notebooks y portátiles. 2.3. ORGANIZACIÓN DE LA MEMORIA DRAM 49 2.3.1.d. Serial Presence Detect (SPD) Desde que los módulos de memoria comenzaron a evolucionar, es inevitable que cada uno tenga sus características en cuanto a latencia de acceso a columna o a la, tiempo de precarga, o de activación de una la. Esta variabilidad en cuanto a los módulos DRAM incrementa la complejidad de diseño cuando se quiere conseguir la máxima compatibilidad posible entre diferentes módulos. No obstante, esto no siempre es posible, ya que las nuevas generaciones de dispositivos DRAM pueden tener ciertas características de diseño físicas que las hagan incompatibles con los slots actuales, o ciertas características que el DMC no está preparado para soportar. Para reducir la confusión que provoca la sustitución de módulos de memoria, cada uno de ellos viene con información sobre su conguración y parámetros de latencia que se almacena en una memoria de sólo lectura. El contenido es leído por el DMC en el proceso de inicialización para optimizar los accesos todo lo posible. Esta memoria de sólo lectura se conoce como Serial Presence Detect . 2.3.2. Topología habitual En la gura 2.11 [13] se muestra un ejemplo de sistema de memoria donde 16 dispositivos DRAM están conectados a un mismo DMC. Estas DRAM se organizan en 4 ranks. Es posible apreciar cómo las conexiones unidireccionales para pasar direcciones, el bus de comandos, el bus bidireccional de datos y el bus de selección de chip no muestran un patrón regular, y cada uno tiene sus particularidades. Figura 2.11: Topología de un sistema de memoria DRAM. Cuando se quiere realizar una operación en este ejemplo, las señales de direccionamiento y selección de comando se propagan a todas las DRAM, pero la señal de selección de chip hace que 50 CAPÍTULO 2. CONTEXTO TECNOLÓGICO sólo se active un rank determinado. Cada DRAM dentro de un rank está conectada a una parte del bus de datos en el que servir los bits leídos, por ejemplo, en una petición de lectura. La topología del sistema de memoria determina la longitud que deben recorrer las señales eléctricas y, por tanto, inuyen en gran medida en el rendimiento. La topología típica, como la presentada en el ejemplo anterior, se ha visto inalterada en el paso de las DRAM originales a las FPM, SDRAM y DDR. Un ejemplo de topología radicalmente diferente es la de un sistema Direct RDRAM , aunque no será presentada aquí. 2.4. Protocolo básico de acceso a memoria DRAM El protocolo de acceso a memoria dene todos los posibles comandos y restricciones de tiempo que el DMC maneja para el ujo de datos con las distintas DRAM. El protocolo y los comandos que se explican en esta sección están descritos bajo un marco general, puesto que cada arquitectura diferente los adapta para sacar el máximo partido a los dispositivos. Examinar completamente y con detalles el protocolo completo de acceso a memoria es complicado debido a la existencia de incontables combinaciones y ordenaciones de los comandos. Por una parte, es necesario hablar de los comandos básicos a partir de los cuáles se forman otros más complejos, así como de las interacciones entre los comandos de una DRAM básica. Ésto último permite conocer la latencia del sistema completo y otras características relevantes, como el ancho de banda. 2.4.1. Comandos básicos El protocolo de acceso a memoria DRAM asume que dos comandos se llevan a cabo simultáneamente siempre que no se requiera el uso de un recurso compartido. Por este motivo, muchas de las operaciones se superponen para reducir el tiempo necesario en un aceso de lectura o escritura. Concretamente, en un acceso a memoria se distinguen cuatro fases que se pueden superponer parcialmente en el tiempo. 1. En la fase 1, el comando concreto se transporta desde el DMC a través de los buses correspondientes, y la DRAM lo decodica cuando lo recibe. 2. En la fase 2 se tiene un ujo de datos de una la en el banco elegido dentro de la DRAM. En primer lugar, los bits almacenados en las celdas de memoria pasan al array de amplicación (los bits necesitan amplicarse para poder trabajar con ellos); posteriormente se vuelven a llevar a las celdas individuales. 3. En la fase 3 hay un ujo de datos entre la interfaz de entrada y salida (interfaz E/S) y los registros de lectura o escritura, dependiendo del tipo de operación. 2.4. PROTOCOLO BÁSICO DE ACCESO A MEMORIA DRAM 51 4. En la fase 4, si estamos manejando una petición de lectura, se colocan los datos de una columna en el bus de datos para llevarlos hasta el DMC. Si es una pertición de escritura, los datos van desde el DMC hasta la columna elegida. El protocolo de acceso a DRAM también dene una serie de restricciones temporales entre comandos consecutivos. Abstrayendo las características temporales, los comandos pueden ser descritos a más alto nivel y ser comprendidos mejor. 2.4.1.a. Comando de acceso a la El comando de acceso a la, o comando de activación de la, tiene como objetivo llevar los datos de las celdas de una determinada la hasta el array de amplicación, y después volverlos a colocar en las celdas correspondientes. Como parte de este comando, hay dos tiempos que deben tenerse en cuenta. tRDC ( Row to Column Command Delay ) es el tiempo necesario para llevar los datos desde las celdas individuales al array de amplicación. Después del tiempo tRCD es posible hacer una lectura o escritura de una columna mediante la conexión que existe entre el array de amplicación y el DMC a través del bus. Aunque tras tRCD los datos ya están disponibles, es necesario volver a cargar la la. Esta operación se puede realizar en paralelo con el movimiento de los datos a través del bus. Al tiempo invertido en el paso de los datos al array de amplicación y su retorno se le conoce como tRAS ( Row Access Strobe latency ). Tras este tiempo, se ha completado el acceso y restauración de la la, y el sistema está preparado para otro comando de acceso a la. 2.4.1.b. Comando de lectura de columna Tras el tiempo tRCD en el comando de acceso a la, es posible realizar un comando de lectura de columna. En este caso se copian los datos de los arrays de amplicación en el bus de datos para que el DMC los pueda recibir. Hay tres tiempos importantes en este comando: El tiempo tCAS ( Column Access Strobe latency ) es el tiempo que le lleva a la DRAM colocar los datos en el bus tras la recepción del comando. Como normalmente se transmiten ráfagas de datos desde la aparición de las DRAM modernas, es necesario tener en cuenta los dos tiempos siguientes. El tiempo tCCD ( Column to Column Delay ) es el tiempo invertido en el procesamiento de cada una de las pequeñas ráfagas de datos que se tienen que considerar internamente. El tiempo tBURST es el tiempo que cada ráfaga de datos permanece en el bus para que el DMC lo pueda recibir correctamente. Suele ser mayor que tCCD . 52 CAPÍTULO 2. CONTEXTO TECNOLÓGICO 2.4.1.c. Comando de escritura de columna En este comando hay un ujo de datos desde el DMC hasta el array de amplicación de la columna sobre la que se va a escribir. Las fases son similares a las del comando de lectura, pero con la dirección del movimiento de los datos invertida. Los tiempos que se deben tener en cuenta son: El tiempo tCW D ( Column Write Delay ) es el tiempo que ocurre entre la colocación de la petición para un comando de escritura en el bus de comandos y la colocación de los datos concretos a escribir en el bus de datos. Si los dos se envían a la vez, entonces tCW D = 0 . Inmediatamente tras tCW D hay que volver a tener en cuenta tBURST , el tiempo necesario que los datos deben estar en el bus hasta llegar correctamente al array de amplicación. En el caso de que después se vaya a realizar un comando de precarga debe respetarse el tiempo tW R ( Write Recovery Time ). Este es el tiempo necesario que transcurre entre la llegada de los datos al array de amplicación, y su paso a las celdas de memoria. En el caso de que después se vaya a realizar un comando de lectura debe respetarse el tiempo tW T R ( Write-to-Read Turnaround Time ). Este es el tiempo que transcurre hasta que los recursos derivados de la E/S son liberados. 2.4.1.d. Comando de precarga El acceso a datos en una DRAM es un proceso en dos pasos. En primer lugar tiene el acceso a la la que lleva los datos al array de amplicación, a lo que le sigue uno o varios comandos de acceso a columna. La segunda fase es el comando de precarga, que reestablece los sensores y arrays de amplicación y los prepara para otro acceso a la. El tiempo asociado a este reset es tRP (Row Precharge Time). Un comando de acceso a la debe hacerse tras un comando de precarga. Los dos tiempos implicados en los accesos a la, tRAS y tRP , en ocasiones se combinan mediante una suma simple para formar tRC ( Row Cycle Time ). Este es el mínimo tiempo que debe transcurrir entre dos accesos a las diferentes en un mismo banco, y constituye la mayor limitación en cuanto a las velocidades que pueden alcanzar las DRAM. 2.4.1.e. Comando de refresco Como hemos mencionado anteriormente, debido a la pérdida gradual de la carga en un condensador, los datos deben ser leídos y reescritos cada cierto tiempo para asegurar que no se pierden. Esta tarea está asociada al comando de refresco. Sin embargo, refrescar la información consume evidentemente ciertos recursos (energía y ancho de banda). El tiempo entre dos comandos de refresco consecutivos para una misma la debe ser menor que el tiempo que tarda la carga eléctrica en degradarse. El correcto uso de este comando garantiza 2.4. PROTOCOLO BÁSICO DE ACCESO A MEMORIA DRAM 53 que los datos en una determinada la son íntegros y válidos. Aunque depende del tipo de DRAM y de su arquitectura interna, típicamente se envían unos 8192 comandos de refresco cada 64 milisegundos. Habitualmente existe un registro en la DRAM que contiene la última la que se ha refrescado. El DMC envía un comando de refresco a la DRAM sin especicar una la concreta, y el propio dispositivo incrementa el contador de la en una unidad para saber a cuál toca aplicarlo a continuación. Además, el comando de refresco se realiza concurrentemente sobre todos los bancos. El tiempo invertido hasta que todos ellos llevan a cabo un refreso se conoce como tRF C ( Refresh Cycle Time ). 2.4.1.f. Ciclo de lectura Una vez que conocemos los comandos básicos en una DRAM, podemos preguntarnos cuál es el proceso completo de lectura. Un comando de acceso a la lleva muchos bits de información a los arrays de amplicación en un banco determinado. Desde ahí, un comando de lectura de columna hace que algunos de esos bits pasen al bus de datos y el DMC los pueda recibir. Tras el tiempo tRCD en el que los datos son llevados al array de amplicación, el DMC envía el comando de lectura de columna, y concurrentemente, los datos se vuelven a restaurar en las celdas de memoria correspondientes. Tras tRAS , el DMC envía un comando de precarga para preparar los arrays de amplicación para otro acceso. En ciertas aplicaciones, como en streaming a través de una DRAM, es probable que a un cierto acceso de columna le siga un acceso a la siguiente (localidad espacial). En estos casos, hacer que los bits permanezcan en los arrays de amplicación evita una operación innecesaria de acceso a la. Los sistemas de memoria con este comportamiento se conocen como open-page . Por otro lado, en aplicaciones donde estas situaciones no se suelen dar, se preere utilizar sistemas de memoria close-page que llevan a cabo un comando de precarga inmediatamente después del acceso a la, para preparar el sistema para otro acceso. 2.4.1.g. Ciclo de escritura Un ciclo de escritura es similar al de lectura, pero con la salvedad de que los datos que se vuelven a colocar en las celdas de memoria en el proceso de recuperación son distintos. Los datos son colocados en el bus por el DMC y pasan a través de la interfaz de E/S hasta llegar al array de amplicación y, después, a las celdas de memoria. La consecuencia directa de esto es que el tiempo de un ciclo de la está restringido por el tiempo del ciclo de escritura. Un ciclo de la se dene como la mínima cantidad de tiempo que tiene que transcurrir para que una DRAM pueda proporcionar el acceso a cualquier la de cualquier banco. Todas las acciones relacionadas con la escritura deben ser llevadas a cabo antes de que el comando de acceso a la termine, para poder hacer persistentes los datos, y antes de que el comando de 54 CAPÍTULO 2. CONTEXTO TECNOLÓGICO precarga se lleve a cabo. Formalmente, tRAS debe ser sucientemente amplio como para vericar tRAS ≥tRCD +tCW D +tCCD +tW R . 2.4.1.h. Comandos compuestos A lo largo de la evolución de las DRAM, poco a poco se han ido diseñando comandos más complejos a partir de ciertas combinaciones de los básicos. Un ejemplo es el comando de lectura de columna y precarga en los sistemas close-page . La precarga inmediata permite que el DMC pueda colocar otro comando de acceso a la en el bus de comandos inmediatamente después, ya que de lo contrario habría que enviar una señal de precarga igualmente. Otro ejemplo de comando complejo es el comando de acceso retardado a columna. No es más que un comando de acceso a columna que se pospone un cierto número de ciclos en el dispositivo DRAM. La ventaja es que el DMC puede colocar el comando de acceso a columna inmediatamente después del de acceso a la (en caso contrario debería esperar un cierto tiempo), lo que simplica el diseño del controlador de memoria. 2.4.2. Interacciones entre comandos Hasta ahora sólo hemos tenido en cuenta la utilización de los recursos disponibles para determinar si dos comandos se pueden solapar en el tiempo o no. Sin embargo, no es la única limitación, pues incluso es posible que no esté permitido ejecutar un comando después de otro concreto en ciertas circunstancias. Las interacciones posibles entre diferentes comandos son necesarias en los sistemas DRAM modernos, especialmente en los open-page . La solicitud de un comando en estos sistemas depende del estado actual de la DRAM, y las posibilidades de interacción son también mayores. Como ya se ha descrito anteriormente, los comandos de lectura de columnas consecutivas en un mismo rank, banco y canal se pueden combinar con ráfagas. Para ello, tBURST debe ser mayor que tCCD , para asegurar que la ráfaga se transmite correctamente antes de pasar a la siguiente. De igual forma, también se pueden programar comandos de escritura consecutivos. Otro ejemplo de interacción delicada es el comando de precarga inmediatamente después del de lectura de una columna. Si no se respeta el tiempo suciente como para colocar los datos en el bus de datos, y se resetea el array de amplicación antes de tiempo, los datos leídos por el DMC no serán correctos. El tiempo tRT P es lo mínimo que hay que esperar entre un comando de lectura y de precarga. Por otro lado, las lecturas de diferentes las en un mismo banco necesitan varios comandos de acceso a la, con el correspondiente incremento de coste en comparación con accesos a columnas de una misma la. Para cada nueva la, los datos de toda ella deben ser llevados a los arrays de amplicación, además del comando de precarga. En el mejor caso se puede realizar el comando 2.5. CONTROLADOR DE MEMORIA DRAM 55 de precarga inmediatamente después del anterior acceso a la. Sin embargo, estamos suponiendo que ha transcurrido un tiempo tRAS desde el último acceso, necesario para que los datos se hayan devuelto a sus correspondientes celdas. En caso contrario, hay que esperar hasta que tRAS se complete antes de hacer la precarga. Es especialmente interesante el caso de múltiples comandos de lectura o escritura sobre diferentes ranks . En una lectura es posible que las diferentes peticiones no se puedan paralelizar, dependiendo del mecanismo de sincronización del sistema de memoria. En una escritura, por contra, se puede paralelizar dependiendo de las conexiones del bus. Si se producen simultáneamente varios comandos de lectura de columna a varios ranks, cada uno de ellos debe tomar el control del bus compartido, colocar los datos, y devolver el control para que otro rank lo tome. Las escrituras tienen más potencial de ser concurrentes puesto que es el DMC el único que mantiene bajo control el bus y no necesita cedérselo a ningún otro componente. Otras situaciones que deben ser consideradas en el diseño de un sistema de memoria, aunque no serán explicadas en este texto con más detalle, son los comandos de escritura consecutivos en un banco , escritura inmediatamente tras una lectura y viceversa. Además de las restricciones de tiempo que existen, de las cuáles sólo se han mencionado unas pocas, existen otros factores que limitan la capacidad de actuación de las DRAM. Un ejemplo es que, a medida que avanzan las investigaciones sobre nuevas memorias con mejores prestaciones, también lo hace la cantidad de energía que consumen y cada vez en mayor medida. Operar a mayor velocidad cuesta más, y en muchas ocasiones los propios ingenieros limitan el consumo de las DRAM y, con ello, sus capacidades reales. 2.5. Controlador de memoria DRAM El controlador de una memoria DRAM, o DMC, tiene la responsabilidad de manejar internamente los dispositivos DRAM conociendo sus especicaciones concretas acerca de sus tiempos de respuesta, señales eléctricas, etc. El diseño de los DMC determina algunas de las características más relevantes de un sistema de memoria, como la latencia o el ancho de banda. 2.5.1. Arquitectura del controlador de memoria DRAM La principal función del DMC es servir de interfaz para el acceso y escritura de los datos. Su diseño es complejo, debido a la complejidad intrínseca del protocolo de acceso a DRAM. Un DMC se puede diseñar para minimizar el tamaño de las DRAM, su consumo eléctrico, maximizar el rendimiento, o alcanzar un equilibrio. Concretamente, en el diseño e implementación del DMC, son particularmente importantes los siguientes aspectos: Políticas de manejo de buer de la. 56 CAPÍTULO 2. CONTEXTO TECNOLÓGICO Figura 2.12: Arquitectura de un controlador de memoria DRAM. Fuente: [14]. Esquema de traducción de direcciones de memoria. Ordenación de los comandos DRAM y transacciones de memoria. Serán explicados posteriormente en esta sección. La gura 2.12 muestra los componentes básicos de un DMC. Tanto la CPU como los dispositivos de E/S pueden realizar peticiones al DMC. Estas peticiones pasan primero por un árbitro que decide sobre la planicación y coloca las peticiones en una cola. La planicación puede ser de lo más variada. Por ejemplo, una petición de baja prioridad puede ser seleccionada sobre una de más prioridad si se realiza sobre la la actualmente activa en un sistema open-page . Cuando una petición gana el arbitraje y entra al DMC, se traduce a los comandos básicos de DRAM vistos en la sección anterior, que se colocan en una cola que maneja el DMC. Esta cola puede ser genérica para todo el sistema de memoria, o puede haber una cola para cada rank o cada banco. Cuando un comando está listo para ejecutarse, se envía la señal a cada DRAM. 2.5.2. Políticas de manejo de buer de la Los arrays de amplicación en una DRAM pueden actuar como buers que almacenan los datos de una la. Existen dos políticas que ya han sido mencionadas anteriormente: open-page y close-page . Los sistemas open-page se benecian de la localidad de los programas y no llevan a cabo una precarga tras un acceso a la. Sólamente se resetean los arrays de amplicación en un acceso a otra la diferente. En contraposición, los sistemas close-page se benecian de procesos con baja localidad, localidad poco predecible, o con pocos accesos a memoria. No obstante, es conveniente mencionar algunas políticas híbridas que no adoptan un enfoque tan estricto como los sistemas open-page o close-page . Algunos procesos pueden exhibir cambios en la localidad dependiendo del momento de ejecución, y la utilización de la historia de ejecución 2.5. CONTROLADOR DE MEMORIA DRAM 57 del programa parece relevante para decidir el mejor modo de acceso. Dos modos de implementar una política híbrica, aunque existen más, son los siguientes. Llevar un contador del número aciertos y fallos de la consecutivos. Un acierto de la es cuando se accede a la misma la que el acceso anterior, mientras que un fallo es evidentemente la situación contraria. Si en un momento dado el sistema funciona como open-page , pero hay un número muy elevado de fallos de la, entonces se podría pasar a un sistema close-page . Por otro lado, si estamos en un close-page pero se está accediendo repetidamente a una misma la, pasaríamos a un open-page . Utilizar un temporizador que se restablece a un valor predenido cada vez que se produce un acceso a una la distinta. Con cada ciclo de reloj, el temporizador se va decrementando en una unidad. Si llega a cero, se lleva a cabo un comando de precarga para resetear el array de amplicación. La elección del tipo de política determina en gran medida el diseño del esquema de traducción de direcciones, la ordenación de los comandos, y el mecanismo de reordenación de transacciones. Además, también provoca cambios en el rendimiento y consumo eléctrico de la DRAM. Por ejemplo, un sistema close-page puede ser adecuado si no se realizan demasiadas peticiones al dispositivo. En caso de usar un open-page , el coste de mantener los datos en el array de amplicación demasiado tiempo sin utilizarlos no compensa el coste de precarga y acceso a la. 2.5.3. Esquema de traducción de direcciones de memoria Además de las políticas de manejo de la, la forma en la que se traduce una dirección de memoria para determinar su ubicación física afecta directamente al rendimiento del sistema completo. Cuando el DMC recibe una petición sobre una dirección concreta, tiene que convertir esa información en términos de cuál es el canal, rank, banco, la y columna donde están los datos. A este proceso también se le conoce como mapeo de direcciones. Consideremos el caso de un sistema de memoria donde no se da demasiada importancia al mapeo o traducción de direcciones. Es posible que una cierta aplicación solicite accesos a memoria con direcciones físicas muy parecidas, pero que resulten en distintas las de un mismo banco debido al mecanismo de traducción. Esto hace que haya muchos conictos en un mismo banco, que se producen cuando se quiere acceder a una la distinta y se necesita un comando de precarga y de acceso a la. Evidentemente, todo este proceso conlleva una disminución en el rendimiento si lo comparamos, por ejemplo, con un sistema donde el mapeo coloca datos adyacentes en distintas las de diferentes bancos. De esta última forma, el acceso se puede llevar a cabo con cierto grado de paralelismo a la vez que se minimiza la probabilidad de conictos en un banco. Al contrario que las políticas de manejo de buer de las, un mapeo de direcciones no puede ir cambiando sobre la marcha y se necesita decidir a priori. En los subsiguientes 64 CAPÍTULO 2. CONTEXTO TECNOLÓGICO Capítulo 3 Accesos a memoria fuera del chip Una vez detalladas las características más importantes de las memorias caché y de las memorias DRAM, vamos a describir las herramientas software necesarias para la obtención de datos sobre accesos a memoria. En el proyecto que nos atañe, vamos a utilizar la herramienta Intel R  Pin para simular un sistema que esté compuesto por tres niveles de memoria caché (véase la gura 3.1). Supondremos un sistema multiprocesador donde cada una de las CPU tiene una memoria caché L1 y una L2. Una caché de último nivel (LLC) sirve a todos los procesadores. Figura 3.1: Esquema de la simulación y nivel de monitorización de Pin Durante la ejecución normal de un programa cualquiera, si se necesita un dato que no está presente en la LLC, es necesario acceder al nivel inferior de la jerarquía de memoria donde se encuentra la RAM. Ahora mismo no es relevante qué tipo de memoria RAM constituye el sistema de memoria ni cómo esté organizado. 65 66 CAPÍTULO 3. ACCESOS A MEMORIA FUERA DEL CHIP Pin se utilizará para monitorizar las peticiones que se hagan al sistema de memoria debidos a fallos de caché. El objetivo es disponer de un chero de datos con el histórico de las operaciones enviadas al DMC. Con esta información es posible realizar simulaciones de diferentes esquemas de memoria principal, y concretamente la que nos interesa en este trabajo: una SDRAM sobre una RRAM. Las operaciones que se pueden llevar a cabo sobre el sistema de memoria principal son las siguientes: Operación de lectura. Si en un cierto momento se necesita un dato que no está en ninguno de los niveles de caché, se necesita realizar una operación de lectura sobre la memoria principal. Operación de escritura. Si se necesita escribir un cierto dato que no se encuentra presente en la memoria caché, hay que realizar una petición de escritura al sistema de memoria. Una operación de reemplazo tiene lugar cuando un elemento de la caché LLC marcado con el dirty bit (esto es, contiene información modicada que aún no se ha hecho persistente en memoria principal) es desalojado de la misma. Es necesario realizar una operación de escritura sobre el sistema de memoria para garantizar la persistencia de la información modicada. Las operaciones de lectura y de escritura serán las más interesantes, pues reejan el verdadero comportamiento de la aplicación. En una operación de lectura se elevan los datos y porciones cercanas a la memoria caché, desalojando otras entradas si es necesario. En una operación de escritura, aunque pueda sonar contradictorio, también se produce una lectura de los datos en la memoria caché. La modicación solicitada (la escritura) se hace sobre los datos que almacena la caché, y muy raramente sobre memoria principal. Cuando esta entrada sea desalojada, dicha modicación sí se hará en memoria principal. Una razón por la que resultaría conveniente que la escritura se hiciera directamente sobre el sistema de memoria es el caso en el que se tengan múltiples sistemas trabajando sobre una memoria compartida. Para asegurar la integridad de los datos en cualquier momento, es necesario que las modicaciones se hagan sobre memoria principal. Salvo que se indique lo contrario, no supondremos este tipo de comportamiento en nuestro trabajo. Por otro lado, las operaciones de reemplazo no conllevan una lectura desde el sistema de memoria. No dependen de los accesos de la aplicación, sino de la estructura de la memoria caché y los desalojos producidos. En muchos casos interesará tratarlas aparte para estudiar por separado las secuencias de lecturas y escrituras, sin que éstas resulten empañadas por los reemplazos que, por otra parte, son mucho más impredecibles. El objetivo de esta sección es convertir los fallos de la caché en un chero de datos tratable para la posterior agrupación de aplicaciones en función de su comportamiento, así como el diseño de un mecanismo de prebúsqueda. Primeramente, se describirá la herramienta Intel R  Pin, utilizada para obtener este chero. Seguidamente, hablaremos del formato de los datos obtenidos. 3.1. INTEL R  PIN 67 3.1. Intel R  Pin Intel R  Pin es una herramienta bajo la licencia de Intel R  centrada en el análisis de la ejecución de cualquier proceso. Tiene soporte en sistemas Linux, OS X y Windows, sobre ejecutables creados para la arquitectura IA-32, Intel R  64 y ciertas arquitecturas Intel R  integradas. Para una mayor información sobre Pin, consúltese el manual de usuario disponible desde la página ocial de Intel R  [16]. Pin permite insertar código (cualquier tipo de código) escrito en C o C++ en cualquier lugar durante la ejecución de un programa. El código se añade dinámicamente mientras el proceso principal está en ejecución. Pin proporciona un conjunto de APIs que permiten abstraerse de las particularidades de un juego de instrucciones para realizar ciertas operaciones. Por ejemplo, es posible pasar el contenido de los registros en un determinado momento como parámetros al nuevo código insertado. Pin automáticamente guarda el estado de ejecución de un programa (contenido de los registros, contador de programa, etc.) para la ejecución del código inyectado, y después recupera el estado original para continuar con la ejecución del proceso principal. Esto permite un análisis de la mayoría de los aspectos de un proceso que se ejecuta sobre un sistema, como por ejemplo generar una traza minuciosa de la ejecución del programa, o realizar simulaciones de comportamiento sobre cachés virtuales. Algunos ejemplos de preguntas que se pueden resolver utilizando Pin podrían ser determinar el número de instrucciones ejecutadas en un programa, o cuántas ramicaciones (saltos de programa) se llevan a cabo. 3.1.1. Funcionamiento básico La manera más sencilla de pensar en Pin es como un compilador Just-In-Time, que recibe como entrada un ejecutable binario. Pin intercepta la ejecución de la primera instrucción y genera (compila) un nuevo código compuesto por la instrucción original y las secuencias de control inyectadas que se deseen. Entonces transere el control a la secuencia generada. Una vez que esta secuencia ha terminado, el control es devuelto a Pin. Pin examina el siguiente código que será ejecutado e inserta el que sea conveniente en cada caso, repitiéndose así el proceso. En el modo JIT (Just-In-Time) sólo se generan secuencias para el código que es ejecutado. Esto signica que, si hay ciertas partes que el programa nunca ejecutará, Pin nunca las examinará ni generará secuencias que lo contengan. El código original sólo se puede usar de referencia. A medida que Pin va generando código, se le brinda al usuario la oportunidad de inyectar su propio código entre instrucciones. Pin sólo es capaz de examinar las instrucciones que realmente se ejecutan, independientemente de dónde se encuentren o cuándo se ejecuten realmente, aunque hay ciertas excepciones en saltos entre partes del programa. 68 CAPÍTULO 3. ACCESOS A MEMORIA FUERA DEL CHIP 3.1.2. Pintools La instrumentación o control de un proceso tiene en cuenta dos aspectos: El mecanismo que decide dónde y qué código se debe ejecutar. El código que se ejecuta en el punto de inserción. Al código relevante sobre la primera parte se le conoce como código de instrumentación , mientras que el del segundo aspecto es referido como código de análisis . Los dos componentes se guardan en un único ejecutable nal, llamado Pintool . Un Pintool es como un plug-in que regula la generación de código de Pin. El Pintool registra las funciones y rutinas que se deben llamar en cualquier punto donde se deba inyectar código. A este aspecto es a lo que hemos llamado el componente de instrumentación. Se encarga de inspeccionar el código que será generado, sus propiedades, y decidir si inyectar llamadas a rutinas de análisis. Por otro lado, el componente de análisis es el que contiene el código propiamente inyectado. Puede tener cualquier propósito: desde simular el comportamiento de una caché para averiguar la tasa de fallos de página (un fallo se produce cuando los datos no se encuentran en la caché y deben ser traídos de memoria principal) hasta simplemente guardar en un chero la traza completa del programa. Esta parte está bajo el control de Pin, que se asegura de guardar el estado de ejecución del programa antes y después del código inyectado para no alterar su ejecución normal. Un Pintool también puede registrar rutinas en función de cuando se producen ciertos eventos, como la creación de varios hilos en un programa o tras una llamada a fork . 3.1.3. Observaciones sobre Pin Algunas consideraciones importantes que se deben tener en cuenta sobre Pin y un Pintool son las siguientes. Un Pintool funciona como un plug-in del ejecutable original, por lo que utiliza el mismo espacio de direcciones que Pin y que el ejecutable a ser monitorizado. Por lo tanto, el Pintool tiene acceso a todos los datos que maneja el ejecutable. Pin y los Pintools monitorizan el comportamiento del ejecutable desde la primera instrucción. Para ejecutables que se compilan con librerías externas, esto implica que dichas librerías también serán visibles por el Pintool, ya que la carga dinámica de los recursos suele ser lo primero que hace un proceso. 3.1. INTEL R  PIN 69 Al crear un Pintool es más importante centrarse en el código de análisis que en el de instrumentación. El de instrumentación simplemente redirige las llamadas a las funciones de análisis en el momento oportuno, y estas funciones serán llamadas (previsiblemente) muchas veces. Es mejor centrarse en mejorar este código, que se repetirá en varias ocasiones. La instrumentación de Pin es Just-In-Time, lo que quiere decir que Pin toma el control cada cierto tiempo para insertar código de análisis en las partes que se consideren convenientes. En función de dónde Pin toma el control de la aplicación (o mejor dicho, la parte de instrumentación de Pin), podemos distinguir diferentes modos de funcionamiento. La instrumentación de instrucción hace que Pin tome el control antes de que se ejecute cada instrucción. Pin decide en ese momento si se realizará una llamada al código de análisis o, por el contrario, se continua la ejecución normal del programa. Para la ejecución de cada instrucción es necesario que Pin tome el control, guarde el estado actual del proceso, examine la instrucción, decida qué tipo de llamada de análisis se debe realizar, recupere el estado del proceso, devuelva el control al proceso original, y se ejecute la instrucción. Esto conlleva un evidente aumento del tiempo de ejecución del programa. La instrumentación de traza no tiene por qué detenerse en cada instrucción. La instrumentación ahora tiene lugar a nivel de BBL ( Basic Block ). Un BBL es una secuencia de instrucciones que está perfectamente delimitada por un punto de entrada y un punto de salida. Un punto de entrada será típicamente la primera instrucción a ejecutar tras un jump , y una salida que será un jump , call o return generalmente. Pin toma el control en cada ramicación que hay y examina el siguiente BBL a ejecutar. Pin puede decidir insertar código entre instrucciones (en cuyo caso estaríamos en un modelo parecido a la instrumentación de instrucción), o simplemente inyectar código de análisis al principio del BBL. La instrumentación de rutina hace que Pin tome el control cada vez que una nueva rutina es cargada en memoria. Puede inyectarse código al principio de la rutina que ha sido llamada, pero también se puede realizar un análisis a nivel de instrucción. No obstante, Pin no puede detectar BBLs trabajando en este modo. El último modo de funcionamiento se conoce como instrumentación de imagen , y Pin sólo toma el control al inicio de la ejecución, cuando se crea la imagen del proceso en memoria, y puede insertar código al principio. También puede programarse para llamar a una función de análisis en cada llamada a una rutina o, igual que en todos los casos anteriores, llamar a una misma función antes de cada instrucción. A este nivel tampoco puede discriminarse entre BBLs. 3.1.4. Propósito para utilizar Pin La herramienta Intel R  Pin se utilizará en un contexto de simulación de los niveles superiores de una jerarquía de memoria. Se desea monitorizar el número y tipo de accesos a memoria de una aplicación cualquiera, para generar un chero de traza donde el comportamiento del proceso esté 70 CAPÍTULO 3. ACCESOS A MEMORIA FUERA DEL CHIP descrito por las solicitudes al sistema de memoria principal. Con estos datos, es posible simular el comportamiento de un sistema de memoria con parámetros arbitrarios, puesto que se tiene la secuencia de operaciones solicitadas, así como el instante temporal en que se realiza. Concretamente, la infraestructura de Pin nos permitirá crear un script para simular un sistema de caché de tres niveles, donde la última caché sea compartida por todos los procesadores. Las operaciones a monitorizar serán, sobre todo, las de lectura y escritura, aunque también son de especial interés aquellos casos en los que el desalojo de una entrada de caché provoca una operación de escritura si el dirty bit está activo. A este último tipo se le conocerá como reemplazo . 3.2. Fichero de traza y aplicaciones monitorizadas La monitorización que se hace de Pin es a nivel de instrucción, lo que signica que se examina individualmente cada una de las ejecutadas por la aplicación. Si la instrucción resulta ser una petición al sistema de memoria, se recogen los datos relevantes de dicha instrucción. El programa Pin se puede ejecutar en distintas condiciones. Entre ellas, se examinarán las siguientes conguraciones: Puede elegirse el tamaño de la LLC entre dos posibles: 16MB o 32MB. Puede elegirse el tipo de asociatividad de la LLC. Una posibilidad es que sea asociativa por conjuntos de nivel 1, es decir, cada bloque de caché sólo puede ser localizado en una única entrada. La otra posibilidad es que la asociatividad sea por conjuntos de tamaño 8, donde cada bloque de caché, una vez determinado el conjunto al que pertenece, puede ser colocado en cualquiera de las 8 entradas. El programa no está preparado para realizar modicaciones sobre los tamaños o asociatividad de las cachés L1 (32KB) y L2 (2MB). La salida del programa Pin será un archivo de traza .nvt que contendrá información sobre todos los accesos a memoria principal. Será una secuencia de entradas, donde cada entrada esté formada por: Número de ciclo donde se ha llevado a cabo la petición. Tipo de la petición ( R , Read; W , Write). Dirección de memoria donde se dirige la petición. Datos involucrados en la transacción. Para el agrupamiento y descubrimiento de patrones de accesos a memoria se han elegido ciertas aplicaciones para ser monitorizadas. La lista completa puede ser consultada en la tabla 3.1. Todas ellas pertenecen al repertorio estándar SPEC2006 excepto Firefox, Openoce, gcc y g++. 3.2. FICHERO DE TRAZA Y APLICACIONES MONITORIZADAS 71 Astar Bzip2 Firefox g++ gcc gobmk h264ref hmmer lbm libquantum mcf milc namd omnetpp Openoce povray sjeng specrand sphinx3 Xalan Tabla 3.1: Listado de aplicaciones a monitorizar. Bajo el script de Pin preparado para simular una jerarquía y monitorizar los accesos a memoria, las 20 aplicaciones han sido ejecutadas. Para cada una de ellas, se han tenido en cuenta cuatro posibles escenarios: LLC de 16MB y asociatividad de nivel 1. LLC de 16MB y asociatividad de nivel 8. LLC de 32MB y asociatividad de nivel 1. LLC de 32MB y asociatividad de nivel 8. De esta forma, en total se generan 80 cheros de traza con extensión .nvt . Para cada acceso a memoria interesa guardar el número de ciclo en el que se produce, de qué tipo es, y a qué dirección de memoria se dirige la petición. Un ejemplo de comienzo de un chero de traza se puede encontrar en la tabla 3.2. En ella se pueden comprobar los cuatro primeros accesos a memoria que realiza Firefox cuando la LLC tiene 16MB y la asociatividad es de nivel 1. Ciclo Tipo Dirección 1 R 0x7f487cb82c00 2 W 0x7ecf8e0240 3 R 0x7f487cb83980 16 R 0x7f487cda7e40 Tabla 3.2: Comienzo del chero de traza .nvt para Firefox en el caso de 16MB de LLC y asociatividad de nivel 1. Dado que una aplicación puede generar muchísimos accesos a memoria, el chero de traza puede ser sorprendentemente grande. En el caso del chero de traza de Firefox, ocupa algo más de 1GB, ya que ha realizado más de 7 millones de accesos a memoria. Otras aplicaciones pueden generar menos accesos, aunque hay algunas cuyo tamaño de chero de traza sobrepasa los 20GB. En general, cuanto mayor es el tamaño del chero de traza, es porque la aplicación es más exigente, ha estado en ejecución durante más tiempo, y por tanto ha realizado más accesos a memoria. Debido al enorme tamaño del chero de traza, es necesario resumir la información de alguna manera para aprovechar no sólo mejor el espacio, sino también mejorar la legibilidad e 72 CAPÍTULO 3. ACCESOS A MEMORIA FUERA DEL CHIP interpretabilidad de la información. En este contexto se propone una transformación del chero .nvt en otro con extensión .outA a partir de un script de Python. En el chero .outA se quiere almacenar la información sobre las peticiones de acceso a memoria, agrupando todas aquellas que se reeran a una misma dirección. Este chero será referido a partir de ahora como chero de accesos a memoria , o simplemente chero de accesos . El objetivo es disponer de la información de la siguiente forma: Dirección de memoria - (número de acceso, tipo) [(número de acceso, tipo)] ... (3.1) Para cada dirección de memoria se almacena el instante temporal y el tipo de la petición solicitada sobre esa dirección de memoria. El número de elementos almacenados dependerá del número de peticiones realizadas sobre una misma dirección. A diferencia del chero de traza, en este no mediremos el instante temporal como el ciclo en el que se produce la solicitud. En su lugar se toma el número de solicitud realizada, empezando siempre por el uno. El segundo acceso a memoria se tomará con el valor 2, independientemente del número de ciclos que hayan transcurrido entre ambos. Esta aproximación permite abstraerse del nivel de procesamiento de la aplicación y utilizar únicamente la información sobre los accesos a memoria. Si durante un largo periodo de tiempo no se lleva a cabo ningun acceso, el contenido de la memoria caché no cambia y esta situación no es de interés. Así también evitamos la distorsión introducida por otras tareas ajenas a la propia aplicación monitorizada, que puedan afectar al tiempo de ejecución. Continuando con el chero de traza de Firefox, si lo convertimos a un chero de accesos, las cuatro primeras líneas son las siguientes: 0x7f487cb82c00 1 R 0x7ecf8e0240 2 W 0x7f487cb83980 3 R 0x7f487cda7e40 4 R 329010 R 998785 R 1053536 R 1321342 R 1422107 R 1431184 R 1572377 R 2357256 R 2728021 R 3595809 R 3939819 R 4008074 R 4145967 R 4275977 R 4399616 R 4765392 R En este pequeño ejemplo podemos ver como la línea a la que se accede por cuarta vez vuelve a ser consultada otras 16 veces, y todas las peticiones son de lectura. Las tres primeras líneas sólo se acceden una vez y no vuelven a ser consultadas. Un punto importante es que en el chero de accesos se han eliminado todos los accesos a memoria de tipo reemplazo . De hecho, no cuentan como número de acceso, por lo que aunque haya varios accesos de reemplazo entre dos peticiones de lectura o escritura, la diferencia temporal será de 1 acceso. Esto se hace para evitar la distorsión introducida por los reemplazos, que no son propiamente una operación lanzada de forma directa para acceder a un dato, sino desencadenada de forma indirecta por un desalojo de la memoria caché. 3.2. FICHERO DE TRAZA Y APLICACIONES MONITORIZADAS 73 En vista del chero de accesos, es posible darse cuenta de ciertos patrones recurrentes en las peticiones a una misma dirección de memoria: En muchísimas líneas sólo se realiza un único acceso, que puede ser o bien de lectura, o bien de escritura. Aunque pueda parecer que hacer un acceso de escritura para luego no leer el dato es un sinsentido, hay que recordar que es posible que se esté utilizando a nivel de caché y que no haya sido desalojado nunca, por lo que no se necesita una operación de lectura para consultarlo. Otro patrón recurrente es el de múltiples accesos, pero únicamente de lectura. En el ejemplo de Firefox puede observarse este comportamiento. El último patrón que parece repetirse también está relacionado con varios accesos, aunque está vez se encadenan solicitudes de lectura y escritura. Además del chero de accesos, se considera también un chero de ciclos con extensión .out . Contiene la misma información que el primero en cuanto a secuencias de accesos, pero indica el instante temporal exacto (en número de ciclo) en que se realiza una petición en lugar del número de acceso. Siempre trabajaremos con el chero de accesos, salvo que se indique explícitamente lo contrario y se trabaje con ciclos. A partir del chero de accesos es posible obtener información de todo tipo. Una posibilidad es el estudio de la localidad temporal de la aplicación, tal y como se hace en el Capítulo siguiente. También se puede extraer información sobre la localidad espacial, la distribución del número de accesos a una misma línea, e información sobre la estabilidad e irregularidad en los accesos a memoria, como veremos en los Capítulos posteriores. 80 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES En resumen, el preprocesamiento que se ha realizado a las observaciones de la distancia temporal para cada caso ha sido: 1. Se elimina el 5% de los valores más elevados para paliar el efecto de medidas atípicas. 2. No se consideran aquellos casos donde haya menos de 50 mediciones. 3. Se toman b= 10 alturas para el agrupamiento, y b= 100 en las representaciones grácas. 4. La medida de distancia para valorar las diferencias es la basada en JSD. A partir de la matriz de distancias, se propone un clustering jerárquico ascendente basado en el método de Ward. Teniendo en cuenta que la LLC puede tener 16MB o 32MB, y que la asociatividad puede ser de nivel 1 o de nivel 8, se tienen 4 escenarios para probar las aplicaciones. El agrupamiento discutido será únicamente para el escenario de 16MB y asociatividad de nivel 1, pues es donde se espera una tasa más elevada de fallos de caché, y por tanto más accesos a memoria. El objetivo del clustering es dividir a las aplicaciones en función de sus accesos a memoria para poder diseñar optimizaciones por separado. El dendograma resultante de aplicar el método descrito se puede consultar en la gura 4.2. Es fácil ver que fundamentalmente hay cuatro grupos que permiten separar a las aplicaciones atendiendo al criterio JSD. Por un lado, todas las aplicaciones del grupo de la izquierda tienen un comportamiento muy similar, además de ser el grupo más grande. Por otro lado, los grupos de la derecha están formados por menos elementos. Figura 4.2: Dendograma para las aplicaciones con LLC de 16MB y asociatividad de nivel 1 4.1. AGRUPAMIENTO EN BASE A LA LOCALIDAD TEMPORAL 81 Las guras 4.3, 4.4, 4.5, 4.6 contienen los histogramas de todas las aplicaciones que han participado en el análisis, separados por los cuatro grupos que sugiere el dendograma. Debajo de cada uno se incluyen unos pequeños resúmenes de la distribución: la máxima distancia temporal que determina la escala del eje x, el número de accesos repetidos que se han producido en total, y el valor medio. Figura 4.3: Aplicaciones del grupo 1 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1 Es necesario llamar la atención sobre algo importante antes de continuar. Dada la forma en la que se ha construido el histograma, no se pueden comparar las aplicaciones entre sí en la escala de tiempo (eje x) representada. Los datos de cada aplicación se han discretizado en 100 intervalos de igual longitud, por lo que la amplitud y rango de los mismos no son directamente comparables. Si dos aplicaciones tienen unos histogramas similares donde el mayor peso se sitúa a la izquierda, no es correcto decir las dos aplicaciones tienden a volver a acceder tempranamente a los datos una vez utilizados. Si la máxima distancia temporal en la primera aplicación es de, por ejemplo, 1.000 accesos, pero en la segunda es de 10.000, entonces el primer intervalo de accesos considerado si tomamos b= 100 es de [1,10] accesos para la primera aplicación y [1,100] para la segunda. Si la primera barra tiene alturas similares en las dos aplicaciones, se estaría indicando que aproximadamente hay el mismo número de casos que caen entre 1 y 10 accesos en la aplicación 1 y entre 1 y 100 accesos en la aplicación 2. Sin embargo, puesto que el rango de la distancia temporal puede variar de manera drástica entre aplicaciones, esta escala relativa parece más adecuada para comparar la distancia temporal de manera global. Así, se mide el comportamiento de la localidad temporal tomando como referencia el rango en el que se suele mover la distribución de la distancia temporal. La armación correcta sería más bien que las dos aplicaciones tienden a volver a acceder tempranamente a los datos una vez utilizados, cada una en relación con el comportamiento habitual y la escala apropiada para cada aplicación. No obstante, no se incluirá esta aclaración en todos los casos, por ser redundante y demasiado tediosa. Se recomienda tener siempre presente esta diferencia en las escalas para la 82 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES Figura 4.4: Aplicaciones del grupo 2 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1 interpretación de los resultados. Como indicativo del rango de la distancia temporal se incluye, en la parte inferior del histograma el valor máximo de la distancia temporal. A la vista de los histogramas y la agrupación de las aplicaciones, podemos deducir que: El grupo 1 está formado por aplicaciones que no acceden tempranamente de nuevo a la misma información, sino que hay un número de accesos no despreciable entre medias. Si Ri denota la máxima distancia temporal para la aplicación i del grupo 1, entonces con una alta probabilidad se volverá a acceder a una misma posición de memoria aproximadamente dentro de 0.6Ri accesos. Nótese que para astar, la máxima distancia temporal es 6, y que entonces la mayoría de accesos se repite cada 4 accesos intermedios. Además, ocurre un número no despreciable de veces, pues se tienen 112.692 valores de la distancia temporal. Esto distingue a astar de sus dos compañeras, donde el rango es mucho más elevado en comparación. El grupo 2 se corresponde con aplicaciones cuyo tiempo entre accesos a una misma dirección está distribuido a lo largo del rango, es decir, hay accesos repetidos en casi cualquier intervalo de tiempo. No obstante, es cierto que la forma de los histogramas es diferente. En el caso de `refox y `namd la forma es parecida: hay varios accesos repetidos tempranos, y van decreciendo progresivamente, aunque siempre hay unos pocos. El decrecimiento para `milc es más lento, igual que para `povray. Esta última merece una mención aparte, pues la 4.1. AGRUPAMIENTO EN BASE A LA LOCALIDAD TEMPORAL 83 Figura 4.5: Aplicaciones del grupo 3 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1 84 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES Figura 4.6: Aplicaciones del grupo 4 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1 máxima distancia temporal es muy pequeña: 293 accesos intermedios. Por otro lado, `bzip2 y `gobmk no presentan esta tendencia decreciente. El grupo 3 caracteriza a aplicaciones con una fuerte reutilización de direcciones de memoria a corto plazo. Se diferencian de las aplicaciones del grupo 2 en que la altura del histograma es prácticamente cero a partir de un cierto tiempo. Esto motiva separarlas de aplicaciones como `refox y `namd. El último grupo contiene dos aplicaciones donde la mayoría de accesos repetidos se producen tras un número muy elevado de accesos intermedios, aunque hay un pequeño número de accesos tempranos. 4.1.2. Agrupamiento considerando un umbral de olvido La segunda aproximación para la categorización de aplicaciones en función de su localidad temporal pasa por un umbral de olvido. Cuando se accede a una posición de memoria, se elevan esos y los datos cercanos a la memoria caché, pues existe una alta probabilidad de volverlos a utilizar en un futuro próximo. Si no se vuelven a utilizar, acabarán siendo desechados por el algoritmo de selección de víctima. Es posible que tiempo después se vuelva a acceder a la misma posición de memoria, pero ha habido tantos accesos intermedios que no queda ningún residuo en la caché, y este acceso se trata a todos los efectos como una posición de memoria no vista hasta ese momento. En este contexto tiene sentido denir un parámetro de olvido que se denotará como Tu . Se considera que el acceso a una posición de memoria es el primero de una posible secuencia de 4.1. AGRUPAMIENTO EN BASE A LA LOCALIDAD TEMPORAL 85 accesos repetidos en cualquiera de los dos siguientes casos: a. Es, realmente, la primera vez que se accede a dicha posición de memoria. b. Se ha accedido anteriormente a esa posición, pero el número de accesos intermedios m verica que m > Tu . La elección de Tu depende del tamaño de la caché, puesto que en función de éste se tardará más o menos tiempo en eliminar los residuos de una posición de memoria. Nótese que siempre que haya espacio, no será necesario desalojar un bloque de datos. No debemos olvidar el propósito de este trabajo: encontrar una buena conguración para que una memoria SDRAM pueda actuar como caché de una RRAM que trabaje inmediatamente por debajo en la jerarquía de memoria. Consideremos una cache SDRAM con un tamaño de datos de 4GB y un tamaño de línea de 64 Bytes. El número de líneas será, aproximadamente, de 64 millones. Si la asociatividad fuera por conjuntos de nivel 16, por ejemplo, tendríamos 4 millones de conjuntos de 16 líneas cada uno. En un caso óptimo podríamos recibir 4 millones de accesos sin repetir ningún conjunto, aunque la realidad es diferente y habrá varios conjuntos con muchos accesos, lo que da lugar a reemplazos. Podríamos considerar que la vida media de una línea en esta cache podría ser del orden de un millón de accesos, aunque es simplemente una suposición. Por ello, un valor de Tu= 1.000.000 parece un buen candidato. El preprocesamiento que se necesita realizar en el chero de localidad temporal para incluir la información del parámetro de olvido es muy sencillo. Para cada línea del chero, si el valor de la distancia temporal es superior a Tu , no debemos considerarlo como un acceso repetido y, por tanto, borrarlo del chero. El resultado es que para todas las aplicaciones y escenarios, se tienen unos datos que informan sobre la localidad temporal y en ningún caso se supera el valor Tu . Para hacer el clustering, podemos de nuevo quedarnos con las alturas del correspondiente histograma que resuma la distribución. Sea b el número de alturas del histograma que resume la muestra de la localidad temporal considerando un parámetro de olvido. El histograma se crea de forma que el valor máximo es Tu independientemente de la muestra, por lo que ahora los histogramas comparten escala y el eje x es comparable entre sí. El problema que dicultaba la interpretabilidad en la solución anterior, debido a la escala relativa denida por la máxima distancia temporal, desaparece por completo. En la gura 4.7 se muestra un histograma con b= 100 para la aplicación Firefox, con LLC de 16MB y asociatividad de nivel 1. La forma no es muy diferente del que se representa en la gura 4.1, aunque puede verse cómo representa una ampliación para valores pequeños, resultado de eliminar las observaciones mayores que Tu . Además, ahora podemos proporcionar una interpretación más natural del polígono de frecuencias acumuladas. Casi el 60% de las veces, se vuelve a acceder a memoria para consultar una dirección repetida con menos de 200.000 accesos intermedios a otras posiciones. De hecho, casi el 20% de los accesos repetidos involucran menos de 10.000 accesos intermedios. En este caso apenas se nota, pero veremos como en otras aplicaciones, la forma del histograma sí cambia por cuestiones de escala. 86 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES Figura 4.7: Histograma de la distribución de la localidad temporal para Firefox y polígono de frecuencias relativas acumuladas, con LLC de tamaño 16MB y asociatividad de nivel 1, considerando un parámetro de olvido. Para el clustering, se tomará b= 10 de la misma forma que en el caso anterior. En todas las representaciones grácas se utiliza b= 100 . También se han eliminado aquellas aplicaciones que acceden menos de 50 veces a memoria, y se ha utilizado la métrica JSD para valorar las diferencias en los histogramas. De igual forma que antes, se propone un clustering jerárquico basado en el método de Ward para el escenario con 16MB de LLC y asociatividad de nivel 1. El dendograma resultante se muestra en la gura 4.8. A diferencia del anterior, no hay un número de clusters que resulte evidente a primera vista. Podría pensarse que 4 clusters son adecuados. Nótese que el comportamiento de libquantum es tan peculiar que cuesta mucho agruparla con otro cluster. Vamos a elegir 5 clusters, separando también el comportamiento de sjeng del resto, pues ahora veremos que tanto él como libquantum merecen mención aparte. Las guras 4.9, 4.10, 4.11, 4.12 y 4.13 contienen los histogramas de todas las aplicaciones, separados por grupos. Debajo de cada histograma se incluye el número de accesos repetidos a posiciones de memoria (esto es, el número de datos con los que se ha representado el histograma). A diferencia del anterior clustering, ahora sí se pueden comparar entre sí las distintas aplicaciones en la escala de tiempo. Si dos aplicaciones tienen unos histogramas similares donde el mayor peso se sitúa a la izquierda, es correcto decir que las dos aplicaciones tienden a volver a acceder tempranamente a los datos una vez utilizados. La altura de la barra i , hi,∀i∈ {1, . . . , b} , indica el porcentaje relativo de veces en las que, entre dos accesos a una misma posición de memoria, hay entre b Tu(i−1) y b Tui accesos intermedios, independientemente de la aplicación. 4.1. AGRUPAMIENTO EN BASE A LA LOCALIDAD TEMPORAL 87 Figura 4.8: Dendograma para las aplicaciones con LLC de 16MB y asociatividad de nivel 1, considerando umbral de olvido 88 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES Figura 4.9: Aplicaciones del grupo 1 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1, considerando un umbral de olvido Figura 4.10: Aplicaciones del grupo 2 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1, considerando un umbral de olvido 4.1. AGRUPAMIENTO EN BASE A LA LOCALIDAD TEMPORAL 89 Figura 4.11: Aplicaciones del grupo 3 para el clustering cuando la LLC es de 16MB y la asociatividad por conjuntos de nivel 1, considerando un umbral de olvido 96 CAPÍTULO 4. AGRUPAMIENTO DE APLICACIONES Capítulo 5 Mecanismo de prebúsqueda Hasta ahora hemos examinado el comportamiento de la localidad temporal y algorítmica. La localidad temporal nos ha servido para agrupar aplicaciones en función de lo que tardan en volver a acceder a una misma posición de memoria, mientras que la localidad algorítmica ha sido estudiada a través del perl de accesos a memoria. Sin embargo, todo el estudio que se ha hecho hasta ahora es más bien descriptivo. En este capítulo examinaremos algo más complicado: la localidad espacial. La localidad espacial de los programas se reere, como ya hemos comentado anteriormente, a la elevada probabilidad de acceder a una zona cercana de memoria en un corto intervalo de tiempo. Esto es evidentemente más complicado de medir, puesto que no hay que vigilar una única posición de memoria, sino toda la zona de alrededor. También se vuelve algo subjetivo, pues para proporcionar medidas cuantitativas de la localidad espacial no hay que denir sólo un umbral de olvido, sino también delimitar la zona de memoria que se considera cercana. El propósito de este trabajo es determinar una buena forma de organizar el sistema de memoria principal en dos niveles: una memoria SDRAM que actúa como caché de una memoria RRAM. En este apartado daremos, precisamente, la respuesta a esta pregunta. Utilizar una memoria SDRAM como caché de otra más grande tiene varias implicaciones. Por un lado, la memoria SDRAM será una memoria grande, por lo que la caché podrá almacenar gran cantidad de información que la RRAM mantiene. Está destinado fundamentalmente a aplicaciones muy grandes y exigentes, con un gran volumen de utilización de memoria. Un ejemplo de estas aplicaciones son las destinadas al tratamiento de grandes cantidades de datos ( Big Data ), de las que tanto se habla hoy en día. El verdadero interés de esta situación pasa por suponer una memoria RRAM grande (por ejemplo, del orden de 256GB), que sabemos es más lenta que las memorias RAM dinámicas, y colocar una SDRAM como caché en el nivel superior (por ejemplo, del orden de 16GB). En el Capítulo 2 pudimos comprobar que la creación de una jerarquía de memoria nos permite disfrutar de las ventajas de ambas partes: mantenemos el carácter no volátil de la RRAM, pero permitimos un acceso más rápido a través de una caché SDRAM. Por otro lado, este sistema será siempre más lento que uno que sólo posea una SDRAM de suciente tamaño. Al añadir más niveles y sustituir la SDRAM por una RRAM funcionando de 97 98 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA apoyo principal, se pierde la rapidez de acceder únicamente a una memoria y aumenta el consumo de energía, pues hay que añadir el mecanismo de caché, denir la política de reemplazo, crear nuevas conexiones, etc. El estudio de la localidad espacial que se realiza en este apartado es mucho más que descriptivo: veremos cómo podemos utilizar esta información para diseñar un mecanismo de prebúsqueda . Un sistema de prebúsqueda ubicado en la SDRAM se encarga de analizar la secuencia de peticiones de acceso que proceden de los niveles superiores de la jerarquía y predecir las próximas. Por simplicidad y por no añadir ruido innecesario, nos centraremos únicamente en los accesos de lectura y escritura, dejando de lado los reemplazos. Si la memoria SDRAM dispusiera de un método ecaz de prebúsqueda, podría realizar peticiones de acceso a la RRAM situada en la capa inferior mientras está ociosa, de manera que, si nalmente la predicción se cumple, el acceso a la línea será más rápido al no tener por qué llegar hasta el nivel de RRAM. Suponiendo una caché SDRAM sucientemente grande, podemos permitirnos que la prebúsqueda sea menos na, tomar menos riesgos, y traer más porciones de memoria aunque la probabilidad de usarlas no sea tan alta. Sin embargo, analizar la secuencia de accesos reciente no es para nada sencillo. El comportamiento de las aplicaciones está lejos de ser reconocible, al menos si nos jamos únicamente en el comportamiento reciente sin realizar ninguna discriminación. En la gura 5.1 podemos comprobar los 10 primeros accesos que llegan al sistema de memoria RAM suponiendo una LLC de 16MB y una asociatividad por conjuntos de nivel 1. En la izquierda, los diez accesos se muestran a escala real. Da la impresión de que los accesos 2 y 4 son extraños, y que el resto se mantiene en una línea horizontal. Sin embargo, en la gura de la derecha se ha representado únicamente la parte inferior. Podemos comprobar como, lejos de ser una línea recta, se repite la distinción entre direcciones de memoria superiores e inferiores. Adicionalmente se muestra la tabla con las direcciones virtuales exactas utilizadas. Podemos distinguir fácilmente tres zonas diferentes en una simple secuencia de diez accesos: Los accesos 1, 3, 7 y 10 corresponden al rango de direcciones 0x7FB01E60XXXX. Son las direcciones más bajas. Los accesos 2 y 4 corresponden al rango 0x7FFEDCDFXXXX y son las direcciones más altas. Tanto, que en la gura 5.1 (b) no aparecen. Los accesos 5, 6, 8 y 9 corresponden al rango 0x7FB01E83XXXX, el intermedio entre los tres. Las principales causas de que se produzcan accesos a tres zonas diferentes de memoria es que un proceso rara vez está dedicado exclusivamente a una tarea, sino que realiza varias intercaladamente. El comienzo de la ejecución de un programa es especialmente interesante, pues aún no se ha estabilizado su comportamiento. 99 (a) Sin ampliar (b) Ampliado Número de acceso Dirección de memoria 1 0x7FB01E60BC00 2 0x7FFEDCDF2400 3 0x7FB01E60C980 4 0x7FFEDCDF23C0 5 0x7FB01E830E40 6 0x7FB01E830C40 7 0x7FB01E60C9C0 8 0x7FB01E831000 9 0x7FB01E8319C0 10 0x7FB01E60CA00 (c) Direcciones físicas Figura 5.1: Primeros diez accesos a memoria de la aplicación astar (asociatividad 1, tamaño LLC 16MB) 100 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA Si en una simple secuencia de 10 accesos ya aparecen tres zonas de memoria, vamos a necesitar diseñar un procedimiento sosticado de prebúsqueda que atienda a la posibilidad de acceso alternado a diferentes zonas en la memoria principal. Este capítulo se ha dividido en diferentes secciones, cada una detallando diferentes aproximaciones para enfrentarnos a este problema. En la primera sección se aborda un modelo basado en una distribución binomial, con el objetivo de predecir el número de accesos a zonas cercanas de memoria. En la segunda sección exploraremos la posibilidad de utilizar la información inmediatamente anterior para decidir si un bloque de memoria merece ser cacheado o no. La última aproximación y la más útil de todas se basa en un modelo de Markov oculto para separar las zonas de memoria. Por último, se diseñará un mecanismo de prebúsqueda basado en el modelo oculto de Markov que permita predecir accesos futuros a memoria. Para comprobar su funcionamiento, se propondrá un modelo de simulación de una caché SDRAM en el que se aplique la prebúsqueda. Por último, se mostrarán los resultados obtenidos para las 20 aplicaciones que se han venido considerando hasta ahora. 5.1. Primera propuesta: modelo binomial Sea li la línea asociada a la i -ésima posición de memoria asignada a una determinada aplicación. Para caracterizar la localidad espacial debemos denir: Una ventana espacial, S , que distinga las líneas que pertenecen a la zona de memoria cercana a una porción. Una ventana temporal, T , que permita caracterizar si el acceso es cercano o no en el tiempo. Denición 1. (Localidad espacial de una aplicación) . Sea tij el tiempo en el que se accede a la línea li por j -ésima vez. Se considera que existe localidad espacial si se accede a otra línea cualquiera, lk , de forma que i−S≤k≤i+S , con k6=i , siempre que el momento de acceso se encuentre en el intervalo temporal denido, es decir, existe algún j0 tal que tij −T≤tkj0≤tij +T . En este caso, lk pertenece al grupo de la localidad espacial de la línea li accedida por j -ésima vez: lk∈locspa(li, j) . Nótese que, según los principios de localidad temporal, suelen producirse varios accesos a una misma línea, de ahí la necesidad del doble subíndice. La denición anterior nos dice que existe localidad espacial si accedemos a una ventana espacial en una determinada ventana temporal. Ambas ventanas se tienen en cuenta por los dos sentidos: la ventana espacial delimita la zona de memoria tanto por arriba como por abajo, y la ventana temporal tanto a lo que ha ocurrido antes como lo que ocurrirá después. Para nuestras tareas de predicción, será mucho más útil distinguir entre este pasado y futuro. 5.1. PRIMERA PROPUESTA: MODELO BINOMIAL 101 Denición 2. (Localidad espacial pasada y futura) . Sea tij el tiempo en el que se accede a la línea li por j -ésima vez. Se considera que existe localidad espacial futura si se accede a otra línea cualquiera, lk , de forma que i−S≤k≤i+S , con k6=i , siempre que el momento de acceso se encuentre en el intervalo temporal denido, es decir, existe algún j0 tal que tij < tkj0≤tij +T , y lk∈locspafut(li, j) . Por otro lado, se considera localidad espacial pasada si tij −T≤tkj0< tij , y lk∈locspapas(li, j) . Sea Yij la variable aleatoria que indica el número de líneas que pertenecen al conjunto de la localidad espacial futura para el j -ésimo acceso de la línea i , para i= 1, . . . , K , j= 1, . . . , ni . El valor K es el número de líneas de memoria asociadas al proceso, mientras que ni es el número de veces que se ha accedido a la línea li . Formalmente, Yij =|locspafut(li, j)| . Siempre se cumple que 0≤Yij ≤2S . Si Yij = 0 , entonces no se ha accedido a ninguna línea cercana en el espacio y en el tiempo; si Yij = 2S se han accedido a todas las que conforman la zona de localidad espacial. Supongamos que Yij sigue una distribución binomial: Yij ∼B(2S, pij) . Esto signica que todas las líneas que se encuentran dentro de la ventana espacial tienen la misma probabilidad de ser usadas. Esta probabilidad, pij , es la probabilidad de acceder a cualquiera de las líneas dentro de la ventana espacial y temporal, considerando sólo el futuro. Si somos capaces de modelar pij , podemos discernir si resulta rentable traer el bloque entero de direcciones de memoria a la caché. Si pij es grande, se espera que al llevar todo el bloque de direcciones desde li−S hasta li+S acertemos en gran parte. Sin embargo, esta suposición está lejos de ser cierta. Algo más realista sería suponer que no es igual de probable acceder a todas las líneas cercanas, y que la probabilidad va decreciendo a medida que nos alejamos. De esta manera, pasaríamos a modelar variables aleatorias de Bernouille y no un proceso binomial directamente. Bajo este supuesto, sea Yijk una variable indicadora que vale 1 si la línea lk∈locspafut(li, j) , es decir, se accede a lk en la ventana espacial y temporal denida, y sea pijk la probabilidad de que este suceso ocurra. Ahora Yij =Pi+S k=i−S,k6=iYijk . En lugar de tomar pijk =pij ∀k∈ {i−S, . . . , i−1, i+1, . . . , i+S} como hacíamos antes, parece más razonable modelar pijk =αkpij , con α∈(0,1) . Esto garantiza que la probabilidad de acceder a una línea va disminuyendo conforme nos alejamos. Para modelar y obtener una estimación de pij y α podríamos utilizar un enfoque parecido a la regresión logística. Sea Xij otra variable aleatoria asociada a la localidad espacial, pero esta vez a la localidad espacial pasada. Xij indica el número de líneas que pertenecen al conjunto de la localidad espacial pasada para el j -ésimo acceso de la línea i , con i= 1, . . . , K , j= 1, . . . , ni . Formalmente, Xij =|locspapas(li, j)| . Siempre se cumple que 0≤Xij ≤2S . Un modelo razonable para las probabilidades futuras sería modelar de forma lineal el logit de la probabilidad: log pij 1−pij =β0+β1Xij 102 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA De esta forma, pijk =eβ0+β1Xij 1 + eβ0+β1Xij ·αk Antes de entrar en el proceso de estimación de los parámetros del modelo, es necesario comprobar si las hipótesis distribucionales son ciertas o, por el contrario, no es posible continuar con un modelo así. Para ello vamos a crear un nuevo tipo de chero dedicado a la localidad espacial. 5.1.1. Fichero de localidad espacial La obtención de los cheros de localidad espacial , de extensión .locspa , tal y como se describen a continuación, es una tarea muy ardua. El objetivo es disponer de los valores de las variables Xij e Yij para poder desarrollar la estimación del modelo. Tal y como está denido, Xij contiene información sobre la localidad espacial pasada, mientras que Yij almacena lo relevante al futuro. Además de la separación en dos de la ventana temporal, también es interesante dividir en dos zonas la ventana espacial: las líneas situadas antes y después de la considerada. El comportamiento de los procesos puede tener una tendencia creciente o decreciente en la utilización de la memoria en función de la tarea que se esté realizando, y es interesante caracterizar este comportamiento. De esta manera, la variable X1 ij se reere a la localidad espacial pasada para las líneas sucedidas antes de li , mientras que X2 ij se utiliza para las líneas posteriores. Siguiendo la notación anterior: X1 ij ={lk:lk∈locspapas(li, j)∧k < i} (5.1) X2 ij ={lk:lk∈locspapas(li, j)∧k > i} (5.2) De forma que, combinando (5.1) y (5.2), se tiene de forma trivial Xij =X1 ij +X2 ij (5.3) Análogamente, se realiza la misma distinción para la localidad espacial futura que denotábamos como Yij . Y1 ij ={lk:lk∈locspafut(li, j)∧k < i} (5.4) Y2 ij ={lk:lk∈locspafut(li, j)∧k > i} (5.5) Yij =Y1 ij +Y2 ij (5.6) El chero de localidad espacial parte del procesamiento del chero de accesos, tiene tantas las como accesos a memoria haya producido la aplicación, y 7 columnas: El momento de acceso a la línea, medido en número de accesos. 5.1. PRIMERA PROPUESTA: MODELO BINOMIAL 103 La dirección de memoria involucrada. El número de veces que se ha accedido a esta línea, contando con éste. El valor de X1 ij . El valor de X2 ij . El valor de Y1 ij . El valor de Y2 ij . Puesto que para cada acceso individual tienen que examinarse posiciones cercanas de memoria y contar cuántos ha habido, se requiere mucho tiempo para obtener un chero de localidad espacial. En el ejemplo de Firefox que venimos manejando, hay 7.248.108 accesos a memoria, aunque otras aplicaciones manejan cheros con mayor número de ellos. En la tabla 5.1 se encuentra un ejemplo de chero de localidad espacial. Concretamente, se muestra el comienzo para la aplicación astar tomando una LLC de 16MB y asociatividad 1. La ventana temporal se ha establecido como T= 1000 , y la ventana espacial a S= 100 . Este chero está ordenado alfabéticamente por tag y no por t , ya que de esta forma resultaba mucho más rápido el cálculo (aunque en este ejemplo el orden para los dos coincide). t tag numAcceso X1 ij X2 ij Y1 ij Y2 ij 194 0x558de3770040 1 0 0 0 16 197 0x558de3770080 1 1 0 0 15 201 0x558de37700c0 1 2 0 0 14 202 0x558de3770100 1 3 0 0 13 204 0x558de3770140 1 4 0 0 12 205 0x558de3770180 1 5 0 0 11 207 0x558de37701c0 1 6 0 0 10 208 0x558de3770200 1 7 0 0 9 246 0x558de3770280 1 8 0 0 8 Tabla 5.1: Comienzo del chero de localidad espacial para la aplicación astar, con LLC de 16MB y asociatividad 1. En esta tabla podemos comprobar varias cosas. En primer lugar, la zona de memoria que aparece descrita conlleva una lectura en orden creciente. Esto se deduce de que el valor de X1 ij es cada vez mayor, pues cada vez hay más líneas anteriores que han sido leídas en un pasado reciente; de la misma forma, el valor de Y2 ij cada vez es menor, puesto que las líneas posteriores futuras se van leyendo poco a poco. Concretamente, esto marca una zona de 16 líneas de memoria que se leen en orden creciente. 104 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA Por otro lado, puesto que el valor de X2 ij y de Y1 ij es 0 siempre, no hay líneas posteriores leídas en el pasado ni tampoco líneas anteriores futuras, es decir, no se está leyendo de adelante hacia atrás. Ahora que ya tenemos un chero adecuado con el que podemos poner en práctica este modelo, examinemos si resulta factible. 5.1.2. Violación de las suposiciones De los dos modelos propuestos al comienzo de esta sección, el primero tomaba una distribución binomial para Yij , y el segundo asume que las probabilidades decrecen a medida que nos alejamos de li . Con el objetivo de comprobar si Yij sigue una binomial, representaremos su histograma para el caso de astar (gura 5.2). Figura 5.2: Histograma para Yij en el caso de astar, LLC 16BM y asociatividad 1. A la vista del gráco es imposible suponer que Yij sigue una distribución binomial, pues se presenta una distribución bimodal con un pico cercano a 0 y otro pico cercano a S . Situaciones similares se presentan en otras aplicaciones. Esto invalida el primer modelo presentado. En la gura 5.3 podemos comprobar que, además de no poder suponer un modelo binomial, la distribución no es la misma para Y1 ij y Y2 ij . En cuanto a las suposiciones del segundo modelo, que establecen que la probabilidad de acceder a una línea decrece con la distancia, tampoco se pueden suponer ciertas. Que los histogramas de la gura 5.3 muestren picos en el valor S= 100 indica que hay determinadas zonas en la 5.2. SEGUNDA PROPUESTA: INFORMACIÓN INMEDIATA ANTERIOR 105 (a) Histograma para Y1 ij (b) Histograma para Y2 ij Figura 5.3: Histograma para Yij en el caso de astar, LLC 16BM y asociatividad 1, separando por zona de memoria. memoria que se leen consecutivamente, tanto en una orientación como en la otra. En estas zonas, la probabilidad de leer una línea posterior (cercana) es la misma independientemente de que se encuentre al principio o al nal de la ventana espacial. Por tanto, no se verica que pijk =pijαk . Un modelo alternativo con pijk =pijαk i podría explorarse, pero parece demasiado complejo, y ya hemos comprobado que éste no es un buen camino. Por tanto, una vez desechados los modelos binomiales, pasamos a otra aproximación, que utiliza igualmente el chero de localidad temporal. 5.2. Segunda propuesta: información inmediata anterior Como hemos podido comprobar en el ejemplo de astar de la tabla 5.1, existe una fuerte relación entre X1 ij y Y2 ij , así como también entre X2 ij y Y1 ij . Esto parece lógico, pues el pasado de lo que ha sucedido detrás puede ayudarnos a pedecir el futuro de lo las líneas posteriores, y viceversa. Si estamos en una zona de memoria grande donde leemos secuencialmente hacia delante y la ventana espacial es lo sucientemente pequeña, es bastante probable que X1 ij =Y2 ij =S . En este caso, podríamos utilizar directamente X1 ij para decidir si merece la pena cachear todo el bloque posterior, y lo mismo se aplica con X2 ij para cachear el bloque anterior. La tabla 5.2 muestra las correlaciones entre estas cuatro variables, medidas para astar, con una LLC de 16MB y asociatividad 1. Aquello que podíamos intuir sobre la relación de X1 ij y Y2 ij , y entre X2 ij y Y1 ij , se conrma conociendo la estructura de correlación. Este par de casos son los únicos con una correlación signicativa. En la gura 5.4 se encuentra un gráco de dispersión para Y2 ij frente a X1 ij . Cuanta más densidad de puntos haya en una zona, quiere decir que mayor es la frecuencia de esa situación. Por ejemplo, 112 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA El conjunto V contiene las direcciones de memoria que pueden ser accedidas. Como se direccionan líneas, y cada línea está compuesta por 64B, se verica que V⊆ { 0x000000000000, 0x000000000040, . . . ,0xFFFFFFFFFF80, 0xFFFFFFFFFFC0 } Las probabilidades πi, i = 1, . . . , N son desconocidas. Las probabilidades de transición aij también son desconocidas. Supondremos normalidad para la distribución de Y(t) , de forma que Y(t)|S(t) = qk∼ N (µk(t), σ2 k(t)) El valor de Y(t) se toma como un número en base hexadecimal, y ya queda denida bj(vk) . El procedimiento que se va a construir para estimar la secuencia S(t), t = 1, . . . , T es un procedimiento iterativo y voraz con una complejidad temporal O(n) . En el paso t , elegiremos el valor más plausible para S(t) , y se denotará como d S(t) . Una vez que la asignación a un grupo haya sido hecha, no será reconsiderada más adelante. El algoritmo para la estimación de la secuencia de grupos se describe mediante dos partes: hay que denir tanto los valores iniciales del procedimiento, como el paso iterativo . El paso iterativo se reere a cómo estimamos el valor de S(t+ 1) , una vez que conocemos d S(1),..., d S(t) . Al comienzo se debe determinar cómo estimar los primeros valores de la secuencia para poder comenzar con el procedimiento iterativo. 5.3.1. Paso iterativo Empezaremos describiendo el paso iterativo . Supongamos que estamos en el paso t+ 1 , y que conocemos el valor y(t+ 1) . El problema que hay que resolver es: ¾a qué grupo asignamos el instante t+ 1 ? ¾Cuál es el valor más probable para \ S(t+ 1) ? Deniremos en primer lugar aquel conjunto de estados de los que conocemos su existencia en tiempo t , para después mostrar la elección de \ S(t+ 1) . Denición 4. ( Conjunto de estados conocidos ). Si Q={q1, . . . , qN} es el conjunto total de estados, con N desconocido, se dene el conjunto de estados conocidos en tiempo t , Qc(t)⊆Q , como Qc(t) = nq∈Q:q∈nd S(1),..., d S(t)oo Podemos basar la decisión para \ S(t+ 1) en cálculo de probabilidades. Sea At+1 el suceso obtener un valor para Y(t+ 1) tan o más extremo que y(t+ 1) . Si conocemos el estado S(t+ 1) , entonces formalmente At+1|[S(t+ 1) = qk] = Y(t+ 1) −µk(t+ 1) ≥ |y(t+ 1) −µ(t+ 1)|∪ Y(t+ 1) −µk(t+ 1) ≤ − |y(t+ 1) −µ(t+ 1)| (5.7) Si conseguimos obtener, al menos una aproximación razonable, para P(S(t+ 1) = q|At+1),∀q∈Qc(t) , podremos decidir el estado más plausible teniendo 5.3. TERCERA PROPUESTA: MODELO OCULTO DE MARKOV 113 en cuenta la información observada (es decir, la línea de memoria). Podemos aproximar esta probabilidad con el teorema de Bayes . P(S(t+ 1) = qk|At+1) =P(S(t+ 1) = qk∧At+1) P(At+1)∝P(S(t+ 1) = qk∧At+1) = =P(S(t+ 1) = qk)·P(At+1|S(t+ 1) = qk) (5.8) donde el símbolo proporcional ∝ se utiliza para eliminar constantes de proporcionalidad que no dependan de k . Para continuar con la ecuación (5.8) necesitamos estimar tanto P(S(t+ 1) = qk) como P(At+1|S(t+ 1) = qk) . En cuanto a lo primero, no conocemos el número de estados que hay en total. Como no disponemos de más información, parece razonable tomar P(S(t+ 1) = qk) = 1 N (5.9) aunque no podemos conocer su valor exacto, al desconocer N . Con respecto a la estimación de P(At+1|S(t+ 1) = qk) , lo que queremos obtener es una medida acerca de cuán verosímil es que los parámetros de la Normal de la que procede y(t+ 1) sean µk(t+ 1) y σ2 k(t+ 1) . El cálculo es exactamente igual al del p-valor en un test normal de dos colas. Es bien sabido que un test de dos colas es adecuado en el caso en que podamos considerar tan inverosímil alejarnos por arriba o por debajo de la media (como en este caso), y que en dicha situación el p-valor es el doble que el de un test unilateral (gura 5.9). P(At+1|S(t+ 1) = qk) = PZ≥|y(t+ 1) −µk(t+ 1)| σk(t+ 1) +PZ≤− |y(t+ 1) −µk(t+ 1)| σk(t+ 1)  (5.10) donde Z∼ N(0,1) . Figura 5.9: Test de dos colas aplicado a la distribución Normal. 114 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA Si Φ se reere a la función de distribución de una N(0,1) , y teniendo en cuenta que Φ(x) = 1−Φ(−x) por simetría (gura 5.9), el cálculo se simplica a P(At+1|S(t+ 1) = qk) = 2Φ −|y(t+ 1) −µk(t+ 1)| σk(t+ 1)  (5.11) Combinando la información de (5.8), (5.9) y (5.11), podemos continuar desarrollando la expresión: P(S(t+ 1) = qk|At+1)∝P(S(t+ 1) = qk)·P(At+1|S(t+ 1) = qk) = =2 NΦ−|y(t+ 1) −µk(t+ 1)| σk(t+ 1) ∝Φ−|y(t+ 1) −µk(t+ 1)| σk(t+ 1)  (5.12) La ecuación (5.12) muestra que la probabilidad de obtener un valor de y(t+ 1) o más extremo, suponiendo que S(t+ 1) = qk , es directamente proporcional a la probabilidad buscada en un principio. Hemos podido reducir la ecuación inicial utilizando símbolos proporcionales en lugar de igualdades porque lo que nos interesa determinar es el estado qk donde se alcanza el máximo para P(S(t+ 1) = qk|At+1) , y para ello no necesitamos el valor exacto. La relación de igualdad exacta es P(S(t+ 1) = qk|At+1) = 2 N·P(At+1)Φ−|y(t+ 1) −µk(t+ 1)| σk(t+ 1)  (5.13) Como la primera parte no depende de k , queda claro así que arg max qk∈Qc(t) P(S(t+ 1) = qk|At+1) = arg max qk∈Qc(t) Φ−|y(t+ 1) −µk(t+ 1)| σk(t+ 1)  (5.14) De esta forma, elegiremos como valor para \ S(t+ 1) aquel estado conocido solución de (5.14), pero siempre que se supere un umbral. Cabe la posibilidad de que la línea y(t+ 1) sea una que pertenece a un estado aún no conocido, de ahí la necesidad de abrir la puerta para un nuevo estado y de establecer un umbral mínimo. Si no se llega a una mínima probabilidad, consideraremos que es el estado inicial de un nuevo grupo, ya que no resulta plausible ubicarlo en ninguno de los grupos actuales. Denición 5. ( Estado más probable ). Sea Qc(t) el conjunto de estados conocidos en tiempo t , pmax(t+ 1) = m´axq∈Qc(t)P(S(t+ 1) = q|At+1) , y pmin un umbral mínimo para la probabilidad. Se dene el estado más probable en tiempo t+ 1 , qmp(t+ 1) , como sigue. qmp(t+ 1) = (arg maxq∈Qc(t)P(S(t+ 1) = q|At+1) si pmax(t+ 1) ≥pmin un nuevo estado qn, con qn/∈Qc(t) si pmax(t+ 1) < pmin 5.3. TERCERA PROPUESTA: MODELO OCULTO DE MARKOV 115 Como estado asignado en el instante t+ 1 elegimos el estado más probable de la denición anterior: \ S(t+ 1) = qmp(t+ 1) . No obstante, según lo especicado en la ecuación (5.13), no podemos conocer directamente pmax(t+ 1) al desconocer N y P(At+1) , por lo que difícilmente podemos comprobar si pmax(t+ 1) ≥pmin . Consideremos en su lugar p0 max(t+ 1) = m´axqk∈Qc(t)Φ−|y(t+1)−µk(t+1)| σk(t+1)  y p0 min un umbral mínimo para la probabilidad p0 max(t+ 1) . Entonces es evidente que existe una biyección entre pmin y p0 min dada por la relación de igualdad de (5.13): pmin =2p0 min P(At+1)·N (5.15) Esta biyección permite determinar el estado más probable de una manera práctica, qmp(t+ 1) = (arg maxqk∈Qc(t)Φ−|y(t+1)−µk(t+1)| σk(t+1)  si p0 max(t+ 1) ≥p0 min un nuevo estado qn, con qn/∈Qc(t) si p0 max(t+ 1) < p0 min (5.16) utilizando los valores de Φ−|y(t+1)−µk(t+1)| σk(t+1)  , sin necesidad de conocer las probabilidades reales, y asegurando la denición 5 (aunque sin conocer el valor exacto de pmin ). La desventaja principal es que, si utilizamos el valor de p0 min y la equivalencia de la ecuación 5.16, el valor de pmin depende de t (a través de At+1 ). Esto provoca que, al jar p0 min en el procedimiento iterativo de calcular el estado más probable, estamos considerando diferentes umbrales de probabilidad pmin en cada paso. Para solucionar este problema podemos aprovecharnos de la estructura de probabilidad de la normal. Previsiblemente, P(At+1) será un valor no muy grande, pero que no podemos conocer al no conocer todos los estados. Las colas de la distribución normal no son pesadas, de manera que encontrar valores muy alejados de la media (digamos, por ejemplo, más de tres veces su desviación estándar) es poco probable. Si un valor está muy alejado de todos los grupos conocidos hasta el momento, todas sus probabilidades serán enormemente pequeñas, por lo que podemos permitirnos un umbral pequeño para pmin . Si la elección de p0 min es lo sucientemente pequeña, los cambios que sufre pmin no serán muy relevantes, pues serán de órdenes muy pequeños. No parece demasiado importante si pmin = 0.001 o pmin = 0.0005 , puesto que cuando no pertenece a ningún grupo esperamos valores de pmax(t+ 1) por debajo de ambos. Teniendo esto en cuenta, queda la elección de un umbral adecuado p0 min que proporcione buenos resultados. Se ha comprobado empíricamente que un valor adecuado puede rondar en torno a p0 min = 0.000025 . Éste será el valor utilizado en el procedimiento iterativo. Otro de los asuntos que resta resolver para el cálculo del estado más probable según la ecuación 5.16 es la estimación de µk(t+1) y σk(t+1) , ∀qk∈Qc(t) . La estimación de estos valores es crítica para poder aproximar correctamente Φ−|y(t+1)−µk(t+1)| σk(t+1)  y, por tanto, elegir de forma adecuada el estado más probable. Para ello introducimos una nueva denición, así como nueva notación que simplique la expresión. 116 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA Denición 6. ( Estado más cercano ). Sea Qc(t) el conjunto de estados conocidos en tiempo t , y qk∈Qc(t) un estado. Se dene el estado más cercano a qk en tiempo t como aquel estado qk0 que verica qk0= arg min qi∈Qc(t) |µk(t)−µi(t)| Sea nk(t) el número de elementos asignados al estado qk en tiempo t , nk(t) = Pt i=1 I(d S(i) = qk) . Los elementos de la secuencia Y(t), t = 1, . . . , t asignados al estado qk se denotan como yk,1, yk,2, . . . , yk,nk(t) . La estimación de µk(t+ 1) y σk(t+ 1) , \ µk(t+ 1) y \ σk(t+ 1) respectivamente, se actualiza cada vez que un nuevo elemento es asignado al estado correspondiente. El cálculo del estimador distingue entre varias situaciones. Si nk(t)=1 estamos hablando de un grupo con un sólo elemento. En este caso, se toma \ µk(t0) = yk,1, t0≥t (5.17) Por otro lado, obtener un buen valor para \ σk(t0), t0≥t es más complicado. Sea tk el instante en el que se asignó la primera observación al estado qk . Esto ocurrió porque la probabilidad de pertenencia a cualquier estado conocido en tiempo tk no era lo sucientemente grande, por lo que se asigna dicha observación a un estado no conocido en ese momento. Sea qk0 el estado más cercano a qk en tiempo tk . De esta forma se toma \ σk(t0) = m´ın (10 \ σk0(tk), σmax), t0≥tk (5.18) donde σmax es una cota superior para la estimación de σk(t0) y no puede superarse en ningún momento. La justicación de esta decisión es simple: se elige la desviación estándar del grupo más cercano porque se espera que el comportamiento sea similar al comienzo. Se multiplica por un factor de 10 para asegurar que la desviación estándar es lo sucientemente amplia como para permitir que las observaciones cercanas caigan en el nuevo grupo con una probabilidad razonable. Cuando haya más observaciones asignadas a este estado, entonces la estimación para la desviación estándar será más pequeña y se irá adaptando a las nuevas observaciones. La cota superior σmax se utiliza para evitar que la desviación estándar crezca más de la cuenta. Un valor plausible es σmax = 200 . Esto implica que el acceso a una línea con más de 400 líneas de diferencia con respecto a lo esperado se considera extraño (se toma 2σmax al ser un umbral característico cuando se habla de observaciones atípicas en una distribución Normal). Por otro lado, para evitar que la desviación estándar sea muy grande y se solape con las distribuciones de estados cercanos, se diseña una pequeña heurística de adaptación de la 5.3. TERCERA PROPUESTA: MODELO OCULTO DE MARKOV 117 desviación típica. En el momento de la creación del nuevo grupo, se comprueba si \ σk(tk)> |µk(tk)−µk0(tk)| 2 . Si se cumple esta condición, se toma como nueva estimación \ σnew k(t0) = \ σk(tk) 2, t0≥tk (5.19) Si la condición vuelve a violarse, el resultado vuelve a dividirse entre dos y así sucesivamente hasta que se verique. Esto asegura que una distribución con una desviación estándar estimada muy grande no robe elementos a otro grupo. Si 1< nk(t)≤5 , hablamos de estados que tienen más de una observación, pero aún son grupos pequeños. En este caso, se actualiza la estimación de la media y se utiliza la media muestral: \ µk(t0) = 1 nk(t) nk(t) X i=1 yk,i, t0≥t (5.20) Sin embargo, la estimación de la desviación estándar no cambia y sigue siendo la denida en el momento de la creación del grupo. Si nk(t)>5 , la estimación es más complicada. Sea Yk,1, . . . , Yk,nk(t) las variables aleatorias que denen la secuencia accedida en el estado qk . Consideramos un modelo de regresión lineal de la forma Yk,i =β0+β1·i+k,i, i = 1, . . . , nk(t) (5.21) con k,i ∼ N(0, σ2 k) . El proceso de estimación de los coecientes por el método de mínimos cuadrados para obtener ˆ β0 y ˆ β1 es ampliamente conocido [23]. Una vez conocida esta estimación, la predicción para una observación del análisis viene dada por dµk,i =ˆ β0+ˆ β1·i, i = 1, . . . , nk(t) Puede comprobarse [23] que un estimador insesgado para σk se obtiene de bσk=v u u t1 nk(t)−2 nk(t) X i=1 (Yk,i −dµk,i)2 De esta manera, la actualización de los estimadores relativos al estado qk utilizan la información del modelo lineal propuesto y \ µk(t0) = ˆ β0+ˆ β1·(nk(t) + 1), t0> t (5.22) \ σk(t0) =      1 si bσk≤1 bσk si 1<bσk< σmax σmax si bσk≥σmax , t0> t (5.23) La estimación de la media según la ecuación 5.22 permite adaptarse a una tendencia en el uso de las líneas de memoria. Como ya hemos comentado, es habitual ir leyendo en un orden 118 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA secuencial, y esta forma de estimar la media permitiría esta adaptación. Por otro lado, la estimación de la desviación típica según la ecuación 5.23 es la más razonable, puesto que el modelo lineal ha separado la tendencia del ruido. Adicionalmente, se considera una cota inferior y superior. La cota superior sirve al mismo propósito que el explicado en el primer caso: evita que el valor se dispare. La cota inferior evita que se tome un valor tan pequeño que sea imposible considerar observaciones cercanas a un mismo grupo, además de evitar una estimación muy reducida para la desviación estándar de un hipotético nuevo grupo más cercano (nótese que en la creación de este nuevo grupo, se comenzaría con un valor muy pequeño para \ σk(t0) según la ecuación 5.18). En la práctica, veremos como en ocasiones es conveniente ajustar un modelo de regresión robusta en lugar de un modelo de regresión lineal normal. Las ventajas de utilizar estos modelos fundamentalmente radican en la detección de outliers y puntos muy inuyentes en el modelo. Existen procedimientos para ajustar un modelo reduciendo el peso de estas observaciones raras, y en ocasiones provoca unos mejores resultados (para nuestro propósito) que un modelo lineal habitual. No es el objetivo de este trabajo profundizar en los modelos de regresión robusta, y por tanto no se mostrarán los fundamentos teóricos del mismo. No obstante, veremos como en la práctica resulta conveniente ajustar un modelo de este tipo, y elegir dinámicamente cuál de los dos es más apropiado. Puede consultar más información en [24]. Por último, se considera una limitación en el tamaño del modelo lineal. El cómputo empieza a hacerse pesado a medida que crece el valor de nk(t) , así que en la práctica no se utilizan todos los valores en la regresión, sino que se limita a los últimos 500 . Con esto, ya tenemos completo el procedimiento para el paso iterativo. A grandes rasgos, los pasos que se siguen, suponiendo que nos encontramos en el instante t+ 1 , son los siguientes: 1. Determinar el estado más probable, qmp(t+ 1) , siguiendo las directrices de la ecuación 5.16. 2. Si el estado más probable es un estado conocido en tiempo t , entonces actualizamos la estimación de la media y la desviación típica relativa a dicho estado según lo especicado anteriormente. 3. Si el estado más probable es un estado nuevo, estamos creando un nuevo grupo. Debemos buscar el estado más cercano para obtener una estimación inicial de la desviación estándar y utilizar las ecuaciones 5.18 y 5.19 para determinar su valor. 5.3.2. Paso inicial Ahora que está denido el proceso de actualización y asignación de estados de forma iterativa, queda por especicar cómo creamos el primer grupo. Una vez que hay un grupo, el procedimiento continúa de forma natural. Mientras sea plausible asignar observaciones a dicho estado, se 5.3. TERCERA PROPUESTA: MODELO OCULTO DE MARKOV 119 continuará haciendo. En el momento en que una observación quede lo sucientemente alejada, crearemos un nuevo grupo. La elección del primer grupo es especialmente importante. Debemos asegurarnos de que realmente las observaciones escogidas forman parte de un mismo estado, pues si no estaremos cimentando un procedimiento sobre una mala base. Por ello, no está de más ser un poco más estrictos a la hora de elegir el primero. Consideremos los cinco primeros valores de la secuencia de accesos, y(1), y(2), y(3), y(4), y(5) . Nos preguntamos si todos ellos pertenecen a un mismo estado. Una consecuencia directa de grandes diferencias en estas cinco observaciones sería la obtención de un dendograma que muestre claramente la existencia de más de un grupo. Siguiendo un proceso similar al agrupamiento de aplicaciones (véase la sección 4), se propone un clustering ascendente jerárquico con el método de Ward para esta primera secuencia de observaciones. Para que sea más sencillo entender el criterio de decisión, se proponen dos ejemplos. Consideremos dos secuencias de valores, x1= (1,8,4,12,5) y x2= (1,8,97,5,94) . En la primera, parece que se pueden considerar como un grupo, mientras que en la segunda parece haber dos. En la gura 5.10 se muestran los dos dendogramas asociados. (a) Secuencia 1 (b) Secuencia 2 Figura 5.10: Dendogramas para las secuencias de ejemplo A la vista de la gura 5.10 podemos considerar que la secuencia 2 tiene dos grupos bastante marcados, no ocurriendo lo mismo en la secuencia 1. Sabemos esto gracias a que el cociente de alturas es mucho mayor en el segundo caso. Para la primera secuencia, las alturas (ordenadas) donde se producen las uniones en el dendograma son h1,1= 1, h1,2= 4, h1,3= 4, h1,4= 11 . Si calculamos los cocientes de cada altura con la inmediata anterior, obtenemos h1,2 h1,1= 4,h1,3 h1,2= 1,h1,4 h1,3= 2.75 . Al no haber grandes diferencias, se puede considerar como un único grupo. Por otro lado, para la segunda secuencia, las alturas son h2,1= 3, h2,2= 3, h2,3= 7, h2,4= 96 . Esto provoca unos cocientes entre alturas más grandes: h2,2 h2,1= 1,h2,3 h2,2= 2.3333,h2,4 h2,3= 13.71429 . 120 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA A la vista del dendograma y de las diferencias en las alturas, concluiríamos que la primera secuencia se considera un grupo, pero la segunda no. Para automatizar esto, podemos considerar un umbral de inicio, uini , de manera que si todos los cocientes de alturas son menores que uini se considera un estado válido. Denición 7. ( Primera secuencia reconocida ). Sea Y(t), t = 1, . . . , T una secuencia de accesos a memoria. Se dene la primera secuencia reconocida de longitud n a la secuencia Y(i), . . . , Y (i+n−1) , con i mínimo, de forma que si h1, . . . , hn−1 representan las alturas ordenadas calculadas para el dendograma según el método de Ward, se cumple que hi hi−1≤uini,∀i∈ {2, . . . , n −1} En nuestro procedimiento, buscaremos la primera secuencia reconocida de longitud 5 para formar el primer estado conocido. Sea Y(i), . . . , Y (i+ 4) esta secuencia. La asignación de estados para el comienzo del procedimiento es la siguiente: d S(j) = ∅, j = 1, . . . , i −1 d S(j) = q1, j =i, . . . , i + 4 (5.24) donde el símbolo ∅ se utiliza para mostrar que dicha observación no se asigna a ningún estado, y q1 se utiliza para representar el primer estado. Por otro lado, la estimación de la media y la desviación estándar se hace como sigue: \ µ1(t0) = 1 5 4 X j=0 Y(i+j), t0≥i (5.25) [ σ1(t0) = v u u t1 4 4 X j=0 Y(i+j)−µ1(i+j)2, t0≥i (5.26) que no es más que el cálculo de la media y cuasi-desviación muestral. Un buen umbral, comprobado empíricamente, ha resultado ser uini = 3 . Nótese que éste es un valor muy estricto: según este criterio, ni siquiera la secuencia 1 se considera como un grupo. Es preferible ser muy exigentes y despreciar más observaciones al principio, que ser permisivos, tomar un valor alto para uini , y que el primer estado sea asignado a una secuencia incorrecta. 5.3.3. Procedimiento completo Ahora que está denido tanto el paso inicial como el paso iterativo, queda completado el procedimiento de reconocimiento para el Modelo Oculto de Markov. En la gura 5.11 se encuentra el pseucodódigo del procedimiento completo. Cuando hemos comenzado a describir esta técnica, hemos comentado la posibilidad de que exista ruido en los accesos a memoria: ciertas peticiones de lectura o escritura que no se encuadren bien dentro de los demás grupos. Sin embargo, el procedimiento que hemos detallado no permite 5.3. TERCERA PROPUESTA: MODELO OCULTO DE MARKOV 121 Entrada : Secuencia de accesos a memoria (en número de línea), Y(t), t = 1 ...,T . Salida : Estimación de los estados, d S(t), t = 1 ...,T . Algoritmo : Encontrar la primera secuencia reconocida de longitud 5, Y(i), . . . , Y (i+ 4) Asignar d S(j) = ∅, j = 1, . . . , i −1 Asignar d S(j) = q1, j =i, . . . , i + 4 Calcular \ µ1(t0) = 1 5P4 j=0 Y(i+j), t0≥i Calcular [ σ1(t0) = q1 4P4 j=0 Y(i+j)−µ1(i+j)2, t0≥i Para cada t=i+ 5, . . . , T , hacer Obtener el conjunto de estados conocidos, Qc(t−1) Determinar p0 max(t) = m´axqk∈Qc(t−1) Φ−   y(t)− \ µk(t)   \ σk(t+1)  Obtener el estado más probable, qk=qmp(t) (ecuación 5.16) Asignar d S(t) = qk Si qk∈Qc(t−1) (probabilidad de pertenencia sucientemente alta), entonces Si nk(t)≤5 , entonces Actualizar \ µk(t0) = 1 nk(t)Pnk(t) i=1 yk,i, t0≥t Si no , entonces Plantear el modelo Yk,i =β0+β1·i+k,i Estimar β0 y β1 considerando una regresión lineal: c β1 0 y c β1 1 Estimar β0 y β1 considerando una regresión robusta: c β2 0 y c β2 1 Calcular d µ1 k,i =c β1 0+c β1 1·i, i = 1, . . . , nk(t) Calcular d µ2 k,i =c β2 0+c β2 1·i, i = 1, . . . , nk(t) Calcular b σ1 k=r1 nk(t)−2Pnk(t) i=1 Yk,i −d µ1 k,i2 Calcular b σ2 k (se omiten detalles) Determinar el mejor modelo, j= arg minz=1,2b σz k Actualizar \ µk(t0) = b βj 0+b βj 1·(nk(t) + 1), t0> t Actualizar \ σk(t0) =        1 si b σj k≤1 b σj k si 1<b σj k< σmax σmax si b σj k≥σmax , t0> t Fin-si Si no (creación de un nuevo grupo): Asignar \ µk(t0) = yk,1, t0≥t Determinar el estado más cercano a qk en tiempo t , qk0 Calcular \ σk(t0) = m´ın (10 \ σk0(tk), σmax), t0≥t Mientras [ σk(t)>|µk(t)−µk0(t)| 2 , hacer Asignar \ σk(t0) = \ σk(t) 2, t0≥tk Fin-mientras Fin-si Fin-para Fin Figura 5.11: Pseudocódigo para el reconocimiento de estados en el Modelo Oculto de Markov 128 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA ninguno. Por este motivo es necesario separar los accesos en zonas antes de proponer el mecanismo de prebúsqueda, que marcará el n de esta memoria y este trabajo. Consideremos un grupo cualquiera que ha sido reconocido y que está compuesto por varias observaciones. Por construcción, la secuencia de accesos asociada debe tener un comportamiento, tendencia, y formas parecidos. Examinando uno y sólo un grupo simultáneamente, y suponiendo que dicho grupo va a continuar en un futuro, podemos elaborar predicciones sobre los accesos posteriores. El abanico de opciones que se abre de cara a las predicciones futuras de un grupo de accesos a memoria es enorme. Entre las técnicas que podríamos usar, destacan las redes neuronales recurrentes, modelos ARIMA, suavizado exponencial, etc. Todos ellos tienen la característica fundamental de incorporar el tiempo en la predicción. Nótese que este tiempo debe ser entendido como si únicamente existiera esa secuencia de accesos; aunque haya habido accesos anteriores, la primera observación en un nuevo grupo se encuentra en tiempo 1, y de igual forma, aunque existan accesos intercalados a otros grupos, la segunda observación clasicada en dicho grupo se encontrará en tiempo 2. Si recordamos el propósito de este TFG, buscamos utilizar una memoria SDRAM como una caché sobre una RRAM mucho más grande. En cuánto a tamaños, podría pensarse en una caché SDRAM de 16 o 32GB, sobre una RRAM mucho mayor. En la gura 5.15 se muestra un diagrama de la jerarquía de memoria propuesta para acoplar una SDRAM a la RRAM subyacente. El controlador de la SDRAM es una unidad que se encarga de los cálculos necesarios para el reconocimiento de grupos y de la prebúsqueda. Nótese que, dada la naturaleza del procedimiento oculto de Markov, se soportan varias tareas simultáneamente trabajando en zonas diferentes de memoria. Según el diagrama de la gura 5.15, las peticiones a memoria SDRAM serían capturadas por el controlador de la SDRAM, que dispone del mecanismo de prebúsqueda. Mientras se satisface la operación recibida del anterior nivel en la jerarquía de memoria, se realizan las operaciones necesarias para encuadrar el nuevo acceso en algún estado o grupo. Una vez ubicado, se determina si es necesario traer alguna línea con el mecanismo de prebúsqueda (que se expondrá a continuación), y se traslada la orden a la RRAM situada en el nivel inferior. Al disponer de una SDRAM más grande, podemos permitirnos un cierto grado de desperdicio en la caché: podemos traer ciertas líneas aunque no tengamos una certeza grande sobre su uso futuro. Esto no implica traer toda la aplicación, o todas las zonas colindantes a una línea cada vez que su uso, pero nos permite cierta libertad a la hora de diseñar el mecanismo de prebúsqueda. De entre todas las posibilidades, vamos a optar por un enfoque sencillo y utilizar la regresión lineal sobre el tiempo. Sea Yk={Yk,1, . . . , Yk,nk} el vector aleatorio que contiene la secuencia de observaciones asignadas al estado qk . Se asume un modelo de regresión lineal (similar al considerado anteriormente) como sigue. Yk,i =β0+β1·i+k,i, i = 1, . . . , nk (5.28) 5.5. PREBÚSQUEDA 129 Figura 5.15: Diagrama de la arquitectura SDRAM-RRAM propuesta. con k,i ∼ N(0, σ2 k) . Una vez estimados los coecientes b β0 y b β1 por el método de mínimos cuadrados, podemos elaborar predicciones. En concreto, nos interesa la predicción para el siguiente instante en que un acceso a memoria sea asignado a qk . El valor buscado es: \ Yk,nk+1 =ˆ β0+ˆ β1·(nk+ 1) (5.29) Sin embargo, de esta estimación puntual surgen varios problemas: El siguiente valor para Yk,nk+1 será un número entero, correspondiente a la línea de memoria accedida, pero esta restricción no existe en la ecuación 5.29. La predicción puntual, una vez redondeada, tiene una probabilidad muy baja de acertar debido al ruido que existe. En lugar de utilizar una estimación puntual, se propone utilizar un intervalo de predicción para el modelo lineal de la ecuación 5.28 [23]. Es bien sabido que, en el caso general, si X es la matriz de diseño del modelo, un intervalo de predicción para Yk,i viene dado por c Yk,i ±tnk−2,1−α 2qˆσk21 + xt i(XtX)−1xi (5.30) donde bσk=q1 nk−2Pnk i=1 (Yk,i −dµk,i)2 es una estimación insesgada para σk , xi="1 i# , y tnk−2,1−α 2 es el cuantil 1−α 2 de una distribución t -student con nk−2 grados de libertad. El intervalo de 130 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA predicción garantizaría una conanza de aproximadamente un 100(1 −α) % de que el verdadero valor se encuentra dentro del intervalo. La matriz de diseño del modelo propuesto es muy sencilla, pues tan sólo es necesario estimar dos parámetros: X=      1 1 1 2 . . .. . . 1nk       (5.31) Los cálculos necesarios para obtener una expresión particular de la ecuación 5.30 pasan por obtener (XtX)−1 . En este caso particular es muy sencillo: XtX="Pnk i=1 1Pnk i=1 i Pnk i=1 iPnk i=1 i2#="nk nk(nk+1) 2 nk(nk+1) 2 nk(nk+1)(2nk+1) 6# (5.32) La inversa de esta matriz existe y es sencilla de hallar, siempre que nk>1 : (XtX)−1=1 nk(nk−1) "2(2nk+ 1) −6 −612 nk+1# (5.33) En concreto nos interesa un intervalo de predicción para la siguiente línea de memoria, Yk,nk+1 . En este caso xnk+1 ="1 nk+ 1# , por lo que continuamos la particularización de la expresión 5.30 de la forma que sigue. xt nk+1(XtX)−1xnk+1 =2(2nk+ 1) nk(nk−1) (5.34) El intervalo de predicción buscado resulta, nalmente, \ Yk,nk+1 ±tnk−2,1−α 2sˆσk21 + 2(2nk+ 1) nk(nk−1) (5.35) con una conanza del 100(1 −α) % de que el verdadero valor para Yk,nk+1 esté dentro. Sea \ Yl k,nk+1 el extremo inferior del intervalo, y \ Yu k,nk+1 el extremo superior. \ Yl k,nk+1 = \ Yk,nk+1 −tnk−2,1−α 2rˆσk21 + 2(2nk+1) nk(nk−1) \ Yu k,nk+1 = \ Yk,nk+1 +tnk−2,1−α 2rˆσk21 + 2(2nk+1) nk(nk−1) (5.36) Sean bxc y dxe las funciones de redondeo por abajo y por arriba, respectivamente. Consideremos la secuencia de valores b \ Yl k,nk+1c,...,d \ Yu k,nk+1e , que representa un grupo de posibilidades para la dirección de la siguiente línea accedida, con una conanza aproximadamente del 100(1 −α) . El mecanismo de prebúsqueda que se plantea trata todas estas líneas con la misma 5.5. PREBÚSQUEDA 131 probabilidad de ser elegidas . Por tanto, y aprovechando que la caché SDRAM dispondrá de una capacidad razonable, se trae a la caché SDRAM todo el bloque colindante de direcciones. No obstante, existen ciertas restricciones. Recordemos que en la sección 5.3 hemos descrito un valor umbral ng que se exige a todos los estados reconocidos para ser considerado como un grupo válido. Anteriormente habíamos establecido ng= 100 . De esta forma, al pseudocódigo de la gura 5.11 le añadimos los siguientes pasos: 1. Si qk es el estado al que se ha asignado la observación Y(t) , y se cumple que nk(t)≥ng , se realiza una prebúsqueda y se prosigue en el paso siguiente. En caso contrario, no se continúa. 2. Se escogen las 100 últimas observaciones que han sido asignadas a qk , Yk,nk(t)−99, . . . , Yk,nk(t) . 3. Se plantea el modelo de la ecuación 5.28, se estiman los coecientes β0 y β1 , y se calcula la estimación puntual \ Yk,nk+1 =ˆ β0+ˆ β1·(nk+ 1) . 4. Obtenemos la secuencia b \ Yl k,nk+1c,...,d \ Yu k,nk+1e utilizando la expresión 5.35, y con una conanza del 90% ( α= 0.1 ). 5. El prebuscador efectúa la orden de traer a la SDRAM todas las líneas de la secuencia anterior. Para ilustrar de forma gráca cuáles son las posibilidades de este procedimiento, se presentan de nuevo los grupos mostrados en la sección anterior (gura 5.14). Esta vez, se muestra adicionalmente una banda roja que corresponde al intervalo de predicción, calculado con el procedimiento descrito anteriormente, y utilizando los últimos 100 valores del grupo. Nótese que según los pasos especicados no se realiza una prebúsqueda hasta que el grupo está compuesto por lo menos por 100 accesos, aunque en los grácos se muestra el intervalo desde el principio. Para estas primeras observaciones, no se realizaría la prebúsqueda. En el caso del grupo secuencial (gura 5.14 a), el intervalo de predicción comienza siendo elevado debido al salto inicial. A partir de la observación número 101, la primera no se tiene en cuenta para realizar la prebúsqueda, por lo que la amplitud del intervalo decrece. Además, al tratarse de un grupo perfectamente secuencial, el intervalo de predicción contiene exactamente un único punto. Es por esto que en grupos secuenciales, el mecanismo de prebúsqueda tiene un excelente potencial. Por otro lado, es lógico, pues son los grupos más predecibles que nos podremos encontrar. Para el grupo con tendencia creciente (gura 5.14 b) podemos comprobar cómo el intervalo de predicción permite ajustar una pequeña curva que va adaptándose a la forma de los datos. Esto se debe a la utilización de los últimos 100 valores para el cálculo, lo que anula la inuencia del principio, y permite ir adaptándose a una velocidad aceptable. Al utilizarse α= 0.1 , se estima que aproximadamente el 10 % de los accesos no son capturados correctamente por el método de prebúsqueda. Variaciones en el valor de α provocan directamente un cambio en la amplitud del intervalo de predicción, que repercute a su vez en un aumento o disminución del número de líneas traídas a la SDRAM. 132 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA (a) Grupo secuencial (lbm) (b) Grupo con tendencia (astar) (c) Grupo sin tendencia (Firefox) (d) Grupo impredecible (Firefox) Figura 5.16: Ejemplos de grupos reconocidos por el procedimiento oculto de Markov junto con intervalos de predicción 5.5. PREBÚSQUEDA 133 En el caso del grupo sin tendencia (gura 5.14 c) las bandas rojas sugieren un estrechamiento progresivo en las direcciones de memoria accedidas, pero siempre en torno a un rango de valores especíco. Para el último grupo (5.14 d), los cambios en el comportamiento de los accesos a memoria ocasionan grandes cambios en la estructura de los intervalos de predicción. No obstante, aún así hay un gran número de accesos que son capturados dentro de las bandas. Puede parecer que el mecanismo de prebúsqueda que se propone tiene un alto desperdicio de la caché, pues por cada línea accedida se traen numerosas líneas colindantes. Sin embargo, aquí entra en juego el intervalo de predicción inmediato anterior, por lo que en la mayoría de ocasiones el número de líneas nuevas traídas por cada acceso será bastante reducido. Ilustremos esto con los cuatro ejemplos de la gura 5.14. En el caso del grupo secuencial, tras cada acceso examinado, el procedimiento de prebúsqueda determinará que la siguiente línea es la única candidata para ser prebuscada, por lo que se trae exactamente un elemento extra. En el caso del grupo con tendencia, el intervalo de predicción parece tener una amplitud de unas 100 líneas intermedias. Supongamos que en un cierto instante t deben traerse a mayores unas 100 líneas extra. Muchas de ellas habrán sido traídas en el instante anterior, ya que la intersección de ambos intervalos de predicción contendrá un número muy grande de líneas. Por tanto, aunque el mecanismo de prebúsqueda determine 100 líneas extra, muchas de ellas ya se encontrarán en la SDRAM y para las que sólo es necesario actualizar ciertas estadísticas (como el instante en el que fue traída). Algo similar ocurre en el grupo sin tendencia y en el grupo impredecible. Con respecto al primero, el intervalo parece estrecharse con el tiempo, pero siempre en torno a un valor, por lo que casi todas las líneas ya han sido traídas antes. En el grupo impredecible será necesario traer alguna más. Nótese además que los cálculos necesarios en este mecanismo de prebúsqueda no son triviales. Todo ello consume tiempo y recursos, y mientras tanto la SDRAM puede seguir recibiendo peticiones de los niveles superiores. No es tanto problema la complejidad de los cálculos a este nivel, puesto que en los niveles superiores ya hay una jerarquía de caché a la que el procesador podrá acceder, y por ende pasará más tiempo entre dos accesos consecutivos a la SDRAM. Según la jerarquía propuesta, el controlador de la SDRAM va recibiendo peticiones de acceso y, mientras la SDRAM sirve la petición a los niveles superiores, el controlador ubica el acceso en un grupo y solicita a la RRAM traer las líneas que sean necesarias. En esta arquitectura será necesario añadir alguna estructura de datos para poder almacenar una cola de peticiones tanto a la SDRAM como a la RRAM inferior. Tan sólo resta una simulación de la arquitectura propuesta para conocer las posibilidades que ofrece esta técnica en las aplicaciones reales. En la siguiente sección se propone un marco de simulación y los resultados producidos, con lo que concluiremos este capítulo y también esta memoria. 134 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA 5.6. Resultados de la prebúsqueda Para nalizar esta sección, proponemos un marco de simulación que permita conocer cuán bueno es el mecanismo de prebúsqueda sobre las aplicaciones reales consideradas. Para cada una de las 20 aplicaciones, simularemos que las peticiones de lectura y escritura llegan a una caché SDRAM. Si ésta puede satisfacer las peticiones al nivel superior lo hará inmediatamente, pero en caso negativo solicitará a la RRAM inferior el dato correspondiente. Se proponen tres condiciones para simular la caché: En la primera simulación consideraremos una caché SDRAM ideal, sin límite de tamaño, pero con un umbral de olvido de 25.000 accesos. Esto quiere decir que, aunque no existe un número máximo para las líneas que pueden almacenarse simultáneamente en la SDRAM, todas aquellas que lleven más de 25.000 peticiones intermedias sin ser utilizadas son desechadas. Esta caché ideal se supone con un sólo conjunto. Una caché SDRAM con 16MB de capacidad y asociatividad por conjuntos de nivel 4. No se considera umbral de olvido. Una caché SDRAM con 64MB de capacidad y asociatividad por conjuntos de nivel 8. Tampoco hay umbral de olvido. La razón para utilizar cachés SDRAM de pequeño tamaño, a pesar de que los objetivos iniciales se referían a cachés de gran capacidad, es el número de peticiones consideradas en la simulación. Habitualmente vamos a considerar unos 5 millones de accesos, por lo que si realizamos la prueba con una SDRAM muy grande, todo el conjunto de trabajo se podrá localizar en la caché, no habrá reemplazos, y la simulación no contendrá ningún tipo de información válida. El tamaño de la caché simulada se ha elegido teniendo en cuenta el número de accesos recibidos. Para cada uno de estos tres tipos de caché, se realizan dos simulaciones: En una de ellas, no se considera el mecanismo de prebúsqueda. Una línea sólo es traída a la caché SDRAM cuando es requerida, y se almacena por si en un futuro vuelve a ser necesitada. Sólamente se basa en la localidad temporal . En la otra, además de mantener una línea en la caché cuando se utiliza, también se considera el mecanismo de prebúsqueda descrito. Cuando una línea se encuadra dentro de un grupo y hay un número suciente de ellas, la cache SDRAM elabora una predicción basada en un modelo lineal y solicita a la RRAM el contenido de todas las líneas resultantes. Por tanto, en esta simulación, estamos aprovechando la localidad temporal y espacial . Adicionalmente, en todos los casos, consideraremos las siguientes características: 5.6. RESULTADOS DE LA PREBÚSQUEDA 135 Los bits menos signicativos de la línea, despreciando el oset , sirven para elegir el número de conjunto al que pertenece dicha línea en la caché SDRAM, según se explicó en el Capítulo 2. En la gura 2.4 (página 34) pueden encontrarse más detalles sobre esta división. Esto garantiza que líneas consecutivas elegidas en el procedimiento de prebúsqueda vayan a conjuntos diferentes, evitando así reemplazos innecesarios. Todas las líneas elegidas en el mecanismo de prebúsqueda acabarán en la caché, pues es imposible que se solapen los números de conjuntos. Nótese que esto convierte a la asociatividad en el principal límite de la caché: se espera un correcto funcionamiento siempre que la asociatividad sea de al menos el número de grupos a los que se accede simultáneamente. Si una aplicación accede intercaladamente a 4 zonas de memoria, pero la asociatividad sólo es de nivel 2, pueden producirse reemplazos entre la prebúsqueda de estas 4 zonas y disminuir notablemente el rendimiento. Se utiliza una política de reemplazo LRU en cada conjunto. Cuando una línea deba ser traída a la caché SDRAM, primero se comprueba si ya se encontraba allí. En caso armativo, se actualiza el instante de uso de dicha línea, pero si no es así debe ser traída de la RRAM. Si no hay más espacio en el conjunto, la víctima que será desalojada es aquella que lleva más tiempo sin usarse. Véase el Capítulo 2 para más detalles sobre las políticas de reemplazo. Se considera un acierto de caché siempre que una petición pueda ser satisfecha a nivel de SDRAM, sin tener que recurrir al nivel inferior para conseguir la información. El sistema de memoria llevará un registro sobre las peticiones de memoria en todo momento, registrando el uso de cada línea cuando sea necesario. Una línea se puede encontrar en la caché por dos motivos: fue traída porque se necesitaba, o porque fue prebuscada. En caso de que se necesite una línea pero no se encuentre en la SDRAM se considera un fallo. El controlador de la SDRAM llevará todas las estructuras de datos necesarias para la prebúsqueda: los grupos reconocidos hasta el momento por el modelo oculto de Markov, los estimadores de la media y la desviación estándar, el historial de la caché y los modelos de predicción. Todas estas simulaciones se realizan en R [25], por la facilidad de este lenguaje para el ajuste de los modelos necesarios, así como la versatilidad y exibilidad en cuánto al tipado de las estructuras de datos y variables (tiene un tipado muy débil). R es un entorno y lenguaje de programación con un enfoque al análisis estadístico. Apareció en 1993 ( Ross Ihaka y Robert Gentleman ) y adopta un enfoque de alto nivel. Se trata de un software libre diseñado para la comunidad estadística con enfoques de minería de datos, investigación biomédica, bioinformática y matemáticas nancieras. Permite una gran exibilidad, como cualquier usuario de R conoce, pero a costa de una menor eciencia en la ejecución donde, la interpretación en lugar de la compilación es, en gran medida, su causa. Para la simulación de la caché ideal se utilizan, como máximo, 500.000 accesos a memoria. Esta simulación es rápida y permite hacernos una idea sobre el funcionamiento del mecanismo 136 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA de prebúsqueda, y compararlo con el que no lo tiene. Para las simulaciones de las cachés 16/4 y 64/8 se tendrán en cuenta un máximo de 5.000.000 accesos de cada aplicación. Estas simulaciones requieren de un tiempo considerable dado el rendimiento de R, y a fecha de entrega de este TFG, existe una aplicación que aún se encuentra en examen. Para cada simulación individual, dada la conguración de la caché SDRAM, queremos conocer las siguientes estadísticas: 1. El número de accesos a memoria que se han examinado. 2. El porcentaje de accesos reconocidos , que deberá ser el mismo independientemente del modelo de caché. El único motivo por el que pueden diferir estos porcentajes es por una modicación de los parámetros (umbral de inicio, probabilidad mínima), o por una elección aleatoria en caso de empate de estados más probables. 3. El número de entradas totales que han pasado por la caché, teniendo en cuenta incluso las que se han desechado por la política de reemplazo. En denitiva, el número de veces que se ha tenido que crear una entrada. 4. El número de entradas actuales que hay en la caché en el momento de nalización de la simulación. 5. El número de reemplazos que han ocurrido en la caché. En la ideal, se considera un reemplazo eliminar la línea transcurrido el umbral de olvido. 6. El porcentaje prebuscado , que indica cuátas de las entradas de la caché SDRAM han sido traídas por orden del mecanismo de prebúsqueda y no por el requerimiento inmediato de una línea de memoria. En el caso de que no exista un mecanismo de prebúsqueda, se tiene un 0%. 7. El porcentaje de desperdicio , que indica cuántas de las entradas que se han creado en la caché no han sido nalmente utilizadas. Si no hay mecanismo de prebúsqueda, se tendrá un 0%. 8. El porcentaje de éxitos de caché. 9. El porcentaje de aciertos por prebúsqueda , que indica, de todos los aciertos existentes, cuántos se deben al mecanismo de prebúsqueda en lugar de a un acceso repetido basado en la localidad temporal (0% si no hay prebúsqueda). 10. El porcentaje de prebúsquedas útiles , que indica cuántas de las entradas que se han creado en la caché como orden del mecanismo de prebúsqueda han sido nalmente utilizadas. No debe confundirse con el porcentaje de desperdicio, que incluye también las líneas traídas por efecto de la localidad temporal. Si no hay mecanismo de prebúsqueda, se tendrá un 0%. 5.6. RESULTADOS DE LA PREBÚSQUEDA 137 5.6.1. Caché SDRAM ideal con umbral de olvido Aquí examinaremos los resultados de una caché SDRAM ideal con un umbral de olvido de 25.000 accesos, para cada una de las 20 aplicaciones, limitando el número de accesos examinados a 500.000. El objetivo es tener una primera comparación sobre las diferencias entre utilizar y no utilizar el mecanismo de prebúsqueda. Puesto que la prebúsqueda trata tanto la localidad temporal como la espacial, es de esperar que en todos los casos funcione mejor una caché con este mecanismo. Lo realmente interesante es determinar si dicha mejora es signicativa teniendo en cuenta la complejidad de la técnica. Para la presentación de los resultados incluiremos una tabla con los resultados numéricos, y un gráco. La gura 5.17 contiene información sobre el porcentaje de éxito de la caché ideal con y sin el mecanismo de prebúsqueda (representado con un círculo y una cruz, respectivamente). Además, como sabemos, incluir esta prebúsqueda ocasiona que cierta parte de la caché se desperdicie, pues habrá ciertas líneas que se traigan pero nunca sean requeridas. El porcentaje de desperdicio de la caché se representa con un triángulo. Una medida de eciencia de la técnica podría ser derivada de la comparación de las diferencias en los porcentajes de éxito con la tasa de desperdicio. Por otro lado, en la tabla 5.4 podemos encontrar las 10 características que hemos descrito arriba. La numeración de la columna de información corresponde al mismo orden en que estas estadísticas fueron especicadas. Como es sabido, el porcentaje de accesos reconocidos será el mismo haya o no prebúsqueda, pues no se ve inuido por ello. Para que la comparación se ajuste a la realidad lo máximo posible, se ha examinado el mismo número de accesos para cada posibilidad dentro de una misma aplicación. Se espera que el número de entradas totales de la caché, el número de entradas actuales, y el número de reemplazos aumenten al utilizar la prebúsqueda. Además, el porcentaje prebuscado, el porcentaje de desperdicio, el porcentaje de aciertos por prebúsqueda, y el porcentaje de prebúsquedas útiles, será siempre de 0% si ésta no se ha realizado. Especialmente interesante es la diferencia entre el porcentaje de éxitos de caché, tal y como aparece en la gura 5.17. Las aplicaciones que parecen beneciarse mucho más del mecanismo de prebúsqueda son bzip2, gobmk, lbm, libquantum, mcf, namd y sjend. En todos estos casos, la tasa de éxito aumenta notablemente y a costa de una baja tasa de desperdicio. Otras aplicaciones, como h264ref, milc, povray y Xalan, tienen una ganancia mucho menor, y a costa de un cierto desperdicio en la caché. Esto es porque estas aplicaciones tienen un comportamiento más difícil de reconocer, los intervalos de predicción son más amplios, y en consecuencia hay líneas prebuscadas que no se usan. La aplicación que tiene un mayor desperdicio de la caché es astar, llegando casi a un 50%. Por otro lado, aunque para algunas aplicaciones la prebúsqueda no proporcione una mejora tan grande, como milc, podemos comprobar en la tabla que el porcentaje de aciertos debido a la prebúsqueda no es despreciable. La prebúsqueda aumenta la tasa de éxito de un 74.13% a un 94.47% a costa de desperdiciar un 44.89% de la caché. Sin embargo, sólo el 52.5% de las prebúsquedas se utilizan. Esta aplicación, junto con astar, es la que tiene un menor índice de prebúsquedas útiles. 144 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA astar bzip2 Firefox g++ gcc Info Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. 1 249.164 249.164 615.821 615.821 5e+06 5e+06 5e+06 5e+06 5e+06 3.500.000 2 88.4951% 88.4951% 91.5649% 91.5649% 77.5941% 77.5941% 81.326% 81.326% 62.5091% 52.5763% 3 131.129 174.957 298.537 303.736 2.504.406 4.002.909 2.677.753 4.790.973 1.591.902 1.526.758 4 131.129 174.957 298.537 303.351 1.046.783 1.048.560 1.048.482 1.048.576 1.048.482 1.048.566 5 0 0 0 385 1.457.623 2.954.349 1.629.271 3.742.397 543.420 478.192 6 0% 91.9769% 0% 88.4703% 0% 78.7517% 0% 89.9538% 0% 56.4989% 7 0% 25.0507% 0% 1.7114% 0% 31.2104% 0% 40.6804% 0% 8.2658% 8 47.3724% 94.3664% 51.5221% 94.3133% 49.9119% 82.989% 46.4449% 90.3738% 68.162% 81.0241% 9 0% 75.5179% 0% 86.7597% 0% 78.3968% 0% 86.6124% 0% 58.005% 10 0% 72.7641% 0% 98.0656% 0% 60.3686% 0% 54.7764% 0% 85.3701% gobmk h264ref hmmer lbm libquantum Info Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. 1 5e+06 5e+06 2.648.497 2.648.497 3.351.430 3.351.430 5e+06 5e+06 5e+06 5e+06 2 95.8011% 95.8011% 81.7642% 81.7642% 95.7508% 95.7508% 99.9639% 99.9639% 99.9587% 99.9587% 3 439.968 458.208 322.396 338.547 472.291 475.281 4.999.990 5.000.583 528.043 528.370 4 439.968 458.208 322.396 338.547 472.291 475.281 1.048.576 1.048.576 528.043 528.370 5 0 0 0 0 0 0 3.951.414 3.952.007 0 0 6 0% 95.2281% 0% 69.8417% 0% 97.9681% 0% 99.9511% 0% 99.5359% 7 0% 3.9807% 0% 4.7707% 0% 0.6291% 0% 0.0119% 0% 0.0619% 8 91.2006% 99.5627% 87.8272% 96.145% 85.9078% 99.7119% 2e-04% 99.9511% 89.4391% 99.951% 9 0% 95.7853% 0% 49.0224% 0% 92.4977% 0% 99.9998% 0% 99.9804% 10 0% 95.8198% 0% 93.1693% 0% 99.3579% 0% 99.9881% 0% 99.9378% mcf milc namd omnetpp Openoce Info Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. 1 5e+06 5e+06 5e+06 5e+06 1.961.439 1.961.439 5e+06 5e+06 5e+06 5e+06 2 97.836% 97.836% 97.3394% 97.3394% 86.8271% 86.8271% 87.9315% 87.9315% 78.2115% 78.2115% 3 3.589.335 3.641.941 149.504 152.659 747.689 752.750 1.314.557 1.384.853 1.954.530 2.443.343 4 1.048.576 1.048.576 149.504 152.659 747.689 752.750 1.048.573 1.048.576 1.048.576 1.048.576 5 2.540.759 2.593.365 0 0 0 0 265.984 336.277 905.954 1.394.767 6 0% 96.814% 0% 93.5195% 0% 90.86% 0% 74.3714% 0% 61.3628% 7 0% 0.9628% 0% 2.0667% 0% 0.6723% 0% 4.969% 0% 17.935% 8 28.2133% 97.6794% 97.0099% 99.8021% 61.8806% 96.4923% 73.7089% 92.9016% 60.9094% 81.1192% 9 0% 98.8851% 0% 95.0254% 0% 91.7542% 0% 72.5325% 0% 59.6202% 10 0% 99.0055% 0% 97.7901% 0% 99.26% 0% 93.3187% 0% 70.7722% povray sjeng specrand sphinx3 Xalan Info Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. Sin pr. Con pr. 1 185.871 185.871 5e+06 5e+06 3.508 3.508 5e+06 5e+06 5e+06 5e+06 2 89.5261% 89.5261% 99.941% 99.941% 49.3444% 49.3444% 94.9335% 94.9335% 90.0227% 90.0227% 3 60.411 65.293 4.658.414 4.659.350 3.504 3.845 614.407 618.672 651.582 668.189 4 60.411 65.293 1.048.576 1.048.576 3.504 3.845 614.407 618.672 651.582 668.189 5 0 0 3609838 3610774 0 0 0 0 0 0 6 0% 47.2118% 0% 99.9008% 0% 44.6294% 0% 93.0272% 0% 52.9723% 7 0% 7.4771% 0% 0.0189% 0% 8.8687% 0% 0.6894% 0% 2.4854% 8 67.4984% 81.4565% 6.8317% 99.9076% 0.114% 39.3101% 87.7119% 99.1372% 86.9684% 93.7153% 9 0% 24.1348% 0% 99.998% 0% 99.7099% 0% 93.4953% 0% 35.4075% 10 0% 84.1627% 0% 99.9811% 0% 80.1282% 0% 99.2589% 0% 95.3082% Tabla 5.6: Comparación de la caché SDRAM con y sin prebúsqueda, suponiendo una SDRAM con conguración 64/8. 5.6. RESULTADOS DE LA PREBÚSQUEDA 145 Esto es debido a que, en muchos casos, se reutilizan líneas en instantes futuros. Además, al eliminar la restricción del umbral de olvido, ya no es necesario re-acceder a ella en menos de 25.000 accesos, puesto que ahora está limitado por el tamaño real de la caché; en muchos casos evitamos un reemplazo innecesario. La tasa de éxitos derivada de la localidad temporal también aumenta al pasar de una conguración SDRAM 16/4 a 64/8, puesto que hay menos reemplazos, y una línea vive más en la caché, teniendo más tiempo para ser aprovechada. La tasa de éxitos en el caso con prebúsqueda suele aumentar al pasar de la caché ideal a la caché 16/4, aunque en algunos casos se produce una ligera disminución. De nuevo, al pasar a una 64/8 también se produce una mejora. Hay muchas variaciones en cuanto a la tasa de desperdicio, tendiendo a aumentar al considerar más accesos y la caché 16/4. Sin embargo, al aumentar el tamaño, el desperdicio es cada vez menor. Con una conguración SDRAM 16/4, podemos distinguir los siguientes grupos, en función del impacto de la prebúsqueda: Las aplicaciones libquantum, lbm, mcf y sjeng funcionan extraordinariamente bien. Para la primera, la tasa de éxito pasa de un 0.0002% a un 99.9511%, debido en gran parte al buen reconocimiento en grupos con el modelo de Markov, con un desperdicio de tan sólo 0.0119%. Situaciones similares se producen en las demás. Existen otras aplicaciones donde ya había una componente de localidad temporal notoria, pero aún así la técnica ofrece estupendos resultados. Es el caso, por ejemplo, de astar, bzip2, gobmk y namd. La tasa de éxito aumenta, aunque a costa de algunas líneas desperdiciadas. Existen otras aplicaciones, como Firefox y g++, que también aumentan notablemente la tasa de éxito. En éstas, sin embargo, no llega a valores excesivamente altos, y la tasa de desperdicio es enorme. Para Firefox, el 62.25% de las entradas creadas en la caché no se utilizan nunca, mientras que para g++ este porcentaje es de casi el 80%. También podemos encontrar un grupo de aplicaciones cuya mejora es mínima, pues la localidad temporal ya hacía casi todo el trabajo (h264ref, hmmer, Xalan, sphinx3). Por otro lado, la conguración 64/8, en comparación, tiene unas tasas de desperdicio menores, mejores tasas de éxito, y proporciona mejores resultados en general. Aunque esto es esperable, la diferencia en el rendimiento de estas dos cachés puede darnos una idea sobre cuán exhaustiva es la técnica. En algunas aplicaciones podemos observar un gran número de reemplazos en la caché 16/4. Es el ejemplo de Firefox, donde la prebúsqueda lleva en total a desalojar más de 10 millones de entradas. En la conguración 64/8, el número de entradas desalojadas es de apenas 3 millones. La causa de esta diferencia será, probablemente, la propia prebúsqueda. Al utilizar una caché pequeña 146 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA en una aplicación exigente habrá colisiones, especialmente si los grupos están fragmentados y los intervalos de predicción son muy amplios. La prebúsqueda sobrecarga demasiado la caché, y muchas son desalojadas antes de tener tiempo de ser utilizadas. Con un tamaño mayor, la caché no está sometida a este estrés y puede implementar mejor la técnica. Con una conguración 64/8 podemos concluir que: lbm, mcf y sjeng siguen manteniendo un comportamiento muy bueno. Algo diferente ocurre en libquantum, donde el aumento de la caché hace que la localidad temporal tenga mucho más peso y que no se reemplacen las líneas tan fácilmente. La tasa de éxito sin prebúsqueda pasa de un 13.03% con una SDRAM 16/4, a un 89.43% con una 64/8. Las aplicaciones bzip2, astar, y namd mantienen un comportamiento similar. De forma similar a limquantum, la localidad temporal toma más peso en gobmk. Firefox y g++ mantienen su comportamiento, con una mejora general del rendimiento. Apenas se producen cambios donde las aplicaciones ya mostraban una fuerte localidad temporal. El número total de simulaciones es muy alto. Para cada una de las veinte aplicaciones se han tomado 6 escenarios distintos, y se presentan diez campos numéricos como resumen de cada par aplicación-escenario. Sería muy arduo e innecesario realizar una interpretación completa de todas las estadísticas presentadas en las tablas 5.5 y 5.6. En lugar de ello, vamos a elegir dos aplicaciones, una con un buen funcionamiento de la técnica, y otra donde se den algunos problemas. Vamos a considerar en primer lugar el ejemplo de Firefox, una de las aplicaciones con una menor tasa de éxito en la simulación con prebúsqueda. La técnica de Markov es capaz de reconocer tan sólo el 77% de los accesos, de forma que un número no despreciable (más de 1 millón) no se encuadra en ningún grupo. La caché 16/4 está siendo completamente utilizada: las 262.144 entradas que hay disponibles se encuentran en uso. Existe un gran número de reemplazos en los dos casos. Sin tener en cuenta la prebúsqueda, hay más de 3 millones de reemplazos, que ascienden hasta 10 millones al utilizar la técnica. El 86.21% de la caché está compuesta por entradas que han sido prebuscadas. Desgraciadamente, el 62.25% de las entradas creadas no se utilizan nunca, y sólo el 27.8% de las prebúsquedas son realmente utilizadas. A pesar de este desperdicio, la técnica permite aumentar la tasa de éxito notablemente, pasando de un 29.2689% al no haber prebúsqueda, a un 70.53%. Otra medida que asegura el benecio del prebuscador es el porcentaje de aciertos debidos a la prebúsqueda, que asciende a un 88.61%. A pesar de que Firefox es una aplicación compleja e interactiva, y de que no se reconocen todos los accesos, podemos estar satisfechos con el funcionamiento global. Con una caché SDRAM 64/8 obtenemos mejores resultados. Cuando no hay prebúsqueda se producen aproximadamente 1 millon y medio de reemplazos, cantidad que duplica cuando sí la hay. En este caso no se llena por completo la SDRAM de entradas de caché. La tasa de éxito pasa 5.6. RESULTADOS DE LA PREBÚSQUEDA 147 de un 50% a un 83% al considerar la prebúsqueda, y la tasa de desperdicio se reduce a la mitad: el 31.2% de las entradas no se utilizan. La cantidad de prebúsquedas que resultan útiles aumenta hasta un 60.36%, lo que conrma que unas prebúsquedas reemplazan a otras si la caché no tiene el tamaño suciente. No obstante, al ser también más complicado eliminar las entradas creadas por localidad temporal, el porcentaje de aciertos por prebúsqueda desciende de un 88.61% a un 78.4%. La causa de que Firefox sea una aplicación más difícil de clasicar en grupos es la fragmentación de los accesos a memoria. Como hablamos de una aplicación interactiva, que dispara muchos hilos, y realiza muchas tareas simultáneamente, es mucho más complicado distinguir zonas claras de uso de la memoria. De forma similar a lo que ocurría con gcc, la mayoría de los grupos reconocidos tienen un tamaño muy pequeño. En la gura 5.20 se encuentra el histograma para el tamaño de los grupos. Es claramente apreciable cómo la mayoría de grupos tiene menos de 2.000 elementos, muchos de ellos menos que 500 accesos. La prebúsqueda sólo se lanza cuando hay al menos 100 accesos en un mismo estado, por lo que un número muy elevado de grupos diculta la tarea. Figura 5.20: Histograma para el número de elementos que hay en cada grupo reconocido de la aplicación Firefox. En la gura 5.21 se muestran dos ejemplos de grupos reconocidos para Firefox. En la parte de la izquierda se representa un grupo pequeño, de 120 accesos, con una amplitud de 13 líneas de memoria. Podemos ver que muchas de las líneas se repiten con el tiempo, provocado por una LLC en el nivel superior que elige mal a sus víctimas. Además, muchas de las líneas que se deban traer con la prebúsqueda ya se encontrarán en la SDRAM. En la parte de la derecha tenemos un grupo fácil de reconocer, grande, y con una tendencia creciente. La prebúsqueda aquí tiene un potencial mucho mayor. Adicionalmente, en la gura 5.22 se han representado trozos de las peticiones de acceso en 148 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA (a) Grupo pequeño (b) Grupo grande Figura 5.21: Ejemplos de grupos reconocidos para Firefox diferentes puntos de la ejecución. Los colores indican una separación por los estados reconocidos en el modelo de Markov. En la izquierda tenemos una imagen donde los accesos se van alternando a dos zonas de memoria. En la derecha, los accesos están repartidos a lo largo de un espacio muy grande de direcciones, y es imposible detectar patrones. (a) Zona reconocible (b) Zona irreconocible Figura 5.22: Ejemplos de zonas de memoria para Firefox Como ejemplo de aplicación con excelente rendimiento en la arquitectura propuesta se elige mcf. El modelo oculto de Markov reconoce con éxito el 97.836% de los accesos a memoria producidos. En la gura 5.23 se encuentra el histograma del tamaño de los grupos. En total se reconocen 2391 estados diferentes, cuando en Firefox se tenían más de 7000. Aunque en el histograma parece que los grupos tienen un tamaño pequeño, existen tres grupos especialmente grandes que no aparecen en esta gura. El estado más grande tiene asignados 2.495.933 accesos de memoria, y los siguientes más destacados 934.729 y 102.405. Esto indica una gran facilidad para reconocer accesos, lo que repercute en el rendimiento del prebuscador. 5.6. RESULTADOS DE LA PREBÚSQUEDA 149 Figura 5.23: Histograma para el número de elementos que hay en cada grupo reconocido de la aplicación mcf. Tomando la conguración 16/4, la caché se utiliza completamente, y tanto cuando existe prebúsqueda como cuando no, hay aproximadamente 4 millones y medio de reemplazos. El número de entradas totales es ligeramente inferior al número de accesos examinados porque hay repeticiones en los accesos. Que el número de reemplazos no sea signicativamente más grande cuando el prebuscador actúa signica que los intervalos de predicción son muy estrechos y que hay muchos aciertos de caché. Concretamente, pasamos de un 3.8% a un 94.27% con la técnica. El desperdicio de la caché es mínimo, tan sólo un 1.98% de las entradas no se utilizan nunca. El 94.16% de ellas se crean por orden del mecanismo de prebúsqueda, y el 97.89% de todas estas entradas resultan nalmente útiles. La inmensa mayoría de aciertos (99.07%) se deben a la técnica. En la conguración 64/8, la tasa de éxito tomando sólo la localidad temporal pasa a un 28.21%, previsiblemente porque ya no hay tantos desalojos. La tasa de acierto asciende a un 97.67% al utilizar la prebúsqueda. Esta SDRAM de 64MB también está llena, aunque en total se crean aproximadamente un millón menos de entradas con respecto a la 16/4. La tasa de desperdicio también disminuye, siendo ahora de 0.9628%, y la tasa de prebúsquedas útiles supera el 99%. En la gura 5.24 se encuentran dos imágenes que corresponden a un grupo pequeño y otro grande de los reconocidos por el procedimiento de Markov. El grupo pequeño en este caso presenta una tendencia creciente, con el intervalo de predicción muy estrecho, lo que agiliza la prebúsqueda. El grupo grande, con aproximadamente 100.000 accesos, muestra un comportamiento creciente también. Los grupos son, en general, mucho más fáciles de reconocer que en Firefox. En la gura 5.25 se encuentra la imagen de un par de tramos en el recorrido de la aplicación. 150 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA (a) Grupo pequeño (b) Grupo grande Figura 5.24: Ejemplos de grupos reconocidos para mcf Las zonas son, en general, mucho menos caóticas que Firefox. En la izquierda tenemos una porción similar a la representada en la gura 5.22, mientras que en la derecha podemos ver un comportamiento regular, aunque con ligeros accesos a otras zonas separadas. (a) Zona 1 (b) Zona 2 Figura 5.25: Ejemplos de zonas de memoria para mcf Queda entonces mostrado el enorme potencial de la técnica desarrollada, en general para las 20 aplicaciones, y en particular para estos dos ejemplos. Esta técnica, compuesta en dos fases (la fase de separación de estados, y la fase de prebúsqueda), es capaz de aprender de las peticiones de acceso que llegan al sistema de memoria principal, y anticiparse a las necesidades de la LLC preparando el contenido con anterioridad. Incluso en aplicaciones donde no es posible reconocer muchos patrones, la tasa de éxitos aumenta signicativamente, aunque a costa muchas veces de 5.6. RESULTADOS DE LA PREBÚSQUEDA 151 un alto desperdicio. Todas las simulaciones realizadas en este apartado suponen una LLC con una conguración 16/1. Bajo este escenario, con una LLC de la que no se espera un comportamiento bueno, disponemos de mucha información a nivel de SDRAM. En una conguración 32/8, no siempre podremos esperar estos buenos resultados, pues muchas peticiones se resuelven en el nivel superior y la información nunca llega a la SDRAM. Cuanto peor sea la caché en niveles superiores, se espera que la técnica funcione mejor. Si por el contrario, las cachés de niveles superiores tienen un comportamiento muy bueno, entonces es menos probable que los resultados a este nivel tengan un potencial grande. Sea como sea, el conjunto de la jerarquía de memoria en general asegura un nivel de rendimiento muy bueno. 152 CAPÍTULO 5. MECANISMO DE PREBÚSQUEDA Conclusiones y trabajo futuro A lo largo de este Trabajo Fin de Grado hemos realizado un análisis exhaustivo de la localidad temporal, espacial y algorítmica de ciertas aplicaciones, a nivel de memoria principal. Para ello hemos utilizado ciertas aplicaciones de la suite SPEC2006, además de Firefox, Openoce, gcc y g++. Utilizando una herramienta de Intel, llamada Intel R  Pin, podemos monitorizar las peticiones de acceso a memoria que realiza la LLC y aprender de estos datos. Por un lado, la localidad temporal nos ha servido para agrupar aplicaciones con un comportamiento similar. Hemos utilizado algunas técnicas de clustering para diferenciar entre aquellas que volvían a acceder muy tempranamente a los datos y aquellas que no. Como la información de la que se disponía era muy abundante, la hemos resumido en histogramas de igual longitud, y hemos utilizado la medida de divergencia de Jensen-Shannon para valorar diferencias entre estos histogramas. Una vez realizado el agrupamiento, se ha comprobado que aquellas aplicaciones que acceden muy tempranamente a los datos tienen un comportamiento patológico de la caché de nivel superior, que puede estar producido por un tamaño demasiado pequeño o una mala elección de la asociatividad. Si la memoria de nivel superior ofreciera un mejor rendimiento, no sería necesario acceder a líneas repetidas. La localidad algorítmica ha sido estudiada en menor profundidad por la dicultad para ser comprendida y analizada, y por la fuerte dependencia de cada aplicación. Hemos examinado el perl de utilización de memoria, entendido como el número de operaciones solicitadas por unidad de tiempo, para cada una de las veinte aplicaciones, y hemos podido comprobar la existencia de ciertas estructuras y patrones regulares en el número de peticiones. En todos los casos, una caché LLC en el nivel superior con una conguración 16/1 ofrece peores resultados que las demás. Hay ciertas aplicaciones para las que aumentar la asociatividad resulta enormemente benecioso, pues se reduce el número de fallos por conicto. Otras, por contra, mejoran al aumentar el tamaño, evitando fallos de capacidad. Además, hay algunas aplicaciones que sólo mejoran su rendimiento al aumentar tanto la asociatividad como el tamaño. El análisis más detenido ha sido el correspondiente a la localidad espacial. En el Capítulo 5 hemos propuesto una arquitectura SDRAM-RRAM para mejorar la velocidad global del sistema, sin renunciar a las ventajas que ofrecen las memorias resistivas, entre las que se encuentra la no volatilidad. Junto a la memoria SDRAM hemos incluido un pequeño controlador, que se encarga de ir analizando las peticiones de memoria que se reciben del nivel superior, y aplica técnicas de reconocimiento de patrones para realizar una prebúsqueda. Aunque hemos examinado algunos 153