Multithreading -> Instabilere Programme?

rüdiger schrieb:

und schrieb:

rüdiger schrieb:

Man kann Multithreading auch dafür nutzen, dass man stabilere Programme erzeugt.

Wie?

In dem man Multithreading für Redundanz nutzt zB.

Da fällt mir jetzt nur sowas wie in Raketen oder Flugzeugen ein, also mehrere Rechner und dann das Ergebnis nehmen das die meisten haben. Aber was bringt sowas bei einem Rechner?

Shade Of Mine

Jester schrieb:

Wie sieht denn die automatische Parallelisierung von einem einfachen Algorithmus in Erlang aus? Was passiert, wenn ich ein simples Quicksort implementiere. Wie sieht dazu die automatische Parallelisierung aus? Was passiert da parallel und was nicht?

In Erlang rufst du eher selten Funktionen auf - du sendest viel oefter Nachrichten. Ich wuerde in meiner naivitaet einfach folgendes machen: Die rekursiven aufrufe von QuickSort durch Message Passing ersetzen.

Und immer wenn die nur Nachrichten verschickst, kannst du Parallel Arbeiten. Ganz trivial ist das ganze natuerlich nicht. (ich habe jetzt 10 min ueberlegt wie man das am besten implementieren wuerde - aber da ich in Erlang nicht ganz so fit bin, bin ich am Design gescheitert :/)

Jester

Shade Of Mine schrieb:

In Erlang rufst du eher selten Funktionen auf - du sendest viel oefter Nachrichten. Ich wuerde in meiner naivitaet einfach folgendes machen: Die rekursiven aufrufe von QuickSort durch Message Passing ersetzen.

Das ist genau das wo ich Probleme bei der automatischen Parallelisierung sehe: Diese naive Parallelisierung von Quicksort skaliert nicht.

Allein das erste partitionieren, das dadurch ja nicht parallelisiert wird, benötigt O(n) Zeit. Das heißt egal wieviele Prozessoren ich Dir spendiere, es wird ab einer gewissen Sättigungsgrenze einfach nicht mehr schneller, der erste Partitionierungsschritt wird zum Flaschenhals.

Ich denke dieses Problem lässt sich am besten durch geeignete Bibliotheken umgehen, die die Algorithmen bereit stellen.

Shade Of Mine

Jester schrieb:

Ich denke dieses Problem lässt sich am besten durch geeignete Bibliotheken umgehen, die die Algorithmen bereit stellen.

PLINQ

array.AsParallel().Orderby(x => x)

Jester

Klingt nach einem guten Ansatz. Zumindest die wichtigsten Grundoperationen sollten dadurch abgedeckt werden können.

Shade Of Mine

Jester schrieb:

Klingt nach einem guten Ansatz. Zumindest die wichtigsten Grundoperationen sollten dadurch abgedeckt werden können.

Das steckt ebenfalls noch in den Kinderschuhen und mit .NET 3.5 kam die erste Version raus. LINQ sagt dir uU etwas - query syntax auf Datenstrukturen.

Danach ging man einen Schritt weiter und hat PLINQ entwickelt (wobei PLINQ seit 2005 in Entwicklung ist) um eben solche Sachen parallelisieren zu koennen.

Was aber wieder fehlt ist eine Garantie dass der Code wenn er parallel ablaeuft nicht durch Seiteneffekte kaputt gemacht wird. Weiters glaube ich, dass (P)LINQ keine Inplace Operationen machen kann. Sprich man hat enormen Speicherverbrauch

Ideal ist es also noch lange nicht - aber die unterliegende Technik ist ziemlich interessant. PLINQ basiert auf der TPL.

TPL (Task Parallel Library) ist die Library um das Subsystem in .NET dass die komplette Parallelisierung uebernimmt. Ein Parallel.forEach oder ein PLINQ Query machen nichts anderes als eine Menge kleiner Tasks zu erstellen - die Arbeit also in kleine Stueckchen zu schneiden. Diese Tasks werden dann je nach Plattform parallelisiert.

Worum es nun geht ist, den Programmierern die Tools zu geben um solche Tasks moeglichst automatisiert zu erstellen. PLINQ ist da recht nett - man macht Queries auf Datenstrukturen und diese koennen dann Parallel ablaufen. Aber wie dein QuickSort Beispiel ja zeigt - so einfach ist das nicht immer. Denn man wird immer Algorithmen haben die man selber Parallelisieren muss und das suckt.

