Ein bisschen InlineAssembler hilfe :)

[Medium]

Bei den 50% liegst du richtig. Weitere Kerne zu nutzen ist aber, wieder ein mal, nur möglich wenn du parallelisieren kannst, wie auch bei der Grafikkarte oder den SIMD Befehlssätzen. Ein einzelner Thread (den dein Programm derzeit wohl nur hat) kann nicht verteilt werden, und eine Aufgabe müsste in Teile zerlegt werden die gleichzeitig verarbeitet werden können. Im Idealfall in so viele Teile wie Cores vorhanden sind, und alle mit ca. gleicher Laufzeit. Dann kannst du Multicores super ausnutzen/lasten, nur ist das hier wie gesagt nicht so möglich. (Wenn man genau wüsste worum es geht, ließe sich evtl. ein zerteilbarer Algo finden, mit genau dem Source wird's jedenfalls nix.)

Genauer als Double (64 Bit) ist nur noch Extended (80 Bit) was native Typen angeht. Dennoch halte ich meine Sinn-Frage aufrecht ;)

Wenn du i übrigens als Int64 nimmst hast du die selbe Genauigkeit wie mit Double. Int64 kann maximal 2^64-1 genau darstellen (*) - ich bin mir fast sicher dass Double schon vorher ganzzahlige Sprünge bei großen Werten aufweist. An spätestens der selben Stelle dürfte dann auch die Division 1/N keine verlässlichen Ergebnisse mehr liefern - eher früher.

Eine zusätzliche if-Abfrage ist mindestens ein "comp" oder "fcomp+statusbits schaufeln" + einem jump mehr, was auf die geringe Menge Code sicherlich gut messbaren Einfluss haben dürfte.

(*) Delphis Int64 ist ja nun leider Vorzeichenbehaftet, so dass nur halb so viele positive Zahlen möglich sind. Ein UInt64 kennt Delphi nicht - zumindest nicht in den Win32 Varianten, bei .NET bin ich unsicher. Auch bin ich nicht auf dem Stand, ob und wie 64er Ints auf der FPU verarbeitet werden können.


Alles in allem ist das gesamte Vorhaben problematisch, und solange es keinen größeren Zusammenhang gibt in dem man das ganze evtl. anders angehen könnte, seine Sache auch kaum wert.


Edit: 4 Postings dazwischen, uiuiui ich werd alt und lahm :cry:


Edit2:

Zitat:

Zitat von NamenLozer

Bitte schlagt mich nicht, wenn ich jetzt mit meinem Halbwissen irgendwas falsches erzählt habe, aber ich glaube, das ist eifnach eine schlechte Idee. Und dein ursprüngliches Problem kriegst du auf diese Weise garantiert nicht gelöst.

Eigentlich war das alles :thumb:

[Apollonius]

Double ist 64 Bit groß, insofern muss dort aufgrund des Exponenten die Genauigkeit zwangsläufig unter der von Int64 liegen. Extended stellt 64 Bit für die Mantisse bereit, wenn ich mich nicht irre.

[himitsu]

UInt64 kennt Delphi schon, auch schon D7,
abe rleider gab es da ein Problem, so daß viele UInt64-Operationen auf die Int64-Proceduren übergeben wurde, statt auf die teilweise schon vorhandenen UInt64-Prozeduren.

Seit spätestens Delphi 2006 sollte es da aber keine/kaum noch Probleme mehr geben.


PS: was die "genauen" Ganzzahlen in den Fließkommatypen angeht.
siehe OH > signifikante Stellen
Single = 7-8
Double = 15-16
Extended = 19-20

und 19-20 Stellen haben übrigens auch Int64/UInt64 (nur das Extended nochmal 2 Byte größer ist)

[helgew]

ein kleiner Vorschlag:

wie oben gesagt, kann man auch mit integerarithmetik arbeiten, dann bietet es sich auch an, die Sprünge zu reduzieren, also zB. sechzehn mal die Operation (für n ... n+15) hinzuschreiben in der Hoffnung, dass sich durch pipelining noch etwas rausholen lässt. Auf die Schnelle konnte ich das jetzt nicht testen :/

Ach und noch etwas: dieses ständige
fstp
wait
ist der blanke Unfug. Ich würde alle Werte im Stack halten, wozu immer speichern und laden?

