The Java TutorialsのFork/Joinのところをテキトーに読んで訳した。さすがに本格的なことは書いてないんで、まぁふーんって感じ。
Fork/Join
fork/joinフレームワークは、マルチプロセッサの利点を生かすためのExecutorService
インタフェースの実装です。再帰的に小さな断片に分割して動作するように設計されています。その目的は、アプリケーションのパフォーマンスを向上させるために、すべての利用可能なプロセッサの能力を使うことです。
どのExecutorService
実装を使うとしても、fork/joinフレームワークはスレッドプールのワーカスレッドにタスクを分配します。fork/joinフレームワークはwork-stealingアルゴリズムを使用するので、独立しています。やることがなくなったワーカースレッドはビジー状態の他スレッドからタスクをスチール*1できます。
fork/joinフレームワークのコアクラスはForkJoinPoolで、AbstractExecutorService
クラスを拡張しています。ForkJoinPool
は核となるwork-stealingアルゴリズムを実装し、ForkJoinTaskプロセスを実行可能です。
Basic Use
fork/joinフレームワークを使用するための最初のステップは、ある問題のセグメントを処理するコードを書くことです。以下の疑似コードのようになるべきです。
if (ある問題の部分が十分に小さい) 問題を直接解く else 問題を二つの断片に分割する 二つの断片を実行して結果を待機する
ForkJoinTask
サブクラスである、RecursiveTask(結果を返すことが可能)かRecursiveActionのどちらかを一般的には使用して、この疑似コードをラップします。
ForkJoinTask
サブクラスが用意できたら、実行すべきすべての問題を表現するオブジェクトを生成し、ForkJoinPool
インスタンスのinvoke()
メソッドに渡します。
Blurring for Clarity
fork/joinフレームワークがどのように動作するのかの理解を助けるために、以下の例を考えてみます。いま、ぼかし画像を作ろうとしている、と仮定します。元画像は整数の配列によって表現されており、各整数は単一ピクセルの色値です。また、ぼかしを入れた先の画像も元画像と同一サイズの整数配列によって表現されます。
元画像の配列を一度に一ピクセル処理することでぼかし作業は完了します。各ピクセルは周囲のピクセルの平均値で、その結果を変換先の配列に配置します。画像は巨大な配列なので、この処理は長時間かかる可能性があります。fork/joinフレームワークを使用するアルゴリズムを実装するためのマルチプロセッサーのシステムでコンカレント処理の利点を生かすことができます。
public class ForkBlur extends RecursiveAction { private int[] mSource; private int mStart; private int mLength; private int[] mDestination; // Processing window size; should be odd. private int mBlurWidth = 15; public ForkBlur(int[] src, int start, int length, int[] dst) { mSource = src; mStart = start; mLength = length; mDestination = dst; } protected void computeDirectly() { int sidePixels = (mBlurWidth - 1) / 2; for (int index = mStart; index < mStart + mLength; index++) { // Calculate average. float rt = 0, gt = 0, bt = 0; for (int mi = -sidePixels; mi <= sidePixels; mi++) { int mindex = Math.min(Math.max(mi + index, 0), mSource.length - 1); int pixel = mSource[mindex]; rt += (float)((pixel & 0x00ff0000) >> 16) / mBlurWidth; gt += (float)((pixel & 0x0000ff00) >> 8) / mBlurWidth; bt += (float)((pixel & 0x000000ff) >> 0) / mBlurWidth; } // Reassemble destination pixel. int dpixel = (0xff000000 ) | (((int)rt) << 16) | (((int)gt) << 8) | (((int)bt) << 0); mDestination[index] = dpixel; } } ...
まず、compute()
抽象メソッドを実装し、これはぼかし作業か二つの小タスクへの分割か、どちらかを実行します。作業を実行するか分割するかは、単純に配列長としきい値が決定します。
protected static int sThreshold = 100000; protected void compute() { if (mLength < sThreshold) { computeDirectly(); return; } int split = mLength / 2; invokeAll(new ForkBlur(mSource, mStart, split, mDestination), new ForkBlur(mSource, mStart + split, mLength - split, mDestination)); }
RecursiveAction
のサブクラスを使用する場合、ForkJoinPool
で実行するためのタスクのセットアップは簡単で、以下のステップの通りです。
1. 実行すべき全作業を表現するタスクを生成。
// src に変換元画像のイメージのピクセル // dst に変換先画像のイメージのピクセル ForkBlur fb = new ForkBlur(src, 0, src.length, dst);
2. タスクを実行するForkJoinPool
を生成。
ForkJoinPool pool = new ForkJoinPool();
3. タスクの実行。
pool.invoke(fb);
ソースコード全体には、変換先イメージファイルを生成するその他のコードも含まれており、詳細はForkBlurを参照してください。
Standard Implementations
マルチプロセッサシステムでコンカレントに実行するタスクのためにカスタムアルゴリズム(前のセクションのForkBlur.java
など)を実装するfork/joinフレームワークの使用法に加えて、Java SEにはfork/joinフレームワークを使用して実装されている一般的で有用な機能があります。Java SE 8で導入されたそうした実装の一つが、java.util.ArraysのparallelSort()
メソッドで使用されています。これらのメソッドはsort
に似ていますが、fork/joinフレームワークを使用してコンカレントの利点を取り入れています。マルチプロセッサシステムで実行するとき、大規模配列のパラレルソートはシーケンシャルソートよりも高速です。しかし、fork/joinフレームワークがどのようにそれらのメソッドで活用されているかについてはJava Tutorialsの範囲外です。詳細な情報についてはJava APIドキュメントを参照してください。
fork/joinフレームワークのその他の実装はJava SE 8でリリース予定のProject Lambdaの一部であるjava.util.streams
パッケージのメソッドで使用されています。詳細な情報についてはLambda Expressionsを参照してください。