Aber die Ansaetze sind ja schonmal da - wenn wir zB von einem Binary Tree ausgehen und wir wollen alle Elemente aufsummieren:

int sum() {
  return left.sum()+right.sum();
}

dann bietet uns ParallelFX folgendes nettes:

int sum() {
  int r,l;
  Parallel.Do(
    delegate { l=left.sum(); }
    delegate { r=right.sum(); }
  );
  return l+r;
}

Wobei man hier natuerlich aufpassen muss, dass man nicht zuviel Zeit mit dem Schedulen verbringt und man Sequentiell nicht schneller waere - da Threads ja doch Overhead bringen.

Ich bin jedenfalls gespannt was es noch so alles geben wird - denn momentan gibt es verschiedene interessante Ansaetze - aber das wichtigste fehlt noch: die Garantie dass Seiteneffekte den Code nicht zerstoeren.

Automatische Parallelisieurng funktioniert wahrscheinlich genauso gut wie automatisch Programme schreiben lassen. Parallelisierung ist bei nicht standard Sachen meistens was das vom Mensch besser erkannt wird als vom PC, weil der PC den Sinn des Programms nicht versteht. Woher soll der PC z.B. wissen, dass ein Thread den oberen und ein Thread den unteren Teil eines Bildes bearbeiten kann? Da müsste er ja erst mal wissen was ein Bild ist.

Eben. Man muss schon Funktionen vorgeben, die parallel laufen sollen. Und dann kann man auch gleich eine normale thread-library nehmen (z.B. boost::thread). Da brauch man kein parallelfx & Co.

Shade Of Mine

naja schrieb:

Automatische Parallelisieurng funktioniert wahrscheinlich genauso gut wie automatisch Programme schreiben lassen. Parallelisierung ist bei nicht standard Sachen meistens was das vom Mensch besser erkannt wird als vom PC, weil der PC den Sinn des Programms nicht versteht. Woher soll der PC z.B. wissen, dass ein Thread den oberen und ein Thread den unteren Teil eines Bildes bearbeiten kann? Da müsste er ja erst mal wissen was ein Bild ist.

Nein muss er nicht. Er muss nur wissen ob 2 Funktionen einander beeinflussen. Wenn wir zB von Haskell ausgehen - dort gibt es praktisch keinen shared state - so kann dort Problemlos parallelisiert werden.

Natuerlich ist das nur ein Teil der Parallelisierung die wir brauchen. Wo die Entwicklung hingeht ist die parallelisierung von Algorithmen. Beispielsweise Map/Reduce zur verarbeitung von Daten oder eben alternativen zu Sortieralgorithmen wie QuickSort. Jester hat da vor ein paar Jahren beim Forentreffen zB Super Scalar Sample Sort vorgestellt.

Aber genau wegen sowas gibt es ja Abstraktion. Ich rufe nicht "QuickSort" auf, sondern "sort". Gerade bei den Algorithem gibt es viel Potential und Tools wie PLINQ sind eben ein Ansatz dieses leichter zu entfalten. Wir stehen aber erst am Anfang von dem was moeglich ist.

Was Tools wie ParallelFX oder auch MCSTL bieten ist eine Vereinfachung der Parallelisierung. Keines dieser Tools kann Zaubern. Aber sie uebernehmen enorm komplexe Aufgaben was Load Balancing und Locking betrifft. Load Balancing ist zB wieder ein enorm wichtiges Thema - auf Single Core CPUs war es das nicht, da ja alles was man rechnen musste auf der einen CPU ablief - jetzt mit 2,4,8,... CPUs muss man ploetzlich die einzelnen Worker Threads Load Balancen - ParallelFX bietet hier eben ein "Work Stealing System" das das Balancen uebernimmt (zumindest einen Teil davon. Andere Sachen wie eben das Partitionieren des WorkLoads uebernimmt zB PLINQ oder der Programmierer selber).

Aber auch das Partitionieren ist kein einfaches Thema und das Mergen am Ende der Arbeit ist auch nicht trivial.

Man braucht Tools die das automatisieren. Natuerlich ist ParallelFX prinzipiell schlecht weil es von Microsoft kommt - aber soweit ich sehe ist es das aktuell weitest entwickelte Tool. Andere werden folgen und uU auch ParallelFX in den Schatten stellen.

Worum es aber geht ist, diese Tools zu verlangen. Wir brauchen diese Automatisierungen. Es steckt soviel Parallelisierungspotential in unserem Code das wir sofort nutzen koennten. Fuer andere Sachen muessen wir unseren Programmierstil oder unsere Algorithmen/Datenstrukturen aendern - aber viel ist mit guten Libraries jetzt schon machbar.

