Kann die Rekursion parallel erfolgen? Wäre das sinnvoll?

Angenommen, ich verwende ein einfaches rekursives Algo für Fibonacci, das wie folgt ausgeführt wird:

fib(5) -> fib(4)+fib(3)
            |      |
      fib(3)+fib(2)|
                fib(2)+fib(1)

und so weiter

Die Ausführung erfolgt weiterhin sequentiell. Wie würde ich dies stattdessen so codieren, dass fib(4)und fib(3)durch Berechnen von 2 separaten Threads berechnet werden, dann werden in fib(4)und 2 Threads für fib(3)und erzeugt fib(2). Gleiches gilt für wann fib(3)wird auf fib(2)und aufgeteilt fib(1)?

(Mir ist bewusst, dass die dynamische Programmierung für Fibonacci ein viel besserer Ansatz wäre. Ich habe sie hier nur als einfaches Beispiel verwendet.)

(Wenn jemand ein Codebeispiel auch in C \ C ++ \ C # freigeben könnte, wäre das ideal)

Dies ist möglich, aber eine wirklich schlechte Idee; Berechnen Sie beispielsweise die Anzahl der Threads, die Sie bei der Berechnung von fib (16) erzeugen, und multiplizieren Sie diese mit den Kosten eines Threads. Fäden sind wahnsinnig teuer; Dies für die von Ihnen beschriebene Aufgabe zu tun, ist wie eine andere Schreibkraft einzustellen, um jede Figur eines Romans zu tippen.

Rekursive Algorithmen sind jedoch häufig gute Kandidaten für die Parallelisierung, insbesondere wenn sie den Job in zwei kleinere Jobs aufteilen, die unabhängig voneinander ausgeführt werden können. Der Trick besteht darin, zu wissen, wann die Parallelisierung beendet werden muss.

Im Allgemeinen möchten Sie nur "peinlich parallele" Aufgaben parallelisieren. Das heißt, Aufgaben, die rechenintensiv sind und unabhängig berechnet werden können . Viele Leute vergessen den ersten Teil. Themen sind so teuer , dass es nur Sinn macht , zu machen , wenn Sie eine haben große Menge an Arbeit für sie zu tun, und darüber hinaus, dass Sie einen ganzen Prozessor auf den Thread widmen . Wenn Sie 8 Prozessoren haben, werden sie durch das Erstellen von 80 Threads gezwungen, den Prozessor gemeinsam zu nutzen, wodurch jeder einzelne von ihnen enorm verlangsamt wird. Es ist besser, nur 8 Threads zu erstellen und jedem 100% Zugriff auf den Prozessor zu gewähren, wenn Sie eine peinlich parallele Aufgabe ausführen müssen.

Bibliotheken wie die Task Parallel Library in .NET ermitteln automatisch, wie effizient Parallelität ist. Sie könnten in Betracht ziehen, das Design zu untersuchen, wenn Sie an diesem Thema interessiert sind.

Die Frage hat eigentlich zwei Antworten.

Kann die Rekursion parallel erfolgen? Wäre das sinnvoll?

Ja natürlich. In den meisten (allen?) Fällen kann ein rekursiver Algorithmus ohne Rekursion umgeschrieben werden, was zu einem Algorithmus führt, der häufig leicht parallelisierbar ist. Nicht immer, aber oft.

Denken Sie an Quicksort oder durchlaufen Sie einen Verzeichnisbaum. In beiden Fällen könnte eine Warteschlange verwendet werden, um alle Zwischenergebnisse bzw. Unterverzeichnisse gefunden. Die Warteschlange kann parallel verarbeitet werden, wodurch schließlich weitere Einträge erstellt werden, bis die Aufgabe erfolgreich abgeschlossen wurde.

Was ist mit dem fib()Beispiel?

Leider ist die Fibonacci-Funktion eine schlechte Wahl, da die vollständigen Eingabewerte von zuvor berechneten Ergebnissen abhängen. Diese Abhängigkeit macht es schwierig, dies parallel zu tun, wenn Sie jedes Mal mit 1und beginnen 1.

Wenn Sie jedoch häufiger Fibonacci-Berechnungen durchführen müssen, ist es möglicherweise eine gute Idee, vorberechnete Ergebnisse zu speichern (oder zwischenzuspeichern), um alle Berechnungen bis zu diesem Zeitpunkt zu vermeiden. Das Konzept dahinter ist Regenbogentischen ziemlich ähnlich.

Nehmen wir an, Sie zwischenspeichern jedes 10. Fibo-Zahlenpaar bis zu 10.000. Starten Sie diese Initialisierungsroutine in einem Hintergrundthread. Wenn nun jemand nach der Fibo-Nummer 5246 fragt, nimmt der Algorithmus einfach das Paar von 5240 auf und startet die Berechnung von diesem Punkt an. Wenn das 5240-Paar noch nicht vorhanden ist, warten Sie einfach darauf.

Auf diese Weise könnte die Berechnung vieler zufällig ausgewählter Fibo-Zahlen sehr effizient und parallel erfolgen, da es sehr unwahrscheinlich ist, dass zwei Threads die gleichen Zahlen berechnen müssen - und selbst dann wäre dies kein großes Problem.

Natürlich ist es möglich, aber für ein so kleines Beispiel (und in der Tat für viele, die viel größer sind) würde die Menge an Installations- / Parallelitätskontrollcode, die Sie schreiben müssten, den Geschäftscode bis zu dem Punkt verdecken, an dem dies nicht der Fall wäre Seien Sie eine gute Idee, es sei denn, Sie brauchen wirklich, wirklich, wirklich Fibonacci-Zahlen, die sehr schnell berechnet werden.

Es ist fast immer besser lesbar und wartbar, Ihren Algorithmus normal zu formulieren und dann eine Parallelitätsbibliothek / Spracherweiterung wie TBB oder GCD dafür sorgen zu lassen, wie die Schritte tatsächlich auf Threads verteilt werden.

In Ihrem Beispiel berechnen Sie fib (3) zweimal, was zu einer doppelten Ausführung der gesamten fib (1) und fib (2) führt. Bei höheren Zahlen ist dies sogar noch schlimmer.

Sie werden wahrscheinlich schneller als die nicht rekursive Lösung, aber sie kostet viel mehr Ressourcen (Prozessoren) als es wert ist.

Ja, kann es! Mein einfachstes Beispiel, das ich Ihnen geben kann, ist die Vorstellung eines binären Zahlenbaums. Aus irgendeinem Grund möchten Sie alle Zahlen in einem Binärbaum addieren. Um dies zu tun, müssen Sie den Wert des Wurzelknotens zum Wert des linken / rechten Knotens hinzufügen. Der Knoten selbst kann jedoch die Wurzel eines anderen Baums sein (ein Teilbaum des ursprünglichen Baums),
anstatt den zu berechnen Summe des linken Teilbaums, dann die Summe des rechten ... dann addieren Sie sie zum Wert der Wurzel ... Sie können die Summe des linken und rechten Teilbaums parallel berechnen.

Ein Problem ist, dass der rekursive Standardalgorithmus für die Fibonacci-Funktion einfach furchtbar schlecht ist, da die Anzahl der Aufrufe zur Berechnung von fib (n) gleich fib (n) ist, was sehr schnell wächst. Also würde ich mich wirklich weigern, darüber zu diskutieren.

Schauen wir uns einen vernünftigeren rekursiven Algorithmus an, Quicksort. Es sortiert ein Array wie folgt: Wenn das Array klein ist, sortieren Sie es mit Bubblesort, Insertion-Sortierung oder was auch immer. Andernfalls: Wählen Sie ein Element des Arrays aus. Legen Sie alle kleineren Elemente auf eine Seite, alle größeren Elemente auf die andere Seite. Sortieren Sie die Seite mit den kleineren Elementen. Sortieren Sie die Seite mit den größeren Elementen.

Um eine willkürlich tiefe Rekursion zu vermeiden, besteht die übliche Methode darin, dass die schnelle Sortierfunktion einen rekursiven Aufruf für die kleinere der beiden Seiten (die mit weniger Elementen) ausführt und die größere Seite selbst behandelt.

Jetzt haben Sie eine sehr einfache Möglichkeit, mehrere Threads zu verwenden: Anstatt einen rekursiven Aufruf zum Sortieren der kleineren Seite durchzuführen, starten Sie einen Thread. Sortieren Sie dann die größere Hälfte und warten Sie, bis der Faden fertig ist. Das Starten von Threads ist jedoch teuer. Sie messen also, wie lange das Sortieren von n Elementen im Durchschnitt dauert, verglichen mit der Zeit zum Erstellen eines Threads. Daraus finden Sie das kleinste n, sodass es sich lohnt, einen neuen Thread zu erstellen. Wenn also die kleinere Seite, die sortiert werden muss, unter dieser Größe liegt, führen Sie einen rekursiven Aufruf durch. Andernfalls sortieren Sie diese Hälfte in einem neuen Thread.