Introdução à Computação
Paralela e Ambientes de
Grade
Inês de Castro Dutra
Departamento de Ciência de Computadores
Universidade do Porto
[email protected]
1
Grades Computacionais
 Idéia é utilizar computadores
 independentes
 geograficamente distantes
 Diferenças: clusters x grids
 heterogeneidade (nós muito diferentes)
 alta dispersão geográfica (escala mundial)
 compartilhamento (inexistente)
 múltiplos domínios administrativos
 controle totalmente distribuído
2
Grades Computacionais
 Componentes
 PCs, SMPs, MPPs, clusters
 controlados por diferentes entidades 
diversos domínios administrativos
 Não têm uma imagem única do sistema
 Sistema não dedicado
 Aplicação deve estar preparada para:
 dinamismo
 variedade de plataformas
3
Grades Computacionais
 Escalonamento de aplicação
 recursos controlados por vários escalonadores
distintos que devem decidir:
 quais recursos serão utilizados pela aplicação
 quais tarefas cada um destes recursos realizará
 submeter solicitações aos escalonadores
apropriados  tarefa do escalonador de
aplicações
 Grids: duas camadas de escalonamento
4
Grades Computacionais
usuário
usuário
Escalonador
de Aplicação
Escalonador
de Recursos
MPP
usuário
Escalonador
de Aplicação
Escalonador
de Recursos
SMP
Escalonador
de Recursos
Cluster
SMP
5
Grades Computacionais
Workstation
MPP
Computador
convencional
Cluster
Workstation
Internet
SMP
Servidor
Cluster
SMP
Servidor
MPP
6
Grades Computacionais
 Middleware: Globus, Condor, OurGrid,
gLite
 usuário pode obter poder computacional
de forma transparente
 sob demanda
 Soluções:
 evitam problemas no nível do usuário
 introduzem novas abstrações que facilitam
o uso da grade
7
Top500 Supercomputer
Site
Computer
Procs
Year
Rmax
Rpeak
DOE/NNSA/LLNL
United States
BlueGene/L - eServer Blue Gene Solution
IBM
131072
2005
280600
367000
IBM Thomas J. Watson Research Center
United States
BGW - eServer Blue Gene Solution
IBM
40960
2005
91290
114688
DOE/NNSA/LLNL
United States
ASC Purple - eServer pSeries p5 575 1.9 GHz
IBM
10240
2005
63390
77824
NASA/Ames Research Center/NAS
United States
Columbia - SGI Altix 1.5 GHz, Voltaire Infiniband
SGI
10160
2004
51870
60960
Sandia National Laboratories
United States
Thunderbird - PowerEdge 1850, 3.6 GHz, Infiniband
Dell
8000
2005
38270
64512
Sandia National Laboratories
United States
Red Storm Cray XT3, 2.0 GHz
Cray Inc.
10880
2005
36190
43520
The Earth Simulator Center
Japan
Earth-Simulator
NEC
5120
2002
35860
40960
Barcelona Supercomputer Center
Spain
MareNostrum - JS20 Cluster, PPC 970, 2.2 GHz, Myrinet
IBM
4800
2005
27910
42144
ASTRON/University Groningen
Netherlands
Stella - eServer Blue Gene Solution
IBM
12288
2005
27450
34406.4
Oak Ridge National Laboratory
United States
Jaguar - Cray XT3, 2.4 GHz
Cray Inc.
5200
2005
20527
24960
Rmax Maximal LINPACK performance achieved
Rpeak Theoretical peak performance GFlopss
8
Resumindo...
 Plataformas de Execução Paralela
Características
Conectividade
Heterogeneidade
Compartilhamento
Imagem do Sistema
Escalabilidade
SMPs
excelente
nula
não
única
10
MPPs
muito boa
baixa
não
comum
1.000
NOWs
boa
média
sim
comum
1.000
Grids
média/ruim
alta
sim
múltipla
100.000
9
Programação Paralela
10
Programação Paralela
 Paralelismo explícito
 Linguagens (SR)
 Bibliotecas (OpenMP, MPI)
 Suporte de Sistema (lib do SO)
Paralelismo implícito
 Compiladores paralelizadores (F90, HPF)
 Linguagens declarativas (Prolog)
 Sistemas híbridos (Concurrent Logic)
11
Modelos de Programação Paralela
 Modelos
 Memória Compartilhada
 Passagem de Mensagem
 Paradigmas
 SPMD (Single Program Multiple Data)
 MPDM (Multiple Program Multiple Data)