Ich kann mir nicht wirklich vorstellen, dass das so einfach klappt. Mal abgesehen davon, dass in der praxis kaum Haskell, sondern mehr C++, C# und Java und ähnliches eingesetzt wird. Bei normal geschriebnem Code ist es doch so, dass eine Funktion was berechnet und die nächste dann mit diesen Ergebnissen weiterarbeitet. Da kannst du schon mal garnicht beide gleichzeitig ausführen lassen.

Das größte Parallelisierungspotential steck halt darin große Datenmenge aufzuteilen, aber ob sowas einfach geht, weiß halt keine Sprache oder Compiler. Klar kann man irgendwie sowas schreiben

doParallel(function(data1), function(data2))

Aber das sich die Funktionen nicht stören muss schon der Programmierer wissen. Und so ne doParallel Funktion zu schreiben ist ja auch nicht so schwer.

Wahrscheinlich wird es schon bald ein paar Libs geben, die standard Sachen wie Sort parallelisieren können, aber die komplizierten Sachen muss schon der Programmierer machen (die Libs macht ja auch einer).

Shade Of Mine

Und genau da liegst du falsch. PLINQ erfuellt bereits fast alle Anforderungen an Arbeiten mit Datensets.

Und enorm viele Sachen sind Parallelisierbar - schau dir einfach nur mal die Schleifen an die du in deinem Code hast. Ein nicht unrelevanter Teil davon ist jetzt parallelisierbar oder mit kleinen Aenderungen parallelisierbar.

Nahezu alle STL Algos sind parallelisierbar. Das Problem ist das fehlen an Tools dafuer. Ein simpler for Loop ist ohne Tools nicht so einfach parallelisierbar weil einem die Infrastruktur killt.

Wir muessen lediglich von der Idee in Threads zu denken weggehen. Deshalb finde ich den ParallelFX Ansatz ganz interessant. Jede Aufgabe wird in kleinere Aufgaben aufgeteilt und diese dann irgendwie verarbeitet. Ich muss also nur ein "Tasks" denken. Die Idee dahinter ist locking freier Concurrent Code.

Klar ist noch nicht alles machbar - aber wir stehen hier auch am Anfang. Was sich noch alles ergeben wird weiss noch Niemand. Aber jeder Programmierer sollte sich dennoch Gedanken machen: wie koennen meine Anwendungen 32 Prozessoren benutzen? Threads sind hier der falsche Ansatz. Denn 32 Threads auf einem 2 Kern System ist eine Katastrophe und 2 Threads auf einem 32 Kern System ebenso. Aber auch 32 Threads auf einem 32 Kern System ist nicht unbedingt das gelbe vom Ei (denn X Kerne koennen ja komplett ausgelastet sein durch andere Anwendungen).

Wir muessen also in anderen Bahnen denken. ParallelFX geht den Weg in Tasks zu denken. uU ist das Bloedsinn und in ein paar Jahren wissen wir dass das der falsche Ansatz war - aber irgendwohin muessen wir ja arbeiten.

Mal ein Beispiel. Es gibt ne Message Queue und die Messages werden in ner Schleife abgearbeitet. So jetzt sag ich dem Framework mach das mal parallel für jede Message nen Task und das macht das auch schön. Das Problem ist nur, das Farmework weiß garnicht, dass die Reichenfolge wichtig ist und die ganze Anwendung nicht mehr geht, wenn man das durcheinander abarbeitet. Das muss ich als Programmierer wissen und entsprechend darauf achten, sowas kann mir kein Framework abnehmen. Einfach nur Task statt Thread zu sagen hilft da nicht viel.

Klar kann das Framework schauen wieviele Kerne mein System hat und dann die Daten aus ner Collection entsprechend verteilen. Das ist aber der einfachere Teil der Arbeit.

Das wissen, dass Daten parallel abgearbeitet werden können kommt vom Programmierer. Sowas zu analysieren kann extrem komplex sein. Hier keinen Fehler zu machen und irgendeinen Nebeneffekt zu übersehen kann mir kein Framework abnehmen. Und einfach mal hergehen und alle Schleifen zu parallelisieren, bei denen es einfach geht, halte ich für genauso sinnvoll, wie zu optimieren ohne vorher nen Profiler zu verwenden. Der Programmierer muss wissen, wo es sinnvoll ist zu parallelisieren. Wenn du z.B. ein Bild skalieren willst und einfach mal die Schleife im Kernel (der Teil der die Bilddaten interpoliert) parallelisierst, dann wird das nicht viel bringen, weil da immer nur ein paar Pixel abgearbeitet werden und das Aufteilen in Tasks/Threads dann nur mehr Zeit braucht, als der eigentliche Schleifendurchlauf. Da ist es sicher schlauer das Bild in n Teile aufzuteilen und die parallel abzuarbeiten, aber sowas weiß kein Framework oder Compiler.

