, l'élimination de branchement

Question

float mixValue = ... //in range -1.0f to 1.0f 
for(... ; ... ; ... ) //long loop 
{ 
    float inputLevel = ... //in range -1.0f to 1.0f 
    if(inputLevel < 0.0 && mixValue < 0.0) 
    { 
     mixValue = (mixValue + inputLevel) + (mixValue*inputLevel); 
    } 
    else 
    { 
     mixValue = (mixValue + inputLevel) - (mixValue*inputLevel); 
    } 
} 

juste une simple question, peut-on calculer mixValuesans ramification? ou toute autre suggestion d'optimisation, telle que l'utilisation de SIMD?

modifier: juste pour plus d'informations, je fini par en utilisant cette solution, basée sur la réponse choisie:

const float sign[] = {-1, 1}; 
float mixValue = ... //in range -1.0f to 1.0f 
for(... ; ... ; ... ) //long loop 
{ 
    float inputLevel = ... //in range -1.0f to 1.0f 
    unsigned a = *(unsigned*)(&mixValue); 
    unsigned b = *(unsigned*)(&inputLevel); 

    float mulValue = mixValue * inputLevel * sign[(a & b) >> (8*sizeof(unsigned)-1)]; 
    float addValue = mixValue + inputLevel; 
    mixValue = addValue + mulValue; 
} 

merci.

Answer 1

Inspiré par la réponse de Roku (qui, MSVC++ 10 branches), cela ne semble pas à la branche:

#include <iostream> 

using namespace std; 
const float sign[] = {-1, 1}; 
int main() { 
    const int N = 10; 
    float mixValue = -0.5F; 
    for(int i = 0; i < N; i++) { 
     volatile float inputLevel = -0.3F; 
     int bothNegative = ((((unsigned char*)&inputLevel)[3] & 0x80) & (((unsigned char*)&mixValue)[3] & 0x80)) >> 7; 
     mixValue = (mixValue + inputLevel) + (sign[bothNegative]*mixValue*inputLevel); 
    } 

    std::cout << mixValue << std::endl; 
} 

est ici le démontage, comme analysé par l'IDA Pro (compilé sur MSVC + 10, le mode de sortie):

Disassembly http://img248.imageshack.us/img248/6865/floattestbranchmine.png

Answer 2

Avez-vous référencé la boucle avec et sans la branche?

Au moins, vous pouvez supprimer une partie de la branche, puisque mixValue est en dehors de la boucle.

float multiplier(float a, float b){ 
    unsigned char c1Neg = reinterpret_cast<unsigned char *>(&a)[3] & 0x80; 
    unsigned char c2Neg = reinterpret_cast<unsigned char *>(&b)[3] & 0x80; 
    unsigned char multiplierIsNeg = c1Neg & c2Neg; 
    float one = 1; 
    reinterpret_cast<unsigned char *>(&one)[3] |= multiplierIsNeg; 
    return -one; 
} 
cout << multiplier(-1,-1) << endl; // +1 
cout << multiplier(1,-1) << endl; // -1 
cout << multiplier(1, 1) << endl; // -1 
cout << multiplier(-1, 1) << endl; // -1 

Answer 3

Si vous êtes inquiet au sujet de ramification excessive, regardez Duff's Device. Cela devrait aider à dérouler la boucle un peu. À vrai dire, le déroulement de boucle est quelque chose qui sera fait par l'optimiseur, essayant ainsi de le faire à la main peut être une perte de temps. Vérifiez la sortie de l'assemblage pour le savoir.

SIMD sera certainement utile si vous effectuez exactement la même opération sur chaque élément de votre réseau. Soyez conscient que tout le matériel ne supporte pas SIMD mais certains compilateurs comme gcc fournissent des intrinsèques pour SIMD qui vous évitera de plonger dans l'assembleur.

Si vous utilisez gcc pour compiler le code ARM, les valeurs intrinsèques SIMD se trouvent here

Answer 4

