Étude et conception d'opérateurs arithmétiques [1cm] Habilitation à diriger les recherches Université

Arnaud Tisserand

Description

Plan IntroductionEtude et conception d’operateurs arithmetiques Resume des activitesHabilitation a diriger les recherches Selection de travaux :Universite Rennes 1I Architecture recon gurable pour l’arithmetique en ligneI Multiplication par des constantesArnaud TisserandI Operateurs arithmetiques securises et bibliotheque arithmetique pourCNRS, IRISA, equipe-projet CAIRNla cryptographie6 juillet 2010 Conclusion et perspectivesArnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 2/39Exemples d’operateurs arithmetiques (1/3) Exemples d’operateurs arithmetiques (2/3) 0filtre "idéal"1#i n c l u d e filtre arrondi2#i n c l u d e Voir moins Voir plus

Informations

• Publié par: Nishor
• Nombre de lectures: 86
• Langue: Français

Extrait

Plan
Introduction
Etude et conception d’operateurs arithmetiques
Resume des activites
Habilitation a diriger les recherches Selection de travaux :
Universite Rennes 1
I Architecture recon gurable pour l’arithmetique en ligne
I Multiplication par des constantesArnaud Tisserand
I Operateurs arithmetiques securises et bibliotheque arithmetique pourCNRS, IRISA, equipe-projet CAIRN
la cryptographie
6 juillet 2010
Conclusion et perspectives
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 2/39
Exemples d’operateurs arithmetiques (1/3) Exemples d’operateurs arithmetiques (2/3)
0
filtre "idéal"1#i n c l u d e <s t d i o . h>
filtre arrondi
2#i n c l u d e <math . h> −10 filtre de Samueli
3
4 t y p e d e f f l o a t f u n c t ( f l o a t x ) ; −20
5
N −30X6 f l o a t i n t e g r a t e ( f u n c t f , f l o a t a , f l o a t b , i n t n )
7f y[n] = cx[n i]i −40
8 i n t i ; f l o a t x = a ; f l o a t s = 0 . 0 ; f l o a t h = ( b a ) / ( n 1);
i=0
9 f o r ( i =0 ; i<n ; i ++) f s += f ( x ) h ; x += h ; g −50
10 r e t u r n s ;
11g −60
0 0.2 0.4 0.6 0.8 112
fréquence normalisée13 f l o a t f ( f l o a t x ) f r e t u r n 1 . 0 / x ; g
14
15 i n t main ( v o i d ) y
16f
17 f l o a t r , r t h =0.69314718055994530942; 0
P
18 0x cos sin x
19 r = i n t e g r a t e ( ( f u n c t) f , 1 . 0 , 2 . 0 , 1 0 0 0 ) ; =0y sin cos y20 P
21 p r i n t f ( " r=%f r t h=%f e r r=%fnn" , r , rth , f a b s ( rth r ) ) ;
22 r e t u r n 0 ;
23g x
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 3/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 4/39
atténuation (dB)6
Exemples d’operateurs arithmetiques (3/3) Arithmetique des ordinateurs, une ( de nition )
2 3Operations sur la courbe elliptique y = x + 4x + 20 sur le corps ni F29 precision vitesse, debit, latence
comportement surface de circuitarithmetique
memoire (I et D)test, simulationaddition de 2 points : P + Q
preuve, meth. formelle energie, puissancerepresentationdoublement d’un point : [2]P
y des nombres validation performances
resultat : le point (x ; y ) avec3 3
N;Z;Q;’R;F a prioriq25 modelisation2x = x x ; y =(x x ) y3 1 2 3 1 3 1 a posteriori mesureQ2P
820 y y algorithme2 136P > psi P =Q< q;;; ; mod;4P x x2 1
15 x = 2 S;e ;’ f (x); : : :3x + a> 1: si P = Q adequation2y110 P
1 outils etoperations sur le corps ni : ;; x
5 implantation
support
applicationP = (8; 10), Q = (24; 22) soft GPP/SP,3PP + Q
generateurs de code HW/SWx ASIC, FPGA5 10 15 20 25 multiplication scalaire (k2N, grand) :
bibliotheques
[k]P = P + P +::: + P cible integration outils haut niveau| {z }
k fois
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 5/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 6/39
Resume des activites : encadrement Resume des activites : collaborations
ST
Andrianina ACI SI
these M2R
Andriamanga
100% 90% ST ACI NIM
Romain Danuta
ACI crypto. BEAMichard Pamula
PAI PAI PAI30% 90% 90%
Martin Nicolas Veyrat- Thomas ST LIRMM UCC
Dimmler Charvillon Chabrier
U. CalgaryACI JC30% 40% 45%
Fabio Saurabh-
Julien Francq
CSEM POSIC UQAC ANR ROMARestrepo Kumar Raina
PAI90% 20% 100%
Jose EPFL UCI U. Cardi UCD Waterloo UMassNicolas Stephane
PICSLopesBoullis Simard
UCLA
98 99 00 01 02 03 04 05 06 07 08 09 10
98 99 00 01 02 03 04 05 06 07 08 09 10
CSEM INRIA{LIP CNRS{LIRMM CNRS{IRISA
CSEM INRIA{LIP CNRS{LIRMM CNRS{IRISA
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 7/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 8/39Resume des activites : enseignement & animation Resume des activites : production scienti que
sem. inv.
ARITH18 ECOFAC
MEPLIB
SEEDGEN
ecoles ARCHI DIVGEN
4 pers. 1{3 inge. 15 pers. FLIP PACE
resp. resp.
resp. moyens info
equipe equipe
conferences
admin. elu conseil tutorialadmin. outils CAO
systeme labo.
30 h/an 50 h/an 12 h/an 30 h/an 10 h/an journaux
Unix Prg. Solaris archi. mat. circ. integ. arith. ordi.
C/C++ (FC SUN) (DEA) (DEA) (M2R) chapitres
98 99 00 01 02 03 04 05 06 07 08 09 10
brevet
CSEM INRIA{LIP CNRS{LIRMM CNRS{IRISA 98 99 00 01 02 03 04 05 06 07 08 09 10
CSEM INRIA{LIP CNRS{LIRMM CNRS{IRISA
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 9/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 10/39
Themes de recherche abordes Architecture recon gurable pour l’arithmetique en ligne
Arithmetique en ligne
Generalites :
Architectures recon gurables pour le calcul : FPOP et FPPA
FPOP : Field Programmable On-line oPerators
Operateurs speci ques pour FPGA
Travail avec P. Marchal, P. Nussbaum et C. Piguet
n Multiplication : par des constantes, tronquee, x (n2N)
Cible : applications embarquees de contr^ ole numerique
Division : par une constante, asynchrone, generateur automatique
Approximation de fonctions : tables ou polyn^ omes
brevet Bibliotheques ottantes : CoolRISC et FLIP (ST200)
SPIE
Arithmetique a basse consommation d’energie : operateurs, FPL
modelisation, evaluation, GPU
FPOP Operateurs arithmetiques pour la cryptographie : corps nis,
hachage, securisation contre les attaques, bibliotheque PACE
98 99 00 01 02 03 04 05 06 07 08 09 10
Outils : generateurs, programmation, gestion de la precision CSEM INRIA{LIP CNRS{LIRMM CNRS{IRISA
Arithmetique par estimation
Generateurs vraiment aleatoires
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 11/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 12/39Arithmetique en ligne (1/2) Arithmetique en ligne (2/2)
Representation redondante des nombres :x x x x x x x x 0 0x y 1 2 3 4 5 6 7 8i+d i+dArithmetique en ligne :
y y y y y y y y 0 0 n1 2 3 4 5 6 7 8 Xoperator
i arithmetique serie X = x x 2Di iinvalid r r r r r r r r1 2 3 4 5 6 7 8ri t poids forts en t^ete i= m
t t t t t t t t
d.t
toutes les operations avec les poids forts en t^ete
Avantages : Inconvenients :
certaines op a delai en ligne (latence) variable (p. ex.S)
faible surface operations lentes
bases utilisees :
parallelisme (pipeline) synchronisation lourde
I base = 2 : chi res dans D =f 1; 0; 1g (borrow-save)bs
haut debit peu (pas) d’outil I base = 4 : chi res dans D f 3;:::; 3g ouD f 2;:::; 2g4;3 4;2
circuit regulier
Caracteristiques des principales operations : interconnexion simple
p precision variable possible operation
assez simplement
surface O(1) O(n) O(n) O(n)
temps calcul O(n) O(n) O(n) O(n)Origine : M. Ercegovac dans les annees 70
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 13/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 14/39
FPOP : architecture generale FPOP : cellule lineaire
main data flow
cell inputs
D/D A/D D/D input blocks programmable delay
ROM programmable FIFOs (1−8 bits)
linear operators array CTRL
loop data flow
computation blocks
RAM PRG programmable multipliers (1−8 bits)non-linear operators
D/D D/A D/D output blocks
programmable adder tree(s)
saturation blocs d’operations lineaires c x et con guration pour : programmable routing point
Pk normalization
I c x + y, c xk ki=0
cell outputsI multiplication x y, x y + z
p
autres operations : x y; 1=x; x et approx. fonction f (x)’ p(x)
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 15/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 16/39FPOP : con gurations d’une cellule lineaire FPOP : ot de programmation
source code
parsing
signal list operation list control structure(8 ) r a . x + y (4 ) r x . y + z (2 ) r x . y + x . y + r (1 ) r r + x . y1 1 2 2 i i
resource allocation schematic toolFPOP model
netlist netlist
(4 ) r a . x + y (2 ) r x . y + z (2 ) r x . y + r (1 ) r x . y + x . y + r1 1 2 2
optimization scheduling
netlist
(2 ) r a . x + y (1 ) r x . y + z (2 ) r a . x + r (1 ) r x . y + r place and route
physical configuration
FPOP
(2 ) r a . x + y (1 ) r x . y + z (2 ) r a . x + r (1 ) r x . y + r
Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 17/39 Arnaud Tisserand, CNRS{IRISA. HDR: Etude et conception d’operateurs arithmetiques 18/39
Multiplication par des constantes Multiplication par des constantes : probleme
Generalites : Idee generale : remplacer les multiplications par des constantes par une
suite d’additions (ou soustractions) et de decalages Travail commence avec la these de N. Boullis
Generateur automatique de code VHDL tres optimise Buts :
Resultats utilises dans : augmenter la vitesse
I d’autres travaux et publications (p. ex. approx. de fonctions, TNS) reduire la taille et la consommation
I des collaborations : UQAC, U. Calgary
I Exemple simple : r = 165 x 165 = (10100101)des aides ponctuelles 2
x x
t
r +ARITH IEEE TC
SYMPA r165 4x +
32