Augusto J. Vega [email protected] Tesis de Grado en Ingeniería en Informática Orientación en...
-
Upload
armando-ante -
Category
Documents
-
view
230 -
download
0
Transcript of Augusto J. Vega [email protected] Tesis de Grado en Ingeniería en Informática Orientación en...
Augusto J. [email protected]
Tesis de Grado en Ingeniería en InformáticaOrientación en Sistemas Distribuidos
Febrero de 2007
Un Ambiente para la Evaluación de Arquitecturas de Memoria en
Esquemas Multihilo Simultáneo
Introducción
• Interrogantes respecto al desempeño de los recursos compartidos (memoria caché L1) en los nuevos procesadores con soporte multihilo (HyperThreading, Power5, etc.).
• Presentación de una nueva organización caché adecuada para estos procesadores.
• Desarrollo de herramientas para el estudio de memorias caché en ambientes multihilo.
• Creación de nuevas métricas y adaptación de otras existentes.
Estructura de laPresentación
• Recolección de trazas.• Procesamiento de trazas y simulación.• Caché para procesadores multihilo.• Conclusiones y trabajo a futuro.
Recolección de Trazas
• Traza: secuencia de referencias a memoria generadas por un programa.
• Útil para la simulación de memorias caché.• Típicamente, provenientes de programas
secuenciales (un solo hilo de ejecución).• Necesidad de trazas multihilo. 0x804879C
0x804879D0x804879F0x80487A20x80487A50x80487A70x80487AA0x80487AD0x80487B00x80487B1
...
Técnicas de Recolección
Sistema Operativo
Compilador
Ensamblador
Enlazador (linker)
Cargador (loader)
Emulación
Microcódigo
Circuitos y Compuertas
Ejecuciónpaso a paso
Instrumentación estática de código
Emulación deinstrucciones
Modificación delmicrocódigo
Analizadorlógico
Har
dwar
eS
oftw
are
El Sistema Valgrind
• Herramienta para depuración y análisis de desempeño, para ejecutables Linux-x86.
• Implementación de un procesador sintético x86.• Instrumentación dinámica de código binario.• Herramienta pública (GPL) y de código abierto.• Sitio web: http://www.valgrind.org/
Diseño General
PROGRAMA DE USUARIO
PLATAFORMA DE BASE(x86)
COREGRIND MÓDULO
INSTRUCCIONESx86
INSTRUCCIONESx86
UCODE
UCODEINSTRUMENTADO
Valgrind
El Sistema Valgrind(cont.)
Valgrind puede clasificarse como un emulador del conjunto de instrucciones.
Sistema Operativo
Compilador
Ensamblador
Enlazador (linker)
Cargador (loader)
Emulación
Microcódigo
Circuitos y Compuertas
Ejecuciónpaso a paso
Instrumentación estática de código
Emulación deinstrucciones
Modificación delmicrocódigo
Analizadorlógico
Har
dwar
eS
oftw
are
Valgrind
Valgrind + Multihilo
• Soporte para hilos POSIX (pthreads).• Coregrind es responsable de la planificación
mediante política round-robin.• Modificaciones al planificador, para lograr una
ejecución pseudo-simultánea de los hilos.
El Módulo Tracegrind
• Módulo para recolección de trazas multihilo, aprovechando el soporte de Valgrind.
• Instrumenta cada operación de lectura/escritura.• Comprime la traza “al vuelo”, usando LZ77.
PROGRAMA DE USUARIO
( MULTIHILO )
PLATAFORMA DE BASE(x86)
COREGRIND TRACEGRIND
INSTRUCCIONESx86
INSTRUCCIONESx86
UCODE
UCODEINSTRUMENTADO
TRAZA
El Módulo Tracegrind(cont.)
Tracegrind
log_reference()
Thread ID = 2
GETL %EAX, t0log_reference()
BLOQUE BÁSICO
Thread ID = 2
GETL %EAX, t0
BLOQUE BÁSICO
Thread ID = 2
GETL %EAX, t0
BLOQUE BÁSICO
EJECUCIÓN
COMPRESIÓNLZ77
TRAZA DATOS
TRAZA INSTR.
Validación de Trazas
• No se puede “confiar” en los resultados posteriores si las trazas no son válidas.
• No existen metodologías rigurosas.• Consejos obtenidos del Prof. Alan Jay Smith[1]:
– Tomar muestras de la traza y compararlas “manualmente” contra el código objeto.
– Realizar un análisis básico de tasas de lecturas y escrituras, cant. de instrucciones, distancia de saltos, etc. y compararlos contra resultados publicados.
[1] Computer Science Division, EECS Department, University of California, Berkeley.
Validación de Trazas deInstrucciones y Datos
• Uso de programas multihilo “modelo”.• Ejecución de los mismos sobre Valgrind, y
recolección de sus trazas.• Desensamblado de los programas “modelo”, y
comparación “a mano” contra la traza de instrucciones.
• Salida por pantalla de las direcciones de memoria de estructuras de datos y variables, y comparación “a mano” contra la traza de datos.
Trazas Recolectadas
• Subconjunto de los benchmarks SPLASH-2 (Stanford Parallel Applications for Shared Memory).
• Aplicaciones para procesamiento paralelo de algoritmos típicos (FFT, LU, Cholesky, etc.).
• Construido en base a macros PARMACS.• Se utilizaron PARMACS para hilos POSIX.
Trazas Recolectadas(cont.)
Aplicación DescripciónTrazas de Datos
Trazas de Instrucciones
1 hilo 4 hilos 1 hilo 4 hilos
FFTTransformada Rápida de Fourier de n números complejos en una dimensión.
17-MB
0,4 hs
26-MB
0,7 hs
6-MB
0,4 hs
43-MB
0,7 hs
LUFactorización de una matriz densa.
191-MB
3,5 hs
364-MB
6,3 hs
47-MB
3,5 hs
371-MB
6,3 hs
CholeskyFactorización de una matriz rala. 309-MB
4,7 hs
484-MB
9,4 hs
98-MB
4,7 hs
759-MB
9,4 hs
RadixOrdenamiento de números enteros.
67-MB
2,7 hs
263-MB
5,5 hs
37-MB
2,7 hs
519-MB
5,5 hs
OceanSimulación del movimiento de los océanos.
359-MB
4,7 hs
547-MB
8,2 hs
50-MB
4,7 hs
633-MB
8,2 hs
WaterSimulación del comportamiento de partículas de agua a lo largo del tiempo.
156-MB
5,3 hs
433-MB
10,5 hs
157-MB
5,3 hs
1231-MB
10,5 hs
Estructura de laPresentación
• Recolección de trazas.• Procesamiento de trazas y simulación.• Caché para procesadores multihilo.• Conclusiones y trabajo a futuro.
Procesamiento de Trazasy Simulación
• Posibles procesamientos sobre una traza:– Conversión de formato.– Compresión.– Filtrado y muestreo.– Simulación.
• Construcción de un framework flexible para el procesamiento de trazas SimiOO
• Extensible mediante la construcción de plug-ins.• Programado en lenguaje Java.
Simulación deMemorias Caché
• Metodologías:– Modelado analítico.– Simulación.
• Técnicas de simulación:– Manejada por ejecución: la simulación se realiza
mientras se ejecuta el programa.– Manejada por trazas: la simulación se realiza
utilizando el “historial” de accesos a memoria.
• Uso de estructuras (arreglos lineales y matrices) para modelar las organizaciones de memoria.
Procesamientode una Traza
• Lectura secuencial de todas las referencias.• Procesamiento sobre cada referencia leída (por ejemplo,
alimentarla a un simulador).
SimiOO...0xAFEFE0A80xAFEFE0AC0x3A97C1E80x3A97BF340x3A97C2380x3A97BF3C0x3A97C2100x3A97BF440x3A97C214
...
0x3A97C238 Core Plug-in
0x3A97C238
TRAZAESTADÍSTICAS
Por ejemplo, simulador de
memorias caché
Interfaz Gráfica de Usuario
Marco genérico aportado por el
núcleo de SimiOO
Perspectiva aportada por el
plug-in
Estructura de laPresentación
• Recolección de trazas.• Procesamiento de trazas y simulación.• Caché para procesadores multihilo.• Conclusiones y trabajo a futuro.
Paralelismo a Nivelde Instrucciones
• Un procesador superescalar puede procesar dos o más instrucciones simultáneamente.
• Replica algunas unidades funcionales (ALU).• Explota el paralelismo a nivel de instrucciones.• Podría implementar un mecanismo de pipeline.
INS
TR
UC
CIO
NE
S
TIEMPO
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
Paralelismo a Nivelde Instrucciones (cont.)
• En la práctica, este paralelismo suele ser pobre, debido a “riesgos” (hazards):– Estructurales: recursos insuficientes.– De Datos: dependencias de datos entre dos
instrucciones.– De Control: debido a transferencias del flujo de
control (branches).
• Además, el flujo de ejecución podría bloquearse ante una operación de E/S o un desacierto en la memoria caché.
Paralelismo a Nivelde Instrucciones (cont.)
• Se generan “desperdicios”:– Horizontales.– Verticales.
• Se explota el paralelismo a nivel de hilo:– CMT (Coarse-Grain Multithreading).– FMT (Fine-Grain Multithreading).– SMT (Simultaneous Multithreading).
TIE
MP
O
UNIDADES FUNCIONALES
Superscalar
Desperdicio vertical
Desperdicio horizontal
Multihilo Simultáneo - SMT
• Permite la ejecución simultánea de dos o más “hilos” de instrucciones, aprovechando el TLP.
• También explota el ILP presente en cada hilo.• Competencia por los recursos (e.g., la memoria
caché).• Implementaciones comerciales:
– Intel Hyper-Threading.– IBM Power5.– MIPS MT.
Multihilo Simultáneo - SMT(cont.)
TIE
MP
O
UNIDADES FUNCIONALES
Superscalar FMT SMT
Hilo 1
Hilo 2
Hilo 3
Desperdicio vertical
Desperdicio horizontal
Multihilo Simultáneo - SMT(cont.)
¿Cómo se comporta la memoria caché en un procesador multihilo simultáneo?
Memorias Caché
• Caché: lugar oculto para guardar provisiones.• En computación, memoria pequeña y de rápido
acceso para mantener los datos que, se supone, serán usados en un futuro inmediato.
• Explota el principio de localidad.• Reduce los accesos a memorias más lentas.
Memorias Caché(cont.)
• En caso de desacierto, se trae el bloque desde el nivel inferior.
• Estrategias para ubicar el nuevo bloque:– Correspondencia directa.– Asociativa por conjuntos.– Completamente asociativa.
• Políticas de reemplazo:– LRU (Least Recently Used).– FIFO.– Aleatoria.
Registrosde la CPU
Caché(L1, L2 y L3)
MemoriaPrincipal
Memoria Secundariay Dispositivos de E/S
Cos
to
Cap
acid
ad y
Tie
mpo
de
acce
so
Memoria Cachéde Correspondencia Directa
El nuevo bloque puede ubicarse en un solo lugar de la caché.
Índice 0
Índice 1
Índice 2
Índice 3
Índice 4
Índice 5
Índice 6
Índice 7
...
Memoria Principal Memoria Caché
Memoria CachéAsociativa por Conjuntos
El nuevo bloque puede ubicarse en un conjunto de lugares posibles de la caché.
Memoria Caché
VIA 1 VIA 2
Índice 0
Índice 1
Índice 2
Índice 3
Índice 4
Índice 5
Índice 6
Índice 7
...
Memoria Principal
Conjunto
Memoria CachéCompletamente Asociativa
El nuevo bloque puede ubicarse en cualquier lugar de la caché.
Índice 0
Índice 1
Índice 2
Índice 3
Índice 4
Índice 5
Índice 6
Índice 7
...
Memoria Principal Memoria Caché
El Esquema SWSA
• Esquema asociativo tradicional.• Los bancos (vías) pueden ser de tamaños diferentes.• Los bloques pueden compartirse entre diferentes
conjuntos.Memoria Caché
VIA 1 VIA 2
El Esquema SWSA-MT
• Se basa en el diseño SWSA.• Cada hilo dispone de un banco privado.• Todos los hilos acceden a un banco compartido.
Memoria Caché
VIA 1 VIA 2
Hilo 1
Hilo 2
Hilo 3
Hilo 4
Nuevos Criteriosy Métricas
• Tasa de aciertos compartidos: tasa de aciertos debido a accesos a bloques previamente referenciados por otros hilos.
• Acierto “largo”: acierto debido a que el bloque buscado por el hilo x se encuentra en la memoria privada del hilo y, siendo x y.
• Tasa de reubicación: tasa de reubicaciones debido a aciertos “largos”. BANCO 1 BANCO 2
HILO 2
HILO 1
A
¿Dato A?
Dato A
Clasificación de Desaciertos
• Objetivo: Conocer la causa de los desaciertos en una memoria caché para descubrir “debilidades”.
• Los modelos clásicos de clasificación no contemplan ambientes de ejecución multihilo.
• Uno de los más utilizados: modelo de las 3C [1]– Desaciertos obligatorios (compulsory).– Desaciertos de capacidad (capacity).– Desaciertos de conflicto (conflict).
[1] Mark Hill, Aspects of Cache Memory and Instruction Buffer Performance, Ph.D. Thesis, University of California, Berkeley.
Clasificación de Desaciertos:El Modelo de las 4C
• Propuesto en esta tesis, como extensión del modelo de las 3C.
• Útil para ambientes multihilo.• Tipos de desaciertos:
– Obligatorios (compulsory).– De capacidad (capacity).– De conflicto cerrado (closed-conflict).– De conflicto cruzado (crossed-conflict).
Ambiente de Simulación
Esquemas simulados
(nivel 1 de datos)
2WSA
4WSA
SWSA-MT
Tamaños 8-KB
16-KB
32-KB
64-KB
Línea 32 bytes
Política de reemplazo LRU
Benchmarks
(1 y 4 hilos)
FFT
LU
CHOLESKY
RADIX
OCEAN
WATER
Tasa de Desaciertos
Tasa de Desaciertos(cont.)
Clasificación de Desaciertos
1
2
3
4
5
6
7
8
9
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
LU
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
1
2
3
4
5
6
7
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
FFT
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
Clasificación de Desaciertos(cont.)
2
4
6
8
10
12
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
RADIX
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
2
4
6
8
10
12
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
CHOLESKY
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
Clasificación de Desaciertos(cont.)
1
2
3
4
5
6
7
8
9
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
WATER
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
5
10
15
20
25
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
2WSA
4WSA
SWSA-M
T
Cla
sific
ació
n d
e D
esa
cie
rto
s e
n D
ato
s d
e L
1 (
%)
OCEAN
ObligatoriosCapacidad
Conflicto CerradoConflicto Cruzado
64-KB32-KB16-KB8-KB
Tasa de Aciertos Compartidos
Tasa de Aciertos Compartidos(cont.)
Tasa de Reubicación
Tasa de Reubicación(cont.)
Tasa de Desaciertos “Ideal”
Tasa de Desaciertos “Ideal”(cont.)
Tasa de Desaciertos1 Hilo
Tasa de Desaciertos1 Hilo (cont.)
Aspectos deImplementación
Organización 2WSA:• 2 bancos multipuerto con soporte
para 4 hilos.
• 8 comparadores (2 por hilo).
• 4 multiplexores “2 a 1”.
• 1 bit por conjunto para manejo de política LRU.
Rótulo Datos Rótulo Datos
Rótulo Despl.Índice
Referencia Hilo 1
Rótulo Despl.Índice
Referencia Hilo 2
Rótulo Despl.Índice
Referencia Hilo 3
Rótulo Despl.Índice
Referencia Hilo 4
=? =?
Multiplexor 2:1
Datos
Aspectos deImplementación
Organización 4WSA:• 4 bancos multipuerto con soporte
para 4 hilos.
• 16 comparadores (4 por hilo).
• 4 multiplexores “4 a 1”.
• Política LRU de dificultosa implementación (pseudo-LRU).
Rótulo Datos Rótulo Datos Rótulo Datos Rótulo Datos
Rótulo Despl.Índice
Referencia Hilo 1
Rótulo Despl.Índice
Referencia Hilo 2
Rótulo Despl.Índice
Referencia Hilo 3
Rótulo Despl.Índice
Referencia Hilo 4
=? =? =? =?
Multiplexor 4:1
Datos
Aspectos deImplementación
Organización SWSA-MT:• Un banco multipuerto con soporte para
4 hilos.
• 24 comparadores (6 por hilo).
• 4 multiplexores “2 a 1”.
• k bits por conjunto para manejo de política LRU (siendo k la cantidad de bancos privados).
Rótulo Datos
Rótulo Despl.Índice
Referencia Hilo 1
Rótulo Despl.Índice
Referencia Hilo 2
Rótulo Despl.Índice
Referencia Hilo 3
Rótulo Despl.Índice
Referencia Hilo 4
Datos
=? =? =? =? =?
Multiplexor 2:1
Hardware de Reubicación
=?
Rótulo Rótulo Rótulo Rótulo Rótulo Datos
Un acierto en la memoria privada permite detener la búsqueda en el
banco compartido (ahorro de tiempo y energía).
Política LRU escalable
Estructura de laPresentación
• Recolección de trazas.• Procesamiento de trazas y simulación.• Caché para procesadores multihilo.• Conclusiones y trabajo a futuro.
Conclusiones
• SWSA-MT: nueva organización de memoria caché para procesadores multihilo.
• Modelo de las 4C: para clasificación de desaciertos en ambientes multihilo.
• Tracegrind y SimiOO: Herramientas para el estudio de memorias caché multihilo.
• Nuevos criterios y métricas (tasa de aciertos compartidos, acierto “largo”, tasa de reubicación).
Conclusiones(cont.)
• SWSA-MT se comporta mejor que el esquema 2WSA y similar a 4WSA.
• Más simple de implementar respecto a 4WSA.• Minimiza la interferencia “destructiva” (conflictos
cruzados).• Agrega hardware de reubicación (que se usa
muy esporádicamente).
Conclusiones(cont.)
2WSA 4WSA SWSA-MT
Bancos multipuerto
2 4 1 Comparadores 8 16 24 Multiplexores 4 x “2 a 1” 4 x “4 a 1” 4 x “2 a 1” Implementación de LRU
Si
(escalable)
Dificultoso
(no escalable)
Si
(escalable) Hardware adicional
No No De reubicación
Otras características
Simple de implementar
Minimiza efectos de
hiperpaginación
Ahorro de energía y tiempo ante aciertos en la
memoria privada
Trabajo a Futuro
• Política dinámica de redistribución de la caché entre los hilos activos.
• Heurística para detectar accesos compartidos (eliminando el hardware de reubicación).
• Adaptación de SWSA-MT a procesadores con múltiples núcleos (tecnología multicore).
Participación en Congresos
Partes de esta tesis fueron publicadas en los siguientes congresos y simposios:
– World Computer Congress 2006 – Santiago (Chile).– 6th Argentine Symposium on Computing
Technology 2005– Rosario (Argentina).– 5th Argentine Symposium on Computing
Technology 2004 – Córdoba (Argentina).
Augusto J. [email protected]
Tesis de Grado en Ingeniería en InformáticaOrientación en Sistemas Distribuidos
Febrero de 2007
Un Ambiente para la Evaluación de Arquitecturas de Memoria en
Esquemas Multihilo Simultáneo