UCI Engine mit GPGU unterstützung als Seminarfacharbeit selbst erstellen

-------Achtung: Wall of Text--------------------------------------------


Ich möchte hier mein vorraussichtliches Facharbeitsthema vorstellen:
Eine Schachengine, welche mehr oder wenige Brute Force mäßig spielen wird, da ich weder Zeit noch Erfahrung habe, um komplexe Stellungserkennungsalgorithmen o.ä einzubauen.
Vereinfacht gesagt wird sie Varianten suchen, in denen sie Materialvorteil besitzt und diese auswählen.
Kleinere Verbesserungsideen besitze ich natürlich, aber viel mehr werde ich wohl nicht schaffen.
Da die Variantenanzahl aber exorbitant zunimmt kam ich auf die Idee die GPU einzubinden.


Wie ich das ganze umsetze weiß ich noch nicht, aktuell scheint mir aber das UCI Protokoll am einfachsten, da ich dann mein Fritz/Houdini Gui nutzen kann.
Die "Nutzungsanleitung" die ich hier gefunden habe fand ich nicht sonderlich schwer umzusetzen:
http://www.shredderchess.de/schach-info/features/uci-universal-chess-interface.html

Der Grund warum ich das ganze vorhab ist folgender:
IT interessiert mich und grundkentnisse besitzte ich bereits (Gerade dabei mein 1. Semester abzuschließen, dazu vorkentnisse in C++)
Schach vorkentnisse natürlich auch (DWZ 1900-2000)

Somit könnte ich beides verbinden. Als Wissenschaftlichen Hintergrund würde ich Erklärungen über GPGU einbauen und deren nutzen in der Wissenschaft. Als Bsp würde ich u.a Boinc projekte aufführen.
Das Schachprogramm soll daher nur ein Beispiel für die Leistungsfähigkeit dieser "Idee" (GPGU) sein.

Umsetzen würde ich das wahrscheinlich durch openCL (ziehe AMD vor, besitzte auch selbst eine AMD graka), wenn ich es nicht schaffe mir in den 3 Monaten die Grundkentnisse anzueignen bleibe ich bei CUDA wo ich bereits grundkentnisse besitze und die Uni server nutzen kann (2 x 4-way SLI )
Die entsprechende Nvidia hardware könnte ich über die Uni server nutzen.

Abschließend möchte ich sagen, dass mir klar ist das das gesamte Projekt deutlich umfangreicher werden dürfte als bei einem normalen Thema.

Das stört mich aber nicht weiter, es sind beides Hobbys von mir und ich hatte onehin vor in den nächsten Monaten eine Engine zu schreiben, die mich besiegen soll.
Da noch die GPU berechnungen einzufügen dürfte kein zu großer Mehraufwand sein, wenn ich dadurch die Facharbeit gleich mit erleidige. Der Lehrer ist einverstanden.

Falls ihr irgendwelche Anmerkungen, anregungen, vereinfachungsvorschläge oder ähnliches habt immer her damit, ich bin für jegliche Kritik dankbar

Wie du richtig erkannt hast, wird der Suchraum in wenigen Zügen gewaltig groß. Er wächst so stark an, dass mehr Kerne drauf zu schmeißen keine sinnvolle Lösung für das Problem ist. Denn deine 10000 Kerne sind nur ein Tropfen auf den heißen Stein der über alle Maßen wachsenden Zahl möglicher Züge.
Viel wichtiger ist es, offensichtlich sinnlose Züge nicht weiter zu verfolgen und den Suchraum einzuschränken. Dabei helfen aber zigtrilliarden Kerne auch nicht weiter. Egal wie toll deine GPU ist, deine Brute Force Idee ist zum Scheitern verurteilt und du wirst um Minimax, Alpha-Beta-Pruning und Quiescence Search nicht herumkommen und damit solltest du vermutlich erstmal mehr als genug zu tun haben.

Erstmal danke für den Hinweis, wenigstens einer der sich erbarmt
Das die 20.000 zusätzlichen Kerne "vergleichsweise" wenig sind ist mir klar.
Bei geschätzt 40 Halbzügen pro Stellung macht das aber immerhin eine zusätzliche Tiefe von 2,7 halbzügen, ein klein wirkender aber nicht zu verachtender Vorteil. Irgendwas kleineres a la Alpha-Beta test baue ich natürlich ein, ist ja vergleichsweise schnell gemacht, sofern ich bei den Stellungsvergleichen (fast) nur auf Material achte. Hab mir den Spaß schonmal bei einer KI für 4-gewinnt gemacht und viel ändert sich ja nicht

