Computação Numérica e Programação Distribuída SIADM Nuno Pereira ESTIG - ADM

Computação Numérica e

Programação Distribuída

SIADM

Nuno Pereira

ESTIG - ADM

SIADM - Computação Numérica e Programação Distribuída

2

Conteúdo da Apresentação

• Computação Numérica

– Porquê?

– Como?

– Onde?

– Problemas.

– Tendências.

• Programação Distribuída

– Porquê?

– Como?

– Modelos.

– Metodologia.

– Problemas.

– Evolução.

– Ferramentas.

– Aplicações.


3

Computação Numérica: Porquê?

• Modelos matemáticos complexos

– Problemas sem solução analítica• Ex.: Equações diferenciais.

– Elevado número de equações• Ex.: Simulação de sistemas de partículas.

– Quantidade de dados elevada• Ex.: Inversão de uma matriz de 10000x10000.


4

Computação Numérica: Como?Etapas da R esolução de um P roblem a

R eso lu çã o d oP rob lem a

?

P rob lem aR ea l

M od e loF ís ico

R eso lu çaoA n a lit ica

S e lecçã o d oM é tod o N u m é rico

A lg oritm oS é rie

A lg oritm oD is trib u id o

M od e lo d eP rog ram açã o

+L in g u ag em

P rog ram aS é rie

P rog ram aD is trib u id o

S o lu çã oN u m é rica

R eso lu çã oN u m é rica

M od e loM atem á tico


5

Computação Numérica: Como?

• Utilização de métodos numéricos:

– Resolução de equações não-lineares.

– Integração e diferenciação.

– Sistemas de equações lineares e não-lineares.

– Equações diferenciais (ordinárias e parciais).

– Interpolação e extrapolação.


6

Computação Numérica: Como?

• Ferramentas de Cálculo Numérico:

– Mathematica ©– Axiom ©

– Mapple © – Gauss ©– MatLab ©

• Bibliotecas de Funções

– NAG ©– LAPACK ©– LINPACK ©


7

Computação Numérica: Onde?Investigação Científica

• Astrofísica

– Formação e evolução de um enxame de galáxias

– http://www.lanl.gov


8


• Cosmologia

– Evolução de larga escala.

– Simulação de 17 milhões de partículas num cenário CDM.



9


• Visualização

– Rotação de 16.7 milhões de partículas numa caixa de 100 Mpc (simul. CDM)



10


• Química

– Dinâmica Molecular

– Ex: Simulação do bombardeamento de uma superfície de Si por fluoreno (5 KeV).

– hppt://cnlswww.lanl.gov/ ~deardm/MolecularDynamics/ index.html


11

Computação Numérica: Onde? Investigação Científica

• Química

– Dinâmica Molecular

– Ex.: Impacto (500 eV) de fluoreno em grafite (C60)


12


• Bioquímica

– Métodos computacionais para estudo de processos de catálise de enzimas

– http://indigo15.carb.mst. gov/hpcc/proj-1.html


13


• Geofísica:

– Modelos do Clima

– Ex: Modelo de Circulação Geral da Atmosfera (Meteorological Research Institute)

– http://mriim1.mri-jma.go.jp


14

Computação NuméricaProblemas de Atitude

• “We assume that because a problem is familiar, it is no longer a problem.” Guckenheimer [2].

• Simulações complexas supondo que os métodos são fiáveis !

• Utilização de bibliotecas numéricas como produtos acabados.

• Necessidade de continuar a investigar algoritmos.


15

Computação NuméricaProblemas na Abordagem

• As questões de análise numérica não são consideradas centrais:

– Para alguns matemáticos são inferiores à demonstração de teoremas.

– Os cientistas da computação dedicam a sua atenção a problemas de linguística e de tecnologia de informação.

– Os cientistas computacionais de outras disciplinas acreditam que a “Lei de Moore” resolverá os seus problemas.


16

Computação NuméricaProblemas nas simulações

