Sumario: 1- Introducción 2- Análisis del problema 3- Estado del arte 4- Solución propuesta 5- Implementación 6- Experiencias de uso 7- Conclusiones.

No description available.

Made available in DSpace on 2013-08-07T18:42:45Z (GMT). No. of bitstreams: 1 000418219-Texto+Completo-0.pdf: 4033858 bytes, checksum: 2661cfd90512a0fe826582c0489e6ce1 (MD5) Previous issue date: 2009 / MPSoCs are multi-processor systems integrated in a single chip. They are a trend in VLSI circuit design, since they minimize the design productivity crisis represented by the gap between the silicon technol-ogy and the actual SoC design capacity. Examples of MPSoCs include those proposed by Intel and Tilera, composed by 80 and 64 processing elements respectively. MPSoCs may employ NoCs to integrate several processors, memories, as well as specific hardware cores. NoCs may be used to replace busses, due to their ad-vantages of higher scalability and communication parallelism. The target architecture of the present work is a NoC-based heterogeneous MPSoC supporting hard-ware task execution through embedded reconfigurable logic, together with software tasks executed by pro-grammable processors. One of the processors of the target architecture, named manager processor, is respon-sible for system resources management, task scheduling, task mapping, and configuration control. Task map-ping defines the placement of a new task into the system. Most works in literature propose static mapping techniques defined at design time, where all application tasks are mapped simultaneously. This static map-ping is not appropriate for dynamic workloads scenarios. Since applications running in MPSoCs may con-tain a varying number of tasks, and since their number may exceed the available resources, task mapping at run-time is necessary. Such task mapping method is named dynamic task mapping. The present work investigates the performance of heuristics for dynamic task mapping, targeting NoC congestion minimization. Tasks are mapped on demand, according to the communication requests and the load in NoC channels. The implemented algorithms employ a greedy approach, where tasks are indivi-dually mapped. The mapping decision is based on local information, considering the communication con-straints of the requested task. The algorithm used as the reference mapping strategy in experiments maps a task into the first free resource available. Four congestion-aware mapping heuristics are proposed. Through the experiments employing RTL abstraction level modeling, it is possible to observe reductions of 31% in channel load distribution, 15% in average latency, and 87% in congestion level. These results demonstrate the efficiency of proposed heuristics. / MPSoCs são sistemas multiprocessados integrados na forma de um SoC. Eles são tendência no projeto de circuitos VLSI, pois minimizam a crise de produtividade de projeto, representada pelo descompasso entre a capacidade da tecnologia do silício e a capacidade atual de projeto de SoCs. Cita-se como exemplo de MPSoCs os propostos pela Intel e pela Tilera, compostos respectivamente por 80 e 64 núcleos de processa-mento. MPSoCs podem empregar NoCs para integrar diversos processadores, memórias, bem como núcleos de hardware específicos. O uso de NoCs deve-se a suas vantagens em relação a barramentos, entre as quais maior escalabilidade e paralelismo na comunicação. A arquitetura alvo do presente trabalho consiste em um MPSoC heterogêneo, com utilização de NoC como meio interconexão entre os elementos de processamento, suportando a execução de tarefas de hardware via lógica reconfigurável, e a execução de tarefas de software via processadores. Um dos processadores da arquitetura alvo, denominado processador gerente, é responsável por: gerência da ocupação dos recursos do sistema, escalonamento, mapeamento, e configuração de tarefas. O mapeamento de tarefas define a posição de uma dada tarefa no sistema. A maioria dos trabalhos encontrados na literatura propõe técnicas de mapeamento estático, definido em tempo de projeto, no qual todas as tarefas de uma dada aplicação são mapeadas simultaneamente. Este mapeamento estático não é adequado para cenários com carga dinâmica de tarefas. Dado que aplicações executando em um MPSoC podem possuir um número variável de tarefas, e que tal número pode exceder os recursos disponíveis, é necessário realizar o mapeamento de tarefas em tempo de execução, mapeamento este denominado de mapeamento dinâmico.O presente trabalho investiga o desempenho de heurísticas para mapeamento dinâmico de tarefas, com o objetivo de minimizar congestionamentos em NoCs. As tarefas são mapeadas sob demanda, de acordo com as requisições de comunicação e com a ocupação dos canais da NoC. Os algoritmos implementados aplicam estratégias gulosas, onde as tarefas são mapeadas uma por vez. Para isso, a decisão é baseada na informação local da aplicação, apenas relacionada à tarefa requisitada. O algoritmo utilizado como referência nos experimentos mapeia uma dada tarefa no primeiro recurso livre encontrado. Quatro heurísticas congestion-aware são propostas. Através de experimentos realizados com base na modelagem do sistema no nível RTL, pode-se observar redução de 31% na carga nos canais da NoC, de 15% na latência média, e de até 87% no nível médio de congestionamento. Tais resultados demonstram a eficiência das heurísticas propostas.