Prinzipiell sollte es aber doch möglich sein, durch entsprechende "Einstellungen" dafür zu sorgen, dass "genug" Variantenzweige übrig bleiben, um 20.000 Kerne zu beschäftigen?
Gehe ich mal davon aus, dass lediglich 5-10 Züge weiter analysiert werden und ich die GPU bei 1 GHZ 1 sek laufen lasse schaffe ich grob überschlagen 7-11 Halbzüge was imho ok ist.
Im Vergleich zu einer 4 Kern CPU mit 3 GHZ welche im direkten Vergleich (ja, vereinfacht!) nur 4 - 6 Halbzüge schafft, finde ich das außerordentlich.


Der Punkt ist halt das ich irgendwie den nutzen von GPGU berechnungen veranschaulichen möchte und da ich eh vorhabe ne engine zu basteln das Praktische mit dem nützlichen verbinden möchte. Das bloße erstellen einer Schachengine reichte meinem Tutor leider nicht und Projekte ala Fightxyz@HOME sind mir leider ne nummer zu hoch

Falls du dir eine eine sinvollere Anwendungsdemonstration vorstellen kannst könnte ich natürlich auch überlegen zu wechseln, noch habe ich noch nicht angefangen. Allerdings ist dann irgendwo auch noch die Frage was mein Mathelehrer bereit ist zu korrigieren..

Wenn du dir bei einer Arbeit für die Schule/Uni (GP)-GPU auf die Fahnen schreibst, solltest du auch drauf eingehen. Da ist es im allgemeinen schlecht wenn das Fazit der Arbeit ist:
Ich habe einen parallelen Algorithmus auf der GPU implementiert.
Denn das ist keine Kunst und eventuell sogar so halb themaverfehlung. Deshalb sollte das Fazit deiner Arbeit sein:
Ich habe einen parallelen Algorithmus so modifiziert, dass er gut auf einer GPU lauffähig ist indem ich die Hardwareeigenschaften der GPU berücksichtigt habe.

Gerade das Optimieren ist ein sehr großes Thema für sich. Aus dem Grund lohnt sich eine GPU Arbeit m.E. nur, wenn man den Fokus auf das Optimieren legt. Dafür muss der grundlegende Algorithmus in Relation zur Arbeitszeit so halbwegs einfach implementierbar sein. Gerade das bezweifle ich etwas bei den Schachalgorithmen gemäß deinen Aussagen. Denn ansonsten hat man zwar wegen dem GPU-Teil einen deutliche Mehraufwand, da man sich in OpenCL einarbeiten und die Ansteuerung der GPU mit OpenCL programmieren muss. Allerdings kann man aus dem GPU-Teil an sich wahrscheinlich keinerlei erkenntnisse ziehen.

Hmmm, klingt überzeugend was du schreibst.
Um mal etwas konkreter zu werden, es geht um eine Schul-Seminar-Facharbeit.
Ziel ist es offiziell "Wissenschaftliches arbeiten" zu lernen, ergo richtiges nutzen von bereits bekanntem.
Aus dem Grund wollte ich mich in dem ersten Teil (~8 Seiten) damit beschäftigen wie GPU´s bzw GPGU aufkam und wie es mitlerweile genutzt wird, da kann ich schließlich wunderbar quellen nutzen, zitieren und das ganze übrige, geforderte gedöns.
Da ich nicht nur theoretisch bleiben möchte dachte ich daran auf den folgenden seiten zu beschreiben, wie ich die massive, parallele Leistung der GPU nutze um eine Schachengine zu verstärken. Dem würde ich direkt die Singlecore/Multicore Variante der selben Engine gegenüberstellen, welche lediglich die CPU nutzt. Dabei könnte ich dann auch auf die von dir erwähnten möglichen Optimierungen eingehen, bzw. auf der Verwaltungsaufwand, wegen dem das ganze nicht optimal skaliert. Das wiederrum könnte man ja wieder mit anderen Programmen, welche GPU´s nutzen vergleichen.

Mit open CL kenne ich mich leider noch nicht aus, aber zumindest so einfache Programme sind mittels CUDA ja nicht besonders schwer zu realisieren. Notfalls greife ich darauf zurück.

Hältst du eine derartige Arbeit für angemessener oder ist die Begründung für das implementieren zu schwach?
Ich könnte ja auch komplett auf die Praxis (engine) verzichten und lediglich 15 Seiten theorie abschreiben.
Aber genau das wollte ich wenn möglich eigentlich vermeiden.

Ich bin da ebenfalls bei Nai. Wie du zwar gesagt hast, es ist kein riesen Problem etwas einfaches - z.B. Vektoraddierung - für CUDA oder OpenCL zu schreiben und zum Laufen zu bekommen, jedoch ist der Code meilenweit entfernt davon gut zu sein.
Wenn du den Hauptpunkt der Arbeit auf das Thema GP-GPU legen willst, würde ich vielleicht etwas in die Richtung mit Matrizenmultiplizierung vorschlagen. Sprich du imlementierst einmal eine dumme Matrizenmultiplikation für die CPU und dann einfach und schnell für die GPU. Danach optimierst du immer weiter die GPU-Version und schilderst dabei was der aktuelle Optimierungsschritt gebracht hat und warum - z.B. Verwendung von Shared Memory, oder besseres Kernelkonfiguration (Threds/Blocks). All die Zeiten kannst du immer schön messen und das dann schildern - am Ende vielleicht noch mit eine CPU-Blas und GPU-Blas-Implementierung vergleichen.

