Problème de performances de parallélisme multi-thread avec la séquence de Fibonacci dans Julia (1.3)

J'essaie la fonction multithread de Julia 1.3avec le matériel suivant:

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

Lors de l'exécution du script suivant:

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

cela me donne la sortie suivante

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

Cependant, lors de l'exécution du code suivant copié à partir de la page Julia sur le 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)

ce qui se passe, c'est que l'utilisation de la RAM / CPU passe de 3,2 Go / 6% à 15 Go / 25% sans aucune sortie (pendant au moins 1 minute, après quoi j'ai décidé de tuer la session julia)

Qu'est-ce que je fais mal?

Grande question.

Cette implémentation multithread de la fonction Fibonacci n'est pas plus rapide que la version à thread unique. Cette fonction n'a été présentée dans le billet de blog que comme un exemple de jouet du fonctionnement des nouvelles capacités de threading, soulignant qu'elle permet de générer de nombreux threads dans différentes fonctions et que le planificateur trouvera une charge de travail optimale.

Le problème est que la @spawnsurcharge n'est pas anodine 1µs, donc si vous générez un thread pour effectuer une tâche qui prend moins de temps 1µs, vous avez probablement nui à vos performances. La définition récursive de fib(n)a une complexité temporelle exponentielle de l'ordre 1.6180^n[1], donc lorsque vous appelez fib(43), vous générez quelque chose de 1.6180^43threads d' ordre . Si chacun prend1µs pour apparaître, cela prendra environ 16 minutes juste pour générer et planifier les threads nécessaires, et cela ne tient même pas compte du temps qu'il faut pour effectuer les calculs réels et re-fusionner / synchroniser les threads, ce qui prend même plus de temps.

Des choses comme celle-ci où vous générez un thread pour chaque étape d'un calcul n'ont de sens que si chaque étape du calcul prend beaucoup de temps par rapport à la @spawnsurcharge.

Notez qu'il y a du travail pour réduire les frais généraux de @spawn, mais par la physique même des puces en silicone multicœurs, je doute que cela puisse jamais être assez rapide pour la fibmise en œuvre ci-dessus .

Si vous êtes curieux de savoir comment nous pourrions modifier la fibfonction threadée pour qu'elle soit réellement bénéfique, la chose la plus simple à faire serait de ne générer un fibthread que si nous pensons que cela prendra beaucoup plus de temps que 1µsson exécution. Sur ma machine (fonctionnant sur 16 cœurs physiques), je reçois

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)

c'est donc deux bons ordres de grandeur par rapport au coût de création d'un thread. Cela semble être une bonne coupure à utiliser:

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

maintenant, si je suis la méthodologie de référence appropriée avec BenchmarkTools.jl [2] je trouve

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 demande dans les commentaires: C'est un facteur de 2 accélération en utilisant 16 cœurs semble-t-il. Est-il possible de rapprocher quelque chose d'un facteur 16?

Oui, ça l'est. Le problème avec la fonction ci-dessus est que le corps de la fonction est plus grand que celui de F, avec beaucoup de conditions, la génération de fonctions / threads et tout ça. Je vous invite à comparer @code_llvm F(10) @code_llvm fib(10). Cela signifie que fibjulia a beaucoup plus de mal à optimiser. Cette surcharge supplémentaire fait toute la différence pour les petits nboîtiers.

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

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

Oh non! tout ce code supplémentaire qui n'est jamais touché n < 23nous ralentit d'un ordre de grandeur! Cependant, il existe une solution simple: quand n < 23, ne récapitulez pas fib, appelez plutôt le thread unique 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

ce qui donne un résultat plus proche de ce que nous attendions pour tant de threads.

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

[2] La @btimemacro BenchmarkTools de BenchmarkTools.jl exécutera les fonctions plusieurs fois, ignorant le temps de compilation et les résultats moyens.

@Anush

Comme exemple d'utilisation manuelle de la mémorisation et du multithreading

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

Mais l'accélération est venue de la memmiozation et pas tellement du multithreading. La leçon ici est que nous devrions penser à de meilleurs algorithmes avant le multithreading.