Download Computadoras Paralelas - Cinvestav

Laboratorio de
Tecnologías de Información
Introducción al Cómputo Paralelo
Enero 2012
Arturo Díaz Pérez
Centro de Investigación y de Estudios Avanzados del IPN
Laboratorio de Tecnologías de Información
[email protected]
Cómputo Paralelo
Intro- 1
Contenido
 
 
 
 
 
 
 
 
 
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Antecedentes y motivación
¿Qué es computación paralela?
¿Por qué estudiar computación paralela?
Tendencia en las aplicaciones
Tendencia en la tecnología
Tendencia en la arquitectura
Aspectos de economía
Aspectos de la computación paralela
¿Cuál es la relación con nuestro curso?
Intro- 2
Antecedentes
Laboratorio de
Tecnologías de Información
♦  Existen una demanda permanente por mayor
rendimiento computacional de los sistemas de cómputo
♦  Los enfoque seguidos para obtener mejor rendimiento
son cambios
■  Tecnológicos
■  Arquitecturales
Cómputo Paralelo
Intro- 3
Antecedentes
Laboratorio de
Tecnologías de Información
♦  Ejemplos de diferentes de sistemas de alto rendimiento
■  Procesadores multicore (2004-)
■  Procesadores multithreading (2002-)
■  Procesadores superescalares (1992-2002)
»  Relojes de alta velocidad
»  Paralelismo a nivel de instrucciones
»  Varios niveles de memoria cache
■ 
■ 
■ 
■ 
■ 
Procesadores para Vectores (1970´s)
Supercomputadoras (1980)
Arreglos de Procesadores VLSI (1985)
Custom Computing (1992)
Computadoras Paralelas (1986)
Cómputo Paralelo
Intro- 4
Tendencias Generales
Laboratorio de
Tecnologías de Información
♦  El rendimiento de los procesadores se incrementa entre
♦ 
♦ 
♦ 
♦ 
50% y 100% cada año
La densidad de transistores en CI se duplica cada 3
años
La capacidad de la DRAM se cuadruplica cada 3 años
Una gran inversión para desarrollo es posible al
mercado existente
El paralelismo es una forma natural de mejorar el
rendimiento
Cómputo Paralelo
Intro- 5
La Ley de Moore
Laboratorio de
Tecnologías de Información
♦  Crecimiento en el número de transistores de los procesadores
Cómputo Paralelo
Time
Intro- 6
Uso del Silicio
Laboratorio de
Tecnologías de Información
PE
PE
FFT
MMX
VIZ
RC5
M
Más Caché
PE
PE
PE
PE
PE
PE
Cómputo Paralelo
64-way Superscalar
PE
CISC
PE
PE
Reconfigurable
Logic
M
M
M
MPP
Vector
Procesador
Reconfigurable
Intro- 7
¿Por qué Computación Paralela?
Laboratorio de
Tecnologías de Información
♦  Porque existen aplicaciones que demandan un alto
rendimiento
♦  Se requiere tener
■  Respuesta rápida en tiempo razonable
■  Procesar grandes volúmenes de información de manera efectiva
Cómputo Paralelo
Intro- 8
El Universo es Paralelo
Laboratorio de
Tecnologías de Información
• Galaxy formation
• Planetary
movement
• Weather and
ocean patterns
• Tectonic plate drift
• Rush hour traffic
• Automobile
assembly line
• Building a space
shuttle
• Ordering a
hamburger at the
drive through.
• drift
Cómputo Paralelo
Intro- 9
Uses for Parallel Computing
♦ 
Laboratorio de
Tecnologías de Información
Historically, parallel computing has been considered to be "the high end of
computing", and has been used to model difficult scientific and engineering problems
found in the real world. Some examples:
■ 
■ 
■ 
■ 
■ 
■ 
■ 
■ 
Atmosphere, Earth, Environment
Physics - applied, nuclear, particle, condensed matter, high pressure, fusion, photonics
Bioscience, Biotechnology, Genetics
Chemistry, Molecular Sciences
Geology, Seismology
Mechanical Engineering - from prosthetics to spacecraft
Electrical Engineering, Circuit Design, Microelectronics
Computer Science, Mathematics
Cómputo Paralelo
Intro- 10
Parallel Computing Applications
Laboratorio de
Tecnologías de Información
♦ 
Today commercial applications provide an equal or greater driving force in the
development of faster computers. These applications require the processing of large
amounts of data in sophisticated ways. For example:Databases, data mining
» 
» 
» 
» 
» 
» 
» 
» 
» 
Cómputo Paralelo
Oil exploration
Web search engines, web based business services
Medical imaging and diagnosis
Pharmaceutical design
Management of national and multi-national corporations
Financial and economic modeling
Advanced graphics and virtual reality, particularly in the entertainment industry
Networked video and multi-media technologies
Collaborative work environments
Intro- 11
Simulación de Corrientes Oceánicas
Laboratorio de
Tecnologías de Información
(a) Secciones de corte
(b) Discretización espacial de un corte
♦  Se modela como mallas bidimiensionales
♦  Discretización del tiempo y del espacio
■  a una mayor resolución espacial y temporal se obtiene mayor exactitud
♦  Muchos cálculos diferentes por unidad de tiempo
■  obtención de parámetros y solución de ecuaciones
♦  Existe concurrencia entre los cálculos en el mallado
Cómputo Paralelo
Intro- 12
Algunos Números
Laboratorio de
Tecnologías de Información
♦  El Golfo de México tiene ~ 1,000 Km de litoral
♦  Simulemos 10 Km de litoral
♦  Definamos una malla de 1 Km2
■  Usemos 100 niveles de profundidad
♦  Se tienen 1000x10x100 = 106 puntos de la malla
Cómputo Paralelo
Intro- 13
Algunos Números
Laboratorio de
Tecnologías de Información
♦  Supongamos que se requieren 100 iteraciones para
alcanzar un estado estable
■  En cada instante se requieren 106x100=108 operaciones básicas
♦  Supongamos que queremos simular lo que sucederá en
un día en pasos de una hora
■  Se requieren 24x108 operaciones= 2,400 Millones de
operaciones
♦  Si cada operación toma 1 milisegundo,
■ 
■ 
■ 
■ 
2.4 millones de segundos,
40,000 minutos,
667 horas,
27.77 días
Cómputo Paralelo
Intro- 14
Algunos Problemas de Estudio
Laboratorio de
Tecnologías de Información
♦  Simulación de Corrientes Oceánicas
■  Estructura regular, cómputo científico
♦  Simulación de la Evolución de Galaxias
■  Estructura irregular, cómputo científico
♦  Producción de Imágenes Mediante Trazo de Rayos
■  Estructura regular, visualización
♦  Minería de Datos
■  Estructura irregular, procesamiento de información
♦  Simulación de circuitos VLSI
■  Estructura irregular, sistemas de eventos discretos masivos
Cómputo Paralelo
Intro- 15
¿Qué es lo común en las aplicaciones?
Laboratorio de
Tecnologías de Información
♦  Toman mucho tiempo
♦  Manejan grandes volúmenes de datos
■  El tamaño del problema es extremadamente grande
♦  Para que sean efectivas se requiere un procesamiento en
un tiempo razonable
♦  Fácilmente paralelizables
Cómputo Paralelo
Intro- 16
Why Use Parallel Computing?
♦ 
Laboratorio de
Tecnologías de Información
Save time and/or money: In theory, throwing more resources at a task will
shorten its time to completion, with potential cost savings. Parallel clusters can be built
from cheap
♦ 
Solve larger problems: Many problems are so large and/or complex that it is
impractical or impossible to solve them on a single computer, especially given limited
computer memory.
■  "Grand Challenge" (en.wikipedia.org/wiki/Grand_Challenge) problems requiring
PetaFLOPS and PetaBytes of computing resources.
■  Web search engines/databases processing millions of transactions per second
♦ 
Provide concurrency: Multiple computing resources can be doing many
things simultaneously
■  Access Grid (www.accessgrid.org) provides a global collaboration network where people from
around the world can meet and conduct work "virtually".
♦ 
Use of non-local resources: Using compute resources on a wide area
network, or even the Internet when local compute resources are scarce.
■  SETI@home (setiathome.berkeley.edu)
■  Folding@home (folding.stanford.edu)
Cómputo Paralelo
Intro- 17
Why Use Parallel Computing?
♦ 
Laboratorio de
Tecnologías de Información
Limits to serial computing: Both physical and practical reasons pose significant
constraints to simply building ever faster serial computers:
■  Transmission speeds - the speed of a serial computer is directly dependent upon
how fast data can move through hardware. Absolute limits are the speed of light
(30 cm/nanosecond) and the transmission limit of copper wire (9 cm/nanosecond).
Increasing speeds necessitate increasing proximity of processing elements.
■  Limits to miniaturization - processor technology is allowing an increasing number
of transistors to be placed on a chip. However, even with molecular or atomic-level
components, a limit will be reached on how small components can be.
■  Economic limitations - it is increasingly expensive to make a single processor
faster. Using a larger number of moderately fast commodity processors to achieve
the same (or better) performance is less expensive.
■  Current computer architectures are increasingly relying upon hardware level
parallelism to improve performance:
»  Multiple execution units
»  Pipelined instructions
»  Multi-core
Cómputo Paralelo
Intro- 18
Computadoras Paralelas
Laboratorio de
Tecnologías de Información
♦  Una computadora paralela es de manera simple:
■  Una colección de procesadores, típicamente del mismo tipo,
interconectados de alguna manera para permitir la coordinación
de sus actividades y el intercambio de datos
Procesador
Procesador
Procesador
Procesador
Procesador
Red de
Interconexión
o
Memoria
Compartida
Procesador
Procesador
Procesador
Procesador
Procesador
Cómputo Paralelo
Intro- 19
¿Qué es Computación Paralela?
Laboratorio de
Tecnologías de Información
♦  Computación Paralela
■  “es el procesamiento de información que enfatiza la manipulación
concurrente de elementos de datos pertenecientes a uno o más
procesos resolviendo un problema común” (Quinn 1994)
♦  Computadora Paralela
■  “es una computadora con múltiples procesadores capaz de
realizar cómputo paralelo” (Quinn 1994)
■  “una colección de elementos de procesamiento que se comunican
y cooperan entre sí para resolver problemas grandes de manera
rápida” (Culler 1994)
Cómputo Paralelo
Intro- 20
Algunas Preguntas Sobre Computación
Paralela
Laboratorio de
Tecnologías de Información
■  ¿qué tan grande debe ser la colección de procesadores?
■  ¿qué tan poderosos deben ser los elementos de
procesamiento?
■  ¿cómo se comunican y cooperan los elementos de
procesamiento?
■  ¿cómo se transmiten los datos entre procesadores?
■  ¿cuáles son las abstracciones y primitivas para
cooperación?
■  ¿cómo se integra todo ello para obtener mejor
rendimiento?
■  ¿cómo es posible crecer (escalar) las computadoras
paralelas?
Cómputo Paralelo
Intro- 21
¿Por qué estudiar Computación
Paralela?
Laboratorio de
Tecnologías de Información
♦  Paralelismo
■  proporciona alternativas a los relojes rápidos para mejorar el
rendimiento
■  se aplica a todos los niveles del diseño de un sistema de cómputo
■  es una perspectiva desafiante desde la cual se observa la
arquitectura de computadoras
■  es cada vez más importante para aplicaciones que demandan
alto rendimiento
■  el cómputo paralelo es inevitable
Cómputo Paralelo
Intro- 22
¿Por qué estudiar Computación
Paralela?
Laboratorio de
Tecnologías de Información
♦  El paralelismo es cada vez más importante para
aplicaciones que demandan alto rendimiento
♦  El cómputo paralelo es inevitable
♦  Desarrollar aplicaciones paralelas no es simple
♦  Evaluar sus resultados es complicado
Cómputo Paralelo
Intro- 23
Las 10 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Rank Site
Computer/Year Vendor
Cores
1
National
Supercomputing
Center in Tianjin
China
2
DOE/SC/Oak Ridge Jaguar - Cray XT5-HE Opteron 6-core
National Laboratory 2.6 GHz / 2009
United States
Cray Inc.
3
National
Supercomputing
Nebulae - Dawning TC3600 Blade, Intel
Centre in Shenzhen X5650, NVidia Tesla C2050 GPU / 2010
Dawning
(NSCS)
China
4
GSIC Center, Tokyo
Institute of
Technology
Japan
TSUBAME 2.0 - HP ProLiant SL390s G7
Xeon 6C X5670, Nvidia GPU, Linux/
73278
Windows / 2010
NEC/HP
5
DOE/SC/LBNL/
NERSC
United States
Hopper - Cray XE6 12-core 2.1 GHz /
2010
Cray Inc.
Cómputo Paralelo
Rmax GFLOP Rpeak GFLOP Power
Tianhe-1A - NUDT TH MPP, X5670
2.93Ghz 6C, NVIDIA GPU, FT-1000 8C /
186368 2566.00
2010
NUDT
4701.00
4040.00
224162 1759.00
2331.00
6950.60
120640 1271.00
2984.30
2580.00
1192.00
2287.63
1398.61
153408 1054.00
1288.63
2910.00
Intro- 24
www.top500.org
Las 10 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Rank Site
Computer/Year Vendor
Cores
Commissariat a
l'Energie Atomique
(CEA)
France
Tera-100 - Bull bullx super-node S6010/
S6030 / 2010
Bull SA
138368 1050.00
1254.55
4590.00
7
DOE/NNSA/LANL
United States
Roadrunner - BladeCenter QS22/LS21
Cluster, PowerXCell 8i 3.2 Ghz / Opteron
122400 1042.00
DC 1.8 GHz, Voltaire Infiniband/ 2009
IBM
1375.78
2345.50
8
National Institute for
Computational
Kraken XT5 - Cray XT5-HE Opteron 6Sciences/University core 2.6 GHz / 2009
Cray Inc.
of Tennessee
United States
98928
831.70
1028.85
3090.00
9
Forschungszentrum
JUGENE - Blue Gene/P Solution / 2009
Juelich (FZJ)
IBM
Germany
294912 825.50
1002.70
2268.00
10
DOE/NNSA/LANL/
SNL
United States
107152 816.60
1028.66
2950.00
6
Cómputo Paralelo
Cielo - Cray XE6 8-core 2.4 GHz / 2010
Cray Inc.
Rmax GFLOP Rpeak GFLOP Power
Intro- 25
www.top500.org
Las 500 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Number of
Processors
Count
Share %
Rmax Sum
(GF)
Rpeak Sum
(GF)
Processor
Sum
1025-2048
2
0.40 %
156,020
199,932
3,328
2049-4096
60
12.00 %
2,284,042
2,716,312
221,438
4k-8k
291
58.20 %
11,685,027
18,923,817
1,769,924
8k-16k
96
19.20 %
7,607,941
10,538,478
1,037,103
16k-32k
20
4.00 %
3,375,425
4,351,903
506,760
32k-64k
17
3.40 %
5,227,787
8,820,874
783,950
64k-128k
5
1.00 %
4,655,000
6,694,211
483,678
128k-
9
1.80 %
8,681,851
12,409,784
1,666,146
Totals
500
100%
43,673,092
64,655,310
6,472,327
Cómputo Paralelo
Intro- 26
www.top500.org
Projected Performance
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 27
www.top500.org
Resumen
Laboratorio de
Tecnologías de Información
♦  El cómputo paralelo es atractivo debido a cuestiones de
■ 
■ 
■ 
■ 
Economía,
Tecnología,
Arquitectura, y
Demanda de aplicaciones
♦  El paralelismo se puede explotar a muchos niveles
■  A nivel de instrucciones
■  Servidores multiprocesadores
■  Computadoras paralelas masivas
Cómputo Paralelo
Intro- 28
Aspectos Importantes
Laboratorio de
Tecnologías de Información
♦  Aspectos que tienen que ver con la
Computación Paralela:
■ Diseño de Computadoras Paralelas
■ Diseño de Algoritmos Eficientes
■ Métodos para Evaluar Algoritmos Paralelos
■ Programación Automática de Computadoras
Paralelas
■ Lenguajes de Programación Paralela
■ Herramientas para Programación Paralela
■ Portabilidad de Programas Paralelos
Cómputo Paralelo
Intro- 29
¿Qué hay con nuestro curso?
Laboratorio de
Tecnologías de Información
♦  El enfoque de este curso es:
■ ¿Cómo programar computadoras paralelas?
»  Para obtener mejor rendimiento
»  Para hacer un uso eficiente de los recursos
■ Es necesario estudiar
»  Los modelos de programación paralela
»  Diseño de algoritmos paralelos
»  Modelos para evaluar el rendimiento
»  Herramientas para programación paralela
Cómputo Paralelo
Intro- 30
Laboratorio de
Tecnologías de Información
Fin de la Introducción
Preguntas, comentarios, observaciones, etc.
Cómputo Paralelo
Intro- 31
Administrativos
Laboratorio de
Tecnologías de Información
♦  Página del curso:
■  http://www.tamps.cinvestav.mx/~adiaz/ParComp/ParComp2012.html
♦  Correo electrónico
■  Preguntas y comentarios: [email protected].
■  Entrega de tareas: [email protected]
♦  Recursos:
■ 
■ 
■ 
■ 
Cluster de 32 núcleos SUN en Sede Tamaulipas
Servidor de 24 núcleos AMD en Sede Tamaulipas.
Cluster de 80 núcleos Intel en Sede Tamaulipas.
Servidor con 4 tarjetas NVIDIA Tesla C2070
»  2 Procesadores Intel Xeon 6 Nucleos
»  448 Cuda cores cada una
Cómputo Paralelo
Intro- 32
Calendario
Laboratorio de
Tecnologías de Información
Entrega
Fecha
1. Resumen y reporte con la descripción del
problema y la solución mediante el algoritmo
secuencial
Enero 20
2. Versión secuencial
Febrero 03
10
3. Versión para memoria compartida
Febrero 17
15
4. Versión para CUDA
Marzo 02
15
5. Examen Parcial
Marzo 09
15
6. Versión para memoria distribuida MPI
Marzo 16
15
7. Reporte Final: Análisis de Rendimiento
Marzo 30
10
8. Examen Final
Abril 13
15
Bono: Estudio sobre algún aspecto de cómputo
paralelo (relativo al proyecto)
Abril 20
10
Cómputo Paralelo
Evaluación
5
Intro- 33
Tipo de Procesadores
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 34
Ubicación por Países
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 35
www.top500.org
Las 500 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Vendors/Systems
November 2010
Cómputo Paralelo
Intro- 36
www.top500.org
Las 500 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Cómputo Paralelo
Intro- 37
www.top500.org
Las 500 Computadoras Más Rápidas
Laboratorio de
Tecnologías de Información
Cómputo Paralelo
Intro- 38
www.top500.org
Tecnología de Interconexión
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 39
www.top500.org
Áreas de Aplicación
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 40
www.top500.org
Segmentos de Mercado
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 41
www.top500.org
Performance
Cómputo Paralelo
Laboratorio de
Tecnologías de Información
Intro- 42
www.top500.org
Lista de Estudiantes
Cómputo Paralelo
1
Tamaulipas
2
Tamaulipas
3
Tamaulipas
4
Tamaulipas
5
Tamaulipas
6
Tamaulipas
7
Tamaulipas
8
Tamaulipas
9
Zacatenco
10
Zacatenco
11
Zacatenco
12
Zacatenco
13
Zacatenco
14
Zacatenco
15
Zacatenco
16
Zacatenco
Laboratorio de
Tecnologías de Información
Intro- 43
Economía
Laboratorio de
Tecnologías de Información
♦  Los procesadores escalares no son solamente rápidos
sino también BARATOS
■  Los costos de desarrollo son decenas de millones de dólares
(5-100 típico)
■  Sin embargo, se venden muchos más microprocesadores
comparados con las supercomputadoras
■  Crucial para tomar ventaja de la inversión y usar a los
microprocesadores como el bloque básico
■  Es más barato usar dos procesadores de una velocidad x que
uno de una velocidad 2x
Cómputo Paralelo
Intro- 44
Economía
Laboratorio de
Tecnologías de Información
♦  Alternativas efectivas en costo y rendimiento
■  Arquitecturas multicore
»  Impulsados por vendedores de hardware y software (Ej. bases de
datos).
»  Impulsados por Intel y varios fabricantes
»  Un mercado potencial grande
■  Cómputo Científico
»  El mercado es muy limitado
»  Dominado por procesadores de vectores durante los 79´s
»  En los 90´s, multiprocesadores de gran escala han ido
reemplazando a las supercomputadoras
Cómputo Paralelo
Intro- 45