Made available in DSpace on 2013-08-07T18:43:36Z (GMT). No. of bitstreams: 1 000422461-Texto+Completo-0.pdf: 1656872 bytes, checksum: 4520cf1ef2435e86327deed3e89baed9 (MD5) Previous issue date: 2009 / Model trees are a particular case of decision trees employed to solve regression problems, where the variable to be predicted is continuous. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is a NPComplete problem, traditional model tree induction algorithms make use of a greedy top-down divideand- conquer strategy, which may not converge to the global optimal solution. In this work, we propose the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to global optimal solutions. We test the predictive performance of this new approach using public UCI data sets, and we compare the results with traditional greedy regression/model trees induction algorithms. Results show that our approach presents a good tradeoff between predictive performance and model comprehensibility, which may be crucial in many data mining applications. / Árvores-modelo são um caso particular de árvores de decisão aplicadas na solução de problemas de regressão, onde a variável a ser predita é contínua. Possuem a vantagem de apresentar uma saída interpretável, auxiliando o usuário do sistema a ter mais confiança na predição e proporcionando a base para o usuário ter novos insights sobre os dados, confirmando ou rejeitando hipóteses previamente formadas. Além disso, árvores-modelo apresentam um nível aceitável de desempenho preditivo quando comparadas à maioria das técnicas utilizadas na solução de problemas de regressão. Uma vez que gerar a árvore-modelo ótima é um problema NP-Completo, algoritmos tradicionais de indução de árvores-modelo fazem uso da estratégia gulosa, top-down e de divisão e conquista, que pode não convergir à solução ótima-global. Neste trabalho é proposta a utilização do paradigma de algoritmos evolutivos como uma heurística alternativa para geração de árvores-modelo. Esta nova abordagem é testada por meio de bases de dados de regressão públicas da UCI, e os resultados são comparados àqueles gerados por algoritmos gulosos tradicionais de indução de árvores-modelo. Os resultados mostram que esta nova abordagem apresenta uma boa relação custo-benefício entre desempenho preditivo e geração de modelos de fácil interpretação, proporcionando um diferencial muitas vezes crucial em diversas aplicações de mineração de dados.

Made available in DSpace on 2013-08-07T18:43:06Z (GMT). No. of bitstreams: 1 000422345-Texto+Completo-0.pdf: 5665717 bytes, checksum: 5cf597a5b5d81b97f33438b9e1b499e0 (MD5) Previous issue date: 2009 / The increase in the number of transistors on a single chip has brought new design challenges, among them, how to design new circuits using this available number of transistors. The reuse of Intellectual Property (IP) cores enables the design of such complex systems. The design of a system through the reuse of processors results in a MPSoCs (Multiprocessor System on Chip). MPSoCs are becoming increasingly popular in embedded systems for the high degree of performance and flexibility they permit. In recent years universities and companies have been developing large projects in multiprocessing. The goal of the work is to develop a homogenous MPSoC, using a NoC as the communication infrastructure. NoC is employed due to its higher degree of parallelism and scalability, when compared to busses. The performance of the implemented MPSoC is evaluated, demonstrating the benefits when this architecture is used to design embedded applications. / O aumento do número de transistores em um único chip trouxe novos desafios de projeto, entre eles como aproveitar efetivamente este elevado número de componentes. Uma das formas encontradas é através do reuso de módulos de hardware. Quando estes módulos de hardware são processadores, temos multiprocessamento em chip, resultando nos MPSoCs (Multiprocessor System on Chip). Os MPSoCs estão se tornando elementos comuns em sistemas embarcados, devido ao alto desempenho e à flexibilidade que eles trazem ao projeto. Nos últimos anos universidades e empresas vem desenvolvendo grandes projetos em multiprocessamento. O presente trabalho tem por objetivo desenvolver um MPSoC homogêneo, com interconexão por NoC. A motivação para a adoção de NoCs reside no maior paralelismo e escalabilidade desta infraestrutura de comunicação, quando comparado a barramentos. O desempenho do MPSoC desenvolvido é avaliado, demonstrando-se os benefícios em se utilizar este tipo de arquitetura no projeto de sistemas embarcados.

