Un Ambiente para la Evaluación de Arquitecturas de Memoria en

Loading...

Un Ambiente para la Evaluaci´ on de Arquitecturas de Memoria en Esquemas Multihilo Simult´ aneo Tesis de Grado en Ingenier´ıa Inform´atica Orientaci´on en Sistemas Distribuidos

Augusto J. Vega [email protected]

Director: Dr. Ing. Jos´ e Luis Hamkalo Facultad de Ingenier´ıa Universidad de Buenos Aires

“Se debe hacer todo tan sencillo como sea posible, pero no m´ as sencillo.” Albert Einstein

Resumen En los u ´ltimos a˜ nos, una nueva arquitectura de procesadores conocida como multihilo simult´aneo (SMT − Simultaneous Multithreading), ha crecido en relevancia y ha sido incorporada en los microprocesadores actuales, tales como los Intel Pentium 4 Hyper-Threading y Sun Microsystems UltraSPARC T1. La ejecuci´on de m´ ultiples hilos en un mismo procesador genera interrogantes respecto al desempe˜ no de las unidades funcionales en escenarios donde varios flujos de ejecuci´on compiten por los recursos disponibles. La memoria cach´e de nivel 1 es una de las componentes m´as afectadas, debido a que la existencia de m´ ultiples instrucciones pertenecientes a m´ ultiples hilos de ejecuci´on dentro del procesador genera una situaci´on de competencia que se traduce en una alta interferencia de los hilos en la memoria cach´e. En esta tesis se propone y analiza el desempe˜ no de un nuevo esquema de memoria cach´e para procesadores multihilo. Dado que es una tecnolog´ıa muy reciente, son escasas (o inexistentes en la pr´actica) las herramientas que simulen o aporten los datos necesarios para realizar simulaciones de estos ambientes multihilo. Por esta raz´on, en la primera parte de esta tesis se presenta una herramienta, p´ ublica y de c´odigo abierto, que permite la captura de trazas de referencias a memoria de programas con m´ ultiples hilos de ejecuci´on. La misma fue implementada como un m´odulo para el sistema Valgrind, el cual permite realizar tareas de debugging y profiling sobre programas ejecutables, para ambientes Linuxx86. La herramienta construida se utiliz´o para recolectar las trazas de los programas que conforman los benchmarks SPLASH-2. ii

III

En la segunda parte, se describe una herramienta de simulaci´on construida para este trabajo, que ha sido llamada SimiOO. La misma fue desarrollada en base al paradigma de orientaci´on a objetos, en lenguaje Java, y sobre una arquitectura de plug-ins que le permite ser extendida con nuevas funcionalidades. La herramienta SimiOO y el plug-in de simulaci´on permiten la evaluaci´on de organizaciones de memoria cach´e a partir de las trazas recolectadas anteriormente. Finalmente, en la tercera parte, se presenta la organizaci´on de memoria cach´e SWSA-MT para procesadores multihilo propuesta en esta tesis, y la evaluaci´on de su desempe˜ no. Adem´as, se propone un nuevo modelo para la clasificaci´on de desaciertos para ambientes multihilo, denominado “modelo de las 4C” (y que es una extensi´on del popular “modelo de las 3C”). Este modelo es utilizado para la clasificaci´on de desaciertos en el estudio de la organizaci´on cach´e presentada. Para cerrar la tercera parte, se realizan las conclusiones finales. Adem´as de las herramientas para recolecci´on de trazas y simulaci´on, y el modelo de clasificaci´on de desaciertos, esta tesis contribuye con un nuevo dise˜ no de memoria cach´e para procesadores multihilo. Esta nueva organizaci´on es estudiada y comparada contra esquemas tradicionales asociativos por conjuntos de dos y cuatro v´ıas, observ´andose que el dise˜ no propuesto presenta un desempe˜ no muy superior respecto al asociativo por conjuntos de dos v´ıas, y similar al de una cach´e de cuatro v´ıas, pero con menor complejidad de implementaci´on. Se concluye de esta manera que la organizaci´on cach´e presentada es adecuada para los procesadores multihilo actuales.

Abstract In the last years, a new processor architecture known as Simultaneous Multithreading (SMT), has been incorporated in new processors, such as the Intel Pentium 4 Hyper-Threading and Sun Microsystems UltraSPARC T1 series. The execution of concurrent threads in a processor yields questions about the performance of functional units when several execution flows compete for available resources. Cache memory is one of the most stressed components, since the issuing of instructions belonging to concurrent threads generates a competition situation which turns out in a high inter-thread interference. In this dissertation, a new cache organization for multithreaded processors is studied and analyzed. Because this is a recently developed technology, in practice there are few public tools for studying it. So, the first part of this work presents a new free and open-source tool for collecting memory reference traces from multithreaded workloads. This tool was built as a Valgrind module and it was used in order to collect traces from programs of the SPLASH-2 benchmark suite. Valgrind is a suite of tools for debugging and profiling Linux-x86 programs. The second part describes a simulation tool that was built for this work, which is called SimiOO. This framework was developed in Java, making use of object-oriented programming, and it’s based on a plug-in architecture that allows SimiOO to be extended with new functionalities. The SimiOO framework and the simulation plug-in were used to evaluate cache memory schemes making use of traces previously collected. Finally, the third part presents and analyzes a novel cache memory for iv

V

multithreaded processors, called SWSA-MT. Furthermore, a new miss classification model for multithreaded environments is proposed. This scheme, which is called “4C model”, is an extension of the widely-used “3C model” of cache behavior, and it was used in order to classify misses for the cache memory proposed. Finally, future work and conclusions are presented. Besides of the trace collection and simulation tools, and the 4C miss classification model, this thesis contributes with a new cache memory design for multithreaded processors. This organization is studied and compared against traditional cache schemes, such as two and four-ways set-associative designs. It was observed that the proposed scheme performs better than two-way set associative caches, and it performs similar than four-way set associative memories, but with a simpler implementation. To conclude, it’s possible to say that this new cache organization is suitable for new multithreaded processors.

Agradecimientos En primer lugar, dedico este esfuerzo a Dios, que es el fin u ´ltimo de todas las cosas, el u ´nico objetivo. Deseo agradecer, adem´as, a muchas personas por su apoyo en este trabajo y en la vida misma. Al Dr. Jos´e Luis Hamkalo, mi tutor en esta tesis, por allanarme el camino y por responderme un mill´on de preguntas. A mis padres, Carlos y Miryam que, sin medir en sacrificios o privaciones propias, entendieron que la educaci´on de un hijo es la mejor inversi´on. Y lo hicieron. Al Lic. Gustavo L´opez, amigo incondicional. A los profesores y amigos del Instituto Parroquial “Sagrada Familia” de mi pueblo natal, Realic´o. A los maestros de mi querida escuela “San Mart´ın” Nro. 34. Ellos entendieron que en las ciencias estaba mi pasi´on.

Augusto J. Vega Febrero de 2007

vi

Acerca del Autor Augusto J. Vega naci´o en la localidad de Realic´o, provincia de La Pampa, el 11 de octubre de 1979. Sus estudios primarios los llev´o a cabo en la Escuela San Mart´ın Nro. 34 de esa localidad. Posteriormente, complet´o los tres primeros a˜ nos del nivel secundario en el Instituto Parroquial Sagrada Familia. En el a˜ no 1996, junto a sus padres y hermana, se mud´o a la ciudad de Chivilcoy, provincia de Buenos Aires, donde finaliz´o sus estudios secundarios en la Escuela de Ense˜ nanza Media Nro. 4. Habiendo comenzado sus estudios universitarios en Buenos Aires, en el a˜ no 1998, actualmente es estudiante de la carrera Ing. en Inform´atica, en la Facultad de Ingenier´ıa, Universidad de Buenos Aires. Adem´as, es docente auxiliar en los departamentos de Computaci´on y Electr´onica.

vii

´Indice general Resumen

II

Abstract

IV

Agradecimientos

VI

Acerca del Autor

VII

1. Introducci´ on 1.1. Motivaciones de la Tesis . . . . . . . . . . . . . . . . . 1.1.1. El Procesamiento Multihilo Simult´aneo (SMT ) 1.1.2. Recolecci´on de Trazas: El M´odulo Tracegrind . 1.1.3. Procesamiento de Trazas y Simulaci´on . . . . . 1.1.4. El Esquema de Memoria Cach´e Propuesto . . . 1.2. Objetivos de la Tesis . . . . . . . . . . . . . . . . . . . 2. Recolecci´ on de Trazas: El M´ odulo Tracegrind 2.1. Introducci´on . . . . . . . . . . . 2.2. Recolecci´on de Trazas . . . . . . 2.3. El Sistema Valgrind . . . . . . . 2.4. El M´odulo Tracegrind . . . . . 2.5. Consideraciones sobre Multihilo 2.6. Validaci´on de Trazas . . . . . . 1

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7 7 8 10 12 12 16

. . . . . .

18 18 19 22 24 25 27

´INDICE GENERAL

2

2.6.1. Un Programa Simple para la Validaci´on de la mienta . . . . . . . . . . . . . . . . . . . . . . 2.6.2. Validaci´on de las Referencias a Instrucciones . 2.6.3. Validaci´on de las Referencias a Datos . . . . . 2.7. Benchmarks SPLASH-2 . . . . . . . . . . . . . . . . 2.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . 3. Procesamiento de Trazas: La Herramienta SimiOO 3.1. Introducci´on . . . . . . . . . . . . . . 3.2. El Proyecto Eclipse . . . . . . . . . . 3.2.1. La Plataforma de Cliente Rico 3.2.2. El Modelo de Plug-ins . . . . 3.3. La Herramienta SimiOO . . . . . . . 3.3.1. Modelo de An´alisis . . . . . . 3.3.2. Dise˜ no General . . . . . . . . 3.4. El Plug-in de Simulaci´on . . . . . . . 3.4.1. Dise˜ no General . . . . . . . . 3.4.2. Integraci´on Dominio−Interfaz 3.4.3. Motor de Simulaci´on . . . . . 3.5. Conclusiones . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . RCP . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Un Esquema de Memoria Cach´ e para Ambientes Multihilo 4.1. Introducci´on . . . . . . . . . . . . . . . . 4.2. Paralelismo a Nivel de Instrucciones . . . 4.3. Procesadores Multihilo . . . . . . . . . . 4.4. Jerarqu´ıa de Memoria . . . . . . . . . . 4.5. Clasificaci´on de Desaciertos . . . . . . . 4.6. Otros Criterios y M´etricas . . . . . . . . 4.7. El esquema de banco compartido SWSA

. . . . . . .

. . . . . . .

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

. . . . . . .

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

. . . . . . .

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

. . . . . . .

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

. . . . . . .

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

. . . . . . .

Herra. . . . . . . . . . . . . . . . . . . .

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

. . . . . . .

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

. . . . . . .

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

. . . . . . .

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

. . . . . . .

. . . . .

28 30 34 36 37

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

39 39 40 40 41 43 44 48 51 51 53 54 54

. . . . . . .

56 56 57 60 64 66 69 69

´INDICE GENERAL

4.8. Adaptaci´on del esquema SWSA a un ambiente SWSA-MT . . . . . . . . . . . . . . . . . . . . . . 4.8.1. An´alisis de Asociatividad . . . . . . . . . . 4.9. El Modelo de las 4C . . . . . . . . . . . . . . . . 4.10. Ambiente de Simulaci´on . . . . . . . . . . . . . . 4.10.1. Herramientas . . . . . . . . . . . . . . . . 4.10.2. Arquitecturas Simuladas . . . . . . . . . . 4.10.3. Benchmarks . . . . . . . . . . . . . . . . . 4.11. Resultados de las Simulaciones . . . . . . . . . . . 4.11.1. Tasa de Desaciertos . . . . . . . . . . . . . 4.11.2. Clasificaci´on de Desaciertos . . . . . . . . 4.11.3. Tasa de Aciertos Compartidos . . . . . . . 4.11.4. Tasa de Reubicaci´on . . . . . . . . . . . . 4.12. Esquemas Privados . . . . . . . . . . . . . . . . . 4.13. Subexplotaci´on de la Cach´e . . . . . . . . . . . . 4.14. Aspectos de Implementaci´on . . . . . . . . . . . . 4.15. Conclusiones . . . . . . . . . . . . . . . . . . . . .

3

multihilo: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

71 72 73 74 74 75 75 77 77 79 83 83 87 89 92 97

5. Conclusiones 100 5.1. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . 103 A. Tracegrind: Detalles y Modo de Uso 105 A.1. Detalles de Implementaci´on . . . . . . . . . . . . . . . . . . . 105 A.2. Modo de Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 B. C´ odigo Fuente del M´ odulo Tracegrind 110 B.1. C´odigo Fuente . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

´Indice de figuras 1.1. Interacci´on de Valgrind con el programa de usuario y la plataforma de base. . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Niveles de una jerarqu´ıa de memoria cl´asica. . . . . . . . . . . 1.3. Direcci´on de memoria. . . . . . . . . . . . . . . . . . . . . . . 1.4. Asociatividad en una organizaci´on de banco compartido SWSA 1.5. Asociatividad en la organizaci´on presentada . . . . . . . . . . 2.1. Niveles de abstracci´on en la recolecci´on de trazas. . 2.2. Interacci´on de Valgrind con el programa de usuario taforma de base. . . . . . . . . . . . . . . . . . . . 2.3. El M´odulo Tracegrind. . . . . . . . . . . . . . . . .

. y . .

11 13 14 15 16

. . . . . 19 la pla. . . . . 23 . . . . . 25

3.1. Extensi´on de un plug-in. . . . . . . . . . . . . . . . . . . 3.2. Diagrama de Casos de Uso. . . . . . . . . . . . . . . . . 3.3. Extensi´on de SimiOO mediante el plug-in de simulaci´on. 3.4. Almacenamiento y lectura de trazas en SimiOO. . . . . . 3.5. Modelado de memorias cach´e en el plug-in de simulaci´on. 3.6. Modelado de la pol´ıtica de reemplazo en el simulador. . . 3.7. Interfaz gr´afica de SimiOO, presentada al usuario. . . . . 3.8. Integraci´on SimiOO - Plug-in. . . . . . . . . . . . . . . . 3.9. Interfaz gr´afica del simulador. . . . . . . . . . . . . . . . 3.10. Modelo de clases del motor de simulaci´on. . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

43 45 46 47 47 48 50 52 53 55

4.1. Tuber´ıa de 5 etapas. . . . . . . . . . . . . . . . . . . . . . . . 58 4

´INDICE DE FIGURAS

4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. 4.9.

Uso de los recursos en arquitecturas Superescalar, FMT y SMT. Niveles de una jerarqu´ıa de memoria cl´asica. . . . . . . . . . . Direcci´on de memoria. . . . . . . . . . . . . . . . . . . . . . . Esquema de asociatividad en una organizaci´on SWSA. . . . . Esquema de asociatividad en la organizaci´on SWSA-MT. . . . Organizaci´on SWSA-MT de tama˜ no T = 2×P + C. . . . . . . Tasa de desaciertos para los benchmarks FFT y LU. . . . . . . Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER. . . . . . . . . . . . . . . . . . . . . 4.10. Clasificaci´on de desaciertos para el benchmark FFT. . . . . . . 4.11. Clasificaci´on de desaciertos para el benchmark LU. . . . . . . 4.12. Clasificaci´on de desaciertos para el benchmark CHOLESKY. . 4.13. Clasificaci´on de desaciertos para el benchmark RADIX. . . . . 4.14. Clasificaci´on de desaciertos para el benchmark OCEAN. . . . . 4.15. Clasificaci´on de desaciertos para el benchmark WATER. . . . . 4.16. Tasa de aciertos compartidos para los benchmarks FFT y LU. 4.17. Tasa de aciertos compartidos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER. . . . . . . . . . . . . . 4.18. Acierto “largo”. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.19. Tasa de reubicaci´on para los benchmarks FFT y LU. . . . . . 4.20. Tasa de reubicaci´on para los benchmarks CHOLESKY, RADIX, OCEAN y WATER. . . . . . . . . . . . . . . . . . . . . 4.21. Organizaci´on SWSA-MT y esquemas privados 2WSA y 4WSA. 4.22. Tasa de desaciertos para los benchmarks FFT y LU. . . . . . . 4.23. Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER. . . . . . . . . . . . . . . . . . . . . 4.24. Tasa de desaciertos para los benchmarks FFT y LU de un u ´nico hilo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.25. Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER de un u ´nico hilo. . . . . . . . . . . . 4.26. Diagrama en bloques del esquema 2WSA. . . . . . . . . . . .

5

63 65 66 70 72 74 77 78 80 80 81 81 82 82 84 85 86 87 88 89 90 91 92 93 95

´INDICE DE FIGURAS

6

4.27. Diagrama en bloques del esquema 4WSA. . . . . . . . . . . . 96 4.28. Diagrama en bloques del esquema SWSA-MT. . . . . . . . . . 98

Cap´ıtulo 1 Introducci´ on 1.1.

Motivaciones de la Tesis

En los u ´ltimos a˜ nos, una nueva arquitectura de procesadores conocida como multihilo simult´aneo (SMT − Simultaneous Multithreading) [9] [35] [36], ha crecido en relevancia y ha sido incorporada en los microprocesadores actuales, tales como los Intel [19] Pentium 4 Hyper-Threading [34]. Posteriormente, nuevas generaciones de procesadores multihilo fueron introducidas en el mercado, como ser la tecnolog´ıa CoolThreads [33] de Sun Microsystems [32], implementada en la l´ınea de servidores UltraSPARC T1. La ejecuci´on de m´ ultiples hilos en un mismo procesador genera interrogantes respecto al desempe˜ no de las unidades funcionales en escenarios donde varios flujos de ejecuci´on compiten por los recursos disponibles. La memoria cach´e de nivel 1 es una de las componentes m´as afectadas, debido a que la existencia de m´ ultiples instrucciones pertenecientes a m´ ultiples hilos de ejecuci´on dentro del procesador genera una situaci´on de competencia que se traduce en una alta interferencia de los hilos en las l´ıneas de la memoria cach´e. En este trabajo se propone y analiza el desempe˜ no de un nuevo esquema de memoria cach´e para procesadores multihilo. Dado que es una tecnolog´ıa muy reciente, son escasas (o inexistentes en la pr´actica) las herramientas que simulen o aporten los datos necesarios para 7

1.1. MOTIVACIONES DE LA TESIS

8

realizar simulaciones de estos ambientes multihilo. Si bien, en la actualidad, se est´a trabajando sobre diferentes proyectos de simuladores (e.g., de c´odigo abierto), deber´a realizarse un mayor esfuerzo para generar una variedad m´as amplia de simuladores para sistemas multiprocesadores y multihilo [43]. En ese sentido, se trabaj´o en el desarrollo de un ambiente (framework ) que permita tanto la captura de referencias a memoria (trazas) multihilo, como tambi´en la simulaci´on de organizaciones de memoria cach´e [31] alimentadas por dichas trazas [37]. Para la captura de las trazas de referencias a memoria, se trabaj´o en la construcci´on de un m´odulo para la herramienta Valgrind [30] [39], mientras que para la simulaci´on de memorias cach´e, se construy´o un simulador tal que, alimentado con las trazas recolectadas, permita evaluar la organizaci´on propuesta en ambientes multihilo. Por otra parte, dicho simulador se integr´o dentro de una herramienta m´as general construida en base a la reciente arquitectura de plug-ins RCP (Rich Client Platform) [29] del proyecto Eclipse [8].

1.1.1.

El Procesamiento Multihilo Simult´ aneo (SMT )

Una arquitectura uniprocesador tradicional (por ejemplo, superescalar) explota el paralelismo a nivel de instrucci´on (ILP) [15] para lograr un mejor desempe˜ no en la ejecuci´on de los procesos. Sin embargo, este grado de paralelismo suele ser pobre en la mayor´ıa de los casos [15], dando como resultado un desperdicio en el aprovechamiento de los recursos del procesador. En adici´on al problema del bajo nivel de ILP, un procesador superescalar tambi´en se caracteriza por desperdiciar capacidad de c´omputo, permaneciendo durante algunos ciclos de reloj en estado ocioso. En ocasiones, la ejecuci´on del flujo de instrucciones suele bloquearse debido a, entre otras cosas, malas predicciones de los saltos, desaciertos en la memoria cach´e, operaciones de E/S, etc., lo que se traduce indefectiblemente en un procesador ocioso, a la espera de una instrucci´on a ejecutar. En base a lo anterior, se determina que un procesador puede sufrir de:

1.1. MOTIVACIONES DE LA TESIS

9

Desperdicio Horizontal: debido al bajo nivel de ILP que impide, para un ciclo de reloj dado, aprovechar todos los recursos (unidades funcionales) disponibles. Desperdicio Vertical: debido al bloqueo o latencias en las instrucciones ejecutadas (con el consiguiente desaprovechamiento de la capacidad de procesamiento), el procesador debe permanecer ocioso. Por otra parte, y desde hace varios a˜ nos, los sistemas de software se basan en la utilizaci´on de m´ ultiples procesos livianos o hilos de ejecuci´on (threads). En este caso, existen varios flujos de instrucciones a ejecutar que comparten un mismo espacio de direcciones de memoria. El uso de un procesador superescalar como el descrito anteriormente resulta en un serio cuello de botella, ya que la ejecuci´on de los hilos es serializada en el mismo. Para aprovechar el paralelismo de los sistemas multihilo, se introdujeron modificaciones a dichos procesadores, de manera tal que sean capaces de tomar instrucciones de los diferentes hilos, e intercalar la ejecuci´on de las mismas. As´ı, surgieron dos esquemas, conocidos como Coarse-Grained Multithreading (CMT) y FineGrained Multithreading (FMT). En el primer caso, la ejecuci´on de los flujos se alterna cuando el que estaba en ejecuci´on incurre en alguna penalidad, tal como en el caso de un desacierto en la memoria cach´e L2 [15], mientras que en el esquema FMT, los flujos se alternan en cada instrucci´on ejecutada. El objetivo de estas pol´ıticas consiste en reducir el desperdicio de ciclos de reloj: si un flujo se bloquea, entonces el procesador realiza un cambio de contexto y contin´ ua con la ejecuci´on del otro flujo. Sin embargo, solo resuelven un problema (desperdicio vertical), pero no mejoran el uso de las unidades funcionales por cada ciclo de reloj. En los u ´ltimos a˜ nos se propuso un nuevo esquema, que es en s´ı mismo una variaci´on del FMT, y que se llam´o SMT (Simultaneous Multithreading) [9] [35] [36]. La soluci´on planteada consiste en reducir los desperdicios de tiempo y uso de recursos que se˜ nalamos anteriormente (o sea, se busca minimizar tanto el desperdicio horizontal como tambi´en el desperdicio vertical). Para evitar que el procesador permanezca

1.1. MOTIVACIONES DE LA TESIS

10

ocioso, las instrucciones a ejecutar se toman de varios flujos simult´aneamente, de manera tal que, ante el bloqueo de uno de ellos, se pueda continuar con la ejecuci´on de alguno de los otros. En realidad, la anterior ya es una caracter´ıstica de la pol´ıtica FMT. La diferencia est´a en que un esquema SMT busca maximizar, para cada ciclo de reloj, la utilizaci´on de los recursos del procesador. Si el flujo (o hilo) en ejecuci´on presenta un alto nivel de ILP, entonces ese paralelismo permite explotar al m´aximo la utilizaci´on de las unidades funcionales para un ciclo de reloj. Por otra parte, si varios flujos presentan cada uno un bajo nivel de ILP, entonces pueden ser ejecutados simult´aneamente, para maximizar el aprovechamiento de los recursos.

1.1.2.

Recolecci´ on de Trazas: El M´ odulo Tracegrind

El an´alisis y dise˜ no de arquitecturas de memoria (por ejemplo, cach´e) requiere de t´ecnicas que permitan evaluar el desempe˜ no de una organizaci´on dada, antes de ser efectivamente construida. Para ello, existen diferentes alternativas, como por ejemplo los modelos anal´ıticos [1] [21] y la simulaci´ on manejada por trazas [4] [28] [37]. El modelado anal´ıtico implica desarrollar un conjunto de f´ormulas que describan el desempe˜ no a partir de caracter´ısticas de los programas o par´ametros de la micro-arquitectura y, en la pr´actica, esta t´ecnica es menos precisa respecto a la simulaci´on manejada por trazas [43]. Esta u ´ltima se basa en simular la organizaci´on, aliment´andola con referencias a memoria obtenidas de un ambiente de trabajo real. Dichas referencias constituyen una “traza”, cuya recolecci´on y validaci´on suelen ser tareas dificultosas y complejas. C´omo obtener las trazas, c´omo asegurarnos de la validez de las mismas, y c´omo almacenarlas, son cuestiones que han sido encaradas con mayor o menor ´exito en las u ´ltimas dos d´ecadas, y que se tratar´an con detenimiento en esta tesis. Para la recolecci´on de las trazas, se trabaj´o sobre la herramienta p´ ublica y de c´odigo abierto Valgrind, que permite realizar tareas de debugging y profiling sobre programas ejecutables, para ambientes Linux-x86 [30] [39]. B´asicamente, consiste en una m´aquina virtual, que implementa un procesador

1.1. MOTIVACIONES DE LA TESIS

11

sint´etico x86, y sobre la cual se ejecutan programas de usuario. Este dise˜ no constituye a Valgrind en una capa adicional, que se inserta entre el programa de usuario y la arquitectura de base (ver figura 1.1), permiti´endole, entre otras cosas, tener un control total de las referencias a memoria que se efect´ uan.

PROGRAMA DE USUARIO

INSTRUCCIONES x86 UCODE COREGRIND

INSTRUCCIONES x86

MÓDULO

Valgrind

UCODE INSTRUMENTADO

PLATAFORMA DE BASE (x86)

