Computação paralelae distribuída - DEINFOdeinfo.uepg.br/~ljsenger/2010/cpd/intro.pdf · 1...

1

Computaçãoparalela e distribuída

Aula 01Introdução

Prof. Dr. Luciano José Senger

Conteúdo

• Visão geral da disciplina• Introdução• Conceitos básicos• Arquiteturas paralelas• Introdução as tecnologias de software para

computação paralela

Visão geral da disciplina

• Pré-requisitos– Conceitos de programação– Linux ou similar– Recomendável

• Inglês• Compilador de textos LaTEX• Editor de textos vi

• Objetivos principais– Desenvolvimento de software paralelo com bibliotecas

de software– Arquiteturas alvo

• Arquiteturas com processamento simétrico (SMP)• Arquiteturas de memória distribuída (MIMD) construídas

com computadores pessoais

• Exploração da execução de instruções de máquina visando melhorar o desempenho da computação através de elementos de processamento quecooperam e comunicam entre si

• É a habilidade de programar em uma linguagem que permite que o programador torne explícito quais porções da computação podem ser executadas concorrentemente

• Técnica que permite aumentar a velocidade da computação através de caminhos de dados, memória e elementos de armazenamento múltiplos

• Processamento paralelo consiste na utilização de múltiplos processadorespara executar partes diferentes de um mesmo programa simultaneamente

Computação paralela: definições

Computação sequencial comparada com paralela Porque computação paralela?

• Reduzir o tempo de execução de aplicações (programas) sequenciais

• Permitir que aplicações que consomem grandes quantidades de memória possam ser executadas

• Melhorar a qualidade das soluções através da exploração do paralelismo

• Ao explorar a computação paralela, pode-se obter uma redução de custos na computação (p.e. Cluster x supercomputador)

• Crescimento em escala

• Tendência no desenvolvimento do hardware: manutenção de mesma velocidade de clock com aumento de número de elementosde processamento como uma forma de resolver as limitações de problemas físicos (p.e. aquecimento)

2

Onde a computação paralela tem sido empregada (Fonte: http://www.top500.org)?

Quais sistemas operacionais são mais empregados (Fonte:

http://www.top500.org)?

Quais aplicações?

• Simulação

• Previsão do tempo

• Projeto de aeronaves

• Sequenciamento genoma

• Dinâmica de fluidos

• Processamento de imagens

• Mineração de dados

• Criação de uma linguagem de programação paralela que permita que o programador deixe explícito quais partes do programa serãoexecutadas em paralelo

– Linguagem Occam, Ada

• Ferramentas de paralelização automática: compilador que aceita comoentrada um programa escrito em uma linguagem de programaçãosequencial e gera automaticamente um programa paralelo parauma determinada arquitetura

– Compiladores C e Fortran

• Extensão de linguagens de programação sequenciais, através da criaçãode API para programação concorrente

– MPI, PVM, OpenMP

• A melhorar alternativa depende da análise de custo, possibilidadede crescimento em escala, desempenho, natureza da aplicação e portabilidade

Como utilizar o paralelismo (ferramentas)?

• Elementos de processamento são representados por:– Processadores: em computadores com mais de um

processador

– Núcleos (cores): em computadores que tem um processadorcentral com vários elementos de processamento (p.e. Dual Core, Athlon)

– Nós: aglomerado de computadores (cluster)

– Estações de trabalho: rede de estações de trabalho

– Processador gráfico

• A definição depende do nível de exploração do paralelismo: por exemplo, um nó de processamentopode ser composto por vários processadores, cada um com vários núcleos

Arquiteturas paralelas Arquiteturas paralelas

• Classificação de Flynn: a mais utilizada– Organiza os computadores em relação aos fluxos

de instruções e dados– Quatro grupos

• SISD (Single instruction single data)• SIMD (Single instruction multiple data)• MISD (Multiple instruction single data)• MIMD (Multiple instruction multiple data)

– Outras classificações:• Organização de memória

– Compartilhada– Distribuída

• Acoplamento, etc...

3

13

Arquiteturas paralelas: SISD

• Existe uma únicaunidade de processamento, queexecuta fluxos de dados e instruções únicos

• Exemplo– Computadores de um

processador simples, que não implementanenhuma forma de paralelismo(funcional, pipeline, etc)

Instruções

14

Arquiteturas paralelas: variações do modelo SISD

• Há tempos o modeloSISD tem sidomelhorado, incorporando técnicasde processamentoparalelo ousuperescalar

– Pipeline

– Paralelismo em nívelde instrução

– Paralelismo funcional

15

Arquiteturas paralelas: detalhamento do modelo SISD com pipelining de instruções

Slide Source: Wikipedia, Flynn’s Taxonomy 16

Arquiteturas paralelas: modelo SIMD

• Único fluxo de instruçõesopera sobre um fluxomúltiplo de dados

• Cada elemento de processamento recebe a mesma instrução, oquemuda são os dados

• Exemplos– Computadores

paralelos antigos

– Tecnologia SSE

– Placas aceleradorasgráficas

Arquiteturas paralelas: detalhamento do modelo SIMD

B(I)=A(I)*4LOAD A(I)

MULT 4

STORE B(I)

TEMPO:

t1

t2

t3

LOAD A(1)

MULT 4

STORE A(1)

LOAD A(2)

MULT 4

STORE A(2)

LOAD A(3)

MULT 4

STORE A(3)

. . .

. . .

. . .

18

Arquiteturas paralelas: comparação entre os modelosSISD e SIMD

4

Not useful…

Slide Source: Wikipedia, Flynn’s Taxonomy

19

Arquiteturas paralelas: modelo MISD

• Não há arquiteturasque implementameste modelo

• Alguns autoresconsideram o pipelining umaforma de implementaçãoMISD

As of 2006, all the top 10 and most of the TOP500 supercomputers were based on a MIMD architecture

Slide Source: Wikipedia, Flynn’s Taxonomy

20

Arquiteturas paralelas: modelo MIMD

• Fluxos de instruçõesdiferentes operamsobre fluxos de dados também diferentes

• Podem ser organizadas em doisgrupos

– Memóriacompartilhada

– Memóriadistribuída

Arquiteturas paralelas: modelo MIMD

• Memória compartilhada– Chamados também de

multiprocessadores

– Todos os computadorescompartilham a mesmamemória

• Memória distribuída• Chamados também de

multicomputadores

• Os elementos de processamento comunicamatravés de troca de mensagens

Exemplos de arquiteturas MIMD

• Clusters– Conjunto formado por computadores de uso geral (PCs, estações de

trabalho) e interligados preferencialmente por uma rede de baixa latênciana comunicação

– gerenciado por um software, chamado de software de escalonamento (batchsystem)

Exemplos de Arquiteturas MIMD

• Redes de estações de trabalho• Permite utilizar computadores frequentemente ociosos

para o processamento paralelo• “Computador paralelo dos pobres”

• Máquinas de processamento altamente paralelo(MPPs)

• Computadores paralelos montados a partir de processadores de mercado e com redes dedicadas de comunicação

• exemplo:IBM SP2

E o software?

• É possivel obter uma execução paralela de váriasformas, empregando diferentes ferramentas (software)

• A ferramenta de software mais indicada dependerá de fatores como:

– Custo

– Adequação ao hardware

– Crescimento em escala

– Desempenho

– Aplicações legadas

• A computação paralela usa conceitos de programaçãoconcorrente

– Existe a necessidade de comunicação, sincronismo e controle da execução paralela