クライアントでのスケジューリング
クライアントでのスケジューリング |
|
この文書では、 BOINC コア・クライアント内の相互に関連する以下の3つの部分について記述しています。
上述の方針の目標は、以下のとおりです(重要なものの順です)。
以前の版の BOINC では、参加しているプロジェクトあたり最低1つのリザルトを保持するよう試みていました。 そして、それらの全プロジェクトの間で重みづけしたラウンド・ロビン方式の CPU スケジューリングを実施しようとしていました。 いくつかのシナリオ(コンピュータが遅い場合、参加プロジェクトが多い場合、 報告期限まで余裕がない場合、および、これらの組合せのシナリオ)では、 すべてのリザルトで報告期限を守れないこともあり得ました。 新しい方針では、この問題点を以下のように解決します。
柱時計 CPU 時間 とは、プロセスが OS から見て走行可能状態(runnable)だった経過時間(柱時計で測った時間)です。 実際の CPU 消費時間はこの値より小さいことがあります。 たとえば、 そのプロセスでペイジングが多量に発生した場合や、他の( BOINC でない) 仕事が同時に走っていたという場合にそうなります。
BOINC は、柱時計 CPU 時間をもって、CPU 資源の使用状況の指標とします。 柱時計 CPU 時間のほうが、ペイジングを起こすアプリケーションの場合、より公平です。 さらに、実 CPU 消費時間の測定は、アプリケーションが正しくその値を報告することに依存しますが、 アプリケーションは正確に答えないかもしれません。
リザルトの 正規化された CPU 時間(Normalized CPU time) とは、 以下を考慮に入れて、リザルト計算完了までの柱時計時間を推定した値です。
リザルトの プロジェクトごとに正規化された CPU 時間(Project-normalized CPU time) とは、 リザルト計算完了までの柱時計時間を推定した値であって、 上述の考慮を入れた上、さらに対象プロジェクトの資源占有率が 他の走行可なプロジェクトとの間でどのような比率になっているのかも考慮に入れたものです。
スケジューラ RPC 要求 に含まれる 'work_req' 要素は、 プロジェクトごとに正規化された CPU 時間を単位に表現されます。 どのような大きさの仕事を送るか決めるときに、 スケジューラはそのプロジェクトの資源占有率が全体に占める割合と、 その計算機の「on-fraction」および「active-fraction」を考慮する必要があります。
例をあげましょう。 ある計算機は 1 GFLOPS の CPU 群をもっていて、 対象プロジェクトの資源占有率が全体に占める割合は 0.5、 その計算機の 「on-fraction」は 0.8、「active-fraction」は 0.9 とします。 すると、CPU ごとの期待される処理速度は、以下のとおりです。
(1 GFLOPS) * 0.5 * 0.8 * 0.9 = 0.36 GFLOPSこの計算機が、プロジェクトごとに正規化された CPU 時間で、 1000 秒の長さの仕事を要求したとすると、スケジューラは 少なくとも 360 GFLOP の長さの仕事を送るべきです。
長期の負債(LTD：Long-term debt) という指標が、仕事獲得の仕組みで用いられます。 この値は、全てのプロジェクトに対して定義された値であり、 潜在的に走行可の状態にあるプロジェクトの集合について、調整されます。 すべてのプロジェクトにわたり、長期の負債の平均値がゼロになるように正規化されます。
ほぼ走行可のリザルトの集合に対して、重みづけしたラウンド・ロビン・スケジューリングの模擬をします。 この結果を、CPU スケジューリングと仕事獲得の方針で使用します。 この模擬は、「on-fraction」と「active-fraction」を考慮に入れます。 以下の出力を出します。
下記の例では、プロジェクト A と B がそれぞれ資源占有率 2 と 1 をもっています。 このコンピュータには、2つの CPU があります。 時刻 0 から 4 まで、3つのリザルトすべてが同じ重みでスケジュールされて走ります。 時刻 4 に、リザルト A2 が終わります。 時刻 4 から 8 では、プロジェクト A は資源を使える割合が 0.5 だけになっています。 というのは、A は1つしかリザルトをもっていないからです。 時刻 8 で、リザルト A1 が終わります。
この例では、shortfall(A) は 4で、shortfall(B) は 0、total_shortfall は 2 です。
この CPU スケジューラは、2つの方針を使いわけます。 報告期限を超過する恐れがあるリザルトについては、期限余裕最短を優先 (EDF: earliest-deadline-first) という方針を使って CPU を割当てます。 そしてまだ別の CPU が使えれば、上記以外のプロジェクトについて 重みづけのあるラウンドロビン方式を適用します。 こうすれば、クライアントは超過しかねなかった期限を守ることができ、なお、 長期にわたる資源占有率の指示を尊重して動作することができます。 このスケジューリング方針は以下のように記述できます。
この CPU スケジューラが走るのは、リザルトの計算が完了したとき、 参加者が指定した仕事期間の終了点に達したとき、 新しいリザルトが走行可の状態になったとき、そして、 参加者がユーザインタフェースを通じて何らかの操作をしたとき (たとえば、プロジェクトあるいはリザルトの一時停止・再開をしたとき) です。
この CPU スケジューラは、どのリザルトを走らせるべきかを決定しますが、 その判断を実施する役割は負っていません。 実施するのは別の スケジュール執行関数(scheduler enforcement function) です。 CPU スケジューラは結論を出したところで、これらを呼びます。 X を 現在 走行していないがスケジュールされたリザルトの集合とします。 Y を 今回はスケジュールされなかったが、現在 走行しているリザルトの集合とします。 T を スケジューラが最後に走った時刻とします。 スケジュールの執行方針は以下のとおりです。
プロジェクト P が仕事超過(overworked) であるとは、
この条件が満たされるのは、P のリザルトが EDF モードにおいて走る場合です。 (極端な場合としては、とても LTD(長期の負債) が大きな負数であったプロジェクトから離脱した場合があります)。 この仕事獲得の方針では、仕事超過の状態にあるプロジェクトには仕事を取りに行かせません。 これによって、間近な報告期限の仕事をもっているプロジェクトが、 CPU 時間の占有率を越えてもさらに仕事を取り出すことを防ぎます。
仕事獲得の方針においては以下の関数を使います。
frs(project P)
仕事獲得可能(fetcharable)プロジェクトに占める、プロジェクト P の資源占有率の割合。
この仕事獲得方針のための関数は、数分おきに(および必要に応じて) スケジューラ の RPC ポーリング関数から呼ばれます。 この関数は、変数 P.work_request_size を各プロジェクト P ごとに設定します。 その値は、PIへのスケジューラ RPC を発行するとしたらどれだけの仕事を要求するかを、 単位を秒として表現したものです。 その値は以下のように計算します。
for each project P
if P が一時停止状態(suspended)、通信延期状態(deferred)、
仕事超過状態(overworked)、あるいは、新しい仕事の禁止(no-new-work)
のいずれかならば、
P.work_request_size = 0
else
P.work_request_size = shortfall(P)
if total_shortfall > 0
if すべてのプロジェクト(P)について P.work_request_size==0 ならば、
for each project P
if P が一時停止状態(suspended)、通信延期状態(deferred)、
仕事超過状態(overworked)、あるいは、新しい仕事の禁止(no-new-work)
のいずれかならば、
continue
P.work_request_size = 1
if すべてのプロジェクト(P)について P.work_request_size==0 ならば、
for each project P
if P が一時停止状態(suspended)、通信延期状態(deferred)、
あるいは、新しい仕事の禁止(no-new-work) のいずれかならば、
continue
P.work_request_size = 1
P.work_request_size>0 である P に対して、
P.work_request_size を正規化します。 つまり、合計が total_shortfall
になり、それぞれの占める割合が P.resource_share に比例するように正規化します。
CPU を散発的にしか使わないプロジェクトでは、 プロジェクト P が 走行可能状態に近い(nearly-runnable)訳注5 リザルトをもっていなければ P.work_request_size を 1 に設定し、さもなくば 0 に設定します。
スケジューラ RPC の仕組みは、サーバへ接続するプロジェクトを色々な理由で選択することがあります。 参加者が要求したり、トリクル・アップ・メッセージが突出している場合、 あるいは、報告期限を超過した計算結果がある場合です。 このようなケースでサーバに接続するときも、そのプロジェクトに対して仕事を要求します。 以上の場合ではないなら、RPC の仕組みは下記の条件をみたすプロジェクト P に仕事を獲得しに行かせます。
P.work_request_size>0 かつ、 P.long_term_debt + shortfall(P) が最大のプロジェクト注意: P.work_request_size は、正規化された CPU 時間を単位に表現しますから、 実際の仕事要求の値 (これはプロジェクトごとに正規化した CPU 時間を単位に表現)は、 P.work_request_size の値を 走る可能性のあるプロジェクトに占める対象プロジェクト P の持つ資源占有率の割合で、 分割したものになります。
注意: 以下に記述された内容はまだ実装されていません。 また、上述の方針とも独立なものです。
スケジューラは初めから報告期限を守れそうもないリザルトを送りつけるべきではありませんし、 すでにクライアントが持っているリザルトが期限を守れなくなるようなリザルトも送るべきではありません。 これを実現するため以下のようにします。
スケジューリングのシナリオを記述する際には、下記の記法を用いることを勧めます。 (時の単位は、時間(hours)です)。
P(C, D, R)
これは以下の性質を持つあるプロジェクトを意味します。
P1(1000, 2000, .5) P2(1, 10, .5) NCPUS=4
P1(0.1, 1, .5) P2(1, 24, .25) P3(1, 24, .25) NCPUS = 2 leave_in_memory = false cpu_scheduling_period = 1典型的には、どちらか1つの CPU が P1 の 6分かかるタスクを処理します。 もう1つの CPU は、P2 と P3 の仕事を切り替えて処理します。 重要なのは、スケジューラが P2 と P3 のタスクのそれぞれを スケジューリング期間全般にわたって走らせることです。 「負債」の考え方に正確に合わせてスケジューリングすると、6分ごとに毎回、 P2、P3の間で切り替えを起こすという結果になりますから、 P2 と P3 はそのたびごとにチェックポイントから再開せざるを得ないでしょう。 いくつかのアプリケーション(例： Einstein@home) では、 チェックポイントから再開するために数分の処理が必要です。 ということは、このシナリオでは片側の CPU の時間の大半を無駄にしてしまうことになります。
最終更新時刻 00:50:39, 2006年08月12日(JST)
Copyright © 2008 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 © 2008 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.