Tese de mestrado integrado. Engenharia Electrotécnica e de Comunicações. Telecomunicações. Universidade do Porto. Faculdade de Engenharia. 2011

Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Jaqueline Oliveira (jaqueoliveiram@gmail.com) on 2008-12-04T18:50:12Z No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / Approved for entry into archive by Georgia Fernandes(georgia@bce.unb.br) on 2009-02-12T17:40:49Z (GMT) No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / Made available in DSpace on 2009-02-12T17:40:50Z (GMT). No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / O alinhamento de seqüências biológicas é uma das operações mais básicas em bioinformática, tendo por objetivo determinar a similaridade entre as seqüências. A solução deste problema envolve geralmente a comparação de seqüências através de programação dinâmica. Este tipo de comparação gera resultados ótimos mas possui complexidade quadrática de tempo, justificando métodos para sua aceleração em hardware como o FPGA. Na presente tese foram projetadas arquiteturas wavefront em FPGA utilizando espaço linear para três diferentes algoritmos. O primeiro algoritmo foi o de Smith-Waterman. Ele foi implementado na forma de um vetor wavefront e foi utilizado na aceleração da fase inicial de um algoritmo de alinhamento. Esta arquitetura foi capaz de recuperar o maior escore e posição em espaço linear. Esta arquitetura foi sintetizada em FPGA e o melhor resultado da arquitetura foi 246,9 vezes mais rápido que em software, demonstrando a utilidade da arquitetura. A seguir, foi projetada uma arquitetura para a recuperação do escore ótimo do algoritmo de programação dinâmica DIALIGN também em espaço linear. Foram obtidos resultados até 383,41 vezes superiores ao programa em software. Para recuperar o alinhamento ótimo no DIALIGN é necessário espaço quadrático. Assim, foi projetada uma variante do DIALIGN capaz de recuperar o alinhamento de duas seqüências em espaço linear. Após a implementação em hardware, os resultados obtidos foram até 141,38 vezes mais rápido que a implementação em software. ______________________________________________________________________________________ ABSTRACT / The alignment of biological sequences is one of the more basic operations in bioinformatics. Its purpose is to find the similarity between sequences. The solution to this problem generally involves sequence comparison through dynamic programming. This kind of comparison yields optimal results but has quadratic time complexity thus justifying its hardware acceleration in FPGA. In this thesis, linear space wavefront architectures were designed in FPGA for three different algorithms. The first algorithm was Smith-Waterman. It was implemented in a wavefront array and utilized to accelerate the initial phase of a sequence alignment algorithm. This architecture was able to retrieve the largest score and its position in linear space. It was synthesized in FPGA and the best result was 246,9 times faster than software, showing the appropriateness of the architecture. Also, an architecture to retrieve the optimal DIALIGN score in linear space was designed. The results were up to 383,41 times better than software. The retrieval of the optimal alignment for DIALIGN needs quadratic space. Therefore, a variant for the DIALIGN dynamic programming algorithm was proposed to retrieve the alignment in linear space. This variant was implemented in hardware and the results were up to 141,38 times faster than the software implementation.

