(gelöst) Effizente Sum of Scaled Copies

[Krishty]

Hi,

Ist schon ironisch … eine FFT auf 2048² Daten geht fix wie nix, aber eine Sum of Scaled Copies mit 64 Samples auf 512² bringt meine GPU zum kochen. Kennt ihr einen schnellen Algorithmus, bzw ein Paper dafür?

(Bei einer Sum of Scaled Copies werden mehrere Kopien des Bildes jeweils leicht vergrößert übereinandergelegt. Quasi radialer Motion Blur.)

Ich habe mir schon überlegt, zwischen Start- und Endpunkt Bresenham-mäßig einzelne Samples abzuklappern (das würde bilineare Filterung und damit drei Viertel der Texture-Loads sparen), aber bevor ich das umsonst mache, wollte ich fremde Meinung einholen.

Gruß, Ky

[Schrompf]

Du machst pro 512^2er Fragment 64 Samples? Das sollte doch nichtmal im Profiler auftauchen... steckt da evtl. irgendwo ein Bug drin?

Crysis hat das als dreistufige Kaskade gemacht: zuerst 8 Samples auf extrem kurze Distanz, dann 8 Samples auf der vielfachen Distanz, dann nochmal 8 auf dem Vielfachen der vielfachen Distanz. Könnte bei Dir auch funktionieren, auch wenn der Unterschied ob der cache-untauglichen Zugriffsmuster kleiner als erhofft ausfallen dürfte.

[Krishty]

Bug ist möglich. Das passiert im Compute Shader, und es könnte durchaus sein, dass ich durch ungünstige Branches beim Berechnen der Texturkoordinaten (die brauche ich, weil meine FFT momentan noch um eine halbe Bildschirmbreite verschoben ist) versehentlich durchgehend die Pipeline stalle.

Der Dreistufenansatz klingt gut; ich muss jetzt nur schauen, ob ich ihn dicht genug kriege, dass er keinen Griesel bildet.

[Krishty]

Also, in einer Sache bin ich schonmal weiter: Über den Speicher hinauszulesen kostet unheimlich viel. Wenn ich eine 512×512-Textur in einem passend großen Fenster anzeige, komme ich auf 40 fps. Bei 1400×900 Pixeln – also 5/6 Leseoperationen über die Textur hinaus – sind es nur noch 2 fps. Ich werde also vor allem erstmal Lesen über den Rand hinaus vermeiden müssen.


Aktualisierung: Okay. Ich hatte den Betrag einer komplexen Zahl in der inneren Schleife der SSC – das bedeutete eine Wurzel und eine Division pro Durchlauf. Ich habe das auf eine frühere Stufe verlegt, so dass das für jeden Texel nur noch einmal ausgeführt wird, und die Framerate hat sich von zwei auf vier verdoppelt. Ich stöbere weiter nach Verbesserungen.


Und nocheiner: Auf den HLSL-Compiler komme ich absolut nicht klar. Das hier wird nicht abgerollt; 32 Anweisungen und 38 fps:

Code: Alles auswählen

const float2 vectorToMid = float2(swapCoordinateSystems(ItsPosition)) - 256.0f;
float3 glare = float3(0.0f, 0.0f, 0.0f);
for(float CurrentSamplesIndex = 0.0f; CurrentSamplesIndex < 1.0f; CurrentSamplesIndex += (1.0f / 32.0f)) {
	const float4 spectralColor = spectralTexture.SampleLevel(Bilinear, CurrentSamplesIndex, 0.0f);

	const float2 samplesPosition = vectorToMid * spectralColor.a;
	const uint2 position = samplesPosition + 256.0f;

	const float PSFIntensity = glareTexture[uint2(2, 1) * swapCoordinateSystems(position)];
	glare += PSFIntensity * spectralColor.rgb / (spectralColor.a * spectralColor.a) * float3(3.0f, 0.8f, 0.6f) / 32.0f;
}

Verschiebe ich jetzt position in den Aufruf von swapCoordinateSystems():

Code: Alles auswählen

const float2 vectorToMid = float2(swapCoordinateSystems(ItsPosition)) - 256.0f;
float3 glare = float3(0.0f, 0.0f, 0.0f);
for(float CurrentSamplesIndex = 0.0f; CurrentSamplesIndex < 1.0f; CurrentSamplesIndex += (1.0f / 32.0f)) {
	const float4 spectralColor = spectralTexture.SampleLevel(Bilinear, CurrentSamplesIndex, 0.0f);

	const float2 samplesPosition = vectorToMid * spectralColor.a;

	const float PSFIntensity = glareTexture[uint2(2, 1) * swapCoordinateSystems(samplesPosition + 256.0f)];

	glare += PSFIntensity * spectralColor.rgb / (spectralColor.a * spectralColor.a) * float3(3.0f, 0.8f, 0.6f) / 32.0f;
}