Auch wenn ich mich mit den von dir genannten Algorithmen nicht groß auskenne, klingen sie für mich aber fast so als ob sie nicht wirklich gut für GPU's geeignet sind. Denn auch das ist eine "Kunst". Wie kann man eine CPU-Implementierung für die GPU umsetzen? Ist der Algo überhaupt geeignet oder muss ich einen komplett anderen wählen.

Aus dem Grund wollte ich mich in dem ersten Teil (~8 Seiten) damit beschäftigen wie GPU´s bzw GPGU aufkam und wie es mitlerweile genutzt wird, da kann ich schließlich wunderbar quellen nutzen, zitieren und das ganze übrige, geforderte gedöns.

Zum Vergrößern anklicken....

Viel zu viel; deine Arbeit ist keine Geschichtsstunde . Eine bis zwei Seiten für den geschichtlichen Hintergrund als Motivation reichen; und selbst die sollten in die Richtung GPU bezüglich Schach gehen. Dafür lieber GPU-Grundlagen, also wie eine GPU tickt (Ein paar Stichwörter die wahrscheinlich vorkommen sollten: Threads, Thread-Blocks, Warps, Shared-Memory, Occupancy, Caching, Register, SIMT, Latency Hiding, Coalescing, Bank Conflicts). Und zusätzlich Stand der Forschung: Welche aktuellen Ansätze gibt es momentan so das was du machst auf einer GPU zu implementieren?

Da ich nicht nur theoretisch bleiben möchte dachte ich daran auf den folgenden seiten zu beschreiben, wie ich die massive, parallele Leistung der GPU nutze um eine Schachengine zu verstärken. Dem würde ich direkt die Singlecore/Multicore Variante der selben Engine gegenüberstellen, welche lediglich die CPU nutzt. Dabei könnte ich dann auch auf die von dir erwähnten möglichen Optimierungen eingehen, bzw. auf der Verwaltungsaufwand, wegen dem das ganze nicht optimal skaliert. Das wiederrum könnte man ja wieder mit anderen Programmen, welche GPU´s nutzen vergleichen.

Mit open CL kenne ich mich leider noch nicht aus, aber zumindest so einfache Programme sind mittels CUDA ja nicht besonders schwer zu realisieren. Notfalls greife ich darauf zurück.

Zum Vergrößern anklicken....

Es geht nicht darum es irgendwie zu implementieren, sondern es geschickt zu implementieren. Das heißt dass man sich die Eigenschaften einer GPU zu nutzen macht. Auch ist die niedrige Performance *meist* nicht den Verwaltungsaufwand geschuldet. So werden wahrscheinlich folgende Probleme vermutlich bei deinen Schachalgorithmen auftreten, die die Performance lindern (ich weiß nicht wie die Algorithmen genau funktionieren deshalb sind das nur Vermutungen):
-Baumalgorithmen sind in der Regel nicht datenparallel. GPUs sind datenparallele Rechner. Wie optimierst du das Ganze, damit es datenparallel wird?
-Rekursiv geschriebene Programme laufen grauenhaft auf der GPU, sofern der Compiler nicht die Rekursion herausoptimieren kann und selbst dann laufen sie schlecht - in OpenCL sind rekursive Programme sogar komplett verboten. Das heißt du darfst das ganze iterativ programmieren, was wiederum etwas umständlicher ist. Eine Iteration sollte eine möglichst hohe Datenparallelität besitzen. Wie gestaltest du die Schleifenstrukturen dafür?
-Wahrscheinlich musst du die Berechnungen, die du auf der GPU durchführst, auf der CPU auswerten. Damit die GPU und die CPU permanent rechnen können, musst du das Kopieren zwischen beiden Asynchron (und am besten über zusätzliche Threads) in einer Pipeline gestalten. Eine solche Pipeline ist nicht leicht zu programmieren.
-GPUs sind für Algorithmen designt, welche einen relativ kleinen Workingset (Stichwörter: Registerplatz, Cacheplatz beziehungsweise Stackgröße, Occupancy) für automatische Variablen besitzen. Baumalgorithmen besitzen aber oft einen großen Workingset für automatische Variablen. Kannst du die Algorithmen irgendwie so umgestalten, damit der Workingset nicht explodiert.
-GPUs benötigen einen sehr hohen Parallelitätsgrad. Eine R290X kann gleichzeitig bis zu 100 000 Threads bearbeiten. Somit solltest du am besten ein großes Vielfaches von den 100 000 Threads starten. Kannst du die Algorithmen so umgestalten um den Parallelitätsgrad zu erreichen? Wie parallelisierst du das ganze so sehr, ohne dass der Workingset explodiert (Stichwort Thread Blocks, Shared Memory)?

