ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4441188
Jetzt (Chat):
15 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-

ZFX
Coding-Foren
Algorithmen und Datenstrukturen
Anstoss für das Ausnutzen von MultiCore-Systemen
Normal
AutorThema
BlueShark Offline
ZFX'ler


Registriert seit:
05.05.2005

Niedersachsen
Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Moin moin,

durch die neuen MultiCore Prozessoren wird es glaube ich immer wichtiger Lösungen zu finden, wie man sich diese extra Pferdestärken zu Nutze machen kann. Ich wollte hier mal eine Idee vorstellen, wie man vielleicht an die Sache rangehen könnte. Ist natürlich nicht meine eigene sondern orientiert sich an ein paar Artikeln, die ich gelesen habe.

Überlegungen :

  1. Multithreading lohnt sich nur dann, wenn man möglichst viel von seinen Aufgaben parallelsieren kann.
  2. Dabei ist es besser, wenn die Aufgabe mit Daten arbeiten, die von keiner anderen Aufgabe benötigt wird.(Jedenfalls beim parallelen Ablauf)
  3. Aus Punkt 1 und 2 müsste sich danach ein Modell ergeben, welches mit(vlt. ausschließlich) asynchronen Threads arbeitet.
  4. Aus 1, 2 und 3 ergibt sich, dass man viele Daten doppelt(oder noch öfter) im RAM vorliegen haben müsste. Meistens wohl einen aktuellen und einen veralteten Datensatz.
  5. Jedoch müssen bei Spielen gewisse Reihenfolgen von Aufgaben eingehalten werden.
  6. Schwer zu debuggen.


Meiner Meinung nach kann man Punkt 4 ganz nach unten an die "Dringlichkeitsliste" stellen. Immerhin haben heutige Systeme schon 4Gb RAM oder sogar mehr.

Punkt 6 ist meiner Meinung nach durch ein gutes Log-System erleichtern.

Somit bleiben eigentlich "nur" die restlichen 4 Punkte, die man beachten muss. Beim durchstöbern des Internets bin ich dann auf "Smoke" gestoßen. Dieses Modell(ich glaube von Intel) ist meiner Meinung nach ein interessanter Ansatz. Ich erkläre diesen mal eben kurz :

  1. |-------------------Renderer-----------------|
  2. |-----Physik-----||------KI----||------KI----|
  3. |-----Physik-----||------KI----||------KI----|

Die Zahlen geben an in welchen Thread die jeweilige Aufgabe läuft und die |-Striche geben die Grenzen einer Aufgabe an. Nach diesem Modell läuft der Renderer in einem Thread und gibt mehr oder weniger das Marschtempo an. Ist der Renderer fertig und die KI oder die Physik hängen zum Beispiel hinterher, verwendet der Renderer die letzten aktuellen Daten, die Physik und KI errechnet haben.

Pro :

  • Modell gibt einen Ansatz zur Lösung des Problems
  • die Threads müssen nur wenig miteinander kommunizieren
  • die Anzahl an Threads kann(jedenfalls theoretisch) beliebig erhöht werden

Contra :

  • Renderer gibt den Takt an
  • somit keine komplexeren Renderer möglich ohne dass sich die GHz-Zahl eines Kerns erhöht


Meine Schlussfolgerung :
Solange man es nicht hinbekommt den Renderer in kleine Aufgaben zu zerlegen wird man schnell an Grenzen stoßen. Die einzelnen Kerne werden in naher Zukunft wohl keine großen Geschwindigkeitssprünge machen.

Nun zum lustigen Teil :
Oder auch "Wie könnte man das lösen?".

Nun ich lege mich mal auf ein Genre fest, da unterschiedliche Spiele auch unterschiedliche Umsetzung einer Engine benötigen. Ich greif mir den Shooter raus. Natürlich macht hier die Aufteilung in Physik, KI, Audio, Input und Renderer Sinn. Jedoch wüsste ich nicht, wo man beim Renderer ansetzen könnte um den zu "zerstückeln".

Wie sieht es aus? Was für Ansätze kennt ihr? Wie könnte man den Renderer "zerstückeln"? Wie sollte man die Threads implementiernen?(Ich habe an eine Thread-Klassen gedacht, die die Funktionalitäten für die jeweiligen OS kapseln und via dll eingebunden werden)

