Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-10-24T12:49:20Z (GMT). No. of bitstreams: 1 Ottoni_GuilhermedeLima_M.pdf: 2467303 bytes, checksum: 3894457788c8896fac76459cfbda00e4 (MD5) Previous issue date: 2002 / Resumo: O avanço tecnológico dos sistemas computacionais tem proporcionado o crescimento do mercado de sistemas dedicados, cada vez mais comuns no dia-a-dia das pessoas, como por exemplo em telefones celulares, palmtops e sistemas de controle automotivo. Devido às suas características, estas novas aplicações requerem sistemas que aliem baixo custo, alto desempenho e baixo consumo de potência. Uma das maneiras de atender a estes requisitos é utilizando processadores especializados. Contudo, a especialização na arquitetura dos processadores impõe novos desafios para o desenvolvimento de software para estes sistemas. Em especial, os compiladores - geralmente responsáveis pela otimização de código - precisam ser adaptados para produzir código eficiente para estes novos processadores. Na área de processamento de sinais digitais, como em telefonia celular, processadores especializados, denominados DSPs2, são amplamente utilizados. Estes processadores tipicamente possuem poucos registradores de propósito geral e modos de endereçamento bastante limitados. Além disso, muitas das suas aplicações envolvem o processamento de grandes seqüências de dados, as quais são geralmente armazenadas em vetores. Como resultado, o estudo de técnicas de otimização de referências a vetores tornou-se um problema central em compilação para DSPs. Este problema, denominado Global Array Reference Allocation (GARA), é o objeto central desta dissertação. O sub-problema central de GARA consiste em se determinar, para um dado conjunto de referências a vetores que serão alocadas a um mesmo registrador de endereçamento, o menor custo das instruções que são necessárias para manter este registrador com o endereço adequado em cada ponto do programa. Nesta dissertação, este sub-problema é modelado como um problema em grafos, e provado ser NP-difícil. Além disso, é proposto um algoritmo eficiente, baseado em programação dinâmica, para resolver este sub-problema de forma exata sob certas restrições. Com base neste algoritmo, duas técnicas são propostas para resolver o problema de GARA. Resultados experimentais, obtidos pela implementação destas técnicas no compilador GCC, comparam-nas com outros resultados da literatura. Os resultados demonstram a eficácia das técnicas propostas nesta dissertação / Abstract: The technological advances in computing systems have stimulated the growth of the embedded systems market, which is continuously becoming more ordinary in people's lives, for example in mobile phones, palmtops and automotive control systems. Because of their characteristics, these new applications demand the combination of low cost, high performance and low power consumption. One way to meet these constraints is through the design of specialized processors. However, processor specialization imposes new challenges to the development of software for these systems. In particular, compilers - generally responsible for code optimization - need to be adapted in order to produce efficient code for these new processors. In the digital signal processing arena, such as in cellular telephones, specialized processors, known as DSPs (Digital Signal Processors), are largely used. DSPs typically have few general purpose registers and very restricted addressing modes. In addition, many DSP applications include large data streams processing, which are usually stored in arrays. As a result, studing array reference optimization techniques became an important task in compiling for DSPs. This work studies this problem, known as Global Array Reference Allocation (GARA). The central GARA subproblem consists of determining, for a given set of array references to be allocated to the same address register, the minimum cost of the instructions required to keep this register with the correct address at alI program points. In this work, this subproblem is modeled as a graph theoretical problem and proved to be NP-hard. In addition, an efficient algorithm, based on dynamic programming, is proposed to optimally solve this subproblem under some restrictions. Based on this algorithm, two techniques to solve GARA are proposed. Experimental results, from the implementation of these techniques in the GCC compiler, compare them with previous work in the literature. The results show the effectiveness of the techniques proposed in this work / Mestrado / Mestre em Ciência da Computação