Man muss übrigens nicht ständig prüfen, man kann auch Testen, wann das oft besungene Kind in den Brunnen gefallen ist und dann die letzten Glieder wieder wegsubtrahieren. Eine Vorwärtsberechnung im 16er-Pack sieht dann so aus:

Delphi-Quellcode:

// init
fld [Ergebnisvariable] //  0
fld [const_1]          //  const = 1
fld [const_1]          //  n

// Schleifenanfang

fld st(1)              // st(0) = 1
fdiv st(0), st(1)      // st(0) = st(0) / n
faddp st(3), st(0)     // ergebnis = ergebnis + st(0), pop st(0)
fadd st(0) st(1)       // n = n + 1

fld st(1)              // st(0) = 1
fdiv st(0), st(1)      // st(0) = st(0) / n
faddp st(3), st(0)     // ergebnis = ergebnis + st(0), pop st(0)
fadd st(0) st(1)       // n = n + 1

fld st(1)              // st(0) = 1
fdiv st(0), st(1)      // st(0) = st(0) / n
faddp st(3), st(0)     // ergebnis = ergebnis + st(0), pop st(0)
fadd st(0) st(1)       // n = n + 1

fld st(1)              // st(0) = 1
fdiv st(0), st(1)      // st(0) = st(0) / n
faddp st(3), st(0)     // ergebnis = ergebnis + st(0), pop st(0)
fadd st(0) st(1)       // n = n + 1

// ... noch weitere 12x


// Abbruchtest und Schleifenende ... 

// end
FCOMPP                  // pop st(0) + st(1)
fstp [Ergebnisvariable] // save, pop

// überschüssige Glieder wieder wegsubtrahieren

// ...

Man arbeitet da zwar nicht ganz nach den Vorstellungen einer Stackmaschine... aber wer hat gefragt, ob es der FPU gefällt :cheers: Die Idee, viele Befehle untereinander zu schreiben reduziert den Schleifenoverhead

Befehlsreferenz

[Amateurprofi]

Der Threadersteller war mit dem Zeitbedarf des in #1 gezeigten Pascal-Codes unzufrieden, vermutete, daß ein Assembler-Code schneller sein könnte und bat um Hilfe bei der Umsetzung.
Einige der Kommentare animierten mich, dieses Thema aufzugreifen. Das Resultat findet ihr im Attachment.

Zitat:

Ich denke mal bei solch trivialen Operationen bringt es keinen Geschwindigkeitsvorteil, wenn man sie in Assembler umsetzt.

Zitat:

Das ließe sich zwar übersetzen, aber das würde wie schon gesagt eher keinen Geschwindigkeitsvorteil bringen.. eher das Gegenteil

Doch, gerade bei solch trivialen Operationen läßt sich durch einen guten Assembler-Code viel erreichen, es sei denn man sähe eine Verbesserung um 800-1000 % als "keinen Geschwindigkeitsvorteil" an.
Natürlich bringt es nicht viel, wenn man sich im Debug-Mode anschaut, was der Compiler aus dem Source-Code gemacht hat, dieses abtippt und dann als die optimierte Assembler-Version ansieht.

Zitat:

PS: wir hatten hier schon ein paar Mal, daß die hochoptimierten (Versuche von Menschen) ASM-Codes wesentlich langsamer oder wenigstens/zumindestens genauso schnell waren, wie die optimierten Delphi-Codes aus 'nem Pascal-Compiler.

Die waren dann aber nicht von mir.

Zitat:

600% + (Amd64 SSE3) müssten locker drin sein.

Und auch das ist noch pessimistisch.

Das anhängende Programm enthält 9 unterschiedliche Code-Versionen sowie die Möglichkeit diese bezüglich Performance zu testen. Ich glaube, daß die Oberfläche mehr oder weniger selbsterklärend ist, habe aber einen Hilfefile beigefügt, der mit der F1-Taste angezeigt wird. Es wird vorausgesetzt, daß SSE2 verfügbar ist.

