Bagaimana kerangka kerja fork / join lebih baik daripada kumpulan utas?

134

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?

Joonas Pulakka
sumber

Jawaban:

136

Saya pikir kesalahpahaman dasarnya adalah, bahwa contoh-contoh Fork / Join TIDAK menunjukkan kerja mencuri, tetapi hanya semacam standar pembagian dan taklukkan.

Mencuri pekerjaan akan seperti ini: Pekerja B telah menyelesaikan pekerjaannya. Dia orang yang baik hati, jadi dia melihat sekeliling dan melihat Pekerja A masih bekerja sangat keras. Dia berjalan mendekat dan bertanya, "Hei, Nak, aku bisa membantumu." Balasan "Keren, aku punya tugas ini 1000 unit. Sejauh ini aku sudah selesai 345 meninggalkan 655. Bisakah kamu bekerja pada nomor 673 hingga 1000, aku akan melakukan 346 ke 672." B berkata, "Oke, mari kita mulai jadi kita bisa pergi ke pub lebih awal."

Anda lihat - para pekerja harus berkomunikasi antara satu sama lain bahkan ketika mereka memulai pekerjaan nyata. Ini adalah bagian yang hilang dalam contoh.

Contoh di sisi lain hanya menampilkan sesuatu seperti "gunakan subkontraktor":

Pekerja A: "Sial, saya punya 1000 unit pekerjaan. Terlalu banyak untuk saya. Saya akan mengerjakan 500 sendiri dan mensubkontrakkan 500 kepada orang lain." Ini berlanjut sampai tugas besar dipecah menjadi paket kecil masing-masing 10 unit. Ini akan dieksekusi oleh pekerja yang tersedia. Tetapi jika satu paket adalah sejenis pil racun dan memakan waktu lebih lama dari paket lainnya - nasib buruk, fase pembagian sudah berakhir.

Satu-satunya perbedaan yang tersisa antara Fork / Gabung dan membelah tugas di muka adalah ini: Saat membelah di depan Anda memiliki antrian kerja penuh sejak awal. Contoh: 1000 unit, ambangnya adalah 10, sehingga antrian memiliki 100 entri. Paket-paket ini didistribusikan kepada anggota threadpool.

Fork / Bergabung lebih kompleks dan mencoba untuk menjaga jumlah paket dalam antrian lebih kecil:

  • Langkah 1: Masukkan satu paket berisi (1 ... 1000) ke dalam antrian
  • Langkah 2: Satu pekerja mengeluarkan paket (1 ... 1000) dan menggantinya dengan dua paket: (1 ... 500) dan (501 ... 1000).
  • Langkah 3: Paket satu pekerja muncul (500 ... 1000) dan mendorong (500 ... 750) dan (751 ... 1000).
  • Langkah n: Tumpukan berisi paket-paket ini: (1..500), (500 ... 750), (750 ... 875) ... (991..1000)
  • Langkah n +1: Paket (991..1000) muncul dan dieksekusi
  • Langkah n + 2: Paket (981..990) muncul dan dieksekusi
  • Langkah n + 3: Paket (961..980) muncul dan dibagi menjadi (961 ... 970) dan (971..980). ....

Anda lihat: di Fork / Bergabung, antriannya lebih kecil (6 pada contoh) dan fase "split" dan "work" disisipkan.

Ketika banyak pekerja bermunculan dan mendorong secara bersamaan interaksi tentu saja tidak begitu jelas.

AH
sumber
Saya pikir ini memang jawabannya. Saya ingin tahu apakah ada contoh Fork / Join aktual di mana saja yang akan menunjukkan juga kemampuannya mencuri? Dengan contoh dasar, jumlah beban kerja cukup mudah diprediksi dari ukuran unit (mis. Panjang array) sehingga pemisahan di muka mudah. Mencuri tentu akan membuat perbedaan dalam masalah di mana jumlah beban kerja per unit tidak dapat diprediksi dengan baik dari ukuran unit.
Joonas Pulakka
AH Jika jawaban Anda benar, itu tidak menjelaskan caranya. Contoh yang diberikan oleh Oracle tidak menghasilkan pencurian pekerjaan. Bagaimana cara fork dan join bekerja seperti pada contoh yang Anda jelaskan di sini? Bisakah Anda menunjukkan beberapa kode Java yang akan membuat garpu dan ikut mencuri bekerja seperti yang Anda gambarkan? terima kasih
Marc
@ Markc: Maaf, tapi saya tidak punya contoh.
13-13
6
Masalah dengan contoh Oracle, IMO, bukanlah bahwa ia tidak menunjukkan pencurian pekerjaan (itu memang, seperti yang dijelaskan oleh AH) tetapi bahwa mudah untuk mengkodekan suatu algoritma untuk ThreadPool sederhana yang bekerja dengan baik (seperti yang dilakukan Joonas). FJ 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. Lihat jawaban saya sebagai contoh
ashirley
2
Beberapa contoh pencurian tempat kerja mungkin berguna: h-online.com/developer/features/…
volley
27

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.

