摘要

這篇論文描述了Fork/Join框架的設(shè)計(jì)抗悍、實(shí)現(xiàn)以及性能亡笑。這個(gè)框架通過（遞歸的）把問題劃分為子任務(wù)，然后并行的執(zhí)行這些子任務(wù)祠乃，等所有的子任務(wù)都結(jié)束的時(shí)候梦重，再合并最終結(jié)果的這種方式來支持并行計(jì)算編程×链桑總體的設(shè)計(jì)參考了為Cilk（校注1：英特爾Cilk 語言）設(shè)計(jì)的work-stealing框架琴拧。就設(shè)計(jì)層面來說主要是圍繞如何高效的去構(gòu)建和管理任務(wù)隊(duì)列以及工作線程來展開的。性能測試的數(shù)據(jù)顯示良好的并行計(jì)算程序?qū)?huì)提升大部分應(yīng)用嘱支，同時(shí)也暗示了一些潛在的可以提升的空間蚓胸。

介紹

Fork/Join并行方式是獲取良好的并行計(jì)算性能的一種最簡單同時(shí)也是最有效的設(shè)計(jì)技術(shù)。Fork/Join并行算法是我們所熟悉的分治算法的并行版本除师，典型的用法如下：

Result solve(Problem problem) {

if (problem is small)

directly solve problem

else {

split problem into independent parts fork new subtasks to solve each part join all subtasks compose result from subresults

}

}

Fork操作將會(huì)啟動(dòng)一個(gè)新的并行fork/join子任務(wù)沛膳。Join操作會(huì)一直等待直到所有的子任務(wù)都結(jié)束。Fork/Join算法汛聚，如同其他分治算法一樣于置，總是會(huì)遞歸的、反復(fù)的劃分子任務(wù)贞岭，直到這些子任務(wù)可以用足夠簡單的八毯、短小的順序方法來執(zhí)行。

一些相關(guān)的編程技術(shù)和實(shí)例在Java并發(fā)編程——設(shè)計(jì)原則與模式 第二版 [7] 4.4章節(jié)中已經(jīng)討論過瞄桨。這篇論文將討論FJTask的設(shè)計(jì)(第2節(jié))话速、實(shí)現(xiàn)（第3節(jié)）以及性能（第4節(jié)），它是一個(gè)支持并行編程方式的Java框架芯侥。FJTask 作為util.concurrent軟件包的一部分泊交，目前可以在http://gee.cs.oswego.edu.獲取到。

設(shè)計(jì)

Fork/Join程序可以在任何支持以下特性的框架之上運(yùn)行：框架能夠讓構(gòu)建的子任務(wù)并行執(zhí)行柱查，并且擁有一種等待子任務(wù)運(yùn)行結(jié)束的機(jī)制廓俭。然而，java.lang.Thread類（同時(shí)也包括POSIX pthreads, 這些也是Java線程所基于的基礎(chǔ)）對Fork/Join程序來說并不是最優(yōu)的選擇：

?Fork/Join 任務(wù)對同步和管理有簡單的和常規(guī)的需求唉工。相對于常規(guī)的線程來說研乒，fork/join任務(wù)所展示的計(jì)算布局將會(huì)帶來更加靈活的調(diào)度策略。例如淋硝，fork/join任務(wù)除了等待子任務(wù)外雹熬，其他情況下是不需要阻塞的宽菜。因此傳統(tǒng)的用于跟蹤記錄阻塞線程的代價(jià)在這種情況下實(shí)際上是一種浪費(fèi)。

對于一個(gè)合理的基礎(chǔ)任務(wù)粒度來說竿报，構(gòu)建和管理一個(gè)線程的代價(jià)甚至可以比任務(wù)執(zhí)行本身所花費(fèi)的代價(jià)更大铅乡。盡管粒度是應(yīng)該隨著應(yīng)用程序在不同特定平臺(tái)上運(yùn)行而做出相應(yīng)調(diào)整的。但是超過線程開銷的極端粗粒度會(huì)限制并行的發(fā)揮烈菌。

簡而言之阵幸，Java標(biāo)準(zhǔn)的線程框架對fork/join程序而言太笨重了。但是既然線程構(gòu)成了很多其他的并發(fā)和并行編程的基礎(chǔ)芽世，完全消除這種代價(jià)或者為了這種方式而調(diào)整線程調(diào)度是不可能的挚赊。

盡管這種思想已經(jīng)存在了很長時(shí)間了，但是第一個(gè)發(fā)布的能系統(tǒng)解決這些問題的框架是Cilk[5]捂襟。Cilk和其他輕量級(jí)的框架是基于操作系統(tǒng)的基本的線程和進(jìn)程機(jī)制來支持特殊用途的fork/join程序咬腕。這種策略同樣適用于Java，盡管Java線程是基于低級(jí)別的操作系統(tǒng)的能力來實(shí)現(xiàn)的葬荷。創(chuàng)造這樣一個(gè)輕量級(jí)的執(zhí)行框架的主要優(yōu)勢是能夠讓fork/join程序以一種更直觀的方式編寫涨共，進(jìn)而能夠在各種支持JVM的系統(tǒng)上運(yùn)行。