Irgendwelche standard Algorithmen zu parallelisieren wird bald keinen mehr interessieren, weils sowas schon fertig geben wird. Genauso wie es jetzt schon Quicksort fertig gibt und dich keiner bezahlt um diesen zu entwickeln.

Shade Of Mine

naja schrieb:

Einfach nur Task statt Thread zu sagen hilft da nicht viel.

Du hast nichts von dem verstanden was ich gesagt habe

'threads' sind ja diese dinger, mit denen man manuell die CPU-ressourcen aufteilt. diese, rein technische sichtweise des händischen und statischen zerstückelns von rechenzeit, ist wohl das, was du (shade'o'mine), mit dem begriff 'task' abmildern willst. nenn' es doch 'prozess'. so wird's z.b. im umfeld von hardwarebeschreibungssprachen genannt. da ist es gang und gebe, dass sich viel paralleles und nebenläufiges zeug abspielt (was für die denke reiner softwerker, mit ihren auf sequentiellen code ausgelegten programmiersprachen, erstmal eine grosse hürde ist).

Dann bring doch mal ein Beispiel was der Unterschied zwischen Task und Thread sein soll und was dann besser und einfacher ist.

So einfach wie bei Hardware kleinste Teile parallel ablaufen lassen geht halt bei Software nicht einfach mit ner Lib. Da brauchst du schon mal Unterstützung vom Betriebssystem und obs dann einfach geht bin ich mir auch nicht sicher.

Shade Of Mine

concurrent-freak schrieb:

'threads' sind ja diese dinger, mit denen man manuell die CPU-ressourcen aufteilt. diese, rein technische sichtweise des händischen und statischen zerstückelns von rechenzeit, ist wohl das, was du (shade'o'mine), mit dem begriff 'task' abmildern willst. nenn' es doch 'prozess'. so wird's z.b. im umfeld von hardwarebeschreibungssprachen genannt. da ist es gang und gebe, dass sich viel paralleles und nebenläufiges zeug abspielt (was für die denke reiner softwerker, mit ihren auf sequentiellen code ausgelegten programmiersprachen, erstmal eine grosse hürde ist).

Task ist das englische Wort fuer Prozess. Nenn es halt Prozess - Namen sind Schall und Rauch.

Frueher hat man nur von Taks gesprochen - Threads sind relativ neu. Damals hatte man schon interessante Systeme aber die Tasks im Sinne von ParallelFX sind keine Tasks im Sinne von Prozessen. Ich wuerde es eher mit Aufgaben uebersetzen. In gewissem Sinne sind sie leichgewichtige Prozesse.

Es geht dabei darum grosse Arbeitsschnitte in kleine zu zerlegen. Wenn man mit funktionalen Sprachen zu tun hatte, dann wird man das eher verstehen. Jede Aufgabe fuer sich ist eine abgeschlossene Einheit - eben eine Funktion im funktionalen Sinn. Eine Aufgabe hat Input und produziert Output und das ganze ohne Abhaengigkeiten untereinander. Die schwierigkeit ist eben zu garantieren dass diese Abhaengigkeiten nicht bestehen. Da steckt man aktuell fest.

Wenn man nun aber eine handvoll Aufgaben generieren kann - was oft sehr einfach ist - manchmal aber enorm schwer - dann kann das vom System problemlos parallelisiert werden. Wobei eine Aufgabe nichts mit einem Thread zu tun hat. Das ganze kann komplett seriell ablaufen - das ist den Tasks egal. Meistens will man auch nicht 1 Thread pro Task haben. Man will 100 und mehr Tasks pro Thread haben.

Sehen wir uns einmal an was ein Task, eine Aufgabe eigentlich ist:

vector<Image> images;
fill(images);
//wir haben nun eine menge bilder in unserem vector
//jetzt wollen wir die bilder analysieren und alle bilder
//mit bestimmten merkmalen naeher betrachten und den
//rest wegwerfen
copy_if(images.begin(), images.end(), out.begin(), foo);
//und nun die bilder transformieren
apply(out.begin(), out.end(), bar);

