No description available.

No description available.

Les fonctions élémentaires sont utilisées dans de nombreux codes de calcul haute performance. Bien que les bibliothèques mathématiques (libm) auxquelles font appel ces codes proposent en général plusieurs variétés d'une même fonction, celles-ci sont figées lors de leur implémentation. Cette caractéristique représente un frein à la performance des programmes qui les utilisent car elles sont conçues pour être polyvalentes au détriment d'optimisations spécifiques. De plus, la duplication de modèles partagés rend la maintenance de ces libms plus difficile et sujette à l'introduction de bugs. Un défi actuel est de proposer des "méta-outils" visant la génération automatique de code performant pour l'évaluation des fonctions élémentaires. Ces outils doivent permettre la réutilisation d'algorithmes efficaces et génériques pour différentes variétés de fonctions ou architectures matérielles. Il devient alors possible de générer des libms optimisées pour des besoins très spécifiques avec du code générateur factorisé, qui facilite sa maintenance. Dans un premier temps, nous proposons un algorithme original permettant de générer des tables sans erreur pour les fonctions trigonométriques et hyperboliques. Puis nous étudions les performances de schémas d'évaluation polynomiale vectorisés, premier pas vers la génération de fonctions vectorisées efficaces. Enfin, nous proposons une méta-implémentation d'un logarithme vectorisé, factorisant la génération de code pour différents formats et architectures. Ces contributions sont compétitives comparées à d'autres solutions, justifiant le développement de tels méta-codes. / Elementary mathematical functions are pervasive in many high performance computing programs. However, although the mathematical libraries (libms), on which these programs rely, generally provide several flavors of the same function, these are fixed at implementation time. Hence this monolithic characteristic of libms is an obstacle for the performance of programs relying on them, because they are designed to be versatile at the expense of specific optimizations. Moreover, the duplication of shared patterns in the source code makes maintaining such code bases more error prone and difficult. A current challenge is to propose "meta-tools" targeting automated high performance code generation for the evaluation of elementary functions. These tools must allow reuse of generic and efficient algorithms for different flavours of functions or hardware architectures. Then, it becomes possible to generate optimized tailored libms with factorized generative code, which eases its maintenance. First, we propose an novel algorithm that allows to generate lookup tables that remove rounding errors for trigonometric and hyperbolic functions. The, we study the performance of vectorized polynomial evaluation schemes, a first step towards the generation of efficient vectorized elementary functions. Finally, we develop a meta-implementation of a vectorized logarithm, which factors code generation for different formats and architectures. Our contributions are shown competitive compared to free or commercial solutions, which is a strong incentive to push for developing this new paradigm.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-19T13:38:10Z No. of bitstreams: 1 aroldodepaulamoreira.pdf: 3238077 bytes, checksum: 478168ebbb19952c81b212f653064033 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T13:48:06Z (GMT) No. of bitstreams: 1 aroldodepaulamoreira.pdf: 3238077 bytes, checksum: 478168ebbb19952c81b212f653064033 (MD5) / Made available in DSpace on 2016-02-26T13:48:06Z (GMT). No. of bitstreams: 1 aroldodepaulamoreira.pdf: 3238077 bytes, checksum: 478168ebbb19952c81b212f653064033 (MD5) Previous issue date: 2014-03-18 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho tem o objetivo de propor atividades, com o uso do GeoGebra, para o estudo de funções elementares, direcionado para alunos da 1a série do ensino médio. O autor sugere várias atividades construídas no GeoGebra para auxiliar a visualização e compreensão de gráficos, relacionando-as com a parte teórica. Essas atividades, apresentadas na forma de exemplos, foram feitas baseadas na minha experiência do autor em trabalhar com as séries iniciais do ensino médio em escolas públicas do Estado do Rio de Janeiro. O roteiro de construção das atividades proposto para o GeoGebra, é um caminho alternativo para exploração de alguns tópicos considerados relevantes no estudo das funções elementares. Todos os gráficos apresentados neste trabalho foram construídos no GeoGebra. Foi sugerido no final de cada tópico, uma atividade proposta com a respectiva solução. / This work aims to suggest activities, with the usage of GeoGebra, for the study of elementary functions, focused on students in the first year of High School. The author suggests lots of activities built on GeoGebra to give support on graphics’ view and comprehension, matching them with the corresponding theory. These activities, presented as examples, were based on the author’s experience in working in the first years of High School in public schools in Rio de Janeiro State. The building activities script suggested for GeoGebra, is an alternative way to explore some topics considered relevant when studying elementary functions. All the graphics used in this work were built in the GeoGebra. It was suggested at the end of each topic, an activity with the corresponding answer key.

