UNIVERSIDADE ESTADUAL DE MARINGÁ Departamento de …wesley/wordpress/wp-content/uploads/2011/05/Anais... · Heloise Mânica Paris Teixeira - UEM Dra. Itana Maria de Souza Gimenes

UNIVERSIDADE ESTADUAL DE MARINGÁ Departamento de Informática

Maringá – Pr.

ANAIS do 9º. FÓRUM DE INFORMÁTICA E TECNOLOGIA DE MARINGÁ

UNIVERSIDADE ESTADUAL DE MARINGÁ Departamento de Informática

13 A 17 de Setembro de 2010

Maringá – Pr.

www.din.uem.br/fitem

ANAIS do 9º. FÓRUM DE INFORMÁTICA E TECNOLOGIA DE MARINGÁ

UNIVERSIDADE ESTADUAL DE MARINGÁ

Anais do 9º. Fórum de Informática de Maringá 13 a17 de Setembro de 2010

Comissão Organizadora Comitê de Programa Dante Alves Medeiros Filho Luciano Fiorin Júnior Sandra Ferrari Tânia Fátima Calvi Tait

Dr. Adenilso S. Simão - USP/ICMC Dr. Anderson Faustino Silva - UEM Dra. Clélia Franco - UEM Dra. Cristine Martins Gomes de Gusmão - UFPE Dr. Dante Alves Medeiros Filho - UEM Dr. Delano Medeiros Beder - UNICAMP Dr. Donizete Carlos Bruzarosco - UEM Dr. Edmundo Sérgio Spoto - UFG Dr. Edson Roberto De Pieri - UFSC Dra. Elisa Hatsue Moriya Huzita - UEM Dr. Fernando Barreto - UTFPR Dr. Franklin Cesar Flores - UEM Dra. Gertrudes Dandolini - UFSC Dr. Hélio Crestana Guardia - UFSCar Dra. Heloise Mânica Paris Teixeira - UEM Dra. Itana Maria de Souza Gimenes - UEM Dr. João Angelo Martini - UEM Dr. João Arthur Souza - UFSC Dr. João Fernando Marar – UNESP Dr. Jorge Bidarra - UNOESTE Dr. José B. da Silva Filho – Faculdade Ateneu Dr. José Hiroki Saito - UFSCar Dr. José Leomar Todesco - UFSC Dr. José Remo Ferreira Brega - UNESP Dr. Júlio César Nievola – PUC-PR Dra. Luciana Andréia Fondazzi Martimiano - UEM Dr. Marcelo Lobosco - UFJF Dr. Marcos Antônio Cavenaghi - UNESP Dr. Marcos Sfair Sunye - UFPR Dra. Maria Izabel Cavalcanti Cabral - UFCG Dra. Maria Madalena Dias – UEM Dra. Marilde Terezinha Prado Santos - UFSCar Dr. Maurício Fernandes Figueiredo - UFSCar Dr. Milton Hirokazu Shimabukuro - UNESP Dra. Nelkis de La Orden Medina – Empresa de TI Dra. Rogéria Cristiane Gratão de Souza - UNESP Dr. Ronaldo A. de Lara Gonçalves - UEM Dra. Sarajane Marques Peres - USP Dr. Sérgio Roberto Pereira da Silva - UEM Dra. Sueli de Fátima Poppi Borba - UNOPAR Dra. Tânia Fátima Calvi Tait – UEM Dra. Valéria Delisandra Feltrim - UEM Dr. Valter Vieira de Camargo - UFSCar Dr. Victor F. Araya Santander - UNOESTE Dr. Wesley Romão – UEM



APRESENTAÇÂO O Fórum de Informática e Tecnologia de Maringá (FITEM) é um fórum de discussão de temas relevantes da Informática, composto de diversos subeventos associados à mini-cursos, palestras e mostra de trabalhos, entre outras atividades de caráter tecnológico ou científico. O FITEM é um evento bi-anual de considerável importância, realizado pelo Departamento de Informática da Universidade Estadual de Maringá. O público alvo do FITEM abrange profissionais, professores, pesquisadores, alunos de graduação e pós-graduação da área de Informática. Neste ano, a XII Mostra de Trabalhos de Informática, sub-evento do IX FITEM, promoverá a apresentação de artigos científicos de alta qualidade, selecionados por um Comitê de Programa composto de doutores vinculados a diversas instituições renomadas de ensino superior. Autores interessados em contribuir com a XII Mostra de Trabalhos de Informática foram convidados a submeter artigos escritos em Português, Espanhol ou Inglês, que contribuam com o avanço científico e tecnológico nas diversas áreas da informática. Foram submetidos 30 artigos dos quais apenas um terço foi selecionado para publicação.

Comissão Organizadora

Anais do 9o. Fórum de Informática de Maringá – 13 a 17 de Setembro de 2010 5



Sumário Automatização da Aplicação de Métricas Arquiteturais Convencionais e Sensíveis a Interesses Willian Nalepa Oizumi, Thelma Elita Colanzi ................................................

6-18 Um Algoritmo Genético Difuso Multiobjetivo para Descoberta de Conhecimento em Dados de Pesquisadores Daniel Rossetto de Souza, Wesley Romão, Ricardo G. Coelho, Itana M. S. Gimenes e Ademir A. Constantino...................................................................

19-31

Sistema embarcado para monitoramento aplicado à viticultura Paulo Henrique Sabo, Paulo Cesar Gonçalves, João Angelo Martini, Elvio João Leonardo...................................................................................................

32-43

Arquitetura MIPS: desenvolvimento de um simulador Alison R. P. Freitas, Carlos R. B. Junior, Murilo Z. Souza, Ronaldo A. L. Gonçalves...........................................................................................................

44-57

Investigação de resolução do problema de programação de horários escolares usando FPGA e VHDL Landir Saviniec, Hudson Sérgio de Souza, João Angelo Martini.....................

58-70

Implementação de um Módulo Otimizador para o Compilador SCC visando seu Uso como Ferramenta Educacional George S. Oliveira e Valéria D. Feltrim...........................................................

71-82

Aplicação MPI para Cálculo do Índice de Fragmentação Multidimensional em Imagens de Sensoriamento Remoto Henrique Y. Shishido, Ligia F. A. Batista, Ronaldo A. L. Gonçalves...............

83-94

Proposta de uma Ontologia no Domínio de Doenças Negligenciadas Aldo Sergio de Oliveira, Maria Madalena Dias, Heloise Manica, Sandra Xavier de Macedo ............................................................................................

95-105 O Impacto da Otimizacão Inline na Execução de Programas Java Francis Rangel, Anderson Faustino da Silva ..................................................

106-118


Automatização da Aplicação de Métricas Arquiteturais Convencionais e Sensíveis a Interesses

Willian Nalepa Oizumi, Thelma Elita Colanzi

Departamento de Informática – Universidade Estadual de Maringá (UEM) Caixa Postal 87020-900 – Maringá – PR – Brazil

[email protected], [email protected]

Abstract. The software architecture it is one of the most important artifacts in a software project. Therefore, it is necessary to analyze it in order to identify possible design flaws. This analysis can be performed with the support of conventional architectural metrics (CAM), which aims to analyze issues such as cohesion and coupling, and concern-driven metrics (CDM) that aims to identify design flaws related to architectural concerns. The realization of the measurement process manually can be slow and error prone. Thus, this paper presents the configuration of SDMetrics tool to automate the measurement process of CAM and CDM.

Resumo. A arquitetura de software é um dos artefatos mais importantes em um projeto de software. Por isso é necessário analisá-la a fim de identificar eventuais falhas arquiteturais. Essa análise pode ser realizada com o apoio de métricas arquiteturais convencionais (MAC), que buscam analisar questões como coesão e acoplamento, e de métricas sensíveis a interesses (MSI) que tem como objetivo identificar falhas de projeto relacionadas a interesses arquiteturais. A realização do processo de medição manualmente pode ser demorado e sujeito a erros. Sendo assim, este trabalho apresenta a configuração da ferramenta SDMetrics para automatizar o processo de medição de MAC e MSI.

1. Introdução

Uma arquitetura de software é o conjunto das principais decisões arquiteturais que orientam um sistema de software [Bass, Clements e Kazman 2003]. Em um projeto de software ela influencia vários atributos, como performance, robustez, manutenibilidade e distribuição [Bosch 2000]. Ela desempenha um papel central no desenvolvimento e evolução de um projeto de software. Assim, a arquitetura constitui um dos artefatos mais importantes para gerar um produto de software com sucesso.

A identificação de anomalias em arquiteturas é imprescindível a fim de evitar que as falhas de projeto arquitetural sejam propagadas ao longo do ciclo de vida de um software. A fim de garantir a reutilização de componentes, de facilitar o gerenciamento do projeto e de minimizar os recursos necessários para a manutenção de software, é importante que os componentes da arquitetura sejam minimamente acoplados. Desta forma, mudanças em um componente teriam pouco ou nenhum impacto em outros componentes do produto de software. Por esse motivo, o conceito de modularidade se torna essencial para o desenvolvimento de software, e deve ser priorizada desde a definição da arquitetura inicial.


As métricas arquiteturais de software fornecem indicadores de modularidade e são definidas com o objetivo de medir as abstrações relacionadas a componentes e interfaces [Sant’Anna et al. 2003]. Portanto, elas conseguem revelar questões como: acoplamento e coesão de componentes e complexidade de uma interface.

Muitas dos interesses presentes em um projeto de software são inerentemente transversais, isto é, afetam o escopo do software em diversos pontos. A complexidade do projeto arquitetural pode aumentar em conseqüência de interesses transversais e muitas vezes, esses interesses não são modularizados adequadamente. Sant’Anna et al. [2007] afirmam que as métricas arquiteturais convencionais (MAC) não são sensíveis a interesses arquiteturais e, portanto, não conseguem auxiliar o arquiteto de software a identificar anomalias de modularidade relacionadas a interesses transversais. Assim, a aplicação de conceitos da orientação a aspectos (OA) [Kiczales, 1997] torna-se fundamental em projetos de software. Esses mesmos autores destacam a necessidade de técnicas de avaliação que permitam uma identificação efetiva de anomalias de modularidade referentes a interesses transversais no contexto de projeto arquitetural.

A abordagem OA tem propiciado uma forma de isolar os interesses transversais em módulos denominados aspectos. Com isso, o projeto arquitetural OA tem se tornado mais evidente por facilitar o projeto de modularidade. Porém, como a OA introduz novos mecanismos e abstrações que propiciam diferentes maneiras de decompor o projeto de um software, o uso inadequado dos seus mecanismos pode introduzir anomalias exclusivas de modularidade, além de anomalias similares às encontradas em sistemas OO [Bertrán, Garcia e von Staa 2009]. Desta forma, é preciso dispor de mecanismos que auxiliem o arquiteto de software na tentativa de identificar possíveis anomalias de modularidade. Nesse sentido, Sant’Anna [2008] propôs um conjunto de métricas arquiteturais sensíveis a interesses (MSI) para avaliar arquiteturas de software OA. Ele realizou estudos empíricos aplicando o seu conjunto de métricas em arquiteturas de software construídas a partir do código-fonte, ou seja, usando engenharia reversa. O resultado dos seus estudos foi positivo e mostrou que as MSI são efetivas na detecção de anomalias de modularidade em arquiteturas de software OA construídas em um processo de engenharia reversa.

Para a realização de novos estudos empíricos utilizando as MSI e futura adoção delas na indústria, é imprescindível contar com apoio automatizado para o processo de medição. No entanto, o protótipo desenvolvido por Sant’Anna [2008] não se encontra operacional. A SDMetrics [Wüst 2010] é uma ferramenta para medição de projeto orientado a objetos para UML. Ela pode ser configurada para aplicar algumas de suas métricas convencionais no contexto de projeto arquitetural. Além disso, é possível definir novas métricas na SDMetrics para serem aplicadas em artefatos UML.

Visando à automatização das MSI e a realização de experimentos que utilizem MAC e MSI, a SDMetrics foi configurada para automatizar a medição dos dois conjuntos de métricas arquiteturais. O objetivo deste trabalho é apresentar como algumas MAC foram adaptadas na SDMetrics e como as MSI foram inseridas nessa ferramenta.

Este trabalho foi realizado no contexto de um projeto de pesquisa cujo foco principal é a avaliação de arquiteturas de Linhas de Produto de Software (LPS) [van der Linden, Schmid, Rommes 2007]. Nesse projeto de pesquisa pretende-se realizar


experimentos para comparar os dois conjuntos de métricas arquiteturais: MAC e MSI. A inserção das MSI e adaptação de algumas MAC na SDMetrics viabiliza a automatização da medição de arquiteturas de LPS, e de outros tipos de arquitetura, usando os dois conjuntos de métricas.

Este artigo está organizado em seis seções. A segunda seção contém detalhes referentes às métricas arquiteturais utilizadas neste trabalho. O funcionamento da SDMetrics é explicado na terceira seção. Na Seção 4 estão as informações referentes ao processo de automatização e validação das métricas por meio da SDMetrics. Os resultados e discussões são detalhados na Seção 5. Por fim, na Seção 6 é apresentada a conclusão do trabalho.

2. Métricas Arquiteturais

Esta seção está dividida em duas subseções. Na primeira é apresentado o conjunto de MAC constituído por métricas de acoplamento [Martin 1997], de coesão [Martin 2003] e de herança [Briand 1994] que foi adaptado na SDMetrics para o contexto de projeto arquitetural. Na segunda subseção, é apresentado o conjunto de MSI [Sant’Anna 2008] que foi definido na SDMetrics.

2.1. Métricas arquiteturais convencionais

2.1.1. Métricas de acoplamento de Martin [1997]

As métricas de acoplamento definidas por Martin [1997] têm como principal objetivo mensurar a qualidade de projetos orientados a objetos. Ele estabeleceu um padrão de projeto desejado que está diretamente relacionado com a estabilidade, pois ela é o cerne de todo o projeto de software. Os princípios que norteiam esse padrão são: princípio das dependências estáveis e princípio das abstrações estáveis.

O princípio das dependências estáveis diz que as dependências entre pacotes em um projeto devem ser direcionadas para a estabilidade dos pacotes. Um pacote deve depender somente de pacotes que são mais estáveis que ele [Martin 1997]. Isso significa que um pacote só pode depender de pacotes que sofrem um número de mudanças menor que o dele, pois as mudanças em um pacote podem causar efeitos colaterais nos pacotes que dependem dele.

De acordo com o princípio das abstrações estáveis, pacotes que possuem máxima estabilidade devem possuir máxima abstração. Pacotes instáveis devem ser concretos. A abstração de um pacote deve ser proporcional a sua estabilidade [Martin 1997]. Dessa forma, os pacotes estáveis podem ser facilmente estendidos por meio de sua abstração, e os pacotes mais concretos podem ser modificados com facilidade por serem instáveis.

Dentre as métricas definidas por Martin [1997] foi selecionado um conjunto composto por métricas de estabilidade. Essas métricas se baseiam na contagem de dependência entre pacotes, e têm como finalidade auxiliar na verificação do princípio das dependências estáveis em um projeto de software. As métricas desse conjunto são Afferent Coupling (Ca), Efferent Coupling (Ce) e Instability (I).


A métrica Ca conta a quantidade de classes externas que dependem de classes internas a um pacote. A métrica Ce conta a quantidade de classes internas que dependem de classes externas a um pacote. Por fim, a métrica I se utiliza dos resultados das duas métricas anteriores para indicar o nível de instabilidade de um pacote, por meio da seguinte fórmula: I = Ce/(Ca + Ce) .O valor da métrica I está no intervalo [0,1], em que I=0 indica que o pacote possui estabilidade máxima e I=1 indica que o pacote possui máxima instabilidade.

2.1.2. Métrica de Coesão de Martin [2003]

Considerando que coesão é definida como sendo o relacionamento funcional dos elementos de um módulo, Martin [2003] propôs um conjunto de princípios de coesão que têm como finalidade auxiliar os projetistas a decidir como particionar classes dentro de pacotes. Dentre as métricas propostas por ele está a métrica de coesão relacional (H).

A métrica H conta o número médio de relacionamentos entre classes e interfaces dentro de um pacote. Considerando N como sendo o número de classes e interfaces dentro do pacote, e R como sendo o número de relacionamentos internos ao pacote, temos que: H=(R + 1)/N, onde o valor um é somado a R para evitar que H seja 0 quando N é 1. A métrica H auxilia os projetistas a identificar pacotes que possuem elementos pouco relacionados, o que pode significar que os pacotes são pouco coesos.

2.1.3. Métricas de Herança de Briand [1994]

Briand [1994] definiu e validou um conjunto de métricas de alto nível baseadas em acoplamento e coesão de módulos. Essas métricas têm como objetivo a avaliação de projetos de alto nível a fim de identificar defeitos e falhas de projeto. Dentre as métricas definidas por Briand [1994] está o conjunto de métricas baseadas em relacionamentos is_component_of [Ghezzi et al. 1991]. De acordo com Briand [1994] os módulos que possuem relacionamentos do tipo is_component_of formam estruturas chamadas de bibliotecas hierárquicas de módulos. Esse tipo de estrutura é como uma árvore, na qual os nós são módulos e as setas ligando os nós são relacionamentos is_component_of.

Dentro desse conjunto foram selecionadas duas métricas para o conjunto de métricas arquiteturais convencionais: profundidade máxima (Max_Depth) e profundidade média (Avg_Depth). A métrica Max_Depth conta o nível do nó mais profundo dentro da hierarquia e a métrica Avg_Depth conta o nível médio de profundidade dentro da hierarquia.

2.2. Métricas Sensíveis a Interesses

Um interesse pode ser definido como sendo uma propriedade ou parte de um problema que os stakeholders consideram como uma unidade conceitual e tratam isso de maneira modular. Os interesses podem variar de conceitos de alto nível, como segurança e qualidade de serviço a conceitos de baixo nível, como cache e buffer. Eles podem ser funcionais, como regras de negócio e características, ou não-funcionais, como sincronização e gerenciamento de transação.

As métricas propostas por Sant’Anna [2008] têm como principal objetivo ajudar os engenheiros de software a identificar falhas em projetos arquitetônicos causadas pela


falta de modularidade nos interesses relevantes ao projeto, e consequentemente comparar as possíveis soluções para resolver os problemas relacionados aos interesses do projeto.

O conjunto das métricas sensíveis a interesses propostas por Sant’Anna [2008] que se utilizou neste trabalho é constituído das seguintes métricas: Concern Diffusion over Architectural Components (CDAC), Concern Diffusion over Architectural Interfaces (CDAI), Concern Diffusion over Architectural Operations (CDAO), Component-level Interlacing Between Concerns (CIBC), Interface-level Interlacing Between Concerns (IIBC), Operation-level Overlapping Between Concerns (OOBC) e Lack of Concern-based Cohesion (LCC).

As métricas CDAC, CDAI, e CDAO estão relacionadas com o conceito de difusão de interesses, isto é, dado um determinado interesse elas contam a quantidade de componentes, interfaces e operações, respectivamente, que contribuem para a realização desse interesse. Já as métricas CIBC, IIBC e OOBC realizam contagens relacionadas ao entrelaçamento de interesses, assim, dado um interesse elas contam a quantidade de outros interesses que se relacionam com ele nos níveis de componente, interface e operação, respectivamente. A métrica LCC conta a quantidade de interesses tratados por um dado componente, a fim de analisar a coesão do componente com base nos interesses. Um módulo que se relaciona com muitos interesses é considerado pouco coeso, pois quanto maior for a quantidade de interesses maior será a probabilidade de o módulo sofrer efeitos colaterais oriundos de mudanças nos interesses.

3. Funcionamento da SDMetrics

SDMetrics é uma ferramenta de software cujo principal objetivo é medir a qualidade de projetos de software desenvolvidos com a UML [Wüst 2010]. Ela trabalha com qualquer ferramenta de modelagem UML que exporte seus diagramas para o formato XMI [OMG 2010].

O formato XMI (XML Metadata Interchange) é um padrão baseado em XML, desenvolvido pela OMG para troca de informações de metadados. É comumente utilizado como formato de intercâmbio de modelos UML entre ferramentas de modelagem.

A SDMetrics utiliza quatro arquivos para realizar suas medições:

• XMI Source File: Arquivo no formato XMI que descreve o diagrama que se pretende medir, no contexto deste trabalho, um diagrama que representa a arquitetura projetada;

• Metamodel Definition: Arquivo no formato XML que descreve o metamodelo da UML utilizado pelo diagrama arquitetural do arquivo XMI Source File;

• XMI Transformation: Arquivo no formato XML que possui as especificações necessárias para realizar o mapeamento do arquivo XMI Source File com o arquivo Metamodel Definition;

• Metrics Definition: Arquivo no formato XML contendo a definição das métricas que se pretende mensurar por meio da SDMetrics.

Juntamente com a versão 2.02 da SDMetrics foi disponibilizado um conjunto de métricas previamente automatizadas. Dentre elas estão as métricas apresentadas nas Subseções 2.1.1 e 2.1.2, além de uma série de métricas relacionadas a classes.


Os resultados das métricas são exibidos por meio de tabelas e gráficos. As métricas podem ser definidas para diferentes elementos arquiteturais, então os resultados das métricas são agrupados de acordo com o elemento arquitetural medido.

4. Automatização e validação das métricas na SDMetrics

O processo de automatização das métricas na SDMetrics passou por três estágios: (i) criação das definições das métricas não disponíveis na versão 2.0.2 da SDMetrics, (ii) adaptação de algumas métricas já existentes para o nível arquitetural desejado e (iii) validação da adaptação e da automatização das métricas envolvidas neste trabalho. Esses estágios são descritos nas Subseções 4.1, 4.2 e 4.3, respectivamente.

4.1. Automatização das métricas na SDMetrics

Como foi citado na Seção 3 a automatização das métricas definidas por [Martin 1997] [Martin 2003] foi obtida por meio de um conjunto de métricas previamente automatizadas por Wüst.

A SDMetrics permite que as métricas sejam automatizadas por meio de sua definição em um arquivo no formato XML que contém as especificações necessárias para que a SDMetrics interprete as métricas e realize a contagem na arquitetura fornecida por meio do arquivo XMI.

A definição do arquivo de métricas é feita usando tags e atributos pré-definidos. A seguir exibe-se a estrutura básica de um arquivo de métricas:

1 <?xml version="1.0"?> 2 <!DOCTYPE sdmetrics SYSTEM 'metrics.dtd'> 3 <sdmetrics version="2.0" ruleexemption="taggedvalue " exemptiontag="tagname"> 4 <metric name="IsBusiness" domain="operation" catego ry="aspect"> 5 <description> 6 Indicates if the operation is assigned to Business. 7 </description> 8 <projection relset="stereotypes" target="stereotype " condition="name='Business'"/> 9 </metric>

10 </sdmetrics>

O elemento da primeira linha define a versão da XML utilizada, na linha 2 é definido o arquivo DTD que contém as regras e restrições para as tags e atributos utilizados no arquivo. As palavras xml,sdmetrics,metric,description e projection são tags que representam diversos elementos utilizados pela SDMetrics para realizar a contagem. Palavras como version e name representam atributos para as tags. Cada atributo possui um valor atribuído, que será utilizado pela SDMetrics para realizar as contagens. A tag metric (linha 4) representa uma métrica, podendo existir diversas tags desse tipo dentro de um arquivo de definição de métricas.

No exemplo anterior, a métrica recebe o nome IsBusiness por meio do atributo "name", o domínio da métrica é "operation" (linha 4), isto significa que ela será contada para operações. As métricas de um domínio devem possuir nomes únicos, isto é, não é possível definir mais de uma métrica com um determinado nome para o mesmo domínio, mas podem-se definir métricas com o mesmo nome para domínios diferentes. O atributo "category" indica a categoria da métrica, esse atributo não é necessário, mas pode ser


definido para melhor entendimento das métricas. A tag "description" é utilizada para fazer a definição textual da métrica. A tag "projection" é o elemento que define as condições e restrições para a contagem da métrica (linha 8). O atributo "relset" define o conjunto de elementos relacionados, "target" define o tipo dos elementos relacionados e "condition" filtra os elementos para que sejam contados apenas os elementos que satisfazem a condição definida. No exemplo, a métrica IsBusiness conta quantos estereótipos da operação possuem o nome igual a "Business".

As MSI foram definidas para o nível arquitetural de componentes. A forma encontrada para identificar interesses nos elementos arquiteturais foi por meio de estereótipos, pois a UML em sua versão atual não oferece suporte para modelagem de interesses em seus diagramas. Dessa forma, no exemplo anterior a métrica "IsBusiness" tem valor igual a zero para operações que não possuem o estereótipo "Business" indicando que esse interesse não está associado à operação e valor maior que zero para as operações que possuem esse estereótipo.

Como a SDMetrics não oferece suporte para definição de variáveis ou para que as métricas sejam contadas com base em entradas do usuário, foi necessário replicar todas as métricas para cada um dos interesses que pudessem estar presentes na arquitetura projetada. Assim, para que seja acrescentado um novo interesse a ser medido, basta replicar as definições existentes para cada uma das MSI. Além disso, as métricas de difusão de interesses (CDAC, CDAI, e CDAO) e de coesão baseada em interesses (LCC) foram agrupadas nos mesmos arquivos, pois as métricas auxiliares utilizadas pelos dois grupos são compatíveis. Por outro lado, as métricas de entrelaçamento de interesses (CIBC, IIBC e OOBC) foram definidas em outros arquivos por possuírem características diferentes.

As métricas de Briand [1994] foram automatizadas na SDMetrics usando a adaptação citada a seguir na Subseção 4.2 e conforme a estrutura básica definida pela SDMetrics.

4.2. Adaptação de métricas para o nível de projeto arquitetural

Sant’Anna [2008] definiu suas métricas baseado em uma arquitetura de componentes. Sendo assim, para possibilitar a realização de estudos comparativos entre as MAC e as MSI, as métricas de coesão e acoplamento [Martin 1997] [Martin 2003] que foram definidas baseando-se no conceito de pacotes, foram adaptadas para o nível de componentes. Pode-se ilustrar esta adaptação por meio do seguinte exemplo referente à métrica H:

1 <metric name="H" domain="package" category="Cohesio n"> 2 <description></description> 3 <compoundmetric term="(R+1)/(NumCls+NumInterf)" fal lback="0" /> 4 </metric>

Para realizar a adaptação dessa métrica para o nível de componentes foi necessário alterar o atributo “domain” de “package” para “component”, mantendo a mesma estrutura da métrica para pacotes. Assim, a linha 1 foi substituída pela seguinte linha:


1 <metric name="H" domain="component" category="Cohes ion">

Briand [1994] definiu e validou suas métricas por meio de modelos baseados na linguagem de programação ADA. Esses modelos não foram definidos por meio da UML. Então, para possibilitar a utilização das métricas de Briand [1994] neste trabalho, adaptou-se o conceito de bibliotecas hierárquicas de módulos para a abordagem orientada a objetos, considerando os módulos como sendo classes e os relacionamentos is_component_of como sendo relacionamentos de herança. Dessa forma, neste trabalho considera-se que as métricas Max_Depth e Avg_Depth são computadas para pacotes ou componentes dependendo do nível arquitetural utilizado. Como a hierarquia pode estar completa dentro de um pacote ou espalhada em vários pacotes, as métricas consideram o grau de herança das classes presentes no pacote, mesmo que essa herança venha de classes de outros pacotes.

4.3. Validação das métricas automatizadas

Com o intuito de validar as métricas de acoplamento (Ca, Ce e I) [Martin 1997] e coesão (H) [Martin 2003], primeiramente realizou-se a contagem manual de cada métrica para o modelo da Figura 1. A partir do modelo da Figura 1 no formato XMI e do arquivo de definição destas métricas foi realizada a contagem por meio da ferramenta SDMetrics. Na sequência, os resultados obtidos por contagem manual foram comparados com os obtidos por meio da SDMetrics. Além disso, para as métricas Ca, Ce e I esses dois resultados foram comparados com os resultados apresentados por Martin [1997]. Dessa forma, verificou-se que os resultados das métricas convencionais de acoplamento e coesão automatizados pela SDMetrics estão de acordo com a sua definição [Martin 1997] [Martin 2003] e com a contagem manual. O Quadro 1 apresenta os resultados obtidos para o modelo da Figura 1.

Figura 1. Modelo utilizado para validar as métricas convencionais [Martin 1997]

Para verificar a validade da automatização das métricas de herança (Max_Depth e Avg_Depth) [Briand 1994] utilizou-se também o modelo da Figura 1. O processo de


validação foi o mesmo utilizado para as métricas de Martin, exceto pelo fato de não ser possível comparar os resultados obtidos com os resultados apresentados pelo autor, porque o modelo utilizado no trabalho de Briand [1994] não segue o padrão UML. Os resultados obtidos por meio da SDMetrics para as métricas de herança são apresentados no Quadro 1.

O resultado da métrica Ca para o pacote_2 da Figura 1 é um, pois existe uma classe externa ao pacote que depende de uma classe interna a ele por meio de um relacionamento de composição. Para o pacote_6 a métrica Ce é um porque existe um relacionamento de composição em que uma classe do pacote_6 depende de uma classe externa a ele. Assim, considerando que a métrica Ca para o pacote_6 é zero, temos pela definição que o resultado da métrica I para o pacote_6 é um. Para o pacote_2 a métrica H é um porque existe uma classe interna ao pacote e nenhum relacionamento interno. As métricas Max_Depth e Avg_Depth para o pacote_5 são respectivamente dois e um, pelo fato de existirem duas classes dentro do pacote_5, sendo que uma delas possui grau dois e a outra zero dentro da hierarquia de herança.

Quadro 1. Resultados das métricas de coesão, acopla mento e herança para o modelo da Figura 1.

Pacote Ca Ce I H Max_Depth Avg_Depth

pacote_1 1 0 0 0.5 0 0

pacote_2 1 0 0 1 0 0

pacote_3 1 0 0 0.5 0 0

pacote_4 4 3 0.42857143 0.5 1 0.5

pacote_5 0 2 1 0.5 2 1

pacote_6 0 1 1 1 0 0

pacote_7 0 1 1 0.5 2 1

No processo de validação dos resultados das MSI utilizou-se uma arquitetura baseada em um sistema de informação real chamado Health Watcher [Soares et al. 2002] utilizada por Sant'Anna [2008]. Essa arquitetura é apresentada na Figura 2.


Figura 2. Arquitetura do sistema Health Watcher [Sa nt’Anna 2008].

Assim como nas métricas convencionais, primeiramente realizou-se a contagem manual das métricas para o modelo da arquitetura de Health Watcher. Posteriormente, obteve-se o modelo dessa arquitetura no formato XMI, e com base nesse arquivo XMI nos arquivos de definição das MSI realizou-se a contagem por meio da SDMetrics. Os resultados obtidos por contagem manual e pela SDMetrics foram iguais, porém houve divergência com relação aos resultados apresentados por Sant'Anna [2008] em seus exemplos para a métrica CIBC. Mas, o resultado obtido pela SDMetrics para esta métrica está de acordo com a definição formal apresentada por Sant'Anna [2008]. Dessa forma, averiguou-se que se trata de um erro no exemplo de Sant'Anna [2008], e que os resultados apresentados pela SDMetrics para as MSI estão corretos. Os resultados das MSI para a arquitetura Health Watcher são exibidos no Quadro 2 e na Figura 3.

Quadro 2. Resultados das métricas de difusão de int eresses e de entrelaçamento de interesses para a arquitetura Health Watcher.

Difusão de Interesses Entrelaçamento de Interesses Interesse

CDAO CDAI CDAC OOBC IIBC CIBC

Business 3 5 1 0 2 2

Distribution 4 4 1 1 2 2

Exception Handling 5 2 2 2 4 4

GUI 0 2 1 0 0 0

Persistence 4 6 4 1 4 4


Figura 3. Resultado da métrica de coesão baseada em interesse s na SDMetrics

Na arquitetura da Figura 2 para as métricas CDAO, CDAI e CDAC existem, respectivamente, quatro operações, quatro interfaces e um componente associados ao interesse Distribution. Para OOBC, IIBC e CIBC, Distribution está entrelaçado com um interesse em nível de operação, dois interesses em nível de interface e dois interesses em nível de componente. Para o componente GUI_ELEMENTS, LCC tem valor um porque ele está associado ao interesse Distribution.

5. Resultados e Discussões

Algumas limitações foram encontradas na SDMetrics com relação a definição de métricas genéricas. A ferramenta não possibilita a definição de métricas que recebam parâmetros fornecidos pelo usuário, dessa forma as métricas sensíveis a interesses só puderam ser definidas para interesses fixos. Sendo assim, como mencionado anteriormente foi necessário replicar diversas métricas para cada um dos interesses utilizados no trabalho, isso gerou uma quantidade de código muito grande. Então as métricas foram divididas em vários arquivos para facilitar o manuseio e entendimento.

