gpu-nutzung für rechenintensiven code

[hustbaer]

Also was Speicherzugriffe angeht sind eigentlich nur Cache-Misses interessant.
Ob man dann einen Wert den man gerade eben gelesen/geschrieben hat nun nochmal angreift ist dabei egal - was im L1 Cache steht ist "sofort" da, was im L2 Cache steht ist "ziemlich flott" da. L1 Cache vs. Register ist von der Zugriffsgeschwindigkeit ziemlich egal.

Guck mal im Google nach "cache aware", da gibts etliche Artikel drüber.

Ich denke das wichtigste ist dass du den Algorithmus so hinbringst dass er mit möglichst wenig Cache Misses läuft. Optimal ist wenn die meiste Arbeit auf kleinen Speicherblöcken durchgeführt werden kann, und dass grössere Blöcke möglichst linear durchgegangen werden. Unkontrolliert im Speicher rumspringen ist so ziemlich das schlimmste was du machen kannst.

Ein paar einfache Dinge die daraus folgen sind z.B. dass Arrays "gut" sind, dass "divide & conquer" auch "gut" ist, dass Listen "böse" sind, dass Pointer allgemein "böse" sind... Also viel mit Value-Semantics arbeiten, wenig mit Pointern etc.

[rapso]

tenim schrieb:

durch die bitvariante ist das array jetzt nur noch 502,39kb gross (vorher ca. 4019).

ja, da hatte ich echt ne gute idee

das wäre mit anfwand möglich. allerdings denke ich, das es auch nichts bringt, weil ja anstatt der n zugriffe auf die arrayelemente ein n-facher zugriff auf die puffervariable mit dem jeweils zuletzt gelesenen array-element erfolgt.

wenn du es schlau anstellst, liegt diese variable im register und das ist der zweite grund weshalb man mehrere bits in eine 32bit variable steckt

Also was Speicherzugriffe angeht sind eigentlich nur Cache-Misses interessant.
Ob man dann einen Wert den man gerade eben gelesen/geschrieben hat nun nochmal angreift ist dabei egal - was im L1 Cache steht ist "sofort" da, was im L2 Cache steht ist "ziemlich flott" da. L1 Cache vs. Register ist von der Zugriffsgeschwindigkeit ziemlich egal.

nein, es haengt zwar von der cpu ab, aber variablen im L1 haben ebenfalls eine zugrifszeit die um einiges ueber der eines registers liegt (in das auch erstmal geladen wird).
wobei CPUs vieles davon mit virtuellen registern verdecken (ein P4 soll angaeblich ueber 200 register intern haben).

[tenim]

ja, da hatte ich echt ne gute idee

nein, der code war danach ja langsamer.

wenn du es schlau anstellst, liegt diese variable im register und das ist der zweite grund weshalb man mehrere bits in eine 32bit variable steckt

es kann mir keiner garantieren, das er variable "n" in ein register steckt. also ist es auch kein zweiter grund.

sorry

[Jester]

tenim schrieb:

wenn du es schlau anstellst, liegt diese variable im register und das ist der zweite grund weshalb man mehrere bits in eine 32bit variable steckt

es kann mir keiner garantieren, das er variable "n" in ein register steckt. also ist es auch kein zweiter grund.

Garantiert vielleicht nicht. Aber doch ziemlich sicher. Zumindest gibt das dem Compiler die Chance eine solche Optimierung überhaupt durchzuführen.

[tenim]

ich hab ja den verdacht, das er das ganze array sowiso schon im l2-cache hat.
und demendsprechend dumm würde ich mir dann vorkommen, wenn nach umschreiben auf assembler der speedgewinn +-0 ist.

[Jester]

Was hat das damit zu tun?

[tenim]

es ging in den letzten posts doch darum, das ich durch weiteres umschreiben meines programms in richtung zitat:

Geht das nicht das du ein Integer ausliest (32bit), dann diese 32 Bits prüfst, und dann den nächsten Integer ausliest? So würde man Speicherzugriffe drastisch reduzieren.

die laufzeit verbessern könnte und meine zweifel daran aufgrund der problematik "variable in register". und um 100%ig sicherzustellen, das er die variable in ein register packt, müsste ich das programm in assember umschreiben. und weil ich eben den verdacht habe, das sowiso schon alles im cache abläuft, äußerte ich meine sorge über die viele nutzlose arbeit darüber wenn es dann doch nicht schneller ist.

