「Java の理論と実践」シリーズの前回の記事では、Java 7 の java.util.concurrent パッケージに追加される予定のフォーク/ジョイン・ライブラリーについて調べました。フォーク/ジョインの手法を利用することで、広範な種類のハードウェアに対して、コードを変更することなく、効率的に実行できる形で分割統治法による並列アルゴリズムを容易に表現することができます。

プロセッサー数の増加に合わせ、利用可能なハードウェアを効率的に利用するためには、細粒度並列処理をプログラムの中で特定し、活用する必要があります。最近では、粒度の粗いタスク境界を選択する (例えば Web アプリケーションで 1 つのリクエストを処理するなど) ことにより、またスレッド・プールでタスクを実行することにより、満足できる程度にハードウェアを活用する十分なレベルの並列処理を実現できることが多くなっています。しかしそこにとどまらず、さらに掘り下げ、ハードウェアが常にビジー状態となるぐらいの並列処理を見つける必要があります。並列化するのに最適な処理の 1 つが、大規模なデータ・セットに対するソートと検索です。前回の記事で説明したように、大規模なデータ・セットに対するソートと検索という問題はフォーク/ジョインを使って容易に表現することができます。しかしこの問題は非常に一般的なため、これをもっと容易に行える、ParallelArray というクラス・ライブラリーが提供されています。

復習: フォーク/ジョインによる分割

フォーク/ジョインは分割統治法による手法を具体化しています。つまりこの手法では、問題を取り上げ、その問題を再帰的に副問題に分割していき、シーケンシャルに解決した方が効率的なほど副問題が十分小さくなるまで分割操作を続けます。この再帰ステップでは、問題を 2 つ以上の副問題に分割し、解を求めるために副問題をキューイングし (フォーク・ステップ)、副問題の結果が出るのを待機し (ジョイン・ステップ)、そして結果をマージします。こうしたアルゴリズムの一例がマージ・ソートです。これをリスト 1 に示しますが、ここではフォーク/ジョイン・ライブラリーを使っています。

                
public class MergeSort extends RecursiveAction {
    final int[] numbers;
    final int startPos, endPos;
    final int[] result;

    private void merge(MergeSort left, MergeSort right) {
        int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
        while (leftPos < leftSize && rightPos < rightSize)
            result[i++] = (left.result[leftPos] <= right.result[rightPos])
                    ? left.result[leftPos++]
                    : right.result[rightPos++];
        while (leftPos < leftSize)
            result[i++] = left.result[leftPos++];
        while (rightPos < rightSize)
            result[i++] = right.result[rightPos++];
    }

    public int size() {
        return endPos-startPos;
    }

    protected void compute() {
        if (size() < SEQUENTIAL_THRESHOLD) {
            System.arraycopy(numbers, startPos, result, 0, size());
            Arrays.sort(result, 0, size());
        }
        else {
            int midpoint = size() / 2;
            MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
            MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
            coInvoke(left, right);
            merge(left, right);
        }
    }
}

マージ・ソートはシーケンシャルに行うこともできるため、最初から並列アルゴリズムであるわけではありません。データ・セットが大きすぎてメモリーに入りきらず、部分に分けてソートする必要がある場合にマージ・ソートがよく使われます。マージ・ソートのパフォーマンスは最悪のケースでも平均的なケースでも O(n log n) です。しかし通常マージを実行する場合、クイック・ソートなどの一般的なソート・アルゴリズムと比べると、決められたメモリーの範囲内で実行することが難しいため、メモリーに対する要求も高くなっています。一方で、マージ・ソートは副問題のソートを並行して行えるため、クイック・ソートよりも並列化するには適しています。

プロセッサーの数は固定されているため、並列化を行っても O(n log n) の問題を O(n) の問題に変えることはできません。しかし問題が並列化しやすいものであればあるほど、並列化することによって合計実行時間を n_cpus分の1 近くまで削減することができます。合計実行時間を削減できるということは、(並行して処理を行うことで使用される合計 CPU サイクルの方がシーケンシャル処理の場合より多いとしても) ユーザーにとっては結果をより早く得られるということを意味します。