As MSI foram automatizadas para os interesses: Business, Concurrency, Distribution, Exception Handling, GUI, Logging e Persistence. Para realizar a medição de interesses diferentes, é necessário que as automatizações de das MSI sejam replicadas para cada interesse novo.

Apesar dessa limitação, a SDMetrics tem facilidade para operar com modelos UML e é eficiente para medir arquiteturas, o que atende o objetivo maior do projeto que é automatizar a medição para realizar estudos empíricos. Existem outros protótipos de ferramentas de medição, como a COMET [Sant’Anna 2008], mas nenhum deles é maduro como a SDMetrics.

Ao final do projeto obtiveram-se nove arquivos XML com as definições das métricas convencionais e sensíveis a interesses conforme relação a seguir:

• metricasOO.xml: Contém as métricas convencionais de acoplamento definidas por Martin [1997] e de coesão definida por Martin [2003] para o nível de pacotes além da adaptação feita para o nível de componentes. Além disso, contém as


métricas Max_Depth e Avg_Depth tanto para o nível de pacotes como para o nível de componentes [Briand 1994].

• Concern_Based_Difusion_and_Cohesion.xml: Contém as métricas de difusão de interesses e de coesão baseada em interesses definidas por Sant’Anna [2008].

• Interaction_Between_Concerns_[nome do interesse ].xml: devido a uma limitação da SDMetrics, a definição das métricas de entrelaçamento de interesses ficaram atreladas a interesses específicos. Dessa forma, para cada interesse houve a replicação das definições em arquivos distintos, constituindo-se sete arquivos que levam em seu nome o interesse para o qual as métricas foram especificadas.

6. Conclusão

A aplicação de métricas arquiteturais convencionais e sensíveis a interesses em arquiteturas de LPS possibilita a identificação de anomalias presentes no projeto da arquitetura da LPS. Com o objetivo de automatizar a medição de métricas arquiteturais sensíveis a interesses e convencionais, realizou-se a automatização desses conjuntos de métricas na ferramenta SDMetrics.

Após a especificação dos arquivos com métricas para a SDMetrics, foi realizada a validação da especificação usando os exemplos adotados por Martin [1997] e por Sant’Anna [2008].

A automatização de métricas com a SDMetrics permite a aplicação de métricas em diversos modelos, evitando que a contagem seja realizada manualmente, assim evita-se que ocorram erros de contagem em conseqüência de falhas humanas. Além disso, um modelo com uma alta complexidade pode ser mensurado de forma rápida e eficiente por meio da SDMetrics.

Finalmente, conforme foi relatado, a automatização de métricas arquiteturais facilita o processo de medição tanto de modelos arquiteturais simples como de modelos arquiteturais complexos, evitando que ocorram falhas de contagem. Além disso, por meio dos resultados apresentados pelas métricas, é possível avaliar possibilidades de solução arquitetural para um determinado projeto de software.

Futuramente pretende-se realizar estudos empíricos, com base nos resultados deste trabalho, para analisar a eficácia dos dois conjuntos de métricas automatizados com relação à detecção de anomalias de modularidade em arquiteturas de LPS. Além disso, planeja-se a realização de estudos de caso que permitam uma análise comparativa e a obtenção de indicadores dos ganhos obtidos com o uso da ferramenta configurada com as MAC e MSI.

Referências

BASS, L.; CLEMENTS, P.; KAZMAN, R. (2003) Software Architecture in Practice, Addison-Wesley, 2nd edition.

BERTRÁN, I. M.; GARCIA, A.; von STAA, A. (2009) “Estratégias de Detecção de Anomalias de Modularidade em Sistemas Orientados a Aspectos”, Anais do III Latin


American Workshop on Aspect-Oriented Software Development, XXIII Simpósio Brasileiro de Engenharia de Software. Fortaleza/CE.

BRIAND, L.; MORASCA, S.; BASILI, V. (1994) “Defining and validating high-level design metrics”, CS-TR 3301, Univ. of Maryland, College Park.

BOSCH, J. (2000) Design and Use of Software Architectures, Addison-Wesley.

GHEZZI, C.; JAZAYERI, M.; MANDRIOLI, D. (1991) Fundamentals of Software Engineering, Englewood Cliffs, NJ., USA: Prentice Hall.

KICZALES, G. et al. (1997) “Aspect-Oriented Programming”, EUROPEAN CONFERENCE ON OBJECT-ORIENTED PROGRAMMING (ECOOP), LNCS (1241), Springer-Verlag, Finland.

MARTIN, R. (2003) Agile Software Development: Principles, Patterns, and Practices, Prentice Hall.

MARTIN, R. (1997) “Stability”, C++ Report.

OMG (2010) XMI, http://www.omg.org/spec/XMI/2.1.1/, May.

POHL, K., BOCKLE, G., van der LINDEN, F. (2005) “Software Product Line Engineering: Foundations, Principles and Techniques”, Springer.

SANT’ANNA, C. N. (2008) “On the Modularity of Aspect-Oriented Design: A Concern-Driven Measurement Approach”, Doctoral Thesis. PUC-Rio, Rio de Janeiro.

SANT’ANNA, C.; FIGUEIREDO, E.; GARCIA, A.; LUCENA, C. (2007) “On the Modularity of Software Architectures: A Concern-Driven Measurement Framework”, In: Proceedings of the 1st European Conference on Software Architecture, September, Madrid, Spain.

SANT’ANNA, C.; GARCIA, A.; CHAVEZ, C.; LUCENA, C.; von STAA, A. (2003) “On the Reuse and Maintenance of Aspect-Oriented Software: An Assessment Framework”, XVII SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE. Anais, p. 19-34.

SOARES, S.; LAUREANO, E.; BORBA, P. (2002) Implementing Distribution and Persistence Aspects with AspectJ, Proceedings of the 17th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA’ 02, ACM Press, p. 174–190, November.

van der LINDEN, F. SCHMID, K. ROMMES, E. (2007) “Software Product Lines in Action – The Best Industrial Practice in Product Line Engineering”, Springer.

WÜST, J. (2010) SDMetrics, http://www.sdmetrics.com/, May.


Um Algoritmo Genético Difuso Multiobjetivo para Descoberta de Conhecimento em Dados de Pesquisadores

Daniel Rossetto de Souza¹, Wesley Romão¹, Ricardo G. Coelho² , Itana M. S. Gimenes¹ e Ademir A. Constantino¹.

¹Departamento de Informática - Universidade Estadual de Maringá Maringá – PR.

²Campus Luiz Meneghel – Universidade Estadual do Norte do Paraná Bandeirantes – PR.

[email protected], [email protected], rgcoelho@ffalm. br, [email protected], [email protected]

Abstract. The knowledge discovery in databases process is composed of several steps, among which stands out data mining, which can be done by a heuristic algorithm. This paper proposes a multiobjective fuzzy genetic algorithm called AGDM for discovering prediction rules, using the Pareto dominance concept, based on the technique of non-dominated solutions to find the best combination of two objectives, these being accuracy and user interestingness. Experiments were conducted using researchers’ data provided by CNPq, aiming to generate rules about scientific production.

Resumo. O processo de descoberta de conhecimento é composto por diversas etapas dentre as quais se destaca a de mineração de dados, que pode ser realizada por algum algoritmo heurístico. Este trabalho propõe um algoritmo genético difuso multiobjetivo denominado AGDM para descobrir regras de previsão, utilizando o conceito de dominância de Pareto, baseado na técnica de soluções não-dominadas para encontrar a melhor combinação entre dois objetivos, sendo esses a taxa de acerto e o grau de interesse do usuário. Experimentos foram realizados utilizando dados sobre pesquisadores, fornecidos pelo CNPq, tendo como objetivo gerar regras sobre produção científica.

1. Introdução

Visando melhorar o apoio aos gestores em instituições de fomento a pesquisa, técnicas de mineração de dados (MD) têm sido aplicadas para explorar suas relações de causa e efeito tendo como desafio extrair conhecimentos que sejam corretos, compreensíveis, interessantes e, por fim, úteis. Estas técnicas podem ser aplicadas na área de Ciência e Tecnologia (C&T) a fim de apoiar decisões, em agências de fomento à pesquisa, visando incentivar a melhoria da produção científica.

Neste trabalho o objetivo é resolver a tarefa de classificação em MD, que tem como principal característica a capacidade de previsão de algum atributo meta (e.g.: quantidade de publicações em periódicos internacionais), baseado nos dados passados de produção científica de pesquisadores da região sul o Brasil.


2. Mineração de dados e descoberta de conhecimento

O processo de descoberta de conhecimento visa à extração de informações que não sejam óbvias e que sejam úteis para tomada de decisões. Estas informações devem ser caracterizadas como padrões existentes nos dados passados com validade estatística para prever a prevalência destes padrões nos dados futuros.

A descoberta de conhecimento é realizada essencialmente em três etapas: pré-processamento, mineração de dados (MD) e pós-processamento. A primeira etapa é a que requer mais tempo. Ela consiste em limpar, tirar ruídos e inconsistências dos dados para viabilizar a aplicação das técnicas de mineração. A etapa de MD envolve decidir quais algoritmos serão aplicados aos dados para encontrar algum conhecimento interessante. Para extrair conhecimento interessante, existem diversas técnicas de MD, tais como Estatísticas, Árvores de decisão, Algoritmos Evolucionários, entre outras.

Segundo Fayyad (1996), MD é “o processo não-trivial de identificar, em dados, padrões válidos, novos, potencialmente úteis e ultimamente compreensíveis”. Portanto os seguintes fatores nos padrões extraídos devem ser considerados:

- Validade: os padrões descobertos em dados passados devem ser válidos em novos dados com algum grau de certeza ou probabilidade;

- Novidade: os padrões devem ser previamente desconhecidos;

- Utilidade Potencial: os padrões devem ser úteis para a tomada de decisões;

- Compreensibilidade: deve-se representar os padrões em um formato assimilável ao conhecimento humano de modo que este possa aplicá-lo no mundo real.

A última etapa do processo de descoberta de conhecimento é o pós-processamento. Ela consiste em tornar os padrões encontrados adequados para o usuário aplicando técnicas de visualização e destacando apenas o conhecimento mais relevante.

2.1 Tarefas de MD

Tarefas são classes de problemas que podem ser resolvidos através de técnicas de MD. As principais tarefas são: associação, agrupamento e classificação.

A tarefa de associação tem caráter descritivo. Sua principal função é descobrir relações entre atributos em um determinado conjunto de dados. É muito empregada para se conhecer a natureza dos dados, mas não deve ser utilizada para previsão futura. Os algoritmos de associação geralmente geram regras do tipo “SE X ENTÃO Y”, sendo que cada lado da regra pode conter um ou mais atributos. O algoritmo de associação mais utilizado é o Apriori (Agrawal, 1993). Este pode encontrar todas as regras de associação entre os atributos em um conjunto de dados.

A tarefa de agrupamento consiste na divisão dos dados em grupos, chamados clusters. Para isso, um algoritmo que realiza essa tarefa deve descobrir a classe de cada instância baseado na similaridade deste com outras instâncias. Um algoritmo de agrupamento deve ser capaz de maximizar a semelhança entre os elementos de um mesmo grupo e minimizar as semelhanças entre exemplos pertencentes a grupos


diferentes. Normalmente não há como garantir se uma solução de agrupamento está correta ou não, mas é possível medir a similaridade entre os grupos encontrados.

A classificação é a tarefa de MD mais importante e também a mais complexa. Ela consiste em examinar as características de determinado objeto e então associar a este objeto uma classe. Cada objeto pode ser representado por um conjunto de atributos formando o antecedente (X) de uma regra do tipo: SE X ENTÃO Y.

Para resolver a tarefa de classificação deve-se inicialmente escolher, no conjunto de dados, quais serão os atributos previsores (X) e qual será o atributo meta (Y). Os atributos previsores da regra demonstram as características dos objetos enquanto o meta é o atributo ao qual o algoritmo de classificação, também chamado de classificador, deve prever a qual classe pertence.

Há dois tipos de classificadores: simples e múltiplo. Na classificação simples o atributo meta é binário, ou seja, seu domínio possui apenas dois valores possíveis (duas classes). Por exemplo, se um atributo meta pode assumir apenas os valores alto ou baixo, a missão do classificador é prever se cada regra pertence a classe "alto" ou a classe "baixo". Já na classificação múltipla o objeto pode pertencer a várias classes do atributo meta e o classificador deve indicar a qual delas pertence a regra.

Como esta tarefa tem caráter preditivo, as regras geradas devem ser avaliadas utilizando dados desconhecidos durante a fase de geração das regras. É necessário simular os dados futuros utilizando os dados conhecidos. Para isto, divide-se o conjunto de dados em duas partes, sendo que a maior parte é utilizada para o desenvolvimento do modelo de classificação e a outra parte é utilizada como conjunto de teste que simula a entrada de dados futuros.

Uma das formas de se realizar esta avaliação é utilizar a técnica denominada validação cruzada. Esta técnica consiste em dividir os dados disponíveis em k subconjuntos e executar em k iterações o algoritmo de MD. Em cada iteração, o algoritmo utiliza um desses subconjuntos para simular dados futuros e os demais para o desenvolvimento das regras. A avaliação será, então, a média da avaliação em cada iteração do algoritmo.

Para resolver a tarefa de classificação pode-se aplicar algum algoritmo heurístico. Neste trabalho foi aplicado um algoritmo genético em combinação com otimização multiobjetivo.

3. Algoritmos genéticos

Nas últimas décadas, algoritmos genéticos (AG) vêm sendo muito utilizados como métodos de busca e otimização em várias áreas, incluindo a área de MD. Outras razões para seu sucesso relacionam-se à busca global que eles realizam, à sua facilidade de uso e à vasta aplicabilidade nos mais diferentes domínios (Goldberg, 1989).

Através de analogias com a teoria da evolução natural proposta por Darwin, um AG inicia com uma população de indivíduos (possíveis soluções para um problema) aleatórios que evoluem por gerações procurando otimizar sua composição para solucionar determinado problema. O material genético de informação apresentada por cada


indivíduo é transferido para as gerações subseqüentes em diferentes modos no processo de otimização. Dentro desse método, existem três mecanismos básicos pelos quais a informação é escolhida, alterada e transferida para uma nova geração: seleção, cruzamento e mutação (Goldberg, 1989; Davis, 1991).

Os indivíduos possuem também uma função de avaliação, conhecida como função fitness. Esta função permite avaliar a qualidade do indivíduo de acordo com o objetivo a ser encontrado. A função de avaliação determina os melhores indivíduos no momento da seleção.

4. Otimização multiobjetivo

A otimização multiobjetivo é usada para buscar uma boa solução para problemas que possuem mais de um objetivo, levando todos em consideração. Grande parte dos problemas do mundo real envolve a otimização de múltiplos objetivos. Porém, a maioria dos métodos para resolução desses problemas evita as complexidades que um problema multiobjetivo envolve. Com isso, surgiram muitos métodos para converter problemas multiobjetivos em problemas com um único objetivo (DEB, 2001).

Em problemas com apenas um objetivo, busca-se encontrar uma única solução ótima. Já quando se trabalha com problemas com mais de um objetivo e estes são independentes, é comum encontrar não apenas uma solução ótima, mas um conjunto de soluções ótimas. O maior desafio desta área é utilizar um critério de avaliação justo para decidir qual é a melhor solução.

Segundo Castro (2001), existem duas correntes para da otimização multiobjetivo:

- definidas prioridades e/ou pesos entre os vários objetivos de interesse, encontra-se a solução ótima segundo estas informações fornecidas a priori;

- sem nenhuma informação adicional, encontra-se o conjunto das soluções ótimas de Pareto para dentre estas se escolher uma posteriormente.

Existem diversos métodos para tratar problemas com vários objetivos combinando-os em um único objetivo. O grande desafio é definir pesos ou prioridades sendo que ainda não se conhece como cada objetivo pode influenciar na busca da melhor solução. Também há métodos que retornam um conjunto de soluções ótimas para que seja feita uma escolha posterior.

4.1. Técnicas de análise multiobjetivo

Segundo Cohon e Marks (apud Jardim, p.18, 1999), as técnicas de análise multiobjetivo podem ser classificadas conforme a posição relativa entre analista e decisor. As técnicas de problemas determinísticos são classificadas em:

- Técnicas com antecipação de preferências;

- Técnicas com articulação progressiva de preferências e

- Técnicas de geração das soluções não-dominadas.


Nas técnicas com antecipação de preferências, o analista estabelece antecipadamente valores de peso sobre os objetivos. Já nas técnicas com articulação progressiva de preferências ocorrem interações entre o classificador e o analista e este pode fazer ajustes de acordo com resultados parcialmente encontrados. Por fim, nas técnicas de geração das soluções não-dominadas o classificador gera todas as soluções que não são dominadas para que o analista determine a ação a ser tomada. Neste caso, um problema com muitos objetivos pode tornar esta tarefa confusa para o analista.

4.2. Métodos de otimização

Na maioria dos casos as soluções ótimas individuais de cada objetivo são diferentes. Tais soluções podem ser vistas como pontos no espaço de busca que são otimizadas em cada objetivo. Para encontrar tais pontos, os métodos clássicos convertem todos os objetivos em um único objetivo.

4.2.1. Agregação de objetivos

A agregação de objetivos é o método mais simples utilizado em problemas onde são considerados mais de um objetivo. Também chamado de ponderação de objetivos, o método consiste em considerar o objetivo final como a soma das multiplicações de cada objetivo com seu respectivo peso. Ela é utilizada quando o usuário possui amplo domínio sobre a importância de cada objetivo no problema e pode, então, definir de modo adequado os pesos dos mesmos. Segundo Srinivas e Deb (1994), este método possui a única vantagem de que a ênfase de um objetivo sobre o outro pode ser controlada e a solução obtida geralmente pertence ao conjunto ótimo de Pareto.

Segundo Fonseca e Fleming (1995) a otimização de uma combinação dos objetivos tem a vantagem de produzir uma solução com um objetivo único, não exigindo maior interação com o tomador de decisão. O problema é que, se a solução ótima não pode ser aceita, devido à função utilizada excluindo os aspectos do problema que eram desconhecidos antes da otimização ou de um ajuste inadequado dos coeficientes da função, pode ser necessário rodar de novo o algoritmo de MD até que uma solução adequada seja encontrada.

4.2.2 Minimização de energia

O método de minimização de energia é um método adaptativo de agregação de objetivos. A estratégia do método de minimização de energia procura, em primeiro lugar, resolver o principal desafio do método de agregação de objetivos: a escolha dos pesos de cada objetivo. Este método caracteriza-se pela atualização dos pesos dinamicamente ao longo do processo evolutivo. Ele estabelece pesos maiores para os objetivos que forem menos satisfeitos pela população, fazendo com que os objetivos menos encontrados sejam mais valorizados.

Segundo Srinivas e Deb (1994), a solução obtida depende do vetor de nível de demanda que contem os valores definidos pelo decisor e a seleção arbitrária de um nível de demanda pode ser altamente indesejável. Isto porque um nível de demanda errado levará a uma solução não pertencente ao conjunto ótimo de Pareto.


4.2.3 Minimização-maximização da distância

O método de minimização-maximização da distância ao objetivo avalia uma solução calculando a distância entre o vetor de medidas formado pelas avaliações e as especificações do usuário para cada objetivo. Fazendo isso, ele penaliza soluções com baixo desempenho em algum objetivo, sendo que cada vez mais se priorizem soluções que não fracassem em nenhum aspecto, mesmo que não sejam ótimas em algum objetivo em particular.

Segundo Srinivas e Deb (1994), este método pode render a melhor solução possível quando os objetivos requeridos para serem otimizados possuírem prioridade igual. Este método depende da decisão do usuário para definir o vetor sobre o qual serão feitas as comparações.

A maior desvantagem desta estratégia é a forte possibilidade de prenderem-se a ótimos locais e a usual obtenção de solução única, já que operam iterativamente com um candidato por vez (Castro, 2001).

4.3 Estratégia de Pareto

Trabalhando-se com mais de um objetivo, nem sempre podemos dizer que uma solução é melhor que outra. Existem casos onde uma solução apresenta melhor desempenho em um aspecto, enquanto outra solução tem melhor desempenho em outro aspecto. Muitas vezes, não existe uma única solução ótima, mas sim, um conjunto de soluções alternativas. Essas soluções são ótimas quando nenhuma outra solução no espaço de busca é superior a elas considerando todos os objetivos. Essas soluções ótimas denominam-se soluções ótimas de Pareto (Zitzler e Thiele, 1999).

Quando se utiliza a estratégia de Pareto, os objetivos não precisam ser combinados para se avaliar uma solução. Sendo assim, uma solução não pode ser descartada sem que se encontre uma que a supere em todos os objetivos considerados. Esta característica denomina-se Princípio de Otimalidade de Pareto.

Esta abordagem possui a vantagem de não exigir que as avaliações sejam normalizadas, pois não combina avaliações de diferentes objetivos.

Quando se compara duas soluções, deve-se considerar o conceito da dominância de Pareto. Dizemos que uma solução x1 domina uma solução x2 se e somente se duas condições são satisfeitas: a solução x1 não é pior que x2 em nenhum dos objetivos; e a solução x1 é estritamente melhor que a solução x2 em pelo menos um objetivo.

Todas as soluções que não são dominadas por nenhuma outra solução são consideradas soluções ótimas de Pareto.


5. O algoritmo proposto

Neste trabalho propõe-se um Algoritmo Genético Difuso Multiobjetivo (AGDM) que tem como intuito a descoberta de regras de classificação, denominadas pepitas de conhecimento, utilizando os conceitos de otimização multiobjetivo. Portanto, está fundamentado em algoritmos genéticos.

Os dados aos quais o algoritmo foi aplicado se referem a pesquisadores do CNPq da região sul do Brasil. São considerados atributos de localização, área de conhecimento, experiência do pesquisador, entre outros.

Os atributos utilizados como meta são os diretamente ligados a publicações. São considerados os atributos "artigos em periódicos nacionais", "artigos em periódicos", "capítulos publicados em livros", além de “edições de livros publicadas”.

O AGDM é uma extensão do algoritmo genético difuso proposto por Romão (2002). A principal contribuição do AGDM é a utilização da estratégia de Pareto na fase de seleção de indivíduos. A figura 1 mostra o pseudo-código do AGDM.

Figura 1. Pseudo-código do AGDM.

5.1 Representação do indivíduo

Cada indivíduo dentro da população representa uma regra do tipo:

SE <antecedente> ENTÃO <consequente>

O <antecedente> é um conjunto não-vazio de atributos previsores (no formato “atributo = valor”) e o <consequente> é o atributo meta no formato “atributo = valor”, onde o valor também é denominado classe. Em termos de implementação, cada indivíduo possui dois vetores: um contendo os valores de todos os atributos e outro contendo flags que indicam quais atributos estão ativos e quais estão inativos na regra.

PARA CADA ATRIBUTO META: FORMAR POPULACAO; PARA CADA GERAÇÃO: PARA CADA INDIVIDUO DA POPULAÇÃO: CALCULAR TAXA DE ACERTO; CALCULAR GRAU DE INTERESSE; CALCULAR INDIVÍDUOS DOMINADOS; NOVA POPULAÇÃO <= POPULAÇÃO VAZIA; ENQUANTO NOVA POPULAÇÃO NÃO ESTÁ CHEIA:

INDIVIDUO1, INDIVIDUO2 <= SELEÇÃO(ANTIGA POPULAÇÃO); CRUZAMENTO(INDIVIDUO1, INDIVIDUO2); MUTAÇÃO(INDIVÍDUO1); MUTAÇÃO(INDIVÍDUO2); INSERÇÃO / REMOÇÃO(INDIVÍDUO1); INSERÇÃO / REMOÇÃO(INDIVÍDUO2) ; NOVA POPULAÇÃO += INDIVÍDUO1, INDIVÍDUO2; POPULAÇÃO <= NOVA POPULAÇÃO; ESCOLHER MELHOR REGRA;


Os atributos numéricos passam por um processo chamado de “fuzzificação”. Este processo consiste na discretização de tais valores, ou seja, os valores numéricos passam a assumir classes como “baixo”, ”médio” ou “alto” de acordo com parâmetros fornecidos pelo usuário.

As regras são avaliadas segundo dois objetivos: taxa de acerto e grau de interesse. A taxa de acerto mostra se a regra realmente é válida. Para isso, calcula-se sobre o conjunto de dados a precisão desta regra. O grau de interesse é uma métrica que tem relação com a relevância da regra para o usuário. Uma regra é interessante para o usuário quando contradiz as expectativas iniciais do mesmo. Para tanto, o usuário fornece um conjunto de regras que ele espera encontrar nos dados, denominadas impressões gerais. Considera-se que quanto mais uma regra contradiz uma impressão geral, menos óbvia para o usuário e provavelmente maior seu grau de interesse (Silberschatz, 1996).

5.2 Seleção de indivíduos

A seleção dos indivíduos é realizada por um método denominado "torneio", com k=2 (Back, 2000). São escolhidos aleatoriamente dois indivíduos dentro da população atual e ambos são comparados para decidir qual deles irá para cruzamento. São considerados dois objetivos: taxa de acerto e grau de interesse. A estratégia de Pareto é utilizada para fazer esta comparação. Se uma regra domina a outra, ela é selecionada. Caso nenhuma das regras apresente dominância, é selecionada a regra com maior número de indivíduos dominados na população atual. Em caso de empate, uma das duas é selecionada aleatoriamente.

5.3 Operadores genéticos

Os operadores genéticos aplicados foram: cruzamento, mutação e inserção/remoção de atributos.

O cruzamento pode ocorrer com uma probabilidade de 85% sobre dois indivíduos selecionados pelo torneio. Caso o cruzamento não ocorra, os dois indivíduos passam para a próxima geração sem trocar genes. Após o cruzamento, aplica-se a mutação com probabilidade de apenas 2%. Quando um gene é alterado, o que muda é o valor de um atributo ativo na regra.

A inserção e remoção de atributos ocorrem com probabilidades também baixas. A inserção ocorre com probabilidade de 2% enquanto a remoção ocorre com probabilidade de 1%. Porém caso uma regra se encontre com menos atributos ativos do que a quantidade mínima permitida, é aplicada uma inserção com probabilidade 100%. Do mesmo modo, se uma regra possui mais que a quantidade máxima de atributos ativos, é aplicada uma remoção com probabilidade de 100%.

5.4 Avaliação das soluções encontradas

Após todas as gerações do AG, encontra-se uma população final resultante de todo o processo evolutivo. A partir das regras presentes na população final, é realizada a extração do conjunto ótimo de Pareto contendo todas as regras não-dominadas por outras regras dentro desta população. Dentro do conjunto ótimo de Pareto verifica-se qual regra


possui maior quantidade de indivíduos dominados. Esta regra é escolhida, então, como a melhor regra gerada pelo algoritmo.

6. Resultados computacionais e análise

Os experimentos com o AGDM foram realizados em duas fases: a primeira fase para validação do algoritmo e a segunda para descoberta de regras relevantes. Em ambas as fases foram utilizados seis atributos metas:

- Artigos publicados em periódicos nacionais; - Artigos publicados em periódicos internacionais; - Capítulos de livros nacionais; - Capítulos de livros internacionais; - Edições publicadas de livros nacionais; - Edições publicadas de livros internacionais.

A primeira fase do experimento foi realizada através da validação cruzada.

Tabela1. Validação cruzada para o AGD e o AGDM

Consequente Taxa de acerto (%) Grau de interesse (%)

Atributo Meta Classe AGD

(ã ± dp) AGDM (ã ± dp)

AGD (ã ± DP)

AGDM (ã ± dp)

Baixo 55.8 ± 3.7 72.9 ± 9.9 70.0 ± 8.2 41.7 ± 3.5

Médio 58.5 ± 2.0 64.9 ± 14.7 50.0 ± 0.0 22.5 ± 1.3 Artigos em periódicos nacionais

Alto 5.0 ± 5.0 5.5 ± 2.0 29.0 ± 1.8 40.0 ± 5.1

Baixo 61.6 ± 2.1 98.0 ± 1.5 95.0 ± 5.0 38.3 ± 5.0

Médio 36.0 ± 11.7 20.0 ± 11.3 37.5 ± 4.2 21.3 ± 1.6 Artigos em periódicos

internacionais Alto 10.0 ± 10.0 10.0 ± 10.0 22.2 ± 2.9 32.9 ± 6.2

Baixo 56.2 ± 4.4 98.0 ± 2.0 95.0 ± 5.0 0.0 ± 0.0

Médio 30.0 ± 15.3 48.7 ± 12.6 24.2 ± 0.8 24.2 ± 0.8 Capítulos em

livros nacionais

Alto 21.1 ± 13.2 18.6 ± 5.0 24.5 ± 2.0 41.7 ± 2.8

Baixo 94.8 ± 0.8 100.0 ± 0.0 80.0 ± 8.2 40.0 ± 5.1 Capítulos em livros


Baixo 94.1 ± 1.1 97.5 ± 1.5 100 ± 0.0 48.3 ± 7.6 Edições de livros

nacionais Alto 12.5 ± 9.9 28.3 ± 13.2 45.8 ± 9.1 0.0 ± 0.0

Baixo 78.5 ± 13.1 100.0 ± 0.0 70.0 ± 8.2 35.0 ± 7.6 Edições de livros



Os resultados foram comparados com o Algoritmo Genético Difuso (AGD), apresentado em Romão (2002). A tabela 1 compara os resultados alcançados com cada um dos algoritmos. Os resultados se referem à média (ã) e desvio padrão (dp) dos acertos em todas as partições.

Pode-se notar que o AGDM obteve, em geral, melhores resultados com relação à taxa de acerto, enquanto o AGD se mostrou mais eficiente em encontrar regras com alto grau de interesse.

Após a descoberta do modelo, realizou-se a segunda fase do experimento onde as regras foram novamente descobertas e os valores de taxa de acerto e grau de interesse foram recalculados utilizando todos os dados disponíveis a fim de descobrir as melhores regras no espaço de busca.

A seguir são apresentadas três figuras contendo algumas das melhores regras do AGD comparadas às do AGDM utilizando o atributo meta “Artigos em periódicos nacionais” com as classes "baixo" (Figura 2), "médio" (Figura 3) e "alto" (Figura 4).

Figura 2. Regras encontradas para “Artigos em perió dicos nacionais = baixo”.

Conforme pode-se observar na Figura 2 e na Figura 3 o AGDM conseguiu explorar um espaço de busca maior, devido à utilização da Estratégia de Pareto para a agregação de objetivos, obtendo um conjunto maior de regras com mais equilíbrio entre os dois objetivos.


Figura 3. Regras encontradas para “Artigos em perió dicos nacionais = médio”.

Pode-se observar também que diferentes soluções foram escolhidas como a melhor por cada um dos algoritmos.

Conforme previsto no modelo descoberto pode-se observar que, para este atributo, nas melhores regras descobertas pelo AGD prevalece o grau de interesse, enquanto o AGDM prioriza a taxa de acerto.

Figura 4. Regras encontradas para “Artigos em perió dicos nacionais = alto”.

7. Conclusões

O objetivo deste trabalho foi encontrar técnicas de auxílio à tomada de decisões. Os resultados obtidos com o AGDM demonstram que o mesmo é capaz de extrair pepitas de conhecimento, a partir de dados, que podem auxiliar gestores na tomada de decisões em instituições que promovem e fomentam a pesquisa no Brasil.


A avaliação do AGDM foi realizada por meio de experimentos realizados com dados da área de C&T obtidos do CNPq, visando encontrar conhecimento relevante no que diz respeito à produtividade dos pesquisadores. O AGDM pode viabilizar um melhor conhecimento da realidade dos pesquisadores da região sul do Brasil, possibilitando suporte à tomada de decisões no fomento a C&T.

Os resultados dos testes de validação do algoritmo mostraram que o AGDM mostrou-se mais eficiente quanto à taxa de acerto quando comparado com o AGD, sem deixar de considerar o grau de interesse. De modo geral, o AGDM encontrou regras mais específicas que o AGD, ou seja, regras com mais atributos previsores.

Os resultados obtidos revelam que ambos os algoritmos avaliados consideram os dois objetivos, mas o AGD prioriza o grau de interesse e o AGDM prioriza a taxa de acerto. Entretanto o AGDM apresenta um conjunto maior de regras contendo o equilíbrio entre os dois objetivos comprovando a sua eficácia.

Como pesquisas futuras pretende-se investigar possíveis melhorias nos algoritmos implementados e experimentos com outros algoritmos heurísticos visando à melhoria dos resultados buscando a maximização dos dois objetivos.

Referências

Agrawal, R.; Imielinski, T. and Swami, A.. “Mining association rules between sets of items in large databases”, Proc. ACM SIGMOD Int'l Conf. Management of Data, vol. 22, pp.207-216, 1993.

