UNIVERSIDADE TÉCNICA DE LISBOA
INSTITUTO SUPERIOR TÉCNICO
Optimização e Avaliação de Aplicações de Simulação
Numérica
João Nuno de Oliveira e Silva
(Licenciado)
Dissertação para obtenção do grau de
Mestre em Engenharia Informática e de Computadores
Orientador: Doutor Paulo Jorge Pires Ferreira
Presidente: Doutor Paulo Jorge Tavares Guedes
Vogais: Doutor João Luís Ferreira Sobral
Doutor Paulo Jorge Pires Ferreira
Setembro 2002
Dissertação realizada sob a orientação do
Prof. Doutor Paulo Jorge Pires Ferreira
Professor Auxiliar do Departamento de Engenharia Informática
do Instituto Superior Técnico da Universidade Técnica de Lisboa
Nome: João Nuno de Oliveira e Silva
Título: Optimização e Avaliação de Aplicações de Simulação Numérica
Palavras-chave: Simulação Numérica, optimização, paralelização, Memória Paralela e
Distribuída
Keywords: Numerical Simulation, Code Optimization, Paralelization, Distributed
Shared Memory
Resumo
A simulação numérica é, cada vez mais, usada na substituição de experiências físicas. Na
indústria naval, as simulações de modelos de embarcações em tanques de ensaio é
passível de ser substituída por simulações numéricas. Com um esforço, adicional ao
desenvolvimento desses programas, consegue-se obter uma redução dos tempos de
simulação, tornando-os aplicáveis em todo o processo de desenho de embarcações.
A aplicação analisada é um simulador do comportamento hidrodinâmico de carenas de
embarcações. A necessidade de optimizar esta aplicação advêm de uma das características
desejadas ser a avaliação rápida dos cascos, cujos resultados influenciam alterações
futuras no seu desenho.
Para optimizar esta aplicação utilizaram-se diversas técnicas. Ao código que resolvia os
vários sistemas de equações, e que não manipulava estruturas dinâmicas, aplicaram-se
optimizações dependentes da arquitectura dos computadores. O código que manipulava
estruturas dinâmicas apenas foi optimizado aplicando técnicas dependentes do
processador (alteração do algoritmo).
Para além das optimizações, também se realizou a sua paralelização de algum código,
usando-se threads e Memória Partilhada e Distribuída. Com estas optimizações também se
conseguiu comparar a eficiência de diversas tecnologias de suporte à execução paralela de
aplicações: threads, PVM e Memória Partilhada e Distribuída.
Ao longo deste trabalho usaram-se diversas técnicas de avaliação de desempenho.
Em resumo, para além de termos conseguido tornar a aplicação de simulação mais usável,
reduzindo-lhe o tempo de execução, também se consegui experimentar e avaliar os
ganhos obtidos com a aplicação de várias técnicas sobre código com características
distintas.
i
Abstract
Numerical simulation became a good substitution of physical experiences. In Naval
industry, ship hull numerical simulation may be used instead of ship hull towing tank
experiment. With an additional effort, by reducing simulation time, we can apply these
numerical simulations to all the ship design and analysis process.
The analyzed application simulates the ship behavior in a towing tank experience. This
application must be optimized due to the fact that the results produced should be used in
subsequent phases of the ship design process.
In order to optimize this application we used several optimization techniques. In the
equation systems solver witch didn’t handle any dynamic structure we used machinelevel optimization. On the other hand, the code that handled dynamic structures was
optimized using application-level optimizations (algorithm changes).
Besides the optimizations, we also parallelized some of its code using threads and
Distributed Shared Memory. With these optimizations we also managed to compare the
efficiency of some parallel execution support platforms: threads. PVM and Distributed
Shared Memory.
During this work we also used some performance evaluation techniques.
With this work we not only managed to make the simulation application more usable, by
reducing the execution time, but also experienced and evaluate several optimization
techniques applied to distinct codes.
iii
Agradecimentos
Ao Professor Dr. Paulo Guedes pela orientação inicial na execução do trabalho aqui
descrito e ao Professor Dr. Paulo Ferreira pela orientação final e acompanhamento na
escrita deste documento.
A todos os elementos do Grupo de Sistemas Distribuídos que ao longo destes anos se
interessaram pelo trabalho por mim realizado e pelas ideias com eles discutidas.
Ao Professor Dr. Paulo Ferreira, Engº João Garcia e Engº Alfonso Sandoval pela leitura
atenta que fizeram a este documento.
Ao Eng. David Matos e Drª Luísa Coheur pelas consultas de orientação profissional ☺
gratuitas dadas ao longo destes últimos anos.
À malta do Aikido (Engº Artur Caetano, João Almeida e Isabel Bentes) pelas horas de descontracção partilhadas e pela descoberta de algo novo.
Finalmente, mas não menos sentido, aos meus Pais e Irmãos, pelo longo acompanhamento e imprescindível apoio dado durante toda a minha educação e formação.
João Nuno Silva
Lisboa, 1 de Setembro de 2002
v
Para quem ler…
vii
Índice
Resumo........................................................................................................................... i
Abstract ....................................................................................................................... iii
Agradecimentos........................................................................................................... v
Índice............................................................................................................................ ix
Índice de Figuras..................................................................................................... xiii
Índice de Tabelas ...................................................................................................... xv
1 Introdução ...................................................................................................1
1.1 Motivação ............................................................................................................... 1
1.2 Enquadramento ..................................................................................................... 2
1.3 Contribuições......................................................................................................... 3
1.4 Estrutura do Documento...................................................................................... 4
2 Trabalho Relacionado ..............................................................................5
2.1 Introdução .............................................................................................................. 5
2.2 Técnicas de Optimização de Código Sequencial............................................ 7
2.2.1 Optimizações não dependentes da plataforma ............................................... 8
2.2.2 Optimizações dependentes da plataforma .................................................... 11
2.2.2.1 Arquitectura do Pentium II .......................................................................... 11
2.2.2.2 Optimizações aplicáveis a Pentium II ........................................................ 18
2.3 Paralelização ........................................................................................................ 21
2.3.1 Arquitectura de Sistemas Paralelos .............................................................. 22
2.3.2 Comunicação entre tarefas em multiprocessadores ..................................... 28
2.3.2.1 Memória Partilhada....................................................................................... 28
2.3.2.2 Infra-estrutura de passagem de mensagens.............................................. 29
2.3.2.3 Distributed Shared Memory............................................................................. 32
ix
Optimização e Avaliação de Aplicações de Simulação Numérica
2.3.2.4 High Performance Fortran (HPF)....................................................................34
2.3.3 Optimizações aplicáveis a código paralelo ...................................................35
2.4 Lei de Amdahl ......................................................................................................35
2.5 Técnicas de avaliação de desempenho ............................................................36
2.5.1 Timers ...........................................................................................................37
2.5.1.1 Relógio do sistema .........................................................................................37
2.5.1.2 Contadores de alta precisão .........................................................................38
2.5.2 Contadores dos processadores ......................................................................39
2.5.3 Contadores do S.O. .......................................................................................40
2.5.4 Polling vs. Instrumentação............................................................................42
2.5.5 Software de profiling.....................................................................................43
2.5.5.1 Gprof.................................................................................................................43
2.5.5.2 Etch ...................................................................................................................44
2.5.5.3 Vtune ................................................................................................................45
2.6 Resumo e enquadramento .................................................................................46
3 Enquadramento........................................................................................47
3.1 Descrição do Projecto Flash ...............................................................................47
3.1.1 Arquitectura do sistema ................................................................................49
3.1.2 Aplicação de simulação ................................................................................50
3.1.3 Ambiente de execução ..................................................................................52
3.1.4 Participação do INESC .................................................................................54
4 Realização .................................................................................................55
4.1 Optimização do Solver (Conjugate gradient)..................................................55
4.1.1 Função Solve ..............................................................................................56
4.1.2 Função Atimes ...........................................................................................58
4.1.3 Função Asolve ...........................................................................................61
4.2 Paralelização do Solver (Conjugate gradient) .................................................62
4.2.1 Paralelização usando threads........................................................................62
4.2.2 Paralelização usando DSM ...........................................................................66
4.3 Optimização do simulador (aplicação FLASH) .............................................67
4.4 Paralelização do simulador (aplicação FLASH).............................................69
4.4.1 Servidor para execução de tarefas remotas (TreadMark) .............................73
4.5 Avaliação de desempenho das versões série..................................................74
x
Índice
4.5.1 Driver para leitura de contadores ................................................................. 74
4.6 Avaliação de desempenho das versões paralelas ......................................... 76
4.7 Resumo.................................................................................................................. 78
5 Avaliação ...................................................................................................81
5.1 Ambiente de teste ............................................................................................... 81
5.2 Optimização do Solver (Conjugate gradient) ................................................. 82
5.3 Paralelização do Solver (conjugate gradient) ................................................. 87
5.4 Optimização do simulador (aplicação FLASH)............................................. 88
5.5 Paralelização do simulador (aplicação FLASH) ............................................ 89
6 Conclusões ................................................................................................93
Apêndice A – Matrizes esparsas ......................................................................... 97
Apêndice B –
Conjugate Gradient...................................................................... 99
Bibliografia .............................................................................................................. 103
Glossário................................................................................................................... 107
xi
Índice de Figuras
Fig. 2.1 – Micro-arquitectura dos processadores da família P6 com Advance Transfer Cache
(cache de nível 2)...................................................................................................................12
Fig. 2.2 – Unidade de Execução ..................................................................................................15
Fig. 2.3 – Exemplo de uso não optimizado da cache ................................................................19
Fig. 2.4 – Exemplo de uso optimizado da cache........................................................................20
Fig. 2.5 – Alteração do acesso a vectores de modo a permitir a utilização de registos .....21
Fig. 2.6 – Arquitectura de multiprocessadores de memória partilhada com ligações........23
Fig. 2.7 – Exemplo da arquitectura de um computador multiprocessador vectorial .........24
Fig. 2.8 – Exemplo da arquitectura de um computador massivamente paralelo ................25
Fig. 2.9 – Configuração de um cluster formando dois sistemas paralelos independentes .27
Fig. 2.10 – Desempenho máximo de uma aplicação paralela segundo lei de Amdahl ......36
Fig. 3.1 – Arquitectura geral da plataforma de desenvolvimento e simulação das
embarcações .........................................................................................................................49
Fig. 3.2 – Vista conceptual do simulador (versão série)..........................................................50
Fig. 3.3 – Diagrama de classes simplificado do simulador.....................................................51
Fig. 3.4 – Exemplo de uma iteração da simulação ...................................................................52
Fig. 4.1 – Optimização da função solve ..................................................................................56
Fig. 4.2 – Implementação original da função atimes ............................................................58
Fig. 4.3 – Versão optimizada da função atimes .....................................................................60
Fig. 4.4 – Implementação original da função asolve ............................................................61
Fig. 4.5 – Versão paralela dum produto interno ......................................................................64
Fig. 4.6 – Multiplicação de uma matriz por um vector (versão série)...................................64
Fig. 4.7 – Multiplicação de uma matriz por um vector (versão paralela).............................65
xiii
Optimização e Avaliação de Aplicações de Simulação Numérica
Fig. 4.8 – Criação de um vector em memória partilhada e distribuída................................ 67
Fig. 4.9 – Conversão para matriz esparsa (versão não optimizada)..................................... 67
Fig. 4.10 – Conversão para matriz esparsa (versão optimizada) .......................................... 68
Fig. 4.11 – Envio dos dados necessário à criação do sistema de equações
(comunicação entre processos usando PVM) ................................................................. 70
Fig. 4.12 – Envio dos dados necessário à criação do sistema de equações
(comunicação entre processos usando DSM) ................................................................. 72
Fig. 4.13 – Envio da solução do sistema de equações
(comunicação entre processos usando DSM) ................................................................. 73
Fig. 4.14 – Inicialização de um contador do processador Pentium ...................................... 75
Fig. 4.15 – Leitura de um contador do processador Pentium................................................ 76
Fig. 4.16 – Programação necessária à leitura dos contadores do Windows ........................ 77
Fig. 4.17 – Leitura de um valor contabilizado num contador do Windows........................ 78
Fig. 5.1 – Tempos de execução da versão paralela usando TreadMarks ............................. 90
Fig. 5.2 – Dados transmitidos e enviados pelo nó mestre nas versões paralelas usando
PVM e TreadMarks............................................................................................................. 92
Fig. A.1 – Representação esparsa de uma matriz.................................................................... 97
xiv
Índice de Tabelas
Tab. 2.1 – Eventos contabilizáveis com Performance-Monitoring counters .............................40
Tab. 2.2 – Contadores contabilizáveis com Performance counters do Windows ..................41
Tab. 3.1 – Sistemas usados pelo parceiros para execução do código de simulação............53
Tab. 4.1 – Dados manipulados na função solve e suas dependências ...............................63
Tab. 5.1 – Características dos computadores usados nos testes de desempenho ...............82
Tab. 5.2 – Análise estática do solver............................................................................................83
Tab. 5.3 – Número total de acessos à memória numa execução típica do solver................85
Tab. 5.4 – Número total de cache misses no acesso à memória numa execução típica do
solver .....................................................................................................................................86
Tab. 5.5 – Tempos de execução da versões serial do solver numa execução típica do solver
................................................................................................................................................86
Tab. 5.6 – Resultados da paralelização do solver usando threads e TreadMarks ................87
Tab. 5.7 – Tempos de execução da aplicação de simulação....................................................89
Tab. 5.8 – Speedups expectáveis e obtidos com a versão paralela usando TreadMarks......91
Tab. 5.9 – Comparação dos tempos de execução das versões paralelas usando PVM e
TreadMarks (DSM)..............................................................................................................91
xv
1 Introdução
1.1 Motivação
Desde há várias décadas que têm vindo a ser realizadas simulações de fenómenos físicos
usando computadores. Nos primeiros tempos, as simulações eram realizadas em computadores especialmente construídos para o efeito. Com o desenvolvimento da electrónica e
das arquitecturas de processadores, nasceu um mercado para supercomputadores unicamente dedicados ao cálculo numérico.
O preços dos supercomputadores sempre limitou o seu uso às grande empresas e grandes
centros de investigação. As pequenas e médias empresas nunca tiveram possibilidade de
efectuar simulações dos seus produtos devido ao custo proibitivo dos supercomputadores
e do seu tempo de processamento.
Nos últimos anos, verificou-se um aumento de desempenho considerável nos computadores pessoais, já suplantando o desempenho dos supercomputadores de alguns anos atrás.
Aliado a este aumento de desempenho, a possibilidade de usar vários computadores
ligados numa rede para a realização de cálculos em paralelo, tornou o cálculo numérico
intensivo mais acessível.
Para as pequenas e médias empresas, o uso de computadores pessoais tornou-se uma
alternativa viável à aquisição de supercomputadores. O desempenho dos computadores
pessoais está ao nível do das estações de trabalho. Também é possível, com custo mínimo,
usar vários computadores em paralelo formando um cluster. As empresas já usam abun1
Optimização e Avaliação de Aplicações de Simulação Numérica
dantemente os computadores pessoais na sua operação normal, podendo estes computadores ser usados em conjunto na simulação de produtos. Para além da fácil criação de um
cluster, também a sua escalabilidade os torna atraentes: o aumento do desempenho é conseguido substituindo os computadores existentes por outros mais rápidos ou, mais simplesmente, adicionando novos computadores ao conjunto já existente.
Para tirar partido da existência de vários computadores, é necessário alterar o código
sequencial, paralelizando-o. Um programa, depois de paralelizado, pode ser executado
em simultâneo em vários processadores ou computadores. O tempo de execução dos
programas consegue ser reduzido aumentando o número de computadores participantes
no cálculo.
O desenvolvimento destes programas de simulação é útil mas, com algum esforço adicional, é possível aumentar o desempenho destas aplicações. Este aumento do desempenho
permite que o tempo despendido na simulação dos produtos se reduza, permitindo a
avaliação de soluções distintas para o mesmo produto ou uma afinação iterativa dos
mesmos.
A solução mais óbvia para a aceleração das aplicações é a aquisição de computadores
mais rápidos. Os ganhos podem ser substanciais, mas os custos podem tornar esta solução
inviável para muitas empresas.
A optimização do código é a solução com custos mais reduzidos, se executada durante a
produção do software de simulação, visto não obrigar à aquisição de computadores mais
rápidos. A optimização consiste na alteração do código do programa de modo a que este
se execute mais rapidamente no tipo de computadores a usar na simulação. Este passo
nem sempre é realizado, visto as aplicações serem desenvolvidas por especialistas no
domínio da simulação, mas sem conhecimentos de arquitectura de computadores.
1.2 Enquadramento
O trabalho apresentado nesta tese desenvolveu-se no âmbito dum projecto europeu. Este
projecto, “FLASH – HPCN Tools for Enhanced Hydrodynamic Design of Fast Ships on Parallel
Computing Platforms”, tinha como objectivo o desenvolvimento de um pacote de software
para desenho de embarcações, que integrasse ferramentas de CAD, com software de
simulação do comportamento dos cascos das embarcações.
Após a avaliação dos meios computacionais existentes nas instalações dos participantes,
foi decidido que a plataforma de execução dos programas desenvolvidos consistiria em
2
Introdução
computadores pessoais. Também se constatou que havia a possibilidade de executar código paralelo, quer em várias máquinas quer em multiprocessadores de memória partilhada.
O trabalho por nós desenvolvido neste projecto, centrou-se na melhoria do desempenho
do código de simulação produzido por um dos parceiros, recorrendo-se à optimização do
código sequencial e do código paralelizado.
Numa primeira fase, tendo apenas acesso a uma versão preliminar do simulador, optou-se por efectuar primeiramente a sua optimização sem preocupações de execução num
ambiente paralelo:
•
Observou-se inicialmente onde era despendido mais tempo durante a execução;
•
Realizaram-se optimizações, primeiro da ordenação das instruções de modo a
reduzir os tempos perdidos pelo processador e, depois, dos algoritmos usados,
para reduzir as instruções executadas.
Durante esta primeira fase também se observaram as possibilidades de paralelização de
partes deste código.
Após a optimização do código sequencial, decidiu-se efectuar alterações à versão paralela
desenvolvida por um dos parceiros. Esta primeira versão paralela usava passagem de
mensagens (PVM[Gei94]) para efectuar a comunicação entre os computadores. Constatou-se o fraco desempenho desta versão paralela. O trabalho por nós realizado prendeu-se
com a tentativa de, usando outra tecnologia de comunicação (memória partilhada e distribuída), optimizar a versão paralela e permitir uma fácil instalação clusters de computadores pessoais.
Alterou-se a implementação paralela para passar a usar memória partilhada e distribuída,
usando-se o sistema TreadMarks[Kel94], tentando-se com esta opção reduzir a
comunicação entre os vários computadores.
Um outro factor que se teve em conta no desenvolvimento desta última tarefa, foi o público alvo da aplicação. Uma preocupação constante foi a facilidade de uso das aplicações
paralelas. Para tal alterámos o sistema de lançamento remoto das tarefas do TreadMarks.
1.3 Contribuições
A primeira e mais evidente contribuição é a optimização das várias versões do simulador.
Foram por nós desenvolvidas duas versões optimizadas do simulador:
3
Optimização e Avaliação de Aplicações de Simulação Numérica
•
Protótipo para execução em monoprocessador, optimizado e com desempenho superior à versão original;
•
Protótipo paralelo para execução em rede de computadores pessoais, com desempenho superior às versões originais (série e paralela) ;
Também ao nível de software de suporte, foram realizadas implementações que deverão
ser referidas:
•
Software para medição da ocorrência de eventos de processador associados ao desempenho de aplicações
•
Alteração do modo de iniciação de tarefas no sistema TreadMarks;
Paralelamente, pode-se considerar este documento como referência interessante a futuras
optimizações. São aqui descritas as várias técnicas de optimização por nós aplicadas a
software de simulação, com a apresentação dos ganhos reais obtidos.
1.4 Estrutura do Documento
Este documento está dividido em 6 capítulos. Neste primeiro capítulo apresenta-se uma
introdução ao trabalho realizado e descrito nesta dissertação.
No segundo capítulo apresentam-se as várias técnicas de avaliação e optimização de código existente. Descrevem-se, não só, as técnicas de optimização aplicáveis a código executado em um só processador, mas também se apresentam várias tecnologias de suporte à
execução de código em vários processadores.
Nos dois capítulos seguintes apresenta-se uma descrição do projecto onde este trabalho se
inseriu (capítulo “Enquadramento”) e o trabalho por nós aí realizado (capítulo
“Realização”).
Os resultados de desempenho são apresentadas no capítulo “Avaliação”; as conclusões do
nosso trabalho são descritas no último capítulo.
4
2 Trabalho Relacionado
São apresentadas neste capítulo, técnicas que permitem o aumento de desempenho de
aplicações de simulação numérica. São apresentadas optimizações que dependem da arquitectura de execução e outras das quais se obtêm resultados independentemente da arquitectura. São descritas algumas técnicas de optimização de código e tecnologias que
permitem a execução paralela de código em vários processadores ou computadores. A
escolhas das técnicas de optimização aqui apresentadas foi realizada ao longo do
desenvolvimento do projecto, sendo representativas das várias técnicas existentes e
possíveis de aplicar em aplicações de simulação numérica.
Em relação aos sistemas computacionais paralelos, apresentamos uma resenha histórica,
com indicação dos sistemas actualmente em uso. Também descrevemos as várias
possibilidades existentes no campo de sistemas de suporte à programação paralela.
No fim deste capítulo, apresentamos várias ferramentas de análise do desempenho
existentes e investigadas antes do início do projecto, assim como algumas características
dos computadores e sistemas operativos actuais usadas na avaliação concreta da nossa
aplicação de simulação.
2.1 Introdução
Existem duas características que se desejam do software de simulação: exactidão e rapidez.
Como os resultados a obter devem ser o mais próximos possíveis da realidade, a exactidão é característica importante. A outra característica, a rapidez, também é importante,
5
Optimização e Avaliação de Aplicações de Simulação Numérica
visto os resultados das simulações serem dados importantes para decisões futuras e necessários em tempo útil.
Neste capítulo, serão apresentadas técnicas cuja aplicação permitem a melhoria do desempenho de aplicações de simulação numérica. Também são apresentadas metodologias de
avaliação de programas, a fim de identificar o código cuja alteração introduz maiores
ganhos de desempenho.
Existem duas tarefas que se podem realizar e que permitem o aumento do desempenho
dos programas:
•
optimização do código que se executa de forma sequencial num único processador;
•
paralelização do código para ser executado em vários processadores (multiprocessadores ou rede de PC's).
Enquanto que, com a optimização do código, se altera o programa para que execute o mínimo de instruções e o mais rapidamente possível, com a paralelização, divide-se o trabalho a realizar por vários processadores ou computadores, reduzindo-se o tempo total de
execução à medida que se aumenta o número de processadores envolvidos nos cálculos.
A optimização do código sequencial necessita de acesso ao código dos programas de simulação, e com um custo muito inferior ao da aquisição de novo hardware conseguem-se
obter ganhos significativos nos tempos de execução.
A optimização de código sequencial segue duas fases:
•
Avaliação do programa
•
Aplicação de técnicas de optimização
Para se concluir quais as instruções duma aplicação que demoram mais tempo, é necessário medir com exactidão o tempo de execução de cada função. Um modo de conseguir
isso, consiste em alterar o código do programa a observar, introduzindo as chamadas às
funções de temporização no início e fim de cada função, ou em blocos pais pequenos. Em
seguida é apenas necessário avaliar os tempos medidos. As modificações podem ser realizadas automaticamente por um programa externo ou manualmente pelo programador. A
inclusão das funções explicitamente por um programador permite a medição do tempo de
execução do código com maior precisão.
Outro modo consiste em usar técnicas de amostragem. Com uma determinada frequência
avalia-se qual o código que se executa, traçando um gráfico aproximado do tempo
6
Trabalho Relacionado
despendido na execução de cada módulo e função.
As técnicas básicas de optimização sequencial consistem em alterar porções de código de
modo a reduzir o número de instruções executadas. Este tipo de optimização não necessita de conhecimento da arquitectura computacional usada. Basta apenas observar o código
que permite melhores ganhos e alterar o algoritmo aí usado de modo a reduzir o número
de instruções executadas.
Existem também outras técnicas de optimização em que o conhecimento da arquitectura é
necessário. Quando se pretende, por exemplo, reduzir o tempo de espera do processador
devido a determinados encadeamentos de instruções, é necessário conhecer a arquitectura
interna do processador. Neste caso, não é suficiente saber onde se despende mais tempo,
mas também é necessário saber com exactidão porque ocorrem estas perdas de desempenho dependentes do processador utilizado.
Para efectuar a paralelização de código, também é necessário avaliar quais as partes do
programa que permitem maiores ganhos. É necessário, depois, decidir qual o tipo de distribuição dos dados entre os vários nós de processamento e que tecnologia usar para efectuar a comunicação entre os vários nós.
Dependendo do tipo de computadores existentes, assim diferentes tecnologias de comunicação devem ser utilizadas. Se o código paralelizado vai ser executado em multiprocessadores de memória partilhada, é mais atractivo utilizar o paradigma de memória partilhada[Bro97]. Nos computadores multiprocessadores de memória distribuída, já é mais natural usar uma infra-estrutura de passagem de mensagens[Sun90], [Sni96]. Caso se deseje
utilizar vários computadores ligados por uma rede para executarem código paralelo,
pode-se usar passagem de mensagens ou memória partilhada e distribuída, como se
apresentará mais adiante.
2.2 Técnicas de Optimização de Código Sequencial
Os compiladores actuais efectuam optimizações ao código dependentes do processador
de destino. Embora tais optimizações sejam válidas e eficientes, existem alguns casos
onde a observação do código e sua alteração pelo programador pode trazer ganhos
adicionais; em particular, quando:
•
o número de instruções é elevado, havendo um modo mais eficiente de codificar o
problema;
•
a sequência dos acessos aos dados provoca atrasos nos acessos;
7
Optimização e Avaliação de Aplicações de Simulação Numérica
•
o encadeamento das instruções provoca atrasos na sua execução.
O primeiro problema apontado advém do uso de algoritmos não optimizados. Muitas
vezes, a descrição dos algoritmos, devido a requisitos de legibilidade e compreensão, não
é a óptima.
Os dois problemas seguintes são causados pelo facto dos processadores não executarem
de modo óptimo algumas sequências de instruções. Devido ao uso de caches, também a
ordem pela qual os dados são acedidos, pode provocar atrasos, como se verá na
secção 2.2.2.2.
Estes problemas podem ser resolvidos por duas acções distintas mas complementares.
Primeiro, é necessário alterar a implementação dos algoritmos de modo a reduzir o número de instruções realizadas, verificando depois se essas instruções executam do modo
mais eficiente, em termos de acesso aos dados e encadeamento de instruções, na arquitectura escolhida para a execução do programa.
2.2.1 Optimizações não dependentes da plataforma
O primeiro tipo de optimização que se deve tentar realizar é a que for independente da arquitectura. Este tipo de optimizações pode-se realizar logo após a identificação das rotinas
que demoram mais tempo a executar. Normalmente estas optimizações limitam-se a
alterar as instruções usadas de modo a reduzir o seu número; por exemplo, reduzir o
número de iterações de um ciclo, reduzir o número de operações aritméticas e reduzir o
número de comparações. Em casos extremos, este tipo de optimizações pode-se traduzir
na alteração de todo o algoritmo por um outro mais eficiente.
As optimizações apresentadas podem ser realizadas sem preocupações relacionadas com
a arquitectura de execução se o código for executado em computadores do tipo monoprocessador não vectorial. No caso de computadores vectoriais ou multiprocessadores
(secção 2.3.1), algumas alterações poderão reduzir o desempenho, visto não possibilitarem
a utilização das capacidades dos processadores[Dow98]. Com efeito, os computadores
vectoriais e os multiprocessadores aproveitam a estrutura dos dados e o modo como o
código lhes acede para executar em paralelo várias instruções.
Apresentamos de seguida algumas optimizações não dependentes da arquitectura de execução aplicáveis a código de cálculo numérico. Estas optimizações prendem-se com a eliminação de instruções repetidas, expressões complexas ou condições. Também se apresenta o loop unrolling que tenta reduzir os custos de avaliação da condição de terminação
dos ciclos.
8
Trabalho Relacionado
Eliminação de sub-expressões
Uma das situações onde se pode obter algum ganho de desempenho é na redução de cálculos duplicados.
1
2
c = a + b + d
e = q + a + b
Observa-se no exemplo anterior que se duplica o cálculo da expressão a + b. Consegue-se
optimizar este código usando uma variável auxiliar onde ficará guardado o resultado da
expressão em causa.
3
4
5
temp = a + b
c = temp + d
e = q + temp
Os ganhos desta optimização aumentam com a complexidade da expressão desnecessariamente calculada.
Uma optimização semelhante é a eliminação de cálculos invariantes dentro de um ciclo.
1
2
3
for (i = 0 ; i < N ; i++){
a[i] = a[i] / sqrt(x*x + y*x);
}
Ao exemplo anterior retirar-se-á a expressão sqrt(x*x + y*x) de dentro do ciclo, reduzindo os cálculos efectuados.
1
2
3
4
temp = sqrt( x*x +y*x);
for (i = 0 ; i < N ; i++){
a[i] = a[i] / temp;
}
Alguns compiladores efectuam a eliminação de sub-expressões simples. No entanto,
quando as sub-expressões contêm chamadas a funções, os compiladores não efectuam
esta optimização. Como as funções invocadas podem ter efeitos paralelos no estado do
programa, só o programador sabe se pode substituir as várias chamadas às funções por
uma única.
Eliminação de condições dentro de ciclos
A existência de condições dentro de um ciclo aumenta os atrasos causados por este tipo
de instrução. Quando se verifica que estas condições são a causa de grandes tempos de
execução, é necessário eliminá-las.
Quando, dentro de um ciclo, o teste depende do seu índice, é possível com o conhecimento prévio que se tem dos dados, eliminar essas condições. No exemplo seguinte, em cada
iteração do ciclo interior, comparam-se os índices i e j.
9
Optimização e Avaliação de Aplicações de Simulação Numérica
1
2
3
4
5
6
7
8
for (i = 0; i < N; i++){
for (j = 0; j < N; i++){
if (j <= i)
a[i][j] = a[i][j] + b[i][j] * c;
else
a[i][j] = 0;
}
}
A condição testada N*N vezes durante a execução do código apresentado pode ser eliminada:
1
2
3
4
5
6
7
8
for (i = 0; i < N; i++){
for (j = 0; j <= i; i++){
a[i][j] = a[i][j] + b[i][j] * c;
}
for ( ; j < N; i++){
a[i][j] = 0;
}
}
Loop unrolling
Existem situações em que o peso da avaliação da guarda de um ciclo é superior ao das
operações executadas em cada iteração. Nestes casos, o loop unrolling permite obter ganhos significativos. Com efeito, com o loop unrolling tenta-se reduzir o número de testes
executados, aumentando o número de instruções a executar em cada iteração.
1
2
3
for (i = 0 ; i < N; i++){
a[i] = A[i] +b[i] * c;
}
Se no exemplo anterior N for múltiplo de 4, pode-se aplicar loop unrolling, passando-se, em
cada iteração, a executar 4 atribuições. Considere-se o exemplo seguinte:
1
2
3
4
5
6
for (i =
a[i]
a[i]
a[i]
a[i]
}
0
=
=
=
=
; i < N; i
A[i] +b[i]
A[i] +b[i]
A[i] +b[i]
A[i] +b[i]
+= 4){
* c; i++;
* c; i++;
* c; i++;
* c; i++;
Com a aplicação desta técnica, reduz-se o tempo despendido na execução das instruções
de controle do ciclo.
Caso o número de iterações seja constante e predefinido, aquando da compilação, é possível eliminar completamente o ciclo, substituindo-o por uma simples sequência de operações.
10
Trabalho Relacionado
2.2.2 Optimizações dependentes da plataforma
A arquitectura dos processadores e computadores usados no cálculo no tempo de execução do código. Estas arquitecturas são desenvolvidas de modo a reduzir o tempo de execução das instruções mas, devido à arquitectura interna dos processadores e aos tipos de
cache usados, existem determinadas combinações de operações e acessos aos dados que
não são executadas tão eficientemente quanto possível.
Descrevem-se de seguida as características arquitecturais do processador Pentium II relevantes para as possíveis optimizações a realizar. Apresentam-se depois as optimizações
possíveis.
A escolha deste processador (Pentium II) prendeu-se com sua grande implantação e ser
este o processador usado nos computadores que executam o simulador optimizado. O
facto da sua arquitectura ser semelhante à de outros processadores disponíveis também
teve influência na sua escolha, tornando-o um bom exemplo. Este processador apresenta
toda as técnicas de aumento de desempenho presentes em todos os outros processadores
de alto desempenho:
•
arquitectura super-escalar;
•
execução de instruções for a de ordem;
•
existência de pipeline de execução
•
predição da execução dos saltos.
2.2.2.1 Arquitectura do Pentium II
Os processadores Pentium II e Pentium III[Int01a] são implementações da arquitectura de
32 bits da Intel (IA-32). Estes processadores têm uma arquitectura de execução dinâmica
que fornece as seguintes características que influenciam o desempenho das execuções de
aplicações:
•
Execução de instruções fora de ordem – para aproveitar paralelismo
•
Arquitectura super-escalar – para aproveitar paralelismo
•
Pipeline de execução – para aproveitar paralelismo
•
Predição de saltos – para reduzir atrasos de execução
•
Caches nível 1 de dados e instruções internas ao processador
Embora estes processadores tenham algumas inovações em relação ao processador
11
Optimização e Avaliação de Aplicações de Simulação Numérica
Pentium Pro, a arquitectura básica é a mesma , pertencendo todos à mesma família, que se
referencia a partir daqui como P6[Int98].
O pipeline desta família de processadores é formado por 3 partes:
•
Fetch & Decode Unit
•
Dispatch / Execute Unit
•
Retirement Unit
Na Fig. 2.1 mostra-se o esquema geral desta arquitectura e os fluxos de dados entre os
vários componentes.
System Bus
Bus Unit
2nd Level Cache
1st Level
Instruction Cache
Fetch/Decode
1st Level Data Cache
Execution
Retirement
Instruction Pool/reorder buffer
BTBs/Branch Prediction
Fig. 2.1 – Micro-arquitectura dos processadores da família P6 com Advance Transfer
Cache (cache de nível 2)
A unidade de fetch/decode é responsável por traduzir as instruções assembly em µoperações
que serão executadas na unidade de execução. Para garantir que a unidade de execução
não espera pela descodificação de instruções, a unidade de descodificação deve garantir
um fluxo constante de µoperações. Isto é conseguido aproveitando-se a rapidez da cache de
instruções e efectuando a descodificação de várias instruções em paralelo.
Também é nesta unidade que se prevêem quais as instruções a descodificar quando se
atinge um salto (JMP, JE, …). Com a informação armazenada nos BTBs (Branch Target
Buffer) prevê-se se um salto vai ser executado ou não e quais as instruções a descodificar
de seguida.
A unidade de execução é responsável por executar as instruções existentes na Instruction
12
Trabalho Relacionado
Pool de modo mais eficiente. Se uma micro-instrução não pode ser executada, porque os
seus operandos ainda não foram calculados, esta unidade pode executar outra micro-instrução; deste modo os atrasos causados por dependência de µoperações são minorados executando instruções que não dependem de operações ainda não terminadas. Devido ao desenho desta unidade, é possível executar várias instruções independentes em paralelo.
A unidade de retirement é responsável por, após a conclusão das instruções, actualizar os
dados em memória pela ordem correcta. Como as instruções podem ser executadas por
uma ordem diferente daquela com que aparecem no código, não é possível actualizar a
memória logo que uma instrução se complete. A retirement unit observa a ordem correcta
pela qual as instruções deveriam ter sido executadas e vai actualizando a memória segundo essa ordem.
Descrevem-se de seguida as várias características destes processadores, indicando qual a
funcionalidade de cada um dos componentes atrás apresentados. Consegue-se assim perceber de que modo os encadeamentos de instruções tiram ou não proveito da arquitectura
e como essas instruções se podem optimizar.
Execução de instruções fora de ordem
O núcleo dos processadores P6 permite avaliar a interdependência entre as várias instruções assembly e µoperações (resultados e operandos) e realizar a sua execução por ordem
diferente daquela pela qual aparecem no código. Conseguem-se assim esconder os atrasos
na execução das instruções, intercalando outras independentes.
A descodificação das instruções assembly é realizada na unidade de fetch/decode e são
armazenadas, com informação da localização dos operandos e resultados, na Instruction
Pool.
Aquando do fim de uma instrução, esta é retirada da Instruction Pool, e são verificadas
quais as instruções aí existentes que dependiam deste resultado. Todas aquelas que não
dependam de nenhum outro resultado podem ser imediatamente executadas pela unidade de execução. Consegue-se assim que a unidade de execução tenha sempre instruções
para executar, mesmo que não sejam executadas pela ordem pela qual aparecem no
código.
A forte interdependência entre operandos das várias instruções obriga a que estas sejam
executadas pela ordem do programa, o que pode levar ao não aproveitamento do
paralelismo associado às várias unidades do processador.
13
Optimização e Avaliação de Aplicações de Simulação Numérica
Pipeline de execução
O uso de um pipeline permite a realização de várias actividades sucessivas em paralelo.
Esta característica é conseguida utilizando as três unidades atrás descritas: unidade de
fetch/decode, unidade de execução e retirement unit.
O aumento de desempenho obtém-se pelo facto de todos os três componentes atrás descritos funcionarem em paralelo, processando dados que, num determinado instante, são
independentes. Enquanto a unidade de execução executa uma determinada instrução, a
unidade de fetch/decode lê da memória instruções que serão mais tarde executadas. Quando a unidade de execução terminar uma instrução, não necessita de esperar que novas
instruções sejam lidas e descodificadas. Estas operações foram realizadas em paralelo com
a execução de instruções anteriores.
Após a conclusão da execução de uma instrução, a retirement unit é responsável pela
actualização da memória com os resultados da execução. Esta operação é realizada em
paralelo com a leitura, descodificação e execução de outras instruções.
Arquitectura Super-escalar
A unidade de execução permite a execução de várias instruções independentes em paralelo. A unidade de execução é responsável por distribuir as várias µoperações existentes na
Instruction Pool pelos 5 portos existentes nesta unidade (ver Fig. 2.2). Esta distribuição é
realizada à medida que as várias sub-unidades de execução vão ficando livres.
Estas unidades podem executar em paralelo e permitem a finalização de várias instruções
num mesmo ciclo de relógio. Como cada unidade tem um tipo específico de instruções
que pode executar, é necessário garantir que existem na Instruction Poll instruções dos vários tipos possíveis, porque só assim é possível garantir que existe paralelismo na
execução das instruções.
A existência de uma única unidade de execução de operações de vírgula flutuante, evita
que duas instruções de vírgula flutuante sejam iniciadas simultaneamente. Neste caso,
não se aproveita tão eficientemente o paralelismo da unidade de execução. Um caso
semelhante pode ocorrer com instruções inteiras, quando duas instruções só podem ser
executadas pela mesma sub-unidade de execução.
14
Trabalho Relacionado
MMX
Execution Unit
Floating Point
Execution Unit
Port 0
Integer
Execution Unit
MMX
Execution Unit
Instruction Poll
(ReOrder Buffer)
Reservation
Station
Jump
Execution Unit
Port 1
Integer
Execution Unit
Port 2
Store
Execution Unit
Port 3, 4
Load
Execution Unit
Fig. 2.2 – Unidade de Execução
Cada uma destas sub-unidades de execução tem no seu interior um pipeline para garantir
a frequência máxima de execução de instruções (até 1 micro-instrução/ciclo). Com a combinação correcta de instruções é possível garantir uma frequência de terminação de
instruções superior a 1 instrução por ciclo de relógio.
Predição de saltos
Normalmente, a leitura e descodificação de instruções realiza-se sequencialmente, tal qual
aparecem no código, e não como são executados. Este facto é problemático no caso dos
saltos que se realizam e alteram o fluxo de execução do código.
Quando um salto ocorre, a próxima instrução a executar não é aquela que se encontra a
seguir no código. Se a leitura e descodificação for cega, as instruções anteriormente descodificadas (devido à existência de pipeline) devem ser ignoradas e será necessário recomeçar a leitura e descodificação de instruções a partir da nova posição de execução. No caso
de um if,que apenas é executado uma vez, estas perdas podem não ser muito significativas mas nos ciclos com guarda no fim de cada iteração, o tempo perdido pode ser
significativo. Em cada iteração, sempre que o salto se executa, há necessidade de esvaziar
o pipeline.
Os processadores com arquitectura IA-32 conseguem, usando o historial de execução dos
ciclos, prever qual a instrução que se vai executar de seguida. Num ciclo, por exemplo, a
previsão só falha aquando da última iteração. No caso dos processadores de família P6 é
a BTBs/Brach Prediction que armazena a direcção do salto (para a frente ou para trás),
15
Optimização e Avaliação de Aplicações de Simulação Numérica
assim como o seu destino, e indica à unidade de fetch/decode qual a instrução que, a seguir
ao salto, deve ser lida e descodificada.
Para além desta predição (dita dinâmica), quando não existe informação nos Branch Target
Buffers acerca do salto a executar, é executada predição estática; esta baseia-se em algumas
heurísticas:
•
todos os saltos não condicionais serão executados;
•
saltos condicionais para trás serão executados;
•
saltos condicionais para a frente não serão executados.
Resumindo, com estas técnicas consegue-se reduzir drasticamente o tempo perdido nos
saltos, devido à eliminação da necessidade de esvaziar completamente o pipeline na maioria das situações:
•
Salto erradamente predito — penalidade de 10 a 15 ciclos
•
Predição dinâmica
•
o
salto executado e correctamente previsto — penalidade de 1 ciclo
o
salto não executado e correctamente previsto — sem penalidade
Predição estática correcta — penalidade de aproximadamente 6 ciclos
O número de ciclos correspondentes a um salto erradamente predito é devido ao esvaziamento de todo o pipeline até ao início da nova instrução. Nas outras situações as penalidades, caso haja, são devidas à necessidade de carregar e descodificar um novo conjunto
de instruções.
No caso de um ciclo, a última iteração será erradamente prevista, perdendo-se cerca de 15
ciclos de processador. No entanto, nas várias iterações intermédias, quando as previsões
acertam, as penalidades, caso existam, são substancialmente menores.
Cache de dados e instruções
Devido à sua rapidez, os acessos aos dados em memória atrasam significativamente a execução das instruções no processador. O tempo de acesso à memória é cerca de 10 vezes
superior ao tempo de acesso aos registos internos do processador.
Para melhorar o tempo de leitura e escrita na memória existem algumas alterações arquitecturais que se podem aplicar ao computador:
•
16
Usar memória mais rápida
Trabalho Relacionado
•
Usar bancos de memória para serem acedidos intercaladamente (escondendo os
atrasos de funcionamento da memória)
•
Usar buses de memória mais largos
•
Usar caches rápidas entre a memória e o processador.
Ao desenhar um computador é necessário balancear os custos envolvidos com a aplicação
das tecnologias acima descritas e os ganhos obtidos. Uma das soluções adoptadas e que
permitem bons ganhos é o uso de caches de vários níveis e com tamanhos variados.
A cache é formada por memória rápida que, em cada instante, aloja um determinado conjunto de dados. Esta memória está organizada por linhas onde são armazenados valores
contíguos existentes na memória. Estas linhas de memória são carregadas quando o processador acede a uma posição de memória que não se encontra na cache. Na leitura do primeiro valor o tempo perdido é elevado: o valor tem de ser lido do nível de memória seguinte mas as seguintes leituras contíguas já se efectuam sem atrasos.
Com a organização da memória em várias hierarquias, cada vez mais rápidas e caras mas
mais pequenas, consegue-se reduzir o tempo de leitura da memória com uma boa relação
custo/desempenho.
Enquanto que as três primeiras alterações ao sistema de memória não obrigam ao redesenho das aplicações, o uso de caches obriga à avaliação e redesenho dos padrões de acesso à
memória para obter os ganhos máximos. Há sequências de acessos à memória que não
aproveitam os dados armazenados nas várias caches.
Os processadores com arquitectura P6 contêm, no seu núcleo, duas caches de nível 1, uma
de dados e outra de código. Estas duas caches são associativas de quatro vias, têm uma capacidade de 16 Kbytes (8 Kbytes no caso do Pentium Pro) e o comprimento de cada linha
é de 32 bytes. Usam um mecanismo de write-back e um algoritmo pseudo-LRU (least recently
used) para a substituição dos valores armazenados.
A cache de nível 2, que armazena dados e código, está ligada ao processador por um bus
dedicado de 64 bits com relógio igual ao do processador. Esta cache tem um tamanho
variável, mas superior a 256 Kbytes. Assim, dependendo do mercado de destino do
processador, alterando o tamanho da cache, consegue-se balancear o desempenho com o
custo.
O uso de dois níveis de cache consegue esconder o tamanho reduzido da cache de nível 1.
Nem todos os misses à cache de nível 1 resultam num acesso à memória. Só quando os dados não se encontram em nenhuma das caches tal acontece. Neste caso perdem-se cerca de
17
Optimização e Avaliação de Aplicações de Simulação Numérica
10 ciclos de relógio. Para o preenchimento de uma linha de cache são lidos 4 blocos de 8
bytes da memória. Os dados lidos ficam acessíveis ao processador à medida que vão sendo
transferidos para a cache.
Também com a finalidade de optimizar as escritas em memória, os processadores
Pentium usam 12 store buffers. Aquando da execução de uma instrução de escrita, os dados não são transferidos imediatamente para a cache ou memória, mas sim para um destes
buffers. Mais tarde, os dados serão realmente transferidos para a memória. Deste modo, logo que os dados são transferido para os buffers, o processador e buses ficam livres para a
realização de outras instruções.
Estes buffers também são necessários para garantir que os dados são escritos na memória
pela mesma ordem pelas quais as operações aparecem no código. Como as instruções são
ordenadas por questões de optimização, é necessário garantir que a ordem das escritas
seja a correcta.
2.2.2.2 Optimizações aplicáveis a Pentium II
Descrevem-se nesta secção algumas optimizações realizáveis em programas e que dependem das arquitecturas do processador e computador:
•
Optimização do acesso aos dados – de modo a aproveitar os ganhos introduzidos
pelas caches
•
Optimizar a execução das instruções – usando instruções mais rápidas e permitindo a sua execução em paralelo.
Existem outra optimizações[Int97], [Int99] que podem ser realizadas mas estão mais orientadas para o desenho de compiladores. A optimização do uso dos registos, por exemplo, é
um tipo de optimização que é difícil realizar tendo apenas acesso ao código de alto nível,
mas que é imprescindível que seja realizada por um compilador.
Optimização do uso da cache
O uso de caches nos computadores modernos faz com que os acessos à memória não tenham todos o mesmo custo. Ao aceder-se a uma posição de memória, se esta não estiver
já na cache, são também transferidos os valores adjacentes. As próximas leituras a algum
desses valores realizar-se-ão muito mais rapidamente. Assim, para obter os ganhos do uso
de caches, é necessário que haja localidade espacial nos acessos consecutivos à memória.
No exemplo apresentado na Fig. 2.3, devido à ordem dos ciclos e de actualização dos
18
Trabalho Relacionado
índices, a contabilização de elementos nulos de uma matriz não tira partido da existência
de caches.
1
2
3
4
5
6
7
8
for (j =0; j<= N; j++){
/* percorrer colunas */
for (i =0; I <=N; i++){
/* percorrer linhas */
if (m[i][j] == 0)
count ++;
}
}
x
i
x
x
x
x
x
j
Fig. 2.3 – Exemplo de uso não optimizado da cache
(acesso com cache misses - x, dados carregados para cache –
)
Na primeira iteração do ciclo exterior são visitadas todas as linhas da matriz, verificando
se a primeira posição é nula. Em cada acesso é lida uma linha de dados para a cache. A
partir do momento em que a cache já está cheia, é necessário substituir as linhas mais antigas. Para matrizes grandes, quando se termina a primeira iteração, as primeiras linhas já
não se encontram na cache. Se o tamanho da matriz for superior ao da cache, é provável
que a partir de determinada linha, os cache misses obriguem à substituição dos dados armazenados na cache. Assim, na segunda iteração externa são percorridas outra vez todas
as linhas da matriz, obrigando à leitura de todos os dados a partir da memória.
Neste caso, a existência da cache não se reflecte me ganhos observáveis, Com efeito, os
acessos aos dados demorariam o mesmo tempo se as caches não existissem. Com esta
aproximação não se obtém ganho nenhum do uso da cache. Em todas as leituras é
necessário efectuar a transferência de dados a partir da memória principal. Trocando a
ordem dos ciclos já se obtêm ganhos do uso da cache, tal como se observe na Fig. 2.4.
No primeiro acesso à matriz, é necessário efectuar a leitura de uma linha da cache. Os próximos acessos (nos endereços seguintes) já aproveitam os dados armazenados em cache,
não obrigando à transferência de dados a partir da memória principal. A partir deste momento, como os acessos à memória são todos sequenciais, após uma leitura da memória
principal, ocorrem diversos acessos cujos dados já se encontram em cache, reduzindo o
tempo total de leitura.
Para tipo de dados dinâmicos a optimização dos acessos à memória já é mais difícil. Como
a localização lógica das estruturas não influencia a sua localização física, não se consegue
garantir uma localidade espacial de referência aquando do acessos aos dados. Assim, não
19
Optimização e Avaliação de Aplicações de Simulação Numérica
se consegue tirar partido da cache.
1
2
3
4
5
6
7
8
for (i =0; i<= N; j++){
/* percorrer linhas */
for (j =0; j <=N; i++){
/* percorrer colunas*/
if (m[i][j] == 0)
count ++;
}
}
x
i
√
√
√
x
√
j
Fig. 2.4 – Exemplo de uso optimizado da cache
(acesso com cache misses - x, acesso com cache hit – √, dados carregados para cache –
)
Optimização da execução das instruções
As optimizações relacionadas com o encadeamento das instruções, geralmente, podem ser
resolvidas pelo compilador e pela possibilidade do processador executar instruções fora
de ordem. Há, no entanto, casos em que a organização do código impossibilita a execução
óptima das instruções.
A arquitectura da unidade de execução dos processadores Pentium II permite a execução
simultânea de várias instruções em portos diferentes. Como cada porto executa determinado tipo de instruções é necessário garantir que existem instruções de tipos distintos
para manter o funcionamento dos vários portos em paralelo.
Uma outra origem de atrasos é a dependência entre operandos e resultados de várias
instruções. Uma instrução só pode ser executada caso todos os seus operandos já tenham
sido calculados pelas instruções anteriores. Quando se têm uma grande dependência
entre resultados e operações posteriores é possível que ocorram stalls no processador.
Em código de processamento numérico, a alta densidade de instruções de vírgula
flutuante, os dois problemas anteriores são muito frequentes. O elevado tempo de
execução das instruções de vírgula flutuante (entre 5 e 17 ciclos de relógio) e o facto dos
processadores Pentium
II só terem uma unidade de execução de vírgula flutuante
agravam os problemas atrás descritos.
É então necessário escrever o código de modo a que seja possível intercalar operações de
vírgula flutuante e outras de manipulação de inteiros ou leituras/escritas.
Se houver a intercalação de instruções não dependentes entre si, consegue-se aproveitar o
pipeline de execução de instruções de vírgula flutuante. É possível iniciar a execução de
20
Trabalho Relacionado
uma nova instrução ainda antes de ter terminado a instrução de vírgula flutuante
anterior.
As operações sobre registos são executadas mais rapidamente do que sobre posições de
memória. Se o código gerado pelo compilador executar as instruções, tendo por operandos os registos e não a memória, consegue-se um ganho no tempo de execução. Para facilitar a tarefa dos compiladores é aconselhável reduzir ao mínimo os acessos a posições de
vectores indexadas por variáveis. Se, por exemplo, em cada iteração se transferir o valor
indexado para uma variável local, e se realizarem todos os cálculos sobre ela, há a possibilidade do código ser executado sobre registos. No fim dos cálculos, é efectuada a transferência do novo valor para o vector.
1
2
3
4
5
6
for (i =0; i<= N; j++){
a[i] = 0;
for (j =0; j <=N; i++){
a[i] += j;
}
}
a)
1
2
3
4
5
6
7
for (i =0; i<= N; j++){
aux = 0;
for (j =0; j <=N; i++){
aux += j;
}
a[i] = aux;
}
b)
Fig. 2.5 – Alteração do acesso a vectores de modo a permitir a utilização de registos
a) versão não optimizada, b) versão optimizada
Deste modo, não só se possibilita a execução de instruções que manipulam registos, como
também se elimina a necessidade de gerar endereços em cada iteração do ciclo.
Nesta secção apresentámos uma série de optimizações simples que podem ser aplicadas
após a implementação da aplicações. Preferencialmente, de modo a reduzir as alterações
necessárias, é preferível que, aquando da codificação das aplicações, se tenha em atenção
este tipo de técnicas:
•
redução do número de instruções através da substituição de sub-expressões e
eliminação de código repetido;
•
optimização dos acessos à memória, para se tirar partido da cache;
•
geração de código cujo assembly seja executado eficientemente num determinado
processador.
2.3 Paralelização
A paralelização de código permite aproveitar os vários processadores existentes num
21
Optimização e Avaliação de Aplicações de Simulação Numérica
computador para executar código mais rapidamente. Actualmente, com o aumento da velocidade das redes de dados locais, é também possível executar programas paralelos que
são executados em vários computadores, em simultâneo.
Neste capítulo, apresentamos resenha histórica sobre os diferentes tipos de configurações
de sistemas paralelos:
•
Clusters
•
Multiprocessadores de memória distribuída
•
Multiprocessadores de memória partilhada
•
Computadores vectoriais
•
Arrays de processadores
Também são apresentadas os sistemas que actualmente se podem usar para desenvolver
programas paralelos em diversas plataformas:
•
threads sobre memória partilhada;
•
passagem de mensagens (PVM e MPI);
•
memória partilhada e distribuída;
•
High performance Fortran.
2.3.1 Arquitectura de Sistemas Paralelos
Ao longo da história da computação paralela têm existido vários tipos de sistemas paralelos que se enumeram a seguir, agrupados pela taxinomia de Flynn[Fly72]:
•
•
Multiple Instruction Multiple Data (MIMD)
o
multiprocessadores de memória partilhada
o
multiprocessadores de memória distribuída
o
Clusters (sistema multiprocessador de memória distribuída)
Single Instruction Multiple Data (SIMD)
o
multiprocessadores de memória partilhada
o
multiprocessadores de memória distribuída (arrays de processadores)
Apresentam-se, de seguida, as características genéricas de cada um destes tipos de sistemas paralelos.
22
Trabalho Relacionado
Multiprocessadores de memória partilhada (MIMD)
Os primeiros computadores multiprocessadores tinham vários processadores, executando
as instruções em paralelo. Todas as tarefas executadas em processadores distintos tinham
o mesmo espaço de endereçamento mapeado sobre uma única memória. Este tipo de
computadores ainda é hoje largamente utilizado.
Neste tipo de computador cada processador executa uma sequência de instruções diferentes (programa ou tarefa) de todos os outros, manipulando os dados que se encontram na
memória partilhada.
Por questões de custos, o acesso à memória partilhada é realizado através de um bus (Fig.
2.6.a). O facto deste bus ser partilhado por todos os processadores para comunicação com
o sistema de memória reduz o número máximo de processadores possíveis dado que, a
partir de um determinado número de processadores, o tráfego de dados satura o bus. Um
outro modo de ligação dos processadores à memória é o uso de um crossbar (Fig. 2.6.b)
como por exemplos os servidores Sun Fire 15k[Sun01]. Aqui o tráfego agregado é superior
mas continua a existir a possibilidade de contenção aquando do acesso aos dados.
CPU
CPU
CPU
CPU
CPU
CPU
MEMÓRIA
BUS
I/O
I/O
MEMÓRIA
MEMÓRIA
MEMÓRIA
I/O
I/O
a)
b)
Fig. 2.6 – Arquitectura de multiprocessadores de memória partilhada com ligações
distintas: a) bus de ligação, b) crossbar
Em geral, este tipo de sistemas é programado usando threads e memória partilhada (ver
secção 2.3.2.1 – Memória Partilhada). A cada processador fica atribuída uma tarefa, que se
executa em paralelo com todas as outras, existindo estruturas de dados na memória partilhada que são manipuladas por cada uma das tarefas. O acesso aos dados partilhados é
efectuado tal como num programa sequencial, mas existe a necessidade de sincronização.
Este tipo de sistemas ainda hoje se encontra em uso, sendo o tipo de arquitectura mais
usada para computadores multiprocessadores com até cerca de 100 processadores[Sun01].
23
Optimização e Avaliação de Aplicações de Simulação Numérica
Computadores vectoriais (SIMD)
No ano de 1976 nas o primeiro computador (CRAY I[Hoc81]) com arquitectura vectorial e
sucesso comercial. A rapidez de cálculo deste computador resultava da capacidade do
processador em executar eficientemente uma determinada operação sobre vectores de
dados. Para realizar uma operação sobre um vector não era necessário programar um ciclo, mas simplesmente usar uma instrução máquina.
Os processadores usados eram especializados para o cálculo numérico e usavam técnicas
de pipelining para garantir que essas instruções sobre vectores produziam no mínimo um
resultado por ciclo de relógio.
Em 1983 apareceu o primeiro computador paralelo que usava vários processadores vectoriais (CRAY 2[Haw98]) , executando todos eles a mesma instrução, mas sobre dados diferentes. Usavam memória partilhada e tinham um bus de ligação entre os processadores e a
memória.
Neste tipo de computadores o controlo da execução é realizada por um processador dedicado a essa tarefa, sendo os cálculos realizados pelos vários processadores vectoriais.
Num determinado instante, todos os processadores vectoriais executam a mesma instrução, mas sobre dados distintos. Consegue-se assim reduzir a complexidade dos processadores vectoriais, eliminando destes a lógica de controlo.
....
Unidade de
Controlo
Processador
Vectorial
........
Processador
Vectorial
....
Memória Escalar
Memória Vectorial
(dados Partilhados)
Fig. 2.7 – Exemplo da arquitectura de um computador multiprocessador vectorial
Hoje, o uso de computadores vectoriais já não é viável devido aos custos de desenvolvimento e ao aumento do desempenho dos processadores genéricos, mas a tecnologia de
cálculo vectorial volta a ser implementada em alguns processadores, por exemplo através
da tecnologia MMX[Int01a].
24
Trabalho Relacionado
Arrays de processadores (SIMD)
Os primeiros computadores massivamente paralelos (até 64000 processadores) usavam
várias unidades de processamento simples para efectuar os cálculos em paralelo. Cada
unidade de processamento contém um processador escalar, memória local e um processador de entradas/saídas. Todo o controlo do fluxo do programa é realizado por um processador dedicado e único no sistema; este processador realiza a avaliação de condições,
efectua a leitura e descodificação das instruções e envia as instruções correctas para todos
o processadores participantes no cálculo. Todo o array de processadores trabalha sincronizado; em cada instante, todos os processadores executam simultaneamente a mesma
instrução emitida pela unidade de controlo.
Fig. 2.8 – Exemplo da arquitectura de um computador massivamente paralelo
(MasPar MP-2 – 1992)
A transferência de dados entre os processadores realiza-se através do uso de mensagens
explícitas de comunicação, visto não haver memória partilhada entre unidades de processamento. Devido à grande quantidade de processadores, a rede de interligação deverá
suportar taxas de transferência elevadas. Para aumentar a taxa de transferência agregada,
usaram-se diversas topologias de rede[Alm94] (estrela, toros, anel, hiper–cubo, …)
25
Optimização e Avaliação de Aplicações de Simulação Numérica
Computadores de memória distribuída (MIMD)
Com o desenvolvimento dos processadores genéricos, uma evolução natural dos computadores baseados em arrays de processadores foi a inclusão dos novos processadores genéricos neste tipo de computador. Conseguiu-se, assim, o desenvolvimento de máquinas
com maior desempenho e com custo menor, devido ao uso de processadores genéricos e
largamente disponíveis.
A eliminação dos processadores escalares muito simples usados nos arrays de processadores permitiu a execução de diferentes fios de execução nos vários processadores. Estes
computadores passaram a pertencer à família MIMD.
Estes sistemas, devido ao elevado número de processadores, continuavam a ter memória
distribuída, de modo a reduzir o tempo de acesso a dados locais. Continua a haver cuidado especial na topologia da interligação entre os processadores para garantir a taxa máxima de transferência de dados entre processadores. Em alguns destes computadores, cada
unidade de execução tem, para além da memória privada, vários processadores que acedem através de uma ligação rápida aos dados locais.
Nas primeiras máquinas deste tipo a comunicação entre os vários processadores era programada explicitamente, inserindo funções de transferência de dados. Para tal, usavam-se
bibliotecas de transferência de mensagens (ver secção 2.3.2.2) proprietárias, que vieram a
ser substituídas pelas bibliotecas públicas MPI[Gropp] (ver secção 2.3.2.2.2) ou
PVM[Sun90] (ver secção 2.3.2.2.1).
Existem outros computadores de memória distribuída em que todos os processadores
vêem um único espaço de endereçamento, independentemente da localização dos dados
ser em memória local ou remota (por exemplo SG Origin 2000[Lau97]). Para isso é usado
hardware especial que consegue garantir a coerência entre as caches e as vistas das memórias de cada processador. Nestas máquinas, a programação da comunicação já não necessita de ser por passagem de mensagens, podendo-se recorrer a variáveis partilhadas. O
hardware de suporte que permite a partilha de dados entre os processadores implementa
um sistema de Distributed Shared Memory (secção 2.3.2.3).
Clusters (MIMD)
Recentemente, desenvolveu-se um novo tipo de arquitectura de computadores paralelos:
os clusters. Um cluster é, essencialmente, um conjunto de computadores ligados por uma
rede rápida e com software de sistema que permite que os vários nós se comportem como
um só sistema. A grande diferença entre um cluster e os sistemas atrás descritos é que,
26
Trabalho Relacionado
num cluster, cada unidade de processamento quando desligada do resto do sistema
comporta-se como um computador normal. Estas unidades de processamento variam
desde computadores multiprocessadores de memória partilhada, nos sistemas de maior
desempenho, até simples computadores pessoais.
Este tipo de computadores, para além do seu desempenho elevado, permite uma gestão
facilitada dos recursos. É possível, dinamicamente, criar partições do sistema que se comportam como computadores distintos.
Dois dos componentes mais importantes de um cluster são a rede de ligação entre os nós e
a infra-estrutura de software que suporta a computação.
Com o aumento das taxas de transferência das redes locais (fast-ethernet, por exemplo),
estas soluções de interligação viabilizaram a construção de sistemas com várias dezenas
de computadores. Para conjuntos de nós maiores, é necessário usar tecnologias que
permitem maiores taxas de transferência e menor latência (Myrinet[Vit98], SCI[Dol96]).
SISTEMA 1
SISTEMA 2
NÓ DE GESTÃO
Fig. 2.9 – Configuração de um cluster formando dois sistemas paralelos independentes
Embora os clusters de maiores dimensões actualmente existentes consigam desempenhos
da ordem do teraflops, as máquina com tal desempenho não estão à disposição da maioria
dos utilizadores. Versões mais reduzidas podem ser abrangidas pelos mais variados orçamentos: os clusters têm a vantagem de permitir a construção de sistemas em função do orçamento. Um cluster com 4 máquinas, por exemplo, é facilmente realizável com um investimento mínimo: é suficiente instalar o software necessário em quatro computadores
pessoais de modo a tornarem-se um único sistema paralelo.
Esta adaptabilidade aos orçamentos existentes também se observa na expansão dos
clusters. O aumento do seu desempenho é conseguido com a adição de novas máquinas,
sem substituição das anteriores, ou aumentando o desempenho de cada um dos nós.
Tal como os computadores de memória distribuída, também aqui, os paradigmas de pro27
Optimização e Avaliação de Aplicações de Simulação Numérica
gramação existentes são a passagem de mensagens (ver secção 2.3.2.1) ou de Distributed
Shared Memory (secção 2.3.2.2.1) implementado em software. Para além do suporte à comunicação, para clusters de grandes dimensões, também há necessidade de usar software para
administração e configuração do cluster, para gestão das filas de trabalhos e armazenamento dos dados.
2.3.2 Comunicação entre tarefas em multiprocessadores
Nos computadores de memória partilhada, a comunicação entre tarefas a executar em
processadores distintos é trivial, pois é realizada através do uso de variáveis globais e
acessíveis a todas as threads.
Nos sistemas de memória distribuída, como cada memória é local a cada unidade de
processamento, é necessário garantir suporte para a transferência de dados entre as várias
memórias. Existem duas possibilidades para transferência de dados entre tarefas. A
primeira e mais simples de implementar é usando passagem de mensagens. Aquando da
programação, apenas se usam primitivas de comunicação explícita entre os vários
processadores. A outra possibilidade é a emulação da existência de um espaço de
endereçamento único a todo o sistema. Esta abordagem permite o uso de variáveis
partilhadas, mas obriga ao uso de um sistema de suporte (software ou hardware) que
efectue a emulação.
2.3.2.1 Memória Partilhada
Enquanto que a capacidade de multiprocessamento de um sistema operativo permite que
se executem vários programas em paralelo num mesmo computador, a execução multitarefa possibilita paralelismo semelhante mas ao nível da aplicação. O uso de threads permite que uma aplicação tenha vários fios de execução paralelos que acedem a dados partilhados.
No caso de multiprocessadores de memória partilhada, é possível, durante a execução das
várias threads, associá-las a processadores diferentes, aproveitando-se assim a existência
dos vários processadores.
Presentemente, todos os sistemas operativos para computadores multiprocessadores de
memória partilhada disponibilizam rotinas de manipulação de threads, algumas proprietárias (Windows[MsSDKc] ou Solaris[Pow91]) e outras portáveis entre sistemas (threads
POSIX[POSIX]).
Em computadores multiprocessadores de memória partilhada, o uso de threads, aliado à
28
Trabalho Relacionado
memória partilhada, apresenta-se como uma solução eficiente para a programação paralela. A programação da distribuição e comunicação de dados entre threads é fácil e a execução resulta eficiente.
Embora o acesso aos dados partilhados entre as threads seja automático e transparente para o programador, é necessário o uso de bibliotecas especiais que forneçam rotinas de
manipulação de threads e de sincronização no acesso aos dados.
Como exemplo, apresenta-se de seguida uma implementação do método de relaxação de
Jacobi usando threads. O código apresentado faz parte da rotina executada por todas as
threads. Após a inicialização da matriz, as várias tarefas são criadas e todas executam o
código apresentado.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*calculo dos limites inferior e superior */
first = myid*stripSize + 1;
last = first + stripSize - 1;
for (iters = 1; iters <= numIters; iters++) {
for (i = first; i <= last; i++) {
for (j = 1; j <= gridSize; j++) {
grid_aux[i][j] = (grid1[i-1][j]+ grid1[i+1][j]+
grid1[i][j-1]+ grid1[i][j+1]) * 0.25;
}
}
barrier();
for (i = first; i <= last; i++) {
for (j = 1; j <= gridSize; j++) {
grid1[i][j] = grid_aux[i][j];
}
}
barrier();
}
Como os dados estão em memória partilhada não há comunicação explícita entre as várias
tarefas. Observa-se que não existem invocações a rotinas de comunicação; a única invocação externa aos cálculos é à função barrier. Esta rotina é de sincronização, não lhe estando associada qualquer transferência de dados.
2.3.2.2 Infra-estrutura de passagem de mensagens
A passagem de mensagens é o paradigma de programação paralela mais usado em computadores de memória distribuída. Até há pouco tempo, o único modo de transferência
de dados entre tarefas consistia no uso de mensagens explícitas de comunicação. Durante
a execução do programa, as mensagens de recepção emparelham com as de envio, obrigando também à sincronização entre as tarefas.
29
Optimização e Avaliação de Aplicações de Simulação Numérica
Embora a implementação de um sistema de passagem de mensagens seja simples, a codificação da comunicação num programa paralelo requer o conhecimento exacto dos dados
a transmitir e de quais os receptores.
Embora inicialmente todos os fabricantes de sistemas paralelos tivessem a sua biblioteca
de programação por passagem de mensagens, actualmente, apenas duas subsistem:
PVM[Sun90] e MPI[Gropp]. Estas bibliotecas serão descritas mais adiante.
Apresenta-se de seguida um excerto duma iteração do método de relaxação de Jacobi
programada usando MPI[Gropp]. Antes do bloco apresentado, aparecem as rotinas de
inicialização e distribuição dos dados iniciais. No fim do programa, aparecem as rotinas
de transferência de dados necessárias à consolidação dos resultados.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
if (rank < size - 1)
/* envio da fronteira inferior*/
MPI_Send(xlocal[maxn/size], maxn, MPI_DOUBLE,
rank + 1, 0, MPI_COMM_WORLD );
if (rank > 0)
/* recepção da fronteira superior*/
MPI_Recv(xlocal[0], maxn, MPI_DOUBLE,
rank - 1, 0, MPI_COMM_WORLD, &status );
if (rank > 0)
/* envio da fronteira superior*/
MPI_Send(xlocal[1], maxn, MPI_DOUBLE,
rank - 1, 1, MPI_COMM_WORLD );
if (rank < size - 1)
/* recepção da fronteira inferior*/
MPI_Recv(xlocal[maxn/size+1], maxn, MPI_DOUBLE,
rank + 1, 1, MPI_COMM_WORLD, &status );
itcnt ++;
diffnorm = 0.0;
for (i=i_first; i<=i_last; i++)
for (j=1; j<maxn-1; j++) {
xnew[i][j] = (xlocal[i][j+1] + xlocal[i][j-1] +
xlocal[i+1][j] + xlocal[i-1][j]) / 4.0;
diffnorm += (xnew[i][j] - xlocal[i][j]) *
(xnew[i][j] - xlocal[i][j]);
}
for (i=i_first; i<=i_last; i++)
for (j=1; j<maxn-1; j++)
xlocal[i][j] = xnew[i][j];
/* envio das diferenças */
MPI_Allreduce(&diffnorm, &gdiffnorm, 1, MPI_DOUBLE,
MPI_SUM, MPI_COMM_WORLD );
Observa-se que, em cada iteração, a transmissão da fronteira dos dados privados é
30
Trabalho Relacionado
realizada explicitamente. Para tal, são invocadas as rotinas MPI_Send e MPI_Recv. Na
invocação das rotinas de comunicação são indicados os dados a transmitir, assim como
qual o outro nó interveniente. Devido ao emparelhamento dos envios e recepções
consegue-se obter sincronização entre as tarefas de forma implícita.
A conversão para PVM resumir-se-ia à alteração das chamadas de comunicação e de
criação de tarefas.
2.3.2.2.1
PVM
PVM[Sun90] (Portable Virtual Machine) é um sistema de software que permite que um conjunto de computadores heterogéneos sejam usados como uma única máquina de memória
distribuída (por exemplo, para a realização de cálculos numéricos). Os computadores que
participam na computação podem ser desde computadores pessoais até supercomputadores de memória distribuída, interligados por rede (ethernet, FDDI, …).
Para além da infra-estrutura de comunicação entre os nós, também é fornecida uma biblioteca que permite a programação de aplicações paralelas para serem executadas nos
vários nós.
O paradigma de programação implementado é a passagem de mensagem, havendo rotinas para a criação das tarefas nos vários computadores e rotinas de comunicação para
transferência de dados[Gei94].
Quando um computador tem vários processadores e executa várias tarefas em paralelo, a
comunicação entre estas é realizada usando o método de comunicação mais eficiente para
a plataforma, s, continuando o modelo de programação a ser passagem de mensagens.
2.3.2.2.2
MPI
MPI[Sni96] é uma outra biblioteca para programação paralela, que nasceu da necessidade
de tornar portáveis os programas paralelos que executam em se multiprocessadores de
memória distribuída.
O objectivo deste esforço foi elaborar uma biblioteca com todas as construções comuns às
bibliotecas de programação baseadas em passagem de mensagens já existentes. Deste modo tenta-se melhorar a portabilidade deste tipo de aplicações paralelas. Tal como o PVM,
também as rotinas implementadas se dividem em manipulação (criação, destruição, …)
de tarefas e comunicação de dados entre os vários nós participantes nos cálculos.
Embora inicialmente o objectivo fosse o de tornar os programas portáveis, actualmente é
31
Optimização e Avaliação de Aplicações de Simulação Numérica
possível, usando vários computadores, utilizar MPI na programação de aplicações para
executar em clusters, à semelhança do PVM.
Uma das grande diferenças entre MPI e PVM é a impossibilidade de, durante a execução
de uma aplicação que use MPI, serem criadas tarefas remotas. Em MPI, todas as tarefas
são criadas no início do programa.
2.3.2.3 Distributed Shared Memory
Os sistemas de Distributed Shared Memory simulam a existência de um espaço de memória
partilhada por todas as tarefas que executam em computadores diferentes. Os programas
criam dados num espaço de memória mapeado num mesmo espaço de endereçamento
por todas as tarefas e o sistema permite que a visão desse espaço seja coerente entre todas
elas, estando a memória física distribuída pelos vários computadores.
Para garantir o modelo de consistência sequencial[Lam79] entre as várias vistas deste
espaço partilhado, seria necessário, para cada escrita na memória partilhada, transmitir as
alterações para cada computador detentor de uma cópia dos dados. Como esta
comunicação pode ser realizada sobre uma rede local (Ethernet, ATM, …) a transmissão de
todas as alterações é incomportável. Para resolver este problema decidiu-se implementar
protocolos de coerência de dados mais fracos. Estes novos modelos obrigam o uso de primitivas de sincronização. Estas primitivas também são usadas pelo sistema para a transferência de dados entre nós, de modo a garantir a coerência entre as várias memórias.
O primeiro, e mais estrito, dos modelos a aparecer foi o de consistência fraca[Adv90]. Este
modelo obriga o programador a introduzir uma barreira entre dois acessos que possam
originar uma corridas. A execução das barreiras é sequencialmente consistente e garante
que todos os acessos anteriores foram executados e que nenhum acesso posterior se
iniciou. Se o programador garantir que não existem corridas entre duas barreiras, o
sistema de DSM garante que todos os acessos à memória parecem sequencialmente
consistentes.
O modelo de release consistency [Gha90]usa duas primitivas de sincronização (acquire e
release) para sincronização entre as tarefas. Todos os acessos a dados partilhados devem ser realizados entre um acquire e um release. O acquire garante que nenhum
acesso que lhe segue se executou, enquanto que o release garante que todos os acessos anteriores já terminaram. Estas duas instruções garantem que, ao entrar-se numa região
crítica, a memória está consistente entre tarefas, e que, ao sair, todas as alterações são propagadas aos outros computadores (as propagações são realizadas após o release).
32
Trabalho Relacionado
Este modelo é mais eficiente que a consistência sequencial, embora requeira atenção semelhante por parte do programador. A comunicação entre nós é reduzida, visto que só a
última alteração de uma variável é propagada e que as alterações de várias variáveis
podem ser agrupadas numa única mensagem, mas podem ser enviadas mais mensagens
do que uma implementação usando passagem de mensagens explícitas.
Os programas são muito semelhantes àqueles desenvolvidos usando threads e memória
partilhada, mas é necessário ter em atenção a quantidade de dados transmitidos entre os
vários computadores. A paralelização tem de ser realizada tendo em atenção a latência na
comunicação dos dados partilhados, devendo esta ser reduzida ao mínimo necessário.
Como não existem chamadas explícitas a funções de comunicação, a compilação directa
de uma aplicação programada com threads usando uma biblioteca deste tipo, pode criar
programas que executam de modo pouco eficiente em vários computadores. De facto, o
programador, ao limitar-se a compilar o programa usando uma nova biblioteca, pode-se
esquecer que os acessos a dados partilhados podem provocar a comunicação entre
computadores.
2.3.2.3.1
TreadMarks
O sistema TreadMarks[Kel94] implementa Distributed Shared Memory em software executando as várias tarefas em vários computadores ligados por uma rede local (ethernet ou
ATM). O modelo de consistência usado é o lazy release consistency[Kel92] que é um
refinamento do release consistency descrito anteriormente. Este sistema fornece ao
programador todas as rotinas necessárias a criação de dados partilhados e criação e
manipulação estruturas de sincronização. O sistema também fornece a infra-estrutura
para manter a memória consistente ao longo da execução das aplicações.
O modelo de consistência usado é uma refinamento do modelo release consistency.
Também neste modelo, todos os acessos à memória que possam gerar corridas devem
estar separados por uma rotina de sincronização. No entanto, a diferença entre ambos está
no escalonamento da transmissão dos dados entre computadores. No release consistency, os
dados alterados por uma tarefa são enviados para os outros computadores durante a
execução do release. Neste novo modelo apenas quando os dados são acedidos é que os
valores são transferidos entre computadores. Durante a execução do release, apenas é
transmitida informação acerca dos dados alterados. Com este atraso na comunicação das
alterações consegue-se reduzir a quantidade de dados transmitidos entre computadores.
O sistema TreadMarks fornece uma biblioteca de funções necessárias à criação e acesso à
33
Optimização e Avaliação de Aplicações de Simulação Numérica
memória partilhada e primitivas de sincronização.
Todos os dados a partilhas entre os vário processos devem ser criados explicitamente
através da função Tmk_malloc. Todos os outros dados, criados estaticamente ou através
do malloc, continuam locais a cada tarefa. É possível efectuara a actualização explícita de
uma posição de memória dos outros processos através da instrução Tmk_distribute.
A sincronização pode ser realizada através de barreiras ou locks. As barreiras herdam o
funcionamento da weak consistency, mas a transmissão dos dados é atrasada. Os locks
podem ser adquiridos (Tmk_lock_acquire) ou libertados(Tmk_lock_release).
Embora simples, esta API permite o desenvolvimento de aplicações paralelas e distribuídas complexas.
2.3.2.4 High Performance Fortran (HPF)
O High Performance Fortran[Hig97] não é um sistema de suporte à programação paralela,
mas sim um conjunto de extensões à linguagem Fortran 95 que permitem o desenvolvimento de aplicações paralelas. Os modos de comunicação subjacentes são completamente
independentes da programação.
Os objectivos aquando do início do desenvolvimento do HPF eram:
•
Definição de um conjunto mínimo de extensões à linguagem Fortran necessárias
ao desenvolvimento de aplicações paralelas
•
Obtenção de desempenho máximo em multiprocessadores de memória distribuída
•
Redução do esforço aplicado na paralelização de programas escritos em Fortran
•
Desenvolvimento de uma linguagem portável entre várias arquitecturas paralelas,
desviando-se o mínimo dos standard do Fortran
As extensões fornecidas pelo HPF fornecem meios de expressar o paralelismo possível
para os tipos de dados manipulados. Normalmente, o programador limita-se a indicar como é que os dados devem ser divididos, sendo responsabilidade do compilador introduzir as rotinas de distribuição, comunicação e sincronização entre os processos. Os paradigmas de comunicação e sincronização usados não estão explicitados no código; cabe
ao compilador, sabendo a arquitectura de execução, a escolha do tipo de rotinas de comunicação a usar (memória partilhada ou passagem de mensagens).
O compilador também é responsável por, observando as estruturas de controle do programa, descobrir o código que deve ser executado em paralelo pelos vários processadores.
34
Trabalho Relacionado
1
2
3
4
5
6
7
8
9
REAL A(1000, 1000)
!HPF$ PROCESSORS procs(4, 4)
!HPF$ DISTRIBUTE (BLOCK, BLOCK) ONTO procs :: A
DO k = 1, num_iter
FORALL (i = 2:999, j = 2:999)
B(i,j)= (A(i,j-1)+A(i-1,j)+A(i,j+1)+ A(i+1,j))/4
END FORALL
A = B
! copia matriz em paralelo
END DO
No exemplo acima, a única diferença entre a versão paralela e a versão série é a existência
das duas directivas HPF. A primeira directiva indica a existência de uma grelha de 4x4
processadores chamada procs. A directiva DISTRIBUTE recomenda ao compilador que
o vector A seja distribuído pelos processadores procs. A partir deste momento a
descoberta das possibilidades de paralelismo é realizada pelo compilador, tendo em
atenção a estrutura do código (ciclos), a estrutura dos dados (vectores ou matrizes) e as
primitivas do HPF introduzidas pelo programador. No código fonte não há referências directas à comunicação ou sincronização entre processos.
2.3.3 Optimizações aplicáveis a código paralelo
As optimizações apresentadas anteriormente na secção “2.2 – Técnicas de Optimização de
Código Sequencial” também podem ser aplicadas a código já paralelizado.
Outro tipo de optimização possível é a redução dos dados transferidos entre tarefas. Se
em sistemas de memória partilhada estes tempos podem ser negligenciáveis, em sistemas
de memória distribuída, o tempo de comunicação pode-se sobrepor ao dos cálculos. Neste
caso é necessário garantir que os tempos de transferência de dados são mínimos.
Esta redução pode-se conseguir alterando os algoritmos, de modo a reduzir os dados que
é necessário partilhar entre tarefas, ou efectuando uma selecção mais fina dos dados a
transmitir.
2.4 Lei de Amdahl
Em 1967, Gene Amdahl[Amd67] formulou uma lei em que descrevia os ganhos máximos
que se podem obter da paralelização de código. Todos os programas têm código que é
inerentemente sequencial e outro que é paralelizável. Amdahl descreveu os ganhos
máximos que se obtêm da paralelização de apenas parte do código.
Quando se paraleliza um programa, o tempo de execução da sua parte sequencial mantém-se constante. É este facto que faz com que a redução do tempo de execução não seja
35
Optimização e Avaliação de Aplicações de Simulação Numérica
linearmente dependentes do número de processadores. Com efeito, considere-se a paralelização de um programa com 95% de código paralelizável (t_para); se for utilizado um
número infinito de processadores, o speedup máximo obtido é 20. O tempo correspondente
aos 5% (t_serie) do código sequencial mantêm-se constante e limita os ganhos máximos.
A regra geral de cálculo dos speedups segundo a lei de Amdahl fica então:
t_serie + t_para
t para
t_serie +
n
speedup =
em que t_serie é o tempo de execução do código série, t_para é o tempo de execução
do código paralelizável (com 1 processador) e n é o número de processadores.
20
Speedup
15
10
5
0
0
16
32
48
64
80
96
112
128
144
Processadores
Fig. 2.10 – Desempenho máximo de uma aplicação paralela segundo lei de Amdahl
Para o exemplo anterior (95% de código paralelizável) e segundo a fórmula anterior
obtém-se o gráfico da Fig. 2.10 de ganhos máximos para várias quantidades de
processadores.
2.5 Técnicas de avaliação de desempenho
Antes de se efectuar qualquer tipo de alteração de código para melhorar o desempenho de
uma aplicação, é necessário quantificar o tempo despendido em cada parte do programa.
Só depois deste passo podemos avaliar os possíveis ganhos da optimização ou paralelização desse código.
Para rentabilizar as tarefas de optimização é necessário encontrar o código que despende
36
Trabalho Relacionado
mais tempo. Deve-se, depois, avaliar as possíveis causas do fraco desempenho do código;
se o este for causado por características arquitecturais do computador é necessário
descobrir quais os problemas no código e porque razão o código não executa
eficientemente.
Descreve-se de seguida quais as ferramentas hoje disponíveis que nos permitem, não só
medir o tempo de execução das aplicações, mas também descobrir onde ocorrem os
eventos que atrasam a execução dos programas:
•
timers;
•
contadores de processador;
•
contadores de Sistema operativo;
•
aplicações de profiling.
2.5.1 Timers
A medição do tempo despendido em cada procedimento indica-nos qual o código que potencialmente executa menos eficientemente. Esta medição pode ser realizada através do
uso do relógio do computador. Este relógio é externo ao processador e tem uma precisão
pouco adequada à velocidade de processamento dos processadores actuais. Os processadores modernos já incluem registos que permitem a contabilização de tempo com precisão
superior.
2.5.1.1 Relógio do sistema
O relógio dum computador é composto por um gerador de sinal com uma determinada
frequência e uma série de registos. Este relógio está ligado ao gerador de interrupções que
permite assinalar ao sistema operativo, periodicamente e com uma frequência predeterminada, a passagem do tempo.
As interrupções geradas pelo relógio do computador são usadas pelo sistema operativo
para execução das tarefas de escalonamento e contabilização dos tempos de execução dos
programas. Os sistemas operativos fornecem chamadas de sistema que permitem consultar esses valores.
Enquanto que os sistemas operativos que seguem a norma POSIX[POSIX] fornecem as
funções times ou clock, o Windows[MsSDKa] disponibiliza a função GetTickCount.
A precisão destas rotinas, devido ao modo como são implementadas, é da ordem das
dezenas de milisegundos.
37
Optimização e Avaliação de Aplicações de Simulação Numérica
Embora a norma POSIX especifique que a unidade dos valores retornados por times e
clock seja o microsegundo, não é obrigatório que as implementações garantam precisão
de tal ordem. Em sistemas Linux e Solaris, a precisão destas funções é de 10 milisegundos.
2.5.1.2 Contadores de alta precisão
Com o aumento de velocidade de execução das instruções, o uso do relógio do sistema
passou a sofrer de algumas deficiências. Em particular, a precisão da ordem do
milisegundo não é suficiente para medir com exactidão o tempo de execução de algumas
rotinas.
Como o relógio do sistema tem a finalidade de calcular e memorizar o valor corrente do
tempo do modo mais preciso possível, há sistemas que efectuam alterações periódicas ao
valor do relógio, para este se manter certo. Este facto faz com que, em algumas medições
de intervalos de tempo, não se obtenha um valor preciso.
Para resolver os problemas atrás descritos, as famílias de processadores mais recentes
incluem um contador de tempo guiado pela frequência de funcionamento do processador
e sem necessidade de sincronização com relógios externos. Estes contadores também têm
uma precisão maior.
No caso da família x86 da Intel, este contador apareceu pela primeira vez no processador
Pentium[Int01c]. Este contador tem o comprimento de 64 bits que é inicializado a 0
aquando do reset do computador e é incrementado em cada ciclo de relógio do processador.
A instrução usada para efectuar a leitura deste registo é RDTSC[Int01b] que transfere o valor armazenado no contador para os registos EDX:EAX, permitindo a sua posterior utilização.
Assim, tal como o aumento da velocidade dos processadores obrigou, ao nível do
hardware, à criação de novos contadores de tempo, também nos sistemas operativos foram
introduzidas chamadas ao sistema que permitem a leitura do tempo com mais precisão
que a função clock (ou times ou GetTickCount).
As versões mais recentes do sistema operativo Windows (a partir do Windows NT 3.51 e
Windows 95) fornecem a função QueryPerformanceCounter[MsSDKa] que permite
efectuar a medição de tempo com uma precisão da ordem dos microsegundos.
Adicionando o atraso devido à chamada da função, este método tem uma precisão
superior a 1 milisegundo.
38
Trabalho Relacionado
Como a frequência do contador varia entre máquinas e versões do sistema operativo, é
necessário obter esse valor. A função QueryPerformanceFrequency permite obter a
resolução dos valores obtidos por QueryPerformanceCounter.
2.5.2 Contadores dos processadores
Os novos processadores (MIPS[Zag96], por exemplo) incluem novos registos que permitem a contabilização de eventos que ocorram dentro do processador ou nos buses de ligação. Estes registos, com auxílio dos contadores de tempo, permitem a avaliação precisa
das aplicações, descobrindo quais as causas dos atrasos na execução dos programas.
Os processadores Pentium Pro e posteriores, da Intel, têm dois Model-Specific Registers[Int01c], designados por PerfCtr0 e PerfCtr1, que permitem contabilizar a ocorrência dos eventos relevantes para o desempenho das aplicações. Estes eventos estão relacionados com o funcionamento do processador (excepções de vírgula flutuante, por exemplo) e a sua interacção com a memória (faltas de cache, …).
Os processadores que dispõem destes registos também têm novas instruções que permitem a sua leitura[Int01b]. A instrução RDPMC (Read Performance-Monitoring Counters) permite a transferência do valor acumulado por um dos contadores para os registos
EDX:EAX.
Antes de efectuar as leituras dos contadores é necessário indicar quais os eventos a contabilizar. A programação dos eventos a contabilizar é realizada colocando nos registos
específicos PerfEvtSel0 ou PerfEvtSel1 o código dos eventos a registar.
Apresentam-se na Tab. 2.1 alguns dos eventos que é possível detectar e que estão directamente relacionados com a avaliação do desempenho de aplicações.
A instrução assembly RDPMC para aceder aos registos específicos do processador
(PerfEvtSel0 e PerfEvtSel1) é privilegiada, só podendo ser invocada por código a
executar em modo núcleo. Por esta razão, sem a utilização de um driver específico, não é
possível a contabilização dos eventos.
Estes contadores não só permitem a contabilização dos eventos, mas também a geração de
interrupções quando atingem um
valor predeterminado. É possível programar estes
contadores de modo a ser gerada uma interrupção aquando do seu overflow. Deste modo,
é possível, sem alteração do código, efectuar a sua avaliação: programa-se o contador para
contabilizar um determinado evento, indica-se que este deverá gerar uma interrupção
aquando do overflow e programa-se uma rotina que, quando invocada, verifica que código
39
Optimização e Avaliação de Aplicações de Simulação Numérica
se executava quando foi gerada a interrupção.
Mnemónica do evento
Descrição
DATA_READ
Número de leituras à memória – contabiliza
número de hits e misses na cache nível 1
DATA_WRITE
Número de escritas na memória – contabiliza número de hits e misses na cache nível 1
DATA_READ_MISS
Número de leitura à memória que geram
miss na cache nível 1
DATA_WRITE_MISS
Número de escritas na memória que geram
miss na cache nível 1
PIPELINE_FLUSHES
Número de flushes do pipeline devido a
excepções, interrupções e saltos mal previstos
INSTRUCTIONS_EXECUTED
Número de instruções executados por ciclo
(no máximo 2 por ciclo de relógio)
INSTRUCTIONS_EXECUTED_V_PIPE
Número de instruções executadas em paralelo
PIPELINE_AGI_STALLS
Número de atrasos devido a interdependência de endereços (Address generation interlock
– AGI).
FLOPS
Número de instruções de vírgula flutuante
– Inclui as quatro operações básicas, restos e
raízes. As operações compostas incrementam este contador várias vezes.
FLOATING_POINT_STALLS_DURATION
Número de ciclos que a execução espera
pela terminação de uma operação de vírgula flutuante
TAKEN_BRANCHES
Saltos executados
PIPELINE_FLUSHES_DUE_
TO_WRONG_BRANCH_PREDICTION
Limpeza do pipeline devido a incorrecta predição da execução de saltos
Tab. 2.1 – Eventos contabilizáveis com Performance-Monitoring counters
2.5.3 Contadores do S.O.
Existem alguns eventos relativos ao funcionamento do sistema operativo que são relevantes para a avaliação do desempenho das aplicações. Estes eventos estão relacionados com
os acessos ao disco (e consequentes atrasos) e transferências de dados na rede.
O Sistema operativo Windows[MsWRK] disponibiliza uma infra-estrutura de recolha e
leitura de dados acerca do funcionamento do sistema operativo e componentes do computador. Os contadores estão organizados numa hierarquia de dois níveis. O primeiro é o
40
Trabalho Relacionado
nível físico, constituído pelas classes de objectos (memória, rede, processos, por exemplo),
e o segundo é composto pelos contadores característicos de cada objecto. Numa mesma
máquina, podem existir várias instâncias de um mesmo objecto cada uma com o seu conjunto de contadores.
Contador
Descrição
Network Interface
Bytes Sent
Quantidade de informação enviada por
cada interface de rede
Bytes Received
Quantidade de informação recebida por
cada interface de rede
Memory
Page Faults
Número de faltas de página ocorridas
Page Read
Número de páginas lidas de memória
secundária
Page Write
Número de páginas
memória secundária
escritas
para
Process
IO Read Bytes
Quantidade de informação lida (a partir
do sistema de ficheiros ou rede) em cada
processo
IO Write Bytes
Quantidade de informação escrita (para o
sistema de ficheiros ou rede) em cada
processo
Page Faults
Número de faltas de página ocorridas
durante a execução do processo
Working Set
Memória física utilizada por cada processo
Virtual Bytes
Memória virtual utilizada por cada processo
Tab. 2.2 – Contadores contabilizáveis com Performance counters do Windows
(divididos por objectos do sistema)
Os dados acerca dos objectos, instâncias e contadores são armazenados no registry, sendo
o seu acesso realizado através das instruções de manipulação do registry. Para facilitar o
acesso e manipulação destes contadores, a Microsoft disponibiliza uma API específica
chamada Performance Data Helper[MsSDKb] (PDH).
Esta API fornece instruções para selecção dos contadores, obtenção das suas características e leitura dos seus valores.
41
Optimização e Avaliação de Aplicações de Simulação Numérica
Também é possível implementar novas fontes de dados e novos contadores, implementando dlls que efectuam as operações necessárias à inicialização, recolha de dados e leitura.
Apresenta-se na Tab. 2.2 alguns objectos e seus contadores relevantes para a observação
do desempenho de aplicações.
2.5.4 Polling vs. Instrumentação
A comparação entre os tempos de execução de duas versões duma aplicação é suficiente
para verificar se as optimizações já introduzidas de uma versão para a outra trazem benefícios, mas não é suficiente para descobrir que partes da aplicação necessitam de optimizações, e onde estas poderão ser mais proveitosas.
Para fazer esta avaliação é necessário saber com a granularidade mais fina possível, quais
as funções, ou mesmo linhas de código, que mais tempo demoram a executar. Também
pode ser interessante saber onde ocorrem os eventos do processador e sistema operativo
contabilizáveis (ver secções 2.5.2 e 0). para tal, pode-se efectuar a instrumentação do
código, que implica a sua alteração, ou, de modo transparente para a aplicação, efectuar
polling.
O polling é um método não intrusivo de contabilização de tempos de execução. Consiste
em, periodicamente, interromper a execução do programa para observar que instrução
estava a ser executada naquele instante. Consegue-se assim avaliar quais as instruções
que mais ocupam o processador. Para realizar este tipo de medição, não é necessário
alterar o código da aplicação a observar, podendo a contabilização ser efectuada por um
programa externo à aplicação a avaliar.
Se a frequência de amostragem não for suficiente alta, não se conseguem obter resultados
conclusivos, dado que, entre cada amostra existe uma série de instruções que se executam,
mas não são contabilizadas.
Com a instrumentação obtêm-se resultados mais precisos. São introduzidas no código instruções de contabilização de tempo, possibilitando a medição do tempo de execução entre
pontos no código com muita exactidão. A introdução das instruções de medida do tempo
pode ser efectuada automaticamente ou pelo programador que as introduz nos pontos
onde deseja efectuar a medição.
Se a introdução das instruções de medida for realizada automaticamente, a granularidade
de medida, normalmente, é a rotina. As ferramentas de análise de desempenho introdu42
Trabalho Relacionado
zem chamadas a funções de leitura do tempo no início e fim de cada sub-programa, e, no
fim da execução, é apresentada uma contabilização do tempo despendido em cada sub-programa. Esta tarefa pode ser realizada aquando da compilação (gprof, ver 2.5.5.1) ou
após (Etch, ver 2.5.5.2).
Se a introdução das rotinas de contabilização for realizada pelo programador é possível
contabilizar o tempo de execução do código com granularidade inferior, i. e. ao nível do
bloco de código ou mesmo da linha de código.
Um outro método de profiling possível é a geração de interrupções após a ocorrência de
um determinado número de eventos (ver secção 2.5.2 acerca destes eventos). Os processadores mais recentes, para além da contagem de diversos eventos, permitem a geração
de interrupções tratáveis pelo software após a ocorrência de vários eventos. Seleccionando
um valor correcto, e sem a alteração do programa a examinar, é possível obter os valores
aproximados do número de eventos ocorridos durante a execução do programa.
2.5.5 Software de profiling
Apresentam-se nesta secção programas que permitem a avaliação do software e a descoberta do tempo despendido por cada bloco. Estes pacotes de software permitem, de modo
automático, sem alteração do código, a avaliação do desempenho de aplicações, apresentando os tempos de execução das diversas funções e blocos.
Dois dos pacotes (Gprof e Etch) efectuam instrumentação do programa, sendo também
possível usar a técnica de polling através do Vtune e do Etch.
2.5.5.1 Gprof
O Gprof[Gra82] permite a obtenção de três tipos de informação acerca de uma aplicação:
número de invocações das rotinas, tempo de execução e grafos de dependências entre os
vários sub-programas.
Para obter os resultados pretendidos é necessário efectuar a recompilação de todos os módulos do programa, de modo a serem introduzidas as rotinas de contabilização. Durante a
execução do programa alterado, as rotinas do gprof efectuam a contabilização dos
tempos e número de execuções. Toda esta contabilização é efectuada sem recurso a aplicações externas. Após a execução do programa são criados ficheiros com os resultados.
A possibilidade de obtenção do número de invocação das rotinas e seus grafos de
dependências é obtida com a alteração do código da aplicação. Aquando da compilação e
43
Optimização e Avaliação de Aplicações de Simulação Numérica
ligação do código do programa são introduzidas chamadas a funções do gprof que efectuam a contabilização pretendida. Durante a execução do programa a avaliar, e quando é
invocada uma qualquer função, é também executada uma rotina do gprof, que contabiliza o número de invocações e onde foram realizadas.
Para a obtenção do tempo de execução de cada rotina, o gprof usa dois métodos distintos: instrumentação e polling. Através do uso da instrumentação do código são introduzidas instruções de medição do tempo no início e fim de cada função. Aliado à informação
obtida do grafo de chamadas consegue-se obter com exactidão o tempo de execução do
código de cada função. Nos sistemas de time-sharing esta aproximação apenas nos indica o
tempo real que as funções demoraram, mas não nos informa do tempo que estas estiveram a executar no processador.
O uso de polling permite saber durante quanto tempo cada função esteve a ser executada
no processador. No início do programa a avaliar é iniciado um outro processo que, com
uma determinada frequência, interrompe o programa e verifica qual a função que se
executava nesse momento. Com toda a informação obtida durante a execução é possível
obter uma aproximação estatística ao tempo de execução de cada rotina. É necessário um
cuidado especial com o valor da frequência de interrupção para não ignorar as funções
que executam muito rapidamente.
Esta segunda técnica não precisa de suporte especial do processador, visto apenas necessitar de temporizadores para efectuar a interrupção do programa com determinada frequência.
Após a execução da aplicação a observar passam a existir os ficheiros com os dados recolhidos durante a sua execução, tendo sido realizada a sua geração no fim da sessão de
profiling. Para serem apresentados de modo legível é necessário executar a aplicação
gprof. Esta aplicação permite a apresentação dos resultados de modos diversos, por
exemplo: tempo total ou médio de execução das funções, divisão do tempo de execução
pelas várias rotinas invocadas, etc.
2.5.5.2 Etch
O sistema Etch[Rom97] permite a alteração e rescrita de executáveis sem o acesso ao código fonte e sem compilação. Esta possibilidade de rescrita dos programas, sem acesso ao
código fonte, não só permite a optimização dos programas como também a contabilização
dos tempos de execução das várias funções e instruções.
44
Trabalho Relacionado
O Etch é uma plataforma que suporta a inclusão num programa de qualquer tipo de contabilização a realizar durante a execução. A avaliação da aplicação realiza-se em três fases:
i) compilação de uma versão sem instruções de contabilização, ii) instrumentação através
do Etch e iii) recolha dos dados durante a execução da aplicação. Estas três fases permitem que, para um mesmo executável, e sem alteração do código e posterior compilação, se
consigam efectuar diversas medições de indicadores distintos.
Para efectuar a instrumentação é necessário, numa primeira passagem, realizar a leitura
do executável e análise para obter a sua estrutura. Pode-se então efectuar a rescrita do
programa, introduzindo nos locais certos as instruções de contabilização de tempos ou
outros eventos relevantes.
Após a instrumentação e durante a execução do programa, são contabilizados os tempos
despendidos por cada bloco e o número de execuções. No fim do programa existe código
que recebe os valores contabilizados durante a execução, agrupa-os e guarda-os num ficheiro.
Com o sistema Etch são disponibilizados programas que alteram os executáveis de modo
a contabilizar vários factores relevantes (tempo de execução, cache misses, acessos à memória desalinhados,…), mas podem ser escritos programas que, usando as bibliotecas fornecidas, alteram os executáveis de modo a serem contabilizados outros factores.
2.5.5.3 Vtune
Vtune[Int02] é um sistema de avaliação de aplicações que, sem o recurso a instrumentação e usando os recursos fornecidos pelos processadores da Intel, permite a avaliação
de aplicações. Este sistema permite contabilizar o número de execuções de cada instrução,
o seu tempo de execução e o número de eventos relevantes para o desempenho que ocorreram durante a execução (ver secção 2.5.2). O Vtune também efectua avaliação estática
do código encontrando situações onde o encadeamento das instruções introduz atrasos na
execução.
As aplicações a observar não necessitam de qualquer alteração ou compilação adicional,
visto o sistema Vtune executar em paralelo com a aplicação e observar o seu estado durante a recolha dos dados. Apenas a informação de debug (tradução de símbolos) deverá
estar presente de modo a facilitar a apresentação dos resultados recolhidos. Para efectuar
o profiling de uma aplicação apenas é necessário executá-la dentro do ambiente Vtune.
O sistema Vtune permite efectuar a avaliação das aplicações através de polling ou por in45
Optimização e Avaliação de Aplicações de Simulação Numérica
terrupção após determinado número de eventos. Se o Vtune for configurado para usar
polling, com uma determinada frequência, interrompe a execução da aplicação e verifica
qual a instrução a executar e armazena os valores relevantes para a contabilização. No
outro modo de funcionamento, e usando uma característica dos processadores Pentium,
o Vtune interrompe a aplicação após a ocorrência de um determinado número de eventos, sendo então armazenada informação acerca da instrução que se executava nesse instante. Com estes dois métodos conseguem-se obter resultados muito aproximados dos valores reais.
Após a recolha dos dados é fornecida ao utilizador uma interface que permite a navegação no código, sendo apresentados os valores contabilizados para cada módulo, função e
instrução.
Os eventos mais relevantes para a optimização de código e contabilizáveis pelo Vtune
são os apresentados na secção 2.5.2. Embora os eventos contabilizáveis variem com o processador usado, é sempre possível contabilizar o tempo de execução e o número de
invocações de cada rotina e instrução.
2.6 Resumo e enquadramento
Neste capítulo foram apresentadas técnicas de optimização de código. Estas técnicas estão
divididas em dois tipos: dependentes e não dependentes da arquitectura de execução. As
técnicas apresentadas podem ser aplicadas a código de alto nível sem necessidade de manipulação do código assembly. Nos próximos capítulos são demonstrados de que modo se
aplicaram as técnicas de optimização a código de simulação numérica e que resultados se
obtiveram.
Também se descreveram neste capítulo várias arquitecturas de sistemas paralelos. Como
se concluiu do levantamento de requisitos do projecto Flash apenas clusters e multiprocessadores de memória partilhada está disponíveis em pequenas e médias empresas (ver a
secção 3.1.3 – Ambiente de execução). Também se descreu as bibliotecas e sistemas que
permitem o desenvolvimento de aplicações paralelas (MPI, PVM, TreadMarks e HPF).
Dois destes sistemas (PVM e TreadMarks) foram usados na paralelização de uma
aplicação e os resultados de ambas as execução serão apresentados no próximo capítulo.
As ferramentas de análise de desempenho apresentadas são representativas daquelas hoje
disponibilizadas para uso. Na avaliação da aplicação de simulação não foram usadas
todas elas, por em parte se sobreporem em funcionalidades. Como se verá utilizaram-se
os timers, os contadores do processador e do sistema operativo e a aplicação Vtune.
46
3 Enquadramento
O trabalho apresentado nesta dissertação foi realizado no âmbito do projecto europeu
n.º 24903 intitulado “HPCN Tools for Enhanced Hydrodynamic Design of Fast Ships on Parallel
Computing Platforms”. O objectivo geral deste projecto era o desenvolvimento de ferramentas de análise e desenho de cascos de embarcações rápidas, usando os meios computacionais já existentes nos utilizadores do sistema.
Neste capítulo apresenta-se com mais detalhe o projecto Flash e a participação do INESC.
Também se descreve o código de análise de cascos anteriormente existente e que serviu de
suporte ao projecto, assim como o ambiente e plataformas de execução do resultado final.
3.1 Descrição do Projecto Flash
Na indústria naval, para avaliar o desenho dos cascos das embarcações, usa–se a
simulação de modelos à escala, em tanques de ensaio. Este processo é útil mas os resultados obtidos são poucos e difíceis de avaliar: resistência total, perfil e elevações das ondas
geradas. Estes resultados são úteis na comparação do desempenho das carenas, mas não
permitem a análise estrutural dos navios.
A simulação numérica destes testes, não só permite obter os resultados atrás descritos, como também outros valores necessários à avaliação do comportamento dos cascos. A pressão exercida ao longo de todo o casco, assim como a velocidade real dos fluxos são valores
que é possível obter com a simulação.
A simulação numérica, para além dos resultados adicionais que fornece, também permite
47
Optimização e Avaliação de Aplicações de Simulação Numérica
a realização dos testes com custos menores e mais rapidamente. Não há necessidade de
realizar modelos dos cascos e os resultados numéricos são disponíveis logo após a
finalização dos testes, permitindo a sua integração com ferramentas de análise de
estruturas.
O objectivo geral do projecto Flash era a criação de uma plataforma integrada de desenho,
simulação e avaliação de cascos de embarcações rápidas (Número de Froude superior a
0.3), que aproveitasse as possibilidades de processamento paralelo dos computadores
existentes nos gabinetes de desenho de embarcações. Os objectivos específicos
apresentados eram:
•
Fornecer à indústria naval um novo sistema eficiente
para o desenho e
optimização de cascos e estruturas de embarcações usando uma rede de
computadores formando um cluster.
•
Demonstrar e avaliar o uso de sistemas HPCN em computações de larga escala
típicas do desenho de cascos de embarcações envolvendo problemas de
hidrodinâmica e mecânica de estruturas.
•
Aumentar o interesse para as utilização de aplicações de simulação computacional
na indústria naval europeia, fornecendo uma interface amigável para ferramentas
de desenho e optimização de embarcações comerciais (passageiros e mercadoria)
rápidas.
O consórcio participante neste projecto era formado por parceiros representativos da
indústria naval europeia e áreas afins:
•
4 construtores navais com desenhos de embarcações próprios
•
1 empresa de ensaios em tanques
•
2 grupos de investigação (um ligado à simulação numérica e outro ligado às
ciências da computação).
O desenvolvimento da plataforma Flash desenvolveu-se em três frentes: i) integração do
pré/pós-processador Gid[CIM02] e simulador com aplicações CAD já existentes; ii) melhoria dos resultados obtidos para o tipo de embarcações alvo; iii) optimização do código
de simulação.
A integração do código com as ferramentas de desenho foi realizada pelos elementos do
CIMNE, os especialistas em simulação numérica. Também estes investigadores alteraram
o código de modo a obterem-se resultados mais próximos dos obtidos em testes de tan48
Enquadramento
ques de ensaio. A avaliação dos resultados foi realizada pelos vários construtores de embarcações (BAZAN, ENVC, SP Technologies e NAUTATEC) com base em valores obtidos
no tanque de ensaios (BEC). A equipe do INESC foi responsável pela optimização do código de simulação produzido e testado pelos outros parceiros.
3.1.1 Arquitectura do sistema
A plataforma a instalar nos utilizadores do sistema é composta por três elementos principais:
•
Aplicação CAD para desenho da embarcação;
•
Aplicação CFD de simulação de comportamento do casco;
•
Aplicação para avaliação dos resultados e impacto na estrutura da embarcação.
Modelo
embarcação
Pre-processador
Malha
Aplicação de CAD
Aplicação de simulação
Alterações
Pos-processador
(visualização do
resultados)
Resultados
GiD
Plataforma FLASH
Fig. 3.1 – Arquitectura geral da plataforma de desenvolvimento e simulação das
embarcações
A aplicação de CAD serve para o desenho da embarcação, não só do contorno do seu casco, mas também de toda a estrutura de suporte. O GiD, desenvolvido por um dos parceiros (CIMNE), é um pré/pós-processador que, a partir da descrição da embarcação, gera
as malhas necessárias ao simulador. Após a simulação é possível não só observar os
resultados numéricos como também analisar as influências expectáveis sobre a estrutura
proposta.
O pré-processador gera a representação de 3 malhas com tipos de elementos diferentes:
contorno do casco, superfície do líquido e volume do líquido. Os elementos do contorno
do casco e da superfície são triangulares e o do volume do líquido são tetraédricos. Estes
dados juntamente com os parâmetros da simulação são lidos pela aplicação de simulação.
49
Optimização e Avaliação de Aplicações de Simulação Numérica
3.1.2 Aplicação de simulação
O código do simulador resolve as equações incompressíveis de Navier Stokes, que regem o
comportamento de fluidos num determinado domínio. A discretização temporal das
equações de Navier Stokes realiza-se através dum método de passos fraccionados semi-implícitos, enquanto que para a discretização espacial se usa um método de elementos
finitos.
Na simulação do contorno livre (superfície livre do fluido) utiliza-se um método de transpiração, em conjunto com o transporte euleriano da superfície de corrente. Também para
a discretização destas equações se usaram métodos de elementos finitos[Woo99].
Apresenta-se de seguida a vista conceptual[Hof00] da versão série do simulador.
Domínio
Leitura dos
dados
Malha
Escrita dos
resultados
Cod.
Simulação
Leitura da
configuração
Solver
Fig. 3.2 – Vista conceptual do simulador (versão série)
O módulo malha representa os dados físicos do problema, contorno do casco e fluidos
envolventes. O Código de Simulação é responsável pela manipulação dos dados
armazenados na malha, é este código que gera os sistemas de equações a resolver e
actualiza os dados. O Solver resolve os sistemas de equações construídos pelo Código
de Simulação.
Na Fig. 3.3 é apresentada a hierarquia das classes necessárias à implementação do código
numérico do simulador (malha , Código de Simulação e Solver). O armazenamento
dos elementos é realizado usando listas dinâmicas(Plex), uma para cada tipo de
elementos armazenados: casco, fluido e superfície livre. Também os nós são armazenados
usando a classe Plex. Cada nó, para além da informação acerca dos elementos a que
50
Enquadramento
pertence, tem associado os vários graus de liberdade (Dof). Toda a codificação dos
algoritmos e manipulação de dados foi implementada em C++ e usou-se metodologia
orientada a objecto para definição da hierarquia de classes e das relações entre elas. Todos
os dados são criados dinamicamente e os seus acesso, como é obvio, são realizados através de referências.
«bind»(Elemento)
ReaVec
ElmSet
«bind»(VirDof)
«bind»(MVirDof)
T
Plex
Node
FluidElmSet
BodyElmSet
FreeSElmSet
«bind»(Dof)
Elemento
«bind»(Node)
Domain
Conj_Grad
FreeSElm
FluidElm
Solver
BodyElm
Módulo
malha + Cod. Simulação
Fig. 3.3 – Diagrama de classes simplificado do simulador
Em cada iteração da simulação são gerados sistemas de equações (armazenados e
resolvido pelo solver) a partir da representação das malhas. Após a resolução dos
sistemas, os dados armazenados nas listas dinâmicas são actualizados. O sistema é representado por uma matriz esparsa e a resolução dos sistemas é realizada usando o método
iterativo de gradientes conjugados, tal como apresentado por W. Press et al[Pre92].
Versão paralela original
Inicialmente foi desenvolvido por um dos parceiros uma versão paralela do simulador
que executava sobre uma rede de computador usando PVM.
Esta primeira versão paralela do simulador efectua a criação dos sistemas de equações e a
actualização dos dados em paralelo. A resolução dos sistemas é realizada por um único
computador. Os únicos elementos particionados e distribuídos pelos vários computadores
são os que representam o fluido; todos os outros elementos encontram-se replicados pelos
vários nós participantes nos cálculos. O cálculo da distribuição dos elementos do fluido é
realizado pelo particionador genérico Metis[Kar98].
51
Optimização e Avaliação de Aplicações de Simulação Numérica
<<process>>
<<module>>
master
<<module>>
<<module>>
<<module>>
<<module>>
Domínio
malha
Solver
Sist. Com.
Sist. Com.
cria sist.
parcial
ret. sist
parcial
<<process>>
slave
* lê info
no/elem
cria sist.
parcial
ret. valor
send sist
send
sistem
ret sist.
parcial
read Values
create sist
Solve
Read res
Send res
Send res
Send
result
Update
data
Update
data
* Update
node
Fig. 3.4 – Exemplo de uma iteração da simulação
Apresenta-se na Fig. 3.4 uma interacção entre dois processos (o master e um slave) durante
uma iteração da simulação. Em cada iteração os processos criam as submatrizes correspondentes aos dados por si tratados. Antes da solução do sistema, as submatrizes são
transmitidas a um nó que as agrupa num único sistema e resolve-o. Após o cálculo da solução, os resultados são transmitidos para todos os nós que os usam para actualizar os
seus dados privados. A criação dos sistemas de equações é realizado em paralelo pelos
vários processos, reduzindo o tempo total de construção. No entanto, a resolução dos
sistemas de equações e a manipulação dos elementos replicados não aproveita a existência
dos vários processadores: i) o sistema de equações apenas é resolvido num processo e ii)
os dados replicados são manipulados simultaneamente por todos os processos participantes.
3.1.3 Ambiente de execução
Na fase inicial do projecto submeteram-se os parceiros a um inquérito[Cha97] para a
obtenção do tipo de ambiente possivelmente existente nos futuros utilizadores do sistema
a desenvolver. Parte do questionário prendia-se com o ambiente computacional e quais as
possibilidades de executar código paralelo nas suas instalações. Os meios disponibilizados por cada parceiro para a realização de testes está apresentado na Tab. 3.1.
Da observação dos resultados obtidos no inquérito foi possível inferir o tipo de equipa52
Enquadramento
mento informático existente nos futuros utilizadores do sistema. Observa-se facilmente,
que este tipo de empresas não tem possibilidade de usar os sistemas paralelos com melhores desempenhos. Dos sistemas apresentados na secção 2.3.1 (“Arquitectura de Sistemas
Paralelos”), estas empresas apenas têm acesso a multiprocessadores de memória partilhada (com 2 processadores) e, maioritariamente, a clusters de pequenas dimensões.
Parceiro
BAZAN
Execução de código série
Computador Pessoal
 Pentium II
 266MHz
 128Mb RAM