フォーク/ジョインの方法を使うことによる主なメリットは、移植しやすい形で並列実行のアルゴリズムをコーディングできることです。プログラマーは、作成しているプログラムがデプロイされたときに CPU がいくつ使用できるかを気にする必要はなく、利用可能なワーカー全体に渡ってランタイムが作業をうまく配分してくれるため、さまざまな種類のハードウェアに対して適切な結果を得ることができます。

細粒度の並列処理

主要なサーバー・アプリケーションにおいて細粒度並列処理が最も多く行われるのが、データ・セットのソート、検索、選択、そして集計 (これらは sort、search、selection、summarize といずれも s で始まっています) です。これらの問題は、どれも分割統治法を使って容易に並列処理することができ、またフォーク/ジョインのタスクとして容易に表現することができます。例えば大規模なデータ・セットの平均を取る処理を並列化する場合には、(マージ・ソートで行ったように) そのデータ・セットを小さなデータ・セットに再帰的に分割してサブセットの平均を取り、それを合成するステップでは単純にサブセットの平均の加重平均を計算します。

ParallelArray

フォーク/ジョイン・ライブラリーには、ソートと検索の問題に関してデータ・セットに対して行われる演算で、並列化することが可能な演算をもっと容易に表現するための方法が用意されています。それが ParallelArray クラスです。その概念としては、ParallelArray は構造的に類似したデータ項目のコレクションを表しており、そのデータの分割方法を記述するために ParallelArray のメソッドが使われます。そしてその記述を使って実際の配列操作 (実は裏でフォーク/ジョインのフレームワークが使われています) を並行して実行します。この方法では、データの選択や変換、後処理の操作を宣言型で指定することができ、また適切な並列実行計画をフレームワークに作成させられる、という効果があります。これはちょうど、データベース・システムではデータ操作を SQL で指定することができ、どのように操作を実装しているのか、その方法を隠せるのと似ています。ParallelArray の実装には、(オブジェクトの配列やさまざまな基本型の配列など) さまざまなデータ型やデータ・サイズに応じて、いくつかの種類があります。

リスト 2 は ParallelArray を使って生徒の成績を集計する例であり、選択、予測、そして集計の基本演算を示しています。Student クラスは生徒に関する情報 (名前、卒業年、GPA (訳注: Grade Point Average の略で、学生を評価するために成績をポイントに換算した平均値のこと。欧米で一般的に使われている。)) を含んでいます。ヘルパー・オブジェクト isSenior は今年卒業する生徒のみを選択するために使われ、またヘルパー・オブジェクト getGpa は指定された生徒の GPA フィールドを抽出します。リストの先頭にある式によって、生徒の集まりを表す ParallelArray が作成され、その ParallelArray を使って今年卒業する生徒の GPA の中から最高の GPA を選択します。

                
ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data);
double bestGpa = students.withFilter(isSenior)
                         .withMapping(selectGpa)
                         .max();

public class Student {
    String name;
    int graduationYear;
    double gpa;
}

static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() {
    public boolean op(Student s) {
        return s.graduationYear == Student.THIS_YEAR;
    }
};

static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() {
    public double op(Student student) {
        return student.gpa;
    }
};

並列配列に対する操作を表現するコードは見掛け倒しで、withFilter() メソッドと withMapping() メソッドは、実際にデータを検索したり変換したりするわけではなく、単に「クエリー」のパラメーターを設定しているにすぎません。実際の作業は最後のステップ (この場合は max() への呼び出し) で行われます。

ParallelArray でサポートされている基本的な操作は次のとおりです。

