Schnelle Assembler Multiplikation

[Johannes (Gast)]

Man stelle sich eine Assemblersprache vor, die Addieren/Subtrahieren und 
Bit shiften kann, aber sonst keine mathematischen Operationen.
(Bedingte Sprünge, Zuweisungen, Unterprogramme natürlich schon)

Um zu multiplizieren, muss man Bits shiften und addieren,
z.B. Faktor 10

reg1 * 1010b -> reg2:

reg2 = 0
reg1 <<= 1
reg2 += reg1
reg1 <<= 2
reg2 += reg1

Bei vielen Bits im Multiplikator könnte man es mit einem Trick 
wesentlich schneller machen.
Normaler Algo:

reg1 * 0xf -> reg2:

reg2 = 0
reg2 += reg1
reg1 <<= 1
reg2 += reg1
reg1 <<= 1
reg2 += reg1
reg1 <<= 1
reg2 += reg1

Trick mit Subtraktion:

reg1 * 0xf -> reg2:

reg2 = 0
reg3 = reg1
reg3 <<= 4 // mit 16 multiplizieren
reg2 += reg3
reg2 -= reg1  // wieder 1 abziehen

Gibt es einen bekannten Algorithmus,
der dies bei beliebigien Faktoren feststellt,
wo man mit größeren Zahlen (z.B. nächstgrößere 2-er Potenz) 
multiplizert,
und dann wieder abziehen muss?

[Karl H. (kbuchegg)]

Johannes schrieb:

> Trick mit Subtraktion:
>

> reg1 * 0xf -> reg2:
> 
> reg2 = 0
> reg3 = reg1
> reg3 <<= 4 // mit 16 multiplizieren
> reg2 += reg3
> reg2 -= reg1  // wieder 1 abziehen
>

Du triffst hier aber eine Annahme. Nämlich die, das reg3 auch frei ist. 
Ist es das nicht, dann kommt da noch dazu

reg1 * 0xf -> reg2:
 
push reg3
reg2 = 0
reg3 = reg1
reg3 <<= 4 // mit 16 multiplizieren
reg2 += reg3
reg2 -= reg1  // wieder 1 abziehen
pop reg3

Ob das dann immer noch schneller ist, hängt unter anderem auch davon ab, 
welche Operation wieviele Taktzyklen benötigt.

Und genau da liegt auch die Antwort auf deine Frage:
>
> Gibt es einen bekannten Algorithmus,

Beide Varianten vom Compiler ausformulieren lassen, Takte abzählen und 
die schnellere nehmen.

Wobei das heutzutage mit den ganzen Caches und überlappenden Operationen 
alles andere als simpel ist.

[Yalu X. (yalu) (Moderator)]

Johannes schrieb:
> Gibt es einen bekannten Algorithmus,

Mir ist jedenfalls keiner bekannt, obwohl sich die Aufgabe ziemlich
interessant anhört.

Es geht also darum, eine variable Zahl möglichst effizient mit einem
vorgegebenen, konstanten Faktor zu multiplizieren, wobei nur Additionen,
Subtraktionen, Shift-Operationen und Zuweisungen zur Verfügung stehen.

Mathematisch könnte man das Problem folgendermaßen formulieren:

Gesucht ist die Darstellung einer gegebenen Zahl (nämlich des konstanten
Faktors) als Summe möglichst weniger Zweierpotenzen mit jeweils
positivem oder negativen Vorzeichen.

Dafür gibt es sicher einen recht einfachen Lösungsalgorithmus, auch wenn
mir spontan keiner einfallen will ;-)

Allerdings ist die Laufzeit eines optimalen Programms nur näherungsweise
eine monotone Funktion der Anzahl der benötigten Zweierpotenzen. Um die
Laufzeit perfekt zu optimieren, müssen weitere Aspekte berücksichtigt
werden:

- Sonderbehandlung der Zweierpotenz 2⁰

- Laufzeit der einzelnen Operationen, insbesondere die mögliche
  Abhängigkeit der Shift-Operation vom zweiten Operanden

- Anzahl der verfügbaren Register zur Speicherung und späteren
  Wiederverwendung von Zwischenergebnissen

Das macht den Algorithmus gleich sehr viel komplizierter. Wahrscheinlich
wird er auf eine Backtracking-Suche hinauslaufen.

[Karl H. (kbuchegg)]

Karl Heinz schrieb:

> Du triffst hier aber eine Annahme.

Eigentlich hast du 2 Annahmen getroffen.
Die Sache mit dem Register UND die Annahme, dass du um beliebig viele 
Bits in einem Rutsch schieben kannst. Manche Prozessoren können das, 
andere wieder nicht.

