Note: Descriptions are shown in the official language in which they were submitted.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 1 -
Procédé d'ajustement de la précision d'un programme d'ordinateur
manipulant au moins un nombre à virgule
L'invention concerne un procédé pour ajuster la précision d'un
programme d'ordinateur manipulant au moins un nombre à virgule, et en
particulier pour améliorer la précision d'un tel programme. Elle concerne
également un programme d'ordinateur et un système mettant en oeuvre un
tel procédé.
Le domaine de l'invention est le domaine de la précision de calcul des
programmes d'ordinateur manipulant des nombres à virgule.
Etat de la techniaue
Par précision on désigne l'écart, ou la valeur, (absolu ou relatif) entre
le résultat théorique d'un calcul mathématique que l'on obtient dans le
corps des réels et le résultat effectif de ce même calcul quand il est
réalisé par une machine qui utilise l'arithmétique fixe ou flottante.
La précision comprend d'une part les erreurs induites par la
représentation informatique choisie par l'auteur du programme d'ordinateur
pour les nombres et d'autre part, celles introduites par les instructions
manipulant ces nombres. Dans tous les cas, il est difficile, voire impossible,
pour un auteur de mesurer et d'ajuster de façon manuelle la précision d'un
programme d'ordinateur manipulant des nombres à virgule.
D'une part, il est très difficile de mesurer la précision d'un programme
d'ordinateur lorsqu'il sera exécuté par une machine car les arithmétiques
utilisées causent des problèmes de précision qui ne peuvent pas être
anticipés facilement par un être humain. Un long travail d'analyse manuelle
et de tests est nécessaire pour juger de la précision d'un calcul.
D'autre part, l'amélioration ou l'optimisation de la précision est
principalement combinatoire. En effet, il existe un nombre exponentiel (voire
infini) de manières possibles d'écrire un même calcul (ou, en d'autres termes
de formules mathématiquement équivalentes, par associativité, distributivité,
etc.). Chaque manière d'écrire une formule peut avoir une mesure de
précision différente des autres.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 2 -
II n'existe actuellement aucun procédé automatisé permettant de
prendre en compte les erreurs induites dans un programme d'ordinateur
manipulant un nombre à virgule et d'ajuster ou d'optimiser la précision de ce
programme d'ordinateur.
L'invention a pour but de pallier ces inconvénients.
Il est un but de la présente invention de proposer un procédé pour
ajuster de manière automatisée la précision d'un programme d'ordinateur
manipulant au moins un nombre à virgule.
L'invention a également pour but de proposer un procédé permettant
de personnaliser la précision que l'on souhaite obtenir lors de l'exécution
d'un programme d'ordinateur manipulant au moins un nombre à virgule.
Un autre but de l'invention est de proposer un procédé permettant
d'améliorer la précision d'un programme d'ordinateur manipulant au moins
un nombre à virgule, pour des ressources d'exécution données, et/ou un
temps d'exécution donné.
Encore, un autre but de l'invention est de proposer un procédé
permettant de diminuer, pour une précision donnée, les ressources
nécessaires à l'exécution, et/ou le temps d'exécution, d'un programme
d'ordinateur manipulant au moins un nombre à virgule.
Exposé de l'Invention
L'invention permet d'atteindre au moins l'un des buts précités par un
procédé d'ajustement de la précision fournie par un programme d'ordinateur,
dit source, manipulant au moins un nombre à virgule, ledit procédé
comprenant les étapes suivantes :
- mesure, dite en précision initiale, d'au moins une valeur d'au
moins un nombre à virgule dans ledit programme source ;
- mesure, dite en précision infinie, d'au moins une valeur dudit
nombre à virgule dans ledit programme source dans lequel un
format d'au moins un nombre à virgule, en particulier de tous les
nombres à virgule, et/ou d'une opération primitive manipulant un
nombre à virgule, en particulier de toutes les opérations
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 3 -
manipulant des nombres à virgule, est préalablement remplacé par
un format prédéterminé plus précis, dit format optimal ;
- pour au moins une instruction manipulant, dans ledit
programme source, au moins un nombre à virgule, une étape, dite
d'optimisation, comprenant les étapes suivantes :
= écriture d'au moins une variante réalisant la même
fonction que ladite au moins une instruction ;
= pour chaque variante, mesure d'au moins une valeur
dudit nombre à virgule obtenue avec ladite variante ; et
= sélection d'au moins une variante, dite optimale, en
fonction de ladite valeur mesurée et desdites valeurs en
précision initiale et en précision infinie ; et
- modification dudit programme source par remplacement de
ladite instruction par ladite variante sélectionnée.
Ainsi, le procédé selon l'invention permet d'améliorer, voire
d'optimiser, la précision obtenue avec un programme d'ordinateur en
identifiant une manière spécifique de coder ce programme d'ordinateur, et
plus précisément en identifiant une combinaison particulière de variantes de
codage pour différentes instructions manipulant des nombres à virgules dans
le programme d'ordinateur.
Un programme d'ordinateur optimisé obtenu par le procédé selon
l'invention ne consomme pas nécessairement plus de ressources d'exécution,
et ne nécessite pas forcément un temps d'exécution plus long, comparé au
programme source, tout en proposant des résultats plus précis que ceux
obtenus avec le programme source. En effet, dans le programme
d'ordinateur optimisé, obtenu grâce au procédé selon l'invention, le type de
données manipulées, et le type et la nature des fonctions, restent identiques
à ceux utilisés dans le programme source. Par conséquent, le temps et les
ressources nécessaires pour l'exécution du programme optimisé sont
similaires au temps et aux ressources nécessaires pour exécuter le
programme source.
Plus encore, le procédé selon l'invention permet de diminuer les
ressources et le temps nécessaires à l'exécution du programme d'ordinateur
pour une précision donnée. En effet, il est possible pour une précision
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 4 -
donnée de sélectionner la ou les variante(s) qui nécessite(nt) un temps
d'exécution et/ou des ressources d'exécution plus faibles, de sorte que le
temps d'exécution du programme optimisé est diminué ou les ressources
nécessaires à l'exécution du programme optimisé sont plus petites.
Dans la présente demande, les termes initial et optimal sont
des appellations utilisées uniquement pour éviter des lourdeurs
rédactionnelles. Ainsi, le terme optimal ne veut pas forcément dire qu'il
s'agit de la meilleure variante ou du meilleur format.
Selon l'invention un format/type primitif peut être un des formats
définit par la normes 1EEE754 (par exemple float ou double ) ou tout
autre type défini par l'utilisateur se reposant en interne en partie ou en
totalité sur un des format du standard 1EEE754, ou se reposant sur un
format personnalisé de nombre à virgule (par exemple dans le cadre de
l'arithmétique fixe).
Selon l'invention un format optimal peut être le format MPFR (issu de
la librairie GNU MPFR) présentant une précision plus grande dans la
représentation des nombres à virgule et des opérations traitant ces nombres.
Ainsi, le format d'un nombre à virgule, par exemple le format float
x=0.1 ; en langage C, peut être remplacé par le format MPFR
correspondant, par exemple mpfr_t x=new mpfr_t (0.1, PRECISION) ; ,
où PRECISION est une valeur entière bien plus grande que le taille du
format initiale float . De plus, une opération primitive, par exemple
l'opération d'addition + , peut être remplacée par l'opération réalisant la
même fonction dans la librairie MPFR, par exemple mpfr_add().
Pour ce faire, une bibliothèque peut être définie de sorte que chaque
format primitif soit associé à un format optimal. Ainsi, dès qu'un format
primitif est détecté dans le programme source pour un nombre à virgule ou
une opération, le format optimal correspondant est simplement lu dans ladite
bibliothèque.
Selon une variante nullement limitative, l'étape de mesure en
précision initiale et/ou l'étape de mesure en précision infinie d'une valeur
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 5 -
d'un nombre peut comprendre un ajout dans le programme d'au moins une
instruction, dite d'instrumentation, fournissant ladite valeur.
Avantageusement, le procédé selon l'invention peut comprendre en
outre une étape d'analyse syntaxique, ou parsing en anglais, du
programme source.
Une telle analyse syntaxique permet de fournir une représentation,
dite intermédiaire, dudit programme source, indépendamment du langage,
qui a été utilisé pour coder le programme source. Par exemple la
représentation intermédiaire peut être en langage XML.
Dans ce cas, au moins une, en particulier chacune, des étapes du
procédé selon l'invention peut être réalisée, en fonction de ladite
représentation intermédiaire, et plus particulièrement à partir de ladite
représentation intermédiaire.
Par exemple, au moins une étape de mesure d'au moins une valeur,
d'au moins un nombre à virgule, en précision initiale ou en précision infinie,
est réalisée à partir de ladite représentation intermédiaire. En effet, la
représentation intermédiaire peut être analysée pour détecter au moins une
instruction manipulant au moins un nombre à virgule dans le programme
source. En fonction de la position de cette instruction dans le programme
source, une nouvelle instruction est ajoutée dans le programme source au
niveau ou juste après ladite instruction pour capter la valeur dudit au moins
un nombre à virgule, et afficher et/ou mémoriser ladite valeur captée.
De même, le remplacement d'un format primitif, d'un nombre à
virgule ou d'une opération, dans le programme source peut être réalisé à
partir de la représentation intermédiaire fournie par l'analyse syntaxique.
Par
exemple, au moins un format primitif, d'un nombre à virgule ou d'une
opération, et sa position, et en particulier son point de contrôle, dans le
programme source peuvent être déterminés en analysant la représentation
intermédiaire du programme source. Après avoir déterminé le format primitif
et sa position, et plus particulièrement le point de contrôle associé audit
format primitif, dans le programme source, ce dernier est peut être modifié
pour remplacer le format primitif par le format optimal.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 6 -
La position d'un format primitif renvoyé par l'analyseur syntaxique
peut correspondre au point de contrôle associé audit format, éventuellement
enrichi par au moins une donnée de mise en forme pouvant comprendre une
donnée d'indentation, une donnée de mise en forme textuelle utilisée lors du
codage du programme source, etc.
Plus encore, le procédé selon l'invention peut en outre comprendre
avant l'étape d'écriture d'au moins une variante, une représentation, dite
unifiée, du programme source dans un langage, dit unifié, quel que soit le
langage utilisé pour le programme source.
Ainsi, l'étape d'optimisation peut être réalisée sur le programme
source dans ledit langage unifié.
Un tel langage unifié permet de représenter n'importe quel programme
source dans n'importe quel langage de programmation dans un seul et
unique langage dans lequel il est alors aisé d'identifier une ou des variantes
pour une ou un ensemble d'instructions.
Plus particulièrement, la représentation du programme source dans un
langage unifié peut prendre en entrée le programme source lui-même, ou
une représentation intermédiaire fournie par une analyse syntaxique du
programme source.
Selon un premier exemple de réalisation, au moins une variante d'au
moins une instruction, ou d'un groupe d'instructions, peut être préalablement
renseignée dans une base de données. Dans ce cas, lorsque ladite instruction
(ou ledit groupe d'instruction) est détectée, il suffit de lire dans ladite
base
de données la ou les variantes associée(s) à cette instruction (ou ce groupe
d'instruction).
Alternativement ou en plus, selon un deuxième exemple de réalisation,
au moins une instruction, ou un groupe d'instruction, est associé un ou
plusieurs algorithmes de génération de variantes. Ainsi, lorsque ladite
instruction, ou ledit groupe d'instructions, est détecté le ou lesdits
algorithmes associés sont exécutés pour générer une ou plusieurs variantes
pour ladite instruction ou ledit groupe d'instructions. Pour ce faire, une
base
de données peut mémoriser, pour une ou des opération(s) (ou une ou des
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 7 -
combinaison(s) d'opérations) pouvant être détectée dans le programme
source, par exemple à partir de sa représentation unifiée, un ou des
algorithmes de génération de variante(s) associé(s) à ces opérations (ou
combinaison d'opérations). Ainsi, lorsqu'une opération (ou combinaison
d'opération) est détectée, la base de donnée est lue pour déterminer
l'algorithme de génération de variante. Ce dernier est ensuite exécuté pour
générer les variantes pour cette opération (combinaison d'opérations). Selon
un exemple de réalisation, lorsqu'une combinaison comprenant des
opérations + et x est détectée, un algorithme de factorisation ou de
distributivité prédéterminé est appelé en fonction de la position et du nombre
de ces opérations et des opérantes impliqués.
Avantageusement, pour au moins une instruction, l'étape de
modification du programme source peut comprendre les étapes suivantes :
- identification de l'instruction dans le programme source, par
exemple en fonction d'une représentation dans un langage unifié
dudit programme source et éventuellement en fonction d'une
représentation intermédiaire fournie par une analyse syntaxique
du programme source,
- codage de la variante optimale de ladite instruction dans le
langage du programme source, et
- remplacement de ladite instruction par sa variante optimale
dans le programme source.
Pour réaliser le remplacement de ladite instruction par sa variante
optimale, l'emplacement de l'instruction est identifié dans le programme
source, par exemple à l'aide de la représentation intermédiaire ou la
représentation unifiée, en prenant bien soin d'identifier le début et la fin
de
l'instruction. Puis l'instruction originale est effacée et remplacée par sa
variante optimale.
Selon une caractéristique particulièrement avantageuse, au moins une
variante d'au moins une instruction manipulant au moins un nombre à
virgule peut être écrite en fonction d'au moins une valeur en précision
infinie
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 8 -
dudit nombre, préalablement mesurée lors de l'étape de mesure en précision
infinie.
En effet, il peut arriver qu'une variante d'une instruction donnant les
résultats les plus précis, soit celle dont la structure est adaptée aux
valeurs
que peut(vent) prendre le(s) nombre(s) à virgule manipulé(s) par cette
instruction.
Une telle situation est particulièrement vraie lorsqu'une instruction
manipule un nombre à virgule pouvant prendre différentes valeurs, telles
qu'un intervalle de valeurs.
Selon un exemple de réalisation non limitatif, une instruction peut
manipuler une variable x dont les valeurs sont comprises dans l'intervalle de
valeurs [1-100000], avec 99% des valeurs comprises dans le sous intervalle
[1-2[, la valeur optimale d'une telle instruction peut en réalité comprendre
un ensemble de deux instructions, une première traitant le sous intervalle
[1-2[, et une deuxième traitant le sous intervalle [2-100000].
Ainsi, le procédé selon l'invention permet de tenir compte d'une ou des
valeur(s) en précision infinie d'un nombre à virgule manipulée par une
instruction en vue de déterminer la variante optimale de cette instruction.
La sélection d'une variante optimale peut en outre être réalisée en
fonction d'au moins un autre paramètre préalablement renseigné, en
particulier un paramètre relatif à une durée d'exécution du programme et/ou
un paramètre relatif à une ressource nécessaire pour l'exécution dudit
programme, etc.
Un tel paramètre relatif à une durée d'exécution du programme et/ou
à une ressource nécessaire pour l'exécution dudit programme, peut être un
paramètre concernant le parallélisme du programme source, le format des
nombres à virgules en arithmétique fixe, ou encore le format d'un nombre à
virgule dans au moins une partie du programme source.
Dans ce cas, le procédé selon l'invention peut en outre comprendre
une mesure, pour chaque variante d'une instruction de la valeur dudit
paramètre pour ladite variante, par exemple :
- d'un temps total d'exécution de ladite variante ou de ressources
nécessaires à l'exécution de ladite variante ;
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 9 -
- un nombre de cycle (estimé ou réel) pour exécuter une
variante ;
- un nombre d'instructions exécutées par cycle ( IPC en
anglais) ;
- un niveau de parallélisme d'instructions ( ILP en anglais) ;
- le nombre d'occurrence d'une ou plusieurs opérations ; et/ou
- etc.
Avantageusement, la mesure et l'ajustement de la précision peut
porter sur la valeur elle-même d'une variable.
Alternativement, ou en plus, la mesure et l'ajustement de la précision
peuvent porter sur un critère calculé à partir de ladite valeur de la variable
ou d'un groupe de variable, ou l'évolution de ladite valeur d'une ou plusieurs
variables tout au long du programme, à savoir :
- un écart type de ladite valeur par rapport à celle mesurée en
précision infinie ;
- un écart maximal entre lesdites valeurs d'une même variable
par rapport à celles mesurées en précision infinie tout au long
d'une exécution ;
- la somme (en valeur absolue ou non) des écarts successifs
entre lesdites valeurs d'une ou plusieurs variables par rapport à
celles mesurées en précision infinie tout au long du
programme ;
- l'évolution des écarts successifs entre lesdites valeurs d'une ou
plusieurs variables par rapport à celles mesurées en précision
infinie tout au long du programme. Cette évolution peut être
caractérisée, par exemple, par le calcul d'une dérivée, d'une
interpolation linéaire ou polynomiale, d'une régression ; et/ou
- etc
Avantageusement, et de manière nullement limitative, au moins une
instruction pour laquelle au moins une variante est écrite lors de l'étape
d'écriture peut comprendre :
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 10 -
- une opération mathématique, ou une relation comprenant
plusieurs opérations mathématiques, mise en oeuvre dans le
programme source, et/ou
- un bloc fonctionnel formé par plusieurs instructions,
- un bloc conditionnel formé par plusieurs instructions ;
- un bloc itératif formé par plusieurs instructions ;
- un appel de fonction,
- une définition d'une variable ou d'une fonction,
- etc.
Selon une première variante, pour chaque variante de chaque
instruction, le procédé selon l'invention peut comprendre une génération
d'une variante du programme source en entier.
Alternativement, selon une deuxième variante préférée, l'étape
d'écriture peut comprendre un enrichissement du programme par une ou
plusieurs variantes d'une ou plusieurs instructions, en particulier dans une
représentation unifiée ou intermédiaire dudit programme.
Ainsi, le programme peut être exécuté et/ou analysé statiquement au
fur et à mesure avec toutes les combinaisons possibles en vue de déterminer
les variantes permettant une plus grande précision du programme, dans son
ensemble et non uniquement pour une partie seulement du programme.
Plus particulièrement, l'étape de mesure de la valeur d'un nombre
obtenue avec une variante d'une instruction peut comprendre les opérations
suivantes :
- parcourir le programme avec ladite variante, éventuellement en
combinaison avec chacune des variantes d'au moins une autre
instruction, en particulier de chacune des autres instructions ; et
- faire propager l'erreur obtenue avec ladite variante au fur et à
mesure du programme pour chaque combinaison, en particulier
l'erreur est propagée dans un format optimal tel que par exemple
le format MPFR.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 1 1 -
Ainsi, pour une instruction donnée, il est possible de mesurer la
précision fournie par ladite variante en combinaison avec au moins une, en
particulier chaque, variante d'au moins une autre instruction, en particulier
de chacune des autres instructions dudit programme pour lesquelles des
variantes sont déterminées.
Prenons le cas non limitatif d'un programme source comportant cinq
instructions, ou groupes d'instructions, à savoir les instructions (A, B, C,
D,
E) pour lesquelles il existe au moins une variante, par exemple ((Ai, A2),
(B1,
B2, B3), (Cl, C2, C3, C4), (Dl, D2), ...,
En)). Pour déterminer, la variante
optimale de C , chacune des variantes (Ci, C2, C3, C4) est testée en
combinaison avec chacune des variantes des autres instructions, afin de
déterminer la variante de C qui permet d'obtenir la meilleure précision,
ou plus généralement la précision souhaitée, par l'ensemble du programme
source.
Avantageusement, pour la mesure d'au moins une valeur d'au moins
un nombre à virgule pendant l'étape d'optimisation, pour au moins une
combinaison, la propagation de l'erreur peut être réalisée en utilisant le
format optimal, par exemple le format MPFR.
Ainsi, il est possible de déterminer la précision réellement obtenue par
la variante d'une instruction, indépendamment de la précision introduite par
la représentation utilisée par dans le programme source.
Selon un exemple de réalisation nullement limitatif, et tel que décrit
plus haut :
- le format optimal pour au moins une variable peut être le format
MPFR ou le format rationnel, de sorte qu'au moins une variable au
format primitif est redéfinie au format MPFR ou au format d'un
nombre rationnel ; et/ou
- le format optimal pour une opération peut être le format MPFR
de sorte qu'au moins une opération mathématique au format
primitive est redéfinie par un appel de fonction au format MPFR.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 12 -
L'étape de modification du programme source fournit, un programme
dit optimisé.
Le procédé selon l'invention peut en outre comprendre une étape de
vérification de l'optimisation, comprenant les étapes suivantes :
- mesure en précision initiale, d'au moins une valeur d'au moins
un nombre à virgule dans ledit programme source optimisé ; et
- comparaison de ladite valeur mesurée à une valeur dudit
nombre à virgule mesurée en précision initiale pour le programme
source.
Selon un autre aspect de la présente invention, il est proposé un
programme d'ordinateur comprenant des instructions pour mettre en oeuvre
toutes les étapes du procédé selon l'invention, lorsque ledit programme est
exécuté par un appareil électronique/informatique.
Un tel programme d'ordinateur peut être écrit dans tout langage de
programmation, et en particulier en C, C++, JAVA, Fortran, Pascal, ADA,
COBOL, etc.
Selon encore un autre aspect de la présente invention, il est proposé
un système comprenant :
- un programme d'ordinateur, et/ou
- des moyens configurés pour mettre en oeuvre toutes les étapes
du procédé selon l'invention.
Un tel système peut comprendre ou consister en un ou plusieurs
ordinateurs munis d'instructions exécutables par un ou plusieurs processeurs
pour mettre en oeuvre toutes les étapes du procédé selon l'invention.
Un tel système peut être tout matériel électronique et/ou informatique
capable d'exécuter des instructions informatiques. Un tel système peut
également se réduire à un processeur ou une puce électronique configurée
matériellement et/ou avec des instructions informatiques pour mettre en
oeuvre chacune des étapes du procédé selon l'invention.
Un tel système peut, dans une version pratique, être mis en oeuvre ou
correspondre à un ordinateur.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 13 -
D'autres avantages et caractéristiques apparaîtront à l'examen de la
description détaillée des exemples nullement limitatifs, et des dessins
annexés sur lesquels :
- la FIGURE 1 est une représentation schématique sous la forme
d'un diagramme des étapes d'un premier exemple non limitatif
d'un procédé selon l'invention ;
- la FIGURE 2 est une représentation schématique des résultats
fournis par le procédé de la FIGURE 1 sur un exemple non
limitatif d'un programme source ;
- la FIGURE 3 est une représentation schématique sous la forme
d'un diagramme des étapes d'un deuxième exemple non limitatif
d'un procédé selon l'invention ; et
- la FIGURE 4 est une représentation schématique d'un exemple
non limitatif d'un système selon l'invention.
Il est bien entendu que les modes de réalisation qui seront décrits
dans la suite ne sont nullement limitatifs. On pourra notamment imaginer
des variantes de l'invention ne comprenant qu'une sélection de
caractéristiques décrites par la suite isolées des autres caractéristiques
décrites, si cette sélection de caractéristiques est suffisante pour conférer
un
avantage technique ou pour différencier l'invention par rapport à l'état de la
technique antérieur. Cette sélection comprend au moins une caractéristique
de préférence fonctionnelle sans détails structurels, ou avec seulement une
partie des détails structurels si cette partie uniquement est suffisante pour
conférer un avantage technique ou pour différencier l'invention par rapport à
l'état de la technique antérieur.
En particulier toutes les variantes et tous les modes de réalisation
décrits sont combinables entre eux si rien ne s'oppose à cette combinaison
sur le plan technique.
Sur les figures, les éléments communs à plusieurs figures conservent
la même référence.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 14 -
La FIGURE 1 est une représentation schématique sous la forme d'un
diagramme des étapes d'un premier exemple non limitatif d'un procédé selon
l'invention.
La FIGURE 2 est une représentation schématique des résultats fournis
par les différentes étapes du procédé 100 de la FIGURE 1, sur un exemple
non limitatif d'un programme source.
Le procédé 100 représenté sur la FIGURE 1 comprend une étape 102
chargeant le programme source. Le programme source chargé peut être un
code source, c'est-à-dire dans le langage utilisé pour le coder, ou sous la
forme d'un exécutable, c'est-à-dire dans le langage utilisé pour être exécuté
dans un ordinateur ou une machine capable d'exécuter un programme en
langage machine, tel qu'un automate par exemple. Lors de cette étape 102,
le programme source est copié en au moins deux exemplaires, une copie du
programme source est mémorisée et l'autre copie est utilisée pour réaliser
les étapes suivantes.
Un exemple non limitatif d'un programme source 200 chargé lors de
l'étape 102 est donné en FIGURE 2a. Ce programme source est codé en
C++. L'exemple donnée en FIGURE 2a comprend une fonction appelée
polynôme qui a pour fonction globale d'évaluer le polynôme x2+x sur une
série de points compris entre 4097 et 4105.
Lors d'une étape 104, une analyse syntaxique du programme source
est réalisée par un parseur. Cette étape 104 fournit une représentation
intermédiaire du programme source, par exemple en langage XML. Cette
représentation intermédiaire comprend :
- chaque événement dans le programme source manipulant au moins
un nombre à virgule,
- pour chaque événement, l'emplacement et en particulier le point de
contrôle éventuellement enrichi tel que décrit plus haut, dans le
programme source, de l'instruction, ou du bloc/groupe d'instructions,
réalisant cet événement.
Chaque événement peut être une opération mathématique, une
fonction informatique, une boucle conditionnelle, etc...
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 15 -
En fonction de la représentation intermédiaire, une étape 106 ajoute
dans une copie du programme source, une ou des instructions, dite(s) de
sortie, pour mesurer la valeur d'un ou plusieurs nombres à virgule dans le
programme. Autrement dit, cette étape 106 réalise une instrumentation en
précision initiale du programme source par ajout dans le programme source
d'instructions d'instrumentation qui ont pour but de fournir la ou les valeurs
d'un ou plusieurs nombres à virgule, manipulé(s) dans le programme source.
Cette étape 106 fournit une version instrumentée du programme source en
précision initiale.
Une version instrumentée en précision initiale 202 du programme
source 200 de la FIGURE 2a est donnée en FIGURE 2b. On remarque que
cette version instrumentée en précision initiale comprend à plusieurs reprises
l'instruction d'instrumentation sauvegarder() qui permet de mémoriser la
valeur d'un nombre à virgule manipulée dans la fonction polynome().
Une étape 108, qui est réalisée après l'étape 106, réalise une
instrumentation du programme source en précision infinie. Pour ce faire,
cette étape 108 prend en entrée une copie de la version instrumentée en
précision initiale 202 fournie à l'étape 106. Dans cette copie de la version
instrumentée en précision initiale 202, l'étape 108 replace :
- chaque, format primitif par un format de précision plus grande
que le format primitif, tel que par exemple par un format MPFR.
Par exemple lorsque le programme source est codé en C++, un
format primitif tel que double , float , double double est
remplacé par les équivalents MPFR ;
- chaque opération primitive par une opération de précision plus
grande que l'opération primitive, telle que par exemple par une
opération MPFR. Par exemple, lorsque le programme source est
codé en C++, opération primitive telle que l'addition, c'est à dire
+ , est remplacé par l'opération mpfr_add().
Une version instrumentée en précision infinie 204 du programme
source 200 de la FIGURE 2a est donnée en FIGURE 2c. On remarque que,
dans la fonction polynome() , le format de la variable y a été changé
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 16 -
de float en extend et le format de la variable calcul a été changé
de float en extend . De plus, l'opération d'addition primitive + a
été remplacée par un appel de fonction add de précision supérieure, et
l'opération de multiplication primitive x a été remplacée par un appel de
fonction mult de précision supérieure.
Ensuite, une étape 110 exécute la version instrumentée en précision
initiale 202 et la version en précision infinie du programme source. Les
valeurs de la variable calcul obtenues avec chacune de ces versions sont
mémorisées. La FIGURE 2d donne dans un tableau 206 les valeurs de la
variable calcul obtenues en précision initiale et en précision infinie ou
idéale. La différence entre les deux valeurs est également signalée pour
chaque valeur de départ.
Ensuite, lors d'une étape 112, le procédé réalise une représentation
dans un langage unifié du programme source 200, et en particulier de la
fonction polynome() du programme 200 qui manipule des nombres à
virgule. Pour ce faire, l'étape 112 prend en entrée la représentation
intermédiaire fournie par l'étape 104 et fournit la représentation unifiée
grâce à un programme informatique dédié au parseur utilisé lors de l'étape
104. Une telle représentation unifiée peut être réalisée dans un langage
connu ou dans un langage propriétaire spécifiquement défini pour l'étape
112.
Une version 208 dans un langage unifié du programme source 200 de
la FIGURE 2a, et en particulier de la fonction polynome() de ce
programme source 200 manipulant les nombres à virgule, est donnée en
FIGURE 2e. Le langage unifié dans cet exemple est un langage propriétaire
dans lequel, les flèches avec deux traits représentent l'enchaînement des
instructions, les flèches simples représentent l'arbre syntaxique mais aussi
d'évaluation de l'instruction.
Ensuite, lors d'une étape 114, une fois la représentation dans le
langage unifié construit, différents algorithmes de transformation syntaxique
sont appliqués au programme dans le langage unifié, pour fournir un
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 17 -
programme enrichi avec des variantes pour une ou plusieurs instructions
manipulant des nombres à virgule, tel que par exemple des algorithmes de
distributivité, de factorisation, de dépliement de bloc itératif, etc. Cette
étape
114 fournit un programme source enrichi dans le langage unifié.
Une version enrichie dans le langage unifié 210 du programme 208 de
la FIGURE 2e est donnée en FIGURE 2f. Les algorithmes appliqués lors de
l'étape 114 conduisent à former des classes d'équivalence représentées par
des ovales en pointillés sur la FIGURE 2f qui contiennent de nouvelles
manières d'écrire ce programme. Entre autre ces algorithmes peuvent
conduire à former une expression où l'on substitue cakul 0 par sa définition
dans la formulation de calcul 1. Par la suite d'autres algorithmes de
transformation vont identifier que l'expression y + (v x y) peut être
transformé avec la règle de factorisation de l'arithmétique réelle. Par
exemple, l'expression y + (y x y) peut être transformée en y x (v +
1.0) .
Lors d'une étape 116, pour chaque instruction, et pour chacune des
variantes identifiées lors de l'étape 114 pour cette instruction, les valeurs
du
ou des nombres à virgule fournie par cette variante combinée à chacune des
variantes des autres instructions sont mesurées, par analyse statique ou par
analyse dynamique. Cette mesure consiste, par exemple, à instrumenter le
programme source enrichi dans le langage unifié obtenu à l'étape 114 en vue
de fournir les valeurs du ou des nombres à virgule, par exemple de manière
identique ou similaire à celle décrite en référence à l'étape 106. Lors de
cette
étape, l'erreur est, de préférence, propagée en utilisant le format optimal
par
exemple le format MPFR.
Une fois les valeurs mesurées lors de l'étape 116, pour chacune des
variantes, ces valeurs sont comparées lors d'une étape 118 à celles obtenues
en précision initiale et en précision infini, lors de l'étape 110. Cette
comparaison permet de déterminer/choisir la variante qui fournit la meilleure
précision, ou la plus petite erreur. Dans l'exemple représenté sur la FIGURE
2f, c'est la variante calcul _1 = y x (y + 1.0) qui fournit la meilleure
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 18 -
précision, c'est-à-dire la valeur qui se rapproche le plus de celle obtenue en
précision infinie.
Lors d'une étape 120, le programme source est modifié de sorte qu'au
moins une instruction manipulant un nombre à virgule est remplacée par sa
variante optimale identifiée lors de l'étape 118. Pour ce faire, la
représentation intermédiaire obtenue à l'étape 104 est consultée pour
identifier la position, et en particulier le début et la fin, de l'instruction
en
question (ou des instructions ou encore du bloc d'instructions). Elle est
ensuite remplacée par sa variante dans le langage utilisé pour coder le
programme source. Cette étape 120 fournit donc un programme source
optimisé.
Un exemple de programme optimisé 212 pour le programme source
200 de la FIGURE 1, et en particulier pour la fonction polynome() est
donné en FIGURE 2g. On remarque les lignes de code dont la fonction était
de calculer la variable var float calcul , à savoir les lignes de code
suivantes :
calcul = y x ; // calcul du polynôme x2
calcul = calcul + ; // calcul du polynôme x2 +X
ont été remplacées par leur variante optimisée, à savoir par la ligne de code
suivante :
calcul = y x (v + 1.0) ;
Lors d'une étape 122, optionnelle, le procédé 100 permet de confirmer
que le programme source optimisé fournit des résultats plus précis. Pour ce
faire, le programme source optimisé est instrumenté en précision initiale, de
manière similaire ou identique à l'étape 106, puis exécuté. Les valeurs
mesurées sont comparées à celles obtenues lors de l'étape 110, avec le
programme source, en précision initiale et en précision infinie.
La FIGURE 3 est une représentation schématique sous la forme d'un
diagramme des étapes d'un deuxième exemple non limitatif d'un procédé
selon l'invention.
CA 02970551 2017-06-09
WO 2016/091826
PCT/EP2015/078872
- 19 -
Le procédé 300 représenté sur la FIGURE 3 comprend toutes les
étapes du procédé 100 représenté sur la FIGURE 1.
En plus, le procédé 300 comprend suite à l'étape 102, une étape 302
réalisant une exécution du programme source chargé pour mesurer et
mémoriser la valeur, dite initiale, d'au moins un paramètre relatif à
l'exécution du programme source, à savoir par exemple :
- un temps total d'exécution,
- une quantité de ressources nécessaires pour l'exécution,
- etc.
De plus, le procédé 300 comprend suite à l'étape 116, une étape 304,
réalisant pour chaque variante la valeur du ou des paramètres relatifs à
l'exécution.
Ainsi, dans le procédé 300, lors de l'étape 118, le choix de la variante
optimisée est réalisé :
- d'une part en fonction de la précision, et
- d'autre part en fonction d'au moins une valeur mesurée pour au
moins un paramètre relatif à l'exécution du programme, tel que
par exemple :
= un temps d'exécution du programme, ou
= une quantité totale de ressources nécessaires à
l'exécution du programme.
Ainsi, il est par exemple possible de choisir pour au moins une
instruction, une variante qui fournit la même précision que l'instruction
initiale, mais qui permet de diminuer le temps total d'exécution du
programme et/ou les ressources nécessaires à l'exécution du programme.
Plus généralement, le procédé 300 représenté sur la FIGURE 3 permet
d'ajuster la précision du programme d'ordinateur en fonction d'au moins un
autre paramètre d'exécution du programme.
La FIGURE 4 est une représentation schématique d'un exemple non
limitatif d'un système selon l'invention.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 20 -
Le système 400 représenté sur la FIGURE 4 comprend un ensemble de
modules agencés ou configurés pour mettre en oeuvre le procédé selon
l'invention, tel que par exemple les procédés 100 ou 300 décrits plus haut.
Le système 400 comprend :
- un module 402, dit parseur, pour fournir par analyse syntaxique
d'un programme source, une représentation intermédiaire de ce
programme source,
- un module 404, dit d'instrumentation, pour insérer dans un
programme source des instructions d'instrumentations pour
mesurer et fournir au moins une valeur d'au moins un nombre à
virgule manipulé par/dans le programme source ;
- un module 406, dit de précision infinie, permettant de modifier
au moins un format (ou un type) d'au moins un nombre ou d'une
opération du programme source,
- un module 408 d'exécution d'un programme d'ordinateur pour
fournir :
o une valeur d'au moins un paramètre relatif à l'exécution du
programme tel que par exemple le temps d'exécution, et/ou
o une valeur d'au moins un programme préalablement
instrumenté ;
- un module 410, dit de conversion, permettant de convertir le
programme source dans un langage unifié, tel que par exemple le
langage utilisé sur la FIGURE 2f;
- un module 412, dit d'enrichissement, configuré pour enrichir le
programme source par au moins une variante d'au moins une
instruction et/ou d'au moins un bloc d'instructions ; et
- un module 414 configuré pour gérer les autres modules et de
choisir au moins une variante d'au moins une instruction, ou d'un
bloc d'instructions en fonction des valeurs fournies par les autres
modules, et en particulier par le module 408.
Le système 400 peut en outre comprendre un ou plusieurs moyens de
mémorisation 416 pour y mémoriser une ou des valeurs mesurées par les
autres modules, et en particulier par le module 408.
CA 02970551 2017-06-09
WO 2016/091826 PCT/EP2015/078872
- 21 -
Bien que représenté de manière séparée sur la FIGURE 4, plusieurs
modules, et en particulier tous les modules, peuvent être intégrés dans un
unique module.
Le système 400 peut être un ordinateur, un processeur, une puce
électronique ou tout autre moyen configurable physiquement ou par logiciel
pour réaliser les étapes du procédé selon l'invention.
Bien entendu l'invention n'est pas limitée aux exemples qui viennent
d'être décrits.
