Çatal/birleştirme çerçevesini iplik havuzundan nasıl daha iyi?

Yeni çatal/katılma çerçevesini kullanmanın yararları nelerdir? sadece büyük görevi başlangıçta N alttakımlarına bölerek, önbelleğe alınmış bir iş parçacığı havuzuna gönderir ( Yürütücüler ) ve her bir görevin tamamlanmasını bekliyor musunuz? Bence çatal/soyutlamayı kullanmanın problemi nasıl basitleştirdiğini ya da çözümü yıllardır sahip olduğumuzdan daha verimli hale getirdiğini göremiyorum.

Örneğin, öğretici örnek içindeki paralelleştirilmiş bulanıklaştırma algoritması, böyle uygulandı:

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
    }
}

Başlangıçta bölün ve görevleri iş parçacığına gönder:

// 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 futures = new ArrayList();

// 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!

Görevler, iş parçacığı kullanılabilir hale getirildikçe, iş parçacığı havuzu kuyruğuna gider. Bölme işlemi yeterince ayrıntılı olduğu sürece (özellikle son görevi beklemek zorunda kalmamak için) ve iş parçacığı havuzunda (en az N işlemci) iplik varsa, tüm işlemciler tüm hesaplama tamamlanana kadar tam hızda çalışır.

Bir şey mi eksik? Çatal/birleştirme çerçevesinin kullanılmasının katma değeri nedir?

103

10 cevap

Temel yanlış anlaşılma, Çatal/Katılma örneklerinin çalmadığını göstermenin çalınmasını , ancak sadece bir tür standart bölünme ve fethetmesi olduğunu düşünüyorum.

Çalmak işe yaramazdı: İşçi B işini bitirdi. O bir tür, bu yüzden etrafına bakıp A İşçi'sinin hala çok çalıştıklarını görüyor. Gezinip şöyle sorar: "Hey delikanlı, sana yardım edebilirim." Cevaplar. "Cool, 1000 birimden oluşan bu görevim var. Şimdiye kadar 345'i 655'yi terkettim. Lütfen 673'den 1000'e kadar çalışabilir misiniz, 346'dan 672'ye kadar çalışacağım." B "Tamam, hadi başlayalım, daha önce pub'a gidebiliriz" diyor.

Görüyorsunuz - işçiler, gerçek işe başladıklarında bile birbirleri arasında iletişim kurmalılar. Bu örneklerdeki eksik kısım.

Öte yandan örnekler sadece "alt yüklenicilerin kullanımı" gibi bir şeyi göstermektedir:

İşçi A: "Dang, 1000 tane işim var. Benim için çok fazla. 500 kendim yapacağım ve 500 kişiyi bir başkasına devredeceğim." Bu, büyük görev her biri 10 birimden oluşan küçük paketlere bölünene kadar devam eder. Bunlar mevcut işçiler tarafından yürütülecek. Ancak bir paket bir tür zehirli hap ise ve diğer paketlerden çok daha uzun sürerse - şanssızlık, bölünme aşaması sona erer.

Çatal/Birleştirme ve görevi ön ayırma arasında kalan tek fark şudur: Ön tarafa ayrılırken, iş kuyruğu baştan itibaren tam sağa kalır. Örnek: 1000 birim, eşik 10, yani sıra 100 girdiye sahip. Bu paketler threadpool üyelerine dağıtılır.

Çatal/Birleştir daha karmaşıktır ve kuyruktaki paket sayısını daha küçük tutmaya çalışır:

  • 1. Adım: (1 ... 1000) içeren bir paketi sıraya koyun
  • 2. Adım: Bir işçi paketi (1 ... 1000) açar ve iki paketle değiştirir: (1 ... 500) ve (501 ... 1000).
  • 3. Adım: Bir işçi paketi (500 ... 1000) açar ve iter (500 ... 750) ve (751 ... 1000).
  • Adım n: Yığın bu paketleri içerir: (1..500), (500 ... 750), (750 ... 875) ... (991..1000)
  • Adım n + 1: Paket (991..1000) attı ve yürütüldü
  • Adım n + 2: Paket (981..990) attı ve yürütüldü
  • Adım n + 3: Paket (961..980) atılır ve (961 ... 970) ve (971..980) 'e bölünür. ....

