14

これは、今日の別の質問に対する回答の「副作用」として現れました。それは実際の問題よりも好奇心に関するものです。

Java SE 7は、Oracleが「フォーク/結合フレームワーク」と呼ぶものを提供します。これは、複数のプロセッサに作業をスケジュールするためのおそらく優れた方法です。それがどのように機能するかは理解していますが、それがどこで優れているのか、そして仕事を盗むことについての主張は理解できません。

たぶん、他の誰かが、なぜこのアプローチが望ましいのかについてより多くの洞察を持っているでしょう（それが派手な名前を持っているという理由以外で）。

fork / joinの基礎となるプリミティブはForkJoinTasksであり、これはFuturesであり、作業をすぐに実行するという考え方です[原文のまま]（「すぐに」という表現は、メインスレッドで同期的に発生することを意味するため、誤解を招く可能性があります。実際には、これは内部で発生します。 a Future）特定のしきい値を下回るか、しきい値に達するまで作業を2つのタスクに再帰的に分割します。

未来とは、不透明で不特定の方法で非同期的に実行されるタスクをオブジェクトにカプセル化するという概念です。結果が利用可能かどうかを確認できる関数があり、結果を（待機して）取得できる関数があります。
厳密に言えば、futureが非同期で実行されるかどうかさえわかりません。それは、内部で実行される可能性get()があります。理論的には、実装は将来ごとにスレッドを生成したり、スレッドプールを使用したりすることもできます。
実際には、Javaは、スレッドプールが接続されたタスクキューにタスクとしてfuturesを実装します（同じことがフォーク/ジョインフレームワーク全体にも当てはまります）。

フォーク/結合のドキュメントには、この具体的な使用例が示されています。

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));
}

これにより、Mergesortがタスクをトラバースする方法と同じ方法で、基になるスレッドプールのタスクキューにタスクが送信されます（再帰のおかげで）。
たとえば、処理する32個の「アイテム」の配列があり、しきい値が4で、均等に分割すると、それぞれ4個の「アイテム」を持つ8つのタスクが生成され、次のようになります。

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                                               .
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                       .                       .                       .
00 01 02 03 04 05 06 07|08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23|24 25 26 27 28 29 30 31
           .           .           .           .           .           .           .
00 01 02 03|04 05 06 07|08 09 10 11|12 13 14 15|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31
------------------------------------------------------------------------------------------------
     1     |     2     |     3     |     4     |     5     |     6     |     7     |     8     |

シングルコアプロセッサでは、これによりタスクグループ1-2-3-4-5-6-7-8が順番に送信/実行されます（非常に複雑な方法で）。
デュアルコアプロセッサでは、これは（1,3）-（2,4）-（5,7）-（6,8） [1]を送信/実行します。
クアッドコアプロセッサでは、これは（1,3,5,7）-（2,4,6,8）を送信/実行します。

それに比べて、優れた魔法がすべてない単純な実装では、タスク1-2-3-4-5-6-7-8をすぐにタスクキューに送信するだけです。いつも。

シングルコアプロセッサでは、これは1-2-3-4-5-6-7-8を送信/実行します。
デュアルコアプロセッサでは、これは（1,2）-（3,4）-（5,6）-（7,8）を送信/実行します。
クアッドコアプロセッサでは、これは（1,2,3,4）-（5,6,7,8）を送信/実行します。

質問：

  1. sThresholdの連続するアイテムを1つのタスクに詰め込み、スレッドプールのタスクキューに次々にタスクを送信する代わりに、ツリーのような再帰階層が生成されます。これには、実際には何も行わないN個のサブタスクのN + log2（N）オブジェクトの構築、参照、および破棄が含まれます。なぜこれが優れているのですか？

  2. 参照の局所性は保持されません。プロセッサキャッシュも仮想メモリも、そのように扱われるようなものではありません。なぜこれが優れているのですか？

  3. ユニプロセッサシステムを除いて、タスクは元の順序に近い順序でスケジュールされないことが保証されています。それが本当に問題でなければ、これは問題ではないかもしれませんが、それは例えば柵や障壁のようなものをかなり実行不可能にします。フェンスのようなものを作成する唯一の方法は、ルートオブジェクトが完了するのを待ってから、新しいタスクを送信することだけです。これは、完全なパイプラインストールに相当します（これはまさにあなたが決して起こりたくないことです）。

  4. Oracleのドキュメントによると、このアプローチは作業の盗用を実装しているため、スレッドプールよりも優れています。私はこれが起こっているのを見ていません。私が見ることができるのは、単純な通常のスレッドプールにタスクを送信する非常に複雑な方法です。これはどのように魔法のように仕事を盗むことを実装することになっていますか？

