Recent advancements in semiconductor fabrication technology have enabled field-programmable gate arrays (FPGAs) with hundreds of embedded memories. Usually, these embedded memories can be configured to work with different widths of address and data buses, In some FPGAs there is also a variety of different types of embedded memories with different capacities and configuration sets. As a consequence, it is becoming cumbersome to bind the data memory of an algorithm to these embedded memories manually. A computer-aided design tool that automates the process of binding embedded memories can save the engineering time for a design, as well as explore different alternatives to bind the data memory with the use of less embedded memories and less amount of peripheral hardware in terms of logic cells of the FPGA. In this thesis, we first motivate the need for an algorithmic solution to the memory binding problem in FPGAs and explain the design trade-offs. Then we present an exact solution for the problem using a branching method to search the solution space exhaustively. However, due to the large solution space and the plenitude of choices in each step of the algorithm, the runtime of the algorithm is far from being acceptable for realistic problems. To manage the runtime, we have developed a fast heuristic approach. Our experimental results show that the heuristic method can achieve a suboptimal solution, which for the small problem instances is shown to be close to the optimal in acceptable runtime. Moreover, when compared to manual solutions, besides substantially improving the implementation time, the heuristic can often enable a more efficient usage of the FPGA logic resources and embedded memories. / Thesis / Master of Applied Science (MASc)

This thesis presents the design and implementation of the Image Wavelet Compression (IWC) algorithm on Field Programmable Gate Arrays (FPGAs) by using the run-time reconfigurable custom computing machine design tool Janus. The four routines implementing the IWC are discussed. The structure of Janus is introduced and the IWC implementation design framework to use Janus structure is described in detail. The Janus hardware circuit design model, which has been used in the IWC implementation, is demonstrated here. The hardware implementation results are presented and analyzed, focusing on reconfiguration and computing time. Future research areas are suggested to improve the Janus tool. / Master of Science

L'essor considérable de la technologie CMOS a permis l'accroissement de la densité d'intégration selon la loi de Moore. Cependant, la poursuite de cette évolution est en voie de ralentissement dû aux contraintes physiques et économiques. Le défi devient alors de pouvoir utiliser un maximum de circuits tout en tolérant des défauts physiques présents en leur sein. Les circuits reconfigurables de type FPGA (Field Programmable Gate Array) connaissent un succès croissant car leurs performances et leurs capacités d'intégrer des applications très complexes ont directement bénéficié de l'évolution technologique. Le but de cette thèse est de proposer une architecture de FPGA contenant des mécanismes permettant de tolérer plus de 20% d'éléments défectueux après fabrication. La première partie du manuscrit étudie les différentes architectures de FPGA (matricielles et arborescentes) ainsi que les différentes techniques de contournement des défauts. Dans la seconde partie de cette thèse, nous présentons l'architecture cible matricielle (matrice de grappes ou groupes). Cette architecture combine les avantages des architectures matricielles (sa généricité) et arborescentes (réduction du taux d'utilisation de l'interconnexion. La troisième partie de cette thèse présente le développement d'une méthode d'identification des blocs les plus critiques contenus dans le FPGA ainsi que l'impact des différentes techniques de contournement retenues et proposées sur l'architecture et sur la criticité des blocs de base du FPGA. Pour finir, nous définissons les performances des différentes techniques de contournements en termes de tolérance aux défauts, de performances temporelles et de surface. / The increasing integration density according to Moore’s law is being slowed due to economic and physical limits. However, this technological evolution involves an higher number of physical defects after manufacturing circuit. As yield goes down, one of the future challenges is to find a way to use a maximum of fabricated circuits while tolerating physical defects spread all over the chip. Fiel Programmable Gate Array (FPGA) are integrated circuits that contain logic blocks and reconfigurable interconnect. Their ability to integrate more complex applications, their flexibility and good performance make FPGAs the perfect target architecture. The aim of this thesis is to propose an FPGA architecture containing mechanisms to tolerate more than 20% of defective resources after manufacture. The first part of the manuscript studies the different FPGA architectures (mesh and tree) and different defects bypass techniques. In the second part of this thesis, we present the target architecture called Mesh of Clusters (MoC). This architecture combines the advantages of mesh architectures (genericity) and tree (reduction of the interconnect). The third contribution of this thesis is the development of a method to identify the most critical blocks in the FPGA and the impact of all bypass techniques on the architecture and on the criticality. Finally, we define the performance of all bypass techniques in terms of defect tolerance, timing and area overhead. Finally, thanks to these local redundancy techniques, we are able to tolerate more than 20% of defect on the FPGA architecture. In addition, the designer can fix his own metric in terms of area, timing and defect tolerance.

