Repositorio Institucional de Documentos

2013 17 Luis Carlos Aparicio Cardiel Jerarquía de memoria para instrucciones y cálculo del WCET Departamento Director/es Informática e Ingeniería de Sistemas Rodríguez Lafuente, Clemente Segarra Flor, Juan Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Luis Carlos Aparicio Cardiel JERARQUÍA DE MEMORIA PARA INSTRUCCIONES Y CÁLCULO DEL WCET Director/es Informática e Ingeniería de Sistemas Rodríguez Lafuente, Clemente Segarra Flor, Juan Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Universidad de Zaragoza Dpto. Inform´atica e Ingenier´ıa de Sistemas Tesis Doctoral Jerarqu´ıa de Memoria para Instrucciones y C´alculo del WCET D. Luis C. Aparicio Cardiel Directores: Dr. Juan Segarra Flor Dr. Clemente Rodr´ıguez Lafuente Zaragoza, Octubre 2012 Jerarqu´ıa de Memoria para Instrucciones y C´alculo del WCET Memoria presentada por D. Luis C. Aparicio Cardiel para obtener el t´ıtulo de Doctor en Inform´atica Dirigida por: Dr. Juan Segarra Flor Dr. Clemente Rodr´ıguez Lafuente Universidad de Zaragoza Dpto. Inform´atica e Ingenier´ıa de Sistemas Zaragoza, Octubre 2012 Resumen Uno de los principales retos de los sistemas de tiempo real es el c´alculo del tiempo de ejecuci´on del peor caso (WCET/ Worst Case Execution Time), es decir, determinar el tiempo de ejecuci´on del camino m´as largo. El c´alculo del WCET tiene que ser seguro y tambi´en preciso, ya que la planificabilidad del sistema debe estar garantizada antes de su ejecuci´on. El mercado de los sistemas de tiempo real a˜nade una restricci´on importante en el dise˜no de la jerarqu´ıa de memoria, la necesidad de conocer un l´ımite m´aximo del tiempo de ejecuci´on, ya que este tiempo depende en gran medida del n´umero m´aximo de fallos de cache que se producir´an durante la ejecuci´on. Pero, el an´alisis del comportamiento temporal en el peor caso de la cache es complejo, por lo tanto los dise˜nadores de sistemas de tiempo real descartan su utilizaci´on. En esta Tesis se analiza el comportamiento en el peor caso de varias jerarqu´ıas de memoria para instrucciones. En concreto se estudia, tanto una cache de instrucciones convencional, como una cache que pueda fijar su contenido. El principal objetivo de este an´alisis es conseguir el mejor rendimiento, en un sistema de tiempo real, de la jerarqu´ıa de memoria estudiada. As´ı pues, tambi´en se presentan diferentes t´ecnicas de an´alisis y c´alculo del WCET para cada una de las jerarqu´ıas de memoria estudiadas. Para una cache de instrucciones convencional con algoritmo de reemplazo LRU, analizamos su comportamiento en el peor caso y demostramos que el n´umero de caminos relevantes generado por estructuras condicionales dentro de bucles no depende del n´umero de iteraciones del bucle, sino que depende del n´umero de caminos del condicional. Esto permite obtener la contribuci´on exacta al WCET de los accesos a memoria, cuando el n´umero de caminos condicionales dentro de un bucle no es grande. As´ı pues, proponemos una t´ecnica para determinar la contribuci´on exacta al WCET de los accesos a memoria. A esta t´ecnica la denominamos poda din´amica de caminos. Estudiamos una jerarqu´ıa de memoria formada por un (LB/ Line Buffer) y una cache que pueda fijar su contenido (Lockable iCache). Para esta jerarqu´ıa de memoria proponemos un algoritmo ´optimo que selecciona las l´ıneas a fijar en la i ii cache durante la ejecuci´on de cada tarea del sistema. A este algoritmo lo hemos denominado Lock-MS (Lock for Maximize Schedulability). Adem´as, proponemos una nueva jerarqu´ıa de memoria en sistemas de tiempo real con hardware de preb´usqueda secuencial (PB/ Prefetch Buffer) y analizamos su influencia en el WCET de cada tarea. El LB y el PB capturan muy bien la localidad espacial y reducen considerablemente el WCET de las tareas. Tambi´en permiten reducir la capacidad de la Lockable iCache sin comprometer la planificabilidad del sistema. Dado un conjunto de tareas que podr´ıan formar un sistema de tiempo real, para cada una de las jerarqu´ıas de memoria analizadas, proponemos t´ecnicas de an´alisis y c´alculo del WCET totalmente seguro y m´as preciso que el obtenido con las t´ecnicas de an´alisis ya descritas en la literatura. Finalmente, tambi´en se presenta un estudio sobre el consumo energ´etico de una jerarqu´ıa de memoria formada por un LB, un PB y una Lockable iCache. Los resultados de este estudio indican que el camino del WCET de una tarea no coincide con el camino del WCEC (Worst Case Energy Consumption) de dicha tarea. Palabras Clave: WCET, tiempo de ejecuci´on en el peor caso, jerarqu´ıa de memoria, memoria cache, camino m´as largo, caminos relevantes, m´axima planificabilidad, preb´usqueda secuencial, WCEC, consumo de energ´ıa en el peor caso. Cap´ıtulo 1 Introducci´on El empleo de los sistemas inform´aticos es cada vez m´as habitual en nuestra vida diaria. Desde un sencillo microondas hasta el complejo sistema de seguridad y control de un reactor nuclear dependen del correcto funcionamiento de un sistema inform´atico. En concreto, la mayor parte de los sistemas inform´aticos son sistemas empotrados que no suelen ser visibles directamente por el usuario y forman parte de sistemas m´as grandes y complejos [28, 88, 125]. Se pueden encontrar sistemas empotrados en equipos de telecomunicaci´on, en sistemas de transporte, en equipos de fabricaci´on y en dispositivos electr´onicos de uso diario. Los sistemas empotrados deben ser fiables y seguros, con la garant´ıa de que en caso de fallo la reparaci´on sea posible; deben estar siempre disponibles; no deben causar da˜nos y no deben generar p´erdida de informaci´on. Igualmente han de ser eficientes en consumo energ´etico, ya que muchos sistemas empotrados son dispositivos m´oviles que funcionan con bater´ıas; en tama˜no del c´odigo, puesto que todo el c´odigo debe almacenarse en la memoria del sistema; y en la utilizaci´on de los recursos del sistema. Finalmente, si son dispositivos port´atiles o dispositivos electr´onicos de uso diario, adem´as de garantizar una calidad m´ınima de servicio para que resulten atractivos a los usuarios, han de ser ligeros y su coste debe ser competitivo en el mercado [88, 125]. Los sistemas empotrados adquieren una relevancia especial cuando se utilizan para responder temporalmente a un evento externo. En este caso, el sistema se denomina Sistema de Tiempo Real [28]. La correcci´on de un sistema de tiempo real, no s´olo est´a en funci´on de los resultados obtenidos, sino que tambi´en depende del instante en el que dichos resultados son generados, por lo tanto es esencial predecir su funcionamiento. En los sistemas de tiempo real, tanto la fiabilidad como la seguridad adquieren una relevancia especial, ya que suelen ser sistemas cr´ıticos y un mal funcionamiento en estos sistemas puede provocar incluso graves da˜nos personales. En los autom´oviles que conducimos encontramos ejemplos cl´asicos de sistemas de 1 21. INTRODUCCI ´ ON Figura 1.1: Sistema de Tiempo Real. tiempo real, tales como el sistema de control del airbag, el sistema de control de frenado (ABS) y por supuesto el sistema de control de tracci´on del que ya disponen la mayor´ıa de los veh´ıculos actuales. Los programas escritos para sistemas de tiempo real deben ser verificados para asegurar el correcto funcionamiento del sistema. Pero adem´as tambi´en se debe verificar la correcci´on temporal del mismo, es decir, es obligatorio garantizar el tiempo de respuesta de las tareas del sistema en el peor caso. Por ejemplo, es obligatorio asegurar que el sistema de control del airbag, en caso de accidente, lanzar´a el airbag en un corto plazo de tiempo para prevenir los posibles da˜nos sobre los ocupantes del veh´ıculo. En definitiva, un sistema de tiempo real debe responder a los diferentes eventos generados por ´este en unos plazos de tiempo preestablecidos. El sistema se divide habitualmente en un conjunto de tareas que cooperan para conseguir una funcionalidad, y cada una de ellas se encarga de responder a un determinado evento o conjunto de eventos generados por el entorno (ver Figura 1.1). Para poder responder a dichos eventos en un determinado plazo de tiempo, es necesario determinar qu´e tarea o tareas se deben ejecutar en cada instante, y para ello es necesario definir algoritmos o pol´ıticas de planificaci´on que determinar´an si las restricciones temporales del sistema se pueden satisfacer. Por lo tanto, es necesario realizar un an´alisis de planificabilidad que tenga en cuenta: las tareas del sistema, sus plazos de finalizaci´on, sus periodos de ejecuci´on y su tiempo de ejecuci´on en el peor caso. CAP´ ITULO 1. 3 Figura 1.2: An´alisis del tiempo de ejecuci´on de una tarea [198]. C´alculo del WCET y planificabilidad en sistemas de tiempo real Uno de los principales retos de los sistemas de tiempo real es el c´alculo del tiempo de ejecuci´on del peor caso (WCET/ Worst Case Execution Time). El WCET de un programa es el mayor tiempo de ejecuci´on que una invocaci´on del programa podr´ıa exhibir en una arquitectura hardware espec´ıfica. Es decir, calcular el WCET es determinar el tiempo de ejecuci´on del camino m´as largo. Obtener el WCET de una tarea de tiempo real es clave en el an´alisis de planificabilidad que garantiza el correcto funcionamiento temporal del sistema [28]. Por lo tanto, el c´alculo del WCET tiene que ser seguro (safe), de tal forma que una sobrestimaci´on m´ınima podr´ıa ser aceptada pero una subestimaci´on no se aceptar´ıa en ning´un caso. Adem´as, el WCET tambi´en tiene que ser preciso, ya que la planificabilidad del sistema debe estar garantizada antes de su ejecuci´on. En la Figura 1.2 se muestra un exhaustivo an´alisis temporal de la ejecuci´on de una tarea. Se han representado todos los posibles tiempos de ejecuci´on de la tarea, pero s´olo se han podido medir algunos de ellos. En la figura tambi´en aparecen reflejados el tiempo de ejecuci´on del mejor caso (BCET/ Best Case Execution Time) y el WCET. Como se muestra en la Figura 1.2, cualquier aproximaci´on al WCET basada en medida no es segura, ya que s´olo considera un subconjunto de las posibles ejecuciones del programa. Una vez garantizada la planificabilidad del sistema, tambi´en es necesario ordenar la ejecuci´on de sus tareas. Uno de los algoritmos m´as sencillos y utilizados en planificaci´on es el algoritmo Ejecutivo C´ıclico que ordena la ejecuci´on de las tareas mediante una tabla donde se indican los instantes en que cada tarea debe tomar y abandonar la CPU [13]. Este algoritmo es muy f´acil de implementar y muy eficiente en tiempo de ejecuci´on. Adem´as, permite asegurar la planificabilidad del sistema desde el primer momento, ya que facilita la predicci´on de los instantes de ejecuci´on de las tareas que son fijos y conocidos. Pero este algo- 41. INTRODUCCI ´ ON ritmo es muy r´ıgido y no permite incorporar nuevas tareas al sistema de forma sencilla. Adem´as, al no existir un sistema operativo propiamente dicho, no es posible utilizar algunos servicios de comunicaci´on del sistema. Los sistemas operativos de tiempo real utilizan algoritmos de planificaci´on en tiempo de ejecuci´on basados en prioridades. En funci´on del tipo de prioridad de las tareas, los algoritmos pueden seguir una pol´ıtica de planificaci´on con expulsiones o sin ellas. Cuando en el sistema se permiten las expulsiones, una tarea abandona el procesador en cuanto otra tarea de mayor prioridad est´a lista para su ejecuci´on. Si la prioridad de las tareas es constante, los algoritmos se denominan est´aticos o de prioridades fijas. En la literatura encontramos algunos trabajos cl´asicos que definen este tipo de planificaci´on, basada principalmente en asignar la prioridad m´as alta a la tarea m´as frecuente RMA (Rate Monotonic Analysis) o a la tarea m´as urgente DMA (Deadline Monotonic Analysis) [111]. La teor´ıa subyacente en estos algoritmos tambi´en permite demostrar que la asignaci´on ´optima de prioridades debe ser inversamente proporcional a su plazo de ejecuci´on, esto es, a menor plazo de ejecuci´on mayor prioridad. Mediante estos algoritmos, tambi´en es posible determinar si un conjunto de tareas es planificable, es decir, si se cumplir´an los requisitos temporales en forma de plazos de finalizaci´on marcados para ellas. Por ejemplo, un sistema con Ntareas peri´odicas con prioridades fijas, donde Cies el WCET y Pies el periodo de activaci´on de la tarea Taski, ser´a planificable si la utilizaci´on del procesador Uverifica la siguiente expresi´on: U= N X i=i Ci Pi ≤N·21 N−1(1.1) Consideremos el ejemplo de la Tabla 1.1 formado por tres tareas. Para cada una de ellas se indica el tiempo de ejecuci´on del peor caso Ci, su periodo Pi, que en este caso coincide tambi´en con su plazo de finalizaci´on Di, y la utilizaci´on del procesador. La prioridad de cada tarea es fija y es inversamente proporcional a su periodo. Por lo tanto, seg´un el an´alisis de planificablidad basado en medir la utilizaci´on del procesador, el sistema de la Tabla 1.1 es planificable, ya que U= 0,75 < U(3) = 3 ·(21/3−1) = 0,779, es decir, se verifica la Ecuaci´on 1.1. Sistema de tiempo real Tarea WCET Periodo / Plazo Finalizaci´on Utilizaci´on Task15 20 0,25 Task210 40 0,25 Task320 80 0,25 Tabla 1.1: Ejemplo de un sistema planificable. Supongamos ahora que el WCET de la tarea Task1es 7. En este caso, la utilizaci´on del procesador es U= 0,85 > U(3) = 3 ·(21/3−1) = 0,779, luego CAP´ ITULO 1. 5 Figura 1.3: Planificaci´on mediante RM de las nuevas tareas Task1,Task2 yTask3. no se verifica la Ecuaci´on 1.1, por lo tanto no se puede asegurar que el sistema sea planificable. Sin embargo, esta condici´on es suficiente, pero no es necesaria para garantizar la planificabilidad del sistema. Es decir, en algunas ocasiones un sistema puede ser planificable sin verificar la expresi´on anterior, como por ejemplo en este caso. En la Figura 1.3 se muestra una ejecuci´on del sistema planificando las tareas mediante RM (Rate Monotonic), y obviamente todas ellas acaban su ejecuci´on antes de que termine su plazo de finalizaci´on. Un sistema tambi´en es planificable si se puede garantizar, en cualquier caso, que el tiempo de respuesta de cada tarea Taskies menor que su plazo de finalizaci´on (RTA/ Response Time Analysis). Es decir una tarea Taskiverifica sus restricciones temporales si Ri≤Di, siendo Risu tiempo de respuesta y Di su plazo de finalizaci´on. En este caso, el tiempo de respuesta Rise determina mediante la expresi´on recursiva siguiente: Rn+1 i=Ci+ i−1 X j=1 Rn i Dj·Cj(1.2) En la Figura 1.3 se observa que es posible planificar las tareas del ejemplo anterior. Pero para demostrar la planificabilidad del sistema debemos aplicar RTA. Para ello basta comprobar que el tiempo de respuesta de la tarea Task3 es menor que su plazo de finalizaci´on, es decir R3≤D3= 80. Aplicando la Ecuaci´on 1.2 tenemos que: R0 3= 0 R1 3= 20 (C3= 20) R2 3=d20/20e · 7 + d20/40e · 10 + 20 = 37 R3 3=d37/20e · 7 + d37/40e · 10 + 20 = 44 R4 3=d44/20e · 7 + d44/40e · 10 + 20 = 61 R5 3=d61/20e · 7 + d61/40e · 10 + 20 = 68 R6 3=d68/20e · 7 + d68/40e · 10 + 20 = 68 61. INTRODUCCI ´ ON As´ı pues, como R3= 68 ≤80, queda demostrado que el sistema es planificable. Si por el contrario la prioridad de las tareas puede cambiar en funci´on del estado del sistema, los algoritmos se denominan din´amicos o de prioridades din´amicas. Estos algoritmos basados en prioridades din´amicas presentan dos importantes ventajas. Por un lado aprovechan al m´aximo la potencia del procesador, haciendo que un conjunto de tareas sea planificable cuando no lo era utilizando un algoritmo de prioridades est´aticas; y por otro, se adaptan perfectamente a entornos m´as din´amicos en los que la carga del sistema no puede ser conocida de antemano. Por ejemplo, el algoritmo EDF (Earliest Deadline First) asigna en cada instante la prioridad m´as alta a la tarea cuyo plazo de respuesta est´a m´as pr´oximo; pero el plazo de ejecuci´on de una tarea no es un valor constante y la prioridad de la misma va aumentando cuanto m´as cerca se encuentre de incumplir sus restricciones temporales [111]. El algoritmo LLF (Least Laxity First) asigna en cada instante la prioridad m´as alta a la tarea que menor holgura tiene para finalizar su ejecuci´on. En este caso la prioridad de la tarea depende de su plazo de finalizaci´on y del tiempo de ejecuci´on que todav´ıa tiene pendiente [11]. Dificultades para calcular el WCET La investigaci´on sobre la Jerarqu´ıa de Memoria es uno de los m´as importantes y cl´asicos campos de la Arquitectura de Computadores. Las velocidades del procesador y de la memoria contin´uan creciendo a diferentes ritmos. Por otra parte, el desarrollo tecnol´ogico permite integrar en un solo chip varios procesadores que pueden ejecutar uno o varios hilos de ejecuci´on. La combinaci´on de ambos factores obliga a realizar un sustancial redise˜no de la jerarqu´ıa de memoria, para impedir que ´esta llegue a ser un importante cuello de botella en los computadores del futuro. Los problemas relacionados con la creciente disparidad de velocidades entre procesador y memoria son objetivo de investigaci´on desde todos los puntos de vista. El mercado de los sistemas de tiempo real a˜nade otra restricci´on en el dise˜no de la jerarqu´ıa de memoria, la necesidad de conocer un l´ımite m´aximo del tiempo de ejecuci´on, ya que, por ejemplo, este tiempo depende en gran medida del n´umero m´aximo de fallos de cache que se producir´an durante la ejecuci´on. Aunque las memorias cache, tanto de instrucciones como de datos, reducen el tiempo medio de los accesos a la memoria principal y son muy utilizadas en los procesadores comerciales, la mayor parte de los dise˜nadores de sistemas de tiempo real descartan estos procesadores o proponen el apagado de las caches, debido a que el an´alisis de su comportamiento temporal, en el peor caso, es complejo. Pero las estimaciones pesimistas son poco pr´acticas, ya que el planificador asignar´a a cada tarea m´as tiempo del estrictamente necesario para su ejecuci´on, y adem´as gran parte de los recursos se desaprovechan, lo que genera CAP´ ITULO 1. 7 una gran desconfianza en el usuario. Por lo tanto es muy importante obtener valores seguros y precisos del WCET. Los procesadores actuales disponen de una serie de componentes hardware, tales como la ejecuci´on segmentada de instrucciones, los predictores de saltos, las memorias cache, etc., que permiten reducir la media del tiempo de ejecuci´on de los programas [83]. Desafortunadamente estos componentes tienen latencia variable dependiente del pasado; as´ı por ejemplo, la segmentaci´on introduce los riesgos estructurales y de control que afectan al tiempo de ejecuci´on de las instrucciones, el funcionamiento de los predictores de saltos depende de la historia local o global de ejecuci´on, y las memorias cache pueden hacer aumentar el WCET en funci´on del n´umero de fallos. Todos estos componentes hardware hacen complejo el an´alisis del WCET y obligan a considerar la m´axima latencia. Por lo tanto, el WCET es ampliamente sobrestimado forzando el incremento de los recursos disponibles del sistema para garantizar su funcionamiento temporal. El an´alisis temporal de los procesadores superescalares con ejecuci´on fuera de orden donde los recursos del procesador se asignan din´amicamente, a´un es m´as complejo, ya que podr´ıa alcanzar complejidad exponencial. Adem´as, en este tipo de procesadores no es cierto suponer que la estimaci´on del WCET es segura siempre que se asigna el tiempo de ejecuci´on de peor caso a cada instrucci´on, debido a las anomal´ıas de distribuci´on (timing anomalies) [43, 115, 155, 193]. Una anomal´ıa de distribuci´on se produce cuando el peor caso local no est´a incluido en el peor caso global. Aunque es posible encontrar otros tipos de anomal´ıas de distribuci´on, los casos m´as significativos a tener en cuenta durante el an´alisis del WCET son los siguientes: las anomal´ıas de distribuci´on que se producen en la planificaci´on o asignaci´on de recursos, por ejemplo durante la asignaci´on de las unidades funcionales del procesador; las generadas por la especulaci´on, como por ejemplo las que producen los predictores de saltos; y las generadas por el funcionamiento de las memorias cache [155]. Pero, aunque las producidas en la asignaci´on de recursos s´olo aparecen en procesadores fuera de orden, las otras dos dependen del funcionamiento de los predictores de saltos y del comportamiento particular de las memorias cache. En la Figura 1.4 se presentan dos casos t´ıpicos de anomal´ıas de distribuci´on. El caso a) muestra el efecto en la cache de un fallo durante la predicci´on de un salto. En este caso un fallo de cache en la instrucci´on Aevita el fallo de predicci´on y mejora el tiempo de ejecuci´on con respecto a un acierto de cache en dicha instrucci´on A. En el caso b) se muestra la planificaci´on de un conjunto de instrucciones dependientes unas de otras. En este caso el tiempo de ejecuci´on de la instrucci´on Avar´ıa. Curiosamente, el tiempo de ejecuci´on de todas las instrucciones en conjunto es menor cuando el tiempo de ejecuci´on de la instrucci´on Aes mayor. Aunque en la literatura se han propuesto diferentes t´ecnicas para analizar el WCET de un programa, s´olo el an´alisis est´atico permite determinar el WCET 81. INTRODUCCI ´ ON Figura 1.4: Anomal´ıas de distribuci´on [155]. de forma segura. Sin embargo, el hardware moderno, que cada vez es m´as complejo, supone una gran limitaci´on para estas t´ecnicas de an´alisis. Por ejemplo, el tiempo de ejecuci´on de algunos segmentos del programa puede variar en funci´on de si se utiliza hardware que act´ua en paralelo o de si se emplean componentes que dependen de la historia de ejecuci´on. En definitiva, el c´alculo del WCET es complejo, ya que depende tanto del software (por ejemplo el compilador, la arquitectura del lenguaje m´aquina, etc.), como del hardware (por ejemplo la jerarqu´ıa de memoria, los predictores de saltos, la ejecuci´on segmentada de las instrucciones, etc.) [198]. Debido a la complejidad del hardware moderno, el tiempo de an´alisis del WCET podr´ıa exceder de lo razonable, obligando a sobrestimar el WCET de forma muy pesimista. En general, s´olo es posible obtener un WCET preciso si todos estos factores se consideran a la vez. En particular, se debe analizar el funcionamiento del procesador de la forma m´as exacta posible. El n´umero de iteraciones de los bucles CAP´ ITULO 1. 9 y el n´umero de llamadas recursivas han de estar acotados y las cotas tienen que ser conocidas. Por eso en la literatura, el t´ermino WCET hace referencia a una cota superior del tiempo de ejecuci´on en el peor caso del programa, ya que se puede afirmar que anal´ıticamente s´olo es posible obtener cotas del tiempo de ejecuci´on del programa. Por lo tanto, el WCET es la m´ınima cota superior obtenida durante el an´alisis. Contribuciones de la Tesis En esta Tesis se analiza el comportamiento, en el peor caso, de varias jerarqu´ıas de memoria para instrucciones. El principal objetivo de este an´alisis es conseguir el mejor rendimiento de la jerarqu´ıa de memoria estudiada en un sistema de tiempo real. Adem´as se presentan diferentes t´ecnicas de an´alisis y c´alculo del WCET para cada una de las jerarqu´ıas de memoria analizadas. En concreto, para un conjunto de tareas que podr´ıan formar un sistema de tiempo real, mediante las t´ecnicas de an´alisis y c´alculo que presentamos se consigue calcular un WCET totalmente seguro y m´as preciso que el obtenido con las t´ecnicas de an´alisis ya descritas en la literatura. A continuaci´on comentamos brevemente las contribuciones m´as importantes de esta Tesis: Las estructuras condicionales dentro de bucles hacen que el an´alisis del WCET en presencia de caches adquiera complejidad exponencial, debido a las interferencias intr´ınsecas de la cache. Como primera contribuci´on demostramos que el n´umero de caminos que es necesario analizar para determinar el comportamiento exacto de una cache de instrucciones con algoritmo de reemplazo LRU, no depende del n´umero de iteraciones de los bucles, sino que est´a en funci´on del n´umero de caminos del condicional. Cuando el n´umero de caminos alternativos de un bucle no es grande, la complejidad del problema se reduce considerablemente y en muchos casos se puede predecir de forma exacta el comportamiento de la cache de instrucciones en el peor caso [7]. As´ı pues, proponemos una t´ecnica de poda que permite analizar y calcular el WCET de una tarea que se ejecuta de forma aislada en presencia de una cache de instrucciones. Este an´alisis, centrado en el comportamiento de una cache de instrucciones convencional, permite determinar la contribuci´on exacta de los accesos a memoria al WCET. Por lo tanto, el WCET obtenido es m´as preciso [7]. En un sistema multitarea analizamos una cache de instrucciones que pueda fijar o bloquear su contenido durante algunos periodos de la ejecuci´on. Como segunda contribuci´on se presenta el algoritmo Lock-MS (Lock for Maximize Schedulability) para optimizar el rendimiento de una jerarqu´ıa de memoria formada por un LB (Line Buffer) y una cache de instrucciones que pueda fijar su contenido (Lockable iCache) durante algunos periodos de la ejecuci´on del 10 1. INTRODUCCI ´ ON sistema. Al fijar el contenido de la cache su comportamiento es totalmente predecible. Adem´as, si el procesador considerado no dispone de otros componentes hardware de latencia variable, se evita la explosi´on combinatoria de los caminos condicionales dentro de bucles. Finalmente, tambi´en se evitan las interferencias de cache, tanto las intr´ınsecas, como las extr´ınsecas. El algoritmo Lock-MS est´a basado en ILP (Integer Linear Programming) y permite obtener un WCET seguro y preciso de cada una de las tareas del sistema. El objetivo de Lock-MS es seleccionar las l´ıneas de memoria m´as adecuadas que se bloquear´an en la cache, para obtener la m´axima planificabilidad del sistema en esta jerarqu´ıa de memoria, teniendo en cuenta adem´as el WCET de cada tarea y el coste de los cambios de contexto del sistema [6]. Sin embargo, cuando el n´umero de caminos de un programa es grande, no es posible representar todos los caminos mediante restricciones lineales. Como tercera contribuci´on se presenta un modelo compacto del algoritmo Lock-MS que permite reducir el n´umero de caminos del problema ILP, sin perder precisi´on en el WCET obtenido [6]. Como cuarta contribuci´on presentamos la posibilidad de predecir el WCET con un hardware de preb´usqueda secuencial (PB/ Prefetch Buffer). As´ı pues, se propone una nueva jerarqu´ıa de memoria con preb´usqueda para un sistema de tiempo real formada por un LB, un PB y una Lockable iCache. Para obtener la m´axima planificabilidad del sistema, en esta nueva jerarqu´ıa de memoria, proponemos, tanto la extensi´on del algoritmo Lock-MS, como la extensi´on del modelo compacto de dicho algoritmo. En general el hardware de preb´usqueda permite reducir el WCET y la capacidad de la cache de instrucciones. En particular, la preb´usqueda reduce el WCET en programas de c´odigo plano, llegando a obtener un rendimiento equivalente al caso ideal [5]. Finalmente, y dado que el consumo de energ´ıa tambi´en es un aspecto importante en los sistemas de tiempo real, se presenta un estudio sobre el consumo energ´etico en el peor caso (WCEC/ Worst Case Energy Consumption). En este estudio se pone de manifiesto que no existe una correspondencia lineal entre el WCEC y el WCET de una tarea. As´ı pues, se introduce la posibilidad de que el dise˜nador del sistema decida si su objetivo es obtener un WCET m´as preciso o reducir el WCEC. Tambi´en se muestra que la preb´usqueda aumenta considerablemente el consumo de energ´ıa del sistema y, en algunos casos, no consigue reducir significativamente el WCET de las tareas analizadas. Actualmente, estamos analizando el comportamiento en el peor caso de la cache de datos, ya que podr´ıa reducir a´un m´as el WCET de una tarea. Sin embargo, predecir el funcionamiento de la cache de datos es un problema bien distinto, ya que para una misma instrucci´on de acceso a datos, las direcciones de memoria a las que se accede pueden cambiar a lo largo de la ejecuci´on. En concreto, estamos estudiando el comportamiento de una nueva estructura hardware predecible para la cache de datos en sistemas de tiempo real. Como CAP´ ITULO 2. 17 Figura 2.3: Esquema que sigue el c´alculo del WCET basado en AST [198]. de cada una de las alternativas del condicional. Por ejemplo, en el caso de un condicional: TiempoExe(if E then A else B) = TiempoExe(E) + m´ax ( TiempoExe(A), TiempoExe(B) ) Por lo tanto, aplicando las reglas anteriores, como se indica en la Figura 2.3, al esquema del programa mostrado en la Figura 2.2 se tiene que: WCET = 3072 En general, los m´etodos basados en ´arbol no pueden capturar las restricciones de flujo de control complejas o los tiempos de ejecuci´on variables para un mismo segmento o bloque b´asico. El c´alculo basado en ´arbol es local, es decir, el tiempo de ejecuci´on de los bloques b´asicos se obtiene de forma independiente y luego se utiliza en las estructuras de programaci´on de las que forman parte dichos bloques. C´alculo del WCET basado en caminos En los m´etodos de c´alculo del WCET basados en caminos se enumeran todos los caminos que puede seguir el programa durante su ejecuci´on. El WCET se calcula como el m´aximo tiempo de ejecuci´on asociado a dichos caminos. Conviene 18 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. indicar que un camino es una secuencia de segmentos o bloques b´asicos que no contiene estructuras condicionales ni bucles. Esta t´ecnica puede alcanzar complejidad exponencial cuando se aplica a programas con sentencias condicionales dentro de bucles, en especial en presencia de componentes hardware con latencia variable durante la ejecuci´on, como por ejemplo los predictores de saltos y las memorias cache. En estos casos, esta t´ecnica s´olo se puede utilizar para determinar el tiempo de ejecuci´on de un trozo o segmento del programa, pero el WCET del programa completo se podr´ıa sobrestimar ampliamente debido a la p´erdida de informaci´on que se produce al evitar la complejidad exponencial que presenta. Considerando el ejemplo de la Figura 2.2 donde se indica el camino m´as largo de un programa, el WCET basado en caminos se determina a partir de los siguientes c´alculos: Enumeraci´on de caminos path1 : A+B+C+E+F+H path1 : A+B+C+E+G+H path2 : A+B+D+E+F+H path3 : A+B+D+E+G+H Unidades de tiempo de programa Tiempopath1= 31 Tiempopath2= 28 Tiempopath3= 28 Tiempopath4= 25 Tiempoheader = 3 C´alculo del WCET WCET =T iempoheader +Tiempopath1·(Iteraciones −1) WCET = 3 + 31 ·99 = 3072 C´alculo del WCET basado en IPET En los m´etodos de c´alculo del WCET basados en la enumeraci´on impl´ıcita de caminos (IPET/ Implicit Path-Enumeration Technique), el flujo de control del programa y el tiempo de ejecuci´on de los bloques b´asicos se transforman en un problema de Programaci´on Lineal Entera (ILP/ Integer Linear Programming) [105, 152]. El m´etodo IPET permite expresar mediante restricciones lineales, tanto las dependencias temporales, como las del flujo de control, y con una herramienta de c´alculo adecuada o solver se resuelve el problema ILP de CAP´ ITULO 2. 19 forma muy efectiva [161]. El c´alculo del WCET basado en IPET es m´as complejo, y en ´el se deben considerar las restricciones de conservaci´on de flujo asociadas al CFG. As´ı pues, el n´umero de veces que se ejecutar´a cada bloque b´asico debe cumplir las reglas de conservaci´on de flujo, garantiz´andose que el n´umero de veces que se ejecutan los bloques de entrada es igual al n´umero de veces que se ejecutan los bloques de salida. A estos enlaces de los bloques b´asicos se les denomina restricciones estructurales y forman parte de las restricciones de flujo de control del programa. Por ejemplo, si consideramos el CFG con restricciones de conservaci´on de flujo de la Figura 2.2, las restricciones que modelan el problema ILP son las siguientes: Restricciones de Inicio y Finalizaci´on Xstart = 1 Xexit = 1 Restricciones estructurales Xstart =XstatA XA=XstartA +XHA =XAexit +XAB XB=XAB =XBC +XBD XC=XBC =XCE · · · · · · XH=XF H +XGH =XHA Xexit =XAexit Restricciones asociadas a los l´ımites de los bucles XA≤100 Expresi´on que determina el WCET del programa WCET = m´ax (3 ·XA+ 5 ·XB+ 7 ·XC. . . 2·XH) WCET = 3072 Los datos necesarios para determinar un WCET seguro y preciso mediante IPET son las restricciones estructurales y el tiempo de ejecuci´on de cada uno de los bloques b´asicos del programa. Adem´as, teniendo en cuenta las condiciones de flujo de control, se determinan las restricciones de funcionalidad del programa. En muchas ocasiones, estas restricciones se obtienen de forma autom´atica, otras veces el usuario las a˜nade directamente al problema ILP. Las restricciones de 20 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. funcionalidad permiten estimar de una forma m´as precisa el WCET. As´ı pues, el c´alculo del WCET se modela como un conjunto de restricciones lineales cuya funci´on objetivo maximiza el tiempo de ejecuci´on del programa. El c´alculo el WCET tambi´en se podr´ıa formular como un problema de programaci´on lineal (LP/ Linear Programming) pero, en algunas ocasiones, la soluci´on no ser´ıa v´alida, ya que en este caso la soluci´on no tiene por qu´e ser entera. Sin embargo, el WCET obtenido al resolver el problema LP suele ser una buena aproximaci´on al WCET exacto, proporcionando una cota inferior. La ejecuci´on de programas complejos en procesadores actuales no se puede modelar de una forma sencilla, como un simple problema de conservaci´on de flujo. As´ı por ejemplo, para considerar las funcionalidades del programa es necesario a˜nadir restricciones de flujo complejas. Pero si adem´as el tiempo de ejecuci´on de los bloques b´asicos puede ser variable, por ejemplo debido a la utilizaci´on de memorias cache, se deben a˜nadir nuevas restricciones relativas a la historia de ejecuci´on del programa. As´ı pues, aunque los m´etodos de c´alculo del WCET basados en IPET pueden tener algunas limitaciones a la hora de describir el problema ILP, el WCET obtenido es seguro y suele ser mucho m´as preciso que el logrado mediante AST o mediante la enumeraci´on de caminos, ya que las limitaciones de estos m´etodos todav´ıa son mayores. C´alculo del WCET: Un ejemplo basado en ARM v7 Como ejemplo de los comentarios anteriores, en este apartado se calcula el WCET de un programa escrito en C. En la Figura 2.4 se muestra el c´odigo ensamblador del programa compilado con GCC 2.95.2 -O2 para ARM v7. En el c´odigo ensamblador se han marcado los bloques b´asicos del programa y su coste de ejecuci´on. Suponemos, por sencillez, que cada instrucci´on tiene un coste de ejecuci´on de un ciclo, por lo tanto los tiempos de ejecuci´on de cada bloque b´asico son constantes para todos los posibles caminos de ejecuci´on. Asociado al programa de la Figura 2.4, se muestra en la Figura 2.5 el ´arbol de sintaxis abstracta, el grafo de flujo de control con el camino m´as largo marcado y el grafo de flujo de control con las restricciones de conservaci´on de flujo necesarias. El WCET del programa de la Figura 2.4, que se obtiene a partir del AST de la Figura 2.5 a), se determina en funci´on del tiempo de ejecuci´on de cada bloque b´asico mediante la siguiente expresi´on: WCET =B1 + 10 ·(B2 + m´ax (B3, B4) + B5 ) + B6 WCET = 8 + 10 ·( 4 + m´ax (7,2) + 7 ) + 1 = 189 CAP´ ITULO 2. 21 @ Generated by gcc 2.95.2 19991024 (release) for ARM/elf .file "programa.c" gcc2_compiled.: .global n .data .align 2 .type n,object .size n,4 n: .word 10 .global z .align 2 .type z,object .size z,4 z: .word 0 .text .align 2 .global main .type main,function main: @ args = 0, pretend = 0, frame = 0 ______ @ frame_needed = 1, current_function_anonymous_args = 0 |-> B1: 8 ciclos mov ip, sp | stmfd sp!, {fp, ip, lr, pc} | sub fp, ip, #4 | mov r1, #0 | mov lr, r1 | mov r2, r1 | mov r0, r2 |_______ ldr ip, .L10 ______ .L6: |-> B2: 4 ciclos add r3, r2, #1 | cmp r3, #5 | mov r2, r3 |_______ bgt .L7 |-> B3: 7 ciclos add lr, lr, #1 | add r1, r1, #2 | ldr r3, [ip, #0] | add r0, r0, #3 | add r3, r3, #4 | str r3, [ip, #0] |_______ b .L8 ______ .L7: |-> B4: 2 ciclos mov r1, r1, asl #1 |_______ mov r0, r0, asl #2 ______ .L8: |-> B5: 7 ciclos ldr r3, [ip, #0] | cmp r2, #9 | add r3, r3, lr | add r3, r3, r1 | add r3, r3, r0 | str r3, [ip, #0] |_______ ble .L6 |-> B6: 1 ciclo ldmea fp, {fp, sp, pc} .L11: .align 2 .L10: .word z .Lfe1: .size main,.Lfe1-main .ident "GCC: (GNU) 2.95.2 19991024 (release)" /* programa.c */ int n = 10; int z = 0; int main() { int i, j; int v, x, y; v = 0; x = 0; y = 0; for (i = 0; i < 10; i++) { j = i + 1; if (j <= 5) { v = v + 1; x = x + 2; y = y + 3; z = z + 4; } else { x = x * 2; y = y * 4; } z = z + v + x + y; } } Figura 2.4: C´odigo ensamblador ARM y bloques b´asicos asociados a un programa en C. 22 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. Figura 2.5: ´ Arbol de sintaxis abstracta, grafo de flujo de control y grafo de flujo con restricciones del programa de la Figura 2.4. El programa de la Figura 2.4 tiene 210 posibles caminos de ejecuci´on que deben ser explorados para determinar el WCET. Sin embargo, cuando el tiempo de ejecuci´on de cada bloque b´asico es fijo, se puede simplificar calculando los m´aximos locales a los diferentes subcaminos condicionales que presenta el programa. As´ı pues, el c´alculo del WCET del programa basado en la enumeraci´on de caminos se puede simplificar de la siguiente manera: WCET =B1 + 10 ·(B2 + m´ax (subPathB3, subPathB4) + B5 ) + B6 WCET = 8 + 10 ·( 4 + m´ax (7,2)+7)+1 WCET = 8 + 10 ·( 4 + 7 + 7 ) + 1 = 189 Finalmente, en la Tabla 2.1 se muestran las restricciones estructurales y de funcionalidad asociadas al grafo de flujo de control con la informaci´on de conservaci´on de flujo de la Figura 2.5 c). Tambi´en se indica el tiempo de ejecuci´on de los bloques b´asicos del programa de la Figura 2.4. A partir de esta informaci´on se modela el problema ILP que determina el WCET del programa mediante IPET. En este caso los tiempos de ejecuci´on de cada bloque b´asico son constantes y las variables del problema ILP son el n´umero de veces que se ejecuta cada uno de los bloques b´asicos. El tiempo de ejecuci´on del camino m´as largo del programa se obtiene resol- CAP´ ITULO 2. 23 Restricciones Restricciones Ciclos de ejecuci´on estructurales funcionales de bloques b´asicos x1= 1 x3≤5B1 = 8 x1=e1x5≤10 B2 = 4 x2=e1+e6B3 = 7 x2=e2+e3B4 = 2 x3=e2B5 = 7 x3=e4B6 = 1 x4=e3 x4=e5 x5=e4+e3 x5=e6+e7 x6=e7 x6= 1 Tabla 2.1: Restricciones IPET y tiempo de ejecuci´on de los bloques b´asicos del programa de la Figura 2.4. viendo el siguiente problema ILP. m´ax : 6 X k=1 Bk ·xi C´alculo del WCET basado en par´ametros El c´alculo del WCET basado en par´ametros es otra t´ecnica que proporciona una estimaci´on precisa del tiempo de ejecuci´on en el peor caso. Se trata de evaluar una expresi´on simb´olica que depende de una serie de variables asociadas al programa. Mediante este c´alculo no se proporciona una cota fija del WCET, sino que se obtiene una funci´on dependiente de una serie de par´ametros asociados al programa. Cuando se asigne un valor a cada uno de los par´ametros y se eval´ue la funci´on, se obtendr´a una cota del WCET. Existen diferentes razones para justificar este tipo de c´alculo. En algunos casos, el valor de ciertos par´ametros s´olo es conocido en tiempo de ejecuci´on, por ejemplo el n´umero m´aximo de iteraciones de un bucle para una ejecuci´on particular del programa. En otros casos, los datos de entrada del programa determinan el camino a seguir durante la ejecuci´on, y por lo tanto pueden fijar el tiempo de ejecuci´on de algunas subrutinas. Por ´ultimo, se justifica el uso de este tipo de c´alculo, por la rapidez con la que se obtiene el WCET del programa cuando ya se han asignado los valores a todos los par´ametros. Como ya se ha comentado, para conseguir una cota precisa del WCET de un programa es necesario indicar el n´umero m´aximo de iteraciones de cada uno de 24 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. sus bucles. Si esta informaci´on no se conoce de forma exacta, el an´alisis est´atico no es efectivo y puede llegar a producir una sobrestimaci´on inadmisible en el WCET calculado. En algunos trabajos se propone el an´alisis del WCET basado en par´ametros para evitar esta sobrestimaci´on [37, 184]. En este caso, la funci´on obtenida en el an´alisis depende del n´umero de iteraciones que se decide durante la ejecuci´on. Los beneficios de este tipo de an´alisis son claros, ya que el WCET se calcula de una forma muy r´apida, se mejora la planificaci´on din´amica del sistema y se gestiona de forma m´as efectiva la utilizaci´on de los recursos del sistema. Por otra parte, cuando la funci´on que determina el WCET depende de los datos de entrada del programa o del tiempo de ejecuci´on de alguna funci´on, el WCET conseguido es m´as sensible al contexto. Puesto que el tiempo de ejecuci´on de la funci´on no es constante, la estimaci´on del WCET se puede obtener evaluando dicha funci´on para los valores extremos [19]. Finalmente, dado el inter´es suscitado por esta t´ecnica, en algunos trabajos de investigaci´on incluso se ha propuesto utilizar Programaci´on Param´etrica Entera (PIP/ Parametric Integer Programming) [52]. Se trata de transformar el c´alculo del WCET basado en IPET, que se soluciona mediante un problema ILP, en un problema basado en par´ametros que se resuelve mediante PIP [4, 33, 110]. 2.2. An´alisis de flujo de control El an´alisis de flujo de control es una de las fases que m´as influencia tiene en el an´alisis y c´alculo del WCET. Durante esta fase se intenta obtener la mayor informaci´on sobre la estructura del programa, generalmente, a partir del c´odigo fuente. Posteriormente es necesario combinar la informaci´on obtenida durante el an´alisis de flujo de control y el an´alisis del funcionamiento del procesador, para lograr una estimaci´on del WCET del programa lo m´as precisa posible. El principal objetivo del an´alisis de flujo de control es determinar la estructura del programa mediante el ´arbol de sintaxis abstracta (AST/ Abstract Sysntax Tree) o mediante el grafo de flujo de control (CFG/ Control Flow Graph). En algunos casos, el compilador puede generar la estructura del programa autom´aticamente, por lo que, tanto la construcci´on del AST, como la del CFG suelen ser directas. Adem´as, durante el an´alisis de flujo de control del programa tambi´en es de gran importancia determinar el n´umero m´aximo de iteraciones de los bucles y detectar los caminos imposibles. En este ´ambito de investigaci´on, los caminos imposibles son aquellos caminos que nunca pueden ser recorridos durante la ejecuci´on del programa. An´alisis de la estructura del programa El an´alisis de flujo de control es complejo, ya que depende del tama˜no del c´odigo, de los valores de los datos de entrada e incluso del tama˜no del domi- CAP´ ITULO 2. 25 nio de las variables del programa. No obstante, si queremos realizar un an´alisis exhaustivo de la estructura del programa, son tambi´en de inter´es las t´ecnicas que intentan reducir la complejidad del an´alisis a costa de perder cierta informaci´on [38, 73, 159]. As´ı, por ejemplo, estas t´ecnicas intentan fusionar caminos o eliminar las instrucciones que no influyen directamente en el flujo de control del programa. Para determinar la estructura del programa se utiliza, tanto el c´odigo fuente, como el c´odigo objeto. Si la informaci´on de flujo de control se obtiene a partir del c´odigo fuente es necesario trazar un mapa de la estructura del programa sobre el c´odigo objeto, aunque en la mayor parte de los casos, tanto el AST, como el CFG se suelen generar de forma directa a partir del c´odigo fuente. Cuando el compilador no realiza optimizaciones destructivas es relativamente sencillo trazar este mapa sobre el c´odigo objeto, aunque no es suficiente para obtener un WCET preciso. En la literatura se han presentado diferentes t´ecnicas que consiguen la informaci´on m´as relevante del programa de forma autom´atica para calcular el WCET. Estas t´ecnicas analizan el c´odigo objeto del programa, y con la informaci´on obtenida completan el AST o el CFG. La mayor parte de estas t´ecnicas utilizan ejecuci´on simb´olica, para analizar el c´odigo objeto del programa o transformar la informaci´on conseguida durante el an´alisis en restricciones lineales que luego incorporan al c´alculo del WCET [34, 48, 49, 50, 168]. Pero cuando el compilador puede aplicar optimizaciones destructivas, trazar un mapa de la estructura del programa sobre el c´odigo objeto es mucho m´as dif´ıcil. De hecho, en muchos trabajos de investigaci´on se prohiben este tipo de optimizaciones para evitar este problema. Puesto que la estructura del c´odigo objeto compilado con optimizaciones puede ser muy diferente a la estructura del c´odigo fuente, establecer la relaci´on entre el c´odigo objeto y el c´odigo fuente es m´as complejo, y por lo tanto el an´alisis del WCET tambi´en lo es. Cuando la informaci´on de flujo de control se obtiene a partir del c´odigo objeto, ya no es necesario trazar un mapa de la estructura del programa sobre el c´odigo objeto. Adem´as, se aprovechan todas las optimizaciones del compilador que, en general, mejoran el funcionamiento del programa y reducen el tama˜no del c´odigo. Ambos factores disminuyen el coste del sistema y, no s´olo mantienen las prestaciones del mismo, sino que las incrementan. Por lo tanto, a la hora de calcular el WCET de un programa no se deber´ıan desaprovechar las optimizaciones del compilador, ya que la cota del WCET obtenida ser´a mucho m´as precisa. En la literatura se han propuesto diferentes trabajos de investigaci´on dedicados a resolver este problema [44, 46, 93, 94, 95, 96, 109, 148, 185]. En general todos estos trabajos tratan de a˜nadir, en el c´odigo objeto, la informaci´on que se obtiene del c´odigo fuente, de tal forma que se pueda aprovechar el trabajo realizado durante el proceso de compilaci´on. 26 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. La programaci´on orientada a objetos a˜nade a´un m´as complejidad al an´alisis de flujo de control. Obviamente con este tipo de programaci´on es dif´ıcil establecer una relaci´on entre el c´odigo fuente y el c´odigo objeto del programa. Este problema ha sido tratado mediante interpretaci´on abstracta en diferentes trabajos de investigaci´on [67, 68, 69, 70, 71, 72]. Iteraciones de un bucle y caminos imposibles El an´alisis de flujo de control tambi´en trata de determinar el n´umero m´aximo de iteraciones de los bucles y los caminos imposibles, por ejemplo, mediante alguna t´ecnica de an´alisis formal como la interpretaci´on abstracta [40]. En principio es habitual que el programador indique en el c´odigo fuente el n´umero de iteraciones de los bucles, pero estas indicaciones pueden llevar asociado alg´un tipo de error. Adem´as, cuando se permite al compilador realizar optimizaciones, estas indicaciones pueden no ser exactas, por ejemplo, cuando el compilador desenrolla un bucle, el n´umero de iteraciones se reduce. Por lo tanto, tambi´en son importantes los trabajos de investigaci´on que determinan autom´aticamente el n´umero de iteraciones de los bucles [41, 51, 75, 76, 77, 80, 81, 84, 89, 112, 126]. La mayor parte de estas propuestas tratan de determinar directamente los invariantes de los bucles, por ejemplo mediante la interpretaci´on abstracta [51, 126]. En otros casos particulares se ha propuesto el an´alisis de flujo de datos [41], o el an´alisis sint´actico [76, 77]. Aunque tambi´en es habitual utilizar ejecuci´on simb´olica [80, 81, 84, 89]. Un camino imposible puede hacer que la cota obtenida durante el c´alculo del WCET no sea precisa, ya que durante el an´alisis est´atico dicho camino se podr´ıa considerar como el camino m´as largo. Dicho camino nunca ser´a tomado durante la ejecuci´on del programa y, por lo tanto, el WCET obtenido, aunque seguro, no ser´a preciso. En la literatura tambi´en se han presentado soluciones para detectar los caminos imposibles ofalsos caminos, y evitar una posible sobrestimaci´on del WCET [2, 3, 35, 57, 73, 74, 75, 89, 99, 172]. Estos trabajos utilizan ejecuci´on simb´olica, ejecuci´on abstracta, o programaci´on lineal con restricciones. El ejemplo de la Figura 2.6 muestra distintos tipos de caminos imposibles y dos bucles anidados cuyos l´ımites dependen de un par´ametro [75]. El programa contiene dos funciones, la funci´on foo que tiene que estudiarse dos veces dependiendo del punto del programa desde donde se invoca, y la funci´on bar que tiene dos bucles anidados dependientes de un par´ametro. La funci´on main puede seguir algunas de las siguientes combinaciones de caminos: pathAopathB, pathCopathDypathEopathF. La funcion foo puede seguir los caminos: pathG opathHypathIopathJ. Analizando este c´odigo mediante ejecuci´on abstracta, se pueden detectar los caminos imposibles y determinar el n´umero m´aximo de iteraciones del bucle [75]. CAP´ ITULO 2. 33 tiempo real utilizan procesadores muy simples sin caches, los nuevos dise˜nos, por ejemplo en telecomunicaciones, intentan utilizar la ´ultima tecnolog´ıa hardware para incrementar las prestaciones. Por lo tanto, el tiempo de ejecuci´on de los bloques b´asicos debe ser m´as sensible al hardware en el que se ejecuta el programa. Si no se aprovechan adecuadamente los recursos hardware disponibles, las estimaciones del WCET pueden ser muy pesimistas. Una vez realizado el an´alisis del procesador es necesario integrar dicho an´alisis en las t´ecnicas de c´alculo del WCET presentadas en la Secci´on 2.1, pero esta integraci´on no est´a exenta de dificultades. En la literatura se han propuesto t´ecnicas que analizan y determinan el c´alculo del WCET como un solo paso. As´ı por ejemplo, mediante ejecuci´on simb´olica se puede analizar el comportamiento del procesador, en particular la ejecuci´on segmentada de instrucciones, y el comportamiento de las memorias cache [114, 116]. Estos trabajos, para evitar la complejidad exponencial del an´alisis, reducen el n´umero de caminos mediante t´ecnicas de fusi´on (path merging), pero la fusi´on de caminos lleva asociada una importante p´erdida de informaci´on y el WCET suele ser ampliamente sobrestimado. A continuaci´on se describen algunas t´ecnicas que modelan est´aticamente los principales componentes del procesador en el peor caso, y tambi´en se indican algunos detalles para incorporar estos modelos al c´alculo del WCET. An´alisis de la segmentaci´on de instrucciones La segmentaci´on consiste en dividir la ejecuci´on de cada instrucci´on en una serie de etapas con un tiempo de duraci´on fijo. Por ejemplo una implementaci´on t´ıpica del conjunto de instrucciones RISC se divide en cinco etapas o ciclos: capturar la instrucci´on (fetch), decodificar la instrucci´on (decode), ejecuci´on (execution), acceso a memoria (memory access), y escritura del resultado (write-back) [83]. En el caso ideal, durante la ejecuci´on de un bloque b´asico, se puede conseguir ejecutar hasta una instrucci´on por ciclo. Pero durante la ejecuci´on, pueden surgir algunos problemas que impidan aprovechar este solapamiento, por ejemplo los riesgos estructurales que aparecen cuando los recursos hardware no son suficientes para mantener todas las instrucciones en ejecuci´on; los riesgos de datos que surgen cuando una instrucci´on depende del resultado de la ejecuci´on de una instrucci´on previa con la que ha solapado; y finalmente los riesgos de control que aparecen con las instrucciones de salto que modifican el contador de programa [83]. As´ı pues, en un procesador segmentado tambi´en se debe tener en cuenta el tiempo de ejecuci´on de las instrucciones solapadas, para que la estimaci´on del WCET sea precisa. Por lo tanto, es necesario analizar, por un lado, dentro de un 34 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. bloque b´asico, los retardos producidos por los riesgos de datos y estructurales; y por otro, entre dos bloques b´asicos consecutivos, los riesgos de control. En la literatura se han presentado diferentes trabajos que estudian el efecto de la segmentaci´on en el c´alculo del WCET [17, 47, 82, 79, 108, 141, 160, 169, 204]. La forma m´as habitual de analizar la influencia de la segmentaci´on en el WCET es determinar el tiempo de ejecuci´on de las instrucciones mediante tablas de tiempos o mediante simulaci´on de la ejecuci´on. El tiempo de ejecuci´on de cada instrucci´on se utiliza posteriormente para determinar el WCET mediante las t´ecnicas de c´alculo ya comentadas en la Secci´on 2.1, por ejemplo mediante IPET [47, 169]. Mucho m´as ambiciosas son las propuestas para analizar el WCET en procesadores fuera de orden [103, 104]. La dificultad de estas propuestas reside principalmente en determinar el tiempo m´aximo de ejecuci´on de cada uno de los bloques b´asicos durante la asignaci´on din´amica de recursos en un procesador fuera de orden, evitando las anomal´ıas de distribuci´on. Esta propuesta modela, mediante restricciones, un problema ILP que determina el tiempo de ejecuci´on de peor caso, de cada uno de los bloques b´asicos del programa. Finalmente conviene indicar que algunas propuestas, adem´as de estudiar la ejecuci´on segmentada de instrucciones, tambi´en modelan el comportamiento de una cache de instrucciones [82, 79] o de un predictor de saltos [17]. An´alisis del predictor de saltos El predictor de saltos tiene como objetivo principal reducir el retardo que se puede producir despu´es de una instrucci´on de salto. Para cada instrucci´on de control este mecanismo de predicci´on determina, est´atica o din´amicamente, si se producir´a una interrupci´on en la secuencia de ejecuci´on de las instrucciones del programa (salto tomado) o no (salto no tomado), mientras se calcula la direcci´on de la siguiente instrucci´on a ejecutar. Aunque los predictores de saltos mejoran la media del tiempo de ejecuci´on del programa, en los sistemas de tiempo real, debido a las anomal´ıas de distribuci´on, la predicci´on del salto debe ser totalmente segura, asumiendo un fallo cuando no lo es. Las estrategias utilizadas en la predicci´on de saltos se clasifican en est´aticas, cuando la predicci´on del salto es siempre la misma, y en din´amicas, cuando la predicci´on del salto depende de la historia de ejecuci´on [165]. A continuaci´on se resumen brevemente algunas de las estrategias m´as sencillas utilizadas. Estrategias est´aticas: Predicen todos los saltos como tomados. Predicen los saltos tomados en funci´on del c´odigo de operaci´on. Predicen los saltos hacia atr´as como tomados. CAP´ ITULO 2. 35 Estrategias din´amicas: Predicen el salto igual a como se realiz´o en la ´ultima ejecuci´on. Predicen los saltos como tomados si aparecen en una tabla que se actualiza durante la ejecuci´on. Predicen los saltos de acuerdo a uno o m´as bits que se actualizan durante la ejecuci´on. Los predictores din´amicos necesitan una peque˜na memoria para guardar la historia de la ejecuci´on a partir de la cual se realiza la predicci´on [83]. Esta memoria se denomina habitualmente branch-prediction buffer obranch-history table. Adem´as, si para predecir el salto s´olo se tiene en cuenta la propia instrucci´on de salto, los predictores din´amicos se denominan predictores locales, y si tienen en cuenta el comportamiento de todos los saltos realizados hasta ese instante se denominan predictores globales. Aunque los predictores de saltos din´amicos presentan mejor rendimiento que los est´aticos, la predicci´on de su funcionamiento en el peor caso es m´as compleja, y algunos investigadores desaconsejan su uso en sistemas de tiempo real [45]. En la literatura se han presentado t´ecnicas para utilizar predictores de saltos est´aticos en sistemas de tiempo real [24, 26]. Sin embargo, las propuestas para determinar el funcionamiento en el peor caso de algunos predictores de saltos din´amicos son habituales. Por ejemplo, para guardar la historia de ejecuci´on del programa se ha propuesto utilizar una tabla de destinos de saltos (BTB/ Branch Target Buffer). En algunas casos, para predecir el comportamiento de los saltos, se ha simulado est´aticamente el comportamiento del BTB [39]. En otros se ha creado un entorno que permite analizar el WCET en presencia de algunos BTBs particulares [65, 66]. Especial relevancia adquiere la predicci´on de los saltos en bucles y mucho m´as en bucles anidados. Este problema se ha tratado con m´as detalle en diferentes trabajos, donde se presentan m´etodos de an´alisis est´atico para clasificar las instrucciones de salto en el c´odigo fuente, ampliando su an´alisis, tanto a un predictor local (bimodal banch predictor), como a un predictor global (globalhistory branch predictor) [16, 17, 25, 157]. En otros trabajos de investigaci´on se modela el impacto sobre el WCET de un predictor de saltos gen´erico. A partir del grafo de flujo de control se determinan de forma autom´atica el conjunto de restricciones lineales que modela el n´umero de fallos del predictor de saltos. Con estas restricciones, y resolviendo un problema basado en ILP, se calcula el WCET del programa analizado [102, 127, 128]. Se trata en definitiva de maximizar el tiempo de ejecuci´on de cada uno de los bloques b´asicos del programa, teniendo en cuenta los fallos en la predicci´on de los saltos. Si el bloque b´asico no contiene ninguna instrucci´on de salto, el tiempo de ejecuci´on no se ver´a afectado por la predicci´on. Adem´as, este 36 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. modelo tambi´en permite medir el impacto de los fallos de predicci´on en la cache de instrucciones [106]. 2.5. El WCET con caches de instrucciones Uno de los componentes hardware del procesador que m´as influyen en el tiempo de ejecuci´on de una tarea son las memorias cache. Las memorias cache se utilizan para incrementar la velocidad media de acceso a la memoria principal, y por lo tanto reducen significativamente el tiempo de ejecuci´on. Predecir el comportamiento de las memorias cache es esencial para poder calcular una cota del WCET precisa, pero analizar su comportamiento es complejo ya que depende de la historia de ejecuci´on del programa. Las memorias cache son almacenes peque˜nos de r´apido acceso que contienen instrucciones y datos. Las memorias cache se dividen en conjuntos de l´ıneas donde cada l´ınea s´olo puede almacenar un bloque de memoria. Cuando al referenciar a una instrucci´on o a un dato, el bloque que los contiene est´a en la cache, se produce un acierto de cache. En caso contrario, se produce un fallo de cache. Como el tama˜no de la cache es mucho menor que la memoria principal, una l´ınea de cache puede guardar varios bloques de memoria distintos, por lo tanto es necesario definir una funci´on de correspondencia para decidir en que l´ınea de cache se guarda un bloque de la memoria. Existen tres tipos de correspondencia: directa, totalmente asociativa y asociativa por conjuntos. La correspondencia directa asigna a cada bloque de memoria una ´unica l´ınea de cache. Aunque esta correspondencia es simple, si durante la ejecuci´on de un programa se referencia varias veces a instrucciones o datos de bloques diferentes asignados a una misma l´ınea, se producir´an muchos fallos de cache porque dichos bloques se estar´an reemplazando continuamente. La correspondencia totalmente asociativa permite que cada bloque de memoria se pueda cargar en cualquier l´ınea de cache. Pero en este caso, es necesario examinar todas las l´ınea de la cache para ver si la instrucci´on o el dato referenciado est´a en la cache. Finalmente, la correspondencia asociativa por conjuntos es una soluci´on de compromiso, ya que la cache se divide en Sconjuntos de l´ıneas. En este caso un bloque de memoria puede cargarse en un solo conjunto, y dentro de ´este puede hacerlo en cualquiera de sus l´ıneas. El n´umero de l´ıneas wque pertenecen a un conjunto se denominan v´ıas. As´ı pues, la capacidad de una cache asociativa por conjuntos viene determinada por el producto S·w. Lo mismo sucede para una cache de correspondencia directa, que tiene una ´unica v´ıa (w= 1); y para una cache totalmente asociativa, que tiene un ´unico conjunto (S= 1). En la Figura 2.7 se muestra un ejemplo de cada uno de los tipos de correspondencia descritos. CAP´ ITULO 2. 37 Figura 2.7: Posibles tipos de correspondencia entre bloques de memoria y l´ıneas de cache. Cuando se carga un nuevo bloque de memoria en la cache hay que determinar el conjunto en el que se guardar´a dicho bloque, y esto depende del tipo de correspondencia de la cache. As´ı pues, si denotamos con jel n´umero de bloque de memoria principal que se cargar´a en la cache, el conjunto idonde se guardar´a dicho bloque se obtiene mediante la siguiente expresi´on: i=jmod S Pero tambi´en es posible que haya que reemplazar alguna de las l´ıneas del conjunto por el nuevo bloque de memoria. Para una cache de correspondencia directa no hay elecci´on, ya que cada conjunto s´olo tiene una l´ınea de cache. Pero para las caches totalmente asociativas o asociativas por conjuntos, es necesario definir una pol´ıtica de reemplazo para poder seleccionar la l´ınea de cache 38 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. a reemplazar. Existen diferentes algoritmos de reemplazo, no obstante, el m´as efectivo es el algoritmo LRU (Least-Recently Used) que sustituye, dentro de un conjunto, a la l´ınea de cache con el bloque de memoria que m´as tiempo lleva sin ser referenciado. En el caso de que la l´ınea de cache contenga datos, tambi´en se habr´a de tener en cuenta la posibilidad de que dichos datos hayan sido actualizados durante la ejecuci´on, ya que en este caso se debe actualizar la memoria principal. No obstante, existen dos pol´ıticas de escritura en la cache. Por un lado, la escritura inmediata (write through), en la que se actualiza a la vez la l´ınea de cache y el bloque de memoria que contiene el dato, por lo tanto la memoria principal siempre est´a actualizada. Por otro, la escritura retardada (write back), en la que s´olo se actualiza el dato en la cache, y s´olo en caso de que sea reemplazada esa l´ınea se actualiza el bloque de memoria. En definitiva, el funcionamiento de las caches no es f´acilmente predecible en tiempo de compilaci´on. El contenido de sus l´ıneas depende totalmente del camino seguido por el programa durante la ejecuci´on. Determinar est´aticamente las l´ıneas de memoria presentes en la cache en todo instante de ejecuci´on es dif´ıcil, puesto que equivale a calcular en cada referencia a memoria si va a producirse un fallo obligatorio, un fallo de capacidad o un fallo de conflicto [83]. Un fallo de cache obligatorio se produce siempre que se accede por primera vez a un bloque de memoria, ya que ´este no puede estar en la cache. Un fallo de capacidad se produce porque la cache no puede contener todos los bloques del programa a los que se accede durante su ejecuci´on. As´ı pues, algunos de estos bloques son descartados y posteriormente son otra vez solicitados durante la ejecuci´on. Un fallo de conflicto se produce porque algunos bloques son reemplazados por otros, dentro de un mismo conjunto, y luego son otra vez requeridos durante la ejecuci´on. Los fallos de conflicto se producen en caches asociativas por conjuntos o en caches de correspondencia directa. As´ı pues, algunos aciertos en caches totalmente asociativas, son fallos en caches asociativas por conjuntos en funci´on del grado de asociatividad. Los fallos por conflicto son debidos a las interferencias, denominadas interferencias intr´ınsecas de cache, que se producen en la cache durante la ejecuci´on de una tarea. En un sistema multitarea aparecen fallos por conflictos entre las diferentes tareas cuando se produce una expulsi´on, en este caso estos fallos de cache tambi´en se denominan interferencias extr´ınsecas de cache. En el momento en que la tarea, que ha sido expulsada de la CPU, reanude su ejecuci´on, puede ser necesario volver a cargar algunas instrucciones y datos que ten´ıa en la cache antes de la expulsi´on, esto provoca, en la ejecuci´on de la tarea, un retardo adicional (cache-related preemption delay). Las memorias cache en los procesadores de altas prestaciones se organizan en varios niveles integrados en el chip. Hoy en d´ıa podemos encontrar hasta tres niveles integrados, el primero peque˜no y con una latencia de uno o dos ciclos y el resto progresivamente m´as grandes y lentos. En la Tabla 2.2 se muestran algunos ejemplos de procesadores cl´asicos con sus configuraciones de cache. CAP´ ITULO 2. 39 Procesadores de prop´osito general Procesador Arquitectura Cache en chip L1i L1d L2u L3u Intel Itanium 2 Madison Itanium 16KB 16KB 256KB 6MB AMD Opteron IA-32 64KB 64KB 1MB Intel P4 Xeon 96KB 8KB 512KB 6MB Procesadores para sistemas empotrados Procesador Arquitectura Cache en chip L1i L1d L2u L3u IBM PPC 750GX PowerPC 32KB 32KB 1MB PMC-Sierra RM9000*2GL MIPS64 16KB 16KB 256KB ARM 1020E ARM 32KB 32KB F. PowerPC MPC 7448 PowerPC 32KB 32KB Tabla 2.2: Configuraciones de cache integrada en chip en procesadores cl´asicos. L1,L2yL3indican el nivel de cache. Se utiliza ipara instrucciones, dpara datos, upara instrucciones y datos. Los dise˜nadores de sistemas de tiempo real, en una primera aproximaci´on, han decido no utilizar memorias cache, debido a su comportamiento no predecible. No obstante, cuando en el dise˜no del sistema se propone un procesador con caches, se determina el WCET de las tareas asumiendo que cada acceso a memoria ser´a un fallo de cache. Pero el WCET de cada tarea es ampliamente sobrestimado y el an´alisis de planificabilidad puede fallar cuando en realidad el sistema es capaz de cumplir todos sus requisitos temporales. El an´alisis del WCET de una tarea en presencia de memorias cache presenta dos tipos de retos bien distintos. Por un lado, es necesario determinar las interferencias propias de la tarea o interferencias intr´ınsecas, que aparecen cuando durante la ejecuci´on de una tarea, en la cache se reemplazan algunos de sus propios bloques de memoria debido a los fallos de capacidad o de conflicto. Por otro lado, en un sistema multitarea con expulsiones hay que determinar las interferencias que se producen entre las distintas tareas, tambi´en denominadas interferencias extr´ınsecas. Estas interferencias aparecen cuando, durante la ejecuci´on de una tarea, en la cache se reemplazan bloques de memoria que pertenecen a otras tareas del sistema [14]. En la literatura se han estudiado ampliamente ambas cuestiones. Para determinar las interferencias intr´ınsecas se ha modelado el comportamiento de la cache en el peor caso, cuando las tareas se ejecutan de forma aislada, y para determinar las interferencias extr´ınsecas se ha calculado el retardo adicional en el tiempo de ejecuci´on de la tarea, que se puede producir si es necesario cargar algunas instrucciones y datos que fueron expulsados durante la ejecuci´on de otras tareas. 40 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. No obstante, la obtenci´on de una cota ajustada y segura del WCET de una tarea en presencia de memorias cache, depende de la exactitud de la predicci´on de su funcionamiento. Es decir, se debe predecir si el acceso a una instrucci´on o dato ser´a un acierto o un fallo, asumiendo fallo en caso de duda. Interferencias extr´ınsecas y planificabilidad En este apartado se comentan algunas de las propuestas m´as interesantes para determinar, en un sistema multitarea, el impacto producido por las interferencias extr´ınsecas de la cache sobre el WCET de una tarea. Una primera aproximaci´on, suponiendo conocido el WCET de una tarea que se ejecuta de forma aislada Ci, a˜nade dos nuevos t´erminos constantes en el an´alisis de planificabilidad del sistema [14]. El primer t´ermino est´a asociado al coste de los cambios de contexto δque se producen en los sistemas multitarea [129]. El segundo t´ermino est´a asociado al retardo adicional γque se producir´a como consecuencia de las interferencias extr´ınsecas de la cache. Por lo tanto, el nuevo WCET de la tarea C0 iqueda determinado por la siguiente ecuaci´on: C0 i=Ci+ 2δ+γ(2.1) As´ı pues, la expresi´on que calcula la utilizaci´on del procesador U, y en definitiva proporciona una condici´on suficiente para determinar la planificabilidad de un sistema con prioridades est´aticas planificado mediante RM (Rate Monotonic) [111], tambi´en se debe modificar como se muestra en la siguiente ecuaci´on: U= N X i=i C0 i Di ≤N·21 N−1(2.2) La Ecuaci´on 2.2 es una condici´on suficiente pero no necesaria, por lo que este an´alisis de planificabilidad introduce cierto pesimismo, ya que un sistema puede ser planificable sin verificar dicha expresi´on. As´ı pues, tambi´en se ha propuesto analizar el tiempo de respuesta Ride cada tarea Taskidel sistema utilizando RTA (Response Time Analysis) [27, 78, 87, 111]. Es decir, las tareas de un sistema verifican sus restricciones temporales si Ri≤Di,∀i, siendo Disu plazo de finalizaci´on. Para ello, es necesario modificar el WCET de las tareas que pueden expulsar a la tarea analizada Taskia˜nadiendo la penalizaci´on por la recarga de la cache, como se indica en la siguiente ecuaci´on recursiva que permite calcular el tiempo de respuesta de cada tarea del sistema teniendo en cuenta dicha penalizaci´on. Rn+1 i=Ci+X j∈hp(i)Rn i Dj·(Cj+γj) (2.3) CAP´ ITULO 2. 41 La principal dificultad de las propuestas, que estudian el tiempo de respuesta, reside en determinar de una forma m´as precisa la penalizaci´on por la recarga de la cache, aunque el an´alisis de planificabilidad es equivalente al propuesto inicialmente [27, 78, 87, 111]. A continuaci´on se enumeran algunas de las propuestas para obtener la penalizaci´on por la recarga de la cache en un cambio de contexto: Considerar el tiempo de recarga de la cache completa. Calcular el tiempo de recarga de los bloques reemplazados por la tarea preferente. Determinar el tiempo de recarga de los bloques activos de la tarea expulsada. Determinar el tiempo de recarga para el m´aximo n´umero de bloques activos que puede tener la tarea expulsada en cada instante. Considerar el tiempo de recarga de los bloques de cache compartidos entre la tarea expulsada y la preferente. La penalizaci´on por recarga m´as sencilla de obtener es calcular el tiempo de recarga de la cache completa, ya que en cualquiera de los otros casos enumerados es necesario tener un conocimiento m´as detallado del contenido de la cache en cada instante de la ejecuci´on del sistema. Esta penalizaci´on es la mayor que se debe considerar, y puede hacer que el an´alisis de planificabilidad falle. As´ı pues, en los primeros trabajos de investigaci´on ya se opt´o por utilizar como penalizaci´on el tiempo de recarga de los bloques reemplazados por la tarea preferente [29, 32, 30]. Sin embargo, en trabajos posteriores se han mejorado y calculado cotas m´as precisas del tiempo de recarga de la cache en los cambios de contexto [100, 101, 139, 170, 171]. Por ejemplo, en un sistema de prioridades fijas se ha propuesto analizar los estados de la cache cuando una tarea es expulsada, y los estados de la cache asociados a las tareas que se ejecutar´an durante su expulsi´on [100, 101]. De esta forma, se determina una cota m´as ajustada del tiempo de recarga de la cache, ya que por un lado se obtiene el tiempo de expulsi´on en cada punto del programa, teniendo en cuenta el estado o contenido de la cache, y por otro se consigue el n´umero de expulsiones y los puntos de expulsi´on en el peor caso. Tambi´en son de inter´es, las propuestas que analizan los posibles caminos de ejecuci´on para determinar los estados de cache asociados a la tarea expulsada y a la tarea preferente [139, 170, 171]. Este an´alisis de los estados de cache asociados a los caminos permite obtener de una forma m´as exacta el tiempo de penalizaci´on por recarga de la cache. En concreto, proponen calcular la penalizaci´on, como el tiempo de recarga de las l´ıneas de cache compartidas entre la tarea expulsada y la preferente. Aunque esta propuesta supone que las posibles 42 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. expulsiones s´olo tienen lugar al final de cada bloque b´asico, esta simplificaci´on queda perfectamente justificada [170, 171]. No obstante, a pesar de estas consideraciones, sigue siendo dif´ıcil conseguir un tiempo de penalizaci´on ajustado por recarga de la cache en sistemas multitarea con expulsiones. As´ı pues, para evitar el problema de las interferencias extr´ınsecas de cache, tambi´en se han propuesto m´etodos para repartir o dividir la cache (cache partitioning) entre las diferentes tareas del sistema [91, 92, 202]. Se trata de asignar a cada tarea una porci´on o trozo de la cache para su uso exclusivo. Obviamente, al dividir la cache se eliminan las interferencias extr´ınsecas, pero pueden aumentar las interferencias intr´ınsecas, ya que el tama˜no de cache disponible para cada tarea se reduce considerablemente, por lo tanto podr´ıa aumentar el n´umero de fallos de cache y tambi´en el WCET de las tareas. Pero determinar el tama˜no de cache m´as adecuado que se asignar´a a cada tarea del sistema es un problema NP-completo y suele ser habitual dividir la cache en trozos iguales. Por lo tanto, todas las tareas, independientemente de su prioridad, estructura y tama˜no, disponen de un trozo de cache de igual capacidad. Finalmente tambi´en tienen inter´es las t´ecnicas h´ıbridas que combinan, por un lado la divisi´on de la cache entre algunas tareas, y por otro el c´alculo del tiempo de recarga de la cache para las tareas que comparten un mismo trozo, como se propone en [31]. An´alisis est´atico de la cache Modelar de forma est´atica el comportamiento en el peor caso de una cache de instrucciones es dif´ıcil, ya que es necesario predecir como ser´an todos los accesos a memoria durante la ejecuci´on del programa. A continuaci´on, para un sistema de tiempo real, se describen algunas t´ecnicas de an´alisis est´atico que modelan el comportamiento de una cache de instrucciones con algoritmo de reemplazo LRU. El an´alisis est´atico del comportamiento en el peor caso de la cache siempre es seguro, pero este an´alisis, que es pesimista por definici´on, puede a˜nadir una importante sobrestimaci´on si no se tiene en cuenta la historia de ejecuci´on del programa. Una vez clasificados todos los accesos a memoria, el tiempo de ejecuci´on en el peor caso de cada bloque b´asico del programa que se obtiene es seguro, aunque su precisi´on depende de la exactitud en la predicci´on de los accesos a memoria realizados en el peor caso. En la literatura se han propuesto dos t´ecnicas diferentes para analizar el comportamiento en el peor caso de la cache de instrucciones. La primera de las t´ecnicas utiliza la simulaci´on est´atica de la cache (SCS/ Static Cache Simulation) para clasificar en el peor caso los accesos a la cache de instrucciones [9, 79, 82, 108, 131, 132, 133, 134, 137, 136]. La segunda t´ecnica utiliza la interpretaci´on abstracta para analizar formalmente el comportamiento en el CAP´ ITULO 2. 49 tarea en un sistema de tiempo real. La primera t´ecnica propone bloquear la cache durante toda la ejecuci´on del sistema. En la literatura, esta t´ecnica se conoce como static loking cache. La segunda t´ecnica propone fijar el contenido de la cache durante algunos periodos de la ejecuci´on del sistema, por lo tanto su contenido puede ser actualizado bajo algunas circunstancias especiales. En la literatura, a esta t´ecnica se la denomina dynamic locking cache. Fijar el contenido durante toda la ejecuci´on Fijar el contenido de la cache durante toda la ejecuci´on del sistema permite utilizar caches en sistemas de tiempo real multitarea. No obstante, para poder fijar su contenido, es necesario realizar un an´alisis est´atico y determinar los contenidos a cargar en la cache durante el arranque del sistema, para despu´es bloquear su contenido. La predicci´on del funcionamiento de la cache es totalmente segura y exacta, ya que su contenido no cambia durante toda la vida del sistema. Sin embargo su rendimiento se reduce considerablemente, ya que todas las tareas comparten la cache simult´aneamente y su contenido no puede ser actualizado. En la literatura se han propuesto diferentes t´ecnicas para seleccionar los contenidos a fijar en la cache. En algunos trabajos se ha propuesto la utilizaci´on de algoritmos gen´eticos [117, 118, 120, 121, 122, 124]. El objetivo de los algoritmos gen´eticos es seleccionar las l´ıneas de memoria que se deben cargar en la cache para que el tiempo de ejecuci´on de cada tarea del sistema sea el menor posible. Pero el coste computacional de estos algoritmos gen´eticos suele ser muy alto y, aunque los resultados obtenidos pueden ser interesantes, la selecci´on propuesta no tiene por qu´e ser la mejor. En sistemas multitarea con expulsiones, tambi´en se han propuesto algoritmos de baja complejidad cuyo objetivo se centra en reducir la utilizaci´on del procesador para cada una de las tareas del sistema. Adem´as, esto permite que el tiempo de respuesta de cada tarea sea mucho m´as preciso [8, 146, 147]. El principal objetivo de estos algoritmos de baja complejidad es conseguir que un sistema sin cache de instrucciones que no es planificable, lo sea utilizando una cache que pueda fijar su contenido durante toda la vida del sistema. En concreto, se han propuesto dos tipos de algoritmos: por un lado, se han seleccionado las l´ıneas de memoria con el mayor n´umero de accesos, para minimizar la utilizaci´on del procesador Lock-MU (Algorithm for Minimize Utilization); y por otro se ha intentado minimizar las interferencias entre las diferentes tareas del sistema Lock-MI (Algorithm for Minimize Interferentes). Aunque los resultados mostrados son muy parecidos, el algoritmo Lock-MU siempre obtiene mejores resultados que el algoritmo Lock-MI [147]. Sin embargo el conjunto de l´ıneas a fijar en la cache, propuesto por estos algoritmos, no es la soluci´on ´optima al problema, aunque consigan que el sistema sea planificable. As´ı pues, con una 50 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. selecci´on adecuada de las l´ıneas a fijar en la cache, se obtiene un WCET seguro y m´as preciso para cada una de las tareas, haciendo que el sistema tambi´en sea planificable. Finalmente los algoritmos gen´eticos se han comparado con los algoritmos de baja complejidad [123]. Los algoritmos gen´eticos analizan cada tarea del sistema de forma individual, mientras que los algoritmos de baja complejidad tienen en cuenta el sistema completo. Aunque los resultados de ambas propuestas puedan parecer equivalentes, el coste computacional de los algoritmos gen´eticos es mucho mayor que el coste computacional de Lock-MU yLock-MI. Fijar el contenido durante algunos periodos de la ejecuci´on Como ya se ha comentado anteriormente, fijar la cache durante toda la ejecuci´on del sistema lleva asociada una importante p´erdida en su rendimiento. Por un lado, al fijar su contenido se restringe su funcionamiento habitual, por otro se comparte la cache entre todas las tareas del sistema a la vez. As´ı pues, tambi´en es interesante fijar el contenido de la cache durante algunos periodos de la ejecuci´on del sistema, por ejemplo cuando se ejecutan las tareas. Mientras, en los cambios de contexto, el contenido de la cache se actualizar´a para que cada tarea pueda aprovechar toda la capacidad de la cache y su comportamiento sea m´as din´amico, como se propone en varios trabajos [117, 119, 120, 122, 173]. Pero en ninguno de estos trabajos se ha presentado una soluci´on ´optima para seleccionar los contenidos a fijar en la cache durante la ejecuci´on particular de cada tarea del sistema. Bloquear el contenido de la cache durante algunos periodos de la ejecuci´on puede mejorar de forma significativa el rendimiento del sistema. Pero en general, el an´alisis est´atico que selecciona las l´ıneas de memoria, que se cargar´an y bloquear´an en la cache en cada cambio de contexto, debe ser m´as detallado para cada tarea del sistema, y por lo tanto ser´a m´as complejo. Por ejemplo, si en cada cambio de contexto se permite actualizar el contenido de la cache, la tarea que reanude su ejecuci´on podr´a aprovechar toda la cache. Sin embargo, cuando se realice el an´alisis de planificabilidad es necesario tener en cuenta el coste de cargar las l´ıneas de memoria de cada tarea en la cache, antes de volver a bloquear su contenido. Contenidos a fijar en la cache En la Figura 2.10 se presenta un ejemplo con los posibles contenidos a fijar en una cache con 4 conjuntos de correspondencia directa. En la parte superior de la figura se muestran las l´ıneas de memoria asociadas a las dos tareas Task1 yTask2que forman un sistema de tiempo real. La tarea Task1contiene un condicional con dos posibles caminos de ejecuci´on dentro de un bucle. En el CAP´ ITULO 2. 51 Figura 2.10: Posibles contenidos a fijar en la cache: durante toda la ejecuci´on del sistema vs. durante la ejecuci´on de cada tarea. ejemplo, el n´umero de iteraciones del bucle es 150. La tarea Task2contiene un bucle de 100 iteraciones con un ´unico camino de ejecuci´on. En la Figura 2.10 se han marcado las l´ıneas de memoria m´as adecuadas para bloquear en la cache, pero debido a su capacidad, no es posible fijar todas estas l´ıneas a la vez. Supongamos que el contenido de la cache se fijar´a durante toda la ejecuci´on del sistema. Una posible selecci´on de l´ıneas de memoria a fijar en la cache podr´ıa ser la formada por las l´ıneas line2yline9de la tarea Task1y las l´ıneas line3 yline4de la tarea Task2, como se muestra en la parte inferior izquierda de la Figura 2.10. Se han seleccionado las l´ıneas de memoria a las que m´as veces se accede durante la ejecuci´on. No se han elegido m´as l´ıneas de la tarea Task1 porque no se conoce con exactitud el n´umero de accesos a dichas l´ıneas, ya que depende del camino seguido durante la ejecuci´on. Aunque ya se puede predecir 52 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. de forma exacta el comportamiento de la cache, la tarea Task2no puede aprovechar toda la cache. Adem´as, es posible que esta selecci´on no sea la ´optima, por ejemplo cuando la rama izquierda o la rama derecha del condicional de la tarea Task1se ejecute m´as de 100 veces. Supongamos ahora que la cache quedar´a fijada durante la ejecuci´on de cada tarea y que en los cambios de contexto podemos actualizar su contenido. En este caso, para calcular un WCET preciso, es necesario tener en cuenta el coste de actualizar el contenido de la cache cuando una tarea comience o reanude su ejecuci´on. Una posible selecci´on de l´ıneas de memoria a fijar en la cache durante la ejecuci´on de la tarea Task1y de la tarea Task2se muestra en la parte inferior derecha de la Figura 2.10. De nuevo se han seleccionado las l´ıneas de memoria, de cada tarea, a las que m´as veces se acceder´a durante la ejecuci´on. En este caso, la selecci´on de l´ıneas de memoria de la tarea Task2es la ´optima. Pero no ocurre lo mismo con la selecci´on de l´ıneas de la tarea Task1, ya que no se conoce el n´umero de veces que se ejecuta cada uno de los caminos del condicional. En este caso se ha optado por elegir una l´ınea de memoria de cada camino. En definitiva, bloquear la cache, durante algunos periodos de la ejecuci´on del sistema, permite su utilizaci´on de una forma m´as din´amica en sistemas de tiempo real, ya que su predicci´on sigue siendo segura aunque resulte m´as dif´ıcil seleccionar las l´ıneas de cada tarea a fijar en la cache, durante su ejecuci´on. Sin embargo, es necesario tener en cuenta el coste de actualizar el contenido de la cache para obtener de forma precisa el WCET de cada tarea. 2.6. Conclusiones El an´alisis y c´alculo del WCET es complejo y dif´ıcil. As´ı pues, los trabajos de investigaci´on que tratan este problema se centran en algunos aspectos concretos del an´alisis. En la literatura se han propuesto t´ecnicas de an´alisis de flujo de control, an´alisis del comportamiento del procesador y t´ecnicas para medir el tiempo de ejecuci´on de un programa. El WCET obtenido mediante las t´ecnicas basadas en medida no es seguro. Las t´ecnicas de an´alisis est´atico son seguras, pero en algunas ocasiones sobrestiman el c´alculo del WCET. Para obtener un WCET preciso y seguro, es necesario analizar est´aticamente, tanto la estructura del programa mediante el an´alisis de flujo de control, como el comportamiento en el peor caso de los componentes hardware del procesador. Uno de los componentes hardware m´as utilizados en los procesadores actuales son las memorias cache. Las memorias cache reducen la media del tiempo de acceso a la memoria principal. Pero predecir su comportamiento en el peor caso es complejo, ya que depende de la historia de ejecuci´on. Para analizar el comportamiento en el peor caso de las memorias cache es necesario tener en cuenta, tanto las interferencias intr´ınsecas, como las interferencias extr´ınsecas CAP´ ITULO 2. 53 de la cache. Para resolver el problema de las interferencias intr´ınsecas de cache, en la literatura se han propuesto t´ecnicas como la simulaci´on est´atica de la cache, o m´etodos basados en la interpretaci´on abstracta. Estas t´ecnicas de an´alisis son seguras y permiten determinar la contribuci´on al WCET de los accesos a memoria, pero en muchas ocasiones esta contribuci´on es sobrestimada. En el Cap´ıtulo 3, cuando el n´umero de caminos condicionales dentro de un bucle no es grande, presentamos una t´ecnica para determinar la contribuci´on exacta al WCET de los accesos a memoria. En este cap´ıtulo tambi´en comparamos nuestros resultados con los resultados obtenidos mediante la simulaci´on est´atica de la cache (SCS/ Static Cache Simulation) [134]. Con el objeto de resolver el problema de las interferencias extr´ınsecas de cache, en la literatura se han propuesto m´etodos para medirlas. Tambi´en se ha propuesto la utilizaci´on de caches que puedan fijar su contenido durante toda la ejecuci´on del sistema o durante algunos periodos concretos de la misma. En el Cap´ıtulo 4 presentamos un algoritmo Lock-MS (Lock for Maximize Schedulability) para seleccionar la l´ıneas a fijar en la cache. Para una jerarqu´ıa de memoria formada por un almac´en de l´ınea (LB/ Line Buffer) y una cache que puede fijar su contenido (Lockable iCache), el algoritmo Lock-MS consigue maximizar la planificabilidad del sistema. En el Cap´ıtulo 5 a˜nadimos a la jerarqu´ıa de memoria una preb´usqueda secuencial que reduce considerablemente el WCET de las tareas mejorando a´un m´as la planificabilidad del sistema. Adem´as, tanto en el Cap´ıtulo 4, como en el Cap´ıtulo 5 comparamos los resultados conseguidos mediante el algoritmo Lock-MS, cuando se permite actualizar el contenido de la cache en los cambios de contexto, con los resultados obtenidos mediante el algoritmo Lock-MU (Algorithm for Minimize Utilization) cuando se fija la cache durante toda la ejecuci´on del sistema [147]. 54 2. AN ´ ALISIS Y C ´ ALCULO DEL WCET. Cap´ıtulo 3 El WCET con caches en caminos relevantes Un sistema de tiempo real est´a formado por un conjunto de tareas que cooperan con el fin de conseguir un objetivo. Para garantizar que las tareas se ejecuten siempre en un determinado plazo de tiempo, es necesario definir algoritmos o pol´ıticas de planificaci´on que determinan si las restricciones temporales del sistema se pueden satisfacer. Por lo tanto, antes de poner en funcionamiento un sistema de tiempo real es necesario realizar un an´alisis de planificabilidad que tenga en cuenta: las tareas del sistema, sus plazos de finalizaci´on, sus periodos de ejecuci´on y su tiempo de ejecuci´on en el peor caso. Es decir, cualquier an´alisis de planificabilidad depende del WCET de cada una de las tareas del sistema. En este cap´ıtulo se describe una t´ecnica de an´alisis para determinar de forma exacta el coste de los accesos a memoria en presencia de una cache de instrucciones con algoritmo de reemplazo LRU (Least Recently Used). El algoritmo de reemplazo LRU es totalmente determinista, por lo tanto est´a perfectamente indicado en un sistema de tiempo real, ya que evita cualquier incertidumbre respecto al contenido de la cache durante la ejecuci´on de la tarea [154]. La base de esta nueva propuesta reside en analizar todos los caminos de ejecuci´on que pueden alcanzar el WCET, descartando, sin p´erdida de informaci´on, todos aquellos caminos sobre los que durante el an´alisis se pueda asegurar que en ning´un caso determinar´an el WCET. En los experimentos realizados se ha verificado que mediante esta propuesta se reduce espectacularmente el n´umero de caminos que se deben analizar de principio a fin para determinar el WCET del programa. As´ı pues, en presencia de una cache de instrucciones convencional, si el n´umero de caminos condicionales dentro de los bucles en un programa no es demasiado grande, es posible computacionalmente analizar de forma exacta el coste de los accesos a memoria en el peor caso. 55 56 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. 3.1. Caminos de ejecuci´on en bucles con condicionales Determinar la contribuci´on exacta al WCET de los accesos a memoria, en presencia de una cache de instrucciones, es muy costoso debido a la complejidad exponencial del problema, ya que es necesario analizar todos y cada uno de los posibles caminos de ejecuci´on del programa. Por ejemplo, en un bucle de 100 iteraciones que contenga un condicional con dos caminos se generan 2100 caminos de ejecuci´on diferentes. Puesto que el contenido de la cache depende del camino seguido durante la ejecuci´on, conocer el contenido de la cache en cada instante hace que el problema sea demasiado complejo computacionalmente, tanto en tiempo, como en espacio. En la Figura 3.1 se muestra con un ejemplo sencillo la dificultad que conlleva calcular el WCET exacto de un bucle con un condicional. Teniendo en cuenta el comportamiento de una cache de instrucciones, en la Tabla 3.1 se indica el tiempo de ejecuci´on asociado a los caminos A y B que forman el bucle de la Figura 3.1 a). Casos de Ejecuci´on Camino A Camino B Primera ejecuci´on 30 40 Ejecuciones alternativas 20 28 Dos ejecuciones consecutivas 10 14 Tabla 3.1: Coste de ejecuci´on con una cache de instrucciones. La primera fila de la Tabla 3.1 indica el coste de la primera ejecuci´on de cada uno de los caminos cuando la cache est´a vac´ıa. En la segunda fila se muestra el coste de ejecuci´on de cada uno de los caminos cuando en la iteraci´on anterior del bucle se ejecut´o el otro camino, es decir, primero se ejecuta el camino A y despu´es el B o primero se ejecuta el camino B y despu´es el A. En la tercera fila se indica el coste de la ejecuci´on de cada uno de los caminos cuando en la iteraci´on anterior del bucle se ejecut´o ese mismo camino. Una vez clasificados todos los accesos a memoria de las instrucciones, se determina el tiempo de ejecuci´on de cada bloque b´asico, y finalmente se calcula el WCET del programa, por ejemplo a partir del ´arbol sint´actico que se puede obtener durante el proceso de compilaci´on. La Figura 3.1 b) muestra el c´alculo del WCET en presencia de una cache de instrucciones donde s´olo aprovechamos su localidad espacial, es decir, suponemos que no sabemos predecir la localidad temporal. Finalmente, en la Figura 3.1 c) se indica el c´alculo exacto del WCET considerando todos los caminos posibles de ejecuci´on, aunque s´olo se muestran las 4 primeras iteraciones del bucle. CAP´ ITULO 3. 57 Figura 3.1: C´alculo del WCET en un bucle con un condicional. 58 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. La diferencia en el WCET obtenido es considerable, por lo tanto no es una buena estrategia simplificar excesivamente dicho an´alisis y mucho menos descartar la utilizaci´on de caches en sistemas de tiempo real. En la siguiente secci´on se demuestra que, para determinar la contribuci´on exacta al WCET de los accesos a memoria, en presencia de una cache de instrucciones convencional, el n´umero de caminos que se deben analizar est´a acotado, y en general es mucho m´as peque˜no que el n´umero de posibles caminos de ejecuci´on de la tarea. Esto permite realizar un an´alisis exacto del comportamiento, en el peor caso, de la cache de instrucciones, siempre y cuando el n´umero de caminos que deben ser analizados no sea excesivamente grande. 3.2. N´umero m´aximo de caminos relevantes Como aparece en la Figura 3.1 c), durante el an´alisis del WCET se produce una explosi´on combinatoria de los posibles caminos de ejecuci´on que puede seguir un programa debido a las estructuras condicionales dentro de bucles. Por lo tanto, es necesario acotar el n´umero de caminos posibles de ejecuci´on de la tarea en estas estructuras de programaci´on. Por ejemplo, en un bucle de niteraciones con un condicional, el n´umero de caminos posibles de ejecuci´on es pndonde p representa el n´umero de caminos del condicional. No obstante, si se analizan los diferentes estados de cache que se pueden alcanzar durante la ejecuci´on de todos estos caminos, es decir, si se analiza el contenido de la cache, se observa que muchos de estos estados son iguales. Por lo tanto, para determinar el coste de los accesos a memoria de la tarea s´olo ser´a necesario considerar aquellos estados de cache que sean diferentes. Adem´as, para calcular el WCET de un bucle ser´a suficiente considerar los caminos con el mayor tiempo de ejecuci´on acumulado para cada uno de los estados diferentes de cache alcanzados durante el an´alisis. As´ı pues, se trata de analizar ´unicamente los caminos relevantes, que son aquellos caminos que acumulan el mayor tiempo de ejecuci´on para cada estado diferente de cache alcanzado hasta un determinado punto del programa. En esta secci´on se demuestra que, en presencia de una cache de instrucciones con algoritmo de reemplazo LRU, el n´umero m´aximo de caminos relevantes en un bucle con un condicional est´a acotado por la siguiente expresi´on, en la que n es el n´umero de iteraciones del bucle y prepresenta el n´umero de caminos de la estructura condicional. min(p,n) X i=1 Pi p= min(p,n) X i=1 p! (p−i)! (3.1) En general, el n´umero de iteraciones de un bucle suele ser mucho mayor que el n´umero de caminos de las estructuras condicionales y, aunque la Ecuaci´on 3.1 CAP´ ITULO 3. 65 de iteraciones del bucle. Adem´as, para determinar el WCET del programa no es necesario analizar todas la iteraciones del bucle L, es suficiente con analizar las dloge(p!)e+p primeras iteraciones del bucle. Corolario 3. Dada una estructura condicional, con pcaminos de ejecuci´on diferentes, dentro de un bucle Lde niteraciones, el n´umero m´aximo de estados distintos de cache que se pueden alcanzar para una cache asociativa por conjuntos est´a acotado por: min(p,n) X i=1 Pi p Es decir, el n´umero de estados diferentes de cache que se pueden conseguir, en un bucle que contiene pcaminos de ejecuci´on diferentes, no depende del grado de asociatividad de la cache. Corolario 4. Dada una estructura condicional, con pcaminos de ejecuci´on alternativos, dentro de un bucle Lnde niteraciones, donde a su vez el bucle Ln est´a incluido en otro bucle Lmde miteraciones, el n´umero m´aximo de estados diferentes de cache que se pueden alcanzar en este bucle anidado est´a acotado por la siguiente expresi´on: min(p, n·m) X i=1 Pi p Es decir, los resultados de los corolarios anteriores se pueden aplicar directamente en bucles anidados. Corolario 5. Dados Nestados diferentes de cache, si durante el an´alisis del WCET alcanzamos un bucle de miteraciones que contiene una estructura condicional con pcaminos de ejecuci´on alternativos, el n´umero m´aximo de estados diferentes de cache que se pueden lograr al final del bucle est´a acotado por la siguiente expresi´on: N· min(p,m) X i=1 Pi p 3.3. Contribuci´on exacta de los accesos a memoria al WCET En esta secci´on se describe el funcionamiento de un nueva t´ecnica de an´alisis y c´alculo del WCET que permite calcular la contribuci´on exacta de los accesos a 66 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. memoria de una tarea en presencia de una cache de instrucciones con algoritmo de reemplazo LRU. Esta t´ecnica explora todos los caminos posibles de ejecuci´on de una tarea podando o descartando, de forma segura y sin perder informaci´on, los caminos de ejecuci´on que no puedan determinar en ning´un caso el WCET. Para describir esta t´ecnica de an´alisis se considera un procesador sencillo que dispone de una cache de instrucciones. Es decir, el procesador no es segmentado, no dispone de predictor de saltos ni de cache de datos. La t´ecnica predice el coste de fetch de cada una de las instrucciones de todos los caminos de ejecuci´on que pueden alcanzar el WCET del programa. Esta propuesta tambi´en permite estudiar c´omo afecta al WCET un fallo en la predicci´on del coste de un acceso a una instrucci´on en el camino m´as largo. Adem´as, para evitar cualquier tipo de p´erdida de informaci´on durante el an´alisis, se han integrado el an´alisis de flujo de control, el comportamiento del procesador y el propio c´alculo del WCET de todos los caminos relevantes. El WCET obtenido, en este procesador sencillo, es exacto y se determina en un ´unico paso, es decir, de forma integral. Esta t´ecnica de an´alisis basa su funcionamiento en seguir el flujo de control del programa, decodificando en secuencia las instrucciones y siguiendo el camino indicado por los saltos obligatorios. Sin embargo, el programador debe a˜nadir las indicaciones necesarias para tratar de la forma m´as adecuada y correcta las instrucciones de salto condicional. Por ejemplo, debe indicar el n´umero de iteraciones cuando el condicional est´a asociado a un bucle, y tambi´en especificar el descarte del an´alisis de una de las ramas del condicional, cuando representa un camino imposible1. Si en una instrucci´on de salto condicional no hay ning´un tipo de anotaci´on, el an´alisis se divide, ya que debemos analizar todos los caminos posibles de ejecuci´on. A partir de ese instante, se estudian los dos posibles caminos de ejecuci´on por separado de forma totalmente independiente. Pero, como ya se ha mostrado anteriormente, si la instrucci´on condicional est´a dentro de un bucle, en unas cuantas iteraciones, el an´alisis ser´a inviable ya que el n´umero de caminos posibles de ejecuci´on crece exponencialmente. Para evitar la complejidad exponencial del an´alisis debemos aplicar la teor´ıa desarrollada en la secci´on anterior (Secci´on 3.2). As´ı pues, para analizar el comportamiento de la cache de instrucciones tambi´en se debe guardar el estado de cache asociado a cada uno de los posibles caminos de ejecuci´on. Adem´as, antes de iniciar el an´alisis, es necesario marcar las instrucciones poda para detener dicho an´alisis y comparar los estados de cache de todos los caminos que alcanzan estas instrucciones poda. Si en una instrucci´on poda dos o m´as caminos tienen el mismo estado de cache, se podan o descartan todos aquellos caminos que acumulen el menor tiempo de ejecuci´on hasta ese instante. Estos caminos no son relevantes, ya que en ning´un caso pueden llegar a determinar el WCET. Para cada estado diferente de cache, s´olo el camino con mayor tiempo de ejecuci´on 1Esta t´ecnica permite descartar del an´alisis los caminos imposibles a˜nadiendo las anotaciones oportunas en las estructuras condicionales, pero no los puede reconocer. CAP´ ITULO 3. 67 acumulado puede alcanzar el WCET del programa. Como la arquitectura del procesador considerada es sencilla, sin perdida de informaci´on podemos aplicar el Corolario 1. Es decir, para determinar el coste exacto de los accesos a memoria s´olo es necesario analizar los caminos relevantes. Como ejemplo, en la Figura 3.3 se muestra el c´odigo en lenguaje C de un programa y su c´odigo ensamblador generado con GCC 2.95.2 -O2 para ARM v7. En el c´odigo ensamblador se han marcado los caminos de ejecuci´on. En este caso, el programa puede seguir dos posible caminos durante la ejecuci´on. Tambi´en se han marcado las instrucciones de saltos condicionales y obligatorios. En particular, se ha marcado la instrucci´on condicional asociada al bucle indicando el n´umero de iteraciones. Finalmente, el conjunto de posibles instrucciones poda m´as eficientes se ha indicado mediante llaves. Por lo tanto, modificando adecuadamente una herramienta de simulaci´on, como por ejemplo SimpleScalar [12], para que siga las indicaciones marcadas por el programador, se puede conseguir el WCET exacto del programa. Aunque no se ha definido una pol´ıtica para determinar la elecci´on m´as adecuada de las instrucciones poda, y cualquier instrucci´on com´un a varios caminos podr´ıa ser marcada como tal, parece obvio que el coste computacional de esta t´ecnica din´amica de poda depende, tanto del n´umero de instrucciones poda, como de su efectividad. Puesto que el n´umero de caminos relevantes en los bucles con condicionales est´a acotado, como se demostr´o en la Proposici´on 3, podar o eliminar durante el an´alisis los caminos no relevantes tiene especial importancia en estas estructuras de programaci´on. As´ı pues, es necesario marcar como instrucci´on poda alguna de las instrucciones al final del bucle, para que en cada iteraci´on podamos eliminar el mayor n´umero de caminos posibles de ejecuci´on y s´olo se analicen los caminos relevantes. Por otro lado, cuantos m´as estados de cache sean comparados en las instrucciones poda, mayor n´umero de caminos no relevantes pueden ser descartados. Por lo tanto, tambi´en es interesante marcar instrucciones poda al final de los bloques b´asicos que contengan muchas instrucciones, ya que todos los caminos que ejecuten estos bloques b´asicos alcanzar´an estados de cache muy parecidos y la poda puede llegar a ser verdaderamente efectiva. Si consideramos de nuevo el ejemplo representado en la Figura 3.1 a), se puede observar gr´aficamente en la Figura 3.4 el funcionamiento de la t´ecnica de poda din´amica presentada. En la Figura 3.4 a) se representa el tiempo de ejecuci´on acumulado hasta ese instante para cada uno de los posibles caminos de ejecuci´on y su estados de cache asociados. En la Figura 3.4 b) se pone de manifiesto la efectividad de la poda a la hora de reducir el n´umero de caminos relevantes durante el an´alisis. En ambas figuras se observa que el n´umero m´aximo de caminos analizados en cualquier instante siempre se puede reducir a 4, cifra que coincide con la cota establecida en la Proposici´on 3. Tambi´en puede ser interesante marcar otras instrucciones poda, aunque la 68 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. @ Generated by gcc 2.95.2 19991024 (release) for ARM/elf .file "programa.c" gcc2_compiled.: .global n .data .align 2 .type n,object .size n,4 n: .word 10 .global z .align 2 .type z,object .size z,4 z: .word 0 .text .align 2 .global main .type main,function main: @ args = 0, pretend = 0, frame = 0 @ frame_needed = 1, current_function_anonymous_args = 0 @ 000 mov ip, sp @ 004 stmfd sp!, {fp, ip, lr, pc} @ 008 sub fp, ip, #4 @ 012 mov r1, #0 @ 016 mov lr, r1 @ 020 mov r2, r1 @ 024 mov r0, r2 @ 028 ldr ip, .L10 .L6: @ 032 add r3, r2, #1 @ 036 cmp r3, #5 @ 040 mov r2, r3 @ 044 bgt .L7 < Condicional > @ 048 add lr, lr, #1 @ 052 add r1, r1, #2 @ 056 ldr r3, [ip, #0] @ 060 add r0, r0, #3 @ 064 add r3, r3, #4 @ 068 str r3, [ip, #0] @ 072 b .L8 < Obligatorio > .L7: @ 076 mov r1, r1, asl #1 @ 080 mov r0, r0, asl #2 .L8: @ 084 ldr r3, [ip, #0] @ 088 cmp r2, #9 @ 092 add r3, r3, lr Posibles @ 096 add r3, r3, r1 instrucciones poda @ 100 add r3, r3, r0 @ 104 str r3, [ip, #0] @ 108 ble .L6 [ Bucle : 9 ] @ 112 ldmea fp, {fp, sp, pc} .L11: .align 2 .L10: .word z .Lfe1: .size main,.Lfe1-main .ident "GCC: (GNU) 2.95.2 19991024 (release)" /* programa.c */ int n = 10; int z = 0; int main() { int i, j; int v, x, y; v = 0; x = 0; y = 0; for (i = 0; i < 10; i++) { j = i + 1; if (j <= 5) { v = v + 1; x = x + 2; y = y + 3; z = z + 4; } else { x = x * 2; y = y * 4; } z = z + v + x + y; } } Path A Path B Figura 3.3: Marcado de las instrucciones m´as relevantes para la poda din´amica de caminos. CAP´ ITULO 3. 69 Figura 3.4: Ejemplo gr´afico del c´alculo preciso del WCET mediante la poda din´amica de caminos durante el an´alisis. 70 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. efectividad de la poda depender´a de la estructura del programa, de los condicionales dentro de bucles y de la organizaci´on particular de la cache de instrucciones considerada. La eficacia de la poda depende especialmente de la capacidad de la cache, del tama˜no de sus l´ıneas y de su asociatividad. Pero durante el an´alisis, aunque en los estados de cache s´olo es necesario guardar las tags de los bloques de memoria que contiene la cache, si la capacidad de la cache que se analiza es grande, el tiempo dedicado a comparar los diferentes estados de cache en las instrucciones poda puede ser considerable. Si se dedica demasiado tiempo a comparar los estados de cache, el tiempo de an´alisis puede aumentar significativamente, de hecho puede suponer una de las principales deficiencias de esta t´ecnica. Por lo tanto, el n´umero de instrucciones poda no deber´ıa ser arbitrario, ya que influye decisivamente en el tiempo de an´alisis y c´alculo del WCET. Finalmente conviene indicar que todos aquellos caminos relevantes cuyo tiempo de ejecuci´on acumulado, m´as el coste de cargar completamente la cache, sea inferior al tiempo acumulado por alg´un otro camino relevante, se pueden descartar del an´alisis, ya que en ning´un caso determinan el WCET de la tarea. Esta nueva posibilidad de poda puede mejorar la eficiencia de la t´ecnica cuando el n´umero de iteraciones de los bucles sea muy grande. Por ejemplo, si suponemos que cargar completamente la cache en el an´alisis del WCET de la Figura 3.4 b) cuesta 50 unidades de tiempo, en la iteraci´on n´umero 3 se puede podar el camino cuyo estado de cache es CS(A) y en la iteraci´on 4 se puede podar el camino con estado de cache CS(B) quedando reducido el an´alisis a la Figura 3.5. Si adem´as aplicamos el Corolario 2, donde se indica el n´umero m´ınimo de iteraciones que es necesario analizar para determinar el WCET de la tarea, se puede reducir el tiempo de an´alisis considerablemente. En definitiva, el WCET obtenido mediante esta t´ecnica de poda din´amica se puede utilizar para determinar la planificabilidad de un sistema de tiempo real. Sin embargo, en un sistema multitarea con expulsiones es necesario tener en cuenta las interferencias extr´ınsecas entre las diferentes tareas del sistema, y el coste de los cambios de contexto [14]. No obstante, el coste de las interferencias extr´ınsecas de cache se puede conseguir de diferentes formas, como se ha propuesto en trabajos de investigaci´on anteriores [29, 32, 30, 100, 101, 139, 170, 171]. Por lo tanto, para una tarea Taski, si se considera el WCET obtenido de forma aislada Ci, el coste de un cambio de contexto δy el coste de las interferencias extr´ınsecas de cache γ, el nuevo WCET C0 ide la tarea queda determinado por la siguiente expresi´on: C0 i=Ci+ 2δ+γ En la siguiente secci´on se verifica experimentalmente la viabilidad de la t´ecnica de poda presentada en este apartado y se muestran los resultados m´as destacados obtenidos en los experimentos realizados. CAP´ ITULO 3. 71 Figura 3.5: C´alculo preciso del WCET cuando el coste de cargar la cache es 50. 3.4. Resultados experimentales Las tareas de prueba utilizadas en los experimentos se describen en la Tabla 3.2, donde tambi´en se muestra el tama˜no del c´odigo y el n´umero de instrucciones del camino m´as largo. Los c´odigos fuente se han compilado con GCC 2.95.2 -O2 para ARM v7. Estas tareas ya han sido utilizadas en estudios anteriores de referencia relacionados con el an´alisis del WCET [56, 116, 134, 146, 175]. Programa Descripci´on Tama˜no Instrucciones array sum Suma elementos matriz 152 B 1 737 bs B´usqueda binaria 112 B 56 bubble Algoritmo bubble-sort 160 B 95 178 crc Comp. redundancia c´ıclica 560 B 45 711 integral C´alculo integral por intervalos 420 B 141 102 qurt Ra´ıces ecuaci´on 2ogrado 752 B 1 715 Tabla 3.2: Tareas con estructuras condicionales analizadas. En este caso, se han seleccionado aquellas tareas que contienen sentencias 72 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. condicionales dentro de bucles. Algunas tareas utilizadas en otras propuestas como por ejemplo jfdctint, matmult, etc., se han descartado, puesto que s´olo contienen un ´unico camino de ejecuci´on. Si una tarea no tiene condicionales, s´olo puede seguir un camino durante la ejecuci´on y este camino determina el WCET. El objetivo de los experimentos realizados es determinar la contribuci´on exacta de cada uno de los accesos a la memoria realizados en presencia de una cache de instrucciones y observar su influencia en el WCET. En este modelo, la etapa de fetch tiene un coste asociado de 1 ciclo cuando se produce un acierto, es decir, cuando la instrucci´on est´a en cache; pero tiene un coste asociado de 60 ciclos cuando se produce un fallo, es decir, cuando la instrucci´on no est´a en cache [166]. El coste de ejecuci´on de una instrucci´on siempre es de 1 ciclo, salvo para las instrucciones de accesos a datos load ystore que tienen un coste a˜nadido de 60 ciclos, ya que se accede a la memoria principal para leer o guardar el dato. En los experimentos realizados se ha variado el tama˜no de la l´ınea de memoria, la capacidad y la asociatividad de la cache. Se han considerado caches de instrucciones de capacidad 128, 256 y 512 bytes con tama˜nos de l´ınea de 8, 16 y 32 bytes, es decir con capacidad para 2, 4 y 8 instrucciones por l´ınea respectivamente. La peque˜na capacidad de la cache est´a en consonancia con el reducido tama˜no del conjunto de tareas analizadas. Con respecto a la asociatividad, considerando las potencias de 2 como n´umero de v´ıas, se han analizado todas las configuraciones de cache, desde correspondencia directa hasta totalmente asociativa. An´alisis exacto del WCET con caches En el Tabla 3.3 se resumen los principales resultados obtenidos en los experimentos realizados. Los resultados muestran la gran diferencia entre el n´umero de posibles caminos de ejecuci´on de cada tarea analizada, que aparece en la tercera columna, y el n´umero m´aximo de caminos relevantes, que se muestra en la cuarta columna. Para cada experimento realizado, aparece indicado el tiempo invertido en el an´alisis. Los experimentos se han efectuado en un Pentium 4 a 3,4 GHz y, aunque se han analizado todas las iteraciones de los bucles de las tareas, el an´alisis ha finalizado en muy pocos segundos. Determinar el WCET de todos los caminos posibles de ejecuci´on es pr´acticamente imposible por la complejidad exponencial del problema, excepto para la tarea bs cuyo bucle s´olo tiene 4 iteraciones. Adem´as, si observamos el n´umero m´aximo de caminos relevantes para las configuraciones de cache analizadas, se puede verificar que dicho n´umero es mucho m´as peque˜no que el l´ımite te´orico de la Proposici´on 3. Por lo tanto, determinar la contribuci´on del fetch de instrucciones al WCET mediante la t´ecnica de poda din´amica propuesta, para CAP´ ITULO 3. 73 Tareas Itera. Cam. Te´oricos Tam. 128 B Cache 256 B Cache 512 B Cache Bucles Posib. Relev. L´ınea Relev. T. Relev. T. Relev. T. Min Max An´ali Min Max An´ali Min Max An´ali 8 B 2 3 0,07s 2 3 0,07s 2 3 0,09s array sum 100 ≈1030 3 16B 1 1 0,04 1 1 0,04s 1 1 0,04s 32B 1 1 0,04s 1 1 0,04s 1 1 0,07s 8 1 1 0,02s 1 1 0,02s 1 1 0,02s bs 4 20 1 16B 1 1 0,02s 1 1 0,02s 1 1 0,02s 32B 1 1 0,02s 1 1 0,02s 1 1 0,02s 8 B 3 8 0,33s 3 8 0,34s 3 8 0,35s bubble 5050 ≈101 520 9 16B 3 8 0,29s 3 8 0,29s 3 8 0,30s 32B 3 6 0,22s 3 6 0,22s 3 6 0,22s 8 B 13 29 0,15s 66 114 0,25s 36 216 0,80s crc 2082 ≈10932 216 16B 6 6 0,13s 16 44 0,14s 16 81 0,51s 32B 2 3 0,13s 4 4 0,14s 4 9 0,18s 8 B 9 20 2,09s 20 58 5,55s 11 176 17,24s integral 3000 ≈102 572 176 16B 6 10 1,22s 8 33 2,94s 6 83 5,29s 32B 3 4 0,40s 4 9 0,42s 3 11 0,43s 8 B 7 16 0,05s 24 63 0,06s 79 469 0,25s qurt 60 ≈1044 553 16B 4 11 0,03s 19 24 0,04s 46 142 0,09s 32B 4 6 0,03s 10 18 0,03s 27 84 0,07s Tabla 3.3: N´umero de iteraciones, posibles caminos de ejecuci´on y n´umero m´aximo de caminos relevantes. N´umero m´ınimo y m´aximo de caminos relevantes obtenidos para cada configuraci´on de cache, variando la asociatividad. Tiempo empleado en el an´alisis. 74 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. configuraciones particulares de cache, puede ser incluso mucho m´as efectivo de lo esperado. Por otro lado y de forma clara, tambi´en se observa que el n´umero de caminos relevantes obtenidos durante el an´alisis depende, tanto de la capacidad de la propia cache, como del tama˜no de las l´ıneas de memoria. Por ejemplo, al aumentar la capacidad de la cache, el n´umero de caminos relevantes crece de forma importante, obviamente hasta un cierto l´ımite. Pero, al aumentar el tama˜no de l´ınea de cache, para una misma capacidad de cache, el n´umero de caminos relevantes disminuye considerablemente. As´ı pues, en los experimentos realizados, el n´umero m´aximo de caminos relevantes se obtiene para las caches con capacidad mayor y l´ıneas de memoria m´as peque˜nas, es decir, para caches de 512 bytes con tama˜no de l´ınea de 8 bytes. Para medir la importancia de la asociatividad en esta t´ecnica de poda, se ha fijado en 16 bytes el tama˜no de bloque. Para cada tarea, en funci´on de la capacidad de la cache y de la asociatividad, en las Figuras 3.6 y 3.7 se muestran el WCET y el n´umero de caminos relevantes. En el eje Y de la izquierda aparece la escala asociada al WCET, y en el eje Y de la derecha se muestra la escala asociada al n´umero de caminos relevantes. En general, se observa que la asociatividad no mejora claramente el WCET, pero s´ı aumenta considerablemente el n´umero de caminos relevantes. As´ı pues, la asociatividad de la cache influye de forma negativa en el tiempo de an´alisis de esta t´ecnica. Finalmente conviene recordar que todos aquellos caminos relevantes cuyo tiempo de ejecuci´on acumulado, m´as el coste de cargar completamente la cache, sea inferior al tiempo acumulado por alg´un otro camino relevante, se pueden descartar del an´alisis, ya que en ning´un caso determinan el WCET de la tarea. Esta posibilidad de poda puede mejorar la eficiencia de la t´ecnica cuando el n´umero de iteraciones de los bucles sea muy grande. Adem´as, en casos concretos, para reducir el tiempo de an´alisis, se pueden aplicar las conclusiones del Corolario 2 donde se indica el n´umero m´ınimo de iteraciones que es necesario realizar para determinar el WCET de la tarea. As´ı pues, es interesante aplicar esta optimizaci´on durante el an´alisis de las tareas buble, crc eintegral, donde el n´umero de iteraciones de los bucles es grande. No obstante, como ya se ha comentado anteriormente, en los experimentos se han analizado todas las iteraciones de los bucles de cada tarea. Contribuci´on del fetch de instrucciones al WCET En los experimentos realizados tambi´en se incluye una comparaci´on con el m´etodo SCS (Static Cache Simulation) [134]. Esta t´ecnica permite clasificar en el peor caso los accesos a la cache de instrucciones. No obstante, y aunque el WCET tambi´en depende del tiempo de ejecuci´on de las instrucciones y de los accesos a datos, para que la comparaci´on sea lo m´as justa posible s´olo se considera el coste de acceso a las instrucciones. Adem´as, tambi´en se analiza una cache asociativa de 2 v´ıas, porque el m´etodo SCS obtiene las cotas del WCET CAP´ ITULO 3. 81 Adem´as, conviene indicar que esta t´ecnica de poda din´amica de caminos permite cuantificar la sobrestimaci´on en la predicci´on del peor caso de los accesos a la cache de instrucciones que presentan otros m´etodos propuestos en la literatura, como por ejemplo SCS (Static Cache Simulation) [134]. En particular, para la tarea qurt, la t´ecnica de poda din´amica reduce aproximadamente en un 62 % el IFC obtenido mediante SCS. Tambi´en se ha demostrado que el n´umero de caminos relevantes generado por estructuras condicionales dentro de bucles no depende del n´umero de iteraciones del bucle, sino que depende del n´umero de caminos del condicional. Por lo tanto y dado que el n´umero de caminos alternativos de un bucle no suele ser grande, la mayor´ıa de las tareas que forman un sistema de tiempo real se pueden analizar mediante la t´ecnica de poda din´amica de caminos. Por lo tanto, para estas tareas es posible predecir la contribuci´on exacta al WCET de los accesos a la cache de instrucciones. 82 3. EL WCET CON CACHES EN CAMINOS RELEVANTES. Cap´ıtulo 4 El WCET con caches que pueden fijar su contenido En un sistema de tiempo real multitarea, un m´etodo sencillo para resolver el problema de las interferencias de cache, tanto intr´ınsecas como extr´ınsecas, es fijar el contenido de la cache. Una forma de fijar el contenido de la cache, durante algunos periodos o durante toda la vida del sistema, es deshabilitar el algoritmo de reemplazo. Al fijar el contenido de la cache, cada acceso a memoria se puede predecir de forma totalmente exacta y segura. Adem´as, se evita la explosi´on combinatoria de caminos en bucles que contienen condicionales, ya que el coste de cada acceso a memoria s´olo depende de si la l´ınea a la que se accede est´a bloqueada en la cache o no. Como al fijar el contenido de la cache es posible que disminuyan sus prestaciones haciendo que el WCET de las tareas aumente, es necesario que las l´ıneas que se vayan a fijar en la cache sean las m´as adecuadas para que el rendimiento no disminuya. No obstante, en estudios anteriores ya se demostr´o que, con una selecci´on adecuada de los contenidos a fijar, la planificabilidad del sistema puede mejorar considerablemente [8, 117, 118, 120, 121, 122, 124, 146, 147]. Sin embargo, en ninguno de estos estudios se garantiza que la selecci´on de contenidos a fijar en la cache sea la ´optima. En este cap´ıtulo, para una jerarqu´ıa de memoria (ver Figura 4.1) formada por un almac´en de l´ınea de instrucciones (Line Buffer) y una cache que puede fijar su contenido (Lockable iCache), presentamos un algoritmo basado en programaci´on lineal entera (ILP/ Integer Linear Programming [161, 36, 158]) para seleccionar los contenidos a fijar en la cache de instrucciones, de tal forma que cada una de las tareas del sistema pueda utilizar toda la cache y adem´as, que la planificabilidad del sistema sea m´axima. A este algoritmo lo hemos denominado Lock-MS (Lock for Maximize Schedulability). El algoritmo Lock-MS selecciona las l´ıneas de memoria que cada tarea del 83 84 4. EL WCET CON CACHES BLOQUEADORAS. tag Lockable iCache Line Buffer (LB) decode register file Embedded SRAM memory Figura 4.1: Jerarqu´ıa de memoria para instrucciones en un sistema de tiempo real. sistema debe tener en la cache durante su ejecuci´on. En cada cambio de contexto se actualiza el contenido de la cache con las l´ıneas de memoria asociadas a la tarea que comienza o reanuda su ejecuci´on. Una vez finalizada la carga de los contenidos de la cache seleccionados por el algoritmo Lock-MS, la cache de instrucciones quedar´a totalmente bloqueada. De esta forma, la tarea puede utilizar toda la cache, aunque se debe tener en cuenta el coste de cargar dichas l´ıneas de memoria en cada cambio de contexto. Es decir, nuestra propuesta define un nuevo enfoque de las t´ecnicas que en la literatura se han denominado dynamic locking cache. 4.1. Descripci´on de la jerarqu´ıa de memoria En esta secci´on se describen en detalle los componentes y el funcionamiento de una arquitectura de memoria para instrucciones (ver Figura 4.1), que pretendemos utilizar en un sistema de tiempo real multitarea con expulsiones. Esta organizaci´on de la jerarqu´ıa de memoria ya est´a disponible en procesadores para sistemas empotrados. Adem´as, tambi´en ha sido considerada en estudios anteriores, aunque sin aprovechar al m´aximo sus prestaciones [147, 118]. A continuaci´on se describe el comportamiento de los dos componentes y el funcionamiento general de esta jerarqu´ıa de memoria. Una cache que pueda fijar su contenido: Lockable iCache El primer componente de esta jerarqu´ıa de memoria es una cache de instrucciones asociativa por conjuntos que pueda fijar o bloquear su contenido. Al fijar CAP´ ITULO 4. 85 Vtag = line 4 B 16 B eSRAM LBhit Instruction PC LB Pipeline stages decode · · ·· · · BackwardJump load LB.tag with PC.tag set LB.V iCacheHit →reset LB.V iCacheMiss & LBmiss →load LB.line with eSRAM output BackwardJump →reset LB.V Figura 4.2: Organizaci´on y funcionamiento del LB. el contenido de la cache, su comportamiento es totalmente predecible. Adem´as, todas las interferencias de cache desaparecen, es decir, ya no es necesario considerar durante el an´alisis del peor caso, ni las interferencias intr´ınsecas ni las interferencias extr´ınsecas. Un peque˜no almac´en de l´ınea de instrucciones: Line Buffer El segundo componente de la jerarqu´ıa de memoria es un peque˜no almac´en de instrucciones (LB/ Line Buffer) del tama˜no de una l´ınea de cache para capturar la localidad espacial. En la Figura 4.2 se muestra la organizaci´on y funcionamiento del LB propuesto. Una Lockable iCache con las caracter´ısticas descritas anteriormente s´olo permite aprovechar la localidad temporal. Como se mostrar´a en los experimentos, este LB captura la localidad espacial muy bien, mejorando considerablemente el rendimiento de la jerarqu´ıa de memoria en el peor caso. Adem´as, si las l´ıneas de memoria bloqueadas en la cache son las m´as adecuadas para cada tarea, esta jerarqu´ıa de memoria podr´ıa superar en prestaciones incluso a una cache convencional. Funcionamiento Durante la etapa de fetch de una instrucci´on se realiza una b´usqueda en paralelo, en la Lockable iCache y en el LB. Obtendremos un acierto si encontramos 86 4. EL WCET CON CACHES BLOQUEADORAS. la instrucci´on en la cache o en el LB. En ambos casos, la instrucci´on se sirve en un ciclo de procesador. Pero si se produce un fallo en ambas estructuras, la l´ınea de memoria de la instrucci´on se solicita al siguiente nivel en la jerarqu´ıa de memoria, que es una eSRAM para sistemas empotrados, y el LB se actualizar´a con la l´ınea de memoria solicitada. Por lo tanto, el comportamiento del LB es similar al de una cache con una ´unica l´ınea. El funcionamiento del LB presenta un comportamiento particular, ya que su contenido se invalida autom´aticamente cuando se produce un acierto de cache y tambi´en cuando se produce un salto atr´as, incluso si es a una instrucci´on dentro de la misma l´ınea de memoria que contiene. Por lo tanto, su contenido no puede ser reutilizado y cuando una l´ınea de memoria ya ha sido consumida, si es necesario, se debe solicitar otra vez a la memoria principal. En definitiva, este funcionamiento particular del LB evita que este componente pueda aprovechar la localidad temporal. El procesador no dispone de otros recursos que puedan tener latencia variable, como por ejemplo un predictor de saltos o una cache de datos. El procesador no est´a segmentado y la ejecuci´on de las instrucciones se realiza en orden. De esta forma, el sistema no presenta ning´un tipo de anomal´ıa de distribuci´on (timing anomalies) [43, 115, 155, 193]. Tambi´en suponemos que el n´umero m´aximo de iteraciones de los bucles de cada tarea es conocido y que los caminos imposibles han sido identificados. No obstante, es importante se˜nalar que si no se utilizan componentes con latencia variable, dependientes de la historia de ejecuci´on, las interferencias intr´ınsecas de las tareas desaparecen, como ya se indic´o en estudios anteriores [122]. 4.2. Lock-MS: Selecci´on de l´ıneas a fijar A continuaci´on describimos el algoritmo Lock-MS (Lock for Maximize Schedulability) que selecciona las l´ıneas de memoria a bloquear en la cache de cada tarea, para conseguir la m´axima planificabilidad del sistema. En un sistema de tiempo real, este algoritmo basado en ILP hace posible obtener el m´aximo rendimiento de la jerarqu´ıa de memoria descrita en la Figura 4.1. As´ı pues, consideramos un sistema de tiempo real multitarea donde la prioridad de cada tarea es fija y se permiten las expulsiones. La planificaci´on de las tareas del sistema se puede obtener de diferentes formas [163], en particular mediante RMA (Rate Monotonic Analysis). La arquitectura de memoria que proponemos dispone de una Lockable iCache que puede bloquear su contenido durante algunos periodos de la ejecuci´on del sistema, en particular durante la ejecuci´on de cada tarea. En cada cambio CAP´ ITULO 4. 87 de contexto, el contenido de la cache se actualiza con las l´ıneas de memoria de la tarea que se va a ejecutar. El comportamiento de esta cache es totalmente predecible. Cada tarea, cuando se ejecuta, puede aprovechar toda la cache de forma exclusiva, pero el coste de cargar las l´ıneas de memoria de la tarea en cada cambio de contexto debe ser considerado. Sin embargo, las restricciones lineales para modelar una cache de instrucciones que pueda fijar su contenido son muy espec´ıficas y no son comparables con otras t´ecnicas basadas en IPET (Implicit Path-Enumeration Technique) u otros m´etodos de modelado equivalentes [107]. La arquitectura propuesta tambi´en dispone de un LB cuyo funcionamiento se puede modelar mediante restricciones lineales, ya que su contenido s´olo depende de la localizaci´on de la instrucci´on ejecutada previamente dentro de la l´ınea de memoria. El funcionamiento del LB no genera ning´un tipo de interferencia, puesto que cuando se produce un acierto de cache o un salto atr´as, su contenido se invalida. Con este modelo de arquitectura, en los saltos condicionales el camino de peor caso siempre seguir´a la misma trayectoria, es decir, el camino de peor caso en un condicional se alcanza considerando siempre el salto como tomado o considerando siempre el salto como no tomado. En ning´un caso el camino m´as largo vendr´a determinado por una combinaci´on de las dos posibilidades del condicional, ya que cada uno de los posibles caminos de ejecuci´on es totalmente independiente de los dem´as. El objetivo del algoritmo Lock-MS es determinar las l´ıneas de memoria de cada tarea que se cargar´an en la cache antes de su ejecuci´on. El algoritmo tendr´a en consideraci´on el WCET de cada tarea y el coste de cargar las l´ıneas seleccionadas en la cache en cada cambio de contexto. Para obtener la selecci´on de las l´ıneas a fijar, el algoritmo Lock-MS modela el problema a resolver mediante un conjunto de restricciones lineales basadas en ILP, cuya funci´on objetivo ser´a minimizar el WCET de cada tarea del sistema. En definitiva, al minimizar el WCET de cada tarea y adem´as tener en cuenta el coste de los cambios de contexto, el algoritmo Lock-MS obtiene la selecci´on de l´ıneas a fijar en la cache para que la planificabilidad del sistema sea m´axima. Modelado del problema ILP Para modelar el problema ILP se define un sistema de tiempo real multitarea como un conjunto de tareas peri´odicas Taski, tal que 1 ≤i≤NTasks, donde NTasks indica el n´umero de tareas del sistema. As´ı pues, una tarea Taski se puede modelar como un conjunto de caminos de principio a fin Pathi,j, con 1 ≤j≤NPathsi, donde NPathsiindica el n´umero de caminos de la tarea Taski. Finalmente, cada camino Pathi,j est´a formado por un conjunto 88 4. EL WCET CON CACHES BLOQUEADORAS. de Nlinesi,j l´ıneas de memoria. En la Figura 4.3 se presenta el esquema de flujo de control de un programa sencillo. Se muestran una serie de l´ıneas de memoria desde la L1hasta la L12, organizadas en bloques b´asicos con las estructuras de control del programa y una funci´on. Algunas l´ıneas de memoria pueden formar parte de bloques b´asicos distintos, por ejemplo las l´ıneas L1yL4. Adem´as, los bloques b´asicos pueden contener diferentes l´ıneas de memoria, por ejemplo el camino de la izquierda dentro del bucle contiene las l´ıneas L3yL4. El flujo de control del subgrafo de la derecha corresponde a una funci´on que se puede llamar desde dos puntos diferentes del programa que aparecen marcados con el s´ımbolo &. En la Figura 4.4 se muestra una ampliaci´on de la informaci´on del flujo de control presentado en la Figura 4.3, donde se especifica la informaci´on necesaria para el an´alisis y c´alculo del WCET. En esta nueva representaci´on aparecen algunos detalles clave en el modelado ILP: i) Las l´ıneas de memoria compartidas por bloques b´asicos diferentes se muestran divididas. A cada una de ellas se le asigna un identificador ´unico, por ejemplo las l´ıneas L4ayL4bforman parte de la misma l´ınea de memoria L4, pero pertenecen a dos bloques b´asicos distintos. Esto permite asociar distintos costes y diferentes n´umeros de acceso a cada una de las partes en las que se ha dividido una l´ınea de memoria. ii) La funci´on se debe analizar teniendo en cuenta el punto del programa desde donde se invoc´o. En la Figura 4.4 se ha reflejado el an´alisis de las dos posibles instancias a la funci´on. En este ejemplo se realiza una llamada a la funci´on desde las l´ıneas de memoria L2(&1) y L4b(&2). iii) Todos los bloques b´asicos est´an etiquetados con los posibles caminos a los que pertenecen. Por lo tanto, cualquier camino Pathjest´a perfectamente identificado de principio a fin. Por ejemplo, el camino Path2recorre los bloques b´asicos que forman las l´ıneas de memoria L1a,L1b,L2,L9a,L9b, L11a,L11b,L12a,L12b,L8ayL8b. iv) El coste de ejecutar cualquier l´ınea de memoria en un camino concreto es constante, incluso aunque el camino seguido hasta esa l´ınea sea distinto. Es decir, el coste de ejecutar una l´ınea de memoria no depende, en ning´un caso, de la l´ınea de memoria ejecutada previamente. Por ejemplo, en el camino Path2se ejecuta la l´ınea L1buna vez, despu´es de ejecutar la l´ınea L1a, y bound1 2veces, despu´es de ejecutar la l´ınea L8a. En general, cada tarea Taskise puede modelar como un conjunto de caminos Pathi,j donde el coste de ejecuci´on del camino m´as largo ser´a el WCET de la tarea. As´ı pues, el WCET de una tarea, representado por wceti, debe ser mayor o igual que el coste de ejecuci´on de todos y cada uno de sus caminos. CAP´ ITULO 4. 89 ✆ ✆ ✆ L9 L9 L10 L11 L11 L12 L12 L1 L3 L6 L7 L4 L1 L7 L8 L8 L3L4 L2 L5 Figura 4.3: Modelado del flujo de control donde las l´ıneas de memoria se han dividido en bloques b´asicos. 90 4. EL WCET CON CACHES BLOQUEADORAS. ✆1 ✆2 ✆2 ✆1 L1 9b 1, 2 L1 9a 1, 2 L1 11b L1 12a 1, 2 L1 12b 1, 2 L1 10 1 L1b L3a L5 L6 L7a L4a bound1 1,2,3,4,5,6 bound2 3,4,5,6 L1a L7b L8b L8a 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6 3, 4, 5, 6 L3bL4b 3, 4, 5, 6 3, 4, 5, 6 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6 3 1, 2 4, 5 4, 5 L2 9b 4, 5 L2 11a 5 L2 10 4 L2 11b L2 12a 4, 5 L2 12b 4, 5 L2 9a bound3 4,5 bound3 1,2 L2 L1 11a 2 6 Figura 4.4: Modelado del flujo de control donde: a) las l´ıneas de memoria divididas se han identificado de forma ´unica, b) se han introducido las instancias a la funci´on, c) se han anotado los caminos a los que pertenece cada bloque b´asico. CAP´ ITULO 4. 97 Figura 4.5: Ejemplo de programa con informaci´on funcional [107]. representa un bloque b´asico asociado a una ´unica l´ınea de memoria. Tambi´en se muestran dos caminos dependientes de una estructura condicional if-then-else donde el n´umero m´aximo de iteraciones del bucle es 10. El inter´es del an´alisis funcional de este ejemplo reside en la l´ınea de memoria B5, ya que s´olo se puede ejecutar una vez. Si consideramos los dos posibles caminos de ejecuci´on dentro del bucle, el camino P1siempre ejecutar´a el caso then y el camino P2ejecutar´a s´olo una vez el caso else. El n´umero m´aximo de accesos a las l´ıneas de memoria B4yB5para cada uno de los caminos P1 yP2se puede modelar a˜nadiendo al problema ILP las siguientes restricciones: nfetchi,P 1,B4= 10 nfetchi,P 1,B5= 0 nfetchi,P 2,B4= 9 nfetchi,P 2,B5= 1 Si se sabe que cuando se ejecuta la l´ınea B5el n´umero de iteraciones del bucle es de exactamente 5 iteraciones, se tiene otro ejemplo distinto. En este caso, el n´umero m´aximo de accesos a las l´ıneas de memoria B4yB5, para cada uno de 98 4. EL WCET CON CACHES BLOQUEADORAS. B0 B2B1 B4 B3 B6 B5 B0 B2B1 B31 B51 B61,4 B42B52 B62,4 B61,5B62,5 B32 B41 Figura 4.6: Grafo de flujo de control y explosi´on de los caminos de ejecuci´on. los caminos P1yP2, se puede modelar mediante las siguientes restricciones: nfetchi,P 1,B4= 10 nfetchi,P 1,B5= 0 nfetchi,P 2,B4= 4 nfetchi,P 2,B5= 1 4.3. Un modelo compacto para reducir las restricciones La base del algoritmo Lock-MS es la descripci´on de todos y cada uno de los posibles caminos de ejecuci´on. Pero, si el n´umero de caminos de las tareas es grande, el conjunto de restricciones del problema ILP puede crecer considerablemente haciendo incluso inviable su descripci´on. En esta secci´on definimos una transformaci´on para simplificar la descripci´on de los posibles caminos de ejecuci´on en el modelo ILP. Con el fin de ilustrar esta transformaci´on se considera el ejemplo de la Figura 4.6 donde se muestra un sencillo grafo de flujo de control y la explosi´on de los posibles caminos de ejecuci´on. El grafo de flujo de control representa la ejecuci´on de 4 caminos y sus bloques b´asicos asociados. En este ejemplo, mediante las siguientes descripciones de los caminos, se calcula el WCET como el m´aximo tiempo de ejecuci´on asociado a cada uno de CAP´ ITULO 4. 99 los 4 caminos: P1 = B0 + B1 + B31+B41+B61,4 P2 = B0 + B1 + B31+B51+B61,5 P3 = B0 + B2 + B32+B42+B62,4 P4 = B0 + B2 + B32+B52+B62,5 WCET = m´ax(P1, P2, P3, P 4) (4.12) Para calcular el WCET de la tarea se deben seleccionar, cargar y bloquear las l´ıneas de memoria Lk, de tal forma que el WCET de la tarea sea m´ınimo. Por lo tanto, la Ecuaci´on 4.12 se transforma, en funci´on del conjunto de l´ıneas de memoria SetLasociadas a dicha tarea, como se indica a continuaci´on: WCET = m´ın Lk∈SetL ( m´ax(P1Lk, P 2Lk, P3Lk, P 4Lk) ) No obstante, el modelo ILP presentado puede resolver esta ecuaci´on eligiendo de forma exacta y concreta las l´ıneas Lk∈SetL. Por claridad en la notaci´on y sin p´erdida de generalidad, se eliminan los sub´ındices, y la ecuaci´on anterior se escribe de este modo: WCET = m´ın( m´ax(P1, P2, P3, P4) ) (4.13) Adem´as, como ya se ha comentado anteriormente, al cargar y fijar en la cache los contenidos seleccionados por el algoritmo Lock-MS, el coste de ejecuci´on de cualquier bloque b´asico es independiente del bloque ejecutado anteriormente. De forma an´aloga, esta idea puede extenderse al LB, ya que su comportamiento s´olo depende de la instrucci´on anterior, que adem´as pertenece al camino analizado. Por lo tanto, en la notaci´on utilizada para representar los bloques b´asicos propios de cada camino tambi´en se suprimen los sub´ındices, ya que el coste de ejecuci´on de todos los bloques se calcula de forma aislada. Con esta nueva notaci´on se actualiza la Ecuaci´on 4.13 anterior describiendo el coste de ejecuci´on de cada bloque b´asico. WCET = m´ın( m´ax(B0 + B1 + B3 + B4 + B6, B0 + B1 + B3 + B5 + B6, B0 + B2 + B3 + B4 + B6, B0 + B2 + B3 + B5 + B6) ) Finalmente, si se agrupan los bloques comunes a todos los caminos en varios sumandos constantes, se tiene una nueva ecuaci´on que determina el WCET de forma compacta: WCET = m´ın( B0 + B3 + B6 + m´ax(B1 + B4, B1 + B5, B2 + B4, B2 + B5) ) (4.14) 100 4. EL WCET CON CACHES BLOQUEADORAS. L2a L1 1, 2, . . . L4b 2, . . . L6a L5 L7 1, 2, . . . L6b 1, . . . L2b L3 L4a 1, 2 . . . L1 L3 L5 L7 . . . L2 L4 L6 . . . Figura 4.7: Descripci´on gr´afica del modelo expl´ıcito y del compacto. Para detallar la simplificaci´on anterior, se presenta el ejemplo de la Figura 4.7 donde se muestran dos caminos Path1yPath2formados por una serie de l´ıneas de memoria Lxy sus bloques b´asicos asociados. Si una l´ınea de memoria es seleccionada y bloqueada en la cache, el coste de acceso a las instrucciones de esta l´ınea siempre es el coste de un acierto de cache. Si la l´ınea de memoria no est´a en cache, el coste de un acceso a la l´ınea depende del comportamiento del LB. El primer acceso a la l´ınea de memoria siempre tiene un coste de fallo de LB tmissLB, mientras que el resto de los accesos tienen un coste de acierto de LB thitLB. Adem´as, como ya se ha comentado anteriormente, y se observa en la figura, se debe tener en cuenta la posible divisi´on entre las l´ıneas de memoria y los bloques b´asicos. En el Tabla 4.1 se resume el coste del primer acceso al LB cuando ninguna de las l´ıneas de los caminos Path1yPath2de la Figura 4.7 han sido bloqueadas en la cache. Toda esta informaci´on se puede obtener est´aticamente analizando el c´odigo. Mediante el modelo expl´ıcito de caminos se observan las l´ıneas que pertenecen a cada camino y el coste del primer acceso a cada una de ellas. Si la l´ınea pertenece a los dos caminos, tendr´ıa dos costes asociados y si s´olo pertenece a uno de los caminos s´olo tendr´a un coste asociado. CAP´ ITULO 4. 101 L´ıneas Modelo expl´ıcito Modelo compacto Path1Path2 L1tmissLB tmissLB tmissLB L2atmissLB tmissLB tmissLB L2b0 - 0 L3tmissLB -tmissLB L4atmissLB -tmissLB L4b-tmissLB tmissLB L5-tmissLB tmissLB L6a-tmissLB 0 L6btmissLB 0tmissLB L7tmissLB tmissLB tmissLB Tabla 4.1: Coste del primer acceso a las l´ıneas de memoria en la Figura 4.7 cuando no est´an en cache. En la columna etiquetada como Modelo compacto de la Tabla 4.1 se muestra el coste del primer acceso a cada una de las l´ıneas de memoria del ejemplo, cuando se aplica el m´etodo compacto propuesto. En la mayor parte de los casos se puede trasladar directamente el coste del primer acceso a una l´ınea de memoria del modelo expl´ıcito, al modelo compacto, definiendo una serie de casos b´asicos que se describen a continuaci´on: Caso 1: Si una l´ınea de memoria pertenece a dos o m´as caminos, el coste del primer acceso a dicha l´ınea se traslada directamente al modelo compacto. Caso 2: Si una l´ınea de memoria pertenece a un solo camino, el coste del primer acceso a dicha l´ınea tambi´en se traslada directamente al modelo compacto. Caso 3: Si una l´ınea de memoria tiene una parte com´un que pertenece a dos o m´as caminos, y una parte que s´olo pertenece a uno de los caminos, entonces el coste del primer acceso a dicha l´ınea se asocia y se traslada directamente a la parte com´un en el modelo compacto, y se asigna un coste 0 a cada una de las partes particulares de cada camino. Como se puede observar en la Tabla 4.1, las l´ıneas L1yL7son comunes a los caminos Path1yPath2, y representan un ejemplo del Caso 1. Por lo tanto, en el modelo compacto se asigna directamente el coste del primer acceso a la l´ınea de memoria. Las l´ıneas L3yL4apertenecen s´olo al camino Path1, mientras que las l´ıneas L4byL5pertenecen s´olo al camino Path2. Ambos casos, representan un ejemplo del Caso 2. Por lo tanto, en el modelo compacto se asigna directamente el coste del primer acceso a cada una de las l´ıneas de memoria. Como ejemplo del Caso 3, se observa, por un lado, la l´ınea L2que tiene una parte com´un L2aa los dos caminos y una parte particular L2bque 102 4. EL WCET CON CACHES BLOQUEADORAS. pertenece ´unicamente al camino Path1, y por otro lado, la l´ınea L6que tiene una parte particular L6aque pertenece ´unicamente al camino Path2, y una parte com´un L6bque pertenece a los dos caminos. Por lo tanto, el coste en el modelo compacto se asigna a la parte com´un de las l´ıneas, que en este caso son L2ayL6b, y se asocia un coste 0 a las l´ıneas L2byL6aque son particulares de cada camino. Aplicando los casos anteriormente descritos, al modelo expl´ıcito, el coste de cada camino es igual a la suma de los costes de sus l´ıneas de memoria en el modelo compacto. Por ejemplo, la suma de las columnas asociadas al modelo expl´ıcito de los caminos Path1yPath2de la Tabla 4.1 es igual a la suma de las l´ıneas de memoria de dichos caminos en el modelo compacto. As´ı pues, para cualquier l´ınea de memoria tenemos una representaci´on equivalente al coste de su primer acceso, independientemente del n´umero de caminos que contengan dicha l´ınea, sin a˜nadir ning´un tipo de sobrestimaci´on. Siguiendo con el ejemplo de la Figura 4.6, y considerando la Ecuaci´on 4.14, se puede obtener una expresi´on equivalente de dicha ecuaci´on teniendo en cuenta que si B1≤B2, obviamente B1 + B4≤B2 + B4, y por lo tanto B1 + B4 se podr´ıa eliminar de la ecuaci´on, mientras que B2 + B4 deber´ıa permanecer. As´ı pues, utilizando primero el operador m´aximo entre B1 y B2 y despu´es entre B4 y B5, la ecuaci´on del WCET en el modelo compacto ser´ıa la siguiente: WCET = m´ın( B0 + B3 + B6 + m´ax(B1 + B4, B1 + B5, B2 + B4, B2 + B5) ) WCET = m´ın( B0 + B3 + B6 + m´ax( m´ax(B1, B2) + B4,m´ax(B1, B2) + B5)) WCET = m´ın( B0 + B3 + B6 + m´ax(B1, B2) + m´ax(B4, B5) ) Finalmente, si se agrupan los costes de los bloques b´asicos comunes a los dos caminos, es decir, B0, B3 y B6, la ecuaci´on final que se obtiene todav´ıa es mucho m´as reducida: CmnCost =B0 + B3 + B6 WCET = m´ın( CmnCost + m´ax(B1, B2) + m´ax(B4, B5) ) Para ilustrar esta idea con un ejemplo m´as complejo, se considera el flujo de control de la Figura 4.4. Las restricciones para obtener el WCET, en vez de tener en cuenta los caminos expl´ıcitos, se construyen a partir de los costes comunes a los 6 caminos indicados en la Figura 4.4. En la Tabla 4.2 se describen las l´ıneas que recorre cada uno de los caminos de la Figura 4.4. Esta Tabla 4.2 CAP´ ITULO 4. 103 Path1L1aL1bL2L8aL8bL1 9aL1 9bL1 10 L1 11bL1 12aL1 12b Path2L1aL1bL2L8aL8bL1 9aL1 9bL1 11aL1 11bL1 12aL1 12b Path3L1aL1bL3aL3bL4aL7aL7bL8aL8b Path4L1aL1bL3aL4bL5L7aL7bL8aL8bL2 9aL2 9bL2 10 L2 11bL2 12aL2 12b Path5L1aL1bL3aL4bL5L7aL7bL8aL8bL2 9aL2 9bL2 11aL2 11bL2 12aL2 12b Path6L1aL1bL3aL6L7aL7bL8aL8b CmnAll L1aL1bL8aL8b Cmn{1,2}L2L1 9aL1 9bL1 11bL1 12aL1 12b Cmn{3,4,5,6}L3aL7aL7b Cmn{4,5}L4bL5L2 9aL2 9bL2 11bL2 12aL2 12b Tabla 4.2: Clasificaci´on de las l´ıneas de memoria comunes y particulares de los caminos de la Figura 4.4. 104 4. EL WCET CON CACHES BLOQUEADORAS. L2 10 L2 11a L6 L3b+L4a L1 10 L1 11a Cmn{1,2}+ m´ax(F ork{1,2}) CmnAll + m´ax(F orkAll) Cmn{3,4,5,6}+ m´ax(F ork{3,4,5,6}) Cmn{4,5}+ m´ax(F ork{4,5}) Figura 4.8: Grafo compacto de restricciones de la Figura 4.4. se puede trasladar a un ´arbol como el de la Figura 4.8 que se interpreta como un AST (Abstract Syntax Tree) o como un CFG (Control Flow Graph). Las l´ıneas de memoria aparecen s´olo una vez, es decir, cada nodo es un conjunto de l´ıneas comunes a varios caminos y cada rama representa un camino alternativo. El conjunto de restricciones asociadas al nuevo problema ILP permite calcular el WCET (wceti) de una tarea como en la Ecuaci´on 4.1, pero utilizando directamente el valor de los costes de ejecuci´on de las l´ıneas de memoria lineCosti,j,k sin necesidad de emplear las restricciones asociadas a cada uno de los caminos expl´ıcitos pathCosti. Por lo tanto, estas nuevas restricciones pueden sustituir a las restricciones del modelo expl´ıcito como se indica a continuaci´on, evitando as´ı tener que definir todos y cada uno de los posibles caminos de ejecuci´on: wceti=CmnAll +ForkAll CmnAll =lineCost1a+lineCost1b+lineCost8a+lineCost8b ForkAll ≥Cmn{1,2}+F ork{1,2} ForkAll ≥Cmn{3,4,5,6}+F ork{3,4,5,6} Cmn{1,2}=lineCost2+lineCost1 9a+lineCost1 9b+lineCost1 11b+ lineCost1 12a+lineCost1 12b Fork{1,2}≥lineCost1 10 Fork{1,2}≥lineCost1 11a Cmn{3,4,5,6}=lineCost3a+lineCost7a+lineCost7b Fork{3,4,5,6}≥lineCost3b+lineCost4a Fork{3,4,5,6}≥Cmn{4,5}+Fork{4,5} Fork{3,4,5,6}≥lineCost6 CAP´ ITULO 4. 105 Cmn{4,5}=lineCost4b+lineCost5+lineCost2 9a+lineCost2 9b+ lineCost2 11b+lineCost2 12a+lineCost2 12b Fork{4,5}≥lineCost2 10 Fork{4,5}≥lineC2 11a(4.15) 4.4. Evaluaci´on del algoritmo Lock-MS En esta secci´on se eval´uan las prestaciones del algoritmo Lock-MS para un sistema multitarea, formado por un conjunto de tareas de prioridad fija con una planificaci´on basada en Rate Monotonic. Las tareas analizadas en los experimentos realizados son las mismas que se han utilizado en trabajos anteriores [147]. Los programas considerados son los siguientes: jfdctint: transformada discreta del coseno. crc: comprobaci´on de redundancia c´ıclica. matmult: multiplicaci´on de matrices. integral: integral por intervalos. minver: inversi´on de una matriz. qurt: c´alculo de las ra´ıces de una ecuaci´on de segundo grado. fft: transformada r´apida de Fourier. En la Tabla 4.3 se muestran las tareas analizadas dividas en dos conjuntos denominados small ymedium. Conjunto Tarea WCET Periodo Tama˜no con-LB small jfdctint 10108 23248 1072 B crc 109696 329088 536 B matmul 542229 2440031 208 B integral 716633 3583165 400 B medium minver 8522 19601 1360 B qurt 10117 30351 752 B jfdctint 10108 44475 1072 B fft 2886680 15010736 1016 B Tabla 4.3: Conjunto de tareas: small ymedium. 106 4. EL WCET CON CACHES BLOQUEADORAS. En un sistema cuya jerarqu´ıa de memoria est´a formada por un ´unico LB, los periodos de cada tarea se han elegido para conseguir una utilizaci´on de 1,2 en los dos conjuntos de tareas small ymedium. Adem´as, el WCET y los periodos de cada conjunto de tareas siguen patrones diferentes. Por ejemplo, en el conjunto small, el WCET de cada tarea va creciendo de forma uniforme, al igual que sus periodos. En cambio, en el conjunto medium, 3 tareas tienen un WCET peque˜no y sus periodos de ejecuci´on tambi´en son peque˜nos, mientras que en la cuarta tarea, tanto su WCET, como su periodo son relativamente grandes. En este caso, esta tarea ser´a expulsada muchas veces durante la ejecuci´on del sistema. En concreto, el conjunto de tareas medium tiene muchos m´as cambios de contexto que el conjunto small. Esto puede servir para observar en detalle c´omo influyen los cambios de contexto en la selecci´on de l´ıneas a bloquear en la cache por parte del algoritmo Lock-MS. En los experimentos, la arquitectura considerada est´a formada por un procesador ARM v7 con instrucciones de 4 bytes y una jerarqu´ıa de memoria como la que se describe en la Figura 4.1. Suponemos que el procesador elegido se ha construido bajo la tecnolog´ıa de 32 nm, con una velocidad de ciclo equivalente a 36 FO41que podr´ıa estar alrededor de los 2.4 GHz. Este procesador representa perfectamente las caracter´ısticas de un procesador actual de altas prestaciones para sistemas empotrados [1]. El tama˜no del LB y de cada una de las l´ıneas de la Lockable iCache es de 16 bytes, es decir de 4 instrucciones. En los experimentos se var´ıa la capacidad de la cache de instrucciones desde 128 bytes a 4 KB, mientras que el tama˜no de la eSRAM se mantiene constante en 256 KB. Para determinar la latencia de memoria m´ınima, de la arquitectura propuesta, se ha utilizado Cacti V.6.0 [138]. Si la implementaci´on se realiza con transistores de bajo consumo en reserva, se ha verificado que el tiempo de acceso a una eSRAM de 256 KB estar´a en torno a unos 7 ciclos. El coste de fetch de una instrucci´on cuando se produce un acierto, es decir cuando la instrucci´on est´a en la cache o en el LB, ser´a de 1 ciclo. Pero si se produce un fallo, es decir si se accede a la eSRAM, el coste de fetch ser´a de 7 ciclos. Con esta latencia de memoria se consigue estresar el funcionamiento de la Lockable iCache, por lo tanto los resultados obtenidos representan una cota m´ınima del rendimiento que se puede obtener con esta jerarqu´ıa de memoria. El coste de ejecutar una instrucci´on, si no se accede a memoria, ser´a de 2 ciclos. No obstante, el coste asociado a una instrucci´on predicada que no se ejecuta ser´a de 1 ciclo. Las instrucciones predicadas son instrucciones generales que s´olo se ejecutan si se cumple una determinada condici´on. El coste de ejecuci´on de una instrucci´on de acceso a memoria, instrucciones load ystore, tendr´a un incremento adicional de 7 ciclos, ya que los accesos a datos se sirven directamente desde la eSRAM. En los experimentos realizados se calcula el WCET de cada una de las ta1Un FO4 (A fan-out-of-4) representa el retardo de propagaci´on de un inversor cuando la carga de trabajo es 4 veces la suya propia. CAP´ ITULO 4. 113 posibles cambios de contexto, mientras que el m´etodo de poda s´olo permite analizar una tarea de forma aislada. El conjunto de tareas utilizado en los experimentos ya se ha presentado en la Tabla 4.3. El m´etodo de poda puede analizar este conjunto de tareas y obtener el WCET exacto en poco tiempo. En los experimentos realizados s´olo hemos analizado una cache de correspondencia directa. La asociatividad no influye de forma significativa, ni en los resultados que proporciona el m´etodo de poda din´amica de caminos, ni tampoco en los resultados obtenidos mediante el algoritmo LockMS. Por lo tanto, un aumento de la asociatividad de la cache no aporta una mejora relevante en los resultados logrados por ambos m´etodos. En primer lugar, hemos analizado el WCET de las tareas de los conjuntos small ymedium. Los resultados muestran que el WCET de las tareas obtenido con el m´etodo de poda, en presencia de una cache de instrucciones convencional, es equivalente al WCET conseguido mediante el algoritmo Lock-MS en una jerarqu´ıa de memoria formada por un LB y una Lockable iCache. Las diferencias del WCET de cada tarea calculado mediante estas dos t´ecnicas var´ıan poco, entre un −3,8 % y un 7,4 %. Tambi´en hemos analizado el speed-up del tiempo de respuesta de los conjuntos de tareas small ymedium. Con el fin de determinar el coste de las interferencias extr´ınsecas de la cache, para cada tarea se ha tenido en cuenta el peor caso de expulsi´on, es decir se ha considerado el n´umero m´aximo de l´ıneas de memoria que puede tener cada tarea en la cache. En la Figura 4.11 se muestra el speed-up del tiempo de respuesta de la tarea de menor prioridad del conjunto de tareas small. Como se observa, el comportamiento de ambos m´etodos de an´alisis es equivalente. Adem´as, al aumentar el tama˜no de la cache, entre el 20 % y el 40 % del tama˜no del c´odigo del conjunto de tareas analizado, no se obtiene una mejora significativa en ninguno de los dos m´etodos. En particular, con caches peque˜nas el algoritmo Lock-MS funciona mejor que el m´etodo de poda din´amica. Por ejemplo, su rendimiento es mejor si la capacidad de la cache var´ıa entre el 5 y el 10 % del tama˜no del c´odigo del conjunto de tareas considerado. Esto es debido a que las interferencias intr´ınsecas de cache son mayores en caches convencionales de peque˜no tama˜no, mientras que estas interferencias desaparecen al fijar el contenido de la cache. Cuando la capacidad de la cache est´a entre el 20 y el 80 % del tama˜no del c´odigo del conjunto de tareas considerado, el rendimiento es similar con ambas t´ecnicas de an´alisis, ya que las diferencias entre ambos m´etodos son inferiores al 5 %. Esta tendencia tambi´en se mantiene cuando se analiza el conjunto de tareas medium. No obstante, en este caso y debido al mayor n´umero de cambios de contexto, el sistema s´olo es planificable si la capacidad de la cache convencional est´a entre el 40 y el 80 % del tama˜no del c´odigo del conjunto de tareas considerado, y el speed-up del tiempo de respuesta es inferior a 1,1, por eso no se ha presentado la gr´afica de resultados. 114 4. EL WCET CON CACHES BLOQUEADORAS. An´alisis del conjunto de tareas small Lock-MS Cache convencional 1 1.2 1.4 1.6 1.8 2 2.2 8 sets 16 sets 32 sets 64 sets 128 sets Speed-up del tiempo de respuesta Cache de correspondencia directa con capacidad desde 128 bytes a 2 KB 5 % 10 % 20 % 40 % 80 % Figura 4.11: Comportamiento de Lock-MS vs. caches convencionales. En definitiva, estos dos m´etodos de an´alisis y c´alculo del WCET, tanto el m´etodo de poda din´amica de caminos, como el algoritmo Lock-MS, en las jerarqu´ıas de memoria particulares para las que se han dise˜nado cada uno de ellos, proporcionan un WCET equivalente en las tareas analizadas. Coste computacional de Lock-MS El coste computacional del an´alisis de los conjuntos de tareas small ymedium de la Tabla 4.3 considerados en los experimentos no es relevante, ya que la soluci´on del problema ILP se obtiene en unos pocos milisegundos. No obstante, el coste computacional del algoritmo Lock-MS depende de la estructura y del tama˜no de las tareas analizadas, y del solver que se utiliza para solucionar el problema ILP. Para observar de una forma m´as exacta el coste computacional del algoritmo Lock-MS, se ha creado una colecci´on de tareas sint´eticas en las que el an´alisis es m´as complejo. Se trata de un conjunto de tareas, cuyo tama˜no var´ıa entre 16 KB y 96 KB, que se han dise˜nado con diversas estructuras condicionales if-then-else consecutivas para conseguir aproximadamente unos 2216 posibles caminos de ejecuci´on. Todas estas tareas sint´eticas se han analizado en la jerarqu´ıa de memoria que se describe en la Figura 4.1. En la Tabla 4.4 se resume CAP´ ITULO 4. 115 el conjunto de experimentos realizados para los que se han considerado tres tama˜nos de cache. En total se han realizado 33 experimentos en un Intel Xeon de 64-bits a 2 GHz. El solver utilizado ha sido lp solve versi´on 5.5.0.14 con las opciones por defecto. Tareas iCache (64 conjuntos) Caminos Tama˜no(KB) V´ıas Capacidad(KB) 236 16 4,8,12 4,8,12 272 32 8,16,24 8,16,24 2108 48 12,24,36 12,24,36 2144 64 16,32,48 16,32,48 29,218,230,254,2108,2162,2216 96 24,48,72 24,48,72 Tabla 4.4: Espacio experimental para los programas sint´eticos. En los experimentos efectuados se considera la funci´on a minimizar Wcost de la Ecuaci´on 4.11 y para el c´alculo del WCET de cada tarea el conjunto de restricciones de la Ecuaci´on 4.15. El solver obtiene la soluci´on real muy r´apidamente, ya que el espacio de soluciones es continuo. ´ Esta es la soluci´on ´optima del problema, pero puede que en algunas ocasiones no sea v´alida porque no es entera. Si la soluci´on real no es v´alida, el solver obtiene una soluci´on entera en muy poco tiempo. Esta soluci´on no suele ser la ´optima, pero suele aproximarse bastante. No obstante, el solver sigue verificando otras soluciones hasta que encuentra la ´optima o se da por finalizada la resoluci´on del problema al sobrepasar el l´ımite de tiempo indicado. Si la diferencia entre una soluci´on entera y la soluci´on real es peque˜na, ser´a muy dif´ıcil que la soluci´on entera se pueda mejorar, ya que podr´ıa ser ya la ´optima. Por lo tanto, una soluci´on entera del problema s´olo se puede mejorar si la diferencia entre la soluci´on entera y la soluci´on real es grande. En la Figura 4.12 se muestra la distribuci´on acumulada de las diferencias entre la primera soluci´on entera y la soluci´on real del problema asociada a los experimentos realizados. En el eje Xse representan las diferencias entre ambas soluciones y en el eje Yse representa el n´umero de ocurrencias. Como se observa, en el 28 % de los casos la diferencia es 0, es decir la primera soluci´on entera y la soluci´on real coinciden. Para el resto, la diferencia est´a por debajo del 0,45 %. Es decir, en el 72 % de los casos, la sobrestimaci´on en el WCET que se producir´ıa utilizando la primera soluci´on entera, ser´ıa de unos 5 ciclos de procesador por cada 1000 utilizados. Adem´as, puesto que la soluci´on real del problema no es v´alida, tambi´en es posible que la primera soluci´on entera encontrada por el solver sea la ´optima. En la Figura 4.13 se muestra una comparativa entre el tiempo de an´alisis de ambas soluciones, la primera soluci´on entera y la soluci´on real. En el eje X de la gr´afica se representa el tama˜no de cada tarea analizada, mientras que en el eje Yse indica el tiempo de an´alisis. Los tama˜nos base de la iCache con- 116 4. EL WCET CON CACHES BLOQUEADORAS. 0 20 40 60 80 100 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Porcentaje de experimentos con diferencias ≤x Diferencias (en %) entre la soluci´on entera y la soluci´on real Figura 4.12: Distribuci´on de diferencias entre las soluciones enteras y las reales. siderados en los experimentos son 4, 8 y 12 KB. As´ı pues, para cada tarea se han analizado tres tama˜nos de cache, y el tiempo de an´alisis de cada soluci´on se ha representado con la misma marca. En la Figura 4.13 tambi´en se muestra la curva de tendencia que sigue el tiempo de an´alisis en funci´on del tama˜no de las tareas. Se observa de forma clara que el tiempo de an´alisis crece en funci´on de la complejidad del problema. En la parte superior izquierda tambi´en aparecen representadas las ecuaciones de las curvas de tendencia del tiempo de an´alisis de ambas soluciones. Por lo tanto, el tiempo de an´alisis crece de forma cuadr´atica en funci´on de la complejidad, es decir, en funci´on del tama˜no del c´odigo, del n´umero de caminos de la tarea y del tama˜no de cache considerado. Para finalizar este an´alisis sobre el coste computacional del algoritmo LockMS, en la Figura 4.14 se muestra un estudio equivalente para observar la influencia del n´umero de caminos en el tiempo de an´alisis del problema. Para realizar este experimento se ha analizado la tarea sint´etica de mayor tama˜no (96 KB) con un n´umero de caminos que var´ıa desde 29hasta 2216. La cache considerada es de 64 conjuntos con 24, 48 y 72 v´ıas para tener un tama˜no total de cache de 24, 48 y 72 KB respectivamente. La gr´afica de la Figura 4.14 indica que el tiempo de an´alisis no presenta una clara tendencia ascendente con respecto al n´umero de caminos de la tarea, esto significa que el n´umero de caminos no aumenta el tiempo de an´alisis. Pero adem´as, el tiempo de an´alisis de programas m´as grandes y con mayor n´umero de caminos tambi´en es peque˜no. Por ejemplo, analizar algunas tareas sint´eticas de m´as de 96 KB de tama˜no, con un n´umero de caminos mayor de 1065 en una cache asociativa de 72 v´ıas, ha costado menos de CAP´ ITULO 4. 117 Soluci´on entera y= 6,871 ·10−3x2,179 Soluci´on real y= 2,229 ·10−3x2,320 0 20 40 60 80 100 120 140 160 180 10 20 30 40 50 60 70 80 90 100 Tiempo (en segundos) invertido en el an´alisis Tama˜no (en KB) del programa 236 Paths 272 Paths 2×iC base 2108 Paths 3×iC base 2144 Paths 4×iC base 2216 Paths 6×iC base Figura 4.13: Tiempo de an´alisis en funci´on de la Lockable iCache y del tama˜no del programa. 3 minutos. En particular, este tiempo es relativamente peque˜no en comparaci´on con el de otros modelos de an´alisis y c´alculo del WCET basados en ILP, que han sido criticados por tener un coste computacional demasiado grande [107, 197]. 4.5. Conclusiones En este cap´ıtulo se analiza el comportamiento en el peor caso de una jerarqu´ıa de memoria formada por un LB y una Lockable iCache (ver Figura 4.1). Para obtener el mejor rendimiento de esta jerarqu´ıa de memoria, en un sistema de tiempo real multitarea, se ha propuesto el algoritmo Lock-MS, que obtiene las l´ıneas de memoria de cada tarea del sistema que se cargar´an y fijar´an durante su ejecuci´on en la Lockable iCache. El algoritmo Lock-MS est´a basado en ILP y su objetivo es obtener la m´axima planificabilidad del sistema en esta jerarqu´ıa de memoria, teniendo en cuenta adem´as, tanto el WCET de cada tarea, como el coste de los cambios de contexto del sistema. El algoritmo Lock-MS no es especialmente sensible a la asociatividad, por lo tanto este algoritmo puede obtener una buena planificabilidad del sistema con caches de correspondencia directa. Adem´as, con caches de capacidad peque˜na, comprendidas entre el 5 % y 10 % del c´odigo del sistema, el algoritmo Lock-MS consigue que el sistema sea planificable. En sistemas multitarea con expulsiones, 118 4. EL WCET CON CACHES BLOQUEADORAS. Soluciones enteras Soluciones reales (64 S ×24 w) Sol. Entera Sol. Real (64 S ×48 w) Sol. Entera Sol. Real (64 S ×72 w) Sol. Entera Sol. Real 40 60 80 100 120 140 160 180 200 220 240 1 1e+10 1e+20 1e+30 1e+40 1e+50 1e+60 1e+70 Tiempo (en segundos) invertido en el an´alisis N´umero de posibles caminos de ejecuci´on en la tarea Figura 4.14: Tiempo de an´alisis en funci´on del n´umero de condicionales. el coste de los cambios de contexto es determinante para lograr buenas prestaciones, pero debido a este coste, cuando la capacidad de la cache es grande, de aproximadamente un 80 % del c´odigo del sistema, algoritmos que bloquean la cache durante toda la vida del sistema como Lock-MU [147] pueden superar en rendimiento al algoritmo Lock-MS presentado. Los resultados obtenidos muestran que el redimiendo, en el peor caso, de una jerarqu´ıa de memoria formada por un LB y una Lockable iCache puede ser incluso mejor que el rendimiento de una cache de instrucciones convencional. Por lo tanto, la utilizaci´on de esta jerarqu´ıa de memoria est´a totalmente justificada en sistemas de tiempo real. Tambi´en conviene recordar que la Lockable iCache es totalmente predecible y evita la complejidad exponencial de los condicionales dentro de bucles. Por otra parte, el LB captura muy bien la localidad espacial mejorando considerablemente el rendimiento de la jerarqu´ıa de memoria. El m´etodo Lock-MS tiene un coste computacional relativamente bajo, pero, cuando el n´umero de caminos del programa es grande, representar todos estos caminos mediante restricciones lineales no es posible. No obstante, tambi´en hemos propuesto un modelo compacto de Lock-MS que permite reducir el n´umero de caminos del problema ILP, sin perder precisi´on en el WCET obtenido. El tiempo de resoluci´on del problema ILP para el modelo compacto crece aproximadamente de forma cuadr´atica con respecto a la complejidad del problema, principalmente en funci´on del tama˜no de las tareas analizadas. Esto permite analizar c´odigos grandes en un tiempo relativamente peque˜no. Cap´ıtulo 5 Una jerarqu´ıa de memoria para sistemas de tiempo real En la actualidad, uno de los mayores costes en la ejecuci´on de una instrucci´on sigue siendo su b´usqueda en la memoria. Las t´ecnicas de preb´usqueda tratan de llevar a la CPU un nuevo bloque de la memoria antes de que sea referenciado. La preb´usqueda intenta predecir los futuros accesos a memoria, para ocultar la latencia en dichos accesos. As´ı pues, durante la ejecuci´on se solicita, de forma especulativa, un nuevo bloque de memoria al siguiente nivel de la jerarqu´ıa. El hardware de preb´usqueda es sencillo y no necesita el soporte del software, ni para decidir la solicitud de un bloque de memoria, ni para indicar el instante en el que se debe traer dicho bloque al procesador para mejorar su rendimiento [113, 156, 179]. Con objeto de elegir los bloques de memoria que se llevar´an al procesador, se utilizan algoritmos basados en alg´un tipo de correlaci´on asociada a cierta informaci´on recogida durante la ejecuci´on. As´ı por ejemplo, los fallos de cache durante los accesos a memoria ayudan a resolver si un determinado bloque de memoria se solicitar´a de forma especulativa [86, 167]. En estos casos la preb´usqueda necesita guardar en tablas esta informaci´on para decidir si un determinado bloque se solicita a memoria o no. Otra forma de preb´usqueda m´as sencilla es simplemente solicitar el siguiente bloque de memoria. Esta t´ecnica conocida como preb´usqueda secuencial se basa en algunas de las siguientes pol´ıticas: Ordenar la lectura de la l´ınea de memoria memLinei+1 siempre que se realiza un acceso a la l´ınea memLinei(next-line always) [85]. Si se produce un fallo en el acceso a una l´ınea de memoria, se ordena 119 120 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. tambi´en la lectura de la l´ınea siguiente (next-line on miss) [143]. Cada l´ınea de memoria tiene asignado un bit de estado que durante la preb´usqueda est´a a cero. Cuando se accede por primera vez, y se produce un acierto, el bit de estado cambia y se ordena la lectura de la siguiente l´ınea de memoria (next-line tagged) [164]. Todos estos esquemas se pueden extender en grado, es decir, se puede aumentar el n´umero de l´ıneas que se solicitar´an as´ı como la distancia entre las l´ıneas a prebuscar [164, 143]. En la literatura es habitual encontrar t´ecnicas de an´alisis de la cache de instrucciones en el peor caso. Algunas de estas t´ecnicas incluyen un sencillo LB (Line Buffer) para mejorar el rendimiento de la jerarqu´ıa de memoria, ya que permite explotar la localidad temporal a un coste reducido, y su an´alisis no presenta dificultades relevantes. Pero en sistemas de tiempo real, el hardware de preb´usqueda no se ha utilizado porque es dif´ıcil modelar est´aticamente su comportamiento. Adem´as, el hardware de preb´usqueda poluciona la cache aumentando la dificultad de predecir su funcionamiento. En este cap´ıtulo se introduce una importante mejora en la arquitectura de memoria descrita en el Cap´ıtulo 4 (ver Figura 4.1). Se trata de incorporar un sencillo almac´en de preb´usqueda que se actualiza con la siguiente l´ınea de memoria del programa a la que se acceder´a. El resultado es una nueva jerarqu´ıa de memoria, cuyo comportamiento temporal en el peor caso se puede modelar de una forma muy precisa, y cuyas prestaciones son ideales para un sistema de tiempo real. Al considerar una cache que bloquea su contenido durante la ejecuci´on, desaparece el problema de la poluci´on, ya que la preb´usqueda no puede modificar el contenido de la cache. Adem´as, al combinar en la jerarqu´ıa de memoria un LB (Line Buffer) y un PB (Prefetch Buffer) se reduce considerablemente el tama˜no de la cache de instrucciones y tambi´en aumenta la planificabilidad del sistema. Para conseguir el m´aximo rendimiento de esta nueva jerarqu´ıa de memoria que proponemos, es necesario actualizar el algoritmo Lock-MS (Lock for Maximize Schedulability) que selecciona las l´ıneas a fijar en la cache, para que la planificabilidad del sistema sea m´axima. En la siguiente secci´on se describe la nueva jerarqu´ıa de memoria que proponemos para sistemas de tiempo real y se explica su funcionamiento. 5.1. Jerarqu´ıa de memoria con preb´usqueda Como se observa en la Figura 5.1, la nueva jerarqu´ıa de memoria est´a formada por tres componentes: una Lockable iCache, un LB (Line Buffer)yunPB(Pre- CAP´ ITULO 5. 121 decode Lockable iCache register file Embedded SRAM memory LB PB Figura 5.1: Jerarqu´ıa de memoria para sistemas de tiempo real con preb´usqueda. fetch Buffer). Su funcionamiento es totalmente predecible y su an´alisis temporal se puede formular como un problema ILP equivalente al problema del Cap´ıtulo 4. A continuaci´on describimos cada uno de los componentes de esta nueva jerarqu´ıa de memoria y explicamos su funcionamiento general. Una Lockable iCache La Lockable iCache permite aprovechar la localidad temporal, como ya se ha descrito en el Cap´ıtulo 4. Se trata de una cache de instrucciones que puede fijar su contenido. Por lo tanto su comportamiento es totalmente predecible, ya que todo tipo de interferencias de cache desaparecen. La cache quedar´a bloqueada durante la ejecuci´on de cada tarea y se podr´a actualizar su contenido en cada cambio de contexto. Un Line Buffer Un LB captura la localidad espacial. Se trata de un peque˜no almac´en de l´ınea de instrucciones que mejora considerablemente el rendimiento de la jerarqu´ıa de memoria, con un coste m´ınimo. El LB es un componente habitual en procesadores empotrados, y su funcionamiento se podr´ıa decir que es equivalente al funcionamiento de una cache con una ´unica l´ınea. Un almac´en de preb´usqueda: Prefetch Buffer Dispone de un almac´en de preb´usqueda (PB/ Prefetch Buffer) para mejorar todav´ıa m´as la localidad espacial. El PB captura de forma especulativa la siguiente l´ınea f´ısica de memoria. Se trata de una implementaci´on particular de 122 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. preb´usqueda secuencial basada en la pol´ıtica next-line tagged. La preb´usqueda generar´a un acierto si se accede a la siguiente l´ınea de memoria en secuencia; pero si se realiza un salto en la secuencia habitual de ejecuci´on, se producir´a un fallo. Adem´as, el hardware de preb´usqueda no poluciona la cache en ning´un instante, ya que su contenido est´a bloqueado durante la ejecuci´on de cada tarea. Funcionamiento Durante la etapa de fetch de una instrucci´on se realiza una b´usqueda en paralelo en los tres componentes, es decir, en la Lockable iCache, en el LB y en el PB. Si se produce un acierto en alguna de estas tres estructuras, las instrucciones se sirven en un ciclo de procesador. Pero si se produce un fallo, es necesario solicitar la l´ınea de memoria al siguiente nivel de la jerarqu´ıa de memoria, que en este caso consiste en una eSRAM para sistemas empotrados de altas prestaciones. Posteriormente el LB se actualizar´a con la l´ınea de memoria solicitada. En la Figura 5.2 se muestra un esquema de las operaciones de la preb´usqueda en la etapa de fetch de una instrucci´on cuando la Lockable iCache dispone de un puerto dual. Para respaldar la preb´usqueda secuencial que se propone, tanto la Lockable iCache, como el LB y el PB disponen de un bit para informar al controlador de preb´usqueda del primer acceso a su contenido y poder comenzar una nueva preb´usqueda. Es decir, cuando se produce el primer acierto en alguna de estas tres estructuras, el controlador de preb´usqueda solicita la siguiente l´ınea de memoria a la que supuestamente se acceder´a. Para poder realizar esta operaci´on, suponemos que tambi´en existe un puerto dedicado para que, antes de solicitar la l´ınea al siguiente nivel de la jerarqu´ıa de memoria, el controlador verifique que la l´ınea no est´a en la iCache. S´olo en el caso de que el acceso a esta l´ınea vaya a generar un fallo de cache, es cuando se pide realmente la l´ınea al siguiente nivel de la jerarqu´ıa de memoria. Posteriormente, el PB se actualizar´a con la l´ınea de memoria solicitada. La jerarqu´ıa de memoria propuesta presenta dos comportamientos particulares: a) Cuando todas las instrucciones del LB ya han sido procesadas por la CPU, tanto el LB como el PB intercambian sus funciones. b) Cuando se produce un acierto en la Lockable iCache, tanto el LB como el PB invalidan sus contenidos. Esto elimina cualquier potencial dependencia del camino previamente seguido por el programa durante su ejecuci´on y hace m´as predecible su comportamiento. Finalmente, conviene indicar que el sistema no dispone de otros recursos con latencia variable, como por ejemplo un predictor de saltos o una cache de datos. CAP´ ITULO 5. 129 para diferenciar ambos casos, se ha definido la constante LBCost. Por lo tanto, cuando se produce un fallo de preb´usqueda, se calcula el coste de ejecuci´on de la l´ınea de memoria mediante la siguiente ecuaci´on: LBCosti,j,k =texeci,j,k +tmissLB +thitLB ·(nInsi,j,k −1) (5.5) De forma an´aloga, cuando se produce un fallo de cache, el n´umero de accesos a cada l´ınea de memoria se divide en dos casos, los accesos realizados en secuencia, que son aciertos de preb´usqueda, y los accesos que se producen como destino de salto, que son fallos de preb´usqueda. Para diferenciar estos dos tipos de accesos, se utilizan las constantes nfetchInSequence ynfetchAfterJump respectivamente. Obviamente, estas constantes dependen del n´umero m´aximo de accesos a cada l´ınea de memoria nfetch durante la ejecuci´on de un camino particular. La siguiente ecuaci´on muestra la relaci´on entre cada uno de los tipos de accesos posibles: nfetchi,j,k =nfetchInSequencei,j,k +nfetchAfterJumpi,j,k (5.6) Pero como ya se ha comentado anteriormente, incluso si se produce un acierto en la preb´usqueda, puede aparecer cierta penalizaci´on que se ha de tener en cuenta. Esta nueva penalizaci´on PBPenaltykse da cuando el coste de ejecuci´on de la l´ınea Li,j,k, considerando todos los accesos a las instrucciones de la l´ınea como aciertos hitCosti,j,k, es menor que el tiempo que cuesta actualizar el PB tmissP B con la l´ınea de memoria prebuscada. Esta penalizaci´on ser´a 0 cuando se pueda ocultar totalmente el tiempo de preb´usqueda, es decir, la ejecuci´on de la l´ınea termina despu´es de que el PB se haya actualizado con la l´ınea solicitada. La penalizaci´on m´axima que se puede producir ser´a el tiempo de traer una l´ınea del nivel superior en la jerarqu´ıa de memoria, en este caso ser´a el tiempo de acceso a la IeSRAM menos el coste de ejecutar la l´ınea de memoria a la que se est´a accediendo en ese instante. As´ı pues, la penalizaci´on que se puede sufrir cuando se produce un acierto en la preb´usqueda es la siguiente: PBPenaltyi,j,k = m´ax (0, missP B −hitCosti,j,k−1) Esta penalizaci´on da lugar a dos nuevas restriccciones en el problema ILP: PBPenaltyi,j,k ≥tmissP B −hitCosti,j,k−1 PBPenaltyi,j,k ≥0 (5.7) 130 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. En cualquier caso, una vez que la l´ınea de memoria ya se ha almacenado en el PB, cuando el procesador solicita por primera vez una instrucci´on de dicha l´ınea, el PB pasa a realizar las funciones del LB, y el LB se convierte en el nuevo PB. Por lo tanto, todos los accesos a dicha l´ınea de memoria tienen un coste de thitLB. Para finalizar la descripci´on del modelado ILP del problema, suponemos que un acierto de cache thitCM tiene el mismo coste que un acierto de LB thitLB. Esta suposici´on es habitual y simplifica la notaci´on en las restricciones que describen el problema, ya que as´ı no es necesario especificar si se est´a accediendo a una l´ınea de memoria en la cache o en el LB, aunque para establecer esta distinci´on s´olo se tendr´ıa que a˜nadir una nueva restricci´on al problema. A continuaci´on se describen el conjunto de restricciones asociadas a una l´ınea de memoria Li,j,k que el algoritmo Lock-MS necesita para decidir si dicha l´ınea de memoria se bloquear´a en la cache1: lineCosti,j,k =IChitCosti,j,k ·nIChiti,j,k + PBCosti,j,k·nICmissPBhiti,j,k+ LBCosti,j,k·nICmissPBmissi,j,k IChitCosti,j,k =texeci,j,k +thitCM ·nInsi,j,k PBCosti,j,k=texeci,j,k+PBPenaltyi,j,k+ thitLB ·(nInsi,j,k−1) PBPenaltyi,j,k≥tmissPB −IChitCosti,j,k−1 PBPenaltyi,j,k≥0 nIChiti,j,k =nfetchi,j,k ·cachedl nICmissPBhiti,j,k=nfetchInSequencei,j,k·(1−cachedl) nICmissPBmissi,j,k=nfetchAfterJumpi,j,k·(1−cachedl) nfetchi,j,k=nfetchInSequencei,j,k+nfetchAfterJumpi,j,k Adem´as, en nuestro caso, donde la arquitectura de memoria no est´a exenta de las posibles contenciones causadas por las preb´usquedas err´oneas, tanto en los saltos obligatorios, como en los saltos tomados, la ecuaci´on para obtener el valor de la variable LBCosti,j,k se reemplaza por las siguientes restricciones: LBCosti,j,k=texeci,j,k+contentionPenaltyi,j,k+ tmissLB +thitLB ·(nInsi,j,k−1) 1Las nuevas restricciones del problema ILP para tener en cuenta el comportamiento del PB se han marcado en negrita. CAP´ ITULO 5. 131 contentionPenaltyi,j,k≥tmissPB −contentionCosti,j,m contentionPenaltyi,j,k≥0 Restricciones asociadas a la informaci´on de control Al igual que en el cap´ıtulo anterior, el modelado ILP permite a˜nadir otras restricciones, como por ejemplo las limitaciones que se consiguen durante el an´alisis de flujo de control. Si un bucle contiene varios caminos alternativos, se pueden a˜nadir nuevas restricciones para indicar el n´umero exacto de veces que se ejecutar´a cada uno de los caminos. La forma de modelar estas nuevas restricciones es totalmente equivalente a las ya utilizadas en otros trabajos [6, 107]. Preb´usqueda: Modelo expl´ıcito vs. Modelo compacto La base del algoritmo Lock-MS es la descripci´on de todos y cada uno de los posibles caminos de ejecuci´on, como ya se indic´o en el Cap´ıtulo 4. No obstante, para reducir la complejidad del problema, tambi´en se describi´o un modelo compacto que, en principio, no se puede aplicar directamente a una jerarqu´ıa de memoria con preb´usqueda, ya que depende de la historia de ejecuci´on. En este apartado, para ilustrar c´omo se determinan en general los costes de preb´usqueda en el modelo compacto, se considera el ejemplo de la Figura 5.5. Este ejemplo, ya utilizado en el Cap´ıtulo 4, es bastante representativo, puesto que cada bloque b´asico y sus l´ıneas de memoria abarcan todos los casos de acierto de preb´usqueda que pueden aparecer en un determinado c´odigo. Obviamente, suponemos que ninguna de las l´ıneas de memoria del ejemplo est´a bloqueada en la cache, ya que en estos casos cada acceso se considera como un acierto de cache. Si la jerarqu´ıa de memoria no dispone de preb´usqueda, el coste del primer acceso a cada una de las l´ıneas de memoria ser´a missLB, es decir, se debe considerar un fallo de LB. Pero si la jerarqu´ıa de memoria est´a formada por un LB y un PB, como en la Figura 5.1, cuando se produce un acceso a la siguiente l´ınea de memoria en secuencia, el coste del primer acceso a dicha l´ınea de memoria depender´a de la efectividad de la preb´usqueda, no obstante, se debe tener en cuenta la posible penalizaci´on de preb´usqueda PBPenalty. En este caso, el primer acceso se debe tratar como un acierto de PB. Pero si se produce un acceso despu´es de un salto obligatorio o de un salto tomado, el coste del primer acceso a la l´ınea de memoria ser´a missLB, es decir, se debe tratar como un fallo de preb´usqueda. 132 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. L2a L1 1, 2, . . . L4b 2, . . . L6a L5 L7 1, 2, . . . L6b 1, . . . L2b L3 L4a 1, 2 . . . L1 L3 L5 L7 . . . L2 L4 L6 . . . Figura 5.5: Descripci´on gr´afica del modelo expl´ıcito y del compacto. En la columna etiquetada como Modelo expl´ıcito de la Tabla 5.1 se resume el coste del primer acceso a cada una de las l´ıneas de memoria asociadas a los caminos Path1yPath2de la Figura 5.5. Por claridad en la notaci´on, con super´ındices aparece indicada la l´ınea anterior cuyo coste de ejecuci´on determina la posible penalizaci´on por la preb´usqueda de dicha l´ınea, representada por la variable PBPenalty. Desafortunadamente la transformaci´on al modelo compacto no es directa, llegando en alg´un caso a tener que sobrestimar el coste del primer acceso a la l´ınea de memoria. En la columna etiquetada como Modelo compacto de la Tabla 5.1 se resume el coste del primer acceso a cada una de las l´ıneas de memoria asociadas a los caminos Path1yPath2de la Figura 5.5. El coste del primer acceso a la l´ınea L2a, que es secuencial, depender´a del coste de ejecuci´on de la l´ınea anterior, es decir, de la l´ınea L1. En este caso concreto el coste del primer acceso viene determinado por la constante PBPenaltyL1= m´ax (0, missP B −hitCostL1), donde la constante hitCostL1representa el coste de ejecuci´on de la l´ınea de memoria L1, considerando todos los accesos como aciertos. El coste del primer acceso a las l´ıneas L3,L4a,L5yL6ase calcula de forma equivalente. En todos estos casos, no se produce sobrestimaci´on al asociar directamente estos costes a cada una de las l´ıneas en el modelo compacto. CAP´ ITULO 5. 133 L´ıneas Modelo expl´ıcito Modelo compacto Path 1Path 2 L1missLB missLB missLB L2aPBPenaltyL1PBPenaltyL1P BP enaltyL1 L2b0 - 0 L3PBPenaltyL2-PBPenaltyL2 L4aPBPenaltyL3-PBPenaltyL3 L4b-missLB missLB L5-PBPenaltyL4bPBPenaltyL4b L6a-PBPenaltyL5PBPenaltyL5−missLB L6bmissLB 0missLB L7PBPenaltyL6bPBPenaltyL6P BP enaltyL6b Tabla 5.1: Coste del primer acceso a las l´ıneas de memoria de la Figura 5.5 en la jerarqu´ıa de memoria propuesta. El coste del primer acceso a la l´ınea L4bse ha de tratar como un fallo de PB, ya que esta l´ınea pertenece en exclusividad al camino Path2, y s´olo se puede acceder a ella despu´es de un salto condicional cuando es tomado. En este caso la preb´usqueda fallar´a y el coste del primer acceso ser´a missLB. No obstante, en este caso tampoco se produce sobrestimaci´on al asignar directamente el coste de la l´ınea L4bal modelo compacto. Pero el primer acceso a la l´ınea L6brepresenta un caso en el que se produce una sobrestimaci´on al trasladar dicho coste al modelo compacto. En este caso, se puede acceder a esta l´ınea de dos formas distintas. Si se recorre el camino Path1es destino de salto obligatorio, por lo tanto, al igual que en el ejemplo anterior, la preb´usqueda falla y el coste del primer acceso es missLB. Pero si se recorre el camino Path2, la l´ınea de memoria L6bya est´a en el PB, por lo tanto el coste del primer acceso es 0. Si en el modelo compacto asignamos el valor missLB al coste del primer acceso a la l´ınea L6b, cuando se calcule el coste del camino Path2se producir´a una sobrestimaci´on, puesto que dicha l´ınea ya est´a en el LB. Obviamente, esta sobrestimaci´on s´olo afecta al camino Path2 y para evitarla se puede realizar un ajuste actualizando el coste del primer acceso a la l´ınea L6a, que pertenece en exclusividad al camino Path2. El ajuste a realizar resta dicho valor al coste del primer acceso de la l´ınea L6a, como ya se ha indicado en la Tabla 5.1. Es decir, para evitar la sobrestimaci´on en el primer acceso a la l´ınea L6ben el modelo compacto, se realiza un ajuste en el coste del primer acceso a la l´ınea L6aque viene condicionado por la siguiente expresi´on: P BPenaltyL5−missP B. Desafortunadamente, no se puede realizar un ajuste para evitar la sobrestimaci´on que se produce en el primer acceso a la l´ınea L7. Por un lado, en el camino Path1el coste de ejecuci´on de la l´ınea anterior se corresponde con 134 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. hitCostL6b, mientras que por otro, en el camino Path2se debe considerar el coste de ejecuci´on de la l´ınea L6a, y el de la L6b, es decir, se debe tener en cuenta el coste de ejecuci´on de la l´ınea L6completa. En este caso, en el modelo compacto no se puede evitar la sobrestimaci´on en el primer acceso a la l´ınea L7, ya que forma parte de ambos caminos. Con la jerarqu´ıa de memoria propuesta en este cap´ıtulo, tambi´en podr´ıa ser interesante adoptar una soluci´on intermedia o h´ıbrida entre el modelo explicito y el modelo compacto. Es decir, se pueden tratar algunos trozos del programa de forma expl´ıcita para obtener m´as detalle, tanto de la informaci´on espec´ıfica del flujo de control, como de la historia de ejecuci´on. De esta forma, los resultados conseguidos en algunos trozos del programa son m´as precisos, y en el resto se analizar´ıa con el modelo compacto. Por ejemplo, los trozos de c´odigo en los que la preb´usqueda tiene asociada una gran sobrestimaci´on, se podr´ıan analizar utilizando el modelo expl´ıcito. El resultado parcial se a˜nadir´ıa al resto del tiempo de ejecuci´on del programa determinado con el modelo compacto. 5.3. Evaluaci´on del rendimiento En la siguiente secci´on evaluamos el rendimiento de la jerarqu´ıa de memoria propuesta (ver Figura 5.3), en un sistema de tiempo real multitarea donde se permiten las expulsiones y las tareas tienen prioridad fija. En los experimentos se estudian las tareas que se muestran en la Tabla 5.2, son las mismas que las utilizadas en el Cap´ıtulo 4 y, en este caso, tambi´en se han planificado mediante Rate Monotonic. Conjunto Tarea WCET Periodo Tama˜no con-LB small jfdctint 10108 23248 1072 B crc 109696 329088 536 B matmul 542229 2440031 208 B integral 716633 3583165 400 B medium minver 8522 19601 1360 B qurt 10117 30351 752 B jfdctint 10108 44475 1072 B fft 2886680 15010736 1016 B Tabla 5.2: Conjunto de tareas: small ymedium. Los c´odigos fuente se han compilado con GCC 2.95.2 -O2 y suponemos que el c´odigo de cada tarea se cargar´a en una direcci´on de memoria f´ısica que se corresponda con el conjunto 0 de la cache. El WCET, que aparece indicado en la Tabla 5.2, hace referencia al tiempo de ejecuci´on de peor caso considerando CAP´ ITULO 5. 135 un sistema con LB, es decir, sin cache ni preb´usqueda, y sin tener en cuenta el coste de los posibles cambios de contexto. Los periodos de cada tarea se han elegido para que la utilizaci´on de la CPU en el sistema base sea de 1,2. El conjunto de tareas small ymedium, y la relaci´on entre los periodos de cada tarea, ya se han considerado en trabajos anteriores [6, 147]. Al igual que en el Cap´ıtulo 4, la arquitectura que analizamos en los experimentos es un ARM v7 con instrucciones de 4 bytes. El tama˜no de una l´ınea de memoria es de 16 bytes, tanto en la Lockable iCache, como en el LB y en el PB; por lo tanto, cada l´ınea puede contener hasta 4 instrucciones. En los experimentos realizados, la capacidad de la cache var´ıa desde 128 bytes hasta 4 KB. La memoria principal que tiene una organizaci´on tipo Harvard es de tama˜no fijo. En este caso, tanto la memoria de datos DeSRAM, como la memoria de instrucciones IeSRAM tienen 256 KB. Para determinar el coste de los accesos a memoria se ha utilizado Cacti V.6.0, una herramienta que permite modelar los circuitos de una jerarqu´ıa de memoria [138]. Tambi´en suponemos que esta jerarqu´ıa de memoria formar´a parte de un procesador de alto rendimiento para sistemas empotrados, construido bajo la tecnolog´ıa 32 nm, cuyo ciclo de procesador podr´ıa ser equivalente a 36 FO4. Un procesador de 36 FO4 en la tecnolog´ıa 32 nm tendr´ıa aproximadamente una frecuencia de reloj de unos 2,4 GHz, que est´a en consonancia con la tendencia del mercado actual [1]. Tambi´en se ha verificado que todas las caches analizadas, excepto las totalmente asociativas, pueden proporcionar una instrucci´on en un ciclo de procesador. El tiempo m´ınimo de acceso a una eSRAM de 256 KB, fabricada con transistores de bajo consumo en reserva, podr´ıa ser de unos 7 ciclos. As´ı pues, en los experimentos realizados hemos supuesto que el coste de un acierto de cache o de LB es de 1 ciclo, mientras que el coste de un fallo es de 7 ciclos; con esta latencia de memoria se consigue estresar el funcionamiento de la Lockable iCache. Por otro lado, en caso de producirse un acierto de preb´usqueda, su coste estar´a comprendido entre 1 y 7 ciclos, en funci´on del instante en el que se realiz´o la solicitud de preb´usqueda y del tiempo transcurrido. Tambi´en conviene indicar que todos los accesos a datos se efect´uan directamente a la DeSRAM. Finalmente, los costes de ejecuci´on se han modelado suponiendo que una instrucci´on predicada, que no se ejecuta debido a la condici´on, consume 1 ciclo; y que las instrucciones que se ejecutan, y no son accesos a memoria, lo hacen en 2 ciclos. Todas las instrucciones de acceso a memoria (load ystore) consumen 1+7 ciclos. Localidad espacial con preb´usqueda En este apartado se analiza la influencia de la localidad espacial en el WCET de cada tarea cuando se ejecuta de forma aislada. Los componentes de la jerarqu´ıa de memoria que permiten explotar la localidad espacial son el LB y el PB. 136 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. No obstante, se analiza el WCET de cada tarea en 4 escenarios distintos: En el primer escenario todos los accesos a memoria son fallos, es decir, tanto los accesos a las instrucciones, como a los datos, se realizan directamente a la IeSRAM y a la DeSRAM respectivamente. ´ Este es el escenario m´as pesimista, ya que se asume que ninguno de los componentes de la jerarqu´ıa de memoria propuesta est´a en funcionamiento. Por lo tanto, representa el l´ımite superior en cuanto al coste de los accesos a memoria. En el segundo escenario la jerarqu´ıa de memoria dispone de LB. Aunque este escenario ya se analiz´o con todo detalle en el Cap´ıtulo 4, conviene volver a presentar los resultados logrados, para realizar una comparaci´on con mayor facilidad. En el tercer escenario se tiene en cuenta la preb´usqueda y se a˜nade el PB a la jerarqu´ıa de memoria analizada. Finalmente, en el cuarto escenario se considera un sistema ideal donde todos los accesos a instrucciones son aciertos. Este caso es el m´as optimista. Todos los accesos se realizan directamente desde la cache y ni siquiera se tiene en cuenta la penalizaci´on por cargar las l´ıneas de memoria en la cache. Este escenario representa el l´ımite inferior en cuanto al coste de los accesos a memoria. Es importante destacar que ninguno de los escenarios propuestos incluye el estudio de la Lockable iCache, ya que estamos analizando la localidad espacial en la jerarqu´ıa de memoria propuesta (ver Figura 5.3). As´ı pues, utilizamos la Lockable iCache para capturar la localidad temporal. En la Figura 5.6 se muestra una comparativa de los cuatro escenarios analizados. Los resultados se han normalizado con respecto al primer escenario, en el que todos los accesos se consideran fallos ya que se realizan directamente a la eSRAM. Como se observa en la Figura 5.6, el WCET obtenido, tanto en la jerarqu´ıa de memoria que dispone de LB, como en la que dispone de LB y PB, presenta una reducci´on muy significativa. Esto es debido a que, tanto el LB, como el PB consiguen explotar muy bien la localidad espacial. Por ejemplo, con un simple LB, el WCET se reduce de media en aproximadamente un 47 %. En un sistema con LB y PB, el WCET se reduce de media en un 60 %. Finalmente, en el sistema ideal se reduce el WCET de las tareas analizadas hasta en un 67 %, pero, como ya se ha comentado anteriormente, en este escenario hemos supuesto que todas las instrucciones de la tarea est´an en la cache, sin tener en cuenta el coste de cargar dichas instrucciones en cache. Por lo tanto, la m´axima reducci´on del WCET que se podr´ıa obtener a˜nadiendo, a un sistema que ya dispone de un LB y un PB, una cache de instrucciones para explotar la localidad temporal, ser´ıa de aproximadamente un 7 %, asumiendo que el caso ideal se puede conseguir. Tambi´en conviene indicar que los accesos a datos podr´ıan proporcionar una mejora de aproximadamente el 33 %. CAP´ ITULO 5. 137 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 crc fft integral jfdctint matmul minver qurt media WCET normalizado (accesos a eSRAM ) s´olo LB LB+PB Sistema ideal (1 ciclo) Figura 5.6: WCET de cada tarea en las 4 configuraciones consideradas. En definitiva, teniendo en cuenta que en el sistema ideal el incremento en el rendimiento alcanza de media un 67 %, las mejoras de rendimiento que se pueden obtener en la jerarqu´ıa de memoria propuesta (ver Figura 5.3) son las siguientes: Si la jerarqu´ıa de memoria s´olo dispone de un LB, la mejora en el rendimiento que se alcanza es de un 47 % que representa un incremento relativo del 70 %. En este caso una Lockable iCache podr´ıa aumentar el rendimiento hasta un 30 % m´as. Si la jerarqu´ıa de memoria dispone de un LB y de un PB, la mejora en el rendimiento que se puede alcanzar es de un 60 % que representa un incremento relativo del 90 %. En este caso una Lockable iCache podr´ıa mejorar el rendimiento s´olo hasta un 10 % m´as. Utilizaci´on de la CPU con preb´usqueda En un sistema multitarea tambi´en se puede calcular la utilizaci´on del procesador para medir los efectos de la localidad espacial. La utilizaci´on del procesador se define como la fracci´on de tiempo de la CPU en la que est´a ocupada ejecutando las tareas del sistema en el peor caso. U= NTask X i=1 Wcosti Ti 138 5. JERARQU´ IA DE MEMORIA PARA TIEMPO REAL. Una utilizaci´on del procesador superior a 1 indica que el sistema no es planificable. Pero a´un cuando la utilizaci´on del procesador es inferior a 1, no est´a garantizado que el sistema sea planificable, ya que esta condici´on es necesaria, pero no suficiente. No obstante, cuando la utilizaci´on del procesador es inferior a 1, la planificabilidad del sistema se puede verificar mediante el an´alisis del tiempo de respuesta (RTA/ Response Time Analysis). Mediante RTA se verifica si el tiempo de respuesta Ride cada tarea Taskidel sistema es menor que su plazo de finalizaci´on Di. Es decir, el sistema es planificable si Ri≤Dicon 1 ≤i≤NTask. Como ya se ha comentado anteriormente, los periodos indicados en la Tabla 5.2 se han ajustado para que en ambos conjuntos de tareas, small ymedium, la utilizaci´on del procesador sea de 1,2. Es decir, para que el sistema no sea planificable. Los resultados obtenidos ya indican que en una jerarqu´ıa de memoria sin cache de instrucciones, pero que tenga un LB y un PB, la utilizaci´on del sistema es inferior a 0,9, por lo tanto el sistema ya podr´ıa ser planificable. Para los conjuntos de tareas small ymedium, en la Figura 5.7 se muestra la utilizaci´on del procesador en un sistema donde se accede directamente a la eSRAM ; en este caso el sistema no es planificable en absoluto. Se indica la utilizaci´on del procesador en una jerarqu´ıa de memoria formada ´unicamente por un LB donde la utilizaci´on alcanza el 1,2. Tambi´en se muestra la utilizaci´on del procesador en una jerarqu´ıa de memoria formada por un LB y un PB; en este caso el sistema ya podr´ıa ser planificable. Y finalmente, se expone la utilizaci´on del procesador en un sistema ideal, donde todos los accesos a memoria son aciertos. Con respecto al sistema en el que se accede directamente a la eSRAM, la reducci´on de la utilizaci´on del procesador es cada vez mayor. Por ejemplo, con un simple LB, la utilizaci´on se reduce en casi un 49 %. Cuando se considera un LB y un PB, la utilizaci´on del procesador se reduce hasta un 61 %. En el caso ideal la reducci´on aproximadamente alcanza hasta un 68 %. Como consecuencia de estos resultados, conviene indicar que con una cache de instrucciones la reducci´on m´axima en la utilizaci´on del procesador que se podr´ıa alcanzar, ser´ıa de aproximadamente un 7 %. Por lo tanto, en una jerarqu´ıa de memoria formada por un LB junto con un PB, la localidad espacial se captura perfectamente. As´ı pues, los resultados experimentales confirman que el rendimiento de un sistema de tiempo real aumenta de forma espectacular, con una jerarqu´ıa de memoria formada ´unicamente por un LB y un PB. Adem´as, ambos componentes, y en particular el PB, reducen la influencia de la cache de instrucciones en el WCET de las tareas. An´alisis del tiempo de respuesta con preb´usqueda En el siguiente apartado se compara el tiempo de respuesta obtenido mediante los algoritmos Lock-MU [147] y Lock-MS para los conjuntos de tareas small