Procedimentos de reconfiguração são usados em diversos sistemas para isolar módulos falhos e recuperar o sistema após a ocorrência de erros. Em ambientes multiprocessadores, onde existe redundância implícita de nodos processadores, vários algoritmos de reconfiguração já foram propostos. Entretanto a maior parte destes algoritmos destina-se a topologias específicas bastante exploradas como, por exemplo, arquiteturas na forma de arrays e árvores. Neste trabalho é apresentada uma estratégia de detecção/reconfiguração para tolerar falhas na máquina T-NODE. Esta máquina possui uma arquitetura multiprocessadora fracamente acoplada, que tem como processador base o transputer. Sua arquitetura de interconexão é definida pelo usuário; a organização de barramentos implementada com base em uma chave crossbar, a qual permite uma variada e fácil gama de opções. Assim, os algoritmos tradicionais de reconfiguração não se aplicam pois são excessivamente restritivos. A análise da arquitetura e do software de baixo nível existentes para a T-NODE revelou recursos praticamente inexistentes a nível de controle de falhas nos processadores e erros no processamento. Mesmo considerando-se que o principal objetivo desta máquina é a obtenção de alto desempenho, é possível implementar procedimentos que melhorem suas características de confiabilidade. Neste estudo é apresentada uma maneira de melhorar o nível de tolerância a falhas da máquina de modo que ela possa ser usada em tarefas mais exigentes do ponto de vista de confiabilidade, sem perda excessiva de desempenho. A estratégia definda usa a técnica de redundância dinâmica com detecção de falhas on-line e recuperação do sistema através do isolamento da falha por reconfiguração e conseqüente reinicialização do sistema. A validação da estratégia foi feita pela construção de um protótipo utilizando a linguagem OCCAM2 e um processador transputer conectado ao barramento de um microcomputador PC. No protótipo foram implementados três processos distintos: o testador, o supervisor e o reconfigurador. Estes processos têm respectivamente, as funções de testar os nodos processadores, supervisionar os resultados dos testes e reconfigurar o sistema quando da ocorrência de uma falha. / In many systems, reconfiguration strategies are used to remove failed components and to recuperate system from the resulting errors. Various reconfiguration algorithms have been proposed with the goal of covering faults in multiprocessing systems, but most of them support only specific architecture styles, as arrays or trees. In this study, a reconfiguration algorithm is proposed whose goal is to tolerate faults in the T-NODE machine. The T-NODE is a loosed coupled, multiprocessor machine based on transputers. The analysis of the architecture and of the system software existing for the T-NODE has shown that, in practice, there were not special resources aiming to control processor faults and processing errors. Even considering that the main goal of this machine is processing with high performance, it is possible to implement alternative procedures which result in better reliability characteristics. By other way, the interconnection architecture of this machine is defined by the user; its bus organization implemented with the aid of a crossbar switch allows choices among several possibilities. Consequently, traditional algorithms do not apply because they are too restrictive. Therefore, the research here related aims to improve the fault-tolerance parameters of this machine without changing significantly its original performance. The strategy here presented uses a dynamic redundancy technique with on-line fault detection; system recovery is get by logically isolating the faulty module, reconfiguring the others and restarting the system. The validation of the strategy has been done with the construction of a prototype using the OCCAM2 language and a transputer processor connected to the bus of a microcomputer (PC). Three different processes have been implemented in the prototype: the tester, the supervisior and the reconfigurator. These processes have respectively the functions of: testing the processing nodes, to supervise tests results and to reconfigure the system under fault occurrence.

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2017-04-07T22:12:32Z No. of bitstreams: 1 JulieneVC_DISSERT.pdf: 3209854 bytes, checksum: 18b673023a841a782fbe0c6f32a66254 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-13T15:05:50Z (GMT) No. of bitstreams: 1 JulieneVC_DISSERT.pdf: 3209854 bytes, checksum: 18b673023a841a782fbe0c6f32a66254 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-13T15:05:59Z (GMT) No. of bitstreams: 1 JulieneVC_DISSERT.pdf: 3209854 bytes, checksum: 18b673023a841a782fbe0c6f32a66254 (MD5) / Made available in DSpace on 2017-04-13T15:06:08Z (GMT). No. of bitstreams: 1 JulieneVC_DISSERT.pdf: 3209854 bytes, checksum: 18b673023a841a782fbe0c6f32a66254 (MD5) Previous issue date: 2016-09-09 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Parallel architectures require optimized code that exploits its new features. Some architectures follow the paradigm of Von Neumann machine, while others differ from this model, such as IPNoSys processor. This processor is based on network-on-chip and features a package-driven computer model driven which reflects in its programming model. Initially, this architecture had an assembler and a simulator and needed a compiler. In later papers compilers for IPNoSys have been developed, but none fully explored the features of this architecture. Thus, the objective of this paper is to define a code optimization step in IPNoSys compiler, considering characteristics unexploited as parallelism and improving your generated code. The optimization module offers three levels of optimization. In order to evaluate the created module, made a comparison of the execution time and the size of codes generated in the three levels of optimization. It was obtained that an optimization level showed better run time, but generated applications with a larger size, while another level showed a smaller size. Furthermore, there was an improvement in the generated code / As arquiteturas paralelas necessitam de código otimizado que explore seus novos recursos. Algumas arquiteturas seguem o paradigma da máquina de Von Neumann, enquanto que outras divergem desse modelo, um exemplo é o processador IPNoSys. Esse processador foi baseado em redes-em-chip e apresenta um modelo de computação dirigido a pacotes o que reflete no seu modelo de programação. Inicialmente, essa arquitetura possuía um montador e um simulador e necessitava de um compilador. Em trabalhos posteriores compiladores para a IPNoSys foram desenvolvidos, mas nenhum explorou completamente as características dessa arquitetura. Com isso, o objetivo deste trabalho é definir uma etapa de otimização de código no compilador IPNoSys, considerando características não exploradas como o paralelismo e melhorando seu código gerado. O módulo de otimização oferece três níveis de otimização. A fim de avaliar o módulo criado, efetuou-se uma comparação do tempo de execução e do tamanho dos códigos gerados nos três níveis de otimização. Foi obtido que um nível de otimização apresentou melhor tempo de execução, porém gerou aplicações com um maior tamanho, enquanto que outro nível apresentou um menor tamanho. Além disso, houve uma melhoria nos códigos gerados / 2017-04-07

