stm32. Nous regardons la racine

Au lieu d'introduire

L'article contient un exemple d'optimisation manuelle d'une section critique d'un programme d'application par rapport aux microcontrôleurs stm32 budgétaires, ce qui augmente les performances de 5 fois ou plus par rapport à une fonction de bibliothèque.

L'extraction de racine carrée est souvent utilisée dans les applications. La fonction sqrt est incluse dans la bibliothèque C standard et fonctionne sur des nombres réels:

double sqrt (double num);
long double sqrtl (long double num);

Les microcontrôleurs fonctionnent principalement avec des nombres entiers; ils n'ont généralement pas de registres pour les nombres réels.

En pratique, en plus de la perte de vitesse de calcul sur plusieurs transformations "entier <=> réel" , la précision est également perdue - Exemple 1.

Exemple 1: perte de précision des conversions avant et arrière

//  
uint32_t L1 = 169;
uint32_t L2 = 168;

//  
uint32_t r1 = ( uint32_t )sqrt( ( double ) L1 );
uint32_t r2 = ( uint32_t )sqrt( ( double ) L2 );

//  
L1 = r1*r1; // r1 = 13
L2 = r2*r2; // r2 = 12

//  
// L1 = 169 —  169
// L2 = 144 —  168,    14%

Formulation du problème

Augmentez la précision des calculs sqrt en arrondissant à l'entier le plus proche.

Si possible, augmentez la productivité.

La solution du problème

Créez une fonction personnalisée, par exemple, sqrt_fpu basée sur la fonction standard - Exemple 2.

Exemple 2: calcul d'une racine entière avec l'algorithme sqrt_fpu

uint16_t sqrt_fpu ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    double f_rslt = sqrt( ( double ) L );
    uint32_t rslt = ( uint32_t ) f_rslt;

    if ( !( f_rslt - ( double ) rslt < .5 ) )
        rslt++;

    return ( uint16_t ) rslt;
} 

Avantages de Sqrt_fpu:

• code compact;
• la précision requise est obtenue.

Inconvénients de sqrt_fpu:

• perte de performance due à un appel supplémentaire et à des opérations supplémentaires en virgule flottante;
• absence de potentiel évident d'optimisation de la vitesse de calcul au niveau de l'utilisateur.

sqrt_fpu .

— - ().

-: , .

1. :

« , , .»

sqrt_odd — 3.

3: sqrt_odd

uint16_t sqrt_odd ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint16_t div = 1, rslt = 1;

    while ( 1 )
    {
        div += 2;

        if ( ( uint32_t ) div >= L )
            return rslt;

        L -= div, rslt++;
    }
}

,

.

sqrt_odd:

• ;

sqrt_odd:

• ;
• ; , 10e4+ 150 — 1;
• .

1: sqrt_odd

2. :

« »:

Rj = ( N / Ri + Ri ) / 2

sqrt_new — 4.

4: sqrt_new

uint16_t sqrt_new ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint32_t rslt, div;

    rslt = L;
    div = L / 2;

    while ( 1 )
    {
        div = ( L / div + div ) / 2;

        if ( rslt > div )
            rslt = div;
        else
            return ( uint16_t ) rslt;
    }
}

sqrt_new — sqrt_fpu ( 2).

sqrt_new:

• ;
• — sqrt_fpu;
• ;

sqrt_new:

• .

sqrt_new ( 2):

• ;
• .

2: sqtr_new (!)



(!) — 10e5+ 8 .

sqrt_new :

• , , ( );
• , -, ;
• .

2. sqrt_evn ( 5).

sqrt_evn , , [ 0… 0xFFFFFFFF ].

sqrt_evn 2- 5- , sqrt_new ~40%.

[ 1… 10 000 000 ] sqtr_evn 2-3 .

sqrt_evn — 3.

3: sqtr_evn

, sqrt_evn — 5.

5: sqrt_evn

uint16_t sqrt_evn ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint32_t div;
    uint32_t rslt;
    uint32_t temp;

    if ( L & 0xFFFF0000L )
        if ( L & 0xFF000000L )
            if ( L & 0xF0000000L )
                if ( L & 0xE0000000L )
                    div = 43771;
                else
                    div = 22250;
            else
                if ( L & 0x0C000000L )
                    div = 11310;
                else
                    div = 5749;
        else
            if ( L & 0x00F00000L )
                if ( L & 0x00C00000L )
                    div = 2923;
                else
                    div = 1486;
            else
                if ( L & 0x000C0000L )
                    div = 755;
                else
                    div = 384;
    else
        if ( L & 0xFF00L )
            if ( L & 0xF000L )
                if ( L & 0xC000L )
                    div = 195;
                else
                    div = 99;
            else
                if ( L & 0x0C00L )
                    div = 50;
                else
                    div = 25;
        else
            if ( L & 0xF0L )
                if ( L & 0x80L )
                    div = 13;
                else
                    div = 7;
            else
                div = 3;

    rslt = L;

    while ( 1 )
    {
        temp = L / div;
        temp += div;

        div = temp >> 1;
        div += temp & 1;

        if ( rslt > div )
            rslt = div;
        else
        {
            if ( L / rslt == rslt - 1 && L % rslt == 0 )
                rslt--;

            return ( uint16_t ) rslt;
        }
    }
}

«» — . 1 .

sqrt_evn , .

( 2).

— .

.

[ 3, 7, 13, 25 ] « ». (). .

— .

:

• : STM32F0308-DISCO, MCU STM32F030R8T6
• : STM32CubeIDE
• : USB-UART PL2303HX

:

• :
• : CPU — 48 MHz, UART (RS485) — 9600 bit/s
• : , Release
• : MCU GCC Linker: Miscellaneous: -u _printf_float

sqrt_fpu, sqrt_new sqrt_evn.

100 000 3- — 4.

4:

.

— sqrt_fpu, . — .

, ( 4), .

( 5) .

5:

( 6) , 1 .

sqrt_fpu 19 531, sqrt_evn 147 059 ; sqrt_evn ~7,5 , sqrt_fpu.

6:

, , , .

Dans le même temps, l'optimisation manuelle du code algorithmique peut être efficace dans la production de masse de petits IoT, en raison de l'utilisation de modèles budgétaires de microcontrôleurs, libérant ainsi l'espace de tâches complexes pour les modèles plus anciens.