Das sind nur ein paar einfachere Probleme, die sich so ergeben werden. Wie du siehst, wird das ganze relativ schnell relativ komplex und relativ hässlich. Ich würde die Themenstellung bereits auf dem Niveau einer Masterarbeit an einer Universität einschätzen. Deshalb würde ich dir wirklich auch raten nur einen einfachen Algorithmus zu nehmen. Eventuell die bereits vorgeschlagene Matrizenmultiplikation, das einfache Lösen eines linearen Gleichungssystems, oder eine einfache physikalische Simulation. Nkörper zum Beispiel. Das ist auch relativ einfach. Alternativ etwas aus der Computergraphik, wie beispielhaft irgendwelche Bildfilter oder einen einfachen Raycaster/Raytracer.

Ich könnte ja auch komplett auf die Praxis (engine) verzichten und lediglich 15 Seiten theorie abschreiben.
Aber genau das wollte ich wenn möglich eigentlich vermeiden.

Zum Vergrößern anklicken....

Es geht bei einer solchen Arbeit nicht ums "abschreiben" oder "zusammenfassen", sondern um etwas neues zu erschaffen, etwas zu bewerten, etwas zu diskutieren, oder etwas zu verbessern. Deshalb sind theoretische Arbeiten je nach Themenstellung auch valide, wofür man dann allerdings in der Regel mehrere Quellen vergleichen oder bewerten muss. Was aber genau von deinem Lehrer gewollt ist, kann ich nur mutmaßen. Deshalb spreche dich besser mal mit deinem Lehrer ab, ob und wie viel Praxis du für eine solche Arbeit machen solltest.

Erstmal vielen Dank für eure mühe, ich werde versuchen auf alles einzugehen.
Zuerst zur Parallelisierbarkeit des Alg, ich hätte einen ähnlich dem Wikipedia bsp. genommen, der ist ja universel einsetzbar. http://de.wikipedia.org/wiki/Minimax-Algorithmus
Die Parallelität wollte ich einfach über die große Anzahl an Varianten reinbringen, zehn halbzügen pro Stellung (nur die besten) hätte man ja schon nach 8 Halbzügen eine 290x für eine sek. ausgelastet (bei 1 GHZ), indem jeder thread eine Stellung bewertet (vor allem Figurenwert bestimmen).

Das Rekursion aber solche Probleme verursacht war mir nicht bewusst, ich hatte nur im Kopf was ich vor ewigkeiten gelesen hatte, nämlich das gewisse compiler schleifen, rekursionen und derartiges automatisch bei open MP parallelisieren... Anscheinend irre ich mich da aber und es betrifft wohl nur schleifen. Deshalb ging ich aber davon aus das dies in normalen openCL und CUDA programmen ebenfalls effektiv umgesetzt werden kann.

Das die Umsetzung von mir algemein viel zu naiv angegangen wurde ist mir mitlerweile aber klar geworden.

Was die von Nai angesprochenen 2 Seiten theorie angeht, das würde ich nicht durchbekommen. Mein erster vorschlag, eine selbstgeschriebener, (CPU only) engine wurde bereits abgelehnt, mit der Begründung dass ich da wohl nicht die möglichkeit habe umfangreich genug auf die Werke anderer einzugehen (Zu wenig aktuelle wissenschaftliche schriften in dem gebiet, ist schlieslich kein direktes Forschungsgebiet mehr).
Dabei hätte ich deutlich mehr als 2 Seiten theorie dazu geschrieben.

Es geht bei einer solchen Arbeit nicht ums "abschreiben" oder "zusammenfassen", sondern um etwas neues zu erschaffen, etwas zu bewerten, etwas zu diskutieren, oder etwas zu verbessern. Deshalb sind theoretische Arbeiten je nach Themenstellung auch valide, wofür man dann allerdings in der Regel mehrere Quellen vergleichen oder bewerten muss. Was aber genau von deinem Lehrer gewollt ist, kann ich nur mutmaßen. Deshalb spreche dich besser mal mit deinem Lehrer ab, ob und wie viel Praxis du für eine solche Arbeit machen solltest.

Zum Vergrößern anklicken....

