Multithread-Parallelitätsleistungsproblem mit Fibonacci-Sequenz in Julia (1.3)

Ich versuche die Multithread-Funktion von Julia 1.3mit der folgenden Hardware:

Model Name: MacBook Pro
Processor Name: Intel Core i7
Processor Speed:    2.8 GHz
Number of Processors:   1
Total Number of Cores:  4
L2 Cache (per Core):    256 KB
L3 Cache:   6 MB
Hyper-Threading Technology: Enabled
Memory: 16 GB

Beim Ausführen des folgenden Skripts:

function F(n)
if n < 2
    return n
    else
        return F(n-1)+F(n-2)
    end
end
@time F(43)

es gibt mir die folgende Ausgabe

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

Wenn Sie jedoch den folgenden Code ausführen, der von der Julia-Seite zum Thema Multithreading kopiert wurde

import Base.Threads.@spawn

function fib(n::Int)
    if n < 2
        return n
    end
    t = @spawn fib(n - 2)
    return fib(n - 1) + fetch(t)
end

fib(43)

Was passiert ist, dass die Auslastung von RAM / CPU von 3,2 GB / 6% auf 15 GB / 25% ohne Ausgabe springt (für mindestens 1 Minute, danach habe ich beschlossen, die Julia-Sitzung zu beenden)

Was mache ich falsch?

Gute Frage.

Diese Multithread-Implementierung der Fibonacci-Funktion ist nicht schneller als die Single-Threaded-Version. Diese Funktion wurde im Blog-Beitrag nur als Spielzeugbeispiel für die Funktionsweise der neuen Threading-Funktionen gezeigt. Dabei wurde hervorgehoben, dass viele, viele Threads in verschiedenen Funktionen erzeugt werden können und der Scheduler eine optimale Arbeitslast ermittelt.

Das Problem ist, dass @spawnder Aufwand nicht trivial 1µsist. Wenn Sie also einen Thread erstellen, um eine Aufgabe zu erledigen, die weniger als dauert 1µs, haben Sie wahrscheinlich Ihre Leistung beeinträchtigt. Die rekursive Definition von fib(n)hat eine exponentielle zeitliche Komplexität der Reihenfolge 1.6180^n[1]. Wenn Sie also aufrufen fib(43), erzeugen Sie etwas von Auftragsthreads 1.6180^43. Wenn jeder benötigt 1µs, um zu spawnen, dauert es ungefähr 16 Minuten, nur um die benötigten Threads zu spawnen und zu planen, und das berücksichtigt nicht einmal die Zeit, die benötigt wird, um die eigentlichen Berechnungen durchzuführen und Threads neu zusammenzuführen / zu synchronisieren, was gerade dauert mehr Zeit.

Solche Dinge, bei denen Sie für jeden Schritt einer Berechnung einen Thread erzeugen, sind nur dann sinnvoll, wenn jeder Schritt der Berechnung im Vergleich zum @spawnOverhead lange dauert .

Beachten Sie, dass daran gearbeitet wird, den Overhead von zu verringern @spawn, aber aufgrund der Physik von Multicore-Silikonchips bezweifle ich, dass dies für die obige fibImplementierung jemals schnell genug sein kann .

Wenn Sie neugierig sind, wie wir die Thread- fibFunktion so ändern können, dass sie tatsächlich von Vorteil ist, ist es am einfachsten, einen fibThread nur dann zu erzeugen, wenn wir der Meinung sind, dass die 1µsAusführung erheblich länger dauert als die Ausführung. Auf meinem Computer (läuft auf 16 physischen Kernen) bekomme ich

function F(n)
    if n < 2
        return n
    else
        return F(n-1)+F(n-2)
    end
end


julia> @btime F(23);
  122.920 μs (0 allocations: 0 bytes)

Das sind also gut zwei Größenordnungen über den Kosten für das Laichen eines Fadens. Das scheint ein guter Cutoff zu sein:

function fib(n::Int)
    if n < 2
        return n
    elseif n > 23
        t = @spawn fib(n - 2)
        return fib(n - 1) + fetch(t)
    else
        return fib(n-1) + fib(n-2)
    end
end

Wenn ich nun mit BenchmarkTools.jl [2] die richtige Benchmark-Methodik befolge, finde ich

julia> using BenchmarkTools

julia> @btime fib(43)
  971.842 ms (1496518 allocations: 33.64 MiB)
433494437

julia> @btime F(43)
  1.866 s (0 allocations: 0 bytes)
433494437

@Anush fragt in den Kommentaren: Dies ist ein Faktor von 2 Beschleunigung mit 16 Kernen, wie es scheint. Ist es möglich, etwas näher an einen Faktor von 16 zu bringen?

Ja, so ist es. Das Problem mit der obigen Funktion ist, dass der Funktionskörper größer ist als der von F, mit vielen Bedingungen, Funktions- / Thread-Laichen und all dem. Ich lade Sie zum Vergleich ein @code_llvm F(10) @code_llvm fib(10). Dies bedeutet, dass fibes für Julia viel schwieriger ist, sie zu optimieren. Dieser zusätzliche Aufwand macht für die kleinen nFälle einen großen Unterschied .

julia> @btime F(20);
  28.844 μs (0 allocations: 0 bytes)

julia> @btime fib(20);
  242.208 μs (20 allocations: 320 bytes)

Ach nein! All dieser zusätzliche Code, der niemals berührt n < 23wird, verlangsamt uns um eine Größenordnung! Es gibt jedoch eine einfache Lösung: Wann n < 23, nicht zurückgreifen auf fib, sondern den einzelnen Thread aufrufen F.

function fib(n::Int)
    if n > 23
       t = @spawn fib(n - 2)
       return fib(n - 1) + fetch(t)
    else
       return F(n)
    end
end

julia> @btime fib(43)
  138.876 ms (185594 allocations: 13.64 MiB)
433494437

Dies ergibt ein Ergebnis, das näher an dem liegt, was wir für so viele Threads erwarten würden.

[1] https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/

[2] Das BenchmarkTools- @btimeMakro von BenchmarkTools.jl führt Funktionen mehrmals aus und überspringt die Kompilierungszeit und die durchschnittlichen Ergebnisse.

@ Anush

Als Beispiel für die manuelle Verwendung von Memoization und Multithreading

_fib(::Val{1}, _,  _) = 1
_fib(::Val{2}, _, _) = 1

import Base.Threads.@spawn
_fib(x::Val{n}, d = zeros(Int, n), channel = Channel{Bool}(1)) where n = begin
  # lock the channel
  put!(channel, true)
  if d[n] != 0
    res = d[n]
    take!(channel)
  else
    take!(channel) # unlock channel so I can compute stuff
    #t = @spawn _fib(Val(n-2), d, channel)
    t1 =  _fib(Val(n-2), d, channel)
    t2 =  _fib(Val(n-1), d, channel)
    res = fetch(t1) + fetch(t2)

    put!(channel, true) # lock channel
    d[n] = res
    take!(channel) # unlock channel
  end
  return res
end

fib(n) = _fib(Val(n), zeros(Int, n), Channel{Bool}(1))


fib(1)
fib(2)
fib(3)
fib(4)
@time fib(43)


using BenchmarkTools
@benchmark fib(43)

Aber die Beschleunigung kam von Memmiozation und nicht so sehr von Multithreading. Die Lehre hier ist, dass wir vor dem Multithreading über bessere Algorithmen nachdenken sollten.