Gördüğünüz gibi: Çatal/Katıl sıraya göre daha küçük (örnekte 6) ve "bölünmüş" ve "iş" aşamaları serpiştirilmiş.

Birden çok işçi patlayıp aynı anda iterken, etkileşimler elbette çok net değildir.

114
katma
Bence bu gerçekten cevap. İşlerini çalma yeteneklerini de gösterecek herhangi bir yerde gerçek Çatal/Katılma örnekleri olup olmadığını merak ediyorum. Temel örnekler ile iş yükünün miktarı, ünitenin büyüklüğünden (örn. Dizi uzunluğu) oldukça mükemmel bir şekilde tahmin edilebilir, bu nedenle ön bölme işlemi kolaydır. Çalma, ünite başına iş yükü miktarının, ünitenin büyüklüğünden iyi tahmin edilebilen olmadığı problemlerde kesinlikle fark yaratacaktır.
katma yazar Joonas Pulakka, kaynak
@Marc: Üzgünüm, ancak müsait bir örneğim yok.
katma yazar A.H., kaynak
Çalışmanın çalındığı yerlere dair bazı örnekler: h-online.com/developer/features/…
katma yazar volley, kaynak
Oracle'ın örnek IMO'su ile ilgili problem, çalışmanın çalındığını göstermediği (A.H. tarafından açıklandığı gibi) değil, aynı zamanda Joonas'ın yaptığı gibi basit bir ThreadPool için de bir algoritmanın kodlanması kolay değildir. F-J, işin yeterince bağımsız görevlere bölünemediği, ancak özünde kendi aralarında bağımsız olan görevlere ayrılabildiği zaman en faydalıdır. Örnek için cevabımı görün
katma yazar Edson Medina, kaynak
A.H. Cevabınız doğruysa, nasıl olduğunu açıklamıyor. Oracle tarafından verilen örnek, çalışmanın çalınmasına neden olmaz. Çatal ve katılma, burada açıkladığınız örnekte nasıl çalışır? Çatalacak ve çalmaya katılacağınız bir Java kodu gösterebilir misiniz? Teşekkürler
katma yazar Marc, kaynak

Eğer meşgul meseleleriniz% 100 bağımsız olarak çalışıyorsa, bu bir Çatal-Join (FJ) havuzunda n dişlerinden daha iyi olacaktır. Ama asla böyle yürümez.

Sorunu kesin olarak n eşit parçalara ayıramayabilir. Yapsanız bile, iş parçacığı zamanlaması adil olmaktan çıkar. En yavaş iş parçacığı için beklersiniz. Eğer birden fazla göreviniz varsa, her biri n-yollu paralellikten (genellikle daha verimli) daha azıyla çalışabilir, ancak diğer görevler bittiğinde n-yoluna gider.

Öyleyse neden sorunu sadece FJ boyutundaki parçalara ayırmıyoruz ve bunun üzerinde bir iş parçacığı havuzu çalışması yapmıyoruz. Tipik FJ kullanımı problemi küçük parçalara ayırır. Bunları rastgele sırayla yapmak, donanım düzeyinde çok koordinasyon gerektirir. Genel giderler bir katil olurdu. FJ'de, görevler, Son Giren İlk Çıkar sırasına göre (LIFO/yığın) iş parçacığının okumaya başladığı bir sıraya konur ve çalma (genellikle çekirdek işte) (İlk Giren İlk Çıkar) (FIFO/"sıra") yapılır. Sonuç, uzun dizi işlemenin, küçük parçalara bölünmesine rağmen büyük ölçüde ardışık olarak yapılabilmesidir. (Aynı zamanda problemi, küçük, büyük boyutlu parçalara bir büyük patlamada kırmak önemli olmayabilir. Deneme olmadan bir çeşit hiyerarşi ile uğraştığınızı söyleyin.)

Sonuç: FJ, düzensiz durumlarda donanım ipliklerinin daha verimli kullanılmasına izin verir, bu da birden fazla ipliğiniz varsa her zaman olacaktır.

