はじめに

　SETI (Search for Extraterrestrial Intelligence) は地球外知的生命を探 す事を目標にした科学である[SHO98]。  電波SETIといわれ る一手法は、宇宙からの狭い帯域幅の電波信号を捉えるために電波望遠鏡を使 用する。 自然界で生じないと思われるそのような狭帯域の信号を検出する事は、 地球外生命体による技術の存在の証拠となる [COC59]。 

　電波望遠鏡で捉える信号の大部分は(天空から飛来するあるいは受信 機に起因する)ノイズとテレビ局やレーダーおよび衛星といった地球人由来の 信号である。 現代の電波SETIプロジェクトはデータをディジタルで分析する。  この分析は一般的に3段階で行なわれる。 

1. データの 時間に沿って変化するパワー・スペクトルを計算する
2. それらのパワー・スペクトルに対してパターン認識を使用し,候補の信号を見つける
3. 自然発生か地球由来と思われる候補信号を除去する

　より大きな計算能力は、より広い周波数範囲をより高い感度で探索する事を可 能とすることから、電波SETIにおいては際限ない計算能力への欲求が存在する。  従前の電波SETIプロジェクトでは大量データの分析のために専用のスーパー・コ ンピューターを望遠鏡の傍に配置していた。 

　1995年、David Gedye はインターネットに接続した多数のコンピューターで構 成する仮想スーパーコンピューターを使用して電波SETIを行う事を提案し、この アイデアを実践すべく「SETI@home 」プロジェクトを組織した。 SETI@home では まだ地球外生命体からの信号を見つけていない。 しかし、関連する分散コンピューティン グ・分散ストレージのプロジェクトとともに、(一般大衆から計算機資源が提 供される)パブリックリソース・ コンピューティングの可能性を確立した。 

　パブリックリソース・ コンピューティングは万能薬でも無料ランチでもない。 多 くの作業について、巨大な計算能力と巨大なネットワーク帯域幅を必要とする も、 一般的にネットワーク帯域幅は高価かもしくは制限されている。 より広い範囲の 探索は多くのネットワーク帯域を必要とすることから、上記の要因が、 SETI@home の探索する周波数範囲を制限している。 他の電波SETIプロジェクト と比較してSETI@home はより狭い周波数範囲しかカバーしないが、その範囲の中 ではより徹底的な探索を行っている(表1参照)。 

SETI@homeのデザイン

　SETI@home の最初の関門は高性能電波望遠鏡を見つけることであった。 プエル トリコのアレシボにある世界最大かつ最高感度の電波望遠鏡が最適であるが、こ こは様々な天文学と大気の研究のために使用されており、長期独占使用できない 難点があった。 しかし、1997年、U.C.バークレーSERENDIPプロジェクトは、アレ シボに第2アンテナを相乗りさせる技術を開発した [WER97]。 他の研究者がメインアン テナを天空に固定して観測している間でも、第2のアンテナは弧を描くので, いつかは望遠鏡が見える全ての範囲をカバーできるのである。 このデータソースが、 何億もの星をカバーするべき天球調査に使用できる。 

　SETI@home では SERENDIP のデータソースを拝借することした。 SERENDIPとは 異なり、インターネットを介してデータを分配する必要があった。 当時、アレシ ボのインターネット接続は56Kbpsモデムであった事から、当時最大容量だった35GBの DLTカートリッジにデータを記録してU.C.バークレーの実験室へ郵送し、そこの サーバーからデータ分配する方式とした。 

　私たちは、5Mbpsのデータレートで記録すると決定した。  テープ1本への記録時間を16時間と扱いやすい長さにするには 十分低いレートであり、また、実験室の100Mbpsインターネット接続を介して データを分配する事も実現可能でもあった。 しかし、 科学的な目的には十分に高いレートであった。  本レートで1bit複素サンプリングしたビット列は2.5MHzの周波数幅に相当する。  これは、相対速度260km/秒まで、あるいは銀河の回転速度のドップラー偏移を 扱うのに十分である。 (無線信号は送信器の受信機に対する相対速度に応じて ドップラー偏移する。) 他の多くの電波SETIプロジェクトと同様に、 電波利用が国際条約で禁止されている水素輝線の1.42GHz周波数帯に焦点をあてた。 

