Apa manfaat menggunakan kerangka kerja fork / join yang baru hanya dengan membagi tugas besar menjadi N subtugas pada awalnya, mengirimkannya ke kumpulan utas yang di-cache (dari Pelaksana ) dan menunggu setiap tugas selesai? Saya gagal melihat bagaimana menggunakan abstraksi fork / join menyederhanakan masalah atau membuat solusi lebih efisien dari apa yang kami miliki selama bertahun-tahun sekarang.
Sebagai contoh, algoritma blurring paralel dalam contoh tutorial dapat diimplementasikan seperti ini:
public class Blur implements Runnable {
private int[] mSource;
private int mStart;
private int mLength;
private int[] mDestination;
private int mBlurWidth = 15; // Processing window size, should be odd.
public ForkBlur(int[] src, int start, int length, int[] dst) {
mSource = src;
mStart = start;
mLength = length;
mDestination = dst;
}
public void run() {
computeDirectly();
}
protected void computeDirectly() {
// As in the example, omitted for brevity
}
}
Berpisah di awal dan mengirim tugas ke kumpulan utas:
// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool
int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();
// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
int size = Math.min(maxSize, src.length - i);
ForkBlur task = new ForkBlur(src, i, size, dst);
Future f = threadPool.submit(task);
futures.add(f);
}
// Wait for all sent tasks to complete:
for (Future future : futures) {
future.get();
}
// Done!
Tugas-tugas pergi ke antrian pool thread, dari mana mereka dieksekusi sebagai thread pekerja menjadi tersedia. Selama pemisahan cukup granular (untuk menghindari keharusan menunggu tugas terakhir) dan thread pool memiliki cukup (setidaknya N prosesor), semua prosesor bekerja dengan kecepatan penuh hingga seluruh perhitungan selesai.
Apakah saya melewatkan sesuatu? Apa nilai tambah dari menggunakan kerangka garpu / gabung?
Jika Anda memiliki n utas sibuk semua bekerja pada 100% secara independen, itu akan lebih baik daripada n utas di kelompok Fork-Join (FJ). Tetapi tidak pernah berhasil seperti itu.
Mungkin tidak ada yang bisa membagi masalah dengan tepat menjadi n bagian yang sama. Bahkan jika Anda melakukannya, penjadwalan thread adalah cara yang adil. Anda akhirnya akan menunggu utas yang paling lambat. Jika Anda memiliki banyak tugas, maka masing-masing dapat berjalan dengan paralelisme kurang dari n-arah (umumnya lebih efisien), namun naik ke n-arah saat tugas lain selesai.
Jadi kenapa tidak kita potong saja masalah menjadi ukuran FJ dan buat thread pool. Penggunaan FJ biasa memotong masalah menjadi potongan-potongan kecil. Melakukan ini dalam urutan acak membutuhkan banyak koordinasi di tingkat perangkat keras. Overhead akan menjadi pembunuh. Dalam FJ, tugas dimasukkan ke dalam antrian yang dibacakan utas dalam urutan Last In First Out (LIFO / stack), dan pencurian pekerjaan (pada pekerjaan inti, umumnya) dilakukan First In First Out (FIFO / "queue"). Hasilnya adalah bahwa pemrosesan array panjang dapat dilakukan sebagian besar secara berurutan, meskipun dipecah menjadi potongan-potongan kecil. (Ini juga merupakan kasus yang mungkin tidak sepele untuk memecah masalah menjadi potongan-potongan kecil berukuran merata dalam satu big bang. Katakanlah berurusan dengan beberapa bentuk hierarki tanpa menyeimbangkan.)
Kesimpulan: FJ memungkinkan penggunaan utas perangkat keras yang lebih efisien dalam situasi yang tidak rata, yang akan selalu terjadi jika Anda memiliki lebih dari satu utas.
sumber
maxSize
parameter dalam contoh saya akan menghasilkan pembagian subtugas yang hampir mirip dengan "binary splitting" pada contoh FJ (dilakukan dalamcompute()
metode, yang menghitung sesuatu atau mengirim subtugas keinvokeAll()
).Tujuan utama dari kumpulan utas dan Fork / Gabung adalah sama: Keduanya ingin memanfaatkan daya CPU yang tersedia sebaik mungkin untuk throughput maksimum. Throughput maksimum berarti bahwa sebanyak mungkin tugas harus diselesaikan dalam periode waktu yang lama. Apa yang diperlukan untuk melakukan itu? (Untuk yang berikut, kami akan menganggap bahwa tidak ada kekurangan tugas perhitungan: Selalu ada cukup untuk melakukan utilisasi CPU 100%. Selain itu saya menggunakan "CPU" yang setara untuk core atau virtual core jika terjadi hyper-threading).
Jadi kami menemukan bahwa untuk throughput maksimum, kami harus memiliki jumlah utas yang sama persis dengan CPU. Dalam contoh Oracle yang kabur Anda bisa mengambil kumpulan utas ukuran tetap dengan jumlah utas sama dengan jumlah CPU yang tersedia atau menggunakan kumpulan utas. Itu tidak akan membuat perbedaan, Anda benar!
Jadi kapan Anda akan mendapat masalah dengan kolam utas? Itu jika sebuah thread memblokir , karena utas Anda sedang menunggu tugas lain untuk diselesaikan. Asumsikan contoh berikut:
Apa yang kita lihat di sini adalah algoritma yang terdiri dari tiga langkah A, B dan C. A dan B dapat dilakukan secara independen satu sama lain, tetapi langkah C membutuhkan hasil dari langkah A DAN B. Apa yang dilakukan algoritma ini adalah menyerahkan tugas A ke threadpool dan melakukan tugas b secara langsung. Setelah itu utas akan menunggu tugas A selesai juga dan melanjutkan dengan langkah C. Jika A dan B selesai pada saat yang sama, maka semuanya baik-baik saja. Tetapi bagaimana jika A membutuhkan waktu lebih lama dari B? Itu mungkin karena sifat tugas A yang mendiktekannya, tetapi mungkin juga demikian karena tidak ada utas untuk tugas A yang tersedia di awal dan tugas A perlu menunggu. (Jika hanya ada satu CPU yang tersedia dan dengan demikian threadpool Anda hanya memiliki satu utas ini bahkan akan menyebabkan kebuntuan, tetapi untuk saat ini yang tidak penting). Intinya adalah utas yang baru saja dieksekusi tugas Bmemblokir seluruh utas . Karena kami memiliki jumlah utas yang sama dengan CPU dan satu utas diblokir, itu artinya satu CPU idle .
Fork / Gabung menyelesaikan masalah ini: Di kerangka garpu / gabung Anda akan menulis algoritma yang sama sebagai berikut:
Terlihat sama, bukan? Namun petunjuknya adalah bahwa
aTask.join
tidak akan memblokir . Alih-alih, di sinilah pencuri pekerjaan dilakukan: Utas akan mencari-cari tugas lain yang telah bercabang di masa lalu dan akan dilanjutkan dengan itu. Pertama, ia memeriksa apakah tugas-tugas yang telah dilakukan sendiri sudah mulai diproses. Jadi jika A belum dimulai oleh utas lain, ia akan melakukan selanjutnya, jika tidak akan memeriksa antrian utas lainnya dan mencuri pekerjaan mereka. Setelah tugas ini dari utas lain selesai, ia akan memeriksa apakah A selesai sekarang. Jika itu algoritma di atas dapat memanggilstepC
. Kalau tidak, ia akan mencari tugas lain untuk mencuri. Dengan demikian fork / join pools dapat mencapai utilisasi CPU 100%, bahkan dalam menghadapi tindakan memblokir .Namun ada jebakan: Mencuri pekerjaan hanya mungkin untuk
join
panggilanForkJoinTask
s. Itu tidak dapat dilakukan untuk tindakan pemblokiran eksternal seperti menunggu utas lainnya atau menunggu tindakan I / O. Jadi bagaimana dengan itu, menunggu I / O untuk menyelesaikan adalah tugas bersama? Dalam hal ini jika kita bisa menambahkan utas tambahan ke kumpulan Garpu / Gabung yang akan dihentikan lagi segera setelah tindakan pemblokiran selesai akan menjadi hal terbaik kedua yang harus dilakukan. DanForkJoinPool
sebenarnya bisa melakukan hal itu jika kita menggunakanManagedBlocker
s.Fibonacci
Dalam JavaDoc untuk RecursiveTask adalah contoh untuk menghitung angka Fibonacci menggunakan Fork / Bergabung. Untuk solusi rekursif klasik, lihat:
Seperti yang dijelaskan dalam JavaDocs, ini adalah cara yang cukup untuk menghitung angka fibonacci, karena algoritma ini memiliki kompleksitas O (2 ^ n) sementara cara yang lebih sederhana dimungkinkan. Namun algoritma ini sangat sederhana dan mudah dimengerti, jadi kami tetap menggunakannya. Mari kita asumsikan kita ingin mempercepat ini dengan Fork / Gabung. Implementasi naif akan terlihat seperti ini:
Langkah-langkah di mana Tugas ini dibagi terlalu pendek dan dengan demikian ini akan berkinerja buruk, tetapi Anda dapat melihat bagaimana kerangka kerja umumnya bekerja dengan sangat baik: Dua puncak dapat dihitung secara independen, tetapi kemudian kita membutuhkan keduanya untuk membangun final hasil. Jadi satu setengahnya dilakukan di utas lainnya. Bersenang-senang melakukan hal yang sama dengan kolam utas tanpa mendapatkan jalan buntu (mungkin, tapi tidak sesederhana).
Hanya untuk kelengkapan: Jika Anda benar-benar ingin menghitung angka Fibonacci menggunakan pendekatan rekursif ini di sini adalah versi yang dioptimalkan:
Ini membuat subtugas jauh lebih kecil karena mereka hanya terpecah ketika
n > 10 && getSurplusQueuedTaskCount() < 2
benar, yang berarti ada lebih dari 100 pemanggilan metode yang harus dilakukan (n > 10
) dan tidak ada tugas man yang sudah menunggu (getSurplusQueuedTaskCount() < 2
).Di komputer saya (4 inti (8 saat menghitung Hyper-threading), Intel (R) Core (TM) i7-2720QM CPU @ 2.20GHz)
fib(50)
membutuhkan 64 detik dengan pendekatan klasik dan hanya 18 detik dengan pendekatan Fork / Bergabung yang adalah keuntungan yang cukup nyata, meskipun secara teori tidak sebanyak mungkin.Ringkasan
sumber
Fork / join berbeda dari thread pool karena menerapkan pencurian kerja. Dari Fork / Bergabunglah
Katakanlah Anda memiliki dua utas, dan 4 tugas a, b, c, d yang masing-masing membutuhkan waktu 1, 1, 5, dan 6 detik. Awalnya, a dan b ditugaskan untuk utas 1 dan c dan d untuk utas 2. Dalam kumpulan utas, ini akan membutuhkan waktu 11 detik. Dengan fork / join, utas 1 selesai dan dapat mencuri kerja dari utas 2, sehingga tugas d akhirnya akan dieksekusi oleh utas 1. Utas 1 mengeksekusi a, b dan d, utas 2 hanya c. Waktu keseluruhan: 8 detik, bukan 11.
EDIT: Seperti yang ditunjukkan Joonas, tugas tidak harus dialokasikan sebelumnya ke utas. Gagasan fork / join adalah bahwa utas dapat memilih untuk membagi tugas menjadi beberapa sub-bagian. Jadi untuk menyatakan kembali di atas:
Kami memiliki dua tugas (ab) dan (cd) yang masing-masing membutuhkan waktu 2 dan 11 detik. Thread 1 mulai menjalankan ab dan membaginya menjadi dua sub-tugas a & b. Demikian pula dengan utas 2, ia terbagi menjadi dua sub-tugas c & d. Ketika utas 1 telah selesai a & b, ia dapat mencuri d dari utas 2.
sumber
compute()
apakah menghitung tugas, atau membaginya menjadi dua subtugas. Opsi mana yang dipilihnya hanya bergantung pada ukuran tugas (if (mLength < sThreshold)...
), jadi itu hanya cara mewah untuk membuat sejumlah tugas tetap. Untuk gambar 1000x1000, akan ada tepat 16 subtugas yang benar-benar menghitung sesuatu. Selain itu akan ada 15 (= 16 - 1) tugas "perantara" yang hanya menghasilkan dan menjalankan subtugas dan tidak menghitung sendiri apa pun.computeDirectly()
metodenya, tidak ada cara untuk mencuri apa pun lagi. Seluruh pemisahan dilakukan secara apriori , setidaknya dalam contoh.Semua orang di atas benar bahwa manfaatnya didapat dari mencuri, tetapi untuk memperluas alasannya.
Manfaat utama adalah koordinasi yang efisien antara benang pekerja. Pekerjaan harus dipisah dan dipasang kembali, yang membutuhkan koordinasi. Seperti yang Anda lihat dalam jawaban AH di atas, setiap utas memiliki daftar kerjanya sendiri. Properti penting dari daftar ini adalah diurutkan (tugas besar di atas dan tugas kecil di bawah). Setiap utas menjalankan tugas di bagian bawah daftar dan mencuri tugas dari atas daftar utas lainnya.
Hasilnya adalah:
Kebanyakan skema membagi dan menaklukkan menggunakan kumpulan utas membutuhkan lebih banyak komunikasi dan koordinasi antar-utas.
sumber
Dalam contoh ini Fork / Gabung menambahkan tidak ada nilai karena forking tidak diperlukan dan beban kerja dibagi secara merata di seluruh utas pekerja. Fork / Gabung hanya menambah overhead.
Berikut ini adalah artikel yang bagus tentang masalah ini. Mengutip:
sumber
Perbedaan penting lainnya tampaknya dengan FJ, Anda dapat melakukan beberapa fase "Bergabung" yang rumit. Pertimbangkan jenis penggabungan dari http://faculty.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture18.html , akan ada terlalu banyak orkestrasi yang diperlukan untuk melakukan pre-split pekerjaan ini. mis. Anda perlu melakukan hal-hal berikut:
Bagaimana Anda menentukan bahwa Anda harus melakukan hal-hal sebelum penggabungan yang menyangkut mereka dll.
Saya telah mencari cara terbaik untuk melakukan hal tertentu untuk masing-masing daftar item. Saya pikir saya hanya akan membagi daftar dan menggunakan ThreadPool standar. FJ tampaknya paling berguna ketika pekerjaan tidak dapat dipisah-pisah menjadi tugas-tugas independen yang cukup tetapi dapat secara rekursif dibagi menjadi tugas-tugas yang independen di antara mereka sendiri (misalnya menyortir bagiannya adalah independen tetapi menggabungkan 2 bagian yang disortir menjadi keseluruhan yang disortir tidak).
sumber
F / J juga memiliki keuntungan berbeda ketika Anda memiliki operasi penggabungan yang mahal. Karena ia terbagi menjadi struktur pohon, Anda hanya melakukan log2 (n) penggabungan sebagai lawan n penggabungan dengan pemisahan ulir linear. (Ini memang membuat asumsi teoritis bahwa Anda memiliki sebanyak prosesor sebagai utas, tetapi masih menguntungkan) Untuk tugas pekerjaan rumah, kami harus menggabungkan beberapa ribu array 2D (semua dimensi yang sama) dengan menjumlahkan nilai pada setiap indeks. Dengan garpu bergabung dan prosesor P waktu mendekati log2 (n) ketika P mendekati tak terbatas.
1 2 3 .. 7 3 1 .... 8 5 4
4 5 6 + 2 4 3 => 6 9 9
7 8 9 .. 1 1 0 .... 8 9 9
sumber
Anda akan kagum dengan kinerja ForkJoin dalam aplikasi seperti crawler. di sini adalah tutorial terbaik yang akan Anda pelajari.
sumber
Jika masalahnya adalah kita harus menunggu utas lainnya untuk menyelesaikan (seperti dalam hal pengurutan array atau jumlah array), fork join harus digunakan, karena Executor (Executors.newFixedThreadPool (2)) akan tersedak karena terbatas jumlah utas. Kolam forkjoin akan membuat lebih banyak utas dalam hal ini untuk menutupi utas yang diblokir untuk mempertahankan paralelisme yang sama
Sumber: http://www.oracle.com/technetwork/articles/java/fork-join-422606.html
Masalah dengan pelaksana untuk menerapkan algoritma divide and conquer tidak terkait dengan membuat subtugas, karena Callable bebas untuk mengirimkan subtugas baru kepada pelaksana dan menunggu hasilnya secara sinkron atau asinkron. Masalahnya adalah paralelisme: Ketika Callable menunggu hasil Callable lain, itu diletakkan dalam keadaan menunggu, sehingga membuang-buang kesempatan untuk menangani Callable lain yang antri untuk dieksekusi.
Garpu / gabung kerangka ditambahkan ke paket java.util.concurrent di Java SE 7 melalui upaya Doug Lea mengisi celah itu
Sumber: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html
Pool berusaha untuk mempertahankan thread yang cukup aktif (atau tersedia) dengan menambahkan, menangguhkan, atau melanjutkan kembali thread pekerja internal secara dinamis, bahkan jika beberapa tugas terhenti menunggu untuk bergabung dengan yang lain. Namun, tidak ada penyesuaian seperti itu dijamin dalam menghadapi IO diblokir atau sinkronisasi yang tidak dikelola lainnya
public int getPoolSize () Mengembalikan jumlah utas pekerja yang sudah dimulai tetapi belum dihentikan. Hasil yang dikembalikan oleh metode ini mungkin berbeda dari getParallelism () ketika utas dibuat untuk mempertahankan paralelisme saat yang lain diblokir secara kooperatif.
sumber
Saya ingin menambahkan jawaban singkat untuk mereka yang tidak punya banyak waktu untuk membaca jawaban panjang. Perbandingan diambil dari buku Applied Akka Patterns:
sumber