Programação Paralela Simone de Lima Martins Março-Julho/2001 Universidade Federal do Mato Grosso do Sul Programação Paralela • • • • • • • • Conceitos gerais Programação por passagem de mensagens Computação embaraçosamente paralela Estratégia de divisão e conquista Computação pipelined Computação com sincronização Programação com memória compartilhada Algoritmos e aplicações Visão Geral • Processamento paralelo consiste na utilização de múltiplos processadores para executar partes diferentes de um mesmo programa simultaneamente • Principal objetivo é reduzir o tempo total de processamento (wall-clock time) • Número de trabalhadores versus aceleração obtida Objetivos • Reduzir tempo total de processamento (wall clock time) • Custo – execução em paralelo utilizando um grande número de estações de trabalho pode ser menor que utilizar um super computador • Recursos locais versus não locais • Restrições de memória Porque utilizar programação paralela ? • Aumento de desempenho de um único processador – capacidade de memória – desempenho • aumento do tamanho da palavra e da precisão utilizada – velocidade • tecnologia de substratos mais finos, mais transistores em menor espaço, maiores e mais rápidas vias de comunicação • Limites para esse aumento – Velocidade de transmissão faz com que módulos tenham que ser colocados relativamente perto um dos outros para não perder sincronização Porque utilizar programação paralela ? • Limites para esse aumento – Velocidade de transmissão faz com que módulos tenham que ser colocados relativamente perto um dos outros para não perder sincronização • Limites na minituarização dos componentes • Limites econômicos – aumento da velocidade dos processadores faz com que outros componentes tenham que ser modificados para trabalhar com maior velocidade aumento de custo – aumento da densidade de transistores • aumenta a complexidade do processo de preparação do substrato para a implementação da matriz de transistores e as ligações que os conectam e necessita-se desenvolver novos isoladores e dissipadores de calor Porque utilizar programação paralela ? • Problemas denominados grandes desafios demoram muito para serem resolvidos • Exemplos: – Previsão do tempo – Modelo de movimentação de corpos celestes • Processadores bastante rápidos disponíveis e baratos • Utilização de um maior número de processadores relativamente baratos em paralelo Taxonomia de Arquiteturas (Flynn 1966) Único Único Fluxo de instruções Múltiplo Fluxo de dados Múltiplo Single Instruction Single Data Single Instruction Multiple Data SISD SIMD Multiple Instruction Single Data Multiple Instruction Multiple Data MISD MIMD Single Instruction, Single Data (SISD) B(I)=A(I)*4 LOAD A(I) MULT 4 STORE B(I) TEMPO: Processador P t1 LOAD A(1) Processador P t2 MULT 4 Processador P t3 STORE A(1) Single Instruction, Single Data (SISD) • Serial – Instruções são executadas uma após outra • Determinismo – Pode-se saber o que está ocorrendo exatamente em cada instante de tempo e reproduzir o processo passo a passo mais tarde • Exemplos: – Computadores pessoais, estações de trabalho com uma única CPU, minicomputadores e mainframes Multiple Instruction, Single Data (MISD) • Existem poucas máquinas que se encaixam nessa definição • Exemplos de máquinas de propósito especial: – Múltiplos filtros de freqüência operando sobre um único fluxo de sinal – Múltiplos algoritmos de criptografia para decodificar uma mensagem Single Instruction, Multiple Data (SIMD) B(I)=A(I)*4 TEMPO: t1 t2 P1 P2 P3 LOAD A(1) LOAD A(2) LOAD A(3) P1 P2 P3 MULT 4 P1 t3 LOAD A(I) MULT 4 STORE B(I) STORE A(1) MULT 4 P2 STORE A(2) MULT 4 ... ... P3 STORE A(3) ... Single Instruction, Multiple Data (SIMD) • Síncrono – Todas as unidades devem receber a mesma instrução no mesmo instante de tempo de modo que todas possam executá-la de forma simultânea • Determinismo – Em cada instante de tempo só existe uma instrução sendo executada por várias unidades, então se o programa é executado com os mesmo dados de entrada, utilizando o mesmo número de unidades de execução, o resultado será o mesmo • Apropriado para aplicações que utilizam paralelismo orientado a instrução Single Instruction, Multiple Data (SIMD) • Exemplos: – Cambridge Parallel Processing Gamma II Plus • 1024 processadores em um array 32x32, ou 4096 em 64x64 • processador de controle armazena instruções e dados são armazenados na memória de cada processador – Quadrics Apemille • Máximo de 128 nós • Comunicação controlada por Controlador de memória e Controlador de comunicação do backplane – Hoje em dia existem poucos supercomputadores SIMD vetorizados pipelined Multiple Instruction, Multiple Data (MIMD) TEMPO: P1 P2 P3 Programa principal Inicializa Dispara tarefa A Dispara tarefa B Espera por processador Tarefa A Tarefa B Fim Dispara tarefa C Tarefa C Espera por processador Fim Dispara tarefa D Fim Espera fim de todas as tarefas Junta resultados Fim Tarefa D Fim Múltiple Instruction, Multiple Data (MIMD) • Síncrono ou assíncrono • Determinismo ou não determinismo – Sistemas MIMD pode ter comportamento determinístico tomando cuidado com alguns fatores, como a ordem de recepção das mensagens • Adequado para paralelismo orientado a bloco, loop ou subrotinas – Requerimentos de comunicação menos restritos que paralelismo orientado a instrução Múltiple Instruction, Multiple Data (MIMD) • Exemplos: – Assíncronos: • IBM SP ou clusters utilizando PVM, MPI – utilizado para aplicações com menor comunicação e acoplamento entre tarefas • Múltiplas unidades vetoriais trabalhando em um problema (Fujitsu VPP5000) • Hipercubos (nCube2S) e meshes (Intel Paragon) – Síncronos • IBM RS/6000 (4 instruções por ciclo) • Processadores capazes de executar instruções em modo pipelined requerem compiladores capazes de ordenar instruções para resolver dependência de dados Terminologia • Tarefa – Uma seção logicamente discreta de um trabalho computacional – Exemplos: • Calcular a transformada de Fourier • Calcular a média de 1000 valores • Tarefas paralelas – Tarefas cujo processamento é independente um dos outros • Execução serial – Execução de um programa de forma seqüencial, uma instrução de cada vez • SPMD (Single Program, Multiple Data) Problema paralelizável • Um problema que pode ser dividido em tarefas paralelas – Exemplos: • Calcular a energia potencial de cada uma das diferentes conformações de uma molécula e determinar aquela de menor energia potencial Paralelizável • Calcular a série de Fibonacci pela fórmula: F (k 2) F (k 1) F (k ) Não paralelizável Tipos de paralelismo • Paralelismo de dados – Cada tarefa executa uma mesma série de cálculos sobre diferentes dados – Localidade dos dados é parte essencial do algoritmo – Exemplos: • cálculo da média de temperatura em um estado, procura de pessoas com mais de 65 anos em uma população • Jogo de xadrez: tempo Lista de possíveis movimentos p1 m1 m2 m3 ... mn p2 p3 p4 p5 m1 m2 m3 m4 m6 m5 m7 m8 Tipos de paralelismo • Paralelismo funcional – Cada tarefa executa cálculos diferentes para resolver um problema – Tarefas podem ser executadas sobre mesmos dados ou dados diferentes – Exemplo: • Modelagem de um ecossistema, onde cada programa calcula a população de um determinado grupo que depende dos vizinhos Plantas Herbívoros Carnívoros Decompositores tempo p1 p2 p3 p4 de p4 para p1 Modelos de acesso à memória • Um computador convencional consiste de um processador executando um programa armazenado na memória: Memória principal Instruções para o processador Dados para ou do processador Processador • Cada lugar da memória possui um endereço que inicia em 0 e vai até 2n - 1, onde n é o número de bits do endereço Memória compartilhada P P ... P Interconexão • • • • • M ... M M A mesma memória é acessada pelos múltiplos processadores Sincronização entre tarefas é feita por escrita/leitura na/da memória compartilhada e usuário é responsável por sua especificação Um lugar da memória não pode ser modificado por uma tarefa enquanto outra o estiver acessando Comunicação entre tarefas é rápida Escalabilidade limitada pelo número de caminhos entre memória e processadores Memória compartilhada • SMP (Symetric MultiProcessors) utiliza esse modelo • Programação: – Linguagens de programação paralela • Construções e instruções paralelas permitem declarações de variáveis compartilhadas e seções paralelas de código • Compilador responsável pela geração do código final executável – Threads • Seqüências de código escritas em alto nível para processadores individuais que podem acessar localidades compartilhadas Memória distribuída M P M ... P Interconexão • • • • Memória fisicamente distribuída entre os processadores e cada memória local só pode ser acessada pelo seu processador Sincronização requer comunicação entre processadores através de troca de mensagens Problema na decomposição de domínio de dados Tarefas se comunicam através de troca de mensagens Memória distribuída • Programação: – Bibliotecas com rotinas para passagem de mensagens que são ligadas a programas seqüenciais convencionais são bastante utilizadas – Problema dividido em um número de tarefas – Tarefas se comunicam entre si pela troca de mensagens, único modo de distribuir dados e resultados entre elas Memória compartilhada distribuída M P M ... P Interconexão • • • Cada processador tem acesso à toda memória utilizando um único espaço de endereçamento de memória Para um processador acessar um lugar da memória que não está localizado na sua memória local, deve haver uma troca mensagens para que os dados sejam passados da memória para o processador ou dele para a memória de uma forma automática que esconde o fato da memória ser fisicamente distribuída Máquinas ccNUMA (Cache Coherent Non-Uniform Memory Access) Fator de aceleração (speedup) S (n) t tempode execuçãoserial s tempode execuçãoparalela t p • Para uma máquina paralela com n processadores, speedup ideal seria n (speedup linear) • S(n) > n, chamado de superlinear speedup – algoritmo seqüencial sub-ótimo – característica particular da arquitetura da máquina paralela • memória extra, por exemplo Speedup Processo 1 Processo 2 Computando Processo 3 Inclinação indica tempo para enviar mensagem Processo 4 Tempo Espera para enviar mensagem Mensagem Speedup máximo t s (1 f )ts ft s Seções paralelizáveis Seção serial Um processador Múltiplos processadores n processadores tp (1 f )t s n Speedup • O fator de speedup é dado por: S ( n) ts n ft s (1 f )t s / n 1 (n 1) f • Equação conhecida com Lei de Amdahl Lei de Amdhal 20 16 12 8 f=5% f=10% f=20% 4 4 8 12 16 20 Número de processadores Fator de speedup, S(n) Fator de speedup, S(n) f=0% 20 n=256 16 12 8 4 n=16 0.2 0.4 0.6 0.8 1.0 Fator serial, f • Mesmo com número infinito de processadores o speedup é limitado a 1/f • 5% de fração serial speedup máximo de 20, independente do número de processadores Eficiência E t tempo de execuçãoserial s tempo de execuçãoparalela númerode processadores t p n E S ( n) 100 % n • Eficiência fornece a fração de tempo que os processadores estão sendo utilizados para processamento Custo • Custo de um processamento é definido como: Custo tempode execução númerototalde processadores utilizados • O custo de uma execução seqüencial é simplesmente o tempo de execução ts • O custo de uma execução paralela e´: tp n ts t n s S ( n) E • Custo é considerado ótimo para um determinado algoritmo paralelo quando o custo da execução paralela é proporcional ao custo da execução seqüencial Sincronização • Necessária para coordenar troca de informações entre tarefas – Ex: Somente após todas as tarefas terem calculado a energia potencial de cada conformação de molécula, pode-se encontrar a molécula que possui a energia mínima • Pode consumir tempo de processamento, pois um processador pode ter que ficar esperando o término de tarefas em outros processadores • Fator de redução da aceleração (speedup), porque o tempo utilizado para esperar uma outra tarefa poderia ser utilizado para processamento Overhead de paralelismo • Tempo utilizado para coordenar as tarefas paralelas • Tempo para iniciar uma tarefa – – – – – identificação da tarefa procura de um processador para executá-la carregamento da tarefa no processador carregamento de dados necessários à execução da tarefa inicialização da tarefa • Tempo para terminar uma tarefa • Sincronização Granulosidade • Uma medida da razão entre a quantidade de computação realizada em uma tarefa paralela e a quantidade de comunicação necessária INÍCIO tempo granulosidade fina Tarefas paralelas geradas Execução serial Segundo ponto FIM de sincronização INÍCIO granulosidade grossa FIM Granulosidade • Nível de granulosidade varia de fina (muito pouco processamento por comunicação de byte) a grossa (muita comunicação por comunicação de byte) • Quanto mais fina a granulosidade, menor a aceleração devido à quantidade de sincronização exigida Granulosidade fina Nível de instrução Granulosidade grossa Loop com poucas iteraões Rotinas longas Escalabilidade • Escalabilidade de hardware ou de arquitetura – Aumento do tamanho do sistema aumenta o desempenho • capacidade de interconexão memória-processador e processadorprocessador • Escalabilidade do algoritmo – Algoritmo pode acomodar um aumento do tamanho do problema a ser tratado com um aumento baixo e limitado dos passos de computação • tamanho do problema: – número de elementos de dados sendo processados – duplicação de dados de entrada não leva necessariamente à duplicação do número de passos de computação » Ex: duplicar matrizes, duplica número de passos para adição de matrizes mas quadruplica número de passos para multiplicação – complexidade do melhor algoritmo seqüencial (O(n), O(log n)) Convertendo programas seriais em paralelos • Conversão manual versus automática – Conversão automática • Compiladores tentam fazer alguma paralelização automática de loops DO • Para obter bons speedups deve-se ter a ajuda de especialistas além do nível de automatização – Conversão manual • Programador gasta tempo paralelizando • Dicas para extrair paralelismo de códigos seriais – re-arranjar índices de loop para evitar interdependência de loops – chamadas a rotinas já paralelizadas e indicações (constructs) para préprocessadores ou geradores de código indicando tentativa de paralelismo que deve ser executada em parte do código serial – checar código gerado com constructs – reestruturação do algoritmo (tirar cálculo de um loop, por exemplo) Convertendo programas seriais em paralelos • Dependências gerais – Existe dependência entre instruções quando a ordem de execução delas afeta o resultado do programa – Dependência de dados resulta do uso múltiplo do mesmo local da memória – Exemplo: • Programa com 3 instruções: a=b+1;c=4-a;b=2a-c; • 3 dependências de dados • 3 instruções dependentes de execução Convertendo programas seriais em paralelos • Dependências gerais – Dependência de comunicação A B C send(B) send(C) send(A) blocking_ recv(C) blocking_ recv(A) blocking_ recv(B) – Problemas de execução devido à dependência entre tarefas paralelas Convertendo programas seriais em paralelos • Dependências em loops – Dependência independente no loop: local da memória é usado por instruções sucessivas em uma iteração, mas não por iterações diferentes pode ser paralelizado porque iterações do loop podem ser executadas de forma independente e assíncrona • Ex: DO 500 J=2,9 C[J]=A[J]+B[J] C[J]=C[J]*2.0 500 CONTINUE – Dependência carregada no loop: local da memória é utilizado por instruções, com pelo menos uma escrita, durante diferentes iterações do loop não pode ser paralelizado • Ex: DO 500 J=2,9 A[J]=A[J-1]*2.0 500 CONTINUE Convertendo programas seriais em paralelos • Dependências em loops – Dependência carregada no loop: local da memória é utilizado por instruções, com pelo menos uma escrita, durante diferentes iterações do loop não pode ser paralelizado Proc. 2 J=4,6 DO 500 J = 2,9 A(J) = A(J-1) * 2.0 500 CONTINUE A(4)=A(3)*2.0 A(5)=A(4)*2.0 A(2)=A(1)*2.0 Proc. 1 J=2,3 A(2)=A(1)*2.0 A(3)=A(2)*2.0 A(6)=A(5)*2.0 A(3)=A(2)*2.0 A(4)=A(3)*2.0 A(6)=A(5)*2.0 Proc. 3 J=7,9 A(7)=A(6)*2.0 A(7)=A(6)*2.0 A(8)=A(7)*2.0 A(8)=A(7)*2.0 A(9)=A(8)*2.0 A(5)=A(4)*2.0 A(9)=A(8)*2.0 Custo de desenvolvimento de um programa paralelo • Tempo do programador – análise do código para paralelizá-lo – re-escrita do código • Depuração complicada • Perda de portabilidade do código • Tempo gasto em todas as CPUs é contabilizado pelo centro de computação • Replicação de código e dados requer mais memória • Utilização de recursos por outros usuários