Sistemas de recomendação foram propostos no início da década de 1990 com o objetivo de auxiliar seus usuários a lidar com a sobrecarga cognitiva criada com o advento da internet e o aumento constante de documentos. De lá para cá tais sistemas passaram a assumir vários outros papéis, tais como “auxiliar usuários a explorar”, “melhorar a tomada de decisão”, ou até mesmo “entreter”. Para atingir tais novos objetivos, o sistema necessita olhar para características do usuário que auxiliem no entendimento da tarefa desempenhada pelo usuário e como a recomendação pode auxiliar tal tarefa. Nesse sentido, propõe-se nessa tese uma integração entre estratégias de recomendação e de adaptação para criar um novo processo de recomendação adaptativa. É mostrado que tal integração pode melhorar a acurácia da recomendação, e dar bons resultados na retenção de usuários, e na interação destes com os sistemas. Para validar a abordagem, é implementado um protótipo para recomendação de filmes a serem utilizados em sala de aula. São também coletadas estatísticas de 78 usuários que participaram do experimento de avaliação da abordagem. / Recommender systems were proposed in early 90’s with the goal to help users deal with cognitive overload brought by the internet and the constant increase of documents. From there to now such systems have assumed many other roles like “help users to explore”, “improve decision making”, or even “entertain”. To accomplish such new goals, the system needs to look to user characteristics that help in understand what the user task is and how to adapt the recommendation to support such task. In this direction, it is proposed in this thesis an integration between recommender and adaptive strategies into a new process of adaptive recommendation. It is shown that such integration can improve recommendation accuracy and give good results to user retention, and interaction with the systems. To validate the approach, it is implemented a prototype to recommend movies to be used in a classroom. It is also collected some statistics about the 78 users who have participated of the experiment for evaluation of the new approach.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T21:29:21Z (GMT). No. of bitstreams: 1 Firmino_RaoniFassina_M.pdf: 582747 bytes, checksum: c50225f2dc75c4235a785d90a82d71b2 (MD5) Previous issue date: 2010 / Resumo: Esta dissertação concentra-se no atual momento de transição entre as atuais e as novas arquiteturas de processadores, oferecendo uma alternativa para minimizar o impacto desta mudança. Para tal utiliza-se a plataforma Java, que possibilita que o desenvolvimento de aplicações seja independente da arquitetura em que serão executadas. Considerando a arquitetura Cell B.E. como uma nova plataforma que promete desempenho elevado, este trabalho propõe melhorias na Máquina Virtual Java que propiciem um ganho de desempenho na execução de aplicações Java executadas sobre o processador Cell. O objetivo proposto é atingido por meio da utilização do ambiente disponível na própria plataforma Java, o Java Native Interface (JNI), para a implementação de interfaces entre bibliotecas nativas construídas para a arquitetura Cell - com a intenção de obter o máximo desempenho possível - e as aplicações Java. É proposto um modelo para porte e criação das interfaces para bibliotecas e mostra-se a viabilidade da abordagem proposta através de implementações de bibliotecas selecionadas, consolidando a metodologia utilizada. Duas bibliotecas foram portadas completamente como prova de conceito, uma multiplicação de matrizes grandes e o algoritmo RC5. A multiplicação de matrizes obteve um desempenho e escalablidade comparável ao código original em C e em escala muitas vezes superior ao código JNI para arquitetura x86 a ao código Java executando em arquiteturas x86 e Cell. O RC5 executou apenas aproximadamente 0,3 segundos mais lento que o código C original (perda citada em segundos pois se manteve constante independente do tempo levado para as diferentes configurações de execução) / Abstract: This dissertation focuses on the present moment of transition between the current and new processor architectures, offering an alternative to minimize the impact of this change. For this, we use the Java platform, which enables an architecture-independent application development. Considering the Cell BE architecture as a new platform that promises high performance, this paper proposes improvements in the Java Virtual Machine that provide performance gains in the execution of Java applications running on the Cell processor. The proposed objective is achieved through the use of the environment available on the Java platform itself, the Java Native Interface (JNI), to implement interfaces between native libraries built for the Cell architecture - with the intention of obtaining the maximum possible performance - and the Java applications. It is proposed a model to port and build interfaces to libraries and it shows the viability of the proposed methodology with the implementation of selected libraries, consolidating the used methodology. Two libraries were completely ported as proof of concept, a multiplication of large matrices and a RC5 algorithm implementation. The matrices multiplication achieved scalability and performance in the same basis as the native implementation and incomparable with JNI implementation targering x86 architecture and Java implementation running in x86 and Cell architectures. The RC5 was just 0.3 seconds slower than the original C code (the loss is put in seconds since it was constant, independent of the execution time taken by different configurations of execution) / Mestrado / Computação / Mestre em Ciência da Computação

