Multithreading -> Instabilere Programme?
-
Shade Of Mine schrieb:
naja schrieb:
Bei 100000 Bildern würde ich es so machen, dass ich einfach gleich viele Bilder auf jeden Thread verteile. Bei 4 Kernen also 25000 Bilder pro Thread. Musst nur die Bilder so sortieren, dass jeder Thread die gleiche Datenmenge bekommt, also jeder bekommt gleich viele große, mittlere und kleine Bilder.
Und genau damit bist du schonmal deutlich langsamer als ich mit ParallelFX. Du ignorierst hier viele Sachen die Performance relevant sind. zB wenn du Pech hast, bist du keinen deut schneller als wenn du es seriell ausfuehrst weil alle grossen Bilder in einem Thread landen und die anderen nur ganz kleine bekommen.
Aber meistens hast du halt nicht 100000 Datenpakete, bei denen es so einfach ist diese zu verteilen.
Fast alle Schleifen sind so reduzierbar. Nicht alle, aber viele. Das zB mal als Ansatz.
Das hier
Parallel.ForEach(image.getPixel(), p => { p=transform(p) });geht nicht so einfach. Wenn dein transform nicht gerade eine einfache Spiegelung oder 90° Drehung ist, brauchst du immer die benachbarten Pixel. Und außerdem würde es dir den ganzen CPU Cache kaputt machen, wenn du nicht mehr durch ein Pixels Array wanderst, sondern durch ein Tasks Array und dann immer wieder ein paar Pixels holst.
Klar geht das nicht immer, aber den Cache mache ich mir nicht kaputt - dafuer habe ich ja die Library die hier eben das Aufteilen der Pixel an die einzelnen Threads uebernimmt. Natuerlich ist der Overhead groesser als wenn ich es sequentiell mache - aber das ist immer der Fall wenn ich mehrere Kerne nutze.
Wenn ich die Nachbar Pixel brauche - ist das hier uebrigens auch kein Thema - ich muss dann eben ein neues Bild erstellen und kann nicht inplace die Pixel aendern - aber ich habe ja lesezugriff auf das komplette original Bild.
Hast du schonmal einen Algorithmus zum Beareiten von Bildern geschrieben? Mit separierbaren Filtern usw. gearbeitet? Diese Lib müsste zaubern können, wenn die das alles kann, was du da beschreibst. Natürlich brauchst du ein zweites Bild in das du die Daten schreibst. Du gehst z.B. eine Zeile des Bildes durch und nimmst vom linken, rechten und aktuellen Pixel den Farbwert und schreibst den Mittelwert in das Zielbild. Jetzt gehst du ein Pixel weiter und hast mit extrem großer wahrscheinlichkeit dieses Pixel und das linke im Cache, weil du vor ein paar Operationen darauf zugegriffen hast. Generiert mir die Lib ein Codestück das dann abgearbeitet wird ohne wieder zurück zu den Tasks zu springen? Wenn du immer wieder zum Task zurück springst und dann wieder ein Pixel bearbeitest hast du mit sehr großer wahrscheinlichkeit doppelt soviele oder mehr Cache Misses wie ohne. Erklär mir doch mal wie das Schritt für Schritt ablaufen soll ohne das die ganzen Cache Misses auftreten.
100000 große unabhängige Tasks auf mehrere Threads zu verteilen ist nicht das große Problem, egal ob mit oder ohne Lib. Aber einfach zu hoffen, dass das mit jeder Schleife funktioniert wird nicht gehen. Die Tasks Idee funktioniert gut bei Tasks die die richtige größe haben, aber solche zu finden ist meistens nicht so einfach.
Und genau da erkennt man, dass du dich damit nicht tiefer beschaeftigt hast. Natuerlich kann ich die Tasks _irgendwie_ verteilen - aber bei so simplen Sachen wie dem copy_if haengt man schon mal etwas rum. Und dein images Code ist auch recht lahm und klappt nur weil du inplace operieren kannst - sobald du Daten nach aussen schreiben musst haengst du komplett.
Wenn ich nach außen schreibne muss, dann geht das ohne lib genauso wie mit. Wenn ich dabei locken muss, dann kann das die Lib auch nicht wegzaubern.
-
Es ist langweilig - du ignorierst die Punkte die du nicht widerlegen kannst und streitest dann um die Grenzfragen. Es gibt nunmal ueberall Grenzfragen aber worum es geht sind die Kernfragen - und da du diese nicht anfasst nehme ich mal an dass du sie nicht widerlegen kannst
Das reicht mir.Und implementiere mir einfach mal ein copy_if und ein unique mit Threads und ich zeig dir dann in einer Zeile Code wie ich es machen wuerde und wette dass die Performance von meiner einen Zeile Code deutlich schneller ist als das was du produziert hast.
Genau fuer soetwas hat man Libraries.
-
Shade Of Mine schrieb:
Es ist langweilig - du ignorierst die Punkte die du nicht widerlegen kannst und streitest dann um die Grenzfragen. Es gibt nunmal ueberall Grenzfragen aber worum es geht sind die Kernfragen - und da du diese nicht anfasst nehme ich mal an dass du sie nicht widerlegen kannst
Das reicht mir.Naja, Du hältst dich ja auch nur bei den spielzeugbeispielen auf. Wie parallelisierst Du denn automatisch das Filteranwenden auf ein Bild? Woher weiß die Library wie das Bild im Speicher liegt und wie man daher am geschicktesten die Aufteilung wählt, ohne sich viel mehr Cache-Misses einzufangen. Oder beispielsweise eine Matrixmultiplikation. Die sequenzielle Schleife lässt sich sehr leicht hinschreiben. Wenn man das naiv parallelisiert (und was soll die Library anderes tun) kriegt man bei einer nxn-Matrix O(n) Cache-misses pro Element.
Dass Du die Probleme nicht anerkennst heißt nicht, dass sie nicht existieren.
Natürlich ist es ein netter Ansatz sowas wie for_each mit automatischem Load-Balancing anstoßen zu können. Aber damit lassen sich eben viele Probleme nicht lösen.
-
Jester schrieb:
Naja, Du hältst dich ja auch nur bei den spielzeugbeispielen auf. Wie parallelisierst Du denn automatisch das Filteranwenden auf ein Bild? Woher weiß die Library wie das Bild im Speicher liegt und wie man daher am geschicktesten die Aufteilung wählt, ohne sich viel mehr Cache-Misses einzufangen. Oder beispielsweise eine Matrixmultiplikation. Die sequenzielle Schleife lässt sich sehr leicht hinschreiben. Wenn man das naiv parallelisiert (und was soll die Library anderes tun) kriegt man bei einer nxn-Matrix O(n) Cache-misses pro Element.
Der Programmierer muss diese Tasks erstellen - daran fuehrt kein Weg vorbei. Aber ich wiederhole mich.
Deshalb nur noch einmal:
Es geht darum in Tasks zu denken und nicht in Threads.Das ist mein Punkt. Viele Probleme lassen sich so recht leicht parallelisieren - eben weil sie sowieso nur aus Tasks bestehen. Ich hatte zB letztens eine Bildverarbeitung wo mir diese Parallelisierung enorme Runtime ersparnisse gebracht haette.
Ich habe _nie_ behauptet es geht immer und ich habe wohl oft genug erwaehnt dass wir uns am _anfang_ befinden und dass diese Libraries gerade jetzt erst nutzbar werden.
Dass Du die Probleme nicht anerkennst heißt nicht, dass sie nicht existieren.
Natürlich ist es ein netter Ansatz sowas wie for_each mit automatischem Load-Balancing anstoßen zu können. Aber damit lassen sich eben viele Probleme nicht lösen.Ich habe nie davon gesprochen dass _alles_ moeglich ist. Ich habe gesagt dass viel jetzt direkt sofort parallelisierbar ist. Und das sage ich nachdem ich durch x beliebigen Code von mir durchschaue: die meisten Schleifen sind parallelisierbar mit keinen bis geringem Aufwand.
Davon geht zB auch die MCSTL aus.
Aber ich wiederhole es nochmal gerne:
Wir stehen am Anfang von diesen Entwicklungen und Tasks sind vielleicht die falsche Einheit. Ich kann hier nur eins mit sicherheit sagen: die Threads wie wir sie jetzt kennen mit dem manuellen locking ist nicht die Antwort. Wir brauchen etwas anderes und aktuell ist ParallelFX der beste Ansatz den wir haben.Und ich fuege hinzu, dass wenn ParallelFX eine OpenSource Entwicklung fuer C++ aus der Linux/BSD Ecke waere, wir diese Diskussion nicht fuehren wuerden.
Zu sagen ParallelFX ist durch Threads ersetzbar ist einfach katastrophal falsch. Denn es ist eben nicht durch threads ersetzbar - das ist ja eines der Design kriterien gewesen.
Zu sagen ich kann nicht alles mit ParallelFX automatisiert parallelisieren ist irgendwie redundant. Denn wenn ich das koennte waere die Diskussion unnoetig. ParallelFX bietet die Tools damit der programmierer die Sachen parallelisieren kann. Wenn wir Algorithmen haben die nicht parallelisierbar sind, tja dann haben wir Pech gehabt. Worum es aber geht ist, dass alles was parallelisierbar ist, mit keinem bis geringem aufwand zu parallelisieren geht.
-
Ich will garkein copy_if oder unique einfach so mal parallelisieren, weil ich es einfach für Quatsch halte jeden Loop blind zu parallelisieren. Genauso wie ich nicht irgendwas optimiere ohne vorher nen Profiler zu verwenden.
Die Lib und die Tasks Idee mag ja ganz gut sein, aber du machst die Tasks einfach zu klein. Wenn du pro Task nur 5 Operatioen Overhead hättest, aber der Task selber auch nur 20 Operationen braucht, dann erzeugst du viel zu viel Overhead. Und die Chance, dass du den Cache kaputt machst steigt bei kleinen Tasks auch an. Wenn du bei Bilder mit Millionen von Pixeln auch genauso viele Tasks machst, hast du halt viel zu viel Overhead. Wenn du für jede Bildzeile einen Task machst, könne das schon eher sinnvoll sein.
-
Wie sollten eigentlich die Tasks für ein unique aussehen? Ich kann mir da nix ohne locking vorstellen.
-
sunshineCoder schrieb:
Wie sollten eigentlich die Tasks für ein unique aussehen? Ich kann mir da nix ohne locking vorstellen.
hash basierte partitionierung.
du packst alle typen die gleich sind eben in den selben thread - indem du das garantierst, kannst du wieder problemlos parallelisieren.
natuerlich hast du dann uU ein problem wenn du sehr viele gleiche items hast - zB wenn alle items gleich sind, dann hast du seriell gearbeitet und einige zeit fuer die partitionierung geopfert.
PS:
bzgl cache zerstoeren:
man arbeitet nicht auf index 1 dann auch index 100.000 dann auf index 12 dann auf index 2.000.000 sondern man kann auch auf index 1,2,3,4 gleichzeitig, danach auch 5,6,7,8 gleichzeitig arbeiten...
-
Shade Of Mine schrieb:
sunshineCoder schrieb:
Wie sollten eigentlich die Tasks für ein unique aussehen? Ich kann mir da nix ohne locking vorstellen.
hash basierte partitionierung.
du packst alle typen die gleich sind eben in den selben thread - indem du das garantierst, kannst du wieder problemlos parallelisieren.
Ich dachte Tasks sind keine Threads. Und wie stellst du fest was gleich ist? Das macht doch unique.
-
Gregor schrieb:
sunshineCoder schrieb:
Wird Software jetzt noch fehleranfälliger, wenn jetzt immer mehr versuchen Mulhithreading einzusetzen?
Hi. Ja.
Hi. Warum?
-
Shade Of Mine schrieb:
Deswegen arbeitet man ja wie verrueckt an besseren Techniken als diese dummen ewigen locks
ParallelFX von Microsoft sieht da schon mal nicht schlecht aus.Alternativ kann man natuerlich auch Ansaetze wie zB Erlang verfolgen. Ueber kurz oder lang werden wir aber fuer die meisten Anwendungen von den haendischen locks wegkommen.
Du meinst Erlang verdrängt C++?
-
Ist ParallelFX jetzt der große Erfolg?