Um das verbessern und erst recht neu erschaffen geht es bei uns nicht, ich bin einer der wenigen die überhaupt irgendwas praktisches machen (wollen), daher auch die Idee der Engine.
Für den Lehrer ist es auch volkommen ok, einfach nur die Werke anderer zusammenzutragen und umzuformulieren, eigene, neue Ergebnisse werden nicht mal ansatzweise erwartet. Das sei laut ihm was für die Bachelor oder eher noch Masterarbeit. Gymnasium ftw. Daher mein abwertender Kommentar übers abschreiben. Mag sein dass das wissenschaftlich gelegentlich bedeutsam sein mag, mich interessiert es einfach nicht.

Deswegen wollte ich eigentlich auch nichts über Matrixenmultiplikation machen, eine 5 sek google Suche hat schon links zu genau dem Thema einschlieslich einer optimierten Multiplikation mittels CUDA gebracht. http://www.reneschimmelpfennig.de/wp-content/uploads/2011/02/Seminararbeit-CUDA.pdf

Btw. hatte ich das auch schon in dem Udacity kurs geschrieben. Klar hätte ich dadurch kaum arbeit aber wenn es mir darum ginge würde ich mir ein Frühstudium, Turniere und ähnliche Späße schenken.
Hier der Link zum Kurs: https://www.udacity.com/course/cs344

Aber gut, wahrscheinlich schreibe ich die engine dann einfach nur CPU nutzend und such mir für meine Seminarfacharbeit etwas neues um das Potenzial der GPU´s zu demonstrieren. Evtl. finde ich ja auch eher was in Richtung einfacher Neuronaler Netze welche so langsam ja wieder in mode kommen, zugriff auf Neurosolution und entsprechende Lektüre hätte ich. Allerdings währe dass wieder was komplett neues wo ich im Gegensatz zu GPGU keine Erfahrungen habe weshalb mir selbst 3-4 Monate sehr knapp vorkommen.

Zuerst zur Parallelisierbarkeit des Alg, ich hätte einen ähnlich dem Wikipedia bsp. genommen, der ist ja universel einsetzbar.
Die Parallelität wollte ich einfach über die große Anzahl an Varianten reinbringen, zehn halbzügen pro Stellung (nur die besten) hätte man ja schon nach 8 Halbzügen eine 290x für eine sek. ausgelastet (bei 1 GHZ), indem jeder thread eine Stellung bewertet (vor allem Figurenwert bestimmen).

Zum Vergrößern anklicken....

Link ?

Was die von Nai angesprochenen 2 Seiten theorie angeht, das würde ich nicht durchbekommen.

Zum Vergrößern anklicken....

Ich meinte nicht zwei seiten Theorie, sondern ein bis zwei seiten Einleitung, mit wieso machst du das überhaupt. Der Theorieteil sollte stark fallabhängig irgendetwas zwischen 10 \% und 50 \% der Arbeit ausmachen.

Mein erster vorschlag, eine selbstgeschriebener, (CPU only) engine wurde bereits abgelehnt, mit der Begründung dass ich da wohl nicht die möglichkeit habe umfangreich genug auf die Werke anderer einzugehen (Zu wenig aktuelle wissenschaftliche schriften in dem gebiet, ist schlieslich kein direktes Forschungsgebiet mehr).

Zum Vergrößern anklicken....

Hier ist dein Lehrer etwas komisch. Man benötigt keine aktuellen Schriften um etwas gutes auf die Beine zu Stellen. Das ganze geht auch in relativ abgegrasten Forschungsgebieten meist relativ gut.

Für den Lehrer ist es auch volkommen ok, einfach nur die Werke anderer zusammenzutragen und umzuformulieren, eigene, neue Ergebnisse werden nicht mal ansatzweise erwartet. Das sei laut ihm was für die Bachelor oder eher noch Masterarbeit. Gymnasium ftw. Daher mein abwertender Kommentar übers abschreiben. Mag sein dass das wissenschaftlich gelegentlich bedeutsam sein mag, mich interessiert es einfach nicht.

Zum Vergrößern anklicken....

Hier ist dein Lehrer wieder etwas komisch und widersprüchlich: Er will dass ihr aktuelle Forschung liest, aber nicht dass ihr Eigenleistung erbringt? Bei solchen einfacheren wissenschaftlichen Arbeiten, die nur zur Übung dienen, ist doch eben die Eigenleistung von Bedeutung und nicht ob das Forschungsgebiet und Paper gerade aktuell sind. Bei uns war damals auch eine "Eigenleistung" in der Facharbeit Pflicht. Die Aktualität war mehr oder weniger egal. Einer hat beispielhaft die Facharbeit in Physik über einfache Planetenbeobachtung mit dem Fernglas (Teleskop hatte er keins) gemacht. Das ist schon seit 200 bis 300 Jahren nicht mehr aktuell .

Deswegen wollte ich eigentlich auch nichts über Matrixenmultiplikation machen, eine 5 sek google Suche hat schon links zu genau dem Thema einschlieslich einer optimierten Multiplikation mittels CUDA gebracht. http://www.reneschimmelpfennig.de/wp...rbeit-CUDA.pdf