[pt] Este trabalho apresenta uma ferramenta de suporte à programação literária. Para seu desenvolvimento foi criado um framework de prestação dos serviços básicos requeridos por este tipo de ferramenta. Desenvolvido segundo uma arquitetura que o tornou flexível, via uma linguagem de extensão para definição de macros; eficiente, via um núcleo em C++ otimizado para realizar as operações a nível de caracter; e portável, graças a uma implementação em C/C++ padrão, o framework se mostrou adequado aos objetivos propostos. O desenvolvimento sobre este framework validou as soluções adotadas, resultando em uma ferramenta de ótimo desempenho. / [en] This thesis presents a support tool for literate programming.Its development was preceded by a research of the basic facilites usually required for programs of this class. After that, a framework has been developed to offer those facilites. The framework was developed in standard C++, in such away that would guarantee its portability. Its effciency is due to an optimzed kernel which performs all character-level operations, and a well defined application program interface(API)assures its fexibility.On top of this framework an access layer has been created using a confi- guration language. This layer allows that, through small programs written in the configuration language, a user can adapt the tool for diferent literate programming styles like modular or WWW-enabled documentation.

Com o uso da tecnologia de Identificação por Radiofrequência (RFID), arquiteturas heterogêneas de processadores e as novas tendências da TV Digital e televisão via rede IP (IPTV) foi desenvolvido um sistema para montar, em tempo real, em forma automática, uma programação televisiva personalizada, baseada no perfil do grupo de usuários de um determinado televisor. Aplicações de vídeo sob demanda (VoD), IPTV e TV Digital permitem que cada telespectador possa assistir aos programas a qualquer momento, e assim construir sua grade de programação personalizada. Com um sistema de RFID é possível identificar as pessoas que se encontram próximas ao televisor. Com essas tecnologias unidas a um subsistema de análise de perfil, junto com os dados fornecidos pelos telespectadores no momento da contratação do serviço, e uma interface (middleware) para gerenciar os dados, é possível configurar um sistema que escolhe automaticamente quais programas e quais comerciais serão apresentados no aparelho de TV. Essa escolha é baseada no perfil dos telespectadores presentes naquele momento à frente da televisão e dos programas disponíveis naquele instante. As etiquetas (tags) de RFID usadas para o levantamento da audiência foram aparelhos celulares equipados com tecnologia Bluetooth, que possibilitam a identificação simultânea dos telespectadores via rádio. O algoritmo de recomendação é híbrido, possuindo componentes baseados em conteúdo e componentes colaborativos. O uso dos novos processadores heterogêneos exigiu o desenvolvimento de algoritmos paralelos que utilizam instruções do tipo SIMD, aceleradores e GPUs. Os sistemas que existem no momento (2011) nesta área, se limitam à identificação dos usuários mediante a digitação usando o controle remoto da TV e só identificam uma pessoa de cada vez. O uso de tecnologia por rádio, proposto nesta pesquisa, permite a identificação de várias pessoas simultaneamente, exigindo o desenvolvimento de padrões de um sistema completo baseado em grupos de perfis diferentes. A arquitetura do sistema elaborado está baseada no processador Cell BE e nas arquiteturas CPU+GPU, de forma que o tempo de execução do algoritmo fosse minimizado. / Merging together Radiofrequency identification (RFID), heterogeneous architectures of processors and new tendencies of the Digital TV (DTV) and television through IP network (IPTV), a system to create, automatically and in real-time, a personalized TV program schedule, based on the group of people profile next to a TV. Video-on-Demand (VoD) applications, IPTV and DTV allow each person to watch a chosen program at any moment and to its personalized programming guide. The RFID system allows the identification of the people next to the TV. This technology used with a profile analysis subsystem accessing a database of people preferences, and a middleware to manage the data, it is possible to set a system that automatically chooses with TV shows and with TV ads will be presented in the TV. This selection is based on the profile of the people next to the TV in that instant and on the available programs. The RFID tags used to detect the audience were the mobile phones equipped with Bluetooth, which allows the identification of its owner wirelessly. The recommendation algorithm is hybrid, containing collaborative and content-based components. The new heterogeneous processors demanded the development of parallel algorithms that use SIMD instruction, accelerators and GPUs. The systems that were available in the moment of this research (2011) were limited to the identification through login using remote control, one person by time. The use of RFID technology, proposed in this research, enables the simultaneous identification of many people at a time, demanding the development standards for group profiles recommendation. The systems architectures will be based on Cell BE processor and the conjunct CPU+GPU, focusing in the reduction of the algorithm execution time.

Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente, a fim de evitar uma rápida fragmentação do cubo e de não exceder o tempo máximo de espera de uma determinada aplicação. A partir dos algoritmos propostos é apresentada a definição de um servidor de processadores para o compartilhamento de uma máquina multiprocessadora hipercúbica em uma rede de estações de trabalho. Algumas funções deste servidor são implementadas por um protótipo denominado Sub-Cube RPC. Com o objetivo de analisar o comportamento da rede de estações em relação a inclusão de um novo recurso a ser compartilhado, foi desenvolvido, juntamente com o grupo de Avaliação de Desempenho ADMP, um simulador para o ambiente SUN/UNIX. Através desta ferramenta e dos tempos de resposta obtidos pelo protótipo do servidor desenvolvido é possível avaliar o custo que o tráfego gerado pelo servidor adiciona à rede, sendo possível a manipulação de parâmetros da rede e do servidor. Os resultados obtidos nas versões paralelas implementadas são comparados com o desempenho das versões seqüenciais. Para viabilizar esta comparação, todos os algoritmos seqüenciais encontrados na literatura também foram implementados na linguagem "C" no ambiente alvo UNIX e encontram-se em anexo. As versões paralelas foram implementadas utilizando-se recursos da própria rede de estações, através de diretivas socket, e também em Transputers na linguagem C paralela. O protótipo do servidor de processadores foi implementado como um servidor RPC para uma rede de estações UNIX também na linguagem "C". A ferramenta de simulação para o funcionamento do servidor foi implementada na linguagem "C" e seu sistema de entrada de dados e visualização utiliza a interface X-Windows. Com os resultados deste trabalho se pode ter uma boa idéia dos efeitos e das dificuldades encontradas na paralelização dos algoritmos de alocação e gerência de processadores para máquinas Hipercúbicas. As informações contidas no trabalho auxiliam na melhoria do tempo de resposta dos algoritmos seqüenciais atuais e no desenvolvimento de novos algoritmos com mais recursos e ainda assim viáveis em ambientes interativos, graças a utilização de paralelismo. O protótipo Sub-Cube RPC demonstra como os algoritmos estudados neste trabalho podem ser aplicados na construção de um servidor de processadores para máquinas multiprocessadas. O protótipo servirá como base para a implementação de um servidor semelhante no CPGCC/UFRGS, que colocará uma placa de Transputers à disposição da rede de estações do grupo de processamento paralelo. / In the last years massively parallel machines, build with hundreds of processors, are becoming an alternative for the construction of supercomputers. In this new concept of data processing, high performance is achieved by processor cooperation in the resolution of a problem. A great part of the commercial massively parallel machines utilizes the hypercubic topology to interconnect their multiple processors, or may be configured as hypercubes. A very interesting alternative for sharing the processing power of this machines is their utilization as aggregated computer in a network, serving various users [DUT 91]. In such environment, the hypercube behaves like a processor server, permitting the users to allocate part of its processors for local use. This result in a enhancement in the performance of workstation networks to the level of supercomputers and allow higher dimension hypercubes to be better utilized. In such environment the operating system is responsible for serving the users of a shared multiprocessor in a efficient way, not allowing a quick fragmentation of the hypercube and observing the maximal waiting time for the applications. The algorithms for processor allocation and management are responsible for obtention and control of one or more processors of the shared machine for the user's task execution. In this study, parallel versions of the most important algorithms for processor allocation and management in hypercubes found in the literature are proposed. The intention with this paralelization is to achieved a better response time of the more complex algorithms, making their use possible in a real time sharing environment. Because the allocation is considered the most important part of the processor server, the utilization of more complex algorithms allows a better utilization of the shared processors, resulting in a performance increase of the parallel machine. Based on the proposed algorithms, a processor server is defined for sharing a hypercubic multiprocessor in a workstation network. Some functions of this server are implemented in a prototype called Sub-Cube RPC. To analyze the behavior of the network, in relation to the inclusion of this new shared resource, a simulator for the SUN/UNIX environment has been developed together with the Performance Evaluation Group ADMP. With this tool and with the response times of the developed server prototype, it is possible to evaluate the cost of the additional network traffic generated by the server, with the possibility to change parameters of the server and network. The results obtained in the implemented parallel versions are compared with the performance of the sequential algorithms. To make this comparison possible all the sequential algorithms found in the literature are also implemented in the "C" language and can be found in annex. The parallel versions were implemented using network resources, through the socket directive, and also using Transputers in parallel "C". The processor server prototype was implemented as a RPC server for an UNIX network, also in the "C" language. The simulation tool was coded in "C" and the I/O interface use the X-Windows protocol. The results of this study may give a background about the effects and difficulties found in the pa ralelization of the allocation algorithms for the hypercubic machines. The information found in this study will help the operating system designer to obtain a better response time of the sequential algorithms found in the literature and in the development of new and more complex algorithms that will be still practicable in a real time environment due to parallelism utilization. The Sub-Cube RPC prototype demonstrates how the algorithms studied in this work can be applied in the construction of a processor server for multiprocessors. The prototype is the first step for the implementation of a similar server in the CPGCC/UFRGS that will share a Transputer board in a network of workstations from the parallel processing group.