23
katma
Ama neden FJ en yavaş iplik için de beklemiyor? Önceden belirlenmiş bir sayıda alt görev vardır ve elbette bunların bazıları her zaman sonuncusu olacaktır. Örneğimde maxSize parametresinin ayarlanması, FJ örneğindeki "ikili bölme" (neredeyse compute() yöntemiyle yapılan "ikili bölme" yöntemiyle neredeyse benzer alt bölümler üretecektir. veya invokeAll() öğesine alt görevler gönderir.
katma yazar Joonas Pulakka, kaynak
Tamam, eğer alt görevlerin sayısı, aslında paralel olarak işlenebilecek olandan daha büyük olan büyüklük sırasına göre sıralanırsa (ki bu mantıklıdır, sonuncuyu beklemek zorunda kalmamak için), o zaman koordinasyon sorunlarını görebilirim. Bölünme olması gerekiyorsa FJ örneği yanıltıcı olabilir Bu granül olabilir: 1000x1000 görüntü için her biri 62500 öğeyi işleyen 16 gerçek alttakım üretecek olan 100000 eşiğini kullanır. 10000x10000 görüntü için zaten bir şey olan 1024 alttakım olurdu.
katma yazar Joonas Pulakka, kaynak
Çünkü çok daha küçükler - Cevabımı ekleyeceğim.
katma yazar Tom Hawtin - tackline, kaynak

Fork/join is different from a thread pool because it implements work stealing. From Fork/Join

Herhangi bir ExecutorService'de olduğu gibi, fork/join çerçevesi görevleri dağıtır   iş parçacığı bir iş parçacığı havuzuna. Çatal/birleştirme çerçevesi   Farklı bir çalışma algoritması kullanır çünkü. Çalışan konuları   Yapılması gereken şeylerin tükenmesi, diğer iş parçacıklarından gelen görevleri çalabilir   hala meşgul.

İki iş parçacığınız olduğunu ve sırasıyla 1, 1, 5 ve 6 saniye süren 4 görev a, b, c, d olduğunu varsayalım. Başlangıçta a ve b, 1 ve c ve d ile 2 numaralı dişlere atanır. Bir iş parçacığı havuzunda, bu 11 saniye sürer. Çatal/birleştirme ile, iplik 1 tamamlanır ve iş parçacığı 2'den çalınabilir, bu nedenle görev d iş parçacığı 1 tarafından yürütülecektir. İş parçacığı 1 a, b ve d yürütür, iş parçacığı 2 sadece c. Genel süre: 8 saniye, 11 değil.

DÜZENLEME: Joonas'ın işaret ettiği gibi, görevlerin bir iş parçacığına önceden tahsis edilmesi gerekmez. Çatal/birleştirme fikri, bir ipliğin bir görevi birden fazla alt parçaya bölmeyi seçebilmesidir. Yukarıdakileri yeniden göndermek için:

We have two tasks (ab) and (cd) which take 2 and 11 seconds respectively. Thread 1 starts to execute ab and split it into two sub-tasks a & b. Similarly with thread 2, it splits into two sub-tasks c & d. When thread 1 has finished a & b, it can steal d from thread 2.

12
katma
Konu havuzları genellikle ThreadPoolExecutor örnekleridir . Böyle bir durumda, işler sıra ( BlockingQueue . Görevler, anladığım kadarıyla belirli konulara önceden atanmış değil . Her iş parçacığı bir seferde (en fazla) 1 görevi vardır.
katma yazar Joonas Pulakka, kaynak
@Matthew Farwell: Her görev dahilinde, FJ örneğinde compute() görevi hesaplar veya iki alt bölüme ayırır. Seçtiği seçenek, görev boyutunda 'ye bağlıdır ( if (mLength ), bu yüzden sabit sayıda görev oluşturmanın süslü bir yoludur. 1000x1000 görüntü için, aslında bir şeyi hesaplayan tam 16 alt görev olacaktır. Ek olarak, yalnızca alttakımlar üreten ve çağıran ve kendileriyle ilgili hiçbir şey hesaplamayan 15 (= 16 - 1) "orta" görev olacaktır.
katma yazar Joonas Pulakka, kaynak
@Matthew Farwell: Tüm FJ'leri anlamıyorum, ancak bir alt-görev computeDirectly() yöntemini yürütmeye karar verdiyse, artık hiçbir şey çalmanın bir yolu yok. Bütün bölünme en azından örnekte a priori yapılır.
katma yazar Joonas Pulakka, kaynak
AFAIK, bir ThreadPoolExecutor için bir Kuyruğudur ve bu da birkaç Konuları kontrol eder. Bu, bir yürütücüye görevleri veya Runnables (Threads! Değil) atamanın görevlerin belirli bir Threads öğesine önceden atanmamış olduğu anlamına gelir. Tam olarak FJ'nin de yaptığı gibi. Şimdiye kadar FJ kullanmanın yararı yok.
katma yazar A.H., kaynak
@JoonasPulakka: Bu tartışmadaki şeyleri ele almaya çalışan bir cevap yazdım.
katma yazar A.H., kaynak
@AH. Evet, ancak fork/join mevcut görevi bölmenizi sağlar. Görevi yürüten iş parçacığı, onu iki farklı görevlere ayırabilir. Böylece ThreadPoolExecutor ile sabit bir görevler listesi vardır. Çatal/birleştirmeyle, yürütme görevi kendi görevini ikiye bölebilir, bu da işlerini bitirdikten sonra diğer iş parçacıkları tarafından alınabilir. Ya da önce sen bitirirsin.
katma yazar Matthew Farwell, kaynak
@Joonas, evet, bu, bölme için seçtikleri stratejidir. Fakat her bir alt görevin ne kadar süreceğini bilmiyorlar. Bir alttakinin 1 saniye sürmesi ve bir diğerinin (aynı 'boyut') 15 saniye sürmesi mümkündür. Bu durumda, iş çalmak olabilirdi. Belki ne dediğini yanlış anladım.
katma yazar Matthew Farwell, kaynak

Yukarıdaki herkes, çalınan hırsızlıktan elde edilen faydaları düzeltmek için doğrudur, ancak bunun nedenini genişletmek için.

Birincil fayda, çalışan iş parçacıkları arasındaki verimli koordinasyon. İşin ayrılması ve yeniden bir araya getirilmesi gerekir ki bu da koordinasyon gerektirir. A.H'ın cevabında görebileceğiniz gibi her iş parçacığının kendi çalışma listesi vardır. Bu listenin önemli bir özelliği, sıralanmasıdır (üstteki büyük görevler ve alttaki küçük görevler). Her iş parçacığı, listenin en altındaki görevleri yürütür ve diğer iş parçacıklarının listesinin üst kısmındaki görevleri çalar.

Bunun sonucu:

  • Görev listelerinin başı ve kuyruğu bağımsız olarak senkronize olabilir ve listede çekişmeyi azaltabilir.
  • Çalışmanın önemli alt parçaları aynı iş parçacığı tarafından bölünür ve yeniden birleştirilir, bu nedenle bu alt sayfalar için ara parçacık koordinasyonu gerekmez.
  • Bir iş parçacığı çalıyorsa, büyük bir parça alır ve ardından kendi listesinin üzerine bölünür.
  • İş çeliği, iş parçacığının, işlemin sonuna kadar neredeyse tamamen kullanılmış olduğu anlamına gelir.

İplik havuzlarını kullanan çoğu diğer böl ve ele geçirme şemaları daha çok iplik arası iletişim ve koordinasyon gerektirir.

10
katma

Bu örnekte, Çatal/Katılma hiçbir değer eklemez çünkü forking gerekli değildir ve iş yükü çalışan iş parçacıklarına eşit olarak bölünür. Çatal/Katılma sadece ek yükü ekler.

İşte bir güzel makale konuyla ilgili . Alıntı:

Genel olarak, ThreadPoolExecutor'ın tercih edilecek olduğunu söyleyebiliriz   iş yükü çalışan iş parçacıklarına eşit olarak bölünür. Yapabilmek   Bunu garanti etmek için, girdi verilerini tam olarak bilmeniz gerekir   benziyor. Buna karşılık, ForkJoinPool iyi bir performans sağlar   giriş verisine bakılmaksızın ve bu nedenle önemli ölçüde daha sağlamdır   Çözelti.

10
katma
Çok güzel yazı, teşekkürler!
katma yazar Joonas Pulakka, kaynak

İplik havuzlarının ve Çatal/Birleşmenin nihai hedefi aynıdır: Her ikisi de mevcut CPU gücünü maksimum verim için ellerinden gelenin en iyisini kullanmak ister. Maksimum verim, mümkün olduğunca çok sayıda görevin uzun bir sürede tamamlanması gerektiği anlamına gelir. Bunu yapmak için ne gerekiyor? (Aşağıdakiler için hesaplama görevlerinde herhangi bir eksiklik olmadığı varsayılacaktır:% 100 CPU kullanımı için her zaman yeterli olacaktır.Ayrıca "CPU" hiper-iş parçacığı durumunda çekirdekler veya sanal çekirdekler için eşdeğer olarak kullanıyorum).

  1. En azından, CPU'lar mevcut olduğu için çalışan çok sayıda iş parçacığına ihtiyaç vardır, çünkü daha az iş parçacığının çalıştırılması çekirdek kullanılmadan bırakılır.
  2. En yüksek düzeyde, CPU'lar mevcut olduğu kadar çok sayıda iş parçacığı olmalıdır çünkü daha fazla iş parçacığının çalıştırılması, CPU'ları farklı iş parçacıklarına atayan Zamanlayıcı için ek yük oluşturacaktır; bu, bazı CPU zamanlarının, bizim hesaplamamıza değil, zamanlayıcıya gitmesine neden olur. görev.

Böylece, maksimum verim için, CPU'lardan tam olarak aynı sayıda ipliğe sahip olmamız gerektiğini anladık. Oracle'ın bulanıklaştırma örneğinde, hem mevcut CPU'ların sayısına eşit sayıda iş parçacığı sayısına sahip bir sabit boyutlu iş parçacığı havuzu alabilir veya bir iş parçacığı havuzu kullanabilirsiniz. Fark etmez, haklısın!

So when will you get into trouble with a thread pools? That is if a thread blocks, because your thread is waiting for another task to complete. Assume the following example:

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

Burada gördüğümüz, üç adım A, B ve C'den oluşan bir algoritmadır. A ve B birbirinden bağımsız olarak gerçekleştirilebilir, ancak C aşaması, A ve B adımının sonucuna ihtiyaç duyar. Bu algoritmanın yaptığı şey, A görevine gönderilir. threadpool ve doğrudan görev b gerçekleştirin. Bundan sonra iş parçacığı A işinin yapılması için bekleyecek ve adım C ile devam edecektir. A ve B aynı anda tamamlanırsa, her şey yolunda. Ama ya B'nin B'den daha uzun sürmesi? Bunun sebebi A görevinin doğasını gerektirdiğinden, ancak durum böyle olmayabilir çünkü  Görev için iş parçacığı Başlangıçta mevcut A ve görev A'nın beklemesi gerekiyor. (Eğer sadece tek bir CPU mevcutsa ve bu yüzden threadpool'unuz sadece tek bir iş parçacığına sahipse, bu bile bir kilitlenmeye neden olacaktır, ancak şimdilik bu noktaya ek olarak). Bunun anlamı, sadece B görevini yürüten iş parçacığının tüm iş parçacığını engellemesidir . CPU'lar ile aynı sayıda iş parçacığına sahip olduğumuzdan ve bir iş parçacığı engellendiğinden, bir CPU boşta kalıyor demektir .

Çatal/Birleştir bu sorunu çözer: Çatal/birleştirme çerçevesinde, aşağıdaki gibi aynı algoritmayı yazarsınız:

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

Aynı görünüyor değil mi? Ancak ipucu, aTask.join 'un engellenmeyeceğidir . Bunun yerine çalınan çalınan burada devreye girer: İş parçacığı geçmişte çatallanmış olan diğer işler için etrafa bakacak ve bunlarla devam edecektir. Öncelikle, kendisine attığı görevlerin işlenmeye başladığını kontrol eder. Bu yüzden eğer A henüz başka bir iş parçacığı tarafından başlatılmamışsa, bir sonraki görevini yapar, aksi takdirde diğer iş parçacıklarının sırasını kontrol eder ve işlerini çalacaktır. Başka bir iş parçacığının bu görevi tamamlandığında, A'nın şimdi tamamlanıp tamamlanmadığını kontrol eder. Yukarıdaki algoritma ise stepC 'yi arayabilir. Aksi takdirde çalmak için başka bir görev arar. Böylece çatal/birleştirme havuzları, engelleme eylemleri karşısında bile% 100 CPU kullanımı sağlayabilir .

Ancak bir tuzak vardır: İşten çalma sadece ForkJoinTask 'un join çağrısı için mümkündür. Başka bir iş parçacığı beklemek veya bir G/Ç eylemi beklemek gibi harici engelleme eylemleri için yapılamaz. Peki ya, I/O'nun tamamlanmasını beklemek ortak bir görev midir? Bu durumda, engelleme eylemi tamamlanır tamamlanmaz durdurulacak olan Çatal/Birleştir havuzuna ek bir iş parçacığı ekleyebilirsek, yapılacak en iyi ikinci şey olacaktır. Ve ForkJoinPool aslında ManagedBlocker kullanıyorsak bunu yapabilir.

Fibonacci

RecursiveTask için JavaDoc bir Çatal/Birleştir kullanarak Fibonacci sayılarını hesaplamak için örnek. Klasik özyinelemeli bir çözüm için bkz.

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

Açıklandığı gibi JavaDocs, fibonacci sayılarını hesaplamak için oldukça basit bir yoldur, çünkü bu algoritmanın O (2 ^ n) karmaşıklığı vardır, ancak daha basit yollar mümkündür. Ancak bu algoritma çok basit ve anlaşılması kolay, bu yüzden ona bağlıyız. Bunu Çatal/Katıl ile hızlandırmak istediğimizi varsayalım. Saf bir uygulama şöyle görünecekti:

class Fibonacci extends RecursiveTask {
    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();
   }
}

Bu Görev'in ayrıldığı adımlar çok kısadır ve bu yüzden de korkunç bir şekilde çalışacaktır, ancak çerçevenin genel olarak nasıl çok iyi çalıştığını görebilirsiniz: İki summand bağımsız olarak hesaplanabilir, ancak her ikisine de finali oluşturmak için ihtiyaç duyarız. sonuç. Yani bir yarısı başka bir iş parçacığında yapılır. Çarpışmaya girmeden iplik havuzlarıyla aynı işi yapmak (mümkün, ama neredeyse basit değil).

Sadece tamlık için: Bu özyinelemeli yaklaşımı kullanarak Fibonacci sayılarını gerçekten hesaplamak istiyorsanız, optimize edilmiş bir versiyon:

class FibonacciBigSubtasks extends RecursiveTask {
    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);
        }
    }
}

