CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS
PROGRAMA DE PÓS-GRADUAÇÃO EM MODELAGEM MATEMÁTICA E
COMPUTACIONAL
Vitor Tavares Gontijo
Técnica de Engenharia de Software para
desenvolvimento de aplicativos paralelos e
distribuídos
Belo Horizonte
2013
Vitor Tavares Gontijo
Técnica de Engenharia de Software para
desenvolvimento de aplicativos paralelos e
distribuídos
Dissertação apresentada ao Curso de
Mestrado em Modelagem Matemática e
Computacional do Centro Federal de
Educação Tecnológica de Minas Gerais,
como requisito parcial à obtenção do título
de Mestre em Modelagem Matemática e
Computacional.
Orientador:
Prof. Dr. Gray Farias Moita
Belo Horizonte
CEFET/MG
2013
DEDICATÓRIA
Dedico este trabalho aos meus pais
pelo apoio aos estudos sempre e a
minha
esposa
pelo
amor
e
companheirismo.
AGRADECIMENTOS
Aos professores do Programa de Pós-graduação em Modelagem Computacional, em
especial aos que estiveram mais próximo neste projeto, Bruno Santos, Paulo
Almeida e Henrique Borges.
A todos os colegas de mestrado.
Aos colegas de trabalho do CEFET-MG.
Ao meu professor e orientador Gray Farias Moita.
À minha querida esposa que tanto me apoiou e tolerou momentos difíceis nesta
fase. “Se tudo passa, como se explica o amor que fica?” (Zeca Baleiro)
Aos meus pais que sempre me deram plenas condições e incentivo aos estudos.
Aos amigos e todos aqueles que contribuíram de alguma forma com este trabalho
meus sinceros agradecimentos.
“Alguns homens veem as coisas como são, e
dizem 'Por quê?' Eu sonho com as coisas que
nunca foram e digo 'Por que não ?'” (George
Bernard Shaw)
RESUMO
Recentemente, computação paralela e distribuída tem se mostrado tema
amplamente estudado. Também, arquiteturas de hardware de múltiplos núcleos
(multicore) já estão bem consolidadas e são largamente utilizadas em diferentes
campos de aplicações. No entanto, ainda não existe um consenso a respeito das
melhores práticas ou da maneira de utilização da Engenharia de Software no
desenvolvimento específico de softwares para tais arquiteturas e uma avaliação
cuidadosa do atual estado da arte no assunto pode ser uma interessante maneira de
seguir adiante neste campo de pesquisa. No presente trabalho de pesquisa, buscase promover a concepção de softwares eficientes para aproveitar ao máximo o
potencial do hardware multicore ou distribuído disponível usando para isto técnicas
de Engenharia de Software como ponto de partida. Existem várias soluções para
processamento de aplicações paralelas e distribuídas, porém, para obter uso
satisfatório do potencial oferecido por cada solução, o software deve ser concebido
em arquitetura paralela. Portanto, para se desenvolver softwares paralelos de alta
qualidade, que tornem a programação paralela mais compreensível e mais fácil de
desenvolver e manter, são necessárias pesquisas em análise e projeto de software
paralelo. Este trabalho propõe técnicas específicas de Engenharia de Software a
serem utilizadas no desenvolvimento de aplicações para computadores multicores e
de processamento distribuído, e, em especial, para softwares científicos, devido às
suas características intrínsecas, como, por exemplo, a habitual necessidade de alto
desempenho computacional e a frequente inexperiência com programação dos
desenvolvedores dos projetos. Nesta pesquisa são aplicadas as técnicas propostas
em diferentes arquiteturas paralelas como Multicores, Clouds, Grids e Clusters, e
uma abordagem otimizada, controlada e sistemática da Engenharia de Software
para aplicativos paralelos e distribuídos é investigada. No final, uma nova técnica
para desenvolvimento deste tipo de software é proposta.
PALAVRAS-CHAVE: Computação Paralela e Distribuída, Engenharia de Software,
Arquitetura Multicore, Software Científico, Computação de Alto Desempenho.
ABSTRACT
Parallel and distributed computing has been a topic largely studied in the last few
years. Also, multicore architectures can be easily found and are widely used in
different fields of application. However, best practices and the “correct” use of
software engineering to develop such applications are not yet common place and a
careful evaluation of the current state-of-the-art in the subject can be a useful way
forward. In the present work, the main idea is to conceive efficient software to make
the best of the multicore or distributed hardware available; software engineering
techniques can be a good starting point. There exist several solutions for parallel and
distributed processing applications, but to obtain satisfactory use of the potential
offered by each solution, the actual software must be parallel designed. Therefore, to
attain higher quality “products”, parallel software design patterns, that make the
parallel programming more understandable and easier to develop and maintain, are
necessary and should be considered. This work proposes specific techniques of
software engineering to be applied in the development of distributed and concurrent
computer processing, especially for scientific software, due to their inherent
characteristics and the usual need for higher performance in their applications. In this
study the techniques proposed are implemented in different parallel architectures
such as multicore, cloud computing, grid computing and cluster, and an optimized,
controlled and systematic approach is sought. At the end, a new model for
management of this kind of software is proposed.
Keywords: Parallel and Distributed Computing, Software Engineering, Multicore
Architecture, Scientific Software, High Performance Computing.
LISTA DE FIGURAS
Figura 1: Gráfico de desempenho com utilização de Multicores e Multiprocessadores. ...................... 12
Figura 2: Gráfico comparativo de desempenho e eficiência de CPU´s Multicores ............................... 14
Figura 3: Apresentação gráfica da organização da dissertação em capítulos. .................................... 16
Figura 4: Configurações de sistemas .................................................................................................... 24
Figura 5: Diferenças entre as configurações de Cluster e Grid. ........................................................... 28
Figura 6: Cloud Computing. .................................................................................................................. 29
Figura 7: Etapa de identificação do aplicativo. ...................................................................................... 43
Figura 8: Etapa de identificação do ambiente. ...................................................................................... 44
Figura 9: Definição do modelo de controle. .......................................................................................... 46
Figura 10: Níveis de granularidade. ...................................................................................................... 47
Figura 11: Métodos de comunicação. ................................................................................................... 49
Figura 12: Sincronia e plano de testes. ................................................................................................. 50
Figura 13: Visão geral da técnica proposta. .......................................................................................... 53
Figura 14: Estrutura do Grid JPPF ........................................................................................................ 62
Figura 15: Gráfico comparativo de performance – Arquitetura Multicore. ............................................ 78
Figura 16: Gráfico comparativo de Speed-up – Arquitetura Multicore. ................................................. 79
Figura 17: Gráfico comparativo de performance – Arquitetura Grid Computing. .................................. 81
Figura 18: Gráfico comparativo de Speed-up – Arquitetura Grid Computing. ...................................... 81
Figura 19: Gráfico comparativo de performance – Arquitetura Cluster................................................. 84
Figura 20: Gráfico comparativo de Speed-up – Arquitetura Cluster. .................................................... 84
Figura 21: Gráfico comparativo de variação de granularidade - Arquitetura Cloud Computing. .......... 86
Figura 22: Gráfico comparativo de performance – Arquitetura Cloud Computing. ............................... 87
Figura 23: Comparativo entre o tempo de execução em diferentes arquiteturas ................................. 88
LISTA DE TABELAS
Tabela 1: Comparativo entre interfaces de programação paralela ....................................................... 17
Tabela 2: Tempo de execução sem paralelismo – Arquitetura Multicore. ............................................. 77
Tabela 3: Tempo de execução com paralelismo sem técnica – Arquitetura Multicore. ......................... 77
Tabela 4: Tempo de execução com aplicação da técnica proposta – Arquitetura Multicore................. 78
Tabela 5: Comparativo de valores de tempo de execução – Arquitetura Multicore. ............................. 78
Tabela 6: Resultados da execução cálculo de PI em arquitetura Grid Computing. .............................. 80
Tabela 7: Comparativo de valores de tempo de execução – Arquitetura Grid Computing. .................. 80
Tabela 8: Comparativo de valores de tempo de execução detalhado – Arquitetura Cluster. ............... 82
Tabela 9: Comparativo de valores de tempo de execução – Arquitetura Cluster. ................................ 83
Tabela 10: Resultados da execução cálculo de PI em arquitetura Cloud Computing. ......................... 85
Tabela 11: Comparativo de valores de tempo de execução – Arquitetura Cloud Computing. .............. 85
SUMÁRIO
1 – INTRODUÇÃO ................................................................................................................................. 11
1.1 – Caracterização do Problema / Motivação ................................................................................. 11
1.2 – Objetivos: Geral e Específico ................................................................................................... 14
1.3 – Estrutura do trabalho ................................................................................................................ 15
2 – FUNDAMENTAÇÃO TEÓRICA ....................................................................................................... 17
2.1 – Programação paralela .............................................................................................................. 17
2.2 – Softwares científicos ................................................................................................................. 20
2.3 – Arquiteturas paralelas ............................................................................................................... 22
2.3.1 – Multicore ........................................................................................................................... 23
2.3.2 – Cluster .............................................................................................................................. 25
2.3.3 – Grid Computing ................................................................................................................ 27
2.3.4 – Cloud Computing ............................................................................................................. 29
2.4 – Visão geral da Engenharia de Software ................................................................................... 31
3 – PRINCIPAIS PROBLEMAS RELACIONADOS AO PARALELISMO .............................................. 34
3.1 – Levantamento bibliográfico ...................................................................................................... 34
3.1.1 – Bloqueios em Programas de memória compartilhada ..................................................... 36
3.1.2 – Escalonamento de tarefas ............................................................................................... 38
3.1.3 – Escalabilidade .................................................................................................................. 39
4 – TÉCNICA PROPOSTA .................................................................................................................... 41
4.1 – Considerações Iniciais.............................................................................................................. 41
4.2 – Proposta para uma Engenharia de Software paralelo ............................................................. 42
4.2.1 – Etapa de identificação ...................................................................................................... 42
4.2.2 – Etapa de definição ........................................................................................................... 46
4.2.3 – Documento de identificação de paralelismo .................................................................... 51
4.3 – Visão geral da técnica proposta ............................................................................................... 52
5 – DESENVOLVIMENTO ..................................................................................................................... 54
5.1 – Aplicação escolhida .................................................................................................................. 54
5.2 – Implementação ......................................................................................................................... 55
5.3 – Métricas de software ................................................................................................................ 56
5.4 – Implantação em Multicore ........................................................................................................ 57
5.4.1 - Documento de Identificação de Paralelismo .................................................................... 58
5.4.2 – Implementação................................................................................................................. 60
5.5 – Implantação em Grid Computing .............................................................................................. 61
5.5.1 – Grid Computing com JPPF Grid. ..................................................................................... 61
5.5.2 - Documento de Identificação de Paralelismo .................................................................... 62
5.5.3 – Implementação................................................................................................................. 65
5.6 – Implantação em Cluster............................................................................................................ 67
5.6.1 – Cluster com Rocks ........................................................................................................... 67
5.6.2 - Documento de Identificação de Paralelismo .................................................................... 68
5.6.3 – Implementação................................................................................................................. 70
5.7 – Implantação em Cloud Computing ........................................................................................... 73
5.7.1 - Cloud Computing com Jelastic.com ................................................................................. 73
5.7.2 - Documento de Identificação de Paralelismo .................................................................... 74
5.7.3 – Implementação................................................................................................................. 76
6 – RESULTADOS OBTIDOS ............................................................................................................... 77
6.1 – Multicore ................................................................................................................................... 77
6.2 – Grid Computing ........................................................................................................................ 79
6.3 – Cluster de Computadores......................................................................................................... 82
6.4 – Cloud Computing ...................................................................................................................... 85
6.5 – Observações gerais .................................................................................................................. 87
7 – CONCLUSÕES E CONSIDERAÇÕES FINAIS .............................................................................. 89
7.1 – Conclusões, limitações e contribuições ................................................................................... 89
7.2 - Trabalhos Futuros ..................................................................................................................... 91
8 – REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................................ 92
11
1 – INTRODUÇÃO
Atualmente, a tendência dos hardwares dos computadores serem mais
simples, com frequência de operação mais baixa e integração em um mesmo chip
de dois ou mais núcleos de processamento – arquiteturas conhecidas como de
múltiplos núcleos (multicore) – já está consolidada e é utilizada amplamente nos
mais diversos campos de aplicações (RIGO et al., 2007). Com isso, a computação
paralela e distribuída tem se mostrado tema amplamente estudado. Entretanto,
somente com estas arquiteturas, sem softwares eficientes e adequados, o potencial
de hardware disponível poderá ser subutilizado. Assim, é real a necessidade de
adequação dos modelos tradicionais de desenvolvimento de softwares sequenciais
para um modelo paralelo.
O grande desafio atual, então, é descobrir como tornar a programação paralela
mais simples e acessível para a grande maioria dos programadores, principalmente
pesquisadores, uma vez que este trabalho tem como principal abordagem o
desenvolvimento de software científico. Desta maneira, o enfoque principal deste
trabalho foram os softwares científicos. Entretanto, em princípio, nada impede que a
técnica seja usada para desenvolvimento de aplicativos paralelos e distribuídos em
geral.
Ao final deste trabalho é disponibilizado para a comunidade acadêmica um
conjunto de técnicas de Engenharia de Software voltadas ao desenvolvimento de
aplicações paralelas, incentivando, facilitando e proporcionando esta evolução na
qualidade dos softwares produzidos principalmente por cientistas.
1.1 – Caracterização do Problema / Motivação
Não é possível notar um volume significativo de produções acadêmicas (ou
comerciais) que envolvam a Engenharia de Software aplicada ao desenvolvimento
de software paralelo. Neste sentido, busca-se, a partir da presente pesquisa, estudar
e propor novas estratégias para a melhoria da qualidade no desenvolvimento desse
tipo de software. Assim, além de melhorar o desenvolvimento de novas aplicações e
proporcionar melhorias também nos aplicativos já desenvolvidos, este estudo
procura incentivar a identificação de padrões de projeto que tornem a programação
paralela mais compreensível e, principalmente, mais fácil de desenvolver e manter.
12
Em complementação, não se percebe um consenso a respeito das melhores práticas
ou da maneira de utilização da Engenharia de Software no desenvolvimento
específico para arquiteturas paralelas e distribuídas. Portanto, o trabalho realiza,
também, uma avaliação cuidadosa do atual estado da arte no assunto, avaliando as
técnicas a serem utilizadas em projetos de engenharia de desenvolvimento de
software especificamente paralelos, e principalmente software científico, devido às
suas características peculiares e necessidade de alto desempenho, e, então, seguir
adiante neste campo de pesquisa.
Segundo Lee et al. (2010), de acordo com a Lei de Amdahl, o desempenho do
código é limitado por sua parte serial. Neste sentido, é algo interessante, quando se
tem um hardware com processamento paralelo, o projeto de sistema possuir um
núcleo para acelerar regiões de códigos não seriais através da utilização de threads,
que seria a paralelização do código. Isto já vem sendo pesquisado, conforme se vê
abaixo no gráfico apresentado por Jason (2012), o qual apresenta os ganhos de
desempenho conquistados através da utilização de uma arquitetura multicore e
multiprocessada (Figura 1).
Figura 1: Gráfico de desempenho com utilização de Multicores e Multiprocessadores.
Fonte: Adaptado de Jason (2012).
O problema da dificuldade de desenvolver software paralelo não é novo e
através do aproveitamento das pesquisas e descobertas já realizadas até hoje,
pode-se partir para a busca de novas descobertas, já considerando que a
13
automatização do paralelismo não é muito interessante e a criação de uma nova
linguagem de programação é inviável. Assim, acredita-se que uma maneira de
resolver este problema é primeiramente entender como arquitetar o software
paralelo da melhor maneira (KEUTZER E MATTSON, 2010). Isto pode ser verificado
quando Rigo et al. (2007) dizem que para fazer uso do potencial oferecido pelo
hardware atual, o software deve ser paralelizado, e confirmado também por
Pankratius (2010), quando diz que todas as aplicações de alto desempenho, não
apenas as aplicações de supercomputadores, devem ser paralelas para explorar
melhor o potencial do hardware. Dessa forma, o modelo sequencial de programação
deve ser alterado para um modelo paralelo.
Segundo Keutzer e Mattson (2010), a chave para escrever software paralelo de
alta qualidade é desenvolver uma análise robusta para este software: o sucesso de
qualquer produto de software de qualidade está na base em que ele foi desenvolvido
- sua arquitetura, análise e desenho – que, consequentemente, irá influenciar
diretamente o bom desenvolvimento e implantação.
A evolução das arquiteturas de hardware já trouxe avanços significativos para o
desempenho, por exemplo, o speed-up dos aplicativos, que é entendido como o
ganho em velocidade de processamento através da adição de núcleos de
processamento. O gráfico da Figura 2, apresentado por Geonumerics (2012) indica a
possibilidade de avanços na utilização dos recursos de hardware disponíveis. Ele
ilustra a perda de eficiência na atual utilização dos computadores multicores,
comparando o speed-up alcançado com diferentes tecnologias de implementação de
paralelismo, como o algoritmo de gerenciamento de tarefas H-Dispatch, o modelo de
endereçamento de memória Scatter-Gather e a interface de comunicação MPI, com
o que denotaria o speed-up ideal.
14
Figura 2: Gráfico comparativo de desempenho e eficiência de CPU´s Multicores
Fonte: Adaptado de Geonumerics (2012)
Uma vez que seja perceptível uma melhoria na qualidade, reusabilidade e
eficiência dos softwares produzidos, acredita-se que o presente projeto se tornará
um multiplicador para uma melhor utilização dos ambientes multiprocessados e de
processamentos distribuídos disponíveis para pesquisas, ampliando assim o
conhecimento e evoluindo os estudos na área de Engenharia de Software voltada
para a computação paralela.
Assim, ao final desta pesquisa, fazendo-se uso do suporte de uma abordagem
otimizada, controlada e sistemática da Engenharia de Software para sistemas
paralelos
e
distribuídos,
pretende-se
apresentar
uma
nova
técnica
para
desenvolvimento deste tipo de sistema.
1.2 – Objetivos: Geral e Específico
O objetivo geral da presente investigação é propor um modelo baseado em técnicas
específicas de Engenharia de Software a serem utilizadas no desenvolvimento de
softwares,
especialmente
científicos,
para
computadores
multicores
e
de
processamento distribuído.
Para que seja possível alcançar o objetivo geral acima descrito, os seguintes
objetivos específicos podem ser elencados:
15
- Levantamento detalhado do estado da arte em computação e técnicas de
programação paralela, arquiteturas paralelas e desenvolvimento de softwares
científicos, com foco principal nos problemas enfrentados durante o desenvolvimento
de software paralelo.
- Estudo da Engenharia de Software aplicada ao desenvolvimento de software
paralelo.
- Proposta de um conjunto de técnicas de Engenharia de Software a serem utilizadas
neste tipo específico de arquitetura, proporcionando opções simples e eficazes de
documentação para os pesquisadores utilizarem o modelo de programação paralela
em seus aplicativos.
- Estabelecimento de um modelo com técnicas e formalização de uma proposta de
abordagem sistematizada da Engenharia de Software para aplicativos a serem
implementados em arquiteturas paralelas e distribuídas.
- Escolha de uma aplicação paralelizável, no caso, o cálculo da constante PI, para
verificação e validação das técnicas propostas no presente estudo.
- Implementação e execução de aplicativos específicos, de cálculo de PI,
desenvolvidos com base nas técnicas propostas, para arquiteturas de Multicores,
Cloud Computing, Grid Computing e Cluster.
- Avaliação, sistematização e conclusão dos resultados obtidos.
1.3 – Estrutura do trabalho
O presente trabalho foi distribuído em sete capítulos. Após o capítulo
introdutório, segue o Capítulo 2 com a fundamentação teórica relevante para o
desenvolvimento da dissertação. No Capítulo 3 é apresentado um levantamento
bibliográfico a respeito dos principais problemas relacionados à programação
paralela. No Capítulo 4, as técnicas desenvolvidas são apresentadas juntamente
com o modo de utilização. Nos Capítulos 5 e 6 são propostas a implementação de
16
um aplicativo de testes e a aplicação da técnica em seu desenvolvimento para
implantação em diferentes arquiteturas paralelas, ao final são apresentados os
resultados obtidos e uma análise a respeito deles. Finalmente, no sétimo e último
capítulo são apresentadas as conclusões a respeito do trabalho desenvolvido. Ao
final, são apresentadas as referências utilizadas e os anexos. A organização dessa
dissertação é apresentada graficamente pela Figura 3:
Figura 3: Apresentação gráfica da organização da dissertação em capítulos.
17
2 – FUNDAMENTAÇÃO TEÓRICA
2.1 – Programação paralela
Pode-se dizer que a programação paralela é, hoje em dia, desenvolvida e
estudada de maneira independente da Engenharia de Software, ou melhor,
utilizando basicamente a Engenharia de Software tradicional. Ritter e Bordin (2009),
em seu trabalho de pesquisa bibliográfica e laboratorial, identificaram e avaliaram
algumas bibliotecas e linguagens utilizadas na programação, chegando ao seguinte
quadro comparativo de interfaces (Tabela 1).
Tabela 1: Comparativo entre interfaces de programação paralela
Fonte: Ritter e Bordin (2009)
POSIX threads (PThreads) é uma interface de programação em linguagem C
padronizada que foi especificada pelo IEEE POSIX. Define uma API padrão para
criar e manipular threads. As bibliotecas que implementam a POSIX threads são
chamadas Pthreads, sendo muito difundidas no universo Unix e outros sistemas
operacionais semelhantes como Linux e Solaris (BARNEY, 2012).
Cilk Plus é um produto da Intel, de código aberto. Essencialmente, o projeto
está trabalhando em extensões para as linguagens C e C++, tornando a
programação paralela eficiente mais fácil. O produto inclui três simples palavras
chave e notações de array que permitem aos desenvolvedores C e C++ fazerem uso
produtivo de processadores modernos que contém tanto múltiplos núcleos quanto
unidades vetoriais (CAMPOS, 2011).
18
Intel® Threading Building Blocks (Intel ® TBB) oferece uma abordagem rica e
completa para expressar paralelismo em um programa C++. É uma biblioteca que
ajuda o desenvolvedor a tirar proveito do desempenho dos processadores multicore
sem ter que ser um especialista em paralelismo. Intel TBB não é apenas uma
biblioteca para substituição de threads. Ela representa um nível mais alto; é
paralelismo baseado em tarefas que abstrai detalhes da plataforma e mecanismos
de segmentação para escalabilidade e desempenho. (INTEL, 2012)
Em relação à autoparalelização, estudos já demonstraram não ser uma boa
opção, pois os compiladores podem especular, ordenar dados e reordenar
instruções para equilibrar a carga entre os componentes de um sistema, mas eles
não conseguem reescrever um algoritmo serial criando um algoritmo diferente mais
adequado para execução paralela. (KEUTZER E MATTSON, 2010)
OpenMP (Open Multi-Processing) é uma interface de programação de
aplicativo para a programação paralela de memória compartilhada em múltiplas
plataformas. Permite acrescentar aos programas escritos em C, C++ e Fortran um
método de paralelização no qual o "master thread", parte serial do código, bifurca
(forks) um específico número de threads escravos e uma tarefa é dividida entre eles.
As threads são então executadas simultaneamente. Esta interface está disponível
em muitas arquiteturas, incluindo as plataformas Unix e Microsoft Windows.
High Performance Fortran (HPF) é uma extensão do Fortran 90 com
construções que suportam a computação paralela, publicada pelo High Performance
Fortran Fórum (HPFF) em seu primeiro fórum em 1993. Com base na matriz de
sintaxe introduzido em Fortran 90, HPF usa um modelo de dados de computação
paralela para apoiar a distribuição da execução de uma matriz de trabalhos em
múltiplos processadores. Isso permite uma execução eficiente em arquiteturas SIMD
e MIMD, que serão abordadas mais a frente. (RICE UNIVERSITY, 2006)
CUDA™ é uma plataforma de computação paralela e um modelo de
programação desenvolvido pela NVIDIA. Ela permite aumentos significativos de
desempenho computacional ao aproveitar a potência da unidade de processamento
gráfico (GPU). Com a CUDA, você pode enviar código em C, C++ e Fortran
diretamente à GPU, sem precisar usar uma linguagem de compilação. (NVIDIA,
2012)
Ao final de seu trabalho, Ritter e Bordin (2009) chegaram à conclusão de que
em seus experimentos, CUDA se apresentou como melhor opção em fase de testes,
19
devido à memória compartilhada rápida, porém o modelo sofre alguns gargalos em
relação à comunicação e é utilizada somente em Unidades de Processamento
Gráfico de Propósito Geral ou GPGPU. HPF e OpenMP continuam sendo as
principais alternativa para aplicações paralelas devido à relativa simplicidade de
implementação. Por sua vez, TBB surgiu com enfoque principal em multicore. Assim,
não existe uma única interface melhor para todos os casos, sendo que uma
avaliação específica da aplicação ainda é necessária e indispensável para definir
bem a ferramenta que será melhor aproveitada.
Outras interfaces de desenvolvimento paralelo poderiam ser abordadas, como,
por exemplo, o MPI, Message Passing Interface, que é um padrão para
comunicação de dados em computação paralela. O MPI tem por objetivo prover um
padrão para escrever programas paralelos com comunicação através de troca de
mensagens de forma prática, portátil, eficiente e flexível. Existem diversas
implementações de MPI, sendo o Open MPI a maior e mais ampla delas. O Open
MPI é um projeto open source mantido por um conjunto de universidades e
entidades de pesquisa, que proporciona a fácil utilização do MPI. (OPEN MPI
PROJECT, 2013)
Além das tecnologias abordadas por Ritter e Bordin (2009), a programação
paralela em Java, hoje em dia, vem se desenvolvendo através da biblioteca Java
Threads, nativa. A implementação de códigos paralelos é realizada através da
Classe Thread (java.lang.Thread). O uso desta classe permite definir algumas
configurações, como, por exemplo, de prioridade de execução das Threads, início e
parada de processamento e tipos de Thread. (JEVEAUX, 2012)
A partir da versão 1.5 do Java, ele passou a fornecer um melhor suporte para o
paralelismo de processamento através do pacote java.util.concurrent. Este novo
pacote fornece ferramentas mais simples para implementação de aplicativos
concorrentes, como, por exemplo, o bloqueio para proteger certas partes do código a
serem executadas por vários segmentos, ao mesmo tempo. (VOGEL, 2012)
Viry (2010) aborda a utilização do Java em computação de alta performance
(HPC - High-Performance Computing) e cita como vantagens da utilização do Java o
desenvolvimento mais ágil, maior confiabilidade do código, portabilidade e a
possibilidade de otimizações em tempo de execução.
Na mesma linha da linguagem Java, de linguagens de programação
gerenciadas,
a
Microsoft
vem
trabalhando
em
seu
principal
produto
de
20
desenvolvimento de softwares, o framework .NET, com o objetivo de melhorar e
facilitar as implementações paralelas através da biblioteca “Task Parallel Library”.
Segundo Macoratti (2011), a partir da versão 4.0 do .NET framework, um novo
modelo de programação paralela foi introduzido, permitindo ao programador focar
principalmente nas tarefas do softwares, e a criação e gerenciamento das Threads
fica sob a responsabilidade do runtime. A principal desvantagem é que ao usar este
recurso, o programador abre mão do controle direto do comportamento da sua
aplicação e isso pode não ser o cenário ideal para aplicações que requeiram um
controle e gestão mais refinado.
Há quem possa questionar o valor de um subsistema avançado em
linguagem gerenciada para escrever código paralelo. Afinal de contas,
paralelismo e simultaneidade dizem respeito a desempenho, e
desenvolvedores interessados em desempenho procuram por linguagens
nativas que ofereçam acesso extremamente rápido ao hardware e controle
total sobre cada manipulação de bit, de linha de cache e cada operação
sincronizada...certo? Eu temo pela situação de nossa indústria se esse for
realmente o caso. Linguagens gerenciadas, como C#, Visual Basic e F#
existem para oferecer a todos os desenvolvedores — tanto os meros
mortais como os super-heróis — um ambiente seguro e produtivo no qual se
possa desenvolver rapidamente código poderoso e eficiente. (TOUB, 2011)
Toub (2011) faz uma análise a respeito da evolução apresentada pelo .NET
Framework 4.0 para desenvolvimento paralelo, onde defende a simplificação e a
utilização de linguagens gerenciadas no desenvolvimento de softwares de alto
desempenho, principalmente paralelos.
Assim, analisando comparativamente, no momento atual o .NET se encontra
mais avançado no sentido de proporcionar facilidade de programação paralela aos
programadores do que o Java, porém este possui um maior controle dos processos
paralelos desenvolvidos, gerando talvez uma maior dificuldade no desenvolvimento
dos códigos fontes, mas o Java possui uma comunidade bastante sólida de
programadores, que se ajudam através da internet a fim de solucionarem os
problemas apresentados pelos colegas.
2.2 – Softwares científicos
O desenvolvimento de software científico, segundo Mohammad (2010), é um
processo pelo qual o software é criado para auxiliar cientistas e pesquisadores na
21
procura de solução para a sua meta. Mohammad (2010) acrescenta ainda que o
estudo de uma melhor abordagem de desenvolvimento de software científico está
em um estágio prematuro, devido ao fato de não existir uma definição formal de
levantamento de requisitos na investigação científica, dada a sua natureza muitas
vezes complexa.
Segundo Pressman (2006), software científico e de engenharia são
principalmente algoritmos de processamento de números. Mas as aplicações de
software científico e de engenharia vão muito além, da astronomia à vulcanologia,
da análise automotiva de tensões à dinâmica orbital do ônibus espacial, e da
biologia molecular à manufatura automatizada.
Assim, softwares científicos são considerados por Pankratius (2010) como mais
comuns na área da programação paralela por não necessitarem tanta robustez como
os softwares comerciais ou industriais, uma vez que a maioria das simulações pode
ser reiniciada, caso haja alguma falha. Contudo, os resultados dos softwares
científicos precisam ser confiáveis, o que é favorecido através de uma boa
engenharia software.
Segundo Pereira Junior (2007), as particularidades que os softwares científicos
apresentam em relação ao software comercial são principalmente: o papel do
cliente, a identificação dos requisitos e a alta rotatividade dos pesquisadores. No
desenvolvimento de um software científico não existe o papel do cliente. Este tipo de
software geralmente é construído por um pesquisador, com a finalidade de validar ou
apoiar sua própria pesquisa. Sendo assim, os pontos de validação existentes no
desenvolvimento de um software comercial inexistem no desenvolvimento de um
software científico. Além disso, na maioria das vezes, os pesquisadores não
possuem muita experiência com desenvolvimento de software, necessitando
aprender como se desenvolve em determinadas tecnologias para implementar seus
aplicativos.
A identificação dos requisitos ao longo do seu desenvolvimento pode mudar,
por exemplo, pela evolução da pesquisa. Sendo assim, o pesquisador e
desenvolvedor não tem o conhecimento dos detalhes do software científico como um
todo, diferentemente do software comercial em sua maioria.
E, por fim, há alta rotatividade dos pesquisadores em uma pesquisa.
Geralmente, um software científico é desenvolvido para validar uma determinada
22
parte de uma pesquisa e, ao término da pesquisa, o desenvolvedor se desvincula da
pesquisa, como acontece com os alunos de mestrado e doutorado, por exemplo. No
entanto, os próximos alunos frequentemente continuam o desenvolvimento do
software. Já no caso de softwares comerciais, frequentemente existe uma equipe de
desenvolvimento pré-definida e não se altera, ou se altera minimamente, até o
término do projeto. Além disso, no desenvolvimento de um software comercial
existem
pessoas
com
funções
distintas,
como
analistas
de
sistemas,
administradores da base de dados, engenheiros de testes, e programadores. No
desenvolvimento de um software científico, o pesquisador tende a desempenhar
todas estas atividades, e muitas das vezes apenas com o mínimo de conhecimento
em cada um dos papeis citados acima.
2.3 – Arquiteturas paralelas
Uma arquitetura paralela de computador pode ser definida como aquela que
permite a computação ou execução de vários cálculos simultaneamente. Isto se
torna possível devido à presença de várias unidades de processamento dedicadas
ao ambiente de execução. Segundo Rose (2010), as arquiteturas paralelas
contribuem para o ganho de desempenho em relação às arquiteturas convencionais,
sendo alternativa quando os limites físicos são alcançados. Hoje, já existe demanda
de aplicações de alto desempenho como simulações de previsão de tempo, modelos
físicos ou biológicos, computação gráfica, entre outros.
As arquiteturas de computadores são classificadas segundo o modelo, pelo
fluxo de instruções e pelos dados que se apresentam. Essa classificação é definida
como taxonomia de Flynn e fica divida em quatro categorias, conforme listadas
abaixo: (FLYNN, 1966, apud COSTA, 2006).
• SISD (Single Instruction stream and Single Data stream): Arquitetura onde
uma unidade de processamento pode executar uma única instrução em um único
conjunto de dados, não há paralelismo. Corresponde a arquitetura de Von Neumann.
Há aproximadamente uma década, essa arquitetura tem deixado de ser o padrão na
construção de computadores, sendo substituída por computadores com arquitetura
do tipo SIMD e MIMD.
• SIMD (Single Instruction stream and Multiple Data stream): Arquitetura onde
uma unidade de processamento pode executar uma mesma instrução e operar em
23
múltiplos conjuntos de dados. Aplicações que precisam executar a mesma operação
em grandes vetores ou matrizes podem tirar vantagem desse tipo de arquitetura.
• MISD (Multiple Instruction stream and Single Data stream): Arquitetura onde
múltiplas
unidades
de
processamento
executam
diferentes
instruções
simultaneamente em um mesmo conjunto de dados.
• MIMD (Multiple Instruction stream and Multiple Data stream): Arquitetura onde
múltiplas
unidades
de
processamento
executam
diferentes
instruções
simultaneamente em diversos conjuntos de dados diferentes.
Estas
arquiteturas
ainda
podem
ser
classificas
também
segundo
o
compartilhamento de memória como multiprocessadores ou multicomputadores. Os
computadores multiprocessados compartilham uma memória central, com um único
espaço de memória que é utilizado por todos os núcleos de processamento. Neste
tipo de arquitetura, normalmente a comunicação e a sincronização entre os
processos é feita através de variáveis compartilhadas. (ROSE, 2010)
Já no caso dos multicomputadores, a memória não é compartilhada, ou seja,
cada elemento de processamento possui seu próprio espaço de memória, e a
comunicação e a sincronização normalmente é realizada através da troca de
mensagens.
2.3.1 – Multicore
Atualmente, os hardwares paralelos mais comuns são as arquiteturas
multicores, ou seja, arquiteturas com múltiplos núcleos de processamento. Esta
tecnologia implica em introduzir vários núcleos de processamento dentro de um
mesmo encapsulamento físico, permitindo a execução de diversas instruções
simultaneamente. Segundo Domeika (2008), multicore é um processador composto
por réplicas idênticas e funcionais de um processador ou várias unidades funcionais
distintas, agregando muita flexibilidade em termos da distribuição da aplicação.
Há alguns anos, a comparação entre processadores era bem mais simples,
bastando analisar a frequência de operação entre eles. No entanto, este paradigma
tornou-se insustentável a partir do momento em que altas frequências geravam uma
quantidade muito grande de calor que provocava limitações nos sistemas, além de
acarretar alto consumo energético. Assim, surgia a nova era dos processadores
multicores, que utiliza diversos núcleos com frequências de processamento mais
24
baixas dentro de um mesmo chip. (SULEMAN, 2011)
Ainda segundo Suleman (2011), núcleos com frequências mais baixas tendem
a ser mais eficientes devido a três razões: primeiramente, devido à economia de
energia proporcionada pela diminuição da dissipação de calor; pela diminuição da
especulação, pois núcleos mais rápidos tendem a ser mais especulativos confiando
mais em valores previstos, sem esperar a confirmação do resultado final, mas isso
pode gerar erros; e, por fim, pela diminuição da potência dos flip-flops, pois núcleos
mais rápidos tendem a possuir pipelines mais profundos na busca por alto
desempenho, e quanto mais estágios de pipelines, maior será o numero de flip-flops,
gerando maior gasto de energia.
Os multicores representam o caminho da evolução dos processadores, pois
representam a replicação real dos recursos de vários processadores dentro de um
único chip, sendo que cada núcleo possui sua própria memória cache e todos eles
ainda compartilham uma memória cache geral do chip. (MIDORIKAWA, 2010)
É importante definir a diferença entre processadores multicores e sistemas
multiprocessados, sendo que um sistema multiprocessado consiste em múltiplos
processadores interconectados em um único sistema ou um único computador,
sendo que cada um destes processadores ainda podem ser core simples ou
multicore (Figura 4). Já os processadores multicores possuem vários núcleos de
processamento dentro de cada processador. Então, pode-se entender que um
computador pode ser multiprocessado e multicore ao mesmo tempo, uma vez que
são conceitos distintos.
Figura 4: Configurações de sistemas
Fonte: Domeika (2008)
25
Atualmente no mercado já estão disponíveis processadores para uso
doméstico de 6 (seis) núcleos, como o caso do Intel i7 980X, com tecnologia HyperThreading, capaz de emular o dobro de núcleos, resultando teoricamente em 12
(doze) núcleos de processamento. Este tipo de processador atualmente atende
perfeitamente a demanda de performance dos usuários domésticos e a maioria dos
usuários profissionais, sendo perceptível a melhora de performance em relação a
modelos anteriores como o Intel i5 somente em trabalhos gráficos como
renderização de vídeos ou cálculos matemáticos pesados. (JORDÃO, 2010)
2.3.2 – Cluster
Existem, além das arquiteturas paralelas citadas acima, alguns tipos de
hardwares que são paralelos, como, por exemplo, os Clusters. Um Cluster pode ser
definido como um sistema constituído de vários processadores, na maioria dos
casos através de uma rede de alta velocidade, onde trabalham de maneira conjunta
para realizar um processamento pesado, dividindo as tarefas de processamento e
trabalhando como se fosse um único computador.
Na década de 1960, a IBM começou a desenvolver uma forma de interligar
grandes mainframes, visando obter uma solução comercialmente viável de
paralelismo, sinalizando o que viria a ser definido como Cluster de Computadores.
A IBM desenvolveu o Cluster de mainframes através do Parallel Sysplex
System, um sistema que permitia ao hardware, ao sistema operacional, ao
middleware e ao software de gerenciamento do sistema prover uma grande melhora
na performance e diminuição dos custos. Este modelo de Cluster ganhou força até
que três tendências se consolidaram nos anos 1980: microprocessadores de alta
performance, redes de alta velocidade e ferramentas padronizadas para computação
distribuída de alto desempenho. Mas, uma quarta tendência, a crescente
necessidade de poder de processamento para aplicações científicas e comerciais,
com um alto custo e baixa acessibilidade dos tradicionais supercomputadores,
enfraqueceu o modelo de Cluster da IBM.
No final de 1993, Donald Becker e Thomas Sterling iniciaram um esboço de um
sistema de processamento distribuído construído a partir de hardware convencional
como uma medida de combate aos altos custos dos supercomputadores. No início
26
de 1994 criaram o primeiro cluster com estas característica, o projeto Beowulf. O
protótipo inicial era um cluster de 16 processadores ligados por dois canais Ethernet
acoplados. A máquina foi um sucesso instantâneo e esta idéia rapidamente se
espalhou pelos meios acadêmicos, pela NASA e por outras comunidades de
pesquisa. (JORGE NETO, 2012)
Pitanga (2004) diz que as características fundamentais para a construção de
Clusters são principalmente a confiança, a distribuição de carga e o desempenho.
Ainda segundo Pitanga (2004), os Clusters são classificados como:
• Cluster de Alta Disponibilidade (High Availability (HA) and Failover): Estes
modelos de clusters são construídos para prover uma disponibilidade de serviços e
recursos de forma ininterrupta através do uso da redundância implícita ao sistema.
• Cluster de Balanceamento de carga (Load Balancing): Este modelo distribui o
tráfego entrante ou requisições de recursos provenientes dos nós que executam os
mesmos programas entre as máquinas que compõem o Cluster.
• Combinação HA & Load Balancing: Como o próprio nome diz, combina as
características dos dois tipos de Cluster, aumentando assim a disponibilidade e
escalabilidade de serviços e recursos.
Cluster de Processamento Distribuído ou Processamento Paralelo: Este
modelo de Cluster aumenta a disponibilidade e desempenho para as aplicações,
particularmente para as grandes tarefas computacionais. Uma grande tarefa
computacional pode ser dividida em pequenas tarefas que são distribuídas ao redor
das estações (nós), como se fosse um supercomputador massivamente paralelo.
Em um ambiente de cluster de computadores, conforme o texto de Appel et al.
(2012), a alocação de recursos é efetuada por domínio administrativo centralizado,
tornando o processo de utilização e o recurso mais seguros, uma vez que a rede de
interconexão esteja desconectada da rede de acesso externo. Além disso, este tipo
de ambiente pode se beneficiar de protocolos de comunicação mais eficientes entre
suas unidades de processamento, pois como a rede de interconexão pertence ao
mesmo domínio administrativo, o recurso é controlado.
Nos dias atuais, as maiores arquiteturas de processamento de alto
desempenho são montadas em Clusters de computadores e classificados
mundialmente conforme o desempenho pelo site http://top500.org. As listas são
atualizadas semestralmente, nos meses de junho e novembro. Segundo a última
27
lista disponibilizada, de novembro de 2012, o primeiro Cluster do ranking é o Titan Cray XK7 , Opteron 6274 16C 2.200GHz da Cray Gemini interconnect, com 560.640
núcleos de processamento, localizado nos Estados Unidos. Na segunda posição do
ranking está o projeto Sequoia da IBM. No Brasil, segundo o mesmo ranking, o
maior Cluster é o Grifo04, um Itautec Cluster, Xeon X5670 6C 2.930GHz Infiniband
QDR, NVIDIA 2050, da Petrobras, classificado na 98º posição no mundo.
2.3.3 – Grid Computing
Segundo Poderoso (2004), Grid Computing pode ser entendido como
computação
por
demanda
ou
computação
em
grade.
Os
recursos
são
dinamicamente alocados para atender as necessidades do sistema na hora em que
eles realmente precisam. É possível entender este conceito como sendo um grupo
de equipamentos compartilhando seus recursos através de redes de altíssima
velocidade. Estas redes seriam capazes de atender às demandas pelas requisições
e os recursos deveriam estar sob o controle de algo que pudesse, dinamicamente,
distribuir o serviço de modo a equilibrar esta equação.
Em um ambiente de Grid, a alocação de recursos normalmente é realizada por
administração descentralizada, ou seja, cada organização, ou nó de processamento,
controla seus próprios recursos, aplicando políticas conforme sua demanda de
utilização. Existe, ainda, a possibilidade de heterogeneidade das arquiteturas e
sistemas operacionais empregados, característica típica de um Grid. Assim, um
grande desafio é obter uma forma de encapsular estas diferenças sem comprometer
a performance do Grid como um todo. A infraestrutura deste ambiente deve permitir
o acesso consistente aos recursos através de serviços padronizados, com interfaces
e parâmetros muito bem definidos. Sem estas normas, os serviços prestados podem
ser ineficazes. (APPEL et al., 2012)
Os Grids são comumente utilizados em projetos de organizações, que podem
ser empresas comerciais ou não, universidades, dentre outras, que necessitam de
longas horas de processamento mas não possuem esta capacidade disponível.
Assim são criadas comunidades em que usuários comuns da Internet oferecem
períodos ociosos de seus computadores para ajudar nestes processamentos. Um
exemplo deste tipo de organização é o Boinc (BOINC, 2012), onde cada nó de
processamento é cadastrado como voluntário no site e fica disponível para ser
utilizado em seus momentos ociosos de processamento, assim como os nós de
28
processamento. Organizações interessadas nestes nós disponíveis podem cadastrar
seus projetos e utilizar todo este potencial disponibilizado através da rede.
Mas os Grids podem ser utilizados também através de redes privadas de
dados, onde todos os nós de processamento utilizados pertencem a uma mesma
rede. Isto proporciona maior potencial de utilização, devido às pequenas distâncias
entre os computadores, e garante também mais segurança nos dados processados.
Um exemplo de aplicativo utilizado para o gerenciamento de Grid Computing é
o JPPF Grid. O JPPF Grid permite a configuração e disponibilização de vários nós
de processamento em uma rede, além do gerenciamento completo do Grid através
de um aplicativo em Java. Por ser desenvolvido em Java, o JPPF ainda possui a
característica de ser multiplataforma e não necessitar de instalação para o seu
funcionamento. (JPPF, 2012)
Cluster e Grid são arquiteturas semelhantes, sendo a principal diferença entre
eles é que um cluster possui um controlador central, ou seja, um único ponto de
onde é possível utilizar todo o poder de processamento do cluster; os demais nós
são apenas escravos que servem a este nó central. Já o Grid pode ser definido
como uma arquitetura mais "democrática" onde, embora possa existir algum tipo de
controle central, se tem um ambiente fundamentalmente cooperativo. Os nós de
processamento ou computadores compartilham os seus ciclos ociosos de
processamento em seus sistemas, e em troca podem utilizar parte do tempo de
processamento do Grid. (MORIMOTO, 2005)
Appel et.al (2012) faz uma comparação interessante entre as características
das arquiteturas de Cluster e Grid Computing, resumida na Figura 5 mostrada
abaixo. Apenas o item que trata a segurança do processamento e do recurso é
questionável, uma vez que, de acordo com a informação tratada pelos
computadores, a segurança pode se tornar um fator muito importante.
Figura 5: Diferenças entre as configurações de Cluster e Grid.
Fonte: APPEL et al. (2012)
29
2.3.4 – Cloud Computing
Também conhecido no Brasil como computação nas nuvens ou computação
em nuvem, Cloud Computing se refere, essencialmente, à idéia de se utilizar, em
qualquer lugar e independente de plataforma, as mais variadas aplicações por meio
da internet com a mesma facilidade de tê-las instaladas em computadores próprios,
como apresentado na Figura 6. Intimamente ligado ao Cloud Computing está o
conceito de Software as a Service (SaaS), ou Software como Serviço. Em sua
essência, trata-se de uma forma de trabalho onde o software é oferecido como
serviço, assim, o usuário não precisa adquirir licenças de uso para instalação ou
mesmo comprar computadores ou servidores para executá-lo. Nesta modalidade, no
máximo, paga-se um valor periódico, como se fosse uma assinatura, somente pelos
recursos utilizados e/ou pelo tempo de uso. Surgem ainda, neste mesmo sentido, a
Platform as a Service (PaaS) ou Plataforma como Serviço, Database as a Service
(DaaS) ou Banco de Dados com Serviço, Infrastructure as a Service (IaaS) ou
Infraestrutura como Serviço, e Testing as a Service (TaaS) ou Testes como Serviço
(ALECRIM, 2011).
Figura 6: Cloud Computing.
Fonte: Adaptado de Nacionalhost (2011)
O Cloud Computing é um modelo que provê um melhor aproveitamento dos
investimentos em hardware. Nesse ambiente, não se tem a garantia de que os
processos serão todos alocados numa mesma máquina, caracterizando assim o
30
processamento distribuído, porém sem a necessidade de linguagens paralelas ou
extensões de programação. Um dos pilares do Cloud Computing é a consolidação
dos recursos de hardware para que eles possam ser aproveitados ao máximo e
gerenciados de forma inteligente, proporcionando economia de custos (NACIONAL
HOST, 2011). Porém, esta proposta de transparência pode limitar o aproveitamento
do hardware, pois limita o controle dos aplicativos, confiando apenas no potencial do
software gerencial do sistema de Cloud Computing para a distribuição das tarefas a
serem processadas.
Conforme Armbrust et al. (2010), as empresas com grandes lotes tarefas
podem obter resultados tão rapidamente quanto seus programas puderam escalar,
isto porque podem usar 1.000 servidores para uma hora de processamento
custando não mais do que usando um único servidor para 1.000 horas de
processamento. Essa elasticidade de recursos, sem pagar um alto valor pela alta
escalabilidade, é sem precedentes na história da TI.
De um provisionamento de hardware e do ponto de vista de custos,
três aspectos são novos na computação em nuvem.
•
A aparência de infinitos recursos computacionais disponíveis
sob demanda, com rapidez suficiente para acompanhar picos de carga,
elimina a necessidade de planejamento a longo prazo dos recursos
computacionais pelos usuários.
•
A eliminação de um compromisso antecipado pelos usuários
na nuvem permite que as empresas comecem utilizando poucos recursos
de hardware e aumentem seus recursos apenas quando há necessidade.
•
A possibilidade de pagar pelo uso de recursos de computação
em uma base de curto prazo, conforme a necessidade (por exemplo, os
processadores por hora e armazenagem por dia) e liberá-los, se necessário,
permitindo que máquinas e armazenamento fiquem disponíveis quando não
estão mais em uso. (ARMBRUST et al., 2010)
Ainda segundo Armbrust et al. (2010), a construção e operação em larga
escala de data centers locáveis com baixo custo foram a chave para o sucesso do
Cloud Computing, que proporcionou ainda a queda dos custos com energia elétrica,
bandas de rede, licenças de softwares e investimentos em hardware. Estes fatores
combinados com análises estatísticas de utilização proporcionaram ainda mais a
diminuição dos custos com serviços de TI através do Cloud.
Assim, diante dos conceitos e diversas arquiteturas apresentados, e pelo fato
de que se deve conseguir o melhor aproveitamento do potencial oferecido por cada
solução, propõe-se que o software deve ser concebido em arquitetura paralela,
31
desenvolvendo-se softwares paralelos de alta qualidade. Por conseguinte, o foco
deste trabalho se volta à Engenharia de Software paralelo.
2.4 – Visão geral da Engenharia de Software
Provavelmente a primeira vez em que se utilizou o termo “Engenharia de
Software” foi em uma conferência com esse nome, realizada em 1968, na Alemanha.
O termo “Engenharia de Software” foi escolhido para destacar o quanto era
necessário que a produção de software fosse baseada nos fundamentos teóricos e
nas disciplinas práticas conhecidas nos diversos ramos da engenharia. E o seu
surgimento se deu principalmente devido à crise do software que aconteceu naquela
época, conforme descrito por Dijkstra (1972):
A maior causa da crise do software é que as máquinas
tornaram se várias ordens de magnitude mais potentes! Em termos
diretos, enquanto não havia máquinas, programar não era um
problema; quando tivemos computadores fracos, isso se tornou um
problema pequeno e agora que temos computadores gigantescos,
programar tornou-se um problema gigantesco. (DIJKSTRA, 1972)
E hoje, com o continuo desenvolvimento dos computadores, principalmente
com tecnologias de processamento paralelo e distribuído, a necessidade de
constante evolução da produção de software é mais que presente.
Em 1969, Fritz Bauer definiu Engenharia de Software como, “o estabelecimento
e uso de sólidos princípios de engenharia para obter software confiável e que
trabalhe de forma eficiente em máquinas reais.” (BAUER,1969).
Segundo Sommerville (2007), a Engenharia de Software é uma disciplina da
Engenharia que se preocupa com todos os aspectos necessários para a produção
de um software de qualidade, e cujos princípios contribuem para a construção de
sistemas computacionais complexos. Pressman (2006) faz uma abordagem ainda
mais ampla em relação à Engenharia de Software, considerando como uma
tecnologia em camadas que integra processo, métodos e ferramentas para o
desenvolvimento de softwares de computador e deve se apoiar em um compromisso
organizacional com a qualidade.
Assim, entende-se que a Engenharia de Software tem como foco o
desenvolvimento de software dentro dos custos adequados e com alta qualidade.
Pressman (2006) aborda o Processo de Software, como parte da Engenharia de
32
Software, onde quando se elabora um produto ou sistema é importante percorrer
uma série de passos previsíveis, sendo como um roteiro que ajuda a criar um
resultado de alta qualidade, dentro de um prazo razoável. Ainda segundo Pressman,
para todo desenvolvimento de software é recomendada a utilização de um processo
adequado para se garantir o controle e organização das atividades a serem
executadas, seja um processo específico para o tipo de software a ser desenvolvido
ou ainda que seja um processo adaptado para a realidade do projeto em
desenvolvimento.
Além do processo de software, a qualidade do software também é um ponto
fundamental, conforme citado acima por Pressman(2006) e Sommerville (2007),
estando ligada diretamente aos requisitos. Um software de qualidade é aquele que
realiza corretamente todas as funções, ou requisitos, a que se foi proposto executar,
com eficiência e eficácia. Geralmente, a qualidade do produto é decorrente do
processo utilizado em sua elaboração, e pode ser detectada de diversas formas,
como, por exemplo, no caso de funções que não são executadas como deveriam, ou
quando se trata de programas difíceis de serem utilizados ou que não atendem aos
seus requisitos funcionais (PAULA, 2001).
Requisitos funcionais podem ser conceituados como o comportamento que se
espera que o software apresente diante de determinada ação realizada pelo usuário.
Já os requisitos não funcionais estão ligados a outros aspectos não relacionados
diretamente com a função específica do software, como por exemplo: usabilidade,
que define o grau de facilidade de uso do software; portabilidade, que mede o
esforço necessário para transferir um programa para outro ambiente; facilidade de
manutenção, ou seja, o nível de esforço necessário para se localizar os problemas e
realizar a manutenção em um programa (PAULA, 2001).
Em resumo, Almeida Filho (2011) apresenta exatamente o conceito de
Engenharia de Software e a sua ligação ao trabalho proposto, dizendo que ela está
preocupada em estruturar todo o processo de produção do software, desde o
primeiro contato com o cliente até a manutenção exigida após o software estar em
funcionamento, sempre tentando agregar técnicas, métodos, processos e outros
procedimentos e mecanismos para tornar o processo de desenvolvimento mais
racional, científico, repetível, de forma a se aproximar das engenharias tradicionais.
Pankratius (2010) vem trabalhando e pesquisando a fim de avançar os
conceitos, métodos e ferramentas de desenvolvimento de software paralelo, com
33
foco principal na Engenharia de Software totalmente interligada com as linguagens
de programação, compiladores, bibliotecas, middlewares e sistemas operacionais.
Ele acredita ser esta a base para tornar o desenvolvimento de software paralelo
mais fácil. Também, segundo Keutzer e Mattson (2010), a indústria de
desenvolvimento de softwares ainda não conseguiu uma solução efetiva para os
problemas da programação paralela, sendo a análise robusta dos softwares a chave
para o desenvolvimento de software paralelo de boa qualidade.
Assim, dentro destes conceitos sobre a Engenharia de Software propõem-se
algumas técnicas, que unidas ao processo de desenvolvimento de software,
possuem o objetivo de facilitar a utilização das arquiteturas paralelas em projeto de
softwares científicos e proporcionar a construção de softwares paralelos de
qualidade.
34
3 – PRINCIPAIS PROBLEMAS RELACIONADOS AO
PARALELISMO
Para o desenvolvimento de uma técnica de Engenharia de Software para
auxiliar, facilitar e incentivar o uso da programação paralela em projetos de software
científicos, foi realizado um levantamento bibliográfico a respeito dos principais
problemas relacionados à programação paralela, além da revisão bibliográfica, como
visto anteriormente, a respeito das arquiteturas paralelas ou de processamento
distribuído, das técnicas e linguagens de programação paralela e da Engenharia de
Software.
Através destes levantamentos bibliográficos, vislumbrou-se a possibilidade de
desenvolver e sistematizar um conjunto de técnicas com o objetivo que tornar a
programação paralela mais acessível através do desenvolvimento da Engenharia de
Software. Durante esta revisão, atentou-se para importantes pontos da programação
paralela como a granularidade, o controle do sincronismo e da comunicação entre as
tarefas a serem executadas em paralelo, e a escalabilidade. Percebe-se que todos
estes fatores podem ser analisados e planejados de forma inteligente, a fim de
minimizar problemas decorrentes de implementações de paralelismo de baixa
qualidade, ou simplesmente feitos com pouca precaução.
Um aplicativo desenvolvido com níveis de granularidade de paralelismo
inadequados para o ambiente, por exemplo, pode significar grandes perdas de
desempenho, que pode tornar a aplicação do paralelismo prejudicial ao aplicativo.
Assim como um controle ineficaz de sincronismo ou de comunicação pode significar
o
comprometimento dos resultados gerados pelo aplicativo,
ou ainda o
comprometimento de todo aplicativo, tornando-o inutilizável.
Assim, chegou-se à conclusão de que quanto melhor for a compreensão do
problema a ser solucionado e quanto melhor for o conhecimento do aplicativo a ser
desenvolvido, além da arquitetura de hardware que será utilizada para executá-lo,
menor será o custo de desenvolvimento e maior será a qualidade do produto final
desenvolvido.
3.1 – Levantamento bibliográfico
Através de uma revisão bibliográfica, abrangendo artigos publicados entre os
anos de 2009 e 2012, foram levantados e documentados alguns dos principais
35
problemas relacionados à programação paralela que são apresentados a seguir.
Abordado por Lee et al. (2010), Afek et al. (2012) e Allen et. al (2009), o
problema dos bloqueios (locks) em programas de memória compartilhada, assim
como o problema de escalonamento de tarefas ou alocação de recursos em
ambiente de processamento paralelo heterogêneo, citado nos artigos de Netto et al.
(2011), Pascual et al. (2011), Jeannot et al. (2012) e Casanova et al. (2010), são os
problemas que se apresentaram mais frequentes atualmente no desenvolvimento de
aplicações paralelas. Além dos problemas mencionados, conforme citado por Afek et
al. (2012) e Chen e Poirier (2010), a escalabilidade em arquiteturas paralelas
normalmente é comprometida devido ao desenvolvimento das aplicações paralelas
de forma ineficiente. Mais adiante, estes problemas serão abordados de forma mais
específica e detalhada.
Além dos problemas citados, que apareceram com mais frequência no
levantamento bibliográfico realizado e por isso serão abordados com mais
profundidade nos tópicos a seguir, outros problemas encontrados na literatura e
considerados pertinentes podem ser citados, como, por exemplo, a necessidade da
paralelização automatizada de aplicações seriais. No caso, Silva et al. (2009)
propôs, em seu artigo, “Mercury: A reflective middleware for automatic parallelization
of Bags of Tasks.”, o desenvolvimento de um middleware, o Mercury, que lê um
arquivo de configuração que contem informações de quais os métodos e classes
devem ser paralelizados, carrega o aplicativo e, em tempo de execução, o
transforma
de
modo
que
os
métodos
especificados
sejam
executados
paralelamente. A solução proposta utiliza meta-classes, permitindo que a
modificação do código possa ser feita em tempo de execução, sem necessidade de
transformar e recompilar o código fonte. Em seus experimentos, Silva et al. (2009)
concluiu que o Mercury pode lidar com a maioria das aplicações Bag-of-Tasks, que
são aplicações com um conjunto de tarefas independentes a serem executadas, e
até mesmo algumas aplicações com um fluxo de trabalho mais complexos. O
overhead provocado pelo Mercury foi baixo e facilmente vencido pelos ganhos na
facilidade de programação e melhorias de speed-up, mas ainda pode ser utilizado
somente em aplicações bem específicas.
Outro tema abordado é a melhoria de códigos paralelos em linguagens
orientadas a objetos. Noll e Gross (2012) propõem em seu artigo uma extensão para
códigos fonte escritos em Java e C# objetivando a sua melhoria sem a necessidade
36
do uso de bibliotecas específicas da linguagem, o que acontece na maioria das
implementações paralelas em tais linguagens. Em suas observações, eles
conseguiram um ganho de desempenho de 15% em comparação com uma versão
padrão de um mesmo aplicativo.
A limitação do paralelismo é um tema abordado por Allen et al. (2009) em seu
artigo “Serialization Sets: A Dynamic Dependence-Based Parallel Execution Model”,
em que os autores propõem um novo modelo de execução paralela onde os
programadores aprimoram um programa sequencial com pedaços de código
chamados “serializers”, que dinamicamente mapeiam operações computacionais em
conjuntos serializados de operações dependentes. Com este modelo, os conjuntos
de operações serializadas estabelecem uma ordenação lógica em todas as
operações, resultando em uma execução paralela previsível, que pode ser realizada
dinamicamente. Com o novo modelo, eles propõem que não codificando
estaticamente as partes paralelas, ou independentes, do código nos programas
pode se explorar melhor a concorrência.
3.1.1 – Bloqueios em Programas de memória compartilhada
Um problema relatado frequentemente na literatura atual são os bloqueios
(locks)
em
programas
paralelos
de
memória
compartilhada.
Isto
ocorre
principalmente por falhas no sincronismo das tarefas executadas paralelamente, pois
várias tarefas podem necessitar de um dado no mesmo instante, causando conflitos
e bloqueios.
O problema de locks em programas paralelos é abordado por Stivala et al.
(2010), em seu artigo ”Lock-free parallel dynamic programming”, através da
utilização de uma hashtable que armazena todos os resultados compartilhados, que
são computados por cada thread. Antes de executar um novo processo, a thread faz
uma busca na hashtable para saber se aquele processo já foi executado. Quando a
primeira thread verifica que todos os resultados já foram processados, a execução é
finalizada. Stivala et al. (2010) obteve ganho de speedup em diversos aplicativos
dinâmicos, como, por exemplo, o problema da mochila, que trata a otimização de
carga por peso e critério de benefício dos objetos a serem carregados.
Lee et al. (2010) aborda o problema como interferências e conflitos entre as
threads, em seu artigo “Adaptive execution techniques of parallel programs for
37
multiprocessors”, quando executam loops paralelos em arquiteturas de SMT
(Multiprocessadores multithreads), propondo uma técnica padrão onde os processos
paralelos são customizados em tempo de execução de acordo com parâmetros de
performance dinâmicos lidos do hardware. Segundo Lee et al. (2010), foram
alcançadas melhorias de desempenho de execução em 8 contextos de hardware
diferentes, executando aplicações numéricas.
O bloqueio de concorrência é abordado também por Afek et al. (2012) em seu
artigo,
“Interrupting
snapshots
and
the
JavaTM
size
method”,
que
trata
principalmente o paralelismo em um método nativo da linguagem Java TM, o método
size(), que apresenta perda de desempenho por apresentar bloqueios de
concorrência. Para a melhoria de performance do método é proposto um novo
algoritmo livre de bloqueios baseado em snapshot (estado de um sistema em um
determinado ponto no tempo). Segundo Afek et al. (2012), o grande progresso e
coerência das propriedades combinado com a alta escalabilidade do novo algoritmo
leva a crer que este é um bom candidato para a substituição da atual implementação
do método size() no pacote JavaTM para programação paralela.
Allen et al. (2009) também comenta em seu artigo sobre a necessidade de
controle nos processos de sincronização durante a programação paralela, propondo
que o seu modelo de execução visa aprimorar e facilitar o desenvolvimento de
aplicativos paralelos, evitando erros de sincronização, deadlock, livelock e inversão
de prioridades, problemas inerentes aos bloqueios. Allen et al. (2009) utilizou uma
biblioteca do C++, chamada Prometheus, nos testes realizados. Segundo Allen et al.
(2009), Prometheus alcançou bons resultados de desempenho, e em alguns casos
chegou a ter melhor desempenho que programas desenvolvidos exclusivamente
paralelo (que possuem um grau de dificuldade de implementação bem maior), com a
codificação significativamente menor e depuração menos complexa.
Enquanto isso, as práticas de programação modernas, incluindo o
uso de linguagens orientadas a objetos, bibliotecas dinâmicas, e sistemas
gerenciados em tempo de execução, permitiram o rápido crescimento da
indústria da tecnologia da informação. A vasta complexidade das
abordagens atuais para escrever e depurar programas paralelos ameaça
descarrilar este sucesso. Para evitar uma grande ruptura, devemos
identificar soluções que permitam a execução paralela de software sem
comprometer a produtividade do programador. (ALLEN et al., 2009)
38
3.1.2 – Escalonamento de tarefas
Especialmente em arquiteturas de processamento heterogêneas, um problema
que é ressaltado é o escalonamento de tarefas a ser realizado de forma a se
conseguir o processamento de todas as tarefas no menor tempo possível. Neste
sentido, alguns autores propõem algumas soluções a serem avaliadas.
Netto et al. (2011) propõe, em seu artigo “Use of run time predictions for
automatic co-allocation of multi-cluster resources for iterative parallel applications”,
uma técnica de co-alocação de recursos com reescalonamento iterativo de tarefas
com base em previsões de desempenho para multicluster de aplicações paralelas.
Esta técnica é direcionada somente para aplicações com etapas de execução
regular, ou seja, aquelas com carga de trabalho de computação uniforme em cada
iteração, pois podem ser realizadas previsões de tempo observando seu
comportamento em uma execução parcial curta. Segundo Netto et al. (2011),
utilizando a técnica de co-alocação dinâmica, os meta escalonadores ficam
responsáveis por tarefas de previsão de tempo de execução, mapeamento de
processos e reescalonamento de aplicações, tarefas antes atribuídas aos usuários.
Na aplicação dos estudos em 7 (sete) casos diferentes, as previsões de tempo de
execução tiveram um erro médio de apenas 7% e superestimativas de 35% e 57%
para reescalonamento de modelos síncronos e assíncronos, respectivamente. Por
conseguinte, os resultados encontrados permitem encorajar o desenvolvimento do
escalonamento dinâmico de tarefas de processamento paralelo utilizando a previsão
de tempo de execução.
Com uma idéia semelhante à de Netto et al. (2011), Pascual et al. (2011), em
seu artigo “Optimization-based mapping framework for parallel applications”, também
se utiliza de uma matriz de custos de processamento das tarefas e propõe um novo
framework capaz de aperfeiçoar o mapeamento de tarefas com o clássico critério de
distância percorrida entre as mensagens e um novo critério de distribuição de
trânsito, que tenta reduzir a contenção devido ao tráfego da rede e analisa, não
apenas os padrões de comunicação das tarefas de aplicação, mas também a
topologia da rede de interligação. Em suas conclusões, Pascual et al. (2011), após
algumas simulações, notou que ocorreu uma incompatibilidade entre a topologia
física e virtual resultando em um mau comportamento do mapeamento consecutivo,
revelando o grande potencial de mapeamentos com base no critério de Distribuição
39
de Trânsito.
O estudo de Jeannot et al. (2012) sobre o escalonamento de tarefas em
aplicativos paralelos trata principalmente a questão do algoritmo de escalonamento
em aplicativos paralelos a fim de permitir uma execução rápida e confiável, porém ao
se aumentar a confiabilidade geralmente implica em aumentar o tempo de execução.
O objetivo principal do seu artigo, que trata sobre a otimização do desempenho e da
confiabilidade em sistemas paralelos heterogêneos, através de algoritmos de
aproximação e heurísticas, é principalmente fornecer uma compreensão profunda do
problema bi-objetivo: makespan vs. confiabilidade, onde makespan é definido como
o menor tempo de execução possível de um processo com várias tarefas.
Casanova et al. (2010) elaborou em seu artigo “On cluster resource allocation
for multiple parallel task graphs” um estudo de um modelo de programação off-line
de PTGs múltiplas, ou múltiplos Gráficos de Tarefas Paralelas, fazendo uma
comparação entre vários algoritmos propostos para paralelização e alocação de
recursos de um cluster. Segundo Casanova et al. (2010), a principal contribuição
deste trabalho foi uma comparação de todos os algoritmos abordados. Esta
comparação foi feita através de simulações ao longo uma grande variedade de
cenários representativos, utilizando três métricas relacionadas ao desempenho e/ou
imparcialidade.
Diante das pesquisas apresentadas a respeito do escalonamento de tarefas em
sistemas paralelos, observa-se que este problema não é simples de ser solucionado,
principalmente de forma automatizada, devendo, portanto, enquanto não exista uma
solução de escalonamento automatizado simples, realizar um planejamento de
distribuição de carga de processamento equilibrada entre os nós de processamento
da arquitetura paralela.
3.1.3 – Escalabilidade
Quando se trata de melhoria de desempenho de execução em processos e
tarefas, aplicando-se paralelismo, uma importante questão deve ser tratada: a
escalabilidade, ou seja, a capacidade de se adicionar novos componentes de
processamento sem a necessidade de alteração do aplicativo, capaz de possibilitar
um ganho de performance e diminuição do tempo total de execução.
Afek et al. (2012), em seu artigo, propõe um algoritmo que trata além do
bloqueio de concorrência, mas também a melhoria da escalabilidade. A sua
40
implementação do método size() do Java TM apresenta alta escalabilidade, levando
a crer que este é um bom candidato para a substituição da atual implementação do
método size() no pacote JavaTM principalmente para programação paralela.
Conforme já citado anteriormente, Afek et al. (2012) conseguiu um grande progresso
e coerência das propriedades, combinado com a alta escalabilidade em seu novo
algoritmo.
Um algoritmo também é proposto para melhorar a escalabilidade e a
generalização para diferentes números de processadores e tamanhos de dados por
Chen e Poirier (2010) em seu artigo “Parallel implementation of an efficient
preconditioned linear solver for grid-based applications in chemical physics. III:
Improved parallel scalability for sparse matrix-vector products”. Eles trouxeram à
tona a questão dos solucionadores de problemas envolvendo grandes matrizes
esparsas, nas áreas de química, física e outras. As causas da baixa escalabilidade
do paralelismo foram identificadas e reparadas através da introdução de um
antibloqueio para comunicações ponto a ponto entre pares de nós apropriados,
proporcionando uma melhor escalabilidade e generalização.
Levando-se em conta a revisão bibliográfica a respeito da escalabilidade, este
ainda é um problema específico de cada ambiente e cada aplicativo, não sendo
apresentada nenhuma solução efetiva para o problema.
Assim, após o levantamento de alguns dos principais problemas relacionados
ao paralelismo, verifica-se que, muito ainda deve ser evoluído, até que se atinja um
nível interessante de soluções para os atuais problemas. Desta maneira, no capítulo
seguinte apresenta-se um conjunto de técnicas que visa proporcionar uma utilização
mais proveitosa deste tipo de arquitetura, evitando-se alguns erros comuns e
proporcionando avanços nesta área.
41
4 – TÉCNICA PROPOSTA
4.1 – Considerações Iniciais
A proposta é conceber uma técnica para incentivar e melhorar a utilização das
arquiteturas paralelas pelos pesquisadores, principalmente desenvolvedores de
softwares científicos, que não possuem um conhecimento avançado em técnicas de
Engenharia de Software.
Diante dos principais problemas levantados na bibliografia acadêmica, a
apresentação de uma técnica com o objetivo de proporcionar uma utilização
facilitada do desenvolvimento de softwares paralelos e, consequentemente, um
melhor aproveitamento das arquiteturas de processamento paralelo e distribuído,
torna-se relevante. Além do levantamento bibliográfico relatado nos capítulos 2 e 3,
o desenvolvimento deste conjunto de técnicas levou em consideração o trabalho
proposto de Foster (1995), que propõe uma metodologia de modelagem e
construção de softwares paralelos, chamada de metodologia PCMA, baseada em
quatro passos principais, Particionamento, Comunicação, Agregação de Tarefas e
Mapeamento.
Inicialmente, a proposta desenvolvida na presente dissertação limita-se a
apresentação de técnicas simples para proporcionar o incentivo inicial ao uso do
paralelismo em aplicativos científicos, não almejando proporcionar grandes
melhorias no processo desenvolvimento dos algoritmos paralelos, mas sim a
facilitação do uso do paralelismo, com qualidade, para a comunidade científica e
acadêmica. Esta técnica nada mais é do que a sistematização de algumas tarefas a
serem lembradas e executadas durante o desenvolvimento de um algoritmo que
permita
o
paralelismo
em
sua
execução,
permitindo
assim
um
melhor
aproveitamento da arquitetura paralela.
A criação de uma técnica para produção de software para máquinas ou
ambientes paralelos irá basicamente acrescentar à Engenharia de Software algumas
estruturas especiais, com o objetivo principal de criar, com facilidade, novos
processos paralelos. Estes processos paralelos podem ser, por exemplo, as
iterações de um vetor executadas ao mesmo tempo, operações aritméticas, ou
tratamento de números.
Lembrando que um mesmo problema possui diversas maneiras diferentes de
42
ser solucionado, a técnica proposta neste trabalho pode ser interessante em
diversos casos, mas, ainda assim, podem haver casos em que esta técnica não será
proveitosa, o que somente será revelado a partir da utilização e validação da
mesma.
4.2 – Proposta para uma Engenharia de Software paralelo
A proposta a ser apresentada a seguir foi subdividida em duas etapas,
primeiramente a etapa de identificação e, em seguida, a etapa de definição. Ambas
serão tratadas a seguir.
4.2.1 – Etapa de identificação
O primeiro passo ao se definir uma técnica para facilitar o desenvolvimento de
softwares paralelos será conhecer o algoritmo e o aplicativo como um todo que será
desenvolvido, pois, tendo por objetivo proporcionar a utilização do paralelismo ou
melhorar o seu uso em softwares, caso o aplicativo não possa ser paralelizado, a
utilização desta técnica torna-se, obviamente, irrelevante.
Um software paralelizável é aquele em que algumas ou todas as tarefas
realizadas pelo software podem ser executadas ao mesmo tempo, de forma
independente, sem que o resultado final seja alterado. Segundo Manacero (2010),
devem ser identificadas as dependências e fazer a paralelização quando,
comprovadamente, existirem trechos de códigos com a lógica independente.
Um exemplo de aplicação paralelizável é o cálculo da energia potencial de
cada uma das diferentes conformações de uma molécula, que determina aquela de
menor energia potencial. Ou outro exemplo, mais simples, é a realização de uma
soma de um conjunto de números. Ambos os exemplos citados acima podem ser
calculados parcialmente, acumulando-se os resultados obtidos, para que ao final do
processo se tenha um objetivo alcançado, ou resultado final.
Assim, o usuário da técnica deverá fazer uma crítica ao seu aplicativo, a fim de
identificar possíveis situações em que sua aplicação poderá ser executada em
paralelo, desde cálculos aritméticos ou outros processos que sejam independentes.
Caso o usuário não identifique nenhum paralelismo em sua aplicação, esta técnica
43
não se aplica.
Após a verificação da possibilidade de paralelização da aplicação, segue-se
com a identificação e a documentação de todos os pontos paralelizáveis da
aplicação, conforme pode ser verificado na Figura 7.
Figura 7: Etapa de identificação do aplicativo.
A identificação dos pontos de paralelização, que serão laços (loops), métodos
de operações aritméticas ou métodos de iterações com dados, será utilizada para se
definir a necessidade real de uma melhoria no algoritmo. Caso não exista uma
quantidade significativa de pontos de paralelização, a execução do aplicativo não
consuma grande quantidade de recursos de processamento ou o paralelismo não
represente uma grande parte do consumo de recursos, a aplicação da técnica não é
aconselhada;
caso
contrário,
a
identificação
destes
pontos
servirá
como
documentação para a etapa de codificação.
Após a identificação do aplicativo a ser desenvolvido, o próximo passo será a
identificação do ambiente em que o aplicativo será executado.
Segundo Tanenbaum (2002), ao se começar o estudo de um sistema de
computação paralela, três aspectos básicos devem ser levados em consideração:
A natureza, o tamanho e a quantidade de seus elementos de
processamento;
A natureza, o tamanho e a quantidade de seus elementos de memória;
Como os elementos de processamento e os elementos de memória
estão interconectados.
Então, seguindo as definições de Tanenbaum (2002), nesta etapa são
identificadas as arquiteturas ou natureza do ambiente onde os processos serão
44
executados, a capacidade de processamento e o tipo e quantidade de memória
disponível, representado no primeiro passo da Figura 8.
Figura 8: Etapa de identificação do ambiente.
No atual estágio da pesquisa, as naturezas do ambiente que serão consideradas
serão Multicores, Cluster, Grid Computing e Cloud Computing. Os conceitos destas
arquiteturas já foram abordados anteriormente no item 2.3 do Capítulo 2.
A identificação da natureza, na maioria dos casos, permitirá a identificação do
tipo de memória, que pode ser compartilhada ou independente (Figura 8). A
identificação do tipo de memória será relevante principalmente para a definição do
modelo de controle e das granularidades a serem adotadas, que serão abordados
mais a frente.
A memória compartilhada normalmente é encontrada em ambientes multicores,
e são memórias onde vários nós de processamento acessam o mesmo endereço de
memória. Neste tipo de ambiente é muito importante o cuidado com a sincronização
entre os processos em execução paralela com o objetivo de se evitar conflitos entre
as threads. Porém, nestes, a paralelização automatizada torna-se mais viável devido
à uniformidade dos núcleos de processamento, facilitando assim o escalonamento
das tarefas, pois não haverá distribuição de cargas diferentes entre os nós de
processamento e controle de acesso à memória. (SILVA et al., 2009)
Podem acontecer casos de memórias compartilhadas distribuídas, onde nós de
45
processamento localizados em máquinas diferentes compartilham suas memórias
entre os diversos nós. Este tipo de configuração acontece principalmente em
Computação de Alto Desempenho, como Clusters de computadores, e normalmente
é implementada através de software, onde um middleware é responsável por manter
a comunicação entre os nós para manter a memória compartilhada atualizada e
consistente. Nestes casos, o cuidado com a sincronização também deve acontecer e
nem sempre esta configuração de ambiente é interessante devido ao alto nível de
controle e tráfego de dados. (SIQUEIRA, 2012)
Já os ambientes de processamento paralelo com memória independente ou
memória distribuída favorecem principalmente a escalabilidade e o controle de
conflitos. São caracterizados pela independência entre as memórias de cada nó de
processamento, ou seja, cada nó possui a sua própria memória. São comumente
encontrados em Clusters e Grids e devem ter como ponto principal a atenção à
alocação dos recursos e mapeamento das tarefas. (CASANOVA et al., 2010)
Podem acontecer casos em que a memória distribuída não se encontra
necessariamente em outro espaço físico, estando apenas logicamente distribuída.
Nestes casos, os endereços de memória são divididos de tal forma que cada nó de
processamento acessa o seu próprio endereço de memória. Este tipo de
configuração não é muito utilizado, pois pode permitir que espaços de memoria
fiquem ociosos.
Netto et al. (2011) propõe em suas pesquisas uma técnica de co-alocação de
recursos com reescalonamento iterativo de tarefas com base em previsões de
desempenho. Esta seria uma ótima opção para a minimização do problema de
alocação de recursos, mas em se tratando de desenvolvedores pesquisadores, o
que pode ser sugerido neste ponto é a tentativa de previsão de capacidade de
processamento de cada nó e a alocação do recurso de forma manual. Quando se
possui uma homogeneidade de elementos de processamento e memória, a
distribuição dos processos pode ser feita de forma homogênea, mas quando existe
uma desproporcionalidade entre os nós, o melhor a se fazer é direcionar maiores
cargas de trabalho aos nós com maior capacidade de processamento.
O tamanho e a quantidade de elementos de processamento e memória se
torna relevante para dimensionar a necessidade de melhorias na concepção e
elaboração do software. Por exemplo, um cálculo de somatório simples com poucos
números pequenos não se caracteriza como uma aplicação interessante de se ter a
46
técnica proposta aplicada, onde a melhoria do tempo de processamento não será
significativa. Manacero (2010) faz uma análise a respeito da viabilidade de
implantação do paralelismo, onde cita que cada grão ou nó de processamento deve
ter uma boa capacidade de execução para valer a pena fazer a distribuição de carga
entre estes nós de processamento, isto levando-se em conta a carga de tarefas a
serem executadas e a sobrecarga de comunicação entre elas.
Outro problema relacionado a paralelismo que foi encontrado recorrentemente
na bibliografia atual foi a questão da escalabilidade, abordada por Afek et al. (2012)
e Chen e Poirier (2010). Para os casos, onde se torna necessária a escalabilidade,
recomenda-se uma nova análise do algoritmo com o objetivo de dimensionar
corretamente o ambiente disponível e o aplicativo a ser desenvolvido.
4.2.2 – Etapa de definição
Após a primeira etapa de identificação do ambiente e do aplicativo a ser
desenvolvido, começa a etapa de definição das características do aplicativo a ser
implementado.
Para a definição do modelo de controle, a arquitetura da memória, abordada
anteriormente, é um dos principais fatores que deve ser levado em consideração,
conforme pode ser observado na Figura 9 abaixo.
Figura 9: Definição do modelo de controle.
47
Quando se desenvolve um software paralelo pode-se definir por uma única
linha de controle, ou seja, existirá apenas um programa em execução com um único
controlador ou sequenciador de instruções, e vários conjuntos de dados a serem
processados de forma paralela. Este tipo de modelo de controle deve ser
implementado em arquiteturas de memória compartilhada, pois o controle de
conflitos será facilitado pelo controle central do software.
Pode-se definir também por um software paralelo com suporte a várias linhas
de controle, onde cada linha de controle possui seus próprios registradores e
variáveis locais, sendo melhor implementado em arquiteturas de memória
independentes. Porém, esta decisão é fortemente influenciada pela sobrecarga de
código que deve gerado. Portanto, para pequenas aplicações, não é aconselhado o
uso de mais de uma linha de controle.
A granularidade em softwares paralelos é um ponto bastante polêmico, pois
existem diversos níveis de paralelismo que podem ser adotados, mas, neste caso, a
granularidade será categorizada em cinco níveis diferentes, abordando desde uma
granularidade mais grossa, que representa o paralelismo em nível de processos ou
programas, até um paralelismo mais fino, no nível de instruções, conforme a Figura
10.
Figura 10: Níveis de granularidade.
Os níveis de granularidade do paralelismo a serem adotados em um software
devem ser definidos principalmente segundo a capacidade de comunicação entre os
48
nós de processamento, ou seja, quanto melhor a comunicação, mais rápidas as
conexões, mais fino deverá ser o nível de granularidade adotada. Porém, sempre se
atentando para as dependências levantadas entre os processos.
O nível mais fino de granularidade que pode ser trabalhado pelo programador é
o nível de instruções, ideal para sistemas fortemente acoplados, com mínima
distância física ou redes de conexão de alta velocidade. Cada instrução ou bloco de
instruções são delegados aos nós de processamento, conforme a disponibilidade.
Em um nível acima, se tem o paralelismo em loops e iterações, onde a maioria
dos programadores consegue trabalhar facilmente com o paralelismo, e tem seu uso
preferencial sempre que existe um bom meio de conexão entre os nós de
processamento. Este é nível de granularidade mais aconselhável em casos onde o
desenvolvedor não se possui grande destreza programação paralela, pois facilita o
controle de sincronismo evitando bloqueios ou locks de processamento.
Em um nível de granularidade um pouco mais grossa, pode-se desenvolver os
procedimentos e as rotinas em paralelo. Neste nível, visa-se a utilização dos nós
sem maior sobrecarga da conexão entre eles.
Para conexões um pouco mais lentas e distâncias físicas significativas entre
os nós de processamento, propõe-se o paralelismo em subprogramas, partes de
processos ou partes de programas. Este nível de granularidade já ocorre em
aplicativos com mais de uma linha de controle, pois cada uma destas realiza o seu
controle interno e um subprograma principal realiza a sincronização.
Manacero (2010) diz: “Se a velocidade no recebimento de novos dados for
menor do que a capacidade de processamento, então não se deve aumentar o grau
de paralelismo (aumentaria a ociosidade dos elementos de processamento)”.
Portanto, se não possuir um meio de conexão com velocidade minimamente
razoável, não é interessante a utilização do paralelismo com granularidades mais
grossas. O nível de granularidade mais grossa, proposto nesta técnica, ocorre
quando se aplica o paralelismo em processos ou programas, e assim serão
implementados com varias linhas de controle do processo.
Após a definição da granularidade a ser aplicada, o próximo item a se definir na
implementação do paralelismo é a forma de comunicação entre os nós de
processamento, e neste ponto, a conexão entre os elementos de memória e os
elementos de processamento é considerada como um fator determinante na
qualidade do paralelismo desenvolvido.
49
O método de comunicação entre os nós de processamento é definido
principalmente a partir da granularidade adotada. Foram identificados dois tipos de
comunicação padrões, apresentados na Figura 11. No primeiro, a troca de
mensagens é utilizada em processos paralelizados com granularidade mais grossa,
devido às baixas taxas de comunicação entre os elementos de processamento e em
ambiente com memórias independentes, onde o processo de controle das variáveis
torna-se mais complexo. O outro método é a utilização de variáveis compartilhadas
que é ideal para sistemas implementados com granularidade fina de paralelismo, ou
sistemas fortemente acoplados, com pouca distância física entre os elementos de
processamento ou com conexões de alta velocidade entre eles, e, principalmente,
arquiteturas de memórias compartilhadas, o que facilita o controle destas variáveis,
uma vez que todos os elementos de processamento acessam os mesmos endereços
de memória onde estão as variáveis do aplicativo.
Figura 11: Métodos de comunicação.
Após as definições dos métodos de comunicação, alguns cuidados devem ser
abordados quando se desenvolve aplicações paralelas. Alguns processos paralelos
devem, além de se comunicar, ter uma sincronia entre eles, pois nestes casos o
resultado final depende da finalização de todos os processos. A sincronia é que
define que os processos paralelos foram realizados por completo e corretamente.
Sugere-se, então, a documentação dos pontos críticos de sincronia a serem
verificados durante o desenvolvimento do aplicativo (Figura 12).
Como já mencionado no Capítulo 3, Stivala et al. (2010) sugere a criação de
uma hashtable onde são listados cada processo paralelo a ser executado e
50
sincronizado, minimizando as falhas de sincronismo, como, por exemplo, os
bloqueios, também conhecidos como locks, que acontecem principalmente em
programas paralelos de memoria compartilhada. Outras técnicas para controle de
sincronismo também foram citadas na revisão bibliográfica mas apresentam níveis
de complexidade maior para desenvolvimento e, por isso, não foram incluídas nesta
proposta, como, por exemplo o desenvolvimento de um algoritmo livre de bloqueios
baseado em snapshot, como Afek (2012).
Figura 12: Sincronia e plano de testes.
Após a sincronia, como em qualquer desenvolvimento de software, deve-se
desenvolver o plano de testes daquele software a fim de garantir a qualidade e a
confiabilidade do software desenvolvido (Figura 12).
Para Myers (2004), não se pode garantir que todo software funcione
corretamente, sem a presença de erros, visto que os mesmos muitas vezes
possuem um grande número de estados, com fórmulas, atividades e algoritmos
complexos. Assim, há princípios vitais para o teste de software. Para o plano de
teste da proposta, sugere-se a criação de, no mínimo, um plano de testes para cada
ponto de paralelismo identificado. Este plano de teste deves ser baseado em
técnicas tradicionais de teste, conforme Myers (2004). O caso de teste deve definir a
saída esperada, de forma a reduzir a interpretação do critério de sucesso. A saída da
execução do teste deve ser exaustivamente analisada. Os casos de teste devem
verificar não somente as condições inválidas de execução, como também as
condições válidas. Outro conceito apresentado é utilizar pessoas e organizações
diferentes para a implementação e para a verificação. Tudo isso com o único objetivo
que minimizar os erros de concepção e implementação do software.
Após a definição da proposta, com o conjunto de técnicas citadas acima, para o
51
desenvolvimento e aplicação de paralelismo em aplicativos científicos, sugere-se, na
próxima seção, a utilização de um documento que tem por objetivo facilitar a
utilização da técnica proposta.
4.2.3 – Documento de identificação de paralelismo
Após o levantamento e elaboração da técnica, propõe-se um documento com o
objetivo de suportar e auxiliar a identificação e documentação do paralelismo em
aplicativos científicos, servindo como artefato de documentação da técnica proposta.
Este documento deve ser preenchido durante a concepção do aplicativo com o
intuito de documentar e proporcionar um aproveitamento melhor dos pontos de
paralelismo na aplicação.
Documento de Identificação de Paralelismo
1. Identificação da aplicação:
1.1. Nome:
1.2. Versão:
1.3. Data de produção:
1.4. Linguagem de Desenvolvimento:
1.5. Ambiente de Desenvolvimento:
1.6. Existem pontos de paralelização na aplicação?
2. Objetivo:
(Descrever o principal objetivo deste documento de identificação de paralelismo adequado a cada
caso de utilização)
3. Descrição:
(Descrever com detalhes como este arquivo se organiza e a proposta de como os objetivos serão
alcançados)
4. Identificação do ambiente de execução:
4.1. Natureza: (Arquitetura do ambiente de execução. Ex: Cloud Computing, Multicore, etc)
4.2. Capacidade de processamento: (Quantidade e velocidade de núcleos de
processamento disponíveis)
4.3. Tipo de memória (Compartilhada ou Independente):
4.4. Tamanho e quantidade de memória:
52
5. Modelo de controle do aplicativo:
(Descrever o modelo de controle que será utilizado no aplicativo em desenvolvimento, podendo ser
com uma linha de controle ou varias linhas de controle).
6. Identificação dos pontos de paralelismo:
(Identificar cada ponto de paralelismo e definir a granularidade a ser adotada em cada um deles)
Ponto de paralelismo 01:
Granularidade:
7. Definição do método de comunicação e sincronismo:
(Para cada ponto de paralelismo – Definir o método de comunicação a ser adotado: Variáveis
compartilhadas ou troca de mensagens)
Ponto de paralelismo 01:
Método de comunicação e sincronismo:
8. Definição dos pontos críticos de sincronia:
(Para cada ponto de paralelismo – Definir a criticidade do sincronismo)
Ponto de paralelismo 01:
Nível de criticidade:
9. Definição de um plano de testes:
(Para cada ponto de paralelismo apresentar um caso de testes)
Ponto de paralelismo 01:
Caso de teste: (Os casos de testes devem ser documentados seguindo os padrões de
desenvolvimento de software)
4.3 – Visão geral da técnica proposta
Em sua concepção final, pode-se ter uma visão geral da técnica proposta,
apresentada separadamente nas figuras 7, 8, 9, 10, 11 e 12, por meio do diagrama
da Figura 13, a seguir.
53
Figura 13: Visão geral da técnica proposta.
54
5 – DESENVOLVIMENTO
Após a definição da técnica, segue-se para a parte de implantação com o
propósito de iniciar sua verificação e validação. Para isso foi definido um escopo
levando-se em consideração as condições de desenvolvimento do projeto.
A linguagem para desenvolvimento escolhida foi o Java, devido à facilidade de
acesso ao ambiente de desenvolvimento desta linguagem e à abrangência da
utilização, proporcionando vasta fonte de pesquisa.
As arquiteturas propostas para implantação, Multicore, Grid Computing, Cluster
e Cloud Computing, foram escolhidas levando-se em conta que são as principais
arquiteturas, de processamento distribuído, utilizadas amplamente na comunidade
acadêmica e científica. Multicore já se trata de uma arquitetura amplamente
difundida e consolidada, já presente na maioria dos computadores inclusive
computadores pessoais. O Grid Computing é uma das arquiteturas de alto
desempenho e baixo custo já também bastante difundido. O Cloud Computing é uma
nova tendência de baixo custo que vem se expandindo a cada dia. E, por fim, o
Cluster é a mais tradicional forma de arquitetura paralela. Apesar de ter algumas
limitações como linguagens e softwares de gerenciamento, é a arquitetura paralela
mais robusta existente nos dias atuais.
Além da ampla utilização, outro fator importante na escolha destes ambientes
escolhidos foi a facilidade de acesso para a realização dos testes.
Finalmente, para a implantação e verificação da proposta foi utilizado o
algoritmo de cálculo do número PI abordado a seguir.
5.1 – Aplicação escolhida
O número PI é o valor da razão entre a circunferência de qualquer círculo e seu
diâmetro, e também é a mais antiga constante matemática que se conhece
(SILVEIRA, 2000). Apesar dessa antiguidade, ele ainda é fonte de pesquisas em
diversas áreas, o PI é um dos poucos objetos estudados pelos antigos gregos, há
mais de 2000 anos, que ainda continua sendo pesquisado. A maior parte dessas
pesquisas centra-se no estudo das propriedades de PI e na invenção de novos
55
métodos para calcular seu valor.
O número PI é calculado pela expressão abaixo:
O cálculo do valor de PI foi escolhido devido a sua escalabilidade,
proporcionada pelo número de iterações utilizadas para o cálculo, variando assim a
precisão do resultado obtido. Desta maneira, pode-se sobrecarregar o cálculo de
acordo
com
o
interesse
do
pesquisador,
proporcionando
maior
precisão
proporcionalmente ao número de iterações. Além disso, as iterações realizadas para
o cálculo podem ser executadas de forma independente ou em blocos, e
sincronizadas quando todas tiverem terminado.
5.2 – Implementação
Abaixo é apresentado o código em Java que foi implementado para calcular o
número PI. Primeiramente é apresentada a Classe CalculoPI, onde são feitos os
cálculos individuas das iterações. O desenvolvimento dos códigos para testes foi
baseado no artigo de Serta (2008).
import java.util.concurrent.Callable;
public class CalculoPI implements Callable<Double> {
private double inicio;
private double fim;
public CalculoPI(double inicio, double fim) {
this.inicio = inicio;
this.fim = fim;
}
public Double call() throws Exception {
double valor = 0.0;
for (double i=inicio; i <= fim; i++) {
valor += Math.pow(-1.0, i + 1) / (2.0 * (double)i - 1.0);
}
return valor;
}
}
56
A classe apresentada no código acima representa somente o núcleo do cálculo
a ser executado, onde um método, sub-rotina ou um subprograma pode chamar o
método call() para executar o número desejado de iterações. Quanto maior o
número de iterações, maior será a precisão do resultado do número PI.
A sincronia final para o resultado do cálculo ocorre no momento em que todos
as iterações ou blocos de iterações finalizam seus cálculos. Todos os resultados são
somados e multiplicados por 4 (quatro), chegando ao resultado final do número de
PI calculado. Conforme o exemplo abaixo:
ExecutorService es = Executors.newCachedThreadPool();
// separa o cálculo em 4 partes definindo o valor de n inicial e final para cada
uma
Future<Double>
Future<Double>
Future<Double>
Future<Double>
parte1
parte2
parte3
parte4
=
=
=
=
es.submit(new
es.submit(new
es.submit(new
es.submit(new
CalculoPI(1, 1000000000));
CalculoPI(1000000001, 2000000000));
CalculoPI(2000000001, 3000000000));
CalculoPI(3000000001, 4000000000));
// agrupa os valores calculados das 4 partes e multiplica por 4
double pi = 4.0 * (parte1.get() + parte2.get() + parte3.get() +parte4.get());
String resposta = "Valor calculado de PI é:" + pi;
Durante a execução, foram criadas várias versões do aplicativo com a
separação das iterações em números variados de blocos, e em diferentes níveis de
granularidade, além de outras alterações que serão abordadas a seguir, com o
objetivo de analisar os resultados obtidos.
5.3 – Métricas de software
Para a correta avaliação da qualidade de um software alguns autores propõem
métricas de software. As métricas de software, do ponto de vista de medição, podem
ser divididas em duas categorias: medidas diretas e indiretas. São consideradas
como medidas diretas do processo de Engenharia de Software, o custo e o esforço
aplicados no desenvolvimento e manutenção do software, a quantidade de linhas de
código produzidas e o total de defeitos registrados durante um determinado período
57
de tempo. Ainda como medidas diretas da qualidade do software produzido existem
as já tradicionais, velocidade de execução e gasto de memória. Porém, a
funcionalidade do software ou a sua capacidade de manutenção são mais difíceis de
serem avaliadas e em sua maioria só podem ser medidas de forma indireta.
(CORDEIRO, 2009)
Neste projeto, a validação baseou-se principalmente na medição direta do
tempo de execução total do aplicativo. Em alguns casos, também foram possíveis as
medições de tempo de execução por nó de processamento e tempo de sincronismo.
Devido às limitações de tempo de implantação e dificuldades encontradas na
montagem e preparação dos ambientes de testes, não foi possível uma coleta maior
de dados, com outras métricas. Mas, ainda assim, os resultados levantados
permitiram constatar indícios da eficácia da técnica proposta, proporcionando
ganhos de desempenho na execução do aplicativo.
5.4 – Implantação em Multicore
Para a aplicação da técnica proposta e execução dos testes em arquitetura
multicore foi utilizado um computador de uso pessoal, com processador Intel Core 2
Duo e 4GB de memória RAM.
Inicialmente, propôs-se a execução de um código para cálculo de PI
completamente sem refinamentos e sem programação paralela, seguindo um padrão
de concepção de software tradicional, sem se preocupar com o paralelismo. Em
seguida foi gerada uma versão do algoritmo com aplicação de paralelismo, porém
sem refinamentos e sem utilização da técnica proposta. Estas execuções têm por
objetivo gerar dados comparativos a serem utilizados confrontando com os
resultados obtidos através da implementação do algoritmo baseando-se no conjunto
de técnicas propostas.
A seguir, apresenta-se o documento da aplicação seguindo as técnicas de
desenvolvimento propostas Este artefato tem por objetivo colaborar com a
documentação geral do software, principalmente em sua manutenibilidade,
atentando-se especificamente para os pontos de paralelismo.
58
5.4.1 - Documento de Identificação de Paralelismo
Documento de Identificação de Paralelismo
1. Identificação da aplicação:
1.1. Nome: Algoritmo de Cálculo de PI - Multicore
1.2. Versão: 1.4
1.3. Data da última alteração: 26/11/2012
1.4. Linguagem de Desenvolvimento: Java Web
1.5. Ambiente de Desenvolvimento: Eclipse Juno
1.6. Existem pontos de paralelização na aplicação? Sim
2. Objetivo:
Documentar o desenvolvimento do aplicativo científico, Cálculo de PI, que
possui pontos de paralelismo, facilitando a implementação e manutenção do
código fonte, e proporcionando o acesso a este conhecimento a toda
comunidade acadêmica.
3. Descrição:
Inicialmente, este documento se propõe a identificar e descrever o aplicativo,
cálculo de PI, e o ambiente de execução em que será implementado o
algoritmo proposto, no caso o ambiente Multicore. Em seguida documentar os
pontos de paralelismo e propor alguns modelos de implementação com foco
principal no aproveitamento do paralelismo disponível nos ambientes Multicore.
4. Identificação do ambiente de execução:
4.1. Natureza: Multicore
4.2. Capacidade de processamento: 2.1GHz CPU (Core 2 Duo)
4.3. Tipo de memória (Compartilhada ou Independente): Compartilhada.
4.4. Tamanho e quantidade de memória: 4GB RAM 800MHz
5. Modelo de controle do aplicativo:
Uma linha de controle.
59
6. Identificação dos pontos de paralelismo:
Ponto de paralelismo 01: Iterações de cálculo de PI. (4.000.000.000)
Granularidade: Fina – nível de loops e iterações.
Nesta arquitetura definiu-se pelo nível de granularidade fina, ou seja, as iterações
do cálculo de PI foram divididas em blocos de execução paralelos, optando-se por
uma divisão em 40 (quarenta) blocos de iterações. (Chegou-se a este valor após
algumas execuções de testes com números aleatórios de blocos de iterações).
Obs.1: Neste algoritmo, a proposta de paralelismo se aplica na divisão das iterações para o cálculo
do número PI. As iterações podem ser divididas em blocos e quando cada um dos blocos finalizar o
seu cálculo, os resultados são somados e multiplicados por 4.
Obs.2: Este nível de granularidade foi definido devido ao único ponto de paralelismo e ao ambiente
de Multicore ser fortemente acoplado, estando todos os nós de processamento totalmente
interligados dentro de uma mesma máquina.
7. Definição do método de comunicação e sincronismo:
Ponto de paralelismo 01: Iterações de cálculo de PI.
Método de comunicação e sincronismo: Variáveis compartilhadas.
Obs.: Devido ao alto acoplamento da arquitetura multicore e à baixa complexidade do algoritmo e
do controle das variáreis compartilhadas, optou-se pela utilização das variáveis compartilhadas.
8. Definição dos pontos críticos de sincronia:
Ponto de paralelismo 01: Ao final dos cálculos dos blocos de iterações, os valores
devem ser somados para a finalização do cálculo.
Nível de criticidade: Alto.
Obs.: Devido ao fato deste ser o único ponto de sincronismo da aplicação e poder invalidar os
resultados obtidos através do cálculo realizado, o nível de criticidade de sincronismo é considerado
alto.
9. Definição de um plano de testes:
Ponto de paralelismo 01: Iterações de cálculo de PI.
Casos de teste 01: Teste do valor final de PI.
Resumo: Comparar o valor de PI calculado com paralelismo e o valor de PI
calculado sem paralelismo.
Pré-condições: Algoritmo disponível para execução.
Entradas: Número de iterações para cálculo de PI = 4.000.000.000
60
Ação: Executar o cálculo de PI com paralelismo e sem paralelismo.
Pós-condições: Os valores de PI calculados em ambos os algoritmos devem ser
iguais ou bem próximos, com pequena variação devido a falhas na precisão dos
cálculos.
5.4.2 – Implementação
O desenvolvimento dos códigos foi baseado no artigo de Serta (2008),
conforme citado anteriormente, mantendo-se a classe base CalculoPI.
Logo abaixo é apresentado um trecho do código da aplicação com melhorias
proporcionadas pela utilização da técnica proposta, atentando-se para o nível de
granularidade e para a sincronização. As iterações foram divididas em blocos
equivalentes e então submetidas ao método de criação de tarefas de cálculo de PI a
serem executadas em paralelo. Ao final, é feita a junção dos cálculos, ou seja, os
resultados são sincronizados para o cálculo do resultado final.
...
// Criação das tarefas particionadas a serem executadas.
Double inicio = 1.0;
// Calcula o tamanho do passo de cada tarefa através do numero de partes
// (Partes: Número de blocos de iterações para o calculo de PI)
Double passo = 4000000000.0 / Integer.parseInt(partes);
Double fim = passo;
System.out.println("Numero de passos: " + partes + " - Passo: " + passo);
// Loop de criação das tarefas
while (fim < 4000000001.0) {
job.addTask(new TemplateJPPFTask(inicio, fim));
System.out.println("Tarefa: (" + inicio + ", " + fim + ")");
inicio = inicio + passo;
fim = fim + passo;
}
...
// Trecho de código onde é chamada a classe base CalculoPI()
// Inicia contagem de tempo para métrica
long ti = System.currentTimeMillis();
CalculoPI calc= new CalculoPI(this.inicio, this.fim);
// Chamada de execução do calculo de PI para o bloco de iteração definido
// acima
Double parte = calc.call();
61
// Seta o resultado para ser sincronizado ao final da execução
setResult(parte);
// Finaliza contagem de tempo
long tf = System.currentTimeMillis();
...
// Sincronização dos valores calculados pelas partes e impressão do resultado
double pi = 4.0 * (double) (processExecutionResults(results));
String resposta = "Valor calculado de PI é " + pi;
Durante a execução dos testes, o aplicativo foi executado com separação dos
blocos de iterações em diversos números de divisão até se chegar aos valores
apresentados abaixo, além da execução sem implementação de paralelismo no
código.
Primeiramente, o aplicativo foi executado com separação dos blocos de
iterações em granularidade mais grossa, ou seja, com grandes blocos de iterações.
O total de iterações foi dividido em apenas 2 (duas) partes (mesmo número de
núcleos de processamento disponíveis), representando a versão do algoritmo com
paralelismo, mas sem refinamentos. Em seguida, o aplicativo foi executado com
separação dos blocos de iterações em 40 (quarenta) partes, representando uma
granularidade mais fina, própria para o ambiente proposto. Com estes valores de
divisões dos blocos de iterações, os resultados obtidos puderam ser comparados,
conforme apresentados posteriormente, no Capítulo 6.
5.5 – Implantação em Grid Computing
5.5.1 – Grid Computing com JPPF Grid.
Para implantação em Grid Computing foi utilizado um software de
gerenciamento de Grid chamado JPPF Grid. O JPPF Grid permite a criação de
trabalhos com listas de tarefas a serem executados. Estes trabalhos são gerados e
configurados pelo cliente e enviados ao servidor, o JPPF Server, que distribui as
tarefas aos nós disponíveis, conforme a configuração do administrador. A arquitetura
de funcionamento do JPPF Grid pode ser observada na Figura 14 abaixo. (JPPF,
2012).
62
Figura 14: Estrutura do Grid JPPF
Fonte: Adaptado de JPPF (2012)
5.5.2 - Documento de Identificação de Paralelismo
A seguir apresenta-se o documento de identificação de paralelismo criado para
o desenvolvimento da versão do aplicativo Cálculo de PI com aplicação das técnicas
propostas especificas para Grid Computing. Além da versão com a aplicação da
técnica, foram desenvolvidas versões do aplicativo com aplicação de paralelismo,
mas sem aplicação da técnica proposta e sem aplicação explícita do paralelismo no
código fonte.
Documento de Identificação de Paralelismo
1. Identificação da aplicação:
1.1. Nome: Algoritmo de Cálculo de PI - Grid Computing JPPF
1.2. Versão: 1.5
1.3. Data de produção: 30/11/2012
1.4. Linguagem de Desenvolvimento: Java Web
1.5. Ambiente de Desenvolvimento: Eclipse Juno
1.6. Existem pontos de paralelização na aplicação? Sim
2. Objetivo:
Documentar o desenvolvimento do aplicativo científico, cálculo de PI, que
63
possui pontos de paralelismo, facilitando a implementação e manutenção do
código fonte, e proporcionando o acesso a este conhecimento a toda
comunidade acadêmica.
3. Descrição:
Este documento se propõe a identificar e descrever o aplicativo, Cálculo de PI
para ambiente de Grid, e o ambiente de execução em que será implementado
o algoritmo proposto, Grid de computadores utilizando o JPPF Grid. Em
seguida, documentar os pontos de paralelismo e propor alguns modelos de
implementação com foco principal no aproveitamento do paralelismo disponível
nos ambientes de Grid Computing.
4. Identificação do ambiente de execução:
4.1. Natureza: Grid Computing
4.2. Capacidade de processamento:
Grid Computing com 6 computadores disponíveis, não dedicados:
Um computador Core I5 com 8Gb de memória RAM;
Dois computadores Core 2 Duo com 4Gb de memória RAM;
Um computador Core 2 Quad com 4Gb de memória RAM;
Dois computadores Core 2 VPro com 4Gb de memória RAM;
4.3. Tipo de memória (Compartilhada ou Independente): Independente.
4.4. Tamanho e quantidade de memória: Descritos acima.
Obs.1: Devido aos Computadores não serem de processamento dedicado exclusivamente às
tarefas do Grid, podem ocorrer pequenas variações momentâneas nas medidas de tempo.
5. Modelo de controle do aplicativo:
Uma linha de controle.
Obs.1: Optou-se pelo desenvolvimento de uma linha de controle devido à simplicidade do
algoritmo proposto, pelo relativo baixo custo computacional e pela maior complexidade e custo em
tempo do desenvolvimento com distribuição de várias linhas de controle.
6. Identificação dos pontos de paralelismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI. (4.000.000.000)
Granularidade: Média – nível de procedimentos e sub-rotinas; e Fina - nível de
64
loops e iterações.
Para este ambiente, as iterações foram divididas em blocos de granularidade mais
grossa (número de nós de processamento) através de procedimentos e
submetidas aos nós de processamento. Em seguida, foram novamente
subdivididas em uma granularidade mais fina (número de partes X 4) para se
aproveitar o paralelismo do multicore de cada nó. Quando cada um dos blocos
finaliza o seu cálculo, os resultados são repassados ao nó central que realiza a
sincronização dos resultados e soma dos resultados de cada bloco.
Obs.1: Este nível de granularidade foi definido devido ao único ponto de paralelismo e ao ambiente
de Grid possuir um baixo acoplamento, com redes de baixa velocidade de conexão entre os nós de
processamento. Em processos com maiores cargas de dados e custo de processamento,
recomenda-se um nível de granularidade ainda maior, evitando grande quantidade de tráfego na
rede.
7. Definição do método de comunicação e sincronismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Método de comunicação e sincronismo: Troca de Mensagens.
Obs.: A troca de mensagens favorece a comunicação em arquiteturas paralelas que possuem links
de comunicação de baixa velocidade entre os nós de processamento.
8. Definição dos pontos críticos de sincronia:
Ponto de paralelismo 01: Ao final dos cálculos dos blocos de iterações, os valores
devem ser somados para a finalização do cálculo.
Nível de criticidade: Alto
Obs.: Devido ao fato deste ser o único ponto de sincronismo da aplicação e poder invalidar os
resultados obtidos através do cálculo realizado, o nível de criticidade de sincronismo é considerado
alto.
9. Definição de um plano de testes:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Casos de teste 01: Teste do valor final de PI.
Resumo: Comparar o valor de PI calculado utilizando-se paralelismo com técnica e
65
o valor de PI calculado sem paralelismo.
Pré-condições: Algoritmo disponível para execução.
Entradas: Número de iterações para cálculo de PI = 4.000.000.000
Ação: Executar o cálculo de PI com paralelismo e sem paralelismo.
Pós-condições: Os valores de PI calculados em ambos os algoritmos devem ser
iguais ou bem próximos, com pequena variação devido a falhas na precisão dos
cálculos.
5.5.3 – Implementação
Na implementação para Grid Computing, foram disponibilizados 6 (seis) nós de
execução, conforme descritos no documento de identificação de paralelismo, onde o
gerenciador do Grid (JPPF) é quem define, através de algoritmos internos de
verificação de disponibilidade, quantas e quais tarefas são enviadas para cada nó.
Em relação ao código fonte gerado, a classe base do algoritmo CalculoPI,
manteve-se a mesma, baseada no artigo de Serta (2008), com o objetivo de se
manter o mesmo resultado final dos cálculos. A principal atenção ao aplicar a técnica
proposta durante o desenvolvimento do código ocorreu em relação à granularidade,
à comunicação entre os nós de processamento e ao sincronismo.
Foram apresentados 2 (dois) níveis de granularidades a serem aplicados no
mesmo algoritmo com o objetivo de aproveitar não somente o paralelismo
proporcionado pelo Grid, mas também o paralelismo dos múltiplos núcleos de cada
nó de processamento (Multicore). Primeiramente, propôs-se um nível de
granularidade mais grossa (equivalente ao número de nós de processamento),
criando-se procedimentos e sub-rotinas independentes, com o objetivo de aproveitar
o poder de processamento do Grid. Os blocos de iterações então foram repassados
aos nós e novamente subdivididos em uma granularidade mais fina (número de
partes X 4) para se aproveitar o paralelismo de cada nó.
A comunicação entre os nós de processamento foi realizada basicamente
utilizando-se mensagens, com o objetivo de se preservar o sincronismo e minimizar
o risco perda ou sobrescrita de dados.
66
Abaixo, segue o trecho de código fonte principal da implementação em Grid
que cria a tarefa que é repassada aos nós de processamento. Pode-se perceber que
a tarefa é dividida em 6 (seis) partes independentes, número de nós de
processamento, que são sincronizadas ao final da tarefa.
public TemplateJPPFTask(double inicio, double fim) {
...
// CALCULO DE PI
Double passo = (Double)(this.fim - (this.inicio - 1)) / 4;
// Cria um pool de threads para realizar o calculo
ExecutorService es = Executors.newCachedThreadPool();
Double i = this.inicio;
Double f = (this.inicio - 1) + passo ;
Future<Double> parte1 = es.submit(new CalculoPI(i,f));
i = this.inicio + passo;
f = (this.inicio - 1) + (2 * passo);
Future<Double> parte2 = es.submit(new CalculoPI(i,f));
i = this.inicio + (2 * passo) ;
f = (this.inicio - 1) + (3 * passo);
Future<Double> parte3 = es.submit(new CalculoPI(i,f));
i = this.inicio + (3 * passo) ;
f = (this.inicio - 1) + (4 * passo);
Future<Double> parte4 = es.submit(new CalculoPI(i,f));
i = this.inicio + (4 * passo) ;
f = (this.inicio - 1) + (5 * passo);
Future<Double> parte5 = es.submit(new CalculoPI(i,f));
i = this.inicio + (5 * passo) ;
f = (this.inicio - 1) + (6 * passo);
Future<Double> parte6 = es.submit(new CalculoPI(i,f));
Double parte = (parte1.get() + parte2.get() + parte3.get() + parte4.get() +
parte5.get() + parte6.get());
setResult(parte);
}
...
Durante a implementação do aplicativo, foram criadas versões com a
separação dos blocos de iterações em 20 (vinte) partes equivalentes, considerada
como a versão sem técnica de paralelismo aplicada, representando uma
granularidade média de paralelismo, sem levar em consideração o ambiente de
execução do aplicativo. Foi desenvolvida, também, uma versão do aplicativo sem
67
implementação de paralelismo, para servir como base de comparação com os
resultados das outras versões do aplicativo, quais sejam, a versão com a aplicação
da técnica proposta e a versão com paralelismo sem técnica.
5.6 – Implantação em Cluster
No processo de implantação do Cluster para testes, foram utilizados os
equipamentos do Departamento de Computação do CEFET-MG, discriminados no
item 4 da seção 5.6.2. Inicialmente, foi realizada uma tentativa de instalação da
distribuição Pelican do Sistema Operacional Linux, um sistema com gerenciamento
de Cluster já pré-instalado. No entanto, não se obteve sucesso nos testes, uma vez
que esta distribuição era executada diretamente a partir do CD, sendo necessárias
algumas alterações no sistema operacional para o correto funcionamento no
ambiente.
A partir de pesquisas na internet, foi encontrada a Distribuição Rocks do Linux,
que segundo as informações disponibilizadas em seu site (Rocks, 2013), atenderia
às demandas do projeto. A única alteração necessária ao projeto foi a utilização da
linguagem C com o OpenMPI, necessária para a execução paralela de aplicativos no
Cluster Rocks.
5.6.1 – Cluster com Rocks
O Rocks é uma distribuição Linux open-source de Cluster que permite aos
usuários finais construir facilmente clusters computacionais. Devido à facilidade de
montagem, centenas de pesquisadores de todo o mundo tem usado o Rocks para
implantar seu próprio Cluster de computadores. Segundo o grupo Rocks (2013), este
projeto é conduzido desde maio de 2000, abordando as dificuldades da implantação
de clusters gerenciáveis, e tendo como objetivo a montagem de clusters de maneira
fácil, ou seja, fácil de implantar, gerenciar, atualizar e escalar. O grupo Rocks ajuda a
disponibilizar o poder computacional dos clusters a uma ampla gama de usuários
científicos. Consequentemente, é evidente que estas arquiteturas estáveis e
gerenciáveis de computação paralela, disponíveis para uma ampla gama de
68
cientistas, ajudarão imensamente a melhorar o estado da arte em ferramentas
paralelas.
5.6.2 - Documento de Identificação de Paralelismo
Documento de Identificação de Paralelismo
1. Identificação da aplicação:
1.1. Nome: Algoritmo de Cálculo de PI - Cluster
1.2. Versão: 1.5
1.3. Data de produção: 30/01/2013
1.4. Linguagem de Desenvolvimento: C / OpenMPI
1.5. Ambiente de Desenvolvimento: Linux
1.6. Existem pontos de paralelização na aplicação? Sim.
2. Objetivo:
Documentar o desenvolvimento do aplicativo científico, Cálculo de PI, que
possui pontos de paralelismo, facilitando a implementação e manutenção do
código fonte, e proporcionando o acesso a este conhecimento a toda
comunidade acadêmica.
3. Descrição:
Este documento se propõe a identificar e descrever o aplicativo, cálculo de PI
para ambiente de Cluster de computadores, e o ambiente de execução, Cluster
de computadores, em que será implementado o algoritmo proposto. Em
seguida, documentar os pontos de paralelismo e propor alguns modelos de
implementação com foco principal no aproveitamento do paralelismo disponível
nos ambientes de Cluster de computadores.
4. Identificação do ambiente de execução:
4.1. Natureza: Cluster de Computadores
4.2. Capacidade de processamento:
- 1 (um) nó principal (Cluster Frontend) - Intel(R) Xeon(R) CPU E5506 2.13GHz
(8 cores) / 40Gb RAM.
- 3 (três) nós de processamento (Cluster Node) - Intel(R) Xeon(R) CPU E5506
69
2.13GHz (8 cores) / 32Gb RAM.
- 3 (três) nós de processamento (Cluster Node) - Intel(R) Xeon(R) CPU E5506
2.13GHz (8 cores) / 48Gb RAM.
4.3. Tipo de memória (Compartilhada ou Independente): Cada Nó de
processamento possui sua memória independente.
4.4. Tamanho e quantidade de memória: Descritos acima.
5. Modelo de controle do aplicativo:
Uma linha de controle.
Obs.1: Optou-se pelo desenvolvimento de uma linha de controle devido à simplicidade do
algoritmo proposto, pelo relativo baixo custo computacional e pela maior complexidade e custo em
tempo do desenvolvimento com distribuição de várias linhas de controle.
6. Identificação dos pontos de paralelismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI. (4.000.000.000)
Granularidade: Média/Fina – nível de procedimentos e sub-rotinas;
Adotou-se neste ambiente um nível de granularidade média / fina de
implementação do paralelismo. As iterações foram divididas em blocos de média
granularidade e submetidas aos nós de processamento através de métodos
próprios do OpenMPI. Quando todos os blocos finalizam o seu cálculo, os
resultados são repassados ao nó central que realiza o sincronismo e a exibição
dos resultados.
Obs.1: Este nível de granularidade ideal para este tipo de arquitetura é exatamente a soma do
número de núcleos de processamento disponíveis, pois devido ao alto acoplamento, à grande
uniformidade entre os nós de processamento e a altíssima velocidade de comunicação, a
distribuição entre os nós de processamento quase não se diferencia da distribuição entre os
núcleos.
7. Definição do método de comunicação e sincronismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Método de comunicação e sincronismo: Troca de Mensagens.
Obs.: A troca de mensagens torna-se necessária nesta arquitetura, Cluster de computadores
utilizando OpenMPI, devido ao padrão de comunicação do OpenMPI e devido ao fato das memória
serem independentes.
70
8. Definição dos pontos críticos de sincronia:
Ponto de sincronia 01: Leitura do número de iterações a serem distribuídas. No
inicio do processamento, todas as contagens de tempo devem ser sincronizadas e
iniciadas somente após a leitura do número de iterações a serem realizadas. Este
ponto deve ser sincronizado para que as threads de processamento não iniciem a
contagem do tempo sem receber nenhum valor. Nível de criticidade: Baixo
Ponto
de
sincronia
02:
Final
dos
cálculos
dos
blocos
de
iterações.
Ao final dos cálculos dos blocos de iterações os valores de resultado de cada um
dos blocos devem ser somados para a finalização correta do cálculo. Nível de
criticidade: Alto
Obs.: Devido ao fato do ponto de sincronismo 02 da aplicação poder invalidar os resultados
obtidos através do cálculo realizado, o nível de criticidade deste sincronismo é considerado alto.
9. Definição de um plano de testes:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Casos de teste 01: Teste do valor final de PI.
Resumo: Comparar o valor de PI calculado com paralelismo e o valor de PI
calculado sem paralelismo.
Pré-condições: Algoritmo disponível para execução.
Entradas: Número de iterações para cálculo de PI = 4.000.000.000
Ação: Executar o cálculo de PI com paralelismo e sem paralelismo.
Pós-condições: Os valores de PI calculados em ambos os algoritmos devem ser
iguais ou bem próximos, com pequena variação devido a falhas na precisão dos
cálculos.
5.6.3 – Implementação
Na implementação para Cluster de computadores foram disponibilizados 6
(seis) nós de processamento e 1 (um) nó central, que não foi utilizado para
processamento, conforme descritos no Item 4.2 do documento de identificação de
paralelismo, Seção 5.6.2. O ambiente do Cluster utilizado foi o Rocks Cluster
71
Distribution, uma distribuição Linux que suporta o paralelismo através do OpenMPI.
Devido à dificuldade de se encontrar um ambiente de Cluster de fácil
montagem e gerenciamento com suporte a Java, optou-se pelo desenvolvimento do
algoritmo em C, com OpenMPI.
O código completo da implementação pode ser verificado a seguir:
#include
#include
#include
#include
#include
<stdio.h>
<stdlib.h>
<mpi.h>
<math.h>
<time.h>
double tempo(){
struct timeval tv;
gettimeofday(&tv,0);
return tv.tv_sec + tv.tv_usec/1e6;
}
int main(int argc, char *argv[]) {
int done = 0, myid, numprocs;
unsigned int i, rc, n;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x, a;
double t1, t2, t_min,t3;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
int namelen;
char processor_name[MPI_MAX_PROCESSOR_NAME];
MPI_Get_processor_name(processor_name,&namelen);
while (!done){
// Realiza a leitura do número de iterações a serem executadas
if (myid == 0) {
printf("Entre com o numero de intervalos desejados:
(0 finaliza) ");
fflush(stdout);
scanf("%d",&n);
}
// Sincroniza todos os processos no mesmo ponto até a leitura .
MPI_Barrier(MPI_COMM_WORLD);
// Inicializa a contagem do tempo
t1 = tempo();
printf("Processo %d em %s de %d\n",myid, processor_name,
numprocs);
72
// printf("Tempo T1: %lf %d\n",t1,myid);
// Broadcast das tarefas para os nós de processamento
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
if (n == 0) break;
h = 1.0 / (double) n;
sum = 0.0;
// Loop do calculo de PI
for (i = myid + 1; i <= n; i += numprocs) {
x = h * ((double)i - 0.5);
sum += 4.0 / (1.0 + x*x);
}
mypi = h * sum;
// Agrupa todos os valores calculados
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,
MPI_COMM_WORLD);
// Contagem do tempo final
t2 = tempo();
//printf("T2: %lf %d\n",t2,myid);
//printf("T2-T1: %lf %d\n",t2-t1,myid);
fflush(stdout);
// Procura o menor tempo inicial para o calculo do tempo total
MPI_Bcast(&t1, 1, MPI_INT, 0, MPI_COMM_WORLD);
// Sincroniza todos os processos para exibir a resposta
MPI_Barrier(MPI_COMM_WORLD);
// Leitura do tempo final total
t3=tempo();
// Sincroniza o calculo do menor tempo inicial
MPI_Reduce(&t1, &t_min, 1, MPI_DOUBLE, MPI_MIN, 0,
MPI_COMM_WORLD);
// Exibe o resultado final
if (myid == 0) {
printf("PI e aproximadamente %.18f, Com um erro de
%.18f\n", pi, fabs(pi - PI25DT));
printf("Tempo gasto: %lf \n",(t3 - t_min));
}
}
MPI_Finalize();
}
73
Para a realização dos testes, foi desenvolvida uma funcionalidade de divisão
dinâmica do processamento, definida pelo usuário em tempo de execução. Esta
funcionalidade tem por objetivo observar, pela comparação de vários resultados, o
comportamento da aplicação no ambiente proposto em diferentes níveis de
granularidade. Ainda foram feitos testes de speed-up através da inclusão gradativa
de nós de processamento ao Cluster. Os resultados obtidos podem ser observados
no próximo capítulo.
5.7 – Implantação em Cloud Computing
Para implantação do algoritmo em arquitetura de Cloud Computing foi utilizado
um prestador deste tipo de serviço na internet, o site jelastic.com, e foi desenvolvida
uma aplicação em Java Web para ser testada neste ambiente. Devido a atual
tendência de popularização do Cloud Computing, e pela sua característica de
fornecer serviços e infraestrutura sob demanda, foram encontrados prestadores
deste tipo de serviço com certa facilidade na web, mas foi escolhido o Jelastic devido
ao período de testes gratuito oferecido.
5.7.1 - Cloud Computing com Jelastic.com
O sistema de Cloud Computing do Jelastic oferece infraestrutura para
hospedagem de servidores sob demanda na internet, e ainda oferece uma conta
para testes sem cobrança de valores sobre os serviços utilizados pelo período de
duas semanas, a qual foi utilizada neste projeto. A conta utilizada para testes no
Cloud Computing Jelastic.com (http://jelastic.com) possui a seguinte configuração
disponível:
•
3 aplicações simultâneas;
•
8 tipos de servidores de aplicação diferentes;
•
16 cloudlets (2 GB) por servidor de aplicação (Cada cloudlet corresponde a
128MB RAM e 200MHz CPU);
•
1 GB de armazenamento de dados;
•
As aplicações são desativadas automaticamente após 48hs de inatividade.
74
5.7.2 - Documento de Identificação de Paralelismo
Documento de Identificação de Paralelismo
1. Identificação da aplicação:
1.1. Nome: Algoritmo de Cálculo de PI - Cloud Computing Jelastic.com
1.2. Versão: 2.0
1.3. Data de produção: 02/11/2012
1.4. Linguagem de Desenvolvimento: Java Web
1.5. Ambiente de Desenvolvimento: Eclipse Juno
1.6. Existem pontos de paralelização na aplicação? Sim
2. Objetivo:
Documentar o desenvolvimento do aplicativo científico, Cálculo de PI, que
possui pontos de paralelismo, facilitando a implementação e manutenção do
código fonte, e proporcionando o acesso a este conhecimento a toda
comunidade acadêmica.
3. Descrição:
Inicialmente, este documento se propõe a identificar e descrever o aplicativo,
cálculo de PI para ambiente de Cloud Computing, e o ambiente de execução,
no caso o Cloud Computing da Jelastic.com, em que será implementado o
algoritmo proposto. Em seguida, documentar os pontos de paralelismo e propor
alguns modelos de implementação com foco principal no aproveitamento do
paralelismo disponível nos ambientes de Cloud Computing.
4. Identificação do ambiente de execução:
4.1. Natureza: Cloud Computing
4.2. Capacidade de processamento: 3.2GHz CPU (16 cloudlets)
4.3. Tipo de memória (Compartilhada ou Independente): Não identificado.
4.4. Tamanho e quantidade de memória: 2GB RAM (16 cloudlets)
5. Modelo de controle do aplicativo:
Uma linha de controle.
75
6. Identificação dos pontos de paralelismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI. (4.000.000.000)
Granularidade: Média – nível de procedimentos e sub-rotinas.
Na aplicação do algoritmo no ambiente de Cloud Computing, a proposta de
paralelismo se aplica na divisão das iterações para o cálculo do número PI. As
iterações podem ser divididas em blocos de média granularidade, utilizando-se
procedimento, e quando cada um dos blocos finalizar o seu cálculo, os resultados
são sincronizados e exibidos.
Obs.1: Este nível de granularidade foi definido devido ao único ponto de paralelismo e ao ambiente
de Cloud ser fortemente acoplado, com redes de alta velocidade de conexão entre os nós de
processamento.
7. Definição do método de comunicação e sincronismo:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Método de comunicação e sincronismo: Variáveis compartilhadas.
Obs.: Devido à baixa complexidade do algoritmo e do controle das variáreis compartilhadas, optouse pela utilização das variáveis compartilhadas.
8. Definição dos pontos críticos de sincronia:
Ponto de paralelismo 01: Ao final dos cálculos dos blocos de iterações, os valores
devem ser somados para a finalização do cálculo.
Nível de criticidade: Alto
Obs.: Devido ao fato deste ser o único ponto de sincronismo da aplicação e poder invalidar os
resultados obtidos através do cálculo realizado, o nível de criticidade de sincronismo é considerado
alto.
9. Definição de um plano de testes:
Ponto de paralelismo 01: Divisão das iterações de cálculo de PI.
Casos de teste 01: Teste do valor final de PI.
Resumo: Comparar o valor de PI calculado com paralelismo e o valor de PI
calculado sem paralelismo.
Pré-condições: Algoritmo disponível para execução.
Entradas: Número de iterações para cálculo de PI = 4.000.000.000
76
Ação: Executar o cálculo de PI com paralelismo e sem paralelismo.
Pós-condições: Os valores de PI calculados em ambos os algoritmos devem ser
iguais ou bem próximos, com pequena variação devido a falhas na precisão dos
cálculos.
5.7.3 – Implementação
Mantendo-se o desenvolvimento dos códigos com base no artigo de Serta
(2008), apresentado na Seção 5.2, a Classe base do projeto, CalculoPI, não foi
alterada.
Para a realização dos testes, foi desenvolvida uma funcionalidade de divisão
do processamento dinâmica, definida pelo usuário, em tempo de execução. Esta
funcionalidade tem por objetivo observar, pela comparação de vários resultados, o
comportamento da aplicação no ambiente proposto, uma vez que a idéia do Cloud
Computing propõe transparência ao usuário final, ou seja, não se apresenta a real
arquitetura entre os nós de processamento.
77
6 – RESULTADOS OBTIDOS
Neste capitulo serão apresentados os resultados obtidos em cada uma das
implantações realizadas apresentando as observações após a aplicação da técnica
em cada um dos ambientes. Ao final, uma avaliação geral englobando todas as
implantações é apresentada.
6.1 – Multicore
A seguir são apresentados os resultados da execução do algoritmo.
Primeiramente, os resultados sem a utilização de paralelismo (Tabela 2),
acreditando-se somente na capacidade de paralelismo gerenciado pelo sistema
operacional.
Tabela 2: Tempo de execução sem paralelismo – Arquitetura Multicore.
Valor de PI
Tempo (s)
1 Núcleo
3.1415926533379395
233,170
2 Núcleos
3.1415926533379395
200,086
Em seguida, são apresentados os resultados do algoritmo com iterações
divididas em 2 (duas) partes, ou blocos de iterações, equivalentes (Tabela 3). Para o
desenvolvimento deste algoritmo não foi utilizada a técnica proposta e, portanto, não
se atentou para a granularidade adequada para a arquitetura. Adotou-se uma
granularidade grossa para a arquitetura proposta, com passos ou blocos de
iterações muito grandes.
Tabela 3: Tempo de execução com paralelismo sem técnica – Arquitetura Multicore.
Valor de PI
Tempo (s)
1 Núcleo
3.1415926533380767
211,873
2 Núcleos
3.1415926533380767
128,751
Finalmente são apresentados os resultados do algoritmo utilizando-se baixa
granularidade, com quarenta blocos de iterações equivalentes (Tabela 4).
Utilizando-se o conjunto de técnicas propostas para esta aplicação, conforme o
78
documento acima, chegou-se aos resultados abaixo. O principal fator de melhoria
proporcionada ao aplicativo, além do paralelismo em si, que proporciona ganhos
significativos de velocidade de processamento, é a atenção à granularidade
adequada ao conjunto aplicativo e ambiente de execução.
Para a aplicação através da técnica proposta identificou-se a necessidade de
uma granularidade fina, obtendo-se ganhos de desempenho conforme pode ser visto
abaixo.
Tabela 4: Tempo de execução com aplicação da técnica proposta – Arquitetura Multicore.
Valor de PI
Tempo (s)
1 Núcleo
3.141592653339327
190,207
2 Núcleos
3.141592653339327
124,747
Observações após a aplicação da técnica proposta
Abaixo, na Tabela 5, se pode observar os resultados compilados dos testes
realizados, e tem-se uma visão geral através da Figura 15, onde são apresentadas
as curvas de performance observadas nos experimentos.
Tabela 5: Comparativo de valores de tempo de execução – Arquitetura Multicore.
1 núcleo
2 núcleos
Sem paralelismo
233,170
200,086
Paralelismo sem técnica
211,873
128,751
Paralelismo com Técnica
190,207
124,747
.
Figura 15: Gráfico comparativo de performance – Arquitetura Multicore.
79
Observa-se, pela Figura 15 acima, que os ganhos de desempenho foram
significativos com a utilização do paralelismo sem aplicação de técnicas específicas
na implementação. Percebe-se, ainda, que estes ganhos de desempenho foram
maiores através de uma concepção bem elaborada do aplicativo paralelo, conforme
pode ser observado pela Figura 15, onde ocorre uma diminuição do tempo de
execução do aplicativo através da implementação do paralelismo utilizando a técnica
proposta.
A Figura 16, a seguir, apresenta um gráfico com o Speed-up alcançado com a
utilização e sem a utilização da técnica proposta no ambiente Multicore, controlandose a quantidade de recursos disponíveis, um ou dois núcleos de processamento.
Figura 16: Gráfico comparativo de Speed-up – Arquitetura Multicore.
6.2 – Grid Computing
A seguir são apresentados os resultados da execução do algoritmo de cálculo
de PI no ambiente de Grid Computing. Conforme a Tabela 6 abaixo, pode-se ver os
valores calculados de PI, além dos tempos de execução em Grids com 2 até 6 nós
de processamento disponíveis, além do tempo de execução de versões do aplicativo
sem aplicação de paralelismo, com paralelismo mas sem técnica e com paralelismo
aplicando as técnicas propostas.
80
Tabela 6: Resultados da execução cálculo de PI em arquitetura Grid Computing.
2 nós
3 nós
4 nós
5 nós
6 nós
3.1415926533 3.1415926533 3.1415926533 3.1415926533 3.1415926533
379395
379395
379395
379395
379395
Valor de PI
Tempo sem paralelismo (s)
Tempo com paralelismo
sem técnica (s)
Tempo com paralelismo
com técnica (s)
174,461
181,105
178,426
178,513
173,059
73,986
71,159
54,720
31,610
48,689
52,024
34,44
28,384
22,721
28,466
Observações após a aplicação da técnica proposta
Com a execução do algoritmo, foram alcançados os seguintes valores para
comparação e análise. A Tabela 7 mostra os valores separados por número de nós
de processamento utilizados, além do tempo de sincronismo gasto nas aplicações
com paralelismo. As oscilações do tempo de sincronismo podem ser percebidas
devido às diferenças de capacidade de processamento entre os nós de
processamento e ao fato dos nós não serem de dedicação exclusiva à execução das
tarefas do Grid.
Tabela 7: Comparativo de valores de tempo de execução – Arquitetura Grid Computing.
2 nós
3 nós
4 nós
5 nós
6 nós
Sem paralelismo
174,461
181,105
178,426
178,513
173,059
Paralelismo sem técnica
73,986
71,159
54,720
31,610
48,689
Tempo de sincronismo
Paralelismo com Técnica (N x N x 4)
9,997
0,040
0,062
0,069
0,068
52,024
34,44
28,384
22,721
28,466
0,005
1,995
0,053
0,064
0,015
Tempo de sincronismo
N x N x 4 = Número de nós X Número de partes X 4
Observa-se,
pela
Figura
17,
um
ganho
de
performance
constante,
comparando-se os tempos de execução do aplicativo implementado sem
paralelismo, do aplicativo implementado com paralelismo mas sem utilização das
técnicas propostas e do aplicativo implementado utilizando o conjunto de técnicas
propostas para desenvolvimento de software paralelo. E, independente da
configuração do Grid, com diferentes números de nós disponíveis, os ganhos de
desempenho no processamento foram significativos.
81
Figura 17: Gráfico comparativo de performance – Arquitetura Grid Computing.
Figura 18: Gráfico comparativo de Speed-up – Arquitetura Grid Computing.
Na Figura 18, percebe-se que os ganhos de Speed-up não foram lineares e
constantes. Tal fato se justifica pelo fato dos nós de processamento não terem
capacidades de processamento idênticas e não serem máquinas dedicadas
exclusivamente ao aplicativo em questão. Ainda assim, observa-se ganhos
interessantes de desempenho considerando apenas o comparativo entre 2 (dois) e 5
(cinco) nós de processamento.
82
6.3 – Cluster de Computadores
Na implantação específico para o ambiente de Cluster, utilizando o Rocks, foi
desenvolvida uma versão do aplicativo de cálculo de PI que permitiu a sua execução
com diferentes números de divisões de blocos de iterações a serem submetidos
para processamento.
A seguir, estão apresentados os valores de tempo de execução do algoritmo,
em segundos, separados por número de nós de processamento (máquinas
disponíveis no Cluster) e por número de blocos de iterações, após a aplicação da
técnica proposta (Tabela 8).
Tabela 8: Comparativo de valores de tempo de execução detalhado – Arquitetura Cluster.
Número de
blocos de
iterações
1 Máquina
no Cluster
2 Máquinas
no Cluster
3 Máquinas
no Cluster
4 Máquinas
no Cluster
5 Máquinas
no Cluster
6 Máquinas
no Cluster
1
2
3
4
8
16
24
32
40
48
56
80
99,819
50,050
33,663
25,391
12,523
12,688
12,544
12,763
12,838
12,547
12,534
12,573
99,819
50,007
33,573
25,258
12,737
6,272
6,916
6,813
7,027
7,500
7,090
7,499
99,819
50,678
33,788
25,149
12,717
6,450
6,057
6,741
7,529
7,824
7,226
6,299
99,819
50,021
33,341
25,009
12,744
6,354
4,239
4,824
4,675
4,822
5,283
5,114
99,819
50,010
33,296
24,998
12,507
6,353
6,336
6,071
4,325
5,616
6,331
5,173
99,819
49,927
33,342
25,007
12,506
6,392
5,808
5,250
4,516
4,206
4,578
4,268
Com a aplicação da técnica proposta, foi verificado que o número de blocos de
iterações ideal para cada configuração do ambiente de Cluster Rocks condiz com a
multiplicação do número de núcleos de processamento disponíveis pelo número de
máquinas disponíveis para processamento no Cluster. Isto ocorre, principalmente,
devido ao alto acoplamento presente na estrutura do Cluster, à grande uniformidade
entre os nós de processamento (todos os nós de processamento são equipamentos
quase idênticos com pequenas variações em relação à quantidade de memória) e à
altíssima velocidade de comunicação entre os nós, resultando na distribuição de
tarefas entre os nós de processamento ser muito semelhante distribuição entre os
núcleos de processamento.
83
Observações após a aplicação da técnica proposta
Após a execução dos testes chega-se à tabela de resultados comparativos,
Tabela 9:
Tabela 9: Comparativo de valores de tempo de execução – Arquitetura Cluster.
1 nó
2 nós
3 nós
4 nós
5 nós
6 nós
Sem paralelismo
99,819
99,819
99,819
99,819
99,819
99,819
Paralelismo sem técnica
12,573
7,499
6,299
5,114
5,173
4,268
Paralelismo com Técnica
12,523
6,272
6,057
4,824
4,325
4,206
Para a aplicação sem paralelismo, foram verificados os valores de tempo de
execução do algoritmo com apenas 1 (um) bloco de iteração no cálculo de PI. Para o
paralelismo aplicado sem técnica, foram verificados os tempos de execução do
algoritmo com 80 (oitenta) blocos de iterações, ou seja, com uma granularidade
muito fina para o ambiente proposto, segundo os levantamentos realizados. E para a
aplicação do paralelismo com técnica, adotou-se a análise do número de núcleos
disponíveis em cada ambiente proposto, de 1 (um) a 6 (seis) nós de processamento,
multiplicando-se o número de núcleos (oito em cada nó) pelo número de nós,
resultando em 8 (oito), 16 (dezesseis), 24 (vinte e quatro), 32 (trinta e dois), 40
(quarenta) e 48 (quarenta e oito) blocos de iterações.
Com base nestes valores, chega-se ao gráfico de comparativo de performance
abaixo (Figura 19), que ilustra melhor o ganho de performance obtido através da
correta utilização da granularidade durante o desenvolvimento de aplicativos
paralelos, embora que, de fato, a melhoria obtida não tenha sido muito significativa,
ainda assim em todas as configurações percebe-se que que houve ganho de
performance.
84
Figura 19: Gráfico comparativo de performance – Arquitetura Cluster
Figura 20: Gráfico comparativo de Speed-up – Arquitetura Cluster.
Observa-se na Figura 20 o comparativo de Speed-up obtido com utilização da
técnica proposta para desenvolvimento do paralelismo e sem a aplicação da técnica
de paralelismo. É possível identificar que ocorreu melhoria de performance em todas
as configurações do ambiente, com diferentes números de nós de processamento,
sinalizando assim a eficácia da técnica proposta também para o ambiente de Cluster
de Computadores.
85
6.4 – Cloud Computing
A seguir são apresentados os resultados da execução do algoritmo de cálculo
de PI em ambiente de Cloud Computing. São apresentados os valores calculados de
PI, os tempos de execução sem aplicação de paralelismo e os tempos de execução
com aplicação de paralelismo, com particionamento dos blocos de iterações em
diferentes números (Tabela 10).
Observa-se que a execução da versão do aplicativo sem paralelismo mantevese com pequenas variações de tempo em todas as simulações realizadas.
Tabela 10: Resultados da execução cálculo de PI em arquitetura Cloud Computing.
Valor de PI
Tempo sem
paralelismo (s)
Tempo com
paralelismo (s)
Sem divisão
3.141592653
3379395
2 blocos
3.141592653
3380767
3 blocos
3.141592653
3380323
4 blocos
3.141592653
3380505
6 blocos
3.141592653
338632
8 blocos
3.141592653
339258
145,048
140,197
141,59
139,953
140,849
141,906
144,748
75,06
51,749
38,827
26,85
19,922
Observações após a aplicação da técnica proposta
Observa-se na Tabela 11 e no gráfico da Figura 21 que a arquitetura utilizada
para testes do Cloud Computing absorve muito bem a implementação e controle do
paralelismo, apresentando ganhos de performance bem interessantes à medida que
se aumenta a divisão das tarefas a serem executadas, ou seja, quanto menor ou
mais fina a granularidade do paralelismo implementado, maior será a performance
de processamento.
Tabela 11: Comparativo de valores de tempo de execução – Arquitetura Cloud Computing.
Número de blocos de iterações
Com paralelismo
Sem paralelismo
1
2
3
4
6
8
141,786
79,011
54,393
42,217
27,166
20,939
~140
86
Tempo de execução
Comparativo de variação da
Granularidade
160,000
140,000
120,000
100,000
80,000
60,000
40,000
20,000
0,000
Paralelismo
1 (Mais
grossa)
2
3
4
6
8 (Mais
fina)
Nível de Granularidade
Figura 21: Gráfico comparativo de variação de granularidade - Arquitetura Cloud Computing.
No caso desta arquitetura em especial, foi realizado este teste de variação de
granularidade para comprovar o aumento da eficiência do paralelismo conforme foi
se adequando a granularidade. Esta observação vai ao encontro do item proposto
na técnica de desenvolver aplicativos com paralelismo de baixa granularidade para
ambientes onde se possui alto acoplamento entre os nós de processamento.
Observa-se ainda, conforme se vê na figura abaixo (Figura 22), que uma
implementação de paralelismo sem se atentar para o ambiente de execução pode
significar perdas significativas de desempenho, que poderiam ser mantidas através
da utilização de técnicas mais controladas para a concepção do algoritmo a ser
desenvolvido, conforme proposto.
87
Tempo de execução
Gráfico comparativo de ganho de performance
com técnica aplicada - Cloud Computing
160,000
140,000
120,000
100,000
80,000
60,000
40,000
20,000
0,000
16 cloudlets
Sem
paralelismo
Paralelismo
sem Técnica
Paralelismo
com Técnica
Tipo de Algorítmo
Figura 22: Gráfico comparativo de performance – Arquitetura Cloud Computing.
Conforme já visto na revisão bibliográfica a respeito da arquitetura de Cloud
Computing, esta caracteriza-se pela transparência nos serviços disponibilizados e
por isso os testes foram limitados, não sendo possível a apresentação de métricas
de software mais elaboradas, como, por exemplo, as medições de tempo de
sincronia ou tempo de execução por nó de processamento. Não foi possível,
também, o teste de Speed-up, uma vez que o conceito do Cloud Computing defende
a alocação de recursos conforme a demanda, não sendo possível a manipulação da
capacidade de processamento. Entretanto, estas limitações não significaram a
impossibilidade de demonstrar sinais de eficiência da técnica proposta, conforme
mostrados nesta seção.
6.5 – Observações gerais
Diante das observações individuais das implantações citadas nos itens 6.1 até
6.4, os resultados foram consolidados no gráfico da Figura 23 que mostra os ganhos
de desempenho alcançados pela aplicação das técnicas propostas de paralelismo. A
Figura 23 abaixo tem caráter apenas qualitativo para se observar os resultados
gerais
de
cada
uma
das
arquiteturas,
mas
não
deve
comparativamente, devido às especificidades de cada uma delas.
ser
observado
88
Foram considerados os resultados dos ambientes com o máximo potencial
disponível, ou seja, com todos os nós de processamento disponíveis em
funcionamento em cada arquitetura.
Gráfico analítico de arquiteturas
250,000
Tempo (s)
200,000
150,000
Cloud
100,000
Multicore
50,000
Grid
Cluster
0,000
Sem paralelismo
Paralelismo sem
técnica
Paralelismo com
Técnica
Tipo de algoritmo
Figura 23: Comparativo entre o tempo de execução em diferentes arquiteturas
Assim verifica-se que a técnica proposta apresenta claros sinais de melhoria de
eficiência nos aplicativos desenvolvidos em todos os ambientes analisados, que
poderão ser validados com maior precisão através da sua utilização em pesquisas
científicas que envolvam implementações de aplicativos paralelos.
89
7 – CONCLUSÕES E CONSIDERAÇÕES FINAIS
Neste capítulo são apresentadas as conclusões deste trabalho, relatando suas
contribuições, dificuldades encontradas e perspectivas futuras.
7.1 – Conclusões, limitações e contribuições
Após o aprofundamento dos conhecimentos em computação e programação
paralela,
arquiteturas
paralelas
e
Engenharia
de
Software
aplicada
ao
desenvolvimento de software paralelo, verificou-se a necessidade de evolução das
técnicas de Engenharia de Software aplicadas ao ambiente paralelo como forma de
ganhos de desempenho e qualidade dos produtos de software científico produzidos.
Inicialmente, o levantamento do estado da arte da Engenharia de Software
Paralelo proporcionou um dimensionamento correto ao trabalho, definindo quais os
pontos da computação paralela deveriam ser focados, sendo estes, arquiteturas de
hardware específicas, técnicas de programação paralela, principais problemas
enfrentados durante a programação paralela e a própria Engenharia de Software
tradicional utilizada como base dos estudos.
No decorrer do desenvolvimento deste trabalho de pesquisa foi apresentada
uma proposta de técnicas de Engenharia de Software a serem utilizadas em
arquiteturas
especificamente
paralelas.
Esta
proposta
aborda
práticas
de
modelagem de software paralelo para proporcionar opções simples e eficazes de
documentação, para os pesquisadores utilizarem o modelo de programação paralela
em seus aplicativos, tornando-os mais eficientes, eficazes, e com código mais
compreensível, fácil de desenvolver e manter.
Através dos testes de implantação e da aplicação da técnica proposta, tornaramse perceptíveis os ganhos de velocidade de processamento dos aplicativos
desenvolvidos, indicando fortemente a vantagem de implantação das técnicas
propostas em processos de desenvolvimento de software paralelo. É possível
concluir ainda, que a disponibilização de uma documentação bem formatada e
90
coesa abordando claramente a implantação do paralelismo em um aplicativo
proporciona facilidade de implantação e manutenção do aplicativo.
Uma vez que seja perceptível uma melhoria na qualidade e reusabilidade dos
softwares produzidos, este modelo se torna um multiplicador para melhor utilização
dos ambientes multiprocessados disponíveis para pesquisas em todos os campos,
ampliando assim o conhecimento e evoluindo os estudos na área de Engenharia de
Software voltada para a computação paralela.
Durante o desenvolvimento do projeto algumas limitações foram enfrentadas,
conforme os itens a seguir:
- Diante do preceito de que a Engenharia de Software foi concebida para se
adaptar a qualquer tipo de arquitetura ou software, não existem muitas bibliografias
a respeito do caso específico abordado, qual seja, arquiteturas paralelas. O que
realmente motivou o desenvolvimento do projeto foram alguns artigos indicando a
necessidade de desenvolvimento de técnicas ou práticas especificas de Engenharia
de Software para desenvolvimento de aplicativos paralelos.
- Indisponibilidade de ambiente para aplicação da técnica em aplicativos
desenvolvidos para as arquiteturas específicas propostas inicialmente no projeto.
Para minimizar este problema, algumas arquiteturas foram montadas e adaptadas
especificamente para executar os aplicativos desenvolvidos como o caso do Grid
Computing, e a utilização de contas gratuitas para testes disponíveis na internet
como, por exemplo, o Cloud Computing.
- Indisponibilidade de pesquisadores para aplicação das técnicas propostas e a
consequente validação, mas ainda assim foram realizados testes de desempenho
com a medição de alguns valores que demonstram indícios da eficácia da técnica
proposta. A real validação da técnica proposta deverá acontecer a partir da utilização
da mesma por pesquisadores e, então, através da parametrização de valores e
métricas de Engenharia de Software, se conseguirá quantificar as vantagens
obtidas.
Após as conclusões e limitações discutidas acima, é importante agora
apresentar as principais contribuições da presente pesquisa, que são listadas a
seguir:
91
- Por meio de uma revisão sistemática nas principais bibliotecas digitais de
publicações disponíveis, foram analisados e descritos trabalhos científicos de
diferentes
autores
que
abordam
os
principais
problemas
relacionados
à
programação paralela.
- Foi disponibilizado para a comunidade acadêmica um conjunto de técnicas de
Engenharia de Software voltadas ao desenvolvimento de aplicações paralelas,
incentivando, facilitando e proporcionando esta evolução na qualidade dos softwares
produzidos principalmente por cientistas.
7.2 - Trabalhos Futuros
Como proposta de trabalhos futuros, a implantação da técnica apresentada em
trabalhos de pesquisa torna-se fundamental para a sua verificação e validação.
Sugere-se ainda a parametrização de um software de caráter científico a ser
executado nas arquiteturas abordadas, que são os Multicores, Grid, Cluster e Cloud
Computing, com o objetivo de gerar números comparativos. Ao final da implantação
o levantamento e documentação dos benefícios percebidos, através dos valores das
métricas de software parametrizados, possibilitarão a comparação e aprimoramento
da técnica proposta.
Como proposta de trabalhos futuros, o desenvolvimento de um conjunto de
técnicas de testes de softwares para aplicações paralelas e distribuídas torna-se
pertinente, uma vez que, acredita-se que este tipo de aplicação possui rotinas
diferentes de execução e maior dificuldade de implementação, devendo assim ser
desenvolvido um conjunto de técnicas específicas de testes.
Sugere-se ainda a aplicação e validação da técnica proposta, abordando não
somente softwares científicos, mas também softwares de caráter comercial, com a
finalidade de proporcionar ganhos de desempenho às diversas áreas que envolvem
processamentos de alto desempenho.
Por fim, pode-se propor também a investigação da adequação da técnica à
implementação HADOOP, uma plataforma de computação distribuída voltada para
Clusters e processamento de grandes massas de dados, que vem sendo utilizada
mundialmente em vários projetos. (APACHE SOFTWARE FOUNDATION, 2013).
92
8 – REFERÊNCIAS BIBLIOGRÁFICAS
AFEK, Y; Shavit, N; Tzafrir, M. 2012. Interrupting snapshots and the JavaTM size
method. Journal of Parallel and Distributed Computing, 72. 880–888.
ALECRIM, Emerson. 2012. O que é Cloud Computing (Computação nas
Nuvens)? 2011. Disponível em: <http://www.infowester.com /cloudcomputing.php>.
Acesso em: 22 fev. 2012.
ALLEN, Matthew D.; Sridharan, Srinath; Sohi, Gurindar S. 2009. Serialization sets:
a dynamic dependence-based parallel execution model. PPoPP '09 Proceedings
of the 14th ACM SIGPLAN symposium on Principles and practice of parallel
programming. Pages 85-96. ACM New York, NY, USA.
ALMEIDA Filho, Adauto Trigueiro. 2011. UM MAPEAMENTO SISTEMÁTICO DE
MECANISMOS PARA GUIAR ESTUDOS EMPÍRICOS EM ENGENHARIA DE
SOFTWARE. DISSERTAÇÃO DE MESTRADO. Universidade Federal de
Pernambuco. Centro de Ciências Exatas e Natureza.
APACHE SOFTWARE FOUNDATION, The. 2013. Welcome to Apache™
Hadoop®! Disponível em:<http://hadoop.apache.org/>. Acesso em: 23 de Abril de
2013.
APPEL, T. Colvero, DANTAS, M., PEZZI, D. da Cunha. Ambientes de Clusters e
Grids Computacionais: Características, Facilidades e Desafios. Anais
SULCOMP,
América
do
Norte,
1,
out.
2012.
Disponível
em:<http://periodicos.unesc.net/index.php/sulcomp/article/view/798/750>.
Acesso
em: 24 de Novembro de 2012.
ARMBRUST, Michael; FOX, Armando; GRIFFITH, Rean; JOSEPH, Anthony D.;
KATZ, Randy; KONWINSKI, Andy; LEE, Gunho; PATTERSON, David; RABKIN, Ariel;
STOICA, Ion; ZAHARIA, Matei. A view of cloud computing. Communications of the
ACM, v.53 n.4, April 2010.
BARCELONA, Universidade Autônoma de. 2012. PelicanHPC GNU Linux.
Disponível em: <http://pareto.uab.es/mcreel/PelicanHPC> Acesso em: 19 de
Dezembro de 2012.
BARNEY, Blayse. 2012. POSIX Threads Programming. Lawrence Livermore
National Laborator. Disponível em: <https://computing.llnl.gov/tutorials/pthreads/
#Pthread> Acesso em: 06 de abril de 2012.
BAUER, Fritz, 1969. Software engineering. In Peter Naur and Brian Randell,
editors, A Report on a Conference Sponsored by the NATO Science Committee.
93
BOINC.
2012.
Grid
computing
with
BOINC.
Disponível
em:
<http://boinc.berkeley.edu/trac/wiki/DesktopGrid> Acesso em: 06 de novembro de
2012.
CAMPOS, Augusto. 2011. Programação paralela: Intel abre código do Cilk Plus.
Disponível em: <http://br-linux.org/2011/programacao-paralela-intel-abre-codigo-docilk-plus/> Acesso em: 06 de abril de 2012.
CASANOVA, H; Desprez, F; Suter, F., 2010. On cluster resource allocation for
multiple parallel task graphs. Journal of Parallel and Distributed Computing, 70.
1193–1203
CHEN, W; Poirier, B. 2010. Parallel implementation of an efficient preconditioned
linear solver for grid-based applications in chemical physics. III: Improved
parallel scalability for sparse matrix-vector products. Journal of Parallel and
Distributed Computing, 70. 779-782.
CORDEIRO, Marco A., 2009. Métricas de Software. Disponível em:
<http://www.batebyte.pr.gov.br/modules/conteudo/conteudo.php?conteudo=88>
Acesso em 08 de setembro de 2012.
COSTA, Jaqueline Henrique Pereira. 2006. Grid Computing: Conceitos e
Aplicações. Disponível em: <http://pt.scribd.com/doc/50751016/Grid-Computing>
Acesso em 08 de março de 2013.
DOMEIKA, M., 2008. Software Development for embedded multi-core systems:
a practical guide using embedded Intel architecture. Local: USA: Elsevier. 420 p.
FOSTER, Ian. 1995. Designing and Building Parallel Programs - Addison Wesley
GEONUMERICS, M., 2012. Numerical Simulation Technologies. Disponível em:
<http://geonumerics.mit.edu/Technologies.aspx> Acesso em 08 de fevereiro de 2012.
INTEL Corporation. 2012. Welcome to Threading Building Blocks.org! Disponível
em: <http://threadingbuildingblocks.org/>. Acesso em: 08 mar. 2012.
JASON, F., 2012. Multi-CPU Support Option. Disponível em: <http://www.fugrojason.com/software/JGW/modules/multicore.php> Acesso em 08 de fevereiro de
2012.
JEANNOT, E; Saule, E; Trystram, D. 2012. Optimizing performance and reliability
on heterogeneous parallel systems: Approximation algorithms and heuristics.
Journal of Parallel and Distributed Computing, 72. 268–280.
JEVEAUX,
Paulo
César
M.
Utilizando
Threads.
Disponível
em:
<http://www.devmedia.com.br/utilizando-threads-parte-1/4459>. Acesso em: 15 abr.
2012.
94
JORDAO, Fábio. 2010. Quais as diferenças entre os processadores Intel Core
i3, i5 e i7? Disponível em: <http://www.tecmundo.com.br/processadores /3904quais-as-diferencas-entre-os-processadores-intel-core-i3-i5-e-i7-.htm> Acesso em:
14 nov. 2012.
JORGE NETO, Calil; Yamagishi, Erika; Sugaya, Helder Ken. Top500.org –
Supercomputadores. Instituto de Computação – Universidade Estadual de
Campinas
(UNICAMP).
Campinas
–
SP.
Disponível
em
<http://www.ic.unicamp.br/~rodolfo/Cursos/mc722/2s2008/Trabalho/g11_texto.pdf>.
Acesso em: 20 de setembro de 2012.
JPPF. 2012. JPPF About. Disponível em: <http://www.jppf.org/about.php> Acesso
em: 16 junho 2012.
KEUTZER, K., 2010 (EECS UC Berkeley); MATTSON, Tim (Intel). A Design Pattern
Language for Engineering (Parallel) Software. Intel Technology Journal:
Addressing the Challenges of Tera-scale Computing, 13(4).
LEE, V. W. et al., 2010. Debunking the 100x GPU vs. CPU Myth: An Evaluation of
Troughput Computing on CPU and GPU. ISCA’10, June 19-23.
MACORATTI, José Carlos. 2011. C# – Programação Paralela (dividir para
conquistar).
Disponível
em:
<http://imasters.com.br/artigo/19623/c-sharp/cprogramacao-paralela-dividir-para-conquistar>. Acesso em: 11 de Setembro de
2012.
MANACERO Jr., Aleardo, 2010. Identificação de Paralelismo. Disponível em:
<http://www.dcce.ibilce.unesp.br/~aleardo/cursos/hpc/paralelo2010.pdf> Acesso em
03 de setembro de 2012.
MIDORIKAWA, Edson T. 2010. Arquiteturas paralelas. ERAD-SP - I Escola
Regional de Alto Desempenho de São Paulo. USP - São Paulo – SP. Julho de 2010.
MYERS, Glenford J., John Wiley & Sons. 2004. The Art of Software Testing, 2,
Nova Jersey. ISBN 0-471-46912-2
MOHAMMAD, A.F. A new perspective in scientific software development innovations
and advances in computer sciences and engineering. Innovations and Advances in
Computer Sciences and Engineering, Ed. T. Sobh, Springer Netherlands, p.129134, 2010.
MORIMOTO,
Carlos
E.
2005.
Grid
Computing.
Disponível
em:
<http://www.hardware.com.br/termos/grid-computing>. Acesso em: 22 jun. 2012.
NACIONALHOST. 2011. Cloud Computing (Computação na Nuvem). Disponível
em:
<http://www.nacionalhost.com/site/index.php?option=com_content&view=
article&id=79&Itemid=86>. Acesso em: 22 mar. 2012.
95
NETTO, M; Vecchiola, C; Kirley, M; Varela, C; Buyya, R. 2011. Use of run time
predictions for automatic co-allocation of multiclusterresources for iterative
parallel applications. Journal of Parallel and Distributed Computing, 71. 1388–1399
NOLL, Albert; Gross, Thomas R. 2012. An Infrastructure for Dynamic
Optimization of Parallel Programs. PPoPP '12 Proceedings of the 17th ACM
SIGPLAN symposium on Principles and Practice of Parallel Programming. Pages
325-326 ACM New York, NY, USA.
NVIDIA Corporation. 2012. CUDA Programação paralela facilitada. Disponível em:
<http://br.nvidia.com/object/cuda_home_new_br.html> Acesso em: 06 abr. 2012.
Open MPI Project, The. 2013. Open MPI: Open Source High Performance
Computing. Disponível em: < http://www.open-mpi.org/> Acesso em: 26 abr. 2013.
PANKRATIUS, V., 2010. Software Engineering in the Era of Parallelism, in
Emerging research directions in computer science: contributions from the
young informatics faculty in Karlsruhe.
PASCUAL, J; Miguel-Alonso, J; Lozano, J. 2011. Optimization-based mapping
framework for parallel applications, Journal of Parallel and Distributed Computing,
71. 1377–1387
PEREIRA JUNIOR, Manoel. Concepção de um processo de desenvolvimento
específico para software científico. Mestrado em Modelagem Matemática e
Computacional. CEFET-MG. 2007
PAULA, W. P. Requirements for an Educational Software Development Process.
ITiCSE '01 Proceedings of the 6th annual conference on Innovation and
technology in computer science education, ACM SIGCSE Bulletin, v. 33,n. 3,
p.65-68, New York, 2001.
PITANGA, M., 2004. Computação em Cluster. 1ª ed., Rio de Janeiro: Brasport.
PODEROSO, C., 2004. Oracle Database 10g (Grid Computing). Disponível em:
<http://www.timaster.com.br/revista/artigos/main_artigo.asp?codigo= 950> Acesso
em 10 de jan. 2012.
RICE UNIVERSITY, 2006. High Performance Fortran.
<http://hpff.rice.edu/index.htm> Acesso em: 08 mar. 2011.
Disponível
em:
RIGO, S., Centoducatte, P. C., Baldassin, A., 2007. Memórias Transacionais: Uma
Nova Alternativa para a Programação Concorrente. Disponível em:
<http://www.sbc.org.br/sbac/2007/cdrom/papers/wscad/minicursos
//33214_1.pdf>
Acesso em: 08 set. 2011.
RITTER, H., Bordin, M. 2009. Ferramentas de Programação Paralela para
Arquiteturas
Multicore.
Disponível
em:
<http://www.slideshare.
96
net/heltonritter/ferramentas-de-programao-paralela-para-arquiteturas-multicore>.
Acesso em 10 de dez. 2011.
ROCKS,
Cluster.
2013.
About
Rocks
Cluster.
Disponível
em:
<http://www.rocksclusters.org /wordpress/?page_id=57>. Acesso em 03 de fev. 2013.
ROSE, César A. F. de. 2010. Arquiteturas Paralelas. ERAD 2010. Disponível em:
<http://www.upf.br/erad/download/brusso.pdf>. Acesso em 03 de nov. 2012.
SERTA, Victor, 2008. Programação concorrente com java.util.concurrent .
Disponível em: <http://victorserta.com.br/blog/2008/12/11/programacao-concorrentecom-javautilconcurrent-parte-1/>. Acesso em 01 de nov. 2012.
SILVA, J; Veiga, L; Ferreira, P., 2009. Mercury: A reflective middleware for
automatic parallelization of Bags of Tasks. ARM '09 Proceedings of the 8th
International Workshop on Adaptive and Reflective MIddleware. Article No. 1. ACM
New York, NY, USA.
SILVEIRA,
J.
F.
Porto.
2000.
O
NÚMERO
PI.
Disponível
em:
<http://www.mat.ufrgs.br/~portosil/aplcom1b.html> Acesso em: 20 de setembro de
2012.
SIQUEIRA, Frank. 2012. Memória Compartilhada Distribuída. Disponível em:
<http://www.inf.ufsc.br/~frank/INE5418/2.5.DSM-Folhetos.pdf> Acesso em: 26 de
abril de 2013.
SOMMEVILLE, I., Engenharia de Software. 8ª ed. São Paulo: Addison Wesley,
2007.
STIVALA, A; Stuckey P.; Garcia de la Banda, M; Hermenegildo, M; Wirth, A. 2010.
Lock-free parallel dynamics programming. Journal of Parallel and Distributed
Computing, 70. 839-848.
TANENBAUM, Andrew S. 2002. Organização Estruturada de Computadores. São
Paulo: LTC.
TOUB, Stephen. 2011. PROGRAMAÇÃO PARALELA: O passado, o presente e o
futuro da paralelização de aplicativos .NET. MSDN Magazine Ago. 2011.
Disponível em: <http://msdn.microsoft.com/pt-br/magazine/hh335070.aspx>. Acesso
em: 11 de Setembro de 2012.
VIRY, Patrick. Java for HPC (High-Performance Computing). Disponível em:
<http://ateji.blogspot.com.br/2010/09/java-for-high-performance-computing.html>.
Acesso em: 23 de novembro de 2012.
VOGEL, Lars. 2012. Java Concurrency / Multithreading. Disponível em:
<http://www. vogella.com /articles/ JavaConcurrency/article.html>. Acesso em: 11 de
Setembro de 2012.
Download

são paralelos