Figura 1.1: Interacci´ on de Valgrind con el programa de usuario y la plataforma de base.

M´as precisamente, se construy´o un m´odulo, llamado Tracegrind, que tiene la responsabilidad de instrumentar las instrucciones recibidas desde Coregrind, de manera tal de capturar cada direcci´on de memoria referenciada, y almacenarla en memoria secundaria (utilizando un esquema de compresi´on adecuado). Adem´as, Valgrind tiene soporte para hilos POSIX (pthreads), lo cual significa que si el programa de usuario est´a programado en base a este tipo de hilos, entonces las trazas generadas ser´an adecuadas para el estudio de organizaciones multihilo.

1.1. MOTIVACIONES DE LA TESIS

1.1.3.

12

Procesamiento de Trazas y Simulaci´ on

Una vez recolectadas las trazas de referencias a memoria, resta procesarlas para obtener resultados de valor. Procesar una traza podr´ıa significar convertirla de su formato original a uno nuevo, o tomarla desde un archivo de texto plano y almacenarla en un archivo comprimido, aplicarle alg´ un tipo de filtrado o muestreo, etc. Si bien en este trabajo se trata la simulaci´on de memorias cach´e manejada por trazas, se desarroll´o un entorno (framework ) lo suficientemente flexible tal que el usuario final pueda adaptarlo a sus necesidades. Esta herramienta, llamada SimiOO, est´a construida sobre la Plataforma de Cliente Rico (Rich Client Platform), del Proyecto Eclipse [8]. Esta caracter´ıstica permite que SimiOO pueda ser extendido, mediante la construcci´on de plug-ins para lograr diferentes funcionalidades, adapt´andose a las necesidades del usuario. En esta etapa, un plug-in de simulaci´on de memorias cach´e (manejada por trazas) se distribuye junto a SimiOO. El mismo soporta cualquier organizaci´on de una o m´as v´ıas, asociativa por conjuntos y con direccionamiento por bits. Adem´as, pueden definirse diferentes pol´ıticas de reemplazo, tama˜ nos de las v´ıas, etc.

1.1.4.

El Esquema de Memoria Cach´ e Propuesto

Todo sistema de c´omputo presenta una jerarqu´ıa de memoria organizada en niveles, como se aprecia en la figura 1.2. Aprovechando el principio de localidad, para las referencias a memoria, presente en las aplicaciones, se espera que el procesador haga un uso intensivo de un conjunto peque˜ no de datos e instrucciones en un tiempo corto. De esta forma, se mantiene temporalmente una copia de estos datos e instrucciones en una memoria de tama˜ no reducido (y, por lo tanto, de r´apido acceso) cercana al procesador (en la pr´actica, dentro del mismo circuito integrado). A estas memorias de r´apido acceso, presentes en los procesadores, se las denomina “cach´es”. Cuando un dato o una instrucci´on no es encontrada en la memoria ca-

1.1. MOTIVACIONES DE LA TESIS

13

Costo

Registros de la CPU Caché (L1, L2 y L3)

Memoria Principal

Capacidad y Tiempo de acceso

ch´e, deber´a recurrirse al nivel inferior (de mayor tama˜ no) en la jerarqu´ıa de memoria. A esta situaci´on se le llama “desacierto” y, en la pr´actica, se busca minimizar su n´ umero, ya que implica acceder a una memoria de mayor tama˜ no y, por lo tanto, m´as lenta. Adem´as, dado que cada nivel est´a incluido en el inferior, deber´a ser actualizado en caso de desacierto.

Memoria Secundaria y Dispositivos de E/S

Figura 1.2: Niveles de una jerarqu´ıa de memoria cl´asica.

En los procesadores actuales, existen dos o m´as niveles de memoria cach´e (nivel 1 o L1, nivel 2 o L2, etc.), cada uno siendo m´as grande y de mayor tiempo de acceso que el anterior. En particular, la cach´e de nivel 1 (que es el m´as peque˜ no y m´as r´apido de estos niveles) est´a dividida en dos partes, una asignada a los datos (cach´e de datos) y la otra a las instrucciones (cach´e de instrucciones). Adem´as, en todos los casos, las memorias cach´e se caracterizan por la estrategia utilizada para ubicar un dato obtenido desde el nivel inferior, en caso de desacierto. En este sentido, una organizaci´on cach´e puede ser: De correspondencia directa (direct mapping): cuando el nuevo dato solo puede ser ubicado en un u ´nico lugar en la cach´e.

1.1. MOTIVACIONES DE LA TESIS

14

Asociativa por conjuntos (set associative): cuando el nuevo dato puede ser ubicado en un conjunto de lugares posibles. Completamente asociativa (fully associative): cuando el nuevo dato puede ser ubicado en cualquier lugar de la cach´e. El mecanismo de acceso a la cach´e es mediante indexaci´on (i.e., a partir de la direcci´on de memoria que est´a siendo referenciada, se genera un ´ındice para acceder a la cach´e). La direcci´on de memoria del dato en cuesti´on puede descomponerse seg´ un se muestra en la figura 1.3. Los bits que conforman el ´ındice permiten acceder a un conjunto en particular dentro de la cach´e, mientras que el r´otulo (o tag), es utilizado para decidir si la l´ınea indexada contiene el bloque buscado. Finalmente, el desplazamiento (o block offset) selecciona, dentro del bloque, el dato solicitado. Dirección del bloque Rótulo

Índice

Desplazamiento del bloque

Figura 1.3: Direcci´ on de memoria.

Las organizaciones cach´e asociativas por conjuntos est´an implementadas a partir de un n´ umero k ≥ 2 de bancos (o v´ıas), y se hace referencia a la cach´e como “asociativa por conjuntos de k v´ıas” (k-way set associative − kWSA). Adem´as, estos bancos son de igual tama˜ no (dado en potencias de 2 para explotar el indexado por mapeo de bits). Sin embargo, el usar bancos de igual tama˜ no es una restricci´on adicional al dise˜ no, la cual puede ser removida, como se discutir´a a continuaci´on. El esquema de banco compartido - SWSA: Si en un esquema de asociatividad mayor o igual a 2 (2WSA, 4WSA, etc.) se quita la restricci´on de que los bancos sean de igual tama˜ no, nos encontramos frente a una organizaci´on de memoria cach´e de nivel 1, conocida como SWSA (Shared-Way Set

1.1. MOTIVACIONES DE LA TESIS

15

Associative) [13]. En la figura 1.4 puede observarse un caso para el esquema SWSA, con el primer banco de tama˜ no C1 y el segundo banco de tama˜ no C2 = C1/2 y cada l´ınea del segundo banco compartida por dos l´ıneas en el primer banco. El quitar la restricci´on de bancos de igual tama˜ no permite obtener una memoria cach´e cuyo tama˜ no total no necesariamente sea potencia de 2, lo cual es una cuesti´on muy importante en el dise˜ no de procesadores, para hacer un uso o´ptimo del a´rea de silicio disponible y minimizar el consumo de energ´ıa. Banco 1

Banco 2

Figura 1.4: Asociatividad en una organizaci´ on de banco compartido SWSA

Adaptaci´ on del esquema SWSA a un ambiente multihilo: La organizaci´on SWSA como fue concebida originalmente no evita el problema de la interferencia entre los hilos que se ejecutan en un ambiente multihilo, dado que los bancos no son privados, sino que se comparten entre todos los hilos de ejecuci´on [22] [25]. En realidad, tampoco lo evitan otras organizaciones tradicionales (como ser DM y kWSA), salvo que se replique, dentro del procesador, tantas memorias como la mayor cantidad de hilos posibles. Teniendo en cuenta esta situaci´on, y el avance de los procesadores con soporte para m´ ultiples hilos, se busca en esta tesis dise˜ nar una organizaci´on de memoria cach´e de nivel 1 cuyo desempe˜ no sea aceptable tanto en un ambiente con

1.2. OBJETIVOS DE LA TESIS

16

pocos hilos en ejecuci´on como tambi´en con el n´ umero m´aximo posible. Para ello, se presenta un nuevo esquema, conformado por una v´ıa de memorias privadas para cada hilo, y otra de memoria compartida entre todos los hilos (ver figura 1.5), y que consiste en una adaptaci´on de la arquitectura SWSA de banco compartido. De esta forma, se busca minimizar la interferencia (asignando una porci´on de memoria privada a cada hilo), pero con la posibilidad de que los hilos puedan compartir datos a trav´es del banco compartido. Se analizar´a el desempe˜ no de esta organizaci´on. BANCO 1

BANCO 2

HILO 1

HILO 2

HILO 3

HILO 4

Figura 1.5: Asociatividad en la organizaci´ on presentada

1.2.

Objetivos de la Tesis

En resumen, el objetivo de la presente tesis consiste en el an´alisis del desempe˜ no de una nueva organizaci´on de memoria cach´e para procesadores multihilo, que es una adaptaci´on del esquema SWSA de banco compartido. Para ello, fue necesario desarrollar un ambiente que permita tanto la captura de referencias a memoria (trazas) multihilo, como tambi´en la simulaci´on de organizaciones de memoria cach´e alimentadas por dichas trazas.

1.2. OBJETIVOS DE LA TESIS

17

Para la captura de las trazas de referencias a memoria, se trabaj´o en la construcci´on de un m´odulo para la herramienta Valgrind. Para la simulaci´on de memorias cach´e, se construy´o un simulador tal que, alimentado con las trazas recolectadas, fue posible evaluar el desempe˜ no del esquema de memoria cach´e de nivel 1 propuesto. El desarrollo del framework y la herramienta de simulaci´on se bas´o en la reciente arquitectura de plug-ins RCP (Rich Client Platform) del proyecto Eclipse.

Cap´ıtulo 2 Recolecci´ on de Trazas: El M´ odulo Tracegrind 2.1.

Introducci´ on

El an´alisis y dise˜ no de arquitecturas de memoria (por ejemplo, cach´e) requiere de t´ecnicas que permitan evaluar el desempe˜ no de una organizaci´on dada, antes de ser efectivamente construida. Para ello, existen diferentes alternativas, como por ejemplo los modelos anal´ıticos [1] [21] y la simulaci´ on manejada por trazas [4] [28] [37]. El modelado anal´ıtico implica desarrollar un conjunto de f´ormulas que describan el desempe˜ no a partir de caracter´ısticas de los programas o par´ametros de la micro-arquitectura y, en la pr´actica, esta t´ecnica es menos precisa respecto a la simulaci´on manejada por trazas [43]. Esta u ´ltima se basa en simular la organizaci´on, aliment´andola con referencias a memoria obtenidas de un ambiente de trabajo real. Dichas referencias constituyen una “traza”, cuya recolecci´on y validaci´on suelen ser tareas dificultosas y complejas. C´omo obtener las trazas, c´omo asegurarnos de la validez de las mismas, y c´omo almacenarlas, son cuestiones que han sido encaradas con mayor o menor ´exito en las u ´ltimas dos d´ecadas, y que se tratar´an con detenimiento a continuaci´on. En esta secci´on se har´a un recorrido sobre las diferentes t´ecnicas de reco18

´ DE TRAZAS 2.2. RECOLECCION

19

lecci´on, validaci´on y almacenamiento de trazas, y se presentar´a la implementaci´on de una herramienta propia (p´ ublica y de c´odigo abierto) desarrollada en este trabajo para tal fin. Las trazas capturadas con esta herramienta son adecuadas para simulaci´on de ambientes multihilo (e.g., Simultaneous Multithreading − SMT), debido a la fina granularidad con la que se ejecutan los hilos.

2.2.

Recolecci´ on de Trazas

La recolecci´on de trazas puede llevarse a cabo de acuerdo a t´ecnicas diferentes, que surgen de necesidades diferentes, y con ventajas y desventajas. Todas estas t´ecnicas, que tienen en com´ un la captura de referencias de un ambiente de trabajo real, pueden clasificarse seg´ un el grado de abstracci´on con que se las implemente (ver figura 2.1). Sistema Operativo

Ejecución paso a paso

Software

Compilador Ensamblador Instrumentación estática de código

Enlazador (linker) Cargador (loader)

Hardware

Emulación

Microcódigo Circuitos y Compuertas

Emulación de instrucciones Modificación del microcódigo Analizador lógico

Figura 2.1: Niveles de abstracci´ on en la recolecci´on de trazas.

´ DE TRAZAS 2.2. RECOLECCION

20

La t´ecnica m´as directa para recolectar las referencias a memoria consiste en sondar cada direcci´on enviada por el procesador al sistema de memoria, a trav´es del bus de direcciones (address bus), mientras se ejecuta el ambiente de trabajo. Esto puede implementarse mediante el uso de un analizador l´ogico, leyendo los valores de tensi´on de cada cable del bus de direcciones, y almacen´andolos en un buffer externo. Si bien este esquema permite recolectar las referencias tanto de los programas de usuario como tambi´en del sistema operativo, presenta una importante desventaja: administrar el buffer externo puede ser un cuello de botella, ya que la velocidad con la que son le´ıdas las referencias en el bus puede ser varios o´rdenes de magnitud superior a la velocidad con que se almacenan dichas referencias en un medio externo, a tal punto que el buffer intermedio no pueda compensar esta diferencia de velocidades. M´as a´ un, esta t´ecnica no es aplicable para recolectar la traza de accesos a la memoria cach´e de nivel 1, dado que esta se encuentra dentro del circuito integrado del microprocesador, y es imposible sondar el bus de direcciones en este caso. Debido al costo y las limitaciones en el uso de analizadores l´ogicos, se ha presentado otra t´ecnica de captura de referencias a memoria, que consiste en modificar el microc´odigo del procesador en cuesti´on. La ejecuci´on de las instrucciones modificadas tiene un efecto secundario: almacenar la informaci´on de cada referencia en una porci´on de memoria principal. Esta t´ecnica tambi´en permite capturar todas las referencias a memoria, a´ un las del sistema operativo, presentando un mejor desempe˜ no respecto al uso de analizadores l´ogicos. Sin embargo, la modificaci´on de microc´odigo se ha vuelto obsoleta en los procesadores modernos, debido a que es dif´ıcil (o imposible, en la mayor´ıa de los casos) acceder a la memoria en donde se almacena el microc´odigo (actualmente, suele ser una memoria incorporada dentro del mismo procesador). M´as a´ un, en la pr´actica, los procesadores RISC ni siquiera presentan unidad de control micro-programada (debido a su simpleza), sino una unidad de control por hardware de alto desempe˜ no. En un nivel de abstracci´on superior, se puede realizar la captura de refe-

´ DE TRAZAS 2.2. RECOLECCION

21

rencias mediante emulaci´on del conjunto de instrucciones. La idea consiste en interpretar las instrucciones del ambiente de trabajo, realizar alg´ un tipo de modificaci´on sobre ellas y, finalmente, alimentarlas al procesador f´ısico. Dado que el emulador tiene control sobre las instrucciones siendo ejecutadas, puede obtener de ellas informaci´on relacionada a las posiciones de memoria que est´an siendo referenciadas. La emulaci´on de instrucciones se realiza (din´amicamente) en tiempo de ejecuci´on y es una alternativa econ´omica y portable. Por otra parte, los tiempos de ejecuci´on de un sistema real utilizando un emulador, suelen ser muy elevados, ya que se interpreta din´amicamente cada instrucci´on ejecutada. Adem´as, el uso de emulaci´on requiere grandes cantidades de memoria, debido a la necesidad de mantener registros y estados durante la ejecuci´on. Como una desventaja adicional, la emulaci´on del conjunto de instrucciones no contempla las referencias a memoria realizadas por el sistema operativo u otros procesos. El costo en tiempo que presenta el uso de emuladores (debido a la interpretaci´on que se hace sobre cada instrucci´on ejecutada), es un precio que no siempre se puede pagar. Como una alternativa, es posible insertar en el programa, instrucciones especiales para la recolecci´on de referencias a memoria. Esta t´ecnica, conocida como “instrumentaci´on est´atica de c´odigo”, presenta, en promedio, un desempe˜ no dos veces mejor que la emulaci´on de instrucciones [37]. Las modificaciones pueden insertarse en el c´odigo fuente, en el archivo objeto, o en el archivo binario compilado. En el primer caso, la instrumentaci´on es relativamente simple: se insertan instrucciones en puntos espec´ıficos del c´odigo (para capturar eventos tales como accesos de lectura/escritura a memoria). Aplicar las modificaciones sobre el archivo objeto puede ser factible, dado que en este nivel todav´ıa se dispone de tablas de s´ımbolos y de reubicaci´on de datos. Sin embargo, el usuario final podr´ıa no disponer de los archivos fuente ni objeto, por lo cual se presenta la alternativa de instrumentar el archivo binario compilado. Desafortunadamente, modificar un archivo binario compilado suele ser una tarea dif´ıcil, que requiere un importante an´alisis previo (debido a que no se dispone de informaci´on de

2.3. EL SISTEMA VALGRIND

22

reubicaci´on, como sucede con los archivos objeto). Es preciso aclarar que la instrumentaci´on est´atica (a nivel de fuentes, objetos o binarios), no contempla bibliotecas externas vinculadas din´amicamente y, menos a´ un, a otros procesos de usuario o del sistema operativo. Finalmente, existe la posibilidad de explotar caracter´ısticas del sistema operativo, como por ejemplo, la ejecuci´on “paso a paso”. Este mecanismo, presente en muchas herramientas de depuraci´on, es f´acil de usar, portable, y no requiere de esfuerzos importantes para la captura de referencias. Sin embargo, presenta retardos elevados y, como ocurre con la instrumentaci´on est´atica, tampoco contempla a bibliotecas vinculadas din´amicamente, sistema operativo ni otros procesos de usuario.

2.3.

El Sistema Valgrind

Valgrind es una herramienta p´ ublica y de c´odigo abierto que permite realizar tareas de debugging y profiling sobre programas ejecutables, para ambientes Linux-x86. B´asicamente, consiste en una m´aquina virtual, que implementa un procesador sint´etico x86, y sobre la cual se ejecutan programas de usuario. Este dise˜ no constituye a Valgrind en una capa adicional, que se inserta entre el programa de usuario y la arquitectura de base (ver figura 2.2), permiti´endole, entre otras cosas, tener un control total de las referencias a memoria que se efect´ uan. En base a la taxonom´ıa dada en la secci´on 2.2, Valgrind puede clasificarse como un emulador del conjunto de instrucciones. Dise˜ no general: El sistema Valgrind est´a construido en base a un dise˜ no modular, en torno a un n´ ucleo llamado Coregrind, que implementa un procesador x86 sint´etico, e interact´ ua con otros m´odulos (skins), para brindar diferentes funcionalidades (detectar problemas de memoria, verificar la ejecuci´on concurrente de hilos, simular memorias cach´e, etc.). La interacci´on de Coregrind con los dem´as m´odulos se produce de la siguiente manera: cuando se ejecuta un programa de usuario sobre Valgrind, el m´odulo central toma

2.3. EL SISTEMA VALGRIND

23

PROGRAMA DE USUARIO

INSTRUCCIONES x86 UCODE COREGRIND

INSTRUCCIONES x86

MÓDULO

Valgrind

UCODE INSTRUMENTADO

PLATAFORMA DE BASE (x86)

Figura 2.2: Interacci´ on de Valgrind con el programa de usuario y la plataforma de base.

el control del mismo, lee el bloque de c´odigo a ejecutar y lo pasa al m´odulo correspondiente. Este m´odulo instrumenta el bloque de c´odigo recibido, y se lo retorna a Coregrind. Posteriormente, el m´odulo central ejecuta el bloque de c´odigo instrumentado. La manera en que un m´odulo instrumenta el bloque de c´odigo provisto por Coregrind depende de qu´e funcionalidad provee dicho m´odulo. Por ejemplo, Memcheck (que permite verificar y detectar errores en cada referencia a memoria de un programa de usuario) instrumenta el c´odigo agregando sentencias para verificar cada acceso a memoria y cada valor calculado. Los m´odulos que provee Valgrind son los siguientes: Memcheck, Addrcheck, Helgrind, Cachegrind, Massif, Corecheck, Lackley y Nulgrind. Detalles de arquitectura: Valgrind es una biblioteca compartida (valgrind.so), con algunas particularidades, como por ejemplo que tiene prioridad en cuanto a su inicializaci´on. Una vez que esto sucede, toma control completo respecto a la ejecuci´on del programa de usuario, traduciendo sus instrucciones en otras sentencias nuevas (en formato UCode). Para esto

´ 2.4. EL MODULO TRACEGRIND

24

utiliza la funci´on VG (translate), mediante la cual traduce bloques b´asicos de instrucciones. Todo c´odigo traducido (e instrumentado) por Valgrind es almacenado en una cach´e de traducciones (Translation Cache − TC) para mejorar el desempe˜ no, evitando volver a traducir c´odigo recientemente usado. Para ejecutar c´odigo traducido (y almacenado en la TC), Valgrind utiliza la funci´on VG (dispatch), que posee la l´ogica necesaria para poder determinar en qu´e momento ejecutar qu´e sentencia de c´odigo (traducida), ir a buscarla a la TC, y alimentarla al procesador real. En cada iteraci´on se obtiene la direcci´on real de la pr´oxima instrucci´on a ejecutar, direcci´on que permite acceder a la TC para recuperar la correspondiente instrucci´on traducida. Mientras estas instrucciones se encuentren en la TC, Valgrind contin´ ua normalmente la ejecuci´on del programa de usuario. Si una instrucci´on no se hallara en la TC, Valgrind retorna de la funci´on VG (dispatch) para hacer una nueva llamada a VG (translate). Conjunto de Instrucciones: Valgrind implementa un procesador x86 sint´etico con instrucciones en un formato propio, conocido como UCode (similar al de un procesador RISC). En el formato UCode, las instrucciones se conocen como UInstr, cada una de las cuales est´a conformada por varios campos (de la misma manera que sucede con las instrucciones assembly de un procesador real). Los m´as relevantes son el tipo de opcode a ejecutar (en Valgrind, UOpcode), y los valores de los operandos (val1, val2 y val3), entre otros.

2.4.

El M´ odulo Tracegrind

Tracegrind es el m´odulo Valgrind construido en este trabajo, y que instrumenta los bloques b´asicos recibidos agregando instrucciones especiales para recolectar las referencias a memoria. Este c´odigo adicional permite analizar cada bloque b´asico con el fin de extraer las direcciones de memoria (a datos y/o instrucciones) siendo referenciadas, y determinar el tipo de acceso (lec-

2.5. CONSIDERACIONES SOBRE MULTIHILO

25

tura/escritura). Una vez realizado este procesamiento sobre el bloque b´asico, Tracegrind lo retorna a Valgrind, donde es almacenado en la cach´e de traducciones (TC), como ya se explic´o en la secci´on 2.3. Adem´as, el c´odigo para recolecci´on tiene la responsabilidad de escribir las direcciones extra´ıdas en un archivo comprimido. La figura 2.3 muestra un bosquejo de este proceso. En el ap´endice B se adjunta el c´odigo fuente del m´odulo Tracegrind. EJECUCIÓN

Tracegrind BLOQUE BÁSICO

BLOQUE BÁSICO

BLOQUE BÁSICO

Thread ID = 2

Thread ID = 2

Thread ID = 2

GETL %EAX, t0

GETL %EAX, t0

GETL %EAX, t0 log_reference()

log_reference() COMPRESIÓN LZ77

TRAZA DATOS

TRAZA INSTR.

Figura 2.3: El M´ odulo Tracegrind.

2.5.

Consideraciones sobre Multihilo

Valgrind tiene soporte para hilos POSIX (pthreads), usando una biblioteca libpthread propia (que reemplaza a la nativa, provista por el sistema operativo). Por otra parte, el m´odulo central es el encargado de planificar la ejecuci´on de los hilos. Con el fin de recrear un ambiente multihilo, se analiz´o y modific´o el esquema de ejecuci´on de hilos de Valgrind, tal que se ajuste a las necesidades de este trabajo.

2.5. CONSIDERACIONES SOBRE MULTIHILO

26

Valgrind planifica la ejecuci´on asign´andole a cada hilo una “rebanada” (slice) de tiempo para su ejecuci´on. Esta porci´on de tiempo es de tama˜ no fijo (unas 300, 000 instrucciones, aproximadamente), antes de que el planificador realice un cambio de contexto, en base a una pol´ıtica round-robin. Sin embargo, en este trabajo era necesario contar con trazas donde los hilos se entrelazaran con un fino nivel de granularidad, tal de lograr un efecto de ejecuci´on “simult´anea”. Este requisito permite que, durante las simulaciones, sean m´as visibles efectos como la “interferencia” o “cooperaci´on” entre hilos. Para lograr este efecto, se analiz´o y modific´o el planificador de Valgrind, tal que se realice un cambio de contexto por cada instrucci´on ejecutada. De esta forma, la secuencia de referencias a memoria generada por Valgrind (y recolectada por Tracegrind) presenta el nivel de paralelismo entre hilos, requerido para las simulaciones realizadas. Adem´as, se defini´o un formato simple para las referencias almacenadas en la traza, que contiene los siguientes campos: Id del hilo

Direcci´on de memoria Tipo de acceso

donde Id del hilo es un identificador num´erico asignado por Valgrind a cada hilo POSIX (el programa principal tiene id = 1, el hilo 0 tiene id = 2, y as´ı sucesivamente), direcci´ on de memoria es la direcci´on virtual (en notaci´on hexadecimal) de la posici´on referenciada, y tipo de acceso indica si la referencia es una lectura ([rd]) o una escritura ([wr]). A modo de ejemplo, el siguiente es un fragmento de traza generada, usando Tracegrind, para una aplicaci´on con un programa principal (id = 1) y tres hilos (id = 2, 3, 4): 1 2 4 3 4

0x3ACCC430 0x3ACCC434 0x3ACCC430 0x3ACCC434 0x3ACCC434 ...

[rd] [wr] [rd] [rd] [rd]

´ DE TRAZAS 2.6. VALIDACION

