Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Nov 01, 2024 00:18

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 16 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
BeitragVerfasst: Di Jan 07, 2014 20:50 
Offline
DGL Member

Registriert: Mi Okt 16, 2002 15:06
Beiträge: 1012
Serv,

ich versuche seit geraumer Zeit einen kleinen in C# geschriebenen Code der mit Parallel.For arbeitet nach Java zu portieren,
aber irgendwie klappt das aber überhaupt nicht. Entweder es funktioniert nicht, also das Ergebnis ist falsch, oder es ist so deutlich langsamer als vorher :-( Meine .NET Kenntnisse gehen leider nur bis .NET 2.0, da gab es diese Konstrukt noch nicht.

Im Übrigen die originale C# implementierung ist um Faktor 30 schneller also ohne Parallel for.

Die Folgenden Methode in C# (.NET 4.0):

Code:
  1.  
  2.  
  3. // Kram in der Klasse auf welchen zugegriffen wird
  4. const int MAX_PARTICLES = 1000;
  5. Vector2[] _delta = new Vector2[MAX_PARTICLES];
  6. int _numActiveParticles = im bereich von 0-1000
  7. int[] _activeParticles = new int[MAX_PARTICLES];
  8. object _calculateForcesLock = new object();
  9.  
  10. public void calculateForces(const float dt) {
  11.             // Calculate forces
  12.             Parallel.For(
  13.                 0,
  14.                 _numActiveParticles,
  15.                 () => new Vector2[MAX_PARTICLES], // Wird das Vector2 Array pro Iteration angelegt oder nur einmalig?
  16.                 (i, state, accumulatedDelta) => calculateForce(_activeParticles[i], dt, accumulatedDelta),
  17.                 (accumulatedDelta) => // accumulatedDelta ist doch dieses zuvor erstellte Vector2 array???
  18.                 {
  19.                     lock (_calculateForcesLock)
  20.                     {
  21.                         for (int i = _numActiveParticles - 1; i >= 0; i--)
  22.                         {
  23.                             int index = _activeParticles[i];
  24.                             _delta[index] += accumulatedDelta[index];
  25.                         }
  26.                     }
  27.                 }
  28.             );
  29. }
  30.  
  31. private Vector2[] calculateForce(const int index, const float dt, Vector2[] accumulatedDelta) {
  32.   // ... code here which modifies accumulatedDelta
  33.   return accumulatedDelta
  34. }
  35.  


Und hier code in Java (Funktioniert zwar ist aber langsamer und Eclipse spackt total rum wenn ich das starte):

Code:
  1.  
  2.  
  3. // Kram in der Klasse
  4. final int MAX_PARTICLES = 1000;
  5. Vector2[] _delta = new Vector2[MAX_PARTICLES];
  6. int _numActiveParticles = im bereich von 0-1000
  7. int[] _activeParticles = new int[MAX_PARTICLES];
  8. final Object _calculateForcesLock = new Object();
  9.  
  10. public void calculateForces(const float dt) {
  11.     // Ergebnis array für Akkumulierte Kräfte anlegen
  12.     final Vec2f[] accumulatedDelta = Vec2f.createArray(maxParticles);
  13.    
  14.     // Thread pool anlegen
  15.     final ExecutorService executor = Executors.newFixedThreadPool(numOfProcessors);
  16.    
  17.     class ForceResult implements Callable<Vec2f[]> {
  18.         private final int index;
  19.         private final float dt;
  20.         private final Vec2f[] accumulatedDelta;
  21.        
  22.         public ForceResult(final int index, final int maxParticles, final float dt, final Vec2f[] accumulatedDelta) {
  23.             this.index = index;
  24.             this.dt = dt;
  25.             this.accumulatedDelta = accumulatedDelta;
  26.         }
  27.        
  28.         @Override
  29.         public Vec2f[] call() throws Exception {
  30.             return sph.calculateForce(index, dt, accumulatedDelta);
  31.         }
  32.     }
  33.    
  34.     // Aufgaben erstellen und an den Threadpool übergeben
  35.     List<Future<Vec2f[]>> futures = new ArrayList<Future<Vec2f[]>>();
  36.     for (int i = 0; i < _numActiveParticles; i++) {
  37.         int index = _activeParticles[i];
  38.         Future<Vec2f[]> future = executor.submit(new ForceResult(index, maxParticles, dt, accumulatedDelta));
  39.         futures.add(future);
  40.     }
  41.    
  42.     // Keine neuen Aufnehmen mehr annehmen
  43.     executor.shutdown();
  44.    
  45.     // Ergebnisse einsammeln
  46.     for (Future<Vec2f[]> future: futures) {
  47.         try {
  48.             Vec2f[] result = future.get();
  49.         } catch (InterruptedException e) {
  50.         } catch (ExecutionException e) {
  51.         }
  52.     }
  53.    
  54.     // Thread pool beenden
  55.     executor.shutdownNow();
  56.    
  57.     // Ergebnisse verarbeiten
  58.     synchronized (_calculateForcesLock) {
  59.         for (int i = numActiveParticles - 1; i >= 0; i--) {
  60.             int index = activeParticles[i];
  61.             VecMath.vec2Add(_delta[index], accumulatedDelta[index], _delta[index]);
  62.         }
  63.     }
  64. }
  65.  
  66. private Vector2[] calculateForce(final int index, final float dt, Vector2[] accumulatedDelta) {
  67.   // ... code here which modifies accumulatedDelta
  68.   return accumulatedDelta
  69. }
  70.  


Wäre wirklich super, wenn ihr euch das mal anschauen könntet und mir tips geben was hier schief läuft.

*Edit: Grad nochmal in die .NET Doku geschaut, also dieses () ist wohl die initialisierung eines lokalen Rückgabe Parameters und wird pro Task angelegt O_o Habe ich 100 aktive Partikel, und jeder dieser Task erzeugt Vector2 array mit länge 1000, das kann ja nicht schnell sein.... aber wieso geht das in C#????????

Danke,
Final


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Jan 07, 2014 22:23 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Wenn du wissen willst, was die Methode macht, schau doch einfach auf MSDN.
Auf der entsprechenden Seite heißt es zum Beispiel klar für den dritten Parameter "localInit": "Der Funktionsdelegat, der den ursprünglichen Zustand der lokalen Daten für jede Aufgabe zurückgibt."
Ich denke, da gibt es nicht mehr viel misszuverstehen. Ist ja alles gut dokumentiert.
Seit Net 2.0 hat sich übrigens nichts mehr fundamental geändert. Es kamen höchstens ein paar neue Klassen ins Framework.

Wenn es ohne parallel for 30 mal schneller ist, wieso verwendest du es dann überhaupt?
Wahrscheinlich sind die Berechnung so trivial das der zusätzliche Organisationsaufwand für das Threading denn Gewinn wieder auffrist. Was für Berechnungen machst du denn in etwa?
Was der "_calculateForcesLock"-Lock im seriellen Codeabschnitt soll, verstehe ich irgendwie nicht.

Bei Java kann ich dir leider nicht wirklich weiterhelfen. Ein möglicher Grund für den Performanceverlust in Java könnte sein, dass unglaublich viele temporäre Objekte erzeugt werden müssen. (Zb. jeder einzellne 2D Vektor)


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 07:58 
Offline
DGL Member

Registriert: Mi Okt 16, 2002 15:06
Beiträge: 1012
OpenglerF hat geschrieben:
Wenn du wissen willst, was die Methode macht, schau doch einfach auf MSDN.
Auf der entsprechenden Seite heißt es zum Beispiel klar für den dritten Parameter "localInit": "Der Funktionsdelegat, der den ursprünglichen Zustand der lokalen Daten für jede Aufgabe zurückgibt."
Ich denke, da gibt es nicht mehr viel misszuverstehen. Ist ja alles gut dokumentiert.
Seit Net 2.0 hat sich übrigens nichts mehr fundamental geändert. Es kamen höchstens ein paar neue Klassen ins Framework.

Wenn es ohne parallel for 30 mal schneller ist, wieso verwendest du es dann überhaupt?
Wahrscheinlich sind die Berechnung so trivial das der zusätzliche Organisationsaufwand für das Threading denn Gewinn wieder auffrist. Was für Berechnungen machst du denn in etwa?
Was der "_calculateForcesLock"-Lock im seriellen Codeabschnitt soll, verstehe ich irgendwie nicht.

Bei Java kann ich dir leider nicht wirklich weiterhelfen. Ein möglicher Grund für den Performanceverlust in Java könnte sein, dass unglaublich viele temporäre Objekte erzeugt werden müssen. (Zb. jeder einzellne 2D Vektor)


Betreffend berechnungen, nein die sind nicht trivial - da wird viel mit Vektoren gerechnet, Wurzel gezogen etc.
Nicht umsonst, macht man das normalerweise auf der GPU und nicht auf der CPU. Da geht es nämlich um Berechnung von Smoothed Particle Hydrodynamics - also das simulieren von Flüssigkeiten und Gase.

Ich habe auch in die MSDN Doku geschaut, also dieses Lambda ist mir aktuell noch echt Suspekt. Aber ich denke ich verstehe nun was passiert. Parallel.For von .NET erzeugt ein paar Threads und teilt die For-Schleife in einzelne Threads auf. Also z.b. 4 Threads, das jeder Thread ein Viertel von der Länge der Schleife abarbeitet. Und dieses AccumulatedDelta sorgt dafür, das nicht jeder einzelne _delta Vector pro Iteration weggeschrieben werden muss - daher wird 4x das array erstellt und am ende des werden die Ergebnisse von dort nach _delta mit einem Lock geschrieben. Richtig?


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 14:19 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Zitat:
da wird viel mit Vektoren gerechnet, Wurzel gezogen etc.

Hm ok. Wie lange dauert es denn auf der CPU single threaded zum Berechnen? Gibt es Partikelinteraktion?
Wurzel ist heute auch nicht mehr wirklich aufwendig.

Zitat:
also dieses Lambda ist mir aktuell noch echt Suspekt.

Lamdas sind ein heutzutage sehr verbreitetes Sprachmittel aus der funktionalen Programmierung.
Im Prinzip einfach eine lokale anonyme Funktion. Das gibt es zwar nicht in der Form in Version 2.0 aber mit der gleichen Funktionalität und etwas anderem Syntax mit dem "delegate"-Schlüsselwort

Zitat:
Ich habe auch in die MSDN Doku geschaut, also dieses Lambda ist mir aktuell noch echt Suspekt. Aber ich denke ich verstehe nun was passiert. Parallel.For von .NET erzeugt ein paar Threads und teilt die For-Schleife in einzelne Threads auf. Also z.b. 4 Threads, das jeder Thread ein Viertel von der Länge der Schleife abarbeitet.

Nicht unbedingt genau ein Viertel. Ich weiß es gerade nicht sicher, aber höchst wahrscheinlich werden die Aufgaben dynamisch verteilt. Also wenn zb. der erste Thread mit "seinen Viertel" vor den anderen fertig ist, er nicht Däumchen drehen muss, sondern weitere Aufgaben außerhalb "seinen Viertel" zugewiesen bekommt.

Zitat:
Und dieses AccumulatedDelta sorgt dafür, das nicht jeder einzelne _delta Vector pro Iteration weggeschrieben werden muss - daher wird 4x das array erstellt und am ende des werden die Ergebnisse von dort nach _delta mit einem Lock geschrieben. Richtig?

Ja, im Prinzip schon. Der "Lock" ist aber nicht optimal. Wobei ich mir gerade nicht sicher bin, ob C#/Parallel.For hier eine andere Möglichkeit vorsieht. Besser wäre es, das einfach lockfrei seriell zu machen.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 20:34 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Finalspace hat geschrieben:

Betreffend berechnungen, nein die sind nicht trivial - da wird viel mit Vektoren gerechnet, Wurzel gezogen etc.
Nicht umsonst, macht man das normalerweise auf der GPU und nicht auf der CPU. Da geht es nämlich um Berechnung von Smoothed Particle Hydrodynamics - also das simulieren von Flüssigkeiten und Gase.
Ich habe auch in die MSDN Doku geschaut, also dieses Lambda ist mir aktuell noch echt Suspekt. Aber ich denke ich verstehe nun was passiert. Parallel.For von .NET erzeugt ein paar Threads und teilt die For-Schleife in einzelne Threads auf. Also z.b. 4 Threads, das jeder Thread ein Viertel von der Länge der Schleife abarbeitet. Und dieses AccumulatedDelta sorgt dafür, das nicht jeder einzelne _delta Vector pro Iteration weggeschrieben werden muss - daher wird 4x das array erstellt und am ende des werden die Ergebnisse von dort nach _delta mit einem Lock geschrieben. Richtig?

Im Prinzip hast du es schon verstanden, aber du gehst noch ein bisschen zu naive an die Sache:

Für Parallel Tasks teilt man typischerweise eine Aufgabe in mehrere Abschnitte und verteilt die einzelnen Abschnitte auf die Threads. Die Anzahl der Abschnitte ist dabei meist sehr viel höher als die Anzahl der Threads. Dies ist der Tatsache geschuldet das in 99% der Fälle (insbesondere bei numerischen Werten) die Performance stark schwanken kann und manche Abschnitte halt die gleiche Aufgabe schneller durchlaufen als andere. Würdest du also brutal durch z.b. 4 Threads teilen, dann würdest du eine Unmenge an NOPs in jeden Thread haben.

Die Parallel.For generiert die zur Laufzeit daher zunächst sehr kleine Abschnitte und macht mit der Zeit immer größerere Abschnitte. Daraus folgt: Je länger eine Aufgabe läuft desto besser wird das Load Balancing deiner Threads. Und je komplexer eine Aufgabe desto besser kann Parallel.For diese optimieren.

Diese automatische Verteilung ist besonders gut geeignet für sehr große Aufgaben. Typischerweise sowas wie Entity Framework wo man ja mal locker auf gigantische Zeiten kommt. Dort kannst du dann mal eben von 32 Updates pro Minute auf 180 Updates kommen.

Für deine spezielle Aufgabe sollte man daher diesen default umgehen und sich ein eigenes Partitioner schreiben. Dann kannst du Verteilung selbst übernehmen.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 21:44 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Zitat:
dann würdest du eine Unmenge an NOPs in jeden Thread haben.

NOPs eher nicht, weil bei der Synchronisierung der Thread "gesleept" werden sollte. (Er bekommt also vom Betriebssystem einfach keine Rechenzeit mehr zugeteilt, bis es weiter geht.)


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 22:56 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
OpenglerF hat geschrieben:
Zitat:
dann würdest du eine Unmenge an NOPs in jeden Thread haben.

NOPs eher nicht, weil bei der Synchronisierung der Thread "gesleept" werden sollte. (Er bekommt also vom Betriebssystem einfach keine Rechenzeit mehr zugeteilt, bis es weiter geht.)


was sogar noch schlimmer wäre.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 08, 2014 23:17 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Eher anders rum. Wenn er weiter läuft, belastet er weiterhin den Prozessor und beansprucht einen Core. Er würde also allen anderen parallel laufenden Threads belasten und ihnen Rechenzeit klauen obwohl er selbst möglicherweise für längere Zeit keine Berechnungen mehr ausführen kann.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 00:29 
Offline
DGL Member

Registriert: Mi Okt 16, 2002 15:06
Beiträge: 1012
So habs jetzt gelöst: For schleife selbst partitioniert und nur soviele Tasks erzeugt wie Kerne vorhanden sind. Hat zwar keine automatische Skalierung wie es Parallel.For tut, aber es ist ein gutes Stück flotter geworden (+30%). Danke für die Tips =)


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 14:53 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Zitat:
Hat zwar keine automatische Skalierung

