A ferramenta ChipCflow vem sendo desenvolvida nos últimos quatro anos, inicialmente a partir de um projeto de arquitetura a fluxo de dados dinâmico em hardware reconfigurável, mas agora como uma ferramenta de compilação. Ela tem como objetivo a execução de algoritmos por meio do modelo de arquitetura a fluxo de dados associado ao conceito de dispositivos parcialmente reconfiguráveis. Sua característica principal é acelerar o tempo de execução de programas escritos em Linguagem de Programação de Alto Nível (LPAN), do inglês, High Level Languages, em particular nas partes mais intensas de processamento. Isso é feito por meio da implementação dessas partes de código diretamente em hardware reconfigurável - utilizando a tecnologia Field-programmable Gate Array (FPGA) - aproveitando ao máximo o paralelismo considerado natural do modelo a fluxo de dados e as características do hardware parcialmente reconfigurável. Neste trabalho, o objetivo é a prova de conceito do processo de partição e do protocolo de comunicação entre as partições definidas a partir de um Grafo de Fluxo de Dados (GFD), para a execução direta em hardware reconfigurável utilizando Reconfiguração Parcial Dinâmica (RPD). Foi necessário elaborar um mecanismo de partição e protocolo de comunicação entre essas partições, uma vez que a RPD insere características tecnológicas limitantes não encontradas em hardwares reconfiguráveis mais tradicionais. O mecanismo criado se mostrou parcialmente adequado à prova de conceito, significando a possibilidade de se executar GFDs na plataforma parcialmente reconfigurável. Todavia, os tempos de reconfiguração inviabilizaram a proposta inicial de se utilizar RPD para diminuir o tempo de tag matching dos GFDs dinâmicos / The ChipCflow tool has been developed over the last four years, initially from an architectural design the flow of Dynamic Data in reconfigurable hardware, but now as a compilation tool. It aims to run algorithms using the model of the data flow architecture associated with the concept of partially reconfigurable devices. Its main feature is to accelerate the execution time of programs written in High Level Languages, particularly in the most intense processing. This is done by implementing those parts of code directly in reconfigurable hardware - using FPGA technology - leveraging the natural parallelism of the data flow model and characteristics of the partially reconfigurable hardware. In this work, the main goal is the proof of concept of the partition process and protocol communication between the partitions defined from Data Flow Graph for direct execution in reconfigurable hardware using Active Partial Reconfiguration. This required a mechanism to partition and a protocol for communication between these partitions, since the Active Partial Reconfiguration inserts technological features limiting not found in traditional reconfigurable hardware. The mechanism developed is show to be partially adequate to the proof of concept, meaning the ability to run Data Flow Graphs in a platform that is partially reconfigurable. However, the reconfiguration time inserts a great overhead into the execution time, which made the proposal of the use of Active Partial Reconfiguration to decrease the time matching Data Flow Graph unfeasible

Este trabalho de pesquisa tem por objetivo o desenvolvimento de um coprojeto de hardware/software para o algoritmo de correlação de imagens visando atingir um ganho de desempenho com relação à implementação totalmente em software. O trabalho apresenta um comparativo entre um conjunto bastante amplo e significativo de configurações diferentes do soft-processor Nios II implementadas em FPGA, inclusive com a adição de novas instruções dedicadas. O desenvolvimento do co-projeto foi feito com base em uma modificação do método baseado em profiling adicionando-se um ciclo de desenvolvimento e de otimização de software. A comparação foi feita com relação ao tempo de execução para medir o speedup alcançado durante o desenvolvimento do co-projeto que atingiu um ganho de desempenho significativo. Também analisou-se a influência de estruturas de hardware básicas e dedicadas no tempo de execução final do algoritmo. A análise dos resultados sugere que o método se mostrou eficiente considerando o speedup atingido, porém o tempo total de execução ainda ficou acima do esperado, considerando-se a necessidade de execução e processamento de imagens em tempo real dos sistemas de navegação robótica. No entanto, destaca-se que as limitações de processamento em tempo real estão também ligadas as restrições de desempenho impostas pelo hardware adotado no projeto, baseado em uma FPGA de baixo custo e capacidade média / This work presents a FPGA based hardware/software co-design for image normalized cross correlation algorithm. The main goal is to achieve a significant speedup related to the execution time of the all-software implementation. The co-design proposed method is a modified profiling-based method with a software development step. The executions were compared related to execution time resulting on a significant speedup. To achieve this speedup a comparison between 21 different configurations of Nios II soft-processor was done. Also hardware influence on execution time was evaluated to know how simple hardware structures and specific hardware structures influence algorithm final execution time. Result analysis suggest that the method is very efficient considering achieved speedup but the final execution time still remains higher, considering the need for real time image processing on robotic navigation systems. However, the limitations for real time processing are a consequence of the hardware adopted in this work, based on a low cost and capacity FPGA