Back, T.; Fogel, D. B. and Michalewicz, Z. Evolutionary Computation 1: Basic Algorithms and Operators. Chapter 24: Blickle T. Tournament selection. Institute of Phisics Publishing, 2000.

Castro, R. E. Otimização de Estruturas com Multi-objetivos via Algoritmos Genéticos. Programa de Pós-graduação em Engenharia Civil, COPPE/UFRJ. Tese de doutorado, UFRJ, 2001.

Davis, L. Handbook of genetic algorithms. New York:Van Nostrand Reinhold, 1991.

Fayyad, U.,; Piateski, S. and Smyth, P. The KDD Process for Extracting Useful Knowledge from Volumes of Data. In: Communications of the ACM, November 1996/vol. 39, no. 11, p. 27-34.

Fonseca, C. M.; Fleming, P. J. An Overview of Evolutionary Algorithms in Multiobjective Optimization. Evolutionary Computation. Vol. 3, no. 1. Spring (1995) 1-16 3(4), p. 257-271, 1999.

Goldberg, D. E. Genetic algorithms in search, optimization, and machine learning. New York: Addison-Wesley Publishing Company, Inc., 1989.

Jardim, S. B. Aplicabilidade de algumas técnicas de análise multiobjetivo ao processo decisório no âmbito de comitês de gerenciamento de bacia hidrográfica. Programa de Pós-Graduação Programa em Engenharia dos recursos hídricos e saneamento


ambiental, Universidade Federal do Rio Grande do Sul - Instituto de pesquisas hidráulicas, Porto Alegre – RS. Dissertação de Mestrado, UFRG, 1999.

Romão, W. Descoberta de conhecimento interessante em banco de dados sobre ciência e tecnologia. Programa de Pós-Graduação em Engenharia de Produção, Florianópolis – SC. Tese de doutorado, UFSC, 2002.

Silberschatz, A.; Tuzhilin, A. What Makes Patterns Interesting in Knowledge Discovery Systems. IEEE Transactions on Knowledge and data engineering, Vol. 8(6), pp. 970-974, 1996.

Srinivas, N. and Deb, K. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation on Vol 2(3), pp 221-248, 1994.

Zitzler E. and Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. In: IEEE Transactions on Evolutionary Computation Vol 3(4), pp 257-271, 1999.


Sistema Embarcado para Monitoramento Aplicado à Viticultura

Paulo Henrique Sabo, Paulo Cesar Gonçalves, João Angelo Martini, Elvio João Leonardo

Departamento de Informática – Universidade Estadual de Maringá (UEM) CEP 87020-900 – Av. Colombo, 5790 – Maringá – PR – Brasil

{phsabo,paulocg,joaomartini , elvio.leonardo}@gmail.com

Abstract. This article describes the development and construction of a weather monitoring system for agricultural purpose. The system’s first intended users are small grape growers, members of a cooperative which produces wine in the city of Marialva, Brazil. The system includes micro weather stations, placed in the field and used, with their sensors, to collect relevant agro-meteorological data. Also, there is a coordinator node, responsible for the general system management, including to maintain the wireless links connecting it to the weather stations, and to receive and to storage the data from the weather stations. At the moment of writing, a system prototype is already available for testing.

Resumo. Este artigo descreve o desenvolvimento e construção de um sistema meteorológico para fins agrícolas. Os usuários alvos do sistema são os pequenos produtores de uva, membros de uma cooperativa que produz vinho, na cidade de Marialva, Brasil. O sistema inclui microestações meteorológicas, colocadas no campo e usadas, com seus sensores, para coletar dados agro meteorológicos relevantes. Além disso, existe um nó coordenador, responsável pela gestão do sistema em geral, inclusive para manter as ligações wireless conectando às estações meteorológicas, e para receber e armazenar os dados das estações meteorológicas. Em meio à pesquisa, um protótipo do sistema já está disponível para testes.

1. Introdução Atualmente a fruticultura tem representado um potencial econômico de grande

importância para os agricultores familiares, pois propicia boa rentabilidade em áreas de terra relativamente pequenas. A produção de uva no Brasil em 2007 foi de 1.354.960 toneladas, apresentando um crescimento de 11,04% em relação ao ano de 2006. Desse total, 47,02% foram destinados à elaboração de vinhos, sucos e outros derivados [MELLO, 2007] [MELLO, 2008]. O setor de viticultura tem recebido ultimamente grandes investimentos, principalmente em regiões não tradicionais do país, dada a característica da cultura, geradora de empregos e renda, especialmente para a pequena propriedade. O estado do Paraná apresenta predomínio de pequenas e médias propriedades rurais enquadradas como unidades produtivas familiares. A região noroeste do estado apresenta características de solo e clima com condições favoráveis à fruticultura, tendo potencial para viabilizar economicamente propriedades familiares.


As cidades de Maringá e Marialva estão inseridas na área de abrangência da AMUSEP (Associação dos Municípios do Setentrião Paranaense), o qual congrega 30 municípios e cerca de 700.000 habitantes. Marialva abriga uma vinícola criada pela união de 25 produtores de uva que formaram a Cooperativa Agroindustrial dos Viticultores (COAVITI), com apoio do programa Paraná 12 Meses. Esta cooperativa produz o vinho Coaviti. No futuro, os cooperados pretendem produzir também outros produtos derivados da uva. Iniciativas do governo do Paraná têm fortalecido o desenvolvimento da agricultura familiar paranaense no contexto do cultivo da uva para produção do vinho, como exemplo pode-se citar a implantação da Escola da Uva e do Vinho. A expectativa é que o Paraná se torne um forte polo de vinícola na região sul fortalecendo mais sua economia [MAZIA, 1998] [PIANI, 2001]. Segundo o Jornal O Diário do Norte do Paraná [2007], recentemente a prefeitura de Maringá entregou à comunidade de Iguatemi uma fábrica de polpa de frutas. Esta que terá capacidade para processar aproximadamente 500 quilos de frutas por hora . Para dar início à comercialização destes sucos a Secretaria do Meio Ambiente e Agricultura doou 34.600 mudas de maracujá para a Associação dos Produtores Rurais de Iguatemi e outros produtores que serão responsáveis pelo plantio. Além de maracujá, outras frutas como morango, acerola, manga, abacaxi, uva e goiaba também serão processadas pela fábrica. A intenção da Secretaria do Meio Ambiente e Agricultura é transformar a região num polo de fruticultura. Apesar destes fatores positivos, nota-se ainda que, há carência de informações e tecnologias para que seja possível oferecer e aprimorar o suporte à produção e comercialização nessa área. Esse fato gera demanda pelo desenvolvimento de tecnologias que possibilitem a produção econômica de frutas saudáveis. [BRUCKNER; PICANÇO, 2001] [BURRELL; BROOKE; BECKWITH, 2004] [WARK et al., 2007] e seguras para a alimentação humana, e que favoreçam o desenvolvimento da agricultura familiar na região. Para atender a essa crescente demanda por informações e tecnologias na área de fruticultura, foi proposto um projeto, com apoio da Fundação Araucária, que visa desenvolver um sistema computacional integrado de apoio à agricultura familiar focado inicialmente na cultura de uva. Por meio desse sistema pretende-se efetuar a coleta de dados agro meteorológicos em campo e tratar as informações coletadas de maneira a oferecer uma base de dados ao agricultor, que a partir das informações oferecidas pelo sistema possa elaborar o planejamento adequado do manejo da cultura da uva, e colher todos os benefícios advindos do uso dessa tecnologia de apoio. O projeto tem três frentes de trabalho: a) estação de coleta de dados, b) comunicação entre estações e c) receptor base. Essas três frentes serão discutidas nas seções subsequentes. O enfoque do presente trabalho se concentra na estação coletora de dados. Este artigo está organizado da seguinte maneira. A Seção 2 apresenta os fundamentos de monitoramento de dados agro meteorológicos aplicados à viticultura. A Seção 3 discute trabalhos relacionados para contextualizar a proposta do projeto. Na Seção 4 a proposta de um modelo de estação de monitoramento é apresentada e os resultados são discutidos na Seção 5. A Seção 6 apresenta as conclusões e propõe trabalhos futuros.


2. Monitoramento aplicado à viticultura As propriedades dos cooperados da COAVITI têm em média de 1 a 2 hectares,

onde são destinados por volta de 50% da área para produção de uva. Essa área é dividida em pequenos parreirais retangulares de aproximadamente 100m² onde são cultivadas variedades de uva de vinho e de mesa. A COAVITI tem como meta produzir, por ano, 30 mil litros de vinhos tinto, branco e rose, provenientes de espécies Niágara, Isabel, Bordô e Itália.

Para que o cultivo da uva aconteça de modo favorável e com qualidade alguns elementos meteorológicos são muito relevantes no monitoramento. Segundo Tonietto e Mandelli [2003] a videira é influenciada por: temperatura, chuva, radiação solar, vento e umidade do ar.

Como um dos elementos influenciadores no cultivo a temperatura do ar apresenta diferentes efeitos sobre a videira, variáveis em função das diferentes fases do ciclo vegetativo ou de repouso da planta. Durante o inverno a videira se encontra em período de repouso vegetativo. O frio é importante para a quebra de dormência das gemas, no sentido de assegurar uma brotação adequada para a videira. Em anos com inverno menos rigoroso pode ocorrer menor índice de quebra de dormência das gemas da videira, sendo necessária a aplicação de alguns produtos químicos para a quebra. Geadas podem causar a destruição dos órgãos herbáceos da planta. No verão altas temperaturas podem resultar na obtenção de uvas com maiores teores de açúcares, menor acidez e, nas cultivares tintas, menor intensidade de cor. E por último, no outono a temperatura afeta o comprimento do ciclo vegetativo da videira, o que é importante para a maturação dos ramos e a acumulação de reservas pela planta. A ocorrência de geadas outonais acelera a queda das folhas e o fim do ciclo vegetativo da planta.

Outro dado importante está relacionado com a precipitação pluviométrica durante a primavera, este fator é fundamental para o desenvolvimento da planta, porém, em excesso, pode favorecer o desenvolvimento de algumas doenças fúngicas da parte aérea, bem como afetar fases importantes da videira, como a floração e a frutificação, causando baixo vingamento de frutos e desavinho.

Um dos fatores que influenciam no desenvolvimento da videira é a luz. Como ela exige alta luminosidade para que seja considerada de qualidade, torna-se importante que o período de maturação aconteça em dias ensolarados, visto que há evolução do teor de açúcar das uvas nestas condições.

Uma dificuldade encontrada em locais com umidade relativa do ar elevada é que os vinhedos localizados nestas áreas poderão estar mais sujeitos à incidência de doenças fúngicas.

Outro problema que pode dificultar na produtividade da uva é o vento que pode causar danos à vegetação, pois os ramos jovens se quebram com relativa facilidade, resultando na diminuição da produção do vinhedo e em dificuldades na poda de inverno.

Para a categorização da região produtora, ou seja, para que haja classificação da qualidade da uva e até determinação de uma melhor espécie para cultivo de acordo com os aspectos meteorológicos da região é utilizado atualmente o Sistema de Classificação Climática Multicritérios (CCM) Geovitícola, que foi desenvolvido para melhorar a


caracterização do clima vitícola das regiões produtoras de vinho no mundo [EMBRAPA UVA E VINHO, 2010].

O Sistema CCM foi idealizado dentro do conceito de Geoviticultura, que corresponde ao processamento da informação vitícola em escala mundial [TONIETTO, 1999]. A Geoviticultura aplicada ao clima possibilita identificar e comparar o clima vitícola das regiões, caracterizar sua variabilidade mundial e estabelecer grupos climáticos de regiões produtoras apresentando certa similaridade de potencial climático.

Por ser multicritério (3 índices climáticos), ele amplia a caracterização dos fatores climáticos que implicam na adaptação das variedades, na qualidade de uva (açúcar, acidez, cor, aroma) e na tipicidade dos vinhos. Esses índices são:

• Índice Heliotérmico (IH). É um índice climático vitícola desenvolvido por Huglin (1978), que estima o potencial heliotérmico de uma condição climática específica; o cálculo das temperaturas estima o período do dia no qual os metabolismos da videira estão mais ativos; o índice também inclui um fator de correção para o comprimento do dia em latitudes mais elevadas de cultivo da videira. O IH está bastante relacionado às exigências térmicas das variedades, bem como ao conteúdo potencial de açúcar das uvas.

• Índice de Frio Noturno (IF). É um índice climático vitícola desenvolvido para estimar a condição nictotérmica (relacionada à concentração dos componentes aromáticos das uvas e coloração em uvas tintas) associada ao período de maturação das uvas [TONIETTO, 1999][TONIETTO; CARBONNEAU, 2004]. Através da análise das temperaturas mínimas noturnas, o índice serve como indicador das características potenciais das regiões em relação aos metabólitos secundários (polifenóis, aromas, cor) nas uvas e vinhos.

• Índice de Seca (IS). É um índice climático vitícola que caracteriza o componente hídrico de uma região, fortemente relacionado com as características qualitativas da uva e do vinho. O IS foi adaptado [TONIETTO, 1999][TONIETTO; CARBONNEAU, 2004] a partir do balanço hídrico potencial do solo de Riou [RIOU et al., 1994]. Informa a disponibilidade hídrica potencial do solo, levando em consideração a demanda climática em um vinhedo padrão, a evaporação em solo desnudo e a precipitação pluviométrica sem dedução do escoamento superficial do solo.

3. Trabalhos Relacionados O projeto i-Farm [AGRI-CIÊNCIA, 2007] é desenvolvido em Portugal e aplicado

à viticultura. Ele integra tecnologias com soluções móveis, redes de sensores, comunicações sem fios e imagens aéreas, no contexto de exploração agrícola, utilizando o conceito de agricultura de precisão [CASTRO NETO, 2008], para formar um sistema de informação que fornece serviços que auxiliam o processo de tomada de decisão do agricultor, considerando variáveis ambientais, sanitárias, econômicas, etc. As informações coletadas pelas redes de sensores podem ser utilizadas para aumentar a produção, reduzir aplicações de produtos químicos, fertilizantes, água, etc. e promover uma agricultura mais sustentável, além de assegurar, aos consumidores finais, maior segurança e qualidade alimentar.

CERERE [UNIVERSITÀ DEGLI STUDI DI PAVIA, 2008] é um projeto italiano e consiste em um sistema de monitoramento vitícola. Pretende ser completo para as


necessidades do produtor, fácil para o agricultor usar e barato em relação a outras estações comerciais disponíveis no mercado. Tem por objetivo criar uma solução, utilizando rede de sensores sem fio (RSSF), com uso de tecnologias baratas, como Arduino e XBee. Utiliza nós Squidbee [LIBELIUM, 2008], normalmente equipados com sensores de temperatura, umidade e luminosidade [DE STEFANI, 2008]. Desempenha um papel importante na preservação do meio ambiente, reduzindo o consumo de água e fornecendo alertas precoces de geada ou danos causados pela alta temperatura, através da análise dos dados provenientes dos sensores. O sistema não possui nenhum mecanismo de economia de energia, seu aplicativo de Web oferece funções básicas. O sistema não trata da segurança em redes de sensores, que é um problema crítico a ser resolvido. Todo o software desenvolvido pelo projeto está disponível gratuitamente e é liberado sob a licença GNU/GPL. O projeto Weather Station [HISCOCKS, 1994] consiste em um laboratório no qual os alunos devem: desenvolver um sistema eletrônico de uma estação meteorológica, utilizando componentes analógicos e microprocessador; desenvolver circuitos que necessitam de cuidados na seleção de componentes, aterramento e blindagem; obter experiência em calibração e verificação do desempenho de um sistema analógico; projetar e construir software para um sistema embarcado.

O Wireless Weather Station [WASINGER, 2001] foi desenvolvido com o intuito de prover uma estação meteorológica instalada no quintal, para regiões onde as condições do clima mudam drasticamente pela ocorrência de trovoadas, depressões tropicais, tornados, tempestades, linhas de instabilidade, frentes estacionárias, frentes frias do Canadá, ar quente e úmido do Golfo, e furacões. É composto por uma estação remota e uma estação base. A primeira é movida à energia solar e é ativada uma vez por minuto para coletar e transferir dados. A estação base recebe e armazena os dados de entrada e, em seguida, os transfere através de uma conexão RS-232 a um PC, para processamento. Em cada uma das estações há um sistema embarcado, bem como uma placa de circuito separado de RF.

4. Proposta de Modelo de Estação de Monitoramento O projeto tem como objetivo, o desenvolvimento de um sistema de

monitoramento vitícola (Figura 1), tendo como alvo as propriedades da COAVITI. O sistema consiste no conjunto de microestações agro meteorológicas de coleta dados provenientes dos sensores instalados na plantação correspondente. Fazendo uso de dispositivo de comunicação sem fio essas microestações formarão uma rede (esta rede deve continuar funcionando e se adaptar a situações em que uma microestação seja excluída ou inserida na rede). Outro dispositivo, dotado também de comunicação sem fio e com acesso à Internet, será responsável por fazer a gerência da rede, coletar os dados agro meteorológicos e transferi-los para um banco de dados (onde estarão armazenados os dados de todas as redes de microestações). Através de um sistema Web os produtores poderão consultar (por meio de tabelas e gráficos) os dados de suas propriedades como também compará-los com os dados de outras propriedades da região.


Figura 1. Visão geral do sistema

A microestação (Figura 2) é construída sob a plataforma Arduino [ARDUINO, 2005], nela estão conectados: relógio, dispositivo de armazenamento, dispositivo de comunicação sem fio e os sensores, que fazem o monitoramento do microclima.

Figura 2. Componentes da microestação

Internet Estações

Usuário

Gerenciador

da rede

Estações

Servidor

WWW Gerenciador

da rede

Arduino

Temperatura e

umidade do ar

Luminosidade Velocidade e

direção do Vento

Relógio

Molhamento

foliar Cartão SD

Pluviosidade

Umidade

do solo ZigBee


Os sensores coletam informações sobre temperatura e umidade do ar, umidade do solo, velocidade e direção do vento, pluviosidade e luminosidade, os quais são elementos meteorológicos importantes a serem monitorados de acordo com Tonietto e Mandelli [2003] e também suficientes para classificação da uva segundo o sistema CCM Geovitícola [EMBRAPA UVA E VINHO, 2010].

Através de reuniões com os cooperados, foram adquiridas informações relevantes para a inclusão de sensor de molhamento foliar a ser utilizado para a prevenção de doenças fúngicas como o míldio.

Na microestação são configurados: data, hora e frequência de leitura/hora dos sensores. No instante especificado a microestação faz a leitura de todos os sensores e armazena as informações. Acumula as informações dos sensores até que o gerenciador estabeleça uma conexão com a estação e solicite a transferência dos dados. Feita a solicitação a estação transfere os dados e os elimina da memória.

O gerenciador é responsável por fazer a configuração das microestações, coletar os dados das microestações, tratá-los e transferi-los para um banco de dados.

No sistema Web é possível consultar os dados através de tabelas e gráficos, salvar gráficos relevantes, renomear microestações e calibrar sensores.

O sistema deve funcionar de maneira semiautônoma (ter pouca ou nenhuma interferência humana durante a coleta dos dados meteorológicos), ter baixo custo de produção, e pouca manutenção, viabilizando ao pequeno produtor que não tem conhecimento na área de tecnologia de informação e comunicação, um sistema barato e fácil de utilizar que possa agregar valor ao produto final.

5. Resultados Atualmente o primeiro protótipo da microestação está operacional, um shield

(Figura 3) foi desenvolvido para a placa Arduino na qual são conectados os componentes como relógio, cartão SD, sensores e XBee.

XBee é um módulo de comunicação sem fio baseado em ZigBee. ZigBee é uma nova tecnologia voltada para aplicações nas mais variadas áreas. Destinado a baixas taxas de transmissão de dados nos campos industrial, científico e médico. A tecnologia, baseada no padrão IEEE 802.15.4, tem se mostrado promissora para rede de sensores, monitoramento e controle [ERGEN, 2004].

A conexão é feita pelo gerenciador da rede que determina com qual estação deseja se comunicar e estabelece uma conexão. Esse tipo de conexão fica transparente à microestação. É como uma conexão direta, ponto a ponto, entre a microestação e o gerenciador. Às vezes são utilizadas outras microestações que estão no meio do caminho como roteadores, o módulo XBee é responsável por isso. Estabelecida a conexão o gerenciador da rede faz o download dos dados (ou também outras configurações na microestação), faz o tratamento necessário nos dados obtidos e os envia para o banco de dados.


Figura 3. Protótipo da microestação

O banco de dados utilizado foi o MySQL, pela sua popularidade, devido à fácil integração com a linguagem PHP para o desenvolvimento do sistema Web e por ser um software livre com base na GPL. Além de tabelas de cadastro de usuários, estações e sensores, a tabela principal armazena os dados dos sensores. Esta tabela é organizada através dos campos: identificação da coleta, identificação da estação, valor do sensor, tipo do sensor e hora da coleta. O sistema Web foi desenvolvido em linguagem PHP, nele foram implementadas funcionalidades como: gerenciar microestações determinando quais sensores estão presentes, adicionar coletas manualmente e gerar gráficos e tabelas. No sistema Web (acessado pela Internet) é possível fazer consultas a esse banco de dados, que são apresentadas ao usuário na forma de gráficos e tabelas para cada microestação.

O estudo da região onde estão localizados os parreirais já foi feito, determinando sua localização geográfica (ver Tabela 1) e disponibilizando em pontos em um plano (Figura 4) para elaboração da topologia da rede. A região é uma planície, portanto não haverá obstáculos tão grandes como montanhas para dificultar a comunicação da rede.

Anais do 9o. Fórum de Informática de Maringá – 13 a 17 de Setembro de 2010

40

Figura 4. Disposição topográfica das

plantações da COAVITI. Pontos referentes às suas respectivas localizações

geográficas no plano (ver Tabela 1). Escala 1:250000

Tabela 1. Localização geográfica dos parreirais da COAVITI

Plantações de uva da COAVITI Latitude Longitude

1. 2. 3. 4. 5. 6. * 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

23°20'40.58" S 23°21'28.18" S 23°22'39.10" S 23°27'44.68" S 23°28'14.91" S 23°28'19.93" S 23°28'27.68" S 23°28'33.78" S 23°29'41.72" S 23°29'50.61" S 23°30'35.30" S 23°30'57.52" S 23°31'20.70" S 23°31'25.55" S 23°31'29.21" S 23°32'18.04" S 23°32'20.53" S 23°32'52.94" S

51°49'19.37" O 51°49'08.36" O 51°48'26.80" O 51°48'14.14" O 51°47'52.95" O 51°48'56.32" O 51°47'57.93" O 51°46'15.15" O 51°49'29.68" O 51°47'58.88" O 51°50'57.17" O 51°50'06.54" O 51°49'24.81" O 51°48'17.20" O 51°49'35.86" O 51°50'24.35" O 51°48'26.69" O 51°51'59.29" O

*Localização da sede da COAVITI

N


6. Conclusões e Trabalhos Futuros Uma síntese das principais contribuições deste trabalho é discutida a seguir:

o No aspecto científico:

� O projeto poderá fornecer informações precisas sobre as condições favoráveis ao ataque de pragas e doenças, viabilizando o desenvolvimento de técnicas mais apuradas de combate a agentes nocivos à uva e a outras culturas. Além disso, o sistema de coleta viabilizará a implementação futura de redes de coletores de dados em campo para diversas culturas, bastando apenas efetuar as adaptações necessárias no software e nos sensores para atender as necessidades de cada cultura a ser investigada.

o No aspecto sócio-econômico:

� O desenvolvimento do projeto abre uma variedade de perspectivas de cooperação com a agroindústria no contexto de automação de processos produtivos com apoio de sistemas embarcados.

� Com a viabilização do controle eficiente de produção da fruta será possível elevar a qualidade e a produtividade das propriedades, o que contribuirá para uma melhor classificação do produto e futuramente a implementação da rastreabilidade e certificação da produção.

� Como consequência das contribuições advindas da redução de custos de produção em função do melhor planejamento de produção, da melhoria de renda, e da geração de postos de trabalho espera-se uma melhoria na qualidade de vida dos agricultores.

o No aspecto ambiental:

� Os resultados do projeto certamente poderão fornecer contribuições significativas em termos de planejamento estratégico de produção das culturas propiciando redução do uso de defensivos agrícolas, água e minerais.

Dentre os trabalhos futuros há previsão para emprego de VANT (veículo aéreo não tripulado) atuando como gerenciador da rede em locais de difícil acesso e fora de alcance de sinal. Possibilitando também utilizá-lo para implementar um sistema de análise de fotos aéreas. Um estudo pode ser feito a fim de melhorar o consumo de energia, aperfeiçoando o programa da microestação para ativar os sensores apenas no momento em que é feita a leitura, desligando-os após. A partir de uma grande quantidade de informação, é possível desenvolver um sistema de mineração de dados a fim de prever a qualidade da uva e a quantidade que será colhida, podendo garantir a venda do produto antes mesmo da colheita.

Agradecimentos Os autores agradecem à Fundação Araucária de Apoio ao Desenvolvimento

Científico e Tecnológico do Paraná e ao CNPq pelo apoio financeiro ao projeto.


Referências AGRI-CIÊNCIA. i-Farm. 2007. Disponível em: <http://www.i-farm.pt/>. Data de acesso

06/06/2010. ARDUINO. Arduino. 2005. Disponível em: <http://arduino.cc/>. Data de acesso

06/06/2010. BRUCKNER, C. H.; PICANÇO, M. C. Maracujá: tecnologia de produção, pós-colheita,

agroindústria, mercado. Porto Alegre: Cinco Continentes, 2001. 472p. BURRELL, J.; BROOKE, T.; BECKWITH, R. Vineyard Computing: Sensor Networks

in Agricultural Production. IEEE PERVASIVE computing. v. 3, n. 1, p. 38-45, jan./mar. 2004.

CASTRO NETO, M. i-Farm: a empresa agrícola inteligente. Jornadas Técnicas, A IMPORTÂNCIA DA METEOROLOGIA NA AGRICULTURA. Centro Operativo e de Tecnologia de Regadio, Beja (Portugal), 28 Mar. 2008.

DE STEFANI, F. Sistema di monitoraggio ambientale tramite WSN. 2008. Corso di Laurea Specialistica in Ingegneria Informatica - Università Degli Studi Di Pavia, Italia, 12/2008 .

EMPRAPA UVA E VINHO. 2010. Sistema CCM Geovitícola. Disponível em: <http://www.cnpuv.embrapa.br/tecnologias/ccm/>. Data de acesso 30/04/2010.

ERGEN, S. C. IEEE 802.15.4 Summary. Relatório Técnico. Advanced Technology Lab of National Semiconductor, Ago. 2004. Disponível em: <http://www.sinemergen.com/zigbee.pdf>. Data de acesso 06/06/2010.

HISCOCKS, P. D. Analog and Microprocessor System Design The Weather Station Project. Department of Electrical and Computer Engineering, Ryerson University, Toronto, Canada, 1994. Disponível em: <http://www.syscompdesign.com/weather/weather-station-instruments.pdf>. Acesso em 21 de julho de 2010.

LIBELIUM. Squidbee Data-Sheet. 2008. Disponível em: <http://www.libelium.com/squidbee/upload/c/c1/SquidBeeDataSheet.pdf>. Data de acesso 06/06/2010.

MAZIA, J. O. Diagnóstico da fruticultura no município de Marialva-PR. EMATER: Marialva, 1998. 28p.

MELLO, L. M. R. Atuação do Brasil no Mercado Vitivinícola Mundial – Panorama 2007. Bento Gonçalves – Embrapa Uva e Vinho. Relatório Técnico. Disponível em: <http://www.cnpuv.embrapa.br/publica/artigos/panorama2007_vitivinicola_mundial.pdf>. Acesso em 21 de julho de 2010.

MELLO, L. M. R. Vitivinicultura brasileira: Panorama 2008. Bento Gonçalves – Embrapa Uva e Vinho. Relatório Técnico. Disponível em: <http://www.cnpuv.embrapa.br/publica/artigos/vitbras2008.pdf>. Acesso em 21 de julho de 2010.

PIANI, A. Noroeste do Paraná em redes: referências para a agricultura familiar. Londrina: IAPAR/EMATER, 2001. 48p.

PRODUTORES de Iguatemi inauguram fábrica de polpa de frutas. O Diário do Norte do Paraná, Maringá, 12 nov. 2007. Seção de Economia (Agroindústria).

RIOU, C.; CARBONNEAU, A.; BECKER, N.; CALÓ, A.; COSTACURTA, A.; CASTRO, R.; PINTO, P. A.; CARNEIRO, L. C.; LOPES, C.; CLÍMACO, P.;


PANAGIOTOU, M. M.; SOTEZ, V.; BEAUMOND, H. C.; BURRIL, A.; MAES, J.; VOSSEN, P. Le determinisme climatique de la maturation du raisin: Application au zonage de la teneur en sucre dans la Communauté Européenne. In: OFFICE DES PUBLICATIONS OFFICIELLES DES COMMUNAUTÉS EUROPÉENNES. EUR 15863 FR/EN. Luxemburgo. 1994. 319p.

TONIETTO, J.; CARBONNEAU, A. A multicriteria climatic classification system for grape-growing regions worldwide. Agricultural and Forest Meteorology, v. 124, n. 1-2, p. 81-97, 2004.

TONIETTO, J.; CARBONNEAU, A. Análise mundial do clima das regiões vitícolas e de sua influência sobre a tipicidade dos vinhos: a posição da viticultura brasileira comparada a 100 regiões em 30 países. In: CONGRESSO BRASILEIRO DE VITICULTURA E ENOLOGIA, 9., 7 a 10 de dezembro de 1999, Bento Gonçalves. Anais. Bento Gonçalves: Embrapa Uva e Vinho/Jorge Tonietto e Celito C. Guerra, ed. 1999. p.75-90.

TONIETTO, J.; MANDELLI, F. Uvas Americanas e Híbridas para Processamento em Clima Temperado. Sistema de Produção 2, 2003. Disponível em <http://sistemasdeproducao.cnptia.embrapa.br/FontesHTML/Uva/UvaAmericanaHibridaClimaTemperado/clima.htm >. Acesso em 21 de julho de 2010.

UNIVERSITÀ DEGLI STUDI DI PAVIA. CERERE: a WSN for Agricultural and Environmental Control. 2008. Disponível em: <http://netlab-mn.unipv.it/wsn/dokuwiki/projects/cerere>. Data de acesso 06/06/2010.

WARK, T. et al. Transforming Agriculture through Pervasive Wireless Sensor Networks. IEEE PERVASIVE computing. Vol. 6, N. 2, pp. 50-57, April-June 2007.

WASINGER, J. (2001). Build a wireless weather station. In Circuit Cellar, pages 34–41. Issue 136.


Arquitetura MIPS: desenvolvimento de um simulador Alison R. P. Freitas, Carlos R. B. Junior, Murilo Z. Souza, Ronaldo A. L. Gonçalves

Departamento de Informática – Universidade Estadual de Maringá (UEM) 87.020-900 – Maringá – PR – Brasil

[email protected], {beleti.junior,murilo.zanga ri}@gmail.com, [email protected]

Resumo. Um dos principais objetivos da disciplina de Arquitetura de Computadores é mostrar como o hardware é construído e como seus componentes interagem para realizar a funcionalidade esperada em um sistema computacional. Mas na maioria das vezes, esses objetivos não são facilmente atingidos. Para facilitar o entendimento desta disciplina, simuladores podem ser utilizados. Este trabalho revê os principais conceitos e trabalhos relacionados à Arquitetura de Computadores, com foco nos processadores MIPS. Além disso, um simulador foi proposto e implementado, e as suas funcionalidades e características são aqui apresentadas. Este simulador permite ver a execução das instruções MIPS por meio de uma interface simples e intuitiva, que facilita a interação com o usuário. O simulador foi experimentado e mostrou-se útil no ensino da disciplina de Arquiteturas de Computadores. Palavras-chave: sistema computacional, Arquitetura de Computadores, processadores MIPS, arquitetura RISC, simuladores. Abstract. One of the main goals of Computer Architecture course is to show how the hardware is built and how its components interact to achieve the functionality expected in a computer system. But in most cases, these goals are not easily achieved. To facilitate the understanding of this course, simulators may be used. This paper reviews the major concepts and works related to Computer Architecture, with focus on MIPS processors. Moreover, a simulator was proposed and implemented, and its features and characteristics are presented here. This simulator lets you see the implementation of the MIPS instruction through a simple and intuitive interface that facilitates user interaction. The simulator was tested and proved useful in the teaching of Computer Architectures. Keywords: computer system, Computer Architecture, MIPS processor, RISC architecture, simulators. 1. Introdução