This keeps the subtasks much smaller because they are only split when n > 10 && getSurplusQueuedTaskCount() < 2 is true, which means that there are significantly more than 100 method calls to do (n > 10) and there are not very man tasks already waiting (getSurplusQueuedTaskCount() < 2).

Bilgisayarımda (Hyper-threading sayılırken 8 çekirdek), Intel (R) Core (TM) i7-2720QM CPU @ 2.20GHz) fib (50) klasik yaklaşımla 64 saniye sürüyor ve teorik olarak mümkün olmasa da oldukça dikkat çekici bir kazanç olan Çatal/Birleştirme yaklaşımı ile sadece 18 saniye.

özet

  • Evet, Örneğinizde Çatal/Birleştir'in klasik iplik havuzlarına göre avantajı yoktur.
  • Engel/Katılma, engelleme söz konusu olduğunda performansı önemli ölçüde artırabilir
  • Çatal/Katılma bazı kilitlenme sorunlarını giderir
8
katma

Bir başka önemli fark, F-J ile çoklu, karmaşık "Birleştirme" aşamaları yapabileceğiniz gibi görünüyor. Birleştirme sırasını http://faculty.ycp.edu/~dhovemey/spring2011/cs365 adresinden ele alalım. /lecture/lecture18.html , bu işi önceden bölmek için çok fazla orkestrasyon gerekli olacaktır. Örneğin. Aşağıdakileri yapmanız gerekir:

  • ilk çeyreği ayır
  • ikinci çeyreği ayır
  • ilk 2 çeyreği birleştir
  • üçüncü çeyreği sırala
  • dördüncü çeyreği sırala
  • son 2 çeyreği birleştir
  • 2 yarıyı birleştirin