• フィルタリング: 計算に含まれる要素群のサブセットを選択します。リスト 2 では、フィルターは withFilter() メソッドによって指定されています。
  
  
• 適用: 選択された各要素に対して 1 つの手続きを適用します。リスト 2 にはこの手法は示されていませんが、apply() メソッドを利用することで、選択された各要素に対して 1 つのアクションを実行することができます。
  
  
• マッピング: 選択された要素群を別の形式に変換します (例えば要素からデータ・フィールドを抽出する、など)。この変換は withMapping() メソッドの例の中で行われています (このメソッドでは Student をその生徒の GPA に変換しています)。その結果は、指定された選択とマッピングの結果から成る ParallelArray です。
  
  
• 置き換え: 各要素を、その要素から派生した別の要素で置き換え、新しい並列配列を作成します。この手法はマッピングと似ていますが、新しい ParallelArray が作成される点が異なり、この新しい ParallelArray に対してさらにクエリーを実行することができます。置き換えの 1 つのケースがソートです。ソートでは、結果として作成される配列がソート順となるように、要素群は異なる要素群で置き換えられます (組み込みの sort() メソッドは、この動作のために用意されています)。もう 1 つの特別なケースが cumulate() メソッドです。cumulate() メソッドは、指定された操作の組み合わせに従って各要素を実行中の累積結果で置き換えます。置き換えは複数の ParallelArray を合成する場合にも使われます (例えば、並列配列 a と b の a[i]+b[i] という値が要素であるような ParallelArrays を作成する場合など)。
  
  
• 集計: すべての値を合成して 1 つの値にします (例えば合計や平均、最小値、最大値の計算など)。リスト 2 の例は max() メソッドを使っています。事前定義された集計メソッド (例えば min()、sum()、max() など) は、より汎用の reduce() メソッドを使って作られています。

一般的な集計演算

リスト 2 では、すべての生徒の GPA の中で最高の GPA を計算する方法を詳細に示すことができました。しかし通常必要な情報は、それとは少し異なり、どの生徒が最高の GPA を持っているのかという情報です。それを計算するためには 2 つの演算を使います (つまり 1 つの演算では最高の GPA を計算し、もう 1 つの演算でその GPA を持つ生徒を選択します)。しかし ParallelArray には、一般的に必要とされる簡単な統計情報 (最大値、最小値、合計、平均、そして最大要素と最小要素のインデックスなど) を容易に得るための方法が用意されています。summary() メソッドは、こうした簡単な統計情報を 1 つの並列演算で計算します。

リスト 3 は簡単な統計情報の計算をする summary() メソッドを示しています。ここには最小要素と最大要素のインデックスが含まれており、データに対して複数パスを作らずにすむようになっています。

                
SummaryStatistics summary = students.withFilter(isSenior)
                            .withMapping(selectGpa)
                            .summary();