Procedimentos de reconfiguração são usados em diversos sistemas para isolar módulos falhos e recuperar o sistema após a ocorrência de erros. Em ambientes multiprocessadores, onde existe redundância implícita de nodos processadores, vários algoritmos de reconfiguração já foram propostos. Entretanto a maior parte destes algoritmos destina-se a topologias específicas bastante exploradas como, por exemplo, arquiteturas na forma de arrays e árvores. Neste trabalho é apresentada uma estratégia de detecção/reconfiguração para tolerar falhas na máquina T-NODE. Esta máquina possui uma arquitetura multiprocessadora fracamente acoplada, que tem como processador base o transputer. Sua arquitetura de interconexão é definida pelo usuário; a organização de barramentos implementada com base em uma chave crossbar, a qual permite uma variada e fácil gama de opções. Assim, os algoritmos tradicionais de reconfiguração não se aplicam pois são excessivamente restritivos. A análise da arquitetura e do software de baixo nível existentes para a T-NODE revelou recursos praticamente inexistentes a nível de controle de falhas nos processadores e erros no processamento. Mesmo considerando-se que o principal objetivo desta máquina é a obtenção de alto desempenho, é possível implementar procedimentos que melhorem suas características de confiabilidade. Neste estudo é apresentada uma maneira de melhorar o nível de tolerância a falhas da máquina de modo que ela possa ser usada em tarefas mais exigentes do ponto de vista de confiabilidade, sem perda excessiva de desempenho. A estratégia definda usa a técnica de redundância dinâmica com detecção de falhas on-line e recuperação do sistema através do isolamento da falha por reconfiguração e conseqüente reinicialização do sistema. A validação da estratégia foi feita pela construção de um protótipo utilizando a linguagem OCCAM2 e um processador transputer conectado ao barramento de um microcomputador PC. No protótipo foram implementados três processos distintos: o testador, o supervisor e o reconfigurador. Estes processos têm respectivamente, as funções de testar os nodos processadores, supervisionar os resultados dos testes e reconfigurar o sistema quando da ocorrência de uma falha. / In many systems, reconfiguration strategies are used to remove failed components and to recuperate system from the resulting errors. Various reconfiguration algorithms have been proposed with the goal of covering faults in multiprocessing systems, but most of them support only specific architecture styles, as arrays or trees. In this study, a reconfiguration algorithm is proposed whose goal is to tolerate faults in the T-NODE machine. The T-NODE is a loosed coupled, multiprocessor machine based on transputers. The analysis of the architecture and of the system software existing for the T-NODE has shown that, in practice, there were not special resources aiming to control processor faults and processing errors. Even considering that the main goal of this machine is processing with high performance, it is possible to implement alternative procedures which result in better reliability characteristics. By other way, the interconnection architecture of this machine is defined by the user; its bus organization implemented with the aid of a crossbar switch allows choices among several possibilities. Consequently, traditional algorithms do not apply because they are too restrictive. Therefore, the research here related aims to improve the fault-tolerance parameters of this machine without changing significantly its original performance. The strategy here presented uses a dynamic redundancy technique with on-line fault detection; system recovery is get by logically isolating the faulty module, reconfiguring the others and restarting the system. The validation of the strategy has been done with the construction of a prototype using the OCCAM2 language and a transputer processor connected to the bus of a microcomputer (PC). Three different processes have been implemented in the prototype: the tester, the supervisior and the reconfigurator. These processes have respectively the functions of: testing the processing nodes, to supervise tests results and to reconfigure the system under fault occurrence.