Onları ilgilendiren birleştirmelerden önce bunları yapmanız gerektiğini nasıl belirtirsiniz?

Öğelerin bir listesi için belirli bir şeyi en iyi nasıl yapacağımıza bakıyorum. Sanırım listeyi önceden bölüp standart bir ThreadPool kullanacağım. F-J, işin yeterince bağımsız görevlere önceden bölünememesi, ancak kendi aralarında bağımsız olan görevlere (örneğin, yarılanların ayrılması bağımsızdır, fakat 2 ayrılan yarının ayrıştırılmış bir bütün halinde birleştirilmesi) yinelemeli olarak bölünebildiği zaman en kullanışlı olanıdır.

7
katma

Pahalı birleştirme işlemleriniz olduğunda F/J'nin de ayrı bir avantajı vardır. Bir ağaç yapısına ayrıldığından, sadece log2 (n), lineer iplik ayırma ile n birleştirme yerine birleşir. (Bu, iş parçacığı olarak birçok işlemciye sahip olduğunuz teorik varsayımı yapar, ama yine de bir avantajdır) Bir ev ödevi için, her indeksdeki değerleri toplayarak birkaç bin 2B diziyi (hepsi aynı boyutlarda) birleştirmek zorunda kaldık. Çatal birleşimi ve P işlemcileri ile zaman, log2 (n) ye yaklaştıkça, P sonsuza yaklaşır.

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

