Hi,

es fing alles ganz harmlos an. Ich wurde gefragt, wie ich einen Algorithmus schreiben würde, der ein Array (n x n) so füllt, dass in jeder Zeile und Spalte jeder Wert nur einmal vorkommt, ohne das eine Regel dahinter gesehen werden kann. Also nicht einfach nur gegeneinander verschieben.

Daraus ist dieses kleine Programm entstanden. Es misst unter anderem die Zeit, die benötigt wird, um das Array zu füllen (wird durch die StringGrid-Operationen verfälscht) und die Anzahl der notwendigen Funktionsaufrufe.

Mich frustriert dabei, dass für eine Matrix von 32 x 32 mein PC, der hier mit kumulativ auf zwei Kernen mit 4 GHz läuft, dafür am längsten braucht. Wie schaffe ich es den Algorithmus so umzustricken, dass er auf beiden Kernen ausgeführt wird.

Wie lange braucht ihr denn für eine 32er Matrix?

Als nächsten Schritt werde ich mal eine grafische Auswertung in Abhängigkeit zur Matrixgröße einbauen.

Also da du jeden Versuch in das StringGrid einträgst musst du dich nicht wundern, wenn das Programm ewig braucht, wenn du das nonvisuell berechnest bist du schon deutlich schneller.
Zweitens scheinst du soweit ich das beim ersten Überfliegen gesehen habe einfach nur durch Ausprobieren die Lösungen zu finden, dass das ewig dauert, wenn du die selben Zahlen tausendmal ausprobierst ist auch klar.

Grundsätzlich liegt bei dir das Problem nicht daran ob ein oder zwei Kerne benutzt werden sondern an deiner Umsetzung würde ich sagen. Ich werde es mir am Abend nochmal anschauen, erstmal muss ich los.

Eins noch: Es ist normal, dass ein Prozessor mit mehr Kernen für einzelne Aufgaben länger braucht als ein vergleichbarer mit einem oder zwei Kernen. Das soll auch gar nicht der Vorteil einer Mehrkern-CPU sein. Dieser Algorithmus hier lässt sich in der Form wie du ihn hast schlecht aufteilen. Mit einem besseren Algorithmus schon, der würde dann auch gleich nicht alles tausendmal ausprobieren. Grundsätzlich lässt sich die Suche durchaus auf mehrere Threads verteilen.

jaenicke hat folgendes geschrieben :

Also da du jeden Versuch in das StringGrid einträgst musst du dich nicht wundern, wenn das Programm ewig braucht, wenn du das nonvisuell berechnest bist du schon deutlich schneller.

Das ist natürlich klar. Es geht auch gar nicht um die Geschwindigkeit an sich. Auf den anderen PCs lief es ja auch mit ständiger Aktualisierung. Der Vergleich untereinander stört mich.

jaenicke hat folgendes geschrieben :

Zweitens scheinst du soweit ich das beim ersten Überfliegen gesehen habe einfach nur durch Ausprobieren die Lösungen zu finden, dass das ewig dauert, wenn du die selben Zahlen tausendmal ausprobierst ist auch klar.

Nicht ganz. Es wird schon ein bisschen vorsortiert. Zumindest fische ich mir die heraus, die nicht mehr gesetzt werden dürfen.

jaenicke hat folgendes geschrieben :

Grundsätzlich liegt bei dir das Problem nicht daran ob ein oder zwei Kerne benutzt werden sondern an deiner Umsetzung würde ich sagen. Ich werde es mir am Abend nochmal anschauen, erstmal muss ich los.

Die Umsetzung kann natürlich fragwürdig sein. Auf die Schnelle war es halt mal eben hingefrickelt. Hast du einen besseren Vorschlag?

jaenicke hat folgendes geschrieben :

Eins noch: Es ist normal, dass ein Prozessor mit mehr Kernen für einzelne Aufgaben länger braucht als ein vergleichbarer mit einem oder zwei Kernen. Das soll auch gar nicht der Vorteil einer Mehrkern-CPU sein.

Dann habe ich da grundsätzlich noch die Frage, wozu denn Mehrkernsysteme überhaupt Vorteile bringen? Nur für das verteilte Rechnen?

jaenicke hat folgendes geschrieben :

Dieser Algorithmus hier lässt sich in der Form wie du ihn hast schlecht aufteilen. Mit einem besseren Algorithmus schon, der würde dann auch gleich nicht alles tausendmal ausprobieren. Grundsätzlich lässt sich die Suche durchaus auf mehrere Threads verteilen.

