Problema Procesador–Memoria
Procesadores lanzan instrucciones aprox. cada nanosegundo.
DRAM puede ser accesada aprox. cada 100 nanosegundos (!).
DRAM no puede mantener al procesador al 100%! La diferencia está creciendo:
procesadores son más rápidos 60% por año
DRAM es más rápida 7% por año (SDRAM and EDO RAM ayudan, pero no es suficiente)
Procesador-Memoria Performance Gap
µProc
60%/yr.
DRAM
7%/año.
1
10
100
1000
1980
1981
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
DRAM
CPU
1982
Procesador-Memoria
Performance Gap:(crece 50% / año)
Performance
“Moore’s Law”
From D. Patterson, CS252, Spring 1998 ©UCB
Procesador-Memoria Performance Gap
Los problemas vienen a ser peores cuando se necesita memoria remota (distribuida o NUMA)
La latencia de red es aprox. 1000-10000 nanosegundos (aprox. 1-10 microsegundos)
Las redes son muy rápidas, pero no lo suficiente
Por tanto, la cache es usada en todos los procesadores
Casi tan rápida como el procesador
costosa, se puede usar cantidades pequeñas
El sistema se debe diseñar para cargar la cache de forma eficiente
CPU
Memoria Principal
Cache
Procesador-Cache-Memoria
La cache es mucho más pequeña que la memoria principal, y por lo tanto existe un mapeo de datos desde memoria principal a cache.
CPU
Cache
Local
Memory
Remote
Memory
Jerarquía de Memoria
Cache-Términos Relacionados
ICACHE : cache de instrucciones
DCACHE (L1) : cache de datos cercana a los registros
SCACHE (L2) : cache secundaria de datos
Los datos desde SCACHE tienen que ir a través DCACHE hacia los registros
SCACHE es más grande que la DCACHE
No todos los procesadores tienen SCACHE
Beneficios de la Cache
La cache de datos fue diseñada con dos conceptos claves en mente
Localidad Espacial
Cuando un elemento es referenciado sus vecinos deberán ser referenciados también
Las lineas de cache son buscadas juntas
Trabajar sobre elementos de datos consecutivos en la misma linea de cache
Localidad Temporal
Cuando un elemento es referenciado, éste volverá a ser referencia de nuevo muy pronto
Los datos en la cache son reusados constantemente
(Gp:) cache
(Gp:) main memory
Cache de Correspondencia Directa
Cache de mapeo directo: Un bloque en la memoria principal puede ir exactamente a un lugar en la cache. Esto es llamado correspondencia directa porque existe un mapeo directo desde cualquier direción de bloque en memoria a una simple ubicación en la cache.
cache
Main memory
Cache Completamente Asociativa
Cache Completamente Asociativa : Un bloque en memoria principal puede ser colocado en cualquier lugar de la cache. Esto es llamado Completamente asociativa porque el bloque en memoria principal puede ser asociado con cualquier entrada en la cache.
(Gp:) 2-way set-associative cache
(Gp:) Main memory
Cache Asociativa por Conjuntos
Cache asociativa por conjuntos : El diseño intermedio entre cache de mapeo directo y cache completamente asociativa es llamado cache asociativa por conjuntos. En una cache asociativa por conjuntos de n-vías un bloque en la memoria principal puede ir a N (N > 1) posiciones en la cache.
Cache-Términos Relacionados
Least Recently Used (LRU): Una estrategia de reemplazo para cache asociativa por conjuntos. El bloque de la cache que es el menos recientemente usado es reemplazado con un nuevo bloque.
Random Replace: Una estrategia de reemplazo para cache asociativa por conjuntos. Un bloque de la cache es reemplazado aleatoriamente.
Ejemplo: CRAY T3E Cache
Los procesadores de la CRAY T3E pueden ejecutar
2 ops punto flotante(1 suma, 1 multiplicación) y
2 ops enteros/memoria (incluye 2 loads o 1 store)
Para ayudar a mantener los procesadores trabajando
on-chip 8 KB direct-mapped data cache
on-chip 8 KB direct-mapped instruction cache
on-chip 96 KB 3-way set associative secondary data cache with random replacement.
Colocando las Piezas juntas
Recordemos:
Arquitectura de memoria compartida:
Uniform Memory Access (UMA): Symmetric Multi-Processors (SMP). Eje: Sun E10000
Non-Uniform Memory Access (NUMA): Las más comunes son Distributed Shared Memory (DSM), o sistemas cc-NUMA (cache coherent NUMA). Eje: SGI Origin 2000
Arquitectura de Memoria Distribuida:
Massively Parallel Processor (MPP): sistema integrado, se tiene la imágende un simple sistema. Eje: CRAY T3E, IBM SP
Clusters: nodes conectados por interconexión. Ejemplo: Beowulf clusters.
Multiproces. Simétricos (SMPs)
Los procesadores SMPs están conectados a una memoria global compartida usando:
bus
crossbar
Provee un simple modelo de programación, pero tiene problemas:
Buses saturados
Tamaño de crossbar debe crecer con el # de procesadores
Los problemas aumentan con el número de procesadores, limitando el tamaño máximo del SMPs
Programación Memoria Compartida
Los modelos de programación son sencillos ya que no es necesario el paso de mensajes. Técnicas:
autoparalelización via opciones del compilador
Paralelismo a nivel de bucles via directivas del compilador
OpenMP
pthreads
Más sobre modelos de programación luego.
Computadores Masivamente Paralelos
Cada procesador tiene su propia memoria:
La memoria no está compartida de forma global
Se adiciona otro nivel en la jerarquía de memoria (memoria remota)
Los nodos procesador/memoria son conectados por una red de interconexión
Varias posibilidades de topología
Los procesadores deben pasar datos via mensajes
La comunicación debe ser minimizada (overhead)
Interconexión
Custom
Las compañias proveen una red de interconexión de alto rendimiento para sus sistemas MPP
La interconexión en la CRAY T3E es la más rápida para MPPs: baja latencia, alto ancho de banda
Commodity
Usada en algunos sistemas MPPs y en todos los clusters
Myrinet, Gigabit Ethernet, Fast Ethernet, etc.
Tipos de Interconexiones
Fully connected
No factible
Array and torus
Intel Paragon (2D array), CRAY T3E (3D torus)
Crossbar
IBM SP (8 nodos)
Hypercube
SGI Origin 2000 (hypercube), Meiko CS-2 (fat tree)
Combinaciones de algunos de los anteriores
IBM SP (crossbar & fully connected para 80 nodos)
IBM SP (fat tree para > 80 nodos)
Clusters
Similar a MPPs
Utilidad procesadores y memoria
Rendimiento del procesador debe ser máximizado
La jerarquía de memoria incluye la memoria remota
No hay memoria compartida—paso de mensaje
El overhead de comunicación debe ser minimizado
Diferencia de MPPs
Comodidad, incluyendo interconexión y SO
Sistemas múltiples independientes: más robusto
Sistema separado de I/O
Cluster: ventajas y desventajas
Ventajas
Menos costoso ($)
Procesadores muy rápidos
Potencial desarrollo de I/O paralela
Alta disponibilidad
Desventajas:
Menos maduración en software (programación y sistema)
Más dificultad en el manejo
Rendimiento bajo de la interconexión: no se puede escalar a grandes números de procesadores
Programación Memoria Distribuida
El paso de mensaje es más eficiente
MPI
MPI-2
Active/one-sided messages
Vendedor: SHMEM (T3E), LAPI (SP)
Viene en MPI-2
Modelos de memoria compartida pueden ser implementados en software, pero no es tan eficiente.
Más sobre modelos de programación en la próxima sección.
“Memoria Compartida Distribuida”
Generalmente llamada cc-NUMA (cache coherent NUMA)
Consiste de m SMPs con n procesadores en un espacio de direccionamiento global:
Cada procesador tiene alguna memoria local (SMP)
todos los procesadores pueden accesar todas las memorias
El hardware garantiza coherencia de cache
El acceso a memoria en otros SMPs es mucho más lento (NUMA)
“Memoria Compartida Distribuida”
Fácil de construir porque los accesos a memoria remota son muy lentos (no es costoso un bus/crossbar)
Problemas similares de caché
Al escribir códigos se debe tener en cuenta la distribución de datos
Balance de carga: Minimizar accesos a memorias “lejanas”
DSM Racional y Realidad
Racional: combina lo fácil de la programación SMP con la escalabilidad de la programación MPP a un costo mayor que un MPP
Realidad: NUMA introduce capas adicionales en la jerarquía de memoria SMP relativa al SMPs, entonces la escalabilidad está limitada si se programa como SMP
Realidad: la programación debe explotar el rendimiento y la alta escalablidad de la arquitectura.
SMPs Clusters
Mucho más simple que DSMs:
Compuesto de nodos conectados por una red, como un MPP o cluster
Cada nodo es un SMP
Procesadores de un SMP no comparten memoria de otros SMPs
Comunicación entre nodos SMP es vía paso de mensajes
Ej: IBM Power3-basado en sistemas SP
Diagrama SMP Cluster
(Gp:) Network
(Gp:) P
(Gp:) P
(Gp:) P
(Gp:) P
(Gp:) BUS
(Gp:) Memory
(Gp:) P
(Gp:) P
(Gp:) P
(Gp:) P
(Gp:) BUS
(Gp:) Memory
Razones para un SMPs Cluster
Natural extension de SMPs y clusters
SMPs ofrece gran rendimiento para su limitado crossbar/bus
La conección de nodos es como una memoria
se puede escalar a muchos procesadores con menos interconexión
Máximo rendimiento:
Optimizar en un nivel SMP – no hay overhead de comunicación
Optimizar en un nivel MPP – minimizar el número de mensajes
SMP Clusters Desventajas
Los clusters SMPs tienen las siguientes desventajas
No hay acceso a la memoria compartida del sistema completo
Tiene otras desventajes del DSMs
Capa extra en la jerarquía de memoria
El rendimeinto requiere más esfuerzo del programador que en SMPs o MPPs
Sin embargo, con los clusters SMPs se obtiene un alto rendimiento y escalabilidad
Cluster SMP: NPACI “Blue Horizon”
Sistema IBM SP:
procesadores Power3: buen rendimiento pico (~1.5 Gflops)
mejora del rendimiento sostenido (superscalar y pipelined) con respecto a otros procesadores
los nodos SMP tienen 8 procesadores Power3
El sistema tiene 144 SMP nodos (1152 procesadores en total)
Programación de Clusters SMPs
NSF: La mayoría de los usuarios sólo usan MPI, para mensajes entre nodos
DoE: la mayoría de aplicaciones están siendo desarrolladas con MPI (entre nodos) y OpenMP (dentro del node)
La programación MPI+OpenMP es más compleja, pero conduce al máximo rendimiento
Los mensajes activos y pthreads deben teóricamente dar máximo rendimiento