Les applications embarquées ont besoin de plus en plus de puissance de calcul et doivent être déployées sur des architectures spécifiques pour assurer les contraintes non-fonctionnelles du système. Ces architectures peuvent être composées d'unités de calcul hétérogènes, comme des processeurs ou des accélérateurs matériels. Cette hétérogénéité rend le déploiement d'applications de plus en plus complexe, notamment avec l'apparition de circuits reconfigurables dynamiquement. Un des verrous majeurs à ce déploiement réside dans la gestion des communications entre les parties statiques et dynamiques des applications.Le verrou adressé dans cette thèse concerne la gestion des communications entre les blocs fonctionnels de l'application répartis de manière statique en logiciel et de manière dynamique en matériel. Pour faciliter le déploiement des applications existantes et à venir, notre approche s'appuie sur deux contributions complémentaires : une méthodologie de conception basée sur le raffinement progressif d'acteurs flot-de-données, et un middleware distribué assurant les communications entre les acteurs une fois ceux-ci déployés sur la plateforme.Nous avons validé ces concepts sur une application dynamique de suivi de cible en traitement d'images.Dans ce contexte, nous nous sommes intéressés à la virtualisation des communications au sein de la plateforme pour faire communiquer les parties matérielles et logicielles de l'application de manière transparente. Nos contributions ont permis d'aboutir à un démonstrateur opérationnel dans le cadre du projet FOSFOR. / Applications require more computing power and need to be implemented on specific architectures to ensure the non-functioning constraints of the system. These architectures can be composed of heterogeneous processing units, such as processors or hardware accelerators. This heterogeneity makes the deployment of applications on such architectures increasingly complex, especially with the emergence of dynamically reconfigurable devices. One of the hardest obstacles to this deployment is to manage the communication between the static parts and the dynamic ones of the applications.This thesis deals with the communication management issue between the application functional blocks, ones being statically implemented in software, and the others dynamically in hardware. In order to facilitate the deployment of existing applications and those to come, our approach relies on two complementary contributions: a methodology of conception based on the progressive refinement of data-flow actors, and a distributed middleware ensuring the communication between the actors deployed on the platform.These concepts have been validated on a dynamic tracking target application relying on image processing. In this context, we were interested in the virtualization of the communication within the platform in order to allow the communications between the software and the hardware parts of the application in a transparent way. Our contributions permits us to achieve an operational demonstrator in the frame of the FOSFOR project.

O aumento da complexidade dos sistemas embarcados e a necessidade de um desenvolvimento cada vez mais acelerado têm motivado o uso de modelos abstratos que possibilitem maior flexibilidade e reusabilidade. Para isso, faz-se necessária a aceitação das linguagens e perfis mais abstratos, como o MARTE. Neste trabalho, foi desenvolvida uma ferramenta para conversão de sistemas embarcados independente de plataforma (PIM) em sistemas de uma plataforma específica (PSM), denominada I2S (Independente to Specific). O I2S é totalmente acoplável a novos desenvolvimentos e necessidades do projetista, capaz de modelar representações gráficas de sistemas embarcados, usando componentes do MARTE e permitindo uma implementação final em tecnologia reconfigurável. A partir de um modelo independente de plataforma faz-se a conversão para o padrão de projeto SOPC-Builder da Altera e XPS da Xilinx, possibilitando a exploração do espaço de projeto nessas duas tecnologias de modo automático. O trabalho faz análise de sistemas convertidos em diversas configurações e traz resultados relevantes para a área que validam o uso da proposta, atendendo aos requisitos de projeto / The growing of embedded systems complexity and the want for a quicker development has motivated the use of abstract models that improves flexibility and reusability. To these objective, we searched for the most adequate languages and profiles, like MARTE. In this work we developed a tool for conversion from platform independent models (PIM) to platfom specific models (PSM), named I2S (Independent to Specific). The I2S is totally acceptable to new developments and necessities of the designer, to open up modelling graphic representations of embedded systems using MARTE components and doing implementation in reconfigurable technology. A platform independent model is converted to the pattern of Alteras SOPC-Builder and Xilinxs XPS, making possible the exploitation of the project space in theses two tecnologies automatically. The work does analysis of systems converted in different configurations and shows relevant results to the area that validate the use of the proposal, meeting the project requirements

