Contribution to the automated generation of programs in computer arithmetic
Résumé
This HDR thesis presents our contributions on the automated generation of programs in computer arithmetic. These results have been obtained from 2010 to 2023 within the DALI team from UPVD and LIRMM. After a brief state of the art on computer arithmetic, we are interested, in a first part, in the implementation of elementary functions in floating-point arithmetic. These implementations are generally based on the use of lookup tables and polynomial approximants. We illustrate how to build tables of exact values in the case of trigonometric functions, and we propose a uniform approach based on polynomial evaluation for the correctly rounded implementation of logb(x) functions. In a second part, we are interested in the implementation of basic blocks of linear algebra in fixed-point arithmetic. We propose a rigorous arithmetic model for the four basic operations, as well as for the division and the square root, that are two operations ill-defined in fixed-point arithmetic. We then use this model for the generation of codes for matrix multiplication and inversion. A lot of our works rely on polynomial evaluation. In a third part, we are interested in the performance and the accuracy of this basic block. These directly depend on the evaluation scheme used. For fixed-point arithmetic, we present a method based on instruction selection for the implementation of schemes optimized for a specific architecture described in an XML file. For floating-point arithmetic, we propose a method to choose the format of each data of a scheme in order to guarantee a certain output accuracy. Finally, we study the performance of these schemes on AVX2 architectures. In a fourth part, we are interested in tools that allow to automatically adapt the format of certain data of a floating-point program, in order to improve its performance while not sacrifying the accuracy of its results. We propose a first method to reduce the format of floating-point instructions that can benefit from SIMD instructions. We then propose an infrastructure allowing to analyze the impact on the accuracy of the results of the modification of data formats in iterative routines. In a last part, we develop two research directions, on the development of new floating-point operators, and that of new adaptation tools that will be more robust to input data and that will make it possible to process larger programs.
Cette thèse d’HDR présente nos contributions sur la génération automatique de programmes en arithmétique des ordinateurs. Ces résultats ont été obtenus entre 2010 et 2023 au sein de l’équipe DALI de l’UPVD et du LIRMM. Après un bref état de l’art sur l’arithmétique des ordinateurs, nous nous intéressons, dans une première partie, à l’implantation de fonctions élémentaires en arithmétique flottante. De manière générale, ces implantations reposent sur l’utilisation de tables de valeurs et de polynômes d’approximation. Nous illustrons comment construire des tables de valeurs exactes dans le cas des fonctions trigonométriques, et nous proposons une approche uniforme à base d’évaluation polynomiale pour l’implantation correctement arrondie des fonctions logb(x). Dans une deuxième partie, nous nous intéressons à l’implantation de briques de base d’algèbre linéaire en aritmétique à virgule fixe. Nous proposons un modèle arithmétique rigoureux pour les quatre opérations de base, ainsi que pour la division et la racine carrée, qui sont deux opérations très mal définies en arithmétique à virgule fixe. Nous utilisons ensuite ce modèle pour la génération de codes pour la multiplication et l’inversion de matrices. Beaucoup de nos travaux reposent sur l’évaluation polynomiale. Dans une troisième partie, nous nous intéressons à la performance et à la précision de cette brique de base. Elles dépendent directement du schéma d’évaluation utilisé. Pour la virgule fixe, nous présentons une méthode à base de sélection d’instructions pour l’implantation de schémas optimisée pour une architecture spécifique décrite dans un fichier XML. Pour la virgule flottante, nous proposons une méthode pour choisir le format de chaque donnée d’un schéma afin de garantir une certaine précision de sortie. Nous étudions enfin la performance de ces schémas sur les architectures AVX2. Dans une quatrième partie, nous nous intéressons aux outils permettant d’adapter automatiquement le format de certaines données d’un programme flottant, afin d’améliorer sa performance sans sacrifier la précision de ses résultats. Nous proposons une première méthode permettant de réduire le format des instructions flottantes pouvant bénéficier des instructions SIMD. Nous proposons ensuite une infrastructure permettant d’analyser l’impact sur la précision des résultats de la modification du format des données dans les routines itératives. Dans une dernière partie, nous développons deux directions de recherche, sur le développement de nouveaux opérateurs flottants, et celui de nouveaux outils d’adaptation plus robustes aux données d’entrées et qui permettront de traiter des programmes plus conséquents.