threading Problem

knivil

Eine Antwort auf deine Fragen: Quick and dirty.

1.) Rekursion: Jeder hat seine eigenen lokalen Variablen, was du mit a und b haendisch einbaust. Divide and Conquer Ansatz ist sehr einfach zu parallelisieren.
1a.) Ich brauche keinerlei Synchronisationsprimitive, d.h. keine Deadlock, keine Threads denen ein Signal geschickt wird, keine Mutex/Conditions, ... It is a no-brainer.
2.) async launch policy: Ich lasse das System entscheiden. Auch sollte die default policy asynchron sein. Es gibt pathologische Faelle aber ich hoffe sie werden vom ueberarbeiteten Standard revidiert.
3.) Threads, die nichts machen: Normalerweise sollte der Rechenaufwand im Vergleich zur Erzeugung sehr gross sein. Bei deinem Spielzeugbeispiel kann das schlecht demonstriert werden. Die paar zusaetslichen Hardwarethreads sind jetzt nicht so wild. Auch kannst du gern erst die Bereiche festlegen, und in einer Schleife fuer jeden Bereich einen Thread starten.
4.) Threadpools: Threadpools haben andere Probleme.

Deine Argumentation laeuft Richtung PPL (parallel pattern library) oder TBB (threading building blocks). Schau dir die doch mal an.

Übrigens läuft dein Algo nur mit random access Iteratoren.

Mir egal, da ansonsten sowieso die Parallelisierung durch std::distance und std::advance aufgefressen wird.

Was mich hauptsaechlich stoert ist, dass bei dir Algorithmus und Parallelisierung sehr verschachtelt sind. Das kann manchmal nicht vermieden werden, aber in diesem Fall ist Parallelisierungsstrategie und Algorithmus sehr gut trennbar.

SeppJ

Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches

std::advance(mid, std::distance(start, end) / 2);

mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.

Stefan schrieb:

Ich will 1 Thread pro CPU-Kern haben, nicht mehr, und die sollen immer schön gefüttert werden.

War vielleicht früher so. Bei Threads gilt lieber zu viel als zu wenig.

__Stefan__

SeppJ schrieb:

Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches
std::advance(mid, std::distance(start, end) / 2);
mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.

Ach komm, das holst du durchs Multithreading wieder rein. Wie willst du sonst z.B. ein paralleles for_each implementieren, das mit einer Liste läuft?

Stefan schrieb:

SeppJ schrieb:
Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches
std::advance(mid, std::distance(start, end) / 2);
mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.
Ach komm, das holst du durchs Multithreading wieder rein. Wie willst du sonst z.B. ein paralleles for_each implementieren, das mit einer Liste läuft?

lol? Du schreibst 2x std::distance(linkedlist.begin(), linkedlist.end()), da wird die Linkedlist pro Funktion 2x vollständig durchlaufen, insg. 4x. Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

knivil

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste. Und der Speedup haengt vom Arbeitsaufwand der einzelnen Threads ab.

Ansonsten ist die Aussage natuerlich sehr naiv:

Ach komm, das holst du durchs Multithreading wieder rein.

There is no silver bullet. And there is no spoon.

knivil schrieb:

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste.

Aber zu Beginn schon. Einmal 2 ganze Durchläufe (2), einmal 2 halbe (1), dann 1/2, dann 1/4 (wird alles sequenziell abgelaufen), macht insgesamt 4 volle Durchläufe nacheinander angenommen es ist perfekt auf unendlich CPUs verteilt.

__Stefan__

knivil schrieb:

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Wieseo Bäume? Die haben doch auch kein random access.

knivil schrieb:

Ansonsten ist die Aussage natuerlich sehr naiv:

Ach komm, das holst du durchs Multithreading wieder rein.

There is no silver bullet. And there is no spoon.

Wichtig ist dass die Algorithmen skalieren. Eines Tages werden Wir Desktop-CPUs mit 128 Kernen haben. Die Parallelisierung hat natürlich einen Overhead der sich bei wenigen Kernen stärker bemerkbar macht.

SeppJ

knilch schrieb:

knivil schrieb:

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste.

Aber zu Beginn schon. Einmal 2 ganze Durchläufe (2), einmal 2 halbe (1), dann 1/2, dann 1/4 (wird alles sequenziell abgelaufen), macht insgesamt 4 volle Durchläufe nacheinander angenommen es ist perfekt auf unendlich CPUs verteilt.

Was übrigens noch toller wird, wenn man bedenkt, dass der Zweck der hier gezeigten Parallelisierung ist, dass man das Ablaufen der gesamten Liste verteilt. Stattdessen hätte man (ohne random access) das Ablaufen der gesamten Liste vervielfacht.
Diese Idee der Parallelisierung bringt daher nur etwas, wenn die Iteratoren random access sind, es ist daher ungerechtfertigt, sich zu beschweren, dass knivils Lösung diese voraussetzt.

Stefan schrieb:

knivil schrieb:

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Wieseo Bäume? Die haben doch auch kein random access.