27

Por otra parte, debido al enorme tama˜ no de las trazas t´ıpicas recolectadas, las mismas fueron comprimidas “al vuelo”, utilizando el algoritmo de Lempel-Ziv (LZ77 ). En el ap´endice A se brindan detalles adicionales sobre la implementaci´on de Tracegrind y su modo de uso.

2.6.

Validaci´ on de Trazas

La etapa m´as importante en el proceso de recolecci´on y almacenamiento de trazas, consiste en la validaci´on de las mismas, tal que podamos confiar en ellas al momento de la simulaci´on. A pesar de su relevancia, la validaci´on de una traza no es una tarea simple, ni tampoco existen metodolog´ıas que permitan hacerlo con rigor. En una consulta a uno de los pioneros en la investigaci´on de jerarqu´ıas de memoria, el Prof. Alan Jay Smith1 , nos dec´ıa: “Unfortunately, I don’t know any good/easy way to validate results.” “For the traces, you should look at samples of the trace and samples of the object code, and by hand verify that the traces correspond correctly. You should also do some basic analysis of the traces (e.g. R/W ratios, instruction counts, branch distances, instruction frequencies and types, etc.) and see if they agree with published numbers. If everything agrees, then presumably you don’t have too many remaining errors in your traces.” En este trabajo, la validaci´on de las trazas se llev´o a cabo mediante la construcci´on y ejecuci´on (sobre Valgrind) de peque˜ nos programas, incluyendo los escenarios m´as significativos del modelo de programaci´on multihilo. Utilizando el m´odulo Tracegrind, se recolectaron las trazas generadas por estos programas tipo (toy benchmarks o “juguete”) y, siguiendo las recomendaciones del Prof. Alan Smith, se compararon fragmentos (muestras) de estas trazas contra los correspondientes bloques de instrucciones de los programas ejecutados, en forma manual. Este procedimiento se aplic´o para ambos tipos 1

Computer Science Division, EECS Department, University of California, Berkeley.

´ DE TRAZAS 2.6. VALIDACION

28

de trazas: de datos y de instrucciones. A continuaci´on se muestra, a modo de ejemplo, el procedimiento utilizado para la validaci´on de las trazas.

2.6.1.

Un Programa Simple para la Validaci´ on de la Herramienta

A continuaci´on se presenta, parcialmente debido al tama˜ no, uno de los programas utilizado en el proceso de validaci´on. La cantidad de hilos ejecutados se regula seg´ un la definici´on NUM THREADS, y cada uno de ellos opera sobre una porci´on de CHUNK SIZE elementos, realizando operaciones aritm´eticas b´asicas (de enteros). #include ... #define NUM_THREADS 4 #define CHUNK_SIZE 10 typedef struct { pthread_t thread; int tid; } tThread; long working_array[NUM_THREADS*CHUNK_SIZE]; FILE *log_file = NULL;

Para procesar su porci´on correspondiente del arreglo working array, cada hilo ejecuta la funci´on thread func() que se muestra a continuaci´on: void *thread_func(void *arg) { int i, t; time_t curtime;

´ DE TRAZAS 2.6. VALIDACION

29

t = *((int *)arg); ... for (i=t*CHUNK_SIZE; i<(t*CHUNK_SIZE)+CHUNK_SIZE; i++) working_array[i] = i; ... pthread_exit(NULL); }

La funci´on anterior, que recibe por par´ametro el identificador del hilo que la ejecuta, tiene como tarea principal rellenar CHUNK SIZE componentes del arreglo de enteros working array. La creaci´on, lanzamiento, y espera de los hilos, son tareas del programa principal: int main() { tThread threads[NUM_THREADS]; pthread_attr_t attr; int rc, tid, i; time_t curtime; ... pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); for(tid=0; tid
´ DE TRAZAS 2.6. VALIDACION

30

for(tid=0; tid
En el programa principal puede observarse la creaci´on de NUM THREADS hilos (mediante llamadas a pthread create()), todos con atributo PTHREAD CREATE JOINABLE. Finalmente, se espera la terminaci´on de cada uno de ellos (mediante llamadas a pthread join()). El programa presentado fue ejecutado sobre Valgrind, utilizando la herramienta Tracegrind. Como resultado de la ejecuci´on se obtuvieron dos archivos de trazas: una de datos (data trace.zip) y una de instrucciones (instr trace.zip), que fueron analizados manualmente. Para la de datos, se obtuvieron 260, 000 referencias, mientras que para la de instrucciones, se recolectaron 550, 000 referencias.

2.6.2.

Validaci´ on de las Referencias a Instrucciones

Luego de compilar el benchmark descripto (sin optimizaciones ni otras opciones de compilaci´on), se procedi´o a desensamblarlo mediante el comando objdump. As´ı, es posible conocer las direcciones de memoria de cada instrucci´on, para compararlas con las referencias de la traza de instrucciones. Por ejemplo, el c´odigo assembly correspondiente a las primeras sentencias de la funci´on thread func() es el siguiente: 0804879c : 804879c: 55

push

%ebp

´ DE TRAZAS 2.6. VALIDACION

804879d: 804879f: 80487a2: 80487a5: 80487a7: 80487aa: 80487ad: 80487b0: 80487b1: ...

89 83 8b 8b 89 83 8d 50 e8

e5 ec 45 00 45 ec 45

18 08 f8 0c f4

72 fe ff ff

mov sub mov mov mov sub lea push call

31

%esp,%ebp $0x18,%esp 0x8(%ebp),%eax (%eax),%eax %eax,0xfffffff8(%ebp) $0xc,%esp 0xfffffff4(%ebp),%eax %eax 8048628

En la traza generada, la secuencia de referencias correspondiente a dicho fragmento es la siguiente2 : 2 2 2 2 2 2 2 2 2 2

0x804879C 0x804879D 0x804879F 0x80487A2 0x80487A5 0x80487A7 0x80487AA 0x80487AD 0x80487B0 0x80487B1

[rd] [rd] [rd] [rd] [rd] [rd] [rd] [rd] [rd] [rd]

Por otra parte, el c´odigo assembly correspondiente al bucle for(...) es el siguiente: 804882b: 804882e: 8048831: 8048833: 8048836: 2

83 8b 89 c1 01

c4 10 55 f8 d0 e0 02 d0

Para el hilo con id = 2.

add mov mov shl add

$0x10,%esp 0xfffffff8(%ebp),%edx %edx,%eax $0x2,%eax %edx,%eax

´ DE TRAZAS 2.6. VALIDACION

8048838: 804883a: 804883d: 8048840: 8048842: 8048845: 8048847: 8048849: 804884c: 804884f: 8048851: 8048853: 8048856: 8048859: 8048860: 8048863: 8048865: 8048867:

01 89 8b 89 c1 01 01 83 39 7c eb 8b 8b 89 8d ff eb 83

c0 45 55 d0 e0 d0 c0 c0 45 02 14 55 45 04 45 00 d6 ec

fc f8 02

0a fc

fc fc 95 a0 a1 04 08 fc

0c

add mov mov mov shl add add add cmp jl jmp mov mov mov lea incl jmp sub

32

%eax,%eax %eax,0xfffffffc(%ebp) 0xfffffff8(%ebp),%edx %edx,%eax $0x2,%eax %edx,%eax %eax,%eax $0xa,%eax %eax,0xfffffffc(%ebp) 8048853 8048867 0xfffffffc(%ebp),%edx 0xfffffffc(%ebp),%eax %eax,0x804a1a0(,%edx,4) 0xfffffffc(%ebp),%eax (%eax) 804883d $0xc,%esp

En la traza generada, la secuencia de referencias correspondiente a dicho fragmento3 se muestra en la tabla 2.1. En esa secuencia, las instrucciones con direcci´on 0x8048853, 0x8048856 y 0x8048859 (resaltadas en negrita) corresponden al cuerpo principal del bucle (working array[i] = i) que, como puede apreciarse, se ejecuta en diez oportunidades (lo cual es consistente con la definici´on de CHUNK SIZE). Este mismo procedimiento se aplic´o a programas adicionales usados en la verificaci´on de las trazas y, en todos los casos, se verific´o la validez de las mismas. 3

Para el hilo con id = 2.

´ DE TRAZAS 2.6. VALIDACION

Refs 1..40 2 0x804882B [rd] 2 0x804882E [rd] 2 0x8048831 [rd] 2 0x8048833 [rd] 2 0x8048836 [rd] 2 0x8048838 [rd] 2 0x804883A [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd]

Refs 41..79 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd]

33

Refs 80..118 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd]

Refs 119..157 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048853 [rd] 2 0x8048856 [rd] 2 0x8048859 [rd] 2 0x8048860 [rd] 2 0x8048863 [rd] 2 0x8048865 [rd] 2 0x804883D [rd] 2 0x8048840 [rd] 2 0x8048842 [rd] 2 0x8048845 [rd] 2 0x8048847 [rd] 2 0x8048849 [rd] 2 0x804884C [rd] 2 0x804884F [rd] 2 0x8048851 [rd] 2 0x8048867 [rd]

Cuadro 2.1: Referencias a instrucciones, efectuadas por el programa de validaci´ on.

´ DE TRAZAS 2.6. VALIDACION

2.6.3.

34

Validaci´ on de las Referencias a Datos

El programa de validaci´on utilizado fue programado para que, como efecto secundario, genere una salida con el detalle de las direcciones de memoria de estructuras y variables utilizadas, y que se muestra a continuaci´on: Mon Aug 8 15:37:56 2005 &Threads array=[0xafefe040] &attr=[0xafefe010] &rc=[0xafefe00c] &tid=[0xafefe008] &i=[0xafefe004] &curtime=[0xafefe000] &thread_func=[0x804879c] Mon Aug 8 15:37:56 2005 Creating thread 0 Mon Aug 8 15:37:56 2005 Creating thread 1 Mon Aug 8 15:37:56 2005 Thread = 0 &chunk=[0x804a1a0]-[0x804a1c4] &i=[0x3accc434] &t=[0x3accc430] &curtime=[0x3accc42c] Mon Aug 8 15:37:56 2005 Thread = 1 &chunk=[0x804a1c8]-[0x804a1ec] &i=[0x3aece434] &t=[0x3aece430] &curtime=[0x3aece42c] Mon Aug 8 15:37:56 2005 Creating thread 2 Mon Aug 8 15:37:57 2005 Creating thread 3

´ DE TRAZAS 2.6. VALIDACION

35

Mon Aug 8 15:37:57 2005 Thread = 2 &chunk=[0x804a1f0]-[0x804a214] &i=[0x3b0d0434] &t=[0x3b0d0430] &curtime=[0x3b0d042c] Mon Aug 8 15:37:57 2005 Thread = 3 &chunk=[0x804a218]-[0x804a23c] &i=[0x3b2d2434] &t=[0x3b2d2430] &curtime=[0x3b2d242c] ...

La salida anterior permite conocer algunas direcciones importantes de estructuras y variables, a partir de las cuales se pueden deducir otras. Por ejemplo, a partir de la l´ınea: &Threads array=[0xafefe040] podemos deducir que las direcciones de memoria de cada hilo son4 : Thread Thread Thread Thread

0: 1: 2: 3:

0xafefe040 0xafefe048 0xafefe050 0xafefe058

Tambi´en pueden obtenerse los rangos de direcciones de las porciones del arreglo sobre el que trabajan los hilos. Por ejemplo: Thread = 0 &chunk=[0x804a1a0]-[0x804a1c4] 4

El arreglo threads est´a conformado por el tipo base tThread, de 8 bytes.

2.7. BENCHMARKS SPLASH-2

36

indica que el hilo 0 trabaja sobre el rango de direcciones 0x804a1a0 a 0x804a1c4 (inclusive). Las siguientes referencias (a direcciones de datos) corresponden a una peque˜ na porci´on de la traza obtenida: 2 2 2 2 2 2 2 2 2 2

0x3ACCC430 [rd] 0x3ACCC434 [wr] 0x3ACCC430 [rd] 0x3ACCC434 [rd] 0x3ACCC434 [rd] 0x3ACCC434 [rd] 0x804A1A0 [wr] 0x3ACCC434 [rd] 0x3ACCC430 [rd] 0x3ACCC434 [rd]

Hilo Hilo Hilo Hilo Hilo Hilo Hilo Hilo Hilo Hilo

0 0 0 0 0 0 0 0 0 0

leyendo la variable local t escribiendo la variable local i leyendo la variable local t leyendo la variable local i leyendo la variable local i leyendo la variable local i escribiendo working array[0] leyendo la variable local i leyendo la variable local t leyendo la variable local i

Esta porci´on de traza es consistente con el comportamiento del bucle for(...) de la funci´on thread func(): for (i=t*CHUNK_SIZE; i<(t*CHUNK_SIZE)+CHUNK_SIZE; i++) working_array[i] = i;

Por ejemplo, cuando escribe el elemento working array[0], se hace referencia a la direcci´on 0x804A1A0. Esto concuerda con la salida generada por el programa de pruebas, donde puede verse que el hilo 0 (con id = 2) trabaja sobre la porci´on 0x804a1a0 a 0x804a1c4.

2.7.

Benchmarks SPLASH-2

Una vez que se verific´o el correcto funcionamiento de Tracegrind y la validez de las trazas generadas, se procedi´o a recolectar las trazas multihilo correspondientes a los benchmarks SPLASH-2 [42], un conjunto de aplicaciones paralelas para el estudio de multiprocesadores con memoria compartida, distribuida y centralizada. Las aplicaciones ejecutadas se dan en la tabla 2.2.

2.8. CONCLUSIONES Aplicaci´ on

Descripci´ on

FFT

Transformada R´ apida de Fourier de n n´ umeros complejos, en una dimensi´ on. Factorizaci´ on de una matriz densa. Factorizaci´ on de una matriz rala. Ordenamiento de n´ umeros enteros. Simulaci´ on del movimiento de los oc´ eanos. Simulaci´ on del comportamiento de part´ıculas de agua a lo largo del tiempo.

LU CHOLESKY RADIX OCEAN WATER

37 Traza Datos 1 Hilo 4 Hilos 17-MB 26-MB

Traza Instr. 1 Hilo 4 Hilos 6-MB 43-MB

191-MB

364-MB

47-MB

371-MB

309-MB

484-MB

98-MB

759-MB

67-MB

263-MB

37-MB

519-MB

359-MB

547-MB

50-MB

633-MB

156-MB

433-MB

157-MB

1231-MB

Cuadro 2.2: Aplicaciones SPLASH-2 ejecutadas.

SPLASH-2 est´a construido en base a un conjunto de macros, conocidas como PARMACS, y desarrolladas por ANL (Argonne National Laboratory) [6] [24]. Originalmente, SPLASH-2 fue concebido para procesamiento paralelo y, siendo que en este trabajo se requer´ıan benchmarks multihilo, se utiliz´o una reimplementaci´on de las macros PARMACS con soporte para hilos POSIX (pthreads), provistas por Ernest Artiaga y otros [2], de la Universidad Polit´ecnica de Catalu˜ na.

2.8.

Conclusiones

Se present´o un ambiente para la recolecci´on de referencias a memoria de programas multihilo. La herramienta utiliza directamente el c´odigo ejecutable de la aplicaci´on analizada, con lo cual no es imprescindible contar con el c´odigo fuente de la misma. Esto u ´ltimo es de gran importancia dado que es posible obtener trazas de aplicaciones comerciales, de las cuales usualmente no se dispone de los c´odigos fuente mencionados. La fina granularidad lograda en la captura de las referencias, hacen a las trazas generadas con la herramienta Tracegrind adecuadas para la simulaci´on de ambientes multihilo, incluso multihilo simult´aneo (SMT). Esto es de gran

2.8. CONCLUSIONES

38

importancia, dado que no existen herramientas libres y de c´odigo abierto que permitan realizar la captura de trazas en procesadores multihilo. Teniendo en cuenta la popularidad que han adquirido este tipo de procesadores (e.g., Intel Pentium 4 Hyper-Threading, Sun Microsystems CoolThreads, IBM Power 5, etc.), resulta de suma relevancia el aporte que se realiza a trav´es de la herramienta Tracegrind presentada.

Cap´ıtulo 3 Procesamiento de Trazas: La Herramienta SimiOO 3.1.

Introducci´ on

Una vez recolectadas las trazas de referencias a memoria (tema tratado en el cap´ıtulo 2), resta procesarlas para obtener resultados de valor. Procesar una traza podr´ıa significar convertirla de su formato original a uno nuevo, o tomarla desde un archivo de texto plano y almacenarla en un archivo comprimido, aplicarle alg´ un tipo de filtrado o muestreo, etc. Si bien en este trabajo se trata la simulaci´on de memorias cach´e manejada por trazas, se desarroll´o un entorno (framework ) lo suficientemente flexible tal que el usuario final pueda adaptarlo a sus necesidades. Esta herramienta, llamada SimiOO (Simulador Orientado a Objetos) y que presentaremos a continuaci´on, est´a construida sobre la Plataforma de Cliente Rico (Rich Client Platform), de reciente aparici´on en el Proyecto Eclipse [8]. Esta caracter´ıstica permite que SimiOO pueda ser extendido, mediante la construcci´on de plug-ins para lograr diferentes funcionalidades, adapt´andose a las necesidades del usuario.

39

3.2. EL PROYECTO ECLIPSE

3.2.

40

El Proyecto Eclipse

El Proyecto Eclipse comienza en noviembre de 2001, como la uni´on de varias empresas de tecnolog´ıa de la informaci´on (Borland, IBM, MERANT, QNX Software Systems, Rational Software, Red Hat, SuSE, TogetherSoft y Webgain). El prop´osito de este consorcio consiste en “...promover la creaci´ on, la evoluci´on, el fomento, y el soporte de la Plataforma Eclipse y cultivar una comunidad de c´odigo abierto y un ecosistema de productos complementarios, capacidades, y servicios.” [8]. Actualmente, la comunidad Eclipse mantiene y desarrolla el producto p´ ublico y de c´odigo abierto Eclipse SDK (para desarrollo de aplicaciones), junto con un gran n´ umero de proyectos asociados. Eclipse SDK es m´as que una herramienta para el desarrollo de aplicaciones. En los u ´ltimos tiempos (particularmente con el lanzamiento de sus versiones 3.x), se ha convertido en una plataforma flexible, capaz de ser adaptada a cualquier necesidad, ya que se construye a partir de plug-ins. Adem´as, ofrece un conjunto de herramientas para la construcci´on de interfaces gr´aficas de usuario, como ser SWT (Standard Widget Toolkit) y JFace.

3.2.1.

La Plataforma de Cliente Rico - RCP

Un “cliente rico” consiste en una porci´on de software que implementa toda la funcionalidad espec´ıfica de la aplicaci´on en el lado cliente, en contraposici´on al concepto de “cliente delgado”, en donde toda la funcionalidad espec´ıfica de la aplicaci´on est´a controlada en el lado servidor (t´ıpicamente, aplicaciones web) [7]. IBM junto con la comunidad Eclipse han desarrollado una arquitectura de cliente rico, conocida como Plataforma de Cliente Rico (Rich Client Platform − RCP) [29], que permite trasladar las ventajas y caracter´ısticas de Java hacia el lado del cliente, permitiendo la construcci´on de aplicaciones de escritorio robustas y vistosas. Si bien en la versi´on 2.x de Eclipse ya era posible la construcci´on de nuevas funcionalidades a trav´es de plug-ins, deb´ıan restringirse a aplicaciones de tipo IDE (Integrated Development Environment) [7]. A partir de la versi´on 3, el

3.2. EL PROYECTO ECLIPSE

41

desarrollador puede utilizar Eclipse como marco para nuevas aplicaciones, reutilizando los men´ ues, barras de herramientas, sistema de ayuda, etc. M´as a´ un, RCP es en s´ı mismo una versi´on m´as reducida de la plataforma Eclipse 3.x, a la cual se le quitan varios plug-ins.

3.2.2.

El Modelo de Plug-ins

Un plug-in es una construcci´on de software que implementa una funcionalidad bien definida, y que es capaz de extender a otros programas para ofrecer sus servicios. En Eclipse, adem´as, es la unidad m´as peque˜ na de extensi´on. Cuando la plataforma Eclipse comienza a ejecutarse, una de las primeras tareas que realiza consiste en relevar cu´ales son los plug-ins disponibles y, as´ı, construye una estructura llamada “registro de plug-ins” (plug-in registry). A lo largo de la ejecuci´on de Eclipse, los plug-ins ser´an efectivamente cargados a memoria cuando sean utilizados por primera vez. Para que un plug-in sea a˜ nadido al registro, deber´a estar almacenado (junto con sus recursos asociados) en el directorio de plug-ins de la plataforma Eclipse. En Eclipse, todo plug-in est´a acompa˜ nado por un documento XML que lo define. Este archivo, conocido como “manifiesto” (y llamado plugin.xml), tiene una estructura similar a la que se muestra a continuaci´on:
3.2. EL PROYECTO ECLIPSE

42

point="org.simioo.traceProcessor"> ...


La interfaz entre dos plug-ins (el que extiende y el extendido) se conoce como “punto de extensi´on” (extension point). B´asicamente, un punto de extensi´on es la “entrada” a trav´es de la cual un plug-in puede aportar una nueva funcionalidad. En el archivo plugin.xml presentado antes, una extensi´on se aporta definiendo el elemento XML extension. En ese caso, las extensiones aportadas son una perspectiva (agrupamiento de vistas) y un procesador de trazas (en la figura 3.1 se muestra de qu´e manera un plug-in extiende a otro a trav´es de sus puntos de extensi´on). Adem´as de los puntos de extensi´on, el “anfitri´on” puede definir acciones globales (retargetable actions). Estas acciones, que son implementadas por el plug-in que extiende, tienen una sem´antica u ´nica. Como ejemplos, encontramos el caso de las acciones “nuevo”, “abrir”, “cerrar” y “guardar”. En ese caso, cada “plug-in” las implementar´a con un comportamiento adecuado, pero la sem´antica de la acci´on se conserva. A continuaci´on se muestra la forma en que el “plug-in” anfitri´on crea una acci´on global: IAction copyAction = new RetargetAction( SimiooDefines.SIMIOO_NEW, "Nuevo"); La creaci´on de una acci´on global requiere un identificador (id ) y una etiqueta. El id le permite a otro plug-in poder identificar la acci´on global a implementar, seg´ un se muestra a continuaci´on:

3.3. LA HERRAMIENTA SIMIOO

43

org.simioo Plug-in anfitrión

Editores

Vistas

Perspectivas

Puntos de extensión

org.simulator
Plug-in

point="org.eclipse.ui.perspectives">

Figura 3.1: Extensi´ on de un plug-in.

getViewSite().getActionBars().setGlobalActionHandler( SimiooDefines.SIMIOO_NEW, newProjectAction ); Donde newProjectAction es una instancia IAction que implementa el m´etodo run() con el comportamiento deseado para la acci´on global. Por otra parte, un plug-in podr´ıa no implementar todas las acciones globales definidas en el anfitri´on, en cuyo caso, quedar´ıan deshabilitadas.

3.3.

La Herramienta SimiOO

En esta secci´on se presenta SimiOO, una herramienta p´ ublica y de c´odigo abierto, que permite procesar trazas de referencias a memoria. En este trabajo, “procesar una traza” significar´a simular organizaciones de memoria

3.3. LA HERRAMIENTA SIMIOO

44

cach´e a partir de ella. Sin embargo, es posible implementar diferentes funcionalidades mediante la construcci´on de nuevos plug-ins dado que su dise˜ no se basa en la Plataforma de Cliente Rico presentada anteriormente. El usuario final, ante la necesidad de nuevas funcionalidades, solamente deber´a construir su propio plug-in (en lenguaje de programaci´on Java) que se integrar´a naturalmente a la herramienta SimiOO. En esta etapa, un plug-in de simulaci´on de memorias cach´e (manejada por trazas) se distribuye junto a SimiOO. El mismo soporta cualquier organizaci´on de una o m´as v´ıas, asociativa por conjuntos, pudiendo definirse diferentes pol´ıticas de reemplazo, cantidad de v´ıas, tama˜ nos de los bancos, etc.

3.3.1.

Modelo de An´ alisis

La herramienta SimiOO interact´ ua con dos actores: el usuario y el graficador. En el primer caso, se trata del usuario final, interesado en aplicar determinado procesamiento sobre un conjunto de trazas, como ser la simulaci´on de organizaciones de memoria. En el segundo caso, el graficador es el responsable de tomar los resultados generados en el procesamiento de trazas, y construir gr´aficos a partir de ellos. Esto es de especial inter´es en la simulaci´on de memorias, donde contar con una representaci´on gr´afica1 de los resultados es de gran importancia. Los actores descriptos hacen uso de SimiOO seg´ un los casos de uso mostrados en la figura 3.2. El usuario final puede crear un proyecto (en el caso del simulador, integrado por las memorias y trazas a simular), ejecutar el procesamiento (e.g., la simulaci´on), y obtener los resultados. Por su parte, el graficador toma los resultados y genera los gr´aficos. En la pr´actica, el actor “graficador” es una herramienta para generaci´on de gr´aficos, como por ejemplo, Gnuplot [11]. En SimiOO, un “proyecto” es, al menos, un conjunto de trazas a procesar, y se ofrece un mecanismo simple para la administraci´on de los mismos, me1

Por ejemplo, la tasa de desaciertos en funci´on de los tama˜ nos de memorias.

3.3. LA HERRAMIENTA SIMIOO

45

Figura 3.2: Diagrama de Casos de Uso.