ENVC
Execução de código paralelo
Rede de
 Pentium II
5 ×  266MHz
 128Mb RAM



Servidor
2 × Pentium 
 133MHz 


Workstation HP
BEC
Computador Sun
2 × processadores 
 1.5 Gb RAM 


NautaTec
Computador Pessoal
 Pentium II
 300MHz
 128Mb RAM
SPTech



Computador Pessoal
 Pentium II
 266MHz
 128Mb RAM



Rede de
 Pentium II
4 ×  300MHz
 128Mb RAM



Rede de
 Pentium II
2 ×  266MHz
 128Mb RAM



 Pentium
4 ×  200MHz
 128Mb RAM



Tab. 3.1 – Sistemas usados pelo parceiros para execução do código de simulação
O esforço e a ordem de desenvolvimento baseou-se no tipo de computadores existentes na
maioria dos parceiro:
•
Versão série executando-se eficientemente num computador pessoal
•
Versão paralela executando-se em cluster de computadores pessoais
•
Versão paralela executando-se em multiprocessador de memória partilhada
53
Optimização e Avaliação de Aplicações de Simulação Numérica
3.1.4 Participação do INESC
As principais acções desenvolvidas pela equipa do INESC que participou neste projecto
prenderam-se com a optimização do código desenvolvido e testado pelos outros parceiros
Um outro factor por nós trabalhado foi a melhoria da interface de configuração e execução
das versões paralelas do simulador.
O trabalho por nós realizado sempre esteve dependente do código produzido e verificado
pelos parceiros. O código de simulação era produzido e testado contra resultados experimentais de tanques de ensaio e só depois era disponibilizado para optimização. Por esta
razão, as primeiras optimizações de código não se realizaram sobre o simulador completo,
mas sim sobre uma das partes estáveis: o solver do sistema de equações.
Só numa fase mais avançada do projecto foi possível contactar com o simulador completo
de modo a avaliá-lo e efectuar as optimizações possíveis e necessárias. Assim, foram
alteradas as duas versões existentes da aplicação de simulador: a versão série e a versão
paralela implementada com PVM.
54
4 Realização
Apresentamos neste capítulo, detalhadamente, as alterações realizadas aos programas originais de modo a aumentar o seu desempenho. Estas alterações são apresentadas pela ordem cronológica da sua realização. Para além das optimizações realizadas, também são
descritas outras acções complementares e úteis à optimização do software.
Apresenta-se inicialmente as optimizações realizadas ao solver usado na aplicação de
optimização, assim como a sua paralelização. Mostra-se em detalhe as alterações efectuadas aos vários blocos de código e a duas funções necessárias à resolução dos sistemas.
Apresenta-se de seguida à várias optimizações realizadas sobre a versão série e paralela
da aplicação de simulação completa. No fim deste capítulo são apresentadas as aplicações
complementares desenvolvidas para efectuar a avaliação do código e para facilitar a execução da versão paralela da aplicação de simulação.
4.1 Optimização do Solver (Conjugate gradient)
Durante uma primeira fase do projecto, o nosso esforço foi centrado na optimização do
código de resolução dos sistemas de equações através do método iterativo de gradientes
conjugados. O código usado na versão original não optimizada é uma variação do apresentado por W. Press[Pre92]. A implementação não optimizada original está apresentada
no “Apêndice B – Conjugate Gradient".
55
Optimização e Avaliação de Aplicações de Simulação Numérica
4.1.1 Função Solve
Ao observar a função solve, a primeira constatação é a da existência de um if dentro do
ciclo que serve unicamente para se executar código diferente na primeira iteração.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
r = rhs –r
asolve()
bnrm = snrm()
while{
bknum = r.r
if(iter = 1)
p=r
else
p = bk*p+r
atimes()
akden = r.p
x += ak*p
r -= ak*z
err = snrm()
if (err < k)
break
A eliminação do if é realizada copiando parte do código da primeira iteração para fora
do ciclo, ficando o código como se apresenta na Fig. 4.1.a.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
r = rhs –r
asolve(p,z)
bnrm = snrm(r)
bknum = r.r
p=r
while{
atimes(p,z)
akden = r.p
x += ak*p
r -= ak*z
err = snrm(r)
if (err < k)
break
bknum = r.r
p = bk*p+r
}
a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
r = rhs –r
bknum = r.r
asolve(p,z)
bnrm = snrm(r)
p=r
while{
atimes(p,z)
akden = r.p
r -= ak*z
bknum = r.r
err = snrm(r)
if (err < k)
break
x += ak*p
p = bk*p+r
}
b)
Fig. 4.1 – Optimização da função solve a) remoção do if interno ao ciclo,
b) reordenamento das operações
Esta alteração introduz ganhos distintos conforme as características dos processadores. Se
56
Realização
o processador usado não tiver mecanismos de predição de saltos, para além da eliminação
de uma comparação, também se elimina a necessidade de “esvaziar” o pipeline por se ter
lido e descodificado instruções que não irão ser executadas (ser secção 2.2.2.1). No caso
dos processadores mais recentes (Pentium Pro, por exemplo), devido à sua capacidade de
predição de saltos, apenas se elimina a necessidade de efectuar a comparação em todas as
iterações.
Assim, não só se elimina o if, como também se facilitam as optimizações posteriores.
Após esta primeira optimização, observou-se onde era gasto mais tempo durante a execução da função solve. Realizaram-se, então, as optimizações necessárias e que se apresentam de seguida.
As alterações realizadas a esta função prenderam-se com a optimização dos acessos à memória, aumentando a percentagem de hits na cache.
Observando a função solve
(Fig. 4.1.a), verifica-se que existem duas ocasiões em que se acede ao vector p (linhas 9 e
15) mas separadas por várias outras instruções, cujo código C aqui se apresenta:
1
2
3
4
5
6
7
for (j=first_r;j<=last_r;j++) {
x[j] += ak*p[j];
r[j] -= ak*z[j];
}
(...)
for (j=first_r;j<=last_r;j++)
p[j]=bk*p[j]+r[j];
Com este código, devido à intercalação de outra instruções entre os ciclo, a cache não é
aproveitada no segundo ciclo. O vector p, que havia sido carregado para a cache no
primeiro ciclo, teve de ser substituído por outros dados.
Com a criação de dois ciclos distintos (correspondentes às linhas 1, 2 e 3 anteriores) já há
possibilidade de reordenar as operações, podendo ficar estas contíguas tal como se observa na Fig. 4.1.b (linhas 14 e 15). Assim já podem ser efectuadas num só ciclo:
1
2
3
4
for (j=first_r;j<=last_r;j++){
x[j] += ak*p[j];
p[j]=bk*p[j]+r[j];
}
Esta alteração permite que na segunda instrução de cada iteração do ciclo, não haja
necessidade de aceder à memória principal para ler a posição p[j] visto esta já se encontrar em cache (o cache miss anteriormente correu na instrução x[j] += ak*p[j]).
Com estas alterações optimizou-se o uso da cache. Em cada segundo acesso ao vector, já os
dados acedidos se encontram em cache, eliminando a necessidade de efectuar uma leitura
57
Optimização e Avaliação de Aplicações de Simulação Numérica
da memória. Na situação original, como os acessos aos vectores se encontravam distantes,
na segunda operação já o vector não se encontrasse em cache.
Alterações semelhantes foram realizadas para os outros vectores sempre que possíveis.
Na Fig. 4.1 encontram-se destacados os vário ciclos que foram deslocados e agregados, de
modo a se tirar melhor partido da cache.
4.1.2 Função Atimes
O código original da função atimes apresentado pelo parceiro responsável é o apresentado na Fig. 4.2. Esta função multiplica uma matriz esparsa (sa e ija)por um vector x.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (i=first;i<=last;i++){
b[i] = sa[i]*x[i];
int* ijai = &(ija[ija[i]]);
Real* bi = &(b[i]);
Real* sak = &(sa[ija[i]]);
int*
up = ijai + ((ija[i+1]-ija[i]) & ~07);
while (ijai<up){
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
}
up = &(ija[ija[i]]) + (ija[i+1]-ija[i]);
while (ijai < up) *bi += *sak++ * x[*ijai++];
}
Fig. 4.2 – Implementação original da função atimes
Embora se observe um loop unrolling, no ciclo while, o problema desta implementação
persiste. Observou-se, através do uso de contadores do processador (ver a secção 2.5.2 –
Contadores dos processadores) que ocorrem stalls do processador devido à dependência
entre os resultados das instruções e os operandos das operações seguintes. Também se
verificam atrasos devido à geração dos endereços necessários às realização das instruções.
A nossa proposta para optimização deste código prendeu-se com a eliminação desses
atrasos. O loop unrolling foi eliminado por se verificar que não introduzia ganhos significativos.
As primeiras inicializações dentro do ciclo for (linhas 2 a 6 na Fig. 4.2) são traduzidas
58
Realização
para o seguinte código assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
;b[i]=sa[i]*x[i];
mov ebx, DWORD PTR [esi+28]
fld DWORD PTR [ecx+edx]
fmul DWORD PTR [ebx+eax*4]
fstp DWORD PTR [edx]
;int* ijai = &(ija[ija[i]]);
mov ebx, DWORD PTR [esi+24]
;Real* bi = &(b[i]);
;Real* sak = &(sa[ija[i]]);
mov esi, DWORD PTR [esi+28]
mov ebp, DWORD PTR [ebx+eax*4]
lea ecx, DWORD PTR [ebp*4]
add esi, ecx
lea eax, DWORD PTR [ecx+ebx]
;int* up
= ijai + ((ija[i+1]-ija[i]) & ~07);
mov ecx, DWORD PTR 8+[esp+16]
add ecx, edx
mov ebx, DWORD PTR [ecx+ebx]
sub ebx, ebp
and ebx, -8
; fffffff8H
lea ebx, DWORD PTR [eax+ebx*4]
Devido ao modo como estas instruções assembly estão encadeadas, não é possível
aproveitar o paralelismo fornecido pelos processadores. Por exemplo, as instruções
fld DWORD PTR[ecx+edx] e fmul DWORD PTR [ebx+eax*4] (linha 3 e 4 no código
anterior) não podem ser iniciadas em simultâneo por serem executadas na mesma
unidade de execução (ver secção 2.2.2.1).
Outra causa de penalidades que ocorre com frequência e atrasam a execução do programa
é a geração explícita de endereços. Nas instruções mov ebx, DWORD PTR [esi+24],
mov esi, DWORD PTR [esi+28] e mov ebp, DWORD PTR [ebx+eax*4] (linhas 7, 8
e 9) há uma dependência entre a primeira e a terceira instrução devido ao registo ebx, que
é alterado na primeira instrução e usado no cálculo de um endereço na última instrução.
Problema semelhante existe devido à proximidade das instruções nas linhas 11 e 12.
A optimização deste trecho de código consistiu, essencialmente, na eliminação das gerações de endereços e na intercalação de instruções de tipos distintos. A geração dos endereços passa a realizar-se unicamente dentro do ciclo while.
Estudo semelhante foi realizado para o ciclo interno da função atimes (while apresentado na Fig. 4.2) , observando-se o código assembly gerado e as penalidades que ocorrem da
sua execução. No código interno ao ciclo while ocorrem atrasos distintos daqueles já
descritos.
59
Optimização e Avaliação de Aplicações de Simulação Numérica
1
2
3
4
5
mov
fld
fmul
fadd
fstp
ebp,dword
dword ptr
dword ptr
dword ptr
dword ptr
ptr [eax-14h]
[edi+ebp*4] ;
[esi-14h]
;
[edx]
;
[edx]
;
leitura de x[*ijai++]
multiplicação
soma
armazenamento de *bi
Na tradução em assembly do cálculo *bi += *sak++ * x[*ijai++] atrás apresentada,
observam-se quatro instruções de vírgula flutuante seguidas (fld, fmul, fadd e fstp)
correspondentes à leitura, multiplicação, soma e armazenamento do resultado.
Como o resultado do fmul será um operando do fadd e estas instruções encontram-se
contíguas, esta dependência obrigará à ocorrência duma penalidade. Esta penalidade,
com duração de 1 ciclo de relógio, permite que o resultado da multiplicação seja calculado
antes de ser usado na instrução seguinte. Também ocorre uma penalidade semelhante
aquando da execução do fstp, que necessita de esperar pelo resultado da soma anterior.
Este problema é resolvido afastando a multiplicação da soma, intercalando outras instruções independentes. Na nossa solução, decidimos intercalar, entre os cálculos, as actualizações dos índices. O código final optimizado da função atimes, e com as alterações
atrás descritas, está aqui apresentado:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (i= first; i<=last; i++){
k= ija[i];
aux = ija[i+1]-1;
kaux = k;
ij_aux = ija[k];
daux = sa[i]*x[i];
while (k<= aux){
k++;
daux2 = sa[kaux]*x[ij_aux];
kaux++;
ij_aux = ija[k];
daux += daux2;
}
b[i] = daux;
}
Fig. 4.3 – Versão optimizada da função atimes
Se observarmos o seguinte trecho do código assembly da versão optimizada, podemos
observar que alguns dos problemas apresentados desaparecem.
1
2
3
4
5
60
fld
fmul
mov
add
add
DWORD PTR [edx+ebx*4]
DWORD PTR [edi]
ebx, DWORD PTR [esi+4]
esi, 4
edi, 4
Realização
6
7
dec eax
faddp
ST(1), ST(0)
Observa-se facilmente que entre a multiplicação (fmul na linha 2) e a soma (faddp na
linha 7), existem uma série de instruções independentes e não de vírgula flutuante que
podem ser executadas. Elimina-se assim a necessidade da existência de um stall do
processador. Também se observa que o uso da variável daux para armazenamento do
valor parcial de b[i] permitiu a eliminação de uma instrução fstp (escrita em memória
de um valor real).
4.1.3 Função Asolve
A função asolve, cujo código está apresentado na Fig. 4.4, exemplifica um tipo de código, que, com processamento escalar, é difícil de optimizar.
1
2
3
4
5
6
7
8
9
10
11
void Conj_Grad::asolve(int first, int last, Real b[],
Real x[], int itrnsp){
register int i;
if (itrnsp)
for(i=first;i<=last;i++)
x[i]=b[i];
else
for(i=first;i<=last;i++)
x[i]=(sa[i] != 0.0 ? b[i]/sa[i] :b[i]);
}
Fig. 4.4 – Implementação original da função asolve
Nesta função, grande parte do tempo é despendido no cálculo da divisão b[i]/sa[i]. A
divisão de número reais, nos processadores Pentium, apresenta dois problemas: a instrução demora muitos ciclos a executar e a divisão não pode ser executada em paralelo com
nenhuma outra instrução de vírgula flutuantes (fld, fcomp, fmul, fstp). Estes dois factos aliados levam as instruções seguintes à divisão (fstp e as operações da iteração seguinte) a esperar pela conclusão da divisão.
1
2
3
4
5
6
7
fld DWORD PTR [edx]
fnstsw
ax
test ah, 64
; 00000040H
jne SHORT $L57519
fdiv DWORD PTR [edi]
$L57519:
fstp DWORD PTR [ebx+edx]
Observando o código assembly anterior (correspondente à linha 10 da Fig. 4.4) observa-se
61
Optimização e Avaliação de Aplicações de Simulação Numérica
que imediatamente a seguir à instrução fdiv (linha 5) é executada uma outra instrução
de vírgula flutuante (linha 7). Devido ao desenho do processador Pentium, a instrução
fstm só pode ser iniciada após a conclusão da divisão (fdiv).
Para “esconder” o tempo de execução da divisão seria necessário permitir a intercalação
de outras instruções (inteiras ou de controle) entre a divisão e o armazenamento do resultado. No código apresentado, devido ao reduzido número de instruções existentes dentro
do ciclo, não é possível realizar essa intercalação.
4.2 Paralelização do Solver (Conjugate gradient)
Após a optimização do código, efectuámos a sua paralelização, primeiro para permitir a
execução em multiprocessadores de memória partilhada, em seguida foi avaliada a possibilidade de executar uma versão paralela do solver num clusters de PC’s. Apresentamos
aqui as alterações de código necessárias para a execução do solver nas arquitecturas atrás
apresentadas.
4.2.1 Paralelização usando threads
O primeiro tipo de optimização realizada teve como objectivo possibilitar a execução do
código em computadores multiprocessadores de memória partilhada. Para a realização
desta optimização, usou-se a biblioteca de threads fornecida pela Microsoft para os
sistemas operativos Windows.
Antes de paralelizar o código há necessidade de observar de que modo os dados são
manipulados de modo a efectuar a distribuição dos dados de forma mais eficiente. Na
optimização óptima, um determinada variável (ou porção de um vector) só deve ser
manipulado por uma tarefa. Só assim se consegue simplificar a sincronização necessária
entre tarefas e, no caso do uso de memória distribuída, reduzir a quantidade de dados
transmitidos entre as várias tarefas.
A primeira operação realizada foi a observação dos dados manipulados durante a solução
dum sistema (A.x = rhs), tendo-se coligido a seguinte informação apresentada na Tab.
4.1.
Para cada variável manipulada na resolução do sistema, é indicado o seu tipo (escalar ou
vector) e tamanho, assim como o significado. Também é indicado, para cada uma das variáveis) de que modo é manipulada durante a execução, mostrando-se também de que variáveis dependem os seu valores.
62
Realização
ija, sa Matriz esparsa A (nrows × nrows)
Sistema de equações
Matriz esparsa onde se encontram guardadas as equações que formam o
sistema. Apenas é lida durante a solução do sistema, não sendo alterada
a partir daí.
Rhs Vector com nrows elementos
Resultado do sistema
Vector com o resultado do sistema. Apenas é lido durante a resolução do
sistema, não sendo alterada a partir daí.
Err Escalar
Erro dos valores calculados
err = r
X Vector com nrows elementos
Valores das incógnitas
x = x + ak * p
R Vector com nrows elementos
Variável auxiliar
r = b - A * x (inic), r = r + ak * z (iter)
Z Vector com nrows elementos
Variável auxiliar
z = diag(A)– 1 * b (inic), z = A * p (iter)
P Vector com nrows elementos
Variável auxiliar
P = z + bk * p
Bknum Escalar
bknum = r . r
Variável auxiliar
akden Escalar
Akden = z . p
Variável auxiliar
ak, bk Escalares
Variáveis auxiliares
ak = bknum/akden, bk = bknum/bknum-1
Tab. 4.1 – Dados manipulados na função solve e suas dependências
Observando a tabela anterior, concluiu-se que os elementos dos vectores X, R Z e P,
devido às operações onde ocorrem, podem apenas ser manipulados por uma tarefa, e que
essa tarefa manipula sempre os elementos dos vários vectores com índices idênticos.
Decidiu-se assim uma destruição dos vectores pelas várias tarefas: a cada tarefa fica associado o limite inferior e superior (first_r, last_r) dos sub-vectores por si guardados e
manipulados.
Apresenta-se de seguida a paralelizações da operação x = x + ak * p. Cada tarefa
executa o mesmo código, mas como cada uma tem limites (first_r, last_r) distintos,
cada elemento dos vectores apenas é acedido por uma tarefa.
63
Optimização e Avaliação de Aplicações de Simulação Numérica
1
2
3
for (j=first_r;j<=last_r;j++) {
x[j] += ak*p[j];
}
De modo igualmente simples, mas com necessidade de comunicação adicional, foram implementados os produtos internos:
1
2
3
4
5
6
7
8
9
for (bknum=0.0, j=first_r;j<=last_r;j++) {
bknum += r[j]*r[j];
bknum += r[j+1]*r[j+1];
}
part_bknum[proc_id] = bknum;
barrier(0);
bknum = 0;
for (aux = 0; aux < Tmk_nprocs; aux ++)
bknum += part_bknum [aux];
Fig. 4.5 – Versão paralela dum produto interno
No primeiro ciclo, cada tarefa calcula o produto interno correspondente ao sub-vector por
si manipulado, armazenando de seguida a sua comparticipação para o valor final num
vector partilhado por todas as tarefas (part_bknum, neste exemplo). A sincronização
entre as várias tarefas é realizada na instrução barrier. Depois de todos os valores terem
sido escritos no vector partilhado, é possível a cada tarefa calcular o valor final do
produto interno (bknum).
O produto entre a matriz A e os vectores (z = A * p, por exemplo) também aproveita a
divisão dos dados anteriormente definida, mas obriga a que alguns vectores sejam partilhados e acessíveis a todas as tarefas. A multiplicação de uma matriz esparsa por um vector era executada originalmente tal como se apresenta na Fig. 4.6.
t0
X
=
t18
A (ija, sa)
x
b
1
2
3
4
5
6
7
8
for (i=0; i<nrows ;i++) {
b[i]=sa[i]*x[i];
k=ija[i]
while(k<=ija[i+1]-1){
b[i] += sa[k]*x[ija[k]];
k++;
}
}
Fig. 4.6 – Multiplicação de uma matriz por um vector (versão série)
Tal qual na multiplicação de uma matriz normal por um vector, o elemento i do vector b
é obtido efectuando o produto interno A[i].x. Como a matriz é esparsa as linhas de A
64
Realização
não são percorridas do início ao fim, mas apenas onde existem valores não nulos (posições cinzentas em A).
Existem dois modos de distribuir os cálculos pelas várias tarefas, estando-lhes associados
dois modo de partir a matriz.
Se a matriz for particionada em colunas, ficando cada tarefa com um conjunto disjunto de
coluna, não há necessidade da partilha de x, mas cada tarefa apenas calcula os resultados
parciais de b. No fim dos cálculos deve-se consolidar os resultados de cada tarefa. Nesta
caso cada tarefa, e para cada índice i, apenas calcula parte do produto interno A[i].x: cada tarefa apenas efectuar A[i][first_r..last_r].x[first_r..last_r]. No final
dos cálculos parciais há necessidade da agregação dos valores parciais.
Na solução por nós adoptada, a matriz é partida em vários conjuntos de linhas, ficando
cada tarefa com um desses conjuntos. Neste caso, cada tarefa consegue calcular completamente os elementos de b a si associados.
Cada elemento de índice i do vector resultado depende apenas da linha i da matriz, mas
também depende, potencialmente, de todo o vector x. Por esta razão o vector x deve ser
partilhado e acessível por todas as tarefas, embora só a sua actualização seja feita noutra
parte do código e em paralelo pelas várias tarefas.
Na Fig. 4.7 é apresentado um esquema e o código da versão paralela de cálculo do produto entre uma matriz e um vector.
t0
X
=
t6
t0
t12
A (ija, sa)
x
b
1 for (i=first_r;i<=last_r;i++){
2
b[i]=sa[i]*x[i];
3
k=ija[i]
4
while(k<=ija[i+1]-1){
5
b[i] += sa[k]*x[ija[k]];
6
k++;
7
}
8}
Fig. 4.7 – Multiplicação de uma matriz por um vector (versão paralela)
Neste caso, os produtos internos A[first_r+i].x realizados por tarefas distintas são
executados simultaneamente (representados pelas setas distintas na Fig. 4.7).
O cálculo do índice mínimo e máximo de cada tarefa (first_r, last_r) é realizado do
modo mais simples: o número de linhas da matriz é dividido pelo número de tarefas,
65
Optimização e Avaliação de Aplicações de Simulação Numérica
sendo, a partir desse valor, calculados os índices.
Como a matriz é esparsa, não é garantido que o número de operações realizadas pelas várias tarefas e o tempo de execução associado sejam iguais para todas elas. Pode ocorrer
que o bloco atribuído a uma das tarefas tenha mais elementos, obrigando à execução de
mais cálculos, mesmo após o término das outras tarefas. Para equilibrar os tempos de
execução das várias tarefas, o cálculo do índice mínimo e máximo de cada tarefa deveria
ser realizado tendo em atenção o número de elementos de cada linha. A situação óptima,
para esta operação seria encontrada quando os elementos estivessem irmãmente distribuídos pelas tarefas. Esta nova distribuição iria aumentar o tempo de execução da função
atimes e da multiplicação de vectores. Com a distribuição equitativa dos elementos dos
vectores entre tarefas, todas as tarefas executam o mesmo número de operações o que minimiza o tempo total de execução das multiplicações e da função atimes.
4.2.2 Paralelização usando DSM
Após a paralelização do código usando threads e memória partilhada, testámos a
possibilidade de executar este código numa rede de computadores pessoais.
O paradigma de programação usado foi memória partilhada e distribuída e a biblioteca
utilizada foi o TreadMarks. Como o paradigma de programação é muito semelhante ao
usado na paralelização anterior, as alterações ao código são mínimas.
O modo de partir e distribuir os dados manipulados pelas tarefas mantém-se iguais. A
sincronização também se mantêm, visto a primitiva usada, a barreira, ser o modo privilegiado de sincronização, quando se programa usando memória partilhada e distribuída.
Só a criação dos dados deve ser alterada. Enquanto que, na memória partilhada normal
com o uso de threads, todas as variáveis globais e dados acessíveis a partir destas são partilhadas por todas as tarefas, na memória partilhada e distribuída tal não ocorre. Há necessidade de, aquando da alocação de memória, indicar explicitamente que esses dados
serão criados no espaço partilhado. Observa-se na Fig. 4.8 o modo de criação de memória
partilhada e distribuída.
Neste exemplo, é a tarefa inicial que cria o vector no espaço de memória partilhado
através de função Tmk_malloc. A referência para essa memória é guardada na variável
global p. Há depois a necessidade de distribuir por todas as tarefas o novo valor da
variável p. Como p é uma variável global, mesmo não se encontrando em memória
partilhada, o seu endereço é igual em todas as tarefas. Após a instrução Tmk_distibute,
66
Realização
todas as tarefas ficam com a variável p a apontar para o vector criado em memória
partilhada e distribuída, passando a ser responsabilidade do sistema a coerência e
actualização dos dados distribuídos.
1
2
3
4
5
if (Tmk_proc_id == 0){
p = (Real *) Tmk_malloc((nrows+1)*sizeof(Real));
Tmk_distribute((char *) &p, sizeof (p));
}
Tmk_barrier(0);
Fig. 4.8 – Criação de um vector em memória partilhada e distribuída
4.3 Optimização do simulador (aplicação FLASH)
Da avaliação da aplicação de simulação (aplicação cuja vista conceptual se apresenta na
Fig. 3.2) observámos que era gasto tempo substancial na construção das matrizes esparsas
necessárias à representação dos sistemas de equações (ver secção 3.1.2). Este tempo era
substancialmente superior ao da leitura dos dados e resolução dos sistemas, correspondendo a cerca de 90% do tempo total de execução. A redução deste tempo foi a primeira
medida tomada na optimização do simulador.
Como as matrizes esparsas optimizam a utilização de memória, antes da sua criação é
necessário saber qual o número de elementos a armazenar e quantos elementos terá cada
linha, não bastando saber quantas linhas a matriz irá ter. É apresentado na Fig. 4.9 o modo
como originalmente se calculava a dimensão (número de elementos) exacta da matriz.
t0 0
1
+1
1
+1
1
0
1
1
1
0
1
1
2
0
1
2
0
1
3
+1
+1
3
4
+1
1
2
+1
+1
+1
3
4
5
+1
+1
+1
+1
+1
t18 1 +1 2 +1 4 +1 5 +1 6 +1
1
2
3
4
5
6
7
8
void usePos(int col,
int lin){
if (col == lin)
return ;
for (j = lin;
j<nrows;j++){
Row[j] ++;
}
Fig. 4.9 – Conversão para matriz esparsa (versão não optimizada)
No exemplo anterior as linhas têm as seguintes dimensões: (1, 1, 2, 1, 1). Cada linha da
figura representa a contabilização de um elemento não nulo pertencente à matriz, sendo
também indicadas as operações (somas) realizadas para cada elemento não nulo.
O código apresentado anteriormente é invocado para cada elemento que se deseja
67
Optimização e Avaliação de Aplicações de Simulação Numérica
armazenar na matriz, tendo como parâmetros a posição do elemento. Durante a contabilização da dimensão da matriz, o vector Row contém em cada posição i o número de elementos já contabilizados pertencentes a linhas com índice menor ou igual a i. No final
tem-se, em cada posição do vector, o número de elementos que iriam existir nas linhas da
matriz com índice menor ou igual.
O código original, para cada novo elemento da matriz não pertencente à diagonal, incrementa o valor de todas as posições do vector com índice superior ou igual ao índice da
sua linha. Consegue-se assim calcular não só, quantos elementos serão armazenados na
matriz, como também em que índice da matriz esparsa começará cada linha. Como se
pode facilmente observar, este código executa em O(n2) tempo, o que o torna ineficiente
para matrizes com dimensões elevadas.
A alteração proposta por nós obtém os mesmos resultados mas, nos estádios intermédios,
não guarda os valores acumulados, mas apenas o número de elementos de cada linha.
t0 0
1
0
+1
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
2
t18 1 +1 1
2
1
1+1
2
t6
+1
+1
2+2
4
+1
1
1
1
1
1
1
1
4+1
5
+1
5+1
6
t10
1
2
3
4
5
6
void usePos(int col,
int lin){
if (col == lin)
return ;
Row[lin] ++;
}
7
8
9
10
for(ind =1; ind <nrows;
ind++){
Row[ind] += Row[ind-1];
}
Fig. 4.10 – Conversão para matriz esparsa (versão optimizada)
A contabilização do número de elementos de cada linha, realiza-se apenas com o incremento do valor correspondente à linha. Após a recolha de todos os dados é necessário
calcular os valores acumulados, bastando para tal um ciclo como o apresentado na Fig.
4.10. Conseguimos assim reduzir o tempo de execução para O(n).
Após esta primeira optimização, cujos resultados se apresentam na secção 5.4 foi investigado se havia mais possibilidades de optimização. Da observação que se realizo concluiu-se que os tempos de execução estavam muito bem distribuído pelas várias funções. Tendo-se tentado optimizar algum código numérico concluiu-se que, embora localmente os
68
Realização
benefícios fossem visíveis, não se observavam resultados globais que compensassem o
esforço de optimizar o código disperso pelo programa.
4.4 Paralelização do simulador (aplicação FLASH)
Após a optimização da versão série do simulador, foi-nos apresentada uma versão paralela que executava sobre uma rede de computadores usando PVM. Apresenta-se aqui todas
as acções tomadas para acelerar a execução desta versão do simulador. O trabalho aqui
descrito foi apresentado na conferência “PARA2000 – Workshop on Applied Parallel
Computing” e publicado nos seus proceedings[Sil00].
Observou-se inicialmente que esta versão, em cada iteração, transmitia entre os vários nós
e o master uma série de vectores, estando parte substancial destes preenchida com zeros.
O nosso objectivo foi tentar reduzir a comunicação entre os vários nós de processamento.
Na primeira alteração proposta, decidiu-se alterar o modo de sincronização e a sua localização. Na versão original, a sincronização das tarefas realiza-se ao nível do código. Quando as tarefas atingem determinada linha de código, bloqueiam-se à espera que todas as
outras atinjam essa mesma posição, de modo a permitir a transmissão dos dados. Na nossa primeira proposta, a sincronização passou a estar associada aos acessos aos dados partilhados.
A divisão dos elementos processou-se do mesmo modo(ver secção 3.1.2), mas os nós que
anteriormente estavam replicados passaram a ser criados em memória partilhada e o seu
acesso passou a ser guardado por primitivas de sincronização.
Para a criação dos objectos em memória partilhada, redefiniu-se o método new de modo a
que , caso se desejasse, este método devolvesse um ponteiro para memória partilhada:
1
2
3
4
5
6
7
void * operator new (size_t sz, int shared){
if (shared && initialized){
return Tmk_malloc(sz);
}else{
return malloc(sz);
}
}
Os novos nós e vectores que devessem estar localizados em memória partilhada passaram
a ser criados invocando o new de um dos seguinte modos:
•
theNode =
•
theNode->NewVector(velc_t,new (1) ReaVec3)
new (1) Node(index, coords)
69
Optimização e Avaliação de Aplicações de Simulação Numérica
A manipulação dos dados dos nós deve ser realizada de modo sincronizado, evitando corridas sobre os dados do objecto. Para tal usam-se os locks fornecidos pela plataforma
TreadMarks:
1
2
3
Tmk_lock_acquire(node(iNodE)->Index()%CONST);
node(iNodE)->ConnectedElems++;
Tmk_lock_release(node(iNodE)->Index()%CONST);
De modo a não haver um único lock a guardar todos os dados, o que reduzia o
paralelismo, ou a exceder o número máximo de locks (caso se atribuísse um lock a cada
nó), decidiu-se distribuir os nós pelos lock tendo em atenção o seu índice.
Embora não houvesse transmissão de dados associada ao acesso, a transmissão de informação de controle da própria sincronização distribuída tornou esta aproximação impraticável. Os tempos de execução cresceram várias ordens de grandeza.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Send_Rhs(){
if(This_Process != 0){ /* escravo – envio */
pvm_initsend( PvmDataDefault );
Pack_Array((rhs + 1), nrows, 1);
Send_Message(tids[0], SEND_IRHS);
}else /* mestre – recepcção */
for(int i=1 ; i<Number_Of_Processes ; i++ )
Recv_Rhs(tids[i]);
}
void Recv_Rhs(int tid){
Real* recv_s;
int ttsize = nrows;
Real* recv_s = new Real[nrows];
Recv_Message( tid, SEND_IRHS );
Unpack_Array( recv_s, nrows, 1 );
Real* up = recv_s + nrows;
register Real* s = recv_s ;
register Real* t = rhs + 1;
while(s < up)
(*t++) += (*s++);
delete recv_s;
}
Fig. 4.11 – Envio dos dados necessário à criação do sistema de equações
(comunicação entre processos usando PVM)
Tendo-se frustrado esta primeira tentativa, decidimos voltar a avaliar a versão paralela
original e tentar reduzir o tempo de transmissão dos dados entre tarefas. Para tal
observou-se de que modo as várias tarefas interagiam e onde e como transmitiam os
70
Realização
dados entre elas.
Em cada iteração (período de tempo) da simulação são transmitidos, para um computador central, os dados manipulados pelas várias tarefas. É então executado código não paralelizado e retornado para todas as tarefas o resultado da computação. O código de
comunicação dos dados está apresentado na Fig. 4.11.
Como os vectores transmitidos não são preenchidos completamente por todas as tarefas
(há elemento privados a cada tarefa), esta solução, implementada em PVM, tem o inconveniente de, em cada chamada da função Send_Message, ser enviado todo o vector, e
não só os dados actualizados pela tarefa e necessários à tarefa receptora.
Com o uso de memória partilhada e distribuída esperámos reduzir os dados transmitidos.
Como os algoritmos de coerência dos sistemas DSM, para reduzir a comunicação, apenas
transmitem os dados realmente alterados e acedidos por outra tarefa, o uso desta
plataforma para comunicação entre as tarefas pareceu-nos uma boa aposta.
Portanto, o código de comunicação entre processos original foi substituído pelo código
apresentado na Fig. 4.12.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void Send_Rhs(){
int i;
if(Tmk_proc_id != 0){ /* escravo – envio */
Tmk_barrier(0);
/* sicronização 1 */
for (i = 1; i<= nrows; i++)
rhs_shr[Tmk_proc_id][i] = rhs[i];
Tmk_barrier(0);
/* sicronização 2 */
}else{
/* mestre – recepcção */
if (rhs_shr[0] == NULL){
rhs_shr[0] = (Real *) 1;
for(i=1 ; i<Tmk_nprocs ; i++ ){
rhs_shr[i] =
(Real *)Tmk_malloc(
(nrows+1)* sizeof(Real));
Tmk_distribute((char *) &rhs_shr[i],
sizeof (Real *));
}
}
Tmk_barrier(0); /* sicronização 1 */
Tmk_barrier(0); /* sicronização 2 */
for(i=1 ; i<Tmk_nprocs ; i++ )
Recv_Rhs(i);
}
}
void Conj_Grad::Recv_Rhs(int tid){
71
Optimização e Avaliação de Aplicações de Simulação Numérica
27
28
29
30
31
32
Real* up = rhs_shr[tid] + nrows +1;
register Real* s = rhs_shr[tid] +1;
register Real* t = rhs + 1;
while(s < up)
(*t++) += (*s++);
}
Fig. 4.12 – Envio dos dados necessário à criação do sistema de equações
(comunicação entre processos usando DSM)
Observa-se que a comunicação explícita foi substituída pela transferência dos dados para
um vector criado em memória partilhada (escrita apresentada na linha 6 e leitura na linha
31, dentro da função Recv_Rhs).
A instrução de sincronização seguinte (linha 7 do lado dos escravos e linha 21 no mestre)
garante que todas as tarefas são informadas da ocorrência de alterações na memória partilhada. Devido ao sistema usado (TreadMarks) e ao seu modelo de coerência de dados,
nesse instante não são transmitidos os dados escritos para memória partilhada, apenas é
enviada informação acerca da memória alterada. A transferência dos dados só será
realizada quando o processo mestre ler os valores presentes no vector. Também devido às
características do modelo de consistência, só os dados alterados serão transmitidos. As
partes do vector que têm sempre o mesmo valor (zeros) apenas são transmitidas entre
processos uma única vez. Em todos os outros acessos subsequentes, não há necessidade
de comunicação, devido ao facto dessa parte do vector não ter sido alterada.
A comunicação dos resultados da computação realiza-se de modo semelhante (ver
Fig. 4.13). O servidor escreve os valores num vector partilhado e cada tarefa acede aos
dados pretendidos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
72
void Read_Second_Solution(){
Node* NodePrt;
int NNode = get_number_of_real_nodes();
Tmk_barrier(0);
if(Tmk_proc_id == 0){ /* mestre – escrita */
if (press_ss_shr == NULL){
press_ss_shr =
(Real *) Tmk_malloc(NNode * sizeof(Real));
Tmk_distribute((char *) &press_ss_shr,
sizeof (Real *));
}
Real* real_pointer = press_ss_shr;
int idx;
Realização
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LOOP_NODES
*real_pointer++ = PRESDOF->x(t);
Tmk_barrier(0); /* sincronização 1 */
}else{
Tmk_barrier(0); /* sincronização 1 */
Real* real_pointer = press_ss_shr;
int idx;
LOOP_NODES
PRESDOF->x(t) = *real_pointer++;
}
}
Fig. 4.13 – Envio da solução do sistema de equações
(comunicação entre processos usando DSM)
Como os nós estão replicados em todas as tarefas, não se obtém ganho algum com o uso
de DSM. Neste caso todas as tarefas necessitam de consultar o vector partilhado. Se os nós
estivessem distribuídos pelas várias tarefas, já não era necessário o envio de todo vector
para todas as tarefas.
4.4.1 Servidor para execução de tarefas remotas (TreadMarks)
O sistema TreadMarks usa, para lançamento das tarefas remotas, o serviço rexec (remote
execute). O uso deste método de invocação remota tem alguns problemas, quando
implementado sobre uma plataforma Windows:
•
difícil de configurar e usar;
•
falta de uma implementação gratuita do servidor de execução remota;
•
modo pouco seguro de invocação remota de comandos.
Devido aos três motivos atrás apresentados, decidimos implementar um pequeno servidor que executa os comandos remotamente invocados, substituindo-se assim o rexec.
Este servidor foi implementado usando o serviço RPC. Não só se conseguiu desenvolver
facilmente o servidor, como também se passa a usufruir da autenticação e segurança
fornecida pelo serviço de RPC do Windows.
O serviço de RPC do Windows fornece um modo de autenticação dos clientes remotos
integrado com a autenticação e identificação dos utilizadores do Windows. Assim, não há
necessidade de, aquando da invocação remota, efectuar a autenticação explícita do utili73
Optimização e Avaliação de Aplicações de Simulação Numérica
zador. Após a autenticação inicial, os processos criados no servidor executam com a identidade do utilizador-cliente. Estes processos só podem realizar as operações permitidas ao
utilizador, reduzindo-se assim a exploração maligna da execução remota. Associada à
autenticação, está a possibilidade de executar a comunicação sobre um canal cifrado.
Para permitir o uso pelos vários programas-clientes, desenvolveu-se também uma biblioteca, que exporta uma rotina que executa a invocação remota.
4.5 Avaliação de desempenho das versões série
Para a realização da avaliação das aplicações e optimizações realizadas e cujos resultados
apresentamos no capítulo 5, usámos várias técnicas distintas:
•
Instrumentação do código
•
Avaliação não intrusiva
A versão original do simulador contém uma classe de medição do tempo de blocos de
código. A inicialização dos temporizadores, o início da contagem e fim são programados
explicitamente no código. A contabilização realizada já permite a identificação das áreas
problemáticas, mas não permite identificar correctamente quais as funções que devem ser
optimizadas. Este método só permite medições com grande granularidade, superior à da
função.
Após esta primeira fase, houve necessidade de observar com maior exactidão quais as
funções e, no seu interior, que código executa com menor eficiência. Para tal, usou-se a
aplicação VTUNE da Intel. Esta aplicação, tal como descrito na secção 2.5.5.3 permite a
identificação do código que executa durante mais tempo e onde ocorrem os eventos
indicativos de quebras de desempenho.
Para a medição precisa do tempo executado e dos ganhos obtidos com as optimizações,
introduzimos no código chamadas à função de leitura dos contador de alta precisão
fornecido pelo sistema operativo (secção 2.5.1.2).
4.5.1 Driver para leitura de contadores
Para identificação mais precisa dos eventos que atrasam a execução da aplicação foi
necessária a leitura dos contadores do processador (ver secção 2.5.2). Como as instruções
de configuração e leitura dos contadores do processador são privilegiadas, é necessária a
execução do código em modo núcleo. O driver desenvolvido exporta duas funções, uma
para configuração do contador, indicando-se qual o evento a contabilizar e outra para
74
Realização
leitura do valor armazenado.
O código de programação de um dos contadores existentes no processador está apresentado na Fig. 4.14. A instrução wrmsr serve para escrever nos registos específicos do processador, o índice do registo está armazenado em ECX e o valor a escrever está em EDX:EAX
(valor de 64 bits).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void inic_c_event1(int n_event, int umask){
__int32 PerfEvtSel1 = 0;
PerfEvtSel1 = PerfEvtSel1 | n_event | (umask * 256)|
_USER_MODE| _EDGE_DECT| _ENABLE;
__asm{
xor edx, edx;
xor eax, eax;
mov ecx, 0xC2;
wrmsr ; inicalizacao do contador a 0
mov edx, DWORD PTR PerfEvtSel1;
mov eax, DWORD PTR PerfEvtSel1;
mov ecx, 0x187;
wrmsr ; programacao do contador
}
}
Fig. 4.14 – Inicialização de um contador do processador Pentium
Na primeira escrita, efectuada sobre o registo PerfCtr1 (contador), inicializa-se o valor
do contador a zero. Sabe-se então que, nas próximas contagens, o valor armazenado no
contador é baixo, reduzindo a probabilidade de overflow do contador.
Na segunda escrita, indica-se que evento será contado e quais as características da contagem, escrevendo no registo PerfEvtSel1 (0x187). Na programação deste registo indicam-se as características da contagem a realizar e cujo valor irá ser armazenado no registo
PerfCtr1:
•
Identificação do evento a contabilizar (n_event e umask)
•
Indicação de que a contagem só se realiza quando ocorre em modo utilizador
•
Detecção das transições dos eventos
Também se indica que a contagem se deve iniciar imediatamente.
A leitura do registo PerfCtr1 (Fig. 4.15) também se deve realizar em assembly. Para
75
Optimização e Avaliação de Aplicações de Simulação Numérica
garantir que, durante a execução da leitura, todas as outras instruções anteriores se
executaram completamente, invoca-se a instrução cpuid.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
__int64 get_c_event(int contador){
__int32 CTR0_L= 0;
__int32 CTR0_H= 0;
__int64 CTR0;
__asm{
xor EAX, EAX;
cpuid;
mov ecx, DWORD PTR contador;
rdpmc;
mov CTR0_L, EAX;
mov CTR0_H, EDX;
}
CTR0 = CTR0_H<<32;
CTR0 += CTR0_L;
return CTR0;
}
Fig. 4.15 – Leitura de um contador do processador Pentium
A instrução rdpmc lê o valor do contador de desempenho armazenado em contador (0
ou 1) e armazena o resultado da leitura nos registos EDX:EAX, que são retornados agrupados num valor de 64 bits.
Para aceder a estas duas funções, houve necessidade de gerar todo o código de controlo e
inicialização do driver, assim como para aceder às funcionalidades exportadas.
4.6 Avaliação de desempenho das versões paralelas
Para avaliar os ganhos obtidos com as várias versões paralelas do simulador, para além
da medição do tempo de execução, houve necessidade de efectuar medições da quantidade de dados transmitidos entre os vários nós. Os tempos de execução forma medidos
usando as técnicas atrás descritas (secção 4.5).
Para efectuar a contabilização dos dados transmitidos na versão paralela, implementadas
com PVM e TreadMarks, usaram-se os contadores do sistema operativo Windows (ver
secção 0) que armazenam a quantidade de dados transmitidos por uma placa de rede.
Para facilitar a leitura dos valores desenvolveram-se duas funções que escondem os de76
Realização
talhes de inicialização dos contadores (Fig. 4.16) e sua leitura (Fig. 4.17).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int inic_count_bytes(HCOUNTER *hCounter1,
HCOUNTER *hCounter2){
PDH_STATUS res;
res = PdhOpenQuery( /* criacao de query */
NULL,
10,
&hQuery);
if (res != ERROR_SUCCESS)
return -1;
res = PdhAddCounter( /* adicao de contador */
hQuery,
"\\Network Interface(NDIS 5.0 driver)\\Bytes
Received/sec",
0,
hCounter1);
if (res != ERROR_SUCCESS)
return -1;
res = PdhAddCounter( /* adicao de contador */
hQuery,
"\\Network Interface(NDIS 5.0 driver)\\Bytes
Sent/sec",
0,
hCounter2);
if (res != ERROR_SUCCESS)
return -1;
}
Fig. 4.16 – Programação necessária à leitura dos contadores do Windows
A instrução inicial (PdhOpenQuery) cria uma estrutura de dados, a partir da qual se acedem aos dados pretendidos. É ao handle hQuery que se irão associar os contadores relevantes e que mais tarde será utilizado para ler os valores pretendidos. Invoca-se de
seguida a instrução PdhAddCounter. É deste modo que se associam os contadores à
query criada anteriormente; também assim são criadas as referências para os contadores
que serão lidos e formatados mais tarde. O primeiro contador indicado representa os
número de bytes recebidos pela interface de rede, enquanto que o segundo representa os
enviados.
A leitura dos valores armazenados nestes contadores efectua-se invocando a seguinte
função:
77
Optimização e Avaliação de Aplicações de Simulação Numérica
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int print_bytes(){
PDH_RAW_COUNTER Value2;
PDH_RAW_COUNTER Value1;
PDH_STATUS res;
res = PdhCollectQueryData(hQuery); //recolha dos valores
if (res != ERROR_SUCCESS)
return -1;
res = PdhGetRawCounterValue( // leitura do contador 1
hCounter1,
NULL,
&Value1);
if (res != ERROR_SUCCESS)
return -1;
res = PdhGetRawCounterValue( // leitura do contador 2
hCounter2,
NULL,
&Value2);
if (res != ERROR_SUCCESS)
return -1;
printf( "-received %I64d -sent %I64d\n",
Value1.FirstValue,
Value2.FirstValue);
}
Fig. 4.17 – Leitura de um valor contabilizado num contador do Windows
A invocação desta função desencadeia duas acções distintas. A recolha dos dados é realizada quando se executa a função PdhCollectQuerydata. Neste instante são lidos os
valores correspondentes aos contadores associados à query. Para aceder aos dados lidos é
necessário executar a função PdhGetRawCounterValue para cada um dos contadores
associados à query. Embora os contadores representem a taxa de transferência de dados e
não a quantidade de dados transmitidos ou recebidos, é possível obter estes últimos valores. Como apenas lemos os valores brutos (Raw) destes contadores, estes apenas representam a quantidade de dados. Se desejássemos obter as taxas seria necessário efectuar uma
leitura formatada, que automaticamente devolve as taxas de recepção e envio.
4.7 Resumo
Apresentámos neste capítulo as várias optimizações realizadas à aplicação de simulação
do sistema Flash.
78
Realização
A optimização do código começou com a alteração do código de resolução de sistemas de
equações, visto ter sido este o primeiro código apresentado pelo parceiro responsável pela
geração do código do simulador. Este código consistia essencialmente em manipulações
matemática de dados armazenados em vectores. Por esse motivo as optimizações aplicadas foram todas elas dependentes do processador onde o código iria executar. Também se
paralelizou este código de modo a ser executado em multiprocessadores de memória partilhada e numa rede de computadores.
Após este primeiro esforço, seguiu-se a optimização da aplicação de simulação. Aqui, apenas se conseguiu aplicar com sucesso optimizações não dependentes do processador.
Mais tarde, também se optimizou a versão paralela da aplicação de simulação que executava numa rede de computadores. Para reduzir o tempo despendido na comunicação dos
dados, decidiu-se substituir a biblioteca de comunicação PVM pelo sistema memória partilhada e distribuída TreadMarks.
79
5 Avaliação
Após a aplicação das várias técnicas de optimização atrás apresentadas, é necessário verificar se as alterações produziram os resultados esperados. Neste capítulo são apresentados e comentados os vários valores medidos durante as várias versões seriais e paralelas,
optimizadas e não optimizadas. Os valores apresentados incluem os tempos de execução
e também outros indicadores do desempenho das aplicações relevantes.
No início deste capítulo descrevemos o ambiente de teste usado na avaliação do código
sendo os resultados obtidos apresentados de seguida. A ordem pela qual os resultados
são apresentados é a mesma pela qual as optimizações foram descritas no capítulo anterior. Aparecem primeiro os resultados da optimização do código de resolução de sistemas
de equações, aparecendo no fim os resultados da optimização da aplicação de simulação.
5.1 Ambiente de teste
Para a avaliação das optimizações usámos três ambientes de teste distintos, correspondentes às arquitecturas da plataforma de execução dos protótipos. As características dos computadores usados neste teste apresentam-se na Tab. 5.1.
O computador pessoal com dois processadores Pentium foi usado na avaliação da paralelização do solver, enquanto que nos outros testes usaram-se computadores Pentium II. Na
execução da versão paralela do simulador (sobre PVM e TreadMarks) usaram-se quatro
computadores PC Pentium II ligado por uma rede ethernet a 100 Mbit/s.
As versões de teste foram compiladas usando o compilador de C/C++ da Microsoft. Das
81
Optimização e Avaliação de Aplicações de Simulação Numérica
flags usadas, as mais significativas são as apresentadas na Tab. 5.1. Os programas gerados
não contêm código de debug e o código gerado contém as optimizações necessárias e conhecidas pelo compilador para aumentar a velocidade de execução:
•
Eliminação de sub-expressões locais e globais;
•
Alocação automática de registos;
•
Optimização de ciclos (Eliminação de sub-expressões internas ao ciclo);
•
Substituição de funções pelo código correspondente (abs, memcpy, strcmp, …);
•
Geração de código mais rápido (invocação de mais instruções assembly, mas com
menor custo de execução).
PC Dual Pentium
PC Pentium II
2x Intel Pentium
Intel Pentium II
@100MHz
@233MHz
Memória Primária
64 Mb
64 Mb
Cache L1 (Dados)
8kb
16Kb – 32b/linha
Processador
4-way set-associative
write-back
Cache L1 (Código)
8kb
16Kb
4-way set-associative
Cache L2
Interface de rede
512 Kb
ethernet 100Base-T
—
Sistema Operativo
Windows NT 4
Compilador
Microsoft 32-bit C/C++ Optimizing Compiler
Versão 12.00.8168 for 80x86
Flags: /MT /O2 /D "NDEBUG"
Tab. 5.1 – Características dos computadores usados nos testes de desempenho
5.2 Optimização do Solver (Conjugate gradient)
Das optimizações realizadas à versão série do solver apresentados na secção 4.1 obtiveram-se os resultados que agora se apresentam. Primeiro apresenta-se uma análise estática
do código, mostrando o número de instruções, a duração de execução destas e o número
de ciclos perdidos devido a penalidades que ocorrem durante a execução.
82
Avaliação
Os testes, cujos resultados aqui apresentamos, foram realizados com um sistema de
equações cuja uma matriz quadrada tem 15099 linhas e 112209 elementos não nulos. Este
sistema é resolvido em 175 iterações. Para a realização dos testes usou-se um computador
Pentium II com as características apresentadas na Tab. 5.1.
Análise estática do código
Apresenta-se na próxima tabela uma contabilização do número de instruções e seu tempo
de execução para cada bloco do solver: i) ciclos onde se efectuam multiplicações de
vectores por escalares, ii) função atimes e iii) restante código. Estes valores foram
calculados directamente da análise do código, indicando o número de instruções (e tempo
de execução) de cada iteração. Nas colunas marcadas a cinzento são apresentados os
valores correspondentes à versão optimizada. A coluna Execuções indica o número de
vezes que esse código é executado:
•
iter – número total de iterações do solver
•
linhas – número de linhas da matriz
•
elem – número de elementos não nulos existentes na matriz
Execuções
Instruções
iter*linhas
37
Paralelismo
Ciclos de
relógio
Penalidades
Solver
Ciclos
31
51
67
20
37
If (unroll)
0/iter
Outro cód.
iter
74
36
180
191
115
126
iter
39
36
25
24
0
1
For
iter*linhas
16
10
25%
60%
24
10
7
3
While
iter*elem
7
13
31%
61%
12
10
4
1
26
50
70
Atimes
Control
Tab. 5.2 – Análise estática do solver
Estes valores foram obtidos através da contagem directa de instruções de cada bloco, tendo sido a usada a aplicação VTUNE para contabilizar os ciclos de relógio e as penalidades
de cada instrução. A contabilização das penalidades não é precisa, visto serem contabili83
Optimização e Avaliação de Aplicações de Simulação Numérica
zadas apenas as penalidades geradas numa execução sequencial do código. As penalidades que ocorrem devido a mudanças do fluxo de execução (ifs e ciclos) não foram contabilizadas. Devido às capacidade de predição dos saltos (ver secção 2.2.2.1) não é possível
saber antes da execução quantos ciclos de relógio serão perdidos.
No caso dos ciclos onde se aplicou/removeu o loop unrolling, a contagem presente na Tab.
5.2 representa o número de instruções e o custo do processamento de um elemento (ou
linha). Os cálculos executados em ambos os casos (existência ou não de loop unrolling)
mantêm-se constantes, sendo o custo de cada cálculo obtido directamente ou ponderado
pelo número de execuções agrupadas com o unrolling.
Com o loop unrolling (aplicado aos ciclos da função Solve) agruparam-se num mesmo
iteração vários cálculos idênticos e consegue-se reduzir o número de instruções por cada
elemento. Observou-se um aumento dos ciclos de relógio e de penalidades devido ao
facto de, num mesmo bloco e na mesma iteração do ciclo, ocorrerem duas penalidades
que agora são contabilizadas na avaliação estática.
Já no caso da função atimes, observa-se uma redução de todos os valores. Embora o número de penalidades seja inferior na versão optimizada, a relação deste valor entre ambas
as versões não é a que se apresenta (1 para 4 e 3 para 7). É expectável que na versão optimizada o número de penalidades reais seja superior, visto haver dependências entre as
várias iterações dos ciclos, mas nunca duplicando de valor. O encadeamento das instruções da função atimes, não só levou à redução das penalidades, como também melhorou
o paralelismo da execução das instruções: consegui-se aumentar o número de instruções
que iniciam simultaneamente a sua execução (de 25% para 60%, por exemplo na função
atimes). Com a nova distribuição das instruções, é possível ao processador executar mais
instruções em paralelo.
Número total de acessos à memória
Os valores apresentados na próxima tabela representam o número de acessos à memória
realizados durante a execução da função Solve. Estes resultados foram obtidos usando o
driver descrito na secção 4.5.1. Durante a execução da função foi lido o contador 0x43 que
representa o número total de acessos à memória realizados. São contabilizados todos os
acessos à memória quer resultem num cache hit (L1 ou L2) ou numa transferência da memória para processador. Os valores apresentados maximizam o número real de acessos,
visto este contador contabilizar todos os acessos realizados no computador e não só os
acessos da aplicação testada.
84
Avaliação
Acessos à memória (total)
Execuções
Não optimizado
Optimizado
Redução
1
222 566 499
165 559 709
25.6%
Inicialização
1
1 059 918
858 790
19.0%
ciclo while
1
221 506 581
164 700 919
25.6%
Atimes
175
155 254 352
96 499 324
37.8%
Outro Cód.
175
66 252 229
68 201 595
-2.9%
Solve
Tab. 5.3 – Número total de acessos à memória numa execução típica do solver
Observa-se que a grande redução do número de acessos à memória se verifica na função
atimes. Em todo o outro código, onde se aplicou maioritariamente o loop unrolling, o número de acessos manteve-se aproximadamente constante.
A redução do número de acessos na função atimes advém da substituição das instruções
*bi+=*sak++ *x[*ijai++] por daux2= sa[kaux]*x[ij_aux];daux += daux2,
com a actualização de *bi no fim (b[i] = daux), tal como foi descrito na Fig. 4.3. Com
este código é possível aos compilador optimizar o código de modo a utilizar mais eficientemente os registos.
Misses à Cache de dados
Apresenta-se aqui o número de misses à cache de dados de nível 1. Também estes resultados foram obtidos usando o driver apresentado na secção 4.5.1. Os valores resultam da leitura do contador 0x45, número total de linhas lidas para a cache de dados resultantes de
misses.
Como se observa facilmente, foi a agregação de vários ciclos num só, realizada ao longo
do código da função solve que resultou em maiores reduções do número de misses da
cache. Reduziu-se em mais de 1/3 o número de misses, conseguindo-se deste modo a
redução do tempo de espera pelas leituras e escritas dos dados para a memória.
Também se observa que as alterações à função times, não resultaram em nenhum decréscimo no número de misses.
85
Optimização e Avaliação de Aplicações de Simulação Numérica
Cache Misses (total)
Execuções
Solve
Não optimizado
Optimizado
Redução
1
9 173 579
8 159 458
11.0%
Inicialização
1
42 804
36 889
13.8%
Ciclo while
1
9 130 775
8 122 569
11.0%
Atimes
175
5 455 105
5 704 616
-4.5%
Outro Cód.
175
3 675 670
2 417 953
34.2%
Tab. 5.4 – Número total de cache misses no acesso à memória numa execução
típica do solver
Tempos de execução
Podemos agora apresentar os tempos de execução do código optimizado, observando e
relacionando os vários valores atrás descritos.
Da observação dos dados anteriormente apresentados podem-se observar dois efeitos da
alteração do código: redução do número de acessos à memória e redução do número de
misses, que podemos agora comparar com os tempos de execução dos trechos de código
correspondentes (Tab. 5.5).
Tempos de execução (segundos)
Execuções
Solve
Não optimizado
Optimizado
Speedup
1
2.713 283
2.178 327
1.25
Inicialização
1
0.013 989
0.012 315
1.14
ciclo while
1
2.699 294
2.166 012
1.25
Atimes
175
2.032 845
1.592 426
1.28
Outro Cód.
175
0.666 449
0.573 586
1.16
Tab. 5.5 – Tempos de execução da versões serial do solver numa execução
típica do solver
As alterações à função atimes resultaram numa redução do número de acessos à memó86
Avaliação
ria, mas com um número de misses constante . Desta observação pode-se concluir somente
que a redução do tempo de execução não advêm dos acessos à memória, visto o acesso a
*bi (ver linhas 8 a 15 da Fig. 4.2) resultarem maioritariamente em cache hits.
Se observarmos com atenção a análise estática desta função (Tab. 5.2), conclui-se que o código desta função já executa com maior rapidez. Esta rapidez é causada pela intercalação
de instruções que possibilita o uso do paralelismo do processador. Também o uso de instruções que manipulam apenas registos, torna a descodificação e execução do código mais
eficiente.
No resto do código, onde se aplicou loop unrolling, observam-se também ganhos no tempo
de execução. Nestes casos o número de acessos à memória são constantes mas o número
cache hits aumentou na versão optimizada, como se pode observar nas Tab. 5.3 e Tab. 5.4.
Estes ganhos são directamente resultantes da redução de misses e consequente maior
rapidez nos acessos aos dados.
5.3 Paralelização do Solver (conjugate gradient)
Na secção 4.2 descreveram-se as paralelizações realizadas ao Solver (threads e Memória
Partilhada e Distribuída). Para testar estas versões paralelas usou-se o computador multiprocessador descrito na Tab. 5.1, para a versão com threads, e dois computadores
Pentium II, também apresentados na Tab. 5.1, ligados por uma rede ethernet a 100Mbit/s.
No caso da paralelização, usando-se threads e memória partilhada num computador
multiprocessador, o speedup expectável quando se usam dois processadores está próximo
de 2. Como se observa na Tab. 5.6.a, tal não acontece, embora se obtenham alguns ganhos
com a paralelização. Esta diferença advém de vários factores, tais como o uso de uma
instrução de sincronização complexa, a existência de código executado num só
processador e a possível distribuição não uniforme dos dados.
Processadores
Tempo (s)
Speedup
Processadores
Tempo (s)
Speedup
1
3.97
—
1
2.18
—
2
2.74
1.44
2
71.43
0.03
a)
b)
Tab. 5.6 – Resultados da paralelização do solver usando a) threads e b) TreadMarks
A instrução de sincronização usada, a barreira, não existe nas bibliotecas de threads, tendo
87
Optimização e Avaliação de Aplicações de Simulação Numérica
sido necessária a sua implementação. Como a matriz é esparsa, não é garantido que todas
as linhas tenham exactamente o mesmo número de elementos. Este facto leva a que duma
divisão equitativa do número de linhas não se obtenha uma distribuição do esforço igual
entre tarefas.
Finalmente, para justificar o speedup obtido, podemos observar que, por exemplo, o cálculo final dum produto interno (ver Fig. 4.5) é executado por todas as tarefas. Este facto leva
a que haja código que não é executado em paralelo, que não aproveita a existência de vários processadores e que reduz o speedup obtido.
Os resultados da paralelização usando TreadMarks não são os desejados (ver Tab. 5.6.b).
O código paralelizado não se executa mais rapidamente que o código série. A grande causa é o custo da comunicação e transferência de dados. A sincronização entre as várias tarefas obriga à comunicação entre elas que, quando executada sobre uma rede local, é muito
mais lenta do que usando memória partilhada. A comunicação de dados provocada, por
exemplo, pelos produtos internos (Fig. 4.5) e pela multiplicação de matrizes (Fig. 4.7) é outra causa para o mau desempenho desta versão. Na versão com memória partilhada ao
acesso a dados manipulados por outras tarefas não incorrem custos. Já com necessidade
de transmitir os dados entre computadores, este tipo de acessos é prejudicial ao desempenho.
5.4 Optimização do simulador (aplicação FLASH)
A optimização realizada ao simulador, e cujos resultados aqui apresentamos, consistiu
apenas na alteração do algoritmo de obtenção dos dados necessários à construção das matrizes esparsas, descrita na secção 1.
São apresentados na tabela Tab. 5.7 os tempos medido na execução da aplicação de
simulação sobre um modelo uma embarcação do tipo Series 60[Ste96], representada por
15000 nós e 85716 elementos. Esta simulação executa-se durante 10000 iterações, igual ao
número de matrizes esparsas construídas. Esta quantidade de nós e elementos e a duração
da simulação são representativos das simulações usualmente realizadas.
As alterações ao código realizadas trouxeram ganhos locais bastante elevados, a construção de uma matriz demorava originalmente 5 segundos, passando a ser executada em
cerca de 0.1 segundos. O speedup local obtido é de 55.6, sendo o speedup global de 12.2.
Este valor, embora inferior a 55.6, é significativo e bastante bom.
Na versão final da aplicação de simulação o código por nós proposto para a construção
das matrizes foi substituído pelo parceiro responsável, mas a ideia da eliminação das ins88
Avaliação
truções redundantes manteve-se e que. sem a optimização inicialmente proposta, a versão
final executaria muita mais ineficientemente.
Tempos de execução (segundos)
Não optimizado
Optimizado
Speedup
Total
58140
4764
12.2
Construção da matriz
54350
974
55.8
Outro Código
3790
3790
1
Tab. 5.7 – Tempos de execução da aplicação de simulação
5.5 Paralelização do simulador (aplicação FLASH)
Efectuaram-se duas tentativas de paralelização do simulador usando TreadMarks, tal
como descrito na secção 4.4. Numa das tentativas não se obtiveram resultados positivos.
A sincronização e comunicação de dados entre computadores aumentou substancialmente o tempo de execução da versão paralela.
Apresentam-se de seguida os resultados da segunda aproximação, comentando-os e comparando-os com os valores obtidos com a versão que usa PVM.
Os resultados seguintes foram obtidos executando a simulação do modelo de uma embarcação do tipo Series 60[Ste96], representado por 16000 elementos. O fluido circundante é
representado por 57000 elementos, sendo necessário um total de 15000 nós. O ambiente de
execução é composto por computadores Pentium II, tal como descrito na Tab. 5.1, ligados
por uma rede ethernet a 100Mbit/s.
Tempos de execução
Na Fig. 5.1 é apresentado um gráfico com a progressão do tempo de execução do simulador, em função do número de computadores usados nos cálculos. São distinguidos os vários tipos de código existentes:
•
Código não paralelizado
•
Código paralelizado
•
Comunicação
89
Optimização e Avaliação de Aplicações de Simulação Numérica
Comunicação
50
00
Paralelizado
00
30
0
10
0
0
20
0
0
Tempo (s)
40
00
Não Paralelizado
1
2
3
4
Processadores
Fig. 5.1 – Tempos de execução da versão paralela usando TreadMarks
A soma do tempo de execução do código paralelizado e da comunicação decresce com
dois e três processadores, aumentando quando se passa a usar um quarto computador.
Este facto deve-se à redução do tempo obtido com a paralelização não ser suficiente para
compensar o aumento de comunicação, quando já se tem quatro computadores.
Devido ao modo como os sistemas de DSM decidem quando os dados são transmitidos
entre os vários computadores (ver 2.3.2.3 – Distributed Shared Memory) os tempos apresentados no gráfico anterior para a comunicação estão aquém dos reais. Como parte da comunicação se realiza quando se acede aos dados partilhados, há casos em que é durante a
actualização dos dados que é realizada a comunicação, sendo esse tempo contabilizado no
código paralelizado.
Como é obvio, o tempo e execução do código não paralelizado mantêm-se constante ao
longo das medições, o que nos permite calcular com alguma precisão o speedup máximo
esperado.
Na Tab. 5.8 são apresentados os speedups esperados (speedup Ideal Corrigido) para uma
paralelização o em que, tal como o nosso simulador, cerca de 77% do código total foi
paralelizado. O Speedup Ideal Corrigido foi calculado pela expressão apresentada na secção 2.4:
speedup =
90
t_serie + t_para
t para
t_serie +
n
Avaliação
Processadores
1
2
3
4
Ideal
1
2
3
4
Ideal Corrigido
1
1.63
2.07
2.38
Real
1
1.36
1.72
1.68
Tab. 5.8 – Speedups expectáveis e obtidos com a versão paralela usando TreadMarks
Observa-se que, embora distante do Speedup Ideal, os ganhos aproximam-se daqueles esperados, tendo em consideração o facto de não se paralelizar todo o código. Também aqui
se observa que a comunicação tem um peso importante no tempo despendido, aumentando com o número de computadores participantes.
Comparação com versão PVM
Como a versão paralela final evoluiu directamente da versão que usa PVM, é interessante
efectuar uma comparação entre ambas e avaliar os ganhos que advêm do uso de DSM.
Na tabela seguinte apresentam-se os tempos de execução das versões paralelas, a original
usando PVM e a final com TreadMarks.
Tempos de execução
Speedup
(segundos)
Processadores
PVM
1
DSM
4764
PVM
DSM
1
1
2
3655
3501
1.30
1.36
3
4126
2756
1.15
1.72
4
—
2821
—
1.68
Tab. 5.9 – Comparação dos tempos de execução das versões paralelas
usando PVM e TreadMarks (DSM)
Observa-se que, na versão original, a partir de três computadores já não havia ganhos no
tempo de execução, e que esse limite passou, com o uso do TreadMarks, para quatro
máquinas.
91
Optimização e Avaliação de Aplicações de Simulação Numérica
Também em termos de desempenho total se observam benefícios na nova versão. Enquanto que com o uso de PVM apenas se obtinha um speedup de 1.30, com o uso do
TreadMarks passou-se a obter 1.72, usando três computadores nos cálculos. O gráfico
apresentado na Fig. 5.2 ajudar-nos-á a perceber a razão da diferença entre versões.
10
00
80
0
0
20
0
40
0
60
0
Mbyte
12
00
14
00
16
00
PVM
ThreadMarks
2
3
4
Processadores
Fig. 5.2 – Dados transmitidos e enviados pelo nó mestre nas versões paralelas usando
PVM e TreadMarks
Observando o gráfico da Fig. 5.2, podemos descobrir as causas da grande discrepância entre os tempos de execução das duas versões. Neste gráfico são apresentados as quantidades de dados transmitidos durante a execução. Estes valores foram obtidos usando os
contadores do sistema operativo que representam os dados transmitidos e recebidos
usando o protocolo TCP/IP.
Observa-se perfeitamente que a solução implementada usando TreadMarks usa mais eficientemente a rede, conseguindo reduzir os dados transmitidos entre computadores.
Esta grande diferença na quantidade de dados transmitidos advêm do facto de, na versão
original e em cada iteração, serem sempre transmitidos os mesmo dados para todos os
nós, independentemente de serem ou não relevantes para os cálculos realizados localmente. Com o uso de memória partilhada e distribuída, a comunicação dos dados só é realizada quando os vectores partilhados são realmente acedidos e estes foram alterados. Consegue-se assim, de modo transparente para o programador, a redução da comunicação, embora com custo adicional ao nível do processamento, devido à necessidade de verificar os
acessos e alterações dos dados.
92
6 Conclusões
Podemos começar por apresentar um resumo dos ganhos de desempenhos que obtivemos. Na optimização do solver, constituído por código C++ mas sem instruções de
manipulação de estruturas dinâmicas, os ganhos obtidos foram substanciais. O speedup
obtido foi de cerca de 1.25. As optimizações aplicadas a este código foram todas
dependentes do processador usado: optimização dos acessos à cache, uso dos registos para
manipulação de variáveis e melhoria do encadeamento das instruções. Tendo tentado
aplicar este mesmo tipo de optimizações ao código do simulador (código C++ com
manipulação intensiva de estruturas dinâmicas) não se obtiveram resultados que
justificassem esse esforço. As instruções aritméticas e optimizáveis estão dispersas pelo
código e grande parte do tempo de execução é perdido com a manipulação das listas
dinâmicas de suporte aos dados.
Embora não se tenha conseguido aplicar optimizações dependentes do processador, o
código do simulador sofreu alterações que influenciaram profundamente os tempos de
execução. O modo de construção das matrizes esparsas original era, embora correcto e
facilmente compreensível, muito ineficiente. O número de operações realizadas era O(n2),
tendo sido reduzido para O(n). Enquanto que na versão original este código dominava
completamente o tempo de execução, na versão final é desprezável.
Também se avaliaram várias possibilidades de execução num ambiente paralelo. A versão
do solver foi paralelizada e executada num multiprocessador de memória partilhada e
num cluster de computadores. Na primeira instalação os ganhos foram próximos dos
93
Optimização e Avaliação de Aplicações de Simulação Numérica
óptimos, enquanto que com os vários computadores ligados por uma rede ethernet os
tempos de execução aumentaram drasticamente.
A versão paralela original do simulador executava sobre PVM, mas a partir de 3
computadores já não se obtinha ganhos. Os tempos de transmissão dos dados superava os
ganhos obtidos com a execução paralela de código. Com o uso de uma tecnologia de
comunicação diferente (DSM) conseguimos reduzir os dados transmitidos, aumentando o
número máximo de máquinas utilizáveis e os ganhos totais.
Perante estes resultados a primeira conclusão a tirar é que, se o desempenho é um dos factores principais, não se pode partir do princípio que o código desenvolvido originalmente
é óptimo, nem que os algoritmos ou soluções apresentadas em livros de texto não são
optimizáveis. Observou-se isso no código do Conjugate Gradient e na solução para construção das matrizes esparsas. O código usado era correcto, mas oferecia possibilidades de
ser optimizado.
Outra conclusão que se tira é, mesmo após efectuada a paralelização do código, ser
necessária a
investigação de possibilidade de redução do tempo de execução. Se a
transmissão de dados for ineficiente, é necessário alterá-la, introduzindo código de
selecção dos dados as transmitir. Com o uso de DSM, essa selecção realiza-se
automaticamente. Sem alteração completa da estrutura do simulador, esta solução foi a
melhor que se tentou aplicar. Certo é, que há sempre a possibilidade de alterar a partição
e partilha dos dados, mas tal tarefa deve ser realizada pelos especialistas no domínio da
aplicação.
Como resultados palpáveis do trabalho realizado temos, obviamente, a aplicação de
simulação, cuja versão final e optimizada oferece um desempenho e rapidez muito
superior ao da versão original. Paralelamente desenvolveram-se ferramentas necessárias à
avaliação do desempenho da aplicação, tendo-se implementado duas bibliotecas para
leitura dos contadores de processador e sistema operativo. Também se desenvolveu um
servidor para lançamento de processos em computadores remotos.
A descrição da optimização da versão paralela encontra-se descrita num artigo apresentado numa conferência internacional.
Este documento, como súmula das várias técnicas de optimização aplicáveis a problemas
reais, também pode ser considerado como um resultado válido. Este documento tem a
mais valia de, não só apresentar as técnicas de avaliação e optimização, como também os
resultados obtidos da sua aplicação e expectáveis em aplicações semelhantes.
94
Conclusões
O grande ensinamento que se pode obter destes trabalho é que há uma grande necessidade dos especialista nos domínios das simulações terem algum conhecimento de técnicas
de optimizações e das arquitecturas de computadores e processadores onde se irá executar o código. Observou-se neste projecto, que o código desenvolvido resolvia os problemas, mas as soluções inicialmente adoptadas poderiam ser melhores. Por exemplo, numa
aplicação onde o desempenho era fundamental, o uso de estruturas de dados dinâmicas,
mostrou-se pouco acertada.
Ao apontarmos esta necessidade de formação na área de arquitecturas e optimização,
pretendemos facilitar o futura desenvolvimento de código eficiente. Os autores do código,
devem passar a ser capazes de avaliar as várias decisões tomadas. Mesmos que não conseguiam efectuar a optimização de código já existente, já há a capacidade de identificar código problemático e as soluções adoptadas menos boas e com necessidade de melhoria.
Um dos modos de melhorar a aplicação de simulação seria alterar o modo de armazenamento dos dados. Eliminado-se as estruturas de dados dinâmicas possibilitar-se-ía a aplicação de optimizações relacionadas com a arquitectura do computador (encadeamento de
intrusões e uso da cache).
95
Apêndice A – Matrizes esparsas
De modo a optimizar o espaço ocupado por matrizes com predominância de elementos
nulos, usam-se matrizes esparsas.
Este tipo de representações necessita de armazenar um dos índices da matriz num vector
distinto dos valores, visto estes não serem contíguos. Neste projecto usaram-se matrizes
esparsas com indexação das colunas, tal como se apresenta na Fig. 6.1.
3
0
1
0
0
0
4
0
0
0
0
7
5
9
0
0
0
0
0
2
0
0
0
6
5
ija[k]
7
8
8
10 11 12
3
2
4
5
4
sa[k]
3
4
5
0
1
7
9
2
6
índice k
1
2
3
4
7
8
9
10
11
a)
5
5
6
b)
Fig. 6.1 – Representação esparsa de uma matriz.
Para uma matriz com NxN elementos, esta representação tem as seguintes características:
•
As primeiras N posições do vector sa armazenam a diagonal da matriz (elementos
nulos também são representados) ;
•
As primeiras N posições do vector ija armazenam o índice de início da linha
correspondente (se alinha não tiver elementos não diagonais, o elemento seguinte
tem o mesmo valor) ;
•
A posição 1 de ija armazena o valor N+2;
•
A posição N+1 do vector ija é obtido somando 1 ao índice de sa do último
elemento armazenado;
•
Os elemento de sa com índice superior a N+2 armazenam o elemento não
97
Optimização e Avaliação de Aplicações de Simulação Numérica
diagonais da matriz, ordenado por linha e, para a mesma linha, ordenados por
coluna;
•
Os elemento de ija com índice superior a N+2 guardam a coluna do elementos
correspondentes de sa.
Com este tipo de representação não só se reduz a utilização de memória para armazenar
os dadas com também se conseguem obter implementações eficientes das operações sobre
matrizes usuais. Apresenta-se de seguida o algoritmo para conversão de uma matriz quadrada N*N para matriz esparsa.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sprsin(float **a, int n, unsigned long nmax,
float sa[],unsigned long ija[]){
int i,j;
unsigned long k;
for (j=1;j<=n;j++)
sa[j]=a[j][j]; /* elementos diagonais */
ija[1]=n+2;
k=n+1;
for (i=1;i<=n;i++) { /* linhas */
for (j=1;j<=n;j++) { /* colunas */
if (a[i][j] != 0){
sa[k]=a[i][j];
ija[k]=j;
}
}
ija[i+1]=k+1; /* índice da proxima linhas */
}
}
Observa-se facilmente que o número de instruções desta função é da mesma ordem das
instruções da cópia de uma matriz não esparsa. Observações semelhantes se podem realizar para outras operações, tais como a multiplicação de matrizes por vectores.
98
Apêndice B – Conjugate Gradient
Apresenta-se aqui a implementação do método iterativo de gradientes conjugados usado
no projecto FLASH. Este código resolve um sistema de equações A.x = b, estando os
coeficientes das equações armazenados numa matriz esparsa (ija e sa) e representando
b os resultados conhecidos das equações.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void Conj_Grad::Solve()
{
register int i,j;
Real ak,akden,bk,bkden,bknum,bnrm,zm1nrm,znrm;
Real err;
int iter=0;
Real *r,*z;
p
r
z
p
=
=
=
=
new
new
new
new
Real[nrows+1];
Real[nrows+1];
Real[nrows+1];
Real[nrows+1];
atimes(first_r, last_r,x,r,0);
//r = A * x
for (j=first_r;j<=last_r;j++) {
//r = b - A * x
r[j]=rhs[j]-r[j];
}
asolve(first_r, last_r, rhs, z, 1); //z = diag(A)-1 * b
bnrm=snrm(first_r, last_r, z);
//bnrm = |z|
while (iter <= itmax) {
++(iter);
zm1nrm=znrm;
for (bknum=0.0,j=first_r;j<=last_r;j++)
bknum += r[j]*r[j];
//bk = r * r
if (iter == 1){
for (j=first_r;j<=last_r;j++){
99
Optimização e Avaliação de Aplicações de Simulação Numérica
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
p[j]=r[j];
}
}else{
bk=bknum/bkden;
for (j=first_r;j<=last_r;j++){
p[j]=bk*p[j]+r[j];
}
}
bkden=bknum;
atimes(first_r, last_r,p,z,0);
//z = A * p
for (akden=0.0,j=first_r;j<=last_r;j++)
akden += z[j]*p[j];
ak=bknum/akden;
//ak = r*z/pp*A*p
for (j=first_r;j<=last_r;j++) {
x[j] += ak*p[j];
r[j] -= ak*z[j];
}
//x = x + ak*p
//r = r + ak*z
znrm=1.0;
err=snrm(first_r, last_r, r);
err = err/bnrm;
if (err <= Tolerance)
break;
//err = |r|/bnrm
}
delete [] p;
delete [] r;
delete [] z;
}
A função asolve, divide os elementos de b pelos valores correspondentes na diagonal da
matriz A e armazena o resultado no vector x. A matriz A está armazenada nos vectores
ija e sa, encontrando-se os N valores diagonais de A nos N primeiros elementos de sa.
1
2
3
4
5
6
7
8
9
10
void Conj_Grad::asolve(int first, int last, Real b[],
Real x[], int itrnsp){
register int i;
if (itrnsp)
for(i=first;i<=last;i++)
x[i]=b[i];
else
for(i=first;i<=last;i++)
x[i]=(sa[i] != 0.0 ? b[i]/sa[i] :b[i]);
}
Para efectuar a multiplicação entre a matriz A e um vector, usa–se a função atimes, que
no nosso caso apenas invoca a função dsprsax (r = A*x).
100
Apêndice B – – Conjugate Gradient
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Conj_Grad::atimes(int first, int last, Real x[],
Real r[], int itrnsp){
dsprsax(x,r,first, last);
}
void Conj_Grad::dsprsax(Real x[], Real b[], int first,
int last){
register int i;
for (i=first;i<=last;i++) {
b[i]=sa[i]*x[i];
int* ijai = &(ija[ija[i]]);
Real* bi = &(b[i]);
Real* sak = &(sa[ija[i]]);
int* up
= ijai + ((ija[i+1]-ija[i]) & ~07);
while (ijai < up){
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
*bi += *sak++ * x[*ijai++];
}
up = &(ija[ija[i]]) + (ija[i+1]-ija[i]);
while (ijai < up)
*bi += *sak++ * x[*ijai++];
}
}
A função snrm calcula o módulo de um vector.
1
2
3
4
5
6
7
8
9
Real Conj_Grad::snrm(int first, int last, Real sx[])
{
register int i;
Real ans = 0.0;
for (i=first;i<=last;i++)
ans += sx[i]*sx[i];
return sqrt(ans);
}
101
Bibliografia
[Adv90] S. Adve, M. Hill. Weak Ordering - A New Definition. Proceedings of the 17th
Annual International Symposium on Computer Architecture, p. 2—14. 1990
[Alm94] G. Almasi, A. Gottlieb. Highly Parallel Computing. The Benjamim/Cummings
Publishing Company, Inc., 1994.
[Amd67] G. M. Amdahl. Validity of the single-processor approach to achieving large scale
computing capabilities. AFIPS Conference Proceedings vol. 30, p. 483—485.
AFIPS Press, 1967.
[Bro97] E. D. Brooks III and K. H. Warren. A Study of Performance on SMP and
Distributed Memory Architectures Using A Shared Memory Programming Model.
Proceedings of SuperComputing97. 1997.
[Cha97] J. R. Chacón, E. Oñate. Questionaire on FSHD Specifications. Documento Interno Projecto FLASH WOR-10-01. 1997.
[CIM02] CIMNE – International Center for Numerical Methods in Engineering.
Gid - The personnal pre and post processor. http://gid.cimne.upc.es/. 2002.
[Dol96] Dolphin Interconnect Solutions AS. The Dolphin SCI Interconnect White Paper.
Dolphin Interconnect Solutions AS, 1996
[Dow98] K. Dowd, C. Severance. High Performance Computing, 2nd ed.: RISC Architectures, Optimization, & Benchmarks. O'Reilly & Associates, Inc, 1998.
[Fly72] M. Flynn. Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, vol. 21(9), p. 948—960. 1972.
[Gei94] A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam. PVM:
Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. Scientific and Engineering Computation. MIT Press, 1994.
103
Optimização e Avaliação de Aplicações de Simulação Numérica
[Gha90] K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, J. Hennessy.
Memory Consistency and Event Ordering in Scalable Shared-Memory
Multiprocessors. Proceedings of the 17th Annual International Symposium on
Computer Architecture, p. 15—26. 1990
[Gra82] S. L. Graham, P. B. Kessler, M. K. McKusick. gprof: a call graph execution profiler. Proceedings of the SIGPlan '82 Symposium on Compiler Construction,
p. 120—126. 1982.
[Gropp] W. Gropp. Tutorial on MPI: The Message-Passing Interface. Mathematics and
Computer Science Division, Argonne National Laboratory.
[Haw98] K. Hawick, J. Dongarra, G. Fox, S. Elmohamed. Survey of High Performance
Computing Systems. National HPCC Software Exchange, 1998.
[Hig97] High Performance Fortran Forum. High Performance Fortran language specification, version 2.0. Center for Research on Parallel Computation, Rice University,
Houston, 1997.
[Hoc81] R. W. Hockney, C. R. Jesshope. Parallel Computers. Admam Hilget Ltd., 1981.
[Hof00] C. Hofmeister, R. Nord, D. Soni. Applied Software Architecture.
Addisson-Wesley, 2000.
[Int01a] Intel Corporation. The IA-32 Intel Architecture Software Developer's Manual
(Volume 1: Basic Architecture). Intel Corporation, 2001.
[Int01b] Intel Corporation. The IA-32 Intel Architecture Software Developer's Manual
(Volume 2: Instruction Set Reference). Intel Corporation, 2001.
[Int01c] Intel Corporation. The IA-32 Intel Architecture Software Developer's Manual
(Volume 3: System Programming Guide). Intel Corporation, 2001.
[Int02] Intel Corporation. Overview of the Intel® VTune™ Performance Analyzer5.0.
http://developer.intel.com/software/products/vtune/vtune_oview.htm.
2002
[Int97] Intel Corporation. Intel Architecture Optimization Manual. Intel Corporation,
1997
[Int98] Intel Corporation. P6 Family of Processors – Hardware Developer’s Manual.
Intel Corporation, 1998
104
Bibliografia
[Int99] Intel Corporation. Intel Architecture Optimization – Reference Manual. Intel Corporation, 1999.
[Kar98] G. Karypis, V. Kumar. METIS, a software package for partitioning unstructured
graphs, partitioning meshes, and computing fill-reducing orderings of sparce matrices. version 4.0. Technical report, Department of Computer Science, University
of Minnesota / Army HPC Research Center, Minneapolis, 1998.
[Kel92] P. Keleher, A. L. Cox, S. Dwarkadas, e W. Zwaenepoel. Lazy Release
Consistency for Software Distributed Shared Memory. Proceedings of the Nineteenth
International Symposium on Computer Architecture, p. 13-21. Maio 1992.
[Kel94] P. Keleher, A. L. Cox, S. Dwarkadas, e W. Zwaenepoel. TreadMarks: Distributed shared memory on standard workstations and operating system. Proceedings of
the Winter 1994 USENIX Conference, p. 115—132. USENIX, 1994.
[Lam79] L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, vol. 28(9)m p. 690—691.
Setembro 1979.
[Lau97] J. Laudon, D. Lenoski. The SGI Origin: a ccNUMA highly scalable server.
Proceedings of the 24th international symposium on Computer architecture.
1997.
[Meu01] H. W. Meuer, E. Strohmaier, J. J. Dongarra, H. D. Simon. Top 500 supercomputer sites – 18th edition. Novembro 2001.
[MsSDKa] Microsoft Corporation. Microsoft Platform SDK, Timers. Microsoft Corporation, 2000.
[MsSDKb] Microsoft Corporation. Microsoft Platform SDK, Performance Monitoring. Microsoft Corporation, 2000.
[MsSDKc] Microsoft Corporation. Microsoft Platform SDK, Processes and Threads. Microsoft Corporation, 2000.
[MsWRK] Microsoft Corporation. Windows 2000 Professional Resource Kit, Overview of Performance Monitoring. Microsoft Corporation, 2000.
[POSIX] Institute of Electrical and Electronics Engineers, Inc., The Open Group.
The Open Group Base Specifications Issue 6/IEEE Std 1003.1-2001. 2001
105
Optimização e Avaliação de Aplicações de Simulação Numérica
[Pow91] M. L. Powell, S. R. Kleiman, S. Barton, D. Shah, D. Stein, M. Weeks. SunOS 5.0
multithread architecture. White paper, SunSoft, 1991.
[Pre92] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical Recipes in C, 2nd. edition. Cambridge University Press, 1992.
[Rom97] T. Romer, G. Voelker, D. Lee, A. Wolman, W. Wong, H. Levy, B. Bershad,
J. Chen. Instrumentation and optimization of Win32/Intel executables using etch.
The USENIX Windows NT Workshop 1997, p. 1—7. USENIX, 1994.
[Sil00] J. Silva, P. Guedes. Ship Hull Hydrodynamic Analysis Using Distributed Shared
Memory. Applied Parallel Computing – New Paradigms for HPC in Industry
and Academia – 5th International Workshop, PARA 2000 Proceedings.
Springer-Verlag, 2001.
[Sni96] M. Snir, S. W. Otto, S. Huss-Lederman, D. W. Walker, J. Dongarra. MPI: the
complete reference. MIT Press, 1996.
[Ste96] F. Stern, J. Longo, Z. J. Zhang, A. Subramani. Detailed bow-flow data and cfd for
a series 60 cb=0.6 ship model for froude number 0.316. Journal of Ship Research.
1996.
[Sun01] Sun Microsystems, Inc., The Sun FireTM 15K Server for High Performance and
Technical Markets. White paper, Sun Microsystems, Inc., 2001.
[Sun90] V. S. Sunderam. PVM: A framework for parallel distributed computing.
Concurrency: practice and experience, vol. 2(4), p. 315—339. 1990.
[Vit98] VITA Standards Organization. Myrinet-on-VME Protocol Specification Draft
Standard – VITA 26-199x Draft 1.1. 1998.
[Woo99] M. Woolfson, G. Pert. An Introduction to Computer Simulation. Oxford
University Press, 1999.
[Zag96] M. Zagha, B. Larson, S. Turner, M. Itzkowitz. Performance analysis using the
MIPS R10000 performance counters. Supercomputing '96 Conference Proceedings. ACM Press e IEEE Computer Society Press, 1996.
106
Glossário
Micro-instrução Operação elementar executada pelo processador. Existem algumas
instruções assembly que são traduzidas em mais que uma micro-instrução
ATM Asynchronous Transfer Mode. Tecnologia de ligação de computadores
suportada pela existência de um comutador de pacotes
CAD Computer-aided design. Sistema de desenho (engenharia naval, …)
assistido por computador
CFD Computational Fluid Dynamics. Ciência que estuda a solução das
equações que regem o comportamento do fluidos, usando sistemas
computacionais e simulação numérica.
Driver Programa que executa em modo núcleo e que permite a interacção
dos programas dos utilizadores com recursos protegidos.
DSM Distributed Shared Memory. Memória Partilhada e Distribuída
Ethernet rede local de alto débito (10 ou 100 Mbit/s)
Handle Valor único, gerido pelo sistema operativo e representativo de um
determinado recurso acedido pela aplicação
NUMA Non-Uniform Memory Access. Sistemas multiprocessadores em que o
custo de acesso aos dados é variável consoante estes se encontram
em memória local o remota.
Número de Froude Quantidade adimensional representativa, na arquitectura naval, da
relação entre a velocidade da embarcação e a velocidade da
107
Optimização e Avaliação de Aplicações de Simulação Numérica
2
v
superfície da onda. Calcula-se usando a formula F =
.
n gL
PVM Parallel Virtual Machine (ou Máquina Paralela Virtual)
Query Pergunta efectuada a uma base de dados cuja resposta é composta
por dados
RPC Remote Procedure Call. Método de invocação remota de funções
através de uma ligação de rede.
Time-sharing Política de gestão do processador por parte do sistema operativo,
em que é atribuído a cada processo um período de tempo de
execução.
Consegue-se
assim
processador para cada processo.
108
simular
a
existência
de
um