PDF de programación - Systematic Analysis of the Cache Behavior of Irregular Codes

Systematic Analysis of the Cache

Behavior of Irregular Codes

Diego Andrade Canosa

Department of Electronics and Systems

University of A Coruña, Spain

Department of Electronics and Systems

University of A Coruña, Spain

PhD THESIS

Systematic Analysis of the Cache

Behavior of Irregular Codes

Diego Andrade Canosa

March of 2007

PhD Advisors:
Basilio B. Fraguela Rodríguez
and Ramón Doallo Biempica

Dr. Basilio B. Fraguela Rodríguez
Profesor Titular de Universidad
Dpto. de Electrónica y Sistemas
Universidad de A Coruña

Dr. Ramón Doallo Biempica
Catedrático de Universidad
Dpto. de Electrónica y Sistemas
Universidad de A Coruña

CERTIFICAN

Que la memoria titulada Systematic Analysis of the Cache Behavior of Irregular
Codes ha sido realizada por D. Diego Andrade Canosa bajo nuestra dirección en el
Departamento de Electrónica y Sistemas de la Universidad de A Coruña y concluye
la Tesis Doctoral que presenta para optar al grado de Doctor en Informática.

A Coruña, 20 de Diciembre del 2006

Fdo.: Basilio B. Fraguela Rodríguez
Codirector de la Tesis Doctoral

Fdo.: Ramón Doallo Biempica
Codirector de la Tesis Doctoral

Fdo.: Luís Castedo Ribas
Director del Dpto. de Electrónica y Sistemas

Resumen de la tesis

Introducción

Existe una enorme diferencia entre la velocidad del procesador y la de la me-
moria. Esta diferencia convierte a la memoria en un cuello de botella que limita el
rendimiento de los computadores. La jerarquía de memoria se utiliza para tratar
de atenuar en lo posible el efecto de este cuello de botella. Se compone de varios
niveles formados cada uno de ellos por memorias implementadas usando diferentes
tecnologías. Las memorias de los niveles superiores son muy rápidas, con velocidades
próximas a las del procesador, pero su tamaño es pequeño. A medida que descende-
mos en la jerarquía las memorias se van haciendo más lentas pero pueden albergar
una mayor cantidad de datos.

La memoria del nivel más bajo de la jerarquía del computador contiene toda
la información disponible. A medida que ascendemos en la jerarquía, cada nivel
contiene un subconjunto de la información contenida en el nivel inferior. El funcio-
namiento de las jerarquías de memoria es sencillo: cuando el procesador necesita un
dato solicita al nivel superior de la jerarquía el bloque de memoria en el que está
contenido. Si el bloque se encuentra en ese nivel la petición es satisfecha y se produce
un acierto, mientras que si el dato no está disponible en ese nivel se produce un fallo
y la petición es trasladada al nivel inferior. Esta petición se propaga hacia abajo en
la jerarquía hasta que el dato se encuentra en alguno de los niveles. En el peor de
los casos, la petición será satisfecha en el nivel más bajo de la jerarquía.

La jerarquía de memoria explota el principio de localidad que en mayor o menor
medida cumplen la mayoría de los procesos ejecutados en un computador. Existen
dos tipos de localidad:

Localidad espacial: si un dato ha sido accedido en un momento dado existe

v

vi

una alta probabilidad de que datos cercanos se accedan proximamente.

Localidad temporal: si un dato ha sido accedido en un momento dado existe
una alta probabilidad de que ese mismo dato vuelva a ser accedido próxima-
mente.

Las jerarquías de memoria están diseñadas de tal forma que los bloques de memoria
más recientemente accedidos van a estar albergados en los niveles superiores de
la jerarquía. Está claro pues que su uso favorece la mejora del rendimiento del
computador porque un alto porcentaje de los accesos a memoria serán resueltos en
los niveles superiores de la jerarquía.

Empezando por el nivel superior, la jerarquía de memoria de un computador
está compuesta típicamente por: los registros del computador, la memoría caché,
dividida a su vez en varios niveles diferentes, la memoria principal y nalmente
el nivel de almacenamiento secundario. Una mejora en la localidad del código a
ejecutar mejoraría el rendimiento de la jerarquía de memoria y en consecuencia la
del computador.

Existen muchas técnicas que tratan de mejorar la localidad de los códigos a eje-
cutar en un computador mejorando así el rendimiento de la memoria. Los diferentes
niveles de caché son la parte de la jerarquía de memoria más usada por el procesador
después de los registros. Por lo tanto es importante tener técnicas que nos permi-
tan conocer de forma rápida y precisa el comportamiento de las cachés durante la
ejecución de un código en un determinado computador. Estas técnicas pueden ser
usadas por ejemplo para guiar procesos de optimización de cara a incrementar la
localidad en los accesos de los programas. Dada la gran disparidad entre la velocidad
de acceso a los datos en las caché en la memoria principal esto puede dar lugar a
grandes reducciones en el tiempo de ejecución.