FJTask框架是基于Cilk設(shè)計(jì)的一種演變宠漩。其他的類似框架有Hood[4], Filaments[8],stackthreads[10], 以及一些依賴于輕量級(jí)執(zhí)行任務(wù)的相關(guān)系統(tǒng)举反。所有這些框架都采用和操作系統(tǒng)把線程映射到CPU上相同的方式來把任務(wù)映射到線程上。只是他們會(huì)使用fork/join程序的簡單性扒吁、常規(guī)性以及一致性來執(zhí)行這種映射火鼻。 所有的這些框架可以兼容（不同程度）并行程序以不同的樣式編寫，它們優(yōu)化了fork / join設(shè)計(jì)：

?一組工作者線程池是準(zhǔn)備好的雕崩。每個(gè)工作線程都是標(biāo)準(zhǔn)的(“重量級(jí)”)處理存放在隊(duì)列中任務(wù)的線程（這地方指的是Thread類的子類FJTaskRunner的實(shí)例對象）魁索。通常情況下，工作線程應(yīng)該與系統(tǒng)的處理器數(shù)量一致盼铁。對于一些原生的框架例如說Cilk,他們首先將映射成內(nèi)核線程或者是輕量級(jí)的進(jìn)程粗蔚，然后再在處理器上面運(yùn)行。在Java中饶火，虛擬機(jī)和操作系統(tǒng)需要相互結(jié)合來完成線程到處理器的映射鹏控。然后對于計(jì)算密集型的運(yùn)算來說，這種映射對于操作系統(tǒng)來說是一種相對簡單的任務(wù)肤寝。任何合理的映射策略都會(huì)導(dǎo)致線程映射到不同的處理器当辐。

?所有的fork/join任務(wù)都是輕量級(jí)執(zhí)行類的實(shí)例，而不是線程實(shí)例鲤看。在Java中缘揪，獨(dú)立的可執(zhí)行任務(wù)必須要實(shí)現(xiàn)Runnable接口并重寫run方法。在FJTask框架中，這些任務(wù)將作為子類繼承FJTask而不是Thread寺晌，它們都實(shí)現(xiàn)了Runnable接口世吨。（對于上面兩種情況來說澡刹，一個(gè)類也可以選擇實(shí)現(xiàn)Runnable接口呻征，類的實(shí)例對象既可以在任務(wù)中執(zhí)行也可以在線程中執(zhí)行。因?yàn)槿蝿?wù)執(zhí)行受到來自FJTask方法嚴(yán)厲規(guī)則的制約罢浇，子類化FJTask相對來說更加方便陆赋，也能夠直接調(diào)用它們。）

我們將采用一個(gè)特殊的隊(duì)列和調(diào)度原則來管理任務(wù)并通過工作線程來執(zhí)行任務(wù)嚷闭。這些機(jī)制是由任務(wù)類中提供的相關(guān)方式實(shí)現(xiàn)的：主要是由fork,join,isDone(一個(gè)結(jié)束狀態(tài)的標(biāo)示符)攒岛，和一些其他方便的方法，例如調(diào)用coInvoke來分解合并兩個(gè)或兩個(gè)以上的任務(wù)胞锰。

一個(gè)簡單的控制和管理類（這里指的是FJTaskRunnerGroup）來啟動(dòng)工作線程池灾锯，并初始化執(zhí)行一個(gè)由正常的線程調(diào)用所觸發(fā)的fork/join任務(wù)（就類似于Java程序中的main方法）。

作為一個(gè)給程序員演示這個(gè)框架如何運(yùn)行的標(biāo)準(zhǔn)實(shí)例嗅榕，這是一個(gè)計(jì)算法斐波那契函數(shù)的類顺饮。

class Fib extends FJTask {

static final int threshold = 13;

volatile int number; // arg/result

Fib(int n) { number = n; }

int getAnswer() {

if (!isDone())

throw new IllegalStateException();

return number;

}

public void run() {

int n = number;

if (n <= threshold) // granularity ctl

number = seqFib(n);

else {

Fib f1 = new Fib(n ? 1);

Fib f2 = new Fib(n ? 2);

coInvoke(f1, f2);

number = f1.number + f2.number;

}

}

public static void main(String[] args) {

try {

int groupSize = 2; // for example

FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);

Fib f = new Fib(35); // for example

group.invoke(f);

int result = f.getAnswer();

System.out.println("Answer: “ + result);

} catch (InterruptedException ex) {}

}

int seqFib(int n) {

if (n <= 1)

return n;

else

return seqFib(n?1) + seqFib(n?2);

}

}

這個(gè)版本在第4節(jié)中所提到的平臺(tái)上的運(yùn)行速度至少比每個(gè)任務(wù)都在Thread類中運(yùn)行快30倍。在保持性能的同時(shí)這個(gè)程序仍然維持著Java多線程程序的可移植性凌那。對程序員來說通常有兩個(gè)參數(shù)值的他們關(guān)注：

對于工作線程的創(chuàng)建數(shù)量兼雄，通常情況下可以與平臺(tái)所擁有的處理器數(shù)量保持一致（或者更少，用于處理其他相關(guān)的任務(wù)帽蝶，或者有些情況下更多赦肋，來提升非計(jì)算密集型任務(wù)的性能）。