Made available in DSpace on 2013-08-07T18:43:25Z (GMT). No. of bitstreams: 1 000445541-Texto+Completo-0.pdf: 1627180 bytes, checksum: 184a4b2054d700b987b074f0fcdf3122 (MD5) Previous issue date: 2011 / The definitory context is part of a text or utterance that provides information about a concept based on its use. The extraction of definitions from texts is an important task in various applications. Several papers present this feature as an aid in the construction of ontologies, in the development of material for aid in translation, in question answering systems, in creation of glossaries, dictionaries, among others. Thus, this study proposes set of heuristics to make the automatic extraction of potentially definitory contexts contained in Portuguese texts. The results of these heuristics were evaluated by terminologists and obtained 35. 1 % F-measure when applied in a General Geology corpus and 51. 7 % F-measure when applied in a General Chemistry corpus, reducing in both more than 50%of the amount of contexts to be examined by a specialist compared with the contexts extraction through a concordancer. / O contexto definitório é a parte de um texto ou de um enunciado que fornece informação sobre um conceito, com base em seu uso. A extração de contextos definitórios a partir de textos é uma tarefa importante em várias aplicações. Diversos trabalhos usam este recurso como auxílio na construção de ontologias, no desenvolvimento de material de auxílio à tradução, na elaboração de sistemas de perguntas e respostas, na criação de glossários, dicionários, entre outros. Nesse sentido, este trabalho propõe um conjunto de heurísticas para fazer a extração automática de contextos potencialmente definitórios em textos de língua portuguesa. Os resultados dessas heurísticas foram avaliados por terminólogos. Os resultados mostram 35,1% de F-measure quando o conjunto de heuristicas foi aplicado a um corpus de Geologia Geral e 51,7% de F-measure quando aplicado a um corpus de Química Geral. Isso proporcionou uma redução, em ambos os corpus, de mais de 50% da quantidade de contextos para serem analisados pelo especialista, comparando-se com a extração de contextos em um concordanciador.

Made available in DSpace on 2015-12-09T01:03:58Z (GMT). No. of bitstreams: 1 000476572-Texto+Completo-0.pdf: 1895232 bytes, checksum: d360d64653c8369496f6a15db1b7c15f (MD5) Previous issue date: 2015 / As robotics becomes more common and people start to use it in routine tasks, dependability becomes more and more relevant to create trustworthy solutions. A commonly used approach to provide reliability and availability is the use of multi robots instead of a single robot. However, in case of a large teams of robots (tens or more), determining the system status can be a challenge. This work presents a runtime monitoring solution for Multi Robotic Systems. It integrates Nagios IT Monitoring tool and ROS robotic middleware. One of the potential advantages of this approach is that the use of a consolidated IT infrastructure tool enables the reuse of several relevant features developed to monitor large datacenters. Another important advantage of that this solution does not require additional software at the robot side. The experimental results demonstrate that the proposed monitoring system has a small performance impact on the robot and the monitoring server can easily support hundreds or even thousands of monitored robots. / À medida que a robótica se torna mais comum e as pessoas começam a utilizá-la em suas tarefas de rotina, dependabilidade torna-se cada vez mais importante para a construção de uma solução digna de confiança. Uma abordagem comum de prover confiabilidade e disponibilidade é o uso de multi robôs ao invés de um único robô devido a sua redundância intrísica. Entretanto, no caso de um grande time de robôs (dezenas ou mais), uma tarefa aparentemente simples como a determinação do status do sistema pode se tornar um desafio. Este trabalho apresenta uma ferramenta de monitoramento de sistemas multi robôs em tempo de execução. Esta solução integra a ferramenta de monitoramento de TI Nagios com o middleware robótico ROS sem a necessidade de instalação de software adicional no robô. O uso de uma ferramenta de TI consolidada permite o reuso de diversas funcionalidades relevantes já empregadas amplamente no monitoramento de datacenters. Os resultados experimentais demonstram que a solução proposta tem um baixo impacto no desempenho do robô e o servidor de monitoramento pode facilmente monitorar centenas ou até milhares de robôs ao mesmo tempo.