Situé juste à côté du haut de ma tête (je suis sûr qu'il peut être réduite):

mixValue = (mixValue + inputLevel) + (((mixValue/fabs(mixValue)) + (inputLevel/fabs(inputLevel))+1)/fabs(((mixValue/fabs(mixValue)) + (inputLevel/fabs(inputLevel))+1)))*-1*(mixValue*inputLevel);

Juste pour clarifier un peu, je vais calculer séparément signe:

float sign = (((mixValue/fabs(mixValue)) + (inputLevel/fabs(inputLevel))+1)/fabs(((mixValue/fabs(mixValue)) + (inputLevel/fabs(inputLevel))+1)))*-1; 
mixValue = (mixValue + inputLevel) + sign*(mixValue*inputLevel); 

C'est flottant mathématiques points, vous aurez probablement besoin de cor rect pour certains problèmes d'arrondi, mais cela devrait vous mettre sur le bon chemin, je pense.

Answer 5

Que diriez-vous ceci:

const float sign[] = {-1, 1}; 

float mixValue = ... //in range -1.0f to 1.0f 
for(... ; ... ; ... ) //long loop 
{ 
    float inputLevel = ... //in range -1.0f to 1.0f 
    int bothNegative = (inputLevel < 0.0) & (mixValue < 0.0); 
    mixValue = (mixValue + inputLevel) + (sign[bothNegative]*mixValue*inputLevel); 
} 

Edit: Mike était exact que & & introduirait une branche et grâce à Pedro pour le prouver. J'ai changé & & en & et maintenant GCC (version 4.4.0) génère du code sans branche.

Answer 6

float mixValue = ... //in range -1.0f to 1.0f 
for(... ; ... ; ... ) //long loop 
{ 
    float inputLevel = ... //in range -1.0f to 1.0f 
    float mulValue = mixValue * inputLevel; 
    float addValue = mixValue + inputLevel; 
    __int32 a = *(__int32*)(&mixValue); 
    __int32 b = *(__int32*)(&inputLevel); 
    __int32 c = *(__int32*)(&mulValue); 
    __int32 d = c & ((a^b) | 0x7FFFFFFF); 
    mixValue = addValue + *(float*)(&d); 
} 

Answer 7

en regardant votre code, vous voyez que vous aurez toujours ajouter la valeur absolue de mixValue et inputLevel, sauf lorsque les deux sont positifs.

Avec un peu de bits tripoter et connaissances IEEE flottante, vous pouvez vous débarrasser du conditionnel:

// sets the first bit of f to zero => makes it positive. 
void absf(float& f) { 
    assert(sizeof(float) == sizeof(int)); 
    reinterpret_cast<int&>(f) &= ~0x80000000; 
} 

// returns a first-bit = 1 if f is positive 
int pos(float& f) { 
    return ~(reinterpret_cast<int&>(f) & 0x80000000) & 0x80000000; 
} 

// returns -fabs(f*g) if f>0 and g>0, fabs(f*g) otherwise.  
float prod(float& f, float& g) { 
    float p = f*g; 
    float& rp=p; 
    int& ri = reinterpret_cast<int&>(rp); 
    absf(p); 
    ri |= (pos(f) & pos(g) & 0x80000000); // first bit = + & + 
    return p; 
} 

int main(){ 
struct T { float f, g, r; 
    void test() { 
     float p = prod(f,g); 
     float d = (p-r)/r; 
     assert(-1e-15 < d && d < 1e-15); 
    } 
}; 
T vals[] = { {1,1,-1},{1,-1,1},{-1,1,1},{-1,-1,1} }; 
for(T* val=vals; val != vals+4; ++val) { 
    val->test(); 
} 
} 

Et enfin: votre boucle

for(...) { 
    mixedResult += inputLevel + prod(mixedResult,inputLevel); 
} 

Note: les dimensions de votre accumulation n » t match. Le inputLevel est une quantité sans dimension, alors que mixedResult est votre résultat ... (par exemple en Pascal, en Volts, ...). Vous ne pouvez pas ajouter deux quantités avec des dimensions différentes. Probablement vous voulez mixedResult += prod(mixedResult, inputLevel) comme votre accumulateur.

Answer 8

Certains compilateurs (c.-à-d. MSC) nécessiteraient également une vérification manuelle des signes.

Source:

volatile float mixValue; 
volatile float inputLevel; 

float u = mixValue*inputLevel; 
float v = -u; 
float a[] = { v, u }; 

mixValue = (mixValue + inputLevel) + a[ (inputLevel<0.0) & (mixValue<0.0) ]; 

IntelC 11.1:

movss  xmm1, DWORD PTR [12+esp]  
mulss  xmm1, DWORD PTR [16+esp]  
movss  xmm6, DWORD PTR [12+esp]  
movss  xmm2, DWORD PTR [16+esp]  
movss  xmm3, DWORD PTR [16+esp]  
movss  xmm5, DWORD PTR [12+esp]  
xorps  xmm4, xmm4     
movaps xmm0, xmm4     
subss  xmm0, xmm1     
movss  DWORD PTR [esp], xmm0  
movss  DWORD PTR [4+esp], xmm1  
addss  xmm6, xmm2     
xor  eax, eax      
cmpltss xmm3, xmm4     
movd  ecx, xmm3     
neg  ecx       
cmpltss xmm5, xmm4     
movd  edx, xmm5     
neg  edx       
and  ecx, edx      
addss  xmm6, DWORD PTR [esp+ecx*4] 
movss  DWORD PTR [12+esp], xmm6  

gcc 4.5:

flds 32(%esp) 
flds 16(%esp) 
fmulp %st, %st(1) 
fld  %st(0) 
fchs 
fstps (%esp) 
fstps 4(%esp) 
flds 32(%esp) 
flds 16(%esp) 
flds 16(%esp) 
flds 32(%esp) 
fxch %st(2) 
faddp %st, %st(3) 
fldz 
fcomi %st(2), %st 
fstp %st(2) 
fxch %st(1) 
seta %dl 
xorl %eax, %eax 
fcomip %st(1), %st 
fstp %st(0) 
seta %al 
andl %edx, %eax 
fadds (%esp,%eax,4) 
xorl %eax, %eax 
fstps 32(%esp)