GNURZ - Arithmetik-Unit für große Zahlen

[mschnell]

Die GNURZ-Routinen sind so flexibel, dass sie mit beliebiger Zahlenbasis (Zehnersystem=10, Hexadezimalsystem=16, u.s.w.) rechnen können.

Ist das wirklich sinnvoll ?

Wenn in den Berechnungen immer wieder auf die Zahlenbasis Rücksicht genommen werden muss, kann das die Ausführung ganz erheblich verlangsamen.

Scheint er zu machen. Das würde demnach die lästige Arbeit mit Pointern ersparen

Sieht gut aus.

Übrigens ist die Addition ein sehr guter und einfach zu machender Kandidat für AS-Optimierung, (Wenn man von der Zahlenbasis-Geschichte absieht. Es muss ja jedesmal beim nächsten Wort der Übertrag vom vorigen einbezogen werden. Das macht ein entsprechender ASM Befehl hardwaremäßig. man braucht nur eine einzige Addition pro Wort.

(Ob das wirklich viel bringt ist allerdings eine andere Frage, weil es viel länger dauert, die Werte aus dem und ins RAM zu transportieren als die Berechnung. Hier hilft natürlich der Cache, das ist aber wiederum vom ganzen Programm abhängig.)

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.

-Michael

[Euklid]

Auf die "Zahlenbasis-Geschichte" kann ich verzichten, die benötige ich jetzt nicht mehr. Sie erfüllte ihren Zweck, als ich mir noch nicht sicher war, welchen Datentyp ich für das Array des GNZTyp verwende. Durch die Einführung der GlobBasis konnte ich den GNZTyp variieren und der Rest des Programms wurde durch einen einfachen Wechsel der GlobZahlenbasis daran angepasst.

Übrigens ist die Addition ein sehr guter und einfach zu machender Kandidat für AS-Optimierung, (Wenn man von der Zahlenbasis-Geschichte absieht. Es muss ja jedesmal beim nächsten Wort der Übertrag vom vorigen einbezogen werden. Das macht ein entsprechender ASM Befehl hardwaremäßig. man braucht nur eine einzige Addition pro Wort.

Gute Idee - nehme an, das funktioniert, indem eine Overflow-Flag gesetzt wird, die in Assembler abgefragt werden könnte. Gibt es Möglichkeiten, diese Flagge auch mit einem Pascal-Befehl abzufragen? Wäre natürich besonders praktisch.

Die Überlauf-Geschichte wird bisher recht aufwendig geregelt:

Code: Alles auswählen

for n:=0 to aAnz-1 do
    begin
      ZwSp:= ZwSp + a[n] + b[n];
      If ZwSp>=GNZ_GlobZahlenbasis then
      begin
        Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
        ZwSp:=1;
      end else
      begin
        Erg[n]:=ZwSp;
        ZwSp:=0;
      end;
    end; //for n:=0 to aAnz-1;

Durch Benutzung von Assembler würde nach deiner Ausführung die komplette if-Schleife wegfallen. Wäre also ein beträchtliche Optimierung, die mit kleinem Aufwand möglich wäre. Bei den CPU-Cache-Größen sowie den aktuellen Prefetching-Einheiten dürfte nach meiner Einschätzung der Speicherzugriff nicht bremsen.

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.

Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.

[mschnell]

Auf die "Zahlenbasis-Geschichte" kann ich verzichten, die benötige ich jetzt nicht mehr. Sie erfüllte ihren Zweck, als ich mir noch nicht sicher war, welchen Datentyp ich für das Array des GNZTyp verwende. Durch die Einführung der GlobBasis konnte ich den GNZTyp variieren und der Rest des Programms wurde durch einen einfachen Wechsel der GlobZahlenbasis daran angepasst.

Ich meine, es wäre sinnvoll als Zahlenbasis 32 Bit und 64 Bit vorzusehen. Allerdings nicht dynamisch wählbar, sondern als Compiler-Option (z.B. mit könnte mit einer {$if Abfrage "Type GNZBaseType=Integer;" bzw "Type GNZBaseType=Int64;" sowie einige notwendige Konstanten ausgewählt werden, die dann später verwendet werden und an entsprechenden Stellen nörigenfalls wieder wieder {$if Abfragen. Das sollte deutlich optimierten Code erzeugen

Gute Idee - nehme an, das funktioniert, indem eine Overflow-Flag gesetzt wird, die in Assembler abgefragt werden könnte. Gibt es Möglichkeiten, diese Flagge auch mit einem Pascal-Befehl abzufragen? Wäre natürich besonders praktisch.

Nein, in Pascal kann man das nicht anfragen. In ASM braucht man es nicht abfragen weil es einen "Addiere mit Carry"-Befehl gibt, der das automatisch ohne zusätzlichen Instruktionen tut. Übrigens "Abfragen" sollte man zur Geschwindigkeits-Optimierung möglichst vermeiden ! (Bedingte) Sprünge sind die langsamsten Prozessor-Befehle überhaupt.

Die Überlauf-Geschichte wird bisher recht aufwendig geregelt...

Das ist natürlich eine ziemliche Katastrophe für die Laufzeit Also sollten wir zunächst 'mal die Addition angehen . Ich versuche das 'mal, wenn Du eine Version mit statisch definierter Zahlenbasis (32 Bit und 64 Bit) hast.

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.

Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.

Dazu wird eine {$if - Compiler-Anweisung nötig sein. Vermutlich gibt es eine automatisch gesetzte option, wenn für 64 Bit übersetzt wird.

-Michael

[af0815]

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.

Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.

mit bedingter Kompilerung sollte es sinnvoll sein, für die Plattformen wo es möglich ist, zu optimieren bzw. die Routinen allgemein zu halten. Dort wo es erst mal möglich ist, das Maximum herauszuholen.

[mschnell]

Die Multiplikation ist ein ganz schöner brocken, da sie diverse Fallunterscheidungen macht.

Das hört sich ganz schlecht an ! Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen. Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter. Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?

Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

-Michael

[indianer-frank]

Das hört sich ganz schlecht an ! Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen. Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter.

Das ist ein ziemlich naiver Einwand: Eine Karatsuba-Multiplikation ist viele Größenordungen komplizierter als if-Abfragen, außerdem sind die vielen Setlength viel schlechter.

Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?
Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

Da gibt's nichts zu testen, es sei denn, Du zweifelst an der Realität. "Pennäler"-Multiplikation skaliert mit Länge^2, Karatsuba mit Länge^log2(3) = Länge^1.585. Es kann nur darum gehen, ob GNZ_Karazubagrenze ein wenig größer gemacht wird.

Frank

[Euklid]

Das hört sich ganz schlecht an !

Hinsichtlich der Addition ist es klar, dass der Übertrag in Hardware schneller geregelt werden kann als in Software, dies gilt gewiss auch für die Multiplikation - an dieser Stelle besteht, wie wir schon feststellten, Optimierungsbedarf.

In diesem Fall dienen die if-Abzweigungen der Optimierung des Codes, sie sind also durchaus sinnvoll. In sehr vielen Fällen ist die Geschwindigkeit einer Routine stärker von dem verwendeten Algorithmus abhängig denn von den Hardware-Optimierungen. Hinsichlich der Multiplikation ist z.B. die Schulmethode der schriftlichen Multiplikation für kleine Zahlen unschlagbar schnell. Da hier aber der Rechanaufwand quadratisch mit der Stellenanzahl zunimmt, wird sie für große Zahlen zu langsam. Daher verwendet die GNURZ-Artihmetik ab einer Stellenanzahl von 44 den sogenannten Karazuba-Algorithmus, der mit n^1,6 im Aufwand zunimmt. Dieser wiederum ist besonders für Zahlen mit ähnlicher Stellenanzahl effektiv, d.h. hier muss erneut eine Fallunterscheidung eingeführt werden.
Hier habe ich Messungen durchgeführt, die die Vorteile zeigten. Die Multiplikation zweier hunderttausendstelliger Zahlen wäre nicht im Hundertstelsekundenbereich möglich ohne Karazuba. Ohne Zweifel können weitere Optimierungen auf Hardware-Seite die Berechnung in den ein- bis zweistelligen Millisekundenbereich drücken.
Theoretisch gibt es für sehr große Zahlen eine Methode, die die schnelle Fourier-Transformation benutzt und welche schneller ist als der Karazuba-Algorithmus. Diese wurde noch nicht implementiert.

Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen.

Naja, bedingte Sprünge brauchen bei heutigen Prozessoren nicht mehr sonderlich viele Zyklen. Aber ich stimme dir zu, dass es dem Prozessor erschwert wird, parallel Befehle abzuarbeiten (was moderne Prozessoren tun), wenn der Code viele Sprünge enthält.

Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter.

Das ist wahr. Bei allen im Laden befindlichen Prozessoren und bei den meisten der aktuell verwendeten Prozessoren dürfte der Instructions-Cache die 64 KB überschreiten. Hier dürften die aktiven Teile des Multiplikationsalgorithmus reinpassen. Man muss bedenken, dass sich die Multiplikation z.B. _nach_ der Entscheidung, per Schulmethode zu multiplizieren, auf einen relativ kleinen iterativen Bereich beschränkt.

Probleme macht der Karazuba-Algorithmus insofern, da mir nur ein rekursiver Algorithmus bekannt ist. Ein iterativer Algorithmus wäre hier effektiver, ich konnte jedoch weder einen finden noch einen herleiten.

Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?

Ich bin mir nicht sicher, ob ich hier verstanden habe, was du meinst: Aber durch die Setzung der GlobZahlenbasis im Constructor Create wird mit 32bit-Werten pro Stelle gerechnet. Das gilt für alle Routinen.

Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

Zustimmung: Das wären ganz sicher lohnenswerte Optimierungen.



Viele Grüße, Euklid

[Euklid]

Hallo Frank,

außerdem sind die vielen Setlength viel schlechter.

Der verwendete Karazuba-Algorithmus ist in der Tat mit Setlength-Anweisungen durchsetzt. Das ist sehr ungünstig. Nur weiß ich nicht, wie ich ihn auf der Grundlage eines GNZTyps, der auf dynamische Arrays beruht, in dieser Hinsicht besser schreiben könnte. Zur Zeit ist jedes Setlength unabdingbar. Ein Ausweg würden statische Arrays ergeben, aber sind diese hier wirklich sinnvoll?
Denn: Der L1-Cache teilt sich, wie mschnell schon andeutete, hälftig in einen Cache für Prozessoranweisungen und hälfig in einen Daten-Cache auf. Bei der Verwendung statischer Arrays, die groß sein müssen um die Rechnung mit großen Zahlen zu ermöglichen, bezweifel ich, dass die da alle reinpassen. Die oben zitierte MPUnit verwendet statische Arrays [0..30000] vom Typ Cardinal. Wenn ich mich nicht verrechne, ist der Cache dadurch mit einer einzigen Zahl schon gefüllt, was möglicherweise stärker auf die Laufzeit auswirkt als die setlength, die für einen minimalen Speicherverbrauch sorgen.

Ev. gibt es einen Mittelweg?

"Pennäler"-Multiplikation skaliert mit Länge^2, Karatsuba mit Länge^log2(3) = Länge^1.585. Es kann nur darum gehen, ob GNZ_Karazubagrenze ein wenig größer gemacht wird.

Die Überlegung ist zwar gut, aber an der Karazubagrenze lässt sich leider nicht mehr viel schrauben. Der Wert GNZ_Karazubagrenze=44 stellte sich nach einen automatisierten Laufzeittest als optimal heraus.

Optimierungsmöglichkeiten in der Multiplikationsroutine sehe ich vor allem in einer Überprüfung der dortigen Funktionsaufrufe (ev. lässt sich durch Verwendung von inline ein Vorteil erzielen, aber die Routine ist generell schon sehr groß) sowie in einer von mschnell angeregten Regelung der Übertragsrechnung durch Verwendung von Assembler. Wenn Euch ein Weg einfällt, einige der setlength-Anweisungen rauszuschmeißen, wäre das natürlich auch gut.

Ich danke Euch für Eure Kommentare, die sich positiv auf die Arithmetik-Unit auswirken.


Viele Grüße, Euklid

[mschnell]

Karatsuba skaliert mit Länge^log2(3) = Länge^1.585.

Wenn das wirklich so ist, dass der Gesamt-Aufwand anders skaliert ist natürlich jede low-level-Optimierung erst auf dieser Basis sinnvoll.

Laut Wikipedia geht der der Algorithmus aber von "teuren" Multiplikationen aus. Das ist bei modernen Prozessoren nicht so. Abfragen und Sprünge dauern viel länger als Multiplikationen. Wenn nur die Multiplikationen, nicht aber die Gesamt-Anzahl der Durchläufe der innersten Schleifen entsprechend kleiner skaliert, wird es nichts nützen.

Wenn wir die Addition mit ASM-Übertrags-Optimierung haben, ist es kein Aufwand mehr eine Primitiv-Multiplikation zu schreiben, um einen Test zu machen.

-Michael

[mschnell]

In sehr vielen Fällen ist die Geschwindigkeit einer Routine stärker von dem verwendeten Algorithmus abhängig denn von den Hardware-Optimierungen.

Da hast Du absolut recht. Erst wenn man den optimalen High-Level Algorithmus verwendet, lohnt sich eine low-level-Optimierung. Ich vermute, der Karazuba benutzt intern wiederholt eine normale Multiplikation mit kürzeren Langzahlen, die wiederum durch low-Level Optimierung verbessert werden könnte.

Der primitiv-Algorithmus braucht für die n^2 Multiplikationen n^2 Schleifendurchläufe. Wenn Karazuba weniger Schleifendurchläufe benötigt, sollte man ihn natürlich verwenden.

Theoretisch gibt es für sehr große Zahlen eine Methode, die die schnelle Fourier-Transformation benutzt und welche schneller ist als der Karazuba-Algorithmus. Diese wurde noch nicht implementiert.

Verstehe ich nicht. Fourier-Transformation ist eine Sache von kontinuierlichen Größen (real- oder Komplex). Du willst diskrete (integer) Größen berechnen.

Naja, bedingte Sprünge brauchen bei heutigen Prozessoren nicht mehr sonderlich viele Zyklen. Aber ich stimme dir zu, dass es dem Prozessor erschwert wird, parallel Befehle abzuarbeiten (was moderne Prozessoren tun), wenn der Code viele Sprünge enthält.

Multiplikationen und Additionen brauchen meist (bis zu einer gewissen Sättigung) überhaupt keine Zyklen, weil sie im Hintergrund ausgeführt werden, während der Programm-Fluss weiterläuft.

Probleme macht der Karazuba-Algorithmus insofern, da mir nur ein rekursiver Algorithmus bekannt ist. Ein iterativer Algorithmus wäre hier effektiver, ich konnte jedoch weder einen finden noch einen herleiten.

Ich glaube nicht, dass ein nicht-rekursiver Algorithmus wesentlich effektiver sein muss, wenn der Rekursive gut geschrieben ist.

Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?

Ich bin mir nicht sicher, ob ich hier verstanden habe, was du meinst: Aber durch die Setzung der GlobZahlenbasis im Constructor Create wird mit 32bit-Werten pro Stelle gerechnet. Das gilt für alle Routinen.

Klar, für eine Assembler-Optimierung muss die Zahlenbasis der Register-Größe entsprechen: für ein 32-Bit Programm also 32 Bit, für ein 64-Bit-Programm 64 Bit. Variabel (vom Create zu setzen) darf sie auf keinen Fall sein.

Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

Zustimmung: Das wären ganz sicher lohnenswerte Optimierungen.

Wenn Du eine Variante der Komponente mit konstantem GlobZahlenbasis (=32, optional =64) hast, könnten wir das 'mal versuchen.

-Michael

[mschnell]

Nur weiß ich nicht, wie ich ihn auf der Grundlage eines GNZTyps, der auf dynamische Arrays beruht, in dieser Hinsicht besser schreiben könnte.

Anscheinend braucht der Algorithmus Zahlen unterschiedlicher "Länge".
Wenn Deine Lang-Zahlen Klasse wären, könnten sie ein dynamisches Array für die Daten-Wörter enthalten, dessen Größe beim Create gesetzt wird und eine Property "AktSize", die nach bedarf gesetzt werden kann und bestimmt, mit wie vielen Stellen gerechnet wird. Wenn Du keine Klasse machen willst, tut's natürlich auch ein Record. C-mäßig wäre es, im ersten Array-Element die effektive Länge zu halten, dann kann ein "normaler" Pointer Cardinal^ verwendet werden, um eine Langzahl anzusprechen.

Der Wert GNZ_Karazubagrenze=44 stellte sich nach einen automatisierten Laufzeittest als optimal heraus.

Wenn die primitive Multiplikation deutlich schneller wird, tritt bei Karazuba der Overhead durch die Code-Komplexität deutlicher zutage und die grenze wird sich nach oben verschieben.

Heißt GNZ_Karazubagrenze=44 bei GlobZahlenbasis=32 44+32 = 1408 Bit ?

-Michael

[indianer-frank]

Karatsuba skaliert mit Länge^log2(3) = Länge^1.585.

Wenn das wirklich so ist, dass der Gesamt-Aufwand anders skaliert ist natürlich jede low-level-Optimierung erst auf dieser Basis sinnvoll.

Ich denke, daß große Mißverständsnisse zu den Multiplikation da sind: Karatsuba beruht im wesentlichen darauf, daß eine Langzahlmultiplikationen von zwei Zahlen der Länge L auf drei Langzahlmultiplikationen der Länge L/2 zurückgeführt wird, das ganze rekursiv bis die Länge L/2^k unterhalb der Karatasubagrenze (GNZ_Karazubagrenze) ist. Darunter setzt "Pennäler"-Muliplikation ein, darunter die Prozessor-Multiplikation.

Wenn man die Karatasubaschleife optimiert, kann man GNZ_Karazubagrenze verkleinern, wenn man die "Pennäler"-Muliplikation optimiert (Stichwort Comba), wird man GNZ_Karazubagrenze vergößern.

Laut Wikipedia geht der der Algorithmus aber von "teuren" Multiplikationen aus. Das ist bei modernen Prozessoren nicht so. Abfragen und Sprünge dauern viel länger als Multiplikationen. Wenn nur die Multiplikationen, nicht aber die Gesamt-Anzahl der Durchläufe der innersten Schleifen entsprechend kleiner skaliert, wird es nichts nützen.

Da mißversteht Du schon wieder Multiplikationen. Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Frank

[mschnell]

Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Das ist nicht logisch, Der Algorithmus soll eine Langzahlen-Multiplikation bewerkstelligen, also kann man seine Effektivität nicht in Größenordnungen von Langzahlen-Multiplikation messen.

-Michael

[indianer-frank]

Wenn Deine Lang-Zahlen Klasse wären, könnten sie ein dynamisches Array für die Daten-Wörter enthalten, dessen Größe beim Create gesetzt wird und eine Property "AktSize", die nach bedarf gesetzt werden kann und bestimmt, mit wie vielen Stellen gerechnet wird. Wenn Du keine Klasse machen willst, tut's natürlich auch ein Record. C-mäßig wäre es, im ersten Array-Element die effektive Länge zu halten, dann kann ein "normaler" Pointer Cardinal^ verwendet werden, um eine Langzahl anzusprechen.

Womit wir dann bei der von EugenE beschriebenen MPArith-Unit sind, die entgegen der Angaben keine statischen Arrays verwenden, sondern genau das, was Du hier vorschlägst.

Frank

[indianer-frank]

Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Das ist nicht logisch, Der Algorithmus soll eine Langzahlen-Multiplikation bewerkstelligen, also kann man seine Effektivität nicht in Größenordnungen von Langzahlen-Multiplikation messen.

Will ja auch keiner, der Vergleich ist zu Langzahl-Additionen und Langzahl-Verschiebeoperationen.

Frank