一個(gè)粒度參數(shù)代表了創(chuàng)建任務(wù)的代價(jià)會(huì)大于并行化所帶來的潛在的性能提升的臨界點(diǎn)励稳。這個(gè)參數(shù)更多的是取決于算法而不是平臺(tái)佃乘。通常在單處理器上運(yùn)行良好的臨界點(diǎn)，在多處理器平臺(tái)上也會(huì)發(fā)揮很好的效果驹尼。作為一種附帶的效益趣避，這種方式能夠與Java虛擬機(jī)的動(dòng)態(tài)編譯機(jī)制很好的結(jié)合，而這種機(jī)制在對小塊方法的優(yōu)化方面相對于單塊的程序來說要好扶欣。這樣鹅巍，加上數(shù)據(jù)本地化的優(yōu)勢，fork/join算法的性能即使在單處理器上面的性能都較其他算法要好料祠。

Work?Stealing

Fork/jion框架的核心在于輕量級(jí)調(diào)度機(jī)制骆捧。FJTask采用了Cilk開創(chuàng)的work-stealing調(diào)度策略：

每個(gè)工作線程都維護(hù)自己的可運(yùn)行的任務(wù)調(diào)度隊(duì)列

隊(duì)列以雙端隊(duì)列的形式被維護(hù)（注：deques通常讀作“decks”），不僅支持后進(jìn)先出——LIFO的push和pop操作髓绽，還支持先進(jìn)先出——FIFO的take操作敛苇。

對于一個(gè)給定的工作線程來說，任務(wù)所產(chǎn)生的子任務(wù)將會(huì)被放入到工作者自己的雙端隊(duì)列中。

工作線程使用后進(jìn)先出--LIFO（最早的優(yōu)先）的順序枫攀，通過彈出任務(wù)來處理隊(duì)列中的任務(wù)括饶。

當(dāng)一個(gè)工作線程的本地沒有任務(wù)去運(yùn)行的時(shí)候，它將使用先進(jìn)先出——FIFO的規(guī)則嘗試隨機(jī)的從別的工作線程中拿（“偷竊”）一個(gè)任務(wù)去運(yùn)行来涨。

當(dāng)一個(gè)工作線程觸及了join操作图焰，如果可能的話它將處理其他任務(wù)，直到目標(biāo)任務(wù)被告知已經(jīng)結(jié)束（通過isDone方法）蹦掐。所有的任務(wù)都會(huì)無阻塞的完成技羔。

當(dāng)一個(gè)工作線程無法再從其他線程中獲取任務(wù)和失敗處理的時(shí)候，它就會(huì)退出（通過yields, sleeps, 和/或者優(yōu)先級(jí)調(diào)整卧抗，參考第3節(jié)）并經(jīng)過一段時(shí)間之后再度嘗試直到所有的工作線程都被告知他們都處于空閑的狀態(tài)藤滥。在這種情況下，他們都會(huì)阻塞直到其他的任務(wù)再度被上層調(diào)用社裆。

使用后進(jìn)先出——LIFO用來處理每個(gè)工作線程的自己任務(wù)拙绊，但是使用先進(jìn)先出——FIFO規(guī)則用于獲取別的任務(wù)，這是一種被廣泛使用的進(jìn)行遞歸fork/join設(shè)計(jì)的一種調(diào)優(yōu)手段泳秀。引用[5]討論了詳細(xì)討論了里面的細(xì)節(jié)标沪。

讓偷取任務(wù)的線程從隊(duì)列擁有者相反的方向進(jìn)行操作會(huì)減少線程競爭。同樣體現(xiàn)了遞歸分治算法的大任務(wù)優(yōu)先策略晶默。因此谨娜，更早期被偷取的任務(wù)有可能會(huì)提供一個(gè)更大的單元任務(wù)，從而使得偷取線程能夠在將來進(jìn)行遞歸分解磺陡。

作為上述規(guī)則的一個(gè)后果趴梢，對于一些基礎(chǔ)的操作而言，使用相對較小粒度的任務(wù)比那些僅僅使用粗粒度劃分的任務(wù)以及那些沒有使用遞歸分解的任務(wù)的運(yùn)行速度要快币他。盡管相關(guān)的少數(shù)任務(wù)在大多數(shù)的fork/join框架中會(huì)被其他工作線程偷取坞靶，但是創(chuàng)建許多組織良好的任務(wù)意味著只要有一個(gè)工作線程處于可運(yùn)行的狀態(tài)，那么這個(gè)任務(wù)就有可能被執(zhí)行蝴悉。

實(shí)現(xiàn)

這個(gè)框架是由大約800行純Java代碼組成彰阴，主要的類是FJTaskRunner，它是java.lang.Thread的子類拍冠。FJTasks 自己僅僅維持一個(gè)關(guān)于結(jié)束狀態(tài)的布爾值尿这，所有其他的操作都是通過當(dāng)前的工作線程來代理完成的。JFTaskRunnerGroup類用于創(chuàng)建工作線程庆杜，維護(hù)一些共享的狀態(tài)（例如：所有工作線程的標(biāo)示符射众，在偷取操作時(shí)需要），同時(shí)還要協(xié)調(diào)啟動(dòng)和關(guān)閉晃财。

更多實(shí)現(xiàn)的細(xì)節(jié)文檔可以在util.concurrent并發(fā)包中查看叨橱。這一節(jié)只著重討論兩類問題以及在實(shí)現(xiàn)這個(gè)框架的時(shí)候所形成的一些解決方案：支持高效的雙端列表操作（push, pop 和 take）， 并且當(dāng)工作線程在嘗試獲取新的任務(wù)時(shí)維持偷取的協(xié)議。

