摘要
本文描述了一個支持并行編程風(fēng)格的Java框架的設(shè)計、實現(xiàn)和性能，該框架通過(遞歸)將問題分解為并行解決的子任務(wù)，等待它們完成，然后組合結(jié)果?？傮w設(shè)計是Cilk提出的工作-竊取框架的一個變體。主要的實現(xiàn)技術(shù)圍繞任務(wù)隊列和工作線程的高效構(gòu)造和管理。測試的性能表明，大多數(shù)程序都具有良好的并行速度，但同時也提出了可能的改進措施。
1. 介紹
Fork/join并行是獲得良好并行性能的最簡單、最有效的設(shè)計技術(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操作啟動一個新的并行的fork/join子任務(wù)。join操作會使得當前的任務(wù)不會繼續(xù)處理直到forked的子任務(wù)完成。Fork/join算法，像其他分而治之算法一樣，幾乎總是遞歸的，重復(fù)拆分子任務(wù)，直到它們小到足以使用簡單的、簡短的串行方法來解決為止。
2. 設(shè)計
可以使用任何支持并行執(zhí)行子任務(wù)的構(gòu)造的框架以及等待它們完成的機制來運行fork/join程序。然而，java.lang.Thread類(也就是POSIX pthreds, Java線程通?；诘木€程)不是最佳的支持fork/join程序的工具：
- fork/join任務(wù)具有簡單和規(guī)律的同步和管理要求。比起需要通用線程，fork/join任務(wù)生成的計算圖表允許更有效的調(diào)度策略。例如，fork/join任務(wù)永遠不需要阻塞除了等待子任務(wù)。因此跟蹤阻塞的通用線程所帶來的開銷和記錄就是浪費的。
- 給定合理的基本任務(wù)粒度，構(gòu)建和管理線程的成本可能大于任務(wù)本身的計算時間。雖然粒度可以并且應(yīng)該在特定平臺上運行程序時進行調(diào)整，但是超過線程開銷所需的極粗粒度限制了利用并行性的機會。
簡單的說就是，標準的線程框架對于支持fork/join程序來說太重量級了。但是，由于線程也構(gòu)成了許多其他并發(fā)和并行編程風(fēng)格的基礎(chǔ)，為了支持這種風(fēng)格，刪除開銷或調(diào)整線程本身的調(diào)度是不可能的（或者至少是不切實際的）。
雖然這些想法肯定有一個較長的heritage，第一個發(fā)表的框架，為這些問題提供系統(tǒng)的解決方案是Cilk。Cilk和其他輕量級可執(zhí)行框架層，在操作系統(tǒng)的基本線程或進程機制之上，提供特殊用途的fork/join支持。本策略同樣適用于Java，即使Java線程又反過來分層到更低級別的操作系統(tǒng)功能上。創(chuàng)建這種Java輕量級執(zhí)行框架的主要優(yōu)點是使fork/join程序能夠以更便攜的方式編寫，并在支持JVM的各種系統(tǒng)上運行。
FJTask框架基于Cilk中使用的設(shè)計的一個變體。在Hood[4]、Filaments[[8]、stackthreads[[10]以及依賴輕量級可執(zhí)行任務(wù)的相關(guān)系統(tǒng)中也可以看到其他變體。所有這些框架將任務(wù)映射到線程，其方式與操作系統(tǒng)將線程映射到CPU的方式相同，但是，在執(zhí)行映射時，要利用fork/join程序的簡單性、規(guī)律性和約束。雖然所有這些框架都可以（以不同的程度）容納以不同樣式編寫的并行程序，但它們針對fork / join設(shè)計進行了優(yōu)化：
- 建立了一個工作線程池。每個工作線程都是一個處理隊列中的任務(wù)的標準("重量級")線程(這里是Thread子類FJTaskRunner的一個實例)。通常，工作線程與系統(tǒng)上的CPU一樣多。在本地框架(如Cilk)中，它們被映射到內(nèi)核線程或輕量級進程，然后依次映射到cpu。在Java中，JVM和操作系統(tǒng)必須被信任，才能將這些線程映射到CPU。但是，對于操作系統(tǒng)來說，這是一個非常簡單的任務(wù)，因為這些線程是計算密集型的。任何合理的映射策略都會將這些線程映射到不同的CPU。
- 所有的fork/join任務(wù)都是輕量級可執(zhí)行類的實例，而不是線程的實例。在Java中，獨立執(zhí)行任務(wù)必須實現(xiàn)Runnable接口，并且定義運行方法。在FJTask框架中，這些任務(wù)是FJTask的子類，而不是子類化Thread，兩者都實現(xiàn)了Runnable。(在這兩種情況下，類都可以實現(xiàn)Runnable，然后提供要在執(zhí)行任務(wù)或線程中運行的實例。由于任務(wù)在FJTask方法支持的受限規(guī)則下運行，因此子類FJTask更方便，從而能夠直接調(diào)用它們。)
- 一個特殊的隊列和調(diào)度規(guī)則用于管理任務(wù)并通過工作線程執(zhí)行它們。這些機制是由任務(wù)類中提供的幾個方法觸發(fā)的：主要是fork、join、isDone(一個完成狀態(tài)指示符)，以及一些方便的方法，如coInvoke，fork接著join兩個或多個任務(wù)。
- 一個簡單的控制和管理工具（此處為FJTaskRunnerGroup）設(shè)置工作池，并在從正常線程（例如Java程序中執(zhí)行main的線程）調(diào)用時啟動給定fork/join任務(wù)的執(zhí)行。
作為程序員如何看待這個框架的標準示例，這里有一個計算Fibonacci函數(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);
}
}
此版本的運行速度至少比同等程序快30倍，其中每個新任務(wù)在第4節(jié)中描述的平臺上的新java.lang.Thread中運行。它在維護多線程Java程序的內(nèi)在可移植性的同時做到了這一點。程序員通常只關(guān)注兩個調(diào)整參數(shù)：
- 要構(gòu)造的工作線程數(shù)，通常應(yīng)該與平臺上可用的CPU數(shù)量相對應(yīng)（或更少，為了其他不相關(guān)的目的而保留處理，或者偶爾更多，以吸收非計算冗余）。
- 粒度參數(shù)，表示生成任務(wù)的開銷超過潛在并行性優(yōu)勢的點。這個參數(shù)通常更依賴于算法，而不是平臺。通常可以確定在單處理器上運行時獲得良好結(jié)果的閾值，但是當它們存在時仍然利用多個CPU。作為一個附帶好處，這種方法與JVM動態(tài)編譯機制很好地融合，這些機制比單片程序更好地優(yōu)化小方法。這與數(shù)據(jù)局部性優(yōu)勢一起，可以使fork/join算法甚至在單處理器上勝過其他類型的算法。
2.1 工作-竊取
fork/join框架的核心在于它的輕量級調(diào)度機制。FJTask采用Cilk工作竊取調(diào)度程序中開創(chuàng)的基本策略：
- 每個工作線程在其自己的調(diào)度隊列中維護可運行的任務(wù)。
- 隊列被維護為雙端隊列(即deques，通常發(fā)音為“decks”)，支持LIFO的push和pop操作，以及FIFO的take操作。
- 在由給定工作線程運行的任務(wù)中生成的子任務(wù)被推送到該工作者自己的deque上。
- 工作線程通過彈出任務(wù)以LIFO（最年輕的優(yōu)先）順序處理自己的deques。
- 當工作線程沒有要運行的本地任務(wù)時，它會嘗試使用FIFO（最早的優(yōu)先）規(guī)則從另一個隨機選擇的工作者那里獲取（“竊取”）任務(wù)。
- 當工作線程遇到j(luò)oin操作時，它會處理其他任務(wù)(如果可用的話)，直到目標任務(wù)被注意到已經(jīng)完成為止(通過isDone)。否則，所有任務(wù)都在不阻塞的情況下運行到完成。
- 當工作者線程沒有工作并且沒有從其它線程中竊取任何工作時，它將回退(通過yield、sleep和/或優(yōu)先級調(diào)整-參見第3節(jié))，并且稍后再試，除非所有的工人都知道類似空閑，在這種情況下，它們都會阻塞，直到從頂層調(diào)用另一個任務(wù)為止。
正如[5]中更詳細討論的那樣，每個線程使用LIFO規(guī)則處理自己的任務(wù)，但竊取其他任務(wù)的FIFO規(guī)則對于一大類遞歸的fork / join設(shè)計是最佳的。不太正式地說，該設(shè)計提供了兩個基本優(yōu)勢：它通過讓偷竊者作為所有者在雙端隊列的另一側(cè)進行操作來減少爭用。它還利用了遞歸分治算法的特性，即早期生成“大”任務(wù)。因此，較舊的被盜任務(wù)可能提供更大的工作單元，導(dǎo)致竊取線程進一步遞歸分解。
作為這些規(guī)則的一個結(jié)果，對于基本操作使用相對較小的任務(wù)粒度的程序往往比那些只使用粗粒度分區(qū)或不使用遞歸分解的程序運行得更快。盡管在大多數(shù)fork/join程序中相對較少的任務(wù)被盜，但創(chuàng)建許多細粒度的任務(wù)意味著只要工作線程準備好運行它就可以使用任務(wù)。
3. 實現(xiàn)
該框架已經(jīng)在大約800行純Java代碼中實現(xiàn)，主要是在java.lang.Thread的子類FJTaskRunner中實現(xiàn)的。FJTasks只維護布爾完成狀態(tài)，并通過委托當前工作線程執(zhí)行所有其他操作。FJTaskRunnerGroup類用于構(gòu)造工作線程，維護一些共享狀態(tài)(例如，偷竊操作所需的所有工作線程的標識)，并幫助協(xié)調(diào)啟動和關(guān)閉。更詳細的實現(xiàn)文檔可以在util.并發(fā)包中獲得。本節(jié)只討論在實現(xiàn)此框架時遇到的兩組問題和解決方案：支持高效的deque操作(Push、POP和Take)，以及管理線程獲得新工作的竊取協(xié)議。
3.1 雙端隊列
為了實現(xiàn)高效且可擴展的執(zhí)行，必須盡可能快地完成任務(wù)管理。 創(chuàng)建，推送和稍后彈出（或者更不頻繁地）執(zhí)行任務(wù)是順序程序中過程調(diào)用開銷的類比。 較低的開銷使程序員能夠采用較小的任務(wù)粒度，從而更好地利用并行性。
任務(wù)分配本身是JVM的責任。Java垃圾收集使我們無需創(chuàng)建一個特殊用途的內(nèi)存分配程序來維護任務(wù)。與其他語言中類似的框架相比，這大大降低了實現(xiàn)FJTask所需的代碼的復(fù)雜性和代碼行。
deque的基本結(jié)構(gòu)采用了每個deque使用單個（盡管可調(diào)整大小）數(shù)組的通用方案，以及兩個索引：top索引就像基于數(shù)組的堆棧指針一樣，在push和pop時改變。 基本索引僅通過take修改。 由于FJTaskRunner操作都與deque的具體細節(jié)密切相關(guān)（例如，fork只是調(diào)用push），因此該數(shù)據(jù)結(jié)構(gòu)直接嵌入到類中，而不是被定義為單獨的組件。
由于deque數(shù)組由多個線程訪問，有時沒有完全同步(見下文)，但是不能將單個Java數(shù)組元素聲明為易失性，因此每個數(shù)組元素實際上是對維護單個易失性引用的小轉(zhuǎn)發(fā)對象的固定引用。這一決定最初是為了確保符合Java內(nèi)存規(guī)則，但結(jié)果卻是為了提高測試平臺上的性能而需要的間接級別，這大概是通過減少由于對附近元素的訪問而引起的緩存爭用，這些元素由于間接性而在內(nèi)存中分布得更多。
deque實現(xiàn)中的主要挑戰(zhàn)是圍繞同步及avoidance。即使在具有優(yōu)化的同步設(shè)備[2]的JVM上，也需要獲得鎖對于每次推送和彈出操作都成為瓶頸。然而，在Cilk[5]中采取的策略的改編提供了一種基于以下觀察結(jié)果的解決方案：
- push和pop操作僅由所有者線程調(diào)用。
- 對取操作的訪問可以很容易地通過“取”上的入口鎖一次僅限于一個竊取線程。(此deque鎖還用于在必要時禁用采取操作。)因此，將干擾控制簡化為兩方同步問題。
- 只有當deque即將變?yōu)榭諘r，pop和take操作才能進行干預(yù)。否則，它們將保證對數(shù)組中不相交的元素進行操作。
將top索引和base索引定義為volatile可確保如果deque肯定具有多個元素，則pop和take可以在不鎖定的情況下繼續(xù)進行。like算法完成的，在該算法中，push預(yù)減top：
if (--top >= base) ...
take預(yù)增top:
if (++base < top) ...
在每種情況下，他們必須通過比較兩個指數(shù)來檢查這是否會導(dǎo)致雙端隊列變空。在潛在沖突時使用非對稱規(guī)則：pop重新檢查狀態(tài)并嘗試在獲得deque鎖定后繼續(xù)（與take持有的相同），僅在deque確實為空時才退出。 take操作只是立即退出，通常然后試圖從另一個受害者竊取。 這種不對稱性與Cilk中使用的其他類似的THE協(xié)議的唯一顯著不同。
使用易失性索引還可以使推送操作在不同步的情況下進行，除非deque數(shù)組即將溢出，在這種情況下，它必須首先獲得deque鎖才能調(diào)整數(shù)組的大小。否則，只需確保topis只在deque陣列插槽被填充后才更新，就可以抑制任何take的干擾。
在初始實現(xiàn)之后，發(fā)現(xiàn)幾個JVM不符合Java內(nèi)存模型[6]規(guī)則，要求在寫入易失性字段對之后進行準確讀取。 作為一種解決方法，如果看起來有兩個或更少的元素，則調(diào)整彈出以在鎖定下重試的標準，并且take操作添加了輔助鎖以確保內(nèi)存屏障。 只要所有者線程（在此處保存用于在讀取易失性字段時保持正確的內(nèi)存順序的平臺）最多丟失一個索引更改，這就足夠了，并且僅導(dǎo)致性能的微小減速。
3.2 竊取和空閑
工作竊取框架中的工作線程對它們正在運行的程序的同步需求一無所知。他們只是generate，push，pop，take，管理狀態(tài)和執(zhí)行任務(wù)。當所有線程都有大量工作時，這種方案的簡單性可以實現(xiàn)高效執(zhí)行。However, this streamlining comes at the price of relying on heuristics when there is not enough work; i.e., during startup of a main task, upon its completion, and around global full-stop synchronization points employed in some fork/join algorithms.
這里的主要問題是當一個工作線程沒有本地任務(wù)而且不能從任何其他線程竊取一個時該怎么辦。 如果程序在專用的多處理器上運行，那么就可以依靠硬忙等待旋轉(zhuǎn)循環(huán)來嘗試竊取工作。 但是，即使在這里，嘗試竊取也會增加爭用，即使那些非空閑的線程也會減慢（由于3.1節(jié)中的鎖定協(xié)議）。 此外，在此框架的更典型的使用上下文中，操作系統(tǒng)應(yīng)該以某種方式確信嘗試運行其他不相關(guān)的可運行進程或線程。
在Java中實現(xiàn)這一目標的工具很薄弱，沒有任何保證(參見[6，7])，但在實踐中通常似乎是可以接受的(類似于Hood[3]所描述的技術(shù)也是如此)。無法從任何其他線程獲得工作的線程在嘗試其他搶斷之前會降低其優(yōu)先級，在嘗試之間執(zhí)行Thread.yield，并在其FJTaskRunnerGroup中注冊為非活動線程。如果所有其他人都變得不活躍，他們都會阻止等待額外的主要任務(wù)。否則，在給定數(shù)量的額外自旋之后，線程進入休眠階段，在那里他們睡眠(長達100 ms)，而不是在盜取嘗試之間屈服。這些強加的睡眠會導(dǎo)致程序的人為延遲，這些程序需要很長時間才能完成任務(wù)。但這似乎是最好的通用妥協(xié)?？蚣艿奈磥戆姹究赡軙峁╊~外的控制方法，以便程序員在影響性能時可以覆蓋默認值。
7. 參考
[1] Agesen, Ole, David Detlefs, and J. Eliot B. Moss. Garbage Collection and Local Variable Type-Precision and Liveness in Java Virtual Machines. In Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[2] Agesen, Ole, David Detlefs, Alex Garthwaite, Ross Knippel, Y.S. Ramakrishna, and Derek White. An Efficient Meta-lock for Implementing Ubiquitous Synchronization. In Proceedings of OOPSLA ’99, ACM, 1999.
[3] Arora, Nimar, Robert D. Blumofe, and C. Greg Plaxton. Thread Scheduling for Multiprogrammed Multiprocessors. In Proceedings of the Tenth Annual ACM Symposium on
Parallel Algorithms and Architectures (SPAA), Puerto Vallarta, Mexico, June 28 - July 2, 1998.
[4] Blumofe, Robert D. and Dionisios Papadopoulos. Hood: A User-Level Threads Library for Multiprogrammed Multiprocessors. Technical Report, University of Texas at
Austin, 1999.
[5] Frigo, Matteo, Charles Leiserson, and Keith Randall. The Implementation of the Cilk-5 Multithreaded Language. In Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[6] Gosling, James, Bill Joy, and Guy Steele. The Java Language Specification, Addison-Wesley, 1996.
[7] Lea, Doug. Concurrent Programming in Java, second edition, Addison-Wesley, 1999.
[8] Lowenthal, David K., Vincent W. Freeh, and Gregory R. Andrews. Efficient Fine-Grain Parallelism on Shared-Memory Machines. Concurrency-Practice and Experience,10,3:157-173, 1998.
[9] Simpson, David, and F. Warren Burton. Space efficient execution of deterministic parallel programs. IEEE Transactions on Software Engineering, December, 1999.
[10]Taura, Kenjiro, Kunio Tabata, and Akinori Yonezawa. "Stackthreads/MP: Integrating Futures into Calling Standards." In Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPoPP), 1999.