diante la clase SimiooProjectManager. Adem´as, cada plug-in puede aportar caracter´ısticas adicionales al proyecto; por ejemplo, en el caso del plug-in de simulaci´on, el proyecto est´a conformado por las trazas a procesar y las memorias cach´e a simular, mediante la clase SimulationProjectManager, que es una extensi´on de SimiooProjectManager. Los proyectos se almacenan en formato XML. Por otra parte, qu´e procesamiento aplicar a cada una de las trazas que integran un proyecto, es responsabilidad exclusiva de cada plug-in (SimiOO solamente provee un “esqueleto”, la clase SimiooTraceProcessor, que debe ser extendido). En el caso del plug-in de simulaci´on, la clase SimulatorTraceProcessor implementa la simulaci´on de memorias cach´e manejada por trazas. En la figura 3.3 se muestra la extensi´on de SimiOO por parte del plug-in de simulaci´on. Una traza es una secuencia de referencias a memoria (direcciones), realizada por un programa durante su ejecuci´on, tanto a datos como a instruc-

3.3. LA HERRAMIENTA SIMIOO

46

Figura 3.3: Extensi´ on de SimiOO mediante el plug-in de simulaci´on.

ciones2 . Como se trat´o en el cap´ıtulo 2, cada referencia se almacena seg´ un un formato determinado (por ejemplo, el formato Tracegrind). Adem´as, el tama˜ no de un archivo de traza puede ser extremadamente grande y, en la pr´actica, se trabaja sobre trazas comprimidas. En este sentido, SimiOO tambi´en modela la forma en que una traza est´a almacenada (clase Source) y c´omo se la l´ee (clase TraceReader). La clase ZippedFileSource representa una traza comprimida, mientras que la clase TracegrindTraceReader implementa la lectura de referencias seg´ un el formato Tracegrind ya descripto. El resultado de acceder a una traza para leer una referencia es una instancia MemoryReference. En la figura 3.4 puede observarse esta relaci´on. En el caso particular del plug-in de simulaci´on, las organizaciones de memoria cach´e a simular est´an modeladas seg´ un se muestra en la figura 3.5. Esta relaci´on de composici´ on permite un alto nivel de flexibilidad al momento de construir organizaciones cach´e para simular. Por ejemplo, una memoria de 2

En este trabajo solo se consideran trazas de datos.

3.3. LA HERRAMIENTA SIMIOO

47

Figura 3.4: Almacenamiento y lectura de trazas en SimiOO.

correspondencia directa (Direct Mapped − DM) de 64-KB, con bloques de 32 bytes, se construir´ıa con 2048 instancias Block, todas ellas agrupadas en una instancia Memory, contenida en una instancia Way, contenida en una instancia MemoryOrganization. De igual forma, podr´ıan armarse otras organizaciones, con dos o m´as v´ıas, incluso asim´etricas (diferente cantidad de memorias en cada v´ıa), como la presentada por Hamkalo et al. [14].

Figura 3.5: Modelado de memorias cach´e en el plug-in de simulaci´on.

Tambi´en en el caso del plug-in de simulaci´on, la pol´ıtica de reemplazo de bloques en la memoria simulada est´a modelada por la clase

3.3. LA HERRAMIENTA SIMIOO

48

SimulatorReplacementPolicy. “Pol´ıtica de reemplazo” significa qu´e decisi´on tomar ante la necesidad de “hacer lugar” en la memoria cach´e para traer un nuevo bloque. En la pr´actica, la m´as utilizada es LRU (Least Recently Used ). Como se aprecia en al figura 3.6, el plug-in de simulaci´on soporta cualquier pol´ıtica, a partir de la extensi´on de la clase SimulatorReplacementPolicy.

Figura 3.6: Modelado de la pol´ıtica de reemplazo en el simulador.

3.3.2.

Dise˜ no General

Uno de los aspectos m´as importantes de SimiOO tiene que ver con la interfaz gr´afica presentada al usuario (ver figura 3.7), compuesta por los siguientes elementos: Barra de men´ ues: en la parte superior de la pantalla, presenta los men´ ues b´asicos (File, Run, Plugins, Help). Barra de herramientas: implementa, mediante botones y otros controles gr´aficos, muchas de las funcionalidades de la barra de men´ ues.

3.3. LA HERRAMIENTA SIMIOO

49

Perspectiva: regi´on principal de la pantalla, donde el plug-in despliega informaci´on e interact´ ua con el usuario. Un plug-in aporta una “perspectiva” a SimiOO, y tiene la libertad de administrar el contenido de la misma seg´ un su conveniencia. Toda perspectiva estar´a integrada por una o m´as “vistas”. La barra de men´ ues est´a integrada por las acciones que se listan en la tabla 3.1. Por otra parte, cada men´ u agrega dos secciones (group markers) al principio y al final en donde, de ser necesario, un plug-in podr´ıa agregar sus propias opciones (no globales). Men´ u

File

Run

Plugins Help

Opci´ on New Open Close Save Exit Play Pause Stop Open Trace (lista de plug-ins disponibles) Preferences Help Contents About SimiOO

Cuadro 3.1: Acciones definidas en SimiOO.

La barra de herramientas est´a constituida por botones gr´aficos, que equivalen a algunas de las acciones (las m´as utilizadas) de la barra de men´ ues. A su vez, un plug-in podr´ıa agregar sus propios controles gr´aficos a esta barra. La perspectiva es lo que el plug-in est´a interesado en mostrarle al usuario en la regi´on principal de la pantalla. Por ejemplo, para el caso del plug-in de simulaci´on, la perspectiva est´a integrada por tres vistas: una para

3.3. LA HERRAMIENTA SIMIOO

Barra de menúes

Barra de herramientas

50

Perspectiva

Figura 3.7: Interfaz gr´ afica de SimiOO, presentada al usuario.

visualizar la representaci´on gr´afica de cada organizaci´on simulada, otra para navegar (en una jerarqu´ıa de a´rbol) las diferentes organizaciones, y otra para desplegar mensajes al usuario. El plug-in le aporta una perspectiva a SimiOO a trav´es del punto de extensi´on org.eclipse.ui.perspectives. El otro aspecto importante tiene que ver con la forma en que un plug-in externo se “enchufa” en SimiOO. Para este fin, SimiOO define un punto de extensi´on propio (es decir, no perteneciente al conjunto est´andar de puntos de extensi´on provistos por Eclipse) denominado org.simioo.traceProcessor, que permite aportar la l´ogica de pro-

´ 3.4. EL PLUG-IN DE SIMULACION

51

cesamiento de cada referencia obtenida de la traza. Para ello, todo plug-in que desee contribuir a SimiOO a trav´es de este punto, deber´a extender la clase org.simioo.clients.SimiooTraceProcessor, sobreescribiendo, entre otros, los m´etodos initProcessor(), processReference(MemoryReference) y finalizeProcessor(). De esta forma, el ciclo de vida de un procesador de trazas est´a definido por la siguiente secuencia (ver figura 3.8): 1. Inicializaci´on del procesador (initProcessor()). 2. Lectura secuencial de la traza, e invocaci´on al m´etodo de procesamiento (processReference(MemoryReference)) por cada referencia le´ıda. 3. Finalizaci´on del procesador (finalizeProcessor()). Es importante aclarar que ninguno de estos m´etodos debe ser obligatoriamente sobreescrito. En caso que el plug-in no lo haga, esa etapa tendr´a un comportamiento nulo. Por otra parte, tambi´en es preciso notar que todo el trabajo de lectura de la traza y control de reproducci´on se encuentra del lado de SimiOO, lo cual permite el desarrollo de plug-ins livianos, cuya u ´nica preocupaci´on radica en el procesamiento a aplicar a cada referencia le´ıda.

3.4.

El Plug-in de Simulaci´ on

A continuaci´on se presentar´a, con m´as detalle, el plug-in de simulaci´on de memorias cach´e, que se distribuye junto a SimiOO. Este implementa la t´ecnica de simulaci´on manejada por trazas, que permite evaluar el desempe˜ no de organizaciones de memoria cach´e, en base a la secuencia (traza) de referencias a memoria realizada por un conjunto de programas (benchmarks).

3.4.1.

Dise˜ no General

El plug-in de simulaci´on extiende al entorno SimiOO, aport´andole una perspectiva, un conjunto de vistas y un procesador de trazas. Como ya se

´ 3.4. EL PLUG-IN DE SIMULACION

52

Figura 3.8: Integraci´ on SimiOO - Plug-in.

se˜ nal´o, una perspectiva agrupa vistas, y permite la construcci´on de una interfaz gr´afica de usuario. El plug-in que extiende, tiene la libertad de disponer el contenido de la perspectiva y las vistas como prefiera; en particular, la aportada por el plug-in de simulaci´on contiene tres vistas: un navegador de organizaciones de memoria (en el lado izquierdo de la pantalla), una vista de representaci´on gr´afica y visualizaci´on de informaci´on (en la parte superior derecha de la pantalla), y una vista de mensajes (en la parte inferior derecha de la pantalla), seg´ un puede verse en la figura 3.9. Por otra parte, el procesador de trazas aportado a SimiOO (y que extiende a la clase SimiooTraceProcessor), toma cada referencia le´ıda desde la traza abierta, y la alimenta en cada organizaci´on cach´e simulada.

´ 3.4. EL PLUG-IN DE SIMULACION

53

Navegador de organizaciones

Representación gráfica e información

Mensajes

Figura 3.9: Interfaz gr´ afica del simulador.

3.4.2.

Integraci´ on Dominio−Interfaz

El plug-in de simulaci´on presenta dos aspectos muy bien definidos: por un lado, los objetos del dominio (memorias, organizaciones de memorias, referencias, etc.) y, por el otro, la representaci´on gr´afica de los mismos. En el caso particular de la vista (´arbol) de navegaci´on de organizaciones, la relaci´on entre los objetos del dominio y su representaci´on gr´afica, se llev´o a cabo utilizando el modelo de “proveedores de contenidos y r´otulos” de JFace [20]. Un “proveedor” (de contenidos o r´otulos) es una clase que se comporta como

3.5. CONCLUSIONES

54

“intermediario” adaptando los datos del dominio al formato utilizado por los controles gr´aficos, logr´andose as´ı un alto nivel de desacoplamiento.

3.4.3.

Motor de Simulaci´ on

Por su parte, la clase MemoryOrganization tambi´en contiene la l´ogica de simulaci´on. A trav´es de un m´etodo, es posible “alimentarla” con las referencias le´ıdas desde la traza, lo cual producir´a aciertos (hits) o desaciertos (misses) en la memoria, con sucesivas actualizaciones de la informaci´on estad´ıstica de cada bloque. Es preciso aclarar que, en esta primer etapa del proyecto, solo se contempla la pol´ıtica de reemplazo LRU (Least Recently Used ). La clase SimulatorTraceProcessor es la responsable de alimentar cada una de las organizaciones simuladas, con las referencias le´ıdas. Esta clase extiende a la provista por SimiOO, SimiooTraceProcessor, sobreescribi´endole los m´etodos de inicializaci´on, finalizaci´on y procesamiento de referencias (ver figura 3.10).

3.5.

Conclusiones

Se present´o un ambiente, p´ ublico y de c´odigo abierto, para el estudio de organizaciones de memoria cach´e mediante la t´ecnica de simulaci´on manejada por trazas (trace-driven simulation). Esta herramienta, llamada SimiOO, est´a construida sobre la Plataforma de Cliente Rico (Rich Client Platform) del Proyecto Eclipse, y basada en plug-ins. Esta u ´ltima caracter´ıstica permite la implementaci´on de diferentes funcionalidades aplicables a una traza, tales como convertirla de su formato original a uno nuevo, o tomarla desde un archivo de texto plano y almacenarla en un archivo comprimido, aplicarle alg´ un tipo de filtrado o muestreo, etc. En este sentido, la simulaci´on manejada por trazas es un caso particular. Finalmente, este trabajo muestra una posibilidad de integraci´on de herramientas de desarrollo de software (como ser Eclipse y el lenguaje Java) en el

3.5. CONCLUSIONES

Figura 3.10: Modelo de clases del motor de simulaci´ on.

´ambito de la computaci´on cient´ıfica [27].

55

Cap´ıtulo 4 Un Esquema de Memoria Cach´ e para Ambientes Multihilo 4.1.

Introducci´ on

Un cach´e es un lugar oculto, normalmente en la tierra, utilizado para guardar municiones, comida, tesoros, etc. Dicho de otra forma, es un lugar seguro para ocultar provisiones. En computaci´on, las organizaciones de memoria cach´e consisten en peque˜ nas memorias de alta velocidad de acceso, y capaces de mantener temporalmente copias de datos e instrucciones de un programa que, debido al principio de localidad para las referencias a memoria presente en las aplicaciones, se acceder´an en el corto plazo. As´ı, el procesador tiene la “chance” de encontrar all´ı el valor requerido, evitando el acceso a memoria principal (situaci´on m´as costosa y, por lo tanto, menos deseable). Las organizaciones de memoria cach´e han sido utilizadas con ´exito desde hace m´as de veinte a˜ nos. Sin embargo, en los u ´ltimos cinco a˜ nos, un nuevo dise˜ no de procesadores capaz de ejecutar simult´aneamente varios flujos (“hilos”) ha planteado nuevos interrogantes sobre el comportamiento de estas memorias en situaciones de competencia. 56

4.2. PARALELISMO A NIVEL DE INSTRUCCIONES

57

En este cap´ıtulo se propone una nueva organizaci´on de memoria cach´e para ambientes multihilo. Este dise˜ no, que ha sido llamado SWSA-MT (Shared Way Set Associative − Multithreading), es comparado contra esquemas tradicionales asociativos por conjuntos de grado k. El estudio se lleva a cabo mediante la t´ecnica de simulaci´ on manejada por trazas, utilizando el simulador tratado en el cap´ıtulo 3, que es “alimentado” por las trazas recolectadas como se describi´o en el cap´ıtulo 2. Antes de comenzar a analizar la organizaci´on propuesta SWSA-MT, en las pr´oximas secciones se har´a una introducci´on al concepto de paralelismo a nivel de instrucciones y se presentar´an los fundamentos de los nuevos procesadores multihilo.

4.2.

Paralelismo a Nivel de Instrucciones

Un procesador escalar opera con datos escalares. En sus formas m´as simples, estas arquitecturas pueden trabajar con n´ umeros enteros y, en versiones m´as avanzadas, pueden operar con n´ umeros de punto flotante. Sin embargo, tal vez la caracter´ıstica m´as sobresaliente sea el hecho de que solamente pueden ejecutar una instrucci´on a la vez. Como ejemplos pueden citarse la arquitectura Intel i486 (CISC) y la arquitectura Sun SPARC CY7C601 (RISC) [40]. Cuando el tipo de dato sobre el cual operan las instrucciones es un vector, entonces estamos en presencia de otra clase de procesador: el procesador vectorial. En este caso, las operaciones manipulan arreglos lineales de n´ umeros (enteros o de punto flotante), con la ventaja de que el c´omputo sobre los elementos del vector puede realizarse en forma paralela. Estas arquitecturas son adecuadas para procesamiento cient´ıfico o de multimedia [15] y, como ejemplos, pueden citarse la serie de procesadores Cray (1, 2, X-MP e Y-MP), el nuevo procesador Cell (desarrollado por Sony, Toshiba e IBM) para la consola PlayStation 3, y el conjunto de instrucciones SIMD (Single Instruction, Multiple Data) de Intel (MMX, SSE, SSE2, SSE3 y SSE4) y AMD (3DNow!),

4.2. PARALELISMO A NIVEL DE INSTRUCCIONES

58

entre otros. Un procesador superescalar es capaz de ejecutar dos o m´as instrucciones simult´aneamente, replicando unidades funcionales (ALU, unidad de desplazamiento, unidad de punto flotante, etc.). As´ı, si bien las instrucciones operan sobre datos simples (como en los procesadores escalares), dos o m´as instrucciones pueden estar procesando simult´aneamente, aprovechando la redundancia de unidades funcionales. Por otra parte, el paralelismo a nivel de instrucciones puede explotarse mediante el uso de un mecanismo auxiliar llamado “tuber´ıa” (pipeline), que permite procesar en paralelo solapando la ejecuci´on de las instrucciones. Cuando una instrucci´on ingresa a la tuber´ıa para ser ejecutada, atraviesa varias etapas, hasta que su ejecuci´on se completa al final de la u ´ltima de estas etapas, en forma similar al funcionamiento de una l´ınea de montaje en serie de autom´oviles. Cuando la instrucci´on pasa de la etapa i a la etapa i + 1, la siguiente instrucci´on en el flujo de ejecuci´on puede ingresar a la etapa i que acaba de desocuparse. En un caso ideal, una instrucci´on es ejecutada por cada T unidades de tiempo, siendo T el tiempo que insume la etapa m´as lenta. El uso de este mecanismo no mejora la latencia en la ejecuci´on de las instrucciones, pero aumenta la tasa a la que se procesan las mismas. TIEMPO

INSTRUCCIONES

IF

ID

EX

MEM

WB

IF

ID

EX

MEM

WB

IF

ID

EX

MEM

WB

IF

ID

EX

MEM

WB

Figura 4.1: Tuber´ıa de 5 etapas.

A modo de ejemplo, en la figura 4.1 se muestra un pipeline simple, con 5

4.2. PARALELISMO A NIVEL DE INSTRUCCIONES

59

etapas: 1. IF (Instruction Fetch): Se toma la instrucci´on indicada por el contador de programa (PC − Program Counter ). 2. ID (Instruction Decode): Se decodifica la instrucci´on en cuesti´on. En caso de un salto condicional, en este punto puede evaluarse la condici´on. 3. EX (Execution): Se ejecuta la instrucci´on, con posible uso de la unidad aritm´etico-l´ogica (ALU). 4. MEM (Memory Access): Se accede a memoria, para carga o almacenamiento. 5. WB (Write-Back ): Se escribe el resultado (operando de salida) en el registro correspondiente. Si cada etapa de la tuber´ıa insume un ciclo de reloj, y considerando un escenario ideal, se alcanzar´ıa un rendimiento de una instrucci´on ejecutada por ciclo de reloj. Es decir, en estado de r´egimen, a la salida del pipeline podr´ıa observarse una instrucci´on finalizada cada un ciclo de reloj o, dicho de otra forma, la cantidad de ciclos por instrucci´on (CPI) es igual a 1: CP Iideal = 1. Sin embargo, ese valor de CPI ideal dista mucho de lo que sucede en la pr´actica donde, ante un “riesgo” (hazard ), la tuber´ıa podr´ıa detenerse moment´aneamente. Estas situaciones pueden clasificarse en: 1. Riesgos estructurales (structural hazards): debido a que dos o m´as instrucciones en la tuber´ıa intentan acceder al mismo recurso en el procesador, de manera simult´anea. 2. Riesgos de datos (data hazards): debido a, por ejemplo, una instrucci´on de la tuber´ıa que requiere un dato que genera una instrucci´on previa, tambi´en en la tuber´ıa (y que, debido al solapamiento, podr´ıa no haberse completado).

4.3. PROCESADORES MULTIHILO

60

3. Riesgos de control (control hazards): debido a saltos durante la ejecuci´on del flujo de instrucciones. Ante estas situaciones, la tuber´ıa se detiene hasta que el riesgo sea resuelto (por ejemplo, que concluya la ejecuci´on de la instrucci´on que debe producir el dato requerido). As´ı, el rendimiento ideal de una instrucci´on por ciclo comienza a degradarse. En la pr´actica, estas situaciones suelen ser muy frecuentes, lo que resulta en una reducci´on significativa en el solapamiento (o paralelismo) a nivel de instrucciones. Por ejemplo, para un programa MIPS t´ıpico, la frecuencia de instrucciones de salto condicional podr´ıa ser del 25 % [15]. Esto significa que, cada cuatro instrucciones ejecutadas, el procesador se encuentra ante un hazard de control. Para maximizar el aprovechamiento de los recursos del procesador se requiere un alto grado de paralelismo a nivel de instrucciones (ILP − Instruction Level Parallelism). Si, como ocurre en la pr´actica, este paralelismo es escaso, entonces deber´an analizarse otras estrategias que le den la oportunidad, al procesador, de ejecutar m´ ultiples instrucciones simult´aneamente. Una posibilidad, con gran auge en los u ´ltimos tiempos, es el aprovechamiento del paralelismo a nivel de “hilo” de ejecuci´on (ILP − Thread Level Parallelism), t´ecnica que se presenta a continuaci´on.

4.3.

Procesadores Multihilo

En adici´on al problema del bajo nivel de ILP (lo que conlleva a un uso ineficiente de los recursos), un procesador superescalar tambi´en se caracteriza por desperdiciar capacidad de c´omputo, permaneciendo durante algunos ciclos de reloj en estado ocioso (idle). En ocasiones, la ejecuci´on del flujo de instrucciones suele bloquearse debido a, entre otras cosas, malas predicciones de los saltos, desaciertos en la memoria cach´e de instrucciones, operaciones de E/S, etc., lo que se traduce indefectiblemente en un procesador ocioso, a la espera de una instrucci´on a ejecutar. Resumiendo, un procesador puede sufrir de:

4.3. PROCESADORES MULTIHILO

61

Desperdicio Horizontal: debido al bajo nivel de ILP que impide, para un ciclo de reloj, usar eficientemente los recursos (unidades funcionales) disponibles. Desperdicio Vertical: debido al bloqueo o latencias en las instrucciones ejecutadas, con lo cual, el procesador debe permanecer ocioso. Una soluci´on al uso ineficiente de los recursos del procesador consiste en la utilizaci´on de m´ ultiples hilos (o flujos) de instrucciones, t´ecnica conocida como ejecuci´ on multihilo. En este trabajo, el concepto de hilo (thread ) difiere al utilizado en el a´mbito del software; aqu´ı se har´a referencia a flujos de instrucciones soportados a nivel de hardware, a diferencia de los hilos creados por el sistema operativo o por el usuario. Sin embargo, en muchos casos, un hilo a nivel de software, podr´ıa corresponderse con un hilo a nivel de hardware. En este sentido, el modelo de ejecuci´on multihilo puede clasificarse en [38]: Multihilo expl´ıcito: cuando el procesador ejecuta hilos o procesos del usuario (e.g., del sistema operativo). Es decir, hay una correspondencia directa entre los hilos de software y los hilos de hardware soportados por el procesador. Multihilo impl´ıcito: cuando el procesador tiene la capacidad de generar, din´amicamente, hilos propios a partir de un u ´nico flujo de instrucciones, mediante mecanismos de especulaci´on. Esto puede lograrse, por ejemplo, explotando la independencia entre secuencias de instrucciones, como podr´ıa ser cada iteraci´on de un bucle (en este caso, cada hilo impl´ıcito corresponder´ıa a la ejecuci´on de una iteraci´on, si las iteraciones son independientes una de otra). En general, la capacidad para generar hilos impl´ıcitos por parte del procesador suele mejorarse con el soporte del compilador. En este trabajo se har´a referencia al primer esquema (multihilo expl´ıcito), por ser el encontrado en los procesadores modernos, aunque es importante

4.3. PROCESADORES MULTIHILO

62

destacar que la organizaci´on cach´e propuesta es independiente del origen de los hilos en ejecuci´on. En los procesadores con multihilo expl´ıcito existen dos alternativas para el manejo concurrente de la ejecuci´on. Por una parte, los hilos podr´ıan ser ejecutados en forma intercalada, mediante sucesivos cambios de contexto (notar que, en un momento determinado, un u ´nico hilo tiene disponible la totalidad de los recursos del procesador). Dependiendo de la granularidad con la que se intercalan los hilos, podr´ıamos estar en presencia de alguna de las siguientes pol´ıticas: FMT (Fine-grain Multithreading): los flujos (hilos) se alternan en cada instrucci´on ejecutada. CMT (Coarse-grain Multithreading): los flujos (hilos) se alternan cuando el que estaba en ejecuci´on incurre en alguna penalidad, tal como un desacierto en la memoria cach´e L2 [15]. La otra alternativa consiste en ejecutar los hilos disponibles en forma simult´anea, dise˜ no conocido como SMT (Simultaneous Multithreading). Esta t´ecnica, propuesta por Eggers y otros en [9], busca minimizar tanto el desperdicio horizontal como tambi´en el desperdicio vertical. Para evitar que el procesador permanezca ocioso, las instrucciones a ejecutar se toman de varios flujos simult´aneamente, de manera tal que, ante el bloqueo de uno de ellos, se pueda continuar con la ejecuci´on de alguno de los otros. En realidad, la anterior ya es una caracter´ıstica de la pol´ıtica FMT. La diferencia est´a en que un esquema SMT busca maximizar, para cada ciclo de reloj, la utilizaci´on de los recursos del procesador. Si el flujo (proceso o hilo) en ejecuci´on presenta un alto nivel de ILP, entonces ese paralelismo permite explotar al m´aximo la utilizaci´on de las unidades funcionales para un ciclo de reloj. Por otra parte, si varios flujos presentan cada uno un bajo nivel de ILP, entonces pueden ser ejecutados simult´aneamente, para maximizar el aprovechamiento de los recursos. En la figura 4.2 puede observarse c´omo se utilizan los recursos en

4.3. PROCESADORES MULTIHILO

63

funci´on del tiempo para las arquitecturas Superescalar, FMT y SMT. Claramente, el esquema SMT presenta un mejor aprovechamiento de las unidades funcionales, al explotar tanto el paralelismo a nivel de instrucciones como el paralelismo a nivel de hilo. UNIDADES FUNCIONALES

TIEMPO

Superscalar

FMT

SMT

Hilo 1

Desperdicio vertical

Hilo 2 Hilo 3

Desperdicio horizontal

Figura 4.2: Uso de los recursos en arquitecturas Superescalar, FMT y SMT.

