L'efficacité et les performances des FPGA à virgule flottante sont limitées par des latences élevées et la congestion du routage. De plus, la méthode de conception traditionnelle des FPGA, basée sur la description du matériel au niveau des registres en Verilog ou VHDL, est mal adaptée à l'implémentation d'algorithmes complexes à virgule flottante.
Altera a développé un nouveau flux de conception pour le calcul en virgule flottante, visant à simplifier l'implémentation des algorithmes de traitement numérique du signal en virgule flottante sur les FPGA Altera. Ce flux permet à ces conceptions d'atteindre des niveaux de performance et d'efficacité inégalés. Au lieu de construire un chemin de données composé d'opérateurs élémentaires en virgule flottante (par exemple, multiplication, addition et mise au carré), le compilateur génère un chemin de données combinant ces opérateurs en une seule fonction. Ceci élimine les redondances présentes dans les conceptions FPGA traditionnelles. De plus, le flux de conception d'Altera est un flux de haut niveau, basé sur un modèle, qui utilise le bloc de conception avancé DSP Builder d'Altera avec MATLAB et MathWorks Simulink. Altera prévoit que cette approche de haut niveau permettra aux concepteurs de FPGA d'implémenter et de vérifier plus rapidement des algorithmes complexes en virgule flottante qu'avec les méthodes de conception traditionnelles basées sur le langage HDL.
BDTI a mené une analyse indépendante du flux de conception DSP à virgule flottante d'Altera. L'objectif de BDTI était de comprendre les performances atteignables avec les FPGA Altera pour les applications DSP à virgule flottante de haut niveau et d'évaluer la facilité d'utilisation du flux de conception DSP à virgule flottante d'Altera. Cet article présente les conclusions de BDTI, ainsi que des informations contextuelles et le détail de la méthodologie employée.
1. Introduction
Deux exemples de conception en virgule flottante
Les progrès réalisés dans le domaine des puces numériques permettent désormais d'intégrer des algorithmes complexes, auparavant réservés à la recherche, dans les applications informatiques embarquées courantes. Par exemple, l'algèbre linéaire (et plus particulièrement la résolution de systèmes impliquant simultanément de grands ensembles d'équations linéaires) est utilisée depuis de nombreuses années principalement en recherche, où des ressources de calcul importantes sont disponibles et où les calculs en temps réel ne sont généralement pas nécessaires. La résolution de grands systèmes requiert l'inversion de matrices ou une forme de décomposition matricielle. Outre les exigences en matière de capacité de calcul, ces techniques peuvent souffrir d'instabilité numérique si la plage dynamique utilisée est insuffisante. Par conséquent, l'implémentation efficace et précise de ces algorithmes n'est envisageable que sur des dispositifs à virgule flottante.
Altera a récemment intégré des capacités de calcul en virgule flottante à son kit d'outils DSP Builder Advanced Blockset afin de simplifier l'implémentation d'algorithmes DSP en virgule flottante sur les FPGA Altera et d'améliorer les performances et l'efficacité des conceptions en virgule flottante par rapport aux techniques de conception FPGA traditionnelles. Dans un article précédent [1], BDTI a analysé et évalué les performances et l'efficacité du kit d'outils logiciels Quartus II v11.0 d'Altera sur un exemple d'implémentation du solveur Cholesky à virgule flottante monocanal, synthétisé pour les FPGA Stratix IV et Arria IV de 40 nm.
Dans cet article, nous évaluons l'efficacité de la solution proposée par Altera à l'aide de la nouvelle version 12.0 du logiciel Quartus II et explorons les capacités des FPGA 28 nm Stratix V et Arria V d'Altera. Pour réaliser cette évaluation, BDTI s'est concentré sur la résolution d'un grand nombre d'équations linéaires simultanées en utilisant deux types de décompositions : une décomposition matricielle de Cholesky multicanaux et une décomposition QR avec le procédé de Gram-Schmidt. Ces décompositions, associées à des substitutions directes et inverses, fournissent une solution pour le vecteur x dans un système d'équations linéaires de la forme Ax = B.
La décomposition matricielle est utilisée dans de nombreuses applications radar militaires, telles que le traitement adaptatif spatio-temporel (STAP), et pour divers problèmes d'estimation en communications numériques. La décomposition QR est couramment employée sur toute matrice A de dimensions m x n, tandis que la décomposition de Cholesky est l'algorithme le plus répandu pour les matrices carrées, symétriques et définies positives, en raison de sa grande efficacité de calcul. Ces deux décompositions font appel à des algorithmes gourmands en ressources de calcul qui exigent une haute précision des données, nécessitant ainsi des opérations en virgule flottante. De plus, les deux exemples présentés dans cet article utilisent des produits scalaires et des boucles imbriquées, opérations fréquentes dans de nombreuses applications de traitement numérique du signal liées à l'algèbre linéaire et aux filtres à réponse impulsionnelle finie (FIR).
Les exemples décrits dans cet article résolvent des systèmes d'équations linéaires simultanées à données complexes à l'aide des deux méthodes et présentent les résultats. Avec le solveur QR, comme expliqué dans la section 4, un FPGA Altera Stratix V est capable d'effectuer 315 décompositions matricielles par seconde de taille 400 × 400, à une fréquence de 203 MHz, atteignant ainsi 162 × 10⁹ opérations en virgule flottante par seconde (GFLOPS).
Les deux exemples de conception évalués dans cet article font partie du logiciel DSP Builder v12.0 ou peuvent être commandés auprès de [
Conception en virgule flottante :
Les FPGA n'ont généralement pas été la plateforme de prédilection pour les applications en virgule flottante de haut niveau. Bien que les fournisseurs de FPGA proposent des bibliothèques de primitives en virgule flottante, les performances des FPGA dans ce type d'applications restent fortement limitées. L'inefficacité des conceptions FPGA traditionnelles en virgule flottante est en partie due à la nature hautement segmentée et aux structures arithmétiques des opérateurs en virgule flottante, qui engendrent une latence élevée sur le chemin des données et une congestion du routage. Ces latences créent à leur tour des problèmes difficiles à gérer dans les conceptions dépendantes des données. Il en résulte souvent une conception à faible fréquence de fonctionnement.
L'outil DSP Builder Advanced Blockset d'Altera s'attaque à ces obstacles tant au niveau de l'architecture que de la conception système. Le compilateur en virgule flottante d'Altera combine de larges sections du chemin de données en une seule fonction en virgule flottante, au lieu de les générer par composition d'opérateurs élémentaires. Ceci est réalisé en analysant la croissance du nombre de bits sur le chemin de données et en choisissant la normalisation d'entrée optimale afin d'allouer une précision suffisante le long de ce chemin et ainsi éliminer autant que possible les étapes de normalisation et de dénormalisation, comme illustré sur la figure 1. Le format IEEE 754 est utilisé uniquement aux limites du chemin de données ; des largeurs de mantisse plus importantes sont utilisées sur le chemin lui-même afin d'accroître la plage dynamique et de réduire le besoin d'étapes de normalisation et de dénormalisation entre les opérateurs successifs. Les fonctions de normalisation et de dénormalisation utilisent des décalageurs à barillet rapides d'une largeur allant jusqu'à 48 bits pour un nombre à virgule flottante simple précision. Ceci consomme une quantité importante de ressources logiques et de routage, et constitue la principale raison du manque d'efficacité des implémentations à virgule flottante sur FPGA. La méthodologie de chemin de données combiné élimine un nombre significatif de décalageurs à barillet rapides. Les multiplications de mantisse de plus haute précision utilisent le mode multiplicateur 27 bits × 27 bits d'Altera sur les dispositifs Stratix V et Arria V. La figure 1(b) compare la méthodologie de chemin de données combiné pour le cas simple d'une chaîne de caractères avec deux additionneurs et l'implémentation traditionnelle illustrée figure 1(a). Le chemin de données combiné de la figure 1(b) élimine la redondance inter-opérateurs en supprimant la dénormalisation de la sortie du premier additionneur et la normalisation de l'entrée du second. L'élimination de la logique et du routage supplémentaires, ainsi que l'utilisation de multiplicateurs matériels, rendent le temps d'exécution et la latence prévisibles pour les chemins de données complexes. Les algorithmes à virgule flottante IEEE 754 en simple et double précision sont implémentés avec moins de ressources logiques et des performances accrues. Altera affirme qu'un chemin de données combiné réduit les ressources logiques et la latence de 50 % par rapport au chemin de données équivalent implémenté à l'aide d'opérateurs élémentaires [2]. De plus, grâce à une représentation plus large des données internes, la précision des données est généralement supérieure à celle obtenue avec une bibliothèque utilisant des opérateurs à virgule flottante IEEE 754 élémentaires.
Le flux de travail de conception DSP à virgule flottante d'Altera intègre le jeu de blocs avancé DSP Builder et l'outil logiciel Quartus II d'Altera, ainsi que MATLAB et MathWorks Simulink. L'environnement Simulink permet au concepteur de travailler au niveau du comportement algorithmique pour décrire, déboguer et vérifier des systèmes complexes. Des fonctionnalités de Simulink telles que la propagation des types de données et le traitement des données vectorielles sont intégrées au jeu de blocs avancé DSP Builder, permettant ainsi au concepteur d'explorer rapidement l'espace de conception algorithmique.
Pour évaluer l'efficacité et les performances du flux de conception à virgule flottante d'Altera, BDTI a utilisé l'outil DSP Builder Advanced Blockset afin de valider deux exemples. Ces exemples consistaient à résoudre un système d'équations linéaires simultanées à l'aide de types de données complexes, représentés en virgule flottante simple précision. Une solution a été obtenue par décomposition de Cholesky, tandis que l'autre a utilisé la décomposition QR via le procédé de Gram-Schmidt. La section 2 de cet article décrit la mise en œuvre de ces deux exemples. La section 3 présente l'expérience de BDTI avec le flux de conception et l'outil. La section 4 présente les performances de l'implémentation sur deux FPGA Altera : le Stratix V 5SGSMD5K2F40C2n, un FPGA haut de gamme de taille moyenne, et l'Arria V 5AGTFD7K3F40I3N, un FPGA de milieu de gamme. Enfin, la section 5 présente les conclusions de BDTI.
2.
Informations générales sur
. De nombreuses applications font intervenir des systèmes d'équations linéaires de la forme Ax = b. Qu'il s'agisse d'un problème d'optimisation par moindres carrés linéaires, d'un filtre de Kalman pour la prédiction d'un problème ou d'une estimation dans un canal de communication MIMO, le problème consiste toujours à trouver une solution numérique à un système d'équations linéaires de la forme Ax = b. Pour une matrice quelconque de taille m × n, où m est la hauteur de la matrice et n sa largeur, la décomposition QR peut être utilisée pour calculer le vecteur x. L'algorithme décompose A en une matrice orthonormée Q de taille m × n et une matrice triangulaire supérieure R de taille n × n. Puisque Q est orthonormée, QTQ = I et Rx = QTb. Puisque R est une matrice triangulaire supérieure, x peut être facilement calculé par substitution arrière sans même avoir besoin d'inverser la matrice originale A. Dans l'exemple de décomposition QR présenté dans cet article, nous travaillons avec des matrices surdéterminées où m ≠ n.
Lorsque la matrice A est symétrique et définie positive, comme c'est le cas pour les matrices de covariance rencontrées dans de nombreux problèmes, la décomposition de Cholesky et son solveur sont couramment utilisés. L'algorithme calcule l'inverse de la matrice A, ce qui permet de résoudre le vecteur x sous la forme x = A⁻¹b. La décomposition de Cholesky est au moins deux fois plus efficace que la décomposition QR, selon les algorithmes de décomposition utilisés. Ces algorithmes étant récursifs et impliquant des divisions, une large plage dynamique numérique est nécessaire lorsque la taille de la matrice augmente. Dans la plupart des cas, même pour des matrices aussi petites que 4x4, par exemple pour l'estimation de canal MIMO, des opérations en virgule flottante sont effectuées. Pour les systèmes plus importants exigeant des performances plus élevées, comme dans les applications militaires, la vitesse de calcul en virgule flottante est souvent prohibitive pour les systèmes embarqués. Les concepteurs abandonnent fréquemment l'algorithme au profit d'une solution moins optimale ou optent pour des processeurs en virgule flottante hautes performances, ce qui entraîne une augmentation des coûts et de la complexité de conception.
Auteur:
Par l'équipe de Berkeley Design Technology, Inc. Octobre 2012
(À suivre en février)