Made available in DSpace on 2015-12-15T01:05:04Z (GMT). No. of bitstreams: 1 000476711-Texto+Completo-0.pdf: 1459361 bytes, checksum: 48f64a1e41d4416a6b1e434eaf5ed4d3 (MD5) Previous issue date: 2015 / The need of more processing capacity for embedded systems nowadays is pushing the research of MPSoCs with tens or hundreds of processors. These characteristics bring design challenges such as scalability and dependability. Such complex systems must have fault tolerant methods to ensure acceptable reliability and availability. This way, the user is not exposed to significant data losses, malfunctioning and even the total system failure. Considering this technology trend, the present work proposes a fault tolerance method with focus in fault recovery. The method uses concepts largely explored in distributed systems to solve the problem of permanent failures in the processing elements of MPSoCs. The implementation is exclusively in software, and recovers the system exposed to a permanent failure on processing elements, reallocating all tasks that were executing in the faulty element to a healthy processing element. The failed application tasks restart their executions since there is no context saving, enabling a lightweight method. The experiments are performed in the HeMPS platform, evaluating the most relevant parameters as recovery time, communication bandwidth impact, scalability and others. In the absence of faults, the proposed protocol has 21 Kbytes of memory area (20% more compared to the original kernel) and no overhead in terms of execution time. In the presence of faults, the results demonstrate total recovery times from 0. 2ms to 1ms, depending on the number of reallocated tasks (1 to 7). The biggest impact in the protocol time is related with the reallocation task phase. / A pesquisa em MPSoCs (do inglês, Multiprocessor System on Chip) tem sido motivada pela necessidade crescente de maior capacidade de processamento das aplicações de sistemas embarcados. Devido à esta tendência, os MPSoCs tornam-se cada vez mais complexos e miniaturizados. Estas características trazem associados desafios como escalabilidade e dependabilidade. O sistema que tem a necessidade de ser confiável e estar disponível em todo o seu tempo operação precisa ser tolerante a falhas a ponto de recuperar-se automaticamente. Dessa forma o usuário não será exposto a perdas de informação, execução malsucedida ou até mesmo a falha total do sistema. Este trabalho propõe um método de tolerância a falhas com foco na recuperação de falhas. O método utiliza conceitos utilizados em computação distribuída para solucionar o problema de falhas permanentes em elementos de processamento de um MPSoCs. O método proposto, implementado exclusivamente em software, recupera um sistema exposto a uma falha permanente de um elemento de processamento, realizando uma realocação das tarefas que estavam sendo executadas pelo elemento que falhou para um elemento de processamento saudável do sistema. As tarefas da aplicação que falharam devem reiniciar suas execuções do ponto de partida dado que o contexto da execução não é salvo, mantendo assim um baixo overhead no sistema, como demonstrado nos resultados obtidos. Os experimentos foram realizados na plataforma HeMPS com uma avaliação dos parâmetros mais relevantes como tempo de recuperação, impacto em banda de comunicação, escala e outros, que justificam a viabilidade e as vantagens do método proposto. Na ausência de falhas, o protocolo proposto não altera o tempo de execução, porém aumenta o tamanho de memória do kernel para 21 Kbytes, 20% de acréscimo comparado com o kernel original. Os resultados obtidos na presença de falhas mostram que o tempo total de recuperação de falhas do método é de 0,2ms a 1ms, dependendo do número de tarefas realocadas devido ao PE defeituoso. O maior impacto de tempo no protocolo se dá com a etapa de realocação de tarefas.