Nun wird die Schleife abgerollt; 423 Anweisungen und 36 fps. Wtf?! Nach was für Merkmalen unterscheidet das Mistding überhaupt? Alles mit unter fünf Zeilen wird abgerollt oder was?!


…: Einen Aufruf von clamp() aus der Schleife genommen, 14 statt vier fps. saturate() kostet nicht einen einzigen verdammten Takt, aber clamp() reißt alles in Stücke … klar …

[Schrompf]

Ok, zum Rest kann ich nicht viel sagen, aber eins ist klar: saturate ist kostenlos. Das ist wie abs() ein Access Modifier, den die Pipeline kostenlos beim Lesen der Operanden mitmacht. clamp() dagegen wird nach meinem Wissen als zwei CMPs implementiert, das kostet natürlich dann auch zwei Taktzyklen.

[hagbard]

Entschuldigung meine Ignoranz aber was macht das SwapCoordinateSystems überhaupt und für was wird das gebraucht? Für mich hört sich das sehr "verdächtig" an (als ob da immer sehr viel umherkopiert wird in jeden Schleifendurchlauf).

[Krishty]

Entschuldigung meine Ignoranz […]

Welche?

[…] aber was macht das SwapCoordinateSystems überhaupt und für was wird das gebraucht? Für mich hört sich das sehr "verdächtig" an (als ob da immer sehr viel umherkopiert wird in jeden Schleifendurchlauf).

Es teilt das Bild in vier Teile und fügt sie umgekehrt wieder zusammen. Das ist nötig, weil die Fourier-Transformationen ihren Koordinatenursprung in die Ecken verschoben ausgibt (siehe hier), ich für die Berechnung des Blurs aber den Koordinatenursprung in der Mitte brauche (nämlich wie hier, damit am Ende das rauskommt).

Code: Alles auswählen

uint2 swapCoordinateSystems(
	const uint2 position
) {
	uint2 result = position;
	if(result.x < 256)
		result.x += 256;
	else
		result.x -= 2562;
	if(result.y < 256)
		result.y += 256;
	else
		result.y -= 256;
	return result;
}

Das sind zwei Conditional Branches pro Koordinate, also 2×n Sprünge für n Kopien. Ich glaube mittlerweile auch, dass dort das Problem liegt (zumal die Koordinaten von uint nach float und wieder zurück konvertiert werden müssen) und arbeite an einer Version, die das nur einmal außerhalb der Schleife erledigt und damit bedeutend Pipeline-freundlicher sein dürfte. Ich kann mich nur gerade nicht aufraffen, die fertigzumachen und zu testen, weil ich es hasse, wenn mir so ein Kötteldetail die ganze Chose vermasselt …

[hagbard]

Ignorant da ich einfach ins blaue geraten habe ohne ganz zu verstehen für was du das übereinanderblenden überhaupt machst und ohne DirectX Kenntnisse ;)

Der gepostete Code war dann jetzt eher enttäuschend für mich bei Swap habe ich halt automatisch an Kopieroperationen gedacht...
Das sieht ja eigentlich harmlos aus.Das mit der Verschiebung der Fouriercoordinaten ist so eine Sache. Normalerweise sollte man das ignorieren da man die Sachen ja eh wieder zurücktransformiert. Ist nur ungünstig wenn zwei Matrizen in unterschiedlichen Formaten vorliegen. Vielleicht bringt es ja was den Kernel vor der Transformation so zu berechnen, dass er im Fourierbereich nicht verschoben werden brauch. Ich hab das aber nicht mehr im Kopf wie das ging. Aber wo ich es so recht überlege ein Multiplikation mit einen entsprechenden Cosinus im Nicht-Fourierbereich sollte genügen. Das setzt natürlich alles vorraus, dass der Kernel nur einmal berechnet wird für N Frames ansonsten bringt das nix.

Ps: All mein Wissen stammt eher aus den Audio-Bereich. Was Computergrafik angeht bin ich eher ein n00b. :D

[Alexander Kornrumpf]

Ich bin ein wenig verwirrt. Also soweit ich mich erinnere, haben wir es immer so gehandhabt, dass Frequenzraumbilder alle zyklisch sind mit einem durch die Zyklizität etwas seltsamen Koordinatensystem und Bildraumbilder halt "normal". In die Verlegenheit beide Typen von Bildern miteinander zu verrechnen kommt man doch quasi nie, sodass ich nicht verstehe, wieso zwei Koordinatensysteme gleichzeitig verwendet werden.

