Problema de rendimiento de paralelismo multihilo con secuencia de Fibonacci en Julia (1.3)

Estoy probando la función de subprocesos múltiples Julia 1.3con el siguiente 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

Al ejecutar el siguiente script:

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

me da el siguiente resultado

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

Sin embargo, al ejecutar el siguiente código copiado de la página de Julia sobre multihilo

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)

lo que sucede es que la utilización de RAM / CPU salta de 3.2GB / 6% a 15GB / 25% sin ninguna salida (durante al menos 1 minuto, después de lo cual decidí matar la sesión de julia)

¿Qué estoy haciendo mal?

Gran pregunta

Esta implementación multiproceso de la función Fibonacci no es más rápida que la versión de un solo subproceso. Esa función solo se mostró en la publicación del blog como un ejemplo de juguete de cómo funcionan las nuevas capacidades de subprocesamiento, destacando que permite generar muchos subprocesos en diferentes funciones y el programador descubrirá una carga de trabajo óptima.

El problema es que @spawntiene una sobrecarga no trivial de alrededor 1µs, por lo que si genera un hilo para realizar una tarea que requiere menos 1µs, probablemente haya perjudicado su rendimiento. La definición recursiva de fib(n)tiene una complejidad de orden exponencial en el tiempo 1.6180^n[1], por lo que cuando llama fib(43), genera algunos 1.6180^43hilos de orden . Si cada uno toma 1µsengendrar, tomará alrededor de 16 minutos solo para generar y programar los hilos necesarios, y eso ni siquiera cuenta el tiempo que lleva hacer los cálculos reales y volver a fusionar / sincronizar hilos que lleva incluso más tiempo.

Cosas como esta donde genera un hilo para cada paso de un cálculo solo tiene sentido si cada paso del cálculo lleva mucho tiempo en comparación con la @spawnsobrecarga.

Tenga en cuenta que se está trabajando para reducir la sobrecarga de @spawn, pero por la propia física de los chips de silicona multinúcleo, dudo que alguna vez pueda ser lo suficientemente rápido para la fibimplementación anterior .

Si tiene curiosidad acerca de cómo podríamos modificar la fibfunción de subprocesos para que sea realmente beneficiosa, lo más fácil sería generar un fibsubproceso si creemos que tomará mucho más tiempo que 1µsejecutarlo. En mi máquina (que se ejecuta en 16 núcleos físicos), obtengo

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)

Eso es un buen dos órdenes de magnitud sobre el costo de generar un hilo. Parece un buen límite para usar:

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

ahora, si sigo la metodología de referencia adecuada con BenchmarkTools.jl [2] encuentro

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 pregunta en los comentarios: Parece que este es un factor de 2 velocidades con 16 núcleos. ¿Es posible acercar algo a un factor de 16 de velocidad?

Sí lo es. El problema con la función anterior es que el cuerpo de la función es más grande que el de F, con muchos condicionales, función / generación de subprocesos y todo eso. Te invito a comparar @code_llvm F(10) @code_llvm fib(10). Esto significa que fibes mucho más difícil para julia optimizar. Esta sobrecarga adicional hace una gran diferencia para los ncasos pequeños .

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

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

¡Oh no! ¡todo ese código extra que nunca se toca n < 23es ralentizarnos en un orden de magnitud! Sin embargo, hay una solución fácil: cuando n < 23no recurras a fib, en lugar de eso, llama al subproceso único 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

lo que da un resultado más cercano a lo que esperaríamos para tantos hilos.

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

[2] La @btimemacro BenchmarkTools de BenchmarkTools.jl ejecutará funciones varias veces, omitiendo el tiempo de compilación y los resultados promedio.

@Anush

Como un ejemplo del uso de memorización y subprocesamiento múltiple manualmente

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

Pero la aceleración provino de la memoria y no tanto de subprocesos múltiples. La lección aquí es que deberíamos pensar mejores algoritmos antes de multihilo.