Mathe: Kombination/Permutation - Optimierung?

[i_hasser]

Ich denke da wird nicht allzuviel mehr Speed bei rauskommen, weil die SIMD eher für viele wirklich parallele Operationen sind - also mal eben 16 Werte mit 5 multiplizieren, oder haufenweise Matrizen zu addieren...

Desswegen hab ich mich dann auch gegen SIMD entschieden (und statt dessen Pipelining verwendet bzw. den region check, der den Aufwand zur 2. Berechnung auf je nach Situation zwischen 0% und 12.5% reduziert... und das kann man noch ausbauen ). Im ersten Teil verhindert das pipelining jegliche Parallelisierung (per SIMD) und im 2. Teil ist einfach nichts mehr da was man parallelisieren könnte.

 

[PuckPoltergeist]

Original geschrieben von intel_hasser
Ich denke da wird nicht allzuviel mehr Speed bei rauskommen, weil die SIMD eher für viele wirklich parallele Operationen sind - also mal eben 16 Werte mit 5 multiplizieren, oder haufenweise Matrizen zu addieren...

Die innere Schleife läßt sich sehr schön parallelisieren. Bin gleich fertig, dann gibt es den Code. 8)

 

[i_hasser]

70ms sind zu unterbieten

Die innere Schleife hab ich mit dem region check auf max. 5313 Durchläufe (effektiv nur die Hälfte davon) reduziert, da brauchst du kein SIMD. Mit 24 oder 36 Regions lässt sich das auf praktisch 0 reduzieren, wenn man die Regions nicht linear sondern jeweils 1/2 durchcheckt kommt man in ca. 5 Tests auf die richtige Region - das macht dann bei 36 Regionen nur noch effektiv 590 Additionen, der K7 schafft ca. 4 davon parallel (ähnlich wie der K5), also sind das grob (bei sagen wir gigantischen 10 Takten pro Operation) 1500 Takte - grob 0.6ns. Ich glaub das kann man vernachlässigen

 

[PuckPoltergeist]

Original geschrieben von intel_hasser
70ms sind zu unterbieten

Ok, ich war in etwa beim doppelten (0.15s).

Der SSE-Code liefert im Moment falsche Werte (zu wenig Summen) und ist außerdem langsamer.

Hier mal der relevante Teil:

for(b=0;b<42504;b++){
	for(a=0;a<42504;a+=4){
		sx.l[0] = XH[a][0];
                sx.l[1] = XH[a+1][0];
                sx.l[2] = XH[a+2][0];
                sx.l[3] = XH[a+3][0];

                sy.l[0] = YH[b][0];
                sy.l[1] = YH[b][0];
                sy.l[2] = YH[b][0];
                sy.l[3] = YH[b][0];

                h.m = _mm_add_ps(sx.m, sy.m);

                if(h.l[3]>2000000){
			p+=4;
                } else {
			c = 0;
                        while (h.l[c]>2000000){
				c++;
                                p++;
			}
			break;
                }
	}
}

Ich habe nur noch keine Ahnung, wieso das weniger Summen werden.

 

[i_hasser]

Mit dem Region Check kannst du das ganze doch besser reduzieren

Den will ich irgendwann auch noch bei sumx implementieren, aber das bringt sicherlich nur wenig Mehrleistung... mir juckts schon wieder im Finger, aber ich darf jetzt mein dummes Referat machen

 

[Sargnagel]

Original geschrieben von intel_hasser
Jetzt bleiben eigentlich nur noch 2 Dinge zu tun:

1. In das Ergebnis müssen wir noch die Zahl der Variationen der jeweiligen Kombination einbeziehen, damit wir auf den selben Wert kommen wie du am Anfang (oder hast du nur die Kombis mit Wiederholung gesucht?)

Es wäre super, wenn Ihr das noch in die Berechnungen mit aufnehmen könntet und als zusätzliche Information ausgebt. D.h. die Zahl der Variationen einer jeden Kombination abzüglich der genau umgekehrten Anordnungen müßten noch mit verrechnet werden. Soll heißen: ohne Beachtung der Reihenfolge einer Variation.

