AI解説
実装: BOINC (Berkeley Open Infrastructure for Network Computing)。https://boinc.berkeley.edu/ 情報源: arXiv 版（表紙に2018-12-09の日付、全37頁）の全文を精読して記述。本文に書かれていない事項は書いていない。
一言で
Volunteer computing（一般家庭のデジタル機器を高スループットな科学計算に使うこと）のための、最も広く使われているオープンソースミドルウェア BOINC の機能・アーキテクチャ・実装をまとめた論文。約70万台の機器（約400万CPUコア、56万GPU）が参加し、平均93ペタFLOPSのスループットを提供している。デバイスの異種性・信頼性の低さ・出入りの激しさという課題に対し、アプリケーションレベルのチェックポイント／再開プロトコルと、締切を考慮したジョブスケジューリングで対処する。
背景・問題
Volunteer computing は、デスクトップ・ラップトップ・タブレット・スマートフォンのような民生機器の持ち主が、科学プロジェクトのサーバからジョブをダウンロード・実行するプログラムをインストールすることで参加する。現在約30の VC プロジェクトがあり、Nature、Science、PNAS など主要誌に多数の論文を生んでいる。潜在的な計算能力はさらに大きく、20億台超のデスクトップ・ラップトップと100億台の携帯機器を考慮すると、近い将来数百エクサFLOPS規模のポテンシャルがあるとされる。
この環境固有の課題は、デバイスの異種性（アーキテクチャ、OS、性能のばらつき）、信頼性の低さ（いつ電源が切られるか、いつネットワークから切断されるか分からない）、そして参加・離脱が絶えず起こる churn である。
提案手法
アプリケーションレベルのチェックポイント／再開プロトコル
BOINC クライアントとアプリケーションは、全 OS がサポートする共有メモリを使ったメッセージパッシングで通信する。クライアントからアプリケーションへは suspend／resume／quit、アプリケーションからクライアントへは現在の CPU 時間・最後にチェックポイントした時点の CPU 時間・進捗率・作業セットサイズを伝えるキューがあり、双方とも毎秒自分の受信キューをポーリングする。BOINC 配下で動く全アプリケーションはこのメッセージプロトコルを実装しなければならない。
プロセス構造は実行形態によって異なる。逐次プログラムでは、ランタイムライブラリがタイマスレッド（クライアントとの通信を管理）を作り、元のワーカスレッドがプログラム本体を実行する。Windows ではタイマスレッドが Windows のスレッドプリミティブでワーカスレッドを制御するが、Unix のスレッドライブラリは1つのスレッドが別のスレッドを一時停止させることを許さないため、10Hz のシグナルをワーカスレッドが処理し、そのシグナルハンドラをスリープさせることで一時停止を実現する。マルチスレッドアプリケーション（OpenMP や OpenCL CPU など）では、Unix ではプログラムが fork し、親プロセスがシグナルでプロセス制御メッセージを扱い、子プロセスがプログラム本体を実行しつつタイマスレッドでステータスとチェックポイントのメッセージを扱う。
Figure 2: The process structure of the BOINC runtime environment。
BOINC はアプリケーションレベルのチェックポイント／再開をサポートする。クライアントは数分おきにアプリケーションへチェックポイントを要求するメッセージを送る。アプリケーションは（例えば外側のループの先頭など）効率よくチェックポイントできる地点に達すると、チェックポイントファイルを書き、それを示すメッセージをクライアントへ送る。これによりクライアントはアプリケーションがいつチェックポイントしたかを把握し、長い間（または一度も）チェックポイントしていないジョブのプリエンプトを避けられる。GPU を使うアプリケーションでは、CPU 側のプログラムが短い「カーネル」を GPU へ発行するが、カーネル実行中にアプリケーションを一時停止させてはならない。そのため BOINC ランタイムライブラリは、一時停止と中断が延期されるマスク区間をサポートし、GPU カーネルの実行やチェックポイントファイルの書き込みはこのマスク区間内で行うべきだとされる。
VM ベースのアプリケーションでは、BOINC クライアントと VirtualBox 実行系との間を仲介する VBox wrapper プログラムを提供する。これは VirtualBox の「スナップショット」機能に基づく、アプリケーションに依存しないチェックポイント／再開機能も提供する。wrapper は数分おきに VirtualBox へスナップショットの作成を指示し、計算が中断された（例えばホストの電源が切られた）場合、そのホスト上で最新のスナップショットからジョブを再開できる。
資源スケジューリングポリシー
クライアントは WRR（Weighted Round-Robin）ポリシーの下で全ジョブの実行を周期的にシミュレートし、これに基づいてどのジョブが締切を守れないかを予測する。この情報をもとに、次の基準で降順にジョブを並べる。
- (a) WRR シミュレーションで締切に間に合わないと予測されたジョブを優先し、それらは EDF（最早締切優先）で実行する
- (b) GPU ジョブを CPU ジョブより優先する
- (c) タイムスライスの途中にあるジョブ、またはまだチェックポイントしていないジョブを優先する
- (d) より多くの CPU を使うジョブを優先する
- (e) スケジューリング優先度がより高いプロジェクトのジョブを優先する
このリストを走査して極大集合を見つけ、それらのジョブを実行し、集合に含まれない実行中のジョブをプリエンプトする。要するに、BOINC は締切超過の予測がない限り WRR スケジューリングを使い、予測がある場合は EDF を使う。
実験・結果（実装と運用データの範囲）
本論文は新規の性能評価実験というより、実運用中のシステムの記述である。約70万台の機器が参加し、約400万 CPU コアと56万 GPU を持ち、平均93ペタFLOPSのスループットを提供している。典型的な BOINC プロジェクトの運用コストは、数台の Linux サーバと非常勤のシステム管理者で年間10万ドル程度とされ、Einstein@Home、Rosetta@home、SETI@home のようなこの規模のプロジェクトは平均約1ペタFLOPSのスループットを得ているとしている。
関連研究との関係（メモ）
- V-BOINC（cite key
mcgilvary2013vboinc）：本論文が説明する VBox wrapper と同種の、VirtualBox スナップショットに基づくアプリケーション非依存のチェックポイント機能を、BOINC のクライアントを修正する形で外部から先に実現した研究。V-BOINC は2013年の研究で、BOINC 自身の VBox wrapper 機能に先行する。 - 分野横断的な位置づけは アプリケーションレベルのチェックポイント の §3.8 を参照。
Q&A
（自分がAIに実際に質問したことだけをQ/A形式で残す。まだなし。）
自分のコメント
（ここは自分で都度書く欄。）