Made available in DSpace on 2014-06-12T16:01:00Z (GMT). No. of bitstreams: 2 arquivo7128_1.pdf: 2072446 bytes, checksum: b6bc5386371d917bd7613b206ac8e92f (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / A demanda cada vez maior por produtos eletronicos e a crescente capacidade de integração dos chips direcionaram a metodologia de projeto de sistemas embarcados para sua completa integração em um único chip ( System-on-Chip, ou SoC). Essa metodologia baseia-se cada vez mais em componentes previamente projetados e verificados (IP-core ) como uma alternativa de disponibilizar os sistemas dentro dos prazos esperados, sem perder o time-to-market do mercado consumidor de eletrônicos. Neste trabalho, é proposto um processo de desenvolvimento de IP-cores baseado em técnicas de engenharia de software chamado ipPROCESS, como um mecanismo de facilitar e promover o desenvolvimento de IP-cores de alta qualidade. Tendo o foco na criação de componentes de qualidade, o ipPROCESS foi definido com base em técnicas de verificação funcional, de modelagem visual da arquitetura, de interface de comunicação e de documentação seguindo os padrões da indústria. O processo foi descrito utilizando o meta-modelo UML denominado SPEM com o objetivo de facilitar e acelerar o seu entendimento, assim como permitir alterações futuras e facilitar o gerenciamento de projetos baseados no processo proposto

Devido à complexidade das aplicações, a demanda crescente por sistemas que usam milhões de transistores e hardware complexo; tem sido desenvolvidas ferramentas que convertem C em Linguagem de Descrição de Hardware, tais como VHDL e Verilog. Neste contexto, esta tese apresenta o projeto ChipCflow, o qual usa arquitetura a fluxo de dados, para implementar lógica de alto desempenho em Field Programmable Gate Array (FPGA). Maquinas a fluxo de dados são computadores programáveis, cujo hardware é otimizado para computação paralela de granularidade fina dirigida por dados. Em outras palavras, a execução de programas é determinado pela disponibilidade dos dados, assim, o paralelismo é intrínseco neste sistema. Por outro lado, com o avanço da tecnologia da microeletrônica, o FPGA tem sido utilizado principalmente devido a sua flexibilidade, facilidade para implementar sistemas complexos e paralelismo intrínseco. Um dos desafios é criar ferramentas para programadores que usam linguagem de alto nível (HLL), como a linguagem C, e produzir hardware diretamente. Essas ferramentas devem usar a máxima experiência dos programadores, o paralelismo das arquiteturas a fluxo de dados dinâmica, a flexibilidade e o paralelismo do FPGA, para produzir um hardware eficiente, otimizado para alto desempenho e baixo consumo de energia. O projeto ChipCflow é uma ferramenta que converte os programas de aplicação escritos em linguagem C para a linguagem VHDL, baseado na arquitetura a fluxo de dados dinâmica. O principal objetivo dessa tese é definir e implementar os operadores do ChipCflow, usando a arquitetura a fluxo de dados dinâmica em FPGA. Esses operadores usam tagged tokens para identificar dados, com base em instâncias de operadores. A implementação dos operadores e das instâncias usam um modelo de implementação assíncrono em FPGA para obter maior velocidade e menor consumo / Due to the complexity of applications, the growing demand for both systems using millions of transistors and consecutive complex hardware, tools that convert C into a Hardware Description Language (HDL), as VHDL and Verilog, have been developed. In this context this thesis presents the ChipCflow project, which uses dataflow architecture to implement high-performance logics in Field Programmable Gate Array (FPGA). Dataflow machines are programmable computers whose hardware is optimized for fine-grain data-flow parallel computation. In other words the execution of programs is determined by data availability, thus parallelism is intrinsic in these systems. On the other hand, with the advance of technology of microelectronics, the FPGA has been used mainly because of its flexibility, facilities to implement complex systems and intrinsic parallelism. One of the challenges is to create tools for programmers who use HLL (High Level Language), such as C language, producing hardware directly. These tools should use the utmost experience of the programmers, the parallelism of dynamic dataflow architecture and the flexibility and parallelism of FPGA to produce efficient hardware optimized for high performance and lower power consumption. The ChipCflow project is a tool that converts application programs written in C language into VHDL, based on the dynamic dataflow architecture. The main goal in this thesis is to define and implement the operators of ChipCflow using dynamic dataflow architecture in FPGA. These operators use tagged tokens to identify data based on instances of operators and their implementation and instances use an asynchronous implementation model in FPGA to achieve faster speed and lower consumption

Devido à complexidade das aplicações, a demanda crescente por sistemas que usam milhões de transistores e hardware complexo; tem sido desenvolvidas ferramentas que convertem C em Linguagem de Descrição de Hardware, tais como VHDL e Verilog. Neste contexto, esta tese apresenta o projeto ChipCflow, o qual usa arquitetura a fluxo de dados, para implementar lógica de alto desempenho em Field Programmable Gate Array (FPGA). Maquinas a fluxo de dados são computadores programáveis, cujo hardware é otimizado para computação paralela de granularidade fina dirigida por dados. Em outras palavras, a execução de programas é determinado pela disponibilidade dos dados, assim, o paralelismo é intrínseco neste sistema. Por outro lado, com o avanço da tecnologia da microeletrônica, o FPGA tem sido utilizado principalmente devido a sua flexibilidade, facilidade para implementar sistemas complexos e paralelismo intrínseco. Um dos desafios é criar ferramentas para programadores que usam linguagem de alto nível (HLL), como a linguagem C, e produzir hardware diretamente. Essas ferramentas devem usar a máxima experiência dos programadores, o paralelismo das arquiteturas a fluxo de dados dinâmica, a flexibilidade e o paralelismo do FPGA, para produzir um hardware eficiente, otimizado para alto desempenho e baixo consumo de energia. O projeto ChipCflow é uma ferramenta que converte os programas de aplicação escritos em linguagem C para a linguagem VHDL, baseado na arquitetura a fluxo de dados dinâmica. O principal objetivo dessa tese é definir e implementar os operadores do ChipCflow, usando a arquitetura a fluxo de dados dinâmica em FPGA. Esses operadores usam tagged tokens para identificar dados, com base em instâncias de operadores. A implementação dos operadores e das instâncias usam um modelo de implementação assíncrono em FPGA para obter maior velocidade e menor consumo / Due to the complexity of applications, the growing demand for both systems using millions of transistors and consecutive complex hardware, tools that convert C into a Hardware Description Language (HDL), as VHDL and Verilog, have been developed. In this context this thesis presents the ChipCflow project, which uses dataflow architecture to implement high-performance logics in Field Programmable Gate Array (FPGA). Dataflow machines are programmable computers whose hardware is optimized for fine-grain data-flow parallel computation. In other words the execution of programs is determined by data availability, thus parallelism is intrinsic in these systems. On the other hand, with the advance of technology of microelectronics, the FPGA has been used mainly because of its flexibility, facilities to implement complex systems and intrinsic parallelism. One of the challenges is to create tools for programmers who use HLL (High Level Language), such as C language, producing hardware directly. These tools should use the utmost experience of the programmers, the parallelism of dynamic dataflow architecture and the flexibility and parallelism of FPGA to produce efficient hardware optimized for high performance and lower power consumption. The ChipCflow project is a tool that converts application programs written in C language into VHDL, based on the dynamic dataflow architecture. The main goal in this thesis is to define and implement the operators of ChipCflow using dynamic dataflow architecture in FPGA. These operators use tagged tokens to identify data based on instances of operators and their implementation and instances use an asynchronous implementation model in FPGA to achieve faster speed and lower consumption

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-12-01T23:34:00Z No. of bitstreams: 1 DanielHolandaNoronha_DISSERT.pdf: 2617561 bytes, checksum: 88cfc246d074eabfd971d5b81edbf109 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-12-05T21:07:17Z (GMT) No. of bitstreams: 1 DanielHolandaNoronha_DISSERT.pdf: 2617561 bytes, checksum: 88cfc246d074eabfd971d5b81edbf109 (MD5) / Made available in DSpace on 2017-12-05T21:07:18Z (GMT). No. of bitstreams: 1 DanielHolandaNoronha_DISSERT.pdf: 2617561 bytes, checksum: 88cfc246d074eabfd971d5b81edbf109 (MD5) Previous issue date: 2017-11-20 / A import?ncia do uso de FPGAs como aceleradores vem crescendo fortemente nos ?ltimos anos. Companhias como Amazon e Microsoft est?o incorporando FPGAs em seus data centers, objetivando especialmente acelerar algoritmos em suas ferramentas de busca. No centro dessas aplica??es est?o algoritmos de aprendizado de m?quina, como ? o caso da M?quina de Vetor de Suporte (SVM). Entretanto, para que essas aplica??es obtenham a acelera??o desejada, o uso eficiente dos recursos das FPGAs ? necess?rio. O projeto possui como objetivo a implementa??o paralela em hardware tanto da fase feed-forward de uma M?quina de Vetores de Suporte (SVM) quanto de sua fase de treinamento. A fase feed-forward (infer?ncia) ? implementada utilizando o kernel polinomial e de maneira totalmente paralela, visando obter a m?xima acelera??o poss?vel ao custo de uma maior utiliza??o da ?rea dispon?vel. Al?m disso, a implementa??o proposta para a infer?ncia ? capaz de computar tanto a classifica??o quanto a regress?o utilizando o mesmo hardware. J? o treinamento ? feito utilizando Otimiza??o Sequencial M?nima (SMO), possibilitando a resolu??o da complexa otimiza??o da SVM atrav?s de passos simples. A implementa??o da SMO tamb?m ? feita de modo extremamente paralelo, fazendo uso de t?cnicas para acelera??o como a cache do erro. Ademais, o Kernel Amig?vel ao Hardware (HFK) ? utilizado para diminuir a ?rea utilizada pelo kernel, permitindo que um n?mero maior de kernels seja implementado em um chip de mesmo tamanho, acelerando o treinamento. Ap?s a implementa??o paralela em hardware, a SVM ? validada por simula??o e s?o feitas an?lises associadas ao desempenho temporal da estrutura proposta, assim como an?lises associadas ao uso de ?rea da FPGA. / The importance of Field-Programmable Gate Arrays as compute accelerators has dramatically increased during the last couple of yers. Many companies such as Amazon, IBM and Microsoft included FPGAs in their data centers aiming to accelerate their search engines. In the center of those applications are many machine learning algorithms, such as Support Vector Machines (SVMs). For FPGAs to thrive in this new role, the effective usage of FPGA resources is required. The project?s main goal is the parallel FPGA implementation of both the feed-forward phase of a Support Vector Machine as well as its training phase. The feed-forward phase (inference) is implemented using the polynomial kernel in a highly parallel way in order to obtain maximum throughput at the cost of some extra area. Moreover, the inference implementation is capable of computing both classification and regression using a single hardware. The training phase of the SVM is implemented using Sequential Minimal Optimization (SMO), which enables the resolution of a complex convex optimization problem using simple steps. The SMO implementation is also highly parallel and uses some acceleration techniques, such as the error cache. Moreover, the Hardware Friendly Kernel (HFK) is used in order to reduce the kernel?s area, enabling the increase in the number of kernels per area. After the parallel implementation in hardware, the SVM is validated by simulation. Finally, analysis associated with the temporal performance of the proposed structure, as well as analysis associated with FPGA?s area usage are performed.

Orientador: Luis Geraldo Pedroso Meloni / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T05:58:36Z (GMT). No. of bitstreams: 1 LemesFilho_JoseMatias.pdf: 2987431 bytes, checksum: 93fc757a06215b93a08427d2f33f88a2 (MD5) Previous issue date: 2009 / Resumo: Este trabalho descreve o estudo, a pesquisa e compilação de técnicas de otimização de códigos em FPGA (Field Programmable Gate Arrays) utilizando uma ferramenta de prototipagem rápida. Para isso, foram implementados alguns algoritmos para auxiliar na apresentação e avaliação de quatro técnicas de otimização: uso de recursos alternativos, multiplexação no tempo, algoritmos alternativos e mudança da freqüência sistêmica. As principais contribuições do presente trabalho foram: compilar em um único documento diversas técnicas para geração eficiente de códigos de processamento digital de sinais; o estudo das etapas de fluxo de projeto baseado em ferramentas de prototipagem rápida; implementações de diversos algoritmos para demonstrar as técnicas de otimização, visando-se o estudo da minimização da área de ocupação em FPGA. Com o uso das técnicas pode-se alcançar uma redução de área da FPGA de até 90%, conforme a complexidade do sistema alvo. / Abstract: This work describes the study, research and compilation of programming optimization techniques for FPGA (Field Programmable Gate Arrays) using a tool technology for rapid prototyping. For this purpose, some algorithms have been implemented to help the presentation and evaluation of four optimization techniques: alternative resources usage, time multiplexing, alternative algorithms and systemic frequency change. The main contributions of this work are: compilation in one document several efficient techniques for generation code in digital signal processing; study of the phases of design flow were based on rapid prototyping tools; implementations of several algorithms to demonstrate the optimization techniques, looking for the minimization of the FPGA occupation area. With the use of these techniques, it is possible to reach a FPGA area reduction of up to 90%, depending of the complexity of the target system. / Universidade Estadual de Campi / Telecomunicações e Telemática / Mestre em Engenharia Elétrica