Fokka/birikma ramkasi ish zarrachalar havosidan yaxshiroqmi?

Yangi fork/join framework dan foydalanishning afzalliklari faqat boshlang'ichdagi N subtasksga katta vazifani ajratib, ularni keshlangan ish zarrachalariga yuborish ( Executors ) va har bir ishni bajarishni kutish kerakmi? Forkliftni ishlatish yoki qo'shilish jarayonini qanday qilib osonlashtirayotganini yoki echimlarni yillar mobaynida nima qilganimizdan samaraliroq qilishini ko'rmayapman.

Misol uchun, o'quv namunasi ning parallellangan loyqa algoritmi bo'lishi mumkin. quyidagi kabi qo'llaniladi:

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

Dastlab bo'linib, ish zarrachalariga havola yuboring:

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

Vazifalar thread hovuzining navbatiga o'tadi va ular ishchi bandlari mavjud bo'lganda amalga oshiriladi. Ajratish etarli miqdorda bo'lsa (oxirgi ishni kutishdan qochish uchun) va ish zarrachalar pulining (eng kamida N protsessorlar) iplari bo'lsa, barcha protsessorlar butun hisoblash jarayoni amalga oshirilgunga qadar to'liq tezlikda ishlaydi.

Biror narsani yo'qotaymi? Fork/birlashma ramkasidan foydalanishning qo'shimcha qiymati qanday?

103

10 javoblar

Menimcha, asosiy noto'g'ri tushunish, Fork/Join misollari NOT ishni o'g'irlash ni ko'rsatishini, lekin faqat bir xil standart bo'linish va bosib chiqarishni bajarishini o'ylayman.

Ishni o'g'irlash bu kabi ish bo'lishi mumkin: Ishchi B o'z ishini tugatdi. U mehribon, shuning uchun atrofdagilarga qaraydi va ishchi A hali ham ishlaydi. U yugurib yuradi va so'raydi: "Hey, o'g'lim, men sizga qo'l berishi mumkin edi". Javoblar. "Salom, 1000 ta ushbu vazifam bor, hozirgacha men 655 raqamini qoldirib, 345ni to'ldirdim. Iltimos, 673-1000 raqamiga ishlasangiz, men 346 dan 672 gacha qilaman". B: "Yaxshi, keling, oldinroq pubga boraylik", deydi.

Ko'rib turganingizdek, ishchilar haqiqiy ish boshlaganlarida ham bir-birlari bilan muloqot qilishlari kerak. Bu misollardagi yo'qolgan qism.

Boshqa tomondan, misollarda "subpudratchilardan foydalanish" kabi bir narsa bor:

Ishchi A: "Dang, mening 1000 ta ishim bor, men uchun juda ko'p, men o'zimni 500 marta va subpudrat shartnomasini 500 kishiga boshqara olaman". Bu katta vazifa har biri 10 ta kichik paketlarga bo'lgunga qadar davom etadi. Ular mavjud ishchilar tomonidan amalga oshiriladi. Ammo agar bitta paket zaharli xastalikka o'xshasa va boshqa paketlarga qaraganda ancha uzoq davom etsa - omadsizlik, bo'linish davri tugadi.

Fork/Join bilan oradagi vazifani oldinga surib qo'yadigan yagona farq quyidagicha: agar oldinga siljish bo'lsa, siz boshdanoq ishni boshlashingiz mumkin. Misol: 1000 ta, eshik 10, shuning uchun navbatda 100 ta yozuv bor. Ushbu paketlar threadpool a'zolariga taqsimlanadi.

Fork/Join qo'shilishi ancha murakkab va navbatdagi paketlar sonini kichkina ushlab turishga harakat qiladi:

  • 1-qadam: (1 ... 1000) bitta paketni navbatga qo'ying
  • 2-qadam: Bir ishchi paketni ochadi (1 ... 1000) va uni ikki paket bilan almashtiradi: (1 500) va (501 ... 1000).
  • 3-qadam: Bir ishchi paket (500 ... 1000) ochadi va (500 ... 750) va (751 ... 1000) ni bosadi.
  • Step n: Bu to'plamda ushbu paketlar mavjud: (1..500), (500 ... 750), (750 ... 875) ... (991..1000)
  • Bosqich n +1: Paket (991..1000) chiqarildi va bajarildi
  • Bosqich n + 2: Paket (981..990) chiqarildi va bajarildi
  • Step n + 3: Paket (961..980) chiqarilib, (961 ... 970) va (971..980) ichiga bo'linadi. ....