Com o uso da tecnologia de Identificação por Radiofrequência (RFID), arquiteturas heterogêneas de processadores e as novas tendências da TV Digital e televisão via rede IP (IPTV) foi desenvolvido um sistema para montar, em tempo real, em forma automática, uma programação televisiva personalizada, baseada no perfil do grupo de usuários de um determinado televisor. Aplicações de vídeo sob demanda (VoD), IPTV e TV Digital permitem que cada telespectador possa assistir aos programas a qualquer momento, e assim construir sua grade de programação personalizada. Com um sistema de RFID é possível identificar as pessoas que se encontram próximas ao televisor. Com essas tecnologias unidas a um subsistema de análise de perfil, junto com os dados fornecidos pelos telespectadores no momento da contratação do serviço, e uma interface (middleware) para gerenciar os dados, é possível configurar um sistema que escolhe automaticamente quais programas e quais comerciais serão apresentados no aparelho de TV. Essa escolha é baseada no perfil dos telespectadores presentes naquele momento à frente da televisão e dos programas disponíveis naquele instante. As etiquetas (tags) de RFID usadas para o levantamento da audiência foram aparelhos celulares equipados com tecnologia Bluetooth, que possibilitam a identificação simultânea dos telespectadores via rádio. O algoritmo de recomendação é híbrido, possuindo componentes baseados em conteúdo e componentes colaborativos. O uso dos novos processadores heterogêneos exigiu o desenvolvimento de algoritmos paralelos que utilizam instruções do tipo SIMD, aceleradores e GPUs. Os sistemas que existem no momento (2011) nesta área, se limitam à identificação dos usuários mediante a digitação usando o controle remoto da TV e só identificam uma pessoa de cada vez. O uso de tecnologia por rádio, proposto nesta pesquisa, permite a identificação de várias pessoas simultaneamente, exigindo o desenvolvimento de padrões de um sistema completo baseado em grupos de perfis diferentes. A arquitetura do sistema elaborado está baseada no processador Cell BE e nas arquiteturas CPU+GPU, de forma que o tempo de execução do algoritmo fosse minimizado. / Merging together Radiofrequency identification (RFID), heterogeneous architectures of processors and new tendencies of the Digital TV (DTV) and television through IP network (IPTV), a system to create, automatically and in real-time, a personalized TV program schedule, based on the group of people profile next to a TV. Video-on-Demand (VoD) applications, IPTV and DTV allow each person to watch a chosen program at any moment and to its personalized programming guide. The RFID system allows the identification of the people next to the TV. This technology used with a profile analysis subsystem accessing a database of people preferences, and a middleware to manage the data, it is possible to set a system that automatically chooses with TV shows and with TV ads will be presented in the TV. This selection is based on the profile of the people next to the TV in that instant and on the available programs. The RFID tags used to detect the audience were the mobile phones equipped with Bluetooth, which allows the identification of its owner wirelessly. The recommendation algorithm is hybrid, containing collaborative and content-based components. The new heterogeneous processors demanded the development of parallel algorithms that use SIMD instruction, accelerators and GPUs. The systems that were available in the moment of this research (2011) were limited to the identification through login using remote control, one person by time. The use of RFID technology, proposed in this research, enables the simultaneous identification of many people at a time, demanding the development standards for group profiles recommendation. The systems architectures will be based on Cell BE processor and the conjunct CPU+GPU, focusing in the reduction of the algorithm execution time.