[1]複雑にしすぎないようにし、ワーカースレッドが互いに追い越さないことを前提としましょう。タスクはすべて、処理に同じ時間がかかります。そうしないと、送信は同じですが、実行はもちろん異なる順序で発生する可能性があります。

4

2 に答える 2

9

を使用するExecutorService 場合、スレッドプールに含めるスレッドの数を決定します。スケジュールするタスクと、これらのタスクが作成するサブタスクの間に、ある種の区別はありません。
ForkJoinPool代わりに、クラスは1）使用可能なプロセッサと2）タスクの要求に基づいてスレッドを管理します。
この場合、アクティブなタスクによって作成されたサブタスクは、外部タスクとは異なる方法でスケジュールされています。
通常、アプリケーション全体に対して1つのフォーク結合プールがあり（ExecutorService重要なアプリケーションで1つ以上あるのが一般的である場合とは異なり）、の必要はありませんshutdown。私はあなたにもっと低レベルの説明を与えるために内部をレビューしていませんが、あなたがここ
を見れば約束された並列処理を表示する測定値を示すプレゼンテーションとベンチマークがあります。

更新：
このフレームワークは、特定の種類の問題に対処します（ExecutorServiceCPUとI / Oアクティビティが混在するタスクに適しています）。
ここでの基本的な考え方は、CPUを常にビジー状態に保つために、再帰/分割統治アプローチを使用することです。アイデアは、新しいタスクを作成し（フォーク）、新しいタスクが完了するまで（参加する）現在のタスクを一時停止しますが、新しいスレッドを作成せず、共有ワークキューを持たないことです。
そのため、フォーク結合フレームワークは、限られた数のワーカースレッド（コアと同じ数）を作成することにより、ワークスティーリングを使用して実装されます。各ワーカースレッドは、プライベートの両端のワークキューを維持します。
フォークするとき、ワーカーはその両端キューの先頭で新しいタスクをプッシュします。待機中またはアイドル状態の場合、ワーカーはタスクを両端キューの先頭からポップし、スリープする代わりに実行します。
ワーカーの両端キューが空の場合、ランダムに選択された別のワーカーの両端キューの末尾から要素を盗みます。Javaでのデータ並列処理を読み、確信を持てるようにいくつかのベンチマークを自分で行うこと
をお勧めします。理論はある程度までしか有効ではありません。その後、測定を行って、パフォーマンスが大幅に向上しているかどうかを確認します

于 2012-08-31T16:21:14.043 に答える
2

フレームワークを批判する記事[はい、私はそれを書きました]から始めましょう。Javaフォーク-災害に参加

今あなたの質問に：

  1. そうではありません。フレームワークはDAGを処理しようとしています。それが設計構造です。

  2. そうではありません。記事で言及されているように、Javaアプリケーションはキャッシュやメモリなどについて何も知らないため、仮定は誤りです。

  3. はい。それがまさに起こることです。ストールは非常に一般的であるため、フレームワークは動き続けるために「継続スレッド」を作成する必要があります。この記事では、700を超える継続スレッドが必要な質問について説明しています。

  4. 私は確かにコードが複雑であることに同意します。スキャッターギャザーは、アプリケーションのワークスティーリングよりもはるかにうまく機能します。ドキュメントに関しては、どのようなドキュメントですか？Oracleからの詳細はありません。フレームワークを使用するためのすべてのプッシュ。

選択肢があります。

于 2012-08-31T17:45:56.420 に答える