Neste trabalho, é apresentado o desenvolvimento de um IP de rede Ethernet com interface para o barramento Avalon para utilização em conjunto com o processador Nios II da Altera. O IPC foi adaptado do projeto Ethernet_tri_mode, e é capaz de transferir dados a velocidades de 1000, 100 e 10 Mbps. O desenvolvimento envolveu a adaptação do código para atingir os requisitos do projeto, feito segundo as diretrizes do CIERMag de manter todo o código em VHDL. Além disso, foi implementada uma interface de comunicação com o processador Nios II para tornar possível a configuração do sistema, bem como a transferência de dados através de um software sendo executado no processador. O IPC Ethernet foi projetado para ser aplicado no espectrômetro digital em desenvolvimento pelo CIERMag e teve como compromissos a baixa utilização de recursos lógicos do FPGA e, ao mesmo tempo, a disponibilização de uma alta taxa de transferência de dados para o espectrômetro. Como ferramenta de desenvolvimento, foi utilizada a plataforma Quartus II cujo fornecedor é a Altera. Já os testes em placa foram realizados em um kit de desenvolvimento DE3-150 da Terasic, o qual utiliza uma FPGA Stratix III, também da Altera. Com o intuito de testar e validar o sistema, foi desenvolvido um software para o processador Nios II capaz de receber e enviar dados através do IPC e com inteligência para responder pedidos do tipo ARP e PING. O subsistema de Gigabit Ethernet desenvolvido aqui já incorpora a versão corrente do Espectrômetro Digital de RM do CIERMag. / In this work we expose the implementation of an Ethernet network core which interfaces to Avalon bus used along with the Nios II Altera processor. This core was adapted from the Ethernet_tri_mode project. It can transfer data at rates of 1000, 100 and 10 Mbps. The development involved the adaptation of the code to fullfil the project requirements, under the policy of the CIERMag to keep the whole coding in VHDL. Furthermore was implemented an interface to communicate with the Nios II processor to enable system configuration and data transfer through a software running on the processor. The core was projected to be applied with focus on the utilization of low FPGA logical resources with the availability of a high data transfer rate. It will be used in a digital spectrometer under development at the CIERMag. The Quartus II platform, supplied by Altera was used as the development tool. The tests on board where carried out on a DE3-150 development kit from Terasic, which has an FPGA Stratix III also from Altera. In order to test and validate the system, a software for the Nios II processor was developed, able to send and receive data via IPC and with intelligence to answer ARP and PING types requests. The developed Gigabit Ethernet subsystem is now part of the running version of the CIERMag Digital MR Spectrometer.

A computação reconfigurável tem se tornado cada vez mais importante em sistemas computacionais embarcados e de alto desempenho. Ela permite níveis de desempenho próximos aos obtidos com circuitos integrados de aplicação específica (ASIC), enquanto ainda mantém flexibilidade de projeto e implementação. No entanto, para programar eficientemente os dispositivos, é necessária experiência em desenvolvimento e domínio de linguagem de descrição de hardware (HDL), tais como VHDL ou Verilog. As técnicas empregadas na compilação em alto nível (por exemplo, a partir de programas em C) ainda possuem muitos pontos em aberto a serem resolvidos antes que se possa obter resultados eficientes. Muitos esforços em se obter um mapeamento direto de algoritmos em hardware se concentram em loops, uma vez que eles representam as regiões computacionalmente mais intensivas de muitos programas. Uma técnica particularmente útil para isto é a de loop pipelining, a qual geralmente é adaptada de técnicas de software pipelining. A aplicação dessas técnicas está fortemente relacionada ao escalonamento das instruções, o que frequentemente impede o uso otimizado dos recursos presentes nos FPGAs modernos. Esta tese descreve uma abordagem alternativa para o mapeamento direto de loops descritos em uma linguagem de alto nível para FPGAs. Diferentemente de outras abordagens, esta técnica não é proveniente das técnicas de software pipelining. Nas arquiteturas obtidas o controle das operações é distribuído, tornando desnecessária uma máquina de estados finitos para controlar a ordem das operações, o que permitiu a obtenção de implementações eficientes. A especificação de um bloco de hardware é feita por meio de uma linguagem de domínio específico (LALP), especialmente concebida para suportar a aplicação das técnicas. Embora a sintaxe da linguagem lembre C, ela contém certas construções que permitem intervenções do programador para garantir ou relaxar dependências de dados, conforme necessário, e assim otimizar o desempenho do hardware gerado / Reconfigurable computing is becoming increasingly important in embedded and high-performance computing systems. It allows performance levels close to the ones obtained with Application-Specific Integrated circuits (ASIC), while still keeping design and implementation flexibility. However, to efficiently program devices, one needs the expertise of hardware developers in order master hardware description languages (HDL) such as VHDL or Verilog. Attempts to furnish a high-level compilation flow (e.g., from C programs) still have to address open issues before broader efficient results can be obtained. Many efforts trying to achieve a direct of algorithms into hardware concentrate on loops since they represent the most computationally intensive regions of many application codes. A particularly useful technique for this purpose is loop pipelining, which is usually adapted from software pipelining techniques. The application of this technique is strongly related to instruction scheduling, whic often prevents an optimized use of the resources present in modern FPGAs. This thesis decribes an alternative approach to direct mapping loops described in high-level labguages onto FPGAs. Different from oyher approaches, this technique does not inherit from software pipelining techniques. The control is distributed over operations, thus a finite state machine is not necessary to control the order of operations, allowing efficient harware implementations. The specification of a hardware block is done by means of LALP, a domain specific language specially designed to help the application of the techniques. While the language syntax resembles C, it contains certain constructs that allow programmer interventions to enforce or relax data dependences as needed, and so optimize the performance of the generated hardware