Made available in DSpace on 2014-06-06T02:01:22Z (GMT). No. of bitstreams: 1 000458539-Texto+Completo-0.pdf: 3705446 bytes, checksum: de3d802acba0f10f03298ee0277b51b1 (MD5) Previous issue date: 2014 / The usefulness of data mining and the process of Knowledge Discovery in Databases (KDD) has increased its importance as grows the volume of data stored in large repositories. A promising area for knowledge discovery concerns oil prospection, in which data used differ both from traditional and geographical data. In palaeogeographic data, temporal dimension is treated according to the geologic time scale, while the spatial dimension is related to georeferenced data, i. e. , latitudes and longitudes on Earth’s surface. This approach differs from that presented by spatio-temporal data mining algorithms found in literature, arising the need to evolve the existing ones to the context of this research. This work presents the development of a solution to employ a density-based spatio-temporal algorithm for mining palaeogeographic data on the Earth’s surface. An evolved version of the ST-DBSCAN algorithm was implemented in Java language making use of Weka API, where improvements were carried out in order to allow the data mining algorithm to solve a variety of research problems identified. A set of experiments that validate the proposed implementations on the algorithm are presented in this work. The experiments show that the solution developed allow palaeogeographic data mining by applying appropriate formulas for calculating distances over the Earth’s surface and, at the same time, treating the temporal dimension according to the geologic time scale. / O uso da mineração de dados e do processo de descoberta de conhecimento em banco de dados (Knowledge Discovery in Databases (KDD)) vem crescendo em sua importância conforme cresce o volume de dados armazenados em grandes repositórios. Uma área promissora para descoberta do conhecimento diz respeito à prospecção de petróleo, onde os dados usados diferem tanto de dados tradicionais como de dados geográficos. Nesses dados, a dimensão temporal é tratada de acordo com a escala de tempo geológico, enquanto a escala espacial é relacionada a dados georeferenciados, ou seja, latitudes e longitudes projetadas na superfície terrestre. Esta abordagem difere da adotada em algoritmos de mineração espaço-temporal presentes na literatura, surgindo assim a necessidade de evolução dos algoritmos existentes a esse contexto de pesquisa. Este trabalho apresenta o desenvolvimento de uma solução para uso do algoritmo de mineração de dados espaço-temporais baseado em densidade ST-DBSCAN para mineração de dados paleogeográficos na superfície terrestre. O algoritmo foi implementado em linguagem de programação Java utilizando a API Weka, onde aperfeiçoamentos foram feitos a fim de permitir o uso de mineração de dados na solução de problemas de pesquisa identificados. Como resultados, são apresentados conjuntos de experimentos que validam as implementações propostas no algoritmo. Os experimentos demonstram que a solução desenvolvida permite a mineração de dados paleogeográficos com a aplicação de fórmulas apropriadas para cálculo de distâncias sobre a superfície terrestre e, ao mesmo tempo, tratando a dimensão temporal de acordo com a escala de tempo geológico.