Este trabalho de pesquisa tem por objetivo o desenvolvimento de um coprojeto de hardware/software para o algoritmo de correlação de imagens visando atingir um ganho de desempenho com relação à implementação totalmente em software. O trabalho apresenta um comparativo entre um conjunto bastante amplo e significativo de configurações diferentes do soft-processor Nios II implementadas em FPGA, inclusive com a adição de novas instruções dedicadas. O desenvolvimento do co-projeto foi feito com base em uma modificação do método baseado em profiling adicionando-se um ciclo de desenvolvimento e de otimização de software. A comparação foi feita com relação ao tempo de execução para medir o speedup alcançado durante o desenvolvimento do co-projeto que atingiu um ganho de desempenho significativo. Também analisou-se a influência de estruturas de hardware básicas e dedicadas no tempo de execução final do algoritmo. A análise dos resultados sugere que o método se mostrou eficiente considerando o speedup atingido, porém o tempo total de execução ainda ficou acima do esperado, considerando-se a necessidade de execução e processamento de imagens em tempo real dos sistemas de navegação robótica. No entanto, destaca-se que as limitações de processamento em tempo real estão também ligadas as restrições de desempenho impostas pelo hardware adotado no projeto, baseado em uma FPGA de baixo custo e capacidade média / This work presents a FPGA based hardware/software co-design for image normalized cross correlation algorithm. The main goal is to achieve a significant speedup related to the execution time of the all-software implementation. The co-design proposed method is a modified profiling-based method with a software development step. The executions were compared related to execution time resulting on a significant speedup. To achieve this speedup a comparison between 21 different configurations of Nios II soft-processor was done. Also hardware influence on execution time was evaluated to know how simple hardware structures and specific hardware structures influence algorithm final execution time. Result analysis suggest that the method is very efficient considering achieved speedup but the final execution time still remains higher, considering the need for real time image processing on robotic navigation systems. However, the limitations for real time processing are a consequence of the hardware adopted in this work, based on a low cost and capacity FPGA