Resumo: Buscas em grafos é uma das ferramentas mais simples e mais utilizadas para algoritmos em grafos. Um algoritmo de busca examina os vértices e as arestas de um grafo a partir de um vértice inicial e, sistematicamente visita um novo vértice por iterativa travessias em arestas incidentes a um vértice anteriormente já visitado. A ordem em que esses vértices são visitados definem uma enumeração desses vértices em um dado grafo. Na literatura disponível, poucos resultados teóricos são conhecidos sobre uma enumeração que pode ser gerada por um algoritmo de busca específico, embora buscas como em Largura e em Profundidade sejam algoritmos tradicionais e bem conhecidos na literatura atual. ecentemente, dois novos algoritmos, Busca em Largura Lexicográfica e a Busca da Cardinalidade Máxima, têm sido aplicados em uma grande variedade de problemas e, além desses, outras estratégias também são conhecidas, como a Busca em Profundidade Lexicográfica, da Vizinhança Maximal e do Rótulo Maximal, usadas para o reconhecimento de certas classes de grafos, por exemplo. Muito dos resultados obtidos nas aplicações desses algoritmos de busca dependem da simples caracterização da numeração que estes algoritmos podem computar. Neste trabalho, generalizamos o conceito de busca orientada por aresta para o caso de hipermultigrafo, apresentaremos características das enumerações e por fim provaremos que essas enumerações caracterizam um algoritmo de busca.