Mal angenommen, die CPU kann das nicht.
Ist

reg1 * 0xf -> reg2:
 
push reg3
reg2 = 0
reg3 = reg1
reg3 <<= 1
reg3 <<= 1
reg3 <<= 1
reg3 <<= 1
reg2 += reg3
reg2 -= reg1  // wieder 1 abziehen
pop reg3

immer noch schneller?

[Karl H. (kbuchegg)]

Beobachtung bzw. Annahme

Der Trick lohnt sich nur, wenn es eine Folge von 1 Bits der Länge n gibt 
(deren rechtestest das LSB ist, wobei ich aus dem Stegreif raus noch 
nicht sagen kann, ob das eine echt Einschränkung ist, oder ob man die 
los wird.)

Dann geht es doch darum, die Multiplikation mit einer derartigen Folge 
von n Stück 1 Bist derart abzuwägen, ob

  reg2 = reg1

  wiederhole n-1 mal {
    reg1 <<= 1
    reg2 += reg1
  }

weniger Instruktionen benötigt, als

  reg2 = reg1
  reg2 <<= n
  reg2 -= reg1

(unter der Annahme, dass alle Instruktionen gleich lang dauern bzw. die 
sonstigen Umstände ... bla, bla, bla))

Hmm. auf den ersten Blick scheint das bei 2 nebeeinander liegenden 1 
Bits bereits zielführend zu sein.

Jetzt erhebt sich 'nur noch' die Frage, wie verallgemeinert das, wenn 
die Folge von 1 Bits nicht beim LSB endet.

[Johannes (Gast)]

>Mathematisch könnte man das Problem folgendermaßen formulieren:
>
>Gesucht ist die Darstellung einer gegebenen Zahl (nämlich des konstanten
>Faktors) als Summe möglichst weniger Zweierpotenzen mit jeweils
>positivem oder negativen Vorzeichen

Ja. Ich würde zwar schreiben "Summe oder Differenz" statt "pos. oder 
neg. Vorzeichen", aber der Sinn bleibt gleich.
Sicherlich bieten Zahlen, wo in der Binärdarstellung viele 1-er 
aufeinandertreffen, große Vorteile.
Bei 3 oder mehr könnte der Trick Vorteile bringen.
Hat die Zahl mehrere solcher 1-er Kolonnen, kann der Algo schwieriger 
werden.





>Eigentlich hast du 2 Annahmen getroffen.
>Die Sache mit dem Register UND die Annahme, dass du um beliebig viele
>Bits in einem Rutsch schieben kannst.

1. Es sind viele Register frei (reg4 ... reg10)
2. man kann bis zu 31 Bits schieben. (Die register haben jeweils 32 
Bits)

[Arc N. (arc)]

Solche Algorithmen gibt es, aber das eigentliche Problem ist (mal 
wieder) NP-vollständig...
http://www.spiral.net/hardware/multless.html
"For a given constant c, the problem is to find a multiplier block with 
the least number of adds/subtracts. This problem and two extensions are 
visualized on the right. We have developed algorithms and online 
generators for each of the problems.

Finding an optimal solution for the these problems is NP complete [1]. 
Thus our algorithms find only a close-to-optimal solution."

[Vlad T. (vlad_tepesch)]

Benutzen Compiler (zb der avr-gcc) sowas eigentlich zur Optimierung von 
Multiplikationen mit konstanten Werten?
Das ersetzen von Multiplikationen mit 2er-Potenzen gehört ja zum 
Standard. Hier muss natürlich auch erücksichtigt werden, ob der 
Prozessor einen Barrelshifter hat, oder nicht. Das war iirc ja mal ein 
Problem beim avr-gcc, dass er multiplikation zu shift "optimiert" hat, 
auch wenn der AVR hardwaremäßig multiplizieren konnte..

[Johannes (Gast)]

Bei einem Faktor von 1011 1111 1001b funktioniert dieser Trick auch ganz 
schön:
(reg1 soll mit 0xbf9 multipliziert werden, der Einfachheit halber sei 
reg1=1)

reg1=1
reg1 <<= 11 // 0x800
reg2 = reg1
reg1 >>= 1
reg2 += reg1 // 0xC00
reg1 >>= 7
reg2 -= reg1 // 0xBF8
reg1 >>= 3
reg2 += reg1 // 0xBF9

[Johann L. (gjlayde)]

Johannes schrieb:
> Gibt es einen bekannten Algorithmus,

Jupp, schau z.B. in die GCC-Quellen.

Der macht das nämlich so; irgendwo in der Gegend von expmed.c.