Como resultado, el esquema SMT permite ocultar las latencias de memoria (debido a desaciertos en la cach´e de nivel 1), como tambi´en otras latencias generadas por operaciones de E/S o de sincronizaci´on [22], ya que en dichos casos, los recursos pueden ser aprovechados por otros hilos de ejecuci´on. Sin embargo, el uso de esta t´ecnica genera nuevos desaf´ıos, particularmente en el dise˜ no de las unidades funcionales que se ven involucradas y afectadas por la explotaci´on del paralelismo a nivel de hilo (TLP − Thread Level Parallelism). Es decir, debe replantearse la concepci´on de aquellos recursos que se comparten entre los hilos. La memoria cach´e de nivel 1 es una de las componentes m´as afectadas, debido a que la existencia de m´ ultiples instrucciones pertenecientes a m´ ultiples hilos de ejecuci´on dentro del procesador genera una situaci´on de competencia que se traduce en una alta interferencia

4.4. JERARQU´IA DE MEMORIA

64

de los hilos en las l´ıneas de la memoria. Por ejemplo, para un esquema de Correspondencia Directa (DM - Direct Mapped ) y una carga dada, la tasa de desaciertos (miss rate), desde uno a ocho hilos, va desde 2.5 % a 14.1 % (para la cach´e de instrucciones), y desde 3.1 % a 11.3 % (para la cach´e de datos) [36]. En este cap´ıtulo se propone y analiza el desempe˜ no de un nuevo esquema de memoria cach´e concebido a partir de la adaptaci´on de una arquitectura de memoria cach´e de banco compartido aplicada a un ambiente SMT.

4.4.

Jerarqu´ıa de Memoria

Todo sistema de c´omputo presenta una jerarqu´ıa de memoria organizada en niveles, como se aprecia en la figura 4.3. Aprovechando el principio de localidad, para las referencias a memoria, presente en las aplicaciones, se espera que el procesador haga un uso intensivo de un conjunto peque˜ no de datos e instrucciones en un tiempo corto. De esta forma, se mantiene temporalmente una copia de estos datos e instrucciones en una memoria de tama˜ no reducido (y, por lo tanto, de r´apido acceso) cercana al procesador (en la pr´actica, dentro del mismo circuito integrado). A estas memorias de r´apido acceso, presentes en los procesadores, se las denomina “cach´es”. Cuando un dato o una instrucci´on no es encontrada en la memoria cach´e, deber´a recurrirse al nivel inferior (de mayor tama˜ no) en la jerarqu´ıa de memoria. A esta situaci´on se le llama “desacierto” y, en la pr´actica, se busca minimizar su n´ umero, ya que implica acceder a una memoria de mayor tama˜ no y, por lo tanto, m´as lenta. Adem´as, dado que cada nivel est´a incluido en el inferior, deber´a ser actualizado en caso de desacierto. En los procesadores actuales, existen dos o m´as niveles de memoria cach´e (nivel 1 o L1, nivel 2 o L2, etc.), cada uno siendo m´as grande y de mayor tiempo de acceso que el anterior. En particular, la cach´e de nivel 1 (que es el m´as peque˜ no y m´as r´apido de estos niveles) est´a dividida en dos partes, una asignada a los datos (cach´e de datos) y la otra a las instrucciones (cach´e de

4.4. JERARQU´IA DE MEMORIA

Caché (L1, L2 y L3)

Memoria Principal

Capacidad y Tiempo de acceso

Costo

Registros de la CPU

65

Memoria Secundaria y Dispositivos de E/S

Figura 4.3: Niveles de una jerarqu´ıa de memoria cl´asica.

instrucciones). Adem´as, en todos los casos, las memorias cach´e se caracterizan por la estrategia utilizada para ubicar un dato obtenido desde el nivel inferior, en caso de desacierto. En este sentido, una organizaci´on cach´e puede ser: De correspondencia directa (direct mapping): cuando el nuevo dato solo puede ser ubicado en un u ´nico lugar en la cach´e. Asociativa por conjuntos (set associative): cuando el nuevo dato puede ser ubicado en un conjunto de lugares posibles. Completamente asociativa (fully associative): cuando el nuevo dato puede ser ubicado en cualquier lugar de la cach´e. El mecanismo de acceso a la cach´e es mediante indexaci´on (i.e., a partir de la direcci´on de memoria que est´a siendo referenciada, se genera un ´ındice para acceder a la cach´e), como se explicar´a en la secci´on 4.5.

´ DE DESACIERTOS 4.5. CLASIFICACION

4.5.

66

Clasificaci´ on de Desaciertos

En el estudio de organizaciones de memoria cach´e, una de las figuras de m´erito es la tasa de desaciertos (miss rate). Cuando el procesador necesita un dato, si este se encuentra en la memoria cach´e, decimos que se produjo un acierto (hit). En caso contrario, estamos en presencia de un desacierto (miss), que desencadenar´a un mecanismo para recuperar dicho dato desde alg´ un nivel inferior en la jerarqu´ıa de memoria, el cual es de mayor tama˜ no y, por lo tanto, insume un mayor tiempo de acceso. El mecanismo de b´ usqueda para determinar si un dato se encuentra (o no) en la memoria cach´e, es mediante indexaci´on (i.e., a partir de la direcci´on de memoria que est´a siendo referenciada, se genera un ´ındice para acceder a la cach´e). La direcci´on de memoria del dato en cuesti´on puede descomponerse seg´ un se muestra en la figura 4.4. Los bits que conforman el ´ındice permiten acceder a un conjunto en particular dentro de la cach´e, mientras que el r´otulo (o tag), es utilizado para decidir si la l´ınea indexada contiene el bloque buscado. Finalmente, el desplazamiento (o block offset) selecciona, dentro del bloque, el dato solicitado. Dirección del bloque Rótulo

Índice

Desplazamiento del bloque

Figura 4.4: Direcci´ on de memoria.

Si los bits de r´otulo de la direcci´on referenciada no coinciden con los del bloque almacenado en la l´ınea de cach´e, entonces estamos en presencia de un desacierto. La fracci´on de accesos a cach´e que resultan en desaciertos se conoce como tasa de desaciertos (miss rate) [15]. Es de inter´es conocer el motivo por el cual se producen los desaciertos en la cach´e, de manera tal de poder tomar decisiones en el dise˜ no de la organizaci´on de memoria. En este sentido, se han propuesto varias clasificaciones, siendo la m´as popular la perteneciente a M. Hill et al. [17], conocida como “modelo

´ DE DESACIERTOS 4.5. CLASIFICACION

67

de las 3C”. Este modelo clasifica los desaciertos en tres tipos: obligatorios (compulsory), de capacidad (capacity) y de conflicto (conflict). Cada una de estas clases es cuantificada de la siguiente forma: Desaciertos obligatorios (compulsory): son los producidos en una organizaci´on de memoria cach´e de tama˜ no infinito. Dicho de otra manera, son los desaciertos debidos al acceso por vez primera a bloques de memoria. Desaciertos de capacidad (capacity): son los desaciertos no obligatorios, producidos en una organizaci´on LRU completamente asociativa (fullyassociative) de igual tama˜ no a la cach´e siendo estudiada. B´asicamente, son causados por referenciar mayor cantidad de bloques que los que caben en la cach´e. Desaciertos de conflicto (conflict): son los producidos en la cach´e siendo estudiada, menos los desaciertos de capacidad y obligatorios. El “modelo de las 3C” es ampliamente usado en el estudio de memorias cach´e. Sin embargo, es sabido que en algunos casos puede generar una cantidad negativa de desaciertos de conflicto. Teniendo en cuenta la definici´on brindada en el p´arrafo anterior, esto significa que existen referencias que son aciertos en la cach´e siendo estudiada pero son desaciertos en la organizaci´on completamente asociativa de igual tama˜ no. Estos desaciertos son denominados “de anticonflicto” [23] y, si bien se consideran poco frecuentes en la pr´actica [16] [23], Hamkalo et. al [12] demuestran que su presencia puede ser significativa en programas de evaluaci´on t´ıpicos, como los benchmarks SPEC95. Por ejemplo, el promedio de los SPECfp95 para una cach´e de correspondencia directa de 8-KB, produce una tasa de desaciertos de anticonflicto del 21,1 % (para el caso de instrucciones), y una tasa del 8,3 % (para el caso de datos). Para el promedio de los SPECint95, una cach´e de 16-KB de instrucciones presenta una tasa de desaciertos de anticonflicto del 19,7 %, mientras que la de datos presenta una tasa del 9,9 %.

´ DE DESACIERTOS 4.5. CLASIFICACION

68

Hamkalo et. al [12] proponen una extensi´on al “modelo de las 3C”, denominado “modelo de las 3C determin´ıstico” (D3C), y que evita la existencia de cantidades negativas de desaciertos a partir de la generaci´on de una taxonom´ıa. En el modelo D3C, la clasificaci´on se redefine de la siguiente manera: Desaciertos obligatorios (compulsory): son los producidos en una organizaci´on de memoria cach´e de tama˜ no infinito, y tambi´en en la ca1 ch´e siendo estudiada . Desaciertos de capacidad (capacity): son los desaciertos no obligatorios, producidos en la cach´e siendo estudiada, y tambi´en en una organizaci´on LRU completamente asociativa (fully-associative) de igual tama˜ no. Desaciertos de conflicto (conflict): son los producidos en la cach´e siendo estudiada, menos los desaciertos de capacidad y obligatorios. Para la clasificaci´on anterior puede darse una definici´on operativa a partir del concepto de “distancia LRU” para un bloque B. Dicha distancia es definida como la cantidad de bloques diferentes que fueron referenciados desde el u ´ltimo acceso a B. De esta forma, el desacierto producido por referenciar a un bloque B con distancia LRU D en una cach´e de T bloques de tama˜ no, puede clasificarse de la siguiente manera: Obligatorio → distancia D no computable Capacidad → D > T Conflicto → D ≤ T La redefinici´on en los conceptos de desacierto obligatorio y de capacidad, evita computar como desaciertos a aquellas referencias que, en la pr´actica, son aciertos en la cach´e estudiada. Como consecuencia, el modelo D3C nunca 1 Este requisito adicional contempla los casos en donde un bloque es referenciado por primera vez, pero no es desacierto por haber sido le´ıdo, a la cach´e estudiada, en forma adelantada mediante alg´ un mecanismo de prefetching.

´ 4.6. OTROS CRITERIOS Y METRICAS

69

genera componentes negativas de desaciertos y, adem´as, permite construir una taxonom´ıa al clasificar individualmente cada referencia. Como se analiza en la secci´on 4.9, los modelos 3C y D3C presentan dificultades para clasificar patrones de accesos en ambientes multihilo y, por esta raz´on, all´ı se replantea la clasificaci´on.

4.6.

Otros Criterios y M´ etricas

En esta secci´on se definen las siguientes m´etricas adicionales, que son utilizadas para el an´alisis de las memorias bajo estudio: tasa de reubicaci´ on y tasa de aciertos compartidos. En la organizaci´on para ambientes multihilo SWSA-MT presentada en este trabajo, cada hilo posee una v´ıa para uso exclusivo. Ante un desacierto, se podr´ıa optar por buscar el dato en las memorias privadas de los dem´as hilos. Si el dato es hallado utilizando esta pol´ıtica, podr´ıa optarse por “moverlo” desde la memoria privada hacia el banco compartido, situaci´on conocida como “reubicaci´on”. La fracci´on de accesos a cach´e que resultan en reubicaciones se conoce como tasa de reubicaci´on (reallocation rate). Por u ´ltimo, en un ambiente multihilo podr´ıa interesar conocer en qu´e grado los datos en la cach´e son compartidos por diferentes hilos. Para ello se defini´o la tasa de aciertos compartidos (shared-hit rate), es decir, la fracci´on de accesos a cach´e que resultan en aciertos en donde el bloque en cuesti´on ya ha sido referenciado por otros hilos.

4.7.

El esquema de banco compartido SWSA

En la jerarqu´ıa de memoria de una computadora, el nivel m´as cercano al procesador corresponde a la memoria cach´e de nivel 1 (L1). Esta memoria est´a dividida en 2 partes: una asignada a los datos (cach´e de datos) y la otra a las instrucciones (cach´e de instrucciones). En la mayor´ıa de los procesadores modernos (AMD Athlon, Pentium III/IV, etc.), el tama˜ no de estas memorias

4.7. EL ESQUEMA DE BANCO COMPARTIDO SWSA

70

oscila entre los 8-KB y 64-KB (para la de datos), y entre los 16-KB y 32-KB (para la de instrucciones), con l´ıneas de entre 32 y 128 bytes, y asociatividades de grado 2 o´ 4 [15]. En todos los casos, los bancos de memoria que se utilizan para implementar las v´ıas de la cach´e asociativa por conjunto, tienen igual tama˜ no, y este est´a dado en potencias de 2 para explotar el indexado por selecci´on de bits. El usar bancos de igual tama˜ no es una restricci´on adicional al dise˜ no, la cual puede ser removida. Si en un esquema de asociatividad mayor o igual a 2 (2WSA, 4WSA, etc.) se quita la restricci´on de que los bancos sean de igual tama˜ no, nos encontramos frente a una organizaci´on de memoria cach´e de nivel 1, conocida como SWSA (Shared-Way Set Associative) [13]. En la figura 4.5 puede observarse un caso para el esquema SWSA, con el primer banco de tama˜ no C 1 y el segundo banco de tama˜ no C2 = C1 /2 y cada l´ınea del segundo banco estar´a compartida por dos l´ıneas en el primer banco. BANCO 1

BANCO 2

Figura 4.5: Esquema de asociatividad en una organizaci´ on SWSA.

El quitar la restricci´on de bancos de igual tama˜ no, permite obtener una memoria cach´e cuyo tama˜ no total no necesariamente sea potencia de 2. El grado de asociatividad para esta organizaci´on es definido en [13] como: n=1+

C2 C1

Para el ejemplo de la figura 4.5, el grado de asociatividad es igual a 1,5. A partir de esta definici´on, podemos deducir a las organizaciones de

´ DEL ESQUEMA SWSA A UN AMBIENTE 4.8. ADAPTACION MULTIHILO: SWSA-MT 71 correspondencia directa y asociativa por conjuntos de grado 2 como casos particulares de la organizaci´on m´as general SWSA [13].

4.8.

Adaptaci´ on del esquema SWSA a un ambiente multihilo: SWSA-MT

La organizaci´on SWSA como fue concebida originalmente no evita el problema de la interferencia entre los hilos que se ejecutan, dado que los bancos no son privados, sino que se comparten entre todos los hilos de ejecuci´on. En realidad, tampoco lo evitan otras organizaciones t´ıpicas, a menos que cada hilo disponga de una memoria para uso privado, lo cual no es admisible (por el desperdicio que se originar´ıa en escenarios con menor cantidad de hilos disponibles). En [35] se efect´ ua un an´alisis respecto del impacto en el desempe˜ no de una memoria cach´e DM de nivel 1, privada y compartida. Se deduce que un esquema privado por hilo de ejecuci´on tiene un mal desempe˜ no para pocos o un u ´nico hilo, ya que en ese caso se desperdician porciones de memoria que no pueden ser accedidas. Como contrapartida, un esquema compartido se desempe˜ na muy bien con pocos hilos en ejecuci´on, pero se hace muy evidente la interferencia cuando estos aumentan en n´ umero. Lo que se busca en este trabajo es una organizaci´on de memoria cach´e de nivel 1 cuyo desempe˜ no sea aceptable tanto en un ambiente con pocos hilos en ejecuci´on como tambi´en con el n´ umero m´aximo posible. En la organizaci´on que se presenta (que es una adaptaci´on del esquema SWSA), el primer banco es privado (por hilo de ejecuci´on), mientras que el segundo banco se comparte entre todos los hilos (ver figura 4.6). El acceso a esta memoria se lleva a cabo mediante indexaci´on por bits, como en las organizaciones cach´e tradicionales. Adem´as, SWSA-MT permite tama˜ nos totales que no sean potencia de 2, como sucede en el dise˜ no SWSA ya discutido.

´ DEL ESQUEMA SWSA A UN AMBIENTE 4.8. ADAPTACION MULTIHILO: SWSA-MT 72

BANCO 1

BANCO 2

HILO 1

HILO 2

HILO 3

HILO 4

Figura 4.6: Esquema de asociatividad en la organizaci´ on SWSA-MT.

4.8.1.

An´ alisis de Asociatividad

Si ante un desacierto en su memoria privada y en la memoria compartida, un hilo x encuentra el dato en la memoria privada de otro hilo y (siendo x = y), entonces estamos en presencia de un acierto “largo”. Ya que el dato en cuesti´on fue accedido tanto por x como por y, se lo considera “compartido”, y se lo reubica en el banco com´ un2 . A esta estrategia se la denomin´o “reubicaci´on” (reallocation) y, en adelante, se utilizar´an como sin´onimos los t´erminos SWSA-MT, SWSA-MT con reubicaci´on, SWSA-MT realloc, para hacer referencia a la organizaci´on propuesta en esta tesis (y se har´a expl´ıcita la situaci´on en donde se adopte alguna estrategia diferente). 2

El dato que se hallaba en el banco compartido es desalojado sin considerar su antig¨ uedad.

4.9. EL MODELO DE LAS 4C

4.9.

73

El Modelo de las 4C

Los modelos de clasificaci´on de desaciertos, 3C y D3C, presentados en 4.5 fueron concebidos para ambientes de un u ´nico flujo de ejecuci´on. La existencia de m´ ultiples hilos genera interrogantes sobre la aplicabilidad de dichos modelos, y presenta desaf´ıos adicionales que deben ser analizados. Adem´as, como se mostr´o en la secci´on 4.8, cada hilo tiene acceso a una parte acotada de la cach´e, conformada por su porci´on privada m´as la v´ıa compartida. Entonces, no ser´ıa correcto clasificar un desacierto como de capacidad utilizando como par´ametro el tama˜ no total de la memoria, siendo que cada hilo solo puede hacer un uso parcial de la cach´e. Por estas razones, en este trabajo se replante´o la clasificaci´on convencional, y se gener´o un nuevo modelo, llamado “de las 4C”, y que es aplicable en ambientes multihilo. En primer lugar, es de inter´es discriminar los desaciertos de conflicto en un ambiente multihilo, seg´ un: Conflictos propios (un hilo consigo mismo). Conflictos entre hilos (interferencia). Esta subclasificaci´on no est´a contemplada en los modelos 3C y D3C, y es de particular importancia para entender en qu´e grado interfieren los hilos en la organizaci´on cach´e estudiada. Considerando un ambiente como el mostrado en la figura 4.7, la nueva clasificaci´on se define de la siguiente manera: Desaciertos obligatorios (compulsory): son los producidos en una organizaci´on de memoria de tama˜ no infinito, y tambi´en en la cach´e siendo estudiada, considerando todos los hilos 3 . Desaciertos de capacidad (capacity): son los desaciertos no obligatorios, producidos en la cach´e siendo estudiada, y tambi´en en una organizaci´on 3

Este requisito es importante, ya que un hilo podr´ıa traer a cach´e un bloque requerido por otro hilo, en cuyo caso no ser´ıa un desacierto obligatorio.

´ 4.10. AMBIENTE DE SIMULACION

BANCO 1

74

BANCO 2

HILO 1

P C HILO 2

P

Figura 4.7: Organizaci´ on SWSA-MT de tama˜ no T = 2×P + C.

LRU completamente asociativa (fully-associative) de tama˜ no P + C; es decir, la distancia LRU del bloque referenciado es D > P + C. Desaciertos de conflicto cerrado (closed-conflict): son los producidos en la cach´e siendo estudiada, por referencias a bloques con distancia LRU D ≤ P + C, y que fueron desalojados por el propio hilo. Desaciertos de conflicto cruzado (crossed-conflict): son los producidos en la cach´e siendo estudiada, por referencias a bloques con distancia LRU D ≤ P + C, y que fueron desalojados por otros hilos. El “modelo de las 4C” es una extensi´on del modelo D3C y, por lo tanto, contempla los escenarios convencionales (un hilo, cach´e tradicional).

4.10.

Ambiente de Simulaci´ on

4.10.1.

Herramientas

Para la simulaci´on de las organizaciones cach´e bajo estudio, se utiliz´o la herramienta SimiOO descripta en el cap´ıtulo 3, mediante la t´ecnica de simulaci´ on manejada por trazas. El simulador fue “alimentado” con las trazas recolectadas en el cap´ıtulo 2.

´ 4.10. AMBIENTE DE SIMULACION

4.10.2.

75

Arquitecturas Simuladas

Se simularon tres esquemas de memoria cach´e de datos de nivel 1: 2WSA, 4WSA y SWSA-MT (con reubicaci´on), de tama˜ nos 8, 16, 32 y 64-KB, l´ınea de 32 bytes, y se consider´o un ambiente con 4 hilos de ejecuci´on. La pol´ıtica de reemplazo adoptada, en todos los casos, fue LRU (Least Recently Used ).

4.10.3.

Benchmarks

Para la simulaci´on de las organizaciones citadas se utiliz´o un subconjunto de los benchmarks SPLASH-2 [42]: CHOLESKY, FFT, LU, OCEAN, RADIX y WATER. SPLASH-2 est´a construido en base a un conjunto de macros, conocidas como PARMACS, y desarrolladas por ANL (Argonne National Laboratory) [6] [24]. Originalmente, SPLASH-2 fue concebido para procesamiento paralelo y, siendo que en este trabajo se requer´ıan benchmarks multihilo, se utiliz´o una reimplementaci´on de las macros PARMACS con soporte para hilos POSIX (pthreads), provistas por Ernest Artiaga y otros [2], de la Universidad Polit´ecnica de Catalu˜ na. A continuaci´on, se describen brevemente los benchmarks simulados: FFT: implementa una Transformada R´apida de Fourier de un conjunto de n n´ umeros complejos, en una dimensi´on. Adem´as, hace uso del √ algoritmo Radix- n Six-Step descripto en [3]. LU: factoriza una matriz densa, utilizando procesamiento por bloques, como el producto de una matriz triangular inferior y una matriz triangular superior. La matriz a procesar, cuya dimensi´on es n × n, es particionada en N ×N bloques de B×B elementos cada uno, para aprovechar la localidad espacial, seg´ un se detalla en [41]. CHOLESKY: factoriza una matriz rala, utilizando procesamiento por bloques, como el producto de una matriz triangular inferior y su transpuesta. La diferencia respecto al benchmark LU radica en que Cholesky

´ 4.10. AMBIENTE DE SIMULACION

76

trabaja sobre matrices ralas, y los hilos no est´an globalmente sincronizados entre pasos del algoritmo. RADIX: implementa un m´etodo de ordenamiento de n´ umeros enteros utilizando el algoritmo Radix descripto en [5]. OCEAN: esta aplicaci´on permite realizar simulaciones del movimiento de los oc´eanos, a gran escala. WATER: simula el comportamiento de un conjunto de part´ıculas de agua a lo largo del tiempo, analizando las fuerzas y los potenciales entre ellas. Todos los benchmarks fueron ejecutados sobre Valgrind [39], de donde se extrajeron las trazas de referencias a memoria mediante el m´odulo Tracegrind desarrollado en el cap´ıtulo 2. En la siguiente tabla se muestran los par´ametros de ejecuci´on: Benchmark FFT

LU

CHOLESKY

RADIX

OCEAN WATER

´metros Para 4 hilos 64K complejos de doble precisi´ on 26M referencias 4 hilos matriz de 512 × 512 elementos bloques de 16 × 16 elementos 234M referencias 4 hilos tk16.O 314M referencias 4 hilos 1M elementos enteros radix = 1024 239M referencias 4 hilos oc´eano de 258 × 258 269M referencias 4 hilos 512 mol´eculas 236M referencias

4.11. RESULTADOS DE LAS SIMULACIONES

77

4.11.

Resultados de las Simulaciones

4.11.1.

Tasa de Desaciertos

Los primeros resultados a analizar corresponden a la tasa de desaciertos para las organizaciones 2WSA, 4WSA y SWSA-MT (con reubicaci´on). Se busca minimizar la cantidad de desaciertos, ya que estos conllevan penalidades muy elevadas, que producen un aumento en la relaci´on ciclos por instrucci´on (CPI), apart´andolo del ideal de 1 ciclo/instrucci´on. En los resultados que se muestran en las figuras 4.8 y 4.9 puede observarse que la organizaci´on propuesta SWSA-MT presenta una tasa de desaciertos significativamente inferior a la mostrada por el esquema 2WSA, y muy similar a la del esquema 4WSA. FFT

LU

7

9 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

8

6

Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

6.5

5.5 5 4.5 4 3.5 3

7 6 5 4 3 2

2.5 1

2 1.5

0 8

16

32

Tamaño Caché (KB)

64

8

16

32

64

Tamaño Caché (KB)

Figura 4.8: Tasa de desaciertos para los benchmarks FFT y LU.

Las ca´ıdas abruptas en la tasa de desaciertos para la organizaci´on 2WSA se deben a efectos de hiperpaginaci´on (thrashing), por el cual, bloques de

4.11. RESULTADOS DE LAS SIMULACIONES

CHOLESKY

RADIX

11

11 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

10

9

9

Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

10

8 7 6 5 4 3

8 7 6 5 4 3 2

2

1

1

0 8

16

32

64

8

Tamaño Caché (KB)

16

32

64

Tamaño Caché (KB)

OCEAN

WATER

24

9 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

8 Tasa de Desaciertos en Datos de L1 (%)

22 Tasa de Desaciertos en Datos de L1 (%)

78

20

18

16

14

12

10

7 6 5 4 3 2 1

8

0 8

16 32 Tamaño Caché (KB)

64

8

16 32 Tamaño Caché (KB)

64

Figura 4.9: Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER.

4.11. RESULTADOS DE LAS SIMULACIONES

79