Made available in DSpace on 2013-08-07T18:42:18Z (GMT). No. of bitstreams: 1 000406064-Texto+Completo-0.pdf: 2136241 bytes, checksum: 1ec360a68cfe28f759f1832832dffb38 (MD5) Previous issue date: 2006 / The Web Usage Mining (WUM) applies data mining techniques to discover web usage patterns from Web server logs. The WUM process is composed by three major phases: pre-processing (where data is collected, cleaned and transformed), pattern discovery (in which mining algorithms are applied), and pattern analysis (where resulting patterns are analyzed). The categorization of visitor’s behavior based on their interaction in the web site is a key issue in WUM. In the E-learning area this topic becomes more relevant due to the lack of face-to-face contact between students and professors, given the physical distance, as well as the semantical gap between URLs and corresponding application events. Clustering, which subject of this research, is a mining technique that aims at grouping objects on basis of high inter-group similarity and low inter-group similarity. Several works leverage clustering techniques with the purpose of characterizing web user behavior during navigation. However, most of the works do not consider the meaning of visited URLs in the application domain, when measuring similarity between web sessions. Page semantics is frequently considered in the pre-processing phase, in data enrichment tasks, in which URLs are mapped into domain concepts. This approach is static in the sense that a new perspective of a URL (e. g. more generalized concept), to obtain better clustering results, often implies re-processing data. In addition to that, the correct clustering technique execution is a complex task which includes data preparation and transformation according to the mining objectives in such way interesting patterns can be found. Considering these problems, this research proposes a clustering mechanism and an interpretation mechanism as a way to characterize student’s behavior in a Web course. These mechanisms aim make the clustering technique execution and group analysis easy to a non data mining expert person. The proposed mechanisms are based in a domain taxonomy representing the domain events for addressing the semantic gap between URLs and application events. The clustering mechanism considers the similarity between visited pages as a way to improve the quality of clustering results. The proposed interpretation mechanism allows visualize the characteristics for each group, according to the clustering objective, as well as inspects groups dynamically considering the different levels of abstraction for application events in the domain taxonomy. These mechanisms establish the basis for categorization of web user behavior, for which a prototype was developed. / Um dos principais problemas evidenciados no domínio da Educação a Distância (EAD) é a falta de percepção que os instrutores de cursos Web têm quanto à interação dos alunos durante o processo de aprendizado. Este problema é mais fortemente evidenciado no ambiente da EAD devido ao pouco contato entre os instrutores e os alunos, dadas as limitações dos ca°nais de comunicação, e à falta de semântica no registro das páginas acessadas, em relação ao seu significado no domínio da aplicação. A Mineração do Uso da Web (MUW) oferece técnicas de mineração de dados que permitem descobrir padrões de utilização da Web para melhor entender e servir as necessidades das aplicações. O processo de MUW é composto de etapas, a saber: préprocessamento, descoberta de padrões e análise de padrões. Várias técnicas podem ser aplicadas na etapa de descoberta de padrões. A técnica de agrupamento, foco deste trabalho, destaca-se por agregar valor nesta questão, pois tende a estabelecer grupos de usuários que mostram padrões de comportamento semelhantes. O agrupamento de sessões Web tem impulsionado uma grande área de pesquisa que visa caracterizar os usuários com base na navegação na Web. Porém, nenhum trabalho foi encontrado que aborde a similaridade entre as páginas considerando a semântica dos eventos da aplicação quando computando a similaridade entre as sessões Web. Além disso, a correta aplicação da técnica de agrupamento é uma tarefa complexa que envolve desde a preparação dos dados até a escolha do algoritmo de agrupamento, além de estar fortemente associada à complexidade do processo de descoberta de conhecimento. Dados os problemas identificados, este trabalho propõe mecanismos de agrupamento e de interpretação de padrões que facilitem, respectivamente, a aplicação da técnica de agrupamento e a análise dos grupos por pessoas leigas, visando auxiliar na caracterização das sessões de aprendizado em um ambiente de EAD. Estes mecanismos fazem uso de uma taxonomia como forma de agregar semântica aos eventos do domínio, reduzindo assim a necessidade de retorno à etapa de pré-processamento. O mecanismo de agrupamento proposto visa facilitar a aplicação da técnica de agrupamento e aumentar a qualidade dos grupos, considerando para isso a similaridade entre as páginas com base na semântica dos eventos do domínio. O mecanismo de interpretação proposto permite representar os grupos visualmente, de modo condizente com o objetivo do agrupamento, bem como inspecionar dinamicamente os grupos formados considerando os diferentes níveis de abstração das páginas no domínio da aplicação. Foi desenvolvido um ambiente de apoio para auxiliar o intrutor durante a execução das etapas da MUW visando a facilitar a aplicação do agrupamento e a análise das sessões de aprendizado.