64bit/32bit Division schneller Algorithmus für ARM/NEON?

Question

Ich arbeite an einem Code, in dem an zwei Stellen gibt es 64-Bit-by-32-Bit-Fixpunkt-Division und das Ergebnis wird in 32 Bits genommen. Diese beiden Orte nehmen zusammen mehr als 20% meiner gesamten Zeit in Anspruch. Ich habe das Gefühl, wenn ich die 64-Bit-Division entfernen könnte, könnte ich den Code gut optimieren. In NEON können wir einige 64-Bit-Anweisungen haben. Kann irgendjemand eine Routine vorschlagen, um den Flaschenhals durch eine schnellere Implementierung zu beheben?

Oder wenn ich die 64-Bit/32-Bit-Division in Bezug auf 32-Bit/32-Bit-Division in C machen könnte, ist das auch in Ordnung?

Wenn jemand eine Idee hat, könnten Sie mir bitte helfen?

Answer 1

Ich habe in der Vergangenheit eine Menge Festkommaarithmetik gemacht und habe viel Forschung betrieben, um selbst nach schnellen 64/32 Bit Divisionen zu suchen. Wenn Sie nach 'ARM division' googlen, finden Sie Tonnen von großen Links und Diskussionen zu diesem Thema.

Die beste Lösung für ARM-Architektur, wo auch eine 32-Bit-Division nicht in Hardware verfügbar ist hier:

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

Dieser Assembler-Code sehr alt ist, und Ihr Assembler kann nicht verstehen, die Syntax davon. Es lohnt sich jedoch, den Code in Ihre Toolchain zu portieren. Es ist der schnellste Divisionscode für Ihren speziellen Fall, den ich bis jetzt gesehen habe, und vertraue mir: Ich habe sie alle bewertet :-)

Das letzte Mal habe ich das getan (vor etwa 5 Jahren, für CortexA8) diesen Code war ungefähr 10 Mal schneller als was der Compiler erzeugte.

Dieser Code verwendet nicht NEON. Ein NEON-Port wäre interessant. Nicht sicher, ob es die Leistung sehr verbessert.

Edit:

fand ich den Code mit Assembler zu GAS portiert (GNU Toolchain). Dieser Code funktioniert und getestet:

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; 
}