View
36
Download
0
Category
Preview:
Citation preview
IntroduçãoProblemas de grande porte
Processamento paralelo
Introdução Processamento Paralelo
Esbel Tomás Valero Orellana
Bacharelado em Ciência da ComputaçãoDepartamento de Ciências Exatas e Tecnológicas
Universidade Estadual de Santa Cruzevalero@uesc.br
9 de Março de 2010
Introdução 1 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Conteúdo
1 Introdução
2 Problemas de grande porte
3 Processamento paralelo
Introdução 2 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Conteúdo
1 Introdução
2 Problemas de grande porte
3 Processamento paralelo
Introdução 3 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Velocidade de processamento
A contínua busca por um maior poder de cálculo e proces-samento tem sido a força principal no desenvolvimento dohardware de computadores;
Período 1950 1970 1990 200‘5 MetaNro. Operações 102 103 106 109 1012
A necessidade de maior poder de computo é sempre cres-cente.
Introdução 4 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Velocidade de processamento
Qual é a causa desta necessidade sempre crescente por
maior poder computacional?
A resolução de problemas complexos nos leva a níveis mais
profundos de conhecimentos.
Diversa áreas da vida moderna impulsionam esta necessi-
dade.
São as ciências e as engenharias os elementos que mais
exigem poder computacional. Porque?
Introdução 5 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Velocidade de processamento
Qual é a causa desta necessidade sempre crescente por
maior poder computacional?
A resolução de problemas complexos nos leva a níveis mais
profundos de conhecimentos.
Diversa áreas da vida moderna impulsionam esta necessi-
dade.
São as ciências e as engenharias os elementos que mais
exigem poder computacional. Porque?
Introdução 5 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Velocidade de processamento
Qual é a causa desta necessidade sempre crescente por
maior poder computacional?
A resolução de problemas complexos nos leva a níveis mais
profundos de conhecimentos.
Diversa áreas da vida moderna impulsionam esta necessi-
dade.
São as ciências e as engenharias os elementos que mais
exigem poder computacional. Porque?
Introdução 5 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Velocidade de processamento
Qual é a causa desta necessidade sempre crescente por
maior poder computacional?
A resolução de problemas complexos nos leva a níveis mais
profundos de conhecimentos.
Diversa áreas da vida moderna impulsionam esta necessi-
dade.
São as ciências e as engenharias os elementos que mais
exigem poder computacional. Porque?
Introdução 5 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Mecanismos das ciências e as engenharias
Por séculos
Introdução 6 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Mecanismos das ciências e as engenharias
Atualmente
Simulações computacionais são mais baratas e confiáveis.
Introdução 7 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Conteúdo
1 Introdução
2 Problemas de grande porte
3 Processamento paralelo
Introdução 8 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Problemas de grande porte
A resolução de um problema computacional deve ser feita
em um tempo razoável.
Temos um problema de grande porte se ele não pode ser
resolvido em intervalo de tempo razoável com os computa-
dores atuais.
Tempo razoável?
Exemplo: Previsão do clima no Brasil nos próximos dois
dias.
Introdução 9 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Problemas de grande porte
A resolução de um problema computacional deve ser feita
em um tempo razoável.
Temos um problema de grande porte se ele não pode ser
resolvido em intervalo de tempo razoável com os computa-
dores atuais.
Tempo razoável?
Exemplo: Previsão do clima no Brasil nos próximos dois
dias.
Introdução 9 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
Computadores atuais um bilhão (109) operações de ponto
flutuante por segundo,
Objetivo fazer uma previsão do tempo para o Brasil a cada
hora nos próximos dois dias,
Incógnitas: temperatura, pressão, humidade, velocidade do
vento, exct.
Discretização do problema: cobrir a região de interesse
com uma grade e calcular as variáveis em cada vértice,
Introdução 10 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
tomamos umagrade cúbica ondecada cubo temuma aresta de0.1km,
Introdução 11 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
Área do Brasil é de 8.5 milhões de km2
8.5E +06 km2 × 20km × 103 cubos por km3 = 1.7E +11 vértices
Consideremos 100 operações aritméticas para determinar
o tempo em um vértice,
Para prevermos o tempo em uma determinada hora temos
1.7E + 11 vértices ×100 operações = 1.7E + 13 operações
Nosso problema 2 dias = 48 horas, temos
1.7E+13 operações×48 horas = 8.2E+14 ≈ 1E+15 operações
Introdução 12 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
Tempo necessário para resolver o problema nos computa-
dores atuais
1015 operações /109 operações por s = 106 s ≈ 11 dias!!!
Computador mais veloz, um trilhão de operações por se-
gundo (1012)
1015 operações /1012 operações por s = 103 s ≈ 20 min!!!
Modificações simples no problema anterior fazem um com-
putador de um trilhão de operações insuficiente.
Introdução 13 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
Tempo necessário para resolver o problema nos computa-
dores atuais
1015 operações /109 operações por s = 106 s ≈ 11 dias!!!
Computador mais veloz, um trilhão de operações por se-
gundo (1012)
1015 operações /1012 operações por s = 103 s ≈ 20 min!!!
Modificações simples no problema anterior fazem um com-
putador de um trilhão de operações insuficiente.
Introdução 13 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsões climáticas
Tempo necessário para resolver o problema nos computa-
dores atuais
1015 operações /109 operações por s = 106 s ≈ 11 dias!!!
Computador mais veloz, um trilhão de operações por se-
gundo (1012)
1015 operações /1012 operações por s = 103 s ≈ 20 min!!!
Modificações simples no problema anterior fazem um com-
putador de um trilhão de operações insuficiente.
Introdução 13 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Movimento de corpos estelares
Problema: Estimar as posições dos corpos estelares,
Cada corpo estelar é atraído por todos os outros por forçasgravitacionais,
O movimento de um corpo é modelado calculando a forçade todos os corpos que atuam sobre ele,
Se temos N corpos teremos N − 1 forças atuando sobreele,
Aproximadamente N2 operações para determinar a posi-ção de todos os corpos,
Após determinamos as posições dos corpos o cálculo érepetido (iterativo),
Introdução 14 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Movimento de corpos estelares
Problema: Estimar as posições dos corpos estelares,
Cada corpo estelar é atraído por todos os outros por forçasgravitacionais,
O movimento de um corpo é modelado calculando a forçade todos os corpos que atuam sobre ele,
Se temos N corpos teremos N − 1 forças atuando sobreele,
Aproximadamente N2 operações para determinar a posi-ção de todos os corpos,
Após determinamos as posições dos corpos o cálculo érepetido (iterativo),
Introdução 14 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Movimento de corpos estelares
A galaxia tem aproximadamente 1011 estrelas,
Se cada operação fosse feita em 1 µs (estimativa otimista),
(1011)2 operações = 1022 operações ×10−6s por operação =
1016 s ≈ 1 bilhão de anos!!!
Isso para uma iteração,
Mesmo aprimorando o algoritmo para N lg N, o tempo de
cálculo é aproximadamente 1 ano!!!
Introdução 15 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Movimento de corpos estelares
A galaxia tem aproximadamente 1011 estrelas,
Se cada operação fosse feita em 1 µs (estimativa otimista),
(1011)2 operações = 1022 operações ×10−6s por operação =
1016 s ≈ 1 bilhão de anos!!!
Isso para uma iteração,
Mesmo aprimorando o algoritmo para N lg N, o tempo de
cálculo é aproximadamente 1 ano!!!
Introdução 15 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Outros exemplos
Simulações de biomoléculas;
Simulações estocásticas, métodos de Monte Carlo;
Prospecção e exploração de hidrocarbonetos;
Biotecnologia (genoma, árvores filogéneticas);
Processamento de imagens (renderização de filmes, efei-
tos especiais);
Nanotecnologias.
Introdução 16 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Capacidade de armazenamento
Poder computacional = velocidade de realizar operações
aritméticas?
Para obtermos elevado poder computacional necessitamos
grandes capacidades de armazenamento;
Um computador que realize trilhões de operações por se-
gundo e tenha acesso a poucos milhões de palavras de
memória, tem pouca utilidade.
Poder computacional = Velocidade + Armazenamento.
Introdução 17 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Capacidade de armazenamento
Poder computacional = velocidade de realizar operações
aritméticas?
Para obtermos elevado poder computacional necessitamos
grandes capacidades de armazenamento;
Um computador que realize trilhões de operações por se-
gundo e tenha acesso a poucos milhões de palavras de
memória, tem pouca utilidade.
Poder computacional = Velocidade + Armazenamento.
Introdução 17 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Conteúdo
1 Introdução
2 Problemas de grande porte
3 Processamento paralelo
Introdução 18 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Desejamos construir um computador capaz de realizar um
trilhão de operações (1012) por segundo,
Enfoque → Aprimorar as tecnologias existentes para fabri-
car o novo computador,
Construir um computador seguindo a arquitetura de Von
Neumann,
Processador de alta velocidade e grande quantidade de
memória disponível.
Introdução 19 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Desejamos construir um computador capaz de realizar um
trilhão de operações (1012) por segundo,
Enfoque → Aprimorar as tecnologias existentes para fabri-
car o novo computador,
Construir um computador seguindo a arquitetura de Von
Neumann,
Processador de alta velocidade e grande quantidade de
memória disponível.
Introdução 19 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Arquitetura de Von Neumann
Introdução 20 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Objetivo: Executar o seguinte código em 1s
1 /∗ x , y , z ar rays de f l o a t s , cada um com ∗ /2 /∗ um t r i l h ã o de dados ∗ /3 for ( i =0; i <ONE_TRILLION ; i ++)4 z [ i ] = x [ i ] + y [ i ] ;
Execução do código na arquitetura de VN:
1 copiar os valores xi e yi da memória aos registradores,
2 somar os valores,
3 copiar o resultado zi na memória.
Introdução 21 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Objetivo: Executar o seguinte código em 1s
1 /∗ x , y , z ar rays de f l o a t s , cada um com ∗ /2 /∗ um t r i l h ã o de dados ∗ /3 for ( i =0; i <ONE_TRILLION ; i ++)4 z [ i ] = x [ i ] + y [ i ] ;
Execução do código na arquitetura de VN:
1 copiar os valores xi e yi da memória aos registradores,
2 somar os valores,
3 copiar o resultado zi na memória.
Introdução 21 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
3.0E + 12 transferências de dados entre a memória e osregistradores em 1s,
Os dados viajam a velocidade da luz 3.0E + 08 m/s(suposição otimista),
r → distancia média entre a memória e a CPU,
Introdução 22 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Um pouco de física básica, r satisfaz:
v =st
s = vt
3.0× 1012r [m] = 3.0× 1012[m/s] ∗ 1[s]
r = 10−4[m]
A memória deve ter capacidade para três trilhões de
palavras (x , y , z).
Introdução 23 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Propomos um dispositivo de memórias quadrado de lado
s,
Conectamos a CPU no centro da memória,
A distancia média entre a memória e a CPU é s/2
s2
= r
s = 2.0× 10−4[m]
Introdução 24 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Em nossa memória uma linha do dispositivo deverá conter√
3× 106 palavras de memória,
palavras em uma linha = ( quantidade de palavras )12
√3× 1012 =
√3× 106
Introdução 25 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Calculamos o tamanho de uma célula de memória,
Devemos colocar uma palavra de memória em um
quadrado de lado
spalavras_em_uma_linha
=2× 10−4[m]√
3× 106= 10−10[m]
10−10[m] é o tamanho de um átomo pequeno,
Como representar 32 bits com um único átomo?
Construir nosso computador é impossível!!!
Introdução 26 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Calculamos o tamanho de uma célula de memória,
Devemos colocar uma palavra de memória em um
quadrado de lado
spalavras_em_uma_linha
=2× 10−4[m]√
3× 106= 10−10[m]
10−10[m] é o tamanho de um átomo pequeno,
Como representar 32 bits com um único átomo?
Construir nosso computador é impossível!!!
Introdução 26 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Entraves de aumentar a velocidade do processador
Aquecimento do processador
Alto consumo de energia elétrica
Como termos um computador que realize 1012 operações
por segundo?
Processamento paralelo
Introdução 27 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Entraves de aumentar a velocidade do processador
Aquecimento do processador
Alto consumo de energia elétrica
Como termos um computador que realize 1012 operações
por segundo?
Processamento paralelo
Introdução 27 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Construindo um computador potente
Entraves de aumentar a velocidade do processador
Aquecimento do processador
Alto consumo de energia elétrica
Como termos um computador que realize 1012 operações
por segundo?
Processamento paralelo
Introdução 27 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Definindo processamento paralelo
Computador paralelo é um computador simples (ou um grupo
de computadores) com múltiples processos que trabalham
juntos na resolução de um único problema.
Processo = processador + memória
Processamento paralelo fornece um poder de computo ili-
mitado (pelo menos em teoria),
Devemos instruir a nossos processos como trabalhar jun-
tos,
É preciso fornecer a cada processo um programa e um con-
junto de dados a serem computados.
Introdução 28 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Entraves processamento paralelo
Divisão de tarefas entre os processos
encontrar subtarefas independentes pode ser muito
complicado;
Organização da execução
iniciar, gerenciar e terminar processos,
precedência de operações,
distribuir as instruções;
Comunicação entre processos
processos adjacentes precisam se comunicar.
Introdução 29 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Entraves processamento paralelo
Processamento paralelo é uma ideia simples,
Se usarmos uma máquina paralela com p processos para
resolver um problema,
Obteremos o resultado p vezes mais rápido?
Isso não é certo, por vários motivos:
A paralelização tem custos,
Mecanismos de controle de falhas e acessos a memória,
Custos de comunicação,
Balanceamento de carga,
Os algoritmos não são completamente paralelizáveis.
Introdução 30 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Entraves processamento paralelo
Processamento paralelo é uma ideia simples,
Se usarmos uma máquina paralela com p processos para
resolver um problema,
Obteremos o resultado p vezes mais rápido?
Isso não é certo, por vários motivos:
A paralelização tem custos,
Mecanismos de controle de falhas e acessos a memória,
Custos de comunicação,
Balanceamento de carga,
Os algoritmos não são completamente paralelizáveis.
Introdução 30 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsão do clima
Balanceamento de carga.
Introdução 31 / 31
IntroduçãoProblemas de grande porte
Processamento paralelo
Exemplo - Previsão do clima
Balanceamento de carga.Introdução 31 / 31
Recommended