PDF de programación - Modelado analítico del comportamiento de las memorias caché

UNIVERSIDADE DA CORU ÑA

Departamento de Electrónica e Sistemas

MODELADO ANALÍTICO

DEL COMPORTAMIENTO DE

LAS MEMORIAS CACH É

Basilio Bernardo Fraguela Rodríguez

Marzo, 1999

”Porque la arquitectura es el arte que más se esfuerza
por reproducir en su ritmo el orden del universo, que
los antiguos llamaban kosmos, es decir, adorno, pues es
como un gran animal en el que resplandece la perfección
y proporción de todos sus miembros.”

Adso en El nombre de la rosa,
de Umberto Eco

Esta tesis está dedicada a
quienes me han enseñado a navegar,
quienes han construido mi barco,
y quienes hoy soplan en sus velas.

Agradecimientos

Un trabajo de investigación de la envergadura de una tesis doctoral no
puede llegar a buen puerto sin la colaboración de muchas personas. Quisiera
agradecer en mi primer lugar a mi familia el apoyo incondicional que siempre
me han prestado en todos los sentidos.

Merecen también una mención especial mis directores, el Dr. Ramón Doal-
lo y el Dr. Emilio L. Zapata, por la gran cantidad de horas que han dedicado
a la dirección de este trabajo, y la orientación que me proporcionaron en las
encrucijadas que se me presentaron.

Ha habido también mucha gente que me ha ayudado en multitud de
problemas técnicos, desde la configuración de mi estación de trabajo, en la que
la colaboración de Miguel Alonso fue fundamental, hasta el mantenimiento
de la red y muchos de los computadores que he usado, realizados hoy por hoy
en parte por el personal del Centro de Cálculo da Facultade de Informática
(CeCaFI).

Quisiera agradecer a mis compañeros en la docencia de la asignatura que
he venido impartiendo los cuatro últimos años, Tecnoloxía de Computadores,
en especial José R. Sanjurjo y Carlos Vázquez, por las numerosas ocasiones
en que han cargado sobre sus hombros con la mayor parte del peso de la
misma.

Entre las personas que me han aguantado estoicamente a la hora del
café quisiera destacar el valor de Cristina Mejuto y Margarita Amor, de-
biéndole también a esta última la consecución de un estilo LATEX para la
escritura de esta memoria.

En lo tocante a los organismos que han hecho posible la realización de
esta tesis, el Departamento de Electrónica e Sistemas da Universidade da
Coruña puso los medios necesarios para ello, apoyado por la Universidad
en la financiación de los desplazamientos a los congresos relacionados con
este trabajo. Otra parte esencial de la financiación la supusieron los proyec-

tos TIC96-1125-C03 del CICYT y XUGA20605B96 de la Xunta de Galicia.
También el Edinburgh Parallel Computer Centre (EPCC) posibilitó, medi-
ante la concesión de una estancia a través del programa TRACS de la Unión
Europea, la preparación y ejecución de varias simulaciones en su CRAY T3D.

Por último, quisiera agradecer a toda la comunidad investigadora en el
área de arquitectura de computadores los avances producidos en los mis-
mos. Hubiera sido muy difícil llevar a cabo muchas de las pruebas necesarias
para verificar nuestros modelos con los computadores de que disponíamos al
comenzar esta tesis.

Índice general

1. El análisis de la jerarquía de memoria

1.1. Estrategias para el estudio del comportamiento de la caché . .

1.2. Trabajos previos

. . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Objetivos y organización de la tesis . . . . . . . . . . . . . . .

2. Aspectos generales del modelado

2.1. Parámetros de entrada . . . . . . . . . . . . . . . . . . . . . .

1

2

4

6

9

9

2.2.

Ideas básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1. Unión de vectores de área . . . . . . . . . . . . . . . . 11

2.2.2. Número de líneas en un vector compitiendo por el mis-

mo conjunto de la caché . . . . . . . . . . . . . . . . . 12

2.3. Patrones de acceso . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1. Acceso secuencial

. . . . . . . . . . . . . . . . . . . . . 14

2.3.2. Acceso a líneas con una probabilidad uniforme de ref-

erencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.3. Acceso a grupos de elementos con una probabilidad

uniforme de referencia . . . . . . . . . . . . . . . . . . 17

2.3.4. Acceso a áreas desplazadas con referencias sucesivas . . 19

2.3.5. Acceso a regiones separadas por una distancia constante 22

2.4. Simplificaciones en el modelado de cachés de correspondencia

directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4.1. Patrones de acceso . . . . . . . . . . . . . . . . . . . . 29

i

ii

ÍNDICE GENERAL

3. Modelado de cachés asociativas por conjuntos para computa-

ciones irregulares

31

3.1. Un procedimiento sistemático . . . . . . . . . . . . . . . . . . 33

3.2. Producto matriz dispersa-vector . . . . . . . . . . . . . . . . . 34