Procedimentos de reconfiguração são usados em diversos sistemas para isolar módulos falhos e recuperar o sistema após a ocorrência de erros. Em ambientes multiprocessadores, onde existe redundância implícita de nodos processadores, vários algoritmos de reconfiguração já foram propostos. Entretanto a maior parte destes algoritmos destina-se a topologias específicas bastante exploradas como, por exemplo, arquiteturas na forma de arrays e árvores. Neste trabalho é apresentada uma estratégia de detecção/reconfiguração para tolerar falhas na máquina T-NODE. Esta máquina possui uma arquitetura multiprocessadora fracamente acoplada, que tem como processador base o transputer. Sua arquitetura de interconexão é definida pelo usuário; a organização de barramentos implementada com base em uma chave crossbar, a qual permite uma variada e fácil gama de opções. Assim, os algoritmos tradicionais de reconfiguração não se aplicam pois são excessivamente restritivos. A análise da arquitetura e do software de baixo nível existentes para a T-NODE revelou recursos praticamente inexistentes a nível de controle de falhas nos processadores e erros no processamento. Mesmo considerando-se que o principal objetivo desta máquina é a obtenção de alto desempenho, é possível implementar procedimentos que melhorem suas características de confiabilidade. Neste estudo é apresentada uma maneira de melhorar o nível de tolerância a falhas da máquina de modo que ela possa ser usada em tarefas mais exigentes do ponto de vista de confiabilidade, sem perda excessiva de desempenho. A estratégia definda usa a técnica de redundância dinâmica com detecção de falhas on-line e recuperação do sistema através do isolamento da falha por reconfiguração e conseqüente reinicialização do sistema. A validação da estratégia foi feita pela construção de um protótipo utilizando a linguagem OCCAM2 e um processador transputer conectado ao barramento de um microcomputador PC. No protótipo foram implementados três processos distintos: o testador, o supervisor e o reconfigurador. Estes processos têm respectivamente, as funções de testar os nodos processadores, supervisionar os resultados dos testes e reconfigurar o sistema quando da ocorrência de uma falha. / In many systems, reconfiguration strategies are used to remove failed components and to recuperate system from the resulting errors. Various reconfiguration algorithms have been proposed with the goal of covering faults in multiprocessing systems, but most of them support only specific architecture styles, as arrays or trees. In this study, a reconfiguration algorithm is proposed whose goal is to tolerate faults in the T-NODE machine. The T-NODE is a loosed coupled, multiprocessor machine based on transputers. The analysis of the architecture and of the system software existing for the T-NODE has shown that, in practice, there were not special resources aiming to control processor faults and processing errors. Even considering that the main goal of this machine is processing with high performance, it is possible to implement alternative procedures which result in better reliability characteristics. By other way, the interconnection architecture of this machine is defined by the user; its bus organization implemented with the aid of a crossbar switch allows choices among several possibilities. Consequently, traditional algorithms do not apply because they are too restrictive. Therefore, the research here related aims to improve the fault-tolerance parameters of this machine without changing significantly its original performance. The strategy here presented uses a dynamic redundancy technique with on-line fault detection; system recovery is get by logically isolating the faulty module, reconfiguring the others and restarting the system. The validation of the strategy has been done with the construction of a prototype using the OCCAM2 language and a transputer processor connected to the bus of a microcomputer (PC). Three different processes have been implemented in the prototype: the tester, the supervisior and the reconfigurator. These processes have respectively the functions of: testing the processing nodes, to supervise tests results and to reconfigure the system under fault occurrence.