Mfg
BS




2 Mal gendert, zuletzt am 12.02.2009, 15:34:50 Uhr von BlueShark.
11.02.2009, 23:18:53 Uhr
Krishty Offline
ZFX'ler


Registriert seit:
01.02.2004

Nordrhein-Westfalen
342173470
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Ich habe letztens ein Paper über PS3-Entwicklung gesehen, wo man ja auch das Problem hat, aus einem einzelnen Thread nicht viel an Renderperformance rausholen zu können.

Die Lösung war Multithreading neuer Generation – Threads, die nur dazu da sind, anderen Threads Befehle zu geben, wie sie die Daten auszurichten haben, damit wieder andere Threads sie so schnell wie möglich abarbeiten können. Damit kann dann der komplette Renderer parallelisiert werden – von der Dekompression der Textur- Vertex- und Animationsdaten (bei Konsolen wegen des geringen RAM-Satzes extrem wichtig) bis zu Animation, Culling und LoD-Berechnung.

Das Problem ist momentan eher, dass wir nicht genug Threads erzeugen können um die Leistung voll auszunutzen, aber Multithreading im oben genannten Umfang wieder zuviele Threads erzeugen würde.

Das Problem, Daten möglichst autonom verarbeiten zu müssen, ist durchaus lösbar, nur eben nicht einfach umsetzbar (das Betriebssystem schafft es ja auch, durch geschickten Umgang mit den Ressourcen Threads so effizient wie möglich zu füttern). Soweit, dass wir am Amdahlschen Gesetz kratzen, ist es in der Spieleentwicklung aber noch lange nicht, auch nicht beim Renderer.

Gruß, Ky

Edit: Hier ist das ganze Paper.

2 Mal gendert, zuletzt am 11.02.2009, 23:47:50 Uhr von Krishty.
11.02.2009, 23:40:51 Uhr
Jörg Offline
ZFX'ler


Registriert seit:
03.12.2005

Nordrhein-Westfalen
133916438
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Renderer zerstueckeln:
Auf Konsolen oder mit DirectX 11 wuerde man einfach mehrere Kommando-Buffer fuer die Grafikkarte parallel fuellen, und diese dann per Indirektion aus dem Hauptthread rendern lassen. So kannst Du wirklich viele Batch-Setups parallel erzeugen.

Ein bisschen aufpassen muss man, wenn in solchen Praesentationen von -zig *Threads* gesprochen wird. Manchmal meinen die einfach nur "Jobs/Tasks/Tasklets/...", halt irgendwas, was ohne Betriebssystemverwaltung durch einen user-space Scheduler abgearbeitet wird. Denn eines ist klar: Preemptiv muessen alle diese Aufgaben nicht zwangsweise abgearbeitet werden, da kommt man mit anderen Methoden schneller zum Ziel.

Was meinst du mit "An Amdahls Law" kratzen? Willst du sagen, dass wegen des Renderers gar nichts gescheit skaliert im Moment?
12.02.2009, 08:43:03 Uhr
Krishty Offline
ZFX'ler


Registriert seit:
01.02.2004

Nordrhein-Westfalen
342173470
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
[quote=Jörg]Was meinst du mit "An Amdahls Law" kratzen? Willst du sagen, dass wegen des Renderers gar nichts gescheit skaliert im Moment?[/quote]Ich will sagen, dass wir das gerade nicht tun – auch wenn BlueShark nicht wusste, wie er eine Engine über Einheiten wie Renderer und KI hinaus parallelisieren kann.

1 Mal gendert, zuletzt am 12.02.2009, 11:33:04 Uhr von Krishty.
12.02.2009, 11:32:49 Uhr
Enrico_ Offline
ZFX'ler


Registriert seit:
08.04.2003

Baden-Württemberg
72778726
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Zitat von BlueShark:
Immerhin haben heutige Systeme schon 4Gb RAM oder sogar mehr.

Und was bringt dir das doch gleich auf einem 32Bit Betriebssystem (ohne PAE, bevor wieder wer damit anfängt)? Arbeitsspeicher != adressierbarer Arbeitsspeicher...
Ansonsten gibts vom MS Gamefest sowie GDC jede Menge Paper über Multithreading.