Orientadores: Silvia Regina Vergilio, Mario Jino / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-26T08:01:35Z (GMT). No. of bitstreams: 1 Peres_LeticiaMara_M.pdf: 8518550 bytes, checksum: 2de6ca87d235b1b8960f087717081807 (MD5) Previous issue date: 1999 / Resumo: Critérios estruturais de teste têm o objetivo de auxiliar a etapa de geração de dados de teste e de avaliar a adequação de um conjunto de casos de teste, oferecendo medidas de cobertura. Eles requerem a execução de caminhos do programa que exercitem alguns elementos, tais como: comandos, decisões, definições e usos de variáveis. A seleção de caminhos e conseqüente geração de dados de teste para aplicação de um critério estrutural é uma das etapas mais difíceis de serem automatizadas. Pois, é indecidível determinar um dado de entrada para executar um particular caminho em um programa; é indecidível determinar até mesmo se esse dado existe, ou seja, se o caminho é ou não executável. Isto, aliado à eficácia dos dados gerados, aumenta a importância dessa etapa e conseqüentemente os custos de teste. Por isso, vários trabalhos na literatura ressaltam a importância de estratégias para minimizar o número de caminhos não executáveis selecionados para satisfazer um dado critério estrutural. Este trabalho tem como objetivos estudar, propor e fornecer mecanismos para automatização e validação de estratégias de seleção de caminhos a serem utilizadas em conjunto com critérios de teste estrutural. São propostas estratégias que consideram diferentes características de programas para seleção de caminhos visando: aumentar a eficácia, facilitar a etapa de geração de dados, e reduzir os efeitos causados por caminhos não executáveis no teste de software. Uma estrutura de representação /automatização dessas estratégias é apresentada e um módulo que implementa essa estrutura é descrito. O módulo é uma extensão à ferramenta Poke-Tool que apóia a utilização de diferentes critérios de teste e foi utilizado para avaliar uma estratégia proposta com o objetivo de minimizar o número de caminhos não executáveis selecionados. Esta aplicação permitiu detectar algumas estruturas de programa para os quais a estratégia avaliada não alcança seu objetivo e também verificar aspectos de eficácia dos dados gerados para a execução dos caminhos selecionados / Abstract: Testing criteria are useful in the task of test case generation and they are predicates to consider the testing activity ended, that is, to determine the adequation of a test set. They require the execution of paths in the program that exercise some elements such as statements, decisions, definitions and uses of variables. Selecting paths and generating automatic test data for a given structural criterion are very hard activities since it is not always possible to determine a data that executes a particular path in a program; it is even undecidable whether this data exists, that is, whether the path is feasible. This makes those activities difficult and increases the cost of testing. Several researches attach importance to strategies that minimize the number of infeasible selected paths to cover structural criteria. The goal of this work is to study, propose and offer strategies to select paths and mechanisms to automate and validate these strategies to be used with structural criteria. The proposed strategies consider different characteristics of programs for paths selection with the goal of: increasing the efficacy, easing the test data generation and reducing the effects caused by infeasible paths in the software testing. A structure to represent these strategies are presented. A module that implements this structure is described. This module is an extension to the testing tool named Poke-Tool, that supports different structural testing criteria. It was used to evaluate a strategy that proposes to 'minimize the number of infeasible selected paths. This application was guided to the detection of some program structures for which the evaluated strategy did not meet its objective and pointed out some results about the efficacy of the generated test data / Mestrado / Mestre em Engenharia Elétrica

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T17:17:44Z (GMT). No. of bitstreams: 1 Ferreira_RodrigoAugustoBarbato_M.pdf: 7083497 bytes, checksum: e0954b25f044d75d0166d511f5bbe192 (MD5) Previous issue date: 2001 / Resumo: A compilação Just-In- Time (JIT) é uma técnica amplamente utilizada no aperfeiçoamento do desempenho da Máquina Virtual Java (JVM, do inglês Java Virtual Machine). Con­tudo, o tempo gasto internamente pelo compilador JIT degrada, em muitos casos, o tempo de execução das aplicações. Algumas técnicas têm sido usadas com o objetivo de diminuir o impacto negativo do JIT sobre a execução, ainda sim preservando a sua eficácia. Entretanto, sempre haverá uma relação inversa entre o tempo gasto pelo compilador JIT e o tempo de execução do código objeto por ele produzido. Segundo nossa concepção, uma Máquina Virtual Java que visa usuários finais executa o mesmo código a maior parte do seu tempo. Os usuários sempre utilizam os mesmos aplicativos, os quais são tipicamente compostos pelo mesmo conjunto de classes. Por outro lado, em grandes companhias, dezenas ou até mesmo centenas de empregados compartilham a mesma aplicação ou pa­cote de aplicações. Usualmente, eles estão conectados a uma mesma Intranet, rápida e segura. Neste cenário, o esforço do JIT por usuário é repetitivo e bem maior que o estritamente necessário. O objetivo deste trabalho é o de desacoplar atividades de tempo de ligação da JVM para um servidor compartilhado, de maneira distribuída. Desta forma, cada cliente JVM se torna um componente de software muito simples que executa código Java nativamente, dispensando um JIT ou interpretador. Todas as atividades complexas de tempo de ligação - como detecção de erros, verificação do formato binário Java e com­pilação JIT - são efetuadas pelo servidor, que armazena suas respostas em uma cache. Este documento é uma descrição de uma implementação alternativa da Máquina Virtual Java que inova em muitos pontos. Em particular, são contribuições deste trabalho: as técnicas para a detecção e recuperação de contextos repetidos em tempo de ligação; um procedimento alternativo, off-line, para a verificação do bytecode Java; o projeto e a im­plementação de uma representação intermediária específica para Java; a descrição, em detalhes, de diversos aspectos de implementação da JVM / Abstract: Just-In-Time (JIT) compilation is a well-known technique used to improve the execution time in the Java Virtual Machine (JVM). However, the amount of time used by the JIT internals degrades, in many cases, the application execution time. Some techniques have been used to decrease the JIT overhead, while still keeping its effectiveness. However, the trade-off between the JIT running time and its object code execution time will always existo From our observation, an end-user Java Virtual Machine deals with the same code most of its time. Users always launch the same applications, which are typically composed of the same set of classes. On the other hand, in big companies, dozens or even hundreds of employees share the same application or application suite. Usually, they are connected under the same fast and secure Intranet. In this scenario, the per-user JIT effort is repetitive and largely greater than the strictly required. The goal of our work is to detach linking activities from the JVM to a shared server, on a distributed fashion. By doing that, the client JVM turns to be a very simple piece of software that runs Java code natively, not requiring a JIT or interpreter. All complex linking activities - like link-time error checking, class file verification and JIT compilation are done by the server, which caches its responses. This document is a description of an alternate implementation of the Java Virtual Machine that innovates. It covers specially: the techniques for detecting and caching repetitive link-time contexts; an alternate, offline, byte code verification procedure; the design and implementation of a Java specific intermediate representation; the detailed description of many JVM implementation issues / Mestrado / Mestre em Ciência da Computação