memoria cach´e son continuamente desalojados, independientemente de cu´an recientes sean. El fen´omeno de thrashing puede darse, por ejemplo, en cach´es cuyo tama˜ no no es suficiente para mantener temporalmente el conjunto de datos con los que se est´a trabajando (working set), o tambi´en, por escenarios de interferencia “destructiva” entre varios hilos, cuyos working sets corresponden a la misma regi´on de la memoria cach´e. El u ´ltimo caso es el que aplica a los resultados mostrados; es decir, hiperpaginaci´on por conflictos entre hilos. Si se tratase de thrashing por capacidad, entonces la ca´ıda abrupta en las curvas tambi´en se obervar´ıa en las otras organizaciones estudiadas. Este an´alisis prematuro quedar´a expuesto a continuaci´on, utilizando el “modelo de las 4C” para clasificaci´on de desaciertos.

4.11.2.

Clasificaci´ on de Desaciertos

Para clasificar los desaciertos se utiliz´o el “modelo de las 4C” elaborado en la secci´on 4.9. Los resultados se presentan en las figuras 4.10, 4.11, 4.12, 4.13, 4.14 y 4.15. En primer lugar, queda en evidencia lo que se coment´o en la secci´on anterior: el punto de inflexi´on en la tasa de desaciertos para el esquema 2WSA est´a dado por una elevada interferencia entre hilos (“conflicto cruzado”) para tama˜ nos 8 y 16-KB. Por otra parte, se observa una de las caracter´ısticas m´as importantes de la organizaci´on SWSA-MT; en todos los casos, la cach´e propuesta presenta una menor tasa de desaciertos por conflicto cruzado, en relaci´on a las otros esquemas estudiados. Esta es la virtud m´as sobresaliente de la organizaci´on SWSA-MT ya que, al disponer de memorias privadas para los hilos, se minimiza la interferencia “destructiva” entre los mismos. Tambi´en es cierto que, casi siempre, la organizaci´on propuesta muestra una mayor proporci´on de conflictos cerrados (un hilo consigo mismo) y de conflictos por capacidad. Esto sucede, por ejemplo, para los tama˜ nos 8 y 16-KB para todos los benchmarks, y se debe a que cada hilo puede hacer un uso parcial de la cach´e (P + C bloques) respecto a los esquemas 2WSA y 4WSA en donde, virtualmente, cada hilo tiene disponible el tama˜ no total de la memoria. A

4.11. RESULTADOS DE LAS SIMULACIONES

80

FFT

Clasificación de Desaciertos en Datos de L1 (%)

7 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado

6

5

4

3

2

1

0

T

−M

SA

SA

32−KB

SW

4W

SA

2W T

−M

SA

SA

16−KB

SW

4W

SA

2W T

−M

SA

SA

SW

4W

SA

2W T

−M

SA

SA

SW

4W

SA

2W

8−KB

64−KB

Figura 4.10: Clasificaci´ on de desaciertos para el benchmark FFT. LU

Clasificación de Desaciertos en Datos de L1 (%)

9 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado

8 7 6 5 4 3 2 1 0

64−KB

T

M

− SA

SA

SW

SA

4W

2W

32−KB

T

M

− SA

SA

SW

SA

4W

2W

16−KB

T

M

− SA

SA

SW

SA

4W

2W T

M

− SA

SA

SW

SA

4W

2W

8−KB

Figura 4.11: Clasificaci´ on de desaciertos para el benchmark LU.

4.11. RESULTADOS DE LAS SIMULACIONES

81

CHOLESKY

Clasificación de Desaciertos en Datos de L1 (%)

12 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado

10

8

6

4

2

0

T

−M

SA

SA

32−KB

SW

4W

SA

2W T

−M

SA

16−KB

SW

SA

SA

4W

2W T

−M

SA

SA

SW

SA

4W

2W T

−M

SA

SA

SW

4W

SA

2W

8−KB

64−KB

Figura 4.12: Clasificaci´ on de desaciertos para el benchmark CHOLESKY. RADIX

Clasificación de Desaciertos en Datos de L1 (%)

12 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado

10

8

6

4

2

0

64−KB

T

M

− SA

SA

SW

SA

4W

2W

32−KB

T

M

− SA

SA

T

16−KB

SW

SA

4W

2W

M

− SA

SA

SW

SA

4W

2W T

M

− SA

SA

SW

SA

4W

2W

8−KB

Figura 4.13: Clasificaci´ on de desaciertos para el benchmark RADIX.

4.11. RESULTADOS DE LAS SIMULACIONES

82

OCEAN

Clasificación de Desaciertos en Datos de L1 (%)

25 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado 20

15

10

5

0

T

−M

SA

SA

32−KB

SW

4W

SA

2W T

−M

SA

SA

16−KB

SW

4W

SA

2W T

−M

SA

SA

SW

4W

SA

2W T

−M

SA

SA

SW

4W

SA

2W

8−KB

64−KB

Figura 4.14: Clasificaci´ on de desaciertos para el benchmark OCEAN. WATER

Clasificación de Desaciertos en Datos de L1 (%)

9 Obligatorios Capacidad Conflicto Cerrado Conflicto Cruzado

8 7 6 5 4 3 2 1 0

64−KB

T

M

− SA

SA

SW

SA

4W

2W

32−KB

T

M

− SA

SA

SW

SA

4W

2W

16−KB

T

M

− SA

SA

SW

SA

4W

2W T

M

− SA

SA

SW

SA

4W

2W

8−KB

Figura 4.15: Clasificaci´ on de desaciertos para el benchmark WATER.

4.11. RESULTADOS DE LAS SIMULACIONES

83

pesar de estos desaciertos adicionales en el esquema SWSA-MT, la cach´e propuesta presenta una tasa de desaciertos comparable a la organizaci´on 4WSA y menor a la 2WSA.

4.11.3.

Tasa de Aciertos Compartidos

La tasa de aciertos compartidos, presentada en las figuras 4.16 y 4.17, es una buena pauta del grado de “cooperaci´on”4 que existe entre hilos para una organizaci´on estudiada. Para todos los benchmarks ejecutados, el esquema SWSA-MT con reubicaci´on presenta una tasa de aciertos compartidos menor en relaci´on a las otras organizaciones estudiadas (2WSA y 4WSA). Esto se debe a que la reubicaci´on implica el desalojo de otros bloques que, por su parte, tambi´en podr´ıan ser compartidos entre hilos. A pesar de que la organizaci´on SWSA-MT con reubicaci´on no favorece la cooperaci´on entre hilos (como lo hacen los otros esquemas), presenta una tasa de desaciertos comparable al esquema 4WSA, como ya se discuti´o. Esto permite concluir que SWSA-MT con reubicaci´on gana m´as por el hecho de reducir la interferencia entre hilos, que por favorecer la cooperaci´on entre los mismos (lo cual ya se observ´o en la secci´on 4.11.2 en la clasificaci´on de los desaciertos seg´ un el modelo de las 4C).

4.11.4.

Tasa de Reubicaci´ on

Si, ante un desacierto en su memoria privada y en la memoria compartida, un hilo encuentra el dato en la memoria privada de otro hilo, entonces estamos en presencia de un acierto “largo”. En tal situaci´on, y utilizando la pol´ıtica de reubicaci´on descripta en la secci´on 4.6, el dato compartido se lleva al banco compartido. En la figura 4.18 se representa esta situaci´on, donde el hilo 1 busca el dato A, presente en la memoria privada del hilo 2. Si bien esta situaci´on es preferible con respecto a un desacierto convencional (que hubiese requerido un acceso al nivel inferior en la jerarqu´ıa de memoria), 4

Tambi´en puede hablarse de interferencia “constructiva”.

4.11. RESULTADOS DE LAS SIMULACIONES

FFT

LU

0.08

16

Tasa de Aciertos Compartidos en Datos de L1 (%)

2WSA 4WSA SWSA−MT (realloc) Tasa de Aciertos Compartidos en Datos de L1 (%)

84

0.07

0.06

0.05

0.04

0.03

0.02

0.01

2WSA 4WSA SWSA−MT (realloc)

14

12

10

8

6

4

2

0 8

16

32

Tamaño Caché (KB)

64

8

16

32

64

Tamaño Caché (KB)

Figura 4.16: Tasa de aciertos compartidos para los benchmarks FFT y LU.

presenta, de todos modos, una penalidad adicional. En el ejemplo dado, si el hilo 1 necesita acceder a la memoria privada del hilo 2, entonces este thread debe ser moment´aneamente bloqueado hasta que el dato A sea “reubicado” en la memoria compartida. La v´ıa privada de cada hilo es una secci´on cr´ıtica que solo puede ser accedida en forma secuencial por los hilos, a menos que se disponga de memorias multipuerto (escenario que no se analizar´a en este trabajo). Esta m´etrica solo aplica para el caso de las organizaciones en donde existe el concepto de memoria “privada”, como ser el esquema propuesto SWSAMT y, por esta raz´on, fue la u ´nica simulada. Si bien un acierto “largo” incurre en una penalidad mayor respecto a un acierto convencional, es necesario analizar con qu´e frecuencia se presenta esta situaci´on ya que, en la pr´actica, se busca optimizar el caso m´as frecuente [15] a costa de penalidades adicionales en los escenarios menos frecuentes. Como se observa en las figuras 4.19 y 4.20, la ocurrencia de aciertos largos es poco

4.11. RESULTADOS DE LAS SIMULACIONES

CHOLESKY

RADIX

7

9.68

Tasa de Aciertos Compartidos en Datos de L1 (%)

Tasa de Aciertos Compartidos en Datos de L1 (%)

2WSA 4WSA SWSA−MT (realloc) 6

5

4

3

2

1

0

2WSA 4WSA SWSA−MT (realloc)

9.66

9.64

9.62

9.6

9.58

9.56

9.54

9.52 8

16

32

64

8

Tamaño Caché (KB)

16

32

64

Tamaño Caché (KB)

OCEAN

WATER

3

26 2WSA 4WSA SWSA−MT (realloc)

2.8

2WSA 4WSA SWSA−MT (realloc)

24 Tasa de Aciertos Compartidos en Datos de L1 (%)

Tasa de Aciertos Compartidos en Datos de L1 (%)

85

2.6 2.4 2.2 2 1.8 1.6 1.4

22 20 18 16 14 12 10 8 6

1.2

4 8

16 32 Tamaño Caché (KB)

64

8

16 32 Tamaño Caché (KB)

64

Figura 4.17: Tasa de aciertos compartidos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER.

4.11. RESULTADOS DE LAS SIMULACIONES

BANCO 1

86

BANCO 2 Dato A

HILO 1 ¿Dato A?

A HILO 2

Figura 4.18: Acierto “largo”.

probable. Solamente para los benchmarks LU y WATER se ubica entre el 3.5 % y 4.5 %, OCEAN ronda el 1 %, y el resto alrededor del 0.1 %, considerando los peores casos. Dicho de otra forma, en la mayor´ıa de los casos, la organizaci´on propuesta SWSA-MT se comporta con la simpleza de una organizaci´on 2WSA (cada hilo accede a un conjunto formado por dos bloques de cach´e, uno privado y el otro compartido). El crecimiento en la tasa de reubicaci´on para mayores tama˜ nos de cach´e (como sucede con los benchmarks FFT, LU, CHOLESKY, RADIX y WATER) se debe a que, al aumentar el tama˜ no de la cach´e simulada, cada hilo puede mantener, por mayor tiempo, conjuntos m´as grandes de datos, y esto le da la posibilidad a otros hilos de encontrar all´ı bloques compartidos (que ser´an reubicados en el banco com´ un). M´as a´ un, las aplicaciones que alcanzan mayores niveles en tasa de reubicaci´on (como ser LU y WATER) son las que comparten mayor cantidad de datos entre hilos (en el extremo opuesto, si los hilos no compartiesen ning´ un dato, la tasa de reubicaci´on ser´ıa nula para cualquier tama˜ no de cach´e). Por otra parte, en el caso del benchmark OCEAN, se aprecia una disminuci´on de la tasa de reubicaci´on, a mayores tama˜ nos de cach´e (en particular, se observa una ca´ıda abrupta al pasar de 16-KB a 32-KB). Haciendo referencia a la tasa de aciertos compartidos para dicho benchmark, en la figura 4.17 de la secci´on 4.11.3, puede notarse un crecimiento abrupto de la los aciertos

4.12. ESQUEMAS PRIVADOS

87

FFT

LU

0.03

4

Tasa de Reubicación en Datos de L1 (%)

Tasa de Reubicación en Datos de L1 (%)

3.5 0.025

0.02

0.015

0.01

3

2.5

2

1.5

1

0.005

0.5 8

16

32

64

Tamaño Caché (KB)

8

16

32

64

Tamaño Caché (KB)

Figura 4.19: Tasa de reubicaci´ on para los benchmarks FFT y LU.

compartidos, tambi´en al pasar de 16-KB a 32-KB. Se concluye entonces que, para la aplicaci´on OCEAN, el esquema SWSA-MT con reubicaci´on es capaz de mantener a largo plazo los bloques que fueron reubicados en el banco com´ un (y que son compartidos entre dos o m´as hilos) y, por consiguiente, disminuye la necesidad de tener que volver a reubicarlos.

4.12.

Esquemas Privados

En esta secci´on se compara la organizaci´on propuesta SWSA-MT con reubicaci´on contra las organizaciones 2WSA y 4WSA, privadas por hilo de ejecuci´on, seg´ un se puede apreciar en la figura 4.21. En los esquemas privados simulados (2WSA y 4WSA), y ante un desacierto en su memoria privada, un hilo puede obtener el dato buscado desde las memorias privadas de los dem´as hilos. Por esta raz´on, y sumada al hecho de

4.12. ESQUEMAS PRIVADOS

88

CHOLESKY

RADIX

0.9

0.12

0.8 Tasa de Reubicación en Datos de L1 (%)

Tasa de Reubicación en Datos de L1 (%)

0.1 0.7

0.6

0.5

0.4

0.3

0.08

0.06

0.04

0.02 0.2

0.1

0 8

16

32

64

8

Tamaño Caché (KB)

1.1

4.5

0.9 0.8 0.7 0.6 0.5 0.4

32

64

WATER 5

Tasa de Reubicación en Datos de L1 (%)

Tasa de Reubicación en Datos de L1 (%)

OCEAN 1.2

1

16

Tamaño Caché (KB)

4 3.5 3 2.5 2 1.5 1

0.3

0.5 8

16 32 64 Tamaño Caché (KB)

8

16 32 64 Tamaño Caché (KB)

Figura 4.20: Tasa de reubicaci´ on para los benchmarks CHOLESKY, RADIX, OCEAN y WATER.

´ DE LA CACHE ´ 4.13. SUBEXPLOTACION

SWSA-MT BANCO 1

BANCO 2

2WSA BANCO 1

89

4WSA

BANCO 2

BANCO 1

HILO 1

HILO 3

HILO 2

HILO 4

BANCO 2

BANCO 3

BANCO 4

Figura 4.21: Organizaci´ on SWSA-MT y esquemas privados 2WSA y 4WSA.

que estos esquemas privados reducen a cero la interferencia destructiva cruzada, se los considera “ideales”. Por otra parte, estas organizaciones privadas son de costosa implementaci´on, debido a que requieren memorias multipuerto (con soporte para 4 hilos concurrentes, en los casos simulados). En los gr´aficos de tasas de desaciertos 4.22 y 4.23 se puede apreciar que la organizaci´on SWSA-MT tiene un comportamiento similar respecto de los esquemas privados 2WSA y 4WSA y, en algunos casos, presenta una tasa significativamente menor. Esto significa que SWSA-MT es capaz de minimizar los conflictos entre hilos de la misma forma en que lo har´ıan las organizaciones privadas 2WSA y 4WSA ideales, ratificando una vez m´as las observaciones realizadas en la secciones 4.11.2 y 4.11.3.

4.13.

Subexplotaci´ on de la Cach´ e

En los resultados dados previamente, siempre se han considerado escenarios con una cantidad de hilos en ejecuci´on igual al n´ umero de memorias privadas disponibles. Sin embargo, este podr´ıa no siempre ser el caso. Por ejemplo, en un ambiente de trabajo con uno, dos o tres hilos, la organizaci´on

´ DE LA CACHE ´ 4.13. SUBEXPLOTACION

90

FFT

LU

5.5

5.5 2WSA 4WSA SWSA−MT (realloc) Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

5

2WSA 4WSA SWSA−MT (realloc)

5

4.5

4

3.5

3

2.5

2

4.5 4 3.5 3 2.5 2 1.5 1

1.5

0.5 8

16

32

Tamaño Caché (KB)

64

8

16

32

64

Tamaño Caché (KB)

Figura 4.22: Tasa de desaciertos para los benchmarks FFT y LU.

SWSA-MT propuesta ser´ıa subexplotada, quedando porciones privadas en desuso. Para estudiar esta situaci´on, se simularon las mismas organizaciones de la secci´on 4.11, pero ejecutando los benchmarks SPLASH-2 con un u ´nico 5 hilo (ejecuci´on secuencial). Las tasas de desaciertos obtenidas de estas simulaciones se presentan en las figuras 4.24 y 4.25. Se observa que la tasa de desaciertos del esquema SWSA-MT es levemente superior respecto a las otras organizaciones simuladas, para todos los benchmarks. Estos resultados podr´ıan ser poco aceptables. Sin embargo, en la pr´actica nunca ocurrir´ıa una situaci´on como tal, ya que todo sistema operativo ejecuta simult´aneamente varios procesos (propios o del usuario), que desde el procesador se ver´ıan como flujos (hilos) independientes, ya que se est´a considerando multihilo expl´ıcito, seg´ un se explic´o en la secci´on 4.3. Adem´as, peor 5

Peor caso (i.e., cuando queda la mayor proporci´ on del esquema SWSA-MT en desuso).

´ DE LA CACHE ´ 4.13. SUBEXPLOTACION

91

CHOLESKY

RADIX

7

2 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc) 1.8 Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

6

5

4

3

2

1.6

1.4

1.2

1

0.8

1

0.6 8

16

32

64

8

Tamaño Caché (KB)

16

32

64

Tamaño Caché (KB)

OCEAN

WATER

18

3 2WSA 4WSA SWSA−MT (realloc)

17

2WSA 4WSA SWSA−MT (realloc) Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

2.5 16 15 14 13 12 11 10

2

1.5

1

0.5 9 8

0 8

16 32 Tamaño Caché (KB)

64

8

16 32 Tamaño Caché (KB)

64

Figura 4.23: Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER.

´ 4.14. ASPECTOS DE IMPLEMENTACION

FFT

LU

3.2

2.4 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

2.2 Tasa de Desaciertos en Datos de L1 (%)

3 Tasa de Desaciertos en Datos de L1 (%)

92

2.8

2.6

2.4

2.2

2

1.8

2 1.8 1.6 1.4 1.2 1 0.8

1.6

0.6 8

16

32

Tamaño Caché (KB)

64

8

16

32

64

Tamaño Caché (KB)

Figura 4.24: Tasa de desaciertos para los benchmarks FFT y LU de un u ´nico hilo.

a´ un, en tal situaci´on el procesador estar´ıa desaprovechando su capacidad de explotar al m´aximo el uso de los recursos, si se tiene en cuenta que el nivel de ILP en las aplicaciones suele ser muy pobre, como ya se discuti´o en la secci´on 4.2; es decir, en ese caso ser´ıa una cuesti´on “menor” la subexplotaci´on de la cach´e.

4.14.

Aspectos de Implementaci´ on

Para concluir el estudio de la organizaci´on SWSA-MT, se presenta en esta secci´on un an´alisis elemental sobre las posibilidades de implementaci´on pr´actica de dicho esquema, comparado con la complejidad de las organizaciones 2WSA y 4WSA. Para este an´alisis se considera un procesador con cuatro hilos de ejecuci´on y, adem´as, que las cuestiones de acceso concurrente a los bloques son administradas por la memoria cach´e, como ocurre en la

´ 4.14. ASPECTOS DE IMPLEMENTACION

93

CHOLESKY

RADIX

6.5

1.3 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

1.2

5.5

Tasa de Desaciertos en Datos de L1 (%)

Tasa de Desaciertos en Datos de L1 (%)

6

5 4.5 4 3.5 3 2.5

1.1 1 0.9 0.8 0.7 0.6 0.5

2 1.5

0.4 8

16

32

64

8

Tamaño Caché (KB)

OCEAN

32

64

WATER

15

1.8 2WSA 4WSA SWSA−MT (realloc)

2WSA 4WSA SWSA−MT (realloc)

1.6 Tasa de Desaciertos en Datos de L1 (%)

14 Tasa de Desaciertos en Datos de L1 (%)

16

Tamaño Caché (KB)

13

12

11

10

9

8

1.4 1.2 1 0.8 0.6 0.4 0.2

7

0 8

16 32 Tamaño Caché (KB)

64

8

16 32 Tamaño Caché (KB)

64

Figura 4.25: Tasa de desaciertos para los benchmarks CHOLESKY, RADIX, OCEAN y WATER de un u ´nico hilo.

´ 4.14. ASPECTOS DE IMPLEMENTACION

94

actualidad en los procesadores multihilo. La organizaci´on de dos v´ıas asociativa por conjuntos, cuyo diagrama en bloques se muestra en la figura 4.26, es la m´as simple6 . Los dos bancos que la componen deben ser multipuerto, en este caso para soportar el acceso concurrente de cuatro hilos. Cada banco est´a compuesto por B = T /2 bloques, siendo T la cantidad total de bloques. Para comparar los r´otulos (tags), cada hilo necesita dos comparadores (uno para cada banco), dando un total de ocho comparadores. Para seleccionar el dato desde el banco correspondiente, en caso de acierto, cada hilo cuenta con un multiplexor “2 a 1”, como se aprecia en el diagrama. Adem´as, la implementaci´on de la pol´ıtica LRU de reemplazo es trivial: un bit por conjunto, que se establece en 1 cuando se accede a uno de los bloques, y en 0 cuando se accede al otro bloque. En la figura 4.27 se muestra el diagrama en bloques del esquema 4WSA que, a diferencia del 2WSA, presenta una mayor complejidad en su construcci´on. En primer lugar, se duplica la cantidad de bancos multipuerto, tambi´en con soporte para cuatro hilos. Para comparar los r´otulos, cada hilo necesita cuatro comparadores, dando un total de diecis´eis comparadores. Como ocurre en la organizaci´on 2WSA, es necesario contar con un multiplexor por hilo pero, en este caso, de cuatro entradas (“4 a 1”) para seleccionar uno de entre cuatro bancos. Este no es un dato menor: la velocidad con la que puede seleccionarse una de las entradas disminuye con el n´ umero de entradas. La pol´ıtica de reemplazo LRU es de dificultosa implementaci´on, ya que a medida que crece la cantidad de bloques a contabilizar en el conjunto, se hace muy costoso administrar esta pol´ıtica y, en la pr´actica, con frecuencia solamente se la aproxima [15]. Finalmente, el diagrama en bloques de la organizaci´on SWSA-MT se presenta en la figura 4.28. Como puede observarse, se agregan bits adicionales de r´otulo por cada bloque en el banco compartido; estos bits son utilizados por un hilo x para detectar la presencia del dato buscado en la porci´on privada de otro hilo y, sin necesidad de acceder a la secci´on de r´otulos de y. A diferencia 6

De las estudiadas; no menospreciar la simpleza del esquema DM.

´ 4.14. ASPECTOS DE IMPLEMENTACION

95

Referencia Hilo 1 Rótulo

Índice

Despl. Referencia Hilo 2 Rótulo

Índice

Despl. Referencia Hilo 3 Rótulo

Índice

Despl. Referencia Hilo 4 Rótulo

Rótulo

=?

Datos

Rótulo

Índice

Despl.

Datos

=?

Multiplexor 2:1 Datos

Figura 4.26: Diagrama en bloques del esquema 2WSA.

de los esquemas 2WSA y 4WSA, la organizaci´on propuesta solo requiere de un banco multipuerto (el compartido) con soporte para cuatro hilos; las memorias privadas, en cambio, son monopuerto, ya que solo las accede el hilo “propietario”. Para comparar los r´otulos, cada hilo necesita seis comparadores (dos para su conjunto, y cuatro adicionales para “consultar” las memorias ajenas), dando un total de veinticuatro comparadores. Sin embargo, a diferencia de la organizaci´on 4WSA, solo son necesarios cuatro multiplexores de dos entradas, para seleccionar el dato desde la porci´on privada del hilo o la memoria compartida, como se puede apreciar en la figura 4.28. Adicionalmente, el esquema propuesto requiere de hardware para reubicar un dato desde una memoria privada hacia el banco compartido. Sin embargo, este mecanis-

´ 4.14. ASPECTOS DE IMPLEMENTACION

96

Referencia Hilo 1 Rótulo

Índice

Despl. Referencia Hilo 2 Rótulo

Índice

Despl. Referencia Hilo 3 Rótulo

Índice

Despl. Referencia Hilo 4 Rótulo

Rótulo

=?

Datos

Rótulo

=?

Datos

Índice

Despl.

Rótulo

Datos

=?

Rótulo

Datos

=?

Multiplexor 4:1 Datos

Figura 4.27: Diagrama en bloques del esquema 4WSA.

mo solo es utilizado espor´adicamente, como se analiz´o en la secci´on 4.11.4, con lo cual no agrega una penalidad considerable. Respecto a la pol´ıtica de reemplazo, en el esquema SWSA-MT puede implementarse LRU de una forma casi tan simple como la organizaci´on 2WSA: se agregan k bits junto con cada bloque en el banco compartido (siendo k la cantidad de bancos privados); cada uno de estos bits permite comparar el bloque compartido contra los k bloques privados correspondientes (para el ejemplo dado, k = 4). En este punto, es importante destacar la escalabilidad ofrecida por el esquema SWSA-MT en relaci´on a la pol´ıtica de reemplazo LRU: la cantidad de bits que deben compararse, para decidir qu´e bloque ser´a victimizado, es lineal con la cantidad k de memorias privadas; esto es mucho m´as aceptable respecto al hecho de que en un esquema kWSA la pol´ıtica de reemplazo LRU es

4.15. CONCLUSIONES

97