Os processadores podem ser classificados de acordo com o número de instruções suportadas, sendo RISC (Reduced Instruction Set Computer) ou CISC (Complex Instruction Set Computer) [6]. Um processador CISC suporta um grande conjunto de instruções que implementa uma grande variedade de tipos, desde instruções simples até muito complexas e profundamente especializadas. Entretanto, quanto maior a quantidade de instruções que um processador suporta, mais lenta é a execução de cada uma delas. Já o processador RISC reconhece um número limitado de instruções, porém mais simples e conseqüentemente rápidas, com um formato único e modos simples de endereçamento.


O processador MIPS (Microprocessor without Interlocked Pipeline Stages) foi desenvolvido pela MIPS Computer Systems Inc1 e utilizava nas primeiras versões um conjunto de instruções de 32 bits da classe RISC. Pela sua popularidade, sua arquitetura tem sido usada como exemplo típico e diversos simuladores desse processador têm sido desenvolvidos e amplamente utilizados na pesquisa e no ensino de Arquitetura de Computadores.

Devido a essa importância, este trabalho tem por objetivo principal apresentar a proposta e implementação de um simulador baseado na arquitetura MIPS, focando no seu conjunto de instruções e nas suas principais características. Este trabalho descreve o funcionamento geral do simulador desenvolvido, realiza comparações e aponta os diferenciais com outros simuladores existentes.

O texto está organizado conforme segue. A seção 2 apresenta uma visão geral sobre a organização de um processador MIPS. A seção 3 detalha o conjunto de instruções. A seção 4 contextualiza os trabalhos relacionados. A seção 5 descreve o simulador proposto, os resultados experimentais e uma análise comparativa entre o simulador desenvolvido e simuladores relacionados. A seção 6 esboça as considerações finais. As referências bibliográficas aparecem na última seção. 2. Arquitetura MIPS A arquitetura MIPS é uma arquitetura de microprocessadores de propósito geral projetada para ser implementada em um único chip VLSI [5] (Very-large-scale integration). O MIPS foi projetado para prover alto desempenho e para isso, a complexidade de instruções individuais é minimizada para simplificar o hardware com a redução do conjunto de instruções. O MIPS é uma arquitetura load-store, o que significa que somente instruções load e store acessam a memória. As instruções de cálculo operam diretamente sobre os registradores. O efeito destas duas características é a simplificação do hardware. O pipeline do MIPS [10] tem cinco estágios que são ilustrados na Figura 1 e descritos a seguir:

• IF (instruction fetch – Busca da instrução): busca a próxima instrução da cache de instruções;

• RD (read registers – Leitura dos registradores): obtém o conteúdo dos registradores;

• ALU (arithmetic/logic unit – unidade lógica e aritmética): Realiza uma operação lógica ou aritmética em um ciclo do clock (matemática de ponto flutuante e instruções mult/div não podem ser efetuadas em um ciclo de clock);

• MEM: é o estagio no qual a instrução pode ler ou escrever as variáveis da memória na cache dos dados;

• WB (write back – escrever resultado): Armazena o valor obtido a partir de uma operação de volta ao banco de registradores.

1 Mais informações em http://www.mips.com/


Figura 1 – Pipeline com cinco estágios MIPS

2.1 Registradores No MIPS estão disponíveis 32 registradores de propósito gerais. Por exemplo, os registradores ‘pc’, que contém o valor do ponteiro de endereço da instrução atual, ‘hi’ e ‘lo’, que são utilizados para armazenar o resultado da multiplicação e divisão. Os registradores são livres para o uso, conforme necessidade da aplicação, e são organizados em grupos, conforme Tabela 1.

Tabela 1 – Registradores MIPS e seus usos. Número Nome Uso

0 Zero constante zero 1 at reservado para o montador

2-3 v0,v1 avaliação de expressão e resultados de uma função 4-7 a0-a3 argumentos de entrada 8-15 t0-t7 temporário (não preservado pela chamada) 16-23 s0-s7 temporário salvo (preservado pela chamada) 24-25 t8-t9 temporário (não preservado pela chamada) 26-27 k0-k1 reservado para o kernel do sistema operacional

28 gp ponteiro global 29 sp stack pointer 30 s8-fp frame pointer 31 ra endereço de retorno

3. Conjunto de instruções MIPS O conjunto de instruções é um dos componentes principais da arquitetura de um processador. Devido às características do conjunto de instruções, a arquitetura sofre grande influência tanto nos aspectos que tangem sua definição quanto sua implementação [8]. Por exemplo, as operações realizadas pela unidade lógica e aritmética, o número e função dos registradores e a estrutura de interconexão dos componentes definem as operações básicas da seção de processamento.


As instruções oferecidas pela arquitetura MIPS podem ser classificadas em categorias, de acordo com o tipo de operação que realizam. Segundo [8], sua arquitetura fornece as seguintes categorias de instruções:

• Aritméticas: são as instruções que realizam operações aritméticas sobre números inteiros (adição, subtração);

• Transferência de dados: instruções que movem os dados entre a memória e os registradores;

• Lógica: são as instruções que realizam operações lógicas bit a bit (AND, OR); • Desvio condicional: instruções de desvio, com base em comparações e testes

de igualdade e desigualdade; • Desvio incondicional: instruções de desvio e de chamada de rotina, que

transferem o controle de execução para determinada instrução dentro do código do programa.

A Tabela 2 mostra exemplos de instruções e seus respectivos significados. Uma listagem completa das instruções pode ser encontrada em [10]. Mais adiante serão detalhadas as instruções implementadas pelo simulador desenvolvido.

Tabela 2 – Exemplos de instruções MIPS Categoria Instrução Exemplo Significado Aritmética add, sub, addi, subi add $s1, $s2, $s3 $s1 = $s2 + $s3

Transf. de Dados sw, lw, lui lw $s1, 100($s2) $s1 = MEM [$s2 +100] Lógica and, or, sll, srl or $s1, $s2, $s3 $s1 = $s2 | $s3

Comparadores beq, bne, slt beq $s1, $s2, L if ($s1 == $s2) go to L Desvio Incond. j, jr, jal j L go to L

3.1 Formato das instruções As instruções no MIPS podem ser de três formatos distintos como mostra a Figura 2.

Figura 2 – Formato das instruções MIPS

Os elementos mostrados na Figura 2 são definidos abaixo:

• op (opcode): operação básica da instrução; • rs: registrador do primeiro operando de origem; • rt: registrador do segundo operando de origem; • rd: registrador do operando de destino; • shamt (shift amount): quantidade de deslocamento;


• funct: seleciona a variante especificada da operação no campo op. Algumas vezes chamado de função.

3.2 Modos de endereçamento Uma instrução pode ter operandos na memória, nos registradores ou mesmo na própria instrução. As várias formas como uma instrução especifica a localização de seus operandos são os modos de endereçamento. De acordo com [8], os modos de endereçamento podem ser classificados como:

• Endereçamento em registrador, no qual o operando é um registrador; • Endereçamento de base ou deslocamento, no qual o operando está no local de memória cujo endereço é a soma de um registrador e uma constante na instrução; • Endereçamento imediato, em que o operando é uma constante dentro da própria instrução; • Endereçamento relativo ao PC, no qual o endereçamento é a soma do PC e uma constante na instrução; • Endereçamento pseudodireto, em que o endereço de jump são os 26 bits da instrução concatenados com os bits mais altos do PC. Mais informações sobre os modos de endereçamento e exemplos dos mesmos

podem ser encontrados em [8]. 4. Trabalhos Relacionados Muitos trabalhos têm sido realizados em termos de simulação arquitetural. O DIMIPSS [4] é um simulador desenvolvido em Java que simula as instruções do processador MIPS. As instruções precisam ser escritas num determinado formato para que possam ser interpretadas e então executadas. Um detalhe importante é a visualização do que está ocorrendo de forma dinâmica em diagramas, o que facilita o entendimento do que está ocorrendo em cada módulo do programa em execução. Em contrapartida, ele não apresenta a visualização do pipeline, visto que seu objetivo é mostrar apenas a arquitetura do MIPS monociclo. O NeanderWin [1] é um simulador com uma arquitetura do tipo acumulador. Simulador esse em que é possível editar o código em linguagem de montagem, compilar e receber imediatamente mensagens relativas a erros de sintaxe, carregar na memória e simular a execução do programa, com visualização imediata e altamente interativa. Contudo, esse simulador se mostrou muito limitado devido à quantidade de instruções possíveis de simulação (apenas 16), ao único modo de endereçamento e a largura de dados e endereços de oito bits. Em contrapartida, esse simulador mostrou facilitar a aprendizagem, pois apresenta uma interface amigável e está disponível em versão Linux e Windows. Ele possui muitas idéias que não foram implementadas, mas que podem torná-lo um simulador mais completo. Um simulador MIPS 32 bits e de propósito especifico, o PS-CAS MIPS, pode ser visto em [7], no qual foi desenvolvido um simulador para o auxílio do aprendizado de técnicas de pipeline. Esse simulador foi desenvolvido com base no WebSimple MIPS [9] que também tem o propósito de mostrar a simulação de pipeline. A análise sintática teve como objetivo principal analisar os possíveis pontos no código em que poderia ocorrer


dependência, mas também analisa a sintaxe do código assembly. O PS-CAS MIPS possui uma unidade de controle especialmente desenvolvida para tratar os possíveis conflitos durante a execução em pipeline. Ele também apresenta uma funcionalidade de geração de relatório, no qual são mostradas as dependências entre instruções, a quantidade de bolhas inseridas no pipeline e os dados relacionados ao acréscimo de desempenho proporcionado pelo pipeline. O MipsIt [3] é um simulador baseado em um processador MIPS ISA de 32 bits que tem a finalidade de mostrar por meio de animações gráficas o funcionamento de um processador MIPS. Ele apresenta diversas interfaces desde o conjunto de registradores, passando pela memória, memória cache, periféricos de entrada e saída, até o pipeline em diagramas mostrando todo o fluxo das instruções. E com essas animações, consegue-se visualizar todo o processo de execução das instruções. Este simulador assim como o PS-CAS MIPS utiliza os adiantamentos de pipeline, porém não é possível escolher quais adiantamentos serão utilizados na simulação. Este simulador se mostrou um dos mais completos, porém com interface complexa que oferece configurações para usuários avançados, não sendo considerado, portanto um simulador para iniciantes na disciplina de Arquitetura de Computadores. O simulador WebMIPS [2] tem uma grande vantagem em relação aos outros simuladores, ele funciona como uma aplicação web que é executado em um servidor remoto. Sendo assim, não é necessário fazer o download do mesmo, só é preciso acessar sua página na internet2 e iniciar a simulação desejada. Toda a simulação pode ser configurada e cada execução tem um limite de 1000 ciclos de clock. Isso para não permitir que ocorram loops infinitos, acessos indevidos a memória, etc. Durante sua execução é mostrada o diagrama da simulação do processador com todos os dispositivos do processador e ainda os estágios de pipeline. Nesse diagrama, você pode entender o funcionamento de cada dispositivo apenas clicando no mesmo. O WebMIPS apresenta a memória de instruções, memória de dados e registradores. Você ainda tem a opção escolher seu exemplo de execução, executar passo a passo ou realizar toda a execução de uma vez. Mas esse simulador apresenta a desvantagem de não ser passível de adicionar implementações, visto que as implementações para sua execução já estão definidas. 5. SimMIPS – Um simulador MIPS O SimMIPS é um simulador baseado na arquitetura MIPS, desenvolvido com o intuito de simular a execução das instruções do processador MIPS 32 bits. Foi desenvolvido na linguagem de programação JAVA3, com o suporte do ambiente de desenvolvimento Netbeans4. Tem como objetivo principal mostrar a dinâmica da execução de programas por meio da simulação das instruções implementadas. O SimMIPS é um simulador que busca simplificar o entendimento do processo de execução de programas por meio de uma interface amigável e de fácil compreensão. 5.1 Características gerais

2 Disponível em http://www.dii.unisi.it/~giorgi/WEBMIPS/.

3 Mais informações em http://java.sun.com/

4 Mais informações em http://www.netbeans.org/


As instruções implementadas são um subconjunto de mesmo formato das instruções especificadas em [10], conforme mostra a Tabela 3.

Tabela 3: Instruções implementas pelo SimMIPS Instrução Significado Exemplo Significado Comentário

Operações Aritiméticas Add add add $1,$2,$3 $1=$2+$3 Sempre 3 operandos Addi add immediate addi $1,$2,10 $1=$2+10 Soma constante Sub subtract sub $1,$2,$3 $1=$2-$3 Sempre 3 operandos Mult multiply mult $s,$t LO = (($s * $t) <<

32) >>32; HI = ($s * $t) >> 32;

Multiplica colocando metade dos bits em HI e LO

Div divide div $s, $t LO = $s / $t HI = $s % $t

Divide colocando resultado em LO e resto em HI

Transferência de dados Sw store word sw $1,10($2) Memória[$2+10]=$1 Registrador para memória Lw load word lw $1,10($2) $1=Memória[$2+10] Memória para registrador Lui load upper

immed. lui $1,10 $1=10x2^16 Armazena uma constante

maior que16bits Mfhi move from high mfhi $d $d = HI Recupera valor de HI Mflo move from low mflo $d $d = LO Recupera valor de LO

Saltos Incondicionais J jump j label go to label Salta para o respectivo label

Jal jump and link jal label $31=PC+4; go to label

Para chamada de procedimento

Jr jump register jr $31 go to $31 Para switch, retorno de procedimento

Operações Condicionais Beq branch on equal beq $1,$2,lab if($1==$2)

go to lab Comparador ‘igual’

Bne branch on not equal

bne $1,$2,lab if($1!=$2) go to lab

Comparador ‘diferente’

Slt set on less then slt $1,$2,$3 if($2<$3)$1=1; else $1=0

Comparador ‘menor que’

Slti set on less immediate

slti $1,$2,10

if($2<10)$1=1; else $1=0

Comparador ‘menor que’

Operações lógicas And and and $1,$2,$3 $1=$2&$3 Sempre 3 operandos Andi and immediate andi $1,$2,10 $1=$2&10 E Lógico constante Or or or $1,$2,$3 $1=$2|$3 Sempre 3 operandos Ori or immediate ori $1,$2,10 $1=$2|10 OU Lógico constante Sll shift left logical sll $1,$2,10 $1=$2<<10 Desloca bits à esquerda Srl shift right logical srl $1,$2,10 $1=$2>>10 Desloca bits à direita

Serviço do sistema syscall chamada do

sistema $v0 == 10 => encerrar execução

$v0 == 1 => imprime o valor de $a0

Foram implementadas as operações de adição, and e or lógico entre registradores

e, entre registrador e inteiro, subtração, deslocamento de bits, multiplicação e divisão. As implementações de manipulação da memória e saltos incondicionais permitem inclusive a simulação de pilha e chamadas de procedimentos/sub-rotinas, utilizando-se para isso os


saltos incondicionais ‘j’ e ‘jal’, referenciando trechos do código por meio de label. A abordagem de considerar o label deve-se ao fato de que ao escrever um código, o programador não conhece o endereço na memória das instruções que se deseja executar, denotando assim uma posição no código que pode ser referenciada através da instrução 'go to', possibilitando a implementação de instruções como o loop, if-else e subrotinas.

Futuros incrementos na funcionalidade do programa são fáceis e intuitivos visto que a parte funcional das instruções no código foi programada estrutural e seqüencialmente, bastando acrescentar poucas linhas de código para adicionar uma nova instrução. 5.2 Interface do simulador O simulador tem uma interface intuitiva e limpa, com apenas três quadros básicos, os quais permitem visualizar o código, os registradores e a memória.

FFigura 3: Interface do SimMIPS


Dessa forma o quadro B representa código-fonte do arquivo aberto, podendo-se visualizar o endereço em hexadecimal e decimal, o label da instrução caso exista, o nome da instrução e os respectivos operadores envolvidos. O endereço aqui apresentado é diferente da região em que aparece no quadro C, o qual tem tamanho de 0 à FF em hexadecimal ou 0 à 255 em decimal, e é disponibilizado para mostrar os dados envolvidos nas instruções. Como no MIPS 32 bits cada instrução e registrador tem 32 bits (ou 4 bytes), a memória assim como o endereço de cada instrução ira saltar de 4 em 4 bytes. 5.3 Características O SimMIPS apresenta características interessantes que alguns dos simuladores avaliados nesse artigo não possuem. A quantidade de instruções implementadas supre todas as necessidades de simulação, com instruções lógicas, aritméticas, transferência de dados, desvios condicionais e incondicionais, pilha e sub-rotina. O código-fonte pode ser escrito respeitando-se o formato padrão de uma instrução por linha, podendo também utilizar comentários e vários espaçamentos. A utilização de expressões regulares para o reconhecimento de todos os tipos de instruções com suas peculiaridades, como a quantidade de operandos e a existência ou não de um label facilitou a inserção dessa versatilidade. A Figura 4 mostra que durante a execução fica evidenciado a posição atual da instrução em execução, a próxima instrução que corresponde ao endereço no PC, todos os registradores envolventes na operação e a posição na memória em que está havendo a transferência de dado.


Figura 4: SimMIPS em execução

No quadro A da Figura 3 pode-se simular passo a passo ou continuamente, este último podendo ser ajustado a velocidade de 0 a 10 segundos de espera. Nesse mesmo quadro existe a opção do tipo de visualização do dado presente nos registradores e na memória, tanto em decimal quanto em hexadecimal e binário, sendo muito útil para perceber as mudanças como, por exemplo, decorrentes de operações aritméticas, visualizando bit a bit. O quadro E da mesma figura mostra um terminal no qual a saída da chamada syscall é impressa. Para tornar o simulador ainda mais amigável, foi realizado um tratamento dos possíveis erros permitindo que o usuário seja alertado no erro da execução do código, mostrando possíveis motivos dos erros que tenham ocorrido. Também foi inserido um texto que explica sua atualização no menu ‘Ajuda’ e possibilidade de mudar o skin do programa.


5.4 Experimentação Como forma de demonstrar a robustez do simulador, três exemplos práticos e comumente utilizados na programação foram descritos e apresentados a seguir. No lado esquerdo da Figura 5, observa-se um laço de iteração utilizando a instrução ‘j’ para que ele salte para o label desejado (na figura o label está representado por while), repetindo isso enquanto o operador condicional ‘beq’ não for satisfeito. Ao satisfazer a condição ‘beq’, o laço termina e a execução da instrução é finalizada.

addi $t4, $zero, 2 sw $t4, 0($zero) lw $t0, 0($zero) add $t2, $zero, $zero while: beq $t0, $t2, end addi $t2, $t2, 1 j while end: sw $t2, 0($zero)

jal subprog addi $v0, $zero, 10 syscall subprog: addi $a0, $zero, 1 addi $v0, $zero, 1 syscall jr $ra lui $t0, 1

Figura 5: Exemplo de um laço à esquerda e de subprograma à direita

Nessa mesma figura (à direita) é mostrada uma implementação de subprograma utilizando o operador ‘jal’ o qual salta para o label ‘subprog’ e adiciona no registrador $ra o endereço da próxima instrução que ele executaria. No momento em que a execução chega na instrução ‘jr $ra’ o endereço armazenado em $ra é recuperado e a execução retorna para a instrução ‘addi $v0, $zero, 10’. É possível realizar a implementação de uma pilha utilizando o registrador $sp (stack pointer) que irá apontar para o topo da pilha. Para cada inserção, o topo da pilha é antes decrementado e a cada remoção é incrementado. A Figura 6 mostra que os valores 4 e 5 são adicionados aos registradores $a0 e $a1 respectivamente. Em seguida os valores de $a0 e $a1 são armazenados na pilha e posteriormente os valores são recuperados em $t0 e $t1.

addi $a0, $zero, 5 addi $a1, $zero, 4 addi $sp, $zero, 8 addi $sp, $sp, -4 sw $a0, 0($sp) addi $sp, $sp, -4 sw $a1, 0($sp) lw $t0, 0($sp) addi $sp, $sp, 4 lw $t1, 0($sp) addi $sp, $sp, 4

Figura 6: Exemplo da implementação de uma pilha


5.5 Análise Comparativa Os simuladores baseados na arquitetura MIPS possuem funcionalidades que os caracterizam como os tais, mas algumas características fazem com que simuladores de mesmo propósito se sobre saiam quando analisados comparativamente. Com base nos estudos realizados e no simulador desenvolvido, a Tabela 4 mostra uma comparação, considerando-se características desejáveis em um simulador MIPS.

Tabela 4: Comparação entre simuladores relacionados e o SimMIPS Simuladores

Características 1 2 3 4 5 6

Portabilidade X X X N/V N/A X

Simula Programas X X X X X

Controla Vel. Simulação N/V X X X

Simulação Passo-a-Passo X X X X X X

Permite Reinicio/Reset N/V X N/V N/V X X

Informa Erro X X X N/V N/A X

Destaque de Instruções X X N/V X X

Destaque da Memória X N/A X X

Destaque de Registradores X X N/A N/V X

Adição de Comentários X X N/V N/A X

Visualização em diferentes Bases X

Instruções de todos os formatos N/V N/V X

1 = DIMIPS / 2 = NeanderWin / 3 = PS-CAS MIPS / 4 = MipsIt / 5 = WebMIPS / 6 = SimMIPS

Na Tabela 4, a característica “Instrução de todos os formatos” refere-se às

categorias descritas na Tabela 2. O Neanderwin é um simulador do tipo acumulador, e devido a isso, algumas das suas características não foram relacionadas. De mesma forma, como tanto o PS-CAS MIPS quanto o WebSimple MIPS são simuladores de propósito especifico, algumas de suas características também não foram relacionadas. Na comparação entre simuladores eles foram relacionados como sendo um simulador, visto que o PS-CAS MIPS pode ser considerado um novo simulador, mas tendo como base o WebSimple MIPS. Ainda em relação aos dados dispostos na tabela, as classificações N/A e N/V referem-se respectivamente a Não Aplicado e Não Verificado, sendo o primeiro atribuído quando não a característica não se aplica ao simulador e o segundo nos casos onde não foi possível constatar a característica em questão. De modo geral observou-se que o SimMIPS possui as características relacionadas e encontradas em alguns dos simuladores analisados, deixando evidente sua qualidade e importância para o estado da arte.


6. Considerações Finais Este trabalho apresentou um simulador com base na arquitetura, subconjunto de instruções e características gerais de um processador MIPS. O simulador SimMIPS mostra a dinâmica de execução de programas por meio da simulação das instruções por eles implementadas. A cada passo da execução o simulador destaca a instrução atual e a seguinte, ilustrando também a movimentação nos registradores, memória e pilha. Ele possui uma interface de fácil compreensão, na qual estudantes podem iniciar seus estudos em disciplinas de Arquitetura e Organização de Computadores de forma rápida e simplificada. Como foi desenvolvido na linguagem JAVA, pode ser executado em diversos sistemas operacionais, sem a necessidade de quaisquer adaptações. Uma característica interessante que apenas o SimMIPS apresentou foi a visualização em diferentes bases decimais, o que facilita a interação e entendimento do usuário. Como possíveis trabalhos futuros, pode-se adicionar instruções ainda não implementadas, acrescentar novas funcionalidades como, por exemplo, o desenvolvimento de técnicas para a melhora no desempenho das execuções como o pipeline e também permitir a entrada de códigos de alto nível realizando sua conversão para linguagem suportada pelo simulador. Referências [1] BORGES, J. A. S., SILVA, G. P. “NeanderWin - Um Simulador Didático para uma

Arquitetura do Tipo Acumulador.”. In: Workshop sobre Educação em Arquitetura de Computadores – WEAC 2006.

[2] BRANOVIC, I., GIORGI, R., MARTINELLI, E.. “WebMIPS: a new web-based MIPS simulation environment for computer architecture education”, In: Proceedings of the 2004 workshop on Computer architecture education: held in conjunction with the 31st International Symposium on Computer Architecture, June 19, 2004, Munich, Germany.

[3] BRORSSON, M.. “MipsIt: a simulation and development environment using animation for computer architecture education”. In: Proceedings of the 2002 workshop on Computer architecture education: Held in conjunction with the 29th International Symposium on Computer Architecture, May 26, 2002, Anchorage, Alaska, p.1 -8.

[4] FELIX A. F., Pousa C. V., Carvalho M. B., “DIMIPSS: Um simulador didático e interativo do MIPS”. In: Workshop sobre Educação em Arquitetura de Computadores – WEAC 2006.

[5] FEUER, M.; , "VLSI design automation: An introduction," in Proceedings of the IEEE , vol.71, no.1, pp. 5- 9, Jan. 1983.

[6] JAMIL, T.. "RISC versus CISC," in Potentials, IEEE, vol.14, nº.3, pp.13-16, Aug/Sep 1995.

[7] MAIA, D. W. N., VIEIRA, M. M., PESSOA, R. F.. “PS - CAS MIPS: Um simulador de pipeline do processador MIPS 32 bits para estudo de Arquitetura de Computadores.” In: Workshop sobre Educação em Arquitetura de Computadores – WEAC 2009.


[8] PATTERSON, D. A. e HENNESSY, J. L. “Computer Organization and Design: The Hardware/Software Interface”, 3nd ed., Morgan Kaufmann Publishers, 2007.

[9] SOUSA, B. F. de, MOREIRA, M. P. A., NOGUEIRA, R. S., BRITTO, R., MARTINS, C. A. “WebSimple - MIPS: Simulador Web-based do Pipeline do MIPS.” In: Workshop em Sistemas Computacionais de Alto Desempenho (WSCAD-SSC 2008).

[10] SWEETMAN, D. “See MIPS Run”. Morgan Kaufmann Publishers, 2ª ed. 2006.


Investigação de resolução do problema de programação de horários escolares usando FPGA e VHDL

Landir Saviniec, Hudson Sérgio de Souza, João Angelo Martini

Departamento de Informática (DIN) - Universidade Estadual de Maringá (UEM) Av. Colombo, 5790 - CEP 87020-900 – Maringá – PR – Brasil

[email protected], {hudsonss, joaomartini}@gmail .com

Abstract. This paper examines the application of programmable logic devices (FPGAs) and VHDL language to develop an auxiliary hardware to solve the School Timetabling Problem (STP). This hardware will provide parallel routines to optimize an algorithm used in STP. This paper also shows good results obtained with the algorithm implementation in software. Key-Words: FPGA, VHDL, hardware, timetabling. Resumo. Este artigo analisa a viabilidade do uso de dispositivo FPGA e da linguagem VHDL para desenvolver um hardware para auxiliar na resolução do STP (School Timetabling Problem). O hardware fornecerá rotinas de execução paralela para otimizar um algoritmo usado na resolução do STP. O artigo apresenta ainda bons resultados obtidos com a implementação do algoritmo em software. Palavras-Chave: FPGA, VHDL, hardware, quadro de horários escolar.

1. Introdução

O Problema de Quadro de Horários Escolar (School Timetabling Problem - STP) é um problema clássico de distribuição de aulas em escolas. O problema é de difícil solução e envolve três variáveis: professor, turma e horário.

O STP possui algumas variantes como: quadro de horários de cursos, quadro de horários de exames e outros. Frequentemente, uma das variantes deste problema é encontrada em escolas de ensino fundamental e médio, que consiste em:

Dados: nt turmas, np professores e nh horários, distribuir um conjunto de pt × em nh horários (ou períodos) de modo a satisfazer várias restrições inerentes ao contexto.

Um dos maiores entraves neste contexto encontra-se na eficiência dos métodos de solução que existem atualmente para resolver o problema. Devido o problema ser de natureza combinatória e complexa, métodos exatos que garantem a obtenção da melhor solução possível, não resolvem o problema em tempo polinomial. Sendo assim, para resolução do STP, normalmente recorre-se aos métodos não exatos (heurísticos), que permitem a obtenção de uma solução aceitável para o problema em tempo polinomial. Entretanto, a eficiência de algoritmos heurísticos neste contexto, é inversa ao tamanho da instância tratada, ou seja, quanto maior a instância do problema, menor a eficiência do algoritmo, que passa a consumir muito recurso computacional para resolver o problema.


Segundo Fang (1994), quatro características tornam difícil a resolução destes tipos de problemas:

o Eles são problemas NP-Completos, o que significa que não existem algoritmos determinísticos que os resolvam em tempo polinomial, pelo fato do espaço de tempo para as soluções possíveis ao problema ser grande;

o As técnicas de busca usando heurísticas avançadas não garantem que as soluções encontradas sejam ótimas ou estejam próximas da ótima;

o Devido a restrições especiais requeridas em instâncias particulares do problema, um algoritmo de abordagem geral pode-se revelar inaplicável ou ineficiente;

o Problemas reais geralmente envolvem restrições que não podem ser precisamente representadas ou determinadas.

De acordo com Lobo (2005), as várias formulações do timetabling despertaram os interesses da comunidade acadêmica a partir do início da década de 1960. Pesquisas recentes sobre o problema vêm sendo desenvolvidos com emprego de diversas metodologias. Em sua maior parte utilizando-se de algoritmos heurísticos, tais como: Algoritmos Genéticos, Redes Neurais, Busca Tabu, Pesquisa em Vizinhança Variável e Simulated Annealing. Dentre elas encontram-se pesquisas em:

o Vizinhança Variável (SOUZA, 2002) aplicada ao problema de alocação de aulas a salas, no Instituto de Ciências Exatas e Biológicas da Universidade Federal de Ouro Preto;

o GRASP e Busca Tabu (COSTA, 2003) aplicada à designação de horários escolares de uma Escola Estadual da cidade de Ouro Preto. Utiliza um algoritmo híbrido construído a partir dos dois métodos, o qual se mostrou eficiente para encontrar soluções viáveis e de melhor qualidade, com maior rapidez;

o Algoritmos Genéticos (FREITAS et al., 2007) aplicados à programação de horários escolares e construção de uma ferramenta computacional para programar os horários, pesquisado na Faculdade Ruy Barbosa em Salvador;

o Redes Neurais Artificiais (CARRASCO; PATO, 2003) aplicadas à designação de horários escolares;

o Caminhos Mínimos (SOUZA; MACULAN; OCHI, 2000) aplicados para melhorar as restrições fracas de quadros de horários viáveis.

Nas últimas décadas um enorme salto tem ocorrido com as pesquisas no sentido de desenvolver sistemas computacionais para auxiliar na resolução do problema de programação de horários escolares. Cada vez mais se busca por sistemas mais eficientes e robustos em que o processamento possa fornecer soluções viáveis em curto espaço de tempo, permitindo melhor e maior quantidade de soluções possíveis e, consequentemente, tomadas de decisões mais eficientes e rápidas.

Partindo deste ponto de vista, as pesquisas neste contexto possuem dois focos. O primeiro busca desenvolver algoritmos com estratégias mais eficientes para otimizar a


fase de processamento. E o segundo visa encontrar metodologias de processamento com melhor desempenho, tais como: hardwares com capacidade de processamento paralelo e arquitetura otimizada.

O presente artigo apresenta uma investigação sobre novas alternativas que contribuam na resolução do STP. Na investigação proposta, analisa-se a viabilidade do uso de dispositivo FPGA e da linguagem VHDL para desenvolver um hardware específico para auxiliar na resolução do problema de horários escolares. O hardware a ser desenvolvido deve fornecer algumas rotinas para executar trechos de um algoritmo usado na resolução do STP, em que o processamento possa ser realizado em paralelo.

O artigo está estruturado da seguinte maneira. As seções 2 e 3 apresentam conceitos da linguagem VHDL, de FPGAs e de computação reconfigurável, a seção 4 apresenta o algoritmo usado para resolução do STP, a seção 5 mostra alguns resultados obtidos com a implementação em software e a seção 6 analisa a viabilidade de implementação do hardware proposto.

2. A linguagem VHDL

VHDL é um tipo de HDL (Hardware Description Language) que é usada para facilitar o projeto e descrição de circuitos digitais, bem como converter projetos em nível de descrição para equações Booleanas.

VHDL usa múltiplos níveis de hierarquia de componentes para descrição de circuitos, facilitando as técnicas de design durante as fases de projeto e a concepção de circuitos digitais implementados em FPGAs (Field Programmable Gate Array) e ASICs (Application Specific Integrated Circuit) (ASHENDEN; LEWIS, 2008).

A linguagem VHDL foi desenvolvida na década de 80, pelo Departamento de Defesa dos Estados Unidos para dar suporte à unificação, documentação, leitura e compreensão do funcionamento de ASICs, utilizando-se de uma linguagem independente do circuito primário. As empresas IBM, Texas e Intermetrics foram contratadas para desenvolver a linguagem e suas ferramentas (AMORE, 2005). A função inicial da VHDL era documentar o projeto VHSIC (Very High Speed Integrated Circuits). Devido à sua capacidade para descrever projetos de circuitos, a linguagem VHDL passou por um processo de evolução de suas funções e sua aplicação em projetos se tornou independente das especificações dos circuitos.

