Paralelismo, ferramentas e aplicações
Celso Carneiro Ribeiro
Noemi Rodriguez
Sérgio Lifschitz
Seminário DI/PUC-Rio
Maio de 2002
Transparência 1/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Paralelismo: evolução
• Anos 70: primeiras máquinas paralelas - Illiac IV, 64
processadores)
• Anos 80: aparecimento em escala comercial de
máquinas paralelas e vetoriais voltadas para
aplicações científicas de grande porte
(meteorologia, petróleo, etc.) – Cray, CDC Cyber
• Diversificação de arquiteturas:
SIMD vs. MIMD
Memória compartilhada (SM) vs. distribuída (DM)
Redes de interconexão (anel, cubo, mesh, shuffle, etc.)
Transparência 2/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Paralelismo: evolução
• Diversificação de fabricantes:
Denelcor HEP (DM-MIMD, poucos processadores)
Sequent Balance, Encore Multimax (SM-MIMD, poucos
processadores)
KSR Intel Paragon, Cray T3D (DM-MIMD, centenasmilhares de processadores)
MasPar MP-1 e MP-2, Connection Machine CM-1 e CM2 (SIMD síncronas com até 65536 pequenos procs.)
• Custos de desenvolvimento, pequena escala, falta de
padrões, dificuldades de programação:
desaparecimento
• Poucos “sobreviventes”: IBM (sistemas SP), SGI-Cray
Transparência 3/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Paralelismo: evolução
• Final dos anos 90 e hoje:
Reaparecimento de multiprocessadores a memória
compartilhada com até algumas centenas de
processadores (SGI Origin)
Clusters de máquinas conectadas por redes locais
rápidas (escalabilidade, tolerância a falhas, economias
de escala, bons índices de custo/benefício)
Conexão de múltiplas máquinas através de redes
nacionais ou internacionais de velocidade muito alta
Transparência 4/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Clusters
• Coleção de PCs ou estações de trabalho conectadas
por uma rede:
Componentes comerciais regulares facilmente
disponíveis
Sistemas operacionais de domínio público (Linux)
Redes comuns (Ethernet, Fast Ethernet) ou mais rápidas
(Myrinet)
Ambientes padrão de software baseados em trocas de
mensagens (PVM, MPI)
• “Beowulf clusters” com alguns milhares de
processadores encontram-se entre as máquinas com
maior capacidade de processamento atualmente
disponíveis
Transparência 5/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Grid computing
• Enfoque para distribuição de capacidade de
processamento: Internet + alto desempenho
• Diferentes realizações: grid computing, P2P,
metacomputing, web, Internet computing, global
computing, web services, etc.
• Sistemas distribuídos: “um sistema distribuído é
uma coleção de computadores independentes que
aparecem para o usuário como um computador
único” (Tanenbaum)
Transparência 6/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Grid computing
• Princípios:
Internet computing: reaproveitamento do tempo ocioso
de milhares de processadores através de um screen-saver
(uso não-comercial: SETI@home, Décrypthon)
Metacomputing: comprar serviços de cálculo (aplicações
pré-instaladas e computadores) sobre a Internet
Supercomputador virtual: oferecer um supercomputador
paralelo virtual fazendo as aplicações executarem sobre
processadores distantes (Globus, Legion, Unicore)
• Resultados práticos e aplicações
Transparência 7/49
03/maio/2002
Paralelismo, ferramentas e aplicações
LabPar - Laboratório de Paralelismo
• Configuração do atual cluster do DI:
32 Pentium II 450 Mhz (32 MB RAM e 6.3 GB HD)
Switch a 10 Mbits
Linux / MPI e PVM / C, C++ e Java
• Com a criação do Laboratório de Paralelismo:
Expansão para um cluster heterogêneo com 64 nós:
mais 32 Pentium IV 1.7 Ghz (256 MB RAM e 40 GB HD)
Subredes a diferentes velocidades: 10/100 Mbits
• SGI Origin 2 e cerca de 10 novos postos de trabalho
para pós-graduandos
• Ferramentas e instalações para grid computing
Transparência 8/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Paralelismo: problemas típicos
•
•
•
•
•
•
Ferramentas e linguagens de programação
Comunicação e redes
Balanceamento de carga
Gerenciamento de recursos
Confiabilidade
Algoritmos para processamento paralelo
Transparência 9/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Programação Paralela Distribuída
Noemi Rodriguez
Transparência 10/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Sistemas distribuídos
• importância atual
crescimento de uso com ambiente de redes
geográficas
forma de baixo custo de provisão de paralelismo
• modelos de programação
cliente-servidor, peer-to-peer, orientação a eventos, ...
• programas distribuídos por diferentes arquiteturas
• gerenciamento de distribuição por várias máquinas
» gerenciamento de recursos
» adaptação dinâmica
Transparência 11/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Ferramentas para programação
• bibliotecas de troca de mensagens
MPI, PVM
• "bibliotecas" para programação concorrente
pthreads
• linguagens para programação distribuída
abstrações de mais alto nível
• linguagens interpretadas
Lua
Transparência 12/49
03/maio/2002
Paralelismo, ferramentas e aplicações
alua
•
•
•
•
•
uso de um paradigma orientado a eventos
envio explícito estilo send
recebimento gera evento
tratamento: execução do trecho recebido
modelo de programação dual:
coordenação em Lua
computação em C
Transparência 13/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Troca de mensagens
B
A
send(B,"a=1")
B
A
send(B,"send(A,'a='..a)")
Transparência 14/49
a=1
03/maio/2002
send(A,'a='..a)
Paralelismo, ferramentas e aplicações
alua multicanal
• eventos podem ter tratamento diferente em cada
canal
Transparência 15/49
03/maio/2002
Paralelismo, ferramentas e aplicações
alua
• envio de código permite alterar o
comportamento da aplicação em tempo real
• modelo assíncrono apropriado para
programação de aplicações distribuídas em
redes geográficas
• modelo de programação dual permite que
aproveitemos o melhor de cada mundo...
Transparência 16/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Trabalhos em andamento
• suporte a abstrações específicas
espaço de tuplas (canal de comunicação)
chamadas remotas de métodos
• suporte ao desenvolvimento de aplicações
paralelas em ambientes geograficamente
distribuídos
framework para programação de aplicações
adaptativas
• uso do alua multicanal para desenvolvimento de
aplicações multimidia distribuídas
Transparência 17/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Bancos de Dados Paralelos,
Agentes e Bioinformática
Sérgio Lifschitz
Transparência 18/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Motivação para BD paralelos
Contexto VLDB...
• Terabytes são realidade (“terror” bytes)
• Algumas empresas > 3TB
• Full scan 1TB a 10MB/s … mais de 1 dia!
• Gargalo I/O: comprar mais hardware… ?!?
• Solução ‘cluster’: MPP e off-the-shelf
Transparência 19/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Aspectos de BD paralelos
Alguns itens a considerar...
• Shared-something ou shared-nothing
• Paralelismo inter/intra query ou intra operação
• I/O (consultas simples) ou CPU (complexas)?
• Particionamento: faixas, hash e round-robin
• Problemas: startup, interferência e desvios
Transparência 20/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Algumas pesquisas em BDs //s
Focos principais …
• Consultas e balanceamento de carga
• Biocomputação e projeto de BD paralelos
… e também ...
• Integração dados + aplicações
• Sistemas (multi-)agentes
Transparência 21/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Resultados recentes
Junções paralelas...
• Junção // com balanceamento preventivo
• Agent-based databases (Minibase)
... e em Bioinformática ...
• BLAST paralelo
• Projeto de BDs distribuídos
Transparência 22/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Oportunidades
… e possibilidades concretas …
• Data mining
• Gerenciador ad-hoc
• Repositórios de biologia computacional
• Self-tuning
• Streaming data
Transparência 23/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Observações finais
• Dados complexos
• Hoje terabytes, breve petabytes
• GRIDs para BDs e Biocomputação
• Já há primitivas DM e DW … e mais!
… SGBDs paralelos já existem ...
O LabPar viabiliza alguns projetos!
Transparência 24/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Metaheurísticas Paralelas e
Aplicações: Redes e Biologia
Celso Carneiro Ribeiro
Transparência 25/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Problemas de otimização
• Problema: otimizar uma função objetivo definida
por variáveis contínuas (intensidades) ou
discretas (decisões) e sujeita a um conjunto de
restrições
• Dificuldade: a grande parte dos problemas de
interesse pertence à classe NP-difícil, problemas
para os quais não se conhece (e possivelmente
não existem) algoritmos exatos eficientes (de
complexidade polinomial)
• Alternativa: bons algoritmos aproximados
eficientes
Transparência 26/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Metaheurísticas
• Paradigmas de estratégias de solução que devem
ser instanciadas para cada problema específico,
baseadas em técnicas de:
Construção de soluções
Melhoria de soluções (busca local)
• Exemplos:
Algoritmos genéticos
Simulated annealing
Busca tabu
GRASP
Colônias de formigas, etc.
Transparência 27/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Metaheurísticas
• Algoritmos genéticos: baseados na analogia com
o processo de evolução natural, ao longo do qual
populações evoluem de acordo com os princípios
de seleção natural e de “sobrevivência dos mais
adaptados” (evolução das propriedades genéticas
da população).
• População representada pelos seus cromossomos
(soluções): novas soluções são geradas a partir da
população corrente e incluídas na população,
enquanto outras são excluídas, através de
mecanismos de reprodução e de mutação.
Transparência 28/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Metaheurísticas
• Algoritmo genético básico:
Gerar população inicial de soluções
while .NOT.critério-de-parada do
Escolher soluções reprodutoras
Fazer o crossover de soluções
Gerar mutações de soluções
Avaliar a aptidão das novas soluções
Atualizar a população
end-while
Transparência 29/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Metaheurísticas paralelas
• Paralelização: distribuição dos cálculos entre
diferentes processadores que cooperam e trocam
informações na busca de melhores soluções
• Vantagens:
Algoritmos mais robustos (menos dependentes de
parâmetros)
Problemas maiores, tempos menores, melhores soluções
• AGs paralelos: dividir a população original em diversas
subpopulações, cujas evoluções ocorrem em paralelo
(modelo de ilhas) com trocas dos melhores indivíduos
entre as subpopulações (quando? quais? como? etc.)
Transparência 30/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de circuitos virtuais privados
• Circuitos virtuais privados (PVCs) entre os pares
origem e destino de cada cliente em um backbone
• Roteamento de cada cliente feito pelo projetista sem
conhecimento de demandas futuras
• Ineficiência e necessidade ocasional de rotear os
PVCs offline
• Problema: minimizar atrasos e congestão,
satisfazendo as demandas e restrições de capacidade
• Aplicação desenvolvida para a AT&T: melhoria
sensível do desempenho e do aproveitamento de
redes reais
Transparência 31/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
Transparência 32/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
Transparência 33/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
Transparência 34/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
Transparência 35/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
capacidade máxima = 3
Transparência 36/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
capacidade máxima = 3
rerotear
Caminho longo!
Transparência 37/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
capacidade máxima = 3
Transparência 38/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento de PVCs
Viável e ótima!
Transparência 39/49
03/maio/2002
capacidade máxima = 3
Paralelismo, ferramentas e aplicações
Projeto de redes locais de acesso
• Construir uma rede de fibras óticas para prover
serviços de banda larga a consumidores
comerciais e residenciais, levando em
consideração o balanceamento entre os custos
de construção (colocação das fibras) e os
rendimentos potenciais dos clientes atendidos
(perda de receita no caso do cliente não ser
atendido).
• Problema de Steiner com prêmios: aplicação
desenvolvida para a AT&T
Transparência 40/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Projeto de redes locais de acesso
rua
penalidade nula
cliente
(prêmio)
raiz
Transparência 41/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Projeto de redes locais de acesso
Transparência 42/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Projeto de redes a k-caminhos
• Dados:
Grafo suporte para a construção de uma rede
Conjunto de pares origem-destino
Custo de construção de cada arco
• Problema: construir uma rede de custo mínimo,
na qual todos os pares origem-destino são
conectados por caminhos usando no máximo k
arcos
• Para que a confiabilidade da rede seja alta, todos
os caminhos devem ser formados por k ≤3 arcos
Transparência 43/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento Internet sob protocolo OSPF
• Objetivo da engenharia de tráfego: melhor
utilização dos recursos da rede
• Roteamento de tráfego pode ter um grande
impacto na eficiência da utilização dos recursos
• OSPF é o protocolo mais comumente utilizado
para roteamento intra-domínio
Todos os roteadores têm conhecimento completo da
rede
Roteamento segundo caminhos mais curtos
Fluxo igualmente repartido em caso de múltiplos
caminhos
Transparência 44/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Roteamento Internet sob protocolo OSPF
• Problema: atribuir pesos  [1,65535] às
conexões da rede, de forma que o roteamento
segundo o protocolo OSPF por um critério de
caminho mais curto minimize uma medida de
congestão
• Algoritmo genético paralelo com soluções
melhoradas por busca local
• Aplicação desenvolvida para a AT&T, levando a
melhorias significativas (tráfego 40% maior) em
relação ao critério proposto pela CISCO (pesos
proporcionais ao inverso das capacidades)
Transparência 45/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Problema da filogenia
• Uma filogenia é uma árvore que relaciona espécies
ou genes homólogos de espécies distintas (taxons)
• Dado um conjunto de taxons caracterizados por um
conjunto de caracteres, obter uma filogenia com o
menor número de passos evolucionários (mudança
de um caracter)
a b c d e f g
• Exemplo:
O
A
B
C
Transparência 46/49
03/maio/2002
0
1
1
1
0
1
1
1
0
0
1
1
0
0
1
1
0
1
1
0
0
1
1
0
0
1
1
0
Paralelismo, ferramentas e aplicações
Problema da filogenia
Exemplo:
O
A
B
C
a
0
1
1
1
b
0
1
1
1
c
0
0
1
1
d
0
0
1
1
e
0
1
1
0
f
0
1
1
0
g
0
1
1
0
Solução com 10 passos:
Solução com 9 passos:
Transparência 47/49
Paralelismo, ferramentas e aplicações
03/maio/2002
Reconhecimento de imagens médicas
• Dados:
Uma imagem a ser identificada
Um atlas de imagens
• Exemplos:
Identificação de tumores
Reconhecimento facial
• Imagens representadas por grafos de atributos
relacionais:
Nós: regiões das imagens
Arestas: relações entre regiões (fronteiras)
Atributos: cores, intensidades, etc.
Transparência 48/49
03/maio/2002
Paralelismo, ferramentas e aplicações
Reconhecimento de imagens médicas
• Medidas de similaridade entre pares de nós e
entre pares de arestas (imagem-modelo)
• Problema:
Determinar a imagem do atlas que mais se
assemelha à imagem a ser identificada
Determinar a correspondência ótima entre as regiões
da imagem e as regiões do modelo
Transparência 49/49
03/maio/2002
Paralelismo, ferramentas e aplicações