12
Ambientes de Programação Paralela
 Clusters
 Memória Compartilhada
 Software DSM (Click, HLRC, TreadMarks)
 Passagem de Mensagens
 PVM
 MPI
 OpenMP
13
Ambiente: PVM
 Modelo de programação
 passagem de mensagem
 software:
 biblioteca no nível do usuário (C/Fortran)
 protocolo TCP ou UDP
 Modelos de paralelismo: SPMD ou MPDM
14
Ambiente: PVM
 Primitivas para:
 criação e gerenciamento de processos
 troca explícita de mensagens
 primitivas de PVM possuem o prefixo
PVM_
 Sistemas computacionais:
 homogêneos ou heterogêneos
15
Ambiente: MPI
 Padronização a partir do PVM
 Modelo de programação:
 passagem de mensagem
 software:
 biblioteca no nível do usuário (C/Fortran)
 protocolo TCP ou UDP
 Modelos de paralelismo: SPMD ou MPDM
16
Ambiente: MPI
 Primitivas para:
 criação e gerenciamento de processos
 troca explícita de mensagens
 primitivas de MPI possuem o prefixo
MPI_
 Sistemas computacionais:
 homogêneos ou heterogêneos
 Corrige algumas deficiências técnicas do PVM
17
Ambiente: OpenMP
 Busca por uma padronização de facto
 Organização independente envolvendo
 fabricantes de computadores (SGI,
Compaq, Hewllet-Packard, Intel, IBM, Kuck
& Associates, Sun , U.S. Department of
Energy ASCI Program)
 desenvolvedores de aplicações e vendedores
18
Ambiente: OpenMP
 Modelo de programação:
 semelhante ao modelo seqüencial
 desenvolvido para dar suporte ao passo final da
