multithreading - Julia (1.3) 中斐波那契数列的多线程并行性能问题

Question

我正在尝试Julia 1.3的多线程功能使用以下硬件:

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

运行以下脚本时:

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

它给了我以下输出

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

但是，当运行从 Julia page about multithreading 复制的以下代码时

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)

发生的情况是 RAM/CPU 的利用率从 3.2GB/6% 跃升至 15GB/25% 没有任何输出(至少 1 分钟，之后我决定终止 julia session )

我究竟做错了什么？

Answer 1

好问题。
斐波那契函数的这种多线程实现并不比单线程版本快。该功能仅在博客文章中作为新线程功能如何工作的玩具示例显示，强调它允许在不同功能中生成许多线程，并且调度程序将找出最佳工作负载。
问题是 @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)

所以这比产生线程的成本高出两个数量级。这似乎是一个很好的使用截止点:

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 Julia 更难优化。这个额外的开销对于小的 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] 基准工具 @btime BenchmarkTools.jl 中的宏将多次运行函数，跳过编译时间和平均结果。