This thesis is about implementing the functions for reciprocal, square root, inverse square root and logarithms on a DSP platform. A multi-core DSP platform that consists of one master processor core and several SIMD coprocessor cores is currently being designed by a team at the Computer Engineering Department of Linköping University. The SIMD coprocessors’ arithmetic logic unit (ALU) has 16 multipliers to support vector multiplication instructions. By efficiently using the 16 multipliers, it is possible to evaluate polynomials very fast. The ALU does not have (hardware) support for floating point arithmetic, so the challenge is to get good precision by using fixed point arithmetic. Precise and fast solutions to implement the mathematical functions are found by converting the fixed point input to a soft floating point format before polynomial approximation, choosing a polynomial based on an error analysis of the polynomial approximation, and using Newton-Raphson or Goldschmidt iterations to improve the precision of the polynomial approximations. Finally, suggestions are made of changes and additions to the instruction set architecture, in order to make the implementations faster, by efficiently using the currently existing hardware.

<p> Magnetic Resonance Imaging (MRI) velocity quantification is addressed in part I of this thesis. In simple MR imaging, data is collected and tissue densities are displayed as images. Moving tissue creates signals which appear as artifacts in the images. In velocity imaging, more data is collected and phase differences are used to quantify the velocity of tissue components. The problem is described and a novel formulation of a regularized, nonlinear inverse problem is proposed. Both Tikhonov and Total Variation Regularization are discussed. Results of numerical simulations show that significant noise reduction is possible.</p> <p> The method is firstly verified with MATLAB. A number of experiments are carried out with different regularization parameters, different magnetic fields and different noise levels. The experiments show that the stronger the complex noise is, the stronger the magnetic field requires for estimating the velocity. The regularization parameter also plays an important role in the experiments. Given the noise level and with an appropriate value of regularization parameter, the estimated velocity converges to ideal velocity very quickly. A proof-of-concept implementation on the Cell BE processor is described, quantifying the performance potential of this platform.</p> <p> The second part of this thesis concerns the evaluation of an elementary function library. Since CBE SPU is designed for compute intensive applications, the well developed Math functions can help developer program and save time to take care other details. Dr. Anand's research group in McMaster developed 28 math functions for CBE SPU. The test tools for accuracy and performance were developed on CBE. The functions were tuned while testing. The functions are either competitive or an addition to the existing SDK1.1 SPU math functions.</p> / Thesis / Master of Applied Science (MASc)