Das ganze ist 100% parallelisierbar aber der Aufwand das wirklich zu parallelisieren ist enorm. Denn fuer jedes der 100.000 Bilder einen Thread erstellen waere Schwachsinn, also erstellen wir einfach soviele Threads wie wir CPU Kerne haben. Und schon haben wir wieder ein Problem: je nachdem wie gross ein Bild ist, desto laenger dauert es das Bild zu bearbeiten. Wir brauchen also Load Balancing Algorithmen.

Dann muessen wir uns um das locken beim merge kuemmern und wir sind rasch auf ueber 100 Zeilen oben.

Wir brauchen also definitiv libraries die uns diese Parallelisierungsarbeit abnehmen. Komplett automatisiert koennen diese Tools natuerlich nicht arbeiten - irgendwo muss der Programmierer schon noch selber agieren und sagen was parallelisierbar ist und was nicht.

Indem wir aber in solchen Tasks denken (ob das sinnvoll ist oder nicht wird die Zeit zeigen - im Moment stehen wir am Anfang) koennen wir parallelisierung leicht ermoeglichen.

foo und bar koennen jeweils problemlos zu einem Task werden. Und ein Task kann natuerlich selber aus Tasks bestehen. bar verwendet zB fuer jeden Pixel einen eigenen Task. Ist ja ganz einfach moeglich:

Parallel.ForEach(image.getPixel(), p => { p=transform(p) });

Das wichtige dabei: wir haben den Code parallelisiert. Nicht zu 100% denn foo und transform koennen uU noch parallelisiert werden - aber es ist ein Anfang. Und vorallem: mit kaum Aufwand von uns als Programmierer.

Wenn wir in Threads denken wuerden, waere eine parallelisierung hier nur mit riesen Aufwand moeglich. Wenn wir aber in Tasks denken, ist das ganze kein Problem mehr. Oder besser gesagt: nicht mehr unser Problem sondern dass der ParallelFX Entwickler.

uU ist dieser Ansatz in Tasks zu denken problematisch und wir sind in ein paar Jahren darueber hinaus. uU ist ParallelFX vom Ansatz her komplett falsch. Aber irgendetwas in diese Richtung brauchen wir. Oder mal ganz ehrlich: wer von euch programmiert gerne Multithreaded Systeme und vorallem: wer debugt sie gerne?

Threads sind nicht die Antwort und IMHO ist der naechste Schritt eben Aufgaben/Tasks. Wobei X Tasks in Y Threads ablaufen. Indem wir einfach garantieren dass ein Task keine Seiteneffekte hat sparen wir uns komplett das locking.

Natuerlich kann man immernoch mist bauen - aber das wiederhole ich ja auch oft genug: die Tools koennen (noch) nicht garantieren dass ein Task keine Seiteneffekte hat die andere Tasks beeinflussen. Aber wenn wir uns Haskell und aehnliche Sprachen ansehen -> gerade bei kleinen Funktionen ist es leicht ohne Seiteneffekte auszukommen. In den meisten Faellen ist es also kein Problem einen Task zu schreiben der keine Seiteneffekte hat.

DEvent

Am coolsten waere es doch wenn man (man Java Beispiel) einfach eine Anotation schreiben wuerde und mir der Jit Compiler die Methode parallelisiert.

class Foo
{
    @parallel
    void foo() {}

    @parallel
    void bar() {}
}

Vielleicht auch die ganze Klasse als @parallel markieren und alles was da drinner berechnet wird kann der Jit Compiler parallelisieren. Ich als Programmierer muss dann halt dafuer garantieren das die Klasse/Methoden keine Seiteneffekte haben.

Noch cooler waere sowas wie "const-correctness" in C/C++, nur eben eine "parallelisierbar-correctness", also das der Compiler ueberpruefen kann das der Code keine Seiteneffekte hat.

Aber kann man eigentlich C++/Java so ummodeln, dass der Compiler immer annimmt das es keine Seiteneffekte gibt, ausser man sagt explizit das es welche gibt? Man tauscht einfach den Compiler aus und fuer ein neues keyword "siteeffect" ein, das angibt das der Code Seiteneffekte hat.

Ok, Tasks sollen also viele kleine Aufgaben sein, die dann die Lib auf ein paar Threads verteilt und somit das Skalieren übernimmt.

Shade Of Mine schrieb:

Wenn man nun aber eine handvoll Aufgaben generieren kann - was oft sehr einfach ist - manchmal aber enorm schwer - dann kann das vom System problemlos parallelisiert werden. Wobei eine Aufgabe nichts mit einem Thread zu tun hat. Das ganze kann komplett seriell ablaufen - das ist den Tasks egal. Meistens will man auch nicht 1 Thread pro Task haben. Man will 100 und mehr Tasks pro Thread haben.

Glaub ich nicht, ich denke in den meisten Fällen ist es extrem schwer solche Tasks zu definieren, die dann beliebig verteilt werden können, vorallem, wenn sie klein sein sollen.

vector<Image> images;
fill(images);
//wir haben nun eine menge bilder in unserem vector
//jetzt wollen wir die bilder analysieren und alle bilder
//mit bestimmten merkmalen naeher betrachten und den
//rest wegwerfen
copy_if(images.begin(), images.end(), out.begin(), foo);
//und nun die bilder transformieren
apply(out.begin(), out.end(), bar);
Das ganze ist 100% parallelisierbar aber der Aufwand das wirklich zu parallelisieren ist enorm. Denn fuer jedes der 100.000 Bilder einen Thread erstellen waere Schwachsinn, also erstellen wir einfach soviele Threads wie wir CPU Kerne haben. Und schon haben wir wieder ein Problem: je nachdem wie gross ein Bild ist, desto laenger dauert es das Bild zu bearbeiten. Wir brauchen also Load Balancing Algorithmen.

Dann muessen wir uns um das locken beim merge kuemmern und wir sind rasch auf ueber 100 Zeilen oben.

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.

vector<Image> images;
fill(images);
distribute(images); //gleichmäßig verteilen
int numCores=GetNumCores();
int numImages = images.size();
int imagesPerThread = numImages / numCores + 1;
std::vector<Thread> threads;
for(int t = 0; t<numCores; t++) {
	int begin = imagesPerThread*t;
	int end = imagesPerThread*(t+1)<numImages ? imagesPerThread*(t+1) : numImages;
	threads.push_back(StartThread(begin, end, images);
}
WaitFor(threads);

WorkThread(int begin, int end, vector<Image>& images) {
	for(int i = begin, i<end; i++) {
		if(foo(images[i]) {
			apply(images[i]);
		}
	}
}

Da brauch ich nichts locken oder mergen und hab auch keine 100 Zeilen.

Gut, das war jetzt ein einfaches Beispiel und die Images sind sozusagen die Tasks und die Lib könnte das mit dem verteilen auf die Cores übernehmen, wird hier keinen Geschwindigkeitsunterschied machen.

Aber meistens hast du halt nicht 100000 Datenpakete, bei denen es so einfach ist diese zu verteilen.

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. Da wirst du bei einem Thread durch den ganzen Tasks Overhead wahrscheinlich um mehr als das doppelte langsamer. Wenn du ein Bild mit mehreren Threads bearbeiten willst, musst du dir schon mehr überlegen, damit du nicht durch irgendwelche Seiteneffekte wieder alles langsamer machst.

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.

Shade Of Mine

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.

Was wenn du ein paar Kerne nicht nutzen kannst - dann hast du sinnlos viele Context Switche.

Der Code ist tragbar so wie er ist, aber gut ist er nicht. Und er funktioniert nur zufaellig, weil du die images inplace bearbeiten kannst - ich habe aber extra noch ein copy_if ins Beispiel dazu genommen wo du es nicht mehr schaffst.

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.

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.

Natuerlich kann man einen load balancer schreiben und den verwenden, und dann eben alles inplace machen - doch wozu? du wirst mit grosser wahrscheinlichkeit langsamer sein als parallelfx und weit aus weniger flexibel.

Genau fuer soetwas gibt es libraries - und wenn ParallelFX eine opensource Loesung fuer C++ waere, wuerden wir diese Diskussion nicht fuehren

Eine kleine Denkaufgabe da es ja so trivial ist:
kannst du mir mal kurz ein std::unique fuer beliebige Kerne implementieren?

Das fiese ist naemlich wenn du ploetzlich nicht mehr dumm partitionieren kannst und intelligente algos brauchst. Denn gleiche Items muessen ploetzlich in dem selben Thread landen...

Es hat schon seinen Grund warum in der Library eine Menge Mann-Jahre stecken und es erst langsam verwendbar wird. Weil es eben _nicht_ trivial ist.

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.

Multithreading -&gt; Instabilere Programme?

Multithreading -> Instabilere Programme?