Visando representar linhas retas digitais, segmentos digitalizados e arcos, cada uma das linhas de pesquisa disponíveis apresenta suas vantagens e aplicações apropriadas. No entanto, considerando as complexidades de cenários do mundo real, o uso dessas representações não é tão popular em situações que requerem modelos flexíveis ou envolvendo interferências espúrias. As tecnologias adaptativas são formalismos da ciência da computação capazes de alterar seu comportamento dinamicamente, sem a interferência de agentes externos, em resposta a estímulos de entrada. Ao serem capazes de responder às mencionadas condições variáveis do ambiente, os dispositivos adaptativos naturalmente tendem a apresentar a flexibilidade requerida para atuarem em cenários dinâmicos. Assim, este trabalho investiga uma alternativa fundamentada no autômato finito adaptativo por meio do dispositivo denominado segmento digitalizado adaptativo, que incorpore o poder expressivo de representar parâmetros desses segmentos. Dentre esses parâmetros destacam-se a capacidade de representar as tolerâncias, a escalabilidade, os erros causados por desvios em ângulo ou em comprimento dos segmentos mencionados, resultando em estruturas mais flexíveis. Considerando que os métodos sintáticos são estruturais, os segmentos digitalizados adaptativos são modelados por conjuntos de regras, partindo-se de primitivas, concebendo-se as funções adaptativas correspondentes para alteração dos estados e de regras de transição. Posteriormente, estruturas mais elaboradas são concebidas relacionadas a arcos digitais pelos quais cadeias (strings) estimulam, em um passo único, autômatos finitos adaptativos que implementam segmentos digitalizados adaptativos. As implementações utilizam uma ferramenta cujo núcleo é um simulador para edição dos arquivos que compõem os autômatos. Consequentemente, o método proposto torna-se uma alternativa relativamente simples e intuitiva comparando-se com as abordagens existentes, apresentando capacidade de aprendizagem, além de ser computacionalmente poderosa. / For the representation of digital straight lines, digitized straight line segments and arcs, each of the available research approaches has its advantages and suitable applications. However, taking into account the complexities of real-world scenarios, the use of these representations is not so popular in situations that require flexible models or involving spurious interferences. Adaptive technologies are computer science formalisms able to change their behavior dynamically, without the interference of external agents, in response to incoming stimuli. By being able to respond to changing environmental conditions, adaptive devices naturally tend to have the required flexibility to work in dynamic scenarios. Thus, the purpose of this study is to investigate an alternative based on adaptive finite automaton through the device called adaptive digitized straight line segment, incorporating the expressive power to represent parameters of these segments. Among these parameters, emphasis is given to the ability to represent tolerances, scalability or errors caused by deviations in angle or length of the mentioned segments, resulting in more flexible structures. Whereas syntactic methods are structural, adaptive digitized straight line segments are modeled by sets of rules, starting from primitives, conceiving the corresponding adaptive functions to amend the set of states and transition rules. Later, more elaborate structures are designed related to digital arcs the corresponding strings of which stimulate, in just a single step, adaptive finite automata that implement adaptive digitized straight line segments. The implementations use a simulator for editing the files that compose the automata. Consequently, the proposed method reveals to be a simple and intuitive alternative capable of learning, besides being computationally powerful.

Os dispositivos lógicos programáveis pertencentes à família APEX 20K, são configurados no momento da inicialização do sistema com dados armazenados em dispositivos especificamente desenvolvidos para esse fim. Esta família de FPGAs possui uma interface otimizada, permitindo também que microprocessadores os configure de maneira serial ou paralela, síncrona ou assíncronamente. Depois de configurados, estes FPGAs podem ser reconfigurados em tempo real com novos dados de configuração. A reconfiguração em tempo real conduz a inovadoras aplicações de computação reconfigurável. Os dispositivos de configuração disponíveis comercialmente, limitam-se a configurar os FPGAs apenas no momento da inicialização do sistema e sempre com o mesmo arquivo de configuração. Este trabalho apresenta a implementação de um controlador de configuração capaz de gerenciar a configuração e reconfiguração de múltiplos FPGAs, a partir de vários arquivos distintos de configuração. Todo o projeto é desenvolvido, testado e validado através da ferramenta EDA Quartus™ II, que propicia um ambiente de desenvolvimento integrado de projeto, compilação e síntese lógica, simulação e análise de tempo. / The APEX 20K programmable logic devices family, are configured at system power-up with data stored in a specific serial configuration device. This family of FPGAs contain an optimized interface that permits microprocessors to configure APEX 20K devices serially or in parallel, and synchronously or asynchronously. After configured, it can be reconfigured in-circuit by resetting the device and loading new data. Real-time changes lead to innovative reconfigurable computing applications. The commercial available configuration devices limit to configure the APEX 20K devices only on the system power-up and always with the same configuration data file. This work shows a configuration controller implementation that can manage the configuration and reconfiguration of several FPGAs from multiple configuration files. The entire project is developed, tested and validated through the EDA tool Quartus™ II, that provide a integrated package with HDL and schematic design entry, compilation and logic synthesis, full simulation and worst-case timing analysis.