[Jester]

Lass das mal ein Problem des Compilers sein. Du kannst Dir ziemlich sicher sein, dass die im Register landet. Da mit asm dranzugehen lohnt sich ziemlich sicher nicht. Ne Hochsprache reicht da vollkommen.

[rapso]

tenim schrieb:

ja, da hatte ich echt ne gute idee

nein, der code war danach ja langsamer.

dann hast du es eventuell falsch implementiert oder dein cache ist zu klein.

//falsch
for...
  if(Array[i>>5]&(1<<(i&0x1f))

//richtig
for...
register uint32_t Tmp=Array[i>>5];
 for(j=0;j<32;j++)
  if(Tmp&(1<<j)

man koennte zwar meinen dass das erste wegoptimiert werden koennte, aber heutzutage haben sich die compiler echt bitchy mit aliasing.

wenn du den zweiten loop ausschreibst koennte das auch was bringen.

wenn du es schlau anstellst, liegt diese variable im register und das ist der zweite grund weshalb man mehrere bits in eine 32bit variable steckt

es kann mir keiner garantieren, das er variable "n" in ein register steckt. also ist es auch kein zweiter grund.

solange du dir das ganze nicht im profiler anschaust ist eh jede optimierung nur ein schuss ins blaue.

[tenim]

das problem ist, das ich den array-inhalt nicht am stück auf werte testen kann, sondern das sich die werte in fragmenten im array befinden. der grund ist der, daß das array den inhalt eines "holzkastens (175x157x147)" darstellt und rechteckige objekte aufnimmt. wenn ein objekt reinkommt, muss ich das über 3 schleifen machen um den jeweils richtigen startoffset zum einfügen zu finden.
der wichtige teil (x,y,z sind die länge, breite und höhe des einzusetzenden steines, setzposition ist die nächste freie position nach dem schema: von links unten beginnen und reihenweise füllen):

// stein einsetzen
	for (ze=0;ze<z;ze++)
		for (ye=0;ye<y;ye++)
			for (xe=0;xe<x;xe++)
			{
				position=*setzposition+(ze*27808)+(ye*176)+xe;
				// prüfen, ob an der einfügeposition schon "holz" ist
				if ( kasten[position] != 0 )
				{
					// alle bisher eingefügten teile des steins wieder entfernen
					positionBackup=position;

					for (ze=0;ze<z;ze++)
						for (ye=0;ye<y;ye++)
							for (xe=0;xe<x;xe++)
							{
					            position=*setzposition+(ze*27808)+(ye*176)+xe;
								if ( position==positionBackup ) return 0;
								kasten[position]=0;
							}
				}

    			kasten[position]=1;
			}

    //---die nächste freie setzposition ermitteln---
	for(i=*setzposition;i<4115584;i++)
		if ( kasten[i] == 0 )
		{
			*setzposition=i;
			break;
		}
	//----------------------------------------------

obiger code ist meine alte byte-variante, und die ist 12 sekunden schneller(es wurden die ersten paar millionen iterationen durchlaufen) als die neue bit-variante:

// stein einsetzen
	for (ze=0;ze<z;ze++)
		for (ye=0;ye<y;ye++)
			for (xe=0;xe<x;xe++)
			{
				position=*setzposition+(ze*27808)+(ye*176)+xe;
				// die genaue bitposition ermitteln
				dwordNr=position/32;
				bitNr=position-(dwordNr*32);

				// prüfen, ob an der einfügeposition schon "holz" ist
				if ( (kasten[dwordNr] & (eins<<bitNr)) !=0 )
				{
					// alle bisher eingefügten teile des steins wieder entfernen
					positionBackup=position;

					for (ze=0;ze<z;ze++)
						for (ye=0;ye<y;ye++)
							for (xe=0;xe<x;xe++)
							{
					            position=*setzposition+(ze*27808)+(ye*176)+xe;
								if ( position==positionBackup ) return 0;

                                // die genaue bitposition ermitteln
								dwordNr=position/32;
								bitNr=position-(dwordNr*32);
								kasten[dwordNr]=kasten[dwordNr] & ~(eins<<bitNr);  // inhalt des kastens ist leer (0)
							}
				}

    			kasten[dwordNr]=kasten[dwordNr] | (eins<<bitNr);
			}

    //---die nächste freie setzposition ermitteln---
	for(i=*setzposition;i<4115584;i++)
	{
        // die genaue bitposition ermitteln
		dwordNr=i/32;
		bitNr=i-(dwordNr*32);

		if ( (kasten[dwordNr] & (eins<<bitNr)) ==0 )
		{
			*setzposition=i;
			break;
		}
	}
	//----------------------------------------------

wenn ich jetzt die bits noch in 32bit-häppchen prüfe, wird alles durch die zusätzliche kontroll-logik noch langsamer.

[rapso]

dein code ist ein wenig unoptimal vom algorithmus her.

1. du pruefst immer byte-weise und setzt gleich den wert. falls da doch etwas nicht frei ist, loescht du wieder alles, das mag eventuell gut laufen wenn noch viel frei ist, aber sobald dein raum ein wenig dichter bepackt ist, ist das unperformant weil:
- du hast im innerste loop ein IF und zudem ein RETURN, das kann die pipeline sehr zerschiessen
- du schreibst oft in die bytes, was schon vorher drinnen stand, naemlich 0. das weiss der cache aber nicht, fuer den sind es neue zahlen, falls eine speicherbank im cache also neue werte cachen soll, muessen die alten zuerueckgeschrieben werden was zeitverschwendung ist. wenn du erst garnicht reinschreiben wuerdest, waer dieses aufwendige arbeit erstmal erspart.
- du reihst deine volumes scheinbar sehr eng aneinander damit es effizient ist, die wahrscheinlichkeit dass mitten im volume ein byte gesetzt ist, geht gegen 0

2. du nutzt die vorteile garnicht aus die dir ein gepacktes byte gibt.

mein vorschlag:
1. such erst die freie stelle, fuelle sie dann erst mit werten wenn du sie gefunden hast
2. pruefe erst die kanten (also die linien zwischen den eckpunkten), pruefe dann die seitenflaechen, pruefe nicht das volumen (fuellen musst es weiterhin falls du ein einfuegeposition findest!)
3. rechne dir die laenge der seiten in bytes um und nutze das dann aus, also

kasten[dwordNr>>3]==255 -> return 0
kasten[dwordNr>>3]!=0 -> pruefe bitweise
(ansonsten ist kasten[dwordNr>>3]==0 -> kannst naechste 8 voxel testen

diese highlevel optimierungen sollten dir x mal mehr performance bringen als deine bruteforce methode auf heutigen GPUs je schaffen kann.

(btw. das sind vorschlaege, kein flame )

[tenim]

du schreibst oft in die bytes, was schon vorher drinnen stand, naemlich 0

nein, das kommt nie vor. ich fange mit dem einfügen eines objektes immer an der nächsten freien einfügeposition an. am anfang ist das x=0,y=0,z=0 (linke untere kastnecke). dann fülle ich die leeren kastenpositionen (0) mit 1. wenn rauskommt, das an der nächsten einfügeposition schon eine 1 ist, liegt dort schon ein teil eines anderen objektes und dann entferne ich alle bisher eingefügten punkte des akteullen objektes. ich überschreibe dann wieder die bisher eingefügten einser mit 0, aber niemals 0 mit 0.

such erst die freie stelle, fuelle sie dann erst mit werten wenn du sie gefunden hast

das mache ich ja schon. am anfang ist die erste einfügeposition wie oben beschrieben 0,0,0. wenn ich ein objekt eingefügt hab, ermittle ich gleich danach die nächste freie position. die ist immer rechts neben der alten und liegt auf der x-ebene, wenn dort nichts mehr frei ist, versuche ich in der nächsten reihe an der tiefsten y-position den stein einzufügen. ich fülle praktisch erst eine ebene komplett, bevor ich zur nächsten gehe.

es ist ein holzpuzzle, in dem 23 steine so eingefügt werden müssen, das sie mit der oberkante des kastens bündig abschliessen. es gibt keine hohlräume und meines wissens nach nur eine lösung.
deshalb gibt es eine reihenfolge der 23 steine, in der man diese in den kasten einräumt um das puzzle zu lösen.

das teil ist es:
http://home.comcast.net/~billcutler/stock/boxedbox-dv.html

ich hab zwar eine lösung(kein programm, durch knobeln gelösst) im internet gefunden, will das teil aber auch selbst durchrechnen. ein anderes holzpuzzle nach demselben schema rechnet er in 4s durch.

[rapso]

tenim schrieb:

du schreibst oft in die bytes, was schon vorher drinnen stand, naemlich 0

nein, das kommt nie vor.

doch da schreibst du es selbst:

dann fülle ich die leeren kastenpositionen (0) mit 1. ...ich überschreibe dann wieder die bisher eingefügten einser mit 0,

also steht im cache am fang 0 und beim zurueckschreiben 0, auf jedenfalls ist diese arbeit totale zeitvergoldung.

such erst die freie stelle, fuelle sie dann erst mit werten wenn du sie gefunden hast

das mache ich ja schon.

nein, du weisst noch nicht ob ein objekt passen kann und schreibst schon unmengen von daten nur um sie gleich danach wieder mit 0 zu fuellen.
such erst einen freien raum und wenn du ihn hast, erst dann fuelle ihn mit einsen.

[tenim]

irgentwie reden wir aneinander vorbei.

also steht im cache am fang 0 und beim zurueckschreiben 0, auf jedenfalls ist diese arbeit totale zeitvergoldung.

nein, BEIM zurückschreiben steht noch eine 1 drin, NACH dem zurückschreiben wieder 0. aber das kann man vorher nicht wissen und auch nicht verhindern.
ich brauche die 1ser ja zum testen des nächsten einzufügenden steines auf kollisionen mit den vorigen.

nein, du weisst noch nicht ob ein objekt passen kann und schreibst schon unmengen von daten nur um sie gleich danach wieder mit 0 zu fuellen.

das stimmt teilweise. ich weiss vorher nicht, ob ein objekt in die nächste freie einfügeposition passt. aber es MUSS in diese nächste freie position passen, wenn die aktuelle steinkombination die richtige/gesuchte ist. wenn nicht, wird der teil des suchbaums verworfen und ich probiere die nächste variante mit einem anderen stein.

such erst einen freien raum und wenn du ihn hast, erst dann fuelle ihn mit einsen.

das wäre von der performance tödlich, würde alles wahrscheinlich um den faktor 100 verlangsamen. durch die variante mit der nächsten einfügeposition habe ich immer ohne grosses rechnen die nächste stelle. und dort MUSS wie gesagt der nächste stein reinpassen, wenn es die gesuchte kombination/lösung ist.

[rapso]

tenim schrieb:

irgentwie reden wir aneinander vorbei.

ja aber ich eklaere es dir gerne so oft bis du es verstehst.

tenim schrieb:

also steht im cache am fang 0 und beim zurueckschreiben 0, auf jedenfalls ist diese arbeit totale zeitvergoldung.

nein, BEIM zurückschreiben steht noch eine 1 drin, NACH dem zurückschreiben wieder 0.

es geht immer noch um den cache und dort steht beim einlesen und am ende beim rausschreiben 0.

aber das kann man vorher nicht wissen und auch nicht verhindern.

doch, wie ich es schon mehrmals schrieb, erst freie stelle finden, dann die freie stelle mit einsen fuellen, nicht schon beim testen des volumens die 1 einfuegen.

ich brauche die 1ser ja zum testen des nächsten einzufügenden steines auf kollisionen mit den vorigen.

ja, wie ich schon sagte, wenn du fertig bist mit der suche nach einer freien stelle fuer den koerper, fuelle sie mir einsen.

nein, du weisst noch nicht ob ein objekt passen kann und schreibst schon unmengen von daten nur um sie gleich danach wieder mit 0 zu fuellen.

das stimmt teilweise. ich weiss vorher nicht, ob ein objekt in die nächste freie einfügeposition passt. aber es MUSS in diese nächste freie position passen, wenn die aktuelle steinkombination die richtige/gesuchte ist. wenn nicht, wird der teil des suchbaums verworfen und ich probiere die nächste variante mit einem anderen stein.

ja und hast zwischendruch unnuetzerweise unmengen einsen und nullen geschrieben.

such erst einen freien raum und wenn du ihn hast, erst dann fuelle ihn mit einsen.

das wäre von der performance tödlich, würde alles wahrscheinlich um den faktor 100 verlangsamen. durch die variante mit der nächsten einfügeposition habe ich immer ohne grosses rechnen die nächste stelle. und dort MUSS wie gesagt der nächste stein reinpassen, wenn es die gesuchte kombination/lösung ist.

von der performance toedlisch ist es unmengen von einsen zu setzen und sie dann zu loeschen.

beispiel aus der realen welt. du suchst ein perfektes regal fuer deine 24baendige herr der dinge sammlung.
deine variante: in jedes regal die buecher einsortieren und falls es gegen ende zu eng wird, nimmst du die buecher wieder stueckweise raus.
meine variante: erst rausfinden ob der band passen wuerde und erst dann einsetzen.

versuch das bitte zu verstehen. arbeit leisten, arbeit rueggaengig machen == keine arbeit machen. du machst ersteres, ich schlage zweiteres vor.

[tenim]

ich verstehe jetzt wie du es meinst.

es wären durch diese optimierung dann 66% weniger schreib/lesezugriffe nötig
wenn ein teil nicht reinpasst. ich probier das mal aus, mal sehen wieviel das ausmacht.

beispiel aus der realen welt. du suchst ein perfektes regal fuer deine 24baendige herr der dinge sammlung.
deine variante: in jedes regal die buecher einsortieren und falls es gegen ende zu eng wird, nimmst du die buecher wieder stueckweise raus.
meine variante: erst rausfinden ob der band passen wuerde und erst dann einsetzen.

das lässt sich aber dennoch nicht vermeiden, weil ich zwar im aktuellen fall von objekteinfügen testen kann ob es reingeht und es erst dann reinsetze, aber wenn das objekt reingeht und das nachfolgeobjekt nicht, muss ich auch das vorherige wieder entfernen. es ist sowas wie ein binärer baum mit 23 ebenen, welche die reihenfolge der steineinsetzung darstellen. wenn alles bis ebene 19 reingeht und in ebene 20 keiner der übrigen steine mehr passt muss ich auch in ebene 19 den nächsten stein nehmen und den alten vorher wieder mit 0 überschreiben.

[tenim]

programm ist 3s schneller als vorher. macht leider nichts aus bei der anzahl von interationen. es müsste um den faktor 100 schneller laufen.

[Jester]

Mußt Du unbedingt die dichteste Packung finden? Oder tut's auch eine Annäherung?

[rapso]

tenim schrieb:

programm ist 3s schneller als vorher. macht leider nichts aus bei der anzahl von interationen. es müsste um den faktor 100 schneller laufen.

hast du die andere optimierung auch eingebaut, dass nicht das volumen getestet wird, sondern nur die flaechen der aussenseiten?

wenn dein volumen z.b. 20*20*20 ist, hast du statt 20^3(8000) dann nur noch 6*(20^2) (2400) tests und je groesser das volumen ist, desto mehr sparst du.

wenn du zudem erst nur die raender testest, findest du statistisch gesehen eher heraus falls ein volumen nicht an die zu testende stelle passt. (zudem sind es dann 12*20+6*(18^2) (~2200) tests

wie gross ist so ein volumen das du einfuegen moechtest in etwa und wie gross die ganze box?

[tenim]

Mußt Du unbedingt die dichteste Packung finden? Oder tut's auch eine Annäherung?

es gibt genau eine lösung, d.h. eine variante, wie die 23 steine in der box angeordnet sein müssen, damit alle platz haben und keiner oben übersteht.

die box ist 175x157x147, und bei mir aber +1 auf jeder seite mehr, weil ich auch eine virtuelle holzwand an den 3 aussenseiten der box eingefügt hab um auch mitzukriegen wenn ein objekt seitlich aus dem kasten in die kastenwand ragen würde.

ein stein ist z.b. 45x68x85, was ungefür der durchschnitt für die steine ist.
die weiter vorgeschlagenen optimierungen mit dem testen der seitenflächen des steins kann ich noch programmieren. aber zuerst die ränder und wenn kein ergebniss kommt noch den rest der seitenflächen testen ist wahrscheinlich durch die zusätzliche kontrollogik auch nicht schneller(muss ich sehen).

das beste wäre wahrscheinlich eine mathematische lösung mit geometrischer berechnung von
a) der nächsten einfügeposition nach dem vorhin genannten schema
b) kollisionsprüfung des neu einzufügenen objektes an der ermittelten position
mit den bisher im kasten befindlichen objekten.

man hätte dann eine tabelle mit allen bisher eingefügten steinen statt dem array mit den volumeninformationen:
1. einfügeposition x,y,z (3 bytes) und die länge, breite, höhe des steins(3 byte) mit insgensamt nur 6 bytes pro eintrag.
dann prüft man rechnerisch die oben genannten dinge und fertig.
aber das übersteigt meine mathe-fähigkeiten bei weitem.