為了能夠獲得高效以及可擴(kuò)展的執(zhí)行任務(wù)罗洗，任務(wù)管理需要越快越好愉舔。創(chuàng)建、發(fā)布伙菜、和彈出（或者出現(xiàn)頻率很少的獲刃汀）任務(wù)在順序編程模式中會(huì)引發(fā)程序調(diào)用開銷。更低的開銷可以使得程序員能夠構(gòu)建更小粒度的任務(wù)仇让，最終也能更好的利用并行所帶來的益處典奉。

Java虛擬機(jī)會(huì)負(fù)責(zé)任務(wù)的內(nèi)存分配躺翻。Java垃圾回收器使我們不需要再去編寫一個(gè)特殊的內(nèi)存分配器去維護(hù)任務(wù)丧叽。相對于其他語言的類似框架，這個(gè)原因使我們大大降低了實(shí)現(xiàn)FJTasks的復(fù)雜性以及所需要的代碼數(shù)公你。

雙端隊(duì)列的基本結(jié)構(gòu)采用了很常規(guī)的一個(gè)結(jié)構(gòu)——使用一個(gè)數(shù)組（盡管是可變長的）來表示每個(gè)隊(duì)列踊淳，同時(shí)附帶兩個(gè)索引：top 索引就類似于數(shù)組中的棧指針，通過push和pop操作來改變陕靠。Base 索引只能通過take操作來改變迂尝。鑒于FJTaskRunner操作都是無縫的綁定到雙端隊(duì)列的細(xì)節(jié)之中，（例如剪芥，fork直接調(diào)用push）垄开，所以這個(gè)數(shù)據(jù)結(jié)構(gòu)直接放在類之中，而不是作為一個(gè)單獨(dú)的組件税肪。

但是雙端隊(duì)列的元素會(huì)被多線程并發(fā)的訪問溉躲，在缺乏足夠同步的情況下，而且單個(gè)的Java數(shù)組元素也不能聲明為volitile變量益兄，每個(gè)數(shù)組元素實(shí)際上都是一個(gè)固定的引用锻梳，這個(gè)引用指向了一個(gè)維護(hù)著單個(gè)volitile引用的轉(zhuǎn)發(fā)對象。一開始做出這個(gè)決定主要是考慮到Java內(nèi)存模型的一致性净捅。但是在這個(gè)級(jí)別它所需要的間接尋址被證明在一些測試過的平臺(tái)上能夠提升性能疑枯。可能是因?yàn)樵L問鄰近的元素而降低了緩存爭用蛔六，這樣內(nèi)存里面的間接尋址會(huì)更快一點(diǎn)荆永。

實(shí)現(xiàn)雙端隊(duì)列的主要挑戰(zhàn)來自于同步和他的撤銷。盡管在Java虛擬機(jī)上使用經(jīng)過優(yōu)化過的同步工具国章，對于每個(gè)push和pop操作都需要獲取鎖還是讓這一切成為性能瓶頸具钥。然后根據(jù)以下的觀察結(jié)果我們可以修改Clik中的策略，從而為我們提供一種可行的解決方案：

Push和Pop操作僅可以被工作線程的擁有者所調(diào)用捉腥。

對Take的操作很容易會(huì)由于偷取任務(wù)線程在某一時(shí)間對take操作加鎖而限制氓拼。（雙端隊(duì)列在必要的時(shí)間也可以禁止take操作。）這樣，控制沖突將被降低為兩個(gè)部分同步的層次桃漾。

Pop和take操作只有在雙端隊(duì)列為空的時(shí)候才會(huì)發(fā)生沖突坏匪，否則的話，隊(duì)列會(huì)保證他們在不同的數(shù)組元素上面操作撬统。

把top和base索引定義為volitile變量可以保證當(dāng)隊(duì)列中元素不止一個(gè)時(shí)适滓，pop和take操作可以在不加鎖的情況下進(jìn)行。這是通過一種類似于Dekker算法來實(shí)現(xiàn)的恋追。當(dāng)push 預(yù)遞減到top時(shí):

If (–top >=base)…

和take 預(yù)遞減到 base時(shí):

If(++base < top)…

在上述每種情況下他們都通過比較兩個(gè)索引來檢查這樣是否會(huì)導(dǎo)致雙端隊(duì)列變成一個(gè)空隊(duì)列凭迹。一個(gè)不對稱的規(guī)則將用于防止?jié)撛诘臎_突：pop會(huì)重新檢查狀態(tài)并在獲取鎖之后繼續(xù)（對take所持有的也一樣），直到隊(duì)列真的為空才退出苦囱。而Take操作會(huì)立即退出嗅绸，特別是當(dāng)嘗試去獲得另外一個(gè)任務(wù)。與其他類似使用Clik的THE協(xié)議一樣撕彤，這種不對稱性是唯一重要的改變鱼鸠。

使用volitile變量索引push操作在隊(duì)列沒有滿的情況下不需要同步就可以進(jìn)行。如果隊(duì)列將要溢出羹铅，那么它首先必須要獲得隊(duì)列鎖來重新設(shè)置隊(duì)列的長度蚀狰。否則，只需確保top只有在deque陣列槽被填滿之后才更新來組織任何的take职员。