Em decorrência do sucesso no projeto de circuitos, de forma simplificada e sem necessidade de especificação explícita das conexões entre os componentes que compõem o sistema, em 1987 a VHDL foi disponibilizada em domínio público e padronizada pelo IEEE (Institute of Electrical and Electronics Engineers) como o padrão IEEE 1076. Mais tarde, foi adicionado também o padrão IEEE 1164 para introduzir sistemas lógicos multivalorados na VHDL (VAHID; LYSEXKY, 2007). Atualmente VHDL está aprovada pelo REVCOM (2008) e pela IEEE 1076-2008.

Ao contrário das linguagens de programação convencionais, a codificação em VHDL pode ser tanto sequencial quanto paralela. Uma vez implementado o código pode ser portado e reusado em novas implementações de circuitos digitais (PEDRONI, 2004), isto facilita bastante o projeto e programação de circuitos digitais.


3. Computação reconfigurável e FPGAs

Em um sistema de computação tradicional há dois métodos primários para implementação e execução de algoritmos. O primeiro utiliza a implementação em ASICs para operar em hardware. E o segundo usa a implementação em software, fazendo uso de microprocessadores de uso geral (COMPTON; HAUCK, 2003). A implementação ainda pode ser mista, sendo que algumas sub-tarefas são alocadas em hardware e outras em software (RIBEIRO, 2002).

A implementação em ASIC possui a vantagem de oferecer alto desempenho, uma vez que o hardware possui dedicação exclusiva para uma aplicação particular, e não há overhead (códigos extra) para interpretar instruções (RIBEIRO, 2002). Sendo assim, seu desempenho se deve às suas características de execução espacial e alto grau de paralelismo, entretanto há uma desvantagem, após sua fabricação o hardware não pode ser alterado (COMPTON; HAUCK, 2003).

Já a implementação em software explora um processador de uso geral, causando overhead na busca, decodificação e execução de conjuntos de instruções gravadas em memória, o que torna sua execução lenta e de característica temporal. Contudo, há uma vantagem, a alteração na funcionalidade de um programa pode ser feita apenas alterando os códigos de instruções, sem necessidade de se substituir o hardware utilizado.

Em implementações espaciais os operadores estão localizados em pontos distintos do espaço, permitindo que a execução seja realizada de forma paralela. Já em implementações temporais, um grupo pequeno de recursos é usado repetidamente ao longo do tempo para realizar uma determinada computação (RIBEIRO, 2002). Em computação reconfigurável o objetivo básico é a combinação entre os dois métodos, buscando unir o alto desempenho do hardware à flexibilidade do software. Um sistema de computação reconfigurável possui a flexibilidade de reprogramação do hardware em tempo real, para permitir dedicação exclusiva à execução de uma aplicação específica.

Com a expansão desta tecnologia e necessidade de obtenção de maior poder de processamento, surgiram os PLDs (Programmable Logic Devices), que é um termo geral para designar alguns tipos de circuitos integrados, usados para implementação de hardwares digitais. Os chips podem ser configurados pelo usuário final para realizar diferentes tipos de projetos (BROWN; ROSE, 2000). Estes dispositivos permitem obter desempenho próximo ao fornecido pelos ASICs e com a vantagem de não possuírem os custos e riscos destes.

Os PLDs mais utilizados na construção de hardware reconfigurável são os FPGAs, que são CIs digitais que contêm blocos lógicos configuráveis com conexões programáveis entre eles (MAXFIELD, 2004).

Os FPGAs são muito úteis para dar suporte ao processamento de aplicações complexas e intensivamente computacionais. Um exemplo deste tipo de aplicação pode ser encontrado na pesquisa de Chiaramonte e Moreno (2002). Eles programam funções para criptografar dados em hardware FPGA e observam que a velocidade de processamento nesse tipo de dispositivo é mais lenta do que em microprocessador. Contudo, seu melhor desempenho se deve à possibilidade de processar maior número de dados em paralelo, otimizando o processamento.


4. Modelo de representação e algoritmo de resolução do STP

Para modelar o problema, considerou-se que: Dados os conjuntos { }nt,,=t ...1,2 de turmas, { }mp,,=p ...1,2 de professores e { }kh,,=h ...1,2 de horários.

Toda turma t deve cumprir obrigatoriamente uma carga horária 25=hk aulas semanais, distribuídas em 5 dias de 5 aulas cada. E um professor p pode lecionar um número de aulas menor ou igual a 25 aulas semanais, distribuídas em várias turmas, conforme mostra a Tabela 1.

Tabela 3. Carga horária semanal de professor por tu rma

p/t 1 2 3 ... nt Total

1 1k 2k 5k ... 0 1s

2 0 3k 5k ... 1k 2s

3 8k 4k 0 ... 0 3s

... ... ... ... ... ... ...

mp 2k 0 0 ... 6k ms

Total 25 25 25 ... 25

Onde: ik=t)PT(p, , se o professor p tem certa carga horária ik a lecionar para a turma t ; 0=t)PT(p, , se o professor p não leciona para a turma t e; ps é a carga horária

semanal de cada professor p . O problema consiste em designar para cada turma t , em cada horário h , um professor p para lecionar, conforme mostra a Tabela 2.

Onde: p=h)TH(t, , se o professor p for designado para lecionar para a turma t no horário h .

Neste modelo, as restrições a seguir foram levadas em consideração. Para tanto, foram classificadas em fortes e fracas, como sugerido no trabalho de Fernandes et al. (2002). No qual utilizam ainda, pesos para determinar quais restrições têm maior prioridade de serem satisfeitas.

Tabela 4. Designação de aulas

t/h 1 2 3 ... nh

1 1p 2p 2p ... 5p

2 3p 4p 1p ... 1p

3 2p 3p 8p ... mp

... ... ... ... ... ...

nt 4p 6p 3p ... 8p

Restrições fortes: São aquelas que se não satisfeitas geram soluções inviáveis.

1) Um professor não pode lecionar para mais de uma turma no mesmo horário, o que gera sobreposição de professores. Isto pode ser observado em cada coluna da Tabela 2, onde não deve haver mais de um professor por coluna.

Restrições fracas: São aquelas que se satisfeitas, aumentam a qualidade das soluções, caso contrário, não implicam em soluções inviáveis.


2) Maximizar o atendimento à preferência de professores por horários de indisponibilidade para lecionarem.

Esta restrição pode ser representada como na Tabela 3.

Tabela 5. Tabela PHI de horários indisponíveis de p rofessores

p/h 1 2 3 ... nh

1 1 0 0 ... 0 2 0 0 1 ... 0 3 0 0 1 ... 0 ... ... ... ... ... ...

mp 0 0 0 ... 1

Onde: 1=h)PHI(p, , se o professor p não estiver disponível para o horário h , e; 0=h)PHI(p, , caso contrário.

3) Reduzir a ocorrência de o professor lecionar mais que duas aulas da mesma matéria por dia, para uma mesma turma.

4) Minimizar o número de aulas divididas, ou seja, aquelas de uma mesma matéria que o professor leciona em horários não consecutivos para uma mesma turma, no mesmo dia.

5) Minimizar o número de janelas na agenda do professor, ou seja, horários que o professor fica livre entre uma ou mais aulas do dia.

Tabela 6. Pesos associados às restrições

Restrição Peso Não sobrepor professores p1 Atender preferência por horários indisponíveis p2 Minimizar número de aulas excedentes de 2 p3 Minimizar número de aulas quebradas p4 Minimizar número de janelas na agenda do professor p5

Para prover um meio de configurar a ordem de prioridade de satisfação das restrições utiliza-se uma tabela de pesos, como mostrado na Tabela 4. Assim, a ordem de prioridade pode ser definida conforme desejado. Os pesos permitem ainda, a possibilidade de se obter uma avaliação da solução obtida, quantificando-se o número de violações em cada restrição e multiplicando-as pelos respectivos pesos. O valor encontrado é atribuído então a uma variável f , a qual é definida como função objetivo. Sendo assim, o valor de f permite comparar duas soluções e determinar qual é a melhor. A Figura 1, mostra o pseudocódigo do algoritmo proposto para o modelo.


FIM retorne 10

ENQUANTO FIM 9encontrada solução nova 8

der menor valo possui que a selecione e permuta cada Avalie turmada horários nos alocados profs os com possíveis permutas as Faça 7

entealeatoriam turmada horários Selecione 6 aleatória turmauma Selecione 5

satisfeito não parada de critério ENQUANTO 4s de avaliaçãof 3

s 2aleatória s inicial solução umaGerar 1

) INICIO(

0

0

0

s

sf

tkk!thk

t

s

←

←←

Figura 1. Algoritmo de k! permutas

O método usa a idéia de recursão proposta em Feofiloff (2010), que diz que se um problema possui a propriedade de recursão. Então se pode reduzi-lo a uma instância menor, encontrar a solução para esta instância e utilizá-la para construir uma solução para a instância original do problema. A implementação deste método pode ser observada nas linhas de 5 a 7 (Figura 1). O algoritmo constrói a solução para o problema a partir do rearranjo dos professores encontrados nos k horários de uma turma t , selecionada aleatoriamente. Assim, num processo recursivo a solução s tende a convergir para uma solução melhor. Uma desvantagem do método é que com o aumento do valor k , analisar as k! possibilidades de troca de horários dos professores (linha 7), torna-se impraticável. Contudo, se dispuser de uma máquina com capacidade de processamento paralelo, pode-se implementar rotinas para realizar as permutas da linha 7 em paralelo. O que pode fornecer soluções melhores e em menos tempo.

5. Resultados de testes realizados com implementação em software

Esta seção apresenta a análise de alguns dos resultados obtidos com testes realizados em software para instâncias reais do problema, os dados foram fornecidos pelo Colégio Estadual Alberto Santos Dumont5.

O algoritmo k! permutas foi codificado com o Microsoft Visual Basic 6.3 incorporado ao Microsoft Excel 2003, e executado em um computador notebook com processador Intel Celeron Dual Core T1400 1732MHz, memória de 2GB, barramento de 533 MHz e 512kB de memória cache.

Nos testes realizados foram utilizados k=6 e os pesos da Tabela 5 abaixo:

Tabela 5. Pesos utilizados

Restrição Peso Não sobrepor professores Atender preferência por horários indisponíveis

100

Minimizar número de aulas excedentes de 2 10 Minimizar número de aulas quebradas 5 Minimizar número de janelas na agenda do professor 1

5 Colégio Estadual Alberto Santos Dumont – Ensino Fundamental e Médio, da Cidade de Campina da

Lagoa, Estado do Paraná, Brasil, no ano letivo de 2008.


Os gráficos a seguir mostram o desempenho do algoritmo para testes realizados com três instâncias diferentes. Neles são mostrados os valores da função objetivo f em função do tempo de execução do algoritmo. Cada gráfico mostra a curva f para seis execuções diferentes.

Conforme a Figura 2, na instância 01 apenas 1 de 6 execuções não convergiu para uma solução viável dentro de um tempo de execução de 300 segundos.

Para a Figura 3, na instância 02 apenas 1 execução não convergiu, considerando um tempo de 210 segundos.

Na Figura 4 para a instância 03 todas as execuções convergiram até um tempo de 60 segundos.

Característica das Instâncias:


66

Instância 01:

- nº. de professores: 27 - nº. de turmas: 12 - nº. de aulas: 300 - nº. de horários com indisponibilidade: 200

Instância 02:


Instância 03:


Instância 01

0

2000

4000

6000

8000

10000

12000

14000

16000

0 30 60 90 120 150 180 210 240 270 300 330

tempo (s)

fo

execução1

execução2

execução3

execução4

execução5

execução6

Figura 2. Execuções com a instância 01

Instância 02

0

2000

4000

6000

8000

10000

12000

0 30 60 90 120 150 180 210 240

tempo (s)

fo

execução1

execução2

execução3

execução4

execução5

execução6


Instância 03

0

1000

2000

3000

4000

5000

6000

7000

8000

0 30 60 90 120 150

tempo (s)

fo

execução1

execução2

execução3

execução4

execução5

execução6



67

6. Análise do algoritmo e esquema para implementação do hardware

Esta seção discute os mecanismos do algoritmo apresentado e exibe um esquema para implementação do hardware proposto, que deve ser programado em dispositivo FPGA com a linguagem VHDL.

Supondo que a Tabela 6 seja uma solução inicial 0s para o problema, mostra-se neste exemplo uma iteração do algoritmo para 3=k . Para isto considera-se apenas as restrições 1 e 4, com peso ajustado para 2 e 1, respectivamente.

Tabela 6. Solução inicial 0s

t/h 1 2 3 4 ... 25

1 2p 1p 2p 4p ... 5p

2 3p 7p 1p 1p ... 1p

3 5p 3p 8p 4p ... mp

... ... ... ... ... ...

nt 6p 1p 3p 8p

... 8p

1ª Iteração:

Linha 3: 5=f , há duas violações na restrição 1 e uma violação na restrição 2, conforme mostram os tons de cor na Tabela 6. Linhas 5 e 6: supondo que a turma selecionada seja a turma 1, e os horários sejam 1, 2 e 4. Linha 7: o algoritmo testa todas as soluções possíveis de serem obtidas, permutando-se os professores destes três horários e selecionando desta forma, a melhor delas.

Como são k! possibilidades, então se tem 63 =! possibilidades, cujas configurações são mostradas nas Tabelas de 7 a 12.

Tabela 7. 1ª permuta 5=f t/h 1 2 3 4 ... 25

1 2p 1p 2p 4p ... 5p


1 2p 4p 2p 1p ... 5p


1 1p 2p 2p 4p ... 5p


1 1p 4p 2p 2p ... 5p


1 4p 1p 2p 2p ... 5p


1 4p 2p 2p 1p ... 5p


68

Tabela 13. Solução s após a iteração 1 t/h 1 2 3 4 ... 25

1 1p 4p 2p 2p ... 5p

2 3p 7p 1p 1p ... 1p

3 5p 3p 8p 4p ... mp

... ... ... ... ... ...

nt 6p 1p 3p 8p ... 8p

Ao fim, a melhor opção é selecionada, neste caso a da 4ª permuta (Tabela 10), onde 0=f e todas as violações foram eliminadas. Linha 8: a iteração termina com a atribuição da melhor solução à variável s e a execução continua na próxima iteração, caso o critério de parada não seja satisfeito.

Como o processamento é muito intenso no ponto recursivo onde são testadas as k! permutas, o processamento em microprocessador se torna lento. Sugere-se o projeto de um sistema para resolução do STP, que compartilhe recursos de software e hardware ao mesmo tempo. Ou seja, programar uma parte do algoritmo que exige menos recurso computacional, em microprocessador. E a parte que executa as permutas na linha 7, em hardware. Conforme mostra o esquema da Figura 5.

Figura 5. Esquema do algoritmo com implementação em Software/Hardware

A proposta visa explorar o recurso de processamento paralelo disponível nos FPGAs, para processar em um único nível as k! permutas de professores nos k horários definidos. Para tanto, se propõe ainda o uso da linguagem VHDL como a ferramenta para projeto e simulação dos circuitos em hardware visando à construção de um sistema otimizado e de melhor desempenho do que o realizado apenas em microprocessador.

Selecione k horários h da

Selecione uma turma t Não

Parada? Sim

FIM

Retorne s

Selecione a melhor solução

←s nova solução

MICROPROCESSADOR

Gerar uma solução inicial 0s

0 de avaliação sf ←

INICIO

Avaliar 1ª

possibilidade

Avaliar 2ª

possibilidade

Avaliar (k!)ª possibilidade

...

DISPOSITIVO


69

7. Considerações Finais

Apesar do processamento realizado em dispositivo FPGA ser mais lento que o mesmo processamento realizado em microprocessadores, sua capacidade de processamento em paralelo compensa esta desvantagem, tornando-o um hardware de alto desempenho.

Uma característica importante do FPGA é a possibilidade de reconfigurabilidade, tornando-o um dispositivo de contribuição significativa em projeto de sistemas. Uma vez implementado o sistema, alterações em funções poderão ser realizadas com facilidade no próprio dispositivo, sem a necessidade de substituição do mesmo. Outro ponto relevante no desenvolvimento do sistema é o uso da linguagem VHDL, que permite a simulação do sistema, facilitando o projeto do circuito a ser implementado em hardware.

A proposta de implementação do hardware teve como base os bons resultados obtidos com testes em software e justifica a proposta do presente trabalho de implementação em FPGA para melhorar o desempenho de processamento do algoritmo.

Referências

AMORE, R. VHDL: descrição e síntese de circuitos digitais. Rio de Janeiro: LTC, 2005.

ASHENDEN, P. J.; LEWIS, J. VHDL-2008: Just the new stuff. USA: Elsevier/Morgan Kaufmann, 2008.

BROWN, S.; ROSE, J. Architecture of FPGAs and CPLDs: A Tutorial. Department of Electrical and Computer Engineering, University of Toronto, 2000. Disponível em: <http://www.eecg.toronto.edu/~jayar/pubs/brown/survey.pdf>. Acesso em: 22 abr. 2010.

CARRASCO M. P., PATO M. V. A Potts Neural Network Heuristic for the class/teacher timetabling problem. Metaheuristics: Computer Decision-Making. Massachusetts, Kluwer Academic Publishers, p. 173-186, 2003.

CHIARAMONTE, R. B.; MORENO, E. D. Criptografia POSICIONAL em Hardware (VHDL e FPGAs). Faculdade de Informática de Marília. Marília, 2002.

COMPTON, K.; HAUCK, S. An Introduction to Reconfigurable Computing. Department of Electrical and Computer Engineering. University of Wisconsin-Madison, 2003. Disponível em: <http://www.ece.wisc.edu/~kati/Publications/ Compton_ReconfigIntro.pdf>. Acesso em: 24 abr. 2010.

COSTA, F. P. Programação de horários em escolas via GRASP e Busca Tabu. 2003. 39 p. Trabalho de Conclusão de Curso (Graduação) – Faculdade de Engenharia de Produção, Universidade Federal de Ouro Preto – Escola de Minas, Ouro Preto, 2003.

FANG, H. Genetic Algorithms in Timetabling and Scheduling. 1994. 243 p. Ph. D. Thesis - Department of Artificial Intelligence, University of Edinburg, 1994.

FEOFILOFF, P.. Minicurso de Análise de Algoritmos. Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2010.


70

FREITAS, C. C. et al. Uma ferramenta baseada em Algoritmos Genéticos para a geração de tabela de horário escolar. Salvador, 2007.

LOBO, E. L. M.. Uma solução do problema de horário escolar via Algoritmo Genético Paralelo. 2005. 86 p. Dissertação (Mestrado em Modelagem Matemática e Computacional) – Centro Federal de Educação Tecnológica de Minas Gerais, Belo Horizonte, 2005.

MAXFIELD, C. The Design Warrior’s Guide to FPGAs. Elsevier: Oxford, 2004. ISBN: 0-7506-7604-3.

PEDRONI, V. A. Circuit design with VHDL . MIT Press: Massachusetts, 2004. ISBN: 0262162245.

RIBEIRO A. A. L. Reconfigurabilidade dinâmica e remota de FPGAs. 2002. 136 p. Dissertação (Mestrado em Ciência de Computação e Matemática e Computacional) – Instituto de Ciências Matemáticas e de Computação – USP, São Carlos, 2002.

SOUZA, M. J. F. et al. Métodos de Pesquisa em Vizinhança Variável aplicados ao problema de alocação de salas. In: Encontro Nacional de Engenharia de Produção, 22, 2002, Curitiba.

SOUZA, M. J. F.; MACULAN, N.; L. S., OCHI. Melhorando quadros de horário de escolas através de caminhos mínimos. In: Sociedade Brasileira de Matemática Aplicada e Computacional, 2, 2000.

VAHID, F.; LYSECKY, R. VHDL for digital design. USA: Wiley, 2007.


71

Implementação de um Módulo Otimizador para o

Compilador SCC visando seu Uso como Ferramenta

Educacional

George S. Oliveira e Valéria D. Feltrim

Departamento de informática – Universidade Estadual de Maringá (UEM) CEP 87020-900 – Maringá – PR – Brazil

[email protected], [email protected]

Abstract. This paper presents the parcial results of the implementation of an optimizer module for the SCC compiler (SOIS C Compiler), which is focused on this part of the compilation process. Several techniques for optimizing intermediate code were implemented, both machine independent and dependent. A graphical interface still being developed should provide resources and feedback regarding the optimization process to the user, making the understanding of the compilation process easier.

Resumo. O presente trabalho apresenta os resultados parciais do desenvolvimento de um módulo otimizador para o compilador SCC (SOIS C Compiler) voltado ao ensino dessa etapa do processo de compilação. Foram implementadas diversas técnicas de otimização de código intermediário, tanto independente quanto dependente de máquina. Uma interface gráfica ainda em desenvolvimento deverá fornecer recursos e feedback relativo ao processo de otimização para o usuário, facilitando assim o entendimento do processo de compilação.

1. Introdução

Devido à complexidade existente na aprendizagem da disciplina de Compiladores, torna-se necessária a criação de técnicas de simulação como ferramentas para facilitação de aprendizado da mesma. O raciocínio auxiliado pelo computador aumenta os recursos e metodologias de ensino, porque facilita a exemplificação e assimilação de processos teóricos e práticos de experimentos difíceis de serem conduzidos na prática real.

O projeto SOIS (Sistema Operacional Integrado Simulado) (Gonçalves et al., 2004), se enquadra no contexto apresentado, envolvendo a simulação parametrizada de um compilador para a linguagem de programação C, um montador (chamado SASM) (Foleiss et al., 2009a), um sistema operacional e um processador. Destes, o último que integrará o sistema é o compilador, chamado de SOIS C Compiler (SCC) (Foleiss et al., 2009b).

A construção do compilador SCC foi norteada por dois objetivos principais. O primeiro é permitir a compilação de programas reais codificados na linguagem C, gerando código de montagem compatível com o montador SASM. O segundo é auxiliar no ensino nos aspectos relacionados à compilação de programas, mostrando e detalhando todas as etapas do processo de compilação, bem como as estruturas auxiliares utilizadas no processo.


72

Esses objetivos permitem trazer flexibilidade ao SCC, se comparados aos compiladores atuais, uma vez que estes últimos não dispõem de recursos que facilitam o aprendizado das etapas do processo de compilação. Etapas como a análise léxica, sintática, semântica e geração de código de montagem já possuem pontos de depuração implementados no SCC, porém, o desenvolvimento de um módulo de otimização, bem como possíveis pontos de depuração para essa etapa, ainda não se encontra finalizado.

Desta forma, o objetivo deste projeto é estudar e implementar as otimizações previstas para o módulo de otimização do SCC, criar pontos de depuração para essa etapa e desenvolver uma interface gráfica que viabilize ao usuário a escolha de otimizações que o mesmo deseja aplicar e mostre os resultados dessas otimizações.

2. O SCC

O SCC (SOIS C Compiler) (Foleiss et al., 2009b) é um compilador de linguagem C para a arquitetura IA-32 capaz de gerar, como saída, uma listagem de código de montagem compatível com o montador SASM (Foleiss et al., 2009a).

O SASM é um montador de linguagem assembly com sintaxe compatível com o padrão da Intel, que é responsável pela geração de código-objeto para processadores da arquitetura IA-32, a arquitetura-alvo de simulação do Projeto SOIS. O SASM foi desenvolvido principalmente para agilizar o processo de teste da ferramenta SOIS, permitindo a escrita de programas complexos e auxiliando no ensino da disciplina de arquitetura de computadores.

Mesmo que existam diversos compiladores da linguagem C para a arquitetura supracitada, entre elas, o conhecido GCC da GNU, o desenvolvimento de um compilador para esta linguagem é justificada pelas seguintes razões: (1) o simulador SOIS não contempla todo o conjunto de instruções da linguagem; (2) o compilador deve proporcionar facilidades que ajudam no ensino de disciplinas que abordam o processo de compilação.

Além de fazer a compilação de um programa em C, o SCC disponibiliza um feedback relativo às etapas de análise sintática e semântica, mostrando ao usuário resultados intermediários e estruturas utilizadas em cada processo (Foleiss et al., 2009b). O objetivo é que tais informações possam ser usadas tanto por professores quanto por alunos para o melhor entendimento das diversas etapas envolvidas na compilação de um programa.

Uma vez que o módulo otimizador faz parte do SCC, o mesmo também deve exibir informações que possam ser utilizadas por professores e alunos, além de realizar as otimizações no código. Assim como foi feito para as etapas sintática e semântica, para a etapa de otimização também devem ser disponibilizados possíveis dados intermediários e estruturas utilizadas em cada otimização.

Tais informações são fornecidas por meio de um processo caracterizado pela sequência “varredura – aviso – otimização”. Tal processo se dá da seguinte forma: supondo uma entrada livre de erros léxico, sintático e semântico, o sistema “varre” a entrada em busca de trechos de código que sejam passíveis de otimização. Caso tais trechos sejam encontrados, os mesmos são mostrados ao usuário, que recebe um “aviso” para que opte por aplicar a(s) otimização(ões) disponíveis para aquele código ou não. Se a escolha for pela aplicação da(s) otimização(ões), a(s) mesma(s) será(ão) aplicada(s), o código resultante será exibido e uma nova varredura a procura por


73

outras otimizações será realizada, iniciando uma nova sequência de interação. A repetição do processo “varredura – aviso – otimização” ocorre até que não haja otimizações disponíveis ou até que o usuário termine o processo. No final, é gerado um relatório descrevendo passo-a-passo as otimizações aplicadas, bem como o código antes e depois de cada otimização.

3. Otimizações de código

Desde o início da história da compilação a qualidade do código gerado pelo compilador é muito importante. O tamanho do código gerado e, principalmente, a velocidade são atributos essenciais para medir a qualidade de um código. A otimização é um processo de coleta de informações e transformação do código-fonte de entrada para um código próximo do ótimo (Aho et al., 2007).

Diversas técnicas de melhoria de código foram desenvolvidas ao longo dos anos, e são coletivamente chamadas de técnicas de otimização de código. A complexidade e implementação dessas técnicas variam bastante, pois são dependentes de vários fatores tais como o escopo do código a ser otimizado, estruturas auxiliares e informações necessárias para julgar certa otimização. Segundo Aho et al. (2007), não se deve utilizar todas as técnicas de otimização disponíveis, mas sim julgar quais devem resultar em melhorias de código significativas que causem menor impacto na complexidade do compilador.

As técnicas desenvolvidas podem ser classificadas em dois tipos: dependentes e independentes de máquina e são utilizadas até hoje nos compiladores mais modernos (Aho et al., 2007; Louden, 2004).

3.1 Otimizações independentes de máquina

Aho et al. (2007) afirma que as construções de alto nível podem introduzir um custo substancial em tempo de execução se construções independentes forem ingenuamente traduzidas para código de máquina. As otimizações independentes de máquina visam substituir seqüências de instruções por outras seqüências equivalentes, porém, mais rápidas.

As construções deste tipo de otimização foram feitas sobre a representação de código de três endereços, que é um tipo de representação que restringe o número de operadores no lado direito de uma instrução para um. Desta forma, uma instrução do código fonte como “L1:a=x+y*z ” é traduzida conforme mostrado na Figura 1.

L1: t1 = y * z

t2 = x + t1

a = t2

Figura 1. Representação em três endereços para a in strução “L1: a=x+y*z”

O desmembramento de expressões aritméticas com múltiplos operadores e de comandos de fluxo de controle aninhados torna o código de três endereços desejável para a geração e otimização de código objeto; e o uso de nomes para os valores intermediários computados por um programa permite que o código de três endereços seja facilmente rearranjado (Aho et al., 2007).

A maioria das otimizações deste tipo necessitou ser implementada a partir da representação em grafo de fluxo, o qual apresenta as seguintes características:


74

a) Seus nós são chamados de blocos básicos, os quais são seqüências máximas de instruções consecutivas de três endereços e com as seguintes propriedades:

i. O fluxo de controle só pode entrar pela primeira instrução do bloco básico, ou seja, não existem desvios no meio dos blocos;

ii. O controle sairá do bloco sequencialmente da primeira para a última instrução ou por um desvio na última instrução;

b) As arestas do grafo de fluxo denotam quais blocos podem ser seguidos após outro bloco.

A idéia de se representar o código intermediário na forma de um grafo se faz útil porque é possível realizar um melhor trabalho de alocação de registradores e seleção de instruções, se soubermos como os valores são definidos e usados (Aho et al., 2007).

A seguir, são descritas quais as otimizações desta categoria que foram implementadas no SCC.

3.1.1. Eliminação de subexpressões comuns globais

Uma expressão E é chamada de subexpressão comum se E tiver sido computada anteriormente e os valores das variáveis em E não tiverem sido modificados desde sua computação anterior. Essa técnica visa usar o valor de E computado anteriormente, evitando recomputa-lo (Aho et al., 2007; Muchnick, 1997).

3.1.2. Propagação de cópia

A idéia da transformação de código utilizando esta técnica é que, após um comando de cópia a = b, as próximas atribuições cujo valor “a” esteja do lado direito seja, então substituído por “b” (Aho et al, 2007; Muchnick, 1997). Aho et al. (2007) afirma que essa modificação é capaz de gerar código morto mesmo que, aparentemente, não apresente melhorias.

O código morto gerado pode ser eliminado por meio da otimização de eliminação a seguir.

3.1.3. Eliminação de código morto

Uma variável estará viva em algum ponto de um programa se seu valor puder ser usado posteriormente Aho et al. (2007). Caso contrário, ela está morta nesse ponto. Uma idéia relacionada é o código morto. Um código estará morto quando ele não possuir utilidade, e sua exclusão não afetar em absolutamente nada a semântica do programa. Embora esse código possa já estar presente no início da compilação, ele é geralmente criado como resultado de outras otimizações, como a propagação de cópia e o desdobramento de constante.

Segundo Muchnick (1997), muitas otimizações geram código morto como parte de um princípio de divisão de trabalho, que se caracteriza por manter cada fase de otimização o mais simples possível a fim de torná-lo mais fácil de ser implementado, deixando para outras fases (a eliminação de código morto) a tarefa de eliminação posterior.


75

3.1.4. Movimentação de código

Os loops constituem um local muito importante para a aplicação de otimizações, já que é onde os programas costumam gastar a maior parte do tempo. Logo, segundo Aho et al. (2007), é muito interessante diminuir a quantidade de instruções num laço interno, mesmo que isso aumente o número de instruções fora do laço.

A otimização por movimentação de código trabalha no reconhecimento de trechos de código que produzem sempre o mesmo valor a cada iteração de um loop, para, então, movê-los para fora dele (Muchnick, 1997).

3.1.5. Desdobramento de constante

Dada uma atribuição “x = c”, tal que “x” é uma variável e “c” uma constante, o desdobramento de constante caracteriza-se por substituir os próximos usos de “x” por “c”, desde que “x” não tenha sido modificado em instruções intermediárias a estas (Muchnick, 1997).

3.1.6. Eliminação de código inalcançável

Código inalcançável é qualquer trecho de código que não será executado em nenhum ponto do programa. Um exemplo claro é qualquer instrução não-rotulada que segue um desvio incondicional. Será uma instrução morta porque não há um caminho no grafo de fluxo para ela.

Os possíveis casos para aplicação desta otimização no SCC são descritas a seguir e exemplificadas nas Figuras 2, 3, 4 e 5.

i. Instruções não rotuladas após um desvio incondicional: nesse caso, todo o trecho a partir do desvio até o próximo rótulo é eliminado (Figura 2).

<comandos1> goto L1: <comandos2> L1: <comandos3>

<comandos1> goto L1: L1: <comandos3>

(a)

=>

(b)

Figura 2. Caso possível de otimização de código ina lcançável no SCC – instruções não rotuladas após desvio incondicional (a) e código já otimizado (b)

ii. Desvio incondicional não-rotulado imediatamente após um desvio condicional: independente do resultado do teste de condição, o fluxo do programa irá mudar para algum rótulo de destino.

t0 = x == 1; if t0 goto L1 goto L2 L1: <comandos1> L2: <comandos2>

t0 = x != 1 if t0 goto L2 <comandos1> L2: <comandos2>

(a)

=>

(b)

Figura 3. Caso possível de otimização de código ina lcançável no SCC – desvio incondicional não-rotulado imediatamente apó s um desvio condicional (a) e código já otimizado (b)

iii. O desdobramento de constante detectou que a variável usada na condição do if tem sempre valor 1 (verdadeiro) em todo o fluxo do programa. Assim, todo código que vem abaixo da condição até o próximo rótulo é excluído.


76

t0 = 0 != 1 if t0 goto L1 <comandos1> L1: <comandos2>

t0 = 1 goto L1 L1: <comandos2>

(a)

=>

(b)

Figura 4. Caso possível de otimização de código ina lcançável no SCC – desdobramento de constante avalia a expressão como sempre verdadeira (a) e código já otimizado (b)

