Bifocal tree : uma técnica para visualização de estruturas hierárquicas

Estruturas de informações organizadas hierarquicamente estão presentes em muitas áreas. Pode-se citar como exemplos diagramas organizacionais, árvores genealógicas, manuais, estruturas de diretórios, catálogos de bibliotecas, etc. Na última década, várias técnicas têm sido desenvolvidas a fim de permitir a navegação em espaços de informações organizados dessa forma. Essas técnicas buscam proporcionar uma melhor percepção de alguns atributos ou fornecer mecanismos de interação adicionais que vão além da tradicional navegação com barras de rolagem ou câmeras 3D em visualização bi e tridimensional, respectivamente. Dentre as várias alternativas de representação utilizadas nas diversas técnicas para dados hierárquicos destacam-se dois grandes grupos: as que utilizam a abordagem de preenchimento do espaço e as baseadas em diagramas de nodos e arestas. Na primeira o espaço disponível para a representação da estrutura é subdividido recursivamente, de forma que cada subárea representa um nodo da hierarquia. Na segunda, os nodos são representados por figuras geométricas e os relacionamentos, por linhas. Outro critério utilizado para classificá-las é a estratégia que cada uma aplica para exibir os detalhes presentes na estrutura. Algumas técnicas utilizam o método Foco+Contexto de modo a fornecer uma representação visual inteira do espaço de informações, bem como uma visão detalhada de itens selecionados na mesma área de exibição. Outras utilizam a abordagem Visão Geral+Detalhe que possui a característica de exibir essas duas partes (conjunto total e subconjunto de interesse) em áreas separadas. O objetivo do presente trabalho é investigar a integração dessas duas abordagens a partir da proposta da técnica Bifocal Tree. Esta estrutura utiliza um diagrama de nodos e arestas e incorpora os conceitos existentes na abordagem Foco+Contexto guardando, porém uma divisão mais perceptível da visão de contexto e de detalhe. Ela introduz o uso de um segundo foco proporcionando duas áreas de visualização onde são exibidos dois sub-diagramas conectados entre si. Um corresponde à subárvore que contém o trecho da estrutura de interesse do usuário, enquanto o outro representa o contexto da hierarquia visualizada. Possui ainda alguns mecanismos de interação a fim de facilitar a navegação e a obtenção das informações exibidas na estrutura. Experimentos baseados em tarefas realizadas por usuários com a Bifocal Tree, o Microsoft Windows Explorer e o browser MagniFind foram utilizados para a avaliação da técnica demonstrando suas vantagens em algumas situações.

Uso do network simulator-NS para simulação de sistemas distribuídos em cenários com defeitos

O desenvolvimento de protocolos distribuídos é uma tarefa complexa. Em sistemas tolerantes a falhas, a elaboração de mecanismos para detectar e mascarar defeitos representam grande parte do esforço de desenvolvimento. A técnica de simulação pode auxiliar significativamente nessa tarefa. Entretanto, existe uma carência de ferramentas de simulação para investigação de protocolos distribuídos em cenários com defeitos, particularmente com suporte a experimentos em configurações “típicas” da Internet. O objetivo deste trabalho é investigar o uso do simulador de redes NS (Network Simulator) como ambiente para simulação de sistemas distribuídos, particularmente em cenários sujeitos à ocorrência de defeitos. O NS é um simulador de redes multi-protocolos, que tem código aberto e pode ser estendido. Embora seja uma ferramenta destinada ao estudo de redes de computadores, o ajuste adequado de parâmetros e exploração de características permitiu utilizá-lo para simular defeitos em um sistema distribuído. Para isso, desenvolveu-se dois modelos de sistemas distribuídos que podem ser implementados no NS, dependendo do protocolo de transporte utilizado: um baseado em TCP e o outro baseado em UDP. Também, foram estudadas formas de modelar defeitos através do simulador. Para a simulação de defeito de colapso em um nodo, foi proposta a implementação de um método na classe de cada aplicação na qual se deseja simular defeitos. Para ilustrar como os modelos de sistemas distribuídos e de defeitos propostos podem ser utilizados, foram implementados diversos algoritmos distribuídos em sistemas síncronos e assíncronos. Algoritmos de eleição e o protocolo Primário-Backup são exemplos dessas implementações. A partir desses algoritmos, principalmente do Primário-Backup, no qual a simulação de defeitos foi realizada, foi possível constatar que o NS pode ser uma ferramenta de grande auxílio no desenvolvimento de novas técnicas de Tolerância a Falhas. Portanto, o NS pode ser estendido possibilitando que, com a utilização dos modelos apresentados nesse trabalho, simule-se defeitos em um sistema distribuído.

