GPars(5):Fork-Join
2166 ワード
Fork/joinは主に問題の分解処理に用いられ,分けて治める.
Fork/joinアルゴリズムは問題を複数の小さなサブ問題に分割し,各サブ問題に対して同じアルゴリズムを用い,サブ問題が十分に小さい場合,問題を直接解決することができる.すべてのサブ問題が解決し、親問題も解決された.
JSR-166 yクラスライブラリはFork/joinのサポートはかなり良いですが、注意しないとトラブルに遭遇する問題があります.また、threads、pools、synchronization barriers(同歩障壁)も自分で処理しなければならない.GParsはこれらのものを隠して、Fork/joinを使ってもっと便利になります.次の例は、指定したディレクトリとそのサブディレクトリのファイル数を統計するアルゴリズムです.
前の例ではParallelizer.orchestrate()メソッドは、渡されたAbstractForkJoinWorkerタイプのパラメータ(ルートタスク)に基づいてForkJoinOrchestratorを作成し、AbstractForkJoinWorkerを実行し、結果が戻るのを待つ.childrenResultsはAbstractForkJoinWorkerのプロパティで、サブタスクの結果が返されるのを待っています.戻り値はListタイプです.
Fork/Joinオペレーションがいくつかの小さなスレッドで安全に実行できるのは、内部TaskBarrierクラスによるスレッドの同期のおかげです.アルゴリズム内のスレッドがブロックされてサブ問題が完了するのを待つと、タスクキュー内の他の実行可能なサブ問題に使用するためにプールに返されます.アルゴリズムは、サブディレクトリが多いため、多くのタスクを作成し、サブディレクトリタスクの完了を待つ必要がありますが、少なくとも1つのスレッドで演算を維持するのに十分です.
GParsガイドには比較的複雑なMergesortの例も示されており,興味のある読者は参考にすることができる.
このシリーズのその他の記事: GPars(1):入門 GPars(2):同時集合のParallelizer GPars(3):同時集合のMap-Reduce GPars(4):Asynchronizer
Fork/joinアルゴリズムは問題を複数の小さなサブ問題に分割し,各サブ問題に対して同じアルゴリズムを用い,サブ問題が十分に小さい場合,問題を直接解決することができる.すべてのサブ問題が解決し、親問題も解決された.
JSR-166 yクラスライブラリはFork/joinのサポートはかなり良いですが、注意しないとトラブルに遭遇する問題があります.また、threads、pools、synchronization barriers(同歩障壁)も自分で処理しなければならない.GParsはこれらのものを隠して、Fork/joinを使ってもっと便利になります.次の例は、指定したディレクトリとそのサブディレクトリのファイル数を統計するアルゴリズムです.
import groovyx.gpars.AbstractForkJoinWorker
import static groovyx.gpars.Parallelizer.*
public final class FileCounter extends AbstractForkJoinWorker
{
private final File file;
def FileCounter(final File file) {
this.file = file
}
protected void compute() {
long count = 0;
file.eachFile {
if (it.isDirectory()) {
println "Forking a thread for $it"
//fork
forkOffChild(new FileCounter(it))
} else {
count++
}
}
//
setResult(count + ((childrenResults)?.sum() ?: 0))
}
}
doParallel(1) { pool -> //1
println """Number of files:
${orchestrate(
new FileCounter(
new File("... ...")
)
)}"""
}
前の例ではParallelizer.orchestrate()メソッドは、渡されたAbstractForkJoinWorkerタイプのパラメータ(ルートタスク)に基づいてForkJoinOrchestratorを作成し、AbstractForkJoinWorkerを実行し、結果が戻るのを待つ.childrenResultsはAbstractForkJoinWorkerのプロパティで、サブタスクの結果が返されるのを待っています.戻り値はListタイプです.
Fork/Joinオペレーションがいくつかの小さなスレッドで安全に実行できるのは、内部TaskBarrierクラスによるスレッドの同期のおかげです.アルゴリズム内のスレッドがブロックされてサブ問題が完了するのを待つと、タスクキュー内の他の実行可能なサブ問題に使用するためにプールに返されます.アルゴリズムは、サブディレクトリが多いため、多くのタスクを作成し、サブディレクトリタスクの完了を待つ必要がありますが、少なくとも1つのスレッドで演算を維持するのに十分です.
GParsガイドには比較的複雑なMergesortの例も示されており,興味のある読者は参考にすることができる.
このシリーズのその他の記事: