Dispositivo para controlar el acceso a una estructura de memoria caché.

Un dispositivo para controlar el acceso a una estructura de memoria caché que comprende varios conjuntos caché durante la ejecución de al menos un programa informático,

comprendiendo el dispositivo:

- un módulo para generar valores semilla aleatorios o pseudo-aleatorios durante la ejecución del al menos un programa informático;

- un módulo de función hash paramétrica para generar un identificador de conjunto caché para acceder a la estructura de memoria caché, generándose el identificador mediante la combinación de un valor semilla generado por el módulo para generar valores semilla y unos bits predeterminados de una dirección para acceder a una memoria principal asociada a la estructura de memoria caché.

Dispositivo para controlar el acceso a una estructura de memoria caché

CAMPO DE LA INVENCIÓN

La presente invención se refiere a un procedimiento para controlar el acceso a una estructura de memoria caché que comprende varios conjuntos caché durante la ejecución de al menos un programa informático. Más específicamente, 10 la invención se refiere a un procedimiento capaz de garantizar que a cada dirección accedida por un programa informático se le puede asociar una probabilidad real de ser asignada a cualquier conjunto caché particular de una estructura de memoria caché.

Además, la invención se refiere también a un dispositivo y un producto de programa informático para controlar el 15 acceso a una estructura de memoria caché adecuados para realizar dicho procedimiento.

La invención se puede aplicar a sistemas en tiempo real, por ejemplo sistemas en tiempo real críticos para la seguridad tales como los sistemas de control de vuelo.

ANTECEDENTES DE LA TÉCNICA

Las memorias caché son generalmente búferes pequeños de almacenamiento rápido que se pueden emplear para almacenar información, tal como código o datos, con el fin de que un programa que se ejecuta en un dispositivo de 25 procesamiento se ejecute más rápido. Típicamente, es más rápido para el dispositivo de procesamiento leer la memoria caché que leer una memoria principal. También, con el rápido aumento de los requisitos de procesamiento intensivo, su importancia en un sistema informático sólo irá en aumento.

Una estructura de memoria caché es conceptualmente una matriz de S*W líneas caché (conceptualmente celdas) 30 dispuestas en S conjuntos (conceptualmente filas) y W vías (conceptualmente columnas). El conjunto (es decir, la fila) en el que se coloca un fragmento de datos en la memoria caché es determinado por la política de colocación. La política de colocación implementa una función hash que utiliza ciertos bits de la dirección de memoria en la que se almacena el dato para asignar ese fragmento de datos a un conjunto caché específico (fila). Desde el punto de vista de la memoria caché, se pueden agrupar diferentes fragmentos de datos en lineas caché, o simplemente lineas. 35 Dado que diferentes líneas de memoria pueden colisionar en el mismo conjunto caché, los conjuntos caché consisten en un determinado número de líneas caché denominadas vías (es decir, columnas). Todos los conjuntos tienen el mismo número de vías, que determinan la asociatividad de la memoria caché. Por lo tanto, una memoria caché asociativa por conjuntos de W vías comprende W vías por conjunto. Para un conjunto dado, la vía (linea caché) en la que se coloca una línea de memoria es determinada por la política de reemplazo. En el caso de que un 40 acceso a la memoria caché produzca como resultado un fallo, la política de reemplazo selecciona, de entre todas las vías (columnas) de un conjunto dado (fila), qué línea de memoria es desalojada para dar cabida a la nueva linea de memoria. La nueva línea de memoria es almacenada, entonces, en la línea caché cuyo contenido (una linea de memoria) acaba de ser desalojado. Cada línea puede estar compuesta por una o varias palabras. La granularidad de una palabra se mide generalmente en bytes (por ejemplo, 1, 2 o 4 bytes).

El comportamiento de temporización (timing behaviour) de una memoria caché está determinado principalmente por sus políticas de colocación y reemplazo. El tamaño de la línea, el tamaño de la palabra y otros parámetros de la memoria caché también pueden afectar el comportamiento de temporización de la memoria caché. Para una determinada configuración de memoria caché, tanto el tamaño de la línea como el tamaño de la palabra son fijos.

Se han propuesto memorias caché aleatorias en procesadores de alto rendimiento para eliminar conflictos de memoria caché mediante el uso de funciones hash pseudo-aleatorias [A. González et al. Eliminating cache conflict misses through XOR-based placement functions. In ICS, 1997.][A. Seznec and F. Bodin. Skewed-associative caches. In PARLE. 1993.][Nigel Topham and Antonio González. Randomized cache placement for eliminating 55 conflicts. IEEE Trans. Comput., 48, February 1999], Sin embargo, el comportamiento de todos esos diseños de memoria caché es totalmente determinista. Esto significa que, cada vez que un determinado conjunto de datos de input para un programa hace que el programa genere un patrón de acceso patológico, este patrón se repetirá

sistemáticamente para dicho conjunto de input en todas las ejecuciones del programa. Por lo tanto, aunque se reduce la frecuencia de casos patológicos, todavía pueden aparecer sistemáticamente porque no hay manera de demostrar que su probabilidad está vinculada.

En el dominio de tiempo real el Análisis Probabilístico de Temporización (Probabilistic Timing Analysis - PTA) (véase, por ejemplo, [F. J. Cazorla et al. Proartis: Probabilistically analysable real-time systems. Technical Report 7869 ( http://hal.inria.fr/hal-00663329 ), INRI A, 2012], [D. Grifíin and A. Burns. Realism in Statistical Analysis ofWorst Case Execution Times. In the 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2011), páginas 44-53, 2010] or [J. Hansen, S. Hissam, and G. A. Moreno. Statistical-based WCET estimation and validation. In the 10 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009]) se ha convertido en una prometedora solución efectiva a los problemas de las técnicas actuales de análisis del tiempo de ejecución en el peor caso (Worst-Case Execution Time - WCET), es decir, análisis estático de temporización y análisis de temporización basado en mediciones.

El Análisis Probabilístico de Temporización impone nuevos requisitos en los diseños del hardware. Más específicamente, en el diseño de la memoria caché las técnicas de Análisis Probabilístico de Temporización requieren que el comportamiento de la temporización de los accesos a memoria pueda estar definido por el par de vectores:

en los que / enumera todas las posibles latencias que la jerarquía de memoria puede tomar para servir los datos y

pi su probabilidad asociada de ocurrencia. Se observa que la probabilidad de ocurrencia de una determinada

latencia es diferente a su frecuencia: mientras que la frecuencia proporciona información sobre eventos pasados, las probabilidades permiten ofrecer garantías sobre la ocurrencia de eventos futuros (véase, por ejemplo, [F. J. Cazorla et al. Proartis: Probabilistically analysable real-time systems. Technical Report 7869 ( http://hal.inria.fr/hal-00663329 ), 25 INRIA, 2012]). Por lo tanto, para el caso de un Análisis Probabilístico de la Temporización de un recurso de memoria caché se requiere que para cada acceso haya una probabilidad calculable de acierto o de fallo en la memoria caché.

En H Vandierendonck et al.: "Randomized Caches for Power-Efficiency", IEICE Transactions on Electronics, Institute of Electronics, Tokyo, vol. E86 C, no. 10, 2003, páginas 2137-2144 se presenta una memoria caché que tiene una 30 función de índice de conjunto aleatorizada ajustada (tuned randomized set índex function). La función de aleatorlzaclón se configura cuando se inicia la aplicación y se basa en información de perfiles generada usando inputs representativos.

Existen políticas de reemplazo aleatorias para hacer que la selección de una línea caché (celda) dentro de un 35 conjunto caché (fila) sea aleatoria. Sin embargo, las políticas de colocación existentes son puramente deterministas en base a la dirección accedida. Por lo tanto, que los accesos a dos direcciones diferentes compitan por el mismo conjunto caché depende únicamente de sus direcciones particulares y de la función de colocación utilizada. Por lo tanto, si dos direcciones son colocadas en el mismo conjunto caché al Inicio de la ejecución, éstas colisionarán en ese conjunto caché siempre durante la ejecución del programa y en todas las ejecuciones del programa. Dado que 40 el comportamiento es puramente determinista no se puede calcular una probabilidad real. Por lo tanto, no se satisfacen las propiedades probabilísticas requeridas por el Análisis Probabilístico de la Temporización.

En la seguridad de procesadores, las memorias caché estándar no aleatorias son vulnerables a la fuga de información crítica tal como claves criptográficas. Los ataques a memorias caché estándar se basan únicamente en 45 la diferencia de temporización entre aciertos y fallos en la memoria caché. Rompiendo el deterninismo entre accesos y si aciertan o fallan mediante el uso de memorias caché de reemplazo aleatorio o similares, hace que los aciertos y fallos se produzcan con una determinada probabilidad,... [Seguir leyendo]

1. Un dispositivo para controlar el acceso a una estructura de memoria caché que comprende varios conjuntos 5 caché durante la ejecución de al menos un programa informático, comprendiendo el dispositivo:

- un módulo para generar valores semilla aleatorios o pseudo-aleatorios durante la ejecución del al menos un programa informático;

- un módulo de función hash paramétrica para generar un identificador de conjunto caché para acceder a la estructura de memoria caché, generándose el identificador mediante la combinación de un valor semilla generado

por el módulo para generar valores semilla y unos bits predeterminados de una dirección para acceder a una memoria principal asociada a la estructura de memoria caché.

2. El dispositivo según la reivindicación 1, en el que la estructura de memoria caché comprende 2n conjuntos, y en el que el identificador de conjunto caché generado comprende n bits.

3. El dispositivo según cualquiera de las reivindicaciones 1 o 2, en el que la dirección determinada comprende una secuencia de bits, una parte de los cuales corresponde a un desplazamiento, y en el que los bits predeterminados de la dirección comprenden la secuencia de bits sin el desplazamiento.

4. El dispositivo según cualquiera de las reivindicaciones 1 a 3, en el que la estructura de memoria caché comprende al menos una línea caché por conjunto.

5. El dispositivo según cualquiera de las reivindicaciones 1 a 4, en el que el módulo para generar valores semilla comprende un generador de números pseudo-aleatorios.

6. El dispositivo según cualquiera de las reivindicaciones 1 a 5, que comprende además un módulo de memoria para almacenar los valores semilla generados.

7. Un procedimiento de controlar el acceso a una estructura de memoria caché que comprende varios conjuntos 30 caché durante la ejecución de al menos un programa informático, comprendiendo el procedimiento:

- generar unos valores semilla aleatorios o pseudo-aleatorios durante la ejecución del al menos un programa informático;

- recibir una dirección para acceder a una memoria principal asociada a la estructura de memoria caché;

- generar un identificador de conjunto caché para acceder a la estructura de memoria caché, generándose el 35 identificador mediante la combinación de un valor semilla generado y unos bits predeterminados de la dirección

recibida.

8. Producto de programa informático que comprende instrucciones de programa para hacer que un ordenador realice un procedimiento de controlar el acceso a una estructura de memoria caché que comprende varios conjuntos

caché según la reivindicación 7.

9. Producto de programa informático según la reivindicación 8, almacenado en un medio de almacenamiento.

10. Producto de programa informático según la reivindicación 8, portado en una señal portadora.

11. Una estructura de memoria caché que comprende varios conjuntos caché y el dispositivo para controlar el acceso a la estructura de memoria caché según cualquiera de las reivindicaciones 1 a 6.