Aber logarithmisch ist immer noch viel besser als linear. Außerdem bietet sich die Baumstruktur ganz natürlich für Divide & Conquer an.

Wichtig ist dass die Algorithmen skalieren.

Und wir sagen dir, dass du es ordentlich machen musst, damit es skaliert. Paralleisierung ist kein Zauberspruch, der alles schneller macht, wenn man nur genügend Kerne hat. Im Gegenteil, es kann ganz leicht passieren, dass etwas langsamer wird (zum Beispiel dein Programm), wenn man es nicht ordentlich macht.

Eines Tages werden Wir Desktop-CPUs mit 128 Kernen haben. Die Parallelisierung hat natürlich einen Overhead der sich bei wenigen Kernen stärker bemerkbar macht.

Du hast es genau falsch rum. Je mehr du parallelisierst, desto mehr Overhead hast du. Das heißt, du musst ganz besonders gut skalierende Algorithmen haben. Das heißt, die obigen Kritikpunkte an deiner Lösung wiegen viel schwerer.

__Stefan__

Ich glaube ich werde es mal messen.

Stefan schrieb:

Ich glaube ich werde es mal messen.

Ja, aber bitte ohne sleep.

knivil

Um nochmal klarzustellen: Ich habe Templatest verwendet, um mir Schreibarbeit bei den Typen/Iteratoren zu sparen. Das ganze wurde fuer std::vector<int> gebastelt und getestet. Bei anderen gibt es wahrscheinlich Fehlermeldungen. Auch habe ich mich am Orginalprogramm orientiert.

Ich sehe beim urspruenglichen Code zwei Probleme:

1. In accumulate wird unsynchronisiert von mehreren threads auf den nicht thread sicheren std::vector zugegriffen. Da dort die Iteratoren unsynchronisiert modifiziert werden, kann es dort zu Fehlern kommen. Warhscheinlich ist das der Grund fuer den Absturz, aber genau findest Du das nur mit einem Debugger heraus.

threadpool::run() ist so implementiert, dass wenn der Pool voll ist eine lang laufende Methode, die dann eingespeist wird, den Pool blockiert, selbst wenn alle pool-threads fertig sind. So kannst Du den Pool nur dann nutzen, wenn eine thread des Pools gerade idle ist, ansonsten wird alles serialisiert.

3. In einer multi-threaded Umgebung wird Dir die try_run Methode nicht viel nutzen, da die Information nach dem Aufruf schon veraltet ist.

4. Du gibst schedule() run() und try_run() Referenzen auf ein task-Objekt, das aber ggf. nicht mehr existiert. Das macht die Nutzung Deines Pools fehleranfaellig.

SeppJ

treader schrieb:

1. In accumulate wird unsynchronisiert von mehreren threads auf den nicht thread sicheren std::vector zugegriffen. Da dort die Iteratoren unsynchronisiert modifiziert werden, kann es dort zu Fehlern kommen. Warhscheinlich ist das der Grund fuer den Absturz, aber genau findest Du das nur mit einem Debugger heraus.

Das wird aber vom Standard garantiert, dass dies möglich ist. Es ist absolut ok, gleichzeitig lesend auf das selber Element zuzugreifen. Aber er tut dies noch nicht einmal, da jedes Element genau einmal von einem der Threads angefasst wird. Die Iteratoren darf er ebenfalls ändern wie er lustig ist, diese sind schließlich threadlokal.

Ich kann zwar nicht genau sagen, was der Fehler ist (da er bei mir nicht auftritt), aber dies ist es nicht.

__Stefan__

treader schrieb:

Ich sehe beim urspruenglichen Code zwei Probleme:

threadpool::run() ist so implementiert, dass wenn der Pool voll ist eine lang laufende Methode, die dann eingespeist wird, den Pool blockiert, selbst wenn alle pool-threads fertig sind. So kannst Du den Pool nur dann nutzen, wenn eine thread des Pools gerade idle ist, ansonsten wird alles serialisiert.

Die Idee von run() ist, dass der Task im this_thread ausgeführt wird, wenn kein Worker frei ist. Der Thread soll arbeiten, nicht warten.
Edit: Bei einem rekursiven Algorithmus könnte das warten den Algorithmus blockieren.
Alternativ kann man machen

if(!pool.try_run(task)) task.run();

was genau das gleiche ist.

Der Mutex dort wird übrigens vorher geunlockt, da blockiert nichts während der ausführung des Tasks.

treader schrieb:

3. In einer multi-threaded Umgebung wird Dir die try_run Methode nicht viel nutzen, da die Information nach dem Aufruf schon veraltet ist.

Die Methode ist eher eine Alternative zu run(), siehe obiges Beispiel.

treader schrieb:

4. Du gibst schedule() run() und try_run() Referenzen auf ein task-Objekt, das aber ggf. nicht mehr existiert. Das macht die Nutzung Deines Pools fehleranfaellig.

Der Task muss natürlich bis nach der Abarbeitung existieren:

task t1(...);
  pool.schedule(t1);
  task t2(...);
  pool.schedule(t2);
  t1.wait();
  t2.wait();