Tom Hawtin - tackline
sumber
Tetapi mengapa FJ tidak akan menunggu utas yang paling lambat? Ada sejumlah subtugas yang ditentukan sebelumnya, dan tentu saja beberapa di antaranya akan selalu menjadi yang terakhir untuk diselesaikan. Menyesuaikan maxSizeparameter dalam contoh saya akan menghasilkan pembagian subtugas yang hampir mirip dengan "binary splitting" pada contoh FJ (dilakukan dalam compute()metode, yang menghitung sesuatu atau mengirim subtugas ke invokeAll()).
Joonas Pulakka
Karena mereka jauh lebih kecil - saya akan menambah jawaban saya.
Tom Hawtin - tackline
Oke, jika jumlah subtugas urutan besarnya lebih besar dari apa yang sebenarnya bisa diproses secara paralel (yang masuk akal, untuk menghindari harus menunggu yang terakhir), maka saya bisa melihat masalah koordinasi. Contoh FJ mungkin menyesatkan jika divisi itu seharusnya granular: menggunakan ambang 100000, yang untuk gambar 1000x1000 akan menghasilkan 16 subtugas aktual, masing-masing memproses 62500 elemen. Untuk gambar 10000x10000 akan ada 1024 subtugas, yang sudah merupakan sesuatu.
Joonas Pulakka
19

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

  1. Setidaknya perlu ada banyak utas yang berjalan karena ada CPU yang tersedia, karena menjalankan lebih sedikit utas akan meninggalkan inti yang tidak digunakan.
  2. Maksimal harus ada sebanyak mungkin utas yang berjalan karena ada CPU yang tersedia, karena menjalankan lebih banyak utas akan membuat beban tambahan untuk Penjadwal yang menetapkan CPU pada utas berbeda yang menyebabkan beberapa waktu CPU untuk pergi ke penjadwal daripada tugas komputasi kami.

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:

class AbcAlgorithm implements Runnable {
    public void run() {
        Future<StepAResult> aFuture = threadPool.submit(new ATask());
        StepBResult bResult = stepB();
        StepAResult aResult = aFuture.get();
        stepC(aResult, bResult);
    }
}

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:

class AbcAlgorithm implements Runnable {
    public void run() {
        ATask aTask = new ATask());
        aTask.fork();
        StepBResult bResult = stepB();
        StepAResult aResult = aTask.join();
        stepC(aResult, bResult);
    }
}

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 memanggil stepC. 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 joinpanggilan ForkJoinTasks. 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. Dan ForkJoinPoolsebenarnya bisa melakukan hal itu jika kita menggunakan ManagedBlockers.

Fibonacci

Dalam JavaDoc untuk RecursiveTask adalah contoh untuk menghitung angka Fibonacci menggunakan Fork / Bergabung. Untuk solusi rekursif klasik, lihat:

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

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:

class Fibonacci extends RecursiveTask<Long> {
    private final long n;

    Fibonacci(long n) {
        this.n = n;
    }

    public Long compute() {
        if (n <= 1) {
            return n;
        }
        Fibonacci f1 = new Fibonacci(n - 1);
        f1.fork();
        Fibonacci f2 = new Fibonacci(n - 2);
        return f2.compute() + f1.join();
   }
}

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:

class FibonacciBigSubtasks extends RecursiveTask<Long> {
    private final long n;

    FibonacciBigSubtasks(long n) {
        this.n = n;
    }

    public Long compute() {
        return fib(n);
    }

    private long fib(long n) {
        if (n <= 1) {
            return 1;
        }
        if (n > 10 && getSurplusQueuedTaskCount() < 2) {
            final FibonacciBigSubtasks f1 = new FibonacciBigSubtasks(n - 1);
            final FibonacciBigSubtasks f2 = new FibonacciBigSubtasks(n - 2);
            f1.fork();
            return f2.compute() + f1.join();
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }
}

Ini membuat subtugas jauh lebih kecil karena mereka hanya terpecah ketika n > 10 && getSurplusQueuedTaskCount() < 2benar, 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