• Simulações ambiciosas:

– Modelo global do clima.

– Automóvel completo.

– Redes de energia eléctrica.

– Batalhas militares.

– Mercado de acções.

– Cérebro humano.

– Universo.

• Obstáculos:

– Interacção entre Subsistemas.

– Multiplicidade de Escalas.

– Efeito de Incerteza.


17

Computação Numérica Problemas nas simulações

P lan eam en tod e S is tem as

V erificaçã od e Teorias

F iab ilid ad e d oresu ltad os

C om p rom eteo en ten d im en to

d o com p ortam en tod o s is tem a g lob a l

D in â m icain te rn a

ig n orad a : In p u t/O u tp u t

H ie rá rq u ia d esu b s is tem as

In te racçã o en treS u b is tem as

D isp en d iosoou

im p oss íve l

A u m en to d ereso lu çã o e

d o n ú m ero d ep arâ m etros

R e laçã om ac ro-m ic ro

M ú lt ip lasE sca las

N ã o exiteu m a ab ord ag em

s is tem á tica

A va liaçã o d o e fe itod a in certeza d o

m od e lo n osresu ltad os com p .

V ariá ve isre levan tes

E fe itos d eIn certeza

S im u laçã oN u m é rica


18

Computação Numérica Tendências

• Presente:

– Previsões quantitativas das modernas teorias.

• Futuro:

– Modelos computacionais como modo dominante de expressão de teorias científicas.

• Posicionamento:

– reforço nas ciências da computação; essencial para o reforço destas junto das ciências e tecnologia.

• Praticar Computação Numérica com consciência.


19

Computação Numérica Problemas não numéricos associados

• Ordenação de dados– Aplicações estatísticas.

• Geração de Malhas– Mecânica de estruturas

e dinâmica de fluidos (elementos finitos).

• Movimentação de dados no computador

• Limitação da velocidade de cálculo

• Computação Distribuída


20

Computação Distribuída: Porquê?“Dividir para Reinar”

• Distribuir o domínio de computação por vários Elementos Processadores.

• Distribuir a carga computacional por vários EP’s

P ara le lizaçã od e u m P rob lem a

E sq u em a C on cep tu a l

Com u n icaçãoen tre EP 's

S 1 (D ad os+O p eraçõ es )

E lem en toP rocessad or





P rob lem a S :D ad os +

O p eraçõ es


21

Computação Distribuída: Como?Modelos de Programação Distribuída [1]

• “Message Passing”– Criação de múltiplas tarefas com dados locais que

comunicam através de mensagens.

• “Data Paralelism”– Explora a aplicação da mesma operação vários

elementos de uma estrutura de dados.

• “Shared Memory”– Todas as tarefas partilham o mesmo espaço de

endereçamento.


22

Computação DistribuídaMetodologia (PCAM) [1]

• Partição do problema– Identificar oportunidades de paralelização.

• Comunicação– Definição das estruturas de comunicação para a

execução da tarefa.

• Aglomeração de tarefas– Optimizar a eficiência (atendendo à classe do modelo).

• Mapeamento– Distribuição das tarefas por processador.


23

Computação Distribuída: Problemas.

• Objectivos a cumprir

– Escalabilidade

– Eficiência

– Balanço de Esforço computacional.

– Portabilidade.

• “Lei de Amdahl”

– O aumento de velocidade está limitado pela componente sequencial.

• Comunicação entre processadores– Largura de banda

– Tempos mortos.


24

Computação Distribuída Ferramentas de desenvolvimento

• PVM: Parallel Virtual Machine [1].

• MPI: Message Passing Interface [1].– Disponíveis para Linux

[3], [4].

• DIPC– Integrado em futuras

versões de Linux [5].

• Compositional C++

• Fortran M– extensões para

programação dist. [1].

• HPF: High Performance Fortran– extensão do F90.


25

Programação Distribuída:Evolução

• Informação retirada de [6] correspondente a 34 máquinas já não disponíveis comercialmente.