iv. O desdobramento de constante detectou que a variável usada na condição do if tem sempre valor 0 (falso) em todo o fluxo do programa. Assim, todo código que é destino do desvio da condição é excluído.

t0 = 1 != 1 if t0 goto L1 <comandos1> L1: <comandos2> L2: <comandos3>

t0 = 0 <comandos1> L2: <comandos3>

(a)

=>

(b)

Figura 5. Caso possível de otimização de código ina lcançável no SCC – desdobramento de constante avalia a expressão como sempre falsa (a) e código já otimizado (b)

3.1.7. Otimização de fluxo de controle

Esta estratégia visa verificar e remover sempre que possível os desvios desnecessários, que podem ser: (1) incondicionais para incondicionais, (2) incondicionais para condicionais e (3) condicionais para incondicionais, conforme mostrado na Figura 6.

goto label1

...

label1: goto label2

Porque desviar para um outro desvio? Faça o primeiro desvio desviar para o destino do segundo:

goto label2

...

label1: goto label2

Se não houver desvios para label1, elimina o comando label1: goto label2:

goto label2

...

Figura 6. Casos para aplicação da otimização de flu xo de controle

3.2 Otimizações dependentes de máquina

Compiladores que produzem códigos-objeto eficientes normalmente incluem uma fase de otimização que fica situada antes da geração de código final. As otimizações realizadas nesse ponto trabalham sobre o código assembly gerado, que é dependente da arquitetura, neste caso, a arquitetura IA-32.


77

As otimizações implementadas para o SCC foram: (1) eliminação de cargas e armazenamentos redundantes; (2) simplificação algébrica e redução de força; (3) uso de idiomas de máquina; e (4) alocação de registradores por coloração de grafo, descritas a seguir.

3.2.1. Eliminação de cargas e armazenamentos redundantes

Um gerador de código objeto é dito ingênuo quando a construção do código objeto é feita a partir de cada comando da representação intermediária, sem levar em conta a natureza do conjunto de instruções da máquina alvo. Esse tipo de construção comando por comando frequentemente produz um código ruim, sendo obrigatória a aplicação de otimizações adicionais (Aho et al., 2007).

Uma destas otimizações é a otimização para eliminação de cargas e armazenamentos redundantes, que visa simplificar uma seqüência de instruções de atribuição que não modificam o estado de um registrador ou variável, para uma atribuição simples, descartando as próximas desde que estas não estejam rotuladas.

MOV EAX, y MOV y, EAX

Figura 7. Exemplo de atribuição redundante não-rotu lada

Conforme exemplificado na Figura 7, a sequencia não precisa conter a segunda atribuição porque uma atribuição igual já foi realizada na linha anterior. Como resultado, a segunda atribuição pode ser excluída.

MOV EAX, y L1:MOV y, EAX

Figura 8. Exemplo de atribuição redundante, porém r otulada

No entanto, se a segunda atribuição fosse rotulada, como mostra a Figura 8, não seria garantido que a primeira sempre seria executada antes dela. Assim sendo, não podemos remover esta instrução. Em outras palavras, as duas instruções precisam estar no mesmo bloco básico (ou seja, deve estar no mesmo nó do grafo de fluxo) para que elas gerem uma seqüência redundante.

3.2.2. Simplificação algébrica e redução de força

Esta técnica tem como finalidade a eliminação de comandos que não afetam o valor da variável de destino (como “x=x+0 ” ou “x=x*1 ”) ou na simplificação de instruções por outra de menor carga, porém equivalente. Por exemplo:

i. “ t0=2*x ” que pode ser modificada para “t0=x+x ”;

ii. ” t0=x/2 ” que pode ser modificada para “t0=x>>1 ”.

3.2.3. Uso de idiomas de máquina

Esta técnica tem por base substituir certas operações por instruções específicas de máquina, já que são mais eficientes. No caso do SCC, cujo código é montado pelo SASM, apenas instruções de incremento e decremento estão disponíveis para substituição de códigos de três endereços, como “x=x+1 ” e “x=x–1 ”, respectivamente.

Dessa forma, uma instrução SCC do tipo “x=x+1 ”, representada em código de três endereços pela sequencia abaixo:


78

t0 = x + 1

x = t0

pode ser simplificada pela instrução inc x .

Instruções como INC e DEC no nível intermediário são facilmente traduzidas pelas instruções correspondentes em nível de máquina (otimização dependente). O fato de esta otimização ser considerada dependente de máquina se deve ao fato de ser passível de tradução para um código que a máquina implementa (como INC e DEC), mesmo que ela seja aplicada na representação intermediária do código.

3.2.4. Alocação de registradores por coloração de grafo

Quando um registrador é necessário na computação, mas todos os registradores disponíveis estão em uso, o conteúdo de um dos registradores deve ser armazenado (“derramado”) em um endereço de memória. A coloração de grafos é uma técnica que permite alocar e gerenciar o derramamento de registradores.

Para o SCC, a implementação desta técnica foi voltada para a alocação de registradores de um subprograma completo (funções do SCC), logo, a sua implementação exigiu a representação em grafo de fluxo e, consequentemente, da análise do fluxo de dados, mais especificamente, a análise de variáveis vivas.

3.3. Exemplo e considerações

Para exemplificar parte das otimizações implementadas no SCC, na Figura 9 é apresentado o código intermediário não-otimizado gerado pelo SCC para uma sub-rotina que implementa o algoritmo de Crout6 para matrizes 4x4 representadas em vetores, cujos elementos são todos inteiros diferentes de 0. Na Figura 10, o mesmo código intermediário é apresentado após ter sido otimizado pelo SCC.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 33 34 35 36 37 38 39 40 41

croutdecomp n = 4 i = 0 __for__0: t0 = n * n t1 = i < t0 iffalse t1 goto __for_final__0: j = 0 __for__1: t2 = j < n iffalse t2 goto __for_final__1: t3 = i + j t4 = l[t3] l[t3] = 0 t5 = i + j t6 = u[t5] u[t5] = 0 __for_passo__1: t7 = j + 1 j = t7 l[t13] = t16 __for_passo__2: t17 = i + 1 i = t17 goto __for__2: __for_final__2: i = 0 __for__3: t18 = n * n t19 = i < t18 iffalse t19 goto __for_final__3: j = 0

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 70 71 72 73 74 75 76 77 78

goto __for__1: __for_final__1: __for_passo__0: i = i + n goto __for__0: __for_final__0: i = 0 __for__2: t8 = i < n iffalse t8 goto __for_final__2: t9 = u[i] t10 = a[i] u[i] = t10 t11 = i * n t12 = l[t11] t13 = i * n t14 = a[t13] t15 = u[0] t16 = t14 / t15 j = t37 __for__6: t38 = j < n iffalse t38 goto __for_final__6: sum = 0 k = 0 __for__7: t39 = i / n t40 = k < t39 iffalse t40 goto __for_final__7: t41 = i + k

6 Dada uma matriz quadrada A, o algoritmo de Crout gera, a partir de “A”, duas matrizes “L” e “U”

triangulares tal que “L x U = A”.


79

42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

__for__4: t20 = i / n t21 = t20 + 1 t22 = j < t21 iffalse t22 goto __for_final__4: sum = 0 k = 0 __for__5: t23 = k < j iffalse t23 goto __for_final__5: t24 = i + k t25 = l[t24] t26 = k * n t27 = t26 + j t28 = u[t27] t29 = t25 * t28 t30 = sum + t29 sum = t30 __for_passo__5: t31 = k + 1 k = t31 goto __for__5: __for_final__5: t32 = i + j t33 = l[t32] t34 = i + j t35 = a[t34] t36 = t35 - sum l[t34] = t36 __for_passo__4: j = j + 1 goto __for__4: __for_final__4: t37 = i / n

79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

t42 = l[t41] t43 = k * n t44 = t43 + j t45 = u[t44] t46 = t42 * t45 t47 = sum + t46 sum = t47 __for_passo__7: t48 = k + 1 k = t48 goto __for__7: __for_final__7: t49 = i + j t50 = u[t49] t51 = i + j t52 = a[t51] t53 = t52 - sum t54 = i / n t55 = i + t54 t56 = l[t55] t57 = t53 / t56 u[t51] = t57 __for_passo__6: t58 = j + 1 j = t58 goto __for__6: __for_final__6: __for_passo__3: i = i + n goto __for__3: __for_final__3: return

Figura 9. Exemplo de código intermediário do SCC nã o-otimizado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 45 46 47 48 49 50 51 52 53 54 55 56

croutdecomp i = 0 __for__0: t1 = i < 16 iffalse t1 goto __for_final__0: j = 0 __for__1: t2 = j < 4 iffalse t2 goto __for_passo__0: t3 = i + j l[t3] = 0 u[t3] = 0 __for_passo__1: inc j goto __for__1: __for_passo__0: i = i + 4 goto __for__0: __for_final__0: i = 0 __for__2: t8 = i < 4 iffalse t8 goto __for_final__2: t10 = a[i] u[i] = t10 t11 = i << 2 t14 = a[t11] t15 = u[0] t16 = t14 / t15 sum = t30 __for_passo__5: inc k goto __for__5: __for_final__5: t32 = i + j t35 = a[t32] t36 = t35 - sum l[t32] = t36 __for_passo__4: j = j + 1 goto __for__4: __for_final__4: j = t20 __for__6: t38 = j < 4 iffalse t38 goto __for_final__6:

23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 65 66 67 68 69 70 71 72 73 74 75 76

l[t11] = t16 __for_passo__2: inc i goto __for__2: __for_final__2: i = 0 __for__3: t19 = i < t0 iffalse t19 goto __for_final__3: j = 0 __for__4: t20 = i >> 2 t21 = t20 + 1 t22 = j < t21 iffalse t22 goto __for_final__4: sum = 0 k = 0 __for__5: t23 = k < j iffalse t23 goto __for_final__5: t24 = i + k t25 = l[t24] t26 = k << 2 t27 = t26 + j t28 = u[t27] t29 = t25 * t28 t30 = sum + t29 t45 = u[t44] t46 = t42 * t45 t47 = sum + t46 sum = t47 __for_passo__7: inc k goto __for__7: __for_final__7: t49 = i + j t52 = a[t49] t53 = t52 - sum t55 = i + t20 t56 = l[t55] t57 = t53 / t56


80

57 58 59 60 61 62 63 64

sum = 0 k = 0 __for__7: t40 = k < t20 iffalse t40 goto __for_final__7: t41 = i + k t42 = l[t41] t43 = k << 2 t44 = t43 + j

77 78 79 80 81 82 83

u[t49] = t57 __for_passo__6: inc j goto __for__6: __for_final__6: __for_passo__3: i = i + 4 goto __for__3: __for_final__3: return

Figura 10. Exemplo de código intermediário do SCC a pós as otimizações.

O programa da Figura 10 executa significativamente menos instruções e instruções mais baratas. No entanto, essas características não são garantidas para todo trecho de programa submetido aos algoritmos de otimização. Isso acontece porque, segundo Aho et al. (2007), não existe garantia, sob qualquer medida matemática, que o código gerado é ótimo.

Mesmo assim, a quantidade e variedade das otimizações implementadas para o SCC e aqui apresentadas abrem espaço para o melhor aprendizado da estrutura e funcionamento de um compilador, uma vez que a etapa de otimização de código, presente na maioria dos compiladores modernos, não fica de fora na exibição de resultados pelo SCC, em estruturas criadas e passos realizados, como já existente nas etapas léxica, sintática, semântica e de geração de código do compilador.

4. Próximos passos

Ainda que o foco do compilador SCC seja o uso educacional, é importante avaliar o quanto as otimizações implementadas de fato influenciam na qualidade do código gerado. Dessa forma, um próximo passo é realizar uma análise comparativa entre conjuntos de entrada e saída para a avaliação da efetividade das otimizações.

Outra questão que ainda não foi abordada neste projeto é relativa à ordem da aplicação das otimizações. À medida que cada otimização é aplicada, oportunidades para novas otimizações podem surgir, o que, em geral, ocorre. Sendo assim, pode ser vantajoso realizar um planejamento tanto da ordem quanto da quantidade de otimizações a serem aplicadas. Até o momento, foi definida a seguinte ordem de aplicação das otimizações:

1. O primeiro passo é eliminar do código intermediário as instruções redundantes. Uma razão para isso é que a exigência computacional nas próximas aplicações será menor se instruções idênticas tiverem sido eliminadas a priori. Para a eliminação destas redundâncias, aplica-se a técnica de movimentação de código e eliminação de subexpressões comuns.

2. Aplica-se a técnica de propagação de cópia.

3. Como o desdobramento de constante possui a mesma característica da propagação de cópia, aplica-se neste passo esta técnica.

4. Assim, como discutido na seção 3.1.3, a aplicação da propagação de cópia, assim como o desdobramento de constante pode gerar código morto. Logo, neste ponto será necessário realizar uma “limpeza” no código, o que pode ser feito pela aplicação da eliminação de código morto.

5. Se o desdobramento de constante avaliar o valor de uma variável como sempre “true” (qualquer valor diferente de zero) ou sempre “false” (valor igual à zero), é interessante realizar neste ponto a eliminação de código inalcançável, já que poderá existir uma possibilidade do valor desta variável ser usada como argumento


81

em um desvio condicional. Se isso acontecer, um dos trechos imediatamente após o desvio poderá ser eliminado do código.

6. Aplica-se as otimizações de fluxo de controle para eliminar possíveis desvios para desvios e, em seguida, realiza novamente a eliminação de código inalcançável para possível eliminação de trechos de código não rotulados imediatamente após um desvio incondicional.

7. Aplica-se as otimizações dependentes de máquina, aplicando, em último lugar, a técnica para alocação de registradores.

Embora um estudo mais detalhado precise ser feito para determinar uma melhor ordem de aplicação destas técnicas, a seqüência citada ainda torna-se viável porque prioriza a aplicação de técnicas que geram código indesejável antes da aplicação das técnicas que executam a limpeza no código. Como o estado final de um código gerado no fim de todas estas aplicações é indeterminado, o mais ideal é que se repita cada otimização na mesma ordem até que nenhuma mudança seja feita no código.

Além disso, outra etapa a ser realizada é o projeto e a implementação de uma interface gráfica para um melhor manuseio do usuário na escolha das otimizações que o mesmo deseja aplicar em um código de entrada, bem como na visualização dos resultados das otimizações.

5. Conclusão

O SCC (SOIS C Compiler) (Foleiss et al., 2009b) é um compilador de linguagem C para a arquitetura IA-32 capaz de gerar, como saída, uma listagem de código de montagem compatível com o montador SASM (Foleiss et al., 2009a). Tal compilador foi desenvolvido tendo como foco sua utilização como ferramenta educacional em disciplinas de Compiladores.

Neste artigo foram apresentados os resultados parciais de um projeto que visa incorporar ao SCC um módulo otimizador de código, que inclui tanto otimizações independentes quanto dependentes de máquina, com o objetivo de permitir aos usuários do SCC não só aplicar as otimizações, mas também visualizar seus resultados, facilitando assim o entendimento do processo de otimização.

Ainda que as análises comparativas entre um conjunto de entrada e um conjunto de saída não tenham sido realizadas, foi bastante animador perceber que um conjunto de saída, aparentemente mais barato em questão de tempo e custo, pôde ser gerado.

Com a conclusão deste projeto espera-se que o SCC possa ser utilizado como ferramenta educacional de apoio ao ensino do processo de compilação de programas como um todo, abrangendo desde as etapas mais simples, como análise léxica e sintática, até as etapas finais, como a geração e otimização de código.

Agradecimentos

Os autores agradecem ao Programa Institucional de Bolsas de Iniciação Científica – PIBIC/CNPq pelo suporte a este projeto.


82

Referências bibliográficas

AHO, A. V., LAM, M. S., SETHI, R., ULLMAN, J. D. Compiladores: princípios, técnicas e ferramentas, 2ª edição. Editora Pearson, 2007.

FOLEISS, J. H.; FELTRIM, V. D.; GONÇALVES, R. A. L. SASM: Uma ferramenta para o ensino do processo de montagem e conjunto de instruções CISC In: WEI – XVII Workshop sobre Educação em Computação, XXIX Congresso da SBC 2009, Bento Gonçalves – RS, 2009a.

FOLEISS, J.H.; ASSUNCAO, G.P.; CRUZ, E.H.M.; GONCALVES, R.A.L.; FELTRIM, V.D. SCC: Um compilador C como ferramenta de ensino de Compiladores. In: Anais do Workshop sobre Educação em Arquitetura de Computadores (WEAC 2009), São Paulo – SP, p. 15-22, 2009b.

GONÇALVES, R.A.; MULATI, M.H.; SILVA, V.P.; GONÇALVES, R.A.L. Sistema Operacional Simulado: Ferramenta para o Ensino de Graduação. In: XXIV Congresso da SBC/XII WEI - Workshop de Educação em Informática, Salvador, 2004.

LOUDEN, K. C. Compiladores: Princípios e Práticas. Thomson Learning, 2004.

MUCHNICK, S. S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.


83

Aplicação MPI para Cálculo do Índice de Fragmentação Multidimensional em Imagens de Sensoriamento Remoto

Henrique Y. Shishido1, Ligia F. A. Batista2, Ronaldo A. L. Gonçalves1

1Departamento de Informática – Universidade Estadual de Maringá(UEM) Av. Colombo, 5790 – UEM – Bloco C56 – 87020-900

2Universidade Tecnológica Federal do Paraná

Av. Estrada dos Pioneiros, 3131 – Campus Londrina – 86036-370

{hyshishido,ronaldo}@din.uem.br, [email protected]

Abstract. The digital image processing has been used in many research areas to pattern recognition and specific image filtering on images. However, depending of image dimension, amount and the used filter type, the runtime can be very lengthy process and difficult the related researches progress. In the context, this work purposes a parallel application of the digital image processing algorithm used in multidimensional index fragmentation (MIF) based on message passing model. Many tests has been executed on geographic satellital images on a cluster composed by 12 cores using the MPI. The result confirms the benefits of the such method of parallelization with a runtime reduction up to 85% in the presented cases.

Resumo. O processamento de imagem digital tem sido usado em diversas áreas de pesquisa como instrumento para o reconhecimento de padrões e de filtragens específicas nas imagens. Entretanto, dependendo do tamanho, da quantidade e do tipo de filtragem utilizada, o tempo de processamento pode ser extremamente alto e dificultar o avanço das pesquisas associadas. Nesse contexto, este trabalho propõe uma aplicação paralela do algoritmo para o processamento de imagem digital utilizado no cálculo de índice de fragmentação multidimensional (IFM) baseado em passagem de mensagens. Várias baterias de testes foram realizadas em imagens geográficas de satélites sobre um cluster composto por 12 núcleos de processamento utilizando o padrão MPI. Os resultados confirmam os benefícios de tal método de paralelização com redução no tempo de processamento acima de 85% nos casos aqui apresentados.

1. Introdução

Os avanços das pesquisas nas diversas áreas de conhecimento humano têm aumentado cada vez mais a demanda por plataformas de hardware e software, que possam oferecer maior capacidade de processamento para a execução de aplicações associadas a problemas complexos do mundo real. Aliado ao crescimento dos novos adventos tecnológicos, a popularização dos computadores tem permitido a criação de novas plataformas com um alto poder de processamento. Computadores off-the-shelf em conjunto com softwares de código aberto permitem a construção de um cluster com capacidade similar àquela oferecida por supercomputadores. Nesse contexto, a computação paralela é utilizada para implementar aplicações que demandam alto poder computacional [Ivanov 2006].


84

Simulações de fenômenos físico-químicos [Gomes 2008] e [Castro and Piccoli 2006], na dinâmica dos fluídos [Carvalho 1995] e [Vasconcelos], previsões sísmicas e climatológicas [Piffer 2009] e [Hallak et al. 2004], entre outros, envolvem grande quantidade de processamento e podem levar dias para serem resolvidos com uso de programação sequencial. Este tempo elevado retarda o avanço das pesquisas, principalmente em áreas que exigem experimentos exaustivos e diversificados. Muitas destas pesquisas fazem uso de processamento de imagens digitais no reconhecimento de padrões [Pedrini and Schwartz 2008], sendo a convolução uma técnica comum de filtragem de frequência que atua no domínio espacial da imagem a fim de se produzir o efeito que se deseja, conforme descrita em [Gonzalez and Woods 2000]. Entretanto, dependendo do tamanho, da quantidade e do tipo de filtragem das imagens, o processamento sequencial tradicional já não atende mais os requisitos de tempo de execução. Nesse contexto, este trabalho propõe, implementa e avalia uma implementação paralela com MPI para o processamento de imagens digitais baseado em convolução com o objetivo principal de reduzir o tempo de execução do processamento. Como estudo de caso, usamos o método de convolução proposto por [Gonzalez and Woods 2000] para gerar o índice de fragmentação de uma imagem de sensoriamento remoto por satélite descrito em [Turner 1989]. Essa implementação paralela foi proposta para um sistema de memória distribuída e implementado na plataforma MPI em um cluster com 12 núcleos. A avaliação de desempenho realizada comprova os ganhos de tal aplicação paralela. Este artigo está organizado como se segue. A Seção 2 apresenta o referencial teórico relacionado ao presente trabalho. A descrição e a análise do algoritmo alvo são apresentadas na Seção 3. A Seção 4 descreve a análise da aplicação com o objetivo de especificar a paralelização. A Seção 5 discorre sobre a aplicação MPI proposta e a sua implementação paralela. A avaliação experimental da versão paralela é discutida na Seção 6. E, por fim, a Seção 7 apresenta as considerações finais. 2. Referencial teórico As arquiteturas paralelas podem ser organizadas de diversas formas de acordo com a Taxinomia de Flynn [Flynn and Rudd 1996]. Tanenbaum [Tanenbaum 2007], ainda subdivide a classe MIMD, proposta por Flynn, em multiprocessadores e multicomputadores. Os multiprocessadores usam memória global e única, compartilhada entre os processadores, para realizar a comunicação entre os processos. Os multicomputadores possuem memória distribuída e comunicam-se por meio de passagem de mensagens. [Dash and Demsky 2009] e [Yu et al. 2004] conceituam uma categoria híbrida, denominada por memória compartilhada distribuída (DSM), cuja comunicação é realizada por meio do mapeamento das memórias compartilhadas de cada máquina dando a visão de uma única memória para todo o ambiente de execução. Dentro deste contexto, surge uma classe arquitetural que tem chamado atenção dos pesquisadores: o cluster. Um cluster é uma arquitetura de multicomputadores interligados por um meio de comunicação dedicado, normalmente acessado do mundo externo por meio de um servidor de acesso e execução, comportando-se portanto como um sistema único do ponto de vista do usuário. Os cluster estão sendo cada vez mais explorados devido ao seu elevado custo/benefício [Bell and Gray 2002] proporcionado pela facilidade de aproveitamento de máquinas que já não atendem mais as expectativas de uso enquanto isoladas. Todos os aspectos relativos à distribuição de dados, tarefas e comunicação entre os computadores podem ser abstraídos do usuário [Bader and


85

Pennington 2001] por meio de uma plataforma de programação paralela baseada nos modelos de passagem de mensagem, memória compartilhada ou memória compartilhada distribuída. No presente trabalho usamos um cluster de 12 núcleos de processamento e uma plataforma de paralelização baseada em passagem de mensagens MPI. 2.1. Passagem de Mensagens A visão lógica do paradigma de passagem de mensagens consiste em p processos, em que cada um possui o seu endereço exclusivo. Para enviar um dado a outro processo é utilizada uma função que necessita basicamente de parâmetros como o endereço de destino, a mensagem e o tamanho da mensagem. O processo receptor normalmente especifica o buffer e o seu tamanho máximo e aguarda a mensagem do endereço remetente. Este modelo de programação pode ter uma comunicação síncrona e assíncrona, um grupo de comunicação e outras funções agregadas [Pacheco 1997]. A maioria dos programas escritos sob o paradigma de passagem de mensagens usam a abordagem Single Program Multiple Data (SPMD). Em programas SPMD o código executado por diferentes processos é idêntico, exceto por um pequeno número de processos (ex.: por um processo raiz ou mestre) que realizam a distribuição das tarefas a serem executadas nos nós de processamento [Krishnamurthy and Yelick 1995]. O desempenho do modelo de passagem de mensagem pode ser medido pelo tempo ou tráfego de dados e são afetados pelo o número de vezes que uma mensagem precisa ser enviada ou recebida e também pelo tamanho da mensagem. Além disso, devem ser considerados a banda de rede agregada, o volume de concorrência, a segurança, a escalabilidade e o gerenciamento do tráfego de mensagens, sendo fatores que influenciam no tempo de execução da aplicação.

2.2. MPI Um dos principais recursos utilizados na programação de uma aplicação paralela com base no modelo de passagem de mensagens é o Message Passing Interface (MPI) composto por uma biblioteca que permite desenvolver programas paralelos, portáveis e escaláveis na linguagem C/C++ ou Fortran [Lusk 2001]. O padrão MPI foi definido por um grupo de fabricantes de computadores paralelos, cientistas da computação e desenvolvedores de aplicações com objetivo de desenvolver um padrão atrativo tanto aos clientes quanto programadores [Graham et al. 2008]. O MPI oferece aproximadamente 125 rotinas para a passagem e gerenciamento de mensagens. Entre elas, as rotinas MPI_Send e MPI_Recv são os principais comandos empregados no desenvolvimento de aplicações MPI. Pacheco [Pacheco 1997] apresenta uma breve introdução sobre o paradigma de passagem de mensagens e uma aplicação prática que faz uso desta biblioteca. Jaquie [Jaquie et al. 1999] e CENAPAD-NE [CENAPAD-NE 1998] destacam a eficiência, facilidade, transparência, segurança e a escalabilidade que o padrão MPI oferece.

3. Aplicação Alvo: Processsamento de Imagens e o Índice de Fragmentação Os métodos de filtragem permitem que determinadas características de uma determinada imagem sejam visualizadas de uma forma melhor, transformando-a em uma forma adequada à aplicação [Pedrini and Schwartz 2008]. Tais métodos estão estruturados em dois domínios: espacial e de frequência. O domínio espacial está relacionado à influência da vizinhança de um pixel sobre ele.


86

No domínio espacial, um ponto p(x,y) depende do nível de cinza original do próprio ponto e de seus pixels vizinhos. A convolução é uma técnica que atua sobre o domínio espacial através de matrizes denominadas de janelas ou máscaras. Esta técnica pode fazer uso de diferentes algoritmos: soma ponderada dos pontos vizinhos, mediana dos pontos, número de vizinhos distintos, entre outros. A cada elemento da janela está associado um valor numérico denominado de coeficiente. A aplicação da janela com centro na coordenada (a,b), sendo a uma linha e b uma coluna, consiste na substituição do valor do pixel central por um novo valor que depende de operações que envolvem o coeficiente dos pixels vizinhos. Em filtragens de imagens digitais é possível aplicar os filtros em janelas de quaisquer dimensões. Porém, alguns programas definem um tamanho máximo das janelas devido a limitações computacionais [Crosta 1992]. [Turner 1989] apresenta o índice de fragmentação para medir o grau de variabilidade da paisagem e revelar as possíveis influências da atividade humana sobre a mesma. O índice fragmentação pode ser adotado como uma medida local de textura, com valores no domínio entre zero e um, sendo calculado para cada ponto da imagem por meio da aplicação de uma convolução específica na região vizinha do ponto. Se todos os pixels posicionados em relação à janela de convolução forem de classes diferentes, seu valor será 1, indicando máxima variabilidade na região em análise. Em contrapartida, se todos os pixels da imagem forem iguais, tem-se o coeficiente de variabilidade 0 [Galo and Novo 1998]. Em termos de reconhecimento de padrões, o índice de fragmentação multidimensional (IFM) considera, além da vizinhança do pixel em cada banda, seu contexto nas múltiplas bandas para classificá-lo [Miller et al. 1995]. Para este trabalho, foi adotada a versão sequencial do algoritmo de IFM implementada pelo Grupo de Pesquisas em Geodésia da Universidade Estadual Paulista (UNESP). Esta versão foi utilizada como referência e serviu de código base para a criação da versão paralela. O algoritmo implementado pelo Grupo da UNESP considera imagens com qualquer número de bandas e, após o processamento, gera uma única banda de saída. Para cada posição da janela, os pixels da imagem são mapeados para classes e indexados numericamente em intervalos a que cada pixel pertence. O tamanho desses intervalos é determinado a partir da divisão do número total de níveis de cinza da imagem pelo número de elementos da janela (n). Após o mapeamento dos pixels da janela para as classes de intervalos, realiza-se a contagem do número de pixels distintos (c). O IFM (F) é calculado pela Equação 1:

Equação 1. Índice de Fragmentação

A Figura 1 apresenta um exemplo de imagem em escala de cinza de 8 bits com janela 3x3. O primeiro procedimento de processamento atua em cada posição da janela que possui apenas um valor que representa o número digital de brilho do pixel. Os valores de brilho são mapeados em classes de intervalos a partir de uma tabela. A atribuição do novo valor de brilho para o pixel central depende do número de valores presentes na janela em cada iteração. Assim, pela Equação 1, tem-se o índice de fragmentação, o qual é multiplicado ao final do processamento do pixel associado por 255, para converter os índices em tons de cinza e assim permitir sua visualização como uma imagem.


87

Figura 1. Exemplo de uma iteração do processo de co nvolução

O tempo de execução do Algoritmo IFM cresce com o aumento dos seguintes atributos: dimensão da imagem, o número de bandas de cada imagem e o tamanho da janela (máscara). A dimensão da imagem e o número de bandas alteram linearmente o tempo de execução desde que os demais parâmetros sejam os mesmos. O terceiro parâmetro influencia exponencialmente o tempo de execução.

3.1. Descrição do Algoritmo Sequencial Para facilitar o entendimento geral do programa e do método de paralelização proposto, o Algoritmo 1 apresenta a versão sequencial utilizada. 01 CarregarImagem(); 02 AtribuirJanelaDeVizinhos(); 03 DividirIntervalo(); 04 RealizarConvolucao(); 05 CriarBufferParaNovaImagem(); 06 para cada linha L, faça: 07 para cada coluna C, faça: 08 se lin < totalLinhas então 09 se col < totalColunhas então 10 DefinirValoresDoPixel(); 11 se col > 1 então 12 DeslocarMascara(); 13 EncontrarIntervalo(); 14 RetornarNovoPixelCentral(); 15 DefinirValorMapeado(); 16 ArmazenaValorMapeado(); 17 GravarImagem();

Algoritmo 1. Versão sequencial do programa


88

Primeiramente, são inicializadas as variáveis de acordo com os parâmetros passados pelo usuário. Nesta etapa, são fornecidos como parâmetros a máscara e o arquivo da imagem de entrada. Após ler os dados de inicialização, é realizada a alocação das estruturas matriciais de entrada e saída de acordo com a dimensão da imagem de entrada. Posteriormente, os intervalos são divididos de acordo com o tamanho da máscara para a representação em tons de cinza. Este algoritmo é marcado por funções que contém muito laços de repetição aninhados. A sub-rotina de início da convolução realiza LxC chamadas ao procedimento de cálculo do índice do pixel central. Esta função percorre cada pixel da matriz para classificar o intervalo de cada elemento e, também, realiza a contagem de números distintos contidos na janela. As iterações dos laços de repetição aninhados dependem diretamente dos parâmetros iniciais que definem quantas iterações serão realizadas. Para cada cálculo do pixel central realizado na rotina de convolução é calculado o valor do pixel central da janela. No final do processo de convolução em todos os pixels da imagem é gravada uma imagem de saída.

4. Análise para a Paralelização do Algoritmo O primeiro passo para paralelizar o Algoritmo IFM foi analisar o problema em busca de segmentos particionáveis. Após analisar e compreender as suas peculiaridades observou-se que o cálculo de cada pixel central da imagem de saída pode ser realizado de maneira independente do cálculo de pixels vizinhos. Na versão sequencial, para cada janela é processado um pixel central de acordo os parâmetros iniciais do algoritmo. Para o cálculo de cada pixel central é gerada uma janela a partir da imagem de entrada em que são computados os intervalos distintos entre cada pixel. Este cálculo independe de qualquer outro resultado previamente calculado, havendo a independência de dados. Então, é possível prosseguir o cálculo dos próximos pixels sem a necessidade de aguardar outras instruções serem executadas. Deste modo, distribuir segmentos da imagem de entrada entre os elementos de processamento do cluster é uma maneira coerente para se particionar o domínio da imagem. Assim, cada nó do cluster será responsável por calcular cada pixel central do segmento de imagem recebida e, posteriormente, devolver o segmento de saída calculado à uma máquina mestre. Esta visão de particionamento independe do número de nós existentes, pois o cálculo da divisão da imagem é dado pela razão entre a altura da imagem e número de nós do cluster. Assim, se temos uma imagem de entrada de dimensão 8460x9530 pixels e um cluster formado por 12 nós de processamento, podemos processar segmento de imagem de 705 x 9530 pixels em cada nó.