　SETI@home の計算モデルは単純である。 信号データは固定長のWU (work unit)に分割され、多数のコンピューター上で走るクライアント・ プログラムにインターネット経由で分配される。  クライアント・プログラムは計算結果(候補信号)をサーバーに返し、 次のWUを得る。 クライアント間では互いに一切の関わりを持たない。 

　SETI@home では各WUが 複数回処理されるような冗長度をもつ。  これにより、不完全なプロセッサーからの、あるいは悪意のユーザからの 結果を検知し除去できる。 この目的には冗長度2〜3のレベルが適切である。  本プロジェクトでは限られた速度でしかWUを生成できず、 WUを求めるクライアントを門前払いにしない事にしたので、 クライアントの数およびその平均処理速度の増加につれて冗長度が増加した。  クライアント数と平均処理速度は プロジェクト中に大幅に増加した。 私たちは、WUについてより多くの 計算を行うようクライアントを改訂する事で、適正な冗長度レベルを維持した。 

　WUの作成および分配は、 実験室のサーバ群で処理される(図1を参照)。  サーバー機能を集中化したのは、例えば、 テープの取扱いの手間を最小限にするなどの主に運用上の理由による。 

図1:データの配布

　WUの生成は、2.5MHzの信号を256分割する事から始まる。  これは周波数帯域約10kHzのバンド幅に相当する。  次に各バンドは107秒間の断片に分割されて個々のWUとなる。  各WUは互いに20秒間分重なっている。 これにより探索している信号 (20秒間以内の信号:下記参照)が少なくとも1つのWUに完全に含まれることを 保証している。 WUのサイズは約350KB、一般的なPCで ほぼ一日中解析するに十分な大きさであり、遅いモデムでも数分以内で ダウンロードできるサイズとなる。 

　テープ、WU、解析結果、ユーザ情報、その他プロジェクトの状況に 関する情報を格納するために、リレーショナル・データベースを使用している。  クライアントにWUを分配するためにマルチスレッドのデータ/結果サーバー を開発した。 ファイアウォール内側に設置されたクライアントでも 接続できるようにHTTPベースのプロトコルを利用している。  WUは分配した回数の少ないもの順に選択して送信される。 

　ガーベージコレクタ・プログラムは、データベースレコード上の 「オンディスクフラグ」をクリアしてディスクからWUを削除する。  この動作に関し以下の2つの方式で実験した:

• 予定冗長度をN とし、 N 件の結果が報告されたら ディスクからWUを削除する。 WU用の記憶装置が満杯になってしまうと WUの生成が停止しシステムの処理効率が低下する。 
• M 回送信したらWUを削除する。 M は N より少し大きめの値とする。  この方法は上記のボトルネックを回避するが、幾つかのWUについて 最後まで結果が戻ってこない事態を引起こす。 この割合はM  を増加させることによりいくらでも小さくする事ができる。  私たちは現在この方式を採用している。 

　SETI@homeの最も困難で最も高価な部分は、サーバー・システムを 常時稼動させることであった。 ハードウェアおよびソフトウェアの双方 から障害が発生し、それは尽きることがないように みえた。 まず、サーバー・サブシステム間の依存性を最小限にする アーキテクチャーとする事に集中した。 例えばデータ/結果サーバーは、 送信用WUを準備するためにデータベースを使用する代わりに、 ディスクファイルからこの情報を得るモードで実行することができる。  これによりデータベースが障害中でもデータを配信できる。 

　クライアント・プログラムは、データ/結果サーバーからWUを得て、 分析し、サーバーに結果(候補信号のリスト)を返す事を繰り返す。  サーバーと通信する間その時だけインターネット接続を必要する。  クライアントはその計算機がアイドル状態の時にだけ働くか、あるいは 絶えず低優先順位で計算するように設定することができる。  計算機がしばしば動作を止めても分析が続けられるように、 プログラムは、周期的にディスクファイルに分析状態を書出し、 スタート時にこのファイルを読取るようコーディングされている。 