implementação de um algoritmo paralelo
 linguagens: C, C++ e Fortran
 expressão do paralelismo
 diretivas incluídas no código fonte (comentários
em Fortran e #pragmas em C ou C ++)
 em conjunto com rotinas de bibliotecas
19
Programação Paralela
 Grades Computacionais
 Globus Toolkit
 Condor
 OurGrid
 gLite
20
Globus Toolkit
Globus Toolkit v4
www.globus.org
Data
Replication
Credential
Mgmt
Replica
Location
Grid
Telecontrol
Protocol
Delegation
Data Access
& Integration
Community
Scheduling
Framework
WebMDS
Python
Runtime
Community
Authorization
Reliable
File
Transfer
Workspace
Management
Trigger
C
Runtime
Authentication
Authorization
GridFTP
Grid Resource
Allocation &
Management
Index
Java
Runtime
Security
Data
Mgmt
Execution
Mgmt
Info
Services
Common
Runtime
21
Sistema Condor
Resource
Condor
Access Control
Match-Making
Request Agent
Sistema Condor
www.wisc.edu/condor
Resource Owner
System Administrator
Customer/User
Application RM
Application
Distributed
Scalable
Adaptable
Customizable
22
Sistema Condor
= Process Spawned
= ClassAd
Communication
Pathway
Central Manager (Frieda’s)
master
startd
schedd
negotiator
collector
startd
schedd
master
startd
Cluster Node
master
startd
Sistema Condor
Desktop
master
Cluster Node
Desktop
master
startd
schedd
www.wisc.edu/condor
23
Sistema Condor-G
 Globus
 middleware deployed
across entire Grid
 remote access to
computational resources
 dependable, robust data
transfer
 Condor
 job scheduling across
multiple resources
 strong fault tolerance with
checkpointing and
migration
 layered over Globus as
“personal batch system”
for the Grid
www.wisc.edu/condor
24
Sistema Condor-G
Job Submission Machine
Job Execution Site
Globus
GateKeeper
Persistant
Job Queue
Fo
rk
End User
Requests
Globus
JobManager
rk
Fo
Condor-G
Scheduler
Globus
JobManager
Submit
Submit
Fork
Site Job Scheduler
(PBS, Condor, LSF, LoadLeveler, NQE, etc.)
Condor-G
GridManager
GASS
Server
Job X
Job Y
25
www.wisc.edu/condor
Sistema OurGrid
 Aplicações Bag-of-Tasks (BoT)
 Compartilhamento de recursos peer-to-peer
 Principais componentes
 OurGrid peer:
 Network of Favors
 mecanismo de alocação autônomo e totalmente
descentralizado
 MyGrid broker: escalonamento
 SWAN security service: máquina virtual de
proteção
www.ourgrid.org
26
Sistema OurGrid
Ourgrid
www.ourgrid.org
27
gLite
 Utiliza funções do Globus
 Estrutura: BDII, UI, RB, WN, CE, SE, IE
 Aplicações definidas utilizando JDL
 Middleware adotado pelo projeto de grid
europeu (EGEE)
 Outros componentes:
 AMGA
 LFC
 API semelhante a de outros RMSs
www.ourgrid.org
28
Desenvolvimento de Programas
Paralelos
29
Metodologia para Programação Paralela
 Metodologia é (quase) independente da
máquina
 Estágios:
 particionamento
 comunicação
 aglomeração
 mapeamento
30
Particionamento
 Divisão da aplicação em tarefas em menores
 Decomposição do domínio da aplicação
 Objetivos aumentar:
 concorrência
 localidade de referência
31
Comunicação
 Troca de informações entre processos
 Sincronização entre processos
 Definir:
 estruturas de dados e
 algoritmos apropriados
32
Aglomeração
 Avaliação de requisitos de desempenho e custo
 Objetivos se necessário:
 combinar tarefas para reduzir custos de
comunicação
 tarefas maiores podem melhorar o
desempenho, mesmo que diminua a
concorrência
33
Mapeamento
 Cada tarefa é atribuída a um processador
 Estático ou dinâmico
 Objetivos:
 maximizar a utilização dos processadores
 minimizar os custos de comunicação
 balanceamento de carga
34
Metodologia para Programação Paralela
Problema
Particionamento
Comunicação
Aglomeração
Mapeamento
35
Métricas de Desempenho
36
Métricas de Desempenho
Speedup = grau de melhora de desempenho
Eficiência = porção utilizada da capacidade
Redundância = aumento da carga qdo em p processadores
Utilização = utilização dos recursos durante computação
Qualidade = importância de utilizar processamento paralelo
37
Métricas de Desempenho
Speedup s(p) = T(1) / T(p),
onde T(1) = tempo do melhor algoritmo sequencial possível e
p = número de processadores
Eficiência e(p) = s / p = T(1) / (p T(p))
Redundância r(p) = O(p) / O(1),
onde O(p) = número total de ops
em máquina com p processadores
Utilização u(p) = r(p) e(p) = O(p) / (p T(p))
Qualidade q(p) = (s(p) e(p)) / r(n) = T3(1) / (p T2(p) O(p))
38
Métricas de Desempenho
• Escalabilidade
• Modelos de aplicações
• Limites algorítmicos
• Limites arquiteturais
39
Modelos de Aplicações
• Carga fixa = máquinas maiores para
computar + rápido
• Tempo fixo = máquinas maiores para
problemas maiores
• Memória fixa = máquinas maiores para
problemas que precisam de + memória
40
Limites Algorítmicos
•
Falta de paralelismo
•
Freqüência de sincronização
•
Padrão de comunicação/acesso
• Escalonamento deficiente
41
Limites Arquiteturais
•
Latência/banda de comunicação
•
Latência/banda de E/S
•
Overhead de sincronização
• Overhead de coerência
• Capacidade de memória
42
Métricas de Desempenho
 Lei de Amdahl:
Speedup: s = T(1)/T(p)
Trabalho total: c = Ts + Tp = T(1)
T(p) = Ts + Tp/p
s = (Ts + Tp) / (Ts + Tp/p) = c / (Ts + Tp/p)
s = c/Ts qdo p tende a infinito
43
Métricas de Desempenho
 Lei de Gustafson:
Tempo total: c = Ts + Tp
Trabalho total: t = Ts + Tp
Scaled Speedup ss = t / c
ss = (Ts + p * Tp) / (Ts + Tp)
= (Ts + p * Tp) / c = (Ts + p * (c - Ts)) / c
= p + (Ts * (1-p)) / c, linear em Ts
44
Métricas de Desempenho
 Speedup superlinear:
• Overhead reduzido (escalonamento, por exemplo)
• Mais memória/cache
• Tolerância a latência
• Randomização (problemas de otimização)
• Problemas que possuem múltiplas soluções
45
Exemplos
46
Modelo de Programação Seqüencial
Modelo mais simples
Paralelismo implementado pelo compilador ou
software + básico
for i = 1 to N
a[i] = 1
Paralelismo explorado pelo compilador
(p.e.: F90, HPF ou runtime paralelo)
47
Modelo de Programação Paralelo baseado em
Memória Compartilhada
doall i = 1 to N
a[i] = 1
for j = 1 to NPROCS-1
fork(compute,j)
compute(0)
lock(mutex)
x=x+1
unlock(mutex)
48
Modelo de Programação Paralelo baseado em Troca de
Mensagens
Proc pid: (N é o tamanho do problema)
chunk = N/NPROCS
for j = pid*chunk to (pid+1)*chunk-1
a[i] = 1
send(dest,&a[pid*chunk],chunk*sizeof(int))
49
Programando em MC
50
Exemplo usando Posix threads (thread do_work)
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NTHREADS 4
#define ARRAYSIZE 1000000
#define ITERATIONS ARRAYSIZE / NTHREADS
double sum=0.0, a[ARRAYSIZE];
pthread_mutex_t sum_mutex;
void *do_work(void *tid) {
int i, start, *mytid, end;
double mysum=0.0;
/* Initialize my part of the global array and keep local sum */
mytid = (int *) tid;
start = (*mytid * ITERATIONS);
end = start + ITERATIONS;
printf ("Thread %d doing iterations %d to %d\n",*mytid,start,end-1);
for (i=start; i < end ; i++) mysum = mysum + a[i];
/* Lock the mutex and update the global sum, then exit */
pthread_mutex_lock (&sum_mutex);
sum = sum + mysum;
pthread_mutex_unlock (&sum_mutex);
pthread_exit(NULL);
}
51
Exemplo usando Posix threads (main thread)
int main(int argc, char *argv[]) {
int i, start, tids[NTHREADS];
pthread_t threads[NTHREADS];
/* Pthreads setup: initialize mutex. Pass each thread its loop offset */
pthread_mutex_init(&sum_mutex, NULL);
for (i=0; i<NTHREADS; i++) {
tids[i] = i;
pthread_create(&threads[i], NULL, do_work, (void *) &tids[i]);
}
/* Wait for all threads to complete then print global sum */
for (i=0; i<NTHREADS; i++) {
pthread_join(threads[i], NULL);
}
printf ("Done. Sum= %e \n", sum);
sum=0.0;
for (i=0;i<ARRAYSIZE;i++) sum = sum + a[i];
printf("Check Sum= %e\n",sum);
/* Clean up and exit */
pthread_mutex_destroy(&sum_mutex);
pthread_exit (NULL);
}
52
Exemplo usando Processos (cliente/servidor)
#include <sys/ipc.h>
#include <sys/shm.h>
#define SHMSZ 27
main() {
char c, *shm, *s;
int chave = 5678, shmid;
shmid = shmget(chave, SHMSZ, (IPC_CREAT|0666));
shm = (char *) shmat(shmid, NULL, 0);
s= shm; /* escreve info em memória */
for (c=’a’; c < =’z’; c++)
*s++= c;
*s = ’\0’;
/* espera até que outro proc altere o 1o. char em memória */
while (*shm != ’*’) sleep(1);
shmdt(shmid); /* liberta segmento */
exit(0);
}
53
Exemplo usando Processos (cliente/servidor)
#include <sys/ipc.h>
#include <sys/shm.h>
#define SHMSZ 27
main()
{
char c, *shm, *s;
int chave= 5678, shmid;
shmid= shmget(chave, SHMSZ, 0666);
shm= (char *) shmat(shmid, NULL, 0);
for (s=shm; *s!=’\0’; s++) /* lê da memória compartilhada*/
putchar(*s);
putchar(’\n’);
*shm=’*’; /* alterar o 1o. caracter em memória */
exit(0);
}
54
Exemplo usando OpenMP
PROGRAM HELLO
PRINT *, “Hello parallel world from threads:”
!$OMP PARALLEL
PRINT *, OMP_GET_THREAD_NUM ( )
!$OMP END PARALLEL
PRINT * , “Back to the sequential world.”
STOP
END
55
Exemplo usando OpenMP: saída
 Saída do programa HELLO
Hello parallel world from threads:
1
3
0
2
Back to the sequential world.
56
Programando com Troca de Msgs
usando MPI
57
Exemplo: usando MPI
#include <stdio.h>
#include <string.h>
#include "mpi.h"
main(int argc, char* argv[]) {
int
my_rank;
/* rank of process
*/
int
p;
/* number of processes */
int
source;
/* rank of sender
*/
int
dest;
/* rank of receiver */
int
tag = 0;
/* tag for messages */
char
message[100]; /* storage for message */
MPI_Status status;
/* return status for receive */
/* Start up MPI */
MPI_Init(&argc, &argv);
/* Find out process rank */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Find out number of processes */
MPI_Comm_size(MPI_COMM_WORLD, &p);
if (my_rank != 0) {
/* Create message */
sprintf(message, "Greetings from process %d!", my_rank);
dest = 0;
/* Use strlen+1 so that '\0' gets transmitted */
MPI_Send(message, strlen(message)+1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
} else { /* my_rank == 0 */
for (source = 1; source < p; source++) {
MPI_Recv(message, 100, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status);
printf("%s\n", message);
}
}
/* Shut down MPI */
MPI_Finalize();
} /* main */
58
Exemplo: SOR (Successive Over-Relaxation)
• Computação sobre uma matriz
• Grupo de linhas consecutivas para cada
processador
• Cada elemento calculado usando vizinhos
• Comunicação nas bordas
59
Exemplo: SOR (Successive Over-Relaxation)
•Usando modelo de memória compartilhada:
for num_iters
for num_minhas_linhas
compute
barreira
• Usando modelo de troca de mensagens
define submatriz local
for num_iters
if pid != 0
envia primeira linha a pid-1
recebe limite superior de pid-1
if pid != P-1
envia ultima linha a pid+1
recebe limite inferior de pid+1
for num_linhas
compute
P0
P1
P2
60
Exemplo: Usando Condor (subm file)
Universe = standard
Executable = /u/dutra/Yap-4.3.20/condor/yap.$$(Arch).$$(OpSys)
Initialdir = /u/dutra/new_experiments/Carcino/diffseeds/theories/x5x4/f5/123
Log = /u/dutra/new_experiments/Carcino/diffseeds/theories/x5x4/f5/123/log
Requirements = ((Arch == "INTEL" && OpSys == "LINUX")
&& (Mips >= 500) && Memory >= 400) ||
(Arch == "SUN4u" && OpSys == "SOLARIS28") ||
(IsDedicated && UidDomain == "cs.wisc.edu"))
Arguments = -b /u/dutra/Yap-4.3.20/condor/../pl/boot.yap
Input = condor.in.$(Process)
Output = /dev/null
Error = /dev/null
Queue 300
61
Exemplo: Usando Condor (input file)
['/u/dutra/Yap-4.3.20/condor/../pl/init.yap'].
module(user).
['/u/dutra/new_experiments/Aleph/aleph.pl'].
read_all('/u/dutra/new_experiments/Carcino/PL/x5x4/f5/123/train').
set(i,5).
set(minacc,0.7).
set(clauselength,4).
set(recordfile,'/u/dutra/new_experiments/Carcino/
diffseeds/theories/x5x4/f5/123/trace-0.7-4.0').
set(test_pos,'/u/dutra/new_experiments/Carcino/PL/x5x4/f5/123/test.f').
set(test_neg,'/u/dutra/new_experiments/Carcino/PL/x5x4/f5/123/test.n').
set(evalfn,coverage).
induce.
write_rules('/u/dutra/new_experiments/Carcino/
diffseeds/theories/x5x4/f5/123/theory-0.7-4.0').
62
halt.
Exemplo: Usando JDL
Executable = "/home/SO/marluce/tmp/yap/condor/yap";
InputSandbox = { "/home/SO/marluce/tmp/yap/condor/yap",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/*.pl",
"home/SO/marluce/tmp/CondorBench//Aleph/aleph.pl",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.b",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.f",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.n",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/condor.in.0" };
OutputSandbox = { "theory-0.9-5.0", "trace-0.9-5.0"};
InputData = { "/home/SO/marluce/tmp/yap/condor/yap",
"home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/*.pl",
“ home/SO/marluce/tmp/CondorBench//Aleph/aleph.pl”,
“home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.b”,
“ home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.f”,
“home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/train.n”,
“home/SO/marluce/tmp/CondorBench//Carcino/diffseeds/theories/x5x4/f1/2/condor.in.0” };
Arguments = "/home/SO/marluce/tmp/yap/condor/yap < home/SO/marluce/tmp/CondorBench/
Carcino/diffseeds/theories/x5x4/f1/2/condor.in.0";
Requirements = "((Arch == "INTEL" && OpSys == "LINUX") && (Mips >= 500)
&& Memory >= 400)";
StdInput
= "condor.in.0";
StdOutput = "/dev/null";
63
StdError = "/dev/null";
Referências
 DSM http://www.ics.uci.edu/~javid/dsm.html
 TOP500 Supercomputers http://www.top500.org
 Globus Toolkit http://www.globus.org/toolkit/
 gLite http://glite.web.cern.ch/glite/
 Condor http://www.wisc.edu/condor
 OurGrid http://www.ourgrid.org
 PVM http://www.csm.ornl.gov/pvm
 MPI http://www.mpi-forum.org
 OurGrid http://www.ourgrid.org
 Projeto EGEE: http://www.egee.org
 Projeto EELA: http://www.eu-eela.org
 Global Grid Forum: http://www.ggf.org
64
Obrigada!!

65