PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Geschwindigkeit von Multiplikationen


aths
2004-09-24, 19:33:11
Wenn ein Single mit einem Integer multipliziert wird, geht das schneller wenn Single mit 2048 multipliziert wird, als z. B. mit 2047? (Optimiert die CPU das automatisch?)

Jazz
2004-09-24, 19:43:05
Es ist in beiden Fällen gleichlangsam, da der Integer auch in einen Singlewert umgewandelt wird. In beiden Fällen findet eine Floatingpointmultiplikation statt.

Wenn du wissen willst, ob die verwendete Bitlänge bei einer Integermultiplikation Einfluss auf die Geschindigkeit hat: Nein, da es zwar mit kürzeren Werten formell schneller geht, der Unterschied im Regelfall aber innerhalb eines Taktes liegt und das Ergebnis sowieso erst mit der neuen Taktflanke ins Register geschrieben wird.

Gruß,
Jazz

Trap
2004-09-24, 19:44:52
Die CPU nicht, aber der Compiler. Alle sinnvollen Compiler ersetzen Multiplikationen mit 2er-Potenzen durch Bitshifts.

Xmas
2004-09-24, 19:47:50
Die CPU nicht, aber der Compiler. Alle sinnvollen Compiler ersetzen Multiplikationen mit 2er-Potenzen durch Bitshifts.
Aber nicht bei FP-Multiplikationen.

Trap
2004-09-24, 20:00:36
Ups, hab statt Single short gelesen...

zeckensack
2004-09-24, 20:04:37
Es ist in beiden Fällen gleichlangsam, da der Integer auch in einen Singlewert umgewandelt wird. In beiden Fällen findet eine Floatingpointmultiplikation statt.Nein. x87 kennt FIMUL, wodurch die explizite Konversion nicht nötig ist.
Sinngemäß das gleiche ist auch bei vielen anderen FP-Operationen möglich.

Die CPU nicht, aber der Compiler. Alle sinnvollen Compiler ersetzen Multiplikationen mit 2er-Potenzen durch Bitshifts.Jawoll. Bei FPU-Operationen gibt es iÜ auch die FXSCALE-Operation, wodurch die volle Multiplikation durch eine vergleichsweise simple Addition auf dem Exponenten ersetzt werden kann.

Dieser Typus von Vereinfachung ist allerdings nur dann möglich, wenn schon beim Kompilieren der Wert des zweiten Operanden bekannt ist. Und es gibt leider auch Compiler, die dafür generell einfach zu dämlich sind.

aths
2004-09-24, 20:15:42
Dieser Typus von Vereinfachung ist allerdings nur dann möglich, wenn schon beim Kompilieren der Wert des zweiten Operanden bekannt ist. Und es gibt leider auch Compiler, die dafür generell einfach zu dämlich sind.Wenn ich das in Delphi einfach durchbenchen will habe ich das Gefühl, dass eine Schleife mit sehr vielen MULs vielleicht nichts bringt da er bei kleinen Schleifen vielleicht Ergebnisse halten und wiederverwenden kann?

Hintergrund des Problems ist, dass Bilder von RGB in HSL umgerechnet werden sollen. Die HSL-Werte liegen normalerweise zwischen 0 und 1. Da müsste zum Testen auf Abweichungen ständig mit float hantiert werden, aber aus Performancegründen würde ich das gerne mit Integer machen, so dass die HSL-Werte halt ein mal hochskaliert werden. Da auch viele Daten umgerechnet werden, könnte diese Skalierung vielleicht etwas schneller werden wenn um eine ganze Zweierpotenz skaliert wird, das war jedenfalls die eigentliche Frage.

Trap
2004-09-24, 20:53:47
Ist die Performance wirklich ein Problem? Du könntest mit Festkommazahlen rechnen, also statt mit dem Intervall [0,1] mit [0,2^32-1].

aths
2004-09-24, 21:09:31
Ist die Performance wirklich ein Problem?Wahrscheinlich wird es das. "In Echtzeit" ist in der Applikation die mir vorschwebt so einiges zu tun. Und es sollte auch auf älteren Läppis noch laufen.

Was die RGB->HSL-Konvertierung angeht, überlege ich auch eine Lookup-Tabelle. Wird aber groß werden (96 MB RAM.)

Du könntest mit Festkommazahlen rechnen, also statt mit dem Intervall [0,1] mit [0,2^32-1].Die Konvertierung ansich rechnet mit Single. Ich glaube nicht, dass man da mit Fixpoint-Arithmetik entscheidend was rausholt.

Gast
2004-09-24, 23:25:59
Wahrscheinlich wird es das. "In Echtzeit" ist in der Applikation die mir vorschwebt so einiges zu tun. Und es sollte auch auf älteren Läppis noch laufen.

Was die RGB->HSL-Konvertierung angeht, überlege ich auch eine Lookup-Tabelle. Wird aber groß werden (96 MB RAM.)

Die Konvertierung ansich rechnet mit Single. Ich glaube nicht, dass man da mit Fixpoint-Arithmetik entscheidend was rausholt.

96MB wären sicherlich wegen den cachemisses langsammer als die berechnungen.
ich benutze für die konvertierung ein paar LUTs, das schaut in etwa so aus
(für YCbCr)


Y = (LUT_YR[R] + LUT_YG[G] + LUT_YB[B])>>8;
Cb = ((LUT_CbR[R] + LUT_CbG[G] + LUT_CbB[B])>>8) + 128;
Cr = (((R<<7) + LUT_CrG[G] + LUT_CrB[B])>>8) + 128;