  • Ya, dalam contoh Anda Fork / Bergabung tidak memiliki keunggulan dibandingkan kolam utas klasik.
  • Fork / Gabung dapat secara drastis meningkatkan kinerja saat pemblokiran terlibat
  • Fork / Gabung menghindari beberapa masalah kebuntuan
yankee
sumber
17

Fork / join berbeda dari thread pool karena menerapkan pencurian kerja. Dari Fork / Bergabunglah

Seperti halnya ExecutorService, kerangka kerja fork / join mendistribusikan tugas ke utas pekerja di kumpulan utas. Kerangka kerja fork / join berbeda karena menggunakan algoritma mencuri kerja. Utas pekerja yang kehabisan hal untuk dilakukan dapat mencuri tugas dari utas lain yang masih sibuk.

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.

Matthew Farwell
sumber
5
Kumpulan utas biasanya adalah instance ThreadPoolExecutor . Dengan demikian, tugas masuk antrian ( BlockingQueue dalam praktik), dari mana utas pekerja mengambil tugas segera setelah mereka menyelesaikan tugas sebelumnya. Tugas tidak ditugaskan sebelumnya pada utas tertentu, sejauh yang saya mengerti. Setiap utas memiliki (paling banyak) 1 tugas sekaligus.
Joonas Pulakka
4
AFAIK ada satu Antrian untuk satu ThreadPoolExecutor yang pada gilirannya mengontrol beberapa Thread. Ini berarti bahwa menugaskan tugas atau Runnables (bukan utas!) Ke pelaksana tugas juga tidak dialokasikan ke utas tertentu. Cara FJ juga melakukannya. Sejauh ini tidak ada manfaatnya menggunakan FJ.
AH
1
@ YA Ya, tetapi garpu / gabung memungkinkan Anda untuk membagi tugas saat ini. Utas yang menjalankan tugas dapat membaginya menjadi dua tugas yang berbeda. Jadi dengan ThreadPoolExecutor Anda memiliki daftar tugas yang tetap. Dengan fork / join, tugas pelaksana dapat membagi tugasnya sendiri menjadi dua, yang kemudian dapat diambil oleh utas lain ketika mereka telah menyelesaikan pekerjaan mereka. Atau Anda jika Anda selesai dulu.
Matthew Farwell
1
@Matthew Farwell: Dalam contoh FJ , dalam setiap tugas, 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.
Joonas Pulakka
2
@ Matthew Farwell: Mungkin saja saya tidak mengerti semua tentang FJ, tetapi jika subtugas telah memutuskan untuk mengeksekusi computeDirectly()metodenya, tidak ada cara untuk mencuri apa pun lagi. Seluruh pemisahan dilakukan secara apriori , setidaknya dalam contoh.
Joonas Pulakka
14

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:

  • Kepala dan ujung daftar tugas dapat disinkronkan secara independen, mengurangi pertikaian pada daftar.
  • Subpohon yang signifikan dari pekerjaan ini dipisahkan dan disusun kembali oleh utas yang sama, sehingga tidak diperlukan koordinasi antar utas untuk sub-subper ini.
  • Ketika sebuah thread mencuri, dibutuhkan sepotong besar yang kemudian dibagi lagi ke dalam daftarnya sendiri
  • Pekerjaan menguatkan berarti benang hampir sepenuhnya digunakan sampai akhir proses.

Kebanyakan skema membagi dan menaklukkan menggunakan kumpulan utas membutuhkan lebih banyak komunikasi dan koordinasi antar-utas.

iain
sumber
13

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:

Secara keseluruhan, kita dapat mengatakan bahwa ThreadPoolExecutor lebih disukai di mana beban kerja dibagi secara merata di seluruh utas pekerja. Untuk dapat menjamin hal ini, Anda harus tahu persis seperti apa data input tersebut. Sebaliknya, ForkJoinPool memberikan kinerja yang baik terlepas dari data input dan karenanya merupakan solusi yang jauh lebih kuat.

tembakan
sumber
8

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:

  • urutkan kuartal pertama
  • urutkan kuartal kedua
  • gabungkan 2 kuartal pertama
  • urutkan kuartal ketiga
  • urutkan kuartal keempat
  • gabungkan 2 kuartal terakhir
  • menggabungkan 2 bagian

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

Ashirley
sumber
6

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

Daemon Fisher
sumber
3

Anda akan kagum dengan kinerja ForkJoin dalam aplikasi seperti crawler. di sini adalah tutorial terbaik yang akan Anda pelajari.

Logika Fork / Join sangat sederhana: (1) pisahkan (garpu) setiap tugas besar menjadi tugas yang lebih kecil; (2) memproses setiap tugas dalam utas terpisah (memisahkannya menjadi tugas yang lebih kecil jika perlu); (3) gabungkan hasilnya.

Daniel Adenew
sumber
3

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.

VS
sumber
2

Saya ingin menambahkan jawaban singkat untuk mereka yang tidak punya banyak waktu untuk membaca jawaban panjang. Perbandingan diambil dari buku Applied Akka Patterns:

Keputusan Anda apakah akan menggunakan fork-join-executor atau thread-pool-executor sebagian besar didasarkan pada apakah operasi dalam dispatcher itu akan diblokir. Fork-join-executor memberi Anda jumlah maksimum thread aktif, sedangkan thread-pool-executor memberi Anda jumlah thread yang tetap. Jika utas diblokir, fork-join-executor akan membuat lebih banyak, sedangkan utas-gabungan-pelaksana tidak akan. Untuk memblokir operasi, Anda biasanya lebih baik dengan pelaksana thread-pool-karena mencegah jumlah thread Anda dari meledak. Lebih banyak operasi "reaktif" lebih baik di fork-join-executor.

Vadim S.
sumber