Upload
dokhanh
View
227
Download
2
Embed Size (px)
Citation preview
Aula 2Computação Distribuída
de Alto Desempenho
Marcelo GiovanniMarcelo GiovanniNilton AlvesNilton Alves
Marcelo Portes de Albuquerque Marcelo Portes de Albuquerque
CBPFCentro Brasileiro de Pesquisas Físicas
VI Escola do CBPF – Rio de Janeiro17 a 28 de julho de 2006
2
Sumário Aula 02
1.1. IntroduIntroduçção ão 2.2. Conceitos e TerminologiaConceitos e Terminologia3.3. Arquitetura de MemArquitetura de Memóóriaria4.4. Modelos de ProgramaModelos de Programaçção Paralelaão Paralela5.5. Projetando Programas em ParaleloProjetando Programas em Paralelo6.6. Exemplo de Algoritmo ParaleloExemplo de Algoritmo Paralelo
VI Escola do CBPF
3
1. Introdução
• Em geral os programas são escritos para a computação serial: – Execução em um único computador com um só processador– Divisão do problema em uma serie de instruções – Instruções são executadas uma após a outra– Somente uma instrução pode ser executada no mesmo instante
O que é a Computação Paralela?
VI Escola do CBPF
4
Computação ParalelaComputação paralela é a utilização simultânea de vários recursos computacionais na solução de um determinado problema computacional
– Deve-se utilizar várias CPUs para resolver o problema– O problema deve ser dividido em partes que podem ser executadas concorrentemente– Cada parte deve ser sub-dividida em uma seqüência de instruções– As instruções de cada parte devem ser executadas simultaneamente em diferentes
CPUs
1. IntroduçãoVI Escola do CBPF
5
Computação ParalelaComputação paralela é uma evolução da computação serial
– Tradução para o computador da forma dos acontecimentos dos eventos naturais: muitos eventos complexos inter-relacionados acontecendo ao mesmo momento e/ou em seqüência.
A computação paralela é considerada por muitos como “a computação de mais alto nível"
Tem sido usada para realizar simulações numéricas de sistemas complexos e resolver “Problemas com Grandes Desafios”:
– Pesquisa científica– Base de dados em paralelo, datamining– Exploração de petróleo – Serviços de busca na Web– Diagnóstico na medicina – Gráficos avançados e realidade virtual (indústria do entretenimento)– ...
1. IntroduçãoVI Escola do CBPF
6
Porque usar a Computação Paralela?Razões principais:
– Economia de tempo para resolver um determinado problema– Resolver problemas muito grande– Realizar tarefas ao mesmo tempo (concorrência)
Outras vantagens: – Aproveitar recursos ociosos– Usar recursos mais baratos ao invés de pagar pelo uso de supercomputadores– Aumentar a quantidade de memória
Limite para a computação serial– Velocidade de transmissão: a velocidade de um computador está associado a
rapidez que os dados trafegam no hardware– Limites de miniaturização: tecnologia vem permitindo o aumento de transistores
nos chips, porém o limite está em quão pequeno eles podem ser– Limitação econômica: É mais caro fazer um único processador mais rápido que
usar um grande número de processadores comerciais para obter a mesma performance
1. Introdução
Nos últimos 10 anos apareceram as redes rápidas, sistemas distribuídos em arquiteturas com vários processadores (mesmo no desktop) Como vão ser os programas para estes ambientes? Programas Paralelos !
O FUTURO:
VI Escola do CBPF
7
Sumário Aula 02
1. Introdução 2.2. Conceitos e TerminologiaConceitos e Terminologia3. Arquitetura de Memória4. Modelos de Programação Paralela5. Projetando Programas em Paralelo6. Exemplo de Algoritmo Paralelo
VI Escola do CBPF
8
2 - Conceitos e TerminologiasArquitetura de von Neumann
– Por mais de 40 anos os computadores seguiram a máquina de von Newmann
– O computador de von Neumann usa o conceito de armazenamento de programa
– A CPU executa um programa armazenado que especifica a seqüência de operações de leitura e escrita na memória
John von NeumannMatemático, Prof. Da Universidade de
Princeton e um dos construtores do ENIAC.
Projeto Básico– A memória é utilizada para guardar os dados e as
instruções
– Instruções são códigos que dizem ao computador para fazer alguma coisa
– Dados são as informações que devem ser processadas
– A CPU pega a instrução e os dados da memória, decodifica a instrução e a executa seqüencialmente
VI Escola do CBPF
9
Algumas Terminologias GeraisTarefa (Task)
– Uma tarefa é tipicamente um conjunto de instruções de um programa que pode ser executada em computador
– Uma tarefa pode ser um programa em série (processo único) ou um programa em paralelo com múltiplos processos
Tarefa Paralela (Parallel Task)– Uma tarefa que pode ser executada por vários processadores
Job: coleção de tarefas iniciada por um usuário
Fila (Queue)– Um enfileiramento e agendamento de jobs– Uma fila contém jobs pendentes, em execução– Jobs completados são removidos da fila
Nó (Node): único nó computacional, com um ou mais processadores (CPUs)
Execução Serial– Execução de um programa sequencialmente, um comando por vez– Tarefas paralelas terão seções do programa paralelo que serão executados serialmente
Execução Paralela– Execução de um programa com mais de uma tarefa e cada tarefa sendo executada por
diferentes processadores ao mesmo
2. Conceitos e TerminologiasVI Escola do CBPF
10
Algumas Terminologias GeraisSpeedup (Observado)
– Definido como
– Indicador mais simples e mais usado para medida de performance de programas paralelos
2. Conceitos e Terminologias
wall-clock time da execução serial
wall-clock time da execução em paralelo
Overhead do Paralelismo– Tempo necessário para coordenar as tarefas em paralelo– Tempo de inicialização das tarefas em paralelo (task start-up time)– Sincronizações – Comunicação de dados – Overhead imposto pelos compiladores, bibliotecas, sistemas operacionais, etc
para o paralelismo
– Tempo de encerramento das tarefas em paralelo (task termination time)
VI Escola do CBPF
11
Classificação dos ComputadoresExistem diferentes formas de classificar os computadoresGrande diversidades de arquiteturas computacionaisA mais usada é a Taxonomia1 de Flynn
– Classificação de ambientes de hardwares
Leva em consideração
1 Taxonomia refere-se à classificação das coisas
2. Conceitos e Terminologias
Número de instruções executadas em paralelo x
Conjunto de dados para os quais as instruções são submetidas
M I M D Multiple Instruction, Multiple Data
M I S D Multiple Instruction, Single Data
S I M D Single Instruction, Multiple Data
S I S D Single Instruction, Single Data
VI Escola do CBPF
12
SISD - Single Instruction, Single Data
Single Instruction– Somente executa uma instrução de um programa por vez– Somente um fluxo de instrução é processada pela CPU
Single Data– Somente um fluxo de dados é processado como entrada
Modelo tradicional de processador únicoExemplo:
– Computador pessoal com processador convencional – Computador serial (não paralelo)
Esta é a mais antiga e até hoje mais utilizada arquitetura de computador
2. Conceitos e TerminologiasVI Escola do CBPF
13
SIMD - Single Instruction, Multiple DataSingle Instruction
– As unidades de processamento executam a mesma instrução no mesmo ciclo de ClockMultiple Data
– Cada unidade de processamento opera em dado diferente
Um tipo de computador paraleloTem normalmente um decodificador de instrução especializado, uma rede interna de alta performance e um grande array para instruções Adaptado para problemas caracterizados por ter regularidade:
– Exemplo: Processamento de Imagem
Supercomputador CRAY T90 do Centro Nacional de Supercomputação (CESUP-RS) da UFRGS
Exemplos: IBM 9000, Cray T90 etc.
2. Conceitos e TerminologiasVI Escola do CBPF
14
MISD - Multiple Instruction, Single DataUm único fluxo de dados para várias unidades de processamento
Cada unidade de processamento opera os dados independentemente via fluxo de instruções independentes
Poucos computadores usaram esta classe de computador paralelo
O uso pode ser – Vários filtros de freqüência operando em um único fluxo de sinal– Vários algoritmos de criptografia tentando quebrar uma única mensagem
2. Conceitos e TerminologiasVI Escola do CBPF
15
MIMD - Multiple Instruction, Multiple DataMultiple Instruction:
– Cada processador pode executar um fluxo diferente de instruções
Multiple Data: – Cada processador pode trabalhar em um fluxo diferente dos dados
É o computador paralelo mais utilizado hoje em diaVários computadores modernos se encaixam nesta categoria
2. Conceitos e Terminologias
Vários supercomputadores atuais, “Grids”, multiprocessadores SMP, alguns PCs etc.
Exemplo: IBM BlueGene/L
Photo credit: IBM Rochester
VI Escola do CBPF
16
BlueGene/C - Cyclops642. Conceitos e Terminologias
It is a massively parallel, supercomputer-on-a-chip cellular architecture It is slated for release in late 2006 or early 2007
The Cyclops64 architecture will containmany hundreds of computing nodes
Cyclops64 project aims to create the first "supercomputer on a chip"
http://www.research.ibm.com/bluegene
VI Escola do CBPF
17
Classificação de Arquiteturas MIMDPreocupação especial na forma como os processadores estão conectados as memórias
– Multiprocessadores– Multicomputadores
Computadores Paralelos e
ConfiguraçõesDistribuídas
MIMD
Computadores Paralelos e
ConfiguraçõesDistribuídas
MIMD
Multiprocessadores(Memória Compartilhada)
Ambientes Fortemente Acoplados
Multicomputadores(Memória Distribuída)
Ambientes Fracamente Acoplados
2. Conceitos e TerminologiasVI Escola do CBPF
18
MultiprocessadoresFortemente acoplada uma vez que processadores e memória estão fortemente interligados através do sistema local de conexão (hardware)
Comunicação entre processadores é efetuada através de instruções de acesso comum a memória
Escalabilidade varia de alguns até centenas de processadores
M
P P P P
M M M
Configuração CompartilhadaBarramento
M – Memória P – Processador
Configuração Comutada
M
P P P P
M M M
Comutador
Configurações Genéricas de Multiprocessadores
2. Conceitos e TerminologiasVI Escola do CBPF
19
MulticomputadoresCaracterizados por centenas (ou milhares) de processadores que tem suas próprias memórias distribuída → fracamente acoplado
Comunicação entre processos é efetuada apenas por troca de mensagens entre os processos que estão sendo executados
Comunicação entre os nós é realizada por meio de uma rede de conexão
Boa escalabilidade
M – Memória P – Processador
Configurações Genéricas de Multicomputadores
Configuração CompartilhadaBarramento
M
P
M
P
M
P
M
P
Configuração Comutada
Comutador
M
P
M
P
M
P
M
P
2. Conceitos e TerminologiasVI Escola do CBPF
20
Multiprocessadores Simétricos - SMP Consiste de múltiplos processadores similares conectados entre si e àmemória por um barramento ou alguma outra forma de circuito de conexão interno
Caracterizado por até dezenas de processadores compartilhando todos os recursos disponíveis, executando um único sistema operacionalOs processadores são considerados simétricos pois tem o mesmo “custo” para acessar a memória
ProcessadorProcessador
CACHE
MemóriaSistema
deE/S
SistemadeE/S
Periféricos
Configuração clássica de uma arquitetura SMP
ProcessadorProcessador
CACHE
ProcessadorProcessador
CACHE
ProcessadorProcessador
CACHE
2. Conceitos e TerminologiasVI Escola do CBPF
21
Outras Características de SMPsTodos os processadores compartilham uma mesma memória
– Existe um único espaço de endereçamento
Todos os processadores compartilham acesso aos mesmos dispositivos de E/S, através de canais comuns (ou não)
O sistema inteiro é controlado por um único sistema operacional que torna transparente ao usuário a existência de vários processadores
– Windows e Linux estão preparados para rodar em sistemas SMP
Todos os processadores podem desempenhar as mesmas funções
O tempo de acesso a qualquer posição de memória por um processador é o mesmo para todos os processadores
– Arquitetura UMA - Uniform Memory Access
Para aumentar a escalabilidade utiliza-se cache local
2. Conceitos e TerminologiasVI Escola do CBPF
22
Exemplo de Sistemas SMP2. Conceitos e Terminologias
Intel Xeon Processor-based 2p Server
VI Escola do CBPF
23
Processamento Massivamente Paralelos - MPP
Classe de computação onde todos os elementos de processamento são conectados entre si para se obter uma capacidade de processamento maior
São normalmente multicomputadores
Pode ser composto por um conjunto de multiprocessadores onde cada um éum nó multicomputador
Computadores MPP são caracterizados por milhares de nós interligados por dispositivos de conexão de alta velocidade
Cada nó possui seu próprio Sistema Operacional
As aplicações executam localmente e se comunicam por meio de troca de mensagens (MPI ou PVM)
Ordem de grandeza de nós conectados → milhares
2. Conceitos e TerminologiasVI Escola do CBPF
24
Processamento Massivamente Paralelos - MPP
A escalabilidade da abordagem MPP é maior do que as arquiteturas com memória compartilhada
Elemento importante é o sistema de interconexão
– Redes -> topologia, roteamento, comutação, latência etc.
Configuração Genérica de um MPP
ProcProcC
ME/S
...ProcProc
CProcProc
C
ME/S
...ProcProc
CProcProc
C
ME/S
...ProcProc
C...
Rede de InterconexãoRede de Interconexão
2. Conceitos e Terminologias
Os ambiente computacionais de melhor performance atuais são sistemas MPP– Earth Simulator, Blue Gene, ASCI White, ASCI Red etc.
VI Escola do CBPF
25
Earth Simulator
Clique aqui!
VI Escola do CBPF
26
Sistemas Distribuídos
Podem ser vistos como configurações com grande poder de escala devido a agregação dos computadores existentes atualmente
O computador mais rápido que existe é a Internet, ou um subconjunto de suas máquinas, agrupadas para a execução de uma aplicação.
Scientific American
Conjunto de máquinas homogêneas ou heterogêneas possuindo sua própria arquitetura de software-hardware, executando seu próprio SO, integradas para a formação de SMPs, MPPs, Cluster e Grids computacionais
• Computação distribuída envolve a descentralização e normalmente a programação em paralelo
• Utiliza dois ou mais computadores que se comunicam para realizar uma tarefa
• Os tipos de ferramentas, linguagens de programação, de sistemas operacionais e outros recursos podem variar muito
2. Conceitos e TerminologiasVI Escola do CBPF
27
Falácias da Computação Distribuída
Existem alguns argumentos que são incorretos, mas que podem convencer as pessoas sobre o desenvolvimento de aplicações distribuídas
As mais comuns são:– A rede é 100% confiável– A latência é zero– A banda de comunicação é infinita– A rede é segura – A topologia não é relevante – Só existe um administrador do sistema– A rede é homogênea
2. Conceitos e TerminologiasVI Escola do CBPF
28
Clusters ComputacionaisCombinação de computadores independentes em um sistema unificado por meio de um software e rede
Cluster são usados para executar aplicações que necessitam de:– Alta disponibilidade– Grande confiabilidade – Elevado desempenho
São considerados sistemas “HighPerformance Computing” (HPC)pois fornecem grande poder computacional
Clusters Linux
2. Conceitos e TerminologiasVI Escola do CBPF
29
Cluster de Workstations (NOW)Conjunto de computadores completos (com teclado, monitor, mouse), conectados em rede, e que cumprem duas funções:
– o uso diário, com diversos tipos de programas como processadores de texto e planilhas
– o uso para processamento paralelo pesado no final do dia e/ou nos fins de semana.
Cluster não dedicado → desempenho do sistema é reduzido
Custo maior por máquina e mais problemas com a manutenção do sistema
2. Conceitos e TerminologiasVI Escola do CBPF
30
Clusters Beowulf
O que é Beowulf?– Processadores comuns
• Intelx86, Alpha, PPC• Pode ter mais de um processador por nó
– Redes comuns• Fast Ethernet, GbE, Myrinet, Infinband
– Sistema Operacional gratuito• Linux, BSD
– Modelos de programação padronizados• MPI, PVM
Sempre se pode melhorar o desempenho adicionando novas máquinas
Clusters Beowulf são escaláveis em termos de performance e estão baseados em hardwares comerciais e Linux
Mestre
Nó 01
GbEMyrinetInfinibandEth
Nó 02
Nó N
Rede Local
Diagrama simplificado de um Cluster Beowulf
2. Conceitos e TerminologiasVI Escola do CBPF
31
Submetendo Tarefas em Clusters
Fila 1
Fila 2
Fila N
UsuárioTamanho do jobPrioridadeTipo de recursoetc.
UsuárioTamanho do jobPrioridadeTipo de recursoetc.
Fila
Cluster #1 Cluster #2 Cluster #3
Agendador de Tarefas
PBS, LSF, MAUI, SGE, Condor, etc.
#ProcMemóriaRuntimeetc.
#ProcMemóriaRuntimeetc.
Tarefa
Realizado por um agendador de tarefas (Batch Scheduler)
2. Conceitos e TerminologiasVI Escola do CBPF
32
Entendendo o Agendador de TarefasRecursos podem ser caros
Objetivo é alcançar a máxima utilização dos recursos disponíveis– Mais trabalhos realizados– Maior número de usuários acessando os recursos
Colocar na fila um conjunto de tarefas – Permite escolher qual é a melhor tarefa para os recursos disponíveis– Escolhas feitas baseadas em
– Prioridade– Recursos solicitados– Objetivos desejados
Passo a Passo1. Usuário submete uma tarefa à fila2. Espera os recursos solicitados estarem disponíveis3. O nó mestre envia a tarefa aos nós escravos que tem o recurso disponível4. Os processadores alocados executam a tarefa5. O gerenciador de tarefa retira-a da fila6. Uma arquivo com saída é gerado
2. Conceitos e TerminologiasVI Escola do CBPF
33
Problema de Gerenciamento de Recursos
Perspectiva da Aplicação– Dada uma aplicação encontrar um conjunto de recurso apropriado para
executá-la– otimizar para obter a melhor performance
Perspectiva do Sistema– Para um conjunto de recursos disponíveis, identificar qual aplicação fará o
melhor uso deles– Otimizar para utilização total do sistema
2. Conceitos e TerminologiasVI Escola do CBPF
34
Computação de Alto Desempenho
Barramento, placa mãe
Memória Compartilhada
Máxima
Performance Absoluta
MPPs,Vectoriais
Rede LocalTCP/IP
Proprietária
Impreciso
Aproveitar processadores
ociosos
Clusters de Worksations
Clusters HPC DedicadosSistemas
Myrinet, Infiniband, GbERede
Passagem de MensagensModelo
Máxima, BoaVelocidade de Conexão
Boa relação Preço/PerformanceObjetivo
Tendência atual → uso de HPCs para resolver grandes desafios computacionais
Diferentes Plataformas para Alcançar Resultados
2. Conceitos e TerminologiasVI Escola do CBPF
35
Top500.org (Junho 2006)2. Conceitos e Terminologias
20025120Earth-SimulatorNEC
The Earth Simulator CenterJapan10
200510880Red Storm Cray XT3, 2.0 GHzCray Inc.
Sandia National LaboratoriesUnited States9
200616384JUBL - eServer Blue Gene SolutionIBM
Forschungszentrum Juelich(FZJ)
Germany8
200610368TSUBAME Grid Cluster - Sun Fire X64 Cluster, Opteron
2.4/2.6 GHz, InfinibandNEC/Sun
GSIC Center, Tokyo Institute ofTechnology
Japan7
20069024Thunderbird - PowerEdge 1850, 3.6 GHz, InfinibandDell
Sandia National LaboratoriesUnited States6
20068704Tera-10 - NovaScale 5160, Itanium2 1.6 GHz, QuadricsBull SA
Commissariat a l'EnergieAtomique (CEA)
France5
200410160Columbia - SGI Altix 1.5 GHz, Voltaire InfinibandSGI
NASA/Ames ResearchCenter/NAS
United States4
200612208ASC Purple - eServer pSeries p5 575 1.9 GHzIBM
DOE/NNSA/LLNLUnited States3
200540960BGW - eServer Blue Gene SolutionIBM
IBM Thomas J. Watson Research Center
United States2
2005131072BlueGene/L - eServer Blue Gene SolutionIBM
DOE/NNSA/LLNLUnited States1
YearProc.ComputerSiteRank
20041024xSeries Cluster Xeon 3.06 GHz - Gig-EIBM
Petroleum Company (C)Brazil171
VI Escola do CBPF
36
Top500 - Maiores Tendências
Crescimento do uso pela IndústriaCrescimento do
uso pela Indústria
2. Conceitos e TerminologiasVI Escola do CBPF
37
Top500 - Maiores Tendências
Os Clusters estão dominando
Os Clusters estão dominando
2. Conceitos e TerminologiasVI Escola do CBPF
38
Top500 - Maiores Tendências
GbE estáganhando espaço
GbE estáganhando espaço
2. Conceitos e TerminologiasVI Escola do CBPF
39
Top500 - Maiores Tendências
Processadores Intel são os escolhidospelos maiores HPC
Processadores Intel são os escolhidospelos maiores HPC
2. Conceitos e Terminologias
64 bits64 bits
VI Escola do CBPF
40
Top500 - Maiores Tendências
Os EUA tem mais de 60% de poder de processamento!
Os EUA tem mais de 60% de poder de processamento!
2. Conceitos e TerminologiasVI Escola do CBPF
41
Grids ComputacionaisGrid é uma infra-estrutura que permite a integração e colaboração de organizações virtuais
Ian Foster and Carl Kesselmanhttp://www.mkp.com/grid2 - Second Edition
Qual a Idéia Básica ?Usário:
• Enviar o Job
O Grid deve:• Encontrar um lugar para executá-lo• Organizar acessos eficientes aos dados• Cache, migração e replicação• Tratar da autenticação nos diferentes
ambientes e sites utilizados• Alocar recursos do site local• Executar o Job• Monitorar o progresso de execução • Recuperar o sistema em caso de
problemas • Avisar quando o trabalho estiver completo• Paralelizar se possível (decompor o Job
em unidades e recursos disponíveis)
Analogia à Rede Elétrica: disponibilização de energia escondendo do usuário detalhes como sua origem e a complexidade da malha de transmissão e distribuição.
2. Conceitos e TerminologiasVI Escola do CBPF
42
RR
R
R
R
R
R
RR
R
Organizações Virtuais• Pessoas e recursos distribuídos• Conectados pela rede• Situados em domínios administrativos diferentes• Compartilhando recursos, mesmos objetivos• Dinâmico
VO-BVO-A
R
R
R
R
2. Conceitos e TerminologiasVI Escola do CBPF
43
Organizações Virtuais• Pessoas e recursos distribuídos• Conectados pela rede• Situados em domínios administrativos diferentes• Compartilhando recursos, mesmos objetivos• Dinâmico• Sistema de gerência → tolerante a falhas
R RR
R
R
R
R
R
RRR
R
VO-A VO-B
2. Conceitos e TerminologiasVI Escola do CBPF
44
Virtualização
Servidores de Execução
Serviços de Distribuição
Aplicações• Conexão automática das
aplicações aos serviços
• ProvisionamentoDinâmico
• Recuperação automática de falhas
Fonte: The Grid: Blueprint for a New Computing Infrastructure (2nd Edition), 2004
União e compartilhamento de recursos heterogêneos com utilização otimizada e o fornecimento automático correspondente à demanda
Virtualização das Aplicações
Virtualização da Infra-estrutura
Administrador
Sistemas Distribuídos
2. Conceitos e TerminologiasVI Escola do CBPF
45
Integração de Sistemas DistribuídosGrids são construídos e não comprados
– Integração com sistemas de outras instituições é necessário
Instituição 3
Internet
Instituição 2
Instituição N
Instituição 1
Instituição 4
Problema:– Diferentes domínios administrativos → políticas de uso diferentes– Estabelecer uma política de uso dos recursos de um organização virtual
2. Conceitos e TerminologiasVI Escola do CBPF
46
Sistema de Integração em GridSistema Sistema GlobusGlobus • Conjunto de serviços que facilitam a computação em Grid
• Permite que uma coleção de máquinas heterogêneas distribuídas trabalhem em conjunto
• Grid Linux
Gerenciamento de Recursos – GRAM
Fornece uma interface uniforme para envio e controle de tarefas.
Serviço de Informação – MDS
Disponibiliza informações sobre a situação da Grid.
Serviço de Segurança – GSI» Autenticação única no Grid.» Autenticação de usuários em diferentes domínios administrativos.
Principais Serviços
2. Conceitos e TerminologiasVI Escola do CBPF
47
26776 U.S. 2753 China 1318 Japan 1017 India 750 U.K. 495 Italy 488 Germany 391 Brazil328 S. Korea306 Taiwan 268 France 241 Canada 211 Viet Nam 211 Spain 202 Russia 187 Pakistan 159 Australia 142 Singapore 131 Greece 119 Colombia 111 Poland 109 Netherlands 107 Thailand 94 Switzerland 77 Chile 74 Sweden
68 Belgium 66 Venezuela 66 Romania 64 Indonesia 62 Mexico 61 Turkey 60 Malaysia 58 Portugal 57 Austria 54 Ireland 44 Hong Kong 40 Hungary 38 Egypt 38 Argentina 34 Uruguay 31 Ukraine 29 Slovakia 25 Israel 23 Yugoslavia 23 Iran 22 Bulgaria 22 Uzbekistan 22 Czech Rep. 22 N. Korea21 Lithuania 21 Croatia
20 Finland 20 New Zealand 17 Nigeria 17 South Africa 16 Jordan 16 Slovenia 16 Afghanistan 15 Denmark 15 Philippines 14 Vanuatu 14 Luxembourg 14 Tunisia 12 Virgin Is. (U.K.) 12 Peru 12 Yemen 11 Norway 11 Algeria 11 Armenia 10 Iceland 9 Zambia 9 Virgin Is. (U.S.) 9 Uganda 9 Bosnia & Herz. 8 Kenya 7 Zimbabwe 7 Saudi Arabia
7 Ecuador 7 Macedonia 6 Bolivia 6 Comoros 6 Zaire 6 Lebanon 5 Puerto Rico 5 Namibia 5 Togo 5 Tajikistan 5 Paraguay 5 Albania 5 Sudan 4 Estonia 4 Camaroon4 Ghana 4 Tuvalu 4 Costa Rica 4 Cuba 4 UAE 4 Tonga 4 W. Samoa 4 Tanzania 3 Syria3 Bahamas 3 Ethiopia
3 Mongolia 3 Sri Lanka 3 Wallis & Futuna Is. 3 Belarus 3 Bangladesh 2 Falkland Islands 2 Kuwait 2 Sierra Leone 2 Trinidad & Tobago 2 Guyana 2 American Samoa 2 Andorra 2 Georgia 2 Cook Islands 2 Turkmenistan 2 Gabon 2 The Gambia 2 Kazakhstan 2 Macau 2 Malta 2 Jamaica 2 Latvia 2 Turks & Caicos1 Bhutan 1 Ascension Island1 Cyprus
1 Mozambique 1 Tokelau1 Greenland 1 Nepal 1 Swaziland 1 Iraq 1 Serbia 1 Barbados 1 Cambodia 1 Qatar 1 Saint Vincent1 Laos 1 San Marino 1 Libya 1 Benin 1 Angola 1 Chad 1 Gibraltar 1 Haiti 1 Guatemala 1 Malawi 1 Equatorial Guinea 1 Palau 1 Bermuda 1 Botswana 1 Suriname
38
66
9 d
ow
nlo
ad
s in
20
04
fro
m g
lob
us.
org
Top 10
Globus Download2. Conceitos e Terminologias
26776 U.S. 2753 China 1318 Japan 1017 India
750 U.K. 495 Italy 488 Germany 391 Brazil328 S. Korea306 Taiwan
VI Escola do CBPF
48
GRID – Exemplo 1
7
2. Conceitos e TerminologiasVI Escola do CBPF
49
GRID – Exemplo 2Projeto de computação em Grade de maior repercussão
Característica: Incentivar usuários domésticos a incorporarem seus recursos à grade
Desvantagem: Impossibilidade de resolver problemas diversos
Signal analysis on a "work unit" of data recorded from the central 2.5 MHz wide band of the SERENDIP IV instrument.
The results are then automatically reported back to UC Berkeley.
Over 5 million computer users in more than 200 countries have signed up
Contribution over 19 billion hours of computer processing time
2. Conceitos e TerminologiasVI Escola do CBPF
50
GRID – Exemplo 3
http://www.grid.org
United Devices Community– Download a small program called the UD Agent – Put unused PC's resources to perform valuable scientific and medical research
without disturbing your usual computer use
Human Genome Project
Genetic Research
Cancer Research Project
Human Proteome Folding
Projects3,597,641Devices
1,318,395Members
2. Conceitos e TerminologiasVI Escola do CBPF
51
Grids & Cluster
Heterogeneidade – Componentes do Grid
Alta Dispersão Geográfica – Escala Mundial
Compartilhamento – Grid não é Dedicado
Múltiplos Domínios – Reúne informações de várias instituições
Controle Distribuído – Não existe uma entidade com controle total da Grid
Grids são mais distribuídos diversos e complexos que outras plataformas
2. Conceitos e TerminologiasVI Escola do CBPF
52
Sumário Aula 02
1. Introdução 2. Conceitos e Terminologia3.3. Arquitetura de MemArquitetura de Memóóriaria4. Modelos de Programação Paralela5. Projetando Programas em Paralelo6. Exemplo de Algoritmo Paralelo
VI Escola do CBPF
53
3. Arquitetura de MemóriaMemória Compartilhada
– Todos os processadores acessam toda a memória como um endereço global
– Múltiplos processadores podem acessar a memória independentemente
– Modificações em um dado é visível a todos os processadores
Memória de Acesso Uniforme (UMA) – Usado nos SMPs (multiprocessadores simétricos)– Igual acesso e tempo de acesso a memória– Com coerência de cache - CC-UMA (Cache Coherent UMA)
Memória de Acesso Não-Uniforme– Usa Link de acesso entre SMPs (lento)– Nem todos os processadores tem igual tempo de acesso a toda memória– Com coerência de cache - CC-NUMA
2 Classes
VI Escola do CBPF
54
Memória Distribuída
Sistemas de Memórias Distribuídas necessitam de estarem conectados entre si para acessar a memória do outro processador
– Cada processador tem sua memória local
– Não existe a idéia de espaço de endereçamento global
– Modificações na memória local não tem nenhum efeito na memória dos outros processadores
– O conceito de cache coerente não se aplica
– Quando um processador precisa de acessar os dados que estão na memória em um outro computador o programador explicita como e quandoos dados devem ser comunicados
3. Arquitetura de MemóriaVI Escola do CBPF
55
Sumário Aula 02
1. Introdução 2. Conceitos e Terminologia3. Arquitetura de Memória4.4. Modelos de ProgramaModelos de Programaçção Paralelaão Paralela5. Projetando Programas em Paralelo6. Exemplo de Algoritmo Paralelo
VI Escola do CBPF
56
4. Modelos de Programação ParalelaExistem vários modelos de programação paralela
– Memória Compartilhada– Threads– Passagem de Mensagens– Paralelismo de Dados– Paralelismo de Objetos– Híbrido
Modelos de programação em paralelo não dependem do hardware e da arquitetura de memória
Qual modelo deve ser usado está associado ao fabricante sendo uma escolha pessoal
Não existe o melhor modelo, embora exista certamente implementações melhores que outras
SGI Origin 300016 R16000 em cada nó
Arquitetura de Memória Compartilhada
Modelo Hibrido:Modelo de Passagem de Mensagens em uma máquina de memória compartilhada: MPI em uma SGI Origin
VI Escola do CBPF
57
Memória CompartilhadaAs tarefas compartilham o mesmo espaço de endereçamento de memória
– Leitura e escrita assincronamente
Vários mecanismos como “lock” ou semáforos são utilizados para controlar o acesso a memóriaNão existe a noção de “dono dos dados”, não há necessidade de comunicação de dados entre as tarefas. O desenvolvimento de programas é mais simples Uma desvantagem em termos de performance → mais difícil de gerenciar a localização dos dados
4. Modelos de Programação Paralela
Implementações: – Um compilador especial traduz as variáveis do programa em endereço de
memória que são globais – Não existe implementação comum para ambientes com memória compartilhada– Existem implementações que permitem ver a memória de dados de forma
continua mesmo se a memória física esteja distribuída– Exemplo: OpenMP → ambiente de desenvolvimento baseado em computação
paralela com memória compartilhada em Fortran e C/C++ (www.openmp.org)
VI Escola do CBPF
58
Threads - Linhas de ExecuçãoThread é uma maneira de um processo dividir a si mesmo em duas ou mais linhas de tarefas simultâneas
No modelo de programação paralela por Threads, um único processo pode ter várias linhas de execuções diferentes
Analogia é a concepção de um programa que inclui varias sub-rotinas
– O programa principal (a.out) realiza algumas trabalhos seriais, e cria threads que podem ser executadas pelo SO concorrentemente
– Cada thread tem dados locais, mas também, usa os recursos de a.out
– Cada thread se beneficia de visão da memória global de a.out
Neste modelo de programação pode-se executarqualquer sub-rotina ao mesmo tempo
tempo
4. Modelos de Programação ParalelaVI Escola do CBPF
59
Threads - Linhas de ExecuçãoThreads comunicam-se através da memória global
– Sincronização para garantir que mais de um thread não esteja atualizando o mesmo endereço de memória no mesmo instante
Thereads estão associados com arquiteturas de memória compartilhada e com o Sistema Operacional
As implementações de threads compreendem normalmente: – Uma biblioteca de sub-rotinas que são chamadas a partir de um código paralelo– Um conjunto de diretivas de compilação embutidos em um código serial– O programador é responsável pela determinação do paralelismo
Threads são antigos em computação– Historicamente os fabricantes de hardware
implementam versões proprietárias– Implementações bem diferentes e isto
dificulta a portabilidade dos programas
Esforços de padronizações resultou naimplementação do POSIX Threads
Microsoft tem sua implementação de threads
POSIX - Portable Operating System Interface, with the X signifying the Unix heritage of the API
4. Modelos de Programação ParalelaVI Escola do CBPF
60
Passagem de MensagensModelo de programação por passagem de mensagens tem as seguintes características:
– Conjunto de tarefas usando sua própria memória – As tarefas podem estar na mesma máquina física ou em outros máquinas – Tarefas trocam dados através de comunicações enviando e recebendo
mensagens– Dados transferidos requerem operações cooperativas para a realização do
processo– Exemplo: uma operação de envido (send) deve estar associada a uma
operação de recebimento (receive)
4. Modelos de Programação ParalelaVI Escola do CBPF
61
Passagem de MensagensImplementações:
– A implementação de passagem de mensagens compreende uma biblioteca de sub-rotinas que são inseridas no código fonte
– O programador é responsável na determinação o paralelismo
Várias bibliotecas de passagem de mensagem foram disponibilizadas desde 1980
– As implementações era bem diferentes uma das outras sendo muito difícil manter a portabilidade das aplicações
O MPI Forum estabeleceu um padrão para a implementação de passagem de mensagens
– 1994 → MPI versão 1 (Interface para Passagem de Mensagens)– 1996 → MPI-2 (Memória Remota, E/S Paralela ...)– As especificações estão disponíveis em: www-unix.mcs.anl.gov/mpi– É o padrão para passagem de mensagens– Quase todas as plataformas atuais oferecem pelo menos uma implementação
de MPI – Implementação portável do MPI – MPICH
– Desenvolvido pelo Argonne National Laboratory
4. Modelos de Programação ParalelaVI Escola do CBPF
62
Paralelismo dos DadosMuito do paralelismo esta focado em operações nos dadosNormalmente os dados são organizado em estruturasVárias tarefas trabalham na mesma estrutura, porém cada tarefa trabalha em regiões diferentes da estrutura Tarefas realizam a mesma operação
Memória compartilhada → as tarefas acessam os dados pela memória global
Memória distribuída → a estrutura de dados é distribuída em cada uma das memórias locais
4. Modelos de Programação ParalelaVI Escola do CBPF
63
Paralelismo de ObjetosÉ o modelo mais recenteUtiliza o conceito de objetos distribuídos por uma redeObjetos encapsulam estadosSeus métodos (funções) e variáveis podem ser acessados por diferentes processadores para uma determinada finalidade
4. Modelos de Programação Paralela
Classe AMétodo 1Método 2
...Metodo N
......
P1 A[1].mA[1]
P2 A[2].mA[2]
PN A[N].mA[N]
N objetos são
instanciados
Array de objetos distribuídos
Exemplo: Charm++
VI Escola do CBPF
64
Sumário Aula 02
1. Introdução 2. Conceitos e Terminologia3. Arquitetura de Memória4. Modelos de Programação Paralela5.5. Projetando Programas em ParaleloProjetando Programas em Paralelo6. Exemplo de Algoritmo Paralelo
VI Escola do CBPF
65
Paralelização Manual x AutomáticaProjetar programas paralelos é na maior parte das vezes uma processo manual
O programador é quase sempre responsável pela identificação e implementação do paralelismo
O desenvolvimento manual de código paralelo é complexo, gasta-se muito tempo e é um processo iterativo
5. Projetando Programas Paralelos
Ferramentas foram criadas para ajudar a conversão de programas seriais em programas paralelos
O tipo de ferramenta mais comum é a paralelização pelo compilador ou pelo pré-processador
VI Escola do CBPF
66
Paralelização Manual x AutomáticaUm compilador que paraleliza um código funciona de duas formas
1. Totalmente automático– O compilador analisa o código fonte e identifica oportunidades de paralelismo.– Loops (do, for) são as partes mais utilizadas para paralelização automática
2. Diretivas de programação → manual– Uso de diretivas de compilação onde o programador explicita ao compilador como
paralelizar o código– Pode ser utilizado em conjunto com algum grau de paralelização automática– Para os iniciantes, com códigos serial simples, a paralelização automática é a mais
indicada– GNU UPC - A GCC-Based Compilation and Execution Environment for the Unified
Parallel C (UPC) Language (Hello World)
5. Projetando Programas Paralelos
Existem vários problemas na paralelização automática– Resultados errados– Baixa performance– Muito menos flexível que a paralelização manual– Limitado na maior parte aos Loops– Compiladores encontram dificuldade em códigos muito complexos
VI Escola do CBPF
67
Entendendo o Problema e o Programa
Exemplo de problema paralelizável– Cálculo da energia de uma molécula
• Calcular independentemente a energia para milhares combinações da molécula
• Encontrar qual tem a menor energia– Solução em paralelo
• Criar tarefas independentes para combinar as moléculas e calcular a energia
• Determinar em paralelo qual tem a menor energia
5. Projetando Programas Paralelos
O primeiro passo no desenvolvimento de um programa paralelo é determinar onde problema pode ser paralelizado
NAMD - Simulation of Large Biomolecular Systems
Exemplo de um problema não paralelizável– Cálculo da série de Fibonacci (1,1,2,3,5,8,13,...) pela fórmula:
F(k + 2) = F(k + 1) + F(k) • Problema não pode ser paralelizado pois não é independente• Calcular F(k + 2) usa-se F(k + 1) e F(k) • Termos não podem ser calculado independentemente e por
isso não pode ser paralelizavel The Numbers of Life
VI Escola do CBPF
68
Entendendo o Problema e o Programa ...
Identifique os “hotspots” do programa– Saiba onde o programa serial passa a maior parte do tempo– A maior parte de programas científicos passa a maior parte do tempo em
poucos lugares do programa – Use analisadores de performance – Ignore as partes do programa onde o uso de CPU é baixo
Identifique os gargalos do programa– Existem partes do programa que são lentas e/ou causam paradas na execução
do programa em paralelo? • Por exemplo, acesso de E/S normalmente fazem o programa ficar lento
– Reestruturar o programa para usar diferentes algoritmos a fim de reduzir ou eliminar partes lentas e desnecessárias
Identifique inibidores de paralelismo– Tipo de comum de inibidores de paralelismo é a dependência de dados
(Exemplo: série de Fibonacci)
5. Projetando Programas ParalelosVI Escola do CBPF
69
ComunicaçãoNecessidade de comunicação entre tarefas depende do problema
Não precisa-se de comunicação– Alguns tipos de problemas que podem ser decompostos e executados em
paralelo sem a necessidade de compartilhamento de dados entre as tarefas– Exemplo:
• Processamento de imagem P&B onde cada pixel deve ter sua cor invertida• Os dados da imagem podem ser distribuídos em tarefas que agem
independentemente• Estes tipos de problemas são chamados de bag-of-tasks. • Uma comunicação mínima entre tarefas é necessária
5. Projetando Programas Paralelos
Precisa-se de comunicação – A maioria das aplicações paralelas requerem tarefas que compartilham dados – Exemplo:
• Problema de simulação numérica de difusão de calor em 3-D requer que uma tarefa saiba os valores das temperaturas calculadas pelas tarefas adjacentes
• As mudanças nos dados dos vizinhos têm um efeito direto nos dados dessa tarefa
VI Escola do CBPF
70
Comunicação ...Existem inúmeros fatores que devem ser considerados quando se projeta sua própria comunicaçãoCusto da comunicação
– Comunicação entre tarefas implica em overhead– CPU e recursos serão utilizados para a comunicação quando deveriam estar
sendo usado para o cálculo– Comunicação freqüente requer algum tipo de sincronização entre tarefas, o que
resulta em tarefas esperando ao invés de calculando– Comunicação pode saturar a banda disponível
Latência x largura de banda– Latência é o tempo que se leva para enviar uma mensagem mínima (zero byte)
do ponto A ao ponto B (µs ou ns)– Largura de banda é a quantidade de dados que podem ser comunicados por
unidade de tempo (bps)– Enviar muitas pequenas mensagens pode causar o domínio da latência no
overhead de comunicação– Quase sempre é mais eficiente empacotar pequenas mensagens em
mensagens maiores
5. Projetando Programas ParalelosVI Escola do CBPF
71
Comunicação ...Visibilidade da Comunicação
– Com o modelo de passagem de mensagens, comunicação entre processos éexplicita no código sendo de responsabilidade do programador
– Com o modelo de paralelismo dos dados, comunicação é transparente ao programador, principalmente em arquiteturas de memória distribuída
– O programador pode não ser capaz de saber exatamente se a comunicação entre tarefas foi completada
Comunicação Síncrona ou Assíncrona– Síncrona necessita de algum tipo de "handshaking" entre as tarefas que estão
compartilhando dados– Isto pode ser explicito no código pelo programador, ou em níveis mais baixo sem
que o programador saiba– Síncrona normalmente bloqueia a comunicação entre tarefas (“block
communication”)
– Assíncrona permite que as tarefas transfiram dados de forma independentemente– Exemplo: tarefa 1 pode enviar uma mensagem a tarefa 2, e imediatamente
continuar fazendo seu trabalho. Quando a tarefa 2 irá receber os dados não interessa a tarefa 1
– Assíncronas são ditas como “non-blocking communications”
5. Projetando Programas ParalelosVI Escola do CBPF
72
Comunicação ...Escopo da Comunicação
– Saber quais tarefas devem se comunicar é critico durante o desenvolvimento do programa em paralelo
– Ponto a Ponto: envolve duas tarefas com uma das tarefas agindo como “sender/producer” dos dados e a outra como “receiver/consumer”
– Coletiva: envolve compartilhamento de dados entre mais de duas tarefas, que são quase sempre especificados com sendo membros de um grupo comum
5. Projetando Programas ParalelosVI Escola do CBPF
73
Comunicação ...Eficiência da Comunicação
– O programador irá definir os fatores que afetam a performance da comunicação
– Podem ser: • Qual o modelo de implementação deve ser usada
• Modelo de passagem de mensagens (MPI) pode ser mais rápido em um determinado hardware do que em outro
• Qual o tipo de operação de comunicação deve ser usado? Síncrono ou assíncrono? Qual das duas pode aumentar a performance?
• Rede – alguns fabricantes oferecem mais de uma rede de comunicação? Qual deve ser utilizada?
5. Projetando Programas ParalelosVI Escola do CBPF
74
Sincronização Barreira (Barrier)
– Cada tarefa realiza seu trabalho até que encontra uma barreira (“block”)– Quando a última tarefa chega até a barreira, todas as tarefas são sincronizadas– Na seqüência, normalmente uma seção serial do programa é executada– Em outros casos uma troca de informação entre as tarefas é realizada e estas
continuam suas atividades
Lock / Semáforo– Pode envolver várias tarefas – Tipicamente usado para “serializar” o acesso a um dado global ou uma parte do
código. Somente uma tarefa por vez pode usar o lock / semáforo / flag– Pode bloquear ou não a execução do programa
Operações de Sincronismo– Envolve somente as tarefas que estão executando a operação de comunicação– Quando uma tarefa realiza uma operação de comunicação, alguma forma de
coordenação é necessária– Exemplo: antes de enviar um dado uma tarefa pode necessitar de receber um
“acknowledgment” da tarefa que receberá o dado informando que está pronta
5. Projetando Programas ParalelosVI Escola do CBPF
75
Dependência dos DadosExiste quando a ordem dos comandos de execução afeta o resultado do programa
Dependência dos dados resulta do uso por diferentes tarefas das mesmas variáveis de armazenamento
Dependências são importantes para a programação paralela porque são um dos inibidores ao paralelismo
DO 500 J = MYSTART,MYENDA(J) = A(J-1) * 2.0
500 CONTINUE
Loop COM dependência de dados
Loop SEM dependência de dadostask 1 task 2------ ------
X = 2 X = 4. .. .
Y = X**2 Y = X**3
5. Projetando Programas ParalelosVI Escola do CBPF
76
Balanceamento de Carga (“Load Balancing”)
Refere-se a distribuição do trabalho entre as tarefas de modo que todas as tarefas sejam mantidas ocupadas o tempo todo
Pode-se considerar como uma minimização do tempo de “idle” da tarefa
Importante em programas paralelos por razões de desempenho– Se todas as tarefas estiverem sujeitas a um ponto de sincronização, a tarefa mais
lenta determinará o desempenho total
5. Projetando Programas ParalelosVI Escola do CBPF
77
Balanceamento de Carga ...(“Load Balancing”)
Como conseguir o BC– Dividir igualmente o trabalho que cada tarefa recebe– Operações em “array” onde cada tarefa executa trabalho similar, distribuir
uniformemente os dados entre as tarefas– Para os “loops” onde o trabalho em cada iteração é similar, distribuir
uniformemente as tarefas por iteração– Em máquinas heterogêneas com características de desempenho diferentes,
usar ferramentas da análise de desempenho a fim de detectar os desequilíbrios da carga
Balanceamento Dinâmico– Alguns problemas resultam em desequilíbrio de carga mesmo se os dados
estiverem bem distribuídos entre tarefas– Sparse arrays – alguns tarefas tem dados a serem processados enquanto
outras tem somente "zeros"– Adaptive grid methods – algumas tarefas podem necessitar de refinar seus
dados enquanto outras não– Quando uma quantidade de trabalho de cada tarefa é intencionalmente variável,
ou não pode ser predito, o melhor é usar um agendador de tarefas – Ao terminar seu trabalho a tarefa demanda um novo trabalho
– Pode ser necessário projetar algoritmos para detectar e corrigir desequilíbrios de carga dinamicamente
5. Projetando Programas ParalelosVI Escola do CBPF
78
GranularidadeRazão entre Computação / Taxa de Comunicação
– Medida qualitativa entre tempos de computação e de comunicação– Períodos de computação são normalmente separados de períodos
de comunicação para sincronização de eventos
Granularidade Fina– Maior freqüência nas comunicações – Facilita o balanceamento de carga – Processamento é menor do que a comunicação– Tende a diminuir a performance do programa – Alto custo de sincronização
Granularidade Grossa – Processamento é maior do que a comunicação – Pode permitir melhorar a performance do programa.– Dificulta o balanceamento de carga – Menor custo de sincronização
Qual é a melhor?– A granularidade mais eficiente dependente do algoritmo e do
ambiente de hardware utilizado– É um compromisso entre o “overhead” de comunicação e
sincronização e a velocidade de execução. – A própria natureza do problema pode limitar a granularidade
possível
5. Projetando Programas ParalelosVI Escola do CBPF
79
EscalabilidadePropriedade de um sistema paralelo de aumentar o speedup a medida que aumentamos o número de processadores
Dificuldades
Hardware – Um dos maiores gargalos é o tráfego de informação na rede que interliga os
processadores
– O aumento do número de processadores pode degradar a capacidade de comunicação da rede, diminuindo a performance do programa
Software – Alguns algoritmos trabalham melhor em certas escalas de paralelismo
– O aumento do número de processadores pode acarretar uma queda na eficiência durante a execução do programa
5. Projetando Programas ParalelosVI Escola do CBPF
80
Considerações de Performance
– Se nenhuma parte do código pode ser paralelizado → P=0 e o speedup = 1 – Se todo o código pode ser paralelizado → P = 1 e o speedup é infinito (teórico)– Se 50% do código pode ser paralelizado, o speedup = 2, (duas vezes mais rápido) – A relação muda quando introduzimos o número de processadores
5. Projetando Programas Paralelos
Lei de Amdahl - determina o potencial de aumento de velocidade a partir da porcentagem paralelizável do programa
P = tp / ttS = ts / ttP + S = 1
speedup = 1 / (1 – P)tt = tempo total de execuçãotp = tempo de execução da parte paralelats = tempo de execução da parte serial
P = fração paralela, N = número de processadores, S = fração serialspeedup = 1 / ( P/N + S )
Exemplo:tt = 100stp = 85sts = 15s
P = 0.85S = 0.15 speedup = 1 / (0.85/N + 0.15) 4,2610
6,30100
11speedupN
VI Escola do CBPF
81
Sumário Aula 02
1. Introdução 2. Conceitos e Terminologia3. Arquitetura de Memória4. Modelos de Programação Paralela5. Projetando Programas em Paralelo6.6. Exemplo de Algoritmo ParaleloExemplo de Algoritmo Paralelo
VI Escola do CBPF
82
6. Exemplo de Algoritmo ParaleloCálculo de PI
O valor de PI pode ser calculado de várias maneirasVamos considerar o seguinte método para calcular o valor de PI
1. Inscreva um círculo em um quadrado
2. Gere pontos aleatórios dentro do quadrado
3. Determine o número de pontos que caíram dentro do círculo
4. Faça r ser o numero de pontos dentro circulo dividido pelo numero de pontos gerados
5. PI ~ 4 r
6. Quanto mais pontos são gerados mais preciso é o número PI
VI Escola do CBPF
83
Algoritmo Serial para Calcular πPseudo código serial para cálculo de PI
A maior parte do tempo o programa passa executando o Loop “Do”
O programa paralela deve abordar uma solução para: • Cálculo computacional intenso • Mínima comunicação entre tarefas• Baixa operação de E/S
6. Exemplo de Algoritmo Paralelo
1. npoints = 100002. circle_count = 0
3. do j = 1,npoints4. generate 2 random numbers between 0 and 15. xcoordinate = random1 6. ycoordinate = random2 7. if (xcoordinate, ycoordinate) inside circle8. then circle_count = circle_count + 19. end do
10. PI = 4.0*circle_count/npoints
1. npoints = 100002. circle_count = 0
3. do j = 1,npoints4. generate 2 random numbers between 0 and 15. xcoordinate = random1 6. ycoordinate = random2 7. if (xcoordinate, ycoordinate) inside circle8. then circle_count = circle_count + 19. end do
10. PI = 4.0*circle_count/npoints
VI Escola do CBPF
84
Algoritmo Paralelo para Calcular πA estratégia para paralelisar
– Dividir o Loop em partes que podem ser executadas por tarefas independentes
Tarefas para o cálculo de PI:
1. Cada tarefa executa sua parte do Loop um certa número de vezes
2. Cada tarefa pode fazer seu trabalho sem requerer qualquer informação das outras tarefas (não existe dependência de dados)
3. Uma tarefa atua como master coletando os resultados
6. Exemplo de Algoritmo ParaleloVI Escola do CBPF
85
Algoritmo Paralelo para Calcular π
1. npoints = 10000 2. circle_count = 0 3. p = number of tasks4. num = npoints/p 5. find out if I am MASTER or WORKER 6. do j = 1,num 7. generate 2 random numbers between 0 and 1 8. xcoordinate = random19. ycoordinate = random2 10. if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1 11. end do12. if I am MASTER 13. receive from WORKERS their circle_counts14. compute PI (use MASTER and WORKER calculations)15. else if I am WORKER 16. send to MASTER circle_count17. endif
Pseudo código
6. Exemplo de Algoritmo ParaleloVI Escola do CBPF
Aula 2Computação Distribuída
de Alto Desempenho
Marcelo GiovanniMarcelo GiovanniNilton AlvesNilton Alves
Marcelo Portes de Albuquerque Marcelo Portes de Albuquerque
CBPFCentro Brasileiro de Pesquisas Físicas
VI Escola do CBPF – Rio de Janeiro17 a 28 de julho de 2006