1
Programación y Computación paralela
Cap. 2: Modelos de programación y computación
paralelaGlen Rodríguez
[email protected] de clases de J.Demmel (U.Berkeley)
2
Temario
• Resumen de modelos de máquinas (~hardware) y modelos de programación (~software)
• Memoria compartida• Espacio de direcciones compartido• Paso de mensajes• Data en paralelo• Clusters de SMPs• Grid
• El hardware puede o no puede estar amarrado al modelo de programación
• Históricamente, muy amarrado• Hoy, lo importante es portabilidad
• Tendencias
3
Una arquitectura paralela genérica
P P P P
Interconnection Network
M M MM
°Físicamente, dónde está la memoria?
Memoria
P = procesador, M = memoria
4
Modelos de programación paralela
• Control• Cómo se crea el paralelismo?• Qué orden hay entre operaciones?• Cómo los diferentes hilos de control se sincronizan?
• Data• Qué data es privada y qué data se comparte?• Cómo se accede o comunica la data compartida en
forma lógica?
• Operaciones• Qué operaciones son atómicas (indivisibles)?
• Costos• Cómo contabilizar los costos respectivos?
5
Ejemplo sencillo
Sea la suma : • Descomposición paralela:
• Cada evaluación y cada suma parcial es una tarea.
• Asignar n/p números a cada procesador (1 al p)• Cada uno computa independientemente sus resultados
“privados” y la suma parcial.• Uno (o todos) recolectan las p sumas parciales y computa la
suma global.
Dos clases de data: • Compartida lógicamente
• Los n números originales, la suma global.
• Privada lógicamente• Las evaluaciones de las funciones.• Y las sumas parciales individuales?????
∑−
=
1
0
])[(n
i
iAf
6
Modelo de prog. 1: Memoria compartida
• Un programa es una colección de hilos de control.• Se pueden crear dinámicamente en algunos lenguajes.
• Cada hilo tiene variables privadas, ej: variables del stack local.• También hay variables compartidas, ej: variables estáticas, de bloques
comunes, del heap global.• Los hilos se comunican implícitamente escribiendo y leyendo
variables compartidas.• Los hilos coordinan sincronizando en variables compartidas.
PnP1P0
s s = ...y = ..s ...
Memoria compartida
i: 2 i: 5 Memoriaprivada
i: 8
7
Sumando con memoria compartida
HILO 1
for i = 0, n/2-1s = s + f(A[i])
HILO 2
for i = n/2, n-1s = s + f(A[i])
static int s = 0;
• Problema: “race condition” en la variables s• Una “race condition” o carrera por la data ocurre cuando:
- Dos procesadores (o 2 hilos) acceden a la misma variable, y por lo meno uno la escribe.
- Los accesos son concurrentes (no sincronizados) asíque podrían pasar simultáneamente.
8
Sumando con memoria compartida
HILO 1….computa f([A[i]) y put en reg0reg1 = s reg1 = reg1 + reg0 s = reg1
…
HILO 2…computa f([A[i]) y put en reg0reg1 = s reg1 = reg1 + reg0 s = reg1
…
static int s = 0;…(s = 27)
• Sea s=27, f(A[i])=7 en Hilo 1, y f(A[i])=9 en Hilo 2• Si el programa está bien, s debería ser 43 al final
• Pero puede ser 43, 34, o 36
• Las operaciones atómicas son lecturas y escrituras• Ose ve un número u otro, no medio número• Las sumas se hacen en registros (privados generalmente)
7 927 2734 36
3634
9
Sumando con memoria compartida (mejorado)
HILO 1
local_s1= 0for i = 0, n/2-1
local_s1 = local_s1 + f(A[i])
s = s + local_s1
HILO 2
local_s2 = 0for i = n/2, n-1
local_s2= local_s2 + f(A[i])
s = s +local_s2
static int s = 0;
• Como la suma es asociativa, se puede reordenar• La mayor parte de cómputo es en variables privadas
- La frecuencia de uso de mem. compartida baja, lo que puede mejorar la velocidad.
- Pero hay un “race condition” en el update de la v.compartida s- Se puede solucionar añadiendo locks o candados (sólo un hilo
puede usar el lock a la vez; los otros deben esperar)
static lock lk;
lock(lk);
unlock(lk);
lock(lk);
unlock(lk);
10
Modelo de máquina 1a: Shared Memory
P1
bus
$
memoria
• Todos los procesadores se conectan a una memoria compartida grande.
• Nombre típioc: Symmetric Multiprocessors (SMPs)• SGI, Sun, HP, Intel, IBM (nodos del Millennium, SP)• Chips multicore (hacía donde vamos)
• Difícil escalar a gran número de procesadores• <= 32 procesadores es típico
• Ventaja: uniform memory access (UMA)• Costo: es más barato acceder data en cache que en memoria
principal.P2
$
Pn
$
11
Problemas escalando HW de mem. compartida
• Por qué no poner más procesadores (con mayor memoria?)
• El bus de memoria se vuelve cuello de botella
• Ej. del problema: Parallel Spectral Transform ShallowWater Model (PSTSWM)
• Resultados (y gráfico) cortesía de Pat Worley del ORNL• Es un núcleo vital en modelos atmosféricos• 99% de ops. punto flotante son multiplicaciones o sumas,
que generalmente corren bien en toda CPU.• Pero se barre toda la memoria con poco reuso de
operandos���� se usa mucho bus y memoria compartida• El experimento muestra performance serial, con una
“copia” del ejecutable corriendo independientemente en varios procesadores.
• Es el mejor caso para mem.compartida: no comparte• Pero la data no cabe en los registros/cache
12From Pat Worley, ORNL
Ejemplo
• Degradación de performance es una función “suave” del número de procesos.
• No data compartida entre ellos, así que debería haber perfecto paralelismo.
• (Código corrió en 18 niveles z y varios rangos de niveles xy.)
13
Caches y Computación científica
• Caches tienden a tener peor performance en aplicaciones exigentes que operan en grandes conjuntos de datos
• Procesamiento de transacciones• Sistemas operativos• Matrices dispersas
• Códigos de programas científicos modernos usan tiling/blocking para mejorar el desempeño del caché
• Más fácil para programas con matrices densas (ej: matmul) que para matrices dispersas
• tiling y paralelismo son transformaciones similares.
14
Modelo 1b: memoria distribuida compartida
• Memoria es compartida en forma lógica, pero distribuida físicamente
• Cualquier CPU puede acceder cualquier dirección de memoria• Líneas de cache (o páginas) se pasan entre máquinas
• Ejemplo: SGI Origin• Escala a 512 (SGI Altix (Columbia) en NASA/Ames)• Limitada por la coherencia del cache– como mantener las
copias en cache de la misma dirección iguales entre si.
P1
network
$
memory
P2
$
Pn
$
memory memory
15
Problemas de performance al compartir
• Real compartir• Escrituras frecuentes a la misma variable: cuello de botella• OK para read-only o para escrituras infrecuentes • Técnica: hacer copias de un valor, uno por procesador, si se
puede en el algoritmo.
• Falso compartir• Bloqueo el cache añade complejidad• Dos diferentes variables en el mismo bloque de cache• Técnica: colocar la data usada por cada procesador en forma
contigua, o por lo menos evitar intercalado en memoria
16
Programación paralela con Hilos
Hay varias librerías de hilos• PTHREADS es el standard Posix
• Los hilos en Solaris son similares• De bajo nivel• Portable pero algo lento a veces
• OpenMP es un nuevo estándar• Soporte para programación científica en memoria
compartida• http://www.openMP.org
• P4 (Parmacs) es un viejo paquete portable• Más alto nivel que PTHREADS• http://www.netlib.org/p4/index.html
17
Operaciones básicas de hilos
• cobegin/coend
• fork/join
• cobegin cleaner, but fork is more general
cobegin
job1(a1);
job2(a2);
coend
• Las instrucciones en el bloque pueden correr en paralelo
• Se puede anidar los cobegins
• No debe faltar el coend respectivo
tid1 = fork(job1, a1);
job2(a2);
join tid1; • Funciones “forkeadas” corren en paralelo con la inicial
• join espera que todas se completen
18
Hilos y data compartida
• Variables declaradas fuera del “main” se comparten• Objetos en el heap podrían compartirse (vía paso de
punteros)• Variables en el stack son privadas: pasarse punteros
entre hilos puede colgar programas
• Esas variables privadas se establecen generalmente creando una gran estructura de “data de hilos”
• Se pasa a los hilos como argumento
19
Barrera – sincronización globlal• forkear varias copias de la misma función “work”
• SPMD “Single Program Multiple Data”
• Uso simple de barrera – todos los hilos esperan en la misma barrera
work_on_my_subgrid();
barrier;
read_neighboring_values();
barrier;
• Más complicado – barreras en ramas (o loops)if (tid % 2 == 0) {
work1();
barrier
} else { barrier }
Tipos básicos de Sincronización: Barrera
20
Tipos básicos de Sincronización: Mutexes
Mutexes – excluxión mutua ó candados• Hilos trabajan casi independientemente• Necesitan acceder estructura común de datos
lock *l = alloc_and_init(); /* shared */
acquire(l);
access data
release(l);
• Java y otros lenguajes tienen cierto tipo de sincronización
• similar a cobegin/coend vs. fork and join
• Semáforos dan garantías de “fairness” en conseguir el candado, es la misma idea que mutexes
• Candado sólo afecta al procesador usándolo: • pair-wise synchronization
21
Caso de un Sistema de Partículas
• Un sistema de partículas tiene: • Un número finito de partículas.• Que se mueven en el espacio según las leyes de Newton (F =
ma, etc.).• Tiempo continuo.
• Ejemplos:• Estrellas en el espacio con las leyes de la gravedad.• Fabricación de semiconductores con haces de electrones o de
iones.• Átomos en una molécula con fuerzas electrostáticas.• Neutrones en un reactor de fisión.• Carros en autopista.
• Muchas simulaciones combinan técnicas de simulación de partículas con técnicas de eventos discretos
• “Depredador y presa”
22
Fuerzas en un sistema de partículas
• Fuerza en cada partícula descompuesta en lejanas y cercanas:
F = F_externa + F_cercana + F_lejana
• Externa• Corrientes oceánicas en pedradores y presas marítimas• Campo eléctrico externo en haces de electrones.
• Cercana• Pedradores atraídos a presas cercanas • Choque de bolas de billar.• Fuerzas de Van der Waals en un fluido (1/r6).
• Far-field force• Atracciones de predador a cardúmenes (1/r2 )• Gravedad, electrostática• Fuerzas gobernadas por EDP elípticas.
23
Paralelismo en fuerza externas
• Lo más sencillo de implementar.• La fuerza da cada partícula es independiente de otras
partículas.• “embarrassingly parallel” o trivialmente paralelo.
• Distribuir las partículas entre los procesadores en forma pareja
• Cualquier distribución equitativa sirve.• Ni la comunicación ni la localidad son problema.
• Para cada partícula en un procesador, aplicar la fuerza externa.
24
Paralelismo en fuerzas cercanas• Fuerzas cercanas necesitan interacción � necesitan comunicación.• Fuerzas pueden depender de otras partículas cercanas:
• Ejemplo: colisiones.• Algor. simples son O(n2): chequear todos los pares para ver si chocan.
• Modelo paralelo usual es descomposición del dominio físico:• O(n2/p) partículas por procesador si la distribución es pareja.• “domain decomposition” (también es el nombre del alg. numérico)
• Desafíos:• Qué hacer con las partículas cerca de las fronteras entre procesadores?• Qué hacer con el desbalance de carga?
Se debe chequear posibles choques entre regiones
25
Paralelismo en fuerzas lejanas
• Involucran interacción todos-contra-todos y por lo tanto mucha comunicación.
• Fuerzas que dependen de todas las demás partículas:• Ejs: gravedad, plegamiento de proteínas• Los algoritmos más simples son O(n2)• La sola descomposición espacial no ayuda por que cada
partícula necesita “visitar” a todas las demás.
• Use algoritmos más sofisticados para bajar O(n2) a O(nlog n)
Se implementa rotando conjuntos de partículas.
• Mantiene procs. ocupados
• Todos los procs. Llegan a ver a todas las partículas
26
Modelo de program. 2: Paso de mensajes• Programa consiste en colección de procesos nombrados.
• Se establecen al empezar a correr el programa• Hilo de control y direcciones locales -- NO comparte data física.• Data compartida lógica se divide entre procesadores locales.
• Los procesos se comunican por pares de send/receive• Coordinación implícita en cada evento de comunicación.• MPI (Message Passing Interface) es la librería más popular
PnP1P0
y = ..s ...
s: 12
i: 2
Memoria privada
s: 14
i: 3
s: 11
i: 1
send P1,s
Red
receive Pn,s
27
Computar s = A[1]+A[2] en cada procesador°1er intento – qué podría salir mal?
Procesador 1xlocal = A[1]send xlocal, proc2receive xremote, proc2s = xlocal + xremote
Procesador 2xlocal = A[2]receive xremote, proc1send xlocal, proc1s = xlocal + xremote
°2do intento
Procesador 1xlocal = A[1]send xlocal, proc2receive xremote, proc2s = xlocal + xremote
Procesador 2xlocal = A[2]send xlocal, proc1receive xremote, proc1s = xlocal + xremote
°Si send/receive funcionara como el teléfono? Como el correo?
°Si hubiera más de 2 procesadores?
28
MPI se ha vuelto el estándar de facto para computación paralela usando paso de mensajesPros y Contras de los estándares
• MPI creó finalmente un estándar para el desarrollo de aplicaciones en la comunidad HPC →→→→ portabilidad
• El estándar MPI es el mínimo común denominador basado en tecnología de mediados de los 80s, así que puede retrasar la innovación.
Modelo de programación refleja el hardware de moda!
“I am not sure how I will program a Petaflops computer, but I am sure that I will need MPI somewhere” – HDS 2001
MPI – el estándar de facto
29
Modelo de máquina 2a: Memoria distribida
• Cray T3E, IBM SP2• Clusters de PC (Berkeley NOW, Beowulf)• IBM SP-3, Millennium, CITRIS son máquinas de
memoria distribuída, pero los nodos son SMPs.• Cada procesador tiene su propia memoria y cache pero
no puede acceder directamente a la memoria de otro procesador.
• Cada “nodo” tiene una “Network Interface” (NI, tarjeta de red o similar) para comunicación y sincronización
interconnect
P0
memory
NI
. . .
P1
memory
NI Pn
memory
NI
30
Clusters de Tflop/s
He aquí algunos ejemplos de clusters configurados de procesadores y redes separadas
• 72% del Top 500 (Nov 2005), 2 en el top 10• Dell cluster en Sandia (Thunderbird) era #4 en Top 500
• 8000 Intel Xeons @ 3.6GHz• 64 TFlops pico, 38 TFlops en Linpack• Infiniband connection network
• Walt Disney Feature Animation (The Hive) era #96• 1110 Intel Xeons @ 3 GHz• Gigabit Ethernet
• Saudi Oil Company era #107• Credit Suisse/First Boston era #108• Para más detalles usar “statistics/sublist generator” en www.top500.org
31
Modelo de máquina 2b: Internet/Grid Computing• SETI@Home: corría en 500,000 PCs
• ~1000 años de CPU al día• 485,821 años de CPU hasta el 2006
• Análisis sofisticado de señales• Datasets distribuidos desde Radio Telescopio de Arecibo
Sgte. Paso:Allen Telescope Array
32
Mod. de progr. 2b: Espacio global de direcciones
• Programa consiste en colección de hilos nombrados.• Se definen al inicio de la corrida.• Data local y compartida, como en modelo de mem.compt.• Pero la data compartida está dividida entre procesos.• Aparentemente, data remota es cara computacionalmente
• Ejs: UPC, Titanium, Co-Array Fortran• Programación en espacio global de direcciones es punto
medio entre paso de mensajes y mem. compartida.
PnP1P0 s[myThread] = ...
y = ..s[i] ...i: 2 i: 5 Private
memory
Shared memory
i: 8
s[0]: 27 s[1]: 27 s[n]: 27
33
Modelo de máq. 2c: Espacio global de direcs.• Cray T3D, T3E, X1, y cluster HP Alphaserver• Clusters construidos con Quadrics, Myrinet, o Infiniband• La NI soporta RDMA (Remote Direct Memory Access)
• NI puede acceder directamente a la memoria sin interrumpir a la CPU
• Un proces. puede hacer read/write a memoria como operación unilateral (put/get)
• No solo un load/store como en máq. de mem.compartida• Continua computando mientras espera a que la operación en
memoria finalice.
• Data remota generalmente no está en cache local.
interconnect
P0
memory
NI
. . .
P1
memory
NI Pn
memory
NIEspacio global de dirs. puede ser soportado en varios grados
34
Modelos de performance
35
PRAM – modelo de comunicación más sencillo
• Parallel Random Access Memory.• Toda operación de acceso a memoria se completa en
un período de reloj -- no hay jerarquía de memoria (irreal pero sencillo).
• OK para ver si un algoritmo tiene suficiente paralelismo.• Diseñar una estrategia para el Algoritmo paralelo: primero un
alg. PRAM, luego preocuparse de los tienmpos de memoria/comunicación (a veces funciona)
• Algo más realista: Concurrent Read Exclusive Write(CREW) PRAM.
36
Modelo de Latencia y Ancho de banda
• Tiempo para mandar mensaje de longitud n es aprox.:
• Topología se asume irrelevante.• Modelo “α−β” :
• Usualmente α >> β >> tiempo por flop.• Un mensaje largo es menos costoso que varios cortos.
• Costo de un mensaje puede ser de cientos o miles de flops.
• Lección: Se necesita un ratio computación-a-comunicación grande para ser eficiente.
Tiempo = latencia + n*costo_por_word= latencia + n/ancho_de_banda
Tiempo = αααα + n*ββββ
α +α +α +α + n∗β << ∗β << ∗β << ∗β << n∗(α + 1∗β)∗(α + 1∗β)∗(α + 1∗β)∗(α + 1∗β)
37
Parametros Alfa-Beta en Máquinas reales
• Números obtenidos empíricamente
máquina αααα ββββ
T3E/Shm 1.2 0.003T3E/MPI 6.7 0.003IBM/LAPI 9.4 0.003IBM/MPI 7.6 0.004Quadrics/Get 3.267 0.00498Quadrics/Shm 1.3 0.005Quadrics/MPI 7.3 0.005Myrinet/GM 7.7 0.005Myrinet/MPI 7.2 0.006Dolphin/MPI 7.767 0.00529Giganet/VIPL 3.0 0.010GigE/VIPL 4.6 0.008GigE/MPI 5.854 0.00872
α α α α es latencia en µsβ es ancho de banda
en µs por byte
Qué tan bien el modelo αβTiempo = αααα + n*ββββ
predice la performance real?
38
1
10
100
1000
10000
8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072
T3E/Shm
T3E/MPI
IBM/LAPI
IBM/MPI
Quadrics/Shm
Quadrics/MPI
Myrinet/GM
Myrinet/MPI
GigE/VIPL
GigE/MPI
Drop Page Fields Here
Sum of model
size
machine
Tiempo según el modelo para varios n
39
1
10
100
1000
10000
8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072
T3E/Shm
T3E/MPI
IBM/LAPI
IBM/MPI
Quadrics/Shm
Quadrics/MPI
Myrinet/GM
Myrinet/MPI
GigE/VIPL
GigE/MPI
Drop Page Fields Here
Sum of gap
size
machine
Tiempo medido experimentalmente
40
Modelo de prog. 3: Paralelismo de data
• Un solo hilo de control que maneja operaciones paralelas.• Esas operaciones paralelas se aplican a toda (o a parte
determinada) de un array.• Comunicación implícita en los operadores paralelos • Elegante y fácil de entender• Coordinación implícita: instrucciones se ejecutan sincronizadas• Similar a la forma de trabajo de Matlab en operaciones con arrays
• Desventajas: • No todos los problemas encajan en este modelo• Difícil de mapear en computadoras de grano grueso
A:
fA:f
sum
A = array de toda la datafA = f(A)s = sum(fA)
s:
41
Modelo de máquina 3a: Sistema SIMD• Un número grande de “pequeños” procesadores.
• Un solo “procesador de control” emite cada instrucción.• Cada procesador ejecuta la mima instrucción.• Algunos procesadores se pueden “apagar” en alguna
instrucciones
• Originalmente esas computadoras se especializaban en cómputo científico, pocas fabricadas (CM2, Maspar)
• Modelo de programación puede ser implementado en el compilador• Mapear paralelismo n-oper. a p procesadores, n >> p, pero es
difícil (ej., HPF)
interconnect
P1
memory
NI. . .
control processor
P1
memory
NI P1
memory
NI P1
memory
NI P1
memory
NI
42
Modelo de máq. 3b: Máquinas vectoriales
• Arquitecturas vectoriales se basan en 1 sólo procesador• Múltiples unidades funcionales• Todas efectúan la misma operación• Grado de paralelismo posible depende del hardware
• Importancia histórica• Desplazada por los MPPs en los 90s
• Ha reaparecido ultimamente• A gran escala en el Earth Simulator (NEC SX6) y Cray X1• A pequeña escala en extenciones SIMD de procesadores
• SSE, SSE2 (Intel: Pentium/IA64)• Altivec (IBM/Motorola/Apple: PowerPC)• VIS (Sun: Sparc)
• Idea clave: compilador hace parte del trabajo difícl de encontrar el paralelismo, así el HW no tiene que hacerlo.
43
Procesadores Vectoriales
• Instrucciones Vectoriales operan en un array o vector• Operaciones en registros vectoriales
• Un registro vectorial de una superc. ~32-64 elementos• El no. de elementos es mayor que la cantidad de HW paralelo,
llamados pipes o lanes, entre 2 y 4
• El HW hace una operación vectorial completa en• #elementos-por-reg-vectorial / #pipes
r1 r2
r3
+ +
…vr2…vr1
…vr3
(logicamente, hace #elemsumas en paralelo)
…vr2…vr1
(en realidad, hace#`pipes sumas en paralelo)
++ ++ ++
44
Cray X1: Arquitectura Vectorial Paralela
Cray combina varias tecnologías en el X1• Procesadores vectoriales (MSP) de 12.8 Gflop/s• Caches compartidos (inusual)• 4 nodos compartiendo hasta 64 GB de memoria• Única imagen del sistema hasta 4096 Procesadores• put/get remoto entre nodos (más rápido que MPI)
45
Arquitectura del Earth Simulator
Vectorial Paralelo• Procesadores
(vectoriales) de alta velocidad
• Alto ancho de banda de la memoria (vectorial)
• Red rápida (nuevo switch de crossbar)
Cluster de PCs no pueden igualar esta performance
46
Modelo de máq.4: Clusters de SMPs
• SMPs son las computadoras comunes más rápidas, asíque se usan como bloque básico para hacer una máquina mayor en una red
• Nombres comunes:• CLUMP = Cluster de SMPs• Máquinas jerárquicas, constelaciones
• Muchas máquinas modernas son de este tipo o similar:• Millennium, IBM SPs, ASCI machines
• Cual sería el modelo de programación #4 ???• Tratar a las computadoras como “planas”, simepre
usar paso de mensajes, aun dentro del SMP (simple, pero ignora los efectos de la jerarquía de memoria).
• Memoria compartida dentro de un SMP, pero paso de mensajes fuera del SMP.
47
- Listado de las 500 más poderosas
Computadoras en el mundo
- Benchmark: Rmax del Linpack
Ax=b, con matrices densas
- Actualizado 2 veces/año:
ISC‘xy en Alemania, Junio xy
SC‘xy en USA, Noviembre xy
- Todo disponible en www.top500.org
Size
Rat
e
TPP performance
TOP500
48
Listado TOP500 Listado TOP500 -- Data disponibleData disponible• Manufacturer Fabricante o vendedor• Computer Type Según el manual del fabricante• Installation Site Comprador• Location Ubicación, país• Year Año de instalación/último upgrade importante• Customer Segment Academic,Research,Industry,etc.• # Processors Número de procesadores• Rmax Maxmim de la performance en el LINPACK• Rpeak Performance pico teórica• Nmax Tamaño del problema para lograr Rmax
• N1/2 Tamaño del problema para lograr 50% Rmax
• Nworld Posición en el ranking TOP500
49
Los TOP 10 (Nov.2003)
Rank Manufacturer Computer Rmax
[TF/s] Installation Site Country Year
Area of
Installation # Proc
1 NEC Earth-Simulator 35.86 Earth Simulator Center Japan 2002 Research 5120
2 HP ASCI Q
AlphaServer SC 13.88
Los Alamos
National Laboratory USA 2002 Research 8192
3 Self-Made X
Apple G5, Mellanox 10.28 Virginia Tech USA 2003 Academic 2200
4 Dell Tungsten
PowerEdge, Myrinet 9.82 NCSA USA 2003 Academic 2500
5 HP Mpp2, Integrity rx2600
Itanium2, Qadrics 8.63
Pacific Northwest
National Laboratory USA 2003 Research 1936
6 Linux Networx Lightning,
Opteron, Myrinet 8.05 Los Alamos National Laboratory USA 2003 Research 2816
7 Linux Networx/
Quadrics MCR Cluster 7.63
Lawrence Livermore
National Laboratory USA 2002 Research 2304
8 IBM ASCI White
SP Power3 7.3
Lawrence Livermore
National Laboratory USA 2000 Research 8192
9 IBM Seaborg
SP Power 3 7.3
NERSC
Lawrence Berkeley Nat. Lab. USA 2002 Research 6656
10 IBM/Quadrics xSeries Cluster
Xeon 2.4 GHz 6.59
Lawrence Livermore
National Laboratory USA 2003 Research 1920
50
Los TOP 10 (Nov.2006)
Rank Manufacturer Computer Rmax
[TF/s] Installation Site Country Year Area of Installation # Proc
1 IBM BlueGene/L 280 L. Livermore Nat. Lab. USA 2005 Research 131072
2 Cray Red Storm 101 Sandia National Laboratory USA 2006 Research 26544
3 IBM eServer Blue Gene 91 IBM Thomas Watson R.C. USA 2005 IT Services 40960
4 IBM ASC Purple 75.7 L. Livermore Nat. Lab. USA 2006 Research 12208
5 IBM MareNostrum 62.6 Barcelona Supercomp. Center Spain 2006 Medicine 10240
6 Dell Thuinderbird 53 Sandia National Laboratory USA 2006 Research 9024
7 Bull Tera-10 52.8 Commisariat a l’Energie Atom. Fra. 2006 Defense 9968
8 SGI Columbia 51.8 NASA Ames Research Center USA 2004 Aerospace 10160
9 NEC/ Sun Tsubame Grid Cluster 47.3 Tokyo Inst. of Technology Jap. 2006 Research 11088
10 Cray Jaguar 43.4 Oak Ridge National Lab. USA 2006 Research 10424
51
Los TOP 10 (Jun.2009)
Rank Manufacturer Computer Rmax
[TF/s] Installation Site Country Year Area of Installation # Proc
1 IBM RoadRunner 1105 Los Alamos Nat. Lab. USA 2008 ? 129600
2 Cray Jaguar 1059 Oak Ridge Nat. Laboratory USA 2008 ? 150152
3 IBM JUGENE 825.5 Forschungszentrum Juelich Germ. 2009 Research 294912
4 SGI Pleiades 487 NASA Ames Research Center USA 2008 ? 51200
5 IBM BlueGene/L 478 Lawrance Livermore Nat.Lab. USA 2007 Medicine 212992
6 Cray Kraken XT5 463 NICS / Univ. Tennessee USA 2008 Research 66000
7 IBM BlueGene/P 458 Argonne Nat. Lab. USA 2007 Research 163840
8 Sun Ranger 433 TACC / Univ. Texas USA 2008 Res./Educat.? 62976
9 IBM Dawn 415 Lawrance Livermore Nat.Lab. USA 2009 Research 147456
10 Bull JUROPA 274 Forschungszentrum Juelich Germ. 2009 Research? 26304
52
Análisis de los reportes TOP500
• Crecimiento anual de performance cerca de 1.82
• Dos factores contribuyen casi en par en este crecimiento
• Número de procesadores crece anualmente por un factor de 1.30, y
• Performance de un procesador crece en 1.40 vs. 1.58 según la Ley de Moore
1.3 x 1.4 = 1.82
Strohmaier, Dongarra, Meuer, and Simon, Parallel Computing 25, 1999, pp1517-1544.
53
Clusters de PCs: Beowulf
• Un experimento en sistemas de cómputo paralelo
• Estableció una visión de HPC de bajo costo
• Efectividad demostrada de clusters de PC para algunas (no todas) las clases de aplicaciones
• Brindó software para el networking
• Mostró logros a la comunidad en general (buena publicidad)
• Tutoriales y libros• Estándares diseñados
• Estándares trajeron: libros, gente entrenada, SW … ciclo virtuoso
Según Gordon Bell
54
Sumario
• Históricamente, cada computadora paralela fue única, junto a su modelo de programación y de lenguaje.
• Se debía descartar el software y comenzar de cero si se cambiaba por una nueva máquina.
• Ahora se separa el modelo de programa del modelo de la máquina, así que se puede escribir código correctoque corre en muchos tipos de máquina.
• MPI es la opción más portable ahora, pero tedioso a veces.
• Escribir código portable y rápido necesita “tuning” o afinamiento según la arquitetcura de máquina.
• Desafío en el diseño de algoritmos es hacer el proceso fácil (metodologías, herramientas, templates).
• Ej.: escoger un tamaño de bloque, no reescribir todo el algoritmo.