Ich bin sehr gespannt. Reicht es eigentlich schon aus, mehrere Threads anzulegen oder muss ich die Kerne, wenn das überhaupt geht, direkt ansprechen? (Die Frage erscheint mir ja selbst beim Hinschreiben schon dumm... )

17078ms bei Core2Duo E8200 (2,66 GHz). Gewerkelt hat Kern 2 mit 80%.

19140ms Intel Pentium 4 3,01 GHz (96 % Auslastung)

Hey,

die Zeit die das Programm braucht ist nicht wirklich deterministisch, oder?

Hab mir dein Programm nicht angeguckt, aber ich würd spontan folgendes Vorgehen vorschlagen:

1.) Fülle die Matrix vor, also z.B.

1 2 3
2 3 1
3 1 2

2)
Führe grob geschätzt 1000 "zufällige" Vertauschungen durch.
Dabei kannst du ausnutzen, dass die von dir beschriebene Ordnung invariant gegenüber dem Vertauschen von je 2 Zeilen und bzw. 2 Spalten ist.

Grüße, Thorsten

edit: "Habe mir deinen Source nicht angeguckt" trifft es wohl besser

freedy hat folgendes geschrieben :

jaenicke hat folgendes geschrieben : Eins noch: Es ist normal, dass ein Prozessor mit mehr Kernen für einzelne Aufgaben länger braucht als ein vergleichbarer mit einem oder zwei Kernen. Das soll auch gar nicht der Vorteil einer Mehrkern-CPU sein. Dann habe ich da grundsätzlich noch die Frage, wozu denn Mehrkernsysteme überhaupt Vorteile bringen? Nur für das verteilte Rechnen?

Die bringen durchaus Vorteile, aber eben nur, wenn mehrere rechenintensive Threads parallel laufen, das können mehrere Programme sein oder auch mehrere Threads in einem Programm. Wenn man aber nur ein Programm mit einem Thread parallel nutzt, dann läuft beispielsweise das System und das Programm auf dem zweiten Kern, aber mehr nicht. Und da ein einzelner Kern langsamer ist als ein Kern einer vergleichbaren CPU mit weniger Kernen läuft das einzelne Programm dann meistens langsamer.

freedy hat folgendes geschrieben :

Reicht es eigentlich schon aus, mehrere Threads anzulegen oder muss ich die Kerne, wenn das überhaupt geht, direkt ansprechen? (Die Frage erscheint mir ja selbst beim Hinschreiben schon dumm... )

Ja, Threads werden automatisch auf die Kerne verteilt, je nach Rechenzeit der einzelnen Threads. Wenn du also 3 oder mehr rechenintensive Threads hast, dann kann sich auch ein QuadCore lohnen. Ich selbst habe das nicht und habe deshalb einen DualCore und selbst da rechnet meist nur ein Thread wirklich viel.

Sagt doch, dass man den Haken bei "Update" rein machen muss.

202.523ms auf einem Athon X2 4400+ (unter WINE), bei 176.276 Funktionsaufrufen.

Ohne den Haken bei "Update" ist die Matrix in 1-2 Sekunden fertig.

[edit]
Zweite Versuch : 135.716ms bei 146.975 Funktionsaufrufen.
Dritter Versuch: 289.164ms bei 320.762 Funktionsaufrufen.

Thorsten83 hat folgendes geschrieben :

Hey, die Zeit die das Programm braucht ist nicht wirklich deterministisch, oder? Hab mir dein Programm nicht angeguckt, aber ich würd spontan folgendes Vorgehen vorschlagen: 1.) Fülle die Matrix vor, also z.B. 1 2 3 2 3 1 3 1 2 2) Führe grob geschätzt 1000 "zufällige" Vertauschungen durch. Dabei kannst du ausnutzen, dass die von dir beschriebene Ordnung invariant gegenüber dem Vertauschen von je 2 Zeilen und bzw. 2 Spalten ist. Grüße, Thorsten edit: "Habe mir deinen Source nicht angeguckt" trifft es wohl besser

Hallo Thorsten,

die Idee hatte ich anfangs auch. Dadurch passiert aber folgendes: Nahezu jede Zeile enthält die gleiche Reihenfolge der Elemente. D. h. du findest in fast jeder Zeile 2, 3. Bei einer 3x3 Matrix ist das noch überschaubar. Aber auch in den Zeilen sollen die Zahlen getauscht werden.

Hier mal ein Beispiel einer 8x8 Matrix. Ich erkenne jedenfalls (fast) kein Muster.