在隨后的初始化實(shí)現(xiàn)中麻蹋，發(fā)現(xiàn)有好幾種JVM并不符合Java內(nèi)存模型中正確讀取寫入的volitile變量的規(guī)則。作為一個(gè)工作區(qū)焊切，pop操作在持有鎖的情況下重試的條件已經(jīng)被調(diào)整為：如果有兩個(gè)或者更少的元素扮授，并且take操作加了第二把鎖以確保內(nèi)存屏障效果，那么重試就會(huì)被觸發(fā)蛛蒙。只要最多只有一個(gè)索引被擁有者線程丟失這就是滿足的糙箍，并且只會(huì)引起輕微的性能損耗。

在搶斷式工作框架中牵祟，工作線程對于他們所運(yùn)行的程序?qū)ν降囊笠粺o所知深夯。他們只是構(gòu)建、發(fā)布诺苹、彈出咕晋、獲取、管理狀態(tài)和執(zhí)行任務(wù)收奔。這種簡單的方案使得當(dāng)所有的線程都擁有很多任務(wù)需要去執(zhí)行的時(shí)候掌呜，它的效率很高。然而這種方式是有代價(jià)的坪哄，當(dāng)沒有足夠的工作的時(shí)候它將依賴于試探法质蕉。也就是說势篡，在啟動(dòng)一個(gè)主任務(wù)，直到它結(jié)束模暗，在有些fork/join算法中都使用了全面停止的同步指針禁悠。

主要的問題在于當(dāng)一個(gè)工作線程既無本地任務(wù)也不能從別的線程中搶斷任務(wù)時(shí)怎么辦。如果程序運(yùn)行在專業(yè)的多核處理器上面兑宇，那么可以依賴于硬件的忙等待自旋循環(huán)的去嘗試搶斷一個(gè)任務(wù)碍侦。然而，即使這樣隶糕，嘗試搶斷還是會(huì)增加競爭瓷产，甚至?xí)?dǎo)致那些不是閑置的工作線程降低效率（由于鎖協(xié)議，3.1節(jié)中）枚驻。除此之外濒旦，在一個(gè)更適合此框架運(yùn)行的場景中，操作系統(tǒng)應(yīng)該能夠很自信的去運(yùn)行那些不相關(guān)并可運(yùn)行的進(jìn)程和線程测秸。

Java中并沒有十分健壯的工作來保證這個(gè)疤估，但是在實(shí)際中它往往是可以讓人接受的。一個(gè)搶斷失敗的線程在嘗試另外的搶斷之前會(huì)降低自己的優(yōu)先級(jí)霎冯，在嘗試搶斷之間執(zhí)行Thread.yeild操作，然后將自己的狀態(tài)在FJTaskRunnerGroup中設(shè)置為不活躍的钞瀑。他們會(huì)一直阻塞直到有新的主線程沈撞。其他情況下，在進(jìn)行一定的自旋次數(shù)之后雕什，線程將進(jìn)入休眠階段缠俺，他們會(huì)休眠而不是放棄搶斷。強(qiáng)化的休眠機(jī)制會(huì)給人造成一種需要花費(fèi)很長時(shí)間去劃分任務(wù)的假象贷岸。但是這似乎是最好的也是通用的折中方案壹士。框架的未來版本也許會(huì)支持額外的控制方法偿警，以便于讓程序員在感覺性能受到影響時(shí)可以重寫默認(rèn)的實(shí)現(xiàn)躏救。

性能

如今，隨著編譯器與Java虛擬機(jī)性能的不斷提升螟蒸，性能測試結(jié)果也僅僅只能適用一時(shí)盒使。但是，本節(jié)中所提到的測試結(jié)果數(shù)據(jù)卻能揭示Fork/join框架的基本特性七嫌。

下面表格中簡單介紹了在下文將會(huì)用到的一組fork/join測試程序少办。這些程序是從util.concurrent包里的示例代碼改編而來，用來展示fork/join框架在解決不同類型的問題模型時(shí)所表現(xiàn)的差異诵原，同時(shí)得到該框架在一些常見的并行測試程序上的測試結(jié)果英妓。

下文提到的主要的測試挽放，其測試程序都是運(yùn)行在Sun Enterprise 10000服務(wù)器上，該服務(wù)器擁有30個(gè)CPU蔓纠，操作系統(tǒng)為Solaris7系統(tǒng)骂维，運(yùn)行Solaris商業(yè)版1.2 JVM（2.2.2_05發(fā)布版本的一個(gè)早期版本）。同時(shí)贺纲，Java虛擬機(jī)的關(guān)于線程映射的環(huán)境參數(shù)選擇為“bound threads”(譯者注：XX:+UseBoundThreads航闺，綁定用戶級(jí)別的線程到內(nèi)核線程，只與solaris有關(guān))猴誊，而關(guān)于虛擬機(jī)的內(nèi)存參數(shù)設(shè)置在4.2章節(jié)討論潦刃。另外，需要注意的是下文提到的部分測試則是運(yùn)行在擁有4CPU的Sun Enterprise450服務(wù)器上懈叹。

為了降低定時(shí)器粒度以及Java虛擬機(jī)啟動(dòng)因素對測試結(jié)果的影響乖杠，測試程序都使用了數(shù)量巨大的輸入?yún)?shù)。而其它一些啟動(dòng)因素我們通過在啟動(dòng)定時(shí)器之前先運(yùn)行初始化任務(wù)來進(jìn)行屏蔽澄成。所得到的測試結(jié)果數(shù)據(jù)胧洒，大部分都是在三次測試結(jié)果的中間值，然而一些測試數(shù)據(jù)僅僅來自一次運(yùn)行結(jié)果（包括4.2~4.4章節(jié)很多測試）墨状，因此這些測試結(jié)果會(huì)有噪音表現(xiàn)卫漫。