Cette thèse fait une étude sur deux moyens d'enrichir l'environnement flottant courant : le premier est d'obtenir plusieurs versions d'implantation pour chaque fonction mathématique, le deuxième est de fournir des opérations de la norme IEEE754, qui permettent de mélanger les entrées et la sortie dans les bases différentes. Comme la quantité de versions différentes pour chaque fonction mathématique est énorme, ce travail se concentre sur la génération du code. Notre générateur de code adresse une large variété de fonctions: il produit les implantations paramétrées pour les fonctions définies par l'utilisateur. Il peut être vu comme un générateur de fonctions boîtes-noires. Ce travail inclut un nouvel algorithme pour le découpage de domaine et une tentative de remplacer les branchements pendant la reconstruction par un polynôme. Le nouveau découpage de domaines produit moins de sous-domaines et les degrés polynomiaux sur les sous-domaines adjacents ne varient pas beaucoup. Pour fournir les implantations vectorisables il faut éviter les branchements if-else pendant la reconstruction. Depuis la révision de la norme IEEE754 en 2008, il est devenu possible de mélanger des nombres de différentes précisions dans une opération. Par contre, il n'y a aucun mécanisme qui permettrait de mélanger les nombres dans des bases différentes dans une opération. La recherche dans l'arithmétique en base mixte a commencé par les pires cas pour le FMA. Un nouvel algorithme pour convertir une suite de caractères décimaux du longueur arbitraire en nombre flottant binaire est présenté. Il est indépendant du mode d'arrondi actuel et produit un résultat correctement arrondi. / This work investigates two ways of enlarging the current floating-point environment. The first is to support several implementation versions of each mathematical function (elementary such as $\exp$ or $\log$ and special such as $\erf$ or $\Gamma$), the second one is to provide IEEE754 operations that mix the inputs and the output of different \radixes. As the number of various implementations for each mathematical function is large, this work is focused on code generation. Our code generator supports the huge variety of functions: it generates parametrized implementations for the user-specified functions. So it may be considered as a black-box function generator. This work contains a novel algorithm for domain splitting and an approach to replace branching on reconstruction by a polynomial. This new domain splitting algorithm produces less subdomains and the polynomial degrees on adjacent subdomains do not change much. To produce vectorizable implementations, if-else statements on the reconstruction step have to be avoided. Since the revision of the IEEE754 Standard in 2008 it is possible to mix numbers of different precisions in one operation. However, there is no mechanism that allows users to mix numbers of different radices in one operation. This research starts an examination ofmixed-radix arithmetic with the worst cases search for FMA. A novel algorithm to convert a decimal character sequence of arbitrary length to a binary floating-point number is presented. It is independent of currently-set rounding mode and produces correctly-rounded results.

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d'autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing affirmant que tous les modèles raisonnables calculent les mêmes fonctions. Nous montrons des équivalences entre les fonctions récursivement calculables et une certaine classe de fonctions R-récursives et entre les fonctions GPAC-calculables et les fonctions récursivement calculables. Nous montrons également une hiérarchie de classes de fonctions R-récursives qui caractérisent les fonctions élémentairement calculables, les fonctions de la hiérarchie de Grzegorczyk et les fonctions récursivement calculables à l'aide d'un opérateur de limite. Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels / Computation on the real numbers can be modelised in several different ways. There indeed exist a lot of different computation models on the reals. However, there are few results for comparing those models, and most of these results are incomparability results. The case of computation over the reals hence is quite different from the classical case where Church thesis claims that all reasonable models compute exactly the same functions. We show that recursively computable functions (in the sense of computable analysis) can be shown equivalent to some adequately defined class of R-recursive functions, and also to GPAC-computable functions. More than an analog characterization of recursively enumerable functions, we show that the limit operator we defined can be used to provide an analog characterization of elementarily computable functions and functions from Grzegorczyk's hierarchy. Those results can be seen as a first step toward a unification of computable functions over the reals

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-01-27T14:50:48Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Murany de Fátima Botelho Souza - 2014.pdf: 2572668 bytes, checksum: b6e41a3825ec511979b76508b3d5706d (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-01-28T12:59:24Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Murany de Fátima Botelho Souza - 2014.pdf: 2572668 bytes, checksum: b6e41a3825ec511979b76508b3d5706d (MD5) / Made available in DSpace on 2015-01-28T12:59:24Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Murany de Fátima Botelho Souza - 2014.pdf: 2572668 bytes, checksum: b6e41a3825ec511979b76508b3d5706d (MD5) Previous issue date: 2014-03-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The principal objective of this work, is to present the main Free Softwares of Mathemathics, emphasizing their mathemathical functions and corresponding platforms. We present some proposed pedagogical activities for basic and upper education, using GeoGebra and wxMaxima, respectively. It was verified, that activities facilitated by software, should always be based on mathemathical arguments. Furthermore, the teacher should master and know all tools and limitations of the mathemathical software, before employing any classroom activity. Finally, we perceived the limitations of Free Mathemathical Softwares when it comes to the construction of graphics for implicitly given functions. / O trabalho tem por objetivo principal apresentar os principais Softwares Livres Matemáticos, destacando suas funções matemáticas e suas respectivas plataformas. Foram apresentadas propostas atividades pedagógicas para o Ensino Básico e para o Ensio Superior, utilizando o GeoGebra e o wxMaxima respectivamente. Verificou-se que atividades mediadas por software devem ser fundamentada com argumentos matemáticos. Além disso, o professor deve dominar e conhecer todas as ferramentas e limitações do software matemático, antes de desenvolver qualquer atividade em sala de aula. Finalmete pudemos perceber as limitações dos Softwares Livres Matemáticos para a construção de gráficos de funções implícitas.

Au cours des dernières décennies les systèmes embarqués ont dû faire face à des demandes applicatives de plus en plus variées et de plus en plus contraintes. Ce constat s'est traduit pour l’arithmétique par le besoin de toujours plus de performances et d'efficacité énergétique. Ce travail se propose d'étudier des solutions allant du matériel au logiciel, ainsi que les diverses interactions qui existent entre ces domaines, pour améliorer le support arithmétique dans les systèmes embarqués. Certains résultats ont été intégrés au processeur MPPA développé par Kalray. La première partie est consacrée au support de l'arithmétique virgule flottante dans le MPPA. Elle commence par la mise au point d'une unité flottante matérielle basée sur l'opérateur classique FMA (fused multiply-Add). Les améliorations proposées, implémentées et évaluées incluent un FMA à précision mixte, l'addition à 3 opérandes et le produit scalaire 2D, à chaque fois avec un seul arrondi et le support des sous-Normaux. Cette partie se poursuit par l'étude de l'implémentation des autres primitives flottantes normalisées : division et racine carrée. L'unité flottante matérielle précédente est réutilisée et modifiée pour optimiser ces primitives à moindre coût. Cette première partie s’ouvre sur le développement d'un générateur de code destiné à l'implémentation de bibliothèques mathématiques optimisées pour différents contextes (architecture, précision, latence, débit). La seconde partie consiste en la présentation d'une nouvelle architecture de coprocesseur reconfigurable. Cet opérateur matériel peut être dynamiquement modifié pour s'adapter à la volée à des besoins applicatifs variés. Il vise à fournir des performances se rapprochant d'une implémentation matérielle dédiée sans renier la flexibilité inhérente au logiciel. Il a été spécifiquement pensé pour être intégré avec un cœur embarqué faible consommation du MPPA. Cette partie s'attache aussi à décrire le développement d'un environnement logiciel pour cibler ce coprocesseur ainsi qu'explorer divers choix architecturaux envisagés. La dernière partie étudie un problème plus large : l'utilisation efficace de ressources arithmétiques parallèles. Elle présente une amélioration des architectures régulières Single Instruction Multiple Data tels qu’on les trouve dans les accélérateurs graphiques (GPU) pour l'exécution de graphes de flot de contrôle divergents. / In the last decades embedded systems have been challenged with more and more application variety, each time more constrained. This implies an ever growing need for performances and energy efficiency in arithmetic units. This work studies solutions ranging from hardware to software to improve arithmetic support in embedded systems. Some of these solutions were integrated in Kalray's MPPA processor. The first part of this work focuses on floating-Point arithmetic support in the MPPA. It starts with the design of a floating-Point unit (FPU) based on the classical FMA (Fused Multiply-Add) operator. The improvements we suggest, implement and evaluate include a mixed precision FMA, a 3-Operand add and a 2D scalar product, each time with a single rounding and support for subnormal numbers. It then considers the implementation of division and square root. The FPU is reused and modified to optimize the software implementations of those primitives at a lower cost. Finally, this first part opens up on the development of a code generator designed for the implementation of highly optimized mathematical libraries in different contexts (architecture, accuracy, latency, throughput). The second part studies a reconfigurable coprocessor, a hardware operator that could be dynamically modified to adapt on the fly to various applicative needs. It intends to provide performance close to ASIC implementation, with some of the flexibility of software. One of the addressed challenges is the integration of such a reconfigurable coprocessor into the low power embedded cluster of the MPPA. Another is the development of a software framework targeting the coprocessor and allowing design space exploration. The last part of this work leaves micro-Architecture considerations to study the efficient use of parallel arithmetic resources. It presents an improvement of regular architectures (Single Instruction Multiple Data), like those found in graphic processing units (GPU), for the execution of divergent control flow graphs.