Hyper-Automaton: avaliação interativa de alunos em cursos na WEB baseado em autômatos finitos

O objetivo desta dissertação é a elaboração de uma técnica da aplicação do formalismo de Autômatos Finitos com Saída (Máquina de Mealy e Máquina de Moore) como um modelo estrutural para a organização de hiperdocumentos instrucionais, em destacar especial, Avaliação e Exercício. Esse objetivo é motivado pela organização e agilização do processo de avaliação proporcionado ao professor e ao aluno. Existem diferentes técnicas de ensino utilizadas na Internet, algumas dessas continuam sendo projetadas com o uso de metodologias tradicionais de desenvolvimento, outras têm a capacidade de modelar de forma integrada e consistente alguns aspectos necessários para uma aplicação WEB. Para alcançar o objetivo proposto, foram realizadas pesquisas nas várias áreas abrangidas pelo tema em evidência, tanto relativo ao processo tradicional (aplicação de prova utilizando metodologia tradicional), como o desenvolvimento de software mediado por computador e uso da Internet em si. A modelagem de desenvolvimento para Internet deve integrar características de técnicas de projeto de sistemas de hipermídia devido à natureza hipertextual da Internet. O uso de hiperdocumento como autômatos com saída está na forma básica de representação de hipertexto, em que cada fragmento de informação é associado a um nodo ou a um link (estado/transições) do grafo. Sendo assim, os arcos direcionados representam relacionamentos entre os nodos ou links, ou seja, uma passagem do nodo origem para o nodo destino. As n-uplas dos autômatos apresentam uma correspondência as estruturas de hiperdocumentos na WEB, seu estado/transição inicial corresponde a sua primeira página e suas transições definidas na função programa, funcionam como ligações lógicas, quando selecionadas durante a navegação do hipertexto. Entretanto, faz-se necessário um levantamento dos modelos de hipertextos e das ferramentas de implementação disponíveis para a Internet, a fim de que seja capaz de suportar as peculiaridades do ambiente. Tudo isso deve ser integrado preferencialmente em um paradigma de desenvolvimento amplamente aceito, para que os projetistas não tenham muitas dificuldades em assimilar os conceitos propostos. A proposta apresentada nesta dissertação, batizada de Hyper-Automaton (hipertexto e autômato), consiste na integração de um Curso na WEB, utilizando formalismo de Autômatos Finitos com Saída para a modelagem dos conceitos necessários e definição das fases adequadas para completar a especificação de Sistema Exercício e Avaliação, bem como a especificação da Geração Automática dos Exercícios e Avaliações baseadas em autômatos para a WEB. Os modelos criados abrangem conceitos de Máquina de Mealy, Máquina de Moore e Aplicações de Hiperdocumentos e Ferramentas de Programação para Internet, os mesmos já testados em caso real. Os parâmetros apurados, nos testes, serviram a uma seqüência de etapas importantes para modelar e complementar a especificação do sistema projetado. Com os parâmetros e etapas de modelagem, a metodologia Hyper-Automaton consegue integrar, de forma consistente, as vantagens de várias técnicas específicas de modelagem de documentos e sistemas de hipermídia. Essas vantagens, aliadas ao suporte às ferramentas de desenvolvimento para Internet, garantem que a metodologia fique adequada para a modelagem de Sistemas com aplicação de métodos de autômatos para exercícios e avaliação na WEB.

Estimativa de capacitâncias e consumo de potência em circuitos combinacionais CMOS no nível lógico

