The object of the thesis research is to realize a complex-valued QR decomposition (QRD) algorithm on FPGAs for MIMO communication systems. The challenge is to implement a QRD processor that efficiently utilizes hardware resources to meet throughput requirements in MIMO systems. By studying the basic QRD algorithm using Givens rotations and the CORDIC algorithm, the thesis develops a master-slave structure to more efficiently implement CORDIC-based Givens rotations compared to traditional methods. Based on the master-slave structure, an processing-element array architecture is proposed to further improve result precision and to achieve near-theoretical latency with parallelized normalization and rotations. The proposed architecture also demonstrates flexible scalability through implementations for different sizes of QRDs. The QRD implementations can process 7.41, 1.90 and 0.209 million matrices per second for two by two, four by four and eight by eight QRDs respectively. This study has built the foundation to develop QRD processors that can fulfill high throughput requirements for MIMO systems.

Resumo: O objetivo da pesquisa descrita nesta tese foi estudar possíveis aplicações do método das rotações modificadas de Givens na solução de sistemas de equações lineares tipicamente observados em problemas de melhoramento animal. Duas aplicações foram consideradas: a predição de valores genéticos com base em informação fenotípica e genealógica, por meio da metodologia dos modelos mistos; e a predição de valores genéticos com base em informação molecular, obtida pela genotipagem de painéis densos de SNPs. Na primeira aplicação, delineou-se o emprego de um modelo animal reduzido, combinado a uma ordenação do sistema que permitiu uma abordagem multi-frontal de decomposição. As matrizes frontais foram definidas como sendo as partes da triangular superior pertinentes a cada rebanho. Com isso, o problema pôde ser desmembrado em n subproblemas em que n é o número de rebanhos. Um conjunto de programas foi desenvolvido de modo a decompor as matrizes de dados de cada rebanho independentemente, e depois combinar as informações de todos eles na solução do sistema triangular geral, por retro-substituição. Concluiu-se que o método pode ser empregado em um sistema para atualização de predições de valor genético sob modelo animal reduzido, em que se aninham os efeitos de vacas dentro de rebanhos. Na segunda aplicação, comparou-se o emprego das rotações de Givens com o método do Gradiente Conjugado, na solução de sistemas lineares envolvidos na estimação de efeitos de SNPs em valores genéticos. O método das rotações demandou menos tempo de processamento e mais memória. Concluiu-se que, dado o crescente avanço em capacidade computacional, o método das rotações pode ser um método numérico viável e apresenta a vantagem de permitir o cálculo dos erros-padrão das estimativas. / Abstract: The aim of this study was to investigate possible applications of the modified Givens rotations on the solution of linear systems that typically arise in animal breeding problems. Two applications were considered: prediction of breeding values based on phenotypes and relationships, using mixed model methods; and prediction of breeding values based on molecular information, using genotypes from high density SNP chips. In the first application, the use of a reduced animal model, combined with a specific ordering of the system, made it possible to apply a multi-frontal decomposition approach. The frontal matrices were defined as the parts of the upper triangular corresponding to each herd. In this way, the problem could be partitioned into n subproblems, where n is the number of herds. A set of programs was developed in order to factorize the data matrix of each herd independently, and then combine the information from all of them while solving the overall triangular system, by back-substitution. The conclusion was that Givens rotations can be used as a numerical method for updating predicted breeding values under a reduced animal model, if dam effects are nested within herds. In the second application, the modified Givens rotations were compared to the Conjugate Gradient method for solving linear systems that arise in the estimation of SNP effects on breeding values. Givens rotations required less processing time but a greater amount of high speed memory. The conclusion was that, given the increasing rate of advance in computer power, Givens rotations can be regarded as a feasible numerical method which presents the advantage that it allows for the calculation of standard errors of estimates. / Orientador: Sandra Aidar de Queiroz / Coorientador: Luiz Alberto Fries / Coorientador: Flávio Schramm Schenkel / Banca: João Meidanis / Banca: Ricardo da Fonseca / Banca: Roberto Carvalheiro / Banca: Adhemar Sanches / Doutor

This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal </p><p>processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented </p><p>to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. </p><p>Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis </p><p>results are not reliable because of the performance analysis tools.</p>

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable </p><p>and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.</p>

Made available in DSpace on 2014-06-11T19:33:33Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-12-18Bitstream added on 2014-06-13T20:45:15Z : No. of bitstreams: 1 pimentel_ecg_dr_jabo.pdf: 351573 bytes, checksum: 4ed13e3cadb5bcefe457a98cb28d9baf (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O objetivo da pesquisa descrita nesta tese foi estudar possíveis aplicações do método das rotações modificadas de Givens na solução de sistemas de equações lineares tipicamente observados em problemas de melhoramento animal. Duas aplicações foram consideradas: a predição de valores genéticos com base em informação fenotípica e genealógica, por meio da metodologia dos modelos mistos; e a predição de valores genéticos com base em informação molecular, obtida pela genotipagem de painéis densos de SNPs. Na primeira aplicação, delineou-se o emprego de um modelo animal reduzido, combinado a uma ordenação do sistema que permitiu uma abordagem multi-frontal de decomposição. As matrizes frontais foram definidas como sendo as partes da triangular superior pertinentes a cada rebanho. Com isso, o problema pôde ser desmembrado em n subproblemas em que n é o número de rebanhos. Um conjunto de programas foi desenvolvido de modo a decompor as matrizes de dados de cada rebanho independentemente, e depois combinar as informações de todos eles na solução do sistema triangular geral, por retro-substituição. Concluiu-se que o método pode ser empregado em um sistema para atualização de predições de valor genético sob modelo animal reduzido, em que se aninham os efeitos de vacas dentro de rebanhos. Na segunda aplicação, comparou-se o emprego das rotações de Givens com o método do Gradiente Conjugado, na solução de sistemas lineares envolvidos na estimação de efeitos de SNPs em valores genéticos. O método das rotações demandou menos tempo de processamento e mais memória. Concluiu-se que, dado o crescente avanço em capacidade computacional, o método das rotações pode ser um método numérico viável e apresenta a vantagem de permitir o cálculo dos erros-padrão das estimativas. / The aim of this study was to investigate possible applications of the modified Givens rotations on the solution of linear systems that typically arise in animal breeding problems. Two applications were considered: prediction of breeding values based on phenotypes and relationships, using mixed model methods; and prediction of breeding values based on molecular information, using genotypes from high density SNP chips. In the first application, the use of a reduced animal model, combined with a specific ordering of the system, made it possible to apply a multi-frontal decomposition approach. The frontal matrices were defined as the parts of the upper triangular corresponding to each herd. In this way, the problem could be partitioned into n subproblems, where n is the number of herds. A set of programs was developed in order to factorize the data matrix of each herd independently, and then combine the information from all of them while solving the overall triangular system, by back-substitution. The conclusion was that Givens rotations can be used as a numerical method for updating predicted breeding values under a reduced animal model, if dam effects are nested within herds. In the second application, the modified Givens rotations were compared to the Conjugate Gradient method for solving linear systems that arise in the estimation of SNP effects on breeding values. Givens rotations required less processing time but a greater amount of high speed memory. The conclusion was that, given the increasing rate of advance in computer power, Givens rotations can be regarded as a feasible numerical method which presents the advantage that it allows for the calculation of standard errors of estimates.