A eficiência e o desempenho dos FPGAs de ponto flutuante têm sido limitados por longas latências e congestionamento de encaminhamento. Além disso, o fluxo de design tradicional de FPGA, baseado na escrita de descrições de hardware ao nível do registo em Verilog ou VHDL, não é adequado para a implementação de algoritmos complexos de ponto flutuante.
A Altera desenvolveu um novo fluxo de design de ponto flutuante que visa simplificar a implementação de algoritmos de processamento digital de sinais em ponto flutuante nos FPGAs da Altera, permitindo que estes projetos atinjam os mais elevados níveis de desempenho e eficiência até à data. Em vez de construir um caminho de dados composto por operadores de ponto flutuante elementares (por exemplo, multiplicação seguida de adição seguida de exponenciação), o compilador de ponto flutuante gera um caminho de dados que combina operadores elementares numa única função ou caminho de dados. Isto elimina as redundâncias presentes nos projetos tradicionais de FPGA de ponto flutuante. Além disso, o fluxo de projeto da Altera é um fluxo de projeto de alto nível, baseado em modelos, que utiliza o conjunto de blocos avançados DSP Builder da Altera com o MATLAB e o MathWorks Simulink. A Altera espera que esta abordagem de alto nível permita aos designers de FPGA implementar e verificar algoritmos complexos de ponto flutuante mais rapidamente do que com o design tradicional baseado em HDL.
A BDTI realizou uma análise independente do fluxo de projeto de DSP de ponto flutuante da Altera. O objetivo da BDTI era compreender o desempenho alcançável com os FPGAs da Altera para aplicações de DSP de ponto flutuante de alto nível e avaliar a usabilidade do fluxo de projeto de DSP de ponto flutuante da Altera. Este artigo apresenta as conclusões da BDTI, juntamente com informação contextual e detalhes da metodologia utilizada.
1. Introdução
Dois exemplos de design de ponto flutuante
Os avanços nos chips digitais permitem que algoritmos complexos, anteriormente restritos à investigação, entrem em aplicações comuns de computação embarcada. Por exemplo, a álgebra linear (e especificamente a solução de sistemas envolvendo grandes conjuntos de equações lineares simultaneamente) tem sido utilizada há muitos anos principalmente em investigação, onde estão disponíveis recursos computacionais de grande escala e os cálculos em tempo real não são geralmente necessários. A resolução de grandes sistemas requer a inversão de matrizes ou algum tipo de decomposição matricial. Para além dos requisitos de capacidade computacional, estas técnicas podem sofrer de instabilidade numérica se não for utilizada uma gama dinâmica suficiente. Assim sendo, a implementação eficiente e precisa destes algoritmos só é viável em dispositivos de ponto flutuante.
A Altera introduziu recentemente capacidades de computação de ponto flutuante no seu kit de ferramentas DSP Builder Advanced Blockset para simplificar a implementação de algoritmos DSP de ponto flutuante nos FPGAs da Altera e melhorar o desempenho e a eficiência dos projetos de ponto flutuante em comparação com as técnicas tradicionais de design de FPGA. Num artigo anterior [1], a BDTI analisou e avaliou o desempenho e a eficiência do kit de ferramentas de software Quartus II v11.0 da Altera numa implementação de exemplo do solver de Cholesky de ponto flutuante de canal único, sintetizado para os FPGAs Stratix IV e Arria IV de 40 nm.
Neste artigo, avaliamos a eficácia da solução proposta pela Altera utilizando a nova versão 12.0 do software Quartus II e exploramos as capacidades dos FPGAs Stratix V e Arria V de 28 nm da Altera. Para realizar esta avaliação, a BDTI concentrou-se na resolução de um grande número de equações lineares simultâneas utilizando dois tipos de decomposição: uma decomposição matricial de Cholesky multicanal e a decomposição QR com o processo de Gram-Schmidt. Estas decomposições, juntamente com substituições diretas e inversas, fornecem uma solução para o vetor x num grupo simultâneo de equações lineares da forma Ax = B.
A decomposição de matrizes é utilizada em diversas aplicações de radar militar, como o Processamento Adaptativo Espaço-Temporal (STAP), e em diversos problemas de estimação em comunicações digitais. A decomposição QR é comummente utilizada em qualquer matriz A de dimensão m x n, enquanto a decomposição de Cholesky é o algoritmo mais utilizado para uma matriz quadrada, simétrica e definida positiva, devido à sua elevada eficiência computacional. Ambas as decomposições empregam algoritmos computacionalmente intensivos que requerem uma elevada precisão dos dados, necessitando de operações de ponto flutuante. Além disso, os dois exemplos discutidos neste artigo utilizam produtos escalares e laços aninhados dentro do algoritmo, operações que são predominantes numa vasta gama de aplicações de processamento digital de sinais relacionadas com a álgebra linear e filtros de resposta ao impulso finito (FIR).
Os exemplos descritos neste artigo resolvem sistemas simultâneos de equações lineares com dados complexos utilizando ambos os métodos e apresentam os resultados. Utilizando o solver QR, como explicado na Secção 4, um FPGA Altera Stratix V é capaz de realizar 315 decomposições de matrizes por segundo de tamanho 400x400, a uma velocidade de 203 MHz, atingindo 162x10⁹ operações de ponto flutuante por segundo (GFLOPS).
Os dois exemplos de projeto avaliados neste artigo fazem parte da ferramenta de software DSP Builder v12.0 ou podem ser encomendados em [
Fluxo de Projeto de Ponto Flutuante:
Os FPGAs não têm sido, geralmente, a plataforma de eleição para aplicações de ponto flutuante de alto nível. Embora os fornecedores de FPGAs ofereçam bibliotecas de primitivas de ponto flutuante, o desempenho dos FPGAs em aplicações de ponto flutuante tem sido severamente limitado. A ineficiência dos projetos tradicionais de FPGAs de ponto flutuante deve-se, em parte, à natureza altamente segmentada e às estruturas aritméticas dos operadores de ponto flutuante, que criam uma elevada latência no caminho de dados e congestionamento de encaminhamento. Por sua vez, estas latências criam problemas difíceis de gerir em projetos dependentes de dados. O resultado final é, frequentemente, um projeto com uma baixa frequência de operação.
O fluxo de ferramentas DSP Builder Advanced Blockset da Altera aborda estes obstáculos tanto ao nível da arquitetura como ao nível do design do sistema. O compilador de ponto flutuante da Altera combina grandes secções do caminho de dados numa única função de ponto flutuante, em vez de as gerar compondo operadores de ponto flutuante elementares. Isto é conseguido analisando o crescimento de bits no caminho de dados e escolhendo a normalização de entrada ideal para alocar precisão suficiente ao longo do caminho de dados, de forma a eliminar o máximo possível de passos de normalização e desnormalização, como mostrado na Figura 1. O formato IEEE 754 é utilizado apenas nos limites do caminho de dados; larguras de mantissa maiores são utilizadas no próprio caminho de dados para aumentar a gama dinâmica e diminuir a necessidade de passos de normalização e desnormalização entre operadores sucessivos. As funções de normalização e desnormalização utilizam deslocadores de barril rápidos com uma largura até 48 bits para um número de ponto flutuante de precisão simples. Isto consome uma quantidade significativa de recursos lógicos e de encaminhamento e é a principal razão pela qual as implementações de ponto flutuante baseadas em FPGA não têm sido eficientes. A metodologia combinada do caminho de dados elimina um número significativo de deslocadores de barris rápidos. As multiplicações de mantissa de maior precisão utilizam o modo multiplicador de 27 bits x 27 bits da Altera nos dispositivos Stratix V e Arria V. A Figura 1(b) compara a metodologia de caminho de dados combinado para o caso simples de uma string com dois somadores e a implementação tradicional apresentada na Figura 1(a). O caminho de dados combinado na Figura 1(b) elimina a redundância entre operadores, suprimindo a desnormalização da saída do primeiro somador e a normalização da entrada do segundo somador. A eliminação de lógica e encaminhamento adicionais, juntamente com a utilização de multiplicadores de hardware, torna o tempo e a latência previsíveis para caminhos de dados complexos. Os algoritmos de ponto flutuante IEEE 754 de precisão simples e dupla são implementados com menos características lógicas e maior desempenho. A Altera afirma que um caminho de dados combinado reduz os recursos lógicos e a latência em 50% em comparação com o caminho de dados equivalente implementado utilizando operadores elementares [2]. Além disso, como resultado da representação mais ampla dos dados internos, a precisão dos dados é geralmente superior à obtida por uma biblioteca que utiliza operadores elementares de ponto flutuante IEEE 754.
O fluxo de trabalho de design DSP de ponto flutuante da Altera incorpora o conjunto de blocos avançados DSP Builder e a ferramenta de software Quartus II, para além do MATLAB e do MathWorks Simulink. O ambiente Simulink permite ao projetista trabalhar ao nível do comportamento algorítmico para descrever, depurar e verificar sistemas complexos. As características do Simulink, como a propagação de tipos de dados e o processamento de dados vetoriais, estão integradas no conjunto de blocos avançados DSP Builder, permitindo ao projetista explorar rapidamente o espaço de projeto algorítmico.
Para avaliar a eficiência e o desempenho do fluxo de projeto de ponto flutuante da Altera, a BDTI utilizou a ferramenta DSP Builder Advanced Blockset para validar dois exemplos. Ambos envolviam a resolução de um conjunto de equações lineares simultâneas utilizando tipos de dados complexos numa representação de ponto flutuante de precisão simples. Uma solução foi obtida utilizando a decomposição de Cholesky, enquanto a outra empregou a decomposição QR via processo de Gram-Schmidt. A Secção 2 deste artigo descreve a implementação dos dois exemplos de ponto flutuante. A Secção 3 explica a experiência da BDTI com o fluxo de projeto e o conjunto de ferramentas. A Secção 4 apresenta o desempenho da implementação utilizando dois FPGAs da Altera: o Stratix V 5SGSMD5K2F40C2n, de alto desempenho e tamanho médio, e o Arria V 5AGTFD7K3F40I3N, também de gama média. Por fim, a Secção 5 apresenta as conclusões da BDTI.
2.
Informação Geral sobre
Inúmeras aplicações envolvem conjuntos de equações lineares da forma Ax = b. Quer se trate de um problema de optimização envolvendo mínimos quadrados lineares, um filtro de Kalman para prever um problema ou estimação num canal de comunicação MIMO, o problema consiste ainda em encontrar uma solução numérica para um conjunto de equações lineares da forma Ax = b. Para uma matriz geral de tamanho m por n, em que m é a altura da matriz e n a sua largura, pode ser utilizada a decomposição QR para encontrar o vector x. O algoritmo decompõe A numa matriz ortonormal Q de tamanho m por n e numa matriz triangular superior R de tamanho n por n. Como Q é ortonormal, QTQ = I e Rx = QTb. Como R é uma matriz triangular superior, x pode ser facilmente encontrado por retrosubstituição sem a necessidade de inverter a matriz original A. No exemplo de decomposição QR deste artigo, trabalhamos com matrizes sobredeterminadas onde m ≠ n.
Quando a matriz A é simétrica e definida positiva, como nas matrizes de covariância que surgem em muitos problemas, a decomposição e o solucionador de Cholesky são comummente utilizados. O algoritmo encontra a inversa da matriz A, resolvendo assim o vetor x como x = A⁻¹b. A decomposição de Cholesky é, pelo menos, duas vezes mais eficiente que a decomposição QR, dependendo dos algoritmos de decomposição utilizados. Como estes algoritmos de decomposição são recorrentes por natureza e incluem a divisão, é necessária uma grande gama dinâmica numérica à medida que o tamanho da matriz aumenta. Na maioria dos casos, mesmo para matrizes tão pequenas como 4x4, por exemplo, na estimação de canais MIMO, são realizadas operações de ponto flutuante. Para sistemas maiores que exigem maior desempenho, como em aplicações militares, a velocidade de ponto flutuante é frequentemente proibitiva para sistemas embebidos. Os projetistas abandonam frequentemente o algoritmo por completo em busca de uma solução menos otimizada ou recorrem a processadores de ponto flutuante de alto desempenho, com o consequente aumento do custo e do esforço de projeto.
Autor:
Pela equipa da Berkeley Design Technology, Inc. Outubro de 2012
(Continua em fevereiro)