加速比

通過使用不同數(shù)目（1~30）的工作線程對同一問題集進(jìn)行測試，用來得到框架的擴(kuò)展性測試結(jié)果肾砂。雖然我們無法保證Java虛擬機(jī)是否總是能夠?qū)⒚恳粋€(gè)線程映射到不同的空閑CPU上列赎，同時(shí)，我們也沒有證據(jù)來證明這點(diǎn)镐确。有可能映射一個(gè)新的線程到CPU的延遲會(huì)隨著線程數(shù)目的增加而變大包吝，也可能會(huì)隨不同的系統(tǒng)以及不同的測試程序而變化。但是源葫，所得到的測試結(jié)果的確顯示出增加線程的數(shù)目確實(shí)能夠增加使用的CPU的數(shù)目诗越。

加速比通常表示為“Time n/Time1”.如上圖所示，其中求積分的程序表現(xiàn)出最好的加速比（30個(gè)線程的加速比為28.2）息堂，表現(xiàn)最差的是矩陣分解程序（30線程是加速比只有15.35）

另一種衡量擴(kuò)展性的依據(jù)是：任務(wù)執(zhí)行率嚷狞，及執(zhí)行一個(gè)單獨(dú)任務(wù)（這里的任務(wù)有可能是遞歸分解節(jié)點(diǎn)任務(wù)也可能是根節(jié)點(diǎn)任務(wù)）所開銷的平均時(shí)間。下面的數(shù)據(jù)顯示出一次性執(zhí)行各個(gè)程序所得到的任務(wù)執(zhí)行率數(shù)據(jù)储矩。很明顯感耙，單位時(shí)間內(nèi)執(zhí)行的任務(wù)數(shù)目應(yīng)該是固定常量。然而事實(shí)上持隧，隨著線程數(shù)目增加即硼，所得到的數(shù)據(jù)會(huì)表現(xiàn)出輕微的降低，這也表現(xiàn)出其一定的擴(kuò)展性限制屡拨。這里需要說明的是只酥，之所以任務(wù)執(zhí)行率在各個(gè)程序上表現(xiàn)的巨大差異褥实，是因其任務(wù)粒度的不同造成的。任務(wù)執(zhí)行率最小的程序是Fib（菲波那契數(shù)列）裂允，其閥值設(shè)置為13损离，在30個(gè)線程的情況下總共完成了280萬個(gè)單元任務(wù)。

導(dǎo)致這些程序的任務(wù)完成率沒有表現(xiàn)為水平直線的因素有四個(gè)绝编。其中三個(gè)對所有的并發(fā)框架來說都是普遍原因僻澎，所以，我們就從對FJTask框架（相對于Cilk等框架）所特有的因素說起十饥，即垃圾回收窟勃。

垃圾回收

總的來說，現(xiàn)在的垃圾回收機(jī)制的性能是能夠與fork/join框架所匹配的：fork/join程序在運(yùn)行時(shí)會(huì)產(chǎn)生巨大數(shù)量的任務(wù)單元逗堵，然而這些任務(wù)在被執(zhí)行之后又會(huì)很快轉(zhuǎn)變?yōu)閮?nèi)存垃圾秉氧。相比較于順序執(zhí)行的單線程程序，在任何時(shí)候蜒秤，其對應(yīng)的fork/join程序需要最多p倍的內(nèi)存空間（其中p為線程數(shù)目）汁咏。基于分代的半空間拷貝垃圾回收器（也就是本文中測試程序所使用的Java虛擬機(jī)所應(yīng)用的垃圾回收器）能夠很好的處理這種情況作媚，因?yàn)檫@種垃圾回收機(jī)制在進(jìn)行內(nèi)存回收的時(shí)候僅僅拷貝非垃圾內(nèi)存單元攘滩。這樣做，就避免了在手工并發(fā)內(nèi)存管理上的一個(gè)復(fù)雜的問題掂骏，即跟蹤那些被一個(gè)線程分配卻在另一個(gè)線程中使用的內(nèi)存單元轰驳。這種垃圾回收機(jī)制并不需要知道內(nèi)存分配的源頭，因此也就無需處理這個(gè)棘手的問題弟灼。

這種垃圾回收機(jī)制優(yōu)勢的一個(gè)典型體現(xiàn)：使用這種垃圾回收機(jī)制，四個(gè)線程運(yùn)行的Fib程序耗時(shí)僅為5.1秒鐘冒黑，而如果在Java虛擬機(jī)設(shè)置關(guān)閉代拷貝回收（這種情況下使用的就是標(biāo)記–清除垃圾回收機(jī)制了）田绑，耗時(shí)需要9.1秒鐘。

然而抡爹，只有內(nèi)存使用率只有達(dá)到一個(gè)很高的值的情況下掩驱，垃圾回收機(jī)制才會(huì)成為影響擴(kuò)展性的一個(gè)因素，因?yàn)檫@種情況下冬竟，虛擬機(jī)必須經(jīng)常停止其他線程來進(jìn)行垃圾回收欧穴。以下的數(shù)據(jù)顯示出在三種不同的內(nèi)存設(shè)置下（Java虛擬機(jī)支持通過額外的參數(shù)來設(shè)置內(nèi)存參數(shù)），加速比所表現(xiàn)出的差異：默認(rèn)的4M的半空間泵殴，64M的半空間涮帘，另外根據(jù)線程數(shù)目按照公式（2+2p）M設(shè)置半空間。使用較小的半空間笑诅，在額外線程導(dǎo)致垃圾回收率攀高的情況下调缨，停止其他線程并進(jìn)行垃圾回收的開銷開始影響加封疮鲫。

