摘要

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

介紹

Fork/Join并行方式是獲取良好的并行計(jì)算性能的一種最簡(jiǎn)單同時(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ù)可以用足夠簡(jiǎn)單的、短小的順序方法來執(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ǔ)）對(duì)Fork/Join程序來說并不是最優(yōu)的選擇：

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

對(duì)于一個(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ā)揮。

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

盡管這種思想已經(jīng)存在了很長(zhǎ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)勢(shì)是能夠讓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程序的簡(jiǎn)單性、常規(guī)性以及一致性來執(zhí)行這種映射。 所有的這些框架可以兼容（不同程度）并行程序以不同的樣式編寫，它們優(yōu)化了fork / join設(shè)計(jì)：

?一組工作者線程池是準(zhǔn)備好的。每個(gè)工作線程都是標(biāo)準(zhǔn)的(“重量級(jí)”)處理存放在隊(duì)列中任務(wù)的線程（這地方指的是Thread類的子類FJTaskRunner的實(shí)例對(duì)象）。通常情況下，工作線程應(yīng)該與系統(tǒng)的處理器數(shù)量一致。對(duì)于一些原生的框架例如說Cilk,他們首先將映射成內(nèi)核線程或者是輕量級(jí)的進(jìn)程，然后再在處理器上面運(yùn)行。在Java中，虛擬機(jī)和操作系統(tǒng)需要相互結(jié)合來完成線程到處理器的映射。然后對(duì)于計(jì)算密集型的運(yùn)算來說，這種映射對(duì)于操作系統(tǒng)來說是一種相對(duì)簡(jiǎn)單的任務(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接口。（對(duì)于上面兩種情況來說，一個(gè)類也可以選擇實(shí)現(xiàn)Runnable接口，類的實(shí)例對(duì)象既可以在任務(wù)中執(zhí)行也可以在線程中執(zhí)行。因?yàn)槿蝿?wù)執(zhí)行受到來自FJTask方法嚴(yán)厲規(guī)則的制約，子類化FJTask相對(duì)來說更加方便，也能夠直接調(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è)簡(jiǎn)單的控制和管理類（這里指的是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多線程程序的可移植性。對(duì)程序員來說通常有兩個(gè)參數(shù)值的他們關(guān)注：

對(duì)于工作線程的創(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ī)制在對(duì)小塊方法的優(yōu)化方面相對(duì)于單塊的程序來說要好。這樣，加上數(shù)據(jù)本地化的優(yōu)勢(shì)，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操作。

對(duì)于一個(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ì)無(wú)阻塞的完成。

當(dāng)一個(gè)工作線程無(wú)法再?gòu)钠渌€程中獲取任務(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ì)減少線程競(jìng)爭(zhēng)。同樣體現(xiàn)了遞歸分治算法的大任務(wù)優(yōu)先策略。因此，更早期被偷取的任務(wù)有可能會(huì)提供一個(gè)更大的單元任務(wù)，從而使得偷取線程能夠在將來進(jìn)行遞歸分解。

作為上述規(guī)則的一個(gè)后果，對(duì)于一些基礎(chǔ)的操作而言，使用相對(duì)較小粒度的任務(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ù)。相對(duì)于其他語(yǔ)言的類似框架，這個(gè)原因使我們大大降低了實(shí)現(xiàn)FJTasks的復(fù)雜性以及所需要的代碼數(shù)。

雙端隊(duì)列的基本結(jié)構(gòu)采用了很常規(guī)的一個(gè)結(jié)構(gòu)——使用一個(gè)數(shù)組（盡管是可變長(zhǎng)的）來表示每個(gè)隊(duì)列，同時(shí)附帶兩個(gè)索引：top 索引就類似于數(shù)組中的棧指針，通過push和pop操作來改變。Base 索引只能通過take操作來改變。鑒于FJTaskRunner操作都是無(wú)縫的綁定到雙端隊(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ā)對(duì)象。一開始做出這個(gè)決定主要是考慮到Java內(nèi)存模型的一致性。但是在這個(gè)級(jí)別它所需要的間接尋址被證明在一些測(cè)試過的平臺(tái)上能夠提升性能?？赡苁且?yàn)樵L問鄰近的元素而降低了緩存爭(zhēng)用，這樣內(nèi)存里面的間接尋址會(huì)更快一點(diǎn)。

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

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

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

Pop和take操作只有在雙端隊(duì)列為空的時(shí)候才會(huì)發(fā)生沖突，否則的話，隊(duì)列會(huì)保證他們?cè)诓煌臄?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è)不對(duì)稱的規(guī)則將用于防止?jié)撛诘臎_突：pop會(huì)重新檢查狀態(tài)并在獲取鎖之后繼續(xù)（對(duì)take所持有的也一樣），直到隊(duì)列真的為空才退出。而Take操作會(huì)立即退出，特別是當(dāng)嘗試去獲得另外一個(gè)任務(wù)。與其他類似使用Clik的THE協(xié)議一樣，這種不對(duì)稱性是唯一重要的改變。

使用volitile變量索引push操作在隊(duì)列沒有滿的情況下不需要同步就可以進(jìn)行。如果隊(duì)列將要溢出，那么它首先必須要獲得隊(duì)列鎖來重新設(shè)置隊(duì)列的長(zhǎng)度。否則，只需確保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ì)引起輕微的性能損耗。

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