Original geschrieben von intel_hasser

2. Das ganze nach Win32 portieren (per Cygwin oder Mingw32), eine nette Oberfläche schreiben und das Prog für 40€ verkaufen

Gute Idee. Zumindest sind die Algorithmen genial! Macht doch auf sourceforge.net ein Projekt auf.
CombVar-Library oder so ähnlich.

Original geschrieben von intel_hasser

Ach ja - 3. Den Algorithmus als geistiges Eigentum eintragen lassen (region check, pipelining und die Methode die Kombinationen zu finden)... mein Blick fiel gerade auf eine der Sigs...

Hehe ... dann noch die Patentbeschreibung schön allgemein halten und die Euronen sollten nur so fließen ...

 

[Sargnagel]

Original geschrieben von PuckPoltergeist
Der SSE-Code liefert im Moment falsche Werte (zu wenig Summen) und ist außerdem langsamer.

Ich hoffe, Du nutzt GCC 3.3.2 oder höher? Bei GCC 3.3.1 mit cygwin habe ich nur Probleme bei den SIMD-Instruktionen. Lauter Rechenfehler. Ist auch als offizieller Bug gelistet. Nur leider gab es seit ca. einem halben Jahr kein GCC Update mehr für cygwin.

Gute Nacht!

 

[PuckPoltergeist]

Original geschrieben von Sargnagel
Ich hoffe, Du nutzt GCC 3.3.2 oder höher? Bei GCC 3.3.1 mit cygwin habe ich nur Probleme bei den SIMD-Instruktionen. Lauter Rechenfehler. Ist auch als offizieller Bug gelistet. Nur leider gab es seit ca. einem halben Jahr kein GCC Update mehr für cygwin.

Gute Nacht!

gcc-Version 3.3.3 (Debian 20040320)

Es fehlen einfach Summen. Kann mir mal jemand verraten wo die hin sind?

 

[i_hasser]

Versuchs doch mal mit Mingw32

Ich hab mir schon eine recht gute Methode ausgedacht das zu implementieren, aber dafür müsste ich den Region Check abschaffen

Oder ich mach das auch per Region... hmm.... viel Aufwand, aber dafür müsste es gehen. Neben pipe_info würd ich für jede Kombi noch bei search_comb die Anzahl der möglichen Variationen speichern, und dabei gleich für zb. 8 Regionen die Summe der möglichen Variationen der jeweiligen Region mitspeichern.
Dürfte nicht allzuviel Geschwindigkeit kosten.

(vielleicht mach ich das aber gerade auch nicht, weil ich das Endergebniss nicht sehen möchte ... Algs sind schön, wenn sie denn auch wirklich funktionieren )

 

[PuckPoltergeist]

Also mit SSE ist er definitiv langsamer. Ich habe ihn jetzt mal alle Summen ausrechnen lassen:

mit SSE:
Teilsummen: 0.000000 Sekunden
Mergesort: 0.030000 Sekunden
relev. Summen: 14.810000 Sekunden
Gesamt: 14.840000 Sekunden

relevante Summen: 1806590016


ohne SSE:
Teilsummen: 0.000000 Sekunden
Mergesort: 0.030000 Sekunden
relev. Summen: 0.510000 Sekunden
Gesamt: 0.540000 Sekunden

relevante Summen: 1806590016


Das dürfte zum Teil an den Kopieraktionen liegen, um das Zeug zu vektorisieren, zum anderen gewinnt der Opteron durch vektorisierten Code nicht wirklich.

 

[Sargnagel]

Original geschrieben von PuckPoltergeist
Das dürfte zum Teil an den Kopieraktionen liegen, um das Zeug zu vektorisieren, zum anderen gewinnt der Opteron durch vektorisierten Code nicht wirklich.

Wahrscheinlich sind die SIMD-Instruktionen nur effektiv nutzbar, wenn mit den Vektoren mehrere Berechnungen durchgeführt werden. Dann sollten die Vektorladezeiten nicht mehr ins Gewicht fallen.
Irgendwo müßte doch geschrieben stehen, wieviele Zyklen so eine Ladeaktion dauert.