Die Routinen:
1) "PAS_SC (SC=Single Core)
Das ist im Prinzip der vom Threadersteller vorgegebene Code. Diese Version ist nicht multicorefähig. Bei ihr kann nur der Zielwert vorgegeben werden und dieser muß integer sein.
2) "FPU_SC"
Das ist die Übersetzung in Assembler. Auch diese Routine ist nicht multicorefähig und auch hier kann nur der Zielwert vorgegeben werden, der allerdings auch eine Fließkommazahl sein darf.
3) "MMX_SC"
Ebenfalls eine nicht multicorefähige Assembler-Routine, die aber mit den jeweils unteren Hälften der XMM-Register arbeitet.
4-6) "PAS_A", "FPU_A", "MMX_A"
Das sind multicorefähige Versionen. Bei der XMM-Routine wird die volle Breite der XMM-Register genutzt.
7-9) "PAS_B", "FPU_B", "XMM_B"
Hier wurde der Vorschlag aus #24 aufgegriffen, nicht nach jeder Rechnung zu prüfen, ob die Abbruchbedingung erfüllt ist sondern z.B. nur alle 16 Mal zu prüfen. Das Ergebnis ist eher ernüchternd, weil so gut wir keine Verbesserung zu verzeichnen ist.

Die nachstehende Tabelle zeigt ermittelte Rechenzeiten (CPU Intel Core 2 Duo E8400 3.0 GHz) für die verschiedenen Routinen. Es zeigt sich, daß Verbesserungen der Performance um den Faktor 8 bis 10 erreicht werden. Bei einer Quad-Core CPU dürften die Verbesserung deutlich höher sein.

Code:

Zielwert   20       20      25     25
Cores       1        2       1      2
Zeit in    ms       ms       s      s
-------- ----     ----     ---    ---
PAS_SC   4420     -        649      -
FPU_SC   2160     -        306      -
XMM_SC   2270     -        325      -
PAS_A    4160     2130     661    330
FPU_A    2060     1130     298    150
XMM_A    985       547     135     68
PAS_B    4200     2170     612    308
FPU_B    2080     1090     299    151
XMM_B    968       547     136     68

[helgew]

Guten Abend Klaus,

vielen Dank für deine Mühe! Mein Vorschlag macht dann Sinn, wenn nur wenige Befehle pro Durchlauf ausgeführt werden müssen und der Übergang zwischen den Befehlen am Ende und am Anfang des Schleifenblocks ohne direkten Bezug auf die gleichen Register oder Speicherinhalte abläuft, zumindest sieht so meine Vorstellung von pipelining-Optimierung aus. Vielleicht kannst du mich ja diesbezüglich erleuchten :-)

[Medium]

Wie parallelisierst du den Algorithmus? (Hab grad kein Delphi-Parser zur Hand, und das Riesenprogramm war ohne Highlighting bei der Formatierung praktisch undurchschaubar :snowball:)

[Amateurprofi]

@helgew

Innerhalb der Schleife wird folgende Sequenz 16 Mal ausgeführt.
Es ist im Prinzip exakt die von dir vorgeschlagene Sequenz (die sich ja aus dem Problem fast zwingend ergibt)
War für mich auch überrraschend, daß das nichts bringt.

Code:

fld     st(2)     // st0=1
fdiv    st,st(1)  // st0=1/Divisor
faddp   st(4),st  // Summe=Summe+1/Divisor
fadd    st,st(2)  // Divisor=Divisor+1

noch mal zum Vergleich die Sequenz aus deinem Vorschlag

Code:

fld     st(1)         // st(0) = 1 
fdiv    st(0), st(1)  // st(0) = st(0) / n 
faddp   st(3), st(0)  // ergebnis = ergebnis + st(0), pop st(0) 
fadd    st(0), st(1)  // n = n + 1

[R2009]

Hi,

Auf 1/n=0 abzuchecken ist mathematisch Quatsch!
Da dieser Fall niemals eintreten kann solltest du auf kleine Werte checken.
1/n < epsilon. Wobei epsilon beliebig klein werden kann.

es gilt:
lim 1/n = 0
n->unendlich

Grüsse
Rainer

[Amateurprofi]

@Medium:

eigentlich ist das ganz simpel.
Aus dem Zielwert (Summe der Reihe) errechne ich die Anzahl der Elemente der Reihe, also die Anzahl der Durchläufe.
n = Trunc(Exp(Zielwert-0.57721566490153286))
Nehmen wir an ich will in zwei Threads rechnen, dann muß jeder Threat n div 2 Elemente addieren.
also:
h:=n div 2
Erster Threat rechnet 1/1 + 1/2 + ... + 1/h
Zweiter Thread rechnet 1/(h+1) + 1/(h+2) + ... + 1/n
Jeweils nach Ende eines Threads werden die Summen addiert.
Wenn alle Threads fertig sind, wird die Summe geprüft und es werden ggfs. noch Elemente addiert bzw. subtrahiert.