Sistemas embarcados baseados em processadores têm sido largamente aplicados em áreas críticas no que diz respeito à segurança de seres humanos e do meio ambiente. Em tais aplicações, que compreendem desde o controle de freio de carros a missões espaciais, pode ser necessária a execução confiável de todas as funcionalidades do sistema durante longos períodos e em ambientes desconhecidos, hostis ou instáveis. Mesmo em aplicações não críticas, nas quais a confiabilidade do sistema não é um requisito primordial, o usuário final deseja que seu produto apresente comportamento estável e livre de erros. Daí vem a importância de se considerar o auto-teste on-line no projeto dos sistemas embarcados atuais. Entretanto, a crescente complexidade de tais sistemas somada às fortes restrições a que eles estão sujeitos torna o projeto do auto-teste um problema cada vez mais desafiador. Em aplicações de tempo-real a dificuldade é ainda maior, uma vez que, além dos cuidados com as restrições do sistema alvo, deve-se levar em conta o atendimento dos requisitos temporais da aplicação. Entre as técnicas de auto-teste on-line atualmente pesquisadas, uma tem se destacado pela eficácia obtida a um baixo custo de projeto e sem grande impacto no atendimento dos requisitos e restrições do sistema: o auto-teste baseado em software (SBST – Software-Based Self-Test). Neste trabalho, é proposta uma metodologia para o projeto e aplicação de auto-teste on-line para processadores embarcados, considerando-se também aplicações de temporeal. Tal metodologia, denominada STEP (Self-Test for Embedded Processors), tem como base a técnica SBST e prevê o planejamento, a geração e a seleção de rotinas de teste para o processador alvo. O método proposto garante a execução periódica do autoteste, com o menor período permitido pela aplicação de tempo-real, e assegura o atendimento de todas as restrições do sistema embarcado. Além disso, a solução fornecida pelo método alcança uma boa qualidade de teste enquanto auxilia a redução de custos do sistema final. Como estudo de caso, a metodologia proposta é aplicada a diferentes arquiteturas de processadores Java e os resultados obtidos comprovam a eficiência da mesma. Por fim, é apresentada uma ferramenta que implementa a metodologia STEP, automatizando, assim, o projeto e a aplicação de auto-teste on-line para os processadores estudados. / Processor-based embedded systems have been widely used in safety-critical applications. In such applications, which include from cars break control to spatial missions, the whole system operation must be reliable during long periods even within unknown, hostile and unstable environments. In non-critical applications, system reliability is not a prime requirement, but the final user requires an error free product, with stable behavior. Hence, one can realize the importance of on-line self-testing in current embedded systems. Self-testing is becoming an important challenge due to the increasing complexity of the systems allied to their strong constraints. In real-time applications this problem becomes even more complex, since, besides meeting systems constraints, one must take into consideration the application timing requirements. Among all on-line self-testing techniques studied, Software-Based Self-Test (SBST) has been distinguished by its effectiveness, low-cost and small impact on system constraints and requirements. This work proposes a methodology for the design and implementation of on-line self-test in embedded processors, considering real-time applications. Such a methodology, called STEP (Self-Test for Embedded Processors), is based on SBST technique and encloses planning, generation and selection of test routines for the target processor. The proposed method guarantees periodical self-test execution, at the smallest period allowed by the real-time application, and ensures that all embedded system constraints are met. Furthermore, provided solution achieves high test quality while helping in the optimization of the costs of the final system. The proposed methodology is applied to different architectures of Java processors to demonstrate its efficiency. Finally, this work presents a tool that automates the design and implementation of on-line self-test in the studied processors by implementing the STEP methodology.