A escassez de equipamentos e soluções à disposição das pessoas portadoras de necessidades especiais é evidente e, na maioria dos casos, não está entre as prioridades primárias dos governos, tanto nos países desenvolvidos como, e principalmente, nos subdesenvolvidos. O desenvolvimento de dispositivos a preços acessíveis é, desta forma, uma carência real. O alto custo de fabricação de dispositivos assistivos é oriundo da necessidade de se construí-los de forma personalizada o que geralmente utiliza o estado da arte de determinada tecnologia. Aglutinando então, tecnologias já difundidas com novas abordagens e ferramentas, foi implementado um dispositivo assistivo com um índice de \"personalização\" extremamente baixo e com custo acessível. O método GRAFCET como ferramenta de desenvolvimento, aliado a tecnologia FPGA, nas fases de prototipação e produção, mostram-se eficazes e de fácil aplicabilidade. Para essa finalidade foi desenvolvida uma ferramenta de conversão GRAFCET - Circuito Digital que facilita e torna possível não só na elaboração do esquema GRAFCET, mas principalmente possibilita antever semelhança com outras aplicações que não são facilmente visualizadas num primeiro momento, permitindo a sua simplificação. O dispositivo concebido, mostrou que, com pequenas modificações, é possível desenvolvê-los de forma que atenda não apenas um, mas vários portadores de necessidades especiais, viabilizando assim a diminuição dos custos de projeto, desenvolvimento e construção dos equipamentos que venham a atender estas pessoas, permitindo assim melhora significativa em sua qualidade de vida. / In all countries, particularly in underdeveloped ones, there are few equipment and solutions available to people with physical disabilities, whose needs hardly rank among the government\'s top priorities. Therefore, there is a real need to develop low cost equipment to people with disabilities. The high cost of production of assistive devices results from the necessity of building them in a customized way, generally employing some state-of-the-art technology. This work proposes using well known technologies as tools, in such a way to allow the design of assistive devices with a low degree of customization and, consequently, at low cost. Using GRAFCET as a development tool and FPGA technology have shown to be an effective and easily applicable approach during the phases of prototyping and production. We developed a tool that converts GRAFCET designs into a digital circuit. The tool makes it easier to develop GRAFCET schemes and highlights the similarities among different applications, which otherwise could pass unnoticed, resulting in simplified designs. With small modifications, the proposed device can meet the needs of several people with disabilities, resulting in lower design, development and building costs of equipment that can significantly improve their quality of life.