Las principales técnicas que se usan para estudiar el rendimiento de la memoría

caché son:

Simulación dirigida por traza: Se usa una traza de las direcciones de memoria
accedidas durante la ejecución de un código determinado para medir mediante
un simulador el comportamiento de la caché durante su ejecución. Los prin-
cipales inconvenientes de esta técnica son que es necesario ejecutar el código
para obtener la traza y que la simulación a menudo lleva más tiempo que la
ejecución del código real. A cambio, obtenemos buenos niveles de exactitud en
la medición del rendimiento.

vii

Contadores hardware: Los contadores hardware existen en algunas arquitectu-
ras y miden una gran cantidad de eventos relacionados con el hardware, entre
ellos muchos eventos relacionados con el comportamiento de la caché. Podemos
usar estos contadores durante la ejecución del código para estudiar el compor-
tamiento de la caché. El principal inconveniente es que estos contadores están
presentes sólo en ciertas arquitecturas y que sigue siendo necesario ejecutar el
código para medir el comportamiento de la caché. Como en el caso anterior,
la precisión de las mediciones obtenidas es alta.

Modelado analítico: Podemos utilizar un modelo analítico de la caché para
obtener una predicción de su comportamiento. Como información de entrada
se puede usar una traza de las direcciones de memoria accedidas por el pro-
grama o el propio código fuente a ejecutar. El tiempo necesario para obtener
la predicción es menor que en las dos anteriores técnicas, pero en general suele
tener menor precisión en sus predicciones y la clase de códigos que podemos
modelar debe tener unas características determinadas.

El modelo analítico de las PME (Probabilistic Miss Equations) [31] usa como
información de entrada el código fuente a ejecutar para obtener una estimación rá-
pida y able del comportamiento de la memoría caché de un computador. El modelo
PME está limitado a códigos en los que los patrones de acceso a las estructuras son
regulares. Se han propuesto algunos modelados analíticos para códigos irregulares
concretos basándose en las ideas del modelo PME [30], pero no existe una estrategia
automatizable que aborde el modelado del comportamiento de la caché para esta
clase de códigos. Nuestro propósito es crear una extensión al modelo PME que nos
permita abordar de forma automática el modelado de códigos en los que los accesos
a algunas estructuras de datos siguen patrones de acceso irregulares.

Metodología de Trabajo

Abordar el modelado de códigos irregulares utilizando como primera referencia
un código de complejidad excesiva habría sido un enfoque erróneo del problema.
La lógica impone realizar primero el modelado de un código sencillo e ir renando
sucesivamente el modelado sobre códigos de complejidad creciente.

Cuando se considera el primer código se propone una estrategia automatizable de
modelado que trate de cubrir toda la complejidad de la clase de códigos a modelar.

viii

Se deriva a mano el modelado para ese código utilizando la estrategia propuesta. Se
compara la predicción del modelo propuesto con los resultados obtenidos por una
simulación dirigida por traza considerando distintas conguraciones de la caché y
distintos tamaños de las estructuras involucradas en el código. Lo más probable es
que la primera aproximación no funcione bien en todos los casos. En este caso se trata
de identicar las posibles causas de la divergencia entre el simulador y el modelo
y se proponen modicaciones que mejoren la predicción. Una vez se consiga que la
predicción del modelo sea able para un amplio rango de conguraciones caché y
tamaños de las estructuras involucradas, consideraremos que nuestro modelo realiza
bien el modelado de este código concreto.

Sin embargo, el objetivo de nuestro modelo es cubrir el modelado de cualquier
código irregular, por lo tanto se elige un código un poco más complejo y se deriva el
modelado a mano repitiendo el mismo proceso que en el caso anterior hasta que la
predicción sea able. Es necesario comprobar que cualquier modicación del modelo
no afecta a la abilidad en la predicción para códigos anteriores. Cuando se hayan
modelado con éxito un número razonable de códigos de complejidad creciente con-
sideraremos conseguido el objetivo de tener una estrategia general y automatizable
para el modelado de códigos irregulares.

Contribuciones

La existencia de una referencia con un patrón de acceso irregular se puede deber a
diversos motivos: referencias dependientes de una o varias sentencias condicionales,
estructuras indexadas a través de los valores contenidos en otras estructuras de
datos, la existencia de punteros en el código etc. . .

En este trabajo hemos considerado dos fuentes principales de irregularidad: la
existencia de estructuras de datos afectadas por condicionales y los accesos a través
de indirecciones donde una estructura es indexada utilizando los valores contenidos
en otra estructura diferente. Se han propuesto extensiones automatizables del modelo
PME para ambos casos.

En el caso de sentencias condicionales hemos propuesto una extensión [7, 8, 11,
9, 12] capaz de mo