ParSim - Entwicklerblog - Seite 11 - Projektvorstellungen und Stellenangebote

ParSim - Entwicklerblog

1
…
- 2
- 3
- 4
- 5
- 6
- 7
8
9
10
11

Werbeanzeige

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

101

18.03.2014, 10:33

Es ist in der Tat so, dass man auf heutigen CPUs extrem viel rechnen kann und Speicherzugriffe (insbesondere auf den Hauptspeicher) relativ gesehen sehr langsam sind.
Dieser Effekt hat sich stetig verstärkt.

Ein Prefetch hilft dann, wenn du früh genug (!) vorhersehen kannst, dass du auf eine bestimmte Adresse zugreifen wirst und der CPU-eigene Prefetcher dies nicht vorausahnt und die Adresse sowieso schon in den Cache holt.

Der Effekt eines Prefetchings hängt natürlich stark von der Hardware ab.
Es kann gut sein, dass deine Optimierung auf moderneren CPUs gar keine Auswirkung hat, weil sie schon schlau genug sind, um die Daten von selbst in den Cache zu laden.

Hast du mal darüber nachgedacht, die Partikel direkt in den Gridzellen zu speichern?
Dann lägen die Partikel, die miteinander interagieren können, im Speicher näher beieinander.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

102

18.03.2014, 11:38

Zitat

Hast du mal darüber nachgedacht, die Partikel direkt in den Gridzellen zu speichern?

Ja darüber habe ich nachgedacht.

Ich sehe bei einer komplett regionäre Speicherung der Partikel Nachteile.
Interaktion erfolgt in allen Richtungen. Bei einer Iteration durch das Grid liegt nur einer der angrenzenden 8 Zellen in der Cacheline.
Ich würde gleichzeitig einen hohen Preis für die Iteration durch alle Zellen des Grid zahlen.

Beispiel:
Man spiel vielleicht mit 30.000 Partikeln und 30.000.000 Zellen im Grid. Die Partikel bilden dabei hunderte, vielleicht wenige tausend Klumpen.
Es werden im Spiel die Allermeisten Zellen des Grid leer sein. Da wird viel iteriert und klassisch verzweigt, wenn man über das Grid ran will.

Bei einer Gleichmäßigen hohen Dichte der Partikel würde ich eventuell Vorteile erwarten.

Ein Ansatz ist Sortieren. Das habe ich noch vor mir. Eventuell kann eine Sortierung der Partikel helfen.
1. Sortierung nach Position im Raum gegen cache misses?
2 Sortierung nach Partikeltyp zur Verbesserung der Sprungvorhersage?

Beides könnte wirksam sein, ersteres hat bei Experimenten auf der GPU viel gebracht. Vermute durch verbesserte Kohärenz im Speicherzugriff.

Zitat

Ein Prefetch hilft dann, wenn du früh genug (!) vorhersehen kannst, dass du auf eine bestimmte Adresse zugreifen wirst und der CPU-eigene Prefetcher dies nicht vorausahnt und die Adresse sowieso schon in den Cache holt.

Der Zeitpunkt des Prefetch, nicht zu früh, nicht zu spät, nichts was man doch nicht braucht. Wie kann man wissen welcher Zeitpunkt der beste ist. Wohl nur nach Bauchgefühl, dann testen?
Endgültige Ergebnisse stehen noch aus.

Zitat

Es kann gut sein, dass deine Optimierung auf moderneren CPUs gar keine Auswirkung hat, weil sie schon schlau genug sind, um die Daten von selbst in den Cache zu laden.

Das werde ich demnächst auf meinem Laptop, mit einem i7, testen. Nicht ganz der neuste aber schon was anderes als mein Desktop-PC.

MFG

Bilder zu meinem Projekt: ParSim

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Horus« (18.03.2014, 14:39)

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

103

17.04.2014, 10:44

Hallo,

da ich lange nichts geschrieben habe wollte ich mich mal wieder melden.
Es gibt gute Fortschritte. Was neues zeigen geht leider nicht.

Durch die Unterstütztung von Spiele Programmierer sind nun Shader vorhanden.
Außerdem ist das Projekt dank der Libs vonSpiele Programmierer SFML unabhängig geworden und die Kompatibilität verbessert, sowie Opengl 3.3 möglich.
Das entlastet die CPU und bietet neue Möglichkeiten für die Grafik. Leider ist mein GLSL nicht sehr gut

Noch interessant ist _vectorcall
Funktionen in denen man SIMD nutzt werden dadurch erheblich schneller.
Es ist so möglich geworden durch das Chachen von Partikelkollisionen und ein Abarbeiten in 4er (auf zukünftigen CPUs 8er) Schritten ganz ordentlich was zu drehen.
Ohne _vectorcall war das Cachen und Abarbeiten von je 4 Kollisionen mit SIMD einer Einzelbearbeitung ohne SIMD nicht überlegen.