O crescimento das necessidades de recursos computacionais gerado por novas classes de aplicações comerciais e científicas apresenta um novo tipo de desafio para infraestruturas computacionais. O acelerado crescimento das demandas por recursos promove um acelerado crescimento no número absoluto de elementos computacionais nestas. Nesse cenário, o provisionamento e a operação de sistemas tornam-se tarefas progressivamente complexas, devido primariamente ao aumento em escala. Este trabalho propõe um modelo para uma infraestrutura computacional que opera como um repositório abstrato de recursos computacionais de tempo de execução com níveis variáveis de consumo. Desenhado para operar como um ensemble (i.e. um conjunto coordenado) de recursos computacionais, grandes números de elementos são agregados em conjuntos de servidores de recursos de processamento, armazenamento e comunicação. O ensemble é concebido e implementado com ampla utilização de tecnologias de virtualização e possui um mecanismo de provisionamento e operação organizado como uma estrutura distribuída de comando e controle (Command and Control, ou C²). A implementação de uma prova de conceito de tal infraestrutura computacional é apresentada, e a validação da proposta é realizada através de uma combinação de resultados experimentais e emulação. / The increase in computing resource needs posed by new classes of commercial and scientific applications presents a new kind of challenge for computing infrastructures. The accelerated growth in resource demand leads to an accelerated growth in the absolute number of computing elements on such infrastructures. In this scenario, the provisioning and systems operations of such elements becomes a progressively complex task, due mainly to the increase in scale. This work proposes a model for a computing infrastructure that operates as an abstract repository of run-time resources with variable levels of consumption. Designed to operate as a computing ensemble, large numbers of elements are aggregated in pools of processing, storage and communication resource servers. The Computing Resource Ensemble is designed with the heavy use of virtualization technologies and has a provisioning and systems operation engine organized as a distributed Command and Control (C2) framework. A Proof of Concept implementation of such computing infrastructure is presented, and the validation of the concept is carried out by a combination of experiments and emulation.

Visando representar linhas retas digitais, segmentos digitalizados e arcos, cada uma das linhas de pesquisa disponíveis apresenta suas vantagens e aplicações apropriadas. No entanto, considerando as complexidades de cenários do mundo real, o uso dessas representações não é tão popular em situações que requerem modelos flexíveis ou envolvendo interferências espúrias. As tecnologias adaptativas são formalismos da ciência da computação capazes de alterar seu comportamento dinamicamente, sem a interferência de agentes externos, em resposta a estímulos de entrada. Ao serem capazes de responder às mencionadas condições variáveis do ambiente, os dispositivos adaptativos naturalmente tendem a apresentar a flexibilidade requerida para atuarem em cenários dinâmicos. Assim, este trabalho investiga uma alternativa fundamentada no autômato finito adaptativo por meio do dispositivo denominado segmento digitalizado adaptativo, que incorpore o poder expressivo de representar parâmetros desses segmentos. Dentre esses parâmetros destacam-se a capacidade de representar as tolerâncias, a escalabilidade, os erros causados por desvios em ângulo ou em comprimento dos segmentos mencionados, resultando em estruturas mais flexíveis. Considerando que os métodos sintáticos são estruturais, os segmentos digitalizados adaptativos são modelados por conjuntos de regras, partindo-se de primitivas, concebendo-se as funções adaptativas correspondentes para alteração dos estados e de regras de transição. Posteriormente, estruturas mais elaboradas são concebidas relacionadas a arcos digitais pelos quais cadeias (strings) estimulam, em um passo único, autômatos finitos adaptativos que implementam segmentos digitalizados adaptativos. As implementações utilizam uma ferramenta cujo núcleo é um simulador para edição dos arquivos que compõem os autômatos. Consequentemente, o método proposto torna-se uma alternativa relativamente simples e intuitiva comparando-se com as abordagens existentes, apresentando capacidade de aprendizagem, além de ser computacionalmente poderosa. / For the representation of digital straight lines, digitized straight line segments and arcs, each of the available research approaches has its advantages and suitable applications. However, taking into account the complexities of real-world scenarios, the use of these representations is not so popular in situations that require flexible models or involving spurious interferences. Adaptive technologies are computer science formalisms able to change their behavior dynamically, without the interference of external agents, in response to incoming stimuli. By being able to respond to changing environmental conditions, adaptive devices naturally tend to have the required flexibility to work in dynamic scenarios. Thus, the purpose of this study is to investigate an alternative based on adaptive finite automaton through the device called adaptive digitized straight line segment, incorporating the expressive power to represent parameters of these segments. Among these parameters, emphasis is given to the ability to represent tolerances, scalability or errors caused by deviations in angle or length of the mentioned segments, resulting in more flexible structures. Whereas syntactic methods are structural, adaptive digitized straight line segments are modeled by sets of rules, starting from primitives, conceiving the corresponding adaptive functions to amend the set of states and transition rules. Later, more elaborate structures are designed related to digital arcs the corresponding strings of which stimulate, in just a single step, adaptive finite automata that implement adaptive digitized straight line segments. The implementations use a simulator for editing the files that compose the automata. Consequently, the proposed method reveals to be a simple and intuitive alternative capable of learning, besides being computationally powerful.