Orientador : Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T22:42:38Z (GMT). No. of bitstreams: 1 Pinto_RandalJulianoPereira_M.pdf: 1892190 bytes, checksum: d5c7c9a843bf9760d761e985a3df1b3c (MD5) Previous issue date: 2003 / Resumo: Dispositivos portáteis e personalizáveis têm se tornado Ítens cada vez mais importantes em nossas vidas. Telefones celulares, organizadores pessoais, terminais de serviço pos-suem algumas características em comum como a funcionalidade limitada, restrições de tamanho e custo e, principalmente, são um mercado em plena expansão. Para atender a esta demanda, a Sun Microsystems Inc. extendeu o escopo da sua tecnologia Java com a introdução do Java 2 Platform Micro Edition (J2ME). Tendo em vista a característica limitada deste tipo de dispositivo, melhorias no desempenho da plataforma J2ME são essenciais para o seu desenvolvimento e aceitação. Diversas propostas de otimização são encontradas na literatura com enfoque principal nas tecnologias J2SE (Java 2 Standard Edition) e J2EE (Java 2 Enterprise Edition), porém quase nenhuma delas visa exclusi-vamente as necessidades da plataforma J2ME. Este trabalho propõe a aplicação de duas técnicas de otimização no interpretador da KVM. A primeira técnica baseia-se na redução da freqüência de acessos à memória e resultou em ganhos totais nos benchmarks analisa- dos de 0,14% a 5,66% e ganhos em alguns testes de até 37,71%, com aumento no código fonte de apenas 0,62% em relação ao tamanho do executável original. A segunda baseia-se na redução de alguns passos do ciclo de interpretação de bytecodes e seu resultado geral variou de -0,90% até 5,32%, obtendo ganhos em alguns testes de até 18%, com aumento nos códigos fonte variando entre 0,0052% e 0,0142% / Abstract: Mobile and customizable devices are increasingly becoming important items in our lives. Cellular phones, personal organizers, service terminaIs have many characteristics in com- mon such as limited functionality, size and cost restrictions and specially are an expanding market. To attend this demanding market, Sun Microsystems Inc. extended the scope of the Java technology, introducing the Java 2 Platform Micro Edition (J2ME). Considering the limitations on this kind of device, performance improvements on the J2ME platform are essential to its development and general acceptance. Several optimization proposals can be found in the technicalliterature focused on J2SE (Java 2 Standard Edition) and J2EE (Java 2 Enterprise Edition) platforms, but almost none aims at the needs of the J2ME platform. The goal of this dissertation is to apply two optimization techniques to the KVM's interpreter. The first technique is based on reducing the number of memory accesses and resulted in a general performance increase from 0.14% to 5.66% and up to 37% for some benchmark programs. The increase on the source code size was only 0.62%, when compared to the original executable size. The second technique is based on reducing some steps of the bytecode interpretation cycle and its general results varied from a per-formance overhead of 0.90% to a performance increase of 5.32%, and up to 18% speedup for some of the benchmark programs. The increase in the source code size varied from 0.0052% to 0.0142%, when compared to the original executable size / Mestrado / Mestre em Ciência da Computação