Polymorphie und Vererbung sind bei den Partikeln trotz Datenorientierung möglich.
Wenn man mehrere Verzweigungen hat ist dies der Schnellste und sauberste Weg.

Partikel entfernen und zufügen geht nun. Das klingt einfach ist es aber nicht. Da durch die Datenorientierung keine Zeiger sonder Indizes verwendet werden ist das Umsortieren von Partikeln komplexer geworden.
Daten müssen kopiert werden, Indizes aus dem Grid zur Kollisionserkennung und bei den anhanftenden Partikeln müssen angepasst werden.
Insgesamt müssen pro Partikel bis zu sieben Indizes geändert werden wenn beim Entfernen umsortiert wird.
Es war fürchterliches Debuggen nötig.

Zeigeraritmetik ist schon was feines. Alles wird so einfach damit.
Schade, das so ungünstige Cache-Effekte durch Zeiger zustande kommen.

...

Weiterhin suche ich Leute die Lust haben Materialien zu entwickeln.

Material_Simple.cpp

C-/C++-Quelltext

#include "Material_Simple.h"

#include "ParticleContext.h"

using namespace ParticleEngine;

const DescriptorMaterial Material_Simple::Descriptor
(
"Simple",
[](MaterialCreateArgs Args) { return new Material_Simple(Args); }
);

Material_Simple::Material_Simple()
{}

Material_Simple::Material_Simple(const MaterialCreateArgs Args)
{
    Args.Context->Particle_BrownMotion[Args.Index] = 0.f;

    Args.Context->Particle_Acceleration[Args.Index] = Vec<2, float>(0.f, 0.f);
    Args.Context->Particle_Velocity[Args.Index] = Vec<2, float>(0.f, 0.f);

    Args.Context->Particle_Adhesive[Args.Index] = false;
    Args.Context->Particle_AdhesionCount[Args.Index] = 0;
    Args.Context->Particle_AdhesionElasticity[Args.Index] = 0.02f;

    Args.Context->Particle_HeatConduct[Args.Index] = 0.001f;
    Args.Context->Particle_HeatVolume[Args.Index] = 0.f;
    Args.Context->Particle_HeatAdjust[Args.Index] = 0.f;

    Args.Context->Particle_Color[Args.Index] = ColorRGBA<uint8_t>(128, 0, 0, 255);
}

void Material_Simple::Sole(ParticleContext*const Context, const ParticleIndex ParticleIndex)
{
}

void Material_Simple::Interaction(const ParticleIndex P0, const ParticleIndex P1)
{
}

So sieht ein Material aus.

"Descriptor" - Damit man das Material im Editor nutzen kann.
"Sole" - wird mit jedem Rechenschritt einmal aufgerufen
"Interaction" - wird bei jeder Kollision aufgerufen

Dies Beispielmaterial tut nichts und ist recht brüchig.

MFG

Bilder zu meinem Projekt: ParSim

Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von »Horus« (17.04.2014, 10:58)

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

104

05.05.2014, 13:29

Hi,
habe gestern endlich eine Lösung gefunden, für ein Problem an dem ich lange gearbeitet habe.

Es geht um die Übertragung von Wärme, Strom usw. Dort wären eigentlich Verzweigungen nötig.
Das ist jetzt möglich, schnell.

Sieht nicht anders aus. Die Zahlen aus dem Benchmark sind aber vielversprechend.

Durch sone Art Minimalsortierung beim Cachen von Partikelinteraktionen lassen sich bestimmte If-Abfragen an einer sehr wichtigen Stelle zur Compilezeit auflösen.
Es gibt sone Art Kollisionsklasse, welche Templatefunktionen als Mamber hat.
Der Aufruf erfolgt durch einen Array von Member Template-Funktionspointern, unter Nutzung der vectorcall-callingconvention.
Mit dem Ergebnis polymorpher Kollisionen.

Insbesondere wenn mehrere Eigenschaften wie Wärme und Strom usw. durch Materialien übertragen werden, ist hier statische Polymorphie und SIMD fast ohne Overhead vereinbar.
... hat auch ewig gedauert.

MFG

Bilder zu meinem Projekt: ParSim

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

105

09.05.2014, 12:23

Endlich gibts Gas.

Gas gabs zwar schonmal, aber nicht mit SIMD.

Das neue Gas nutzt eure CPU so effizient, es kann doppekt so viel Gas geben.

Schöne Explosionen! Das Gas dehnt sich kraftvoll aus.