O modelo a fluxo de dados tem grande destaque em pesquisas em arquiteturas de alto desempenho. Neste modelo, o controle de execução é feito apenas pela disponibilidade dos dados, permitindo que seja explorado o máximo de paralelismo implícito em um programa. As propostas que serão expostas neste trabalho visam solucionar um particular problema da máquina de fluxo de dados de Manchester. Esta arquitetura para tratar código reentrante, impõe que as fichas de dados, além da indicação da instrução destino, possuam um rótulo. Estas informações extras, que formam 70% da ficha de dado, fazem com que a implantação da máquina seja complexa. Assim, o hardware impõe um sério limite a velocidade de processamento, impedindo a plena utilização do modelo. Neste trabalho, serão apresentadas propostas para a redução do número de informações necessárias para o correto funcionamento da máquina, possibilitando uma implementação mais simples e mais eficiente. / The dataflow model is specially relevant you research in high-performance architectures. In this model, the execution control is done by taking into account only the dates availability, thus allowing maximum exploitation of the paralelism implicit in programs. The present work is based on the Manchester dataflow machine, which, in to order you handle the reentran code, imposes the dates token you have, in addition you the destination instruction Field, albel. Additional This information, which corresponds you 70% of the dates token, compounds the machine implementation it substantially bounds the execution speed and prevents the full model utilization. This work presents approaches will be reducing the amount of information needed will be to proper machine operation in to order you achieve to simpler and lives effective implementation.

Neste trabalho é apresentada a arquitetura SEED, proposta a partir das experiências adquiridas com as arquiteturas baseadas no modelo a fluxo de dados que foram estudadas até o presente. A arquitetura SEED utiliza o modelo a fluxo de dados para escalonar e executar blocos de instruções, visando aproveitar a principal qualidade apresentada pelo modelo, que consiste em expor o máximo de paralelismo existente nos programas. No entanto, a arquitetura explora paralelismo de granularidade mais grossa que as arquiteturas a fluxo de dados, a fim de reduzir o trafego de fichas de dados na arquitetura. Esta redução tenta resolver ou amenizar problemas como a excessiva ocupação de memória e a grande complexidade exigida do hardware. Além da especificação da funcionalidade de toda a arquitetura SEED, este trabalho apresenta uma proposta para o particionamento do código. A utilização desta proposta permite a geração de blocos de códigos que podem ser executados corretamente pela arquitetura SEED. Alguns benchmarks foram gerados utilizando essa proposta de particionamento de código. Estes benchmarks foram executados no simulador da arquitetura SEED, visando analisar e avaliar o comportamento da arquitetura com diversas configurações de hardware. / In this work is presented the SEED architecture. This architecture was proposed considering the experiences obtained with existing architectures based on dataflow model. The SEED architecture uses dataflow model to schedule and execute sets of instructions, called code blocks. This approach tries to make use of the main quality of the dataflow model that is to expose the maximum parallelism of the programs. However, this architecture explores coarser granularity than the one usually considered in dataflow architectures in order to reduce the data token traffic in the architecture. This type of reduction tries to solve problems like excessive occupation of memory and high complexity of the hardware. Besides the specification of all units that compose the SEED architecture, this work also proposes a way of partitioning programs, creating code blocks that may be executed by SEED architecture. Some benchmarks were generated using this proposal for partitioning programs. These benchmarks were executed in the SEED architecture simulator, in order to analyze the behavior of the proposed architecture under special configurations.

