在Julia（1.3）中，使用Fibonacci序列的多线程并行性能问题

Question

在Julia（1.3）中，使用Fibonacci序列的多线程并行性能问题

15

我正在尝试使用以下硬件运行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关于多线程的页面中复制过来的：https://julialang.org/blog/2019/07/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会话）。

我做错了什么？

- ecjb

2个回答

1

@Anush

这是手动使用记忆化和多线程的示例。

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

但速度的提升来自于记忆化而不是多线程。这里的教训是我们在使用多线程之前应该考虑更好的算法。

- xiaodai

这个问题从来不是关于快速计算斐波那契数列的。重点是，“为什么多线程不能改善这个朴素实现？” - Mason

1

对我来说，下一个合乎逻辑的问题是：如何使它快速。因此，阅读此内容的人可以看到我的解决方案并从中学习，也许。 - xiaodai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mason · Accepted Answer

很好的问题。

这个斐波那契函数的多线程实现并不比单线程版本更快。该函数仅作为博客文章中新线程功能的玩具示例，强调它允许在不同的函数中生成许多线程，并且调度程序将找出最佳工作负载。

问题在于@spawn有一个非平凡的开销约为1µs，因此如果你生成一个线程来执行少于1µs的任务，你可能会降低性能。递归定义的fib(n)的时间复杂度是指数级的，阶数为1.6180^n [1]，因此当你调用fib(43)时，你生成了大约1.6180^43数量级的线程。如果每个线程花费1µs来生成，仅生成和调度所需的线程就需要大约16分钟，甚至还没有考虑执行实际计算和重新合并/同步线程所需的时间。

像这样为计算的每个步骤生成一个线程只有在每个计算步骤相对于@spawn开销需要较长时间时才有意义。

请注意，有关减少@spawn开销的工作正在进行中，但由于多核硅芯片的物理特性，我怀疑它永远无法足够快地处理上述fib实现。

如果你想知道如何修改线程化的fib函数以使其真正受益，最简单的方法是仅在我们认为运行时间显着长于1µs时才生成一个fib线程。在我的机器上（运行在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] BenchmarkTools.jl中的BenchmarkTools @btime宏将运行函数多次，跳过编译时间并平均结果。