2014

GPU Computing and Combinatorial Optimization Problems

Par El Baz Didier (LAAS, Toulouse) le 2014-09-10

• Nous présentons des contributions sur le GPU computing dans le domaine de l'optimisation combinatoire. Nous donnons un état de l'art et nous concentrons sur des méthodes parallèles de Branch & Bound.

Impact of Time Delays on Power System Stability

Par Milano Federico (University College Dublin, Ireland) le 2014-09-10

• Time delays arise in every dynamic system and, in particular in power systems with wide area controllers and remote measurement signals. The inclusion of delays in the classical transient model of power systems leads to a set of functional differential algebraic equations of retarded type or, more concisely, delay differential algebraic equations (DDAE). The stability analysis of DDAE is more complex and implies a much higher computation burden than that of standard differential algebraic equations (DAE). Nevertheless, theoretical tools for DDAE and modern computers are mature enough to allow tackling the stability of large scale DDAE systems. This seminar presents some systematic approaches to define small signal stability as well as time domain integration of power systems modeled as DDAE. The performance of some CPU- and GPU-based libraries for the computation of eigenvalues and eigenvectors of large matrices is also briefly discussed. The case studies show that time delays, while generally reducing the stability margin of the system, can have surprisingly effects if controller gains are properly adjusted.

Attacking Randomized Exponentiation using Unsupervised Learning

Par Perin Guilherme (LIRMM, Montpellier) le 2014-04-11

• Countermeasures to defeat most of side-channel attacks on exponentiations are based on randomization of processed data. The exponent and the message blinding are particular techniques to thwart simple, collisions, differential and correlation analyses. Attacks based on a single (trace) execution of exponentiations, like horizontal correlation analysis and profiled template attacks, have shown to be efficient against most of popular countermeasures. This work demonstrates how an unsupervised learning can explore the remaining leakages caused by conditional control tests and memory addressing in a RNS-based implementation of the RSA. The device under attack is protected with the exponent blinding and the leak resistant arithmetic. The developed attack combines the leakage of several samples over the segments of the exponentiation in order to recover the entire exponent and shows how to find the points of interest using trace pre-processing and clustering algorithms. Through three statistical classification methods (majority decision, normal probability density function and Bayesian classifier) it is demonstrated how fully recover the information of protected exponentiations. Furthermore, the application of the fast wavelet transform with a multi-resolution analysis is considered in order to explore the leakage of information through different resolutions of the original signal. The presented attack reinforces the importance of hardware countermeasures in public-key architectures.

Exécution en parallèle d'un programme

Par Rahmoune Djallal (DALI, UPVD/LIRMM) le 2014-03-14

• Cet article présente un modèle d'exécution des programmes basé sur un découpage en blocs de base. Pour être mis en œuvre, il nécessite l'emploi d'un processeur à beaucoup de cœurs (many-core). Ses spécificités sont i) l'extraction en parallèle (d'une fonction et de ce qui suit son appel, des itérations d'une boucle vectorisable et des deux alternatives de tout saut conditionnel), ii) un renommage étendu à la mémoire et parallélisé, iii) une exécution en désordre de toutes les instructions de la trace et iv) un retrait en parallèle. Le modèle présenté est évalué à partir du simulateur PerPI appliqué à la suite de benchmarks PBBS composée de programmes issus d'algorithmes parallèles. Il est comparé au modèle implanté actuellement dans les processeurs à quelques cœurs (multi-core). L'évaluation montre d'une part que le modèle présenté capture mieux le parallélisme d'instructions que le modèle actuel et d'autre part que la quantité de parallélisme captée augmente avec la taille des données des algorithmes parallèles.

Determinism and reliability of multicore architectures

Par Defour David (DALI, UPVD/LIRMM) le 2014-02-28

Fractions continues et systèmes de numération : application à l'implantation de fonctions mathématiques élémentaires correctement arrondies et à l'arithmétique modulaire

Par Gouicem Mourad (LIRMM, Montpellier) le 2014-01-31

• Depuis sa normalisation en 1985, l'arithmétique flottante permet d'approcher les calculs en nombres réels de manière portable et prévisible. Cette deuxième propriété est due à une exigence forte sur les opérateurs dont l'implantation est exigée par la norme : leur résultat doit être correctement arrondi. Bien que la norme IEEE 754, dans sa dernière révision de 2008, exige l'implantation des opérations de base, elle ne fait que recommander l'implantation des fonctions mathématiques élémentaires (exp, log, sin, cos, ...). Ceci est principalement dû à un problème calculatoire difficile nommé le dilemme du fabricant de tables.

• Dans cette exposé, je présenterai des travaux communs avec Pierre Fortin et Stef Graillat sur la résolution en pratique du dilemme du fabricant de table pour le format double précision. Je présenterai des algorithmes ainsi que leurs déploiements sur architectures massivement parallèles, notamment les GPU (Graphics Processing Units). Ces derniers permettent une accélération supérieure par rapport à une exécution séquentielle sur CPU du code de référence de Lefèvre (supérieure à 7 par rapport à une exécution parallèle sur CPU hexa-cœur). Il devient alors possible de tester une fonction telle que l'exponentielle en moins d'une semaine sur un seul GPU.

• Le principal outil algorithmique que nous utilisons sont les systèmes de numération à base de développements en fraction continue. Ces derniers permettent de détecter les cas difficiles pour l'arrondi correct via de l'arithmétique sur les nombres réels modulo 1. Aussi, le calcul de ces développements en fraction continue possède la propriété d'être régulier. Nous montrons que cette régularité peut être exploitée par l'exécution partiellement vectorielle des GPUs.

• Je présenterai également un généralisation de l'utilisation de ces systèmes de numération à l'arithmétique modulaire en nombres entiers. Cela permet alors d'obtenir des algorithmes de multiplication et division modulaires ne reposant que sur l'utilisation de l'algorithme d'Euclide pour le calcul de PGCD.