Aula 02 - 1 - Mesonpi

CBPF
Centro Brasileiro de
Pesquisas Físicas
Aula 2
Computação Distribuída
de Alto Desempenho
Marcelo Portes de Albuquerque
Nilton Alves
Marcelo Giovanni
VI Escola do CBPF – Rio de Janeiro
17 a 28 de julho de 2006
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
2
VI Escola do CBPF
1. Introdução
O que é a Computação Paralela?
•
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
3
VI Escola do CBPF
Computação Paralela
1. Introdução
Computaçã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
4
VI Escola do CBPF
Computação Paralela
1. Introdução
Computaçã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)
– ...
5
1. Introdução
VI Escola do CBPF
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
O FUTURO:
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 !
6
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
7
VI Escola do CBPF
2 - Conceitos e Terminologias
Arquitetura 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
Projeto Básico
– A memória é utilizada para guardar os dados e as
instruções
John von Neumann
Matemático, Prof. Da Universidade de
Princeton e um dos construtores do ENIAC.
– 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
8
VI Escola do CBPF
2. Conceitos e Terminologias
Algumas Terminologias Gerais
Tarefa (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
9
2. Conceitos e Terminologias
VI Escola do CBPF
Algumas Terminologias Gerais
Speedup (Observado)
– Definido como
wall-clock time da execução serial
wall-clock time da execução em paralelo
– Indicador mais simples e mais usado para medida de performance de
programas paralelos
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)
10
2. Conceitos e Terminologias
VI Escola do CBPF
Classificação dos Computadores
Existem diferentes formas de classificar os computadores
Grande diversidades de arquiteturas computacionais
A mais usada é a Taxonomia1 de Flynn
– Classificação de ambientes de hardwares
Leva em consideração
Número de instruções executadas em paralelo
x
Conjunto de dados para os quais as instruções são submetidas
1 Taxonomia
SISD
SIMD
Single Instruction, Single Data
Single Instruction, Multiple Data
MISD
MIMD
Multiple Instruction, Single Data
Multiple Instruction, Multiple Data
refere-se à classificação das coisas
11
VI Escola do CBPF
2. Conceitos e Terminologias
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 único
Exemplo:
– Computador pessoal com processador convencional
– Computador serial (não paralelo)
Esta é a mais antiga e até hoje mais utilizada arquitetura de computador
12
VI Escola do CBPF
2. Conceitos e Terminologias
SIMD - Single Instruction, Multiple Data
Single Instruction
– As unidades de processamento executam a mesma instrução no mesmo ciclo de Clock
Multiple Data
– Cada unidade de processamento opera em dado diferente
Um tipo de computador paralelo
Tem 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
Exemplos: IBM 9000, Cray T90 etc.
Supercomputador CRAY T90 do Centro Nacional de
Supercomputação (CESUP-RS) da UFRGS
13
VI Escola do CBPF
2. Conceitos e Terminologias
MISD - Multiple Instruction, Single Data
Um ú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
14
2. Conceitos e Terminologias
VI Escola do CBPF
MIMD - Multiple Instruction, Multiple Data
Multiple 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 dia
Vários computadores modernos se encaixam nesta categoria
Exemplo: IBM BlueGene/L
Vários supercomputadores atuais, “Grids”,
multiprocessadores SMP, alguns PCs etc.
Photo credit: IBM Rochester
15
VI Escola do CBPF
2. Conceitos e Terminologias
BlueGene/C - Cyclops64
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 contain
many hundreds of computing nodes
Cyclops64 project aims to create the
first "supercomputer on a chip"
http://www.research.ibm.com/bluegene
16
2. Conceitos e Terminologias
VI Escola do CBPF
Classificação de Arquiteturas MIMD
Preocupação especial na forma como os processadores estão
conectados as memórias
– Multiprocessadores
– Multicomputadores
Multiprocessadores
(Memória Compartilhada)
Computadores
Computadores
Paralelos
Paralelos ee
Configurações
Configurações
Distribuídas
Distribuídas
MIMD
MIMD
Ambientes Fortemente Acoplados
Multicomputadores
(Memória Distribuída)
Ambientes Fracamente Acoplados
17
2. Conceitos e Terminologias
VI Escola do CBPF
Multiprocessadores
Fortemente 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
Configurações Genéricas de Multiprocessadores
P
P
P
P
P
P
P
P
Comutador
M
M
M
M
Configuração Compartilhada
Barramento
M – Memória
M
M
M
M
Configuração Comutada
P – Processador
18
2. Conceitos e Terminologias
VI Escola do CBPF
Multicomputadores
Caracterizados 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
Configurações Genéricas de Multicomputadores
M
M
M
M
M
M
M
M
P
P
P
P
P
P
P
P
Comutador
Configuração Compartilhada
Barramento
M – Memória
Configuração Comutada
P – Processador
19
2. Conceitos e Terminologias
VI Escola do CBPF
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
Processador
Processador
Processador
Processador
CACHE
Periféricos
Sistema
Sistema
de
de
E/S
E/S
CACHE
Processador
Processador
Processador
Processador
CACHE
CACHE
Memória
Configuração clássica de uma arquitetura SMP
Caracterizado por até dezenas de processadores compartilhando todos os
recursos disponíveis, executando um único sistema operacional
Os processadores são considerados simétricos pois tem o mesmo “custo” para
acessar a memória
20
VI Escola do CBPF
2. Conceitos e Terminologias
Outras Características de SMPs
Todos 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
21
VI Escola do CBPF
2. Conceitos e Terminologias
Exemplo de Sistemas SMP
Intel Xeon Processor-based 2p Server
22
VI Escola do CBPF
2. Conceitos e Terminologias
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
23
2. Conceitos e Terminologias
VI Escola do CBPF
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
Proc
Proc
C
E/S
...
Proc
Proc
Proc
Proc
C
C
M
...
E/S
Proc
Proc
Proc
Proc
C
C
...
M
E/S
...
Proc
Proc
C
M
Rede
Rede de
de Interconexão
Interconexão
Os ambiente computacionais de melhor performance atuais são sistemas MPP
– Earth Simulator, Blue Gene, ASCI White, ASCI Red etc.
24
VI Escola do CBPF
Earth Simulator
Clique aqui!
25
VI Escola do CBPF
2. Conceitos e Terminologias
Sistemas Distribuídos
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
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
• 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
26
VI Escola do CBPF
2. Conceitos e Terminologias
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
27
VI Escola do CBPF
2. Conceitos e Terminologias
Clusters Computacionais
Combinaçã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
Clusters Linux
São considerados sistemas “High
Performance Computing” (HPC)
pois fornecem grande poder
computacional
28
VI Escola do CBPF
2. Conceitos e Terminologias
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
29
2. Conceitos e Terminologias
VI Escola do CBPF
Clusters Beowulf
Clusters Beowulf são escaláveis em termos de performance e estão
baseados em hardwares comerciais e Linux
O que é Beowulf?
– Processadores comuns
Rede Local
Eth
GbE
Myrinet
Infiniband
Mestre
• Intelx86, Alpha, PPC
• Pode ter mais de um processador por nó
– Redes comuns
Nó 01
• Fast Ethernet, GbE, Myrinet, Infinband
– Sistema Operacional gratuito
Nó 02
• Linux, BSD
– Modelos de programação padronizados
Nó N
• MPI, PVM
Diagrama simplificado de um Cluster Beowulf
Sempre se pode melhorar o desempenho adicionando novas máquinas
30
2. Conceitos e Terminologias
VI Escola do CBPF
Submetendo Tarefas em Clusters
Realizado por um agendador de tarefas (Batch Scheduler)
Fila
Fila 1
Usuário
Usuário
Tamanho
Tamanho do
do job
job
Prioridade
Prioridade
Tipo
Tipo de
de recurso
recurso
etc.
etc.
#Proc
#Proc
Memória
Memória
Runtime
Runtime
etc.
etc.
Cluster #1
Fila 2
PBS, LSF, MAUI,
SGE, Condor, etc.
Fila N
Agendador de Tarefas
Tarefa
Cluster #2
Cluster #3
31
2. Conceitos e Terminologias
VI Escola do CBPF
Entendendo o Agendador de Tarefas
Recursos 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 Passo
1.
2.
3.
4.
5.
6.
Usuário submete uma tarefa à fila
Espera os recursos solicitados estarem disponíveis
O nó mestre envia a tarefa aos nós escravos que tem o recurso disponível
Os processadores alocados executam a tarefa
O gerenciador de tarefa retira-a da fila
Uma arquivo com saída é gerado
32
VI Escola do CBPF
2. Conceitos e Terminologias
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
33
2. Conceitos e Terminologias
VI Escola do CBPF
Computação de Alto Desempenho
Tendência atual → uso de HPCs para resolver grandes
desafios computacionais
Diferentes Plataformas para Alcançar Resultados
Sistemas
MPPs,
Vectoriais
Clusters HPC
Dedicados
Clusters de
Worksations
Objetivo
Performance
Absoluta
Boa relação
Preço/Performance
Aproveitar
processadores
ociosos
Velocidade de
Conexão
Máxima
Máxima, Boa
Impreciso
Modelo
Memória
Compartilhada
Passagem de
Mensagens
Proprietária
Rede
Barramento,
placa mãe
Myrinet,
Infiniband, GbE
Rede Local
TCP/IP
34
VI Escola do CBPF
2. Conceitos e Terminologias
Top500.org (Junho 2006)
Rank
Site
Computer
Proc.
Year
1
DOE/NNSA/LLNL
United States
BlueGene/L - eServer Blue Gene Solution
IBM
131072
2005
2
IBM Thomas J. Watson
Research Center
United States
BGW - eServer Blue Gene Solution
IBM
40960
2005
3
DOE/NNSA/LLNL
United States
ASC Purple - eServer pSeries p5 575 1.9 GHz
IBM
12208
2006
4
NASA/Ames Research
Center/NAS
United States
Columbia - SGI Altix 1.5 GHz, Voltaire Infiniband
SGI
10160
2004
5
Commissariat a l'Energie
Atomique (CEA)
France
Tera-10 - NovaScale 5160, Itanium2 1.6 GHz, Quadrics
Bull SA
8704
2006
6
Sandia National Laboratories
United States
Thunderbird - PowerEdge 1850, 3.6 GHz, Infiniband
Dell
9024
2006
7
GSIC Center, Tokyo Institute of
Technology
Japan
TSUBAME Grid Cluster - Sun Fire X64 Cluster, Opteron
2.4/2.6 GHz, Infiniband
NEC/Sun
10368
2006
8
Forschungszentrum Juelich
(FZJ)
Germany
JUBL - eServer Blue Gene Solution
IBM
16384
2006
9
Sandia National Laboratories
United States
Red Storm Cray XT3, 2.0 GHz
Cray Inc.
10880
2005
10
The Earth Simulator Center
Japan
Earth-Simulator
NEC
5120
2002
171
Petroleum Company (C)
Brazil
xSeries Cluster Xeon 3.06 GHz - Gig-E
IBM
1024
2004
35
VI Escola do CBPF
2. Conceitos e Terminologias
Top500 - Maiores Tendências
Crescimento
Crescimento do
do
uso
uso pela
pela Indústria
Indústria
36
VI Escola do CBPF
2. Conceitos e Terminologias
Top500 - Maiores Tendências
Os
Os Clusters
Clusters estão
estão
dominando
dominando
37
VI Escola do CBPF
2. Conceitos e Terminologias
Top500 - Maiores Tendências
GbE
GbE está
está
ganhando
ganhando espaço
espaço
38
VI Escola do CBPF
2. Conceitos e Terminologias
Top500 - Maiores Tendências
64
64 bits
bits
Processadores
Processadores Intel
Intel
são
são os
os escolhidos
escolhidos
pelos
pelos maiores
maiores HPC
HPC39
VI Escola do CBPF
2. Conceitos e Terminologias
Top500 - Maiores Tendências
Os
Os EUA
EUA tem
tem mais
mais de
de
60%
60% de
de poder
poder de
de
processamento!
processamento! 40
VI Escola do CBPF
2. Conceitos e Terminologias
Grids Computacionais
Grid é uma infra-estrutura que permite
a integração e colaboração de
organizações virtuais
Ian Foster and Carl Kesselman
http://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
41
detalhes como sua origem e a complexidade da malha de transmissão e distribuição.
VI Escola do CBPF
2. Conceitos e Terminologias
Organizações Virtuais
• Pessoas e recursos distribuídos
• Conectados pela rede
• Situados em domínios administrativos diferentes
• Compartilhando recursos, mesmos objetivos
• Dinâmico
R
R
R
R
R
R
R
R
R
R
R
R
VO-A
R
VO-B
42
VI Escola do CBPF
2. Conceitos e Terminologias
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
R
R
R
R
R
R
R
R
R
R
VO-A
R
VO-B
43
VI Escola do CBPF
Virtualização
2. Conceitos e Terminologias
União e compartilhamento de recursos heterogêneos com utilização otimizada
e o fornecimento automático correspondente à demanda
• Conexão automática das
aplicações aos serviços
Aplicações
Virtualização das Aplicações
Administrador
Serviços de
Distribuição
Virtualização da Infra-estrutura
• Provisionamento
Dinâmico
• Recuperação
automática de falhas
Servidores de
Execução
Sistemas Distribuídos
44
Fonte: The Grid: Blueprint for a New Computing Infrastructure (2nd Edition), 2004
2. Conceitos e Terminologias
VI Escola do CBPF
Integração de Sistemas Distribuídos
Grids são construídos e não comprados
– Integração com sistemas de outras instituições é necessário
Instituição 2
Instituição 1
Internet
Instituição 3
Instituição N
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
45
2. Conceitos e Terminologias
VI Escola do CBPF
Sistema de Integração em Grid
Sistema Globus
• 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
Principais Serviços
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.
46
26776 U.S.
2753 China
1318 Japan
1017 India
750 U.K.
495 Italy
488 Germany
391 Brazil
328 S. Korea
306 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
38669 downloads in 2004 from globus.org
VI Escola do CBPF
2. Conceitos e Terminologias
Globus Download
68 Belgium
20 Finland
66 Venezuela
20 New Zealand
66 Romania
17 Nigeria
64 Indonesia
17 South Africa
62 Mexico
16 Jordan
61 Turkey
16 Slovenia
60 Malaysia
16 Afghanistan
58 Portugal
15 Denmark
57 Austria
15 Philippines
54 Ireland
14 Vanuatu
44 Hong Kong
Luxembourg
26776 14
U.S.
40 Hungary2753 14
Tunisia
China
38 Egypt 1318 12
Virgin Is. (U.K.)
Japan
38 Argentina
Peru
1017 12
India
34 Uruguay
12 Yemen
750 U.K.
31 Ukraine
11 Norway
495
Italy
29 Slovakia
11 Algeria
48811Germany
25 Israel
Armenia
23 Yugoslavia39110Brazil
Iceland
3289S.
Korea
23 Iran
Zambia
22 Bulgaria 3069Taiwan
Virgin Is. (U.S.)
22 Uzbekistan
9 Uganda
22 Czech Rep.
9 Bosnia & Herz.
22 N. Korea
8 Kenya
21 Lithuania
7 Zimbabwe
21 Croatia
7 Saudi Arabia
Top 10
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 Camaroon
4 Ghana
4 Tuvalu
4 Costa Rica
4 Cuba
4 UAE
4 Tonga
4 W. Samoa
4 Tanzania
3 Syria
3 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 & Caicos
1 Bhutan
1 Ascension Island
1 Cyprus
1 Mozambique
1 Tokelau
1 Greenland
1 Nepal
1 Swaziland
1 Iraq
1 Serbia
1 Barbados
1 Cambodia
1 Qatar
1 Saint Vincent
1 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 47
1 Suriname
VI Escola do CBPF
2. Conceitos e Terminologias
GRID – Exemplo 1
48
7
VI Escola do CBPF
2. Conceitos e Terminologias
GRID – Exemplo 2
Projeto 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
49
VI Escola do CBPF
2. Conceitos e Terminologias
GRID – Exemplo 3
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
Projects
Members
1,318,395
Devices
3,597,641
Cancer Research Project
Human Genome Project
Genetic Research
Human Proteome Folding
http://www.grid.org
50
VI Escola do CBPF
Grids & Cluster
2. Conceitos e Terminologias
Grids são mais distribuídos diversos e complexos que outras plataformas
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
51
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
52
VI Escola do CBPF
3. Arquitetura de Memória
Memó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
2 Classes
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
53
VI Escola do CBPF
3. Arquitetura de Memória
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 quando
os dados devem ser comunicados
54
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
55
VI Escola do CBPF
4. Modelos de Programação Paralela
Existem 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
Modelo Hibrido:
Modelo de Passagem de Mensagens em uma máquina de
memória compartilhada: MPI em uma SGI Origin
SGI Origin 3000
16 R16000 em cada nó
Arquitetura de Memória Compartilhada
56
4. Modelos de Programação Paralela
VI Escola do CBPF
Memória Compartilhada
As 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ória
Nã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
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)
57
4. Modelos de Programação Paralela
VI Escola do CBPF
Threads - Linhas de Execução
Thread é 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
– Cada thread tem dados locais, mas também, usa
os recursos de a.out
tempo
– O programa principal (a.out) realiza algumas
trabalhos seriais, e cria threads que podem ser
executadas pelo SO concorrentemente
– Cada thread se beneficia de visão da memória
global de a.out
Neste modelo de programação pode-se executar
qualquer sub-rotina ao mesmo tempo
58
VI Escola do CBPF
4. Modelos de Programação Paralela
Threads - Linhas de Execução
Threads 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 na
implementaçã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
59
4. Modelos de Programação Paralela
VI Escola do CBPF
Passagem de Mensagens
Modelo 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)
60
4. Modelos de Programação Paralela
VI Escola do CBPF
Passagem de Mensagens
Implementaçõ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
61
VI Escola do CBPF
4. Modelos de Programação Paralela
Paralelismo dos Dados
Muito do paralelismo esta focado em operações nos dados
Normalmente os dados são organizado em estruturas
Vá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
62
4. Modelos de Programação Paralela
VI Escola do CBPF
Paralelismo de Objetos
É o modelo mais recente
Utiliza o conceito de objetos distribuídos por uma rede
Objetos encapsulam estados
Seus métodos (funções) e variáveis podem ser acessados por diferentes
processadores para uma determinada finalidade
Exemplo: Charm++
Array de objetos
distribuídos
A[1]
Classe A
Método 1
Método 2
...
Metodo N
N objetos
são
instanciados
A[2]
...
A[N]
P1
A[1].m
P2
A[2].m
...
PN
A[N].m
63
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
64
VI Escola do CBPF
5. Projetando Programas Paralelos
Paralelização Manual x Automática
Projetar 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
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
65
VI Escola do CBPF
5. Projetando Programas Paralelos
Paralelização Manual x Automática
Um 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)
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
66
VI Escola do CBPF
5. Projetando Programas Paralelos
Entendendo o Problema e o Programa
O primeiro passo no desenvolvimento de um programa paralelo é determinar
onde problema pode ser paralelizado
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
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
67
VI Escola do CBPF
5. Projetando Programas Paralelos
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)
68
VI Escola do CBPF
5. Projetando Programas Paralelos
Comunicação
Necessidade 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
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
69
VI Escola do CBPF
5. Projetando Programas Paralelos
Comunicação ...
Existem inúmeros fatores que devem ser considerados quando se projeta
sua própria comunicação
Custo 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
70
VI Escola do CBPF
5. Projetando Programas Paralelos
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”
71
VI Escola do CBPF
5. Projetando Programas Paralelos
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
72
5. Projetando Programas Paralelos
VI Escola do CBPF
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?
73
VI Escola do CBPF
5. Projetando Programas Paralelos
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
74
5. Projetando Programas Paralelos
VI Escola do CBPF
Dependência dos Dados
Existe 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
Loop COM
dependência de dados
DO 500 J = MYSTART,MYEND
A(J) = A(J-1) * 2.0
500 CONTINUE
Loop SEM
dependência de dados
task 1
------
task 2
------
X = 2
.
.
Y = X**2
X = 4
.
.
Y = X**3
75
5. Projetando Programas Paralelos
VI Escola do CBPF
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
76
5. Projetando Programas Paralelos
VI Escola do CBPF
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
77
VI Escola do CBPF
5. Projetando Programas Paralelos
Granularidade
Razã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
78
VI Escola do CBPF
5. Projetando Programas Paralelos
Escalabilidade
Propriedade 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
79
5. Projetando Programas Paralelos
VI Escola do CBPF
Considerações de Performance
Lei de Amdahl - determina o potencial de aumento de velocidade a partir da
porcentagem paralelizável do programa
P = t p / tt
S = t s / tt
P+S=1
speedup = 1 / (1 – P)
tt = tempo total de execução
tp = tempo de execução da parte paralela
ts = tempo de execução da parte serial
– 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
speedup = 1 / ( P/N + S )
P = fração paralela, N = número de processadores,
S = fração serial
Exemplo:
tt = 100s
tp = 85s
ts = 15s
P = 0.85
S = 0.15
speedup = 1 / (0.85/N + 0.15)
N
1
10
100
speedup
1
4,26
6,30
80
VI Escola do CBPF
Sumário Aula 02
1.
2.
3.
4.
5.
6.
Introdução
Conceitos e Terminologia
Arquitetura de Memória
Modelos de Programação Paralela
Projetando Programas em Paralelo
Exemplo de Algoritmo Paralelo
81
VI Escola do CBPF
6. Exemplo de Algoritmo Paralelo
Cálculo de PI
O valor de PI pode ser calculado de várias
maneiras
Vamos 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
82
VI Escola do CBPF
6. Exemplo de Algoritmo Paralelo
Algoritmo Serial para Calcular π
Pseudo código serial para cálculo de PI
1.
1. npoints
npoints == 10000
10000
2.
2. circle_count
circle_count == 00
3.
3. do
do jj == 1,npoints
1,npoints
4.
generate
4.
generate 22 random
random numbers
numbers between
between 00 and
and 11
5.
xcoordinate
5.
xcoordinate == random1
random1
6.
ycoordinate
6.
ycoordinate == random2
random2
7.
if
7.
if (xcoordinate,
(xcoordinate, ycoordinate)
ycoordinate) inside
inside circle
circle
8.
then
8.
then circle_count
circle_count == circle_count
circle_count ++ 11
9.
9. end
end do
do
10.
10. PI
PI == 4.0*circle_count/npoints
4.0*circle_count/npoints
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
83
VI Escola do CBPF
6. Exemplo de Algoritmo Paralelo
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
84
VI Escola do CBPF
6. Exemplo de Algoritmo Paralelo
Algoritmo Paralelo para Calcular π
Pseudo código
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
npoints = 10000
circle_count = 0
p = number of tasks
num = npoints/p
find out if I am MASTER or WORKER
do j = 1,num
generate 2 random numbers between 0 and 1
xcoordinate = random1
ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1
end do
if I am MASTER
receive from WORKERS their circle_counts
compute PI (use MASTER and WORKER calculations)
else if I am WORKER
send to MASTER circle_count
endif
85
CBPF
Centro Brasileiro de
Pesquisas Físicas
Aula 2
Computação Distribuída
de Alto Desempenho
Marcelo Portes de Albuquerque
Nilton Alves
Marcelo Giovanni
VI Escola do CBPF – Rio de Janeiro
17 a 28 de julho de 2006