3.2.1. Vectores A y C . . . . . . . . . . . . . . . . . . . . . . . 35

3.2.2. Vectores R y D . . . . . . . . . . . . . . . . . . . . . . . 36

3.2.3. Vector X . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2.4. Validación y análisis

. . . . . . . . . . . . . . . . . . . 38

3.3. Producto matriz dispersa-matriz densa: orden JIK . . . . . . . 42

3.3.1. Vectores A y C . . . . . . . . . . . . . . . . . . . . . . . 43

3.3.2. Vector R . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.3. Validación . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.4. Producto matriz dispersa-matriz densa: orden IKJ . . . . . . . 46

3.4.1. Vector R . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4.2. Vectores A y C . . . . . . . . . . . . . . . . . . . . . . . 47

3.4.3. Matriz D . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.4.4. Matriz B . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.4.5. Validación . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.5. Producto matriz dispersa-matriz densa: orden IJK . . . . . . . 49

3.5.1. Vectores A y C . . . . . . . . . . . . . . . . . . . . . . . 51

3.5.2. Matriz D . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.5.3. Matriz B . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.5.4. Validación y análisis

. . . . . . . . . . . . . . . . . . . 53

3.6. Trasposición de una matriz dispersa . . . . . . . . . . . . . . . 56

3.6.1. Vector A . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.6.2. Vector R . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.6.3. Vectores AT y CT . . . . . . . . . . . . . . . . . . . . . 58

3.6.4. Vector C . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.6.5. Vector RT . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.6.6. Validación y análisis

. . . . . . . . . . . . . . . . . . . 65

ÍNDICE GENERAL

iii

3.7. Producto matriz dispersa-matriz densa con orden IKJ alta-

mente optimizado . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.7.1. Vector R . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.7.2. Vector R2 . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.7.3. Vector A . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.7.4. Vector C . . . . . . . . . . . . . . . . . . . . . . . . . . 76

3.7.5. Vector D . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.7.6. Vector B . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.7.7. Vector WB . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.7.8. Validación y análisis

. . . . . . . . . . . . . . . . . . . 83

3.8. Tiempos de simulación versus tiempos de modelado . . . . . . 90

4. Otras distribuciones: matrices banda

93

4.1. Bandas uniformes . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.1.1. Producto matriz dispersa-vector . . . . . . . . . . . . . 94

4.1.2. Producto matriz dispersa-matriz densa: orden JIK . . . 97

4.1.3. Producto matriz dispersa-matriz densa: orden IKJ . . . 98

4.1.4. Producto matriz dispersa-matriz densa: orden IJK . . . 100

4.1.5. Trasposición de una matriz dispersa . . . . . . . . . . . 103

4.2. Bandas no uniformes . . . . . . . . . . . . . . . . . . . . . . . 112

4.2.1. Producto matriz dispersa-vector . . . . . . . . . . . . . 113

4.2.2. Producto matriz dispersa-matriz densa: orden JIK . . . 117

4.2.3. Producto matriz dispersa-matriz densa: orden IKJ . . . 118

4.2.4. Producto matriz dispersa-matriz densa: orden IJK . . . 122

4.2.5. Trasposición de una matriz dispersa . . . . . . . . . . . 123

5. Una aproximación al modelado automático para patrones de

acceso regulares
129
5.1. Ámbito inicial del modelado . . . . . . . . . . . . . . . . . . . 130

5.1.1. Anidamientos perfectos de bucles . . . . . . . . . . . . 131

5.1.2. Ecuaciones del número de fallos . . . . . . . . . . . . . 131

iv

ÍNDICE GENERAL

5.1.3. Cálculo de los vectores de área de interferencia . . . . . 133

5.1.4. Posiciones relativas de las estructuras de datos . . . . . 135

5.1.5. Referencias secuenciales en traslación . . . . . . . . . . 136

5.1.6. Blocking . . . . . . . . . . . . . . . . . . . . . . . . . . 138

5.2. Referencias múltiples a una estructura de datos

. . . . . . . . 140

5.2.1. Formulación del número de fallos en la dimensión donde

difieren las referencias

. . . . . . . . . . . . . . . . . . 140

5.2.2. Referencias que difieren en varias dimensiones . . . . . 143

5.2.3. Cálculo de vectores de área

. . . . . . . . . . . . . . . 143

5.3. Anidamientos no perfectos y reuso de datos entre bucles

. . . 146

5.4. Verificación del modelado automático . . . . . . . . . . . . . . 149

5.5. Tiempos de simulación versus tiempos de modelado . . . . . . 157

Conclusiones y principales aportaciones

Bibliografía

163

166

Índice de cuadros

2.1. Notación empleada. . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1. Parámetros de la matriz. . . . . . . . . . . . . . . . . . . . . . 32

3.2. Desviación del modelo para el producto matriz dispersa-vector. 39

3.3. Desviación del modelo para el producto matriz dispersa-matriz

densa con orden JIK. . . . . . . . . . . . . . . . . . . . . . . .