Repositorio Institucional de Documentos

2021 112 Alba Pedro Zapater Aportaciones al modelado del cálculo del WCET en entornos de memoria cache Director/es Segarra Flor, Juan Rodríguez Lafuente, Clemente © Universidad de Zaragoza Servicio de Publicaciones ISSN 2254-7606 Alba Pedro Zapater APORTACIONES AL MODELADO DEL CÁLCULO DEL WCET EN ENTORNOS DE MEMORIA CACHE Director/es Segarra Flor, Juan Rodríguez Lafuente, Clemente Tesis Doctoral Autor 2021 UNIVERSIDAD DE ZARAGOZA Escuela de Doctorado Programa de Doctorado en Ingeniería de Sistemas e Informática Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA TESIS DOCTORAL Aportaciones al modelado del cálculo del WCET en entornos de memoria cache Autora: Alba PEDRO ZAPATER Directores: Dr. Juan SEGARRA Dr. Clemente RODRÍGUEZ Memoria presentada para obtener el título de Doctora en informática en el Grupo de Arquitectura de Computadores de la Universidad de Zaragoza Departamento de informática e ingeniería de sistemas 17 de septiembre de 2020 II «Technology is not neutral. We’re inside of what we make, and it’s inside of us. We’re living in a world of connections — and it matters which ones get made and unmade.» Donna Haraway III UNIVERSIDAD DE ZARAGOZA Resumen Aportaciones al modelado del cálculo del WCET en entornos de memoria cache por Alba PEDRO ZAPATER1 Los sistemas de tiempo real cobran cada vez más importancia en numerosas áreas. Para lograr una buena planificación de estos sistemas se requiere un análisis preciso y seguro del peor caso de tiempo de ejecución (WCET) siendo el análisis de la jerarquía de memoria uno de los principales desafíos. En este trabajo nos centramos en mejorar la eficiencia de la jerarquía de memoria en los sistemas de tiempo real estricto en cuanto a su predictibilidad aunque también se consideran otros aspectos como el consumo energético. Este propósito se alcanza reduciendo tanto la cota del WCET como su tiempo de análisis y estudiando patrones de acceso a memoria en tareas relevantes en sistemas de tiempo real. Comenzamos analizando el impacto de la cache de instrucciones en el WCET, centrándonos en el método Lock-MS de análisis del WCET. A fin de usar este método diseñamos el algoritmo necesario para transformar el grafo de control del flujo del binario en una estructura en árbol. Este algoritmo reduce el tiempo de análisis del WCET sin perder precisión para una cache de instrucciones bloqueable. Proponemos una heurística de bloqueo dinámico basada en bucles que aplicada a este método permite obtener el contenido óptimo de cache para el WCET en cada una de las regiones determinadas por la heurística. Además de reducir el WCET, ya que explota el reuso temporal, también reduce su tiempo de análisis. A continuación, ampliamos el estudio del análisis del WCET considerando las instrucciones resultantes de la vectorización automática. Detectamos que la vectorización del código puede ser una buena opción para reducir de manera efectiva el WCET si ésta se lleva a cabo en aquellos bucles que concentran la mayor parte del tiempo ejecución. Por tanto, es conveniente invertir tiempo y recursos en una buena vectorización del código en el contexto de los sistemas de tiempo real. Para finalizar, centramos nuestro estudio en el impacto de la cache de datos estudiando el patrón de acceso a datos en la transposición de matrices y acotando su tasa ideal de aciertos en su versión tiling. De este estudio obtenemos unas expresiones con respecto a los parámetros de cache que garantizan que se alcanzará la tasa ideal de aciertos. Específicamente, cuando la dimensión del tile es igual al tamaño de línea de cache la tasa ideal de aciertos se alcanza con muy pocos conjuntos y tan solo dos vías en una cache asociativa por conjuntos. Además, comparamos nuestros resultados con un algoritmo de la transpuesta «indiferente» a los parámetros de la cache (oblivious). 1Está estrictamente prohibido usar, investigar o desarrollar, de manera directa o indirecta cualquiera de las contribuciones científicas de la autora de este trabajo por cualquier ejercito o grupo armado en el mundo, para propósitos militares o para cualquier uso en contra de los derechos humanos o de cualquier otra especie animal, así como del medio ambiente, a no ser que se cuente con su consentimiento escrito o, si no fuera posible, se deberá contar con el consentimiento escrito de todas las personas del planeta. V Agradecimientos Me gustaría agradecerles a todas las personas que me quieren y me han apoyado durante estos años: soy afortunada y son demasiadas para nombrarlas una a una. Hay muchos cuidados que no se ven sosteniendo todo este trabajo, sin los cuales no hubiera sido posible llegar hasta aquí. Gracias por recordarme una y otra vez que lo esencial es invisible a los ojos. Me gustaría agradecer a mis directores Juan y Clemente por todo el trabajo, aportaciones, consejo y sobre todo paciencia. Habéis sido los pilares que han resistido cada temporal al que nos hemos enfrentado. Gracias también a Rubén por todas sus aportaciones y sobre todo por tener siempre la puerta abierta para mí. Eternamente agradecida a Víctor, que además de aportar todo su conocimiento y experiencia ha sido un apoyo moral increíble. Muchas gracias por haber creído en mí y por toda la escucha. Por último, me gustaría agradecer al gaZ su acogida, apoyo y calidad humana que ya había recibido cuando tan solo era una alumna. Me siento muy afortunada de haber formado parte de este grupo. Y, por supuesto, no me puedo olvidar de mis compañeros doctorandos cuya amistad es una de las mejores aportaciones de esta tesis a mi vida. Muchas gracias por todos esos buenos momentos y también la compañia en los no tan buenos. Reinterpretando a Virginia Woolf, para desarrollar trabajo intelectual, además de un cuarto propio, es imprescindible contar con apoyo económico. Este trabajo se ha llevado a cabo gracias a la financiación recibida de las siguientes entidades y proyectos: Ayuda para la Formación del Profesorado Universitario. FPU14/02463. Ministerio de Educación, Cultura y Deporte. (2015-2020) Jerarquía de memoria y aplicaciones. TIN2013-46957-C2-1-P, Ministerio de Ciencia y Tecnología. (2013-2016) Arquitectura y programación de computadores escalables de alto rendimiento y bajo consumo. TIN2016-76635-C2-1-R, Ministerio de Ciencia y Tecnología. (2016-2019) Supercomputación y Eciencia. Consolider TIN2014-52608-REDC. Ministerio de Ciencia y Tecnología. (2014-2016) gaZ. Reconocimiento Grupo Consolidado de Investigación (T48,T58_17R), Diputación General de Aragón. HiPEAC Collaboration Grant. European Network of Excellence on High Performance and Embedded Architecture and Compilation. (2015) Construyendo Europa desde Aragón. Fondo Europeo de Desarrollo Regional (FEDER) en Aragón. (2014-2020) 2Capítulo 1. Introducción, estado del arte y objetivos FIGURA 1.1: Esquema del análisis temporal de sistemas. Figura tomada de [ARS13]. no a otras tareas del sistema de tiempo real [Ves07]. El análisis de planificabilidad se usa para predecir el comportamiento temporal mediante pruebas que determinan si se cumplirán las restricciones temporales en tiempo de ejecución [Sha+04]. Este análisis puede caracterizarse mediante distintos factores, que incluyen las restricciones del modelo computacional (e.g. uniprocesador, independencia de tareas, etc.) y la cobertura de las pruebas de planificabilidad. Las pruebas necesarias y suficientes son ideales, pero para muchos modelos son demasiado complejas (NP-difícil para modelos computacionales no triviales). Si se aborda el análisis con pruebas suficientes pero no necesarias suele ser más simple, pero más pesimista. Si la planificación falla, el sistema debe rediseñarse y repetir todos los procesos previos. Sea como sea, es imprescindible garantizar la planificabilidad antes de la ejecución del sistema y, como ya hemos señalado, para poder calcular si un sistema es planificable, es imprescindible conocer una cota del WCET para cada tarea. 1.1.2. WCET Determinar una cota superior del tiempo de ejecución, es decir su peor caso, es imprescindible en el desarrollo y validación de los sistemas de tiempo real estricto. Dados componentes hardware con latencia fija, el WCET de una tarea podría calcularse mediante el WCET parcial de cada bloque básico. Sin embargo, para mejorar el rendimiento, los procesadores actuales llevan a cabo muchas operaciones cuya duración es variable. Esas operaciones provienen de las caches, la segmentación, los predictores de saltos y otros componentes especulativos [Wil+08]. Aunque las plataformas orientadas al rendimiento se benefician de estos componentes, dificultan el análisis para sistemas de tiempo real estricto. Ya que el WCET depende de las especificaciones técnicas del hardware y cómo interaccionan con la tarea ejecutada, un WCET concreto no es válido para ningún otro hardware que no sea el analizado. Por lo tanto, un buen método para el análisis del WCET no será solo aquel que dé una cota lo más ajustada posible sino también aquel cuyo tiempo de análisis sea menor ya que esto puede reducir mucho el tiempo necesario para diseñar un sistema de tiempo real. La figura 1.1 ilustra el problema del análisis del WCET. La curva inferior representa un subconjunto de ejecuciones medidas. Su mínimo y máximo son el tiempo de ejecución observado mínimo y máximo, respectivamente. La curva más oscura, 1.2. Estado del arte 3 envolviendo la anterior, representa el tiempo de todas las posibles ejecuciones. Su mínimo corresponde al mejor caso de tiempo de ejecución Best Case Execution Time, BCET) y su máximo al WCET. Resulta importante señalar que, generalmente, cuando hablamos de calcular el WCET hacemos referencia a calcular la cota más aproximada posible al WCET real. En general, la jerarquía de memoria es el componente con mayor impacto en el WCET, tanto por su continuo funcionamiento como por su latencia variable [Apa+08]. Además, en las caches convencionales la latencia de acceso depende de los accesos anteriores lo que dificulta extremadamente su predictibilidad. Según la política de reemplazo esta dependencia suele implicar un mayor tiempo de análisis, por ejemplo LRU (Least Recently Used, menos usada recientemente) o una gran sobrestimación del WCET cuando se agrupan posibles eventos de ejecución alternativos, por ejemplo el efecto domino en Pseudo-LRU (PLRU) [Rei+07]. 1.2. Estado del arte A continuación analizamos el estado del arte que ha sustentado la base teórica de este trabajo. 1.2.1. Métodos de análisis del WCET Los métodos de análisis del WCET deben perseguir tanto ajustar su cota lo máximo posible, es decir sobreestimándolo lo mínimo posible, como reducir su tiempo de análisis. Podemos dividir los métodos que encontramos en la bibliografía para calcular el WCET en tres tipos: Métodos estáticos. Estos métodos usan el código de la tarea junto con anotaciones para analizar el flujo de control, combinándolo con algún modelo (abstracto) de la arquitectura hardware, para obtener cotas temporales. El objetivo es obtener una cota superior lo más ajustada posible al WCET real. Los métodos estáticos ofrecen seguridad mediante dichas cotas, garantizando que la ejecución no las excederá. Estos métodos son complejos porque modelar de manera precisa el hardware es difícil. Además hay que tener en cuenta que generar modelos incorrectos puede producir resultados no seguros (calcular una cota del WCET menor que el propio WCET) y modelos mal diseñados pueden producir resultados demasiado pesimistas (una cota del WCET muy superior al WCET real). Métodos basados en medidas. Estos métodos ejecutan la tarea o partes de ella en el hardware final o en un simulador para un conjunto amplio de entradas. A partir de los tiempos medidos, derivan el tiempo máximo de ejecución observado o su distribución, o combinan los tiempos medidos en distintos fragmentos de código para inferir el WCET de la tarea completa. Estos métodos no son seguros, ya que no puede garantizarse que el peor caso haya sido observado. No obstante, se consideran menos complejos y menos propensos a errores. Métodos probabilísticos. Estos métodos usan teoría de probabilidades para conseguir una distribución probabilística del WCET estimado [Caz+13]. Aunque no pueden garantizar la seguridad, pueden estimar el WCET para una probabilidad de inseguridad dada. Por ejemplo, estimar el WCET con una probabilidad de inseguridad menor que la probabilidad de fallo de hardware. La principal 4Capítulo 1. Introducción, estado del arte y objetivos FIGURA 1.2: Distribución del tiempo de ejecución para arquitecturas deterministas convencionales y una propuesta de arquitectura aleatorizada en el tiempo, superpuestas con la distribución probabilística de peor caso en sistemas de tiempo real analizables probabilísticamente (Probabilistically Analyzable Real-Time Systems, PROARTIS), mostrando la sobrecarga de la aleatorización (a), la posible localización del WCET exacto (b), y las cotas del WCET consideradas (c). Figura tomada de [Caz+13]. desventaja de estos métodos es que la teoría probabilística solo puede aplicarse en hardware/software no determinista, i.e. con comportamiento aleatorio. Obviamente, tanto el hardware como el software son deterministas, así que estos métodos requieren hardware aleatorio (investigado actualmente de manera activa) y el código a analizar tiene que ser aleatorizado con respecto al tiempo. Incluso asumiendo cotas precisas del WCET, requerir aleatoriedad en el sistema puede incrementar artificialmente estas cotas, dando como resultado sistemas ineficientes. Encontramos un ejemplo en la figura 1.2 que ilustra la diferencia entre el tiempo de ejecución en una arquitectura determinista y una aleatorizada. En este trabajo nos centramos en los métodos estáticos ya que son los únicos que nos permiten calcular un cota segura del WCET. En la figura 1.3 encontramos un esquema de una herramienta de análisis temporal que implementa un método estático. Podemos ver que el análisis del WCET incluye normalmente tres pasos: análisis del flujo que consiste básicamente en identificar los caminos (im)posibles y acotar los bucles; el análisis de bajo nivel que pretende determinar los efectos globales de la arquitectura en los tiempos de ejecución y calcular el peor caso de tiempo de ejecución de los fragmentos de código; finalmente, el resultado de los dos análisis anteriores se combina para calcular el WCET en conjunto. Podemos usar un método estático diferente para cada una de estas fases, e incluso para sistemas muy simples podría no desarrollarse alguna de estas fases explícitamente. Otra forma de visualizarlo es que lo primero que necesitamos es extraer la información del flujo de control, para generar un modelo matemático que finalmente podamos resolver obteniendo el WCET. Veamos algunos ejemplos de métodos que se usan para la extracción de la información: Abstract Interpretation (AbsInt): AbsInt es un conocido modelo matemático que aplicado a los métodos de análisis estáticos consiste en partir de un estado abstracto y analizar cómo va evolucionando a lo largo de distintos puntos 1.2. Estado del arte 5 FIGURA 1.3: Los principales componentes de una herramienta de análisis temporal que implementa el método estático. El flujo de información se muestra a través de las flechas grises. Las flechas blancas representan las entradas que construyen la herramienta. Imagen tomada de [Wil+08]. del programa. Una de las finalidades de los métodos que aplican AbsInt es analizar los accesos a la cache de datos [The+03]. En estos casos los estados abstractos representarán el estado de la cache de datos en cada punto del programa. También puede aplicarse para determinar el estado de la cache de instrucciones [FW99]. Adicionalmente existen métodos basados en AbsInt que se aplican al análisis del flujo de control [Gus00]. En este caso los estados abstractos serán los propios caminos en cada punto del código analizado. Finalmente, AbsInt puede aplicarse al análisis de flujo de datos calculando invariantes del estado de ejecución del procesador en cada punto del programa [CC77]. Concordancia de patrones: Estos métodos se aplican al análisis de patrones de los bucles y se basan en que la mayoría de estos usan las mismas instrucciones, o similares, para la inicialización, actualización o comprobación de los contadores de bucle [Gus+03]. Una vez obtenemos esta información, el modelo matemático que se genera y que permitirá calcular el WCET en conjunto puede construirse a partir de los siguientes métodos: Basados en la estructura: Acotan el tiempo de ejecución a partir de un recorrido de abajo hacia arriba del árbol de la tarea. Este árbol se construye a partir del grafo de control del flujo (Control Graph Flow, CFG). En este procedimiento, conjuntos de nodos se fusionan en un único nodo, del que se calcula su cota temporal a partir de los nodos que lo componen hasta reducir todo el árbol en un único nodo con el WCET final [CP00;CB02;Lim+95]. Sin embargo, no todos los flujos de control pueden expresarse como estructuras en árbol. Otro de sus principales inconvenientes surge cuando usamos sistemas con caches convencionales ya que no tolera su propio comportamiento dependiente del contexto. No obstante, esta propuesta es probablemente la más rápida [Wil+08], por lo que, para ciertos objetivos, los métodos basados en la estructura con mejoras son los más adecuados. Basados en el recorrido: El tiempo de ejecución para una tarea se determina calculando las cotas de cada camino, buscando cuál es el de mayor tiempo de ejecución entre todos ellos [SA00;SEE01;Hea+99]. Esto implica que los posibles 6Capítulo 1. Introducción, estado del arte y objetivos caminos de ejecución deben ser representados explícitamente, con el correspondiente coste en la explosión combinatoria de éstos al aumentar su número exponencialmente con respecto al número de puntos de bifurcación. Técnica de enumeración implícita de caminos (Implicit Path Enumeration Technique, IPET): el flujo del programa y las cotas de tiempo de ejecución de los bloques básicos se combinan en un conjunto de restricciones [LM95], bien a través de técnicas de programación lineal entera (Integer Linear Programming, ILP) o programación de restricciones. El número de restricciones tiene una complejidad exponencial al tamaño de la tarea y aumenta con las restricciones que provienen de los datos de flujo. Un método estático que podría sustituir todo lo anterior sería la Simulación Simbólica donde la ejecución de la tarea es simulada en un modelo abstracto del procesador. Esta simulación se lleva a cabo sin ninguna entrada lo que conlleva que el simulador debe ser capaz de manejar estados parcialmente desconocidos. Por lo tanto, este método combina el análisis del flujo, la predicción del comportamiento del procesador y el calculo de la cota del WCET en una sola fase integrada [Lun02]. 1.2.2. Arquitecturas hardware Las arquitecturas hardware son un tema abierto en los sistemas de tiempo real. Se ha invertido mucho esfuerzo para poder usar de forma segura el hardware tradicional de propósito general. Por ejemplo, ARM ofrece una serie Cortex para sistemas de tiempo real (R-series) [Limb], incluida en la arquitectura Xilinx UltraScale MPSoC [Xil]. También la serie LEON (originalmente diseñada por la Agencia Espacial Europea basada en el SPARC V8) da soporte a muchos sistemas operativos de tiempo real. Sin embargo, su falta de especificaciones estrictas de latencia sugiere que deberían desarrollarse nuevos diseños más predecibles. En concreto, la jerarquía de memoria es, como ya hemos indicado, uno de los puntos críticos en los sistemas de tiempo real debido a su latencia variable. Esto es lo que sucede con las caches convencionales con políticas de reemplazo que dependen de los accesos anteriores y los parámetros de cache (asociatividad, tamaño, etc.). Estas caches proporcionan un gran rendimiento en los sistemas convencionales pero resultan contraproducentes ya que la dificultad para acotar la latencia de cada acceso implica un gran tiempo de análisis y, en general, una gran sobrestimación. Por esta razón, muchas veces se prescinde de ellas asumiendo que todos los accesos se dan a memoria principal. En el caso de las caches de instrucciones una de las propuestas más extendidas para abordar esta problemática es el uso de caches bloqueables que simplifican y consiguen un análisis más preciso [Apa+10;Apa+11;Pua06;PD02;CIM01]. Podemos encontrar propuestas de diseños especializadas como las caches con política de reemplazo aleatoria que permiten aplicar métodos de análisis de sistemas de tiempo real probabilísticos [Kos+14]. También encontramos propuestas de diseño específicas para tiempo real de caches de datos, que conllevan un análisis mucho más complejo que las de instrucciones. Algunos ejemplos de estos diseños son la Address-Cache Data-Cache [Seg+15] y la Fully-associative FIFO tagged Buffer [Gra+15]. Estas caches proporcionan una alta predictibilidad sin comprometer la eficiencia evitando la polución, i.e. no permitiendo los reemplazos no deseados. 1.3. Objetivos y Logros 7 1.2.3. Consumo energético Como el análisis temporal de los sistemas de tiempo real es tan crítico, no se suelen considerar otros parámetros como el consumo de energía. Sin embargo, la optimización del peor caso de consumo de energía (worst-case energy consumption, WCEC) puede ser un factor clave en aquellos sistemas que tengan limitaciones importantes en el suministro de energía. Por ejemplo, aquellos sistemas alimentados con baterías o cualquier otra fuente de alimentación que pueda agotarse y para la cual es crítico conseguir un consumo de energía lo más bajo posible. Estos sistemas cada vez adquieren más importancia ya que se extienden desde redes de sensores, sistemas de vigilancia y subsistemas satélites hasta los robots de búsqueda y rescate. Existen trabajos previos relativos al consumo de energía en sistemas de tiempo real que hacen uso del ajuste dinámico de la tensión para conseguir una planificación de tareas que sea eficiente energéticamente [CK07]. Estas investigaciones son básicamente teóricas y estudian cómo gestionar la velocidad del procesador (y por tanto su consumo estimado de energía) cuando hay suficiente margen hasta el deadline, por ejemplo, en base al WCET de las tareas. Sin embargo, no suelen incluir en estos análisis de planificación el WCEC del sistema, ya que generalmente se desconoce este valor. El trabajo que aborda inicialmente el problema de la combinación del WCET con el WCEC [JML06], además de describirlo, muestra que el WCEC no pude calcularse como la energía media por el WCET. Esto se debe a que el camino correspondiente al WCET no tiene porque coincidir con el que tenga un mayor consumo de energía. Así que en este trabajo se propone una técnica que proporciona una estimación del WCEC para un procesador que ejecute una sola tarea. Esta técnica emplea ILP de manera similar a las técnicas de análisis del WCET. Es decir, modelando el consumo de energía de los bloques básicos a través de restricciones lineales y obteniendo el peor caso encontrando el máximo consumo de energía. En un trabajo posterior [Gra+13] se mejora esta propuesta proponiendo una organización de memoria de instrucciones que incluye una cache bloqueable, mucho más apropiada para sistemas de tiempo real por su predictibilidad. Por otro lado también amplian el análisis de un sistema de una sola tarea a uno con varias ejecusandose en un planificador de tiempo real preventivo que permite tener en cuenta las interferencias de los cambios de contexto. En esta propuesta no solo calculan el WCEC sino que lo optimizan en relación al conjunto de instrucciones a bloquear en la cache. Por lo tanto, en el contexto de los sistemas de tiempo real es importante no poner el foco únicamente en el WCET ya que se podrían descartar opciones que tengan algunos ciclos más incluso si consumen mucha menos energía. 1.3. Objetivos y Logros El objetivo general de esta tesis es mejorar la eficiencia de la jerarquía de memoria en sistemas de tiempo real. Esto implica esencialmente mejorar su predictibilidad, aunque también se consideran otros aspectos como el el consumo energético. Los objetivos específicos son: Mejorar tanto el peor caso de tiempo de ejecución (WCET) como su análisis en sistemas de tiempo real que cuenten con jerarquía de memoria. Estudiar patrones de acceso a memoria en tareas para sistemas de tiempo real y sistemas empotrados. 8Capítulo 1. Introducción, estado del arte y objetivos Consideramos que los objetivos se han alcanzado a través de la consecución de los siguientes logros: Hemos diseñado un algoritmo que transforma el CFG del binario a analizar en una estructura en árbol, necesaria para usar Lock-MS como método de análisis del WCET. Este algoritmo permite reducir el tiempo de análisis del WCET sin sacrificar precisión para una cache de instrucciones bloqueable. Hemos proporcionado una heurística de bloqueo dinámico basada en los bucles que permite obtener el contenido óptimo de cache para el WCET de cada región. Esta heurística a la vez que posee una baja complejidad, reduce el WCET explotando de manera efectiva el reuso temporal, y reduce también su tiempo de análisis. Hemos identificado que el WCET se reduce de manera efectiva cuando los bucles vectorizados forman parte del código dónde se lleva a cabo la mayor parte de la ejecución, y por lo tanto, vale la pena trabajar por conseguir una buena vectorización, ya sea a través de la programación o del compilador, en los sistemas de tiempo real. Hemos acotado que la tasa ideal de aciertos para la transposición de matrices en su versión tiling se logra con muy pocos conjuntos y no más de dos vías en una cache asociativa por conjuntos cuando se aplica una configuración de tile apropiada (la dimensión del tile igual al tamaño de línea de cache). 1.3.1. Estructura tesis En este capítulo (capítulo 1) presentamos el problema del análisis y cálculo del WCET y revisamos los trabajos de investigación más relevantes relacionados con este problema. Además describimos los objetivos y logros alcanzados en el desarrollo de este trabajo. En el capítulo 2exponemos los métodos y herramientas que nos han permitido llevar a cabo este trabajo. También caracterizamos los programas de prueba que utilizaremos para obtener los resultados. En el capítulo 3presentamos un algoritmo que permite reducir el tiempo de análisis del WCET en sistemas con una cache de instrucciones simple y bloqueable, centrándonos en el método Lock-MS. Presentamos también cómo ampliar este algoritmo para poder determinar varios puntos de bloqueo en cada tarea, cada uno con un contenido específico de cache, en vez de bloquear un solo contenido para la ejecución de toda la tarea. Además de reducir el tiempo de análisis, los resultados que obtenemos del trabajo de este capítulo muestran que también se ha reducido el WCET y que la tasa de aciertos que se alcanza para la cache de instrucciones bloqueada es similar a una ejecución real con una cache de instrucciones LRU. Finalmente, analizamos la susceptibilidad a las optimizaciones del compilador, mostrando cual es la elección correcta para cada programa de prueba y señalando que O0 es siempre la peor opción. En el capítulo 4se estudia el impacto de la vectorización automática de instrucciones en el análisis del WCET. Una vez aplicada la vectorización por parte del compilador se analizan las partes vectorizadas para acotar su contribución al WCET de la tarea con el objetivo de integrar estas cotas en el análisis del WCET de la tarea correspondiente. Para finalizar presentamos los resultados que muestran que el WCET se reduce de manera efectiva pero que la eficiencia de la vectorización automática es bastante limitada. 1.3. Objetivos y Logros 9 En el capítulo 5analizamos un algoritmo fundamental en los sistemas de tiempo real, la transposición de matrices, en relación con su tasa de aciertos en cache de datos, cuyo efecto es de gran relevancia en el cálculo del WCET. En este análisis obtenemos la relación entre los parámetros de cache que garantizan la tasa (predecible) ideal de aciertos en datos tomando una cache de datos LRU. Tras ello comparamos los algoritmos de transposición de matrices tiling ycache-oblivious, demostrando que, con el tamaño adecuado de tile, la versión tiling del algoritmo obtiene una tasa de aciertos en datos mejor o igual. También analizamos el consumo de energía y el tiempo en ejecución de la transposición en hardware real con caches PLRU. En el capítulo 6se resumen las conclusiones de esta tesis. 11 Capítulo 2 Metodología y caracterización de benchmarks En este capítulo exponemos los métodos y herramientas que nos han permitido llevar a cabo este trabajo. También caracterizamos los programas de prueba que utilizaremos para obtener los resultados. 2.1. Métodos y herramientas existentes para el cálculo del WCET 2.1.1. Herramientas de análisis de CFG Una de las primeras tareas al inicio de esta tesis fue estudiar las distintas herramientas disponibles con las que llevar a cabo el análisis del WCET de los capítulos 3y4. La primera de ellas, Chronos [Li+07], fue descartada debido a que para poder ampliar y adaptar el analizador había que trabajar con SimpleScalar [ALE02] que, si bien ha sido uno de los simuladores más ampliamente usados en la comunidad investigadora, se encuentra actualmente obsoleto sin mantenimiento desde 2011 [Sim]. Otra herramienta interesante es Heptane [HRP17]. En el momento que se desarrolló este estudio (2015) estaba disponible la segunda versión pero llevaba 5 años sin mantenimiento y pese a ser código abierto no facilitaba la integración de nuevos análisis, algo imprescindible para el desarrollo de nuestro trabajo. Sin embargo, publicaron una tercera versión en 2017 en la que habían cambiado totalmente su estrategia de desarrollo y habían redefinido la arquitectura software de Heptane para facilitar tanto la legibilidad del código como el desarrollo de nuevos análisis. Considerando esta última versión, si esta decisión se tuviera que tomar en la actualidad Heptane se presentaría como una buena elección. SWEET [Lis14] se centra en el análisis del flujo de control pero no incluye ningún análisis a nivel de hardware, de hecho se plantea como una herramienta complementaria a otras que realicen un análisis a más bajo nivel. Además esta herramienta no contempla que se añadan nuevos análisis a los ya implementados. Actualmente no se encuentra disponible. Bound-T [Tid] se encuentra totalmente desfasada y podemos encontrar una extensa y honesta declaración en su web sobre los problemas de fiabilidad que presenta debido a sus sucesivas ampliaciones. Una de las herramientas actuales más avanzada para el análisis del WCET es aiT [FH04] pero desgraciadamente no es código abierto sino que es una herramienta 18 Capítulo 2. Metodología y caracterización de benchmarks un camino determinado. Por lo tanto, todos los Bipath se pueden sustituir por Bi y los bloques comunes se pueden analizar por separado. Si una línea de memoria está bloqueada y cacheada, su coste de búsqueda será siempre el de un acierto en cache. Sin embargo el coste debe ser fallo en el line-buffer para la primera referencia de cada línea accedida. Los costes de búsqueda de líneas de memoria que no están en cache y son compartidas por varios bloques básicos son estudiados en profundidad en este método. En resumen, esto permite reescribir la ecuación 2.2 como: WCET =min(B0+B3+B6+max(B1+B4, B1+B5, B2+B4, B2+B5)) (2.3) De la ecuación 2.3 podemos obtener expresiones equivalentes a la función de maximización de la siguiente manera. Si B1>B2, entonces B1+B4>B2+B4, por lo tanto es obvio que B2+B4 puede descartarse ya que no formará parte del peor caso. De lo contrario, B1+B4≤B2+B4 y B2+B4 debe permanecer en la expresión. Así maximizando primero el par B1, B2 y después B4, B5 tenemos: max(B1+B4, B1+B5, B2+B4, B2+B5) = max(B1, B2) + max(B4, B5)(2.4) Por lo tanto, podemos reescribir la ecuación 2.3 como: WCET =min(CosteComun +max(B1, B2) + max(B4, B5)) (2.5) Esta información podría traducirse a un árbol en el que el coste de cada nodo fuera la suma del coste común más el máximo coste de entre sus nodos hijos. Es decir, cada una de las ramas sería un camino alternativo. Como se puede ver la diferencia entre las expresiones de las ecuaciones 2.1 y2.5 es que la primera, expresada por caminos, requiere de muchas más restricciones que la segunda, con estructura de árbol. Sin embargo, este método no proporciona el algoritmo para construir la estructura en árbol necesaria para establecer las restricciones del modelo ILP. 2.2. Caracterización de benchmarks En esta sección presentamos aquellos programas de prueba que utilizamos durante nuestra investigación. 2.2.1. Suites de benchmarks para sistemas de tiempo real Una de las principales cuestiones de la mayoría de los trabajos de investigación de nuestra área es qué programas de prueba (benchmarks) van a utilizarse para medir los resultados de la propuesta de dicho trabajo. Esto es especialmente útil en el área de los sistemas de tiempo real dónde es crucial evaluar y comparar técnicas de análisis del WCET, de los compiladores y de arquitectura de computadores. Por ello, es muy útil tener un conjunto de benchmarks (llamados suites de benchmarks) que se encuentren disponibles con facilidad, que hayan sido probados, que estén bien documentados, que sean fieles a los programas que se están usando en sistemas de tiempo real en la industria y que tengan un reconocimiento de la comunidad investigadora que permita establecer comparaciones en la evaluación de distintos algoritmos, métodos y herramientas. Todos estos motivos son los que nos han llevado a escoger las dos suites de benchmarks que presentamos a continuación: 2.2. Caracterización de benchmarks 19 for ( i =0; i <n ; i ++) for (k=0;k<n ; k++) { t=B[ i ][ k ] ; for ( j =0; j <n ; j ++) A[ i ] [ j ]=A[ i ][ j ]+ t ∗C[k ][ j ] ; } FIGURA 2.4: Algoritmo del benchmark matmult_opti. Mälardalen [Gus+10] es la primera colección de programas especialmente dirigido para las herramientas de análisis del WCET, con un enfoque en el análisis del flujo del programa. Se creó en 2005 recopilando programas de distintas fuentes y desde entonces se ha usado en muchas investigaciones del WCET. La mayoría de sus benchmarks son relativamente pequeños y de un solo camino, lo cual limita su aportación a la hora de evaluar herramientas que admiten códigos de caminos múltiples. TACLeBench [Fal+16] proporciona un conjunto de benchmarks gratuitos disponibles y relacionados con temas de investigación. Sus códigos son autocontenidos; no existen dependencias de cabeceras específicas del sistema a través de #include o del sistema operativo. Todos los datos de entrada forman parte del código fuente en C. Esto hace que la colección TACLeBench sea útil para sistemas empotrados donde no hay bibliotecas estándar disponibles. Como uno de los objetivos de la creación de TACLeBench es abordar las necesidades que requieren las herramientas de análisis temporal, todos los benchmarks contienen anotaciones sobre información del flujo de datos (por ejemplo, el número máximo de iteraciones de los bucles). La tabla 2.1 muestra los benchmarks que se han utilizado en nuestros experimentos de los capítulos 3y4que se descargaron en febrero de 2017 de los paquetes TACLeBench [Fal+16] y Mälardalen [Gus+10], más el benchmark matmult_opt que ejecuta una multiplicación de matrices optimizada (figura 2.4). Algunos de los benchmarks de estos paquetes se han descartado por las siguientes razones: errores de compilación en compiladores cruzados1, número desconocido de iteraciones de bucles en funciones de bibliotecas al compilar con coma flotante emulada2y problemas con la extracción del CFG3. Estos problemas de extracción incluyen construcciones «switch» implementadas mediante saltos a direcciones desconocidas, CFGs con bucles irreducibles (por ejemplo, bucles con múltiples entradas), funciones recursivas, etc. Estas cuestiones provienen de limitaciones en el procesamiento del código binario, pero no afectan a nuestras propuestas. 2.2.2. Transposición de matrices La trasposición de una matriz es una operación que consiste en colocar sus filas en forma de columna, respetando su orden. En la figura 2.5 podemos encontrar un ejemplo de la transposición de una matriz de 3×3 elementos. Esta operación aparentemente sencilla es fundamental en áreas como el álgebra lineal o las transformadas 1powerwindow, bitcount, gsm_dec, rijndael_dec, dijndael_enc, susan. 2powerwindow, prime, adpcm_dec, adpcm_enc, ammunition, anagram, cjpeg_transupp, cjpeg_wrbmp, epic, huff_enc, rijndael_dec, rijndael_enc. 3sha, gsm_enc, h264_dec, cover, duff, mpeg2, lms, test3, quicksort, recursion. 20 Capítulo 2. Metodología y caracterización de benchmarks TABLA 2.1: Benchmarks usados en nuestros experimentos (TACLeBench [Fal+16] y Mälardalen [Gus+10]). Nombre Suite audiobeam TACLeBench basicmath TACLeBench binarysearch TACLeBench bsort Mälardalen bs Mälardalen cnt Mälardalen complex_updates TACLeBench countnegative TACLeBench crc Mälardalen dijkstra TACLeBench fdct Mälardalen fft TACLeBench filterbank TACLeBench fir2dim TACLeBench fmref TACLeBench g723_enc TACLeBench iir TACLeBench janne_complex Mälardalen jfdctint TACLeBench lift TACLeBench ludcmp Mälardalen matmult Mälardalen matmult_opti Propio matrix1 TACLeBench md5 TACLeBench minver TACLeBench nsichneu Mälardalen ndes Mälardalen petrinet TACLeBench pm TACLeBench qsort-exam Mälardalen qurt Mälardalen select Mälardalen st TACLeBench statemate Mälardalen de Fourier, entre otras. Además tiene muchas aplicaciones en otras como el análisis numérico, el procesado de imágenes y gráficos. Hay muchos ejemplos de aplicaciones desarrolladas en los centros de supercomputación que usan, de un modo u otro, la transposición de matrices como parte esencial para solucionar sus problemas. Por ejemplo, el Oak Ridge National Laboratory (EEUU) desarrolla, mantiene, prueba y gestiona SCALE Code System [RJ16] que es un conjunto de benchmarks de modelado y simulación ampliamente usado para el diseño y análisis de seguridad nuclear. Otro ejemplo que encontramos es Geotess [Bal+16] desarrollado por Sandia National Laboratory. Este sistema de soporte software y parametrización de modelos implementa la construcción, almacenamiento y consulta de los datos pertenecientes a modelos 3D de la Tierra. En el área de tiempo real encontramos que el patrón de accesos del algoritmo es determinista y de fácil comprensión, por lo tanto su estudio puede servir de base para analizar otros algoritmos con patrones de acceso más complicados. Sin embargo, su análisis en el entorno de tiempo real no es trivial ya que aparecen muchos 2.2. Caracterización de benchmarks 21 FIGURA 2.5: Ejemplo de transposición de una matriz de 3×3 elementos. parámetros a tener en cuenta: el tamaño de la matriz y todos los relacionados con la estructura de la memoria cache (tamaño, asociatividad, número de conjuntos, tamaño de bloque...). Además, esta operación tiene varias propuestas de implementación que varían el orden de acceso de los elementos de la matriz alterando la eficacia del uso de la cache de datos y, por tanto, la eficacia del sistema. 23 Capítulo 3 Reducción del WCET y del tiempo de análisis en sistemas con caches bloqueables de instrucciones En este capítulo tratamos uno de los retos clave en los sistemas de tiempo real que es el análisis de la jerarquía de memoria. Muchos métodos de análisis del WCET que admiten una cache de instrucciones se basan en algoritmos iterativos o convergentes los cuales son bastante lentos. Nuestro objetivo en este capítulo es reducir el tiempo de análisis del WCET en sistemas con una cache de instrucciones bloqueable, centrándonos en el método Lock-MS. Primero, proponemos un algoritmo para obtener una representación basada en la estructura del grafo de control de flujo. Este algoritmo organiza el problema del WCET como un conjunto de subproblemas anidados, el cual aprovecha los algoritmos habituales de ramificación y poda de los solvers de ILP. Después, añadimos al algoritmo la posibilidad de determinar varios puntos de bloqueo en cada tarea, cada uno con un contenido específico de cache, en vez de bloquear un solo contenido para la ejecución de toda la tarea. Los puntos de bloqueo se establecen heurísticamente antes de los bucles exteriores. Esta heurística es tan simple que no añade complejidad y reduce el WCET aprovechando el reuso temporal que encontramos en los bucles. Debido a que los bucles pueden procesarse como regiones aisladas, para cada región se puede obtener el contenido óptimo a bloquear en la cache y el tiempo de análisis del WCET se verá notablemente reducido. Con estas dos mejoras nuestro análisis del WCET resulta un orden de magnitud más rápido que otras propuestas. Además, nuestros resultados muestran que la tasa de aciertos que se alcanza para la cache de instrucciones bloqueada es similar a una ejecución real con una cache de instrucciones LRU. Finalmente, analizamos la susceptibilidad a las optimizaciones del compilador, mostrando cual es la elección correcta para cada programa de prueba y señalando que O0 es siempre la peor opción. 3.1. Introducción Uno de los principales retos en el análisis del WCET es la jerarquía de memoria [Apa+08]. El comportamiento convencional de la cache depende de las referencias pasadas y, para que el análisis sea preciso, será necesario conocer todos los accesos de memoria previos para determinar la latencia de un determinado acceso a memoria. Si nos centramos en el reemplazo LRU, los métodos estáticos actuales de análisis del WCET se basan en AbsInt [CC77;FW99], IPET [LMW96], o el uso de ambos [Tra]. Dado el considerable tiempo de análisis que estos métodos precisan para 24 Capítulo 3. Reducción del WCET y del tiempo de análisis analizar el WCET en sistemas con una cache de instrucciones, no está claro si pueden analizar programas complejos en sistemas que incluyan otros componentes de hardware como la cache de datos, la prebúsqueda, etc. Por ejemplo, aunque teóricamente tanto AbsInt como IPET permiten caches de datos [LMW96], ningún estudio las ha evaluado a conciencia hasta donde sabemos. Para reducir el tiempo de análisis muchos estudios han propuesto usar caches completamente bloqueables [Mit16]. Estas caches se pueden encontrar en procesadores de la mayoría de fabricantes como Motorola (ColdFire, PowerPC, MPC7451, MPC7400), MIPS32, ARM (904, 946E-S), Integrated Device Technology (79R4650, 79RC64574), Intel 960, etc. En caso de fallo estas caches piden la línea que ha resultado en fallo al siguiente nivel de memoria pero cuando llega se envía a un line-buffer (memoria intermedia con capacidad de almacenar una línea de cache) sin guardar ninguna copia en la cache. Por lo tanto, no será necesario realizar ningún reemplazo y todo el almacenamiento y control dedicado a su implementación en las caches convencionales se suprime al carecer de utilidad. Debido a que el contenido de la cache bloqueable es conocido y no cambia, el cálculo de aciertos y fallos es mucho más fácil y no depende de los accesos anteriores a memoria, de este modo se simplifica el análisis del WCET. Sin embargo, el reto que presentan estas caches es determinar qué conjunto de instrucciones será el mejor para bloquear en la cache, además de llevar a cabo su análisis del WCET. Por lo tanto, los métodos de caches bloqueables tratan de encontrar qué contenidos deben ser bloqueados en la cache para generar el mínimo WCET posible. Dependerá de su flexibilidad en cuanto a los puntos de carga y bloqueo, de los distintos conjuntos de contenidos a gestionar, y también de cómo se aborde el análisis (heurísticamente, analíticamente, etc.). Hay muchos métodos para abordar este problema. Los métodos de «bloqueo estático» seleccionan un solo conjunto de instrucciones para bloquear durante todas las tareas que se ejecutan en el sistema, por lo tanto esta selección se fija cuando el sistema se inicia [PD02]. Por otro lado, los métodos de «bloqueo dinámico» seleccionan uno o más conjuntos de instrucciones para cada tarea. En general, el bloqueo dinámico funciona mejor que el estático en cuanto al WCET [Cam+03]. Centrándonos en el bloqueo dinámico, nos referiremos como bloqueo dinámico de un solo contenido a aquellos métodos que seleccionan un solo contenido por tarea, el cual se carga y bloquea en el cambio de contexto de la tarea correspondiente (por ejemplo [Apa+11]), y bloqueo dinámico de contenido múltiple a aquellos métodos que permiten a cada tarea cargar y bloquear contenidos durante su ejecución en múltiples ocasiones(por ejemplo [Pua06]). Dos propiedades muy interesantes del bloqueo dinámico de un solo contenido son que, primero, se puede llevar a cabo el análisis del WCET con métodos basados en la estructura (cuya solución es mucho más rápida) sin perder precisión, y segundo, que estos métodos también proporcionan la selección óptima de contenidos a bloquear [Apa+11]. Esto permite extender el análisis del WCET de manera que incluya la prebúsqueda [Apa+10], cache de datos [Seg+12;Seg+15], e incluso poder analizar al mismo tiempo el consumo de energía para obtener una solución equilibrada que tenga en cuenta tanto el WCET como el WCEC [Gra+13]. Por otro lado, los métodos dinámicos de contenido múltiple mejoran el WCET pero se añade la dificultad de decidir cuáles serán los mejores lugares del código en los que fijar la carga y bloqueo de instrucciones, y cuales serán estas instrucciones en cada punto de carga. Normalmente estos dos problemas se abordan heurísticamente para intentar limitar el tiempo de análisis, así que sus resultados no son óptimos. Además el tiempo de análisis que necesitan sigue siendo comparable al necesario para realizar el análisis del WCET en una cache LRU [AP;Pua06]. Otros estudios usan algoritmos 3.1. Introducción 25 genéticos para intentar resolver estos problemas [CIM01]. Por último, algunos estudios suponen caches parcialmente bloqueables a nivel de conjunto. En cada conjunto de estas caches puede haber un número variable de líneas no bloqueadas ordenadas en LRU y el resto de líneas del conjunto estarán bloqueadas [DLM13;ZWY17]. La complejidad del control y almacenamiento para implementar este método sobrepasa las capacidades de las caches convencionales y, por supuesto, de las caches completamente bloqueables. Hasta donde sabemos, este hardware todavía no está disponible y los diseños actuales de cache están bastante alejados de alcanzar este comportamiento. Además se necesita mucho tiempo de análisis para el gran número de configuraciones que admite una cache parcialmente bloqueable a nivel de conjunto. Por ejemplo, se ha propuesto un proceso convergente que consiste en dos fases [ZWY17]. En la primera se realiza el análisis del WCET asumiendo una cache de instrucciones que puede tener algunas líneas bloqueadas. En la segunda fase se prueba si hay una nueva línea adecuada para bloquear, configurando la cache de instrucciones de acuerdo con la próxima iteración del algoritmo de convergencia. Sin embargo, ninguno de estos estudios proporciona unos puntos de referencia que sean independientes del sistema (por ejemplo, situación de siempre acierto o de siempre fallo) lo cual dificulta interpretar sus resultados. Además no se comparan con las caches convencionales y cuando se comparan con caches completamente bloqueables usan un hardware sesgado ya que no consideran el line-buffer que es necesario para que las caches bloqueables funcionen correctamente [Apa+10; Apa+11;AP;Pua06;PD02;Seg+12;Seg+15]. Sin embargo, en este capítulo nos centramos en estructuras de cache simples y métodos de análisis del WCET rápidos, así que las soluciones a través de caches bloqueables parcialmente a nivel de conjunto se encuentran fuera de nuestro ámbito. Como hemos afirmado anteriormente, es tan importante mejorar la velocidad del análisis que muchas veces los métodos heurísticos son preferibles a los métodos analíticos. Sin embargo, los métodos de análisis orientados a caches bloqueables no han explorado todavía a conciencia el potencial de estos sistemas para obtener un análisis rápido. Nuestro objetivo en este capítulo es reducir el tiempo de análisis del WCET de tareas en presencia de caches de instrucciones bloqueables. Esto se logrará desarrollando DLock-MS, un método de bloqueo dinámico de contenido múltiple. Básicamente consiste en añadir dos mejoras claves a Lock-MS [Apa+11], un método de bloqueo dinámico de un solo contenido. Este método ha sido detallado más profundamente en las sección 2.1.2 La primera de estas mejoras es un algoritmo que traduce el CFG a una estructura en árbol que representa el problema de análisis del WCET, la cual permite usar LockMS como un método basado en la estructura. Este tipo de métodos son en general los más rápidos, ya que no usan algoritmos de convergencia ni superponen problemas de flujo. Este algoritmo organiza el problema del WCET como un conjunto de subproblemas anidados, el cual aprovecha los algoritmos habituales de ramificación y poda de los solvers (softwares de resolución de modelos ILP). La programación lineal en enteros da respuesta a situaciones en las que se exige maximizar o minimizar funciones que se encuentran sujetas a determinadas restricciones, y cuyas variables de decisión deben ser enteras. Los solvers una vez definidas las funciones y restricciones resuelven esta maximización o minimización de las funciones aplicando las restricciones correspondientes. Al haber hecho una división en subproblemas cada uno se optimiza para conseguir una resolución lo suficientemente rápida. En términos de eficiencia, nuestro algoritmo genera una estructura en árbol en una única pasada y explora cada rama solo una vez. Nuestra segunda mejora trata la limitación de tamaño que presentan los métodos 26 Capítulo 3. Reducción del WCET y del tiempo de análisis Algoritmo 1 Explorar(nodoCFGactual,caminoActual) 1: if |hijos(nodoCFGactual)|=0then # no hay más nodos en el camino 2: return caminoActual +nodoCFGactual 3: else if |hijos(nodoCFGactual)|=1then # hijo único: expandir camino 4: return Explorar(hijo(nodoCFGactual), caminoActual +nodoCFGactual) 5: else if |hijos(nodoCFGactual)|>1and explorado[nodoCFGactual]then 6: return caminoActual +nodoCFGactual # condicional ya explorado 7: else # condicional no explorado (|hijos(nodoCFGactual)|>1) 8: for all nodoHijo ∈hijos(nodoCFGactual)do # procesar cada camino alternativo 9: caminoAlternativo ←Explorar(nodoHijo,nodoCFGactual) 10: procesarYConstruirRestricciones(nodoCFGactual,caminoAlternativo) # establecer restricciones como CBBx ≥caminoAlternativo 11: end for 12: explorado[nodoCFGactual]←true 13: return caminoActual +nodoCFGactual # todos los caminos alternativos han sido procesados 14: end if de bloqueo dinámico con un único contenido, no solo para sobrepasar esa limitación consiguiendo mejores resultados en el WCET sino también teniendo en cuenta el tiempo y eficiencia del análisis. DLock-MS aplica heurísticas basadas en bucles para seleccionar el emplazamiento de los puntos múltiples de carga y bloqueo para la cache de instrucciones. Después permite al solver encontrar los contenidos óptimos para cargar y bloquear en cada punto. Además las regiones dónde permanecen fijos cada uno los contenidos bloqueados se pueden procesar como subproblemas aislados, lo cual acelera aún más el análisis del WCET y su resolución. Esto nos daría la posibilidad también de calcular cada una de las regiones en paralelo (no lo abordamos en este trabajo). El resto del capítulo lo organizamos de la siguiente manera. Nuestras dos propuestas se describen en las secciones 3.2 y3.3. En la sección 3.4 evaluamos las propuestas y, finalmente presentamos nuestras conclusiones en la sección 3.5. 3.2. Transformación de CFG a árbol En esta sección presentamos la primera contribución de este capítulo, un algoritmo que traduce el CFG a una estructura en árbol que representa el problema de análisis del WCET, la cual permite usar Lock-MS como un método basado en la estructura. Comienza sustituyendo los bucles y las funciones que no sean el programa principal por nodos virtuales (bloques básicos) en el CFG. Después, se procesan como sub-CFGs independientes para transformarlos en árboles. El Algoritmo 1se aplica recursivamente tanto en el CFG principal como en cada uno de los sub-CFGs independientes, comenzando desde el nodo de entrada del CFG correspondiente y un camino vacío (Explorar(entrada,∅)). Este algoritmo lleva a cabo una búsqueda recursiva en profundidad que construye los árboles asociados a cada CFG y genera sus correspondientes restricciones ILP conforme al modelo Lock-MS. Básicamente, cada árbol se compone de un nodo condicional más todos sus caminos alternativos hasta que se alcanzan otro nodo condicional. El Algoritmo 1funciona de la siguiente manera: Las líneas 1 y 2 tratan los nodos finales del CFG, devolviendo el camino en curso más el nodo actual (y final), por lo tanto completan la exploración de ese camino. En las líneas 3 y 4, que corresponden a un nodo con un solo hijo, continúa la exploración siguiendo el camino de este hijo único. Las líneas 5 y 6 corresponden a la exploración de un nodo condicional, es decir que tiene más de un hijo, que 3.2. Transformación de CFG a árbol 27 ya ha sido explorado. En consecuencia, ya se ha llevado a cabo su procesamiento y la generación de sus restricciones correspondientes siendo innecesario continuar su exploración. Finalmente, en las líneas 7 a 13 se describe como proseguir cuando el nodo actual es condicional y todavía no se ha explorado. En este caso, se genera un árbol nuevo, con el nodo actual como su raíz. Cada uno de sus hijos se explorará para construir las ramas (caminos alternativos) de esta raíz (líneas 8 y 9). A continuación en la línea 10, se procesa cada una de las ramas y se establecen sus restricciones ILP correspondientes (tal como explicamos más adelante). Finalmente, el nodo actual se marca como explorado, devolviendo el camino hasta este nodo (líneas 12 y 13). Hay que tener en cuenta que el nodo de entrada de un bucle no se considera hijo de ningún nodo que sea interno del propio bucle, ya que los arcos que los puedan relacionar son aquellos responsables de la repetición del bucle. Básicamente, la restricciones ILP (línea 10, Algoritmo 1) modelan un problema de minimización para un árbol de nodos (bloques básicos, BB). El coste de cada nodo en particular BBicorresponde al coste total acumulado de ejecutar ese nodo, lo que resulta en una expresión dependiente de sus diferentes casos de ejecución y su número de instancias. Para cada línea de memoria que puede estar en cache jen un bloque básico, se asocia una variable enCacheBBijque determina si está o no en cache para reducir el WCET. Esta líneas de memoria en cache no pueden aumentar más allá de la capacidad misma de la cache, así que también están restringidas según el número de conjuntos y vías. Por ejemplo, asumiendo una cache bloqueable y un bloque básico BB1 que quepa en una única línea de cache L1, sus costes se establecen como: BB1 =nEjecsBB1 ·CosteBB1 =nEjecsBB1 ·(costeAcierto ·enCacheL1 +costeFallo ·(1−enCacheL1) + ejecInstBB1) , donde costeAcierto ycosteFallo son constantes previamente calculadas en base a los parámetros de hardware, ejecInstBB1 coste de ejecución de las instrucciones del bloque básico, nEjecsBB1 depende del CFG, y enCacheL1 es una variable binaria (0/1). Sin embargo, en este trabajo nos centramos en la estructura de las restricciones generales que modelan el CFG y no en aquellas que modelan el hardware [Apa+10; Apa+11;Gra+13;Seg+12;Seg+15]. Tomamos como ejemplo la figura 3.1 que muestra un CFG con 12 caminos explícitos que hay considerar en el análisis del WCET, los árboles que se obtienen tras su transformación y sus principales restricciones ILP correspondientes. Señalar que con una cache bloqueable el peor tiempo de ejecución de un bucle no puede incluir combinaciones de caminos alternativos en su interior [Apa+11]. Por lo tanto los 12 caminos a considerar ejecutan lo siguientes bloques básicos: 1-2-4-5-10-11-13, 1-2-4-5-10-12-13, 1-3-4-5-10-11-13, 1-3-4-5-10-12-13, 1-2-4-6-7-9-10-11-13, 1-2-4-6-7-910-12-13, 1-2-4-6-8-9-10-11-13, 1-2-4-6-8-9-10-12-13,1-3-4-6-7-9-10-11-13, 1-3-4-6-7-910-12-13, 1-3-4-6-8-9-10-11-13, y 1-3-4-6-8-9-10-12-13. El Árbol A representa el último de los condicionales, en BB10, cuyo coste será el máximo de sus dos ramas alternativas. El Árbol B representa del bloque BB4 a BB10, este último ya ha sido explorado (Árbol A). El bucle que empieza en BB6 se analiza como un CFG independiente con sus propio árbol (Árbol Bucle) y se representa como un nodo virtual (BucleBB6) en el Árbol B. Por último, el Árbol C representa del bloque BB1 al BB4. Por lo tanto en vez de 12 caminos en el CFG, nuestra propuesta proporciona 4 sub-árboles con 2 sub-caminos cada uno. Se puede establecer el WCET como el coste de todo el árbol, es decir, el coste de su raíz: WCET =CBB1. A su vez, el coste de cada árbol (compuesto por los costes 34 Capítulo 3. Reducción del WCET y del tiempo de análisis Cuando aplicamos DLock-MS tenemos que considerar cierto sobrecoste. Asumimos que el bloqueo dinámico se realiza ejecutando funciones, tal como hacen otros estudios [ZWY17]. Esas funciones cargan y bloquean el conjunto de instrucciones necesarias en la cache para la siguiente región del código. En concreto, consideramos una penalización de 47 ciclos por llamada, una por región. Estos ciclos corresponderían a los costes de ejecución, fallos en cache y penalizaciones de la segmentación en una función que, estimando, sería de 12 instrucciones. Además, por cada línea de cache bloqueada, añadimos el coste de latencia de memoria (10 ciclos). Este escenario es bastante conservador ya que para bloquear instrucciones se podrían usar operaciones de carga especializadas, por ejemplo, cargando un gran número de líneas de memoria continuas usando algún tipo de modo de transferencia de memoria en ráfagas, lo que podría reducir de manera notable el tiempo total de transferencia [ZWY17]. El modelo ILP que obtenemos se resuelve por el solver lp-solve versión 5.5.2.3. Debido a las particulares propiedades de anidación de nuestro modelo basado en la estructura, usamos las siguientes opciones en el solver -BB, -Bc, -Bd, -Bg, y -Bo para ordenar variables y aplicar una codiciosa ramificación y poda inversa. 3.4.1. Evaluación de tiempos de análisis En esta sección estudiamos el tiempo necesario para el análisis estático del WCET con el método DLock-MS, una extensión de Lock-MS con una transformación eficiente de CFG a árbol y una heurística de bloqueo dinámico. La figura 3.4 muestra nuestros tiempos de análisis comparados con aquellos que necesita el analizador del WCET (AbsInt +IPET) de Otawa (owcet v1.2.0) [Tra]. En el eje xestán representados los benchmarks y en el eje yla mejora obtenida en el análisis del WCET: el tiempo de ejecución del análisis del WCET de Otawa asumiendo una cache de instrucciones LRU convencional dividido por el tiempo de ejecución de DLock-MS en una cache de instrucciones bloqueable del mismo tamaño. En la parte de la derecha se especifica el nivel de optimización. Los benchmarks están ordenados por número de caminos a explorar en la representación basada en árbol para la optimización O3, de manera que refleja su nivel de complejidad. Para cada benchmark, se muestran con boxplots todos los experimentos variando el tamaño de cache (ver tabla 3.1). Esto es, cada columna muestra una caja cuyos límites indican el primer y tercer cuartil, con una marca dentro que determina la mediana. En las líneas verticales fuera de la caja se muestra la variabilidad fuera de estos cuartiles y los puntos más allá de estas líneas indican valores atípicos, es decir, aquellos que no son estadísticamente relevantes. También, la línea horizontal muestra la unidad de mejora, es decir cuando nuestra propuesta no mejora ni empeora frente a Otawa, y por lo tanto el cociente de comparación es uno. Así, cuanto más altos están los boxplots más rápido es nuestro análisis del WCET comparado con el de Otawa. Con respecto al tiempo de análisis, lo limitamos a un máximo de 10 minutos, así que cualquier experimento que tarde más tiempo se asumirá que ha tardado 10 minutos exactamente. Señalemos entonces que cuando estos casos aparecen en Otawa estamos asumiendo un tiempo de análisis menor que el que debería de ser. Con DLock-MS, solo un experimento tarda más de 10 minutos. Sin embargo, es importante destacar que nosotros somos capaces de proporcionar resultados seguros antes de que se complete nuestro análisis/optimización del WCET. Esto es, cuando paramos nuestro análisis a los 10 minutos, ya tenemos un cota segura del WCET y un conjunto de contenidos específicos para cargarlos en cada punto de bloqueo, 3.4. Resultados 35 -O0 -O1 -O2 -O3 complex_updates countnegative fir2dim iir janne_complex jfdctint matmult matrix1 binarysearch bsort filterbank fft select qsort-exam dijkstra st crc qurt minver lift ndes ludcmp audiobeam md5 pm statemate fmref basicmath petrinet g723_enc 0,1 10 103 0,1 10 103 0,1 10 103 0,1 10 103 Benchmark Tiempo de análisis del WCET (veces más rápido que Otawa) FIGURA 3.4: Comparación de tiempo de análisis estático del WCET para nuestra propuesta (basada en la estructura) y Otawa (AbsInt + IPET). aunque no podamos garantizar que es la configuración óptima, es decir, la que proporciona el WCET menor. Por lo tanto, asumir que los experimentos no tardan más de 10 minutos beneficia a Otawa en la comparación. En la figura 3.4 vemos que en la mayoría de los casos las cajas son simplemente líneas horizontales. Para estos benchmarks, esto significa que la variación de la mejora es muy pequeña en relación al tamaño de cache. Tanto a través de los benchmarks como de los niveles de optimización, DLock-MS es normalmente unas 10 veces más rápido que Otawa, aunque ciertos benchmarks pueden ser especialmente difíciles de analizar para cada método. Por ejemplo, los resultados por encima de 104corresponden a análisis que no se han completado en 10 minutos en Otawa. Por otro lado, en los pocos casos en los que el análisis de Otawa es más rápido parece que se debe a la existencia de varios caminos con un tiempo igual o muy similar de ejecución. Esto evita que el solver pueda descartar rápidamente estos caminos como sucede en el caso de statemate O3. También se tiene que tener en cuenta que Otawa es más rápido que otras propuestas. Por ejemplo, el tiempo de análisis necesario que encontramos en otros estudios es más de 30 veces mayor que el nuestro [ZWY17]. Aunque no se presenta en la figura 3.4, hemos estudiado también el tiempo que DLock-MS invierte en cada parte del análisis. Para los experimentos que se presentan en esta figura, nuestra propuesta tarda una media de 0,06 segundos en obtener el 36 Capítulo 3. Reducción del WCET y del tiempo de análisis complex_updates countnegative fir2dim iir janne_complex jfdctint matmult matrix1 binarysearch bsort filterbank fft select qsort-exam dijkstra st crc qurt minver lift ndes ludcmp audiobeam md5 pm statemate fmref basicmath petrinet g723_enc (todos) -O0 -O1 -O2 -O3 LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD 1.0 1.5 2.0 2.5 3.0 1.0 1.5 2.0 2.5 3.0 1.0 1.5 2.0 2.5 3.0 1.0 1.5 2.0 2.5 3.0 Método de análisis del WCET: Lock-MS (L) o DLock-MS (D) WCET / Siempre acierto WCET (para cada nivel de optimización) FIGURA 3.5: Comparación de WCETs de Lock-MS yDLock-MS, cuanto menor mejor. CFG y generar la estructura en árbol y las restricciones de ILP, mientras que el ILP solver tarda una media de 2,29 segundos en resolver el problema. 3.4.2. Evaluación de la eficacia La figura 3.5 muestra la evaluación de la eficacia de DLock-MS comparada con el método Lock-MS original. Como antes, los resultados están representados por boxplots para cada nivel de optimización. Ya que DLock-MS básicamente extiende a Lock-MS admitiendo múltiples puntos de carga y bloqueo, sus resultados son, en general, iguales o mejores. En concreto, los WCETs se mejoran un 2,2% de media, incluyendo ya el coste extra de introducir los puntos de bloqueo. Este sobrecoste (una llamada a función en cada punto de bloqueo) supone en media un 2,1% del WCET. Aplicando un test de signo de Fisher con un nivel del confianza de 0,99, se obtiene un p-valor de 2,2 ·10−16, lo cual afirma que DLock-MS funciona mejor que LockMS. Aunque las mejoras en la figura 3.5 puedan parecer pequeñas, hay que tener en cuenta que en varios casos Lock-MS ya alcanza el mejor WCET posible (por ejemplo en dijkstra), por lo tanto en estos casos no hay margen de mejora. También puede incrementarse el WCET ligeramente al añadir puntos de carga y bloqueo innecesarios, aunque este incremento debería notarse solo en benchmarks sencillos (por ejemplo en iir,janne_complex ybinarysearch). En los benchmarks más complejos (los de la parte derecha), las mejoras en el WCET son claras y el único caso problemático es cuando varias regiones están volviendo a cargar los mismos contenidos, como pasa en qurt. No obstante, esta situación es bastante trivial de detectar y evitar. Además de las comparaciones previas, evaluamos también la eficacia de la cache de instrucciones bloqueable cuando se analiza con DLock-MS. Debido a que el WCET decrece linealmente con respecto a la tasa de aciertos de la cache de instrucciones, si nuestra tasa de aciertos en el camino del WCET es parecida a aquella en la ejecución real, podemos asegurar que nuestros resultados son lo suficientemente precisos. Además de este modo evitamos que la peculiaridades de los métodos de 3.4. Resultados 37 complex_updates countnegative fir2dim iir janne_complex jfdctint matmult matrix1 binarysearch bsort filterbank fft select qsort-exam dijkstra st crc qurt minver lift ndes ludcmp audiobeam md5 pm statemate fmref basicmath petrinet g723_enc (todos) -O0 -O1 -O2 -O3 SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 Caso de análisis de tasa de aciertos: simulación con LRU convencional (S) o camino WCET con DLock-MS (D) Tasa de aciertos en cache de instrucciones FIGURA 3.6: Comparación de las tasas de aciertos en la cache de instrucciones de nuestra propuesta (tasa de aciertos alcanzada a través del camino WCET analizado) y una simulación de ejecución (tasa de aciertos de una ejecución de simulación con una cache de instrucciones convencional), cuanto mayor mejor. análisis del WCET enturbien el objetivo real, esto es, ser ligeramente mejor que la cota del WCET alcanzada por otros métodos es mucho menos importante que acercarse al WCET real del programa. Así mismo, comparamos los resultados de nuestra cache de instrucciones bloqueable con una cache de instrucciones LRU para comprobar que DLock-MS alcanza un nivel aceptable de rendimiento. Para obtener las tasas de acierto reales usamos el simulador Gem5 v2.0 [Bin+11] configurando una segmentación equivalente con una cache de instrucciones LRU del mismo tamaño. Por otra parte obtenemos la tasa de aciertos de la cache de instrucciones bloqueable en el peor camino de ejecución cuando se aplica DLock-MS. Como antes, estos resultados se presentan a través de boxplots para cada benchmark y nivel de optimización. La figura 3.6 muestra que las tasas de aciertos en el peor camino con una cache bloqueable son comparables con aquellas con una cache LRU en todos los benchmarks y niveles de optimización, y en media es siempre mejor en la cache bloqueada dinámicamente (columna de la derecha). De hecho, hay muchos casos donde la cache bloqueada dinámicamente supera la cache LRU. Esto significa que, para muchos benchmarks, bloquear el código adecuado es probable que funcione tan bien o mejor que la política LRU, cuyo dinamismo puede expulsar contenido que se usará de nuevo pronto. Por otro lado, los benchmarks cuya tasa de aciertos LRU es mayor son mayoritariamente los que están situados a la derecha en la figura 3.6. Esto es coherente, ya que el dinamismo natural de la cache LRU adapta su comportamiento en estos benchmarks que son más grandes y complejos, mientras que la cache bloqueable, incluso con una heurística de bloqueo dinámico, tiene un comportamiento más restringido. 38 Capítulo 3. Reducción del WCET y del tiempo de análisis complex_updates countnegative fir2dim iir janne_complex jfdctint matmult matrix1 binarysearch bsort filterbank fft select qsort-exam dijkstra st crc qurt minver lift ndes ludcmp audiobeam md5 pm statemate fmref basicmath petrinet g723_enc (todos) 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 0.25 0.50 0.75 1.00 Nivel de optimización gcc (-O) WCET con respecto a -O0 FIGURA 3.7: Efectos del nivel de optimización del compilador (GCC 6.3.1) en el WCET (cuanto menor, mejor). 3.4.3. Impacto del nivel de optimización del compilador La mayoría de estudios en sistemas de tiempo real deshabilitan las optimizaciones para que la concordancia entre le código binario y el de alto nivel sea más sencilla. Además, hasta donde sabemos, ninguno de ellos ha realizado un análisis exhaustivo sobre cómo afectan las optimizaciones al peor caso de tiempo de ejecución. De manera intuitiva podemos afirmar que las optimizaciones reducen el tiempo medio de ejecución, así que, en general, debería reducirse también el WCET. Sin embargo, cualquier optimización que reduce el tiempo medio de ejecución incrementando el tiempo de ejecución en caminos infrecuentes, resultará en un incremento del WCET si este se encuentra en uno de estos caminos inusuales. En esta sección estudiamos el impacto en el WCET de los niveles de optimización en compilación. Nos centramos en los resultados para GCC 6.3.1, los resultados para GCC 4.8.4 (no se muestran) presentan tendencias casi idénticas. La figura 3.7 muestra cómo los niveles de optimización afectan al WCET. El eje x representa el WCET relativo a compilar sin ninguna optimización (-O0). Se presenta esta información para cada benchmark más el agregado de todos ellos en la parte de la derecha, y se representan con boxblots como antes. También podemos ver una línea horizontal que indica el caso base (es decir, el WCET del binario compilado sin optimizaciones para cada experimento) en y=1. Por lo tanto, cuanto más bajos estén los bloxpots, menor (mejor) será el WCET correspondiente para esa optimización. La observación más importante es que, en media, los boxplots se sitúan alrededor del 0,3. Esto significa que, en general, el WCET de un código optimizado será en torno a un tercio de su WCET sin optimizaciones. Por lo tanto, se deberían usar binarios optimizados en los sistemas de tiempo real. En media, los mejores resultados se alcanzan con O3, aunque cada benchmark tiene un comportamiento específico. Otro detalle interesante es que la mejora del WCET no se debe (exclusivamente) al tamaño del código del binario optimizado. Los binarios de O3 normalmente son mayores que aquellos compilados con O1 y O2 (ver en la tabla 3.2) y sin embargo 3.5. Conclusiones 39 presentan un WCET menor. Por ejemplo, el tamaño de los binarios O3 es alrededor de dos veces el tamaño de O2 en fir2dim,fmref,g723_enc,iir, cuatro veces en ludcmp, y seis veces en complex_updates, y a pesar de ello O3 consigue un WCET menor. Este es un punto muy importante a tener en cuenta ya que todos los experimentos realizados conllevan un gran trabajo para la cache que el tamaño del binario puede incrementar sustancialmente. Sin embargo, estas optimizaciones pueden tener también efectos ligeramente adversos para el WCET, como puede verse en binarysearch, dónde O3 es unas 7 veces mayor que el tamaño de O2. Destaca el efecto singular que encontramos en petrinet. Como se puede ver, O2 y O3 muestran un WCET significativamente peor que O1. Esto se debe a las transformaciones que se han llevado a cabo en los bucles por estas optimizaciones. Estas transformaciones han derivado en unos patrones de bucle que de manera inherente se sobrestiman en el proceso de análisis del WCET. A continuación, exploramos más profundamente en este problema de análisis de ciertos patrones de bucle. Dependiendo del código fuente y el nivel de optimización, la distribución de bloques básicos que contienen la cabecera y el cuerpo del bucle pueden ser totalmente distintos. En la figura 3.8 se muestran varios patrones de bucle, donde Nes el número máximo de ejecuciones del cuerpo del bucle, que en nuestros experimentos ha sido etiquetado manualmente. En esta figura, las cajas limitadas por líneas discontinuas representan uno o más bloques básicos, mientras aquellas limitadas por líneas continuas representan un solo bloque básico. En el patrón 1 (a) encontramos el bucle básico do-while. Solo hay una salida y está en el mismo bloque básico que vuelve al inicio del bucle. Todos los bloques básicos de este bucle se ejecutan como mucho Nveces. El patrón 2 (b) (un bucle while ofor) tiene solo una salida, que está en el bloque básico de entrada (la cabecera) del bucle. Si el cuerpo del bucle se ejecuta Nveces, su cabecera se ejecuta N+1 veces. Nos encontramos que en otros patrones de bucle, como el 3 (c), puede ser difícil o incluso imposible saber dónde se encuentra la cabecera o el cuerpo del bucle, los cuales pueden incluso estar intercalados con condiciones de salida de bucle, ambos distribuidos a lo largo de varios bloques básicos. Por lo tanto, una aproximación segura implica asumir que todos los bloques básicos implicados se ejecutan N+ 1 veces. Esta aproximación, aunque segura, puede producir una sobrestimación. Este es el caso de los binarios O2 y O3 de petrinet en la figura 3.7. En O1, este benchmark contiene 151 bloques básicos (de un total de 161) que se ejecutan dos veces cada uno en el peor caso, sin embargo en O3 se tiene que asumir que se pueden ejecutar hasta 3 veces. Esto incrementa la cota del WCET en torno a 3/2, como se pude ver en la figura 3.7. 3.5. Conclusiones En este capítulo se ha presentado DLock-MS, una extensión del método de anális del WCET Lock-MS. Nuestro objetivo es reducir el tiempo de análisis del WCET en presencia de una cache de instrucciones bloqueable. Nuestra extensión implementa principalmente dos mejoras. La primera es un algoritmo para transformar el CFG en una estructura en árbol, necesaria para usar Lock-MS como un método de análisis del WCET basado en la 40 Capítulo 3. Reducción del WCET y del tiempo de análisis (b) Patrón 2 N+1 N (a) Patrón 1 N (c) Patrón 3 N+1 N+1 N+1 FIGURA 3.8: Varios patrones de bucle encontrados en el código binario. estructura. Este algoritmo genera un árbol cuyo modelo ILP puede resolverse fácilmente a través de una ramificación y poda invertida. Estas transformaciones se realizan en una sola pasada, procesando cada camino alternativo una sola vez. El árbol resultante tiene muchos menos caminos a explorar que el CFG original, lo cual reduce el tiempo de análisis del WCET sin sacrificar precisión para una cache de instrucciones bloqueable. La segunda mejora es una heurística de bloqueo dinámico basada en los bucles, aplicada en los bucles externos, que permite obtener el contenido óptimo de cache para el WCET de cada región, es decir, la configuración que minimiza el WCET en cada región. La complejidad de esta heurística es muy baja, reduce el WCET explotando de manera efectiva el reuso temporal, y reduce todavía más el tiempo de análisis del WCET aislando el WCET de cada región. Los resultados muestran que DLock-MS es alrededor de 10 veces más rápido que Otawa, una herramienta del estado del arte basada en AbsInt eIPET. Debido a su rapidez este análisis del WCET pude ser muy significativo en el proceso de diseño de un sistema de tiempo real y una alternativa al análisis paramétrico del WCET. Además, nuestro análisis puede detenerse antes de completarse, proporcionando, incluso en este caso, un WCET seguro y una configuración para la cache bloqueable que lo garantiza. Esto quiere decir que cualquier solución de nuestro modelo es segura, y que es al completar el análisis cuando se garantiza el WCET óptimo (mínimo) para cada región. También evaluamos la eficacia de DLock-MS, confirmando que reduce el WCET respecto al método original Lock-MS, y comparamos su tasa de aciertos en una cache bloqueable con una convencional LRU. Nuestros resultados muestran una tasa de aciertos muy similar en todos los benchmarks, siendo la cache bloqueable la que ofrece mejores tasas de aciertos en muchos de ellos. Hay que destacar también que estos resultados se consiguen con un hardware muy sencillo, mucho más que una cache convencional LRU. Finalmente, estudiamos el impacto de los niveles de optimización en el WCET. Nuestra conclusión es que se deben descartar las compilaciones sin optimización (-O0) ya que generan binarios con un WCET entre 3 y 4 veces peor que con la presencia de optimizaciones. En general, O3 genera los binarios con los WCETs más pequeños, pero otros niveles de optimización son también muy eficaces. Sin embargo, optimizaciones agresivas en algunos benchmarks pueden suponer un incremento 3.5. Conclusiones 41 significativo del WCET. Estas optimizaciones pueden cambiar los patrones de bucle de manera que el método de análisis del WCET se ve forzado a asumir iteraciones adicionales en los bucles para garantizar la seguridad del análisis. Este trabajo ha sido publicado en [Ped+20b]. 43 Capítulo 4 Impacto de la vectorización automática en el WCET En este capítulo continuamos el estudio del análisis del WCET considerando las instrucciones resultantes de la vectorización automática. Desde los años 80 los microprocesadores comerciales han estado añadiendo constantemente extensiones vectoriales a su repertorio de instrucciones y recursos hardware para poder ejecutar eficiente estas instrucciones vectoriales. Sin embargo, su impacto en el WCET no se ha estudiado en profundidad debido a la falta de soporte de las instrucciones vectoriales en las herramientas actuales de análisis del WCET. Este será entonces el objeto de este capítulo. Generamos el código vectorizado de manera automática desde el código fuente a través de las funciones que proporcionan los compiladores actuales. Después, partiendo de las especificaciones temporales de los fabricantes estudiamos las partes vectorizadas permitiéndonos acotar su aportación al WCET de la tarea. Finalmente, integramos las cotas obtenidas en el análisis del WCET de la tarea correspondiente. Como resultado obtenemos que el WCET se reduce si se vectorizan los bucles que concentran la mayor parte del tiempo de ejecución. Además, la eficiencia de la vectorización automática en las herramientas de compilación es bastante limitada, por lo que cabe esperar más beneficios en benchmarks más grandes o si se reescribe el código. 4.1. Introducción Independientemente del método de análisis del WCET, mejorar una tarea en los sistemas de tiempo real estricto significa reducir la cota calculada del WCET, aunque esto suponga incrementar el tiempo medio de ejecución. Por el contrario, no siempre que se reduce el tiempo medio de ejecución va a verse reducido el WCET. A este respecto, las mejoras microarquitecturales como la memoria cache han demostrado reducir el tiempo medio de ejecución pero no el peor caso de ejecución, tal y como hemos visto. En este capítulo, nos centramos en otra mejora microarquitectural: la vectorización, que explota el paralelismo de datos, analizando su efecto en el WCET. El procesador Intel Pentium MMX popularizó la vectorización a mediados de los años 90 y actualmente encontramos que existen procesadores de distintos fabricantes que incorporan en su repertorio de instrucciones (instruction set architecture, ISA) las llamadas extensiones vectoriales. Estas extensiones utilizan un tipo de paralelismo en las que cada instrucción define una operación que se aplica simultáneamente en los elementos de un vector (single instruction multiple data, SIMD). Desde su aparición, la vectorización ha demostrado ampliamente su solidez tanto en aplicaciones 50 Capítulo 4. Impacto de la vectorización automática en el WCET De todo nuestro repertorio de benchmarks encontramos que el compilador no ha producido ninguna vectorización del código en 18 de ellos1. Este hecho nos señala que es necesario seguir trabajando para identificar si esta falta de paralelismo vectorial es real o si por el contrario puede subsanarse con transformaciones sencillas del código o de los datos. Debido a que nuestro propósito es comparar benchmarks en sus versiones escalar y vectorizada, aquellos en los que la vectorización no ha surtido efecto se han descartado. Además en este capítulo utilizamos el benchmark matmult_opti en vez de matmult para facilitar su vectorización. Cabe destacar que aunque hay varios benchmarks de la suite TACLeBench cuyo algoritmo coincide con otro benchmark de Mälardalen (binarysearch/bs,countnegative/cnt,jfdctint/fdct,petrinet/nsichneu), su comportamiento al ser vectorizados por el compilador no coincide ya que este resultado depende en gran medida del código en alto nivel. De hecho, de estas duplas, la única que de la que se obtiene una vectorización de la suite de Mälardalen es el benchmark cnt. Este hecho refuerza la idea de la importancia de una programación que facilite la vectorización. El número de iteraciones de los bucles escalares que se dan en el peor caso está anotado en el código fuente de los programas. Estas anotaciones o bien se encontraban ya en el código original del benchmark o las hemos añadido nosotros manualmente. En el caso del número de iteraciones en los bucles vectoriales se han calculado tal como se expone en la sección 4.3.1. 4.5. Resultados experimentales En esta sección, evaluamos el impacto que tiene en el WCET la vectorización de código en los benchmarks de tiempo real. Calculamos el WCET de nuestros benchmarks con nuestro entorno de análisis estático de binarios (sección 4.3) basado en OTAWA [Bal+10] y Lock-MS [Apa+11]. Para cada uno de los benchmarks producimos dos binarios distintos. Uno se ha generado activando la vectorización automática de bucles del compilador GCC 4.8.4 mientras que el otro binario se ha generado evitando esta vectorización. El resto de opciones de compilación están detalladas en la sección 4.4.1. En las tres columnas más a la derecha de la tabla 4.2 encontramos información adicional que nos permite mostrar la eficacia del compilador GCC 4.8.4 vectorizando los bucles del código fuente de cada benchmark. En concreto, se muestra el número de bucles que han sido vectorizados por el compilador (Columna Vect.), el número de bucles que no se han vectorizado (Column No-Vect.), y el número de elementos que se procesan simultaneamente en cada iteración de los bucles vectorizados (Columna Vías). En el caso de jfdctint,md5 ypm, los tipos de dato de los bucles vectorizados son enteros de 32-bit y caracteres así que el número de elementos que se procesan simultáneamente son 4 y 16, respectivamente. El hecho de que la vectorización automática de GCC 4.8.4 haya funcionado en solo 17 de 35 benchmarks, parece indicar que la autovectorización de este compilador es bastante limitada. Seguramente reescribiendo algunas partes del código original podríamos facilitar esta vectorización automática, pero esta tarea va más allá del propósito de este trabajo. La figura 4.3 muestra la mejora relativa del código vectorizado sobre el código no vectorizado para cada benchmark. Asumimos una cache de instrucciones bloqueable de mapeo directo de 128 bytes, con líneas de cache de 32 bytes. También 1bynarysearch, bs, crc, dijkstra, fdct, iir, janne_complex, ludcmp, matmult, ndes, nsichneu, petrinet, qsortexam, qurt, select, st, statemate, minver. 4.5. Resultados experimentales 51 audiobeam basicmath bsort cnt complex_updates countnegative fft filterbank fir2dim fmref g723_enc jfdctint lift matmult_opti matrix1 md5 pm A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F 1.0 1.5 2.0 2.5 3.0 Latencia de datos (A: Siempre acierto, 1 ciclo; F: Siempre fallo, 10 ciclos) WCET no-vectorizado/ WCET vectorizado FIGURA 4.3: Comparación del impacto de la vectorización en el WCET. asumimos la presencia de un line-buffer: una cache convencional (dinámica) de instrucciones de solo una línea de cache [Apa+11;PD02]. Por tanto, el método de análisis del WCET contabiliza los aciertos (1 ciclo) y fallos (11 ciclos) en la búsqueda de instrucciones. Consideramos dos escenarios diferentes que dan una perspectiva de la importancia de la cache de datos (ya sean escalares o vectoriales). El primer escenario (A) corresponde a una jerarquía de cache de datos ideal donde cada acceso a datos resulta siempre en acierto. En el segundo escenario (F), los accesos a datos siempre resultan en fallo y se penalizan con 10 ciclos debido a la latencia de memoria. Probablemente este último escenario se acerca más a la realidad ya que normalmente las instrucciones vectoriales en los procesadores comerciales actuales omiten a la cache de datos L1 y solicitan los datos que necesitan directamente a L2. Destacan los resultados de la vectorización en el caso de matmult_opti ymatrix1 ya que son hasta 3 veces mejor que la versión no vectorizada. Este valor es muy cercano al máximo esperado cuando 4 elementos se procesan simultáneamente, que resultaría una mejora de 4 (ver tabla 4.2). Al inspeccionar manualmente el binario vectorizado descubrimos que el bucle que contiene la mayor carga computacional se ha vectorizado especialmente bien y que no se ha necesitado un bucle de epílogo. Estos casos muestran que las instrucciones vectoriales reducen de forma efectiva el WCET. Para otros benchmarks como fft,g723-enc ylift, a pesar de que algunos de sus bucles se han vectorizado, no consiguen una mejora mayor del 1.25. En esta ocasión, los bucles vectorizados no forman parte de donde se concentra la mayor parte de la ejecución, así que la mejora es menor. Desafortunadamente, en algunos benchmarks, (audiobeam,basicmath,bsort and filterbank) el rendimiento del binario vectorizado es peor que el no vectorizado. En estos casos el número de iteraciones es especialmente pequeño comparado con otros benchmarks. Por ejemplo, el bucle vectorial en basicmath se ejecuta una sola vez. Este no puede compensar el sobrecoste generado en el código al vectorizar el bucle. Esto es, el código en el que se elige entre el bucle escalar o vectorial, las instrucciones adicionales que los bucles vectoriales necesitan para preparar el recorrido del bucle 52 Capítulo 4. Impacto de la vectorización automática en el WCET (por ejemplo, la propagación de constantes en las vías de un registro vectorial) y los fallos adicionales en la cache de instrucciones que el código vectorial pueda causar. De todos modos, nuestra recomendación es comparar los WCET de las versiones escalares y vectoriales y elegir el mejor de ellos, es decir, el menor. 4.6. Conclusiones En este capítulo analizamos la eficacia del código vectorizado en el WCET estudiando las prestaciones de la vectorización automática de GCC en paquetes de benchmark de tiempo real. Tras analizar los código vectoriales, se integran sus especificaciones temporales correspondientes en la herramienta de análisis del WCET. Nuestros resultados muestran que el WCET se reduce de manera efectiva cuando los bucles vectorizados forman parte del código dónde se lleva a cabo la mayor parte de la ejecución. Por ejemplo, en la versión vectorial del benchmark matmult_opti el WCET se reduce por un factor de 3 respecto a la versión escalar. Sin embargo, sus beneficios no resultan tan evidentes como se esperaba, debido, en parte, a la eficacia limitada que ofrecen las herramientas de compilación en la vectorización automática. Se podría solventar reescribiendo el código fuente de manera que se facilitara la vectorización automática o incluso escribiendo explícitamente el código vectorial, pero la eficacia de esta vectorización dependerá de la habilidad de quien programa. El número de iteraciones de los bucles en algunos de los benchmarks de tiempo real que hemos analizado es bastante pequeño, probablemente porque estos benchmarks son simples kernels, es decir, operaciones/algoritmos que forman parte de los núcleos de programas de tiempo real mucho mayores. Por lo tanto, el número de iteraciones no es lo suficientemente grande para compensar el sobrecoste de utilizar código vectorial. En estos casos, se debe evitar la vectorización. Como conclusión, pensamos que nuestros resultados fomentan el uso de los recursos vectoriales en sistemas de tiempo real estricto, posiblemente escribiendo códigos con el paralelismo de datos en mente, tal como puede ser el benchmark matmult_opti que se ha presentado en la sección 4.4.3. Actualmente, como los recursos del chip continúan creciendo, el procesamiento vectorial esta convirtiéndose en una utilidad básica en los mayoría de los procesadores del mercado. Este trabajo podría continuarse en el futuro examinando con más detenimiento los benchmarks que no han podido vectorizarse, para encontrar a qué se debe. Para ello se tendría que evaluar la cantidad de paralelismo en datos y comprobar el estilo de programación buscando construcciones que dificulten la vectorización tal como punteros, reuso escalar a través de distintas iteraciones, vectores no alineados, etc. 53 Capítulo 5 Tasa ideal y predecible de aciertos para la transposición de matrices en caches de datos Tras concluir en los capítulos anteriores el gran impacto de la latencia en la jerarquía de memoria en el WCET y explorar distintas vías tanto para agilizar su análisis como para reducir el propio WCET, en este capítulo, analizamos un algoritmo fundamental en los sistemas de tiempo real: la transposición de matrices. Analizamos el número de accesos y tasa de aciertos en cache de datos, cuyo efecto es de gran relevancia en el cálculo de su WCET. Una transposición de matrices es una operación básica. Sin embargo, su tasa de aciertos en cache de datos para grandes matrices es muy baja y no se puede predecir fácilmente. En el contexto de tiempo real es imprescindible que la tasa de aciertos (su peor caso) se pueda predecir de manera segura. En este capítulo obtenemos la relación entre los parámetros de cache que garantizan la tasa (predecible) ideal de aciertos en datos tomando una cache de datos LRU. Tras ello y teniendo en cuenta nuestras valoraciones analíticas comparamos los algoritmos de transposición de matrices tiling ycache-oblivious. El resultado de esta comparación demuestra que, con el tamaño adecuado de tile, la versión tiling del algoritmo obtiene una tasa de aciertos en datos igual o mejor. Adicionalmente analizamos el consumo de energía y el tiempo de ejecución de la transposición en hardware real con caches PLRU. Gracias a que nuestro análisis de aciertos y fallos proporciona cotas para el peor caso podemos permitir el uso de caches de datos LRU (poco predecibles en general) para la transposición de matrices en sistemas de tiempo real. Además, nuestras valoraciones analíticas permiten restringir sin ningún impacto negativo los recursos dedicados a la transposición de matrices. Se consigue así reducir tanto la contaminación a otros procesos como el consumo de energía, lo que es realmente útil en general y específicamente en la computación de alto rendimiento. 5.1. Introducción La transposición de matrices es una operación fundamental en áreas tales como el álgebra lineal o las transformadas de Fourier. Además tiene muchas aplicaciones en otras como el análisis numérico, el procesado de imágenes y gráficos. Hay muchos ejemplos de aplicaciones desarrolladas en los centros de supercomputación que usan, de un modo u otro, la transposición de matrices como parte esencial para solucionar sus problemas [RJ16;Bal+16]. 54 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices Aunque la transposición en sí misma es un problema bastante simple, cuando tomamos matrices de gran tamaño presenta una tasa de aciertos en cache de datos muy pequeña [CS00]. Esto se debe a que aunque los elementos por filas son accedidos consecutivamente se intercalan con el recorrido por columnas que conlleva la transposición. El que los elementos se accedieran consecutivamente por filas haría posible que encajasen en la misma línea de cache y por lo tanto hubiera reuso temporal. Sin embargo, la interferencia del acceso por columnas conlleva que los aciertos potenciales acaban generando fallos por capacidad. Existen transformaciones de código conocidas y usadas de manera habitual para solventar este problema. La transformación tiling oblocking está presente en las bibliotecas de alto rendimiento (p.e. Intel MKL, NVIDIA cuBLAS) y consiste en dividir todo el problema en pequeños tiles («teselas») que quepan en la cache [LRW91] y con los que se puede trabajar de manera independiente. Al transponer los tiles completamente uno detrás de otro (o por parejas) permite que los tiles implicados permanezcan en cache mientras se están procesando, evitando así los fallos por capacidad. Aunque aplicar eficientemente una transformación de tiling incrementa la tasa de aciertos en la cache de datos todavía podemos encontrar dos importantes desventajas. Primero, añadir bucles implica añadir más instrucciones para poder llevar a cabo la transposición de matrices, con su correspondiente tiempo de ejecución. La segunda desventaja que tenemos que considerar es que la tasa de aciertos del código transformado está influenciada por el tamaño de la matriz a transponer y por la configuración específica de la cache del sistema correspondiente (es decir, número de conjuntos y vías, tamaño de línea de cache, política de reemplazo, prebúsqueda, cache víctima, etc.). Estos inconvenientes se han abordado desde la perspectiva de optimización de compiladores tratando de minimizar el número de fallos en cache que se generan desde el código binario [Bao+18]. Cuando trabajamos con sistemas de tiempo real estas desventajas se vuelven críticas ya que se debe concretar el peor tiempo de ejecución (WCET) en el momento del diseño [Rei+07]. Por esta razón si los aciertos y fallos no se pueden predecir con antelación el sistema de tiempo real se diseñará asumiendo una sobre-estimación en su comportamiento, lo que nos llevará a desaprovechar los recursos hardware e incrementar el consumo de energía. Además, los sistemas de tiempo real necesitan predicciones seguras así que no se pueden aplicar técnicas que no garanticen el resultado del peor caso. También estos inconvenientes son importantes en la computación en la nube ya que las configuraciones de las caches de las máquinas virtuales utilizadas y conocidas pueden no coincidir con las máquinas físicas y además ser desconocidas. Por otro lado podemos usar un algoritmo cache-oblivious de transposición de matrices. Este algoritmo es, esencialmente, una versión recursiva del algoritmo de tiling (hasta alcanzar tiles de 2 ×2 elementos) por lo tanto el rendimiento óptimo de la cache se alcanza por su propia naturaleza recursiva y su configuración no depende de los parámetros de la cache. Como concluyen Tsifakis et al [TRS04]: «No es trivial predecir a priori como va a ser el rendimiento del algoritmo cache-oblivious», por lo tanto persisten las desventajas anteriormente presentadas. No obstante este algoritmo evita tener que añadir un parámetro extra que tener en cuenta: el tamaño de tile. Independientemente de como implementemos la transposición de matrices, hasta donde alcanza nuestro conocimiento, no hay ningún trabajo previo que proporcione una valoración analítica de aciertos/fallos de este problema. Sin este análisis se puede estudiar la tendencia del rendimiento para unos parámetros específicos 5.2. Estudios previos 55 de cache pero no va a ser posible ajustar de forma precisa estos parámetros y de la misma manera tampoco se va a poder dar una predicción concisa del rendimiento. Para abordar este problema estudiamos la transposición de matrices desde una perspectiva teórica y cómo afectan a la tasa de aciertos tanto los parámetros de cache (número de conjuntos, vías y tamaño de línea) como el padding («relleno») aplicado a la matriz para el algoritmo tiling y una cache con política de reemplazo LRU. Validamos las expresiones analíticas obtenidas en nuestro estudio a través de simulaciones en las que consideramos un amplio rango de parámetros. Y también comparamos nuestros resultados con los de una implementación cache-oblivious mejorada con una nueva técnica de padding que hemos denominado phantom padding («relleno fantasma»). Para terminar analizamos el rendimiento de una transposición de matrices en hardware real (con una configuración específica de cache) que nos permitirá verificar si se cumplen nuestras predicciones teóricas. El resto del capítulo se estructura de la siguiente manera. En la sección 5.2 presentamos el trabajo relacionado con el estudio del comportamiento en cache de la transposición de matrices. En la sección 5.3 presentamos el orden de acceso de las diferentes implementaciones de la transposición de matrices. A continuación en la sección 5.4 calculamos las tasas ideales de acierto para la transposición de matrices independientemente de la cache y del tipo de algoritmo. En la sección 5.5 analizamos qué configuraciones de cache LRU son necesarias para alcanzar estas tasas. En la siguiente sección 5.6 proponemos un padding extra que permite alcanzar la tasa ideal de aciertos con menos recursos de cache. Todas las expresiones analíticas obtenidas en estas secciones son validadas por medio de simulaciones extensivas en la sección 5.7. En esta sección, además, los resultados obtenidos se comparan con aquellos proporcionados por el algoritmo cache-oblivious. Finalmente, las conclusiones de este capítulo se exponen en la sección 5.8. 5.2. Estudios previos En esta sección examinamos algunos trabajos que analizan el comportamiento de aciertos y fallos de la cache de varios algoritmos de transposición de matrices. Debido a que el algoritmo de transposición de matrices es bastante simple y hace un uso intensivo de memoria numerosos trabajos se han centrado en tratar de analizar y mejorar el uso de la jerarquía de memoria. Se han investigado dos alternativas para gestionar el patrón de accesos en una cache para este algoritmo tal y como se han introducido en este capítulo: tiling y cache-oblivious. Ambos enfoques buscan exponer a la jerarquía de memoria a un patrón de acceso de datos que explote el reuso (espacial y temporal) en la cache subyacente [Fri+99;LRW91;CS00;TRS04;Yot+07;Lei03;Fri+12]. A continuación, presentamos las diferencias entre los trabajos relacionados y el nuestro. Cache-Efficient Matrix Transposition Reference [CS00] describe varios algoritmos de transposición de matrices y compara su rendimiento usando tanto simulación como ejecuciones reales en un sistema basado en Sun UltraSPARC II. A través de las simulaciones se muestra que el algoritmo cache-oblivious es el que tiene menos número de fallos para matrices de pequeño tamaño. Sin embargo, ocurre al contrario para matrices grandes ya que es el que presenta mayor número de fallos. Además, los tiempos de ejecución presentados muestran que, en la mayoría de los casos, el algoritmo cache-oblivious es significativamente más lento que los otros algoritmos analizados. En el estudio se sugiere que la razón por la que el rendimiento no es el esperado es porque no hay suficiente asociatividad. Si lo comparamos con nuestro 56 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices enfoque, su análisis se limita a una evaluación experimental sin proporcionar ninguna valoración analítica de aciertos y fallos de los diferentes algoritmos. Cache Oblivious Matrix Transposition: Simulation and Experiment Reference [TRS04] analiza en mayor profundidad el algoritmo de transposición de matrices cache-oblivious con la intención de racionalizar los resultados de Chatterjee y Sen [CS00]. Estudian el rendimiento del algoritmo, con respecto a los fallos en cache, tanto con simulación como con contadores hardware en dos sistemas Sun UltraSPARC completamente distintos entre sí. Como en nuestro trabajo, comparan los algoritmos tiling y cache-oblivious pero se centran en el comportamiento de este último. Sin embargo, analizan solo una configuración específica de cache y un solo tamaño de tile, variando únicamente el tamaño de la matriz. Sus resultados muestran que los fallos en cache se caracterizan por un patrón bastante estructurado que depende de la configuración de la cache y del tamaño de la matriz. No obstante, no determinan cuándo el algoritmo cache-oblivious va a tener un buen o un mal rendimiento, sino solamente que incrementando el número de vías de la cache se mejora la tasa de aciertos. En nuestro trabajo, evaluamos analíticamente esta cuestión. The Cache Performance and Optimizations of Blocked Algorithms Reference [LRW91] se centra en optimizar el rendimiento de la cache a través del transformación blocking (tiling) de algoritmos. Su enfoque consiste en, primero, mostrar el comportamiento de caches bajo tiling, para después mejorar su rendimiento a través de técnicas software y/o hardware. Analizan el algoritmo de multiplicación de matrices en su versión tiling y concluyen que el rendimiento de la cache es extremadamente dependiente del tamaño del problema y del tile. También afirman que las tasas de fallo tienen una gran sensibilidad con respecto al tamaño de la matriz. Sin embargo, como veremos en nuestra propuesta, un ajuste preciso del algoritmo tiling de transposición proporciona a quien programa muchos más grados de libertad. An Experimental Comparison of Cache-oblivious and Cache-conscious Programs Reference [Yot+07] compara de manera experimental un programa cache-oblivious con uno cache-conscious (cache consciente, tiene aplicado la transformación de tiling) tanto para la multiplicación como para la transposición de matrices. Afirman que hay un sobrecoste que pagan los programas cache-oblivious por su habilidad para adaptarse automáticamente a la jerarquía de memoria. También determinan que incluso aquellos programas cache-oblivious que están altamente optimizados tienen un rendimiento significativamente peor que su respectivo programa cache-conscious. Sin embargo, a diferencia de nosotros, no analizan un extenso rango de configuraciones de cache ni de tamaños de tile debido a limitaciones experimentales. En general, consideramos al comparar estos trabajos que para llevar a cabo sus experimentaciones e implementaciones muchos de ellos usan un tamaño de matriz múltiplo del tamaño de línea de la cache y del tamaño de tile lo cual facilita el análisis [CS00;LRW91;TRS04] y otros consideran el padding como una técnica para evitar esta restricción pero no evalúan analíticamente sus efectos [Yot+07]. De todos modos, ninguno ha considerado las colisiones en los conjuntos de la cache en el caso de filas consecutivas de la misma columna, que es el caso principal de acceso a las columnas en la transposición. Nosotros abordamos esta cuestión añadiendo un padding adicional, el row-shift padding [Hon+16;Pan+99;Bac+94]. Existe otro problema más para el algoritmo cache-oblivious de transposición de matrices, que hará que se beneficie de la aplicación de un phantom padding (hasta dónde sabemos una propuesta original de nuestro trabajo) que también analizaremos en este capítulo. 5.3. Implementaciones de la transposición de matrices 57 5.3. Implementaciones de la transposición de matrices En esta sección examinamos los recorridos de las diferentes implementaciones de la transposición de matrices ya introducidas en este capítulo. Estas propuestas pretendenden incrementar la tasa de aciertos en cache de datos (objeto de nuestro estudio) varíando el orden de acceso a los elementos de la matriz y, por tanto, a las líneas de cache que los contienen determinando su presencia en la cache (con el consecuente fallo o acierto en el acceso) según la política de reemplazo. En la figura 5.1 se muestran el orden de acceso a los elementos de una matriz 8×8 para cada uno de los algoritmos: Simple: Recorre la matriz por filas intercambiando sus elementos en la posición (i,j)por aquellos en la posición (j,i). Esta implementación es simple pero presenta una tasa de aciertos muy pequeña en grandes matrices ya que no se beneficia del reuso temporal. En la figura 5.1(a) se muestra este comportamiento. Tiling: divide todo el problema en pequeños tiles («teselas») que quepan en la cache [LRW91] y con los que se puede trabajar de manera independiente. Esto permite un aumento de la tasa de aciertos gracias al reuso temporal. Básicamente esta transformación consiste en añadir bucles externos al código original de modo que la secuencia de accesos globales no se extiende a toda la memoria sino que se localiza en el proceso de cada tile. En la figura 5.1(c) encontramos un ejemplo con tamaño de tile 4 ×4 elementos. La matriz se divide en 4 tiles, aquellos que pertenecen a la diagonal se transponen sobre si mismos y los otros se transponen entre sí por parejas (siguiendo uno un recorrido por filas, y el otro por columnas). En cada tile se aplica internamente el recorrido del algoritmo «Simple». Análogamente, en la figura 5.1(d) se muestra el algoritmo tiling si determinamos un tamaño de tile 2 ×2 elementos. Cache-oblivious: Este algoritmo es, esencialmente, una versión recursiva del algoritmo de tiling por lo tanto el rendimiento óptimo de la cache se alcanza por su propia naturaleza recursiva. Es decir, un algoritmo cache-oblivious no precisa conocer explícitamente ningún parámetro de la configuración de la cache. Tal como se muestra en la figura 5.1(b), el algoritmo divide primero la matriz en tiles de 4 ×4 elementos para dividir cada una en tiles de 2 ×2. La principal diferencia en el recorrido con el algoritmo tiling con tiles de 2 ×2 elementos es el orden en la que recorre los tiles, como se puede apreciar en la figura. 5.4. Tasas ideales en cache de datos para la transposición de matrices La tasa de aciertos en cache de datos es el porcentaje de accesos de datos que producen aciertos en cache. Llamamos tasa ideal de aciertos a aquella que se produciría en una cache de capacidad ilimitada. Concretamente consideramos una cache con un número ilimitado de líneas, inicialmente vacía, y con un tamaño de línea capaz de almacenar Lelementos de la matriz a trasponer (1 ≤L∈N). Además, la tasa ideal de aciertos solo tiene en cuenta los fallos obligatorios y no los fallos por capacidad, por conflicto o la secuencia de accesos del algoritmo de transposición. No obstante, el algoritmo 2, que implementa una transposición de matriz directa, es decir, sin transformaciones ni optimizaciones, se puede usar como referencia. 58 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices (a) Simple. (b) Oblivious. (c) Tiling 4 ×4. (d) Tiling 2 ×2. FIGURA 5.1: Orden de acceso a los elementos de una matriz 8×8 para cada uno de los algoritmos estudiados de transposición de matrices. El color solo aporta una guía visual de los recorridos y divisiones por tiles. Algoritmo 2 TransposicionDeMatriz(Matrix,N): Transpone una matriz N×N. 1: for indice1←1to Ndo # N iteraciones 2: for indice2←indice1+1to Ndo # N iteraciones 3: temp ←Matrixindice1,indice2# Lectura de memoria 4: Matrixindice1,indice2←Matrixindice2,indice1# Lectura y escritura de memoria 5: Matrixindice2,indice1←temp # Escritura en memoria 6: end for 7: end for Crear modelos de casos ideales resulta útil para determinar las cotas del mejor escenario de tasa de aciertos dada una determinada configuración de cache, mapeo de elemento a línea o algoritmo. Comenzamos considerando que solo los elementos que se van a transponer en la matriz van a ser tenidos en cuenta para los fallos en cache, por lo tanto se excluyen los elementos de la diagonal y como resultado obtenemos una cota superior para cualquier tasa ideal de aciertos. A continuación mostramos también las tasas ideales de aciertos incluyendo los efectos del padding. Consideramos una matriz N×Npara transponer, con sus elementos almacenados por filas, alineada con el tamaño de línea de cache. Todos los resultados que se presentan en este capítulo son válidos también para elementos almacenados por columnas pero, por simplicidad, trataremos solo uno de los casos. También asumimos que la matriz final, ya transpuesta, se sobrescribe en la matriz inicial y no se usan otras estructuras de memoria más allá de registros. 5.4. Tasas ideales en cache de datos para la transposición de matrices 59 FIGURA 5.2: Diferentes mapeos de memoria cuando se aplica padding a una matriz N×Ncon líneas de cache que contienen Lelementos: (a)r= (Nm´ od L) = 0, (b)r=1, (c)r=3. 5.4.1. Cota de la tasa ideal de aciertos con una línea de cache que contiene L elementos Teniendo en cuenta las consideraciones anteriores se puede calcular fácilmente una cota superior para la tasa ideal de aciertos. Exceptuando los elementos diagonales, todos los elementos (N2−N) se acceden tanto para ser leídos como para ser escritos en memoria, lo que nos da 2(N2−N)accesos en total. Si asumimos que los N2−Nelementos caben perfectamente en las líneas de cache, tendremos (N2−N)/Lfallos obligatorios. Dividir por Limplica implícitamente que los elementos de la diagonal no comparten su línea de cache con otros elementos. Aunque asumir esto no es realista (complicaría de hecho cualquier acceso indexado), proporciona la siguiente cota superior para la tasa de aciertos ideal: 1−(N2−N)/L 2(N2−N)=1−1 2L(5.1) Sin embargo, para calcular otras tasas ideales de aciertos tendremos que analizar la relación entre el tamaño de la matriz y el tamaño de línea de cache. 5.4.2. Tasa ideal de aciertos en una matriz con su tamaño de fila múltiplo del tamaño de línea de cache (r=0) Suponemos que la matriz N×Na trasponer se almacena en memoria por filas y está alineada con el tamaño de línea de cache, incluyendo los elementos diagonales. También asumimos una línea de cache de datos que contiene Lelementos consecutivos de una misma fila, con Nmúltiplo de L. Usando la notación de módulo r= (Nm´ od L) = 0. Esto corresponde a la figura 5.2(a). El número total de accesos es el mismo que en la ecuación 5.1. El número de fallos obligatorios en este caso es (N/L)N, es decir, el número de líneas de cache necesarias para recorrer una fila por el número de filas. Por lo tanto, la tasa ideal de aciertos es: 1−N2/L 2(N2−N)=1−1 2L−1 2L(N−1). (5.2) 66 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices FIGURA 5.7: Mapeo en memoria de los bloques Bi∈[a−h]que contienen cada uno, T=L=4 elementos a transponer. (T>L). En estos casos, son necesarias d(T/L)/Selíneas adicionales de cache que contengan elementos horizontales a transponer. Dependiendo de la relación entre los parámetros de la cache LRU y el tamaño de la matriz, la tasa ideal de aciertos se puede lograr con un número de vías ligeramente distinto. Por ejemplo, las matrices cuya dimensión (N) no es múltiplo de 2 necesitan una vía menos. De todos modos, la asociatividad necesaria para alcanzar la tasa ideal de aciertos para cualquier Sestá acotada por: W=T S+T/L S+1, con T>L. (5.10) 5.6.3. Cota en W para alcanzar la tasa ideal de aciertos con T<L Es bastante poco práctico suponer que usamos una dimensión de tile cuyo número de elementos Tes menor que la capacidad de una línea de cache Lya que esto implica que al procesar un tile de T×Telementos traemos a cache más contenido que el estrictamente necesario. Por lo tanto, para alcanzar la tasa ideal de aciertos este contenido que no se usa no puede ser expulsado hasta que se haya realmente usado. En otras palabras, se necesita una cache lo suficientemente grande para evitar fallos por capacidad. Concretamente, el número de líneas de cache (S×W) tiene que ser mayor que el doble del número de columnas de la matriz (2N). Con este tamaño de tile tan inapropiado, el número de vías necesarias para alcanzar la tasa ideal de aciertos depende del tamaño de la matriz, acotándose de la siguiente manera: W=2N S+1, con T<L. (5.11) 5.7. Experimentos En esta sección validamos las expresiones analíticas que hemos obtenido previamente por medio de simulaciones extensivas. Calculamos la tasa de aciertos en 5.7. Experimentos 67 TABLA 5.1: Evolución del contenido de una pila LRU durante la transposición de un tile en una cache con L=T=4 y S=1. La captura de cada pila LRU se toma después de la ejecución de las instrucciones de lectura (ld) o escritura (st) que acceden a los Efila,columna elementos, y nos muestra la secuencia ordenada de todas las líneas de cache Biaccedidas previamente. Secuencia de accesos a memoria de las instrucciones de lectura (ld) y escritura (st) 1 2 3 4 5 6 7 8 9 ld Ei,jld Ej,ist Ei,jst Ej,ild Ei,j+1ld Ej+1,ist Ei,j+1st Ej+1,ild Ei,j+2 MRU BaBeBaBeBaBfBaBfBa 1BaBeBaBeBaBfBaBf 2BeBeBeBe 3 4 LRU 10 11 12 13 14 15 16 17 18 ld Ej+2,ist Ei,j+2st Ej+2,ild Ei,j+3ld Ej+3,ist Ei,j+3st Ej+3,ild Ei+1,jld Ej,i+1 MRU BgBaBgBaBhBaBhBbBe 1BaBgBaBgBaBhBaBhBb 2BfBfBfBfBgBgBgBaBh 3BeBeBeBeBfBfBfBgBa 4BeBeBeBfBg LRU BeBf 19 20 21 22 23 24 25 26 27 st Ei+1,jst Ej,i+1ld Ei+1,j+1ld Ej+1,i+1st Ei+1,j+1st Ej+1,i+1ld Ei+1,j+2ld Ej+2,i+1st Ei+1,j+2 MRU BbBeBbBfBbBfBbBgBb 1BeBbBeBbBfBbBfBbBg 2BhBhBhBeBeBeBeBfBf 3BaBaBaBhBhBhBhBeBe 4BgBgBgBaBaBaBaBhBh LRU BfBfBfBgBgBgBgBaBa 28 29 30 31 32 33 st Ej+2,i+1ld Ei+1,j+3ld Ej+3,i+1st Ei+1,j+3st Ej+3,i+1ld Ei+2,j MRU BgBbBhBbBhBc 1BbBgBbBhBbBh 2BfBfBgBgBgBb 3BeBeBfBfBfBg 4BhBhBeBeBeBf LRU BaBaBaBaBaBe evicted Ba datos en configuraciones de cache diferentes para un amplio tamaño de matrices. Además, los resultados obtenidos se comparan con aquellos proporcionados por el algoritmo cache-oblivious demostrando que si el tamaño del tile T×Tse establece como igual al tamaño de la línea de cache (T=L), el algoritmo tiling siempre va a tener un rendimiento (en términos de tasa de aciertos en datos) mejor o igual que el de cache-oblivious. También, llevamos a cabo múltiples experimentos en hardware real para estudiar los tiempos de ejecución (y no solo las tasas de aciertos en cache de datos). Para finalizar esta sección, utilizamos los resultados obtenidos para conseguir un modelo del consumo de energía de la jerarquía de cache para cada uno de los sistemas estudiados. Esto nos permite evaluar el gasto energético debido al comportamiento de la actividad de reemplazo en la jerarquía de memoria. 68 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices 5.7.1. Tasa de aciertos en cache de datos en el algoritmo tiling de transposición de matrices En esta sección verificamos si la tasa ideal de aciertos (sección 5.4) se puede alcanzar para el algoritmo tiling de transposición de matrices. Para ello, suponemos una cache de datos LRU y que a la matriz a trasponer se le ha aplicado la técnica de padding tal y como se describe en la sección 5.6. La figura 5.8 muestra varias gráficas que corresponden a diferentes tamaños de línea de cache L(en número de elementos). Todas ellas muestran un boxplot por cada combinación de número de conjuntos (S), vías (W) y tamaños de tile (T). Cada boxplot se prolonga verticalmente y representa la tasa de aciertos en datos para matrices de tamaño desde 1024 ×1024 hasta 2048 ×2048 elementos, es decir, 1025 experimentos. En la mayoría de los casos solo aparece la mediana de los datos, como una línea horizontal, debido a que todas las tasas de aciertos de todas las matrices representadas son iguales o sus diferencias son inapreciables. La línea horizontal y punteada representa la asíntota de la tasa de aciertos 1 −1 2L(ecuación 5.1). El color del boxplot indica si se ha alcanzado la tasa ideal de aciertos (sección 5.4) (azul), o si no (rojo). Como podemos ver, la tasa ideal de aciertos se logra cuando el eje x(T) coincide con el tamaño de línea en las columnas (T=L), dependiendo del número de conjuntos S(ecuaciones 5.7–5.9). Cuando se alcanzan resultados ideales con un tamaño de tile subóptimo (T>L, ecuación 5.10), con los mismos parámetros, un tamaño óptimo de tile (T=L) también lo logra. Además las propiedades de la política LRU garantizan que cuando la tasa ideal de aciertos se alcanza con cierta configuración de cache, se sigue alcanzando al aumentar el número de conjuntos y/o vías de esta configuración. Encontramos que la tasa ideal de aciertos puede no alcanzarse solo si la cache es demasiado pequeña o si sus parámetros no están correctamente ajustados. Afortunadamente, estos casos no son realistas, y la caches de datos actuales son mucho más grandes que las representadas en la figura 5.8. De hecho, la cache más grande que hemos probado (W=4, S=16) con tamaño de línea de 64 bytes tiene un tamaño de solo 4 KiB. 5.7.2. Tasa de aciertos en datos: Tiling vs. Oblivious Los resultados anteriores nos muestran que, con el tamaño apropiado de tile, la tasa ideal de aciertos se logra con caches muy pequeñas. En vez de un algoritmo tiling, se podría usar un algoritmo cache-oblivious [Fri+99;Fri+12]. En esta sección evaluamos los requisitos de la cache de datos para lograr la tasa ideal de aciertos con un algoritmo cache-oblivious, tras lo cual lo compararemos con nuestros resultados con tiling. Un algoritmo cache-oblivious se puede ver como un algoritmo tiling en el cual la matriz a procesar se divide recursivamente hasta llegar, en la transposición de matrices, a un tamaño de tile de 2 ×2 elementos. Por lo tanto, es probable que el procesado de cada tile pueda caber en cache. El orden en el que se lleva a cabo la transposición viene dado por la recursión. Este orden es una variación de Z-order el cual conserva la localidad [Mor66] (ver figura 5.1(b)). Así, no es necesario conocer la configuración de cache para aplicar este algoritmo. Sin embargo, su rendimiento depende de los parámetros de cache y predecir cuando será bueno o malo no es trivial [TRS04]. Debido a que el algoritmo oblivious divide recursivamente la matriz a transponer surgen problemas cuando la dimensión de esta matriz (N) no es potencia de 2. Podemos ver este efecto en la figura 5.9 donde solo alcanzan la tasa ideal de aciertos aquellas matrices cuya dimensión es potencia de dos. Proponemos aplicar un phantom padding («Relleno fantasma») que permite resolver este inconveniente. 5.7. Experimentos 69 S=1 S=2 S=4 S=8 S=16 W=2 W=3 W=4 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 T (elementos) Tasa de aciertos ( %) (a) L=2. S=1 S=2 S=4 S=8 S=16 W=2 W=3 W=4 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 T (elementos) Tasa de aciertos ( %) (b) L=4. S=1 S=2 S=4 S=8 S=16 W=2 W=3 W=4 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 T (elementos) Tasa de aciertos ( %) (c) L=8. S=1 S=2 S=4 S=8 S=16 W=2 W=3 W=4 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 T (elementos) Tasa de aciertos ( %) (d) L=16. FIGURA 5.8: Las gráficas (a–d) muestran las tasas de aciertos en datos variando el número de elementos por línea (L=2,4,8,16 elementos) para diferentes configuraciones de cache con Sconjuntos, Wvías, y tamaño de tile T×Telementos. Cada boxplot reúne los resultados de todas las matrices de 1024×1024 a 2048 ×2048 elementos. El color de cada boxplot muestra si se alcanza siempre la tasa ideal de aciertos (azul) o no (rojo). Su aplicación no modifica el mapeo en memoria de la matriz a transponer pero fuerza al algoritmo oblivious a trabajar como si la dimensión de la matriz fuera potencia de 2. A continuación, solo se intercambian los elementos que son reales, en otras palabras, el intercambio de elementos no se da en los elementos «fantasma» que se añaden debido a la aplicación de este padding. Esta transformación tampoco afecta al número de accesos a datos, simplemente se asegura que la secuencia de accesos en el algoritmo oblivious sea regular. Hasta donde sabemos esta técnica de padding es una propuesta original de este trabajo. Los algoritmos 4y5muestran los algoritmos de transposición de matrices cacheoblivious basados en la propuesta original [Fri+99;Fri+12]. Básicamente, estos algoritmos asumen que el parámetro Nes potencia de 2 y la matriz que realmente se 70 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices 0.86 0.90 0.94 4 8 16 32 64 128 256 512 1024 2048 4096 8192 Dimensión de la matriz (elementos) Tasa de aciertos en datos Phantom padding no si FIGURA 5.9: Tasas de aciertos en cache de datos con y sin phantom padding (algoritmos 4y5) para la transposición de matrices cacheoblivious. La configuración de la cache de datos es: L=16,S=16 y W=2. Los tamaños de matriz varían de 4 ×4 a 8192 ×8192 elementos. La tasa ideal de aciertos en datos (ecuaciones 5.2–5.4) coincide con la versión phantom padding. La línea punteada negra muestra la cota superior de tasa de aciertos de la ecuación 5.1. debe transponer se especifica a través de los parámetros de índice. De esta manera, solo se lleva a cabo el intercambio de elementos cuando el índice correspondiente es menor que N. Podemos encontrar esta condición que hemos introducido en la línea 6 en el algoritmo 4y en la línea 8 en el algoritmo 5. Algoritmo 4 Transpuesta(MatrizConPadding,N,indice1=1, indice2=N): transpone recursivamente una matriz con phantom padding, almacenada por filas. 1: if indice2−indice1≤2then 2: MatrizConPaddingindice1,indice1+1↔MatrizConPaddingindice1+1,indice1 3: else 4: indicemitad ←(indice1+indice2)/2; 5: Transpuesta(MatrizConPadding,N,indice1, indicemitad); 6: if indicemitad <Nthen 7: Transpuesta(MatrizConPadding,N,indicemitad,indice2); 8: TranspuestaIntercambio(MatrizConPadding,N,indicemitad,indice1,indice2,indicemitad); 9: end if 10: end if 5.7. Experimentos 71 Algoritmo 5 TranspuestaIntercambio(MatrizConPadding,N,rs,cs,re,ce). 1: if ((re −rs)≤2and (ce −cs)≤2)then 2: for indice1←rs to re −1do 3: for indice2←cs to ce −1do 4: MatrizConPaddingindice1,indice2↔MatrizConPaddingindice2,indice1 5: end for 6: end for 7: else 8: if rs <Nthen 9: rmitad ←(rs +re)/2; 10: cmitad ←(cs +ce)/2; 11: TranspuestaIntercambio(MatrizConPadding,N,rs,cs,rmitad,cmitad); 12: TranspuestaIntercambio(MatrizConPadding,N,rmitad,cs,re,cmitad); 13: TranspuestaIntercambio(MatrizConPadding,N,rs,cmitad,rmitad,ce); 14: TranspuestaIntercambio(MatrizConPadding,N,rmitad,cmitad,re,ce); 15: end if 16: end if A continuación, repetimos los experimentos de la sección 5.7.1 para este algoritmo oblivious mejorado. La figura 5.10 recapitula nuestros resultados para tiling (figura 5.8), y los correspondientes a oblivious. Esta gráfica muestra el mínimo número de vías de cache Wnecesarias para lograr la tasa ideal de aciertos para cada combinación de tamaño de línea de cache Ly número de conjuntos de cache S, es decir, cuanto más pequeña mejor. Encontramos los resultados de tiling a la izquierda y los de oblivious a la derecha. Solo se muestran tamaños adecuados de tile. Las configuraciones inadecuadas de tiling (T6=L) tienen peores resultados y no aparecen en esta gráfica. La barras verdes señalan el mínimo número de conjuntos necesarios para alcanzar la tasa ideal de aciertos. Se puede ver que, con un número suficiente de conjuntos (S≥L), oblivious necesita el mismo número de vías en cache que tiling. Sin embargo, en caches con un menor número de conjuntos (incluidas las totalmente asociativas) oblivious necesita más vías que tiling para lograr la tasa ideal de aciertos. Esto se debe a que oblivious no se detiene cuando la recursión alcanza el tamaño de tile más apropiado sino que continúa reduciendolo hasta llegar a tiles de tamaño 2×2 elementos. Así, cuanto mayor es el tamaño de línea, más contenido innecesario se trae de memoria. Este contenido (que se necesitará para los tiles posteriores) debe mantenerse en cache para poder garantizar la tasa ideal de aciertos en datos. De modo que si fijamos el número de conjuntos, será necesario incrementar el número de vías. Las caches de datos tienen habitualmente un número relativamente grande de conjuntos(S≥L), así que en general en la transposición de matrices, tanto tiling como cache-oblivious, se alcanza la tasa ideal de aciertos. Aun así hay que tener en cuenta que las caches en los procesadores actuales pueden ser compartidas por diferentes hilos hardware al mismo tiempo, de modo que sigue siendo importante acceder a ellas de la manera más eficiente posible. Los resultados anteriores muestran que tiling alcanza la tasa ideal de aciertos con menos recursos que oblivious. Además es importante señalar que los códigos recursivos, como el del algoritmo oblivious, suelen ser más lentos que los iterativos debido al sobrecoste de las llamadas a funciones y del procesamiento de la pila. También hay que tener en cuenta que para sistemas de tiempo real, con un algoritmo recursivo, tendríamos que proporcionar como información en el análisis el máximo nivel de recursión y comprobar que no 72 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices 42 2 2 2 632 2 2 10 532 2 18 9532 42 2 2 2 842 2 2 16 742 2 32 15 742 Tiling (T=L) Oblivious L=2 L=4 L=8 L=16 1 2 4 8 16 1 2 4 8 16 2 8 32 2 8 32 2 8 32 2 8 32 Conjuntos Mín. núm. de vías para la tasa ideal de aciertos en datos FIGURA 5.10: Mínimo número de vías (W) necesarias para alcanzar la tasa ideal de aciertos, según el número de conjuntos Sy tamaño de línea Lde la cache, para la transposición de matrices con el algoritmo tiling con tamaño de tiles T×T(T=L) y para el algoritmo oblivious con phantom padding (cuánto más pequeño mejor). aparecen problemas en la pila debido a ello. 5.7.3. PLRU y tiempo de ejecución en plataformas reales Los resultados anteriores cuentan con una cache asociativa por conjuntos LRU. Debido a que cuesta bastante construir una política LRU que sea eficiente para una gran cache, la mayoría de caches en los procesadores comerciales usan una política PLRU la cual ofrece un comportamiento parecido pero es más simple de implementar [AR13]. En esta sección primero comparamos la tasa de aciertos en datos LRU con la de PLRU por medio de simulaciones. La figura 5.11 muestra las tasas de aciertos en datos para la transposición de matrices de 4096 ×4096 elementos de 8 B con una configuración común de cache de datos L1 (64 conjuntos, 8 vías, y 64 bytes por línea, siendo su tamaño total de 32 KiB). Con este tamaño de línea, cada una contiene 8 elementos de la matriz. Los experimentos varían la dimensión del tile de T=2 a T=512. El área sombreada muestra los tamaños de tile que alcanzan la tasa ideal de aciertos en datos con LRU para tiles cuya dimensión (T) es múltiplo del tamaño de línea (L=8). Esto se puede ver claramente entre 8 y 16 de tamaño de tile donde decrece la tasa de aciertos. El tile 8 ×8 corresponde a T=L(tasa ideal de aciertos con los mínimos recursos de cache). Al incrementar el tamaño del tile a partir de 8×8 hasta 256 ×256 elementos se alcanza la tasa ideal de aciertos pero utilizando más conjuntos/vías (ecuación 5.10). Se puede ver que tanto LRU como PLRU tienen prácticamente las mismas tasas de acierto. Tal como se espera la tasa de aciertos disminuye fuera del área sombreada tanto en LRU como en PLRU. Las únicas diferencias que se pueden apreciar realmente, aunque mínimas, se encuentran en torno aT=256, es decir, la cota de la ecuación 5.10. Gracias a las conclusiones obtenidas en las secciones previas de este capítulo podemos garantizar la predictibilidad en LRU, tan importante en ciertas áreas como en la que se desarrolla nuestro trabajo, los sistemas de tiempo real. Sin embargo, no puede garantizarse para PLRU que se deberá evitar en estos sistemas, como ya han 5.7. Experimentos 73 0.75 0.80 0.85 0.90 2 4 8 16 32 64 128 256 512 Dimensión del tile Tasa de aciertos en datos LRU PLRU FIGURA 5.11: Tasa de aciertos en datos para la transposición de matrices de 4096 ×4096 elementos (cuanto mayor, mejor) para política de reemplazo LRU y PLRU en una configuración de cache de datos L1 común (64 conjuntos, 8 vías, y 64 bytes por línea, con un tamaño total de 32 KiB). La línea negra punteada muestra la cota superior de tasa de aciertos de la ecuación 5.1. indicado otros estudios [Ber06;Rei+07;AR14]. Aunque el factor más determinante para el rendimiento en estas simulaciones sea probablemente la tasa de aciertos en datos, hay también otros elementos importantes que pueden afectar a este rendimiento como el número de instrucciones ejecutadas (dependiente del tamaño del tile). Para poder tener en cuenta estos y otros factores (p. ej. prebuscadores hardware de datos) medimos los tiempos de ejecución. Estos experimentos se han llevado a cabo en varias máquinas: Intel-Xeon-L5410 2.33 GHz, Intel-i7-4810MQ 2.80 GHz, Intel-Core-2-Quad-Q9550 2.83 GHz,y Intel-i7-2640M 2.80 GHz. Todas ellas tienen una cache L1 de instrucciones y otra de datos, ambas con reemplazo PLRU, 64 conjuntos, 8 vías, y 64 bytes por línea, con un tamaño total de 32 KiB, tal como la que simulamos en la figura 5.11. Se ha codificado el algoritmo 3en C (código fuente disponible online1) y, para cada máquina, se ha generado un binario distinto usando el compilador disponible (GCC-4.7.0 for i7-4810M and Core-2-Quad-Q9550, Intel C++ Composer XE 2013 for Xeon-L5410, y GCC-4.9.2 for i7-2640), pero siempre con optimización de nivel 3. La figura 5.12 muestra el menor tiempo de ejecución para la transposición de matrices de 4096×4096 elementos, variando el número de elementos por tile. Cada uno de los tiempos representados es el menor de 400 repeticiones, representando la ejecución más rápida, es decir la que estaría más cerca de una transposición de matrices aislada de interferencias externas. El área sombreada indica las configuraciones de tile que alcanzan la tasa ideal de aciertos con una cache LRU para tiles múltiplos del tamaño de línea, como antes. El tiempo debería incrementarse para LRU fuera del área sombreada y de hecho se puede ver que este es el comportamiento que presenta PLRU en la gráfica en la plataforma 2QuadQ9550. Sin embargo, en las otras tres plataformas el tiempo de ejecución crece para grandes tiles aunque muy ligeramente. Esto se debe al prebuscador en datos, el cual reconoce los patrones de acceso a 1webdiis.unizar.es/gaz/repositories/tiling-matrix-transposition 74 Capítulo 5. Tasa ideal de aciertos para la transposición de matrices 0.05 0.10 2 4 8 16 32 64 128 256 512 Dimensión del tile Tiempo de ejecución (s) 2QuadQ9550 i7-2640M i7-4810MQ XeonL5410 FIGURA 5.12: Tiempos de ejecución para la transposición de matrices de 4096 ×4096 elementos. Además de los tamaños de tile en el eje-x, se puede ver los tiempos de ejecución para otros valores de T: 6, 10, 12, 14, 20, 24, 28, 40, 48, 56, 96, 192, y 384. datos y evita las penalizaciones en tiempo. En el área de la izquierda los tiles son demasiado pequeños para que el prebuscador reconozca ningún patrón de acceso, por ello el tiempo de ejecución para estos tiles es bastante mayor. Los tamaños que son múltiplos de 8 trabajan con líneas completas de cache y por lo tanto, en general, obtiene un rendimiento mejor que aquellos a su alrededor. Se puede ver claramente que entre 8 y 16 todas las gráficas muestran un incremento del tiempo de ejecución. Por último, cuanto mayor es el tamaño del tile, menos instrucciones se ejecutan. Para cada tile, se tienen que calcular las cotas de sus índices y también asegurar que en los tiles de los extremos de la matriz no se intercambian datos de fuera de ella. Esto es, cuanto menores son los tamaños de tile dentro del área sombreada más eficiente es el uso que hacen de la cache, pero tienen más instrucciones. Por tanto, se produce una compensación entre los recursos de cache y las instrucciones ejecutadas y la tendencia en cuanto al tiempo de ejecución diferirá dependiendo de la máquina en la que se ejecute la transposición. 5.7.4. Modelado y reducción del consumo de energía en el subsistema de memoria para la transposición de matriz versión tiling En esta sección analizamos el consumo de energía en los subsistemas de memoria de las cuatro plataformas de la sección 5.7.3. Para poder hacerlo usamos la tasa analítica de aciertos introducida en la sección 5.6 y la combinamos con las gráficas de energía obtenidas por la herramienta de modelización CACTI 7.0 [Bal+17]. Esta herramienta permite calcular la energía por acceso y la energía estática dada un configuración de cache o de memoria principal. Primero, describimos los subsistemas de memoria de las cuatro plataformas, presentamos las gráficas de potencia y energía de cada componente y explicamos cómo calcular la energía global. Después, nos centramos en un tamaño específico de matriz tomando varios tamaños de tile con lo que obtenemos el consumo de energía global y tras lo cual sugerimos mejoras en el software/hardware. 5.7. Experimentos 75 (a) 2 niveles: QuadQ9550 y XeonL5410. (b) 3 niveles: i7-2640 y i7-4810. FIGURA 5.13: Organización de las jerarquías de memoria. Modelado analítico de consumo de energía La figura 5.13 muestra las dos jerarquías que encontramos en las cuatro plataformas de nuestra experimentación. Xeon-L5410 y 2QuadQ9550 tienen dos niveles de cache, y i7-2640M y i7-4810MQ tienen tres. El último nivel de cache, el más cercano a la memoria principal, está compartido entre los núcleos (solo se muestra uno en la figura 5.13), mientras que los niveles más bajos son privados para cada uno de ellos. Todas las caches de datos son caches copy-back, lo que quiere decir que el efecto de una sola escritura no se ve en niveles superiores hasta que no se expulsa por completo la línea modificada. Las operaciones de lectura y escritura que se ejecutan en el núcleo acceden primero a la cache L1. Cuando se da un fallo, se busca en el siguiente nivel de cache hasta que se produce un acierto o se llega a memoria principal. Un fallo en el último nivel trae la línea de memoria principal al menos a cache L1 y, dependiendo de la política de control de contenido entre niveles, también a las caches L2 y L3. Por simplicidad, ya que las cuatro plataformas tienen diferentes políticas, asumimos que todas tienen una política inclusiva en la cual se ordena que se copien las líneas que vengan de memoria principal a todos los niveles de cache, es decir, L1 ⊂L2 ⊂L3. La tabla 5.2 muestra los parámetros de cache y tecnológicos para todas las plataformas. Las gráficas de energía y potencia han sido calculadas por CACTI, considerando la tecnología del nodo, el nivel de memoria, y los diferentes tamaños y asociatividades. Solo se muestra la energía para leer/escribir un elemento de 8 bytes en las caches L1, cuando las instrucciones de lectura y escritura operan a esta granularidad, mientras que la energía para leer/escribir objetos de 64 bytes permiten considerar las transferencias de líneas entre todos los niveles de memoria. Elegimos una memoria principal de 1 GiB porque es lo suficientemente grande para almacenar 128 MiB, el tamaño de la matriz de 4096 ×4096 elementos de 8 bytes que se usa en la figura 5.12 y en la siguiente sección. Ahora podemos usar el modelo de la tasa de aciertos de la sección 5.6 para contar todos los eventos de interés en cualquier nivel de la jerarquía inclusiva expuesta arriba: escrituras, lecturas, aciertos y reemplazos. Entonces podemos calcular la energía dinámica total multiplicando el número de 82 Capítulo 6. Conclusiones Completamos este estudio analizando el impacto de los niveles de optimización en el WCET y concluyendo que es conveniente descartar las compilaciones sin optimización (-O0) ya que el WCET de los binarios generados resulta entre 3 y 4 veces peor que con la presencia de optimizaciones. Sin embargo, hay que evitar optimizaciones demasiado agresivas que puedan cambiar los patrones de bucle dificultando, y empeorando, el análisis del WCET. El trabajo desarrollado en este capítulo se ha presentado en A. Pedro-Zapater, J. Segarra, C. Rodríguez, R.G. Tejero y V. Viñals-Yúfera (2016) «Obtención del WCET óptimo en caches de instrucciones bloqueables (Lock-MS) en Otawa» V Simposio de sistemas de tiempo real, 13-16 Septiembre 2016, Salamanca. y se ha publicado en A. Pedro-Zapater, J. Segarra, C. Rodríguez, R.G. Tejero y V. Viñals-Yúfera (2020) «Reducing the WCET and analysis time of systems with simple lockable instruction caches» PLOS ONE 15(3): e022998. En el capítulo 4ampliamos el estudio a aquellos programas con código vectorizado analizando su impacto en el WCET. Para ello se estudian las vectorizaciones automáticas generadas por GCC en paquetes de benchmarks de tiempo real, integrando sus especificaciones temporales en la herramienta de análisis del WCET. Si los bucles vectorizados forman parte del código donde se concentra la mayor parte del tiempo de ejecución, nuestros resultados confirman que el WCET se reduce de manera significativa (obteniendo hasta una reducción por un factor de 3 del WCET en alguno de los benchmarks). Sin embargo, en los benchmarks en los que no se da esta situación no hay tanto margen de mejora. Esto se debe en parte a las propias limitaciones de la vectorización automática, y también de la propia programación de los benchmarks. Por tanto, para obtener mejores resultados es necesario o bien reescribir el código facilitando el trabajo de vectorización del compilador o bien escribir código vectorial explícito. En cualquiera de los dos casos la eficiencia de la vectorización queda en manos de quien programa. Otra conclusión que recogemos en este capítulo es que debe evitarse la vectorización si el número de iteraciones de los bucles vectorizados no es lo suficientemente grande para compensar el sobrecoste de utilizar código vectorial. Este sobrecoste se debe al código generado para seleccionar el modo escalar o vectorial, a las instrucciones adicionales que preparan el bucle o a los fallos adicionales en cache de instrucciones por las instrucciones vectoriales. En resumen, estos resultados junto con el hecho de que el procesamiento vectorial está convirtiéndose en una utilidad básica en la mayoría de los procesadores del mercado alientan a usar los recursos vectoriales en sistemas de tiempo real estricto teniendo en cuenta las cuestiones planteadas como un punto de partida para un estudio más extenso. En el capítulo 5abordamos el análisis del WCET en presencia de cache de datos a través del análisis de patrones de accesos de la operación de transposición de matrices, una operación básica en sistemas de tiempo real. Determinar de forma precisa y, si es posible, reducir el número de accesos y aumentar la tasa de aciertos conlleva un impacto directo en el cálculo del WCET. En este capítulo obtenemos las expresiones analíticas que permiten determinar el comportamiento ideal de la cache de datos (fallos obligatorios) para la transposición de matrices y cuál será la configuración óptima para una cache de datos LRU en la versión tiling del algoritmo. Tras ello, validamos las expresiones anteriores y las comparamos con la versión cache-oblivious del algoritmo por medio de simulaciones. En esta comparación observamos que, con el tamaño adecuado de tile, la versión tiling del algoritmo obtiene una tasa de aciertos en datos igual o mejor. Finalmente, ofrecemos resultados experimentales en hardware real y una comparación con PLRU. Capítulo 6. Conclusiones 83 Nuestra principal aportación, la cual era objeto de este estudio, es proporcionar resultados que permiten determinar de forma sencilla los aciertos y fallos de la versión tiling de la transposición de matrices (imprescindible para aplicaciones de tiempo real) en una cache LRU de datos y, bajo determinadas configuraciones de cache, en una cache PLRU. Adicionalmente a estos resultados podemos concluir que no van a ser necesarias más de dos vías en la cache de datos y unos pocos conjuntos para lograr la tasa de aciertos ideal y por tanto las vías que no se usen en una cache de datos asociativa por conjuntos pueden desconectarse sin ningún impacto negativo proporcionando un ahorro de energía (desde un 3% a un 46% en nuestros experimentos, dependiendo de la plataforma). Además, pueden reservarse en exclusiva dos vías en las caches de los últimos niveles para la transposición de matrices, evitando la contaminación de otros procesos. El trabajo desarrollado en este capítulo se ha presentado en A. Pedro-Zapater, C. Rodríguez, J. Segarra, R.G. Tejero y V. Viñals-Yúfera (2019), «Tasa de aciertos ideal y predecible para la transposición de matrices en caches de datos», XXX Jornadas de Paralelismo (JP2019), 18-20 Septiembre 2019, Cáceres. y se ha publicado en A. Pedro-Zapater, C. Rodríguez, J. Segarra, R.G. Tejero y V. Viñals-Yúfera (2020), «Ideal and Predictable Hit Ratio for Matrix Transposition in Data Caches», Mathematics., February, 2020. Vol. 8(2), pp. 184. MDPI AG. 85 Bibliografía [ALE02] Todd M. Austin, Eric Larson y Dan Ernst. «SimpleScalar: An Infrastructure for Computer System Modeling». En: IEEE Computer 35.2 (2002), págs. 59-67. DOI:10.1109/2.982917. [AP] Alexis Arnaud e Isabelle Puaut. «Dynamic instruction cache locking in hard real-time systems». En: In RTNS. [Apa+08] Luis C. Aparicio, Juan Segarra, Clemente Rodríguez, J. L. Villarroel y Víctor Viñals. «Avoiding the WCET Overestimation on LRU Instruction Cache». En: The Fourteenth IEEE Internationl Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008, Kaohisung, Taiwan, 25-27 August 2008, Proceedings. IEEE Computer Society, 2008, págs. 393-398. DOI:10.1109/RTCSA.2008.10. [Apa+10] Luis C. Aparicio, Juan Segarra, Clemente Rodríguez y Víctor Viñals. «Combining Prefetch with Instruction Cache Locking in Multitasking Real-Time Systems». En: 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2010, Macau, SAR, China, 23-25 August 2010. IEEE Computer Society, 2010, págs. 319-328. DOI:10.1109/RTCSA.2010.8. [Apa+11] Luis C. Aparicio, Juan Segarra, Clemente Rodríguez y Víctor Viñals. «Improving the WCET computation in the presence of a lockable instruction cache in multitasking real-time systems». En: J. Syst. Archit. 57.7 (2011), págs. 695-706. DOI:10.1016/j.sysarc.2010.08.008. [AR13] Andreas Abel y Jan Reineke. «Measurement-based modeling of the cache replacement policy». En: 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013. IEEE Computer Society, 2013, págs. 65-74. DOI:10 . 1109 / RTAS.2013.6531080. [AR14] Andreas Abel y Jan Reineke. «Reverse engineering of cache replacement policies in Intel microprocessors and their evaluation». En: 2014 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2014, Monterey, CA, USA, March 23-25, 2014. IEEE Computer Society, 2014, págs. 141-142. DOI:10.1109/ISPASS.2014.6844475. [ARM] GNU ARM. GNU ARM Embedded Toolchain Version 6-2017-q2-update.URL: developer.arm.com/open-source/gnu-toolchain/gnu-rm/downloads (visitado 04-05-2020). [ARS13] Luis Carlos Aparicio Cardiel, Clemente Rodríguez Lafuente y Juan Segarra Flor. «» En: (2013). Presentado: 21 02 2013. [AU14] Pavel G. Zaykov Arthur Pyka Mathias Rohde y Sascha Uhrig. «Case Study: On-Demand Coherent Cache for Avionic Applications». En: 2nd Workshop on High-performance and Real-time Embedded Systems. 2014. 86 Bibliografía [Bac+94] David F. Bacon, Jyh-Herng Chow, Dz-ching Ju, Kalyan Muthukumar y Vivek Sarkar. «A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness». En: Proceedings of the 1994 Conference of the Centre for Advanced Studies on Collaborative Research, October 31 - November 3, 1994, Toronto, Ontario, Canada. Ed. por John E. Botsford, Ann Gawman, W. Morven Gentleman, Evelyn Kidd, Kelly A. Lyons, Jacob Slonim y J. Howard Johnson. IBM, 1994, pág. 3. URL: dl.acm.org/citation.cfm?id=782188. [Bal+10] Clément Ballabriga, Hugues Cassé, Christine Rochange y Pascal Sainrat. «OTAWA: An Open Toolbox for Adaptive WCET Analysis». En: Software Technologies for Embedded and Ubiquitous Systems - 8th IFIP WG 10.2 International Workshop, SEUS 2010, Waidhofen/Ybbs, Austria, October 13-15, 2010. Proceedings. Ed. por Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner y Theo Ungerer. Vol. 6399. Lecture Notes in Computer Science. Springer, 2010, págs. 35-46. DOI:10.1007/978-3-642-162565\_6. [Bal+16] Sanford Ballard, James Hipp, Brian Kraus, Andre Encarnacao y Christopher Young. «GeoTess: A Generalized Earth Model Software Utility». En: Seismological Research Letters 87 (mayo de 2016), págs. 719-725. DOI: 10.1785/0220150222. [Bal+17] Rajeev Balasubramonian, Andrew B. Kahng, Naveen Muralimanohar, Ali Shafiee y Vaishnav Srinivas. «CACTI 7: New Tools for Interconnect Exploration in Innovative Off-Chip Memories». En: TACO 14.2 (2017), 14:1-14:25. DOI:10.1145/3085572. [Bao+18] Wenlei Bao, Sriram Krishnamoorthy, Louis-Noël Pouchet y P. Sadayappan. «Analytical modeling of cache behavior for affine programs». En: PACMPL 2.POPL (2018), 32:1-32:26. DOI:10.1145/3158120. [BC11] Shekhar Borkar y Andrew A. Chien. «The future of microprocessors». En: Commun. ACM 54.5 (2011), págs. 67-77. DOI:10 . 1145 / 1941487 . 1941507. [Ber06] Christoph Berg. «PLRU Cache Domino Effects». En: 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, July 4, 2006, Dresden, Germany. Ed. por Frank Mueller. Vol. 4. OASICS. Internationales Begegnungsund Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006. URL:drops.dagstuhl.de/opus/volltexte/2006/672. [Bin+11] Nathan L. Binkert, Bradford M. Beckmann, Gabriel Black, Steven K. Reinhardt, Ali G. Saidi, Arkaprava Basu, Joel Hestness, Derek Hower, Tushar Krishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib Bin Altaf, Nilay Vaish, Mark D. Hill y David A. Wood. «The gem5 simulator». En: SIGARCH Computer Architecture News 39.2 (2011), págs. 1-7. DOI:10.1145/2024716.2024718. [BMS08] Armelle Bonenfant, Marianne de Michiel y Pascal Sainrat. «oRange: A tool for static loop bound analysis». En: Proceedings of the Workshop on Resource Analysis. 2008. [Cam+03] A. M. Campoy, A. Perles, F. Rodriguez y J. V. Busquets-Mataix. «Static use of locking caches vs. dynamic use of locking caches for real-time Bibliografía 87 systems». En: CCECE 2003 - Canadian Conference on Electrical and Computer Engineering. Toward a Caring and Humane Technology (Cat. No.03CH37436). Vol. 2. 2003, 1283-1286 vol.2. [Cam+05] Antonio Martí Campoy, Eugenio Tamura, S. Sáez, Francisco Rodríguez y José V. Busquets-Mataix. «On Using Locking Caches in Embedded Real-Time Systems». En: Embedded Software and Systems, Second International Conference, ICESS 2005, Xi’an, China, December 16-18, 2005, Proceedings. Ed. por Laurence Tianruo Yang, Xingshe Zhou, Wei Zhao, Zhaohui Wu, Yian Zhu y Man Lin. Vol. 3820. Lecture Notes in Computer Science. Springer, 2005, págs. 150-159. DOI:10.1007/11599555\_17. [Caz+13] Francisco J. Cazorla, Eduardo Quiñones, Tullio Vardanega, Liliana Cucu, Benoit Triquet, Guillem Bernat, Emery D. Berger, Jaume Abella, Franck Wartel, Michael Houston, Luca Santinelli, Leonidas Kosmidis, Code Lo y Dorin Maxim. «PROARTIS: Probabilistically Analyzable Real-Time Systems». En: ACM Trans. Embedded Comput. Syst. 12.2s (2013), 94:1-94:26. DOI:10.1145/2465787.2465796. [CB02] Antoine Colin y Guillem Bernat. «Scope-Tree: A Program Representation for Symbolic Worst-Case Execution Time Analysis». En: 14th Euromicro Conference on Real-Time Systems (ECRTS 2002), 19-21 June 2002, Vienna, Austria, Proceedings. IEEE Computer Society, 2002, pág. 50. DOI: 10.1109/EMRTS.2002.1019185. [CC77] Patrick Cousot y Radhia Cousot. «Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints». En: Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977. Ed. por Robert M. Graham, Michael A. Harrison y Ravi Sethi. ACM, 1977, págs. 238-252. DOI:10.1145/512950.512973. [Che14] Maryline Chetto. Real-time systems scheduling. ISTE Ltd, 2014. [CIM01] Marti Campoy, A. Perles Ivars y J. V. Busquets Mataix. «Static Use of Locking Caches in Multitask Preemptive Real-Time Systems». En: In Proceedings of IEEE/IEE Real-Time Embedded Systems Workshop (Satellite of the IEEE Real-Time Systems Symposium. 2001. [CK07] Jian-Jia Chen y Chin-Fu Kuo. «Energy-Efficient Scheduling for RealTime Systems on Dynamic Voltage Scaling (DVS) Platforms». En: 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), 21-24 August 2007, Daegu, Korea. IEEE Computer Society, 2007, págs. 28-38. DOI:10.1109/RTCSA.2007. 37. [CP00] Antoine Colin e Isabelle Puaut. «Worst Case Execution Time Analysis for a Processor with Branch Prediction». En: Real-Time Systems 18.2/3 (2000), págs. 249-274. DOI:10.1023/A:1008149332687. [CS00] Siddhartha Chatterjee y Sandeep Sen. «Cache-Efficient Matrix Transposition». En: Proceedings of the Sixth International Symposium on HighPerformance Computer Architecture, Toulouse, France, January 8-12, 2000. IEEE Computer Society, 2000, págs. 195-205. DOI:10.1109/HPCA.2000. 824350. 88 Bibliografía [DLM13] Huping Ding, Yun Liang y Tulika Mitra. «Integrated instruction cache analysis and locking in multitasking real-time systems». En: The 50th Annual Design Automation Conference 2013, DAC ’13, Austin, TX, USA, May 29 - June 07, 2013. ACM, 2013, 147:1-147:10. DOI:10.1145/2463209. 2488916. [Fal+16] Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sorensen, Peter Wägemann y Simon Wegener. «TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research». En: 16th International Workshop on Worst-Case Execution Time Analysis, WCET 2016, July 5, 2016, Toulouse, France. Ed. por Martin Schoeberl. Vol. 55. OASICS. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, 2:1-2:10. DOI: 10.4230/OASIcs.WCET.2016.2. [FH04] Christian Ferdinand y Reinhold Heckmann. «aiT: worst case execution time prediction by static program analysis». En: Building the Information Society, IFIP 18th World Computer Congress, Topical Sessions, 22-27 August 2004, Toulouse, France. Ed. por René Jacquart. Vol. 156. IFIP. Kluwer/Springer, 2004, págs. 377-383. DOI:10.1007/978-1-4020-8157-6\_29. [Fla+02] Krisztián Flautner, Nam Sung Kim, Steven M. Martin, David T. Blaauw y Trevor N. Mudge. «Drowsy Caches: Simple Techniques for Reducing Leakage Power». En: 29th International Symposium on Computer Architecture (ISCA 2002), 25-29 May 2002, Anchorage, AK, USA. Ed. por Yale N. Patt, Dirk Grunwald y Kevin Skadron. IEEE Computer Society, 2002, págs. 148-157. DOI:10.1109/ISCA.2002.1003572. [FLS13] B. Fitzgerald, S. Lopez y Julio Sahuquillo. «Drowsy cache partitioning for reduced static and dynamic energy in the cache hierarchy». En: International Green Computing Conference, IGCC 2013, Arlington, VA, USA, June 27-29, 2013, Proceedings. IEEE Computer Society, 2013, págs. 1-6. DOI:10.1109/IGCC.2013.6604475. [Fre12] Inc. Free Software Foundation. GCC, the GNU Compiler Collection. 2012. URL:gcc.gnu.org/ (visitado 20-05-2020). [Fri+12] Matteo Frigo, Charles E. Leiserson, Harald Prokop y Sridhar Ramachandran. «Cache-Oblivious Algorithms». En: ACM Trans. Algorithms 8.1 (2012), 4:1-4:22. DOI:10.1145/2071379.2071383. [Fri+99] Matteo Frigo, Charles E. Leiserson, Harald Prokop y Sridhar Ramachandran. «Cache-Oblivious Algorithms». En: 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA. IEEE Computer Society, 1999, págs. 285-298. DOI:10. 1109/SFFCS.1999.814600. [FW99] Christian Ferdinand y Reinhard Wilhelm. «Efficient and Precise Cache Behavior Prediction for Real-Time Systems». En: Real-Time Systems 17.23 (1999), págs. 131-181. DOI:10.1023/A:1008186323068. [Ger+11] Mike Gerdes, Julian Wolf, Irakli Guliashvili, Theo Ungerer, Michael Houston, Guillem Bernat, Stefan Schnitzler y Hans Regler. «Large drilling machine control code - Parallelisation and WCET speedup». En: Industrial Embedded Systems (SIES), 2011 6th IEEE International Symposium on, SIES 2011. Vasteras, Sweden, June 15-17, 2011. IEEE, 2011, págs. 91-94. DOI:10.1109/SIES.2011.5953688. Bibliografía 89 [Gra+13] Ruben Gran, Juan Segarra, Clemente Rodríguez, Luis C. Aparicio y Víctor Viñals. «Optimizing a combined WCET-WCEC problem in instruction fetching for real-time systems». En: J. Syst. Archit. 59.9 (2013), págs. 667-678. DOI:10.1016/j.sysarc.2013.07.012. [Gra+15] Ruben Gran, Juan Segarra, A. Pedro-Zapater, Luis C. Aparicio, Víctor Viñals y Clemente Rodríguez. «A predictable hardware to exploit temporal reuse in real-time and embedded systems». En: J. Syst. Archit. 61.56 (2015), págs. 227-238. DOI:10.1016/j.sysarc.2015.05.001. [Gus+03] Jan Gustafsson, Björn Lisper, Christer Sandberg y Nerina Bermudo. «A Tool for Automatic Flow Analysis of C-programs for WCET Calculation». En: 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS 2003), 15-17 January 2003, Guadalajara, Mexico. IEEE Computer Society, 2003, págs. 106-112. DOI:10.1109/WORDS. 2003.1218072. [Gus+10] Jan Gustafsson, Adam Betts, Andreas Ermedahl y Björn Lisper. «The Mälardalen WCET Benchmarks – Past, Present and Future». En: WCET2010. Ed. por Björn Lisper. Brussels, Belgium, jul. de 2010, págs. 137-147. DOI: 10.4230/OASIcs.WCET.2010.136. [Gus00] Jan Gustafsson. «Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation». Tesis doct. Department of Computer Engineering, Mälardalen University, Box 883, S-721 23 Västerås, Sweden, y Department of Computer Systems, Information Technology, Uppsala University, Box 325, S-751 05 Uppsala, Sweden, mayo de 2000. URL: http://www.es.mdh.se/publications/231-. [Hea+99] Christopher A. Healy, Robert D. Arnold, Frank Mueller, David B. Whalley y Marion G. Harmon. «Bounding Pipeline and Instruction Cache Performance». En: IEEE Trans. Computers 48.1 (1999), págs. 53-70. DOI: 10.1109/12.743411. [Hon+] Honeywell, BSC, Université Toulouse III - Paul Sabatier y Rapita Systems. MERASA Project.URL:cordis.europa.eu/project/id/216415/ es (visitado 15-06-2020). [Hon+16] Changwan Hong, Wenlei Bao, Albert Cohen, Sriram Krishnamoorthy, Louis-Noël Pouchet, Fabrice Rastello, J. Ramanujam y P. Sadayappan. «Effective padding of multidimensional arrays to avoid cache conflict misses». En: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2016, Santa Barbara, CA, USA, June 13-17, 2016. Ed. por Chandra Krintz y Emery Berger. ACM, 2016, págs. 129-144. DOI:10.1145/2908080.2908123. [HRP17] Damien Hardy, Benjamin Rouxel e Isabelle Puaut. «The Heptane Static Worst-Case Execution Time Estimation Tool». En: 17th International Workshop on Worst-Case Execution Time Analysis, WCET 2017, June 27, 2017, Dubrovnik, Croatia. Ed. por Jan Reineke. Vol. 57. OASICS. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, 8:1-8:12. DOI:10.4230/ OASIcs.WCET.2017.8.URL:https://doi.org/10.4230/OASIcs.WCET. 2017.8. [II] INRIA e I3S. MasCotTE Project.URL:www-sop.inria.fr/teams/mascotte/ (visitado 15-06-2020). 90 Bibliografía [Ins20] Global Market Insights. Embedded Systems Market Size By Component (Hardware, [ASIC & ASSP, Microcontroller, Microprocessor, Power Management Integrated Circuit (PMIC), Field Programmable Gate Array (FPGA), Digital Signal Processor (DSP), Memory], Software (OS, Middleware)], By Function (Standalone System, Real-Time System, Network System, Mobile System), By Application (Automotive, Consumer Electronics, Manufacturing, Retail, Media & Entertainment, Military & Defense, Telecom), Industry Analysis Report, Regional Outlook, Application Potential, Competitive Market Share & Forecast, 2020-2026. 2020. URL:gminsights.com/industry-analysis/ embedded-system-market (visitado 14-09-2020). [IUU] INRIA Siège, Université Toulouse III - Paul Sabatier y Université París VIPierre et Marie Curie. MORE Project.URL:anr.fr/Project-ANR06-ARFU-0002 (visitado 15-06-2020). [JML06] Ramkumar Jayaseelan, Tulika Mitra y Xianfeng Li. «Estimating the WorstCase Energy Consumption of Embedded Software». En: 12th IEEE RealTime and Embedded Technology and Applications Symposium (RTAS 2006), 4-7 April 2006, San Jose, California, USA. IEEE Computer Society, 2006, págs. 81-90. DOI:10.1109/RTAS.2006.17. [Kos+14] Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones y Francisco J. Cazorla. «Efficient Cache Designs for Probabilistically Analysable RealTime Systems». En: IEEE Trans. Computers 63.12 (2014), págs. 2998-3011. DOI:10.1109/TC.2013.182. [Kuc+81] David J. Kuck, Robert H. Kuhn, David A. Padua, Bruce Leasure y Michael Wolfe. «Dependence Graphs and Compiler Optimizations». En: Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, Williamsburg, Virginia, USA, January 1981. Ed. por John White, Richard J. Lipton y Patricia C. Goldberg. ACM Press, 1981, págs. 207-218. DOI:10.1145/567532.567555. [Lei03] Charles E. Leiserson. «Cache-Oblivious Algorithms». En: Algorithms and Complexity, 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings. Ed. por Rossella Petreschi, Giuseppe Persiano y Riccardo Silvestri. Vol. 2653. Lecture Notes in Computer Science. Springer, 2003, pág. 5. DOI:10.1007/3-540-44849-7\_5. [Li+07] Xianfeng Li, Liang Yun, Tulika Mitra y Abhik Roychoudhury. «Chronos: A timing analyzer for embedded software». En: Sci. Comput. Program. 69.1-3 (2007), págs. 56-67. DOI:10.1016/j.scico.2007.01.014. [Lima] ARM Limited. Armv6 reference manual.URL:infocenter . arm . com / help/index.jsp?topic=/com.arm . doc . dui0489e / CJAJIIGG . html (visitado 11-05-2020). [Limb] ARM Limited. Cortex-A8 reference manual.URL:infocenter.arm.com/ help/topic/com.arm.doc.ddi0344k/DDI0344K_cortex_a8_r3p2_trm. pdf (visitado 11-05-2020). [Lim+95] Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-Mook Moon y Chong-Sang Kim. «An Accurate Worst Case Timing Analysis for RISC Processors». En: IEEE Trans. Software Eng. 21.7 (1995), págs. 593-604. DOI:10.1109/32.392980. Bibliografía 91 [Lis14] Björn Lisper. «SWEET - A Tool for WCET Flow Analysis (Extended Abstract)». En: Leveraging Applications of Formal Methods, Verification and Validation. Specialized Techniques and Applications - 6th International Symposium, ISoLA 2014, Imperial, Corfu, Greece, October 8-11, 2014, Proceedings, Part II. Ed. por Tiziana Margaria y Bernhard Steffen. Vol. 8803. Lecture Notes in Computer Science. Springer, 2014, págs. 482-485. DOI:10. 1007/978-3-662-45231-8\_38. [LM95] Yau-Tsun Steven Li y Sharad Malik. «Performance Analysis of Embedded Software Using Implicit Path Enumeration». En: Proceedings of the 32st Conference on Design Automation, San Francisco, California, USA, Moscone Center, June 12-16, 1995. Ed. por Bryan Preas. ACM Press, 1995, págs. 456-461. DOI:10.1145/217474.217570. [LMW96] Yau-Tsun Steven Li, Sharad Malik y Andrew Wolfe. «Cache modeling for real-time software: beyond direct mapped instruction caches». En: Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS ’96), December 4-6, 1996, Washington, DC, USA. IEEE Computer Society, 1996, págs. 254-263. DOI:10.1109/REAL.1996.563722. [LPR14] Hanbing Li, Isabelle Puaut y Erven Rohou. «Traceability of Flow Information: Reconciling Compiler Optimizations and WCET Estimation». En: 22nd International Conference on Real-Time Networks and Systems, RTNS ’14, Versaille, France, October 8-10, 2014. Ed. por Mathieu Jan, Belgacem Ben Hedia, Joël Goossens y Claire Maiza. ACM, 2014, pág. 97. DOI:10. 1145/2659787.2659805. [LPR15] Hanbing Li, Isabelle Puaut y Erven Rohou. «Tracing Flow Information for Tighter WCET Estimation: Application to Vectorization». En: 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2015, Hong Kong, China, August 19-21, 2015. IEEE Computer Society, 2015, págs. 217-226. DOI:10.1109/RTCSA.2015. 18. [LRW91] Monica S. Lam, Edward E. Rothberg y Michael E. Wolf. «The Cache Performance and Optimizations of Blocked Algorithms». En: ASPLOSIV Proceedings - Forth International Conference on Architectural Support for Programming Languages and Operating Systems, Santa Clara, California, USA, April 8-11, 1991. Ed. por David A. Patterson y Bob Rau. ACM Press, 1991, págs. 63-74. DOI:10.1145/106972.106981. [Lun02] Thomas Lundqvist. «A WCET Analysis Method for Pipelined Microprocessors with Cache Memories». Tesis doct. Chalmers University of Technology, Gothenburg, Sweden, 2002. URL:http://publications. lib.chalmers.se/publication/606-a-wcet-analysis-method-forpipelined-microprocessors-with-cache-memories. [Mal+11] Saeed Maleki, Yaoqing Gao, Maríaa Jesús Garzarán, Tommy Wong y David A. Padua. «An Evaluation of Vectorizing Compilers». En: 2011 International Conference on Parallel Architectures and Compilation Techniques, PACT 2011, Galveston, TX, USA, October 10-14, 2011. Ed. por Lawrence Rauchwerger y Vivek Sarkar. IEEE Computer Society, 2011, págs. 372-382. DOI:10.1109/PACT.2011.68. [Mal08] Rajib Mall. Real-time systems: theory and practice. Published by Dorling Kindersley (India), licensees of Pearson Education in South Asia, 2008.