algoritmo di divisione a 64 bit/32 bit più veloce per ARM/NEON?

Question

Sto lavorando su un codice in cui in due punti ci sono 64 bit per divisione in virgola fissa a 32 bit e il risultato è preso in 32 bit. Questi due luoghi stanno prendendo insieme più del 20% del tempo totale impiegato. Quindi mi sento come se potessi rimuovere la divisione a 64 bit, potrei ottimizzare bene il codice. In NEON possiamo avere alcune istruzioni a 64 bit. Qualcuno può suggerire alcune routine per risolvere il collo di bottiglia usando un'implementazione più veloce.

O se potessi rendere la divisione 64 bit/32 bit in termini di divisione 32 bit/32 bit in C, anche questo va bene?

Se qualcuno ha qualche idea, potresti aiutarmi per favore?

Answer 1

Ho fatto un sacco di aritmetica in virgola fissa in passato e ho fatto molte ricerche alla ricerca di partizioni rapide a 64/32 bit. Se cerchi google per "divisione ARM", troverai tonnellate di ottimi link e discussioni su questo argomento.

La soluzione migliore per architettura ARM, dove anche una divisione a 32 bit potrebbe non essere disponibile in hardware è qui:

http://www.peter-teichmann.de/adiv2e.html

Questo codice assembly è molto vecchio, e il tuo assemblatore non può capire la sintassi di esso. Vale comunque la pena portare il codice sulla tua toolchain. È il codice di divisione più veloce per il tuo caso speciale che ho visto finora e mi fido: li ho confrontati tutti :-)

L'ultima volta che l'ho fatto (circa 5 anni fa, per CortexA8) questo codice era circa 10 volte più veloce di quello generato dal compilatore.

Questo codice non utilizza NEON. Una porta NEON sarebbe interessante. Non sono sicuro se migliorerà molto le prestazioni.

Edit:

ho trovato il codice con assembler porting a GAS (GNU toolchain). Questo codice è funzionante e collaudato:

Divide.S

.section ".text" 

.global udiv64 

udiv64: 
    adds  r0,r0,r0 
    adc  r1,r1,r1 

    .rept 31 
     cmp  r1,r2 
     subcs r1,r1,r2 
     adcs r0,r0,r0 
     adc  r1,r1,r1 
    .endr 

    cmp  r1,r2 
    subcs r1,r1,r2 
    adcs r0,r0,r0 

    bx  lr 

C-Code:

extern "C" uint32_t udiv64 (uint32_t a, uint32_t b, uint32_t c); 

int32_t fixdiv24 (int32_t a, int32_t b) 
/* calculate (a<<24)/b with 64 bit immediate result */ 
{ 
    int q; 
    int sign = (a^b) < 0; /* different signs */ 
    uint32_t l,h; 
    a = a<0 ? -a:a; 
    b = b<0 ? -b:b; 
    l = (a << 24); 
    h = (a >> 8); 
    q = udiv64 (l,h,b); 
    if (sign) q = -q; 
    return q; 
}