Flexible pipes are used in the offshore oil production to transport fluid and gas from the sea bead to the floating stations, and vice versa. These pipes have several concentric layers, of different materials, geometries and structural functions, since they are exposed to adverse operating environments, subjected to high internal and external pressures, high axial stresses and a series of dynamic loads. The local analysis is an important stage of a flexible pipe design and it consists on determining the stresses and strains distributions along the layers of the pipe. Multipurpose finite element packages are commonly used in the local analysis of flexible pipes, but they possess many limitations due to its generic nature, varying from the absence of specific tools for model creation to heavy restrictions of the number of degrees-of-freedom to make computational processing feasible. At the Polytechnic School of the University of São Paulo, within a research line in progress, several finite macroelements were formulated specifically for structural analysis of flexible pipes, taking into account their particularities, such as geometric patterns and layers assemblage. However, the numerical tools that implement these elements present very high memory and processing consumptions, limiting its usage for large-scale models. Therefore, this work has been motivated by memory and processing limitations of finite element structural analysis of flexible pipes for offshore applications. In this context, the Element-by-Element method, which does not require the global stiffness matrix, was chosen for its potential in memory reduction and processing capabilities, given its scalability and ease of parallelization. After an extensive literature review on numerical methods regarding the EBE method, it was chosen the Element-by-Element Diagonal Preconditioned Conjugate Gradient Method (EBE-PCG) algorithm. Aiming higher computational performance, the finite macroelements formulated by (PROVASI, 2013) were converted to the C++ language, implemented and parallelized in a new analysis tool, named as PipeFEM. The diagonal preconditioned EBE-PCG algorithm was implemented and parallelized with OpenMP. The scalability of the PCG algorithm is directly influenced by the efficiency of the matrix-vector product, an operation that, in the element-by-element method, is computed in a local basis with the blocks that comprise the model, and that requires synchronization techniques when performed in parallel. Four different synchronization strategies were developed, being the one based on geometric- and mesh- based mappings the most efficient of them. Numerical experiments showed a reduction of almost 92% in the EBE-PCG solution time of the parallelized version in comparison to the sequential one. In order to compare the efficiency of PipeFEM with the well-established finite element package ANSYS, a simplified flexible pipe was modeled in both software. PipeFEM was approximately 82 times faster than ANSYS to solve the problem, spending 24.27 seconds against 33 minutes and 18 seconds. In addition to this, PipeFEM required much less memory, 61.8MB against 6.8GB in ANSYS. In comparison to the dense version of MacroFEM, a reduction of more than three orders of magnitude was achieved in memory consumption. Despite the low the rate of convergence presented by the diagonal preconditioner, the implementation is very efficient in computational terms. Therefore, the objectives of this work were fulfilled with the development and application of the EBE method, allowing a reduction of memory and simulation costs. / Tubos flexíveis são utilizados na produção offshore de petróleo para o transporte de fluidos e gás natural das estruturas submersas até as estações flutuantes, e vice-versa. Estes tubos possuem diversas camadas concêntricas, de diferentes materiais, geometrias e funções estruturais, pois são expostos a ambientes adversos de operação, nos quais são submetidos à elevadas pressões internas e externas, elevados carregamentos e tensões axiais, além de uma série de carregamentos dinâmicos. A análise local é uma etapa importante do dimensionamento de um tubo flexível e consiste em determinar as distribuições de tensões e deformações ao longo das camadas do tubo. Pacotes multiuso de elementos finitos são comumente utilizados na análise local de tubos flexíveis, mas, devido as suas naturezas genéricas, possuem limitações que variam desde a ausência de ferramentas específicas para a criação de modelos até restrições pesadas no número total de graus de liberdade para tornar exequível o processo computacional. Na Escola Politécnica da Universidade de São Paulo, dentro de uma linha de pesquisa em andamento, diversos macroelementos finitos foram formulados especificamente para a análise estrutural de tubos flexíveis, levando em consideração as suas particularidades, como por exemplo padrões de geometrias e de montagem de camadas. Entretanto, a ferramenta numérica que implementa esses elementos apresenta elevado consumo de memória e de processamento, o que limita o seu uso para modelos de grande escala. Portanto, este trabalho foi motivado por limitações de memória e processamento em análises estruturais com o método dos elementos finitos para tubos flexíveis de aplicações offshore. Neste contexto, o método elemento-a-elemento, caracterizado pela eliminação da matriz global de rigidez, foi escolhido devido ao seu potencial de redução de consumo de memória e às suas capacidades de processamento, dada a sua escalabilidade e facilidade de paralelização. Após uma extensa revisão bibliográfica em métodos numéricos a respeito do método EBE, foi escolhido a versão diagonalmente precondicionada do método do gradiente conjugado (EBE-PCG). Com o intuito de se obter maior performance computacional, os macroelementos finitos formulados por (PROVASI, 2013) foram convertidos para a linguagem C++, paralelizados e implementado em uma nova ferramenta de análise chamada de PipeFEM, totalmente escrita em C++ e que explora paralelismo em todos as etapas. O algoritmo EBE-PCG foi implementado e paralelizado com OpenMP. A escalabilidade do algoritmo PCG é diretamente influenciada pela eficiência do produto entre matriz e vetor, uma operação que no método elemento-a-elemento é calculada na base local com os blocos que compõem o modelo, o que requer técnicas de sincronização quando realizada de modo paralelo. Quatro diferentes estratégias de sincronização foram desenvolvidas, sendo a mais eficiente delas a que utilizada mapeamentos baseados em características da geometria e malha. Experimentos numéricos mostraram uma redução de quase 92% no tempo de simulação do algoritmo PCG da versão paralelizada em relação à sequencial. De modo a comparar a eficiência do PipeFEM com o pacote bem estabelecido de elementos finitos, ANSYS, um tubo simplificado foi modelado em ambos os programas. PipeFEM foi aproximadamente 82 vezes mais rápido do que o ANSYS, gastando 24.27 segundos contra 33 minutos e 18 segundos. Além disso, PipeFEM consumiu muito menos memória, 61.8MB contra 6.8GB in ANSYS. Em comparação com a versão densa do MacroFEM, uma redução superior a três ordens de grandeza no consum e de memória foi obtida. Assim, apesar da baixa taxa de convergência apresentada pelo precondicionador diagonal, a implementação está muito eficiente em termos computacionais. Portanto, os objetivos deste trabalho foram alcançados com o desenvolvimento e aplicação do método EBE, o que permitiu uma redução considerável dos custos de simulação e memória.

