Division efficace en virgule flottante avec des diviseurs entiers constants

cette question demande un moyen d'identifier les valeurs de la constante Y qui permettent de transformer en toute sécurité x / Y en un calcul moins coûteux en utilisant FMA pour toutes les valeurs possibles de x . Une autre approche consiste à utiliser l'analyse statique pour déterminer une sur-approximation des valeurs x peut prendre, de sorte que la transformation généralement malsaine peut être appliquée en sachant que les valeurs pour lesquelles le code transformé diffère de la division originale ne ne pas se produire.

en utilisant des représentations d'ensembles de valeurs à virgule flottante qui sont bien adaptées aux problèmes des calculs à virgule flottante, même une analyse prospective à partir du début de la fonction peut produire des informations utiles. Par exemple:

float f(float z) {
  float x = 1.0f + z;
  float r = x / Y;
  return r;
}

en supposant le mode par défaut (*), dans la fonction ci-dessus x peut seulement être NaN (si l'entrée est NaN), +0.0 f, ou un nombre plus grand que 2 ^-24 en magnitude, mais pas -0,0 f ou quelque chose de plus proche de zéro que 2 ^-24 . Cela justifie la transformation en l'une des deux formes indiquées dans la question pour de nombreuses valeurs de la constante Y .

( * ) hypothèse sans laquelle de nombreuses optimisations sont impossibles et que les compilateurs C font déjà à moins que le programme n'utilise explicitement #pragma STDC FENV_ACCESS ON

avant l'analyse statique qui prédit l'information pour x ci-dessus peut être basé sur une représentation des ensembles de valeurs flottantes une expression peut prendre comme un tuple de:

• une représentation pour les ensembles de valeurs possibles de NaN (puisque les comportements de NaN sont sous-spécifiés, un choix est d'utiliser seulement un booléen, avec true signifiant que certains NaNs peuvent être présents, et false indiquant qu'aucun nan n'est présent.),
• quatre drapeaux booléens indiquant respectivement la présence de +inf, -inf, +0.0, -0.0,
• inclusif intervalle de négatif finis les valeurs à virgule flottante, et
• inclusif intervalle de positif finis les valeurs à virgule flottante.

pour suivre cette approche, toutes les opérations à virgule flottante qui peuvent se produire dans un programme C doivent être comprises par l'analyseur statique. Pour illustrer, l'addition entre les ensembles de valeurs U et V, à utiliser pour gérer + dans le code analysé, peut être mis en œuvre comme:

• Si NaN est présent dans l'un des opérandes, ou si les opérandes peuvent être infinis de signes opposés, NaN est présent dans le résultat.
• Si 0 ne peut être le résultat de l'addition d'une valeur de U et D'une valeur de V, utiliser l'arithmétique d'intervalle standard. La limite supérieure du résultat est obtenue pour l'addition arrondie à la plus proche de la plus grande valeur en U et de la plus grande valeur dans V, donc ces limites doivent être calculées avec rond-à-plus proche.
• Si 0 peut être le résultat de L'addition D'une valeur positive de U et d'une valeur négative de V, alors que M soit la plus petite valeur positive en U telle que-M soit présent en V.
  • si succ(M) est présent en U, alors cette paire de valeurs contribue succ(M) - M aux valeurs positives du résultat.
  • si-succ( M) est présent en V, alors cette paire de valeurs contribue la valeur négative m-succ (M) aux valeurs négatives du résultat.
  • si pred(M) est présent en U, alors cette paire de valeurs contribue la valeur négative pred (M) - M aux valeurs négatives du résultat.
  • si-pred(M) est présent en V, alors cette paire de valeurs apporte la valeur M - pred (M) aux valeurs positives du résultat.
• faire le même travail si 0 peut être le résultat de l'addition d'une valeur négative de U et d'une valeur positive de V. 1519410920"

Reconnaissance: ce qui précède emprunte des idées de" Improving the Floating Point Addition and soustraction Constraints", Bruno Marre & Claude Michel

exemple: compilation de la fonction f ci-dessous:

float f(float z, float t) {
  float x = 1.0f + z;
  if (x + t == 0.0f) {
    float r = x / 6.0f;
    return r;
  }
  return 0.0f;
}

l'approche dans la question refuse de transformer la division en fonction f en un forme alternative, parce que 6 n'est pas une de la valeur pour laquelle la division peut être transformée inconditionnellement. Au lieu de cela, ce que je suggère est d'appliquer une simple analyse de valeur à partir du début de la fonction qui, dans ce cas, détermine que x est un flotteur fini soit +0.0f ou au moins 2 ^-24 en grandeur, et d'utiliser cette information pour appliquer la transformation de Brisebarre et al, confiant dans la connaissance que x * C2 ne dépassement de capacité.

pour être explicite, je suggère d'utiliser un algorithme comme celui ci-dessous pour décider s'il faut ou non transformer la division en quelque chose de plus simple:

1. Est Y l'une des valeurs qui peuvent être transformés à l'aide Brisebarre et al de la méthode en fonction de leur algorithme?
2. do C1 et C2 de leur méthode ont le même signe, ou est-il possible d'exclure la possibilité que le dividende soit infini?
3. est-ce que C1 et C2 de leur méthode ont le même signe, ou peut x prendre seulement une des deux représentations de 0? Si dans le cas où C1 et C2 ont des signes différents et x ne peut être qu'une représentation de zéro, n'oubliez pas de bidouiller(**) avec les signes du calcul basé sur FMA pour le faire produire le zéro correct quand x est zéro.
4. L'importance du dividende peut-elle être suffisamment importante pour exclure la possibilité que x * C2 soit sous-payé?

si la réponse aux quatre questions est "oui", alors la division peut être transformée en multiplication et en FMA dans le contexte de la fonction compilée. L'analyse statique décrite ci-dessus sert à répondre aux questions 2., 3. et 4.

( * * ) "jouer avec les signaux" signifie utiliser -FMA (- C1, x, (- C2)*x) au lieu de FMA (C1, x, C2*x) lorsque cela est nécessaire pour rendre résultat sorti correctement lorsque x ne peut être qu'un des deux zéros signés

Le résultat d'une division à virgule flottante est:

• un signe indicateur
• un significande
• un exposant
• un ensemble d'indicateurs (dépassement de, dépassement de capacité, inexactes, etc - voir fenv() )

obtenir les 3 premières pièces correctes (mais le jeu de drapeaux incorrect) n'est pas suffisant. Sans autre connaissance (par exemple, quelles parties du résultat comptent réellement), les valeurs possibles du dividende, etc) je supposerais que le remplacement de la division par une constante avec multiplication par une constante (et/ou un désordre FMA alambiqué) est presque jamais sûr.

de plus; pour les CPU modernes, Je ne dirais pas non plus que le remplacement d'une division par deux Scfg est toujours une amélioration. Par exemple, si le goulot d'étranglement est l'instruction fetch/decode, cette "optimisation" aggraverait les performances. Pour un autre exemple, si les instructions suivantes ne dépend du résultat (le CPU peut faire beaucoup d'autres instructions en parallèle en attendant le résultat) la version FMA peut introduire des décrochages de dépendances multiples et aggraver les performances. Pour un troisième exemple, si tous les registres sont utilisés, la version FMA (qui nécessite des variables "live" supplémentaires) peut augmenter le "débordement" et aggraver les performances.

il faut Noter que, dans de nombreux cas mais pas tous) de la division ou la multiplication par une constante de multiples de 2 peut être fait avec addition seule (spécifiquement, en ajoutant un nombre de décalage à l'exposant).

j'aime @Pascal 'S réponse mais en optimisation, il est souvent préférable d'avoir un sous-ensemble simple et bien compris de transformations plutôt que d'une solution parfaite.

tous les formats flottants historiques courants et communs avaient une chose en commun: un mantissa binaire.

par conséquent, toutes les fractions étaient des nombres rationnels de la forme:

x / 2 ⁿ

ceci est en contraste avec les constantes dans le programme (et toutes les fractions de base possibles-10) qui sont des nombres rationnels de la forme:

x / (2 ⁿ * 5 ^m )

ainsi, une optimisation testerait simplement l'entrée et la réciproque pour m = = 0, puisque ces nombres sont représentés exactement dans le format FP et les opérations doivent produire des données exactes dans le format.

ainsi, par exemple, à l'intérieur de la fourchette (décimale à deux chiffres) de .01 à 0.99 en divisant ou en multipliant par les nombres suivants serait optimisé:

.25 .50 .75

et tout le reste ne le ferait pas. (Je pense, ne tester d'abord, lol.)