鑒于上面的結(jié)果，我們使用64M的半空間作為其他測試的運(yùn)行標(biāo)準(zhǔn)弦叶。其實(shí)設(shè)置內(nèi)存大小的一個(gè)更好的策略就是根據(jù)每次測試的實(shí)際線程數(shù)目來確定俊犯。（正如上面的測試數(shù)據(jù)，我們發(fā)現(xiàn)這種情況下伤哺，加速比會(huì)表現(xiàn)的更為平滑）燕侠。相對的另一方面，程序所設(shè)定的任務(wù)粒度的閥值也應(yīng)該隨著線程數(shù)目成比例的增長立莉。

內(nèi)存分配和字寬

在上文提到的測試程序中多艇，有四個(gè)程序會(huì)創(chuàng)建并操作數(shù)量巨大的共享數(shù)組和矩陣：數(shù)字排序，矩陣相乘/分解以及松弛常侣。其中溯职，排序算法應(yīng)該是對數(shù)據(jù)移動(dòng)操作（將內(nèi)存數(shù)據(jù)移動(dòng)到CPU緩存）以及系統(tǒng)總內(nèi)存帶寬，最為敏感的媒熊。為了確定這些影響因素的性質(zhì)奇适，我們將排序算法Sort改寫為四個(gè)版本，分別對Byte字節(jié)數(shù)據(jù)芦鳍，short型數(shù)據(jù)嚷往，int型數(shù)據(jù)以及l(fā)ong型數(shù)據(jù)進(jìn)行排序。這些程序所操作的數(shù)據(jù)都在0~255之間柠衅，以確保這些對比測試之間的平等性皮仁。理論上，操作數(shù)據(jù)的字寬越大菲宴，內(nèi)存操作壓力也相應(yīng)越大贷祈。

測試結(jié)果顯示，內(nèi)存操作壓力的增加會(huì)導(dǎo)致加速比的降低喝峦，雖然我們無法提供明確的證據(jù)來證明這是引起這種表現(xiàn)的唯一原因势誊。但數(shù)據(jù)的字寬的確是影響程序的性能的。比如谣蠢，使用一個(gè)線程粟耻，排序字節(jié)Byte數(shù)據(jù)需要耗時(shí)122.5秒，然而排序long數(shù)據(jù)則需要耗時(shí)242.5秒眉踱。

任務(wù)同步

正如3.2章節(jié)所討論的挤忙，任務(wù)竊取模型經(jīng)常會(huì)在處理任務(wù)的同步上遇到問題，如果工作線程獲取任務(wù)的時(shí)候谈喳，但相應(yīng)的隊(duì)列已經(jīng)沒有任務(wù)可供獲取册烈，這樣就會(huì)產(chǎn)生競爭。在FJTask框架中叁执，這種情況有時(shí)會(huì)導(dǎo)致線程強(qiáng)制睡眠茄厘。

從Jacobi程序中我們可以看到這類問題矮冬。Jacobi程序運(yùn)行100步，每一步的操作次哈，相應(yīng)矩陣點(diǎn)周圍的單元都會(huì)進(jìn)行刷新胎署。程序中有一個(gè)全局的屏障分隔。為了明確這種同步操作的影響大小窑滞。我們在一個(gè)程序中每10步操作進(jìn)行一次同步琼牧。如圖中表現(xiàn)出的擴(kuò)展性的差異說明了這種并發(fā)策略的影響。也暗示著我們在這個(gè)框架后續(xù)的版本中應(yīng)該增加額外的方法以供程序員來重寫哀卫，以調(diào)整框架在不同的場景中達(dá)到最大的效率巨坊。（注意，這種圖可能對同步因素的影響略有夸大此改，因?yàn)?0步同步的版本很可能需要管理更多的任務(wù)局部性）

任務(wù)局部性

FJTask趾撵，或者說其他的fork/join框架在任務(wù)分配上都是做了優(yōu)化的，盡可能多的使工作線程處理自己分解產(chǎn)生的任務(wù)共啃。因?yàn)槿绻贿@樣做占调，程序的性能會(huì)受到影響，原因有二：

從其他隊(duì)列竊取任務(wù)的開銷要比在自己隊(duì)列執(zhí)行pop操作的開銷大移剪。

在大多數(shù)程序中究珊，任務(wù)操作操作的是一個(gè)共享的數(shù)據(jù)單元，如果只運(yùn)行自己部分的任務(wù)可以獲得更好的局部數(shù)據(jù)訪問纵苛。

如上圖所示剿涮，在大多數(shù)程序中，竊取任務(wù)的相對數(shù)據(jù)都最多維持在很低的百分比攻人。然后其中LU和MM程序隨著線程數(shù)目的增加取试，會(huì)在工作負(fù)載上產(chǎn)生更大的不平衡性（相對的產(chǎn)生了更多的任務(wù)竊取）怀吻。通過調(diào)整算法我們可以降低這種影響以獲得更好的加速比想括。

與其他框架比較