Twenty-first century Field-Programmable Gate Arrays (FPGAs) are no longer used for implementing simple “glue logic” functions. They have become complex arrays of reconfigurable logic resources and memories as well as highly optimised functional blocks, capable of implementing large systems on a single chip. Moreover, Dynamic Partial Reconfiguration (DPR) capability permits to adjust some logic resources on the chip at runtime, whilst the rest are still performing active computations. During the last few years, DPR has become a hot research topic with the objective of building more reliable, efficient and powerful electronic systems. For instance, DPR can be used to mitigate spontaneously occurring bit upsets provoked by radiation, or to jiggle around the FPGA resources which progressively get damaged as the silicon ages. Moreover, DPR is the enabling technology for a new computing paradigm which combines computation in time and space. In Reconfigurable Computing (RC), a battery of computation-specific circuits (“hardware tasks”) are swapped in and out of the FPGA on demand to hold a continuous stream of input operands, computation and output results. Multitasking, adaptation and specialisation are key properties in RC, as multiple swappable tasks can run concurrently at different positions on chip, each with custom data-paths for efficient execution of specific computations. As a result, considerable computational throughput can be achieved even at low clock frequencies. However, DPR penetration in the commercial market is still testimonial, mainly due to the lack of suitable high-level design tools to exploit this technology. Indeed, currently, special skills are required to successfully develop a dynamically reconfigurable application. In light of the above, this thesis aims at bridging the gap between high-level application and low-level DPR technology. Its main objective is to develop Operating System (OS)-like support for high-level software-centric application developers in order to exploit the benefits brought about by DPR technology, without having to deal with the complex low-level hardware details. The developed solution in this thesis is named as R3TOS, which stands for Reliable Reconfigurable Real-Time Operating System. R3TOS defines a flexible infrastructure for reliably executing reconfigurable hardware-based applications under real-time constraints. In R3TOS, the hardware tasks are scheduled in order to meet their computation deadlines and allocated to non-damaged resources, keeping the system fault-free at all times. In addition, R3TOS envisages a computing framework whereby both hardware and software tasks coexist in a seamless manner, allowing the user to access the advanced computation capabilities of modern reconfigurable hardware from a software “look and feel” environment. This thesis covers all of the design and implementation aspects of R3TOS. The thesis proposes a novel EDF-based scheduling algorithm, two novel task allocation heuristics (EAC and EVC) and a novel task allocation strategy (called Snake), addressing many RC-related particularities as well as technological constraints imposed by current FPGA technology. Empirical results show that these approaches improve on the state of the art. Besides, the thesis describes a novel way to harness the internal reconfiguration mechanism of modern FPGAs to performinter-task communications and synchronisation regardless of the physical location of tasks on-chip. This paves the way for implementing more sophisticated RC solutions which were only possible in theory in the past. The thesis illustrates R3TOS through a proof-of-concept prototype with two demonstrator applications: (1) dependability oriented control of the power chain of a railway traction vehicle, and (2) datastreaming oriented Software Defined Radio (SDR).