de dificultosa implementaci´on cuando k crece. Como una ventaja adicional, las memorias privadas son de menor tama˜ no en relaci´on a los bancos de los esquemas 2WSA y 4WSA y, por consiguiente, pueden ser accedidas a mayor velocidad. Por ejemplo, ante un acierto en la porci´on privada, podr´ıa adelantarse el trabajo relacionado a establecer el multiplexor, como se aprecia en la siguiente figura. TIEMPO

TIEMPO DE ACIERTO EN EL BANCO COMPARTIDO TIEMPO DE ACIERTO EN EL BANCO PRIVADO

ESTABLECIMIENTO DEL MULTIPLEXOR

M´as a´ un, si se detecta un acierto en la memoria privada del hilo, puede detenerse la b´ usqueda en el banco compartido, para generar un ahorro en el consumo de energ´ıa [18].

4.15.

Conclusiones

En este cap´ıtulo se present´o la organizaci´on de memoria cach´e SWSA-MT para procesadores multihilo propuesta, y la evaluaci´on de su desempe˜ no. Los resultados obtenidos, a partir de la ejecuci´on de los benchmarks SPLASH-2, muestran un desempe˜ no comparable al de la organizaci´on 4WSA, pero con una complejidad de implementaci´on similar a la de un esquema 2WSA. Se observa que la cach´e propuesta presenta una menor tasa de desaciertos por conflicto cruzado, en relaci´on a las otros esquemas estudiados. Esta es la virtud m´as sobresaliente de la organizaci´on SWSA-MT ya que, al disponer de memorias privadas para los hilos, se minimiza la interferencia “destructiva” entre los mismos. Esto hace de SWSA-MT una excelente opci´on para ser implementada en procesadores multihilo, como los Intel Pentium 4 HyperThreading, o la nueva arquitectura SUN UltraSPARC T1 con tecnolog´ıa CoolThreads.

4.15. CONCLUSIONES

98

Referencia Hilo 1 Rótulo

Índice

Despl. Referencia Hilo 2 Rótulo

Índice

Despl. Referencia Hilo 3 Rótulo

Índice

Despl. Referencia Hilo 4 Rótulo

Rótulo

=?

Datos

Rótulo Rótulo Rótulo Rótulo Rótulo

=?

=?

=?

=?

Índice

Despl.

Datos

=?

Multiplexor 2:1 Datos

Hardware de Reubicación

Figura 4.28: Diagrama en bloques del esquema SWSA-MT.

Adem´as, se propuso un nuevo modelo para la clasificaci´on de desaciertos para ambientes multihilo, denominado “modelo de las 4C” (y que es una extensi´on del popular “modelo de las 3C”). Este modelo, que se utiliz´o para la

4.15. CONCLUSIONES

99

clasificaci´on de desaciertos en el estudio de la organizaci´on cach´e presentada, es capaz de discriminar los desaciertos de conflicto como “cerrados” (un hilo consigo mismo) y “cruzados” (entre hilos), y contempla el hecho de que los hilos podr´ıan acceder parcialmente al total de la cach´e.

Cap´ıtulo 5 Conclusiones En este trabajo de tesis se present´o una nueva organizaci´on de memoria cach´e, que ha sido llamada SWSA-MT (Shared Way Set Associative - Multithreading), adecuada para procesadores con m´ ultiples hilos de ejecuci´on. Para el estudio del esquema propuesto, se construy´o un ambiente para recolecci´on de trazas de referencias a memoria de aplicaciones multihilo, como tambi´en un simulador que, alimentado por dichas trazas, permita evaluar el desempe˜ no de la cach´e estudiada. En el cap´ıtulo 2 se present´o una herramienta, p´ ublica y de c´odigo abierto, que permite la captura de trazas de referencias a memoria de programas con m´ ultiples hilos de ejecuci´on. La misma fue implementada como un m´odulo para el sistema Valgrind, el cual permite realizar tareas de debugging y profiling sobre programas ejecutables, para ambientes Linux-x86. La herramienta construida se utiliz´o para recolectar las trazas de los programas que conforman los benchmarks SPLASH-2. En el cap´ıtulo 3 se describi´o una herramienta de simulaci´on construida para este trabajo, que ha sido llamada SimiOO. La misma fue desarrollada en base al paradigma de orientaci´on a objetos, en lenguaje Java, y sobre una arquitectura de plug-ins que le permite ser extendida con nuevas funcionalidades. La herramienta SimiOO y el plug-in de simulaci´on permiten la evaluaci´on de organizaciones de memoria cach´e a partir de las trazas reco100

101

lectadas anteriormente. Finalmente, en el cap´ıtulo 4 se present´o la organizaci´on de memoria cach´e SWSA-MT para procesadores multihilo propuesta, y la evaluaci´on de su desempe˜ no. Adem´as, se propuso un nuevo modelo para la clasificaci´on de desaciertos para ambientes multihilo, denominado “modelo de las 4C” (y que es una extensi´on del popular “modelo de las 3C”). Este modelo se utiliz´o para la clasificaci´on de desaciertos en el estudio de la organizaci´on cach´e presentada. Los resultados obtenidos del estudio del esquema SWSA-MT, a partir de la ejecuci´on de los benchmarks SPLASH-2, muestran un desempe˜ no comparable al de la organizaci´on 4WSA, pero con una complejidad de implementaci´on similar a la de un esquema 2WSA. En primer lugar, al analizar la tasa de desaciertos (una de las figuras de m´erito en el estudio de organizaciones de memoria cach´e), se observa que el dise˜ no SWSA-MT se comporta significativamente mejor respecto al 2WSA y similar al 4WSA, para todos los benchmarks, 4 hilos de ejecuci´on, y tama˜ nos 8, 16, 32 y 64-KB. Adem´as, al clasificar estos desaciertos seg´ un el “modelo de las 4C” se observa que la cach´e propuesta presenta una menor tasa de desaciertos por conflicto cruzado, en relaci´on a las otros esquemas estudiados. Esta es la virtud m´as sobresaliente de la organizaci´on SWSAMT ya que, al disponer de memorias privadas para los hilos, se minimiza la interferencia “destructiva” entre los mismos. En segundo lugar, si bien el dise˜ no propuesto incorpora un mecanismo de reubicaci´on (no presente en las organizaciones 2WSA y 4WSA), puede verse a partir de las simulaciones que esta situaci´on se trata del caso menos frecuente (entre el 3.5 % y 4.5 % para los benchmarks LU y WATER, 1 % para OCEAN, y alrededor del 0.1 % para el resto, considerando los peores casos). En tercer lugar, y a partir del an´alisis de los aciertos compartidos, se observa que el esquema SWSA-MT (con reubicaci´on) muestra menor grado de aciertos compartidos en relaci´on a las organizaciones 2WSA y 4WSA, debido a que la reubicaci´on implica el desalojo de otros bloques que, por

102

su parte, tambi´en podr´ıan ser compartidos entre hilos. A pesar de que la organizaci´on SWSA-MT no favorece la cooperaci´on entre hilos, presenta una tasa de desaciertos comparable al esquema 4WSA, como ya se discuti´o. Esto permite concluir que SWSA-MT con reubicaci´on gana m´as por el hecho de reducir la interferencia entre hilos, que por favorecer la cooperaci´on entre los mismos. Por u ´ltimo, se analizaron los aspectos de implementaci´on del esquema SWSA-MT con reubicaci´on. Interesa comparar los detalles de implementaci´on de los dise˜ nos SWSA-MT y 4WSA, dado que ambos presentan un desempe˜ no similar (y superior respecto a 2WSA), lo que los convierte en competidores directos: SWSA-MT solo requiere de un banco multipuerto (el compartido) con soporte para cuatro hilos, con respecto a los cuatro bancos multipuerto utilizados en el esquema 4WSA. Esto conlleva un menor costo de fabricaci´on de la cach´e presentada. SWSA-MT utiliza cuatro multiplexores de dos entradas, con respecto a los cuatro multiplexores de cuatro entradas utilizados por 4WSA. Esto conlleva un menor tiempo de acceso en el caso de la memoria propuesta. SWSA-MT puede implementar la pol´ıtica de reemplazo LRU de una forma casi tan simple como la organizaci´on 2WSA, mientras que 4WSA debe aproximarla. Las memorias privadas en el esquema SWSA-MT son de menor tama˜ no respecto a los bancos de 4WSA, lo que implica un menor tiempo de acceso para determinar, en forma temprana, si puede cancelarse la b´ usqueda en el banco compartido (cuando se detecta un acierto en el banco privado) gener´andose, adem´as, un ahorro en el consumo de energ´ıa. Como contrapartida, el esquema SWSA-MT agrega bits adicionales de r´otulo por cada bloque en el banco compartido, y requiere de ocho comparadores

5.1. TRABAJO FUTURO

103

adicionales respecto a 4WSA. Sin embargo, estos requisitos “extras” no son de un costo significativo en la fabricaci´on de la memoria cach´e, ni agregan penalidades en el tiempo de acceso. Tambi´en, SWSA-MT requiere de un hardware adicional para reubicaci´on que si bien podr´ıa agregar penalidades adicionales, su uso es muy poco frecuente para los benchmarks estudiados y no produce un impacto significativo en el desempe˜ no. Como una ventaja adicional de la organizaci´on SWSA-MT, la pol´ıtica de reemplazo LRU es escalable con el incremento de memorias privadas (es decir, con el incremento de hilos de ejecuci´on), lo cual no sucede en las memorias cach´e asociativas por conjuntos kWSA. Esta es una caracter´ıstica importante del esquema propuesto, teniendo en cuenta que en la actualidad existe una tendencia a incrementar la cantidad de hilos de ejecuci´on en procesadores multihilo.

5.1.

Trabajo Futuro

Si durante la ejecuci´on de un workload, uno o m´as hilos de ejecuci´on se bloquearan (por ejemplo, por actividad de E/S, o esperando la sincronizaci´on con otros hilos, etc.), se estar´ıa realizando un uso parcial de la cach´e propuesta dado que, como se discuti´o, cada hilo accede a una porci´on acotada, conformada por su memoria privada y el banco compartido. Por lo tanto, es de inter´es implementar, a futuro, una pol´ıtica din´amica de redistribuci´ on de la cach´e entre los hilos activos, tal que pueda maximizarse la explotaci´on de la totalidad de la memoria cach´e disponible. Se espera que, de esta manera, disminuya el n´ umero de desaciertos por capacidad y conflicto cerrado, ya que cada hilo dispondr´ıa de mayor espacio para almacenar sus datos. Para eliminar definitivamente el hardware de reubicaci´on, descripto anteriormente, deber´ıa implementarse una heur´ıstica que determine, para una referencia a memoria, si se trata de un acceso compartido. De esta forma, todo dato que se considere “compartido” seg´ un la heur´ıstica, se ubicar´ıa en el banco compartido, y un hilo nunca tendr´ıa la necesidad de acceder a las

5.1. TRABAJO FUTURO

104

memorias privadas de los dem´as. Incluso, como una ganancia adicional, el uso de esta heur´ıstica eliminar´ıa la necesidad de los comparadores y bits adicionales en los bloques del banco compartido. A futuro, tambi´en se estudiar´a el comportamiento y adaptaci´on del esquema SWSA-MT en procesadores con m´ ultiples n´ ucleos (tecnolog´ıa multicore). En este sentido, la organizaci´on propuesta podr´ıa ser utilizada como cach´e de nivel 2 (L2) y asignar cada bloque privado a cada core, adem´as del banco compartido entre todos los n´ ucleos. Por u ´ltimo, si bien en este trabajo se utiliz´o la t´ecnica de simulaci´on manejada por trazas, a futuro se estudiar´a la organizaci´on SWSA-MT mediante la t´ecnica de simulaci´on manejada por ejecuci´on. Esto permitir´a tener una visi´on m´as real del comportamiento de la cach´e presentada, en un ambiente conformado no solo por el benchmark multihilo, sino tambi´en por el sistema operativo, bibliotecas din´amicas, otros programas de usuario, etc.

Ap´ endice A Tracegrind: Detalles y Modo de Uso A.1.

Detalles de Implementaci´ on

Al igual que el m´odulo principal Coregrind de Valgrind, la herramienta Tracegrind est´a programada en lenguaje C (el c´odigo fuente se adjunta en el ap´endice B), y su construcci´on se hizo a partir de un “esqueleto”, el m´odulo Nulgrind1 . La versi´on de Valgrind utilizada fue la 2.4.1. En Valgrind, todo m´odulo debe implementar, por lo menos, el siguiente conjunto de rutinas (que constituyen la interfaz con Coregrind): pre clo init() En esta funci´on se ejecutan todas las acciones de inicializaci´on del m´odulo. post clo init() Si el m´odulo necesita realizar alg´ un tipo de procesamiento sobre las opciones en l´ınea de ´ordenes (si recibiera alguna), deber´a hacerlo en esta funci´on. Las siglas “clo” significan command line options. 1

Nulgrind, que es provisto junto con Valgrind, no implementa ninguna funcionalidad en particular, y es utilizado como punto de partida para la construcci´ on de nuevos m´odulos.

105

´ A.1. DETALLES DE IMPLEMENTACION

106

instrument() Esta es la rutina m´as importante, ya que le da la oportunidad al m´odulo de instrumentar las instrucciones recibidas desde Coregrind. Como resultado de la ejecuci´on de esta funci´on, se le retorna a Coregrind el bloque b´asico instrumentado, para ser ejecutado. fini() Finalmente, en esta funci´on deben ejecutarse las acciones de finalizaci´on del m´odulo, y la presentaci´on de resultados. En Valgrind, la instrumentaci´on de c´odigo puede realizarse de dos maneras: insertando, en el c´odigo recibido desde Coregrind, llamadas a funciones escritas en lenguaje C, o agregando nuevas instrucciones al conjunto de instrucciones UCode. En esta tesis se opt´o por la primera, por ser m´as simple y flexible. Esta tarea de instrumentaci´on se lleva a cabo en la funci´on instrument() que recibe, como par´ametro, una referencia al bloque b´asico2 a instrumentar. Posteriormente, se procesan secuencialmente las instrucciones que conforman el bloque b´asico, analizando el opcode de cada una de ellas. De esta manera, es posible distinguir entre lecturas y escrituras, e insertar la instrumentaci´on adecuada, que consiste en agregar una llamada a la funci´on log reference() luego de cada instrucci´on de lectura o escritura. La rutina log reference(), cuya llamada es insertada en tiempo de instrumentaci´on, se ejecutar´a cuando Coregrind decida ejecutar el bloque b´asico. La tarea de esta funci´on es simple: escribir, en memoria externa, la informaci´on recibida por par´ametro (id del hilo, direcci´on de memoria y tipo de acceso). En particular, esta informaci´on debe almacenarse usando un algoritmo de compresi´on, debido a que las trazas pueden alcanzar tama˜ nos muy grandes, del orden del gigabyte. Para tal fin, se utiliz´o la biblioteca Zlib (p´ ublica y de c´odigo abierto), que implementa el algoritmo LZ77 de Lempel-Ziv [44]. Por u ´ltimo, y como sucede con Valgrind, el m´odulo Tracegrind est´a regulado por una licencia GNU GPL (GNU General Public License), para software 2

Un bloque b´ asico es una secuencia de instrucciones, sin saltos.

A.2. MODO DE USO

107

libre.

A.2.

Modo de Uso

En primer lugar, se explicar´a c´omo instalar la herramienta Valgrind junto con el m´odulo Tracegrind, en un ambiente Linux-x86 con kernel 2.4.x o´ 2.6.x: 1. Se requiere el c´odigo fuente de la versi´on 2.4.1 de Valgrind que, al momento de la redacci´on de esta tesis, pod´ıa obtenerse desde un repositorio SVN mediante el siguiente comando: svn co svn://anonsvn.kde.org/home/kde/trunk/valgrind/ 2. La ejecuci´on de la sentencia anterior, en l´ınea de ´ordenes, realiza el check out de la versi´on 2.4.1 de Valgrind, y crea un a´rbol de directorios en el sistema de archivos local, a partir del directorio base valgrind/. All´ı, deber´a editarse el archivo Makefile.am agregando la palabra tracegrind a la definici´on de TOOLS, como se muestra a continuaci´on: TOOLS =

memcheck \ addrcheck \ cachegrind \ corecheck \ massif \ lackey \ none \ tracegrind

3. Posteriormente, debe editarse el archivo valgrind/configure.in para agregar las siguientes entradas a la definici´on de AC OUTPUT:

A.2. MODO DE USO

108

tracegrind/Makefile tracegrind/docs/Makefile tracegrind/input/Makefile tracegrind/tg_dec/Makefile 4. Obtener el c´odigo fuente de Tracegring, desde http://web.fi. uba.ar/~ajvega/download/tracegrind/tracegrind.tar.bz2. Luego, descomprimir el archivo tracegrind.tar.bz2 y copiar su contenido (carpeta tracegrind/ y subcarpetas) en el directorio valgrind/. 5. Para configurar el ambiente, ejecutar: ./autogen.sh ./configure --prefix=‘pwd‘/inst 6. Instalar Valgrind junto con el m´odulo Tracegrind, ejecutando el comando make install. 7. Finalmente, para verificar la correcta instalaci´on, se puede ejecutar: inst/bin/valgrind --tool=tracegrind date Si la instalaci´on fue exitosa, deber´ıa generar dos archivos de traza, con las referencias a memoria (de datos e instrucciones) efectuadas por el comando date. Dichas trazas estar´an almacenadas en el subdirectorio tracegrind/output/. Una vez que han sido instaladas las herramientas Valgrind y Tracegrind, es posible capturar las trazas de referencias a memoria de cualquier binario ejecutable Linux ELF. El modo de uso es el siguiente: inst/bin/valgrind --tool=tracegrind --single-step=yes

A.2. MODO DE USO

109

Mediante la sentencia anterior se ejecuta la herramienta Valgrind utilizando el m´odulo Tracegrind (--tool=tracegrind), siendo el programa de usuario a “tracear”. La opci´on --single-step=yes indica que Coregrind trate a cada instrucci´on como si fuese un bloque b´asico. Esto, combinado con la redefinici´on de la etiqueta VG SCHEDULING QUANTUM en el archivo valgrind/coregrind/core.h a un valor peque˜ no (por ejemplo, 1), permiten que los cambios de contexto en un programa multihilo se realicen con una muy fina granularidad, dando la sensaci´on de ejecuci´on simult´anea en un esquema multihilo simult´aneo. Cuando finaliza la recolecci´on, las trazas quedan almacenadas en el directorio tracegrind/output/, con nombres data trace.zip e instr trace.zip para datos e instrucciones, respectivamente. Por u ´ltimo, en el directorio tracegrind/tg dec/ podr´a encontrarse el utilitario tg dec que permite descomprimir las trazas y almacenarlas como archivos de texto plano.

Ap´ endice B C´ odigo Fuente del M´ odulo Tracegrind B.1.

C´ odigo Fuente

A continuaci´on se adjunta el c´odigo fuente del m´odulo Tracegrind, construido para la recolecci´on de trazas de referencias a memoria, e integrado a Valgrind:

/*--------------------------------------------------------------------*/ /*--- Tracegrind: The tool for collecting instruction and data ---*/ /*--- memory references. ---*/ /*--tg_main.c ---*/ /*--------------------------------------------------------------------*/ /* This file is part of Tracegrind, a Valgrind tool for collecting instruction and data memory references. Copyright (C) 2005 Augusto J. Vega [email protected] This program is free software; you can redistribute it and/or

110

´ B.1. CODIGO FUENTE

111

modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA. The GNU General Public License is contained in the file COPYING. */ #include "tool.h" #include #include #include #include



#include "tg_comp.c"

/*------------------------------------------------------------*/ /*--- Constants ---*/ /*------------------------------------------------------------*/ #define MIN_LINE_SIZE #define MAX_REF_SIZE

16 256

#define INSTR_TRACE_FILE #define DATA_TRACE_FILE

"tracegrind/output/instr_trace.zip" "tracegrind/output/data_trace.zip"

// Address format

´ B.1. CODIGO FUENTE

#define #define #define #define

HEX_REDUCED HEX_ALL DEC_REDUCED DEC_ALL

112

"%d "%d "%d "%d

0x%x\n" 0x%x [%s]\n" %u\n" %u [%s]\n"

/*------------------------------------------------------------*/ /*--- Definitions ---*/ /*------------------------------------------------------------*/ #define NONE #define READ #define WRITE

0 1 2

// Structure with memory reference info. typedef struct { Addr instr_addr; /* instruction address */ Addr data_addr; /* data address */ Int type; /* READ or WRITE */ ThreadId tid; /* running thread id */ } MemRef;

typedef struct { ULong instr_refs; ULong data_rd_refs; ULong data_wr_refs; ULong thread_switches; struct timeval begin_time, end_time, diff_time; } ProfilingInfo;

´ B.1. CODIGO FUENTE

#define HEX #define DEC

1 2

#define ALL #define REDUCED

1 2

typedef struct { Int format; Int info; Bool profiling;

113

/* HEX or DEC */ /* ALL or REDUCED */ /* True or False */

} TracingOptions;

/*------------------------------------------------------------*/ /*--- Global variables ---*/ /*------------------------------------------------------------*/ #define DEFAULT_OPTIONS { HEX, ALL, False } static TracingOptions tracing_options = DEFAULT_OPTIONS; // For profiling purposes static ProfilingInfo prof_info = {0,0,0,0};

// Write the reference in the trace file. void log_reference(MemRef *mem_ref) { Char ref[MAX_REF_SIZE]; //Long addr_offset; /* 64 bits signed long long */ #define LOG(ref) #define REF_TYPE(type)

( INVALID_TEMPREG != ref ) ( type==READ ? "rd" : (type==WRITE ? "wr" : "") )

sk_assert( mem_ref != NULL );

´ B.1. CODIGO FUENTE

114

sk_assert( LOG(mem_ref->instr_addr) || LOG(mem_ref->data_addr) ); if ( LOG(mem_ref->instr_addr) ) { /* Write the instruction reference */ VG_(sprintf)(ref, trace_files[INSTR_REF].format, mem_ref->tid, \ mem_ref->instr_addr, REF_TYPE(mem_ref->type) ); write_deflated_ref(ref, strlen(ref), INSTR_REF); trace_files[INSTR_REF].last_ref = (Addr)mem_ref->instr_addr; } if ( LOG(mem_ref->data_addr) ) { /* Write the data reference */ VG_(sprintf)(ref, trace_files[DATA_REF].format, mem_ref->tid, \ mem_ref->data_addr, REF_TYPE(mem_ref->type) ); write_deflated_ref(ref, strlen(ref), DATA_REF); trace_files[DATA_REF].last_ref = (Addr)mem_ref->data_addr; } #undef LOG }

/*--------------------------------------------------------------------*/ /*--- Command line processing ---*/ /*--------------------------------------------------------------------*/ Bool SK_(process_cmd_line_option)(Char* arg) { // Command line options: // --format=[hex|dec] Format in which addresses are written, hexa or // decimal (default: hex) // --info=[all,reduced] How much info is added to each address // (default: all) // --prof Collect profiling and debugging info from the // process, such as the execution time. if

(VG_CLO_STREQN(9, arg, "--format="))

´ B.1. CODIGO FUENTE

{ if

(VG_CLO_STREQ(arg+9, "hex")) tracing_options.format = HEX; else if (VG_CLO_STREQ(arg+9, "dec")) tracing_options.format = DEC; else return False; } else if (VG_CLO_STREQN(7, arg, "--info=")) { if (VG_CLO_STREQ(arg+7, "all")) tracing_options.info = ALL; else if (VG_CLO_STREQ(arg+7, "reduced")) tracing_options.info = REDUCED; else return False; } else if (VG_CLO_STREQN(7, arg, "--prof=")) { if (VG_CLO_STREQ(arg+7, "yes")) tracing_options.profiling = True; else if (VG_CLO_STREQ(arg+7, "no")) tracing_options.profiling = False; else return False; } else return False; return True; } void SK_(print_usage)(void) { VG_(printf)( " --format=[hex|dec] Format in which addresses are written,\n" " hexa or decimal (default: hex).\n" " --info=[all,reduced] How much info is added to each address\n"

115

´ B.1. CODIGO FUENTE

" " " "

--prof

116

(default: all).\n" Collect profiling and debugging info from\n" the process, such as the execution time\n" (default: none).\n"

); } void SK_(print_debug_usage)(void) { VG_(printf)( " (none)\n" ); } void SK_(thread_run)(ThreadId tid) { prof_info.thread_switches ++; }

/*--------------------------------------------------------------------*/ /*--- Setup ---*/ /*--------------------------------------------------------------------*/ void SK_(pre_clo_init)(void) { VG_(details_name) ("Tracegrind"); VG_(details_version) (NULL); VG_(details_description) ("a memory references collector."); VG_(details_copyright_author)( "Copyright (C) 2005, and GNU GPL’d, by Augusto Vega."); VG_(details_bug_reports_to) (VG_BUGS_TO); VG_(needs_command_line_options)(); /* Register a handler */ VG_(init_thread_run)( SK_(thread_run) );

´ B.1. CODIGO FUENTE

117

/* Trace files creation */ trace_files[INSTR_REF].stream = creat(INSTR_TRACE_FILE, 0777); sk_assert( trace_files[INSTR_REF].stream >= 0 ); trace_files[DATA_REF].stream = creat(DATA_TRACE_FILE, 0777); sk_assert( trace_files[DATA_REF].stream >= 0 ); /* Initialization */ trace_files[INSTR_REF].first_time = 1; trace_files[INSTR_REF].last_ref = 0; trace_files[INSTR_REF].next = trace_files[INSTR_REF].defl_buffer; trace_files[DATA_REF].first_time = 1; trace_files[DATA_REF].last_ref = 0; trace_files[DATA_REF].next = trace_files[DATA_REF].defl_buffer; }