Zum Vergrößern anklicken....

Ja, du hast eine Version der Matrizenmultiplikation geschrieben. Toll. Das geht in 10 Minuten. Du hast auch noch eine optimierte Version nach diversen Vorbildern nachprogrammiert. Das geht auch noch einmal in 10-20 Minuten. Jetzt aber der interessante Teil: Wieso ist deine Matrizenmultiplikation so gut wie sie ist? Wie viel \% der Peak-Performance erreicht sie? Wie kannst du sie weiter verbessern? Daraus kann man selbst bei sehr einfachen Algorithmen sehr viel machen. Interessanterweise lernt man durch solche Optimierungen bezüglich GPGPU-Programmierung auch sehr viel. Deshalb beschäftigen sich sehr viele und auch sehr gute Bacherlor- und Masterarbeiten oft damit, wie sie einen einfachen Algorithmus auf der GPU gut optimieren können.Beispielhaft habe ich in meiner Masterarbeit einen "Standard-Algorithmus" mit 20 Zeilen Quelltext auf ~40 Seiten optimiert und untersucht, relativ interessante Erkenntnisse daraus gezogen, womit ich vermutlich noch einmal 40 Seiten lang weitere Optimierungen hätte erstellen und untersuchen können. Ich kenne auch sehr gute Doktorarbeiten, die sich nur mit der Optimierungen von einem solch einfachen Algorithmus mit wenigen 10 oder 20 Zeilen Quelltext befasst haben. Aus dem Grund würden mir bei der Matrizenmultiplikation wiederum sehr viele interessante Ansätze einfallen um sie weiter zu verbessern. Somit eignen sich solche einfachen Algorithmen, gerade wenn es dir wie ja selbst gesagt um das Lernen von GPGPU geht, sehr gut.

Aber gut, wahrscheinlich schreibe ich die engine dann einfach nur CPU nutzend und such mir für meine Seminarfacharbeit etwas neues um das Potenzial der GPU´s zu demonstrieren. Evtl. finde ich ja auch eher was in Richtung einfacher Neuronaler Netze welche so langsam ja wieder in mode kommen, zugriff auf Neurosolution und entsprechende Lektüre hätte ich. Allerdings währe dass wieder was komplett neues wo ich im Gegensatz zu GPGU keine Erfahrungen habe weshalb mir selbst 3-4 Monate sehr knapp vorkommen.

Zum Vergrößern anklicken....

Gut. Nehmen wir an du tust das. Du implementierst einen Algorithmus für neuronale Netze auf der GPU nach, indem du einfach über eine parallele for-Schleife parallelisierst. Was lernst du daraus bezüglich GPGPU? Du lernst vielleicht den Algorithmus, wie der funktioniert. Aber über GPGPU im Speziellen nichts. Nachdem du am Ende deiner Arbeitszeit fertig bist, wirst du vielleicht erkennen, dass der Algorithmus auf der GPU langsamer als auf der CPU ist. Und dann musst du Rätseln wieso das so ist, weil du dich eben mit GPGPU danach nicht so gut auskennst. Auf diejenige Idee, dass es eventuell an der mangelnden Datenparallelität liegt, weil neuronale Netzwerke afaik auf Graphenalgorithmen basieren, welche eben oft nicht datenparallel sind, würdest du vielleicht gar nicht kommen. Auf diese Weise scheitern auch relativ oft die schlechteren Arbeiten an der Uni. Bei denen heißt es dann häufig am Schluss als Fazit:
"Ja also ich habe den Algorithmus mit der GPU parallelisiert. Und er wurde verglichen mit der CPU um den Faktor 2 langsamer. Ich habe eigentlich absolut keinerlei Ahnung woran das liegen könnte, aber ich tippe einfach einmal auf die Speicherbandbreite. Oder vielleicht doch die Latenzen? Dennoch zeigt die Arbeit das Potential von GPUs, ähm weil, ähm weil man ja zusätzlich auch mit der CPU rechnen kann!"

Deswegen würde ich dir wirklich und dringend aus eigener Erfahrung raten einen einfachen Algorithmus zu implementieren. Dies würde vermutlich etwas gegen deine leichte "Selbstüberschätzung" in Kombination mit einem leichten Dunning–Kruger-Effekt ( tut mir leid, ist nicht böse gemeint, aber deine Posts kommen alle so rüber ) verstoßen, wäre aber für dein Vorankommen sinnvoller.