Amostras de DNA são encontradas em fragmentos, obtidos em vestígios de uma cena de crime, ou coletados de amostras de cabelo ou sangue, para testes genéticos ou de paternidade. Para identificar se esse fragmento pertence ou não a uma sequência de DNA, é necessário compará-los com uma sequência determinada, que pode estar armazenada em um banco de dados para, por exemplo, apontar um suspeito. Para tal, é preciso uma ferramenta eficiente para realizar o alinhamento da sequência de DNA encontrada com a armazenada no banco de dados. O alinhamento de sequências de DNA, em inglês DNA matching, é o campo da bioinformática que tenta entender a relação entre as sequências genéticas e suas relações funcionais e parentais. Essa tarefa é frequentemente realizada através de softwares que varrem clusters de base de dados, demandando alto poder computacional, o que encarece o custo de um projeto de alinhamento de sequências de DNA. Esta dissertação apresenta uma arquitetura de hardware paralela, para o algoritmo BLAST, que permite o alinhamento de um par de sequências de DNA. O algoritmo BLAST é um método heurístico e atualmente é o mais rápido. A estratégia do BLAST é dividir as sequências originais em subsequências menores de tamanho w. Após realizar as comparações nessas pequenas subsequências, as etapas do BLAST analisam apenas as subsequências que forem idênticas. Com isso, o algoritmo diminui o número de testes e combinações necessárias para realizar o alinhamento. Para cada sequência idêntica há três etapas, a serem realizadas pelo algoritmo: semeadura, extensão e avaliação. A solução proposta se inspira nas características do algoritmo para implementar um hardware totalmente paralelo e com pipeline entre as etapas básicas do BLAST. A arquitetura de hardware proposta foi implementada em FPGA e os resultados obtidos mostram a comparação entre área ocupada, número de ciclos e máxima frequência de operação permitida, em função dos parâmetros de alinhamento. O resultado é uma arquitetura de hardware em lógica reconfigurável, escalável, eficiente e de baixo custo, capaz de alinhar pares de sequências utilizando o algoritmo BLAST. / DNA samples are found in fragments, obtained in traces of a crime scene, collected from hair or blood samples, for genetic or paternity tests. To identify whether this fragment belongs or not to a given DNA sequence it is necessary to compare it with a determined sequence which usually come from a database, for instance, to point a suspect. To this end, we need an efficient tool to perform the alignment of the DNA sequence found with the ones stored in the database. The alignment of DNA sequences, which is a field of bioinformatics that helps to understand the relationship between genetic sequences and their functional relationships and parenting. This task is often performed by software that scan clusters of databases, which requires high computing effort, thus increasing the cost of DNA sequences alignment projects. This work presents a parallel hardware architecture, for BLAST algorithm, to DNA pairwise alignment. This is the original version of the BLAST algorithm, that resulted in several other versions. The BLAST algorithm is a heuristic method and is the fastest algorithm for sequence alignment. The strategy of BLAST is to divide the sequences into smaller subsequences of size w. After making comparisons in these subsequences, algorithm steps analyzes only the subsequences that are identical. Thus, reducing the number of tests and combinations needed to perform the alignment. For each identical sequence found, three steps are followed by the algorithm: seeding, extension and evaluation. The proposed hardware architecture is based on the characteristics of the algorithm to implement a fully parallel hardware, where the basic steps of BLAST are pipelined. The proposed architecture was implemented in FPGA and the results show a comparison between the area occupied, number of cycles and maximum frequency of operation permitted, as a function of alignment parameters. The result is a hardware architecture in reconfigurable logic, scalable, efficient and with low cost, capable of aligning the pairs of sequences using BLAST algorithm.

