Hey,
| Zitat von MrSparkle: |
| Das ganze nennt sich Partitioning[...] |
Eigentlich nennt sich das Mapping (nach
Foster's Methodology) Die (Daten-)Partitionierung des Problems hast du schon vorgenommen, wenn du Parallel.For bereits hinschreibst, weil du schon den Algo für das Gesamtproblem in einzelne Tasks für jedes Element aufgebrochen hast.
| Zitat von unconnected: |
| Versuch einmal vllt nur 4 oder 8 Threads aufzumachen. |
Agglomeration und Mapping selbst übernimmt (wenn nicht überschrieben) das .NET Framework von allein, in sofern wird schon eine 'optimale' Anzahl an Threads verwendet.
Aber zurück zu hawwk66's eigentlichem Anliegen, seinen konkreten Algorithmus zu beschleunigen.
| Zitat von hawwk66: |
| [lohnt] es sich bei folgendem Algorithmus [...] zu parallelisieren und wenn ja vor allem wie (richtig). |
Unabhängig von der Parallelisierung würde ich zunächst Folgendes ändern:
- Du hast nur 3 (konstante!) Farben. Also besteht dein MapArray-Dictionary nur aus drei Einträgen. Jeder Zugriff kostet aber unnötig Zeit. Also eliminiere den! Statt dass GetColorForHeight eine Farbe zurückgibt, mit der du im MapArray nach der passenden Liste nachschlagen kannst, lass dir direkt die passende Liste zurückgeben! So sparst du eine viertel Million Dictionary-Zugriffe.
Mach 1-Mal einen Dictionay-Zugriff
 C#-Code: |
List<int> brownList = MapArray[Color.Brown];
List<int> greenList = MapArray[Color.Green];
List<int> blueList = MapArray[Color.Blue];
|
Und lass dir dann immer direkt die richtige Listige zurückgeben:
| C#-Code: |
public Color GetListForHeight (int x, int y, List<int> brownList, List<int> greenList, List<int> blueList)
{
var value = WorldManager.Terrain.Heightmap [x * WorldManager.Terrain.ScaleFactor, y * WorldManager.Terrain.ScaleFactor];
if (value > 0.8)
return brownList;
else if (value > 0.5)
return greenList;
else
return blueList;
}
|
- Auch ich empfehle Jagged statt Rectangular Arrays mit einhergehender Vertauschung der Schleifen-Variablen. Also float[y][x] statt float[x,y].
(Hier ist es bei Bildern in jagged-Arrays üblich, zeilenweise vorzugehen, daher float[y][x])
Und dann Y für die äußere und X als innere Schleife verwenden. So gibt es in der inneren Schleife weniger Cache-Misses beim Iterieren, da ja alle x-Werte hintereinander im Speicher liegen.
Ich stimme zwar herbivore zu:
| Zitat von herbivore: |
| im Vergleich zur Bremswirkung durch lock kann man die Beschleunigung durch "burst-fähige" Speicherzugriffe komplett vernachlässigen. |
Aber wenn das Locking erstmal weg ist (beispielsweise weil weiterhin sequentiell), dann merkt man auch hier den Unterschied!
Das beides zusammen gibt einen Speedup von fast 3x.
Nun zum interessanten Part: Parallelisierung
Wie schon mehrfach aufgezeigt, ist das
locking hier eines der Probleme. Aber man kann noch einen Schritt weiter gehen und das eigentliche Problem beim Verwenden einer
gemeinsam genutzten Datenstruktur selbst sehen. Dies ist für jede parallele Abarbeitung 'tödlich'. Daher sollte - wenn du es parallel abarbeiten willst - jeder Thread die Daten unabhängig von den anderen, separat in privaten Listen sammeln.
Keine gemeinsam genutzten Datenstrukturen, kein Problem :-)
... Naja... leider nur die halbe Wahrheit. Denn du willst ja am Ende alle doch wieder in einer gemeinsamen großen Liste haben. Daher muss der parallelen Abarbeitung noch ein Schritt folgen, der die Ergebnisse der einzelnen Threads zu einem großen Ergebnis zusammenfügt.
Kurz gefasst: Spendiere jedem Thread ein privates 'MapArray' und wirf am Ende alle in ein gemeinsames. Allerdings wird hier das 'Zusammenführen' dann wieder zum Flaschenhals, der mitunter jeglichen Speedup wieder zunichte machen kann. Und genau das passiert auch!
Ich hab es mal testweise implementiert und der zusätzliche Speedup der parallelen Lösung ist sehr gering (wenige %). Gerade im Vergleich zu den obigen vorherigen Optimierungen. Es ist zwar schneller, aber nicht wesentlich. (auf einem Q9300 QuadCore) Das Zusammenführen frisst also den Speedup wirklich komplett auf.
Hier mein Snippet:
| C#-Code: |
using ColorMap = System.Collections.Generic.Dictionary<System.Drawing.Color, System.Collections.Generic.List<int>>;
private ColorMap InitializeThreadLocalMapArray()
{
var threadLocalMapArray = new ColorMap();
threadLocalMapArray[Color.Brown] = new List<int>();
threadLocalMapArray[Color.Green] = new List<int>();
threadLocalMapArray[Color.Blue] = new List<int>();
return threadLocalMapArray;
}
private ColorMap PrepareMapFromTerrainSlice(int y, ParallelLoopState state, ColorMap threadLocalMapArray)
{
var brown = threadLocalMapArray[Color.Brown];
var green = threadLocalMapArray[Color.Green];
var blue = threadLocalMapArray[Color.Blue];
for (int x = 0; x < WorldManager.Terrain.Width; x++)
{
var mapArray = GetColorListForHeight(x, y, brown, green, blue);
mapArray.Add(x);
mapArray.Add(y);
}
return threadLocalMapArray;
}
private void JoinAllMapArrays(ColorMap threadLocalMapArray)
{
lock (MapArray)
{
foreach (var color in threadLocalMapArray.Keys)
{
MapArray[color].AddRange(threadLocalMapArray[color]);
}
}
}
override public void PrepareMap()
{
MapArray[Color.Brown] = new List<int>();
MapArray[Color.Green] = new List<int>();
MapArray[Color.Blue] = new List<int>();
Parallel.For<ColorMap>(
0, WorldManager.Terrain.Height,
InitializeThreadLocalMapArray,
PrepareMapFromTerrainSlice,
JoinAllMapArrays
);
}
protected List<int> GetColorListForHeight(int x, int y, List<int> brown, List<int> green, List<int> blue)
{
var value = WorldManager.Terrain.Heightmap[y][x];
if (value > 0.8)
return brown;
else if (value > 0.5)
return green;
else
return blue;
}
|
Wie man sieht, nutze ich hier eine spezielle Überladung von Parallel.For, wo ich für jeden Thread noch etwas vorbereiten kann (das private Dictionary) und am Ende auch noch etwas Arbeit (das Zusammenführen) durchführen kann.
Bei 500x500 Maps geht fast 50% der Zeit auf das Zusammenführen in der JoinAllMapArrays-Methode.
Das ist nun nicht verwunderlich, da das AddRange fleißig alle Listen umherkopiert.
Optimieren lässt sich das nur noch, wenn du auf das Kopieren verzichtest. Also die Ergebnisse in den privaten Listen belässt und nur 'virtuelle' Gesamtlisten erstellst, die intern immernoch aus den Teillisten aufgebaut ist, statt einem riesigen Array.
Beispielsweise mit IEnumerable.Concat statt List.AddRange.
Da musst du aber schauen, ob es dir nach außen reicht, wenn dein MapArray nur IEnumerables hält.
Wenn das okay wäre, dann änder MapArray von Dictionary<Color, List<int>> auf Dictionary<Color, IEnumerable<int>> und verwende beim Zusammenführen die
Concat Methode.
| C#-Code: |
MapArray[color] = MapArray[color].Concat(threadLocalMapArray[color]);
|
Dann kostet das so gut wie keine Zeit mehr und die kannst die Parallelisierung genießen. Ich komme bei mir damit nochmal auf einen Faktor zwischen 1.5x und 2x.
beste Grüße
zommi
