COMPUTAÇÃO
PARALELA:
UMA INTRODUÇÃO
Guilherme Galante
MOTIVAÇÃO E
JUSTIFICATIVAS
COMO GANHAR DESEMPENHO EM PROGRAMAS?

3 opções
3
COMO GANHAR DESEMPENHO EM PROGRAMAS?
1.
Melhorar o ambiente de execução

2.
Melhorar o algoritmo

3.
Ex: Comprar um processador melhor
Ex: substituir um algoritmo de ordenação Bubble
por Quicksort
Paralelização


Não é a solução para todos os problemas do mundo
Alguns problemas não são paralelizáveis (ou muito
difíceis de se ganhar desempenho)
4
COMPUTAÇÃO SEQUENCIAL

Programa executa em uma única CPU
Dividido em uma série de instruções
 Executadas uma após a outra*
 Apenas uma instrução é executada por vez*

5
COMPUTAÇÃO PARALELA

Utilização de múltiplos recursos computacionais para
resolver um determinado problema


Múltiplas CPUs
Problemas são divididos para serem executados
simultaneamente
6
POR QUE USAR PARALELISMO?





Tempo/Dinheiro
Limite da computação sequencial
Solução de grandes problemas
Alocação de recursos
 Cluster
 Grids
Arquiteturas estão mudando!!!
7
ONDE ESTÁ O PARALELISMO

Paralelismo no nível de instruções
Pipeline, superescalar
 Implícito para o programador


Várias linhas de execução: threads

Suporte do sistema operacional
Vários núcleos
 Vários processadores
 Placas Gráficas (GPUs)

Programador é
responsável pela
exploração do
paralelismo
8
9
10
http://www.isgtw.org/?pid=1001952
ÁREAS DE APLICAÇÃO
11
Top 500 – junho/09
ARQUITETURAS
PARALELAS
ARQUITETURAS PARALELAS

Classificação de Flynn (1970)
SISD
SIMD
MISD
MIMD
13
ARQUITETURA

SISD
Computadores com um único processador
 Instruções executadas em seqüência
 Placas gráficas

14
ARQUITETURA

SIMD

Cada processador executa a mesma instrução em
sincronia, mas usando dados diferentes
15
ARQUITETURA

MIMD
Classe dos computadores paralelos
 Não determinismo:



Memória Compartilhada


SMP, Multicore
Memória Distribuída


Várias coisas ocorrendo ao mesmo tempo
Cluster, MPP
Híbridos
16
IBM – RoadRunner
Los Alamos National Laboratory
Cluster
PowerXCell 8i 3.2 Ghz / Opteron DC 1.8 GHz
129.600 cores
98TB de memória
SO Linux (Fedora and Red Hat enterprise editions)
Interconexão: Infiniband
17
MPP
AMD x86_64 Opteron Quad Core 2300 MHz
181.504 cores
362TB de memória
Interconexão: Cray SeaStar / Infiniband
SO CNL (adaptação do Suse)
Cray – Jaguar
Oak Ridge National Laboratory
18
Cluster Krusty – LCAD Unioeste
18 nós – Pentium IV 3.2 HT GHz
1 GB RAM
Rede Gigabit Ethernet
SO Linux Fedora
Precisa-de
de
usuários!!
19
FERRAMENTAS E
MODELOS DE
PROGRAMAÇÃO
PROGRAMAÇÃO DE
MULTIPROCESSADORES (MEM.
COMPARTILHADA)

Modelo de programação:


Aspecto crítico:


Múltiplas threads compartilhando dados
sincronização quando diferentes tarefas acessam os mesmos
dados
Ferramentas para programação:
linguagens concorrentes (Ada, SR, Java ...)
 linguagens seqüenciais + extensões/biliotecas (OpenMP,
Pthreads, Cilk, HPF)