　WUの分析は、周波数と時間軸上で信号強度を算出する、次に、 スパイク(短い爆発)、 ガウシアン （20秒間のガウシアン型の裾野形状をもつ、狭帯域信号。  このパターンはArecibo望遠鏡のビームが天空の点を通過することに 対応している。 ） パルス信号 (任意の周期、位相、デューティサイクル(訳注1)をもつ、 周期的パルスの形に切り取られたガウシアン） トリプレット (同一周波数で等時間間隔で並んだ３つのスパイク信号。  つまり、パルス信号の単純なもの) といった信号パターンを探す。 そして、強度や適合度がしきい値を 超える信号についてそれを出力ファイルに記録する。 
訳注１：デューティサイクルとは、ONとOFFの周期的な繰返しがあるときに、 全体の中でのONの部分の比率のこと

　外部ループは2つのパラメーターを変える[KOR01]:

• ドップラードリフト 。 固定周波数の送信機が、受信者にたいして 加速される場合には(例えば惑星の運動による加速)、 受信信号は周波数軸で浮動する。  そのような信号は、オリジナルデータの浮動を打消してから、その後、 一定周波数の信号を捜すことにより完全な検出が可能となる。  浮動量は事前にはわからないので、物理的に妥当な加速度の範囲をカバーして、 31,555の異なるレートをチェックする。 
• 周波数分解能: 0.075〜1220.7Hzの15段階の周波数分解能をカバーする。  変調された信号はある範囲に周波数成分が広がるので、これにより増感できる。 

図2:SETI@homeの画面表示例: (画面下半分が計算中のパワースペクトラム。  左上には、最も適合するガウシアンが表示されている。 ）

SETI@home クライアントプログラムはC++でコーディングされている。 こ のコードは稼働環境に依存しない分散コンピューティングのフレームワーク (6,423行)、グラフィックライブラリ等の稼働環境に依存する部分の実装(UNIX版では2,058行)、 SETIに固有のデータ分析コード(6,572行） およびSETIに固有のグラフィックス・コード(2,247行)から構成される。 

　クライアントは175の異なる稼働環境へ移植された。 gccとautoconfを 含むGNUツールはこの作業に非常に役立った。  ウインドウズ、マッキントッシュおよびSPARC/Solarisバージョンは 当方で保守しているが、他への移植ははボランティアに頼っている。 

　クライアントはGUIアプリケーションとして、 あるいはスクリーンセーバーとしてバックグラウンドで稼動する。  多くの稼働環境でこれらの異なるモードをサポートするために、 第一スレッドが通信とデータ分析を、第二スレッドがGUIの操作を、 第3スレッドが(おそらく別アドレス空間で)共有メモリーデータ構造に基く グラフィックス描画を担当するアーキテクチャーとした。 

　分析結果はSETI@homeのサーバー群に返送され、そこで記録されて分析される。  (図3参照)。 

図3: 結果の収集と分析

２つの工程からなる結果処理:

• 科学的工程 : データ/サーバーはディスク・ファイルに結果を書き込む。  あるプログラムがこれらのファイルを読み、 データ・ベース上に結果と信号のレコードを作成する。  このプログラムは同時に数枚走らせて処理能力を確保している。 
• 会計的工程 : サーバーは各分析結果について、処理したユーザ、要したCPU時間他のログなどを書込む。  他のプログラムでこれらのログ・ファイルを読込み、 メモリーキャッシュ上でデータベースレコード(ユーザ、チーム、国、CPUタイプなど) を更新するための累積処理を行う。 このキャッシュは数分毎に、 データベースに書出される。 

ディスクファイル に更新内容をバッファリング することによって、サーバーシステムは、 データベースの停止中や過負荷状態でも処理が継続できる。 

最終的に各WUに対して、データベースにはいくつもの分析結果が入る。  冗長性除去プログラムは、同一WUについての複数の分析結果をチェックする。 それらの結果は、検出した信号の総数や、信号のもつパラメーターに差があるかもしれない。 チェックの結果、近似一致のポリシーに基いて「正統的」な結果を選択する。  「正統的」な結果は別のデータベースにコピー保存される。 

　最終段階、バックエンド処理 はいくつかのステップから構成されている。  システムが正常に働いているか検査するために、 望遠鏡で注入されたテスト信号をチェックする。  地球由来の信号(RFI)を識別し除去する。 さらに天空の同じ位置、 同じ周波数で異なる時刻に観測された信号を探す。  「繰返された信号」は十分な価値をもつ一度だけの信号と同様にさらに十分に吟味し、 既に受け入れられているあるきまり[DOP90]に従い、 他の電波SETIプロジェクトによる最終クロスチェックに持ち出される。 

SETI@home への反響

1998年にSETI@homeの計画を発表し、翌年までに40万人の事前登録を得た。  1999年5月に、ウインドウズ版とマッキントッシュ版のクライアントをリリースした。  一週間以内に約20万人がクライアントをダウンロードして実行し、 2002年7月時点では383万人以上に増加した。  226カ国の人々がSETI@ホームを実行している、一方約半分は米国内である。 

　 2001年7月を起点とする12ヶ月間で、SETI@home参加者全体で221百万のWUを処理し、 期間中の平均処理能力は27.36テラFLOPSになる。 全体として、 1.7x10の21剰回の浮動小数点計算を実行したことになり、史上最大の計算量と なった。 

　 SETI@homeは参加者を募るために、第一にマスメディアでのニュース 報道や口こみに頼った。 本プロジェクトのウェブサイト (http://setiathome.berkeley.edu)はプロジェクトについて説明し、 ユーザにクライアント・プログラムをダウンロードさせ、 科学面と技術面のニュースを提供している。 

　ウェブサイトには、個人向けに、また地域や電子メールドメインのよ うなグループ向けに、処理したWU数に基づいたリーダーボード を掲示している。 ユーザは、 各カテゴリー内で競争するチームを組織することができ、 97,000チームが存在している。 (個人、チーム、 コンピューター・タイプごとの所有者の間での) リーダーボード競争は、 参加者を引きつけて継続させるという点で役立った。  更に、ユーザはWUマイルストーンを達成するたびに、 ウェブサイト上で認定され、電子メールで感謝状が送られる。 

　私たちは、参加者同士が情報と意見を交換できるSETI@homeコミュニティーを 促進しようとした。 ウェブサイトでは、 参加者自身がプロファイルや写真を登録でき、 参加者に関する統計用データ、 SETI、分散コンピューティングに関するオンライン投票アンケートを用意した。  (投票した95,000人のユーザのうち、例えば、93%は男性である。)  SETI@homeに熱心なニュースグループ (sci.astro.seti)の立上げにも協力した。 参加者は、例えば、プロキシデータ サーバーや進行状況を図示するシステムのような様々な付随的なソフトウェアを作成した。  ウェブサイトではこれらへの貢献へのリンクを掲載している。  参加者はまたこのウェブサイトを30言語に翻訳してくれた。 

　クライアントプログラムがソフトウェア・ウィルスの導入役にならないよう努力している。  これまでのところ、この努力は成功している:コード・ダウンロードサーバーは (知る限りにおいて)侵入されていないし、また、 クライアント・プログラムはコードをダウンロードしないしインストールもしていない。  これまでに2つの注目すべき攻撃があった。 大げさに言えば ウェブサーバは危険にさらされたが、ハッカーが例えばトロイの木馬型 ダウンロードページを仕掛けるようなことは起きなかった。  その後、クライアント/サーバープロトコルの欠陥を突かれ、 ハッカーはユーザの電子メールアドレスのいくつかを盗み出した。  しかし何千アドレスも盗まれる前にこの欠陥は塞いだ。 更に、 ある参加者が作り出したメール感染型ウイルスは、SETI@homeをダウンロードして 感染したコンピュータにインストールし、彼の成果となるように設定するものだった。  これは、インストール手順中にマニュアル介入を必要としてあれば、 防止できていたかもしれない。 

　一方で、無法な、あるいは悪意のある参加者からSETI@homeを保護する必要もあった。  事例の枚挙に暇は無いが、これは参加者のほんのごく一部分にすぎない。  比較的良性の例を上げると、何人かの参加者はクライアントプログラムについて 特定のプロセッサー上での実行性能を上げる修正していた。 このような修正の 正確さを我々は信頼しないし、 SETI@homeが「ベンチマーク競争」として使用されたくないので、修正は禁止とした。 

　インチキで実績をあげようとする各種の企てを見破った。  故意に誤りだらけの結果を送り返してくる参加者も居た。  参加者がデバッガでクライアントプログラムを実行でき、ロジックを解析でき、 埋込暗号鍵キーを見破れるとすれば、このような参加者の企てを防止するのは難しい[MOL00]。  冗長性によるチェックと我々の計算処理の誤り耐性とを合わせることで、 これらの問題には十分に対処できた。  これとは別のメカニズムも提案されている[SAR01]。 

結論

パブリックリソース・コンピューティングは、 CPU時間の空きがあるような過剰能力を備えたパソコンに依存する。  分散コンピューティングにこれらの余剰能力を使用するアイデアは、Xerox PARC の Wormによる計算プロジェクトによって提案され、 研究室内のワークステーションを使用していたが[SHO82]、 後に Condor のような学術的なプロジェクトによって追査された。 

　大規模なパブリックリソース・コンピューティングは1990年代の インターネットの普及で実現可能になった。 2つの大きなプロジェクトが SETI@homeに先行している。 素数を探索する The Great Internet Mersenne Prime Search (GIMPS)は、1996年に開始されている。  総当たり計算により暗号解読を行う Distributed.net は1997年に開始されている。  最近のアプリケーションとしては protein folding (folding@home) やdrug discovery (Intel-United Devices Cancer Research Project)が挙げられる。 

パブリックリソース・分散コンピューティングのための 汎用フレームワークを開発する試みがいくつか進行中である。  まとめてGrid と呼ばれるプロジェクト群では、 学校や研究機関でリソース・シェアリングするシステムを開発している[FOS99]。  Platform Computing、Entropia、United Devices 等の民間企業は、 一般市民や各種機関のどちらでも利用できる分散コンピューティング・ 分散ストレージシステムを開発中である。 

　総括的には、パブリックリソース・コンピューティングは、 「ピア・ツー・ピア・パラダイム」の一側面である。 このパラダイムは 資源集約的な機能を中央サーバーからワークステーションや家庭内PCへ 分散させる方向に向かっている[ORA01]。 

　どのような計算処理がパブリックリソース・コンピューティングに向いているか？  いくつかの要因がある。 第一に、その計算処理がデータ量に比して大きな計算量を持つこと。  SETI@homeの各データ単位（WU)では3兆9千億回の浮動小数点演算が必要で、 500MHzのペンティアムIIで約10時間かかるが、ダウンロードするデータ量は 350KBでアップロードは1KBだけで済む。 この計算量とデータ量の間の 高い比率はサーバーにかかるネットワークトラフィックを管理しやすくし、 クライアント側のネットワークにかける負荷も最小限に抑えている。  コンピュータ・グラフィックス・レンダリングのような計算処理では 計算量あたりで考えると大量データを必要とするため、 恐らくパブリックリソース・コンピューティングには適さない。  しかし、通信コストが安くなればこれらの問題は緩和されるであろうし、 WU内の大部分が一定の同じデータであれば、 マルチキャスト技術によりコストを下げられるかもしれない。 

　第ニに、各並列計算が独立しているような計算処理 がより扱いやすい。  SETI@homeのWU計算は独立しているので、参加しているコンピューターは 互いに相手と交信したり待ったりする必要がない。 コンピューターが WUの処理に失敗しても、別のコンピューターへ送られて処理される。  頻繁に同期待ちやノード間の通信を必要とする計算処理ではシェアドメモリ・ マルチプロセッサーのようなハードウェアベースのアプローチにより 並列計算しているか、あるいは、最近ではPVMのようなソフトウェアベースの クラスタ・コンピューティングにより並列化が実現されている [SUN90]。 頻繁にコンピュータが停止しネットワークが切れるような環境下の パブリックリソース・コンピューティングは、これらの計算処理には不適当にみえる。  しかし、LAN接続しているマシンのグループを見つけて 仕事を割当てるスケジューリング機構があれば、困難は克服できそうである。 

　第三に、エラーに対し寛容な計算処理もパブリックリソース・ コンピューティングに適している。 例えば、SETI@homeではWUの分析結果が 不正確であるとか帰ってこない場合でも、最終的な目標に対して殆ど影響が及ぼない。  さらに言えば、データが欠落したら、もう一度望遠鏡を向けて補えば済むのである。 

　最後に、パブリックリソース・コンピューティングプロジェクトは 参加者にとって魅力的であるべき。 現在インターネットに接続している コンピューターの数は、SETI@home規模のプロジェクトを100件程度こな すに十分な台数であるので、 global climate modeling(地球規模気候モデリング)および ecological simulation(生態学シミュレーション)のような分野の、面白くかつ 有益なプロジェクトが提案されている。  参加者を募るには、プロジェクトの目標とその正当性を説明し、 各参加者の視点および全体の視点で、 その進行状況をはっきりと提示する必要があると思う。  スクリーンセーバ画像はバイラルマーケティング（訳注２） の手法を実践するだけでなく、上記の提示活動のための 優れたメディアである。  パブリックリソース・コンピューティングプロジェクトの成功は、 科学についての一般人の意識向上と、 研究資源割付けをある程度民主化するという付随的な利点を引出すだろう。 
訳注２：バイラルマーケティング(viral marketing)とは、 商品を使ってみた人が友人などに口コミでその商品の情報を広げるように仕向けるテクニック。 

謝辞

　SETI@homeはDavid Gedyeにより発案された。 Woody Sullivan, Craig Kasnov, Kyle Granger, Charlie Fenton, Hiram Clawson, Peter Leiser, Eric Heien, Steve Fulton は、SETI@homeにアイデアと努力を捧げた。  プロジェクトの参加者および The Planetary Society、Sun Microsystems、the U.C. DiMI program、富士写真フイルム、Quantum, Informix、Network Appliances、 そしてSETI@homeを支援してくれたその他多くの組織・各位に感謝する。 

参考文献

COC59

Cocconi, G., and Morrison, P., "Searching for Interstellar Communications," Nature, Vol. 184, #4690, p. 844. Sept. 1959.

DOP90

Declaration of Principles Concerning Activities Following the Detection of Extraterrestrial Intelligence. Acta Astronautica 21(2) pp. 153-154, 1990.

KOR01

Korpela, E., D. Werthimer, D. Anderson, J. Cobb, and M. Lebofsky. "SETI@home - Massively distributed computing for SETI", Computing in Science and Engineering 3(1), p. 79, 2001. (訳注: http://www.computer.org/cise/articles/seti.htm)

FOS99

Foster, I. and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kauffman, 1999.

MOL00

Molnar, D. "The SETI@home Problem". ACM Crossroads, Sept. 2000. (http://www.acm.org/crossroads/columns/onpatrol/september2000.html)

ORA01

Oram, Andy (editor). Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O'Reilly and Associates, 2001.

SAR01

Sarmenta, L. F. G. "Sabotage-Tolerance Mechanisms for Volunteer Computing Systems". ACM/IEEE International Symposium on Cluster Computing and the Grid, Brisbane, Australia, May 15-18 2001.

SHO82

Shoch, J. and J. Hupp. "The Worm Programs -- Early Experience with a Distributed Computation". CACM 25(3) pp 172-180, March 1982.

SHO98

Shostak, Seth. Sharing the Universe: Perspectives on Extraterrestrial Life. Berkeley Hills Books, 1998.

SUN90

Sunderam, V.S. "PVM: A Framework for Parallel Distributed Programming". Concurrency: Practice and Experience, 2(4) pp. 315-339, Dec. 1990.

WER97

Werthimer, Bowyer, Ng, Donnelly, Cobb, Lampton and Airieau (1997). The Berkeley SETI Program: SERENDIP IV Instrumentation; in the book Astronomical and Biochemical Origins and the Search for Life in the Universe. Cosmovici, Bowyer and Werthimer, editors.