Ganz flüchtiges Googlen nach sum of scaled copies hat in erster Linie was über Faltungen ergeben, z.B.

Our goal is to show that the response (e.g., membrane potential fluctuation) of a shift-invariant linear system (e.g., passive neural membrane) can be written as a sum of scaled and shifted copies of the system’s impulse response function. [Und dann folgt die Herleitung einer Faltung]

Falls das jemand intuitiv kapieren will hab ich gerade das noch gefunden: http://graphics.stanford.edu/courses/cs ... ution.html siehe unter "An alternative way to think about convolution"

Mir drängt sich ein wenig der Verdacht auf dass das was du vor hast nicht wirklich sum of scaled copies hießt, denn gäbe es einen trivialen Weg das was du willst als Faltung auszudrücken, würdest du hier bestimmt nicht fragen.

Was ich gerade nicht so richtig durchdacht bekomme, ist das Skalierung in diesem Bildverarbeitungssinne (also eigentlich resize/resample), falls es das ist was du meintest, wie der Name resample ja schon sagt eigentlich eine Änderung der Abtastrate ist und damit irgendwie orthogonal zum Signal. Ich schau nachher eventuell nochmal in meine Unterlagen, ich hab echt schon zuviel vergessen.

[Krishty]

Okayokay, entschuldigt, wenn ich das so unklar formuliert habe …

Ich bekomme ein Bild. Keine komplexen Zahlen oder so, einfach ein Graustufenbild.

Und darauf möchte ich eine SSC realisieren. SSC bedeutet in diesem Fall nur: Radialer Blur, der aus dem Mittelpunkt rauskommt. Nicht per Fourier-Transformation oder so, sondern einfach indem man die Lesekoordinate skaliert, jeweils mit einer leicht anderen Farbe multipliziert (damit es wie gebrochenes Licht aussieht) und aufaddiert.

Die Fouriertransformation ist da nur reingerutscht, weil das Bild da herkommt und deshalb leider verschoben ist. Ich muss das Bild horizontal und vertikal je eine halbe Breite rotieren, damit der Mittelpunkt auch wirklich in der Mitte liegt. Und ich glaube, dass das die Chose so langsam macht.

[Alexander Kornrumpf]

Eigentlich sollte die inverse Fourier-Trafo die Verschiebung aber wieder beheben. Oder machst du deine Sum of Scaled Copies im Frequenzraum?

[Krishty]

Beides richtig. Es ist nur ein Bild, das ich blurren will. Und dort liegt der Koordinatenursprung sowohl bei 0,0 als auch bei 512,0, 0,512 und 512,512 – und so lässt sich natürlich kein anständiger Blur realisieren, darum muss ich bei jeder Lese- und Schreiboperation den Koordinatenursprung um 256,256 verschieben (so dass der Koordinatenursprung in der Mitte aller Texel liegt und ich die Koordinate vernünftig skalieren kann). Die Texel werden auch wie ein C-Array adressiert, nicht in Texturkoordinaten zwischen 0 und 1.

Mal zur Veranschaulichung: Diesen Blur will ich erreichen. (Eigentlich würde man von innen nach außen blurren; ich blurre von außen nach innen um out-of-Bounds-Zugriffe zu vermeiden. Das ist aber ein vernachlässigbares Detail, da man einfach die Reziproke des Skalierfaktors nimmt.)

blurdir.png (9.59 KiB) 2513 mal betrachtet

Um das zu tun, rotiere ich jede Koordinate 256 Pixel nach links/rechts und nach oben/unten (rotieren in dem Sinne, dass Koordinaten, die rechts verschwinden, links wieder auftauchen):

blurdir2.png (6.66 KiB) 2511 mal betrachtet

Das ist jetzt trivial. Dann wird dieselbe Operation nochmal ausgeführt und tadaaa, Mission succeeded. Nur habe ich leider an einer anderen Stelle einen Bottleneck und kann die Performance momentan nicht tunen.

[Krishty]

Die Koordinate nur einmal abzufragen und dann aus vier vordefinierten Schleifen auszuwählen war katastrophal langsam (doppelt so lange Ausführungszeit wie vorher). Ich habe nun die SSC-Berechnung in einen eigenen Shader ausgelagert (vorher war sie in einem Shader, der mit den Ergebnissen sofort eine Fourier-Transformation durchgeführt hat). Durch den eigenen SSC-Shader konnte ich von zeilen- zu blockweiser Verarbeitung wechseln, und da weniger und in mehr Threads gearbeitet wird kann die GPU die Stalls besser verstecken. Das Resultat ist 45 % bessere Performance.