21
PROGRAMAÇÃO DE
MULTIPROCESSADORES (MEM.
COMPARTILHADA)
#include <omp.h>
#include <stdio.h>
Exemplo OpenMP
#include <stdlib.h>
int main (int argc, char *argv[])
{
int nthreads, tid;
#pragma omp parallel private(nthreads, tid)
{
/* Obtain thread number */
tid = omp_get_thread_num();
printf("Hello World from thread = %d\n", tid);
/* Only master thread does this */
if (tid == 0)
{
nthreads = omp_get_num_threads();
printf("Number of threads = %d\n", nthreads);
}
}
/* All threads join master thread and disband */
22
PROGRAMAÇÃO DE
MULTICOMPUTADORES (MEM.

Modelo de programação:


troca de mensagens entre tarefas cooperantes
Aspectos críticos:


DISTRIBUÍDA)
Comunicação e distribuição dos dados
(balanceamento de carga)
Ferramentas para programação:
Linguagens sequenciais + extensões/bibliotecas
 MPI (C,C++,Fortran,Java), PVM, Java+RMI


Memória compartilhada distribuída:

Linda, Threadmarks, ...
23
PROGRAMAÇÃO DE
MULTICOMPUTADORES (MEM.
DISTRIBUÍDA)
#include <stdio.h>
#include <mpi.h>
Exemplo MPI
int main (int argc, char *argv[])
{
int rank, size,
MPI_Init (&argc, &argv);
MPI_Comm_rank (MPI_COMM_WORLD, &rank);
MPI_Comm_size (MPI_COMM_WORLD, &size);
printf( "Hello world from process %d of %d\n", rank, size );
MPI_Finalize();
return 0;
}
24
CONSTRUÇÃO DE PROGRAMAS PARALELOS


Não existe um padrão para construção de aplicações
paralelas
Metodologia PCAM – Foster
 Particionamento
 Comunicação
 Agrupamento
 Mapeamento
25
MODELOS DE APLICAÇÃO

SPMD (Single Program, Multiple Data)
processador
dado

processo
Workpool
tarefas/dados
26
processadores
MODELOS DE APLICAÇÃO


Mestre-Escravo
mestre
escravos
Pipeline
F
1
F
2
F
3
F
1
F
2
F
3
27
EXEMPLO DE USO: PCAM + MESTREESCRAVO

Partição


Comunicação


Neste tipo de algoritmo a comunicação é essencialmente entre
o mestre e os escravos para a envio de tarefas e para o retorno
de resultados
Aglomeração


Na fase de partição são identificadas as tarefas que são
geridas pelo mestre
Visando a redução dos custos de comunicação; podem ser
enviadas várias tarefas em cada mensagem
Mapeamento
O mapeamento é efetuado através da distribuição dos escravos
pelos processadores
 Podem ser colocados vários escravos por nodo

28
RESUMINDO...
Escolha da
arquitetura
Validação e
testes de
desempenho
Escolha das
ferramentas
Implementação
Projeto do
software
Problema
Detecção do
paralelismo
29
EXEMPLO DE
APLICAÇÃO PARALELA
EXEMPLO DE
APLICAÇÃO
Simulação de Hidrodinâmica
Rio Guaíba - RS
Área: Computação Científica
Paralela/Aplicações
Dissertação de Mestrado – UFRGS
2004-2006
31
Geração da
Malha
sequencial
paralelo
Particionamento
da malha
Geração dos
Sistemas de
Equações
Resolução dos
Sistemas de
Equações
Obtenção da
solução final
Arquitetura: Cluster
Software: C + MPI
32
RESULTADOS
Testes efetuados no
Cluster Krusty: 18 nodos
33
CONCLUINDO...

Aplicações
Científicas
 Comerciais (desenvolvimento e conversão/paralelização)


Gerenciamento de infra-estrutura

Pesquisa





Clusters
Grids
P2P
Cloud Computing
Aplicações em outras áreas:
 Matemática
 Física
 Inteligência Artificial
 Banco de Dados
 etc...
Oportunidade
s
34
OBRIGADO!
[email protected]
www.inf.unioeste.br/~guilherme
35