System.out.println("Worst student: " + students.get(summary.minIndex()).name;
System.out.println("Average GPA: " + summary.getAverage();

制約

ParallelArray はメモリー内データベースの汎用操作で使われることを目的としているのではなく、また (.NET 3.0 の機能である統合言語クエリー、LinQ のような) データの変換や抽出を指定するための汎用の機構で使われることを目的としているわけでもありません。ParallelArray が目的としているのは、特定の範囲のデータの選択操作や変換操作を単純に表現することで、そうした操作を容易かつ自動的に並列化できるようにすることだけです。そのため、ParallelArray にはいくつかの制限があります。例えば、フィルター操作はマッピング操作の前に指定する必要があります。(複数のフィルター操作は許可されていますが、多くの場合はそれらの操作を 1 つの複合フィルター操作にまとめた方が効率的です。) ParallelArray の主な目的は、開発者が作業を並列化する方法を考えずにすむようにすることです。もし、ParallelArray が提供している操作を利用して変換を表現できるなら、適切なレベルの並列化を労せず実現することができます。

パフォーマンス

私は ParallelArray の効果を評価するために、さまざまなサイズの配列とフォーク/ジョイン・プールに対してクエリーを実行する、単純で非科学的なプログラムを作成しました。この結果は Windows を実行する Core 2 Quad システムで実行した場合のものです。表 1 は、ベース・ケース (生徒 1000、スレッド 1 ) と比較して、どの程度高速化されたかを示しています。

結果は (GC 動作など、いくつかの要因に影響されているため) 一目瞭然というわけにはいきませんが、利用可能なコア数とプール・サイズが等しいときに最高の結果が実現されている (これは、このタスクが完全に計算のみであることから当然想定されることです) ことがわかるだけではなく、1 つのコアの場合と比較して 4 つのコアの場合に 2 倍から 3 倍の高速化を実現できていることもわかります。これは、チューニングを必要としない上位レベルで移植可能な仕組みを利用して、十分なレベルの並列処理を実現できることを示しています。

クロージャーとの関係

ParallelArray はデータ・セットに対するフィルタリングや処理、集約操作を宣言型で指定するための便利な方法である一方、自動的な並列化を促進してくれます。しかし ParallelArray の構文は、フォーク/ジョイン・ライブラリーをそのまま使う場合よりも表現しやすいとはいえ、やはり少し面倒です。つまり各フィルターやマッパー、リデューサーは通常は内部クラスとして指定されるため、例えば「今年卒業する全生徒の GPA の中で最高の GPA を見つける」といった単純なクエリーでさえ、コードは十数行の規模になります。Java 7 で Java 言語に追加される可能性のある機能の 1 つがクロージャーです。クロージャーを支持する理由の 1 つとして、小さなコード・スニペット (例えば ParallelArray のフィルターやマッパー、リデューサーなど) をずっとコンパクトに表現できることが挙げられています。

リスト 4 は、最大の GPA を見つけるクエリーを BGGA クロージャーに関する提案を利用して書き直したものです。(関数型を使って継承した ParallelArray のバージョンでは、withFilter() のパラメーターの型は Ops.Predicate<T> ではなく関数型 { T => boolean } です。) クロージャーによる記法では内部クラスに関連する定型的な記述が省略され、必要なデータ操作を、より簡潔に (そしてもっと重要な点として、より直接的に) 表現することができます。今やコードはたった 3 行になり、そのほとんどすべてが、ここで実現しようとしている結果の重要な側面を表現しています。

                
double bestGpa = students.withFilter({Student s => (s.graduationYear == THIS_YEAR) })
                         .withMapping({ Student s => s.gpa })
                         .max();

まとめ

利用可能なプロセッサーの数が増加するにつれ、プログラムの中で、より細粒度の並列処理を行える部分を見つける必要が出てきます。その最も魅力的な候補のひとつが、データの集約操作 (ソート、検索、そして集計) です。JDK 7 に導入される予定のフォーク/ジョイン・ライブラリーには、並列化が可能なある種類のアルゴリズムを「移植可能な形式で表現する」方法が用意されており、それを利用することで、さまざまなハードウェア・プラットフォームで効率的にプログラムを実行することができます。フォーク/ジョイン・ライブラリーの中にある ParallelArray コンポーネントを利用すると、実行したい操作を宣言型で記述することで、またその操作の効率的な実行方法を ParallelArray に判断させることで、並列の集約操作をさらに容易に表現することができます。

参考文献

学ぶために

• 「Java の理論と実践: フォークを活用する、第 1 回」(developerWorks、2007年11月) は、さまざまなアルゴリズムを分解し、ハードウェアによる並列処理を効果的に利用する上で、フォーク/ジョインがいかに自然な機構であるかを解説しています。
  
  
• 『Concurrent Programming in Java』(Doug Lea 著、1999年11月 Prentice Hall PTR 刊) の第 4.4章では、並列分割が詳細に説明されています。
  
  
• 並行性の話題を取り上げた Doug Lea の Web サイトでは、jsr166y パッケージの一部としてフォーク/ジョインのフレームワークをダウンロードすることができます。またこのサイトでは、このフレームワークの設計に関する論文を読むことができます。
  
  
• Technology bookstore には、この記事や他の技術的な話題に関する本が豊富に取り揃えられています。
  
  
• developerWorks の Java technology ゾーンには、Java プログラミングのあらゆる側面を網羅した記事が豊富に用意されています。
  
  

議論するために

• developerWorks blogs からdeveloperWorks のコミュニティーに加わってください。
  
  

著者について

Brian Goetz はこれまで 20 年間、プロのソフトウェア開発者として活躍してきました。現在は Sun Microsystems のシニア・スタッフ・エンジニアであり、複数の JCP Expert Group の一員でもあります。2006年5月に Addison-Wesley から彼の著書『Java 並行処理プログラミング ― その「基盤」と「最新 API」を究める ―』が出版されています。人気の業界紙に掲載された、Brian のこれまでの記事、そして今後の記事を参照してください。

この記事を評価する

コメント

上に戻る

目次

• 復習: フォーク/ジョインによる分割
• 細粒度の並列処理
• パフォーマンス
• クロージャーとの関係
• まとめ
• 参考文献
• 著者について
• コメント