O crescimento das necessidades de recursos computacionais gerado por novas classes de aplicações comerciais e científicas apresenta um novo tipo de desafio para infraestruturas computacionais. O acelerado crescimento das demandas por recursos promove um acelerado crescimento no número absoluto de elementos computacionais nestas. Nesse cenário, o provisionamento e a operação de sistemas tornam-se tarefas progressivamente complexas, devido primariamente ao aumento em escala. Este trabalho propõe um modelo para uma infraestrutura computacional que opera como um repositório abstrato de recursos computacionais de tempo de execução com níveis variáveis de consumo. Desenhado para operar como um ensemble (i.e. um conjunto coordenado) de recursos computacionais, grandes números de elementos são agregados em conjuntos de servidores de recursos de processamento, armazenamento e comunicação. O ensemble é concebido e implementado com ampla utilização de tecnologias de virtualização e possui um mecanismo de provisionamento e operação organizado como uma estrutura distribuída de comando e controle (Command and Control, ou C²). A implementação de uma prova de conceito de tal infraestrutura computacional é apresentada, e a validação da proposta é realizada através de uma combinação de resultados experimentais e emulação. / The increase in computing resource needs posed by new classes of commercial and scientific applications presents a new kind of challenge for computing infrastructures. The accelerated growth in resource demand leads to an accelerated growth in the absolute number of computing elements on such infrastructures. In this scenario, the provisioning and systems operations of such elements becomes a progressively complex task, due mainly to the increase in scale. This work proposes a model for a computing infrastructure that operates as an abstract repository of run-time resources with variable levels of consumption. Designed to operate as a computing ensemble, large numbers of elements are aggregated in pools of processing, storage and communication resource servers. The Computing Resource Ensemble is designed with the heavy use of virtualization technologies and has a provisioning and systems operation engine organized as a distributed Command and Control (C2) framework. A Proof of Concept implementation of such computing infrastructure is presented, and the validation of the concept is carried out by a combination of experiments and emulation.

Sofisticadas técnicas para estimação de modelos baseadas em simulação, os filtros de partículas ou métodos de Monte Carlo Seqüenciais, foram empregadas recentemente para solucionar diversos problemas difícieis no campo da robótica móvel. No entanto, o sucesso dos fitros de partículas limitou-se à computação de parâmetros em espaços de baixa dimensionalidade. Os atuais esforços de pesquisa em robótica móvel têm comecado a explorar certas propriedades estruturais de seus domnios de aplicação que envolvem a utilização de filtros de partculas em espacos de maior dimensão, aumentando consideravelmente a complexidade da simulação envolvida. Simulações estatsticas dessa natureza requerem uma grande quantidade de numeros pseudo-aleatorios que possam ser gerados eficientemente e atendam a certos criterios de qualidade. O processo de geração de numeros pseudo-aleatorios torna-se o ponto crtico de tais aplicações em termos de desempenho. Neste contexto, a computação reconguravel insere-se como uma tecnologia capaz de satisfazer a demanda por alto desempenho das grandes simulações estatsticas pois sistemas baseados em arquiteturas reconguraveis possuem o potencial de mapear computação em hardware visando aumento de eficiência sem comprometer seriamente sua exibilidade. Tecnologias reconguraveis também possui o atrativo de um baixo consumo de energia, uma caracterstica essencial para os futuros robôs moveis embarcados. Esta dissertação apresenta a implementação um sistema embarcado baseado em FPGA e projetado para solucionar o problema de localização de robôs por meio de tecnicas probabilsticas. A parte fundamental de todo este sistema e um veloz gerador de numeros aleatorios mapeado ao hardware reconguravel que foi capaz de atender rígidos criterios estatsticos de qualidade / Sophisticated techniques for estimation of models based on simulation, particle filters or Sequential Monte Carlo Methods, were recently used to solve many difficult problems in the field of mobile robotics. However, the success of particle filters was limited to the computation of parameters in low dimensionality spaces. The current research efforts in mobile robotics have begun to explore some structural properties of their application\'s domain involving the use of particle filters in spaces of a higher dimension, greatly increasing the complexity of the involved simulation. Statistical simulations of this nature require a lot of pseudorandom numbers that can be generated efficiently and meet certain quality criteria. The process of generating pseudorandom number becomes the critical point of such applications in terms of performance. In this context, reconfigurable computing is a technology capable of meeting the demand for high performance of large statistical simulations because systems based on reconfigurable architectures have the potential to map computation to hardware aiming to increase eficiency without a serious drawback in exibility. Reconfigurable technologies are also attractive because of their low energy consume, a essential feature for the future mobile robots. This dissertation presents an implementation of a FPGA based embedded system designed to solve the robot localization problem by the means of probabilistic technics. The fundamental part from the whole system is a fast random number generator mapped to reconfigurable hardware wich atends a rigid quality criteria