Sistemas embarcados baseados em processadores têm sido largamente aplicados em áreas críticas no que diz respeito à segurança de seres humanos e do meio ambiente. Em tais aplicações, que compreendem desde o controle de freio de carros a missões espaciais, pode ser necessária a execução confiável de todas as funcionalidades do sistema durante longos períodos e em ambientes desconhecidos, hostis ou instáveis. Mesmo em aplicações não críticas, nas quais a confiabilidade do sistema não é um requisito primordial, o usuário final deseja que seu produto apresente comportamento estável e livre de erros. Daí vem a importância de se considerar o auto-teste on-line no projeto dos sistemas embarcados atuais. Entretanto, a crescente complexidade de tais sistemas somada às fortes restrições a que eles estão sujeitos torna o projeto do auto-teste um problema cada vez mais desafiador. Em aplicações de tempo-real a dificuldade é ainda maior, uma vez que, além dos cuidados com as restrições do sistema alvo, deve-se levar em conta o atendimento dos requisitos temporais da aplicação. Entre as técnicas de auto-teste on-line atualmente pesquisadas, uma tem se destacado pela eficácia obtida a um baixo custo de projeto e sem grande impacto no atendimento dos requisitos e restrições do sistema: o auto-teste baseado em software (SBST – Software-Based Self-Test). Neste trabalho, é proposta uma metodologia para o projeto e aplicação de auto-teste on-line para processadores embarcados, considerando-se também aplicações de temporeal. Tal metodologia, denominada STEP (Self-Test for Embedded Processors), tem como base a técnica SBST e prevê o planejamento, a geração e a seleção de rotinas de teste para o processador alvo. O método proposto garante a execução periódica do autoteste, com o menor período permitido pela aplicação de tempo-real, e assegura o atendimento de todas as restrições do sistema embarcado. Além disso, a solução fornecida pelo método alcança uma boa qualidade de teste enquanto auxilia a redução de custos do sistema final. Como estudo de caso, a metodologia proposta é aplicada a diferentes arquiteturas de processadores Java e os resultados obtidos comprovam a eficiência da mesma. Por fim, é apresentada uma ferramenta que implementa a metodologia STEP, automatizando, assim, o projeto e a aplicação de auto-teste on-line para os processadores estudados. / Processor-based embedded systems have been widely used in safety-critical applications. In such applications, which include from cars break control to spatial missions, the whole system operation must be reliable during long periods even within unknown, hostile and unstable environments. In non-critical applications, system reliability is not a prime requirement, but the final user requires an error free product, with stable behavior. Hence, one can realize the importance of on-line self-testing in current embedded systems. Self-testing is becoming an important challenge due to the increasing complexity of the systems allied to their strong constraints. In real-time applications this problem becomes even more complex, since, besides meeting systems constraints, one must take into consideration the application timing requirements. Among all on-line self-testing techniques studied, Software-Based Self-Test (SBST) has been distinguished by its effectiveness, low-cost and small impact on system constraints and requirements. This work proposes a methodology for the design and implementation of on-line self-test in embedded processors, considering real-time applications. Such a methodology, called STEP (Self-Test for Embedded Processors), is based on SBST technique and encloses planning, generation and selection of test routines for the target processor. The proposed method guarantees periodical self-test execution, at the smallest period allowed by the real-time application, and ensures that all embedded system constraints are met. Furthermore, provided solution achieves high test quality while helping in the optimization of the costs of the final system. The proposed methodology is applied to different architectures of Java processors to demonstrate its efficiency. Finally, this work presents a tool that automates the design and implementation of on-line self-test in the studied processors by implementing the STEP methodology.