主要的問題在于當(dāng)一個(gè)工作線程既無(wú)本地任務(wù)也不能從別的線程中搶斷任務(wù)時(shí)怎么辦。如果程序運(yùn)行在專業(yè)的多核處理器上面，那么可以依賴于硬件的忙等待自旋循環(huán)的去嘗試搶斷一個(gè)任務(wù)。然而，即使這樣，嘗試搶斷還是會(huì)增加競(jìng)爭(zhēng)，甚至?xí)?dǎo)致那些不是閑置的工作線程降低效率（由于鎖協(xié)議，3.1節(jié)中）。除此之外，在一個(gè)更適合此框架運(yùn)行的場(chǎng)景中，操作系統(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)很長(zhǎng)時(shí)間去劃分任務(wù)的假象。但是這似乎是最好的也是通用的折中方案?？蚣艿奈磥戆姹疽苍S會(huì)支持額外的控制方法，以便于讓程序員在感覺性能受到影響時(shí)可以重寫默認(rèn)的實(shí)現(xiàn)。

性能

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

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

下文提到的主要的測(cè)試，其測(cè)試程序都是運(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é)討論。另外，需要注意的是下文提到的部分測(cè)試則是運(yùn)行在擁有4CPU的Sun Enterprise450服務(wù)器上。

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

加速比

通過使用不同數(shù)目（1~30）的工作線程對(duì)同一問題集進(jìn)行測(cè)試，用來得到框架的擴(kuò)展性測(cè)試結(jié)果。雖然我們無(wú)法保證Java虛擬機(jī)是否總是能夠?qū)⒚恳粋€(gè)線程映射到不同的空閑CPU上，同時(shí)，我們也沒有證據(jù)來證明這點(diǎn)。有可能映射一個(gè)新的線程到CPU的延遲會(huì)隨著線程數(shù)目的增加而變大，也可能會(huì)隨不同的系統(tǒng)以及不同的測(cè)試程序而變化。但是，所得到的測(cè)試結(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萬(wàn)個(gè)單元任務(wù)。

導(dǎo)致這些程序的任務(wù)完成率沒有表現(xiàn)為水平直線的因素有四個(gè)。其中三個(gè)對(duì)所有的并發(fā)框架來說都是普遍原因，所以，我們就從對(duì)FJTask框架（相對(duì)于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í)候，其對(duì)應(yīng)的fork/join程序需要最多p倍的內(nèi)存空間（其中p為線程數(shù)目）。基于分代的半空間拷貝垃圾回收器（也就是本文中測(cè)試程序所使用的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)存分配的源頭，因此也就無(wú)需處理這個(gè)棘手的問題。

這種垃圾回收機(jī)制優(yōu)勢(shì)的一個(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的半空間作為其他測(cè)試的運(yùn)行標(biāo)準(zhǔn)。其實(shí)設(shè)置內(nèi)存大小的一個(gè)更好的策略就是根據(jù)每次測(cè)試的實(shí)際線程數(shù)目來確定。（正如上面的測(cè)試數(shù)據(jù)，我們發(fā)現(xiàn)這種情況下，加速比會(huì)表現(xiàn)的更為平滑）。相對(duì)的另一方面，程序所設(shè)定的任務(wù)粒度的閥值也應(yīng)該隨著線程數(shù)目成比例的增長(zhǎng)。

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

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

測(cè)試結(jié)果顯示，內(nèi)存操作壓力的增加會(huì)導(dǎo)致加速比的降低，雖然我們無(wú)法提供明確的證據(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)生競(jìng)爭(zhēng)。在FJTask框架中，這種情況有時(shí)會(huì)導(dǎo)致線程強(qiáng)制睡眠。

從Jacobi程序中我們可以看到這類問題。Jacobi程序運(yùn)行100步，每一步的操作，相應(yīng)矩陣點(diǎn)周圍的單元都會(huì)進(jìn)行刷新。程序中有一個(gè)全局的屏障分隔。為了明確這種同步操作的影響大小。我們?cè)谝粋€(gè)程序中每10步操作進(jìn)行一次同步。如圖中表現(xiàn)出的擴(kuò)展性的差異說明了這種并發(fā)策略的影響。也暗示著我們?cè)谶@個(gè)框架后續(xù)的版本中應(yīng)該增加額外的方法以供程序員來重寫，以調(diào)整框架在不同的場(chǎng)景中達(dá)到最大的效率。（注意，這種圖可能對(duì)同步因素的影響略有夸大，因?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ù)的相對(duì)數(shù)據(jù)都最多維持在很低的百分比。然后其中LU和MM程序隨著線程數(shù)目的增加，會(huì)在工作負(fù)載上產(chǎn)生更大的不平衡性（相對(duì)的產(chǎn)生了更多的任務(wù)竊?。?。通過調(diào)整算法我們可以降低這種影響以獲得更好的加速比。

與其他框架比較

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

在加速比的測(cè)試中，不同框架在不同程序上所得到的測(cè)試結(jié)果非常接近，線程數(shù)目1~4，加速比表現(xiàn)在（3.0~4.0之間）。因此下圖也就只聚焦在不同框架表現(xiàn)的不同的絕對(duì)性能上，然而因?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è)簡(jiǎn)單的設(shè)計(jì)規(guī)則和設(shè)計(jì)模式（如[7]中提出和討論的））。該觀察樣本程序的性能特征，這里測(cè)量?jī)烧邽橛脩籼峁┻M(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率相對(duì)較高。 但是，那導(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)為庫(kù)存設(shè)計(jì)的任何fork / join框架的結(jié)果多處理器運(yùn)行在16個(gè)以上的CPU上。 進(jìn)一步需要測(cè)量才能看到是否符合。

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

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