Mittlerweile verwende ich sowieso Futures und übergebe dem Pool packaged_task per move, dann kann man die Tasks auch vergessen wenn sie dem Pool übergeben wurden.

Stefan schrieb:

Die Idee von run() ist, dass der Task im this_thread ausgeführt wird, wenn kein Worker frei ist. Der Thread soll arbeiten, nicht warten.
Edit: Bei einem rekursiven Algorithmus könnte das warten den Algorithmus blockieren.
Alternativ kann man machen
C++:
if(!pool.try_run(task)) task.run();

was genau das gleiche ist.

Der Mutex dort wird übrigens vorher geunlockt, da blockiert nichts während der ausführung des Tasks.

Ich versuche es mal mit einem einfachen Beispiel: Du hast einen threadpool mit vier threads. Jetzt speist Du vier tasks ein, die jeder eine Sekunde laufen. 100ms spaeter rufst du run() mit einer task auf, die eine Stunde laeuft. Nach 900ms laeuft dann nur noch die letzte task (direkt in run() im Hauptthread) und Du kannst keine weiteren tasks mehr einspeisen bis die run-Methode zurueck kehrt. Es sei denn, Du hast in einem anderen Thread Deinen Pool ebenfalls bekannt gemacht.

Besser ist es, immer den task in die queue zu stellen, so kannst Du sicher sein, dass jeder frei werdende task das naechste Element bearbeitet, und vom Hauptthread (oder anderen, die den pool nutzen) kannst Du immer etwas in den pool zur Bearbeitung einstellen

__Stefan__

treader schrieb:

Besser ist es, immer den task in die queue zu stellen, so kannst Du sicher sein, dass jeder frei werdende task das naechste Element bearbeitet, und vom Hauptthread (oder anderen, die den pool nutzen) kannst Du immer etwas in den pool zur Bearbeitung einstellen

Das ist sicher wünschenswert, aber was machst du, wenn du einen Task hast, der wiederum einen Task erzeugt?

void useless(int depth, thread_pool& pool)
{
	if(depth > 0)
	{
		task t(useless, depth - 1, std::ref(pool));
		pool.schedule(t);
		t.wait();
	}
}
int main()
{
  thread_pool pool(8);

  useless(10, pool);

  return 0;
}

Wenn nicht genügend Worker vorhanden sind, blockiert sich das. Wenn du aber folgendes machst, dann läuft es sicher durch:

void useless(int depth, thread_pool& pool)
{
	if(depth > 0)
	{
		task t(useless, depth - 1, std::ref(pool));

                pool.run(t); // erzeugt nur Task wenn Thread frei

		t.wait();
	}
}
int main()
{
  thread_pool pool(8);

  useless(10, pool);

  return 0;
}

SeppJ

Stefan schrieb:

Wenn nicht genügend Worker vorhanden sind, blockiert sich das.

Richtig, das blockiert. Dein Ansatz ist jedoch keine gute Lösung, wie threader mit seinem Beispiel erklärte. Ein besserer Ansatz wäre, an dem Punkt "genügend Worker" anzusetzen: Wenn ein Thread blockiert (zum Beispiel, weil er auf Untertasks wartet), dann wird dem Pool ein neuer Thread hinzugefügt, der eine Task abarbeitet. Später, wenn wieder alle Threads arbeiten, wird ein Thread zerstört, so dass du dich wieder der hardwareabhängigen Optimalzahl näherst, bei der pro Kern ein Thread aktiv(!) ist. "aktiv" ist hier das wichtige Stichwort, wir wollen schließlich keinen Kern blockieren, daher der Ansatz, bei Blockierung einen neuen, aktiven Thread zu erzeugen.

Tipps zur Implementierung dieser Technik findest du in Literatur zu Threadpools.

Eine Frage habe ich noch zum urspruenglichen Code:

Warum wird in schedule() (und in run() auch) ein notify_all() verwendet?

void schedule(task& t)
    {
        std::unique_lock<std::mutex> lock(m_mutex);

        m_queue.push(&t);
        m_cond.notify_all();
    }

Ich wuerde ein notify_one() an der Stelle einsetzen, da ja nur fuer einen Thread neue Arbeit da ist.

threader schrieb:

Eine Frage habe ich noch zum urspruenglichen Code:

Der ursprüngliche Code ist schrecklich. Es wimmelt vor std::lock_guard<std::mutex> , auch an Stellen, an denen es gar nicht nötig wäre. Code mit Mutexen ist nicht multithreaded.

Angenommen, der Ansatz wäre so gewollt (was er nicht ist).

Dann:
- Als queue eine lock-free queue nehmen (boost hat da eine)
- Als m_idle und done ein atomic nehmen
- std::lock_guardstd::mutex kann dann aus allen(!) Funktion

Allerdings sind immer noch gravierende Designfehler drin, vor allem dieses "nur 1 Thread pro CPU" ist ideal.

Wer sich nicht auskennt soll vorhandene Libraries nehmen.