Esta tese propõe o desenvolvimento de um método de estimativa de capacitâncias e de potência consumida nos circuitos combinacionais CMOS, no nível de portas lógicas. O objetivo do método é fazer uma previsão do consumo de potência do circuito na fase de projeto lógico, o que permitirá a aplicação de técnicas de redução de potência ou até alteração do projeto antes da geração do seu leiaute. A potência dinâmica consumida por circuitos CMOS depende dos seguintes parâmetros: tensão de alimentação, freqüência de operação, capacitâncias parasitas e atividades de comutação em cada nodo do circuito. A análise desenvolvida na Tese, propõe que a potência seja dividida em duas componentes. A primeira componente está relacionada ao consumo de potência devido às capacitâncias intrínsecas dos transistores, que por sua vez estão relacionadas às dimensões dos transistores. Estas capacitâncias intrínsecas são concentradas nos nodos externos das portas e manifestam-se em função das combinações dos vetores de entrada. A segunda componente está relacionada às interconexões entre as células do circuito. Para esta etapa utiliza-se a estimativa do comprimento médio das interconexões e as dimensões tecnológicas para estimar o consumo de potência. Este comprimento médio é estimado em função do número de transistores e fanout das várias redes do circuito. Na análise que trata das capacitâncias intrínsecas dos transistores os erros encontrados na estimativa da potência dissipada estão no máximo em torno de 11% quando comparados ao SPICE. Já na estimativa das interconexões a comparação feita entre capacitâncias de interconexões estimadas no nível lógico e capacitâncias de interconexões extraídas do leiaute apresentou erros menores que 10%.

Investigação de técnicas de visualização para representação de autômatos finitos com saída

Atualmente, a World Wide Web (WWW) já se estabeleceu como um dos meios de divulgação mais difundidos. Sendo um meio de publicação de custo relativamente baixo, muitas iniciativas foram desenvolvidas no sentido de estendê-la e transformá-la também numa ferramenta de apoio. Assim, uma série de pesquisas foi realizada no sentido de promover e facilitar o gerenciamento das informações da WWW, que são estruturadas, em sua maioria, como conjuntos de documentos inter-relacionados. Grafos são estruturas utilizadas para a representação de objetos e seus múltiplos relacionamentos. Nesse sentido, pode-se afirmar que hiperdocumentos podem ser modelados através de grafos, onde uma página representa um nodo e um link para outra página é representado por uma aresta. Considerando estas características, e dada a crescente complexidade dos materiais publicados na WWW, desenvolveu-se, ao longo da última década, o uso de técnicas e recursos de Visualização de Grafos com larga aplicação na visualização da estrutura e da navegação na WWW. Técnicas de visualização de grafos são aplicáveis especificamente para representar visualmente estruturas que possam ser modeladas por meio de objetos relacionados, sendo investigadas técnicas para a abstração de modo a facilitar tanto o processo de compreensão do contexto da informação, quanto a apreensão dos dados relacionados. Este trabalho tem como objetivo a investigação de técnicas de Visualização de Grafos aplicadas a autômatos finitos com saída. Este direcionamento se deve ao fato de alguns autores utilizar a abordagem de autômatos finitos com saída para as estruturas de hiperdocumentos. Se for considerado que um documento da WWW (ou o estado de um autômato) é composto por fragmentos de informação (ou saídas) tais como trechos de texto, imagens, animações, etc e que este documento é relacionado a outros por meio de links (ou transições), tem-se a verificação de sua representatividade por meio destas estruturas. Em trabalho anterior, no âmbito do PPGC da UFRGS, a ferramenta Hyper-Automaton foi desenvolvida com o objetivo de estender o uso da Internet no sentido de prover uma ferramenta de apoio à publicação de materiais instrucionais. Por adotar a notação de autômatos finitos com saída, possibilita, além da criação e gerenciamento de hiperdocumentos, a reutilização de fragmentos de informação sem que haja qualquer interferência de um autômato que utilize este fragmento sobre outro. O Hyper-Automaton foi selecionado como caso de estudo motivador deste trabalho. As técnicas aqui desenvolvidas têm como intuito diminuir a complexidade visual da informação, assim como permitir a navegação através dos autômatos finitos com saída de forma que seja possível visualizar detalhes como as saídas e informações relacionadas a cada uma delas, mantendo a visualização do contexto da informação. Foram analisadas técnicas de agrupamento como forma de redução da complexidade visual, e técnicas do tipo foco+contexto, como alternativa para prover a visualização simultânea do contexto e dos detalhes da informação.

Injeção distribuída de falhas para validação de dependabilidade de sistemas distribuídos de larga escala