Orientador: Cecilia Mary Fischer Rubira / Dissertação (mestrado) - Universidade estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-24T16:25:18Z (GMT). No. of bitstreams: 1 Coelho_MariliaGabriela_M.pdf: 2936468 bytes, checksum: 462f6efbbbdec9a8a2e6f94d309a3682 (MD5) Previous issue date: 1998 / Resumo: Uma aplicação interativa é composta de um núcleo funcional (ou aplicação) e da interface do usuário. Uma das maiores dificuldades no desenvolvimento e manutenção de aplicações interativas encontra-se nas dependências entre os módulos que implementam o núcleo funcional e a interface do usuário. Os frameworks atuais para construção de aplicações interativas são baseados em padrões de arquitetura, que não provêem independência de diálogo efetiva para a aplicação. Isto acontece porque, nos padrões de arquitetura existentes, as dependências entre os módulos de uma aplicação interativa são implementadas nos próprios módulos. O objetivo deste trabalho é mostrar como o padrão de arquitetura reflexão computacional pode ser utilizado para implementar de forma efetiva a independência de diálogo em aplicações interativas. Nesta abordagem, os serviços de visuaIização da interface são fornecidos de forma não intrusiva e transparente para a aplicação, pois as dependências entre aplicação e interfuce são implementadas no meta-nível, independentemente do núcleo funcional da aplicação. Este trabalho propõe o padrão de arquitetura MVCR (Modelo Visão Controlador Reflexivo) como uma combinação do padrão de arquitetura para construção de sistemas interativos MVC (Model View Controller) e o padrão de arquitetura reflexão computacional. O padrão MVCR é comparado ao padrão MVC através da efetuação de um estudo de caso utilizando o ET ++, um framework para desenvolvimento de aplicações gráficas cuja arquitetura é baseada no MVC. Para realizarmos o estudo de caso, re-estruturamos o ET ++ utilizando o padrão MVCR (obtendo-se assim o ET ++ Reflexivo) e desenvolvemos uma mesma aplicação utilizando as duas abordagens: o ET ++ original baseado no MVC e o ET ++ Reflexivo baseado no MVCR Desta forma, foi possível comparar e avaliar as vantagens e limitações da abordagem reflexiva. / Abstract: An interactive application is compound by a functional core application (or just application) and its graphical user interface (GUI). One of the main difficulties on the development and maintenance of interactive applications is on the dependence between the application and its graphical user interface. Most of the object-oriented GUI ftameworks are based on arquitectural patterns, that do not provide dialog independence among applications, this occurs in these patterns because the dependence between the application components and GUI components is implemented in the own components. The goal of this work is to show how computational reflection can be used to implement an effective dialog independence in interactive applications. In this appoach, the graphical user interface can be provided in a transparent and non-intrusive way to the application, since the dependence between the application and GUI are implemented on the meta-level. This work proposes the arquitectural pattern RMVC (Reflective ModeWiew/Controller) - a combination of the arquitectura1 pattern MVC (ModeWiew/Controller) and the arquitectural pattern Computational Reflection. We bave carried out a case study in order do compare both patterns MVC and MVCR using the ET++, a GUI framework based on pattern MVC. First, we develop the Reflective ET++, restructuring the ET++ using the MVCR, and then we develop one same application using the two approaches: the original ET ++ based on MVC and the Retlective ET ++ based on MVCR Thus, it was possible to discuss the advantages and limitations of using the retlective approach. / Mestrado / Mestre em Ciência da Computação

[pt] Este trabalho propõe uma arquitetura para um computador analógico controlado por um microcomputador. O escopo da proposta é uma máquina que seja confiável e facilmente utilizável. Com essas idéias em mente é apresentada e discutida a arquitetura da Unidade de Simulação e é mostrado que o sistema pode ser expandido sem limitação teórica. A Unidade de Controle é um microprocessador que recebe os dados do usuário e os utiliza para determinar e implementar as interligações, ganhos e demais parâmetros da Unidade de Simulação. Ao final do trabalho é apresentada uma comparação com dois sistemas comerciais, que mostra ser a estrutura proposta, superior, especialmente em relação à facilidade de programação e operação. / [en] This thesis discusses the architecture of an analog computer controlled by a digital microcomputer. The autho’s goal is to develop a machine which is both reliable and ease to use. The architecture of the Simulation Unit is presented and discussed and it is show that the system can expanded without (theorectical) limits. The Control Unit is based on a microcomputer that receives the data from the user and processes it to determine gains, interconections etc., for the Simulation Unit. The proposed machine is finally compared to two commercially avaliable systems and the results suggest that the proposed arquitecture is superior especially compared the easy of operation and programming.

Diseñador Gráfico / No autorizada para ser publicada en el Portal de Tesis Electrónicas de la U. de Chile.

