Download Introducción a la computación paralela

Porqué computación paralela?
Introducción a la
computación paralela
• Avances tecnológicos (HW)
• Avances en conocimientos (SW)
• Tópicos a comentar
Mario Medina C.
mariomedina@udec.cl
Avances tecnológicos
• Procesador
• Densidad de transistores: ~30% por año
• Velocidad de reloj: ~20% por año
• Memoria
• Capacidad de DRAM: ~60% por año
• Velocidad de memoria: ~10% por año
• Costo por bit: disminuye ~25% por año
• Discos
• Capacidad: ~60% por año
• Red
•
•
•
•
Ley de Moore
Ley de Kryder
Ley de Amdahl
Ley de Gustafson
Ley de Moore
• Gordon Moore, Intel, 1965,
Electronics Magazine
• “El número de transistores en un chip se
duplica cada 24 meses y esto no
cambiará en los próximos 10 años”
• Tenía razón
• Las razones son:
• Tamaño del chip
• Dimensión de los transistores
• Ingenio de los diseñadores
• Ancho de banda: > 100% por año
Ley de Moore
(número de transistores)
©2014 Mario Medina
Ley de Moore
(tamaño de transistores)
1
Tamaño del transistor
Velocidad de reloj de CPU
• Dennard Scaling
• Consumo de
potencia de un
transistor MOSFET
es proporcional al
área del transistor
• International
Technology
Roadmap for
Semiconductors
Qué hacer con tanto transistor?
• CPUs más capaces
• Funciones que antes se realizaban fuera del
chip ahora se hacen dentro de él
• Ejecución especulativa
• Ejecutar instrucciones en forma anticipada
por si acaso . . .
• Incluir más memoria on-chip
• Memorias cache de nivel L1, L2, L3, . . .
• Paralelismo!!
Ley de Moore extendida
La 2da. Ley de Moore
• “El desempeño de un procesador se
duplica cada 18 meses”
• Evidencia muestra que esto también se
ha cumplido
• Combinación de 2 factores:
• Número de transistores se duplica cada 24
meses
• Velocidad de reloj aumenta 50% cada 24
meses
Elementos de un computador
• Procesador
• Realiza el
procesamiento de datos
• Controla la operación
del computador
• Puede haber más de
uno!
• Multi-core y many-core
©2014 Mario Medina
2
El procesador
• Básicamente contiene
• Registros
• Almacenar los datos
• ALU
• Operaciones aritméticológicas
• Decodificador de
instrucciones
• Determinar qué hacer
• Unidad de control
• Control del procesador
Unidades funcionales
• Unidad Aritmético-Lógica (ALU)
• Suma, resta
• Multiplicación, división
• Raíz cuadrada, funciones trigonométricas
• Unidades de movimiento de datos
• Transferencia de datos entre memoria y
registros
• Unidades vectoriales
• Realizan operación sobre vector de datos
Brecha CPU-Memoria
• Procesador debe leer instrucciones y
datos desde la memoria a los registros
• Ciclo de reloj de CPU se reduce en 20%
a 30% cada año
Registros de la CPU
• Almacenamiento básico primario
• Número limitado (Pentium 4 tiene 128)
• Almacenamiento ultrarápido
• Registros internos de propósito general
• Usados para cálculos, ALU, etc.
• Registros especializados
•
•
•
•
Contador de programa
Registros de instrucción y de estado
Punteros a la pila
Registros índices
Jerarquía de memoria
• Memoria
• Jerarquía por
• Tamaño
• Costo
• Velocidad
• Almacenamiento
• Dentro del chip
• En placa madre
• Fuera del PC
Brecha CPU-Memoria
• CPU hoy es fácilmente 100x más rápida
que la memoria
• Velocidad CPU se duplica cada 2 ó 3 años
• Esto no ha sido verdad en los últimos años
• Tiempo de acceso a memoria RAM
disminuye 10% por año
• Velocidad RAM se duplica cada 6 años
©2014 Mario Medina
3
Memorias cache
Memorias cache
• Solución
• Transferir más datos y/o instrucciones en
cada acceso
• Buses de interconexión CPU-memoria más
anchos  $$$
• Memorias más rápidas
• Buses de interconexión CPU-Memoria más
rápidos  $$$
• Memorias Cache
• Memoria intermedia entre CPU y RAM
• Memoria entre CPU y RAM
•
•
•
•
Registros < tamaño < RAM
Registros > velocidad > RAM
Registros > costo > RAM
Puede estar dentro o fuera del chip
• Cómo sacarle provecho a esta memoria?
• Memoria asociativa
• Almacena datos e instrucciones más
frecuentemente usados
Memorias cache
Caches L1 y L2
• Tamaño de la cache importa
• Asociatividad de la memoria importa
• Cómo mejorar desempeño? Otra cache!
CPU chip
Register file
L1
cache
ALU
(SRAM)
System bus
Bus interface
Memory bus
Memory
bridge
Main
memory
(DRAM)
Cache bus
L2 cache
(SRAM)
Cache L1: pequeña y muy rápida
Cache L2: mayor tamaño y más
lenta
Tendencias en procesadores
• Velocidad de la luz impone límites
• Aproximadamente 30 cm/ns
• Señales eléctricas viajan más lento
• Digamos, 10 cm/ns
• Si una señal viaja 1 cm durante una
instrucción, desempeño limitado a 10GIPS
• Mas transistores por cm2
• Tecnología óptica
• Hacer cosas en paralelo
©2014 Mario Medina
Tendencias en procesadores
• Tengo mil millones de transistores: qué
hacer?
• Agregar más unidades funcionales
• Pipelining, VLIW
• Agregar más unidades de control
• Hyperthreading
• Ejecutar más instrucciones a la vez
• Procesamiento superescalar
• Procesadores multi-core!
4
Procesadores multi-core
Tendencias en CPUs Intel
• Tendencia actual en
procesadores
• Integrar varios “cores” en
un solo chip
• Cada core tiene su propia
memoria
• Procesadores interactúan
con el sistema a través de
un bus común
• 2, 4, 6 cores comunes
• 48 y 80 cores en el futuro
Intel 8086 (1978)
• 8086: 1978, 29K transistores
• 8 registros de 16 bits
• Bus de datos de 16 bits
• Bus de dirección de 20 bits
• Multiplexado con bus de datos
• Aprox. 2.5 MIPS
• 8088: CPU de IBM-PC
• Bus de datos de 8 bits para reducir
costos
• Clock de 4.77 MHz (IBM-PC)
• Fabricantes: Intel y AMD
Intel i7-4790 (2014)
•
•
•
•
•
•
•
•
•
•
•
4 Cores
Intel HD Graphics 4600
Microarquitectura Haswell
Sobre 1400M transistores
Velocidad: 4.0/4.4 GHz
Cache L1: 64KB/core
Cache L2: 256 KB/core
Cache L3: 8 MB
Consumo: 88W
Tamaño: 37.5x37.5 mm2
Precio: aprox. US$334
Otro ejemplo: Playstation 4
Intel i7-4790 (2014)
•
•
•
•
•
•
•
•
•
•
•
4 Cores
Intel HD Graphics 4600
Microarquitectura Haswell
Sobre 1400M transistores
Velocidad: 4.0/4.4 GHz
Cache L1: 64KB/core
Cache L2: 256 KB/core
Cache L3: 8 MB
Consumo: 88W
Tamaño: 37.5x37.5 mm2
Precio: aprox. US$334
©2014 Mario Medina
• Especificaciones técnicas
•
•
•
•
•
•
•
•
•
•
CPU 8 cores x86-64 (AMD)
8 GiBytes de memoria GDDR5, 256 MiB DDR3 RAM
Disco duro 500 GB
Tarjeta gráfica ATI Radeon, 18 cores, 1.84 TFLOPS
Lector de Blu-ray 6X, DVD 8X
Ethernet 10/100/1000
Wireless Ethernet 802.11 b/g/n
Sensor Playstation 4 Eye
USB 3.0, Bluetooth
Fines del 2013
• Precio: alrededor de US$400
5
Memorias RAM
Tamaño de bit de memoria
• RAM estática (SRAM)
• mas rápida pero más cara
• Usada en memorias cache
• RAM dinámica (DRAM)
• Ocupa menos espacio
• Usada para memoria principal
• SDRAM: Memoria DRAM sincrónica
• Tecnología en uso hoy
Memorias RAM
• Single Data Rate RAM (SDR SDRAM)
• Una palabra por ciclo (Pentium III)
• Dual Data Rate RAM (DDR SDRAM)
• Dos palabras por ciclo (Pentium 4)
• Dual Data Rate RAM (DDR2 SDRAM)
• Cuatro palabras por ciclo (Intel Core)
• Dual Data Rate RAM (DDR3 SDRAM)
• Ocho palabras por ciclo (Intel Core 2)
Evolución de memorias RAM
Tasas de transferencia RAM
CPU
Reloj del Transferencias
bus (MHz)
por ciclo
Ancho
del bus
Transferencias
(MB/s)
400 – 528
50 - 66
1
64 bits
Pentium II
66 – 100
1
64 bits
528 – 800
Pentium 4
100 – 133
4
64 bits
3200 – 4256
Pentium
Dual-Core
200 – 266
4
64 bits
6400 – 8512
Core 2
Extreme
266 – 400
4
64 bits
8512 – 12800
Core i7
3200
2
64 bits
25600
Pentium
• Core i7 usa QPI en vez de bus CPUmemoria
RAM vs Disco magnético
• El costo por MiB de la RAM
disminuye ~100 veces por década
• Razón de precio RAM/disco: ~100/1
• En 10 años lo que ahora está en disco
estará en RAM
• En 1999:
• Laptop Sony VAIO F-180
• 192 MB RAM, 4 GiB disco
• Hoy en día tengo 4GiB RAM!
©2014 Mario Medina
6
Ley de Kryder
Ley de Kryder
(Capacidad de discos magnéticos)
• “La razón entre almacenamiento y
superficie en un disco magnético se
duplica anualmente”
• 1956: primer disco magnético (2KiB)
• 2013: 2TB por $120K
• 2020: 20TB en el escritorio?
• Qué hacer con tanto almacenamiento?
• Cómo respaldar este almacenamiento?
Ejemplo de disco magnético
Evolución de interfaces de disco
• Disco magnético Seagate S2000NM0011
•
•
•
•
•
•
•
•
•
Capacidad de 2 TiB
Latencia: 4.16 ms
Velocidad de rotación 7,200 RPM
MTBF: 1.2x106 horas
Interfaz SATA: 6 GiB/s
Buffer interno: 64MiB
Transferencias: 150 MB/s
Tiempo de búsqueda R/W: 8.5/9.5 ms
Diseñado para operación 24/7/365
Memoria terciaria
• CD
• 700 MiB (80 min)
• 1X: 150 KiB/s, 50X: 7.5 MiB/s
• DVD
• 3.78 GiB (DVD-5)
• 1X: 1318 KiB/s, 16X: 21.1 MiB/s
• Blu-Ray
• 25 GB (Single layer)
• 1X: 4.5 MiB/s, 6X: 27 MiB/s
©2014 Mario Medina
Costo por GiB Julio ’14)
• Memoria RAM
• DDR3 8GB, 1866 GHz: $9K/GiB
• Disco magnético
• Maxtor SATA 3000 GB: $35/GiB
• Disco estado sólido
• Samsung 840 EO 1TB: $450/GiB
• CD / DVD
• CD-R 700 MiB: $140/GiB
• DVD-R 4.37 GiB: $32/GiB
• Blu-ray 50GiB: $20/GiB
7
Leyes sobre redes
Tendencias en Redes
• Ley de Metcalfe: El valor de una red es
proporcional al cuadrado de las
conexiones que se pueden realizar en
ella
• Ley de Reed: La utilidad de una red crece
exponencialmente con el tamaño de ésta
• Ley de Dunbar: el número de conexiones
activas que una persona puede mantener
es aproximadamente 150
Tendencias futuras
Ancho de banda a usuario residencial
Ley de Nielsen
• Ley de Nielsen: velocidad de conexión a
la internet aumenta 50% por año
• Jakob Nielsen ha graficado su ancho de
banda de conexión a la Internet
• 1983: Modem acústico de 300 baud
• 2010: Conexión via cable modem de 30 Mbps
Ley de Nielsen
Ancho de banda a la Internet
Sistemas computacionales
• Avances tecnológicos han
• Aumentado enormemente las capacidades
computacionales de los sistemas
• Reducido los costos equivalentes de los
sistemas computacionales
• Hecho que la evolución de la razón
costo/beneficio de un computador sea
exponencial
• Masificado el uso de sistemas
computacionales
©2014 Mario Medina
8
Computador 1978
• Cotización servidor para
Paños FIAP Tomé 1978
• Servidor DELL XPS 8700
• Computador Interdata 7/32
• Primer minicomputador de 32
bits, ~1 MHz
• Sistema operativo UNIX
• Primer port de UNIX
• Sistema “fully loaded” $69790 (US$2200)
• 64 KiB RAM
• 2 discos de 5 Mib
Comparación: PC 2014
Interdata 4 (16 bits)
•
•
•
•
•
•
•
•
•
•
“The need for speed”
Porqué paralelismo?
• Más velocidad
• Obtener soluciones más rápido (Ej., predecir
el clima para el siguiente día)
• Problemas interesantes necesitan aún
más
• Capacidad de procesamiento
• Capacidad de memoria
• Capacidad de almacenamiento secundario
• Mayor desempeño
• Resolver más problemas por unidad de
tiempo (Ej., procesamiento de transacciones)
• Resolver problemas más grandes
• Cómo conseguirlo?
• Sistemas paralelos
• Sistemas distribuidos
• Sistemas heterogéneos
• Predecir el clima para la próxima semana
• Mejorar la calidad de la predicción
Grand Challenges
• Problemas difíciles por definición
• Gran impacto económico y/o social
• Desempeño actual de sistemas
computacionales es insuficiente
• Requieren de
•
•
•
•
Gran poder de cómputo
Gran nivel de detalle
Grandes volúmenes de datos
Colaboración entre disciplinas
©2014 Mario Medina
Procesador Intel Quad Core i7-4770 3.4 GHz
16 GiB RAM DDR3 1600 MHz
Disco magnético 2 TiB SATA 7200RPM
Disco de estado sólido 32 GiB
Tarjeta AMD Radeon HD R9 270
Lector CD/DVD SATA
Monitor Dell 23” multi-tactil HDMI
Tarjeta Ethernet 10/100/1000
Wireless 802.11 b/g/n
Aproximadamente US$1600 (2014)
Problemas aún no resueltos
•
•
•
•
•
•
•
•
Biología molecular
Predicción del clima
Simulación de ecosistemas
Modelación ambiental a gran escala
Dinámica de fluidos
Cromodinámica cuántica
Turbulencia de fluidos
Circulación de los océanos
9
Problemas altamente paralelizables
•
•
•
•
Generación de imágenes via ray-tracing
Cálculo de fractales
Decriptación por fuerza bruta
Búsqueda de alineamientos de
nucleótidos
• Algoritmos genéticos
• Simulaciones
Alternativas
• Procesadores vectoriales
• Cray-1, Cray XM-P
• Procesadores masivamente paralelos
• Muchos procesadores conectados entre sí
via un bus de interconexión
• Clusters de computadores
• Muchos computadores conectados entre sí
por una red rápida de interconexión
• Computación heterogénea
• GPGPU
Computación heterogénea
• Coprocesadores matemáticos
• Intel 8086 se usaba en conjunto con el 8087
• Intel 80486 incorpora el coprocesador dentro
del chip
• Coprocesadores gráficos
• GPU (Nvidia Tesla)
• APU (AMD Fusion)
• Bibliotecas especializadas
• CUDA
• OpenCL
Speedup
• Aumento de desempeño al pasar de un
sistema secuencial a un sistema paralelo
de n procesadores
S = T1/Tn
• Idealmente, S = N
• Rara vez es el caso
• Ley de Amdahl!
Ley de Amdahl
Ley de Amdahl
• Gene Amdahl, IBM, Amdahl Corp.
• Define un límite al aumento de
desempeño de un sistema que se puede
obtener via optimización de parte de éste
• Sea T1 = S + P
• Si tenemos N procesadores, se tiene que
Tn = S + P/N
Tn = (1 – P) + P/N
T1/Tn = 1/((1 – P) + P/N)
• Si tenemos infinitos procesadores, el
aumento de desempeño será de 1/(1 – P)
• S: fracción de tiempo de ejecución serial
• P: fracción de tiempo de ejecución paralela
• Desempeño estará limitado por la parte serial
del algoritmo
©2014 Mario Medina
10
Ley de Amdahl
Ley de Amdahl
Ley de Gustafson
Ley de Gustafson
• “Cualquier problema lo suficientemente
grande puede ser paralelizado
eficientemente”
• S tenemos N procesadores, agrandemos
el problema!
• Al agrandar el problema, hay más trabajo
que realizar y éste se reparte mejor
• En vez de mantener el problema constante,
mantener constante el tiempo de solución
Pipelining
Gustafson + Pipelining
• Qué pasa si no puedo aumentar el
tamaño del problema?
• Usar pipelining para ejecutar en paralelo
varias copias del problema!
• Pipelining permite aumentar el desempeño
global de un sistema al dividir el
procesamiento en etapas y tener varias
instancias del problema en ejecución
simultáneamente
• Cada una en una etapa diferente
©2014 Mario Medina
11