Uma etapa fundamental no desenvolvimento de sistemas tolerantes a falhas é a fase de validação, onde é verificado se o sistema está reagindo de maneira correta à ocorrência de falhas. Uma das técnicas usadas para validar experimentalmente um sistema é injeção de falhas. O recente uso de sistemas largamente distribuídos para execução dos mais diversos tipos de aplicações, faz com que novas técnicas para validação de mecanismos de tolerância a falhas sejam desenvolvidas considerando este novo cenário. Injeção de falhas no sistema de comunicação do nodo é uma técnica tradicional para a validação de aplicações distribuídas, para forçar a ativação dos mecanismos de detecção e recuperação de erros relacionados à troca de mensagens. A condução de experimentos com injetores de comunicação tradicionais é feita pelo uso do injetor em uma máquina do sistema distribuído. Se o cenário desejado é de múltiplas falhas, o injetor deve ser instanciado independentemente nas n máquinas que as falhas serão injetadas. O controle de cada injetor é individual, o que dificulta a realização do experimento. Esta dificuldade aumenta significativamente se o cenário for um sistema distribuído de larga escala. Outro problema a considerar é a ausência de ferramentas apropriadas para a emulação de determinados cenários de falhas. Em aplicações distribuídas de larga escala, um tipo comum de falha é o particionamento de rede. Não há ferramentas que permitam diretamente a validação ou a verificação do processo de defeito de aplicações distribuídas quando ocorre um particionamento de rede Este trabalho apresenta o estudo de uma abordagem para injeção de falhas que permita o teste de atributos de dependabilidade de aplicações distribuídas de pequena e larga escala implementadas em Java. A abordagem considera a não obrigatoriedade da alteração do código da aplicação sob teste; a emulação de um cenário de falhas múltiplas que ocorrem em diferentes nodos, permitindo o controle centralizado do experimento; a validação de aplicações que executem em sistemas distribuídos de larga escala e consideram um modelo de falhas realista deste tipo de ambiente, incluindo particionamentos de rede. A viabilidade da abordagem proposta é mostrada através do desenvolvimento do protótipo chamado FIONA (Fault Injector Oriented to Network Applications), o qual atualmente injeta falhas em aplicações desenvolvidas sob o protocolo UDP.

Ambiente de alto desempenho com alta exatidão para a resolução de problemas

Este trabalho visa a disponibilização de um ambiente de alto desempenho, do tipo cluster de computadores, com alta exatidão, obtida através da utilização da biblioteca C–XSC. A alta exatidão na solução de um problema é obtida através da realização de cálculos intermediários sem arredondamentos como se fossem em precisão infinita. Ao final do cálculo, o resultado deve ser representado na máquina. O resultado exato real e o resultado representado diferem apenas por um único arredondamento. Esses cálculos em alta exatidão devem estar disponíveis para algumas operações aritméticas básicas, em especial as que possibilitam a realização de somatório e de produto escalar. Com isso, deseja-se utilizar o alto desempenho através de um ambiente de cluster onde se tem vários nodos executando tarefas ou cálculos. A comunicação será realizada por troca de mensagens usando a biblioteca de comunicação MPI. Para se obter a alta exatidão neste tipo de ambiente, extensões ou adaptações nos programas paralelos tiveram que ser disponibilizadas para garantir que a qualidade do resultado final realizado em um cluster, onde vários nodos colaboram para o resultado final do cálculo, mantivesse a mesma qualidade do resultado que é obtido em uma única máquina (ou nodo) de um ambiente de alta exatidão. Para validar o ambiente proposto foram realizados testes básicos abordando o cálculo do produto escalar, a multiplicação entre matrizes, a implementação de solvers intervalares para matrizes densas e bandas e a implementação de alguns métodos numéricos para a resolução de sistemas de equações lineares com a característica da alta exatidão. Destes testes foram realizadas análises e comparações a respeito do desempenho e da exatidão obtidos com e sem o uso da biblioteca C–XSC, tanto em programas seqüenciais como em programas paralelos. Com a conseqüente implementação dessas rotinas e métodos será aberto um vasto campo de pesquisa no que se refere ao estudo de aplicações reais de grande porte que necessitem durante a sua resolução (ou em parte dela) da realização de operações aritméticas com uma exatidão melhor do que a obtida usualmente pelas ferramentas computacionais tradicionais.