Download Slide 1 - Academia Multicore

El reto de paralelismo y Multicore
Intel® Software College
Motivación
Se requiere mejor
rendimiento
Primera PC
1981
Windows
Mouse
Monitor Color
1980
1990
Internet
Multimedia
Joystick
1995
Multitasking
Menor consumo de
energía
Wireless
Movilidad
Plug’n Play
Juegos
Video Input
PVR
2004
2006
2
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Ley de Moore’s
3
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
¿Quién se Preocupa por la Jerarquía de
Memoria?
Hueco Procesador-Memoria DRAM (latencia)
Rendimiento
1000
CPU
“Ley de Moore”
µProc
60%/año.
(2X/1.5años)
Hueco de rendimiento
Procesador-Memoria
(crece 50% / año)
100
10
“¿Ley Menor?
DRAM
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
1
DRAM
9%/año.
(2X/10 yrs)
Time
4
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Implicaciones de la ley de Moore’s
• La velocidad de la memoria no está incrementando tan
rápido como la velocidad de los microprocesadores
•
~1980 – i486 CPU toma ~8 ciclos de reloj (cpc
acceder memoria
• ~1990 - Intel Pentium toma ~224 cpc
•
) para
cloks per cycle
Consumo de energía
•
•
Intel Pentium ~3 millones de transistores
Intel Itanium 2 ~1 mil millones de transistores
• A estaLa
tasa
tendremos más
calor por centímetro
aproximación
multi-core
mejora el
cuadrado que la superficie del sol
rendimiento usando la estrategia
“divide y vencerás”
5
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Rendimiento / Consumo
Rendimiento
Potencia Requerida
1.00x
Máxima Frecuencia
Relative single-core frequency and Vcc
6
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
“Over-clocking”
1.73x
Rendimiento
Potencia Requerida
1.13x
1.00x
Over-clocked Máxima Frecuencia
(+20%)
Relative single-core frequency and Vcc
7
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
“Under-clocking”
1.73x
Rendimiento
Potencia Requerida
1.13x
1.00x
0.87x
0.51x
Over-clocked Máxima Frecuencia
(+20%)
Under-clocked
(-20%)
Relative single-core frequency and Vcc
8
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Rendimiento Multi-Core y Consumo de Energía
Dual-Core
1.73x
Rendimiento
1.73x
Potencia Requerida
1.13x
1.02x
1.00x
Over-clocked Máxima Frecuencia
(+20%)
Dual-core
(-20%)
Relative single-core frequency and Vcc
9
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Aplicaciones en Procesadores de un solo
Núcleo
Incremento en la frecuencia de reloj produce un incremento
en el rendimiento de la aplicación
• La aplicación gana, no se tomó acción al respecto
Avances en la tecnología de compiladores impulsan el
rendimiento
…2001
• Re-construye tu aplicación para aprovechar los
beneficios adicionales de rendimiento
El cache mejora el rendimiento
• Las aplicaciones se benefician con un pequeño o ningún
cambio
El Rendimiento de la Aplicación Mejora como
Incrementan los GHz (frecuencia de reloj)
10
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Procesadores Multi-Core
(comenzando con Dual-Core)
Varios núcleos del procesador disponibles
• Replicar todo el núcleo del procesador en un solo chip
mejora el rendimiento de una aplicación paralelizada
• Evolución natural de HT
• El rendimiento mejora para aplicaciones paralelizadas
Avances en la tecnología del compilador continúan
impulsando el rendimiento
• OpenMP, Auto-parallelización, los compiladores incorporan
…2005, 2006, las últimas innovaciones del procesador
2007,…
El Cache y la frecuencia de reloj no influyen en el
rendimiento de la aplicación
• El cache y la frecuencia del reloj siguen contribuyendo
La Mejora en el Rendimiento es
lograda por medio de la Paralelización
11
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Rendimiento
Rendimiento a Través de “Multi-Cores”
3X
2004
2000
2008+
Normalized Performance vs. Initial Intel® Pentium® 4 Processor
12
Copyright © 2006, Intel Corporation. All rights reserved.
Intel
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its Source:
subsidiaries
in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Rendimiento a Través de “Multi-Cores”
Rendimiento
MULTI-CORE
Aquí estamos
10X
SINGLE CORE
3X
2009+
2004
2000
Pronóstico
Normalized Performance vs. Initial Intel® Pentium® 4 Processor
13
Copyright © 2006, Intel Corporation. All rights reserved.
Intel
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its Source:
subsidiaries
in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Many-Core
La ruta hacia
“Many cores”
Multi-Core
Dual-Core
Hyper-threading
Standard core
14
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Resumen
La velocidad del procesador (GHz) ya no es el principal
contribuyente al rendimiento de las aplicaciones
Multi-Core hace que haya disponibles varios procesadores
(núcleos/cores) en un solo chip.
• Una aplicación propiamente diseñada puede escalar incrementos
en el rendimiento como el número de núcleos incremente
Las plataformas Multi-Core están aquí!
2005
2006**
2007**
Rendimiento Desktop* Lanzamiento >70%
>90%
Rendimiento Móvil*
Lanzamiento >70%
>90%
Server
Lanzamiento >85%
~100%
* Mobile & Desktop Pentium
Multi-Core es una transición de la tecnología mayor para
los desarrolladores de aplicaciones
15
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Multicores – No hay almuerzo gratis
16
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Estableciendo el Problema
• Algunos en la industria tienen la percepción de que la
paralelización de aplicaciones no es necesaria para sacar el
máximo provecho de multi-core, ya que algunos creen de que
el planificador del SO hace todo el trabajo para ellos.
Por las últimas décadas el software ha sido
desarrollado como una aplicación de un solo
hilo (serial)
Los hilos no han sido comunmente usados para
tareas concurrentes, ejemplo: eventos de GUI
17
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Hechos del Paralelismo
•El paralelismo solo era usado para aplicaciones de alto
rendimiento (No más)
•El cómputo paralelo no se va a detener
•Desarrollar aplicaciones paralelas no es simple
•Evaluar el rendimiento en paralelo es complejo
18
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Implicaciones del Paralelismo
• Diseño de Computadoras Paralelas
• Diseño de Algoritmos Eficientes
• Evaluación de Algoritmos Paralelos
• Desarrollo de lenguajes de programación Paralelos
• Desarrollo de Utilerías de Programación Paralela
• Portabilidad de aplicaciones paralelas
19
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Máquinas Paralelas:
Principalmente hay dos clases de máquinas
paralelas:
• Multicomputadoras
• Paso de mensajes, sistemas de memoria
distribuida, redes de estaciones de trabajo,
clusters, NUMA (non-uniform memory access),
etc.
• Multiprocesadores
• Multiprocesadores con memoria compartida,
multiprocesamiento simétrico, UMA (uniform
memory access systems).
20
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Arquitectura de Memoria Compartida
Cualquier dirección de memoria es accesible desde
cualquier procesador/núcleo: dirección única por posición
de memoria
Bus
Cache
Procesadores y Núcleos
Bancos de Memoria
21
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Estructura de un Proceso
Código
Heap
IP
Stack
Rutinas de Int.
Descriptores
Proceso
22
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Hilos
IP
Hilo
Código
Heap
Stack
IP
Rutinas de Int.
Stack
Descriptores
Hilos
23
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Visión de Alto-Nivel del Paralelismo
PROCESO
Una instancia de un programa en
ejecución con los estados
necesarios para permanecer en
ejecución – la mayoría de las
aplicaciones son procesos
Crear un nuevo proceso
ser costoso en CPU, se ll
tiempo y memoria
HILO
hilos pueden
arse sin replicar todo
roceso
Una instancia de subtareas
subdivididas para ejecutarse en
paralelo – muchas aplicaciones se
dividen en múltiples hilos
24
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Tipos de Paralelismo
por Funcionalidad
Asignar hilos a funciones separadas hechas por la aplicación
• El método más fácil desde que sobreponer tareas es obvio
(ejemplo esperar actualización de una Interfaz de Usuario)
• Por lo general, mejorar la capacidad de respuesta y funcionalidad
• A menudo se hace a través de un modelo de programación por
descomposición funcional
por
Rendimiento
Paralelizar para mejorar tiempo de retorno o tasa de trabajos
• Más difícil ya que los desarrolladores necesitan tener un
conocimiento profundo de flujo de datos y estructuras de datos
• Por lo general, mejorar el desempeño en general
• Usualmente se hace mediante un modelo de programación de
descomposición de datos
25
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Flujo de Tráfico en una Autopista
La Analogía
Imagina…
Una Autopista  Procesador Multi Core
Con Muchos Carriles  Núcleo
Donde los Vehículos son Hilos de una Aplicación
Y la Longitud de un Vehículo es el Tiempo de
Ejecución de un Hilo
Y todo el Flujo de Tráfico es la Ejecución del
Procesador
26
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Flujo de Tráfico en una Autopista
La Analogía
4 Carriles = 4 Núcleos
La línea final representa la ejecución
Los vehículos son hilos de una aplicación
27
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Flujo de Tráfico en una Autopista
Partiendo Procesos
O… Un
Unos
Un
bonche
solo
pocos
hilo…
de
hilos
grandes,
hilos
cortos
de cómputo
intensivo, hilos
independientes
dependientes y quizá
unos cuantos hilos
cortos independientes
o hilos más cortos
28
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Analogía con el Tráfico de una Autopista
¿Qué se puede lograr con el paralelismo?
Vamos
a que
dividir
La
Suponer
Ahora,
carga
llega
en
4 trocas
más
tenemos
podemos
mucho
más
un
poner
pequeñas…
convoy
una
rápido!
troca
largo
en de
carga:
cada
carril…
troncos
de madera…
Cuatro
hilos
Una aplicación
independientes
no paralelizada
Explotar
Resultado:
los
múltiples
Mejora
la tasa
núcleos…
de
trabajos!
29
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Analogía con el Tráfico de una Autopista
Vehículos en la autopista…
Esos
Vehículos
vehículos
(Hilos)
deldel
de
mismo
diferentes
mismo
color
color
colores
(hilos
son dependientes)
dependientes
son independientes
entre
y
vehículos
entre ellos…
ellos…
y por
grandes
lo
y por
tanto
(hilos
lo no
tanto
se
grandes
pueden
pueden
nomoverse
mover
optimizados)
enen
paralelo
paralelo
generan
enen
otros
carriles
otros carriles
carriles,
vacíos
deben
(ser
(utilización
seguirse
ejecutados
entre
ineficiente
paralelamente
ellos. del procesador)…
en múltiples
núcleos)
30
Ejecuta
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Analogía con el Tráfico de una Autopista
Planificación del Sistema Operativo
Planificador del
SO (Selecciona
el carril)
El Sistema Operativo no puede
una aplicación en hilos…
4
3
2
1
Debe
El
SO 2
Carril
1 la
esperar
piensa
troca.
… solo puede planificar hilos exis
31
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Analogía con el Tráfico de una Autopista
Escenario Ejemplo
Vehículos grandes (hilos grandes) y vehículos del mismo color
(hilos dependientes) causan tráfico torpe.. Los carros más
pequeños (hilos pequeños independientes) permiten un flujo
más rápido…
32
Ejecuta
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Analogía con el Tráfico de una Autopista
Resumen
vidir un hilo grande en n hilos más pequeños e
dependientes permite que el SO los planifique en
erentes núcleos… incrementando la tasa de
bajos.
Igual que en la autopista, los vehículos grandes
causan que el tráfico se entorpezca… Los pequeños
permiten un flujo más rápido…
SO ayuda a manejar el tráfico, pero el desarrollador
asegura que cada carril pueda tener suficiente
áfico para que el SO lo pueda planificar, permitiendo
mayor tasa de trabajos de carga (datos).
33
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Aceleración
La concurrencia está limitada por la naturaleza de la aplicación
Es el acuerdo más importante
Si s es la fracción de trabajo serial intrínsico
El tiempo de computación usando p núcleos:
- s)ts
(
1
sts +
p
34
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Tiempo en Paralelo:
T
p
= st
+
(1 - s )t
s
s
p
ts
sts
(1-s)ts
Sección Serial
Sección Paralela
p núcleos
(1-s)ts/p
tp
35
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Ley de Amdahl
Tp
= st +
s
p
S( p) =
Aceleración
S ( p) =
( 1 - s ) ts
t
s
st + (1 - s)t
s
s
p
=
ts
tp
p
1 + ( p -1) s
Si s es la fracción de tiempo secuencial, entonces, la
aceleración es  1/s
limp  S ( p ) =
1
s
36
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Ley de Amdahl
37
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Speedup and Efficiency
Intel® Software College
Aceleración (Simple)
Medir que tanto se acelera la ejecución de cómputo vs. el mejor
código serial
• Tiempo serial dividido entre el tiempo paralelo
Ejemplo: Pintar una barda de tablitas
• 30 minutos de preparación (serial)
• Un minuto para pintar una tabla
• 30 minutos para limpiar (serial)
Por lo tanto, 300 tablas toman 360 minutos (tiempo serial)
38
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Speedup and Efficiency
Intel® Software College
Calculando Aceleración
Numero de
pintores
Tiempo
Aceleración
1
30 + 300 + 30 = 360
1.0X
2
30 + 150 + 30 = 210
1.7X
10
30 + 30 + 30 =
90
4.0X
100
30 + 3 + 30 =
63
5.7X
Infinito
30 + 0 + 30 =
60
6.0X
Illustra la ley de
Amdahl
La aceleración
potencial está
restringida por la
porción serial
Que pasa si el dueño de la barda usa un spray para pintar
300 tablas en una hora ?
• Mejor algoritmo serial
• Si no hay sprays disponibles para varios pintores, cuál es la
máxima paralelización?
39
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Speedup and Efficiency
Intel® Software College
Eficiencia
Medir que tan efectivamente los recursos de cómputo
están ocupados
• Aceleración dividida entre el número de hilos
• Expresada como porcentaje promedio de tiempo no ocioso
Numero de
pintores
Tiempo
Aceleración
Eficiencia
1
360
1.0X
100%
2
30 + 150 + 30 = 210
1.7X
85%
10
30 + 30 + 30 =
90
4.0X
40%
100
30 + 3 + 30 =
63
5.7X
5.7%
Infinito
30 + 0 + 30 =
60
6.0X
Muy baja
40
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
Aceleración + Sincronización
S
p
41
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.
Intel® Software College
42
Copyright © 2006, Intel Corporation. All rights reserved.
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States or other countries. *Other brands and names are the property of their respective owners.