Das geplante Vorhaben ist ja durchaus interessant (außerordentlich interessant würde ich mal sagen), aber für den geplanten Zeitraum und als Schularbeit wohl eher nicht machbar. Selbst bei einer Masterarbeit würde man sich in der Regel entweder um die Findung eines geeigneten Algorithmus oder um die Implementierung kümmern.
Bei einem so komplexen Problem wie dem Schachproblem ist die Seite der Algorithmen auch schonmal nicht ganz einfach. Mit Greedyvorgehen wie vollständigen Entscheidungsbäumen kommt man hier schließlich nicht weit. Also kann man zB eine Heuristik hernehmen. Aber welche? Woher kommt die? Warum ist diese Heuristik gut?
Meine Kenntnisse über Schach sind sehr begrenzt aber meines Wissens nach arbeiten die großen Schachcomputern auf einer Menge von bekannten Zügen. Das ist also vor allem eine riesige Datenmenge, die ausgewertet werden muss. Genau hiermit haben GPUs aber Probleme. Es nützt nichts einfach TB an Daten zur GPU zu schaufeln, wenn der Datentransfer dann wesentlich länger dauert, als die Berechnungen dort. Man benötigt also nicht nur einen Algorithmus, der theoretisch gut ist, sondern auch einen, der in der Praxis auf den jetztigen Maschinen schnell laufen kann. Das ist nochmal ein ganz eigenes Forschungsgebiet. Allein Speicherhierachien können die klassische Theorie gerne mal auf den Kopf stellen.
Es ist sehr wahrscheinlich, dass eine geeignete Rechenvorschrift dann schon recht umfangreich ausfällt und dementsprechend dauert auch so eine Implementierung entsprechend lange und ist dann wohl Gegenstand einer dritten Masterarbeit.

Auf der anderen Seite ist das allerdings ein Schulprojekt. Man sollte sich im Klaren darüber sein, dass hier eher wenig von der Theorie bereits von vorne rein bekannt ist und auch bei der praktischen Umsetzung mangelt es den Meisten wohl eher an Erfahrung. Also wäre vermutlich eine lauffähige Version bereits ausreichend.
Wenn ich an meinen Informatikunterricht an der Schule zurückdenke, so haben wir da eine Visualisierung für Bäume programmiert und Traversierungen durchgeführt. Also eher Malen nach Zahlen als richtige Mathematik. Von daher schätze ich, dass eine lauffähige Version den Lehrer wohl auch zufriedenstellen wird.

Die Eröffnungs- und Endspieldatenbanken sind einfache Hashabellen, bei denen eine (gehashte) Stellung entweder dem Bestmöglichen oder einer (kurzen) Liste gleichwertiger Züge zugeordnet ist. Algorithmisch passiert da gar nichts und GPU-Beschleunigung? Naja....

Nai schrieb:

Link ?

Zum Vergrößern anklicken....

-->Eingefügt

Nai schrieb:

Ich meinte nicht zwei seiten Theorie, sondern ein bis zwei seiten Einleitung, mit wieso machst du das überhaupt. Der Theorieteil sollte stark fallabhängig irgendetwas zwischen 10 \% und 50 \% der Arbeit ausmachen.

Zum Vergrößern anklicken....

Ok, das habe ich falsch verstanden

Nai schrieb:

Hier ist dein Lehrer etwas komisch. Man benötigt keine aktuellen Schriften um etwas gutes auf die Beine zu Stellen. Das ganze geht auch in relativ abgegrasten Forschungsgebieten meist relativ gut. Hier ist dein Lehrer wieder etwas komisch und widersprüchlich: Er will dass ihr aktuelle Forschung liest, aber nicht dass ihr Eigenleistung erbringt? Bei solchen einfacheren wissenschaftlichen Arbeiten, die nur zur Übung dienen, ist doch eben die Eigenleistung von Bedeutung und nicht ob das Forschungsgebiet und Paper gerade aktuell sind. Bei uns war damals auch eine "Eigenleistung" in der Facharbeit Pflicht. Die Aktualität war mehr oder weniger egal. Einer hat beispielhaft die Facharbeit in Physik über einfache Planetenbeobachtung mit dem Fernglas (Teleskop hatte er keins) gemacht. Das ist schon seit 200 bis 300 Jahren nicht mehr aktuell .

Zum Vergrößern anklicken....

Der Punkt dürfte einfach sein, das Schach früher als Forschungsgebiet interessant war, weil man davon ausging über die Spielweise etwas über die Funktionsweise des Gehirns herauszubekommen, was man schlieslich einstellte, da angeblich kein Zusammenhang besteht.
(Mir fällt zwar regelmäßig auf, dass man besssere Schachspieler menschlich meist über ihre Spielweise einordnen kann, aber das hat damit wohl wenig zu tun )
Auf jeden fall sind diese Studien so alt, dass Computer praktisch keine Bedeutung dabei hatten.
Ergo währen diese Quellen veraltet und für mich deshalb belanglos. Ich habe offen gesagt keine Ahnung wo man wissenschaftliche arbeiten sucht, aber zumindest die normalen Suchengines haben mich darin bestätigt-->Einzigen ergebnisse bzgl. Wissenschaftlicher Arbeiten über Schachengines stammen aus meinen beiden Forenthemen.