Made available in DSpace on 2019-04-05T23:09:02Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-12-27 / A scenario describes how one or more system components interact to provide a certain set of functionalities. Because each scenario only represents a partial view of the overall system behavior, scenario-based specifications may hide unexpected interactions (called implied scenarios) which are not part of any scenario individually. Implied scenarios may either indicate gaps in the original scenario specification, or undesired behavior that should be avoided during scenario implementation. This paper presents a reverse engineering process to support extraction and detection of implied scenarios in concurrent systems. The main contribution of the work is to demonstrate how the concept of implied scenarios, which use thus far has been restricted to early phases of the software life-cycle, such as requirements elaboration and reliability prediction, can also be applied to support comprehension and testing of existing systems. The use of the proposed process and its support tools is illustrated through a case study, in which we were able to detect implied scenarios in a existing ecommerce web application. / Um cenário descreve como um ou mais componentes de um sistema interagem para oferecer um conjunto de funcionalidades. Devido a cada cenário representar apenas uma visão parcial do comportamento global do sistema, especificações baseadas em cenários podem esconder comportamentos inusitados, denominados cenários implícitos , não previstos nos cenários originais. A presença de cenários implícitos tanto pode indicar falhas na especificação do sistema, como comportamentos indesejados a serem evitados. Este trabalho propõe um processo de engenharia reversa para apoiar a extração e detecção de cenários implícitos em sistemas concorrentes. A principal contribuição do trabalho é permitir que os desenvolvedores se beneficiem do conceito de cenários implícitos, até então de uso restrito às fases iniciais do ciclo de vida de software, também para apoiar atividades de compreensão e teste de sistemas existentes. A utilização do processo e de suas ferramentas de apoio é ilustrada através de um estudo de caso, onde foram detectados cenários implícitos em uma aplicação web de comércio eletrônico.

Orientador : Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-10-24T13:16:43Z (GMT). No. of bitstreams: 1 GalloFilho_RobertoAlves_M.pdf: 1560614 bytes, checksum: daf319c0056798f7d57a137a6be71d39 (MD5) Previous issue date: 2004 / Resumo: Segurança da Informação é fator chave para o desenvolvimento da sociedade. Diariamente quantidades massivas de dados são transportadas em redes de alta velocidade sem o suporte adequado de segurança criptográfica. Criptografia é infra-estrutura computacional e como tal está migrando para o hardware. Neste contexto a criação de um cripto-processador parametrizado utilizando tecnologia reconfigurável é de importância estratégica para o país. Esta dissertação apresenta estudos acerca da construção de tal cripto-processador, com os estudos e as implementações de vários mecanismos relacionados com dispositivos criptográficoso Foram implementados e testados em VHDe os algoritmos AES3 - FIPS4197 e ECC5 IEEE61363, rendendo aceleradores criptográficos de alto desempenho. Além disso, análises sobre a eficiência em hardware reconfigurável do algoritmo SHA -17 foram realizadas e seus resultados foram estendidos para toda família FIPS 180-2. O interfaceamento lógico e eletrônico do sistema também recebeu atenção nesta dissertação. No primeiro caso, um estudo de interfaces padrão para dispositivos criptográficos, ou tokens, baseados no PKCS8#11 foi realizado, rendendo uma implementação simplificada, mas compatível com este padrão. No caso do interfaceamento elétrico, diversas alternativas foram estudadas, resultando na escolha do sistema PCI PCI-SIG r.2.1 / Abstract: Information Security is a key factor for de development ofmodern society. Every day, massive amounts of data flow through high speed networks without proper cryptographic security support. Cryptography services belong to the computational infTastructure and as such they are migrating into computer' s hardware. In this context, the design of a parameterized crypto-processor that uses reconfigurable technology contributes to the development of such technology in the country. This dissertation presents cases studies on the construction of such crypto-processor, along with de analysis of many mechanisms for cryptographic devices. By using VHDL for both implementation and testing, the AES - FIPS 197 and the ECC - IEEE 1363 algorithms were implemented yielding high performance cryptographic accelerators. In addition, efficiency analysis of hash functions as SHA-! and others from its family were conducted for the resulting reconfigurable hardware. The logical and electrical interfaces received some attention too. In the first case, a brief study of cryptographic token interfaces, based on PKCS# 11, was done and a simplified compatible implementation was constructed. For the electrical interface many alternatives were analyzed and the PCI PCI-SIG r.2.! was chosen / Mestrado / Mestre em Ciência da Computação