Problem wydajności równoległości wielowątkowej z sekwencją Fibonacciego w Julii (1.3)

Próbuję funkcji wielowątkowości Julia 1.3na następującym sprzęcie:

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

Podczas uruchamiania następującego skryptu:

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

daje mi następujący wynik

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

Jednak po uruchomieniu następującego kodu skopiowanego ze strony Julii na temat wielowątkowości

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)

dzieje się tak, że wykorzystanie pamięci RAM / CPU przeskakuje z 3,2 GB / 6% do 15 GB / 25% bez żadnego wyjścia (przez co najmniej 1 minutę, po czym zdecydowałem się zabić sesję Julii)

Co ja robię źle?

Świetne pytanie.

Ta wielowątkowa implementacja funkcji Fibonacciego nie jest szybsza niż wersja z jednym wątkiem. Ta funkcja została pokazana tylko w poście na blogu jako zabawkowy przykład działania nowych możliwości wątków, podkreślając, że pozwala ona na tworzenie wielu wielu wątków w różnych funkcjach, a harmonogram zaplanuje optymalne obciążenie pracą.

Problem polega na tym, że @spawnma około trywialny narzut 1µs, więc jeśli odrodzisz wątek, aby wykonać zadanie, które zajmuje mniej niż 1µs, prawdopodobnie zepsułeś swoją wydajność. Rekursywna definicja fib(n)ma wykładniczą złożoność czasową rzędu 1.6180^n[1], więc kiedy wywołujesz fib(43), odradzasz się z 1.6180^43wątków porządku . Jeśli każdy bierze1µs odrodzi się, zajmie to około 16 minut po prostu odrodzenie i zaplanowanie potrzebnych wątków, a to nawet nie uwzględnia czasu potrzebnego na wykonanie obliczeń i ponownego scalenia / synchronizacji wątków, co zajmuje nawet więcej czasu.

Rzeczy takie jak ten, w których spawnowany jest wątek dla każdego kroku obliczenia, mają sens tylko wtedy, gdy każdy krok obliczenia zajmuje dużo czasu w porównaniu do @spawnnarzutu.

Zauważ, że trwają prace nad zmniejszeniem narzutów @spawn, ale przez samą fizykę wielordzeniowych chipów silikonowych wątpię, że może być wystarczająco szybki dla powyższej fibimplementacji.

Jeśli jesteś ciekawy, jak moglibyśmy zmodyfikować funkcję wątkową, fibaby była naprawdę korzystna, najłatwiej byłoby odrodzić fibwątek tylko, jeśli naszym zdaniem zajmie to znacznie więcej czasu niż 1µsuruchomienie. Na mojej maszynie (działającej na 16 fizycznych rdzeniach) dostaję

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)

więc to dobre dwa rzędy wielkości ponad koszt odrodzenia nici. Wydaje się, że to dobry sposób na użycie:

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

teraz, jeśli zastosuję odpowiednią metodologię testu porównawczego z BenchmarkTools.jl [2] znajdę

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 pyta w komentarzach: Wydaje się, że jest to współczynnik przyspieszenia 2 przy użyciu 16 rdzeni. Czy można uzyskać coś bliższego 16-krotnemu przyspieszeniu?

Tak to jest. Problem z powyższą funkcją polega na tym, że treść funkcji jest większa niż z F, z dużą liczbą warunków, odradzaniem funkcji / wątku i tym podobne. Zapraszam do porównania @code_llvm F(10) @code_llvm fib(10). Oznacza to, że fibJulia jest znacznie trudniejsza do optymalizacji. To dodatkowe obciążenie sprawia, że ​​świat małych nskrzynek stanowi różnicę .

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

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

O nie! cały ten dodatkowy kod, którego nigdy nie dotykamy, n < 23spowalnia nas o rząd wielkości! Jest jednak łatwa poprawka: kiedy n < 23nie powracaj do fib, zamiast tego wywołaj pojedynczy wątek 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

co daje wynik bliższy oczekiwaniom dla tak wielu wątków.

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

[2] @btimeMakro BenchmarkTools z BenchmarkTools.jl będzie uruchamiało funkcje wiele razy, pomijając czas kompilacji i średnie wyniki.

@Anush

Jako przykład ręcznego używania zapamiętywania i wielowątkowości

_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)

Ale przyspieszenie wynikało z memmiozacji i nie tyle wielowątkowości. Lekcja jest taka, że ​​powinniśmy pomyśleć o lepszych algorytmach przed wielowątkowością.