Distribuição da Vel. Pico Teórica

0,1

10,0

1000,0

1980 1985 1990 1995

Ano

Ve

loci

da

de

(G

Flo

p/s

)

Distribuição do Número de Processadores

1

10

100

1000

10000

100000

1980 1985 1990 1995

Ano

Nú

me

ro d

e P

roce

ssa

do

res


26

Programação Distribuída:Evolução

• Mercado altamente competitivo.

• Menos recursos financeiros para adquirir sistemas.

• Relação preço/desempenho está a baixar.

Relação Velocidade vs. Número de Processadores

0,10

1,00

10,00

100,00

1000,00

10000,00

1 10 100 1000 10000 100000Número de Processadores

Ve

loci

dad

e (

GFl

op

/s)


27

Programação Distribuída:Um exemplo: CM-2

• Thinking Machines Corporation

• Ano de introdução:1987

• Ano de saída: 1991

• Número máximo de processadores: 64K

• Velocidade de pico (teórica): 31 GFlop/s

• Referência [6].


28

Computação Distribuída: Aplicações.• Engenharia Aeroespacial.

• Análise e Modelação Comercial.

• Engenharia do Ambiente.

• Tecnologia Médica.

• Indústria dos Combustíveis.

• Processos Industriais.

• Visualização e Multimédia (video servers).• http://epcc.ed.ac.uk


29

Computação Distribuída: Aplicações

• UFAT: Usteady Flow Analysis Toolkit– Simulações numéricas 3D de fluxos não estacionários.

– CFD: “Computational fluid dynamics”.

• FAST: Flow Analysis Software Toolkit– Análise de dados de de simulações de CFD.

– Construção de objectos 3D e animação.

• http://science.nas.nasa.gov/Software


30

Computação Distribuída: AplicaçõesEngenharia Aeronáutica

• Simulação numérica do fluxo em torno de uma asa delta.


31

Computação Distribuída: AplicaçõesAeronáutica

• Simulação numérica do fluxo nas pás de um V-22.


32

Computação Distribuída: AplicaçõesEngenharia Aeroespacial

• FEL: Field Encapsulation Library– Representação de campos e malhas.

– Ex.: Campo de pressão e isolinhas.


33

Computação Distribuída: AplicaçõesSimulações CFD - Visualização de dados

• VWT: Virtual Windtunnel

– Utilização da tecnologia de realidade virtual para visualização de resultados de CFD.


34

Desafios do Futuro

• Programação:

– Desenvolvimento de Algoritmos Distribuídos

– Ferramentas de apoio ao programador

– Ambientes de trabalho distribuídos

– Sistemas operativos distribuídos

• “Hardware”

– Arquitecturas distribuídas

– Redes de elevada largura de banda

– “Hardware” específico• Ex.: GRAPE para

simulação de sistemas de partículas.


35

ConclusõesProgramação DistribuídaProgramação Distribuída

• “Futuro” da computação:– Aplicações científicas e comerciais.

• Investigação:– Pura e aplicada.

• Oportunidades de trabalho:– Científico e comercial.


36

Referências• [1] Foster, I.: Designing and Building Parallel Programs. Addison-

Wesley, 1994.

• [2] Guckenheimer, J.: Numerical Computation In the Information Age. SIAM NEWS, June 1998.

• [3] Konchady, M.: Parallel Computing Using Linux. Linux Journal, 78-81, Jan. 1998.

• [4] Sevenich, R. A.: Parallel Processing using Linux. Linux Journal, 14-18, Jan 1998.

• [5] Sharifi, M., Karimi, K.: DIPC: The Linux Way of Distributed Programming. ---Linux Journal, 10-17, Jan. 1999.

• [6] Van der Steen, A. J.: Overview of recent supercomputers. National Computing Facilities Foundation, The Netherlands, 1998.

Documents

Computação Numérica e Programação Distribuída SIADM Nuno Pereira ESTIG - ADM