與其他不同語言的框架相比較，不太可能會(huì)得到什么明確的或者說有意義的比較結(jié)果烙博。但是，通過這種方法烟逊，最起碼可以知道FJTask在與其他語言（這里主要指的是C和C++）所編寫的相近框架比較所表現(xiàn)的優(yōu)勢和限制渣窜。下面這個(gè)表格展示了幾種相似框架（Cilk,Hood ,Stackthreads,以及Filaments）所測試的性能數(shù)據(jù)。涉及到的測試都是在4CPU的Sun Enterprise450服務(wù)器運(yùn)行4個(gè)線程進(jìn)行的宪躯。為了避免在不同的框架或者程序上進(jìn)行重新配置乔宿，所有的測試程序運(yùn)行的問題集都比上面的測試稍小些。得到的數(shù)據(jù)也是取三次測試中的最優(yōu)值访雪，以確保編譯器或者說是運(yùn)行時(shí)配置都提供了最好的性能详瑞。其中Fib程序沒有指定任務(wù)粒度的閥值掂林，也就是說默認(rèn)的1.（這個(gè)設(shè)置在Filaments版的Fib程序中設(shè)置為1024，這樣程序會(huì)表現(xiàn)的和其它版本更為一致）坝橡。

在加速比的測試中泻帮，不同框架在不同程序上所得到的測試結(jié)果非常接近，線程數(shù)目1~4计寇，加速比表現(xiàn)在（3.0~4.0之間）锣杂。因此下圖也就只聚焦在不同框架表現(xiàn)的不同的絕對性能上，然而因?yàn)樵诙嗑€程方面番宁，所有的框架都是非吃快的，大多數(shù)的差異更多的是有代碼本身的質(zhì)量蝶押，編譯器的不同踱蠢，優(yōu)化配置項(xiàng)或者設(shè)置參數(shù)造成的。實(shí)際應(yīng)用中棋电，根據(jù)實(shí)際需要選擇不同的框架以彌補(bǔ)不同框架之間表現(xiàn)的巨大差異茎截。

結(jié)論

本文已經(jīng)表明可以支持可移植，高效离陶，可擴(kuò)展的并行處理在純Java稼虎，和為可以利用的程序員提供方便的API，框架只是通過以下幾個(gè)簡單的設(shè)計(jì)規(guī)則和設(shè)計(jì)模式（如[7]中提出和討論的））招刨。該觀察樣本程序的性能特征霎俩，這里測量兩者為用戶提供進(jìn)一步的指導(dǎo)框架，并提出一些潛在的改進(jìn)框架本身沉眶。即使可擴(kuò)展性的結(jié)果只顯示在一個(gè)單一的JVM打却，的一些主要實(shí)證結(jié)果應(yīng)該更多一致：

分代GC通常與并行性，它可以阻礙垃圾時(shí)的可擴(kuò)展性一代率迫使非常頻繁的收藏谎倔。 在這個(gè)JVM的根本原因似乎是停止收集線程花費(fèi)時(shí)間大致成正比到運(yùn)行線程的數(shù)量柳击。 因?yàn)楦嗟倪\(yùn)行線程每單位時(shí)間產(chǎn)生更多垃圾，開銷可以以線程數(shù)大致二次爬升片习。即使如此捌肴，這顯著影響了性能GC率相對較高。 但是藕咏，那導(dǎo)致的問題需要進(jìn)一步的研究和開發(fā)并行和并行GC算法状知。 結(jié)果呈現(xiàn)這里另外表明提供的可取性多處理器的調(diào)優(yōu)選項(xiàng)和自適應(yīng)機(jī)制JVM將內(nèi)存擴(kuò)展到活動(dòng)處理器的數(shù)量。

大多數(shù)可擴(kuò)展性問題僅在何時(shí)才顯露出來程序使用比甚至更多的CPU運(yùn)行在大多數(shù)股票多處理器上孽查。 FJTask（以及其他fork / join框架）似乎提供了幾乎理想通常加速幾乎任何一個(gè)fork / join程序可用的2路饥悴，4路和8路SMP機(jī)器。該本文似乎是第一次報(bào)告系統(tǒng)為庫存設(shè)計(jì)的任何fork / join框架的結(jié)果多處理器運(yùn)行在16個(gè)以上的CPU上。 進(jìn)一步需要測量才能看到是否符合西设。

應(yīng)用程序的特點(diǎn)（包括內(nèi)存）經(jīng)常地區(qū)瓣铣，任務(wù)地點(diǎn)，全球同步的使用對可擴(kuò)展性和絕對性都有更大的影響性能比做特性的框架贷揽，JVM或底層操作系統(tǒng)棠笑。 例如，非正式測試表明仔細(xì)避免deques中的同步（在3.1節(jié)中討論）基本上沒有影響任務(wù)生成率相對較低的程序擒滑，如 LU腐晾。 但是，重點(diǎn)是保持任務(wù)管理開銷最小化擴(kuò)大了適用范圍框架和相關(guān)設(shè)計(jì)的實(shí)用性和編程技術(shù)丐一。

除了漸進(jìn)的改進(jìn)藻糖，今后的工作就這樣框架可能包括構(gòu)建有用的應(yīng)用程序（就像反對演示和測試），隨后的評估生產(chǎn)程序加載库车，不同JVM上的測量巨柒，并開發(fā)用于集群的擴(kuò)展多處理器。