Ko'rib turganingizdek: Fork/Kuyovga qo'shilish kichikroq (misolda 6) va "bo'linish" va "ish" bosqichlari interleaved.

Bir vaqtning o'zida bir nechta ishchi ochilib, bir vaqtning o'zida itarib yuborilsa, shovqinlar shunchalik aniq emas.

114
qo'shib qo'ydi
Bu, albatta, javob. O'z ishini o'g'irlash qobiliyatlarini namoyish qiladigan har qanday joyga haqiqiy Fork/Join dasturlari qiziqtirganmi? Boshlang'ich misollarda ish yukining miqdori birlik o'lchamidan (masalan, uzunligi) oldindan taxmin etilishi mumkin, shuning uchun oldindan ajratish osondir. O'g'irlik, birlikdagi ish yukining hajmi emas, balki birlikning o'lchamidan ancha yaxshi bo'lishi mumkin bo'lgan muammolarda farq qiladi.
qo'shib qo'ydi muallif Joonas Pulakka, manba
@Marc: Kechirasiz, lekin hech qanday misolim yo'q.
qo'shib qo'ydi muallif A.H., manba
Ishni o'g'irlashning ba'zi bir misollaridan foydalanish mumkin: h-online.com/developer/features/…
qo'shib qo'ydi muallif volley, manba
Oracle misolida IMO muammosi, u ishni o'g'irlashni ko'rsatmaydi (u XH tomonidan aytilganidek), lekin oddiy (masalan, Joonas kabi) sodda ThreadPool uchun algoritmni kodlash oson emas. F-J ishi etarli mustaqil ishlarga bo'linmasligi mumkin, lekin o'z-o'zidan mustaqil bo'lgan vazifalarga aylantirilishi mumkin. Misol uchun, javobimni qarang
qo'shib qo'ydi muallif Edson Medina, manba
A.H. Sizning javobingiz to'g'ri bo'lsa, u qanday qilib tushuntirmaydi. Oracle tomonidan berilgan misol ishni o'g'irlashga olib kelmaydi. Siz bu erda tasvirlangan misolda qanday ishlashni va ishni qanday qilib olib boradi? Bir necha Java kodlarini ko'rsatib berasizmi? rahmat
qo'shib qo'ydi muallif Marc, manba

Agar sizda n-nizamli ish zarrachalaringiz 100% mustaqil ravishda ishlayotgan bo'lsa, bu Fork-Join (FJ) havuzidagi n tokidan yaxshiroq bo'ladi. Lekin bu hech qachon bunday ishlamaydi.

Muammoni n teng bo'laklarga ajratib bo'lmaydigan bo'lishi mumkin. Agar siz ham shunday qilsangiz, oqim rejasi adolatli bo'lishdan qochadi. Siz eng sekin ishtiyoqni kutishingiz kerak. Agar sizda bir nechta vazifa bo'lsa, ular har bir n-parallellikdan kamroq (odatda ko'proq samarali) ishlashi mumkin, ammo boshqa vazifalar tugaganida n-usulga o'tishlari mumkin.

Xo'sh, nima uchun biz bu muammoni faqat FJ o'lchamli qismlarga aylantirmayapmiz va bunga ishora qilsak bo'ladi? Odatda FJ ishlatish muammolarni kichik qismlarga ajratadi. Bunlarni tasodifiy tartibda bajarish apparat darajasida juda ko'p muvofiqlashtirishni talab qiladi. Yuqoridagi xarajatlar qotil bo'ladi. FJda vazifalar navbatma-navbat Birinchi Chiqish tartibida (LIFO/stack) o'qiladi va o'g'irlik (asosiy ishda odatda) birinchi navbatda (FIFO/"kuyruklar") amalga oshiriladi. Natijada, kichik qismlarga bo'linib ketgan bo'lsa ham, uzoq muddatli qayta ishlash katta darajada ketma-ket amalga oshirilishi mumkin. (Shuningdek, katta portlashdagi muammolarni bir xil kichik o'lchamli qismlarga ajratish juda arzimas bo'lishi mumkin), denglarsiz, ba'zi bir ierarxik shakllar bilan shug'ullanish.

