Paralelismo: evolução

Paralelismo, ferramentas e aplicações03/maio/2002Transparência 1/49

Paralelismo, ferramentas e aplicações

Celso Carneiro RibeiroNoemi RodriguezSérgio Lifschitz

Seminário DI/PUC-RioMaio de 2002


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. MIMDMemória compartilhada (SM) vs. distribuída (DM)Redes de interconexão (anel, cubo, mesh,

shuffle, etc.)



•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,

centenas-milhares de processadores)MasPar MP-1 e MP-2, Connection Machine CM-1

e CM-2 (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



•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


Clusters

•Coleção de PCs ou estações de trabalho conectadas por uma rede:Componentes comerciais regulares

facilmente disponíveisSistemas 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


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)


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


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 MbitsLinux / 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


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


Programação Paralela Distribuída

Noemi Rodriguez


Sistemas distribuídos

• importância atualcrescimento de uso com ambiente de redes

geográficasforma de baixo custo de provisão de paralelismo

•modelos de programaçãocliente-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


Ferramentas para programação

•bibliotecas de troca de mensagensMPI, PVM

•"bibliotecas" para programação concorrentepthreads

•linguagens para programação distribuídaabstrações de mais alto nível

•linguagens interpretadasLua


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 Luacomputação em C


Troca de mensagens

send(B,"a=1"

)

A B

send(B,"send(A,'a='..a)") send(A,'a='..a)

A B

a=1


alua multicanal

•eventos podem ter tratamento diferente em cada canal


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...


Trabalhos em andamento

•suporte a abstrações específicasespaço de tuplas (canal de comunicação)chamadas remotas de métodos

•suporte ao desenvolvimento de aplicações paralelas em ambientes geograficamente distribuídosframework para programação de

aplicações adaptativas•uso do alua multicanal para

desenvolvimento de aplicações multimidia distribuídas


Bancos de Dados Paralelos, Agentes e

Bioinformática

Sérgio Lifschitz


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


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


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


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


Oportunidades

… e possibilidades concretas …

• Data mining

• Gerenciador ad-hoc

• Repositórios de biologia computacional

• Self-tuning

• Streaming data


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!


Metaheurísticas Paralelas e Aplicações:

Redes e Biologia

Celso Carneiro Ribeiro


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


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çõesMelhoria de soluções (busca local)

•Exemplos:Algoritmos genéticosSimulated annealingBusca tabuGRASPColônias de formigas, etc.


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.


Metaheurísticas

•Algoritmo genético básico:Gerar população inicial de soluçõeswhile .NOT.critério-de-parada do

Escolher soluções reprodutorasFazer o crossover de soluçõesGerar mutações de soluçõesAvaliar a aptidão das novas

soluções Atualizar a população

end-while


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.)


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


Roteamento de PVCs


Roteamento de PVCs


Roteamento de PVCs


Roteamento de PVCs


Roteamento de PVCs

capacidade máxima = 3


Roteamento de PVCs

Caminho longo!

rerotear



Roteamento de PVCs



Roteamento de PVCs

Viável e ótima! capacidade máxima = 3


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



cliente(prêmio)

ruapenalidade nula

raiz




Projeto de redes a k-caminhos

•Dados:Grafo suporte para a construção de uma

redeConjunto de pares origem-destinoCusto 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


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ínioTodos os roteadores têm conhecimento

completo da redeRoteamento segundo caminhos mais curtosFluxo igualmente repartido em caso de

múltiplos caminhos


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)


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)

•Exemplo:

a b c d e f g

O 0 0 0 0 0 0 0A 1 1 0 0 1 1 1B 1 1 1 1 1 1 1C 1 1 1 1 0 0 0


Problema da filogenia

a b c d e f g

O 0 0 0 0 0 0 0A 1 1 0 0 1 1 1B 1 1 1 1 1 1 1C 1 1 1 1 0 0 0

Exemplo:

Solução com 10 passos:

Solução com 9 passos:


Reconhecimento de imagens médicas

•Dados:Uma imagem a ser identificadaUm atlas de imagens

•Exemplos:Identificação de tumoresReconhecimento facial

• Imagens representadas por grafos de atributos relacionais:Nós: regiões das imagensArestas: relações entre regiões

(fronteiras)Atributos: cores, intensidades, etc.


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

Documents

Paralelismo: evolução