Nai schrieb:

Ja, du hast eine Version der Matrizenmultiplikation geschrieben. Toll. Das geht in 10 Minuten. Du hast auch noch eine optimierte Version nach diversen Vorbildern nachprogrammiert. Das geht auch noch einmal in 10-20 Minuten. Jetzt aber der interessante Teil: Wieso ist deine Matrizenmultiplikation so gut wie sie ist? Wie viel \% der Peak-Performance erreicht sie? Wie kannst du sie weiter verbessern? Daraus kann man selbst bei sehr einfachen Algorithmen sehr viel machen. Interessanterweise lernt man durch solche Optimierungen bezüglich GPGPU-Programmierung auch sehr viel. Deshalb beschäftigen sich sehr viele und auch sehr gute Bacherlor- und Masterarbeiten oft damit, wie sie einen einfachen Algorithmus auf der GPU gut optimieren können.Beispielhaft habe ich in meiner Masterarbeit einen "Standard-Algorithmus" mit 20 Zeilen Quelltext auf ~40 Seiten optimiert und untersucht, relativ interessante Erkenntnisse daraus gezogen, womit ich vermutlich noch einmal 40 Seiten lang weitere Optimierungen hätte erstellen und untersuchen können. Ich kenne auch sehr gute Doktorarbeiten, die sich nur mit der Optimierungen von einem solch einfachen Algorithmus mit wenigen 10 oder 20 Zeilen Quelltext befasst haben. Aus dem Grund würden mir bei der Matrizenmultiplikation wiederum sehr viele interessante Ansätze einfallen um sie weiter zu verbessern. Somit eignen sich solche einfachen Algorithmen, gerade wenn es dir wie ja selbst gesagt um das Lernen von GPGPU geht, sehr gut.

Zum Vergrößern anklicken....

Wahrscheinlich suche ich mir da tatsächlich einen Algorithmus in der Richtung aus.

Nai schrieb:

Gut. Nehmen wir an du tust das. Du implementierst einen Algorithmus für neuronale Netze auf der GPU nach, indem du einfach über eine parallele for-Schleife parallelisierst. Was lernst du daraus bezüglich GPGPU? Du lernst vielleicht den Algorithmus, wie der funktioniert. Aber über GPGPU im Speziellen nichts. Nachdem du am Ende deiner Arbeitszeit fertig bist, wirst du vielleicht erkennen, dass der Algorithmus auf der GPU langsamer als auf der CPU ist. Und dann musst du Rätseln wieso das so ist, weil du dich eben mit GPGPU danach nicht so gut auskennst. Auf diejenige Idee, dass es eventuell an der mangelnden Datenparallelität liegt, weil neuronale Netzwerke afaik auf Graphenalgorithmen basieren, welche eben oft nicht datenparallel sind, würdest du vielleicht gar nicht kommen. Auf diese Weise scheitern auch relativ oft die schlechteren Arbeiten an der Uni. Bei denen heißt es dann häufig am Schluss als Fazit:
"Ja also ich habe den Algorithmus mit der GPU parallelisiert. Und er wurde verglichen mit der CPU um den Faktor 2 langsamer. Ich habe eigentlich absolut keinerlei Ahnung woran das liegen könnte, aber ich tippe einfach einmal auf die Speicherbandbreite. Oder vielleicht doch die Latenzen? Dennoch zeigt die Arbeit das Potential von GPUs, ähm weil, ähm weil man ja zusätzlich auch mit der CPU rechnen kann!"

Zum Vergrößern anklicken....

Nai schrieb:

Deswegen würde ich dir wirklich und dringend aus eigener Erfahrung raten einen einfachen Algorithmus zu implementieren. Dies würde vermutlich etwas gegen deine leichte "Selbstüberschätzung" in Kombination mit einem leichten Dunning–Kruger-Effekt ( tut mir leid, ist nicht böse gemeint, aber deine Posts kommen alle so rüber ) verstoßen, wäre aber für dein Vorankommen sinnvoller.

Zum Vergrößern anklicken....

Deswegen habe ich zur Sicherheit ja nochmal nachgefragt
Die Sachengine werde ich dann ohne Schulischen zusammenhang und den "zwang" Gpu`s zu nutzen erstellen.
Evtl. kommt dann ja mal irgendwann was vernünftiges raus, denkanstöße gibts im internet ja mehr als genug.

Wahrscheinlich suche ich mir da tatsächlich einen Algorithmus in der Richtung aus.

Zum Vergrößern anklicken....

Falls du ein paar tipps haben möchtest, was du bei einem einfachen Algorithmus deiner Wahl so verbessern könntest, kannst du dich ja noch einmal bei mir melden