Pertanyaan yang bagus
Implementasi multitreaded dari fungsi Fibonacci ini adalah tidak lebih cepat dari versi single threaded. Fungsi itu hanya ditampilkan dalam posting blog sebagai contoh mainan tentang bagaimana kemampuan threading baru bekerja, menyoroti bahwa itu memungkinkan untuk memunculkan banyak banyak utas dalam fungsi yang berbeda dan penjadwal akan mencari tahu beban kerja yang optimal.
Masalahnya adalah bahwa @spawn
ada overhead non-sepele di sekitar 1µs
, jadi jika Anda menelurkan utas untuk melakukan tugas yang membutuhkan waktu kurang dari 1µs
, Anda mungkin akan merusak kinerja Anda. Definisi rekursif dari fib(n)
kompleksitas waktu eksponensial 1.6180^n
[1], jadi ketika Anda menelepon fib(43)
, Anda menelurkan sesuatu dari pesanan1.6180^43
utas . Jika masing-masing diperlukan 1µs
untuk menelurkan, itu akan memakan waktu sekitar 16 menit hanya untuk menelurkan dan menjadwalkan utas yang diperlukan, dan itu bahkan tidak memperhitungkan waktu yang diperlukan untuk melakukan perhitungan aktual dan menggabungkan kembali / menyinkronkan utas yang membutuhkan waktu genap lebih banyak waktu.
Hal-hal seperti ini di mana Anda menelurkan utas untuk setiap langkah perhitungan hanya masuk akal jika setiap langkah perhitungan membutuhkan waktu lama dibandingkan dengan @spawn
overhead.
Perhatikan bahwa ada pekerjaan yang dilakukan untuk mengurangi overhead @spawn
, tetapi oleh fisika chip silikon multicore, saya ragu itu bisa cukup cepat untuk fib
implementasi di atas .
Jika Anda penasaran tentang bagaimana kami dapat memodifikasi fib
fungsi berulir agar benar-benar bermanfaat, hal yang paling mudah untuk dilakukan adalah dengan menelurkan sebuah fib
utas jika kami pikir itu akan memakan waktu lebih lama daripada 1µs
menjalankannya. Di mesin saya (berjalan pada 16 core fisik), saya mengerti
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)
jadi itu adalah dua urutan besar yang baik atas biaya pemijahan utas. Itu sepertinya cutoff yang bagus untuk digunakan:
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
sekarang, jika saya mengikuti metodologi benchmark yang tepat dengan BenchmarkTools.jl [2] saya temukan
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 bertanya dalam komentar: Ini adalah faktor 2 percepatan menggunakan 16 core sepertinya. Apakah mungkin untuk mendapatkan sesuatu yang lebih dekat dengan faktor kecepatan 16?
Ya itu. Masalah dengan fungsi di atas adalah bahwa fungsi tubuh lebih besar dari pada F
, dengan banyak persyaratan, fungsi / pemijahan benang dan semua itu. Saya mengundang Anda untuk membandingkan @code_llvm F(10)
@code_llvm fib(10)
. Ini berarti bahwa fib
jauh lebih sulit untuk mengoptimalkan julia. Overhead tambahan ini membuat perbedaan besar untuk n
case kecil .
julia> @btime F(20);
28.844 μs (0 allocations: 0 bytes)
julia> @btime fib(20);
242.208 μs (20 allocations: 320 bytes)
Oh tidak! semua kode tambahan yang tidak pernah disentuh n < 23
adalah memperlambat kita dengan urutan besarnya! Namun ada perbaikan yang mudah: kapan n < 23
, jangan berulang fib
, panggil single yang di-threaded 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
yang memberikan hasil lebih dekat dengan apa yang kita harapkan untuk begitu banyak utas.
[1] https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/
[2] @btime
Makro BenchmarkTools dari BenchmarkTools.jl akan menjalankan fungsi beberapa kali, melewatkan waktu kompilasi dan hasil rata-rata.
fib
lebih sulit untuk mengoptimalkan julia daripadaF
, jadi kami hanya menggunakanF
bukanfib
untukn< 23
. Saya mengedit jawaban saya dengan penjelasan dan contoh yang lebih mendalam.Threads.nthreads()
untuk Anda? Saya menduga Anda mungkin memiliki julia berjalan hanya dengan satu utas.@Anush
Sebagai contoh menggunakan memoisasi dan multithreading secara manual
Tetapi percepatan datang dari memmiozation dan tidak banyak multithreading. Pelajaran di sini adalah kita harus memikirkan algoritma yang lebih baik sebelum multithreading.
sumber