Das untermauert meine schlimmste Befürchtung: Dass viele spezialisierte Shader, die nur auf einer oder zwei Texturen operieren, effizienter arbeiten als ein Großer, der sich die Daten aus vielen Quellen zusammensucht. Das Problem daran ist, dass sich der Bandbreitenbedarf stark vergrößert – während ein Über-Shader alle Zwischenergebnisse im Gruppenspeicher oder gar in den Registern behalten kann, müssen die kleinen Shader sie aus dem VRAM lesen und wieder zurückschreiben. Verträgt sich nicht mit meiner Speicherbandbreitenparanoia und könnte mir bei HD-Auflösungen die Beine brechen (im Fall der SSC ist der Bandbreitenbedarf eben um ein Drittel gestiegen).

Vielleicht bringt es ja was den Kernel vor der Transformation so zu berechnen, dass er im Fourierbereich nicht verschoben werden brauch. Ich hab das aber nicht mehr im Kopf wie das ging. Aber wo ich es so recht überlege ein Multiplikation mit einen entsprechenden Cosinus im Nicht-Fourierbereich sollte genügen. Das setzt natürlich alles vorraus, dass der Kernel nur einmal berechnet wird für N Frames ansonsten bringt das nix.

Mit einer verschobenen FFT könnte ich die SSC nicht nur schneller, sondern vor allem auch einfacher realisieren. Was verstehst du unter „Kernel“? Oder stützt du dich noch auf die (falsche) Annahme, ich würde die SSC per FFT berechnen?

Update: Ich habe die Blur-Textur im Shader hardgecodet; dadurch hat sich die Ausführungszeit halbiert. Wenn ich jetzt noch die FFT dazu kriegen könnte, den Nullpunkt in die Mitte zu legen, würde mir das nochmal eine Verdopplung bringen … erstmal muss ich mich aber um anderen Kram kümmern.

[hagbard]

Vielleicht bringt es ja was den Kernel vor der Transformation so zu berechnen, dass er im Fourierbereich nicht verschoben werden brauch. Ich hab das aber nicht mehr im Kopf wie das ging. Aber wo ich es so recht überlege ein Multiplikation mit einen entsprechenden Cosinus im Nicht-Fourierbereich sollte genügen. Das setzt natürlich alles vorraus, dass der Kernel nur einmal berechnet wird für N Frames ansonsten bringt das nix.

Mit einer verschobenen FFT könnte ich die SSC nicht nur schneller, sondern vor allem auch einfacher realisieren. Was verstehst du unter „Kernel“? Oder stützt du dich noch auf die (falsche) Annahme, ich würde die SSC per FFT berechnen?

Update: Ich habe die Blur-Textur im Shader hardgecodet; dadurch hat sich die Ausführungszeit halbiert. Wenn ich jetzt noch die FFT dazu kriegen könnte, den Nullpunkt in die Mitte zu legen, würde mir das nochmal eine Verdopplung bringen … erstmal muss ich mich aber um anderen Kram kümmern.

Mit "Kernel" meinte ich den Blur oder die PSF die du transformierst und mit den transformierten Bild multiplizierst. Ich habe zugegebenermaßen nicht jeden Schritt verstanden den du da tuest. Aber wenn man eine 2D-FFT berechnest ist es normal, dass du der Koordinatenursprung nicht in der Mitte liegt das bringt die FFT mit sich. Wenn nun alle Eingabedaten (PSF und Bild) mit der gleichen FFT berechnet werden sollte das keinen Unterschied machen. Aber vielleicht läuft dein Blur ja auch ganz anders ab als ich mir das vorstelle.

[Krishty]

Mit "Kernel" meinte ich den Blur oder die PSF die du transformierst und mit den transformierten Bild multiplizierst. […] Aber vielleicht läuft dein Blur ja auch ganz anders ab als ich mir das vorstelle.

Ja, leider tut er das – ich schreite die Koordinaten von Hand ab, anstatt eine FFT anzuwenden.

Ich habe zugegebenermaßen nicht jeden Schritt verstanden den du da tuest. Aber wenn man eine 2D-FFT berechnest ist es normal, dass du der Koordinatenursprung nicht in der Mitte liegt das bringt die FFT mit sich.

Echt? Ich sehe nämlich auf allen Beispielen immer den Ursprung mittig. Komme mir deshalb schon total seltsam vor :D

[Krishty]

Okay: Der Geschwindigkeitsverlust ist lokalisiert und zum Großteil beseitigt worden; die Leistung hat sich verachtfacht. Ich muss noch einiges bezüglich der DirectX-Spezifikation abklären und trage alle Ergebnisse nach, sobald sie feststehen.

[Alexander Kornrumpf]

Bin ja froh dass du überhaupt noch "lebst". Nach dem Abschied im Jammer Thread...