Sollte ich Einfädeln und Rekursion zusammen?

Question

Ich habe für eine Weile jetzt mit BSP Bäume wurden gebastelt und spiele auch mit Gewinde. Wenn ein Dreieck mit einem BSP-Baum hinzufügen, eine Gelegenheit ergibt einen neuen Thread für die Zwecke der Verarbeitung von Daten in parallel zu erstellen.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

Die beiden Einfügevorgängen oben durch zwei Threads ausgeführt werden kann, und da sie die gleichen Daten nicht ändern, kann günstige Synchronisation verwendet werden.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

Diese neue Methode versucht, einen Thread zu erstellen, um den Betrieb parallel zu vervollständigen, soll aber nicht fehlschlagen, wenn der Thread nicht erstellt werden kann (es wird einfach auf den ursprünglichen Algorithmus zurückkehren).

Ist das eine solide Programmierstil, oder bin ich Threads nicht ordnungsgemäß verwenden? Ich habe nicht in der Lage gewesen, eine Literatur über diese Technik zu finden. Ich mag, dass es dazu neigt, meine CPU in vollstem (2 Kerne) zu verwenden, und theoretisch auf eine beliebige Anzahl von Prozessoren skalieren würde. Ich mag es nicht, dass es auf CPU und Speicher schrecklich verschwenderisch sein könnte.

Answer 1

Themen sind groß, wenn ein Teil der Verarbeitung auf etwas wartet extern (Benutzereingabe, I / O, eine andere Verarbeitung) - der Thread, der warten kann weiterhin wartet auf, während ein Faden, der nicht schmiedet voraus warten .

Doch für verarbeitungsintensive Aufgaben, mehr Threads als Prozessoren tatsächlich schaffen Overhead. Es scheint, wie Threads alle „CPU Arbeit“ tun, also würde ich halten Sie sich an einen Thread pro Kern -. Test, um die optimale Anzahl zu finden, obwohl

Der größte Aufwand erstellt ist von Kontextwechsel (ein Thread Einfrieren und den Ausführungskontext des nächsten Laden) sowie Cache-Misses, wenn Threads Aufgaben mit unterschiedlichen Speicher tun (wenn Ihr Thread die CPU-Cache effektiv verwenden können) .

Answer 2

Ihre beste Wette wäre, einen Threadpool zu erstellen, und dann verwenden, ‚transparent‘ Knoten hinzuzufügen.

zB erstellen 2 Fäden beim Programmstart, haben sie auf einer Semaphore oder ein Ereignis warten. Wenn Sie Knoten muss hinzufügen, Pop Sie die Daten auf eine Warteschlange dann die Semaphore auslösen. Dies weckt einer der Fäden, die die Daten aus der Warteschlange erscheint und führt die Verarbeitung. (Stellen Sie sicher, den Zugang zu der Warteschlange ist THREAD - vollständig synchronisiert mit einem kritischen Abschnitt ist am besten).

Die Gesamtleistung Ihrer App ist langsamer, wie Sie mehr Aufwand haben, in dem Kopieren von Daten in die Warteschlange und die zusätzlichen Threads ausgeführt wird, aber wenn Sie auf einem einzigen Kern laufen verwendet werden Sie jetzt auf 2. laufen Es funktioniert am besten wenn die Gewindebearbeitung ist teuer.

Answer 3

Sicher, kann beispielsweise Quicksort programmiert ganz leicht multithreaded und einige große Performance-Gewinne auf Multi-Core-Systeme, und einige kleine Leistungsverluste auf nicht multithreaded bekommen. Denken Sie daran, dass Sie Kopf zweimal jetzt sind das Hinzufügen - einmal für den Stapel auf der Rekursion speichern und einmal auf dem Faden, so dass, wenn Sie eine große Anzahl von Rekursion tun, dann könnte es ein System schneller als ein nicht-Multithreading-Ansatz überwältigt.