[multithreading] Julia의 피보나치 시퀀스에서 멀티 스레드 병렬 처리 성능 문제 (1.3)

좋은 질문입니다.

피보나치 함수의이 멀티 스레드 구현은 단일 스레드 버전보다 빠르지 않습니다 . 이 기능은 블로그 게시물에서 새로운 스레딩 기능의 작동 방식에 대한 장난감 예제로만 보여졌으며 다른 기능으로 많은 수의 스레드를 생성 할 수 있으며 스케줄러가 최적의 작업 부하를 계산할 수 있음을 강조했습니다.

문제는 @spawn주변의 사소한 오버 헤드 가 있다는 것입니다 1µs. 따라서보다 적은 작업을 수행하기 위해 스레드를 생성하면 1µs성능이 저하 될 수 있습니다. 의 재귀 적 정의는 fib(n)순서의 지수 시간 복잡도를 가지 1.6180^n므로 [1]을 호출 fib(43)하면 주문 1.6180^43스레드가 생성 됩니다. 각각 1µs생성하는 데 필요한 스레드를 생성하고 예약하는 데 약 16 분이 소요되며 실제 계산을 수행하고 스레드를 다시 병합 / 동기화하는 데 걸리는 시간도 고려하지 않습니다. 더 많은 시간.

계산의 각 단계마다 스레드를 생성하는 것과 같은 것은 @spawn오버 헤드에 비해 계산의 각 단계가 오래 걸리는 경우에만 의미가 있습니다.

의 오버 헤드를 줄이는 작업이 @spawn있지만 멀티 코어 실리콘 칩의 물리학으로 인해 위의 fib구현에 충분히 빠르지 않을 것입니다.

스레드 fib함수를 실제로 유용하게 수정하는 방법에 대해 궁금한 경우 가장 쉬운 방법 fib은 1µs실행하는 것보다 훨씬 오래 걸리는 스레드 만 생성하는 것입니다 . 내 컴퓨터 (16 개의 물리적 코어에서 실행)에서

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)

스레드 생성 비용보다 2 배나 큰 크기입니다. 사용하기 좋은 컷오프처럼 보입니다.

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

이제 BenchmarkTools.jl를 사용하여 적절한 벤치 마크 방법을 따르면 [2]

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는 의견을 묻습니다. 이것은 16 코어를 사용하여 2 속도를 높이는 요인입니다. 16 배 빠른 속도로 무언가를 얻을 수 있습니까?

그렇습니다. 위 함수의 문제점은 함수 본문이 F많은 조건, 함수 / 스레드 생성 및 그 모든 것보다 큽니다 . 나는 당신을 비교하도록 초대합니다 @code_llvm F(10) @code_llvm fib(10). 이것은 fib줄리아가 최적화하기가 훨씬 어렵다는 것을 의미합니다 . 이 여분의 오버 헤드는 작은 n경우 에 큰 차이를 만듭니다 .

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

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

아뇨! 절대 손대지 않는 모든 추가 코드 n < 23는 우리 를 몇 배나 느리게합니다! 그래도 쉽게 고칠 수 있습니다. n < 23,로 돌아 가지 fib말고 대신 단일 스레드를 호출하십시오 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

많은 스레드에 기대되는 결과에 더 가까운 결과를 제공합니다.

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

[2] BenchmarkTools.jl의 BenchmarkTools @btime매크로는 컴파일 시간과 평균 결과를 건너 뛰고 함수를 여러 번 실행합니다.

답변

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