Amostras de DNA são encontradas em fragmentos, obtidos em vestígios de uma cena de crime, ou coletados de amostras de cabelo ou sangue, para testes genéticos ou de paternidade. Para identificar se esse fragmento pertence ou não a uma sequência de DNA, é necessário compará-los com uma sequência determinada, que pode estar armazenada em um banco de dados para, por exemplo, apontar um suspeito. Para tal, é preciso uma ferramenta eficiente para realizar o alinhamento da sequência de DNA encontrada com a armazenada no banco de dados. O alinhamento de sequências de DNA, em inglês DNA matching, é o campo da bioinformática que tenta entender a relação entre as sequências genéticas e suas relações funcionais e parentais. Essa tarefa é frequentemente realizada através de softwares que varrem clusters de base de dados, demandando alto poder computacional, o que encarece o custo de um projeto de alinhamento de sequências de DNA. Esta dissertação apresenta uma arquitetura de hardware paralela, para o algoritmo BLAST, que permite o alinhamento de um par de sequências de DNA. O algoritmo BLAST é um método heurístico e atualmente é o mais rápido. A estratégia do BLAST é dividir as sequências originais em subsequências menores de tamanho w. Após realizar as comparações nessas pequenas subsequências, as etapas do BLAST analisam apenas as subsequências que forem idênticas. Com isso, o algoritmo diminui o número de testes e combinações necessárias para realizar o alinhamento. Para cada sequência idêntica há três etapas, a serem realizadas pelo algoritmo: semeadura, extensão e avaliação. A solução proposta se inspira nas características do algoritmo para implementar um hardware totalmente paralelo e com pipeline entre as etapas básicas do BLAST. A arquitetura de hardware proposta foi implementada em FPGA e os resultados obtidos mostram a comparação entre área ocupada, número de ciclos e máxima frequência de operação permitida, em função dos parâmetros de alinhamento. O resultado é uma arquitetura de hardware em lógica reconfigurável, escalável, eficiente e de baixo custo, capaz de alinhar pares de sequências utilizando o algoritmo BLAST. / DNA samples are found in fragments, obtained in traces of a crime scene, collected from hair or blood samples, for genetic or paternity tests. To identify whether this fragment belongs or not to a given DNA sequence it is necessary to compare it with a determined sequence which usually come from a database, for instance, to point a suspect. To this end, we need an efficient tool to perform the alignment of the DNA sequence found with the ones stored in the database. The alignment of DNA sequences, which is a field of bioinformatics that helps to understand the relationship between genetic sequences and their functional relationships and parenting. This task is often performed by software that scan clusters of databases, which requires high computing effort, thus increasing the cost of DNA sequences alignment projects. This work presents a parallel hardware architecture, for BLAST algorithm, to DNA pairwise alignment. This is the original version of the BLAST algorithm, that resulted in several other versions. The BLAST algorithm is a heuristic method and is the fastest algorithm for sequence alignment. The strategy of BLAST is to divide the sequences into smaller subsequences of size w. After making comparisons in these subsequences, algorithm steps analyzes only the subsequences that are identical. Thus, reducing the number of tests and combinations needed to perform the alignment. For each identical sequence found, three steps are followed by the algorithm: seeding, extension and evaluation. The proposed hardware architecture is based on the characteristics of the algorithm to implement a fully parallel hardware, where the basic steps of BLAST are pipelined. The proposed architecture was implemented in FPGA and the results show a comparison between the area occupied, number of cycles and maximum frequency of operation permitted, as a function of alignment parameters. The result is a hardware architecture in reconfigurable logic, scalable, efficient and with low cost, capable of aligning the pairs of sequences using BLAST algorithm.