Edit: Multi-Core Support in Anno 1404

1 Mal gendert, zuletzt am 12.02.2009, 13:00:27 Uhr von Enrico_.
12.02.2009, 12:52:15 Uhr
Krishty Offline
ZFX'ler


Registriert seit:
01.02.2004

Nordrhein-Westfalen
342173470
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Btw: Passt der Thread nicht besser in „Algorithmen und Datenstrukturen“?
12.02.2009, 12:59:08 Uhr
BlueShark Offline
ZFX'ler


Registriert seit:
05.05.2005

Niedersachsen
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Zitat:
Und was bringt dir das doch gleich auf einem 32Bit Betriebssystem (ohne PAE, bevor wieder wer damit anfängt)? Arbeitsspeicher != adressierbarer Arbeitsspeicher...

Das stimmt, dennoch glaube ich, dass die Entwicklung ganz klar in Richtung von 64Bit Systemen geht. Und auf denen ist mehr Arbeitsspeicher dann weniger das Problem. Außerdem ist das ungefähr so, als hätte man ein Spiel was nee 512Mb Graka braucht man aber nur nee 128Mb und 256Mb Graka im Pc hat.(ich weiß stark vereinfacht) Bedeutet also auch nur, dass man das Spiel nicht auf höchsten Einstellungen spielen kann.

@Kristhy : Danke fürs "Paper". Das das Ding gleich über 200 Seiten haben muss.........
Zitat:
Die Lösung war Multithreading neuer Generation – Threads, die nur dazu da sind, anderen Threads Befehle zu geben, wie sie die Daten auszurichten haben, damit wieder andere Threads sie so schnell wie möglich abarbeiten können. Damit kann dann der komplette Renderer parallelisiert werden – von der Dekompression der Textur- Vertex- und Animationsdaten (bei Konsolen wegen des geringen RAM-Satzes extrem wichtig) bis zu Animation, Culling und LoD-Berechnung.

Ich werde mir vielleicht einfach nur das Paper durchlesen müssen, dennoch frage ich mich warum diese Art der Verarbeitung nicht auch aufm Pc umgesetzt wird. Hört sich für mich nach einen Lösungsansatz an, dem man ruhig nachgehen könnte. Wie gesagt, ich muss erstmal das Paper lesen, vielleicht kann ich mir das dann selbst beantworten.
Zitat:
DirectX 11

Was??? Bin ich schon so weit hinterher? Ich dachte wir sind gerade mal bei 10? Oh Mann, ich sollte mir wohl öfters mal die Alternative zu OpenGL ansehen.

Zitat:
Btw: Passt der Thread nicht besser in „Algorithmen und Datenstrukturen“?

Naja ich dachte, dass das ja eher zu Gamedesign gehört, da wir ja hier keinen konkreten Code erhalten sondern nur über Konzepte reden.

Heilige......... dieses Paper ist wirklich pervers^^.

Mfg
BS


1 Mal gendert, zuletzt am 12.02.2009, 15:54:00 Uhr von BlueShark.
12.02.2009, 15:34:36 Uhr
Krishty Offline
ZFX'ler


Registriert seit:
01.02.2004

Nordrhein-Westfalen
342173470
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Zitat von Enrico_:
Und was bringt dir das doch gleich auf einem 32Bit Betriebssystem (ohne PAE, bevor wieder wer damit anfängt)? Arbeitsspeicher != adressierbarer Arbeitsspeicher...
Wer 2009 noch seine Engine auf 32-Bit-Systeme und 3 GiB RAM auslegt, hat entweder gute Gründe dafür (Minispiele / Causual Games) oder ist komplett schmerzfrei.

Zitat von BlueShark:
Wie gesagt, ich muss erstmal das Paper lesen, vielleicht kann ich mir das dann selbst beantworten.
Lies auch Enrico_’s Link, Anno 1404 bewegt sich ja schon in diese Richtung. Ansonsten liegt die Schwierigkeit darin, dass man beim PC keine genau definierte Hardware hat (wie bei Konsolen), wo man sagen könnte, dass das Auslagern auf einen anderen Kern soundsoviel Performance-Plus bringt. Auf dem PC schaufelt man naturgemäß das meiste auf die GPU.

