2012

Exécuter un programme en parallèle

Par Goossens Bernard (DALI, UPVD/LIRMM, Perpignan) le 2012-11-08

• Il y a plusieurs façons d'écrire des programmes parallèles: aujourd'hui, on peut utiliser la bibliothèque "pthread" pour une exécution sur multicoeur, implémenter en CUDA à destination d'un GPU ou se servir de MPI sur une grille. Dans tous les cas, le point de départ est un algorithme parallèle, suivi d'une implémentation faisant un emploi explicite des structures de calcul parallèle, de synchronisation et de communication sous-jacentes.

• Nous proposons une nouvelle façon de paralléliser un programme, qui s'appuie sur une expression de l'algorithme dans un langage classique (C par exemple) et sa traduction en langage machine à partir d'un compilateur standard (gcc par exemple). Nous montrons que les codes machines soi-disant séquentiels issus du couple C/gcc peuvent être évalués de façon parallèle, à condition de modifier les unités d'extraction et de gestion de la mémoire du processeur. Nous montrons que le parallélisme d'instructions disponible bien que grand, est inexploité, principalement à cause de la façon séquentielle dont les instructions sont extraites et la pile est gérée. Nous présentons un exemple de processeur conçu pour exécuter nos programmes usuels en parallèle sur plusieurs coeurs.

Accurate and rigorous trigonometrical function algorithm

Par Yamanaka Naoya (Tokyo Woman's Christian University, Japan) le 2012-10-22

• In a numerical calculation sometimes we need higher than double-precision floating point arithmetic to allow us to be confident a result. One approach is to store numbers in a multiple-component format, where a number is expressed as unevaluated sums of ordinary floating-point words. In this talk, we present an algorithm to verify the trigonometrical function for ''doubled'' double-precision. Proposed method is working on double precision arithmetic in rounding-to-nearest mode. Numerical examples are presented for illustrating effectiveness of the proposed algorithm.

Error-Free Transformation for Matrix Multiplication

Par Ozaki Katsuhisa (Tokyo Woman's Christian University, Japan) le 2012-10-22

• This talk is concerned with accurate numerical algorithms for matrix multiplication. Recently, an error-free transformation from a product of two floating-point matrices into an unevaluated sum of floating-point matrices has been developed by the authors: K. Ozaki, T. Ogita, S. Oishi, S. M. Rump: Error-Free Transformation of Matrix Multiplication by Using Fast Routines of Matrix Multiplication and its Applications, Numerical Algorithms, Vol　59:1 (2012), pp. 95-118. Combining this technique and accurate summation algorithms, new algorithms for accurate matrix multiplication could be investigated. In this talk, it is mentioned that the previous work is not the unique way to achieve an error-free transformation and the constraint of the error-free transformation is clarified. For the application, a new algorithm is developed reducing the number of matrix products compared to the previous algorithm.

Génération de nombres pseudo-aléatoires basée sur des systèmes multi-physiques exotiques et chiffrement d'images

Par François Michael (DALI - UPVD/LIRMM) le 2012-10-12

• L'utilisation des nombres (pseudo)-aléatoires a pris une dimension importante ces dernières décennies. De nombreuses applications dans le domaine des télécommunications, de la cryptographie, des simulations numériques ou encore des jeux de hasard, ont contribué au développement et à l'usage de ces nombres. Les méthodes utilisées pour la génération des nombres (pseudo)-aléatoires proviennent de deux types de processus : physique et algorithmique. Dans cette thèse, deux classes de générateurs basés sur des principes de mesures physiques et des processus mathématiques sont présentées. Pour chaque classe deux générateurs sont présentés. La première classe de générateurs exploite la réponse d'un système physique qui sert de source pour la génération des séquences aléatoires. Cette classe utilise aussi bien des résultats de simulation que des résultats de mesures interférométriques pour produire des séquences de nombres aléatoires. La seconde classe de générateurs est basée sur deux types de fonctions chaotiques et utilise les sorties de ces fonctions comme indice de permutation sur un vecteur initial. Cette thèse s'intéresse également aux systèmes de chiffrement pour la protection des données. Deux algorithmes de chiffrement d'images utilisant des fonctions chaotiques sont proposés. Ces Algorithmes utilisent un processus de permutation-substitution sur les bits de l'image originale. Une analyse approfondie basée sur des tests statistiques confirme la pertinence des cryptosystèmes développés dans cette thèse.

Sum-of-Products Evaluation Scheme with Fixed-Point Arithmetic

Par Lopez Benoît (Equipe Péquan, LIP6) le 2012-07-19

• In context of filter implementation, once we have a good algorithmic relationship to compute the output(s) of a filter, we want to deduce the fixed-point evaluation scheme of this algorithm.
• In this presentation, we propose to detail technics to yield full parametrized evaluation schemes for evaluate a sum-of-products. These technics generate ordered-sum-of-products, propagate fixed-point representation through a syntax tree representing the evaluation scheme, and finally evaluate degradation errors due to the given order.

From filter/controller to code : the optimal implementation problem

Par Hilaire Thibault (Equipe Péquan, LIP6) le 2012-07-18

• The implementation of signal processing algorithms (or control algorithms) in embedded digital devices is a difficult, error-prone and time-consuming task, essentially due to the finite precision problems. The fixed-point arithmetic used in that context implies a deterioration in performance and characteristics of the filters/controllers, due to the quantization of the embedded coefficients and the roundoff errors occurring in the computations.
• We propose in this presentation to detail the "optimal implementation problem" and to list the various possible actions required to deal with the tradeoff precision/performance/implementation cost. A global method to transform real filters/controllers to fixed-point implementations will be presented, and compared to the floating-point function evaluation problem.

On Kahan's algorithm for the accurate computation of 2 by 2 determinants

Par Jeannerod Claude-Pierre (INRIA - LIP, ENS de Lyon) le 2012-04-25

• Determinants of 2 by 2 matrices are basic numerical kernels used for example for implementing complex arithmetic or geometric predicates, and whose naive evaluation in floating point can suffer severe cancellations and eventually produce inaccurate answers (0 instead of 1). When a fused multiply-add operation is available, Kahan gave an algorithm that is known to reduce the effect of such cancellations. In this talk we will see that Kahan's algorithm is in fact always highly accurate. Specifically, we shall present a complete rounding error analysis of this algorithm and establish, for radix r and unit roundoff u, that its absolute error is at most (r+1)/2 ulps of the exact result, that its relative error is at most 2*u, and that these bounds are essentially optimal.

• This is joint work with Nicolas Louvet and Jean-Michel Muller.