以下は JE2BWM ほかが作成した翻訳です。原文は University of California より GFDL で配付されており、この翻訳も GFDL に従います。
原文: Locality scheduling (翻訳対象の更新日付は 10:21 PM UTC, April 16 2007 です)。

局所性スケジューリング

局所性スケジューリング（locality scheduling）は以下のような特徴のプロジェクトを想定しています。

個々のワークユニットは大きな入力ファイルを使う。 (その他に小さなファイルも使うかもしれません。 )
大きなファイルのそれぞれが、多数のワークユニットで用いられます。

局所性スケジューリングの目標は、計算機に転送するデータ量を最小化することです。仕事をある計算機に送るとき、この[機能をそなえた] スケジューラは、その計算機がすでに持っている入力ファイルを使うリザルトを送ろうとします。

局所性スケジューリングを使うプロジェクトは、下記の用意をしなければなりません。

ワークユニットの名前は、FILENAME__* という形をしていなければなりません。ここで、 FILENAME の部分は、そのワークユニットが使おうとしている大きな入力ファイルの名前です。この名前には、'__' ^訳注1 を含ませることはできません。
大きな入力ファイルそれぞれについての <file_info> 要素は、下記のタグを含まねばなりません。
```
   <sticky/>
   <report_on_rpc/>
```
config.xml ファイルには、
```
<locality_scheduling/>
```
を含めておかねばなりません。

局所性スケジューリングは以下のように動作します:

クライアントの計算機に大きなファイルがあれば、スケジューラ RPC [要求] のそれぞれに、そのファイルの一覧目録が含まれます。
[この RPC 要求を受けとった] スケジューラは、その計算機にすでにあるファイルを使うリザルトを選んで送ろうと試みます。ファイル選択時の検索順番は、無作為に非決定論的に行われます。
その計算機にあるファイルのそれぞれについて、送ることのできるリザルトが[スケジューラ側に] ないときは、スケジューラはホストにそのファイルを削除するように指示します。

以下のように指定すれば、ファイル名の昇順に決定論的な探索をさせることができます。

<locality_scheduling_sorted_order/>

オン・デマンドでの仕事生成

この仕組みを局所性スケジューリングと組合わせて使うと、プロジェクトは前もって仕事を用意しておくのではなく、スケジューラの要求に応じてその場で仕事を生成することができます。この仕組みは、config.xml ファイルの中の以下の要素で制御することができます。

<locality_scheduling_wait_period> N </locality_scheduling_wait_period>

ここで、N は秒単位の指定です。

X という名前のファイルを持っている計算機が仕事を欲しがったとき、その X を使う適切な仕事がなければ、スケジューラは下記の「トリガーファイル」を作ります。

PROJECT_ROOT/locality_scheduling/need_work/X

そこで、スケジューラは N 秒待ってから、その計算機に送出するのに適切な未送出のリザルトないかどうか、もう一度だけ調べてみます。

この仕組みを使うプロジェクトは、前述の need_work ディレクトリを走査する「on-demand work generator」デーモンのプログラムを用意しなければなりません。このデーモンはトリガーファイルを見つけると、それに対応した追加のワークユニットを生成し、トランジショナーがそれらのワークユニットに対応するリザルトを作ります。指定値 N 秒のうちに、上記の仕事がほとんどの場合完了するように N を選んで下さい。 (10 秒はそこそこ良い当て推量でしょう)。

この仕事生成のデーモン(work generator)は、仕事を生成したら、処理を起動したトリガーファイルを消す必要があります。

さらに、この仕事生成のデーモン（あるいは他のプロジェクトのデーモン）が、ファイル X についてはワークユニットをもう作成できないと判断したら、下記のまた別のトリガーファイルを作ることができます。

PROJECT_ROOT/locality_scheduling/no_work_available/X

