Introdução Processamento Paralelonbcgib.uesc.br/nbcgib/files/PP/Aula01_proce_paralelo.pdf · Introdução 4/31. Introdução Problemas de grande porte Processamento paralelo Velocidade

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 [email protected]

9 de Março de 2010

Introdução 1 / 31



Conteúdo

1 Introdução

2 Problemas de grande porte

3 Processamento paralelo

Introdução 2 / 31



Conteúdo

1 Introdução



Introdução 3 / 31



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




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









dade.



Introdução 5 / 31









dade.



Introdução 5 / 31









dade.



Introdução 5 / 31



Mecanismos das ciências e as engenharias

Por séculos

Introdução 6 / 31



Mecanismos das ciências e as engenharias

Atualmente

Simulações computacionais são mais baratas e confiáveis.

Introdução 7 / 31



Conteúdo

1 Introdução



Introdução 8 / 31



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



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



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




tomamos umagrade cúbica ondecada cubo temuma aresta de0.1km,





Á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





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.






dores atuais



gundo (1012)









dores atuais



gundo (1012)







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





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





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





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




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.




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.




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.




Conteúdo

1 Introdução






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.





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.





Arquitetura de Von Neumann





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.





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.





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,





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





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]





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





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





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





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?










por segundo?










por segundo?





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.




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.





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.





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.




Exemplo - Previsão do clima

Balanceamento de carga.




Exemplo - Previsão do clima

Balanceamento de carga.Introdução 31 / 31

Documents

Introdução Processamento Paralelonbcgib.uesc.br/nbcgib/files/PP/Aula01_proce_paralelo.pdf · Introdução 4/31. Introdução Problemas de grande porte Processamento paralelo Velocidade