5. Aplicação MPI A paralelização foi desenvolvida utilizando o protocolo MPI a partir do algoritmo IFM sequencial. Esta aplicação MPI aplica a convolução sobre todos os pontos da imagem. A aplicação calcula todos os pixels da imagem de saída da mesma maneira que a versão sequencial, porém de forma paralela, usando uma abordagem de computação distribuída mestre-escravo. Nesta aplicação, o nó mestre da aplicação lê a imagem de entrada e todos os parâmetros necessários para o processamento. Em seguida, os dados são particionados de modo proporcional ao número de nós escravos disponíveis. Este particionamento é feito nas linhas da imagem. Por exemplo, supondo que uma imagem de entrada possua a dimensão igual a 12 linhas e 80


89

colunas e um cluster composto por 3 nós escravos, o nó mestre divide as 12 linhas pelos 3 nós, resultando em segmentos de 4 linhas e 80 colunas. Após o particionamento dos dados, os escravos executam o Algoritmo IFM sobre sua porção. Quando os escravos terminam, o nó mestre grava em disco a imagem de saída completa.

6. Análise do Experimento O Laboratório de Computação de Alto Desempenho (LECAD) do Departamento de Informática da Universidade Estadual de Maringá possui um cluster com nós escravos homogêneos onde todos os experimentos deste trabalho foram executados. Este cluster é composto por seis máquinas da Sun Microsystems. Cada máquina possui um processador AMD Opteron 1218 de 2.6Ghz de dois núcleos, 2MB de cache L2, 4 GB de memória RAM, 1TB de armazenamento e rede Ethernet Gigabit. O ambiente de execução dos nós é formado pelo sistema operacional Linux CentOS com kernel 2.6.18; GCC 4.1.2; versão TCP/IP do protocolo HLRC; e pela ferramenta de monitoramento Ganglia [Sacerdoti et AL. 2003]. Toda esta plataforma operacional é gerenciada pela ferramenta ROCKS [Papadopoulous et al. 2003]. Além disso, foi adotada a biblioteca OpenCV 2.1 para a leitura e gravação das imagens [Bradski and Kaehler 2008]. Os experimentos foram executados a partir de três imagens distintas com 8460x9530 de dimensão com uma banda cada. A Versão MPI Básico é centrada basicamente na ideia da divisão da imagem de entrada, distribuição e processamento de cada segmento e agrupamento das partes enviadas por cada nó. A Figura 2 ilustra o speedup obtido. O eixo X define o número de processos; o eixo Y representa o tamanho da máscara; e o eixo Z mostra o speedup alcançado na intersecção entre os eixos X e Y. A plataforma MPI permite a execução de N processos por nó. No caso deste cluster que conta com máquinas de 2 núcleos, foram executadas baterias de testes de 1 a 12 processos. A sequência de escalonamento de processos inicia-se com 1 processo por máquina até se completar 6 processos. A partir da execução de 7 processos, é alocado 1 processo para cada nó completando 6 processos e, daí por diante, é acrescido mais um processo nas primeiras máquinas da lista de computadores de modo a preencher o total de processos.


90

Figura 2. Speedup MPI

Pode se observar que a versão paralela com 1 processo apresenta desempenho inferior à sequencial, independentemente do tamanho da máscara. O tamanho de máscara de 3 pixels mostra-se pouco viável mesmo com o aumento do número de processos. Com o uso de 5 pixels de máscara, o tempo de execução é reduzido de acordo com o número de processos. Assim, observa-se que na situação de 15 pixels de máscara e 12 processos é obtido speedup 6,91. A Figura 3 descreve a eficiência de acordo com o crescimento do número de processos e do tamanho da máscara. O eixo X define o número de processos; o eixo Y caracteriza o tamanho da máscara; e o Z esboça a eficiência alcançada pelo cruzamento entre os dois eixos. A Figura 3 permite observarmos que o índice de eficiência com 6 e 12 processos tem maior queda. Essa redução de desempenho ocorre em função do tempo de comunicação gasto pela sexta máquina escrava cujo dever é executar o sexto e décimo segundo processo. Contudo, essa deficiência torna-se praticamente invisível conforme o percentual computacional cresce de acordo com o tamanho da máscara. Ao analisar a curva do sexto processo, por exemplo, é possível notar que o índice computacional aumenta de acordo com o tamanho da máscara, ocultando assim a parcela de tempo gasta com comunicação.


91

Figura 3. Eficiência MPI

Podemos consolidar que o ganho de desempenho com 3 pixels de máscara é cada vez menor com o aumentar do número de processos. Apesar de mais amena, esta situação é válida para os demais tamanhos de entrada de máscara. Isso se deve diretamente ao tempo de comunicação que se torna significante conforme o crescimento do número de processos. A Figura 4 ilustra o percentual gasto com comunicação enquanto a Figura 5 mostra o tempo gasto com computação.

Figura 4. Percentual de Comunicação da aplicação


92

Figura 5. Percentual de Computação da aplicação

Se observarmos o impacto da comunicação nas execuções com 3 pixels de máscara, a parcela de comunicação do ambiente com 12 processos atinge aproximadamente 27% do tempo total do experimento. E, com 15 pixels de máscara nota-se que a parcela de computação torna-se mais significativa diante do número de instruções geradas gastando aproximadamente 98% com computação.

7. Conclusões Os experimentos computacionais podem ser uma ferramenta de fundamental importância para que pesquisas obtenham a acurácia dos resultados próxima aos reais. Além disso, com um baixo custo, permitem a execução de experimentos que, na prática, envolvem riscos de magnitude inesperados sem o risco de quaisquer danos materiais. A computação paralela é indiscutivelmente uma solução atrativa para aumentar o desempenho de aplicações com investimento relativamente pequeno aos supercomputadores. Neste panorama, os clusters podem apresentar um desempenho igual ou até mesmo superior aos supercomputadores, sendo uma alternativa para instituições que necessitam de poder computacional, mas não dispõem de recursos financeiros para adquirir um supercomputador. Entretanto, ainda existe uma carência quanto a proposição e utilização de metodologias de paralelização em aplicações complexas do mundo real. A aplicação alvo apresentada neste trabalho, necessita de muito tempo computacional dependendo dos parâmetros de entrada utilizados, impedindo, muitas vezes, que seja implementada como um módulo de sistemas que fazem o uso de processamento de imagens digitais. A paralelização desta aplicação permite que parâmetros que, anteriormente, eram inviáveis de serem experimentados, possam ser executados de maneira a contribuir com as pesquisas de áreas relacionadas a este tipo de processamento de imagens digitais. A aplicação paralela permite executar o algoritmo em um cluster reduzindo o esforço computacional. A implementação proposta reduziu o tempo de execução em 30,1% e 85,5% utilizando três e quinze pixels de máscara, respectivamente. O uso de


93

três pixels de máscara torna a parcela de comunicação responsável por 27% do tempo total de execução. Este percentual é reduzido para 2% quando se utiliza quinze pixels de máscara. Assim, com os dados obtidos podemos comprovar que a aplicação proposta apresenta desempenho e eficiência satisfatória para quaisquer tamanhos de máscaras. Certamente, os benefícios aqui apresentados poderão ser maiores se considerarmos uma convolução mais demorada. Por outro lado, algumas políticas de estimativas mais eficientes em termos de acerto poderão consumir tempo considerável a ponto de reduzir os ganhos da paralelização. Estas questões serão analisadas em trabalhos futuros. Para trabalhos futuros sugerimos a realização de experimentos em cima de imagens de multibandas para se analisar a relação computação/comunicação entre os dois tipos de imagens. Além disso, a proposição de políticas de seleção mais elaboradas, bem como o uso desta implementação em imagens de multibandas são desafios ainda a serem vencidos.

• Referências Bader, D. A. and Pennington, R. (2001). Applications. International Journal of High

Performance Computing Applied, 15(2): 181-185. Bell, G. and Gray, J. (2002). What’s next in high-performance computing? ACM

Communications, 45(2):91-95. Bradski, G. and Kaehler, A. (2008). Learning OpenCV: Computer vision with the

OpenCV library. O’Really Media, USA, 1th edition. Carvalho, L. (1995). Paralelização de um programa de cálculo em mecânica de

fluidos computacional. PhD thesis, Universidade do Porto, Portugal. CENAPAD-NE (1998). Programação Paralela com MPI: Manual do Curso. Centro

Nacional de Processamento de Alto Desempenho do Nordeste. Crosta, A. P. (1992). Processamento Digital de Imagens de Sensoriamento Remoto.

Technical Report, IG/Unicamp. Dash, A. and Desmky, B. (2009). Software Transactional Distributed Shared

Memory. In Proceedings of the Symposium on Principles and Practice of Parallel Programming, pages 297-288, New York/USA.

Flynn, M. J. and Rudd, K. W. (1996). Parallel Architectures. ACM Computing Survey, 28(1):67-70.

Galo, M. and Novo, E. (1998). Índice de Paisagem Aplicado a Análise do Parque Estadual Morro do Diabo e Entorno. In Anais do IX Simpósio Brasileiro de Sensoriamento Remoto, pages 17-28, Santos. INPE/SELPER.

Gomes, J. L. (2008). Paralelização de algoritmo de simulação de Monte Carlo para adsorção em superfícies heterogêneas bidimensionais. Master’s thesis, Universidade Estadual de Maringá.

Gonzalez, R. and Woods, R. (2000). Processamento de Imagens Digitais. Edgard Blucher, São Paulo, 1th edition.

Graham, R., Woodall, T. and Squyres, J. (2008). OpenMPI: A flexible high performance MPI. Lecture Notes in Computer Science, 28(1):67-80.

Hallak, R., Pereira Filho, A., Gandú, A. and da Silva, F. (2004). Uso do modelo de mesoescala ARPS para simulações de tempestades severas em altíssima resolução espacial na Bacia do Alto Tietê (SP). In Anais do XIII Congresso Brasileiro de Meteorologia, Fortaleza, Ceará, volume 29.

Ivanov, L. (2006). A Modern Course on Parallel and Distributed Processing. Journal of Computing Sciences in Colleges, 21(6):29-38.


94

Jaquie, K., Santana, M., Masiero, P., Penteado, R. and Santana, M. (1999). Extensão da Ferramenta de Apoio à Programação Paralela (FAPP) para Ambientes Paralelos Virtuais.

Krishnamurthy, A. and Yelick, K. (1995). Optimizing Parallel SPMD Programs. In Proceedings of the Conference on Languages and Compilers for Parallel Computing, pages 331-345, USA.

Lusk, E. (2001). Programming with MPI on Clusters. In Proceedings of the International Conference on Cluster Computing, pages 360-362, USA.

Miller, D., Kaminsky, E. and Rana, S. (1995) Neural Network Classification on Remote Sensing Data. Computers and Geosciences, 21(3):377-386.

Pacheco, P. (1997). Parallel Programming with MPI. Morgan Kaufmann. Papadopoulos, P., Katz, M. and Bruno, G. (2003). NPACI Rocks: Tools and

Techniques for Easily Deplying Manageable Linux Clusters. Concurrency and Computation: Practice and Experience, 15(7):707-725.

Pedrini, H. and Schwartz, W. (2008). Análise de Imagens Digitais: Princípios, Algoritmos e Aplicações. Thomson Learning, São Paulo, 1th edition.

Piffer, M. (2009). Um Estudo Experimental de Coescalonamento em um Ambiente de Previsão Meteorológica, PhD thesis, Universidade Federal de Santa Catarina.

Sacerdoti, F., Katz, M., Massie, M. and Culler, D. (2003). Wide Area Cluster Monitoring with Ganglia. In Proceedings of the IEEE Cluster, pages 117-123, USA.

Tanenbaum, A. S. (2007). Organização Estruturada de Computadores. LTC, Rio de Janeiro, 5th edition.

Turner, M. (1989). Landscape Ecology: The Effect of Pattern on Process. Annual Review of Ecology and Systematics, 20(1):171-197.

Vasconcelos, P. Paralelização de Algoritmos de Álgebra Linear Numérica com Aplicação na Mecânica de Fluidos Computacional. PhD thesis, Faculdade de Engenharia da Universidade do Porto, 1998.

Yu, B. H., Huang, Z., Cranefield, S. and Purvis, M. (2004). Homeless and Home-based Lazy Release Consistecy Protocols on Distributed Shared Memory. In Proceedings of the Conference on Computer Science, pages 117-123, Australasian.


95

Proposta de uma Ontologia no Domínio de Doenças Negligenciadas

Aldo Sergio de Oliveira, Maria Madalena Dias, Heloise Manica, Sandra Xavier de Macedo

Departamento de Informática – Programa de Pós-Graduação em Ciência da Computação - Universidade Estadual de Maringá (UEM)

Maringá – Paraná – Brasil

[email protected] , [email protected] , [email protected] , [email protected]

Abstract. This paper aims to present the proposal of an ontology for the domain of Neglected Diseases, considered as a challenge for public management today. To facilitate the understanding of ontology, we present concepts and advantages of its use, as well as languages and tools that exist to support the creation of ontology and methods used in its development. The proposal appears to be feasible and could be used by health professionals for a diagnosis quicker and more accurate, contributing to the improvement of the patient health and the welfare of the population it covers.

Resumo. O objetivo deste artigo é apresentar a proposta de uma ontologia para o domínio das Doenças Negligenciadas, consideradas como um desafio para a gestão pública atual. Para possibilitar o entendimento sobre ontologia, são apresentados conceitos e vantagens da sua utilização, bem como linguagens e ferramentas existentes para suporte à criação de ontologia e métodos usados no seu desenvolvimento. A proposta mostra-se viável e poderá ser utilizada por profissionais da saúde para um diagnóstico mais rápido e preciso, contribuindo para a melhora do paciente e do bem estar da população a que se destina.

1. Introdução Um dos grandes desafios da administração pública mundial na atualidade é a saúde pública. Segundo Morel (2006), a Organização Mundial da Saúde (OMS) e os Médicos Sem Fronteiras, propuseram a classificação das doenças como sendo globais (ocorrem em todo o mundo), negligenciadas (mais prevalentes nos países em desenvolvimento) e mais negligenciadas (exclusivas dos países em desenvolvimento). As doenças negligenciadas são doenças que afetam milhões de pessoas em todo o mundo, porém, elas não dispõem de tratamentos eficazes ou adequados. São doenças infecciosas que afetam principalmente pessoas pobres, e que, segundo Carvalheiro (2008), no Brasil limita-se a um conjunto de sete doenças: dengue, tuberculose, esquistossomose, leishmaniose, hanseníase, malária, e doença de Chagas. A população brasileira é muito atingida por essas doenças, pelo fato de ser um país tropical e possuir deficiências sanitárias, sendo o saneamento básico precário, longe de ser adequado (a maioria da população não conta, sequer, com redes para coleta de esgotos e os resíduos gerados são lançados diretamente nos rios, sem nenhum tipo de tratamento). Soma-se a esse quadro a demora e dúvida quanto ao diagnóstico e tratamento de doenças a pacientes carentes que, na maior parte dos


96

casos, são realizados em unidades básicas de saúde por médicos recém formados e que contam com poucos recursos no auxílio ao diagnóstico rápido e preciso. Os profissionais da área médica estão a todo momento processando um grande volume de informações. A Engenharia do Conhecimento vai de encontro à necessidade de gerir o conhecimento, por meio de metodologias e ferramentas, tornando-se fundamental visto que alguns recursos disponíveis, utilizados como fontes de pesquisas para acesso ao conhecimento (livros, periódicos, conferências, entre outros) já não são adequados às necessidades atuais dos profissionais da saúde. Isto ocorre devido a alguns fatores elencados por Arruda (2000), tais como:

• O grande crescimento em ciência e tecnologia e novos conhecimentos surgindo, tornando os velhos conhecimentos obsoletos;

• A rapidez com que as técnicas de representação do conhecimento vão ficando ultrapassadas;

• O aumento da especialização que torna muito difícil o intercâmbio e a comunicação da informação entre disciplinas;

• O grande número de trabalhos científicos e o grande número de periódicos técnico-científicos que existem hoje;

O curto espaço de nos processos (computadores ou pessoas) torna-se mais efetiva ao serem reduzidas diferenças conceituais ou terminológicas (Almeida, 2003).

• Este artigo apresenta o desenvolvimento de uma ontologia para a área da saúde pública, em específico das doenças negligenciadas, favorecendo o compartilhamento e reuso do conhecimento de forma a contribuir com o profissional da área para diagnosticar doenças e tratá-las de maneira rápida e eficaz. O restante deste artigo é dividido em cinco seções. Na Seção 2 é apresentado o conceito de ontologia e discutidas questões sobre o seu uso no domínio da saúde pública; na Seção 3 são descritas as etapas seguidas para o desenvolvimento da ontologia proposta e, também, citadas a linguagem e a ferramenta utilizadas; na Seção 4 são apresentados os resultados preliminares da ontologia que está sendo construída; e, finalmente, na Seção 5 são apresentadas as considerações finais deste artigo tempo que decorre entre a pesquisa e a aplicação, que exige uma informação mais precisa e imediata.

Da mesma maneira que o conhecimento é gerado de forma rápida, também torna-se obsoleto mais rapidamente, comprometendo a qualificação do profissional da saúde. Muitos serviços de saúde costumam desconhecer sua base de conhecimento adquirida e o capital de conhecimento sempre é perdido quando profissionais saem do serviço, devido à rotatividade, atrito, documentação inapropriada e medidas de economia, comumente características de sistemas públicos de saúde. As ontologias vêm sendo utilizadas para representar conhecimento a respeito de um determinado domínio. Segundo Linhalis (2007), a ontologia “pretende estruturar conhecimento consensual, de uma maneira formal, que possa ser compartilhado e reutilizado por agentes (aplicações e grupos de pessoas)”. As ontologias se apresentam como uma forma de representar o conhecimento, possibilitando uma compreensão comum e compartilhada de um domínio, no qual ocorre interação entre pessoas e sistemas. Elas desempenham um papel importante no intercâmbio de informações ao proporcionar estruturação semântica às fontes de dados. Desta forma, a comunicação entre os agentes envolvidos.


97

2. Ontologia e Saúde Pública Ontologia não é um termo novo. Ele nasceu na filosofia e tem sido cada vez mais utilizado em diversas áreas do conhecimento. O conceito comumente utilizado é o de Gruber (1996) que a descreve como sendo “uma especificação formal de uma conceitualização compartilhada”, ou seja, a ontologia deve ser formal no sentido de ser processável por máquinas e compartilhada no sentido que é utilizada por mais de um indivíduo e aceito por um grupo de pessoas. Conforme Almeida (2003) a existência de ontologias pode ser um fator determinante na organização e recuperação da informação em um domínio. Além disso, apresentam diversas vantagens, descritas por Duarte e Falbo (2000):

o Ajudam as pessoas a compreender melhor uma determinada área de conhecimento;

o Ajudam as pessoas a atingir um consenso no seu entendimento sobre uma determinada área de conhecimento. Algumas vantagens proporcionadas por uma ontologia em saúde, tais como:

definição de vocabulário comum; padronização no desenvolvimento de sistemas; possibilidade de desenvolvimento de software mais inteligente; comunicação entre sistemas (hospitais, clínicas, etc.) e reuso do conhecimento em novas pesquisas (Manica et al., 2008). As ontologias na área da saúde têm se propagado. No intuito de auxiliar na troca de informações clínicas entre sistemas e o desenvolvimento de novas aplicações como prontuário eletrônico do paciente, segunda opinião diagnóstica, sistemas de suporte a decisão diagnóstica, entre outros. Podem ser destacados alguns exemplos:

• FMA (Foundational Model of Anatomy): ontologia desenvolvida por Rosse e Menjino Jr. (2003) no domínio dos conceitos e relações que dizem respeito à organização estrutural do corpo humano, à anatomia;

• HF Ontology: ontologia guiada por uma base de conhecimentos que auxilia na gestão dos pacientes com insuficiência cardíaca;

• Canestraro et al. (2006) apresentam uma proposta de um sistema de apoio à decisão (SAD) para auxiliar os profissionais de saúde com atividades nas unidades de dor torácica;

• Uma ontologia de alimentos para o controle de diabetes é proposta em Cantais et al. (2005).

Dentre os mais variados domínios na área da saúde representados em ontologias, faz-se necessário e emergente pensar em problemas de saúde pública e em especial as doenças negligenciadas, cujos desafios são grandes em todas as esferas públicas. As doenças negligenciadas não só predominam em condições de pobreza, mas também contribuem para a sustentação de desigualdade à medida que representam forte entrave ao desenvolvimento dos países. As regiões onde as doenças negligenciadas têm maior ocorrência são de difícil acesso, com escassez ou ausência de acesso à rede de serviços e aos programas de saúde.

De acordo com Penna (2003), a reforma sanitária brasileira em um primeiro momento priorizou a ampliação da cobertura dos serviços básicos de saúde, de modo a atender o princípio da universalidade de acesso à saúde, e não ações de controle de doenças específicas, principalmente aquelas ações que não tivessem efeito sinérgico para a atenção básica. A discussão sobre o controle vetorial sempre foi totalmente periférica porque essa atividade não se realiza na rede de atenção à saúde, arcabouço


98

principal do SUS (Sistema Único de Saúde). Sendo assim, a conjuntura das doenças negligenciadas reflete, portanto, a decisão política de não priorizar o controle vetorial no país, cujo custo (realizado por meio da estratégia tradicional) é muito alto, resultando em um custo benefício baixo comparado à expansão da cobertura das ações básicas de saúde.

Diante deste cenário, propõe-se a elaboração de uma ontologia para área da saúde pública no domínio das doenças negligenciadas. O objetivo é contribuir na disseminação e compartilhamento das informações no ambiente organizacional, auxiliando todos os profissionais que estejam direta ou indiretamente ligados ao caso paciente para que se consiga um diagnóstico mais rápido e preciso e, consequentemente, a melhora de sua saúde.

3. Desenvolvimento da Ontologia

Neste trabalho utilizou-se a ferramenta Protegé (Protégé, 2010), a linguagem OWL- Web Ontology Language (com sublinguagem OWL-DL) e Método 101 (Noy, McGuinness, 2001). A Protégé foi desenvolvida pela Universidade de Stanford usando a linguagem Java com código aberto e arquitetura extensível e dá suporte ao desenvolvimento, visualização e manipulação de ontologias em diferentes formatos.

A linguagem OWL (Horridge, 2003) é utilizada por aplicações que necessitam processar o conteúdo da informação ao invés de apenas disponibilizá-lo. Ela está dividida em três sublinguagens, de acordo com sua expressividade, sendo elas: a OWL Lite, a OWL DL e a OWL Full. A OWL-DL baseia-se na lógica descritiva, um fragmento de Lógica de Primeira Ordem passível de raciocínio automático, sendo possível, assim, computar automaticamente a hierarquia de classes e verificar inconsistências na ontologia.

O Método 101 (Noy and McGuinness, 2001) apresenta um roteiro com tópicos a serem observados na construção de uma ontologia. O método foi escolhido devido à simplicidade de suas etapas de desenvolvimento e facilidade em seu entendimento. Conforme Noy e McGuinness (2001) destacam, não há apenas uma forma ou metodologia correta para o desenvolvimento de ontologias. Os passos para desenvolvimento da ontologia aqui proposta foram definidos como segue. Passo 1 - Determinar o domínio e escopo da ontologia Uma das maneiras de determinar o alcance da ontologia é esboçar uma lista de perguntas que uma ontologia deve ser capaz de responder. Adicionalmente, para esta etapa foram consideradas algumas questões: 1) qual é o domínio que a ontologia cobrirá? 2) qual será o uso da ontologia? 3) para que tipos de perguntas a ontologia deverá fornecer respostas? 4) Quem vai utilizar e manter a ontologia?

A ontologia em desenvolvimento abrange o domínio das doenças negligenciadas, cujo uso será feito por profissionais da saúde, em especial, os médicos. Trará como respostas qual a possível doença do paciente, uma vez que os sintomas foram informados por ele ou detectados pelo profissional. A ontologia poderá ser utilizada, melhorada ou mantida por todos os profissionais e especialistas da área da saúde.

As respostas a estas questões podem mudar durante o processo de construção da ontologia, mas em determinado momento podem ajudar a limitar o âmbito de aplicação do modelo. Passo 2 - Considerar o reuso de ontologias existentes.


99

O reuso de ontologias pode ser um requisito se o novo sistema interage com outras aplicações que já têm ontologias ou vocabulários controlados. Muitas ontologias estão disponíveis em formato eletrônico, podendo ser importados para uma ontologia ainda em desenvolvimento. Após avaliar várias ontologias, optou-se por criar uma nova ontologia. Passo 3 - Enumerar os termos importantes da ontologia. Os termos sobre os quais podem ser feitas declarações devem ser listados, junto com suas propriedades. Em um primeiro momento, é importante ter uma lista de termos, sem se preocupar com a sobreposição entre os conceitos que eles representam, as relações entre os termos e as propriedades que eles podem ter. A ontologia terá como termos: paciente, doença negligenciada, dengue, tuberculose, esquistossomose, leishmaniose, hanseníase, malária, doença de Chagas, sintomas, tratamento, agente etiológico, vetor, reservatório, período de transmissibilidade, imunidade, período de incubação, região. Exemplos de propriedades do tipo objetos (datatypes) podem ser visualizados na Figura 1. Passo 4 - Definir classes e a hierarquia de classes. Há vários enfoques no desenvolvimento de hierarquia:

o Um processo de desenvolvimento top-down começa com a definição dos conceitos mais gerais no domínio e, posteriormente, é feita a especialização dos conceitos;

o Um processo de desenvolvimento bottom-up começa com a definição das classes mais específicas, com subsequente agrupamento destas classes em conceitos mais gerais;

• Um processo de desenvolvimento é formado pela combinação dos dois enfoques anteriores. São definidos os conceitos que mais se sobressaem primeiro e depois esses conceitos são generalizados e especializados adequadamente.

Algumas das classes da ontologia e suas hierarquias podem ser visualizadas na Figura 2. Para a etapa de definição das classes foram consultados especialistas nas área bem como manuais técnicos na área de doenças negligenciadas.


100

Figura 1. Propriedades da ontologia

Figura 2. Classes e Hierarquia de Classes

Passo 5 - Definir as propriedades das classes.


101

As classes por si só não fornecem informações suficientes para responder às questões descritas no Passo 1. Uma vez definidas algumas das classes, necessita-se descrever a estrutura interna dos conceitos. Os termos que sobraram da lista de termos do Passo 3 provavelmente são propriedades. Para cada propriedade na lista, são determinadas quais classes ela descreve. Todas as subclasses de uma classe herdam as propriedades desta classe.

Na Figura 3, pode-se observar a definição das propriedades da subclasse “Clássico”, isto é, as propriedades referentes ao subtipo de dengue clássico.

Figura 3. Propriedade da Classe

Passo 6 - Definir os valores das propriedades. Propriedades podem descrever o tipo de valor, valores permitidos, o número de valores (cardinalidade). Uma propriedade pode ter como tipo um valor que é uma instância, cujo escopo é uma classe específica.

Aqui são descritas diversas facetas comuns, tais como; cardinalidade, que define quantos valores uma propriedade pode ter; tipo de valor, que descreve quais os tipos de valores pode preencher a propriedade, podendo ser string (é o tipo mais simples que é usado para propriedades como nome: o valor é um string simples); número (descreve propriedades com valores numéricos). Um exemplo de valores da propriedade “anorexia” é ilustrado na Figura 4.


102

Figura 4. Valores da Propriedade

Passo 7 - Criar instâncias. O último passo é criar instâncias individuais das classes na hierarquia. Para isto é necessário: escolher uma classe, criar uma instância dessa classe e preencher os valores das propriedades. A Figura 5 ilustra a criação da instancia “Dengue Clássico”.

4. Resultados Preliminares Com o apoio de especialistas, consulta a livros, periódicos e web sites especializados no domínio e com a utilização da ferramenta, linguagem e metodologia escolhidas, foi possível criar a ontologia proposta. Os tutoriais disponíveis para criação de ontologias OWL com utilização da ferramenta Protégé foram essenciais para o melhor entendimento e desenvolvimento da ontologia. Ainda que em desenvolvimento, a ontologia já consegue responder a algumas das perguntas descritas no passo 1, por exemplo, dado os sintomas, a ontologia responde quais as possíveis doenças. A Figura 6 ilustra a resposta de uma consulta dados os seguintes sintomas: anorexia, artralgia, astenia, cefaléia, dor abnominal e dor retro orbital. A resposta é apresentada no quadro à direita (search results) é “Dengue Clássico”.


103

Figure 5. Criação de Instância

Figure 6. Resposta da ontologia perante o problema apresentado


104

5. Considerações Finais Diante de um problema amplo e emergente, a ontologia proposta apresenta-se como uma ferramenta viável no auxilio e diagnóstico das doenças negligenciadas e pode tornar-se fonte de consulta, fornecendo assistência aos profissionais de saúde que atendem a população a que se destina. É evidente que não é a solução para as dificuldades da saúde pública, porém, apresenta-se como um recurso de baixo custo e benefício rápido. A ontologia ainda não está completa, necessitando, assim, que sejam incluídas outras propriedades e classes para que possa ter condições de responder às principais questões comumente levantadas por médicos e demais profissionais da saúde no domínio de doenças negligenciadas e, também, para que possa receber melhorias e ser reutilizada futuramente para outras doenças, sendo o reuso um dos objetivos da ontologia proposta. O uso de uma ontologia proporciona a representação do conhecimento de um determinado domínio, considerado um fator imprescindível e valioso que precisa ser disseminado e empregado para o sucesso e a evolução da humanidade.

Referências ALMEIDA, Mauricio B. Roteiro para construção de uma ontologia bibliográfica

através de ferramenta automatizada. Perspectivas em Ciência da Informação Belo Horizonte, v. 8, n. 2, p. 164-179, jul./dez. 2003

ARRUDA, Maria Izabel Moreira. O Laudo Médico-Legal como Fonte de Informação e seu Papel Social. Belém, 2000. Dissertação. (Mestrado Interinstitucional em Ciência da Informação). Universidade Federal do Pará.

CADERNO DE SAÚDE PÚBLICA. Rio de Janeiro. v. 19, n. 1, p. 305-309, jan-fev, 2003. PENNA, Maria Lucia F. Um desafio para a saúde pública brasileira: o controle do dengue.

CARVALHEIRO, José da Rocha. Epidemias em Escala Mundial e no Brasil. Estud. av. v.22 n.64 São Paulo, 2008. Disponível em: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-40142008000300002&lng=pt&nrm=iso. Acessado em 20 de julho de 2010.

DUARTE, K. C. and FALBO, R. A. Uma ontologia de qualidade de software. In Anais do VII Workshop de Qualidade de Software, João Pessoa - Paraíba. Brasil. Outubro de 2000.

GUIA DE VIGILÂNCIA EPIDEMIOLÓGICA / Ministério da Saúde, Secretaria de Vigilância em Saúde, Departamento de Vigilância Epidemiológica. – 7. ed. – Brasília : Ministério da Saúde, 2009.

HORRIDGE, Matthew. A Practical Guide To Building OWL Ontologies Using Protégé 4 and CO-ODE Tools, Manchester, Março de 2003.

LINHALIS, Flávia. Mapeamento Semântico entre UNL e Componentes de Software para Execução de Requisições Imperativas em Linguagem Natural. São Carlos, 2007. Tese (Doutorado em Ciências – Ciência de Computação e Matemática Computacional), Universidade de São Paulo.

MANICA, Heloisa, DANTAS, M. A. R., TODESCO, José Leomar. Ontologia para Compartilhamento e Representação de Conhecimento em Saúde. Diálogos & Saberes, Mandaguari, v. 4, n. 1, p. 151-161, 2008

MOREL, Carlos. Inovação em saúde e doenças negligenciadas. Cadernos de Saúde Pública, v. 22, p.1522-1523, 2006.


105

NOY, Natalia F.; MCGUINNESS, Deborah L. Ontology Development 101: A Guide to Creating Your First Ontology. Stanford University, Stanford, CA.

PROTEGE, Disponível em: <http://protege.stanford.edu/>. Acesso em: ago. 2010.


106

O Impacto da Otimização Inline na Execução de ProgramasJava

Francis Rangel1, Anderson Faustino da Silva1

Departamento de Informática - Universidade Estadual de Maringá (UEM) Av. Colombo, 5790 - Bloco 19 - 87.020-900 - Maringá - PR - Brasil

francis.rangelogmail.com, andersonodin.uem.br