スケジューラはこの種のトリガーファイルを見つけると、プロジェクトがファイル X について追加の仕事は作れないことが分かるので、前述の「トリガーファイル作成、待機、再度未送出リザルトを検索」という手順を省略します。もちろん、スケジューラは一回めの検索を依然として実施しますから、トランジショナーが既存の（古い）ワークユニットについて新しいリザルトを作った場合でも、それらは拾い上げられるようになっています。

実装上の注記

仕事は下記の階層構造をもっています。

File -> workunit -> result

ここで、N 台の計算機が稼働しているとして、target_nresults=M であるとします。理想的な状況なら、M 台の計算機にそれぞれのファイルを送り、そのファイルを使うリザルトすべてを4台の計算機にやらせたいところです。

もし、one_result_per_user_per_wu の規則を有効にしている場合であると、ファイルに対応する仕事があっても、それを送付するのに、特定の参加者を「除外」しなければならない場合もあります。

ファイルを持たない計算機への仕事の割り当ては以下のようにします。

N/M 個のファイルをワーキングセットとして維持管理します。
ファイルを保持していない計算機から仕事を求められたら、上記のワーキング・セットから、一様なやりかたで(無作為または順番に従って）ファイル F を選びます。
もし F がその計算機を持つ参加者では除外するべきものであったら、上記のワーキング・セットを考慮しない確定的なアルゴリズムで、ファイルを選びます。（一般的に言うと、群がり現象を避けるためにこうしたくはないのですが)。
^訳注3

このワーキング・セットは下記のディレクトリで表現します。

PROJECT/locality_scheduling/file_working_set/

その中には、ワーキング・セットに含むファイルの名前が入っています。プロジェクト固有の「working set manager」デーモンが、この内容を維持管理する責任を負います。

プロジェクトのスケジューラが、あるファイルに対応する未送出のリザルトがないと気がつくと、そのファイルと同じ名前で下記のディレクトリにファイルを作ります。

PROJECT/sched_locality/files_no_work/

プロジェクトの「working set manager」はこのディレクトリを監視して、出現した名前に対応するファイルをワーキング・セットから取り除かねばなりません。
注意：BOINC は、このようにして除外されたファイルについても、追加のリザルトを生成することがあります。ですから、ワーキング・セットに戻すことが必要になることもあり得ます。

ファイル F を持つ計算機に仕事を割り当てるには、

ファイル F に対応するリザルトをさらに送ります。これを効率的に行うために、以下の不変式を維持します：
^訳注4 与えられた、参加者/ファイルの対について、ID が増加する順にリザルトを送出します。

プロジェクトによっては、仕事を徐々に生成したいことがあります。そのようなときは、下記のディレクトリを定期的に監視して、そこに登場したファイル名に対して仕事を生成するような「work generator」デーモンを用意すれば良いのです。

PROJECT/locality_scheduling/need_work/

上記の仕組みを働かせるためには、 <locality_scheduling_wait_period> 要素を config.xml ファイルに追加してください。これをみてスケジューラは、仕事が［その場で］生成されて現れるまで待つ時間の上限を知ります。

注意：すべてのリザルトについて、同一のプラットフォーム集合内で［計算が可能な］アプリケーションの版があると仮定しています。ですから、この想定にあわないという理由で除外されたリザルトは、可能性を調べ回ることなくその場で断念されてしまいます。
^訳注5

(訳注1):'__': ASCIIのアンダースコア2つの連続です。
(訳注2): （欠番）
(訳注3):群がり現象: flocking をこのように訳していますが、なにがどう群がるのかよく分かっていません（照会中）。
(訳注4):不変式(invariant): invariantという言い方にそぐわない手順の説明になっているので、意図を照会中。
(訳注5):すべてのリザルトについて・・・仮定しています: この注意書きは意味内容がよくわかっていません。照会中。

BOINCの訳のメインページに戻る | (原文のメインページに戻る)

最終更新時刻 00:16:04, 2007年04月20日(JST)
Copyright © 2010 University of California. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
Copyright © 2010 Komori Hitoshi(je2bwm at jarl.com). Japanese translation from English web pages on BOINC. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.