Como avanço dos paradigmas de desenvolvimento de sistemas eletrônicos, novos conceitos, modelos e técnicas resultaram dessa evolução, gerando ferramentas mais eficientes e objetivas. Entre estas, as de automação de projetos eletrônicos (EDA - Electronic Design Automation) em nível de sistema (ESL - Electronic System Level) trouxeram um incremento considerável de produtividade à confecção de sistemas eletrônicos, inclusive de sistemas embarcados. Já no que se refere ao desempenho do sistema elaborado, monitorar sua execução e determinar seu perfil de funcionamento são tarefas essenciais para avaliar, a partir do seu comportamento, quais os pontos que representam gargalos ou pontos críticos, afetando sua eficiência geral. Dessa forma, faz-se necessário pesquisar princípios de verificação e otimização dos sistemas elaborados que estejam mais bem adaptados aos novos paradigmas de desenvolvimento de projetos. O presente trabalho tem por objetivo implementar um módulo de coleta e processamento de dados para análise de perfil de programas escritos na linguagem C e que sejam executados em processadores soft core, como o NiosII, da Altera. Entretanto, diferentemente das estatísticas oferecidas pela ferramenta GProf (GNU Profiling) com relação à análise de desempenho, em que cada amostra obtida implica no incremento de um contador para a função flagrada, o presente trabalho volta seu interesse à análise do perfil de uso de memória heap, que encontra-se mormente no volume alocado constatado em cada amostragem. Dessa forma, para diferentes amostragens de uma mesma função interessa saber qual a maior quantidade de memória utilizada pela função entre todas as amostras coletadas. Isso significa que, ao invés de incremento por amostragem, adotar-se-á o princípio do registro do maior valor, em número de bytes, de uso de memória constatado em cada função. Os principais recursos do módulo proposto são: a) o armazenamento das informações de uso de memória heap obtidas no processo de Profiling em formato apropriado para uso posterior por aplicações de co-projeto de hardware e software; e b) a geração de relatórios de Profiling que apresentem o volume de memória dinâmica alocada durante o processamento dos programas analisados para que se possa identificar os locais onde esse uso é mais crítico, permitindo ao projetista tomar decisões quanto à reformulação do código fonte, ou quanto ao incremento no tamanho da memória a ser instalada no sistema, ou quanto à reformulação da arquitetura de um modo geral / Due to the advancement of the paradigms of development of electronic systems, new concepts, models and techniques resulted from this evolution, generating more eficient and objective tools. Among them, the system-level (ESL) electronic design automation (EDA) ones has brought a considerable increase to the productivity of electronic systems manufacturing, especially including the embedded systems. In what refers to elaborated systems, monitoring its execution and determining its operating profile are the essential tasks to assess, from its behavior, which points in this system represent bottlenecks or hot spots, affecting its overall efficiency. Thus, it is necessary to study the principles of verification and optimization of the elaborated systems that are better adapted to the new paradigms of projects development. The present work has as its aim implementing a processing module for data collection and analysis of C language writen programs profile, wich will run in soft core processors, like Alteras NiosII. However, unlike the statistics offered by the tool GProf (GNU Profiling) tool with respect to performance analysis, in which each sample obtained implies the increment of a counter to the function caught, this paper turns his interest to the analysis of memory usage profiling, which is especially found in volume allocated in each sample. Thus, for different samples of the same function, the matter is to know the most amount of memory used by the function among all samples collected. This means that instead of increasing sample we will adopt the principle of registration of the highest number of bytes of memory usage observed in each function. So, this tools main features are: a) storing the information of memory use in the heap memory obtained in the process of Profiling in an appropriate format for later use by hardware and software codesign applications; and b) the reporting of Profiling that shows the dynamic memory volume allocated during analyzed programs processing so one can identify where such use is more critical, allowing the designer to make decisions regarding the reformulation of source code, or as to the increase in memory size to be installed int the system, or as to the architecture redesign

Esse trabalho tem por objetivo descrever o desenvolvimento e os atuais resultados do protótipo dataflow PIFLOW, um processador baseado no modelo de dataflow dinâmico, inspirado na Maquina Dataflow de Manchester e desenvolvido no Instituto de Física de São Carlos, da Universidade de São Paulo. Esse protótipo foi capaz de oferecer speedups muito próximos do ideal, a partir de programas que possuem grande grau de paralelismo, apresentando o grande potencial deste modelo - já bastante estudado no decorrer das últimas décadas - em oferecer desempenho superior ao de processadores sequenciais comerciais modernos. / The aim of this work is to describe the development and the current results of the PIFLOW dataflow prototype, a processor based on the dynamic dataflow model of execution, inspired by the Manchester Dataflow Machine and developed in the Instituto de Física de São Carlos, Universidade de São Paulo. This prototype shows speedups very close to the ideal case, when executing programs with a high degree of parallelism, showing the dataflow model potential, which has been extensibly analysed in the last decades, to offer higher performance when compared to commercial modern sequential processors.