OpenASP

Division mit Konstanten

Während eine Integer-Multiplikation auf modernen Prozessoren in nur wenigen Zyklen berechnet werden kann, benötigt eine Integer-Division deutlich mehr Rechenzeit. In dieser Aufgabe werden wir sehen, wie sich eine Integer-Division mit einer Konstante effizienter durchführen lässt.

1. Schreiben Sie mit einem Editor Ihrer Wahl folgenden Code in die Datei div3.c:

   long div3(long n) {
     return n / 3;
   }
   

   Kompilieren Sie den Code anschließend mit folgendem Befehl und lassen Sie sich danach die Disassembly anzeigen:

   gcc -O2 -c -o div3.o dic3.c

   objdump -d -Mintel div3.o

   Anmerkung: Sie können hierzu auch den Compiler Explorer nutzen.

   Lösung

   0000000000000000 <div3>:
      0:   48 ba 56 55 55 55 55    movabs rdx,0x5555555555555556
      7:   55 55 55
      a:   48 89 f8                mov    rax,rdi
      d:   48 c1 ff 3f             sar    rdi,0x3f
     11:   48 f7 ea                imul   rdx
     14:   48 89 d0                mov    rax,rdx
     17:   48 29 f8                sub    rax,rdi
     1a:   c3                      ret
   

2. In der Disassembly werden Sie eine magische Zahl vorfinden. Versuchen Sie zu verstehen, woher diese Zahl kommt. (Hinweis: Multiplizieren Sie die Zahl mit 3.)

   Lösung

   $$\lfloor \frac{2^{64}+2}{3}\rfloor =5555555555555556_{(16)}$$

3. Betrachten Sie nun die Multiplikation mittels imul von n und der Konstante. Erinnern Sie sich, dass imul mit einem Operanden das Ergebnis in rax und rdx schreibt. Welches der beiden Ergebnisse wird verwendet? Schreiben Sie die Multiplikation als mathematische Formel auf und vereinfachen Sie diese.

   Lösung

   Es werden nur die oberen 64 Bits des Produktes (rdx) verwendet, was einer Abrundenden Division mit $2^{64}$ entspricht. $$\lfloor \frac{n\cdot \lfloor \frac{2^{64}+2}{3}\rfloor }{2^{64}}\rfloor =\lfloor \frac{n}{2^{64}}\cdot \frac{2^{64}+2}{3}\rfloor =\lfloor \frac{n}{3}+\frac{2n}{3\cdot 2^{64}}\rfloor$$

   Für hat der sogenannte Fehlerterm einen Wert kleiner als $\frac{1}{3}$. Somit ist das Ergebnis für positive Eingaben stets korrekt.

   Für negative Eingaben hingegen ist das Ergebnis nicht korrekt. Durch die Abrundung und den stets negativen Fehlerterm ist das Ergebnis immer um genau 1 niedriger, als es sein sollte:

   $$n=-5⇝\lfloor \frac{-5}{3}+\frac{2\cdot -5}{3\cdot 2^{64}}\rfloor =-2\ne -1$$ $$n=-6⇝\lfloor \frac{-6}{3}+\frac{2\cdot -6}{3\cdot 2^{64}}\rfloor =-3\ne -2$$

4. Sehen Sie sich nun die verbleibenden arithmetischen Bestandteile der Funktion an. Erkennen Sie, wie negative Zahlen behandelt werden?

   Lösung

   Bei negativen Eingaben muss, wie oben beschrieben, das Ergebnis stets um 1 erhöht werden. Die Instruktion sar rdi, 0x3f resultiert bei einer positiven Eingabe (Sign-Bit = 0) in dem Wert 0, bei einer negativen Eingabe (Sign-Bit = 1) hingegen in dem Wert -1. Durch Subtraktion von 0 bzw. -1 vom Ergebnis erhält man nun für alle möglichen Eingaben das korrekte Ergebnis.

5. Ändern Sie den Divisor in andere Zahlen, bspw. 2 oder 5. Probieren Sie außerdem, den Datentyp auf unsigned long zu verändern. Wie verändert sich der komplierte Code? Erkennen Sie einen Zusammenhang?

   Lösung

   Vorzeichenlose Divisionen benötigen keine Behandlung von negativen Zahlen, dafür aber mehr Logik (Shifts), um den Wert des Fehlerterms klein zu halten. Größere Divisoren führen zu anderen Konstanten, welche größere Zweier-Potenzen als 2⁶⁴ als Dividend verwenden.

   Eine detaillierte Beschreibung zur Konstruktion der Konstanten und des Divisionsalgorithmus für einen beliebigen Divisor findet sich in Warren, Henry S. Hacker’s Delight. Pearson Education, 2013, Kapitel 10.