Esta dissertação tem por finalidade apresentar uma metodologia de injeção de falhas baseada em emulação de processadores. Os efeitos causados pela radiação em processadores, operando no espaço ou em altitudes elevadas, têm sido estudados na literatura para o desenvolvimento de mecanismos de tolerância a falhas. Com a crescente popularidade do uso de processadores comerciais, (COTS – do inglês, Commercial Off-The-Shelf), em aplicações críticas, uma série de preocupações tem surgido devido a falta de confiabilidade apresentada por estes sistemas. Sendo desprovidos de mecanismos de tolerância para melhor robustez em ambientes espaciais, estes dispositivos comerciais são mais suscetíveis aos efeitos da radiação. Neste contexto, técnicas de tolerância a falhas baseadas em software vêm sendo estudadas a fim de aumentar a confiabilidade desta abordagem. Para a devida validação de tais mecanismos de tolerância, o uso de técnicas de injeção de falhas é aplicável. Estas técnicas de injeção de falhas possuem uma série de limitações que podem inviabilizar a sua aplicabilidade, dependendo da abordagem utilizada. Fatores como custo, indisponibilidade da descrição de hardware – utilizada em técnicas de injeção de falhas por simulação ou emulação em FPGA (Field Programmable Gate Array), e o longo tempo necessário para execução dos experimentos, são alguns exemplos de limitações das técnicas disponíveis. Com base nisso, a metodologia de injeção de falhas alternativa apresentada neste trabalho, visa reduzir as limitações presentes nas mais diversas técnicas. Baseada na utilização de tradução dinâmica de instruções, para acelerar o processo de execução de aplicações em emuladores, a metodologia apresenta um modelo de falhas para efeitos transientes e permanentes, aplicáveis neste cenário. Como método de classificação dos efeitos observados neste processo, um modelo presente na literatura foi utilizado. Para validação desta metodologia, um injetor de falhas baseado no emulador QEMU foi desenvolvido. Posteriormente, um estudo de caso com o injetor de falhas foi realizado para três estruturas de software distintas executando individualmente no processador MIPS 24kc, representando três níveis de complexidade distintos: sistema operacional Linux, sistema de tempo real, (RTEMS – do inglês, Real-Time Operating System), e uma aplicação dedicada. Cada sistema foi submetido a uma campanha de injeção de falhas transientes para emulação de efeitos singulares (SEU – do inglês, Single Event Upset). Como alvo de falhas, foram selecionados os registradores do processador e a memória de dados. Por fim, as análises obtidas através dos experimentos mostraram os diferentes efeitos observados para os três níveis de complexidade dos softwares executados. Além disso, se pôde avaliar o desempenho do injetor de falhas, disponibilizando ao final do trabalho uma ferramenta para o auxílio no desenvolvimento de técnicas de tolerância a falhas por software. / This dissertation aims to present a fault injection methodology based on microprocessor emulation. The effects caused by radiation in microprocessors, operating in space or at high altitudes, have been studied in the literature for the development of fault tolerance mechanisms. With the growing popularity of COTS (Commercial Off-The-Shelf) processors usage, in critical applications, a number of concerns have arisen due to the lack of reliability, presented in these systems. Due to the lack of fault tolerance mechanisms, these COTS devices are more susceptible to radiation effects. In this context, software-based fault tolerance techniques have been studied in the literature in order to increase the reliability of this approach. To validate such fault tolerance mechanisms, the use of fault injection techniques is applicable. These fault injection techniques have several limitations which can preclude their applicability, depending on of its design approach. Factor such as cost, unavailability of hardware description – used by fault injection techniques based on simulation or emulation with FPGA (Field Programmable Gate Array), and the long time demanded to execute experiments, are some examples of limitations in the available techniques. Based on this, the alternative fault injection methodology presented in this work aims to reduce these limitations. Based on the dynamic translation of instructions usage to accelerate the execution of application on emulators, the methodology presents a fault model for transient and permanent faults applicable in this scenario. As a classification method of the observed effects in this process, a model in the literature has been used. To validate this methodology, a fault injector based on the QEMU emulator was implemented. Later, a case study with the fault injector was performed for three software structures running at a time on a MIPS 24kc processor, representing three different levels of complexity: Linux operating system, RTEMS (Real-Time Operating System), and a dedicated application. Each system was submitted to a fault injection campaign emulating Single Event Upsets (SEUs). As fault targets it was selected the processor registers and the data memory. Finally, the analysis obtained with the experiments showed the different effects observed for the three levels of complexity. Besides that, the fault injector performance could be evaluated providing in the end a tool to help in the development of software-based fault injection techniques.