5
katma

Sorun diğer iplikleri (dizi veya dizinin toplamının sıralama durumunda olduğu gibi) tamamlamak için beklemek zorunda olacak şekildedir, fork Yürüten (Executors.newFixedThreadPool (2)) nedeniyle sınırlı için şok gibi kullanılmalıdır birleştirme iş parçacığı sayısı. Forkjoin havuzu, aynı paralellik korumak için engellenmiş iplik için örtmek için bu durumda daha fazla iş parçacığı oluşturacaktır.

Source: http://www.oracle.com/technetwork/articles/java/fork-join-422606.html

Bölünme ve fethetme algoritmalarının uygulanması için yürütücülerle ilgili sorun, subtablar oluşturmayla ilgili değildir; çünkü bir Callable, yöneticisine yeni bir alt görev göndermekte ve sonucunu eşzamanlı veya eşzamansız bir şekilde beklemekte serbesttir. Sorun, paralelliktir: Bir Callable, bir başka Callable'ın sonucunu beklediğinde, bekleme durumuna geçirilir, böylece yürütme için sıraya konulan bir başka Callable'ı ele alma fırsatı doğar.

Java SE 7’den java.util.concurrent paketine eklenen çatal/birleştirme çerçevesi, Doug Lea’nin çabaları bu boşluğu doldurdu

Source: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

Havuz, diğer görevlere katılmak için bekleyen bazı görevler dursa bile, dahili çalışan iş parçacıklarını dinamik olarak ekleyerek, askıya alarak veya sürdürerek yeterli etkin (veya kullanılabilir) iş parçacığı tutmaya çalışır. Ancak, engellenen IO veya diğer yönetilmeyen senkronizasyon karşısında böyle bir ayar garanti edilmez.

public int getPoolSize() Returns the number of worker threads that have started but not yet terminated. The result returned by this method may differ from getParallelism() when threads are created to maintain parallelism when others are cooperatively blocked.

2
katma

Paletli gibi uygulamada ForkJoin performansına hayran kalacaksınız. İşte en iyisi öğretici sizden öğreneceksiniz.

Çatal/Birleşimin mantığı çok basit: (1) her büyük görev için ayrı (çatal)   daha küçük görevlere; (2) her görevi ayrı bir iş parçacığında işleme   (bunları gerekirse daha küçük görevlere ayırmak); (3) katıl   Sonuçlar.

1
katma