2 6 1 3 5 4 7 8
7 1 8 5 2 3 4 6
5 2 4 8 1 6 3 7
8 3 5 7 6 2 1 4
3 4 7 1 8 5 6 2
4 7 6 2 3 1 8 5
6 5 3 4 7 8 2 1
1 8 2 6 4 7 5 3


EDIT: Oh, ich hab übersehen... die Spalten willst du ja auch tauschen. Dann könnte das wahrscheinlich wirklich besser sein und es ließe sich sogar noch in mehrere Threads aufteilen.

freedy hat folgendes geschrieben :

Dann könnte das wahrscheinlich wirklich besser sein und es ließe sich sogar noch in mehrere Threads aufteilen.

Teil eins dieser Aussage stimme ich zu. Mehrere Threads sind hierbei aber nur sehr schwer machbar. Du arbeitest auf einer Matrix und vertauschst Spalten und Zeilen miteinander. Wie soll man das parallel machen? Wenn du zwei Zeilen miteinander vertauschst, werden dadurch alle Spalten geändert. Vertauscht man zwei Spalten, ändern sich dadurch alle Zeilen. D.h. man darf immer nur eins nach dem anderen machen.

Nicht ganz. Es dürfen immer parallel Zeilen ODER Spalten getauscht werden. Nur zusammen geht es nie. Ob es schon in Anbetracht der Tatsache, dass 1000 Vertauschungen relativ schnell sein sollten, sinnvoll ist, bleibt mal dahin gestellt.

Joah. Und wie stellt man sicher, dass zwei Threads, die Spalten vertauschen, nicht zufällig dieselbe Spalte an eine andere Stelle tauschen wollen? Da braucht es wieder zusätzliche Synchronisation und/oder "Sperrflags", d.h. jeder Thread markiert zwei Spalten für sich. Das würde (glaube ich) nur über Critical Sections gehen, die auch nicht unbedingt zur Erhöhung der Geschwindigkeit beitragen. Machbar ist das bestimmt.
Die Frage ist aber auch, ob dann überhaupt die CPU-Leistung das Nadelöhr ist, oder die Zugriffszeiten auf den Speicher. Ich vermute eher letzteres.

Da gebe ich dir Recht. Und somit taugt dieses Beispiel auch nicht, eine Anwendung zu simulieren, die beide Kerne ausnutzt. Darauf wollte ich nämlich irgendwann hinaus. Nach dem ursprünglichen Prinzip war es nämlich sehr rechenintensiv. Schade...

Ging es dir nur darum einen mehrprozessorfähigen Algorithmus zu schreiben?

Da würde ich sonst mal alle Divide&Conquer-Algorithmen empfehlen...

Die Divide&Conquer - Algorithmen sind mir klar. Mir geht es allgemein um verteilte Systeme, verteiltes Rechnen. Mehrprozessorfähige Algorithmen sind ja nur ein Teilbereich. Das oben beschriebene Problem tauscht sich zwar nicht über Nachrichten aus und nutzt einen gemeinsamen Speicher, dachte aber, es wäre gut, um einen Einstieg zu finden.

Hab's auch mal gestartet mit 32x32. Zeit: 63921 msec bei 786387 Funktionsaufrufen.
Pentium 4 3.3GHz W2KSP4

32x32
1. Durchlauf: 10875ms Funktionsaufrufe: 544837
2. Durchlauf: 4125ms Funktionsaufrufe: 198811
3. Durchlauf: 1890ms Funktionsaufrufe 89563

CPU: Intel Core 2 Duo T7700 @2,4Ghz (Kern1: ca. 80%; Kern2: ca 20%)

Und nochmal mit Intel Core 2 2.4Ghz
22906msec 445919 Funktionsaufrufe
18546msec 364176 Funktionsaufrufe
6718msec 130796 Funktionsaufrufe
Core1 ~ 40%
Core2 ~ 70-80%
Edit: Allerdings laufen ein Sack voll administrative Zwangsprozesse im Hintergrund. Ohne die wäre ich ca. 50% performanter

Ich finde es bei euch ja faszinierend, dass die Anzahl der Funktionsaufrufe (sie repräsentieren im Prinzip nicht alle notwendigen Versuche, eine Zahl in ein Feld zu schreiben) abnimmt, wenn ihr das Ganze mehrmals ausführt.

Da stelle ich mir doch die Frage: Warum ist das so???

baka0815 hat folgendes geschrieben :

[edit] Zweite Versuch : 135.716ms bei 146.975 Funktionsaufrufen. Dritter Versuch: 289.164ms bei 320.762 Funktionsaufrufen.

Scheint aber nicht die Regel zu sein. Hier steigt's an.