void SK_(post_clo_init)(void) { sk_assert((tracing_options.format==HEX) || (tracing_options.format==DEC) ); sk_assert((tracing_options.info==ALL) || (tracing_options.info==REDUCED)); if {

( tracing_options.format==HEX

&&

tracing_options.info==REDUCED )

VG_(strcpy)(trace_files[INSTR_REF].format, HEX_REDUCED); VG_(strcpy)(trace_files[DATA_REF].format, HEX_REDUCED); VG_(message)(Vg_UserMsg, "Address format: hex and reduced"); } else if ( tracing_options.format==HEX && tracing_options.info==ALL ) { VG_(strcpy)(trace_files[INSTR_REF].format, HEX_ALL); VG_(strcpy)(trace_files[DATA_REF].format, HEX_ALL); VG_(message)(Vg_UserMsg, "Address format: hex and all"); } else if ( tracing_options.format==DEC && tracing_options.info==REDUCED ) { VG_(strcpy)(trace_files[INSTR_REF].format, DEC_REDUCED);

´ B.1. CODIGO FUENTE

118

VG_(strcpy)(trace_files[DATA_REF].format, DEC_REDUCED); VG_(message)(Vg_UserMsg, "Address format: dec and reduced"); } else if ( tracing_options.format==DEC && tracing_options.info==ALL ) { VG_(strcpy)(trace_files[INSTR_REF].format, DEC_ALL); VG_(strcpy)(trace_files[DATA_REF].format, DEC_ALL); VG_(message)(Vg_UserMsg, "Address format: dec and all"); } gettimeofday(&prof_info.begin_time, NULL); }

/*------------------------------------------------------------*/ /*--- References collection functions ---*/ /*------------------------------------------------------------*/ static REGPARM(1) void collect_1I_0D_mem_reference(Addr instr_addr) { MemRef mem_ref; mem_ref.instr_addr mem_ref.data_addr mem_ref.type mem_ref.tid

= = = =

instr_addr; INVALID_TEMPREG; NONE; VG_(get_running_tid)();

prof_info.instr_refs ++; log_reference(&mem_ref); }

static REGPARM(2) void collect_1I_1Dr_mem_reference(Addr instr_addr, Addr data_addr) { MemRef mem_ref;

´ B.1. CODIGO FUENTE

mem_ref.instr_addr mem_ref.data_addr mem_ref.type mem_ref.tid

= = = =

instr_addr; data_addr; READ; VG_(get_running_tid)();

prof_info.instr_refs prof_info.data_rd_refs

++; ++;

log_reference(&mem_ref); }

static REGPARM(2) void collect_1I_1Dw_mem_reference(Addr instr_addr, Addr data_addr) { MemRef mem_ref; mem_ref.instr_addr mem_ref.data_addr mem_ref.type mem_ref.tid

= = = =

instr_addr; data_addr; WRITE; VG_(get_running_tid)();

prof_info.instr_refs prof_info.data_wr_refs

++; ++;

log_reference(&mem_ref); }

static REGPARM(3) void collect_1I_2D_mem_reference(Addr instr_addr, Addr data_addr1, Addr data_addr2) { MemRef mem_ref; mem_ref.instr_addr mem_ref.data_addr

= instr_addr; = data_addr1;

119

´ B.1. CODIGO FUENTE

mem_ref.type mem_ref.tid

120

= READ; = VG_(get_running_tid)();

prof_info.instr_refs prof_info.data_rd_refs

++; ++;

log_reference(&mem_ref); mem_ref.instr_addr mem_ref.data_addr mem_ref.type

= INVALID_TEMPREG; = data_addr2; = WRITE;

prof_info.data_wr_refs

++;

log_reference(&mem_ref); }

static Bool is_valid_data_size(Int data_size) { return (4 == data_size || 2 == data_size || 1 == data_size || 8 == data_size || 10 == data_size || MIN_LINE_SIZE == data_size); }

/*------------------------------------------------------------*/ /*--- Instrumentation ---*/ /*------------------------------------------------------------*/ /* Instrumentation for collecting memory references. Adds to the code block the call to the C helper. Parameters: cb instr_addr instr_size data_size t_read

: : : : :

code block to be instrumented. instruction address. instruction size. data size (only for control purposes). data memory source address.

´ B.1. CODIGO FUENTE

t_read_addr : t_write : t_write_addr:

121

virtual register address, which holds the data memory source address. data memory destination address. virtual register address, which holds the data memory destination address.

*/ static void references_collection( UCodeBlock* cb, Addr instr_addr, ULong instr_size, ULong data_size, Int t_read, Int t_read_addr, Int t_write, Int t_write_addr) { Int t_instr_addr_addr; // Register where we put the instruction address Addr helper; Int argc; Int t_data_addr1 = INVALID_TEMPREG, t_data_addr2 = INVALID_TEMPREG;

sk_assert( instr_size >= MIN_INSTR_SIZE && instr_size <= MAX_INSTR_SIZE ); #define IS_(X) #define INV(qqt)

(INVALID_TEMPREG != t_##X##_addr) (INVALID_TEMPREG == (qqt))

// Work out what kind of x86 instruction it is if ( !IS_(read) && !IS_(write) ) { sk_assert( 0 == data_size ); sk_assert(INV(t_read) && INV(t_write)); helper = (Addr) & collect_1I_0D_mem_reference; argc = 1; } else if (IS_(read) && !IS_(write)) { sk_assert( is_valid_data_size(data_size) ); sk_assert(!INV(t_read) && INV(t_write)); helper = (Addr) & collect_1I_1Dr_mem_reference;

´ B.1. CODIGO FUENTE

argc = 2; t_data_addr1 = t_read_addr; } else if (!IS_(read) && IS_(write)) { sk_assert( is_valid_data_size(data_size) ); sk_assert(INV(t_read) && !INV(t_write)); helper = (Addr) & collect_1I_1Dw_mem_reference; argc = 2; t_data_addr1 = t_write_addr; } else { sk_assert(IS_(read) && IS_(write)); sk_assert( is_valid_data_size(data_size) ); sk_assert(!INV(t_read) && !INV(t_write)); if (t_read == t_write) { // Source and destination memory address are the same helper = (Addr) & collect_1I_1Dr_mem_reference; argc = 2; t_data_addr1 = t_read_addr; } else { helper = (Addr) & collect_1I_2D_mem_reference; argc = 3; t_data_addr1 = t_read_addr; t_data_addr2 = t_write_addr; } } #undef IS_ #undef INV // Setup 1st arg: instructon address address t_instr_addr_addr = newTemp(cb); uInstr2(cb, MOV, 4, Literal, 0, TempReg, t_instr_addr_addr);

122

´ B.1. CODIGO FUENTE

123

uLiteral(cb, (Addr)instr_addr);

// Call the helper if (1 == argc) uInstr1(cb, CCALL, 0, TempReg, else if (2 == argc) uInstr2(cb, CCALL, 0, TempReg, TempReg, else if (3 == argc) uInstr3(cb, CCALL, 0, TempReg, TempReg, TempReg, else VG_(skin_panic)("argc... not 1

t_instr_addr_addr); t_instr_addr_addr, t_data_addr1); t_instr_addr_addr, t_data_addr1, t_data_addr2); or 2 or 3?");

uCCall(cb, helper, argc, argc, False); }

// Instrument the basic block ’cb_in’ beginning at ’orig_addr’ UCodeBlock* SK_(instrument)(UCodeBlock* cb_in, Addr orig_addr) { UCodeBlock* cb; UInstr* u_in; Int i, t_read_addr, t_write_addr, t_read, t_write; Bool instrumented_Jcc = False; Addr x86_instr_addr = orig_addr; ULong x86_instr_size, data_size = 0;

// cb is the new code block we’ll build and return cb = VG_(setup_UCodeBlock)(cb_in); t_read_addr = t_write_addr = t_read = t_write = INVALID_TEMPREG; for (i = 0; i < VG_(get_num_instrs)(cb_in); i++)

´ B.1. CODIGO FUENTE

124

{ u_in = VG_(get_instr)(cb_in, i); // // // // // // // // // // // // // // // //

We want to instrument each x86 instruction with a call to the appropriate simulation function, which depends on whether the instruction does memory data reads/writes. x86 instructions can end in three ways, and this is how they are instrumented: 1. UCode, INCEIP --> UCode, Instrumentation, INCEIP 2. UCode, JMP --> UCode, Instrumentation, JMP 3. UCode, Jcc, JMP --> UCode, Instrumentation, Jcc, JMP The last UInstr in a BB is always a JMP. Jccs, when they appear, are always second last. This is checked with assertions. Instrumentation must go before any jumps. (JIFZ is the exception; if a JIFZ succeeds, no simulation is done for the instruction.) x86 instruction sizes are obtained from INCEIPs (for case 1) or from .extra4b field of the final JMP (for case 2 & 3).

if (instrumented_Jcc) sk_assert(u_in->opcode == JMP);

switch (u_in->opcode) { // For memory-ref instrs, copy the data_addr into a temporary to be // passed to the cachesim_* helper at the end of the instruction. case LOAD: case SSE3ag_MemRd_RegWr: // Integer Read ?? // Get first operand value (source memory address) t_read = u_in->val1; // Get a virtual register t_read_addr = newTemp(cb); // Append a new uInstruction to the code block // In this case, the instruction MOVes the memory address to a

´ B.1. CODIGO FUENTE

125

// temp virtual register. uInstr2(cb, MOV, 4, TempReg, u_in->val1, TempReg, t_read_addr); data_size = u_in->size; // Append the uInstruction u_in to the code block. VG_(copy_UInstr)(cb, u_in); break; case FPU_R: case MMX2_MemRd: // Floating Point Read ?? t_read = u_in->val2; t_read_addr = newTemp(cb); uInstr2(cb, MOV, 4, TempReg, u_in->val2, data_size = u_in->size; VG_(copy_UInstr)(cb, u_in);

TempReg, t_read_addr);

break; case MMX2a1_MemRd: case SSE2a_MemRd: case SSE2a1_MemRd: case SSE3a_MemRd: case SSE3a1_MemRd: // Floating Point Read ?? t_read = u_in->val3; t_read_addr = newTemp(cb); uInstr2(cb, MOV, 4, TempReg, u_in->val3, data_size = u_in->size; VG_(copy_UInstr)(cb, u_in);

TempReg, t_read_addr);

break; // Note that we must set t_write_addr even for mod instructions; // That’s how the code above determines whether it does a write. // Without it, it would think a mod instruction is a read.

´ B.1. CODIGO FUENTE

126

// As for the MOV, if it’s a mod instruction it’s redundant, but it’s // not expensive and mod instructions are rare anyway. case STORE: case FPU_W: case MMX2_MemWr: // Write ?? t_write = u_in->val2; t_write_addr = newTemp(cb); uInstr2(cb, MOV, 4, TempReg, u_in->val2, TempReg, t_write_addr); data_size = u_in->size; VG_(copy_UInstr)(cb, u_in); break; case SSE2a_MemWr: case SSE3a_MemWr: // Write ?? t_write = u_in->val3; t_write_addr = newTemp(cb); uInstr2(cb, MOV, 4, TempReg, u_in->val3, TempReg, t_write_addr); data_size = u_in->size; VG_(copy_UInstr)(cb, u_in); break; // INCEIP: insert instrumentation case INCEIP: x86_instr_size = u_in->val1; goto instrument_x86_instr; break; // JMP: insert instrumentation if the first JMP case JMP: if (instrumented_Jcc) {

´ B.1. CODIGO FUENTE

127

sk_assert(CondAlways == u_in->cond); sk_assert(i+1 == VG_(get_num_instrs)(cb_in)); VG_(copy_UInstr)(cb, u_in); instrumented_Jcc = False; break; } else { // The first JMP... instrument. if (CondAlways != u_in->cond) { sk_assert(i+2 == VG_(get_num_instrs)(cb_in)); instrumented_Jcc = True; } else { sk_assert(i+1 == VG_(get_num_instrs)(cb_in)); } // Get x86 instr size from final JMP. x86_instr_size = VG_(get_last_instr)(cb_in)->extra4b; goto instrument_x86_instr; } // Code executed at the end of each x86 instruction. instrument_x86_instr: // Large (eg. 28B, 108B, 512B) data-sized instructions will be // done inaccurately but they’re very rare and this avoids // errors from hitting more than two cache lines in the // simulation. if (data_size > MIN_LINE_SIZE) data_size = MIN_LINE_SIZE; references_collection(cb, x86_instr_addr, x86_instr_size, data_size, t_read, t_read_addr, t_write, t_write_addr); // Copy original UInstr (INCEIP or JMP) VG_(copy_UInstr)(cb, u_in); // Update loop state for next x86 instr

´ B.1. CODIGO FUENTE

128

x86_instr_addr += x86_instr_size; t_read_addr = t_write_addr = t_read = t_write = INVALID_TEMPREG; data_size = 0; break; default: // Without instrumentation VG_(copy_UInstr)(cb, u_in); break; } } VG_(free_UCodeBlock)(cb_in); return cb; #undef INVALID_DATA_SIZE } // Subtract the ‘struct timeval’ values X and Y, storing the result in RESULT. // Return 1 if the difference is negative, otherwise 0. void timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) { Int nsec; /* Perform the carry for the later subtraction by updating y. */ if ( x->tv_usec < y->tv_usec ) { nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } if ( x->tv_usec - y->tv_usec > 1000000 ) { nsec = (x->tv_usec - y->tv_usec) / 1000000;

´ B.1. CODIGO FUENTE

129

y->tv_usec += 1000000 * nsec; y->tv_sec -= nsec; } /* Compute the time remaining to wait. tv_usec is certainly positive. */ result->tv_sec = x->tv_sec - y->tv_sec; result->tv_usec = x->tv_usec - y->tv_usec; }

void SK_(fini)(Int exitcode) { float elapsed_time; Int shifted_secs; Char buff1[64]; #define TIME_PRECISION 1000 gettimeofday(&prof_info.end_time, NULL); timeval_subtract(&prof_info.diff_time, &prof_info.end_time, \ &prof_info.begin_time); elapsed_time = prof_info.diff_time.tv_sec \ + prof_info.diff_time.tv_usec/1000000.0; shifted_secs = elapsed_time * TIME_PRECISION; VG_(sprintf)(buff1, "%d.%d", shifted_secs/TIME_PRECISION, \ shifted_secs%TIME_PRECISION); if ( tracing_options.profiling ) { VG_(message)(Vg_UserMsg,"Execution time: %ss", buff1); VG_(message)(Vg_UserMsg,"Thread switches: %u", prof_info.thread_switches); VG_(message)(Vg_UserMsg,""); VG_(message)(Vg_UserMsg,"I refs: %u", prof_info.instr_refs); VG_(message)(Vg_UserMsg,"I per switch: %u", prof_info.instr_refs / prof_info.thread_switches ); VG_(message)(Vg_UserMsg,"");

´ B.1. CODIGO FUENTE

130

VG_(message)(Vg_UserMsg," D rd refs: %u", prof_info.data_rd_refs ); VG_(message)(Vg_UserMsg," D wr refs: %u", prof_info.data_wr_refs ); VG_(message)(Vg_UserMsg,"D refs: %u", prof_info.data_rd_refs + prof_info.data_wr_refs); VG_(message)(Vg_UserMsg,""); } sk_assert( trace_files[INSTR_REF].stream >= 0 ); write_deflated(trace_files[INSTR_REF].defl_buffer, BUFF_USED(INSTR_REF), &trace_files[INSTR_REF], Z_FINISH); sk_assert( trace_files[DATA_REF].stream >= 0 ); write_deflated(trace_files[DATA_REF].defl_buffer, BUFF_USED(DATA_REF), &trace_files[DATA_REF], Z_FINISH); /* Trace files closing */ close(trace_files[INSTR_REF].stream); close(trace_files[DATA_REF].stream); } VG_DETERMINE_INTERFACE_VERSION(SK_(pre_clo_init), 0) /*--------------------------------------------------------------------*/ /*--- end ---*/ /*--------------------------------------------------------------------*/

Bibliograf´ıa [1] A. Agarwal, J. Hennessy, M. Horowitz, “An analytical cache model,” ACM Transactions on Computer Systems, vol. 7, no. 2, pp. 184-215, 1989. [2] E. Artiaga, N. Navarro, X. Martorell, Y. Becerra, “Implementing PARMACS Macros for Shared Memory Multiprocessor Environments,” Technical Report, Polytechnic University of Catalunya, Department of Computer Architecture, 1997. [3] D. Bailey, “FFT’s in External or Hierarchical Memory,” Journal of Supercomputing, pp. 23-35, 1990. [4] T. Ball, J. Larus, “Optimally Profiling and Tracing Programs,” ACM Transactions on Programming Languages and Systems, vol. 16, no. 4, pp. 1319-1360, 1994. [5] G. Blelloch, C. Leiserson, B. Maggs, C. Plaxton, S. Smith, M. Zagha, “A Comparison of Sorting Algorithms for the Connection Machine CM-2,” Proc. of the Symposium on Parallel Algorithms and Architectures, pp. 3-16, 1991. [6] J. Boyle, R. Butler, T. Disz, B. Glickfeld, E. Lusk, R. Overbeek, J. Patterson, R. Stevens, “Portable Programs for Parallel Processors,” Holt, Rinehart, and Winston Incorporation, New York, NY, 1987. [7] B. Daum, “Professional Eclipse 3 for Java Developers,” Wrox, 2004. 131

BIBLIOGRAF´IA

132

[8] The Eclipse Project, http://www.eclipse.org/ [9] S. Eggers, J. Emer, H. Levy, J. Lo, R. Stamm, D. Tullsen, “Simultaneous Multithreading: A Platform for Next-Generation Processors,” IEEE Micro, pp. 12-19, 1997. [10] C. Fuentes, “Hardware Support for Operating Systems,” Technical Report, University of Michigan, 1993. [11] Gnuplot, http://www.gnuplot.info/ [12] J. Hamkalo, B. Cernuschi Fr´ıas, “A Taxonomy for Cache Memory Misses,” Proc. of the 11th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’99), 1999. [13] J. Hamkalo, B. Cernuschi Fr´ıas, “Non Symmetric Two Way Set Associative Caches,” Proc. of the AST2000, pp. 1-8, 2000. [14] J. Hamkalo, A. Vega, B. Cernuschi Fr´ıas, “SWSA-MT: Un Esquema de Memoria Cach´e para Ambientes Multihilo,” 5th Argentine Symposium on Computing Technology (AST 04), 2004. [15] J. Hennessy, D. Patterson, “Computer Architecture. A Quantitative Approach,” 3ra edici´on, Morgan Kaufmann Publishers, 2003. [16] M. Hill, “Aspects of Cache Memory and Instruction Buffer Performance,” PhD thesis, Computer Science Division (EECS), University of California, Berkeley, California, USA, November 1987. [17] M. Hill, A. Smith, “Evaluating Associativity in CPU Caches,” IEEE Transactions on Computers, pp. 1612-1630, 1989. [18] Z. Hu, M. Martonosi, S. Kaxiras, “Improving Cache Power Efficiency with an Asymmetric Set-Associative Cache,” Proc. of the 28th Annual International Symposium on Computer Architecture (ISCA-2001), 2001.

BIBLIOGRAF´IA

133

[19] Intel Corporation, http://www.intel.com/ [20] JFace, http://wiki.eclipse.org/index.php/JFace [21] T. Karkhanis, J. Smith, “Modeling Superscalar Processors,” Proc. of the 31st Annual International Symposium on Computer Architecture (ISCA-2004), 2004. [22] H. Kwak, B. Lee, A. Hurson, S. Yoon, W. Hahn, “Effects of Multithreading on Cache Performance,” IEEE Transactions on Computers, pp. 176-184, 1999. [23] A. Lebeck, D. Wood, “Cache Profiling and the SPEC Benchmarks: A Case Study,” IEEE Computer, vol. 27, pp. 15-26, 1994. [24] E. Lusk, R. Overbeek, “Use of Monitors in FORTRAN: A Tutorial on the Barrier, Self-scheduling DO-Loop, and Askfor Monitors,” Technical Report No. ANL-84-51, Rev. 1, Argonne National Laboratory, June 1987. [25] M. Nemirowsky, W. Yamamoto, “Quantitative Study of Data Caches on a Multistreamed Architecture,” Proc. of the Workshop on Multithreaded Execution Architecture and Compilation (with HPCA-4), 1998. [26] N. Nethercote, “Dynamic Binary Analysis and Instrumentation,” Ph.D. Thesis, University of Cambridge, 2005. [27] D. Patterson, “Computer Science Education in the 21st Century,” Communications of the ACM, vol. 49, no. 3, pp. 27-30, 2006. [28] J. Pierce, T. Mudge, “IDtrace - A Tracing Tool for i486 Simulation,” Proc. of the 2nd International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, 1994. [29] Rich Client Platform, http://wiki.eclipse.org/index.php/Rich_ Client_Platform

BIBLIOGRAF´IA

134

[30] J. Seward, N. Nethercote, J. Fitzhardinge, “Valgrind, version 2.4.0,” Manual correspondiente a la versi´on 2.4.0 de la herramienta Valgrind, 2005. [31] A. Smith, “Cache Memories,” ACM Computing Surveys, vol. 14, no. 3, pp. 473-530, 1982. [32] Sun Microsystems, http://www.sun.com/ [33] “Sun Fire T1000 and T2000 Server Architecture - Unleashing the ULTRASparc T1 Processor with CoolThreads Technology,” White Paper, Sun Microsystems, 2005, http://www.sun.com/servers/ coolthreads/coolthreads_architecture_wp.pdf [34] N. Tuck, D. Tullsen, “Initial Observations of the Simultaneous Multithreading Pentium 4 Processor,” Proc. of the 12th Intl Conference on Parallel Architectures and Compilation Techniques, 2003. [35] D. Tullsen, S. Eggers, H. Levy, “Simultaneous Multithreading: Maximizing On-Chip Parallelism,” Proc. of the 22nd Annual International Symposium on Computer Architecture (ISCA-1995), 1995. [36] D. Tullsen, S. Eggers, J. Emer, H. Levy, J. Lo, R. Stamm, “Exploiting Choice: Instruction Fetch and Issue on an Implementable Simultaneous Multithreading Processor,” Proc. of the 23rd Annual International Symposium on Computer Architecture (ISCA-1996), 1996. [37] R. A. Uhlig, T. N. Mudge, “Trace-Driven Memory Simulation: A Survey,” ACM Computing surveys, vol. 29, no. 2, pp. 128-170, 1997. [38] T. Ungerer, B. Robic, J. Silc, “A survey of processors with explicit multithreading,” ACM Computing Surveys, vol. 35, no. 1, pp. 29-63, 2003. [39] Valgrind, http://www.valgrind.org/

BIBLIOGRAF´IA

135

[40] K. Hwang, “Advanced Computer Architecture - Parallelism, Scalability, Programmability,” Mac Graw Hill and MIT Press, New York, 1993. [41] S. Woo, J. Singh, J. Hennessy, “The Performance Advantages of Integrating Block Data Transfer in Cache-Coherent Multiprocessors,” Proc. of the 6th Symposium on Architectural Support for Programming Languages and Operating Systems, pp. 219-231, 1994. [42] S. Woo, M. Ohara, E. Torrie, J. Singh, A. Gupta, “The SPLASH-2 Programs: Characterization and Methodological Considerations,” Proc. of the 22nd Annual International Symposium on Computer Architecture (ISCA-1995), pp. 24-36, 1995. [43] J. Yi, L. Eeckhout, D. Lilja, B. Calder, L. John, J. Smith, “The Future of Simulation: A Field of Dreams?,” IEEE Computer, vol. 39, no. 11, pp. 22-29, 2006. [44] Zlib, http://www.zlib.net/

Loading...

Un Ambiente para la Evaluación de Arquitecturas de Memoria en

Un Ambiente para la Evaluaci´ on de Arquitecturas de Memoria en Esquemas Multihilo Simult´ aneo Tesis de Grado en Ingenier´ıa Inform´atica Orientaci´o...

1MB Sizes 2 Downloads 7 Views

Recommend Documents

Actividades Para Desarrollar La Memoria En Niños De Primaria
About Actividades Para Desarrollar La Memoria En Niños De Primaria. types of puppers memechowee memegang rape memedavid

andanzas de un an en - Memoria Chilena
deseos. Lo que gnne' y lo que perdi se encontrnrd relatndo veridicn- mente en el primer libro, que se ociilxi preferente

La modalidad B-learning como alternativa de un ambiente de
Dokeos, y Moodle. Identificado Moodle como la más idónea en cuanto a las condiciones funcionales para la implementaciÃ

Arquitecturas para la Federación de Proveedores Cloud - PDF - Data
Mar 20, 2017 - Arquitecturas para la Federación de Proveedores Cloud Daniel Molina Aranda MÁSTER EN INVESTIGACIÓN EN

la memoria de shakespeare
estaba sujeta al pupitre, la mojé en el tintero de bronce y al inclinarme sobre el libro abierto, ocurrió la primera s

Arquitecturas de juego.pdf - Documents
Dec 13, 2015 - Tipo de distorsiones cognitivas durante el juego.pdf · Arquitecturas de cómputo.docx · Arquitecturas d

Memoria de actividades de la AEMPS 2010
Organigrama. El equipo humano. El equipo humano de la AEMPS está formado por más de 400 profesionales altamente cualif

Un modelo para la evaluacion de la narrativa basada en partidas de
y textos predefinidos son parametrizables. El sistema trabaja con dos tipos pre- ... basado en tres niveles de decisión

Establecimiento de un proceso para la obtencion de proteina a
Dec 31, 1996 - ... of Files: Text: 4.7K Graphics: No associated graphics files Introduccion La proteina A de Staphylocco

METODOLOGÍA PARA LA ELABORACIÓN DE UN PLAN DE
Feb 25, 2017 - Elaborar una metodología para la creación de un plan de marketing digital, pretende. complementar lo me