Abstract. Although it is well-known that the inline optimization produces goods results it remains a challenge to develop a good heuristic of its application, so that the performance profit is effective for many applications. The goal of this paper is to make a detailed experimental analysis about how inline works and what are its impacts during java programs execution. The experimental analysis demonstrated that the inline strategy not always reaches the considered goal.

Resumo. Embora seja conhecido que a otimização inline produza benefícios consideráveis é um desafio desenvolver uma boa heurística de sua aplicação, de forma que o ganho de desempenho seja efetivo para diversas classes de programas. O objetivo deste trabalho é realizar uma análise experimental detalhada do funcionamento e do impacto referente a inline, na execução de programas Java. A análise experimental realizada demonstrou que a estratégia de inline nem sempre alcança o objetivo proposto.

1. Introdução

Para melhorar o desempenho de linguagens interpretadas [Scott2008], diversos ambientes de execução utilizam um mecanismo de compilação dinâmica, denominado Just-in-Time Compilation (JIT) [Scott 2008]. Este mecanismo é responsável por gerar código nativo otimizado durante a execução do programa, não sendo mais necessário interpretar novamente algumas porções do programa. Atualmente, a maioria das implementações da máquina virtual Java (JVM) [Meyer and Downing 1997] possuem um compilador JIT em sua arquitetura [MicroSystems 2010, Cierniak et al. 2000, BURKE et al. 1999].

O ambiente de compilação dinâmica além de gerar código nativo, aplica diversas otimizações como o objetivo de melhorar a qualidade do código gerado. No contexto de linguagens orientados a objetos uma otimização que possui um alto potencial é inline [Muchnick 1997]. Isto devido ao fato de programas orientados a objetos possuírem uma grande quantidade de invocações de métodos. Embora seja conhecido que esta otimização seja efetiva, os trabalhos que desenvovolvem ambientes de compilação para Java [Gu et al. 2000, MicroSystems 2010, Cierniak et al. 2000, BURKE et al. 1999] não demonstram o quão esta otimização é efetiva, nem os custos decorrentes de uma má utilização desta.

O objetivo deste trabalho é avaliar o impacto efetivo da otimização inline em programas Java executados pela JVM Sun Microsystems Inc. [MicroSystems 2010], visando entender o funcionamento desta otimização, bem como os motivos que a levam a degradar o desempenho do sistema para alguns programas. Uma análise deste porte é


107

fundamental para possíveis alterações na estratégia de aplicação desta otimização, consequentemente, melhorar o desempenho de sistemas que a utilizam.

O restante deste artigo está organizado da seguinte forma. A Seção 2 descreve a otimização inline. A Seção 3 descreve a heurística utilizada pela JVM da Sun para aplicar inline. A Seção 4 descreve a avaliação experimental realizada para avaliar o impacto da otimização inline em programas Java. E, finalmente, a Seção 5 descreve as considerações finais.

2. Inline

Os compiladores atuais aplicam diversas técnicas de otimização [Muchnick 1997] no código fonte, com o objetivo de gerar um código de boa qualidade. Uma destas técnicas é inline. Esta foi proposta como uma estratégia para eliminar o custo da invocação de métodos (procedimentos), substituindo uma invocação pelo corpo do método invocado.

Estudos de compilação de linguagens orientadas a objetos demostram que inline é uma das mais importantes otimizações aplicadas pelo compilador [Deutsch and Schiffman 1984]. Pois tais programas possuem uma quantidade significativa de métodos.

Existem diversas vantagens em aplicar inline, a saber:

A eliminação do overhead resultante das chamadas à métodos. 0 desempenho obtido por inline fica mais explícito em programas onde apenas uma pequena quantidade de métodos é responsável pela maior parte do custo das chamadas. A aplicação de inline nestes casos reduz significativamente o overhead das chamadas à métodos [Abboy and Peterson 1992].

O aumento da eficiência da cache de dados. Do ponto de vista da cache, inline aumenta a localidade dos dados, eliminando possíveis indireções dos acessos as variáveis [Chen et al. 1991], a medida que aumenta o corpo do método chamador.

O aumento da eficiência da cache de instruções. Depois de aplicar inline, os segmentos de código que antes possivelmente estariam posicionados distantes uns dos outros, agora estão mais próximos, consequentemente reduzindo as chances de ocorrer falhas na cache [Chen et al. 1991].

No entanto, inline não possui apenas vantagens, há também algumas desvantagens, a saber:

A explosão de código. Este crescimento se deve principalmente pelas diversas substituições das chamadas pelos respectivos corpos dos métodos correspondentes. Talvez esta seja a mais comum das desvantagens do uso de inline [Bernstein et al. 1991].

Aumento da pressão por registradores. Após a aplicação de inline a pressão por registradores se torna maior, pois existirão mais temporários em um mesmo escopo [da Silva and Santos Costa 2006]. Portanto, os registradores disponíveis na máquina podem não ser suficientes para comportar esta nova situação, aumentando desta forma a quantidade de spills [Bernstein et al. 1989].


108

Como não é recomendado a aplicação de inline a todas os métodos, a melhor estratégia é utilizar um algoritmo capaz de estimar os ganhos e as percas ao aplicar inline, identificando quais são os melhores candidatos a serem otimizados. O maior esforço em aplicar inline está justamente no desenvolvimento da heurística utilizada pelo algoritmo. Portanto, é preciso definir critérios concretos para determinar quais são as melhores oportunidades para a aplicação de inline. Sendo assim, é possível determinar pelo menos dois critérios básicos para a aplicação de inline. Primeiro, a chamada do método deve ser muito frequente. E segundo, o corpo do método não pode ser muito grande.

3. Inline na JVM da Sun Na JVM da Sun [MicroSystems 2010], o processo de compilação de um determinado método inicia no momento em que seu contador de invocações atinge um limite máximo de invocações. Um método somente será um bom candidato a Mining se o tamanho do código gerado não ultrapassar 8000 bytes. Se o tamanho do código ultrapassar este valor, o método é descartado.

Durante o processo de inline, caso o método candidato a utilizar a otimização possua chamadas a outros métodos, existe um parâmetro que controla o nível em que o compilador pode chegar ao tentar aplicar a otimização também nestes métodos. Por padrão, este parâmetro permite que até nove níveis sejam alcançados, antes que o compilador não procure mais aplicar a otimização em métodos aninhados. Além disto, nem todas as chamadas à métodos serão expandidas pelos seus corpos.

A JVM da Sun utiliza uma classificação de métodos por temperatura que é composta de três níveis: frio, morno e quente. Esta classificação é realizada com base em métricas sobre o perfil do método e tem por objetivo determinar se um método é um bom candidato a ser expandido no corpo de seu chamador. Estas métricas incluem: contagem, benefício, trabalho, tamanho e temperatura.

Contagem é o número de vezes que se espera executar uma determinada chamada. Valores mais altos são considerados melhores para inline, evitando o processo de invocação convencional um grande número de vezes. Benefício é uma estimativa de tempo que será economizado, por execução, aplicando inline a este método. O valor 1 indica que está ocorrendo overhead. Valores altos facilitam a execução da otimização, enquanto valores negativos desabilitam a mesma. Trabalho é uma estimativa de quanto tempo uma chamada convencional, para este método, será necessário. Valores menores também são favoráveis para a otimização, visto que métodos pequenos tem tempo de execução menores e estes são os mais proveitosos para sofrerem inlining.

Tamanho é a quantidade de nós que se espera gerar para este método, no grafo de fluxo de controle. Este valor não considera o inline de chamadas aninhadas a este método. Para avaliar esta métrica são utilizados o código de máquina, seja foi gerado em uma compilação anterior, e o bytecode do método. Valores menores são melhores para inline, pois métodos pequenos reduzem a explosão de código. Temperatura é o resultado da heurística utilizada. Este valor é a base da classificação, com os métodos podendo ser considerados frios, mornos ou quentes. O ideal seria existir apenas dois valores para temperatura: com e sem inline. Como isto não é possível obter, um valor real é alcançado utilizando a expressão Contagem * Beneficio.


109

Caso alguma das verificações realizadas falhe, o método será classificado como frio e não será realizada a cópia de seu corpo no local onde há chamadas para o mesmo. Portanto, métodos muito grandes, pouco utilizados e que estejam aninhados em muitos níveis, não sofrerão a aplicação de inline e serão classificados como frios. Porém, mesmo um método não sofrendo a aplicação imediata da otimização, ele pode ser selecionado e adicionado a uma fila de métodos mornos. Isto ocorre quando a heurística de classificação não considerou um método como bom candidato para aplicar inline, mas seus parâmetros não fazem com que este seja considerado um método frio.

Os métodos que compõem a fila de métodos mornos são os que não possuem um grande benefício, mas que podem aumentar, mesmo que pouco, o desempenho do programa se sofrerem a aplicação de inline. A utilização de elementos dessa fila depende dos métodos anteriormente utilizados para aplicar a otimização. Existe um controle do tamanho máximo do programa após a compilação e aplicação de inlining. A diferença entre o tamanho máximo e o tamanho atual do programa é considerada um espaço disponível para a aplicação de inline em outros métodos.

Caso ainda existam recursos disponíveis para aplicação da otimização e exista um tamanho de código disponível, a fila de métodos mornos é percorrida. Se um método couber no espaço disponível, este é selecionado para sofrer inline. Caso o espaço não seja suficiente, este método é removido da fila e o próximo é verificado. Enquanto ainda há espaço disponível e métodos na fila, este processo continua. Se o espaço disponível for totalmente utilizado, a fila de métodos mornos é descartada.

Após a aplicação de inline, outras otimizaçoes são aplicadas ao código expandido. Como mencionado anteriormente, esta é uma vantagem desta otimização, pois agora as outras otimizaçoes tem um escopo maior para serem aplicadas onde antes havia apenas uma chamada a método.

4. Avaliação Experimental

A avaliação experimental foi realizada em um computador com processador Intel Dual Core T2160 2.1 GHz, 2 GB de memória principal, e utilizando o sistema operacional Ubuntu 8.10, com kernelversao 2.6.27-14 generic. A JVM da Sun utilizada foi a versão 1.6.19.

A Tabela 1 fornece uma breve descrição, a quantidade de classes, a quantidade de métodos e a entrada utilizada de cada programa. Os oito primeiros fazem parte do DaCapo Benchmark [Blackburn et al. 2006], outros cinco programas fazem parte do Java Grande Fórum Benchmark [Bull et al. 2000] e os últimos sete fazem parte do Shootout Benchmark [Brent Fulgham 2010]. Cada conjunto de benchmark possui um foco diferente. Três aspectos da execução são explorados pelos programas: utilização de memória, utilização de processador e operações de entrada e saída. Os programas do DaCapo Benchmark exploram os três aspectos. Já os programas do Java Grande Fórum Benchmark exploram mais o uso do processador e acessos à memória. Por fim, os programas do Shootout Benchmark exploram bastante as operações de entrada e saída.

A análise foi realizada para a JVM com duas configurações. Uma utilizando o compilador Cliente [MicroSystems 2010] e a outra utilizando o compilador Servidor


110

[MicroSystems 2010]. E ambas com ou sem o uso da otimização inline. Além disto, todos os programas foram executados cinco vezes, em todas as configurações. Assim, os dados apresentados correspondem a média entre cinco execuções.

Características Programa

Descrição Classes Métodos Entrada

Antlr Gerador de analisador sintático 675 3368 large Bloat Otimizador de bytecode Java 831 3180 large Chart JFree Chart 1531 6474 large Eclipse Testes na IDE Eclipse 2627 7276 large Jython Interpretador Python 1329 4889 large Luseh Busca Lucene 688 3252 large Pmd Analisador de arquivos Java 1192 3805 large Xalan Transforma XML em HTML 1170 3727 large Euler Resolução de equações de Euler 406 2300 sizeB MolDyn Simulação molecular 441 2433 sizeB MonteCarlo Simulação Monte Carlo 420 2332 sizeB RayTracer Renderização 3D 409 2310 sizeB Search Busca alfa-beta 402 2297 sizeB Binary-trees Gerador de árvores binárias 345 2132 22 Chameneos Simulação de criaturas 366 2219 80000000 Fasta Gerador de sequências de DNA 344 2133 500000 K-nucleotide Atualização de hash 493 2546 484 MB Mandelbrot Gerador bitmap 412 2327 6000 N-body Simulação de corpos 440 2425 100000000 Spectral Calcula da norma espectral 438 2401 10000x10000

Tabela 1. Programas utilizados na avaliação

4.1. Análise de Desempenho

A Figura 1 apresenta o tempo médio de execução de cada programa, com inline ligado e desligado. Em cada sub-figura, as duas primeiras colunas representam a execução do programa utilizando o compilador Cliente, enquanto as duas últimas a execução com o compilador Servidor. A primeira e a terceira coluna representam a otimização inline desligada e as outras duas colunas a otimização ligada. Além disto, cada barra está dividida em três componentes, a saber: tempo gasto em métodos interpretados, tempo gasto em métodos compilados e tempo gasto em outros procedimentos.

4.2. Impacto de Inline no Compilador Cliente

O compilador Cliente obteve um resultado interessante quando a otimização foi ligada. Pode-se verificar que a sua estratégia é muito superior à adotada pelo compilador Servidor. Apenas FASTA apresentou queda de 7,21% no desempenho quando a


111

otimização foi ligada e apenas SEARCH obteve um ganho insignificante de desempenho. Os programas executados utilizando este compilador apresentaram desempenho, em média, 26,25% superior quando a otimização inline foi utilizada.

A variação de ganho de desempenho foi de 0,20% (SEARCH) a 81,39% (CHAMENEOSREDUX). Mesmo entre os piores resultados, o ganho de desempenho com inline é razoável. Portanto, faz muito sentido utilizar esta otimização no compilador Cliente.

Figura 1. Tempo total de execução em segundos dos programas

Os programas que obtiveram os piores resultados são os considerados kernels. Estes programas possuem poucos métodos e geralmente, apenas um método é


112

invocado frequentemente. Portanto, os resultados demonstraram que inline não faz sentido em programas muito pequenos, com pouca quantidade de métodos. Esta otimização atua melhor quando diferentes métodos são invocados frequentemente, pois neste caso o overhead da não utilização de inline seria maior. Além disso, uma maior porção do código é disponibilizada para sofrer a aplicação de outras otimizações. Outro ponto importante a ressaltar é o fato de inline reduzir consideravelmente a chamada de métodos nativos.

Com o objetivo de reduzir o slowdown ocasionado por inlinepara FASTA e SEARCH, a entrada destes programas foi alterada para obter um aumento do tempo de execução. No caso de FASTA, ao invés de uma perda de desempenho de 7,21%, este obte um ganho de 0,42%. Mesmo não sendo um ganho significativo, este ainda é melhor do que uma perda. Contudo, estes resultado somente foi obtido quando o tempo total de execução deste programa atingiu, aproximadamente, uma hora. Já para SEARCH O resultado obtido com o aumento do tempo de execução foi significativo. Este programa passou de um ganho 0,20% para 7,21%. Embora os resultados obtidos pelo compilador Cliente sejam significantes, este últimos resultados demonstram que a estratégia utilizada pela JVM (parametrização estática de inlinè) é vantajosa, em alguns casos, apenas para longos tempos de execução.

4.3. Impacto de Inline no Compilador Servidor

Para o compilador Servidor, a estratégia da aplicação de inline não é tão eficiente quanto a do compilador Cliente. Quando comparado com o tempo de execução do compilador Cliente, o Servidor se mostrou mais rápido, tanto para a otimização ligada quanto desligada. Porém, a redução do tempo de execução com a aplicação de inline é mais significativo no Cliente do que no Servidor.

A variação do desempenho, considerando apenas os programas que obtiveram ganho de desempenho, foi de 0,09% (N-BODY) a 39,73% (RAYTRACER). Esta variação tem um limite superior inferior à variação constatada no compilador Cliente. Além disso, a quantidade de programas que obtiveram um melhor resultado com a otimização ligada foi menor.

Com base nos resultados é possível concluir que o compilador Servidor age melhor durante a execução de programas que despendem um tempo maior de execução. Um dos fatores para que isto ocorra está no fato de que o compilador Servidor tende a adiar, mais que o compilador Cliente, a compilação de métodos. Isto pode ser verificado com base no percentual de compilação de métodos.

A Tabela 2 apresenta informações sobre a requisição e compilação de métodos, feita pelos dois compiladores. Estas informações foram coletadas durante a execução dos programas com a otimização inline ativada. Comparando os dados de um compilador com o outro, nota-se que o Servidor é mais seletivo quanto a compilação de métodos. Estes dados demonstram que este compilador adia mais a decisão de compilar um método, quando comparado ao compilador Cliente.

No caso de um programa possuir um tempo de execução curto e ser executado pelo ambiente justamente com o compilador Servidor, pode ocorrer de seus métodos serem interpretados a maior parte deste tempo, pois este compilador ainda estará reunindo informações para decidir sobre a compilação do método e a possível aplicação de inline. Esta decisão de adiar a compilação e otimização do método pode


113

ocasionar uma perca de desempenho em programas menores. Porém, esta decisão se mostra eficiente quando o programa possui muitos métodos e um longo tempo de execução.

Assim como realizado com o compilador Cliente, o tamanho da entrada dos programas foi aumentada para avaliar os resultados do compilador Servidor para programas com um tempo maior de execução. Contudo, diferentemente dos resultados obtidos pelo compilador Cliente, em alguns casos o degradação do desempenho se agrava.

Surpreendentemente o ganho de desempenho não ocorreu na execução dos programas kernel, utilizando o compilador Servidor. Porém, o problema diminuiu consideravelmente na maior parte dos programas. Por exemplo, FASTA passou de uma perda de

Cliente Servidor Métodos Métodos

Programa

Requisitados Compilados Requisitados Compilados Antlr 18054 497 (2,75%) 8086 335 (4,15%) Bloat 7229 748 (10,35%) 16328 562 (3,44%) Chart 2439 675 (27,68%) 12493 343 (2,75%) Eclipse 15839 3311 (20,90%) 50785 2240 (4,41%) Jython 16402 1170(7,13%) 16934 963 (5,69%) Lusearch 4440 420 (9,46%) 3655 360 (9,85%) Pmd 2876 991 (34,46%) 10393 607 (5,84%) Xalan 4179 1581 (37,83%) 12704 1314 (10,34%) Euler 524 70 (13,36%) 1446 50 (3,46%) MolDyn 155 27 (17,42%) 153 27 (5,88%) MonteCarlo 680 146 (21,47%) 524 146 (21,56%) RayTracer 323 35 (10,84) 394 23 (5,84%) Search 192 24 (12,50%) 1281 11 (0,86%) Binary-trees 107 21 (19,63%) 65 8 (12,31%) Chameneos 145 69 (47,59%) 578 51 (8,82%) Fasta 109 25 (22,94%) 49 3 (6,12%) K-nucleotide 252 64 (25,40%) 348 56 (16,09%) Mandelbrot 49 18 (36,73%) 45 2 (4,44%) N-body 85 18 (21,18%) 61 2 (3,28%) Spectral 245 23 (9,39%) 62 5 (8,06%)

Tabela 2. Histórico de compilação

14,78% para, apenas, 0,28%, para um tempo de execução de aproximadamente uma hora. Embora esta perca seja insignificante, este programa ainda não atingiu o que se espera da otimização. A mesma situação ocorre com o MOLDYN. Este passou de uma perda de 27,79% para 9,68%, para um tempo de execução aproximadamente de cinquenta minutos.

Por outro lado, outros programas obtiveram um resultado positivo, tendo o ganho de desempenho variado de 3,90% a 69,38%. Isto ocorreu para EULER (+3,90%),


114

CHART (+20,84%), LUSEARCH (+30,19%) e ANTLR (+69,38%). Estes que anteriormente não obtiveram um bom desempenho (no caso de ANTLR, inline ocasionava uma perda de 17,31%), foram consideravelmente beneficiados pela aplicação de inline, isto para um tempo de execução superior a uma hora.

No caso do compilador Servidor, os resultados demonstram que um ganho con-siderável de desempenho somente é obtido por programas com longo tempo de execução. Além disto, no compilador Servidor a estratégia de aplicação de inline funciona melhor para programas reais.

4.4. Compilador Cliente x Compilador Servidor

Como mencionado anteriormente, a estratégia do compilador Cliente é superior a do Servidor. Quando a otimização foi ligada, em média, os programas obtiveram um ganho de 26,25%, contra apenas 6,67% para o compilador Servidor. Porém, o compilador Cliente não é o mais vantajoso entre os dois. Este ganho de desempenho não significa que o tempo total de execução do programa será menor. Foram poucos os programas utilizados em que isto ocorreu. Geralmente, o compilador Servidor obtém um desempenho muito superior ao do compilador Cliente, mesmo com o problema da otimização inline ocorrendo.

Com os dados da Tabela 2 é possível traçar um comparativo entre o comportamento dos dois compiladores, que impacta diretamente no desempenho do programa. O compilador Servidor, apesar de receber mais requisições, é muito mais seletivo que o compilador Cliente. Seu percentual de compilação foi de apenas 5,18% das requisições recebidas. Enquanto isso, o compilador Cliente compilou 13,36% das requisições que recebeu. Mesmo compilando um número menor de métodos, o compilador Servidor obtém um tempo total de execução menor que o compilador Cliente. Isto demonstra que os problemas ocasionados por inline são contornados pela aplicação de outras otimizações.

Apenas um programa apresentou um maior percentual de métodos compilados no Servidor. ANTLR saltou de 2,75% para 4,15%. Contudo, seu desempenho no compilador Servidor com inline ligado foi 17,31% pior do que com o inline desligado. Já no compilador Cliente, este programa obteve um ganho de desempenho de 24,03% no seu tempo total de execução, quando inline foi ativado. Isto caracteriza os problemas que podem ocorrer pela agressividade do compilador Servidor e também pela sua má utilização da otimização inline, sendo uma delas a parametrização estática, o que não leva em consideração as características do programa.

4.5. Decisões de Inline

Para compreender o que ocasionou uma perca de desempenho para os programas é necessário analisar os seus perfis. Desta forma, os bytecodes dos programas ANTLR, CHART, LUSEARCH, EULER, MOLDYN, FASTA, N-BODY e SPECTRAL foram analisados para gerar um perfil dos bytecodes utilizados.

Como o padrão de bytecodes dá origem ao código de máquina, no momento em que o método é compilado, programas com um padrão semelhante de bytecodes irão gerar um padrão semelhante de código de máquina. Desta forma, existe a possibilidade de programas com as mesmas características sofrerem o mesmo problema. Um ponto


115

interessante em relação aos bytecodes dos programas que obtiveram uma perda de desempenho é que o seu padrão foi alterado quando utilizado o compilador Servidor.

Os bytecodes mais utilizados nestes programas realizam operações aritméticas, o controle para o carregamento de valores e cálculo. Este último gera um custo de processamento muito grande. Além destas instruções, outro tipo muito utilizado é o de instruções de acesso e gravação de atributos de objetos e invocações de métodos virtuais.

A maior parte das instruções de carregamento e armazenamento de valores é substituída no compilador Servidor para utilizar instruções com o prefixo fast. Este tipo de instrução não foi utilizada pelo compilador Cliente. Com isto, pode-se avaliar que este tipo de instrução de bytecode tem o objetivo de otimizar a execução dos mesmos. Porém, este perfil de programa pode sofrer degradação de desempenho para casos onde a quantidade de métodos é pequena e exista uma grande quantidade de bytecodes utilizados para operações aritméticas.

Estas instruções, quando utilizado inline, fazem com o que o tempo total de execução aumente. Isto pode ocorrer pelo fato de que a cópia de um método para dentro de outro, utilizando este perfil de bytecodes, degrada a geração de código. Isto pode causar um crescimento do código gerando pressão por registradores e misses na cache. Portanto, um programa que gere este perfil de instruções de bytecode está propenso a sofrer destes problemas, quando a otimização inline é ativada.

Utilizando as informações sobre a compilação de métodos nos dois compiladores, juntamente com esta decisão de substituir os bytecodes durante a execução com o compilador Servidor, pode-se concluir que estas não formam uma estratégia consistente para programas pequenos. Porém, esta estratégia tende a melhorar o desempenho da maior parte dos programas quando o tempo de execução é elevado.

4.6. Análise Detalhada

Além de medir o tempo de execução com inline desligado e ligado, durante a análise experimental foram coletadas para alguns programas informações de hardware através da ferramenta Performance Application ProgrammingInterface (PAPI) [Terpstra et al. 2010]. As informações mais importantes quando se trata da otimização inline são: quantidade de instruções por ciclo (IPC) e acessos à memória cache.

Para o compilador Cliente os experimentos foram realizados para SEARCH e FASTA. SEARCH apresentou o mesmo IPC, para inline desligado ou ligado. Já FASTA obteve uma redução do IPC, passando de 0,84 para 0,75 instruções por ciclo, quando a otimização inline foi ligada. Estes resultados demonstram que a otimização causa um efeito negativo para o Fasta, quanto à quantidade de instruções executadas por ciclo. Esta redução de IPC é uma das causas da degradação de desempenho deste programa.

Para o compilador Servidor os experimentos foram realizados apenas para EULER, MOLDYN, FASTA, N-BODY e SPECTRAL. Não foram coletadas informações para os outros programas (que obtiveram uma queda de desempenho) devido ao fato da ferramenta utilizada não funcionar corretamente para o benchmark DaCapo.

EULER e MOLDYN apresentaram um pequeno aumento no IPC utilizando inline (0,91 para 0,92 e 1,45 para 1,46 respectivamente). FASTA obtive uma redução


116

de IPC passando de 0,92 para 0,89. E N-BODY se manteve estável, este foi um dos motivos que o levou a ter um desempenho insignificante.

Outros experimentos foram realizadas com os mesmos programas para avaliar o acesso à memória. Para o compilador Cliente os dois programas apresentaram uma redução na quantidade de acertos à cache (de 1,64% para SEARCH e 1,93% para FASTA). Para SEARCH esta redução não ocasionou em uma perca de desempenho. FASTA ainda apresentou um aumento de 3% na quantidade de acessos à cache, ocasionando uma perca de desempenho. Isto demonstra que a qualidade do código gerado pelo compilador cliente (utilizando inline) para estes programas não possui uma boa localidade.

Já no compilador Servidor os resultados foram mais variados. EULER apresentou um aumento, tanto para os acertos, quanto para os erros de acesso à cache. Porém, os erros aumentaram em 5,17%, enquanto os acertos aumentaram em apenas 1,43%. Este é um dos motivos deste programa ter perda de desempenho, pois muitos erros de acesso a memória cache ocorrem, quando a otimização é ligada.

Para MOLDYN OS aumentos na quantidade de acessos e erros foi insignificante (de 0,09% e 0,58% respectivamente). Embora estes dados não indiquem o que ocasionou a perda de desempenho de 27,79%, possivelmente isto foi ocasionado pelo tempo gasto pelo compilador. Como o compilador Servidor é um compilador agressivo, ele tende a gerar um alto tempo de compilação.

FASTA apresentou números negativos nos dois aspectos. A quantidade de erros de acesso aumentou em 4,25% e a quantidade de acertos de memória aumentou em 19,05%. Estes dados demonstram que a utilização da cache, quando a otimização inline foi ligada, foi prejudicial para a execução. Neste caso, ocorreu o mesmo problema ocasionado com o compilador Cliente, o código gerado pelo compilador Servidor possui uma qualidade baixa, ocasionando em uma má localidade.

N-BODY se manteve estável também quanto aos acessos à cache, obtendo apenas um aumento na quantidade de erros de 0,87% e um aumento insignificante na quantidade de acertos de 0,001%. Mesmo com este aumento nos erros de acesso, o desempenho deste programa se manteve consideravelmente estável. For fim, para SPECTRAL O USO de inline não teve impacto na quantidade de acessos à cache, contudo ocasionou uma redução de 35,14% na quantidade de acertos. Consequentemente, ocasinando uma perca de desempenho.

5. Considerações Finais Em geral, os trabalhos que descrevem ambientes Java com compilação dinâmica, não apresentam uma análise detalhada do impacto das otimizações aplicadas pelo compilador. Embora, alguns trabalhos [Gu et al. 2000, Cierniak et al. 2000, BURKE et al. 1999] destaquem a importância da aplicação de inline não descrevem a heurística utilizada, nem apresentam o ganho real obtido por esta otimização. Este trabalho descreve de forma detalhada a heurística utilizada na aplicação de inline pela máquina Virtual Java da Sun, como também apresenta uma análise detalhada do ganho de desempenho obtido por esta otimização.

A aplicação de inline realizada pelo compilador Cliente se mostrou mais eficiente. Apenas um programa, obteve perda de desempenho. Por outro lado, a agressividade do compilador Servidor se torna prejudicial em muitos casos,


117

ocasionando uma perca de desempenho significativa em alguns casos. Outro aspecto interessante é que o tempo de execução é drasticamente reduzido quando chamadas de métodos nativos sofrem a aplicação de inline. Em média, os programas utilizando o compilador Cliente obtiveram uma melhora de 26,25% no seu desempenho. Por outro lado, utilizando o compilador Servidor, estes programas obtiveram uma média geral de 6,67%. Esta diferença comprova que nem sempre a agressividade será a escolha correta.

Um trabalho futuro compreende desenvolver uma heurística dinâmica de aplicação de inline. Desta forma, os parâmetros que controlam esta otimização não serão mais estáticos, mas dinâmicos, podendo ser ajustado dependendo do perfil do programa em execução.

Referências Abboy, M. B. and Peterson, L. L. (1992). A Language-Based Approach to

Protocol Implementation. Computer Communications Review, 22 (4): 27-37.

Bernstein, D., Cohen, D., and Krawczyk, H. (1991). Code duplication: an assist for global instruction scheduling. In Proceedings ofthe International Symposium on Microarchi-tecture, pages 103-113, New York, NY, USA. ACM.

Bernstein, D., Golumbic, M., et al. (1989). Spill Code Minimization Techniques for Optimizing Compilers. In Proceedings ofthe Conference on Programming Language Design andImplementation, pages 258-263, Portland, Oregon. ACM.

Blackburn, S. M., Garner, R., et al. (2006). The DaCapo Benchmarks: Java Benchmark-ing Development and Analysis. In Proceedings ofthe Conference on Object-oriented Pogramming Sstems, Lnguages, and Applications, volume 41, pages 169-190, USA. ACM.

Brent Fulgham (2010). The Computer Language Benchmark Game. http:// shootout. alioth.debian.org/; acesso em 20 de Março 2010.

Bull, M., Smith, L., Westhead, M., Henty, D., and Davey, R. (2000). Benchmarking Java Grande Applications. In Proceedings ofthe International Conference on The Practical Applications of Java, pages 63-73.

BURKE, M. G., CHOI, J.-D., et al. (1999). The Jalapefío Dynamic Optimizing Compiler forjava. Java Grande Conference, pages 129-141.

Chen, W. Y, Chang, P. P., et al. (1991). The Effect of Code Expanding Optimizations on Instruction Cache Design. In CRHC-91-17, Center for Reliable and High-Performance Computing, University of Illinois. IEEE Computer Society.

Cierniak, M., Lueh, G.-Y, and Stichnoth, J. M. (2000). Practicing JUDO: Java Under Dynamic Optimizations. In Proceedings ofthe Conference on Programming Languages Design and Implementation, Vancouver, Canadá. ACM SIGPLAN.

da Silva, A. F. and Santos Costa, V. (2006). Our Experiences with Optimizations in Sun's Java Just-in-time Compilers. In Proceedings of the Brazilian Symposium on Programming Languages, pages 51-65, Brasil. SBC.

Deutsch, L. P. and Schiffman, A. M. (1984). Efficient implementation ofthe smalltalk-80 system. In POPL '84: Proceedings ofthe 11th ACM SIGACT-SIGPLAN


118

symposium on Principles ofprogramming languages, pages 297-302, New York, NY, USA. ACM.

Gu, W., Burns, N. A., et al. (2000). The Evolution of a High-Performing Java Virtual Machine. IBMSytems Journal, 39(1): 135-150.

Meyer, J. and Downing, T. (1997). Java Virtual Machine. O'Reilly, USA, 1 edition.

MicroSystems, S. (2010). The Java HotSpot Virtual Machine. Technical report, Sun Developer Network Community.

Muchnick, S. S. (1997). Advanced Compiler Design And Implementation. Morgan Kauf-mann, San Francisco, CA, USA.

Scott, M. L. (2008). Programming Language Pragmatics. Elsevier, 3 edition.

Terpstra, D., Jagode, H., You, H., and Dongarra, J. (2010). Collecting Performance Data with PAPI-C. In Proceedings ofthe Parallel Tools Workshop, pages 63-73, Germany. Springer Verlag.


119

Documents

UNIVERSIDADE ESTADUAL DE MARINGÁ Departamento de …wesley/wordpress/wp-content/uploads/2011/05/Anais... · Heloise Mânica Paris Teixeira - UEM Dra. Itana Maria de Souza Gimenes