und es ist fixer als von int->float dann die muls und ->int. die tables passen auch locker in den 1stlvl-cache;)

MfG
micki

aths
2004-09-25, 01:47:23
96MB wären sicherlich wegen den cachemisses langsammer als die berechnungen.
ich benutze für die konvertierung ein paar LUTs, das schaut in etwa so aus
(für YCbCr)


Y = (LUT_YR[R] + LUT_YG[G] + LUT_YB[B])>>8;
Cb = ((LUT_CbR[R] + LUT_CbG[G] + LUT_CbB[B])>>8) + 128;
Cr = (((R<<7) + LUT_CrG[G] + LUT_CrB[B])>>8) + 128;

und es ist fixer als von int->float dann die muls und ->int. die tables passen auch locker in den 1stlvl-cache;)

MfG
mickiSieht nach YUV aus. Das ist nicht der gewünschte Farbraum.

Jazz
2004-09-25, 09:25:06
Nein. x87 kennt FIMUL, wodurch die explizite Konversion nicht nötig ist.
Sinngemäß das gleiche ist auch bei vielen anderen FP-Operationen möglich.
Den Befehl gibts, aber die Konvertierung muss trotzdem durchgeführt werden. Das geschieht jetzt bloß im Prozessor und nicht mehr von Hand (bzw. Compiler). Der Befehl selber ist sogar langsamer als FMUL, was aber von der Konvertierung kommt. Insgesamt wirds minimal schneller sein, aber immer noch langsam im Vergleich zur reinen Integermultiplikation.

Coda
2004-09-25, 09:47:31
Öhm, wie wär's eigentlich mit SIMD?

Gast
2004-09-25, 11:55:44
Sieht nach YUV aus. Das ist nicht der gewünschte Farbraum.
*lol*
Hoffentlich bist du aufgrund der Variablennamen nicht entmutigt es trotzdem mal auf diese Weise zu versuchen.

btw. Beispiele haben oft nicht das Aussehen der Lösung, wäre ja sonst zu einfach.

MfG
micki

Coda
2004-09-25, 14:16:04
wtf micki?
Y, Cb, Cr ist definitiv nicht HSL, das sind die Standardbezeichnungen für YUV Farben.

@aths: Ein 96mb großer LUT ist sehr sehr wahrscheinlich langsamer als die Berechnungen zu machen.
Wie gesagt, probier's mal mit SSE, das dürfte da ziemlich helfen.

aths
2004-09-25, 14:18:51
*lol*
Hoffentlich bist du aufgrund der Variablennamen nicht entmutigt es trotzdem mal auf diese Weise zu versuchen.

btw. Beispiele haben oft nicht das Aussehen der Lösung, wäre ja sonst zu einfach.

MfG
mickiIch will nach HSL konvertieren, nicht nach YUV. Das Problem verlangt nach Farbton, Sättigung, Helligkeit und nicht Helligkeit, Rotdifferenz, Blaudifferenz.

Öhm, wie wär's eigentlich mit SIMD?Krieg ich nicht hin.

Trap
2004-09-25, 15:38:22
Wie schnell ist dein Konvertierungs-Algorithmus im Moment? Ich hab hier auf meinem P3-1,2 GHz mit einer einfachen Implementierung 4MPixel/s.

Welche Wertebereiche und Datentypen hast du und welche willst du bekommen?

zeckensack
2004-09-25, 18:07:26
Da auch viele Daten umgerechnet werden, könnte diese Skalierung vielleicht etwas schneller werden wenn um eine ganze Zweierpotenz skaliert wird, das war jedenfalls die eigentliche Frage.Ja, es geht schneller wenn du mit einer Zweierpotenz multiplizierst, und diese Zweierpotenz schon als Konstante im Code steht. Der Compiler muss es aber auch schneller machen wollen ;)

Den Befehl gibts, aber die Konvertierung muss trotzdem durchgeführt werden. Das geschieht jetzt bloß im Prozessor und nicht mehr von Hand (bzw. Compiler). Der Befehl selber ist sogar langsamer als FMUL, was aber von der Konvertierung kommt. Insgesamt wirds minimal schneller sein, aber immer noch langsam im Vergleich zur reinen Integermultiplikation.Im Vergleich zur Integermultiplikation ist's natürlich langsamer.
Ich "mag" FIMUL und Konsorten, weil man dadurch zumindest ein ISA-Register spart (das ist gerade auf dem doofen FPU-Stack ein Gewinn) und der Code kompakter wird.

Zur Performance:
1)K7
FIMUL: 9 Takte Latenz
FILD: 4 Takte Latenz
FMUL: 4 Takte Latenz

=>FIMUL ist langsamer als FILD+FMUL.

2)K8
FIMUL: 11 Takte Latenz
FILD: 6 Takte Latenz
FMUL: 6 Takte Latenz

=>FIMUL ist schneller als FILD+FMUL.

Zu Intel-Prozessoren habe ich leider keine passenden Informationen gefunden ;(

Coda
2004-09-25, 18:19:20
Ich wusste gar nicht, dass beim K8 die Latenzen so zugenommen haben

zeckensack
2004-09-25, 18:55:48
Ich wusste gar nicht, dass beim K8 die Latenzen so zugenommen habenDie Ausführungszeiten auf dem K8 stehen hier (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF) (PDF) in Anhang C. Für den K7 hier (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf) in Anhang F :)

Coda
2004-09-25, 21:57:10
Ich kenne die Dokumente, aber ich hab sie nie verglichen.