Zitat von BlueShark:
Zitat:
Btw: Passt der Thread nicht besser in „Algorithmen und Datenstrukturen“?

Naja ich dachte, dass das ja eher zu Gamedesign gehört, da wir ja hier keinen konkreten Code erhalten sondern nur über Konzepte reden.
Naja, aber eben Programmkonzepte, keine Spielekonzepte. Vielleicht erbarmt sich ja ein Mod und verschiebt den Thread
12.02.2009, 15:54:56 Uhr
atr_23 Offline
Artwork-Berater


Registriert seit:
16.10.2002

Niedersachsen
107316684
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Ich wollte gerade schon wieder los meckern
genau Spieldesign ist was ganz anderes als Enginedesign. Als Programmierer schert man das immer ganz gern über einen Kamm, da das für viele Programmierer beim Spieleentwickeln im Mittelpunkt steht.
(glaub ich)

Also ich verschiebs mal ^^
12.02.2009, 17:04:28 Uhr
Vault 23
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Der Ansatz einer Task Queue mit x Workerthreads, die sich die Aufgaben der Reihe nach abholen, ist ja ziemlich naheliegend. Ich finde aber, dass bei dieser Problematik die Basis-Arbeitsstruktur das kleinste Problem ist. Nach meinem Empfinden ist der Großteil der Aufgaben nicht wirklich parallelisierbar. Schlichte Sachen wie Partikel, Animationsberechnung, das Laden der Resourcen usw kann man schön in solche Strukturen integrieren. Aber mal ehrlich: wieviel Rechenzeit pro Frame verwendet man denn tatsächlich auf solche Kleinigkeiten?

Der Renderer ist geeigneteres Modul für die Parallelisierung. Zumindest in begrenztem Rahmen, denn ganz am Ende darf man Direct3D nun mal nur aus einem Thread heraus ansteuern. Das Konzept der multiplen Kommandopuffer von DirectX11 lese ich hier gerade zum ersten Mal, aber es klingt verdammt interessant und nach einer guten Basis, um auch den Renderer auf mehr als einen Core verteilen zu können. In Maßen, wie gesagt, ganz am Ende darf auch der Grafikkartentreiber nur auf einem Thread laufen, man schiebt damit die Grenze also nur ein Stück hinaus. Was die praktische Realisierung angeht (bei mir DX9), stelle ich dann aber doch fest, dass es für die eine oder andere Sonderanwendung dann doch nötig ist, aus dem Renderer Daten auch wieder zurückzuholen oder ihm aus anderen Threads Nebeninformationen zuzuschieben. Mit wirklich sauberem Design kann man das evtl. vermeiden, aber zumindest bei meinen Versuchen war das Ganze eher mit ziemlich viel mühseliger Indirektion verbunden, damit der Informationsfluss Engine -> Renderer wirklich immer schön einseitig bleibt. Mühselig, aber es geht.

Das nächste, was ich anstreben würde, wäre eine Parallelisierung der Szenegraph-Iteration. Auch das kostet einiges an Rechenzeit, und muss pro Frame so einige Male gemacht werden. Andere Leute können hier wahrscheinlich mit tollem Design glänzen, aber ich habe mir da durch einen großen Haufen an "Lazy Evaluation" ein ziemliches Ei ins Nest gelegt. Es gibt bei mir eine Menge Punkte, die bei Zugriff prüfen, ob die angeforderte Information veraltet ist, die evtl. neuberechnen und die dann zurückreichen. Das ist tödlich für Parallelität - für die müsste das Iterieren über den Szenegraphen im Idealfall eine komplett nur lesende Operation sein. Mein persönliches Glück ist es da, dass wir sowieso schon knapp die Hälfte der Rechenzeit nur in D3DCalls verbringen... egal, wie sehr ich die Szenegraph-Iterationen parallelisiere, am Ende wartet alles doch auf den Renderer. Daher habe ich das Thema für unsere Engine erstmal auf Eis gelegt. Auch wenn es mich reizen würde...