Xulosa: FJ apparat tarmoqlarini unumdor vaziyatlarda yanada samarali ishlatishga imkon beradi, bu sizning ishingizda bir nechta ish zarrachasi bo'lsa.

23
qo'shib qo'ydi
Lekin nima uchun FJ eng sekin ish zarrachasini kutish bilan yakunlanmaydi? Oldindan ishlaydigan subtasklar soni bor, va, albatta, ulardan ba'zilari har doim yakunlash uchun oxirgi bo'ladi. Mening misolimdagi maxSize parametrini sozlash, FJ misolidagi "ikkilik bo'linishlar" (deyarli o'xshash subtask bo'linmasini ishlab chiqaradi) (yoki compute() yoki invokeAll() ga pastki vazifalarni yuboradi.
qo'shib qo'ydi muallif Joonas Pulakka, manba
OK, subtasklar soni, parallel ravishda aslida parallel ravishda ishlov berilishi mumkin bo'lgan narsalardan kattaroq buyruqlar bo'lsa (bu mantiqan to'g'ri bo'lsa, oxirgi narsani kutishni istamaslik uchun), men muvofiqlashtirish masalalarini ko'ra olaman. FJ namunasi bo'limga kirish kerak bo'lsa, yanglishmasligi mumkin. bu zararli bo'lsin: 100000 eshikdan foydalanadi, 1000x1000 tasvir uchun 16 ta haqiqiy subtasklar ishlab chiqariladi, har birining ishlashi 62500 ta element. 10000x10000 tasvir uchun 1024 ta subtask bor edi, bu allaqachon biror narsa.
qo'shib qo'ydi muallif Joonas Pulakka, manba
Chunki ular juda kichikroq - men javobimni qo'shaman.
qo'shib qo'ydi muallif Tom Hawtin - tackline, manba

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

Har qanday ExecutorService'da bo'lgani kabi, forklift/birlashma doirasi vazifalarni taqsimlaydi   thread havuzundaki ishchi iplar uchun. Çatal/birlashma ramkasi   chunki u ishni o'g'irlash algoritmidan foydalanadi. Ishchi mavzular   narsalarni bajarish uchun ishlatiladigan narsalar boshqa ish zarrachalaridagi vazifalarni o'g'irlashi mumkin   hali ham band.

Aytish kerakki, sizda ikkita ip bor, va 4, vazifalari a, b, c, d, buning uchun 1, 1, 5 va 6 soniyani oladi. Dastlab, a va b 1-bandga va 2 va 2-bandlarga tayinlanadi. Ish zarrachasidagi havuzda bu 11 soniyani oladi. Forklift/biriktirgich bilan 1-son tugaydi va ipdan 2 ishni bajarishi mumkin, shuning uchun vazifa d 1-band bilan bajariladi. 1-soniya a, b va d, 2-bandni bajaradi. Umumiy vaqt: 8 sekund, 11 emas.

EDIT: Joonas ta'kidlaganidek, topshiriqlar, albatta, ishlov berish uchun oldindan taqsimlanmagan. Fork/joining g'oyasi shundan iboratki, ish zarrachani bir nechta kichik bo'laklarga bo'lishni tanlashi mumkin. Ya'ni, yuqorida aytib o'tilganlarni qayta ishlash uchun:

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
qo'shib qo'ydi
Teshikli ko'llar odatda ThreadPoolExecutor namunalari . Bunday vazifalar navbatda ( BlockingQueue ), undan avvalgi ishni tugatgandan so'ng, ishchilarning vazifalari topshiriladi. Vazifalar, men tushunganimga ko'ra, emas, balki ga aniqlik berilgan narsalar oldindan tayinlangan. Har bir ish zarrachasida (eng ko'p) 1 vazifa bor.
qo'shib qo'ydi muallif Joonas Pulakka, manba
@Matthew Farwell: FJ namunasi , har bir topshiriq doirasida , compute() vazifani hisoblab chiqadi yoki uni ikkita subtaskaga ajratadi. Qaysi variantni tanlashi vazifa hajmiga ( if (mLength ) qarab faqat ga bog'liq, shuning uchun u faqat belgilangan vazifalarni yaratishning xayoliy usuli. 1000x1000 tasvir uchun, aslida 16 ta subtaskalar bo'ladi. Bundan tashqari, subtaskalarni ishlab chiqaruvchi va taklif qiladigan va o'zlarini hech narsa hisoblamaydigan 15 (= 16-1) "oraliq" vazifalar bo'ladi.
qo'shib qo'ydi muallif Joonas Pulakka, manba
@Matthew Farwell: Men FJ ni tushunmayman, lekin subtask computeDirectly() usulini bajarishga qaror qilgan bo'lsa, boshqa hech narsani o'g'irlashning usuli yo'q. Barcha parchalanish, hech bo'lmaganda, misolda a priori amalga oshiriladi.
qo'shib qo'ydi muallif Joonas Pulakka, manba
AFAIK bir bir uchun navbat bor <thread> ThreadPoolExecutor bir necha Mavzular nazorat qiladi. Bu vazifalarni bajarish yoki Runnables (emas Mavzular emas) ijrochiga topshirish topshiriqlarni ma'lum bir mavzu uchun oldindan taqsimlanmagan degan ma'noni anglatadi. To'liq yo'l FJ ham buni qiladi. FJ ni ishlatish uchun hozircha hech qanday foyda yo'q.
qo'shib qo'ydi muallif A.H., manba
@JoonasPulakka: Men ushbu munozarada gaplashmoqchi bo'lgan javobni yozdim.
qo'shib qo'ydi muallif A.H., manba
@ A.H. Ha, lekin fork/join sizga joriy vazifani ajratishga imkon beradi. Vazifani bajaradigan ish zarrachasini ikki xil vazifaga ajratishi mumkin. Shunday qilib, ThreadPoolExecutor bilan siz aniq vazifalar ro'yxatiga egasiz. Forklift/qo'shilish bilan bajariladigan vazifa o'z vazifasini ikki qismga bo'linishi mumkin, bu esa o'z ishini tugatgandan so'ng boshqa ish zarrachalari tomonidan olinishi mumkin. Yoki siz birinchi marta tugatsangiz.
qo'shib qo'ydi muallif Matthew Farwell, manba
@Joonas, ha, bu ular uchun ajratilgan strategiya. Biroq, har bir subtask qancha davom etishini bilmaydi. Bir subtaskaning 1 soniyasini olish mumkin, boshqa (bir xil o'lchami) 15 soniyani oladi. Bunday holda ishni o'g'irlash sodir bo'lishi mumkin. Ehtimol, siz aytayotgan gapingizni tushunmayman.
qo'shib qo'ydi muallif Matthew Farwell, manba

Yuqoridagi har bir kishi to'g'ri ishlarni o'g'irlash orqali erishiladi, lekin buning sababini kengaytirish.

Asosiy foyda, ishchi iplari o'rtasida samarali muvofiqlashtirishdir. Ishni muvofiqlashtirishni talab qiladigan bo'linish va qayta qurish kerak. Yuqorida ko'rsatilgan A.H.ning javobida ko'rib chiqqaningizdek, har bir mavzu o'z ish ro'yxatiga ega. Ushbu ro'yxatning muhim xususiyati shundaki, u tartiblangan (quyi qismidagi yuqori va kichik vazifalardagi katta vazifalar). Har bir nuqta o'z ro'yxatining pastki qismidagi vazifalarni bajaradi va boshqa ish zarrachalari ro'yxatining yuqori qismidagi vazifalarni o'g'irlaydi.

Buning natijasi:

  • Vazifa ro'yxatlarining boshi va quyruqlari ro'yxatdagi kelishmovchilikni kamaytirib, mustaqil ravishda sinxronlashtirilishi mumkin.
  • Ishning muhim subtreeslari bir xil yo'nalish bo'yicha bo'linadi va qayta o'rnatiladi, shuning uchun ushbu subtreeslar uchun hech qanday inter ishi muvofiqlashtirilmaydi.
  • Tarmoqni o'g'irlamoqchi bo'lganida, u katta qismi oladi, keyin uni o'z ro'yxatiga bo'linadi
  • Ishni po'latlash jarayoni jarayonning oxirigacha iplar deyarli to'liq ishlatilishini anglatadi.

Jihoz havzalarini ishlatgan boshqa ko'plab bo'linish va bosib olish sxemalari ko'plab intervalli aloqa va muvofiqlashtirishni talab qiladi.

10
qo'shib qo'ydi

Ushbu misolda Fork/Registratsiya uchun hech qanday qiymat qo'shilmaydi, chunki forking zarur emas va ish yuki ishchilarning ish zarralari bo'yicha bir tekis taqsimlanadi. Fork/Join faqat yuklarni qo'shib qo'yadi.

Mana bir Yaxshi maqola mavzu bo'yicha. Iqtibos:

Umuman, biz ThreadPoolExecutor-ni afzal deb ayta olamiz   Ish yukining ishchi iplari bo'ylab teng taqsimlangan joy. Qila olmoq   Buni kafolatlash uchun, kirish ma'lumotlarining aniqligini bilishingiz kerak   kabi ko'rinadi. Aksincha, ForkJoinPool yaxshi ishlash imkonini beradi   kirish ma'lumotidan qat'i nazar, va shuning uchun sezilarli ravishda yanada mustahkam bo'ladi   yechim.

10
qo'shib qo'ydi
Juda yaxshi maqola, rahmat!
qo'shib qo'ydi muallif Joonas Pulakka, manba

Tarmoqli havuzlar va Fork/Joinning yakuniy maqsadi bir xil: Ikkalasi ham mavjud CPU quvvatidan maksimal o'tkazuvchanlik uchun maksimal darajada foydalanishni xohlaydi. Maksimal ishlov berish, imkon qadar ko'p vazifalar uzoq vaqt davomida bajarilishi kerakligini anglatadi. Buning uchun nima qilish kerak? (Quyidagi uchun hisob-kitob qilishning qiyinchiliklari yo'q deb taxmin qilamiz: 100% CPU foydalanish uchun har doim etarli bo'ladi, shuningdek, men "CPU" ni giper-ishlov berishda yadro yoki virtual yadro uchun teng ravishda ishlataman).

  1. Hech bo'lmasa, protsessorlar mavjud bo'lganligi sababli ishlaydigan qancha mavzular bo'lishi kerak, chunki kam ishlaydigan ishlanmalar yadrodan foydalanilmaydi.
  2. Maksimal darajadagi ishlovchilarning ko'pchiligi mavjud bo'lishi kerak, chunki ko'proq ishlovchilarning ishi CPUlarni turli ishlarga topshiradigan Taymer uchun qo'shimcha yuk hosil qiladi, chunki ba'zi CPU vaqtlarini hisoblash o'rniga rejalashtirgichga o'tishga sabab bo'ladi vazifa.

Shunday qilib, maksimal o'tkazuvchanlik uchun protsessorlarga nisbatan bir xil sonda iplarni olishimiz kerakligini anglab etdik. Oracle-ning loyqa misolida, siz ham mavjud bo'lgan CPU soniga teng yoki ish zarrachalar havzasidan foydalanadigan zarrachalar soni bilan qattiq o'lchamli ish zarrachasini olishingiz mumkin. Bu farq qilmaydi, to'g'rating!

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

Bu erda ko'rib turganimizdek, A, B va C uch bosqichdan iborat algoritm mavjud. A va B bir-biridan mustaqil ravishda bajarilishi mumkin, ammo S qadam A va B qadamlarining natijalariga muhtoj. Ushbu algoritm nima uchun A vazifasini topshiradi? threadpool va b vazifasini bevosita amalga oshiradi. Shundan so'ng, ish zarrachasini A bajarish uchun kutib turadi va S qadamida davom etadi. Agar A va B bir vaqtning o'zida bajarilgan bo'lsa, unda hamma narsa yaxshi. Ammo, A B dan uzoqroq bo'lsa nima bo'ladi? Buning sababi, vazifaning tabiati uni belgilab qo'yishi mumkin, lekin u ham bo'lishi mumkin emas, chunki u mavjud emas  vazifa uchun thread A boshida va vazifada mavjud A kutish kerak. (Agar faqat bitta protsessor mavjud bo'lsa va shuning uchun ipli ipingiz faqatgina bitta ipga ega bo'lsa, bu hatto bir qulflashga olib keladi, lekin hozirda nuqta tashqari). Vazifa shundan iboratki, faqat B vazifasini bajaradigan ish zarrachani bloklaydi. CPU sifatida bir xil sonli iplar mavjudligi va bitta ish zarrachasi bloklanganligi sababli bitta CPU bo'sh turgan degan ma'noni anglatadi.

Fork/Join qo'shimchalari bu muammoni hal qiladi: fork/join ramkalarida siz quyidagi algoritmni yozasiz:

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

Xuddi shunday, shunday emasmi? Shunga qaramasdan, aTask.join blokirovka qilmaydi . Buning o'rniga bu erda ishni o'g'irlash funksiyasi paydo bo'ladi: Mavzu, o'tmishda uzilgan boshqa vazifalar uchun atrofga qaraydi va ular bilan davom etadi. Birinchidan, u o'z-o'zidan uzilgan vazifalarni qayta ishlashni boshlaganligini tekshiradi. Shunday qilib, agar "A" hali boshlanmagan bo'lsa, keyingi ishni amalga oshiradi, aks holda boshqa mavzularning navbatini tekshirib, ishlarini o'g'irlaydi. Boshqa bir ipning boshqa vazifasi bajarilgandan so'ng, u A ni tugatganligini tekshiradi. Agar yuqorida ko'rsatilgan algoritm bo'lsa, stepC ni chaqirishi mumkin. Aks holda, u o'g'irlash uchun yana bir vazifani izlaydi. Shunday qilib, fork/join pools blokirovka harakatlariga qaramay, 100% CPU foydalanishga erishish mumkin.

Biroq, tuzoq bor: Ishni o'g'irlash faqatgina ForkJoinTask ning join chaqiruvi uchun mumkin. Boshqa ishni kutish yoki G/Ç harakatlarini kutish kabi tashqi blokirovka qilish uchun bajarilmaydi. Shunday qilib, I/Oni to'ldirishni kutish bu umumiy vazifadir? Bunday holatda blokirovkalash harakati tugallangandan so'ng yana to'xtatiladigan Fork/Birlashma havzasiga qo'shimcha ishtiyoq qo'sha olsak, ikkinchi eng yaxshi narsa bo'ladi. Va ForkJoinPool , aslida, agar biz ManagedBlocker ni ishlatsak, buni amalga oshirishi mumkin.

Fibonachchi

In the JavaDoc for RecursiveTask is an example for calculating Fibonachchi numbers using Fork/Join. For a classic recursive solution see:

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

As is explained int the JavaDocs this is a pretty dump way to calculate Fibonachchi numbers, as this algorithm has O(2^n) complexity while simpler ways are possible. However this algorithm is very simple and easy to understand, so we stick with it. Let's assume we want to speed this up with Fork/Join. A naive implementation would look like this:

class Fibonachchi extends RecursiveTask {
    private final long n;

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

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

Ushbu topshiriqning bo'linishi juda qisqa, shuning uchun bu juda dahshatli tarzda amalga oshiriladi, lekin bu ramkaning odatda juda yaxshi ishlashini ko'rishingiz mumkin: ikkita summa mustaqil ravishda hisoblanishi mumkin, lekin keyin ikkalasini ham yakuniy natijalar. Shunday qilib, yarmi boshqa bir ipda bajariladi. O'yin-kulgilar bilan shug'ullanadigan o'yin-kulgichni o'chirib qo'ying (imkoni boricha, ammo deyarli emas).

Just for completeness: If you'd actually want to calculate Fibonachchi numbers using this recursive approach here is an optimized version:

class FibonachchiBigSubtasks extends RecursiveTask {
    private final long n;

    FibonachchiBigSubtasks(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 FibonachchiBigSubtasks f1 = new FibonachchiBigSubtasks(n - 1);
            final FibonachchiBigSubtasks f2 = new FibonachchiBigSubtasks(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).

Kompyuterimda (4 ta yadro (Hyper-threading hisoblaganda 8), Intel (R) Core (i7-2720QM CPU @ 2.20GHz)) fib (50) klassik yondashuv bilan 64 soniya oladi va taxminan 18 soniya ichida Fork/Join uslubiga ega bo'lib, bu nazariy jihatdan imkon qadar ko'p emas.

Xulosa

  • Ha, sizning namunangizda Fork/Join guruhida klassik ish zarrachalaridan ustunlik yo'q.
  • Cho'zish/Ishtirok etish blokirovkasida ishlashni sezilarli darajada oshirishi mumkin
  • Shpil/Qo`shma bir necha halokatli muammolarni yengib chiqadi
8
qo'shib qo'ydi

Yana bir muhim farq, F-J bilan bir nechta murakkab "qo'shilish" bosqichlarini amalga oshirishingiz mumkin. http://faculty.ycp.edu/~dhovemey/spring2011/cs365 dan birlashma tartibini ko'rib chiqing. /lecture/lecture18.html , bu ishni oldindan ajratish uchun juda ko'p orkestratsiya bo'lishi kerak. Masalan, Siz quyidagi narsalarni qilishingiz kerak:

  • birinchi chorakni tartiblashtirish
  • ikkinchi chorakni tartiblash
  • birinchi 2 chorakni birlashtiradi
  • uchinchi chorakni tartiblash
  • to'rtinchi chorakni tartiblashtirish
  • so'nggi 2 chorakni birlashtiradi
  • 2 yarmini birlashtiradi

O'zingiz va boshqalar bilan bog'liq bo'lgan birlashmalardan oldin bunday narsalarni qilishingiz kerakligini qanday belgilaysiz?

Men narsalarning har bir ro'yxati uchun ma'lum bir narsani qilishning eng yaxshi usulini ko'rib chiqdim. O'ylaymanki, ro'yxatni oldindan ajratishim va standart ThreadPooldan foydalanaman. F-J ishi etarli mustaqil ishlarga bo'linmasligi mumkin, lekin o'z-o'zidan mustaqil bo'lgan vazifalarni o'z-o'zidan ajrata oladigan (masalan, yarmini ajratish mustaqildir, lekin 2 tartiblangan yarmini tartiblangan bir butunga birlashtirmaydi) juda foydali bo'ladi.

7
qo'shib qo'ydi

Agar qimmatbaho birlashma operatsiyalari bo'lsa, F/J shuningdek afzalligi bor. Agar siz daraxt tarkibiga kiradigan bo'lsa, faqat log2 (n) ni birlashtirasiz, buning o'rniga n yassi ipni ajratish bilan birlashtiriladi. (Bu sizning ish zarrachalaringiz kabi juda ko'p protsessorlarga ega bo'lgan nazariy taxminni keltirib chiqaradi, ammo yana bir afzallik). Bir uy vazifasi belgilash uchun har bir indeksdagi qadriyatlarni to'plab, bir necha mingta 2D massivlarini (bir xil o'lchamlarni) birlashtirish kerak edi. Vilkalar va P-protsessorlari bilan log2 (n) ga yaqinlashadi, chunki P-abadiylikka yaqinlashadi.

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
qo'shib qo'ydi

Muammo boshqa iplarning bajarilishini kutishimiz kerak bo'lsa (masalan, qator yoki qator yig'indisi kabi), Ijrochining (Executors.newFixedThreadPool (2)) cheklanganligi sababli, mavzular soni. Forkjoin hovuzida parallelismni saqlab qolish uchun bloklangan ipni qoplash uchun bu holatda ko'proq narsalarni yaratadi

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

Algoritmlarni ajratish va egallashni amalga oshirish uchun ijrochilar bilan bog'liq muammo subtaskalarni yaratishga taalluqli emas, chunki da'vat o'z ijrochisiga yangi subtaskni taqdim etishga va natijasini sinxron yoki asinxron usulda kutish mumkin. Muammo shundaki, parallelizm: chaqiruvchining boshqa chaqiruvchining natijasini kutish bilan kutish holatiga qo'yiladi va shu bilan boshqa ijrochi navbat bilan ijro etilish imkoniyatini yo'qotadi.

Doug Leaning harakati orqali Java SE 7 da java.util.concurrent paketiga qo'shilgan fork/birlashma doirasi bu bo'shliqni to'ldiradi

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

Hovuz, ba'zi bir vazifalar boshqalarga qo'shilishni kutib turgan bo'lsa ham, ichki ishchi threadlarini dinamik ravishda qo'shish, to'xtatish yoki qayta tiklash orqali yetarlicha faol (yoki mavjud) ishlarni bajarishga harakat qiladi. Biroq, bloklangan IO yoki boshqa boshqarilmaydigan sinxronizatsiya sharoitida bunday o'zgartirishlar kafolatlanmaydi

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
qo'shib qo'ydi