Wieso das?
Dafür gibt es im Framework entsprechende Eigenschaften:
http://msdn.microsoft.com/en-us/library/system.environment.processorcount(v=vs.80).aspx


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 18:35 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Naja soviel bringt das auch nicht unbedingt bei so simplen Sachen. Kannst ja mal mit dem Beispiel zum Partioner ein wenig rumspielen. Damit kannst du wunderbar die Sachen vergleichen.

Ich denke das beste wäre wenn man sich mal Schlau macht wie SIMD in C# bzw. Java funktioniert. Das sollte einen massiven Schub an Performance geben.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 18:45 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
SIMD kannst du in managed C# vergessen.
Mono hat so etwas. Aber die wenigsten haben Mono.

Ich fand das immer eine riesen Frechheit.
Schließlich wurde damit "geworben", dass der Vorteil von JIT-Kompiling ist, dass mit dem Wissen um welche Platform es sich handelt, man genau dafür besonders gut optimieren kann.
Und dann wird nichtmal SIMD unterstützt. Naja.

Ob Java SIMD nutzen kann weiß ich nicht. Explizit sicher nicht. Als Optimierung theoretisch vielleicht schon aber ich vermute eher nein, wie es auch bei C# ist. Vektorisation ist nicht gerade die einfachste Optimierung und ist wahrscheinlich nicht sinnvoll schnell als JIT umzusetzen.

In C# kann man auch noch etwas herausholen, wenn man Zeigerarithmetik verwendet. ("Unsafe-Code")


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 21:02 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Ich meinte eigentlich eher über Libs :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 21:06 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Achso, da gibt es prinzipiell das selbe Problem?
Theoretisch die einzige echte Möglichkeit ist über unmanaged Code.
Da stellt sich aber erstens die Frage, ob der Interop nicht mehr Zeit kostet als SIMD etc. einbringt und zum Anderen welche Lib man denn verwenden soll? Auf jeden Fall scheint mir das mit sehr viel Aufwand verbunden zu sein. Außerdem macht das die Verwendung von C# an sich irgendwie überlüssig.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jan 09, 2014 22:42 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
naja...
http://software.intel.com/en-us/blogs/2 ... tions-in-c

scheint doch nen ganz guter Start für den Anfang

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 16 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 10 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.016s | 15 Queries | GZIP : On ]