Wenn die dann parallelisiert wären, hätte man schon eine Menge gewonnen. Was dann noch übrig ist, sind entweder wirklich rein lesend arbeitende Billigjobs oder Sachen, die ich als kaum parallelisierbar betrachte - KI, Spielmechanik, Nutzereingaben-Verarbeitung und so weiter. Glücklicherweise verbrauchen die bestenfalls 1% der Gesamtrechenzeit, wir können die also noch für eine ganze Weile sequentiell lassen

Die Grundaussage, die ich dazu eigentlich machen will, ist: in der Spieleentwicklung arbeiten wir anscheinend primär mit Aufgabenparallelität - einzelne Aufgaben können parallel zueinander arbeiten, aber wenn eine Einzelaufgabe zu groß wird, haben wir gelitten. Die freundlichen Teile der Paralellisierung liegen aber in der Datenparallelität, bei der man simple Aufgaben mit klarer Informationsabhängigkeit auf gewaltigen Datenmengen ausführt. Die sind halt sehr simpel parallelisierbar und praktisch in beliebig viele Segmente zerlegbar. Und davon sehe ich bei Spielen ehrlich gesagt nicht so viele Anwendungsfälle. Die Kunst der Programmierung in den nächsten Jahren wird nach meiner Meinung darin liegen, immer mehr gängige Aufgaben der Spieleentwicklung in den datenparallelen Bereich zu bekommen. Da steht uns noch eine Menge Denkarbeit ins Haus.

Raytracing wäre übrigens ein prächtiges Beispiel für eine datenparallele Aufgabe. Die ist halt genauso wie das Rasterisieren sehr einfach in Teilaufgaben zu zerlegen. Und wegen dieser einfachen Paralellisierbarkeit haben wir ja so hochparallele Grafik-Rechenmonster in unseren Rechnern heutzutage, die das jetzt in Hardware machen
13.02.2009, 00:00:05 Uhr
Dreamworlds Development
Jörg Offline
ZFX'ler


Registriert seit:
03.12.2005

Nordrhein-Westfalen
133916438
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Na da haben wir doch endlich jemanden, der "an Amdahl's Law" kratzt, was ?
Scherz beiseite, man sieht wohl, wie verschieden aktuelle Projekte parallelisierbar sind, und dass man an allen Ecken und Enden mehr Moeglichkeiten braucht, ueberhaupt Sachen parallelisieren zu koennen. Sei es eine erweiterte API fuers Rendern oder andere Algorithmen fuer bisherige (sequentielle) Standardaufgaben (Traversierung).
Sonst haengt man bei vielen Cores wirklich nur an A.L. . Aber das muss ja nicht immer so schlecht sein, wie es klingt...wenn ich trotzdem 120FPS schaffe, was will ich mehr fuer ein Spiel ?
Man koennte argumentieren, dass das 'Folgeprojekt' ja sehr viel mehr rendern muss usw. und das skalierbarer Code aus dieser Sicht zukunftssicher ist. Aber man kann die idle-Zeit der anderen Cores ja auch in Algorithmen investieren, die den eigentlichen (hier als nicht-parallel angenommenen) Rendervorgang optimieren, z.B. durch besseres Culling, LOD, etc. Auch so kann man Multicores besser ausnutzen ohne sich ueber die 'totale' Parallelisierbarkeit den Kopf zu zerbrechen.
13.02.2009, 09:44:47 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Anstoss für das Ausnutzen von MultiCore-SystemenNach oben.
Mir ist auch erst nachher eingefallen, dass zum Beispiel das Traversieren des Szenegraphens ja durchaus eine datenparallele Aktion nach meiner Definition ist... man kann ja einfach verschiedene Teilgraphen auf mehrere Cores verteilen. Solange das Traversieren komplett const ist (oder man den Szenegraphen doppelt ), kann man das ja beliebig weit aufspalten.

Nur die Quintessenz bleibt weiterhin die selbe, zumindest für uns und das aktuelle Projekt: Alles hängt am DirectX-Thread. Den auf einen eigenen Core auszulagern dürfte einen ordentlichen Gewinn bringen. Alles darüber hinaus können wir uns momentan komplett ersparen.

Bye, Thomas
13.02.2009, 12:14:47 Uhr
Dreamworlds Development
Normal


ZFX Community Software, Version 0.9.1
Copyright 2002-2003 by Steffen Engel