情報処理学会プログラミング研究会 発表資料 2003 年 8 月 4 日

1

計算機資源の流通および集約のための P2P ミドルウェア
首
田

藤
中

一
良

幸†
夫†

大
関

西
口

丈
智

治†
嗣†

PC をはじめとする個人情報機器の計算能力やストレージといった資源を，個人間で融通，共有し，ひいては集約して分散処理を行うためのミドルウェア P3 の設計と実装を述べる．自由な並列プログ
ラミングを可能とするために，通信には，オーバレイネットワークを提供する P2P 通信ライブラリ
具体的には JXTA を採用した．本発表では，計算機資源の授受や，集約しての分散処理という目的に対して，P2P 通信ライブラリの提供するピアグループや発見などの諸概念をいかに適用するかを提案する．一方，P2P 通信ライブラリの諸機能は通信性能を犠牲にしていることが予想される．そこで，基本性能とアプリケーションの実行性能を測定し，高スループット計算という目的への適合性と，本ミドルウェアで効率の向上を図ることが可能なアプリケーションの条件を調べた．現実装は，
100 × 106 bps の帯域幅を十分活用できること，部分問題あたりの処理時間が 1 秒以下であっても 32
台で 20 倍以上の性能向上率は達成できることがわかった．一方で，部分問題 1 つの配布と回収に10 ∼ 30 ミリ秒を要しており，単一のジョブに数万台規模の計算機を参加させるためには通信遅延の低減が不可避であることもわかった．

P2P-based Middleware enabling Transfer and Aggregation ofComputational Resources
Kazuyuki Shudo,† Joji Onishi,† Yoshio Tanaka†
and Satoshi Sekiguchi†This presentation describes the design and implementation of P2P-based middleware fortransfer and aggregation of computational resources. We adopted a P2P communication software, JXTA, as the communication library in order to allow application programmers to write
programs in any model of parallel programming. P2P communication presents an overlay network where any computer can communicate with each other directly. In this presentation,
we proposes an application method of useful concepts that JXTA provides to goals of our
middleware. The applied concepts are “peer groups” and “discovery”, and our initial goals
include transfer of resources and distributed high-throughput computation by aggregating
those resources. On the other hand, it is natural to be inferred that such a P2P communication software imposes certain amount of overhead on our middleware in communication
performance. Then we measured communication performance of parallel programming library
our middleware provides and throughput of an application program in diﬀerent conditions.
The results of these experiments outlined conformity of the implemented middleware withhigh-throughput computation and desirable conditions of applications for improvement in
performance. The current implementation of this framework can fully utilize a bandwidth of
100 × 106 bps and shows a speed-up ratio of over 20 times with 32 computers even in casethat the granularity of subproblems is adequately ﬁne as less than a second.

1. は じ め にとして売ろうというアプリケーションサービスプロバ

計算能力やストレージなど，自らが必要とするだけの利用量に応じた課金を行おうというユーティリティの計算機資源を，個人や組織で所有しておくのではな

コンピューティングの提唱は，そのあらわれである．

イダ（ASP）の出現や，電気，水道のようにサービス

く，ネットワークを通して融通，流通させようという取PC クラスタなどの高性能かつ稀少な機器について

り組みが活発になっている．ソフトウェアをサービス

は，Globus Toolkit1) などグリッドミドルウェアの認† 産業技術総合研究所
National Institute of Advanced Industrial Science andTechnology

証，認可機能を利用しての組織間での融通が始まっている．融通を受けた計算機や実験機器を連係させての，大規模な計算や実験が試みられてきた．

2
一方，PC などの個人情報機器については，資源の理ソフトウェアについて説明する．4 章では，アプリ

融通と連係は，様々な点について限定された形で行

ケーションプログラマが並列プログラミングに用いるわれている．利用権（アカウント）の発行による資支援ライブラリについて説明する．5 章では，性能測源の提供では，提供側の手間が大きい上に，機器間の定の結果を示して本ミドルウェアの性能を評価する．

連係も難しい．SETI@home2),3) や distributed.net4) ，最後に，6 章で本ミドルウェアを関連研究と比較し，7

GIMPS5) に代表されるインターネット上分散処理プ
ロジェクトでは，アプリケーションプログラムを用意できるのはプロジェクトの運営者のみであり，参加者
は一方的に計算能力を提供するだけである．

章で本研究の成果をまとめる．

2. P2P 通信ライブラリの活用法
昨今の IPv4 インターネットでは，通信の相手や方そこで，我々は，PC をはじめとする個人情報機器向に大きな制約がある．多くの計算機にプライベートの資源をネットワーク経由で容易に授受し，自由な並アドレス空間から IP アドレスが割り当てられており，

列プログラミングでそれら計算機資源を連係，集約し異なる LAN に属するそれら計算機間では，直接通信て活用するためのミドルウェア P3（Personal Powerを行うことはできない．また，NAT，NAPT ゲート

Plant）を開発している．資源提供者側は，自らの意

ウェイがあっても，通信の開始はプライベートな計算

志で，どういったジョブに資源を提供するのかを決め機側からに限定されている場合が多い．

ることができる．資源利用者側が受け取った計算機資通信の相手や方向に制約があったのでは，分散処理源の利用法としては，まずは並列処理，特に高スルーの際の計算機間通信のパターン，ひいては並列プログ

プット計算を想定して開発を進めている．

ラミングモデルが限定されてしまう．例えば，マスタ・現在のインターネットでは，通信可能な相手や通信

ワーカ型並列処理に限定すれば，ワーカ間で直接通信の方向に制約があることが一般的であり，このため，
TCP/IP をそのまま利用したのでは，並列処理の通信パターン，プログラミングモデルが制限されてしまう．
我々は，通信に P2P 通信ライブラリの提供するオー
バレイネットワークを利用することで，この問題を解できる必要はない．しかしそれでも，マスタ側プログ決した．オーバレイネットワーク上では，任意の計算

方向通信が必要となる．

機間での双方向通信が可能となる．

ラムは全ワーカとの通信が可能な計算機に割り当てる必要がある．つまり，ジョブ割り当てに制約が課せられる．メッセージパッシングモデルの並列プログラミ
ングまで許したければ，結局，任意の計算機間での双本ミドルウェアは自由な並列プログラミングを目標

また，P2P 通信ライブラリの提供する各種の概念としている．そのため，通信相手，方向の制約は許容

は，ジョブや計算機の発見や，特定のジョブに関係すできない．そこで，オーバレイネットワークを提供する計算機群への同報通信などに，自然に適用でき，有る P2P 通信ライブラリを採用した．オーバレイネッ

効に活用できる．本発表では，発見機構およびピアグ

トワークは，現 IPv4 インターネットや Bluetooth 等，

ループといった概念を本ミドルウェアの目的に対して下位のネットワークに通信相手や方向の制約があろう

いかに適用するかを提案する．

とも，その上位層で，任意の計算機（ピア）間での双一方で，P2P 通信ライブラリを用いた場合，上述

方向通信機能を提供する．

の諸機能のために，通信性能が犠牲になることが予想

具体的な P2P 通信ライブラリとしては，利用者ができる．そこで，本ミドルウェアが提供する並列プロ多いことや，利用するためのプログラミングインタ

グラミング支援ライブラリの基本性能と，アプリケー

フェースがほぼ固定されていることから，JXTA6) をション実行性能を測定した．支援ライブラリが，目的採用した．双方向通信などのオーバレイネットワークとする高スループット計算に耐えるものであるかどうの恩恵をあらゆる局面で享受するために，本ミドルかを確認し，本ミドルウェアで処理性能の向上を図る

ウェアが行うすべての通信に JXTA を用いている．

ことのできるアプリケーションの条件を考察した．

JXTA は 2001 年に Sun Microsystems 社が立ち上続く 2 章では，P2P 通信ライブラリの提供する諸げたプロジェクトであり，P2P ソフトウェアに共通す

概念，諸機能を本ミドルウェアの目的に対していかに適用するかを提案する．3 章と 4 章は，2 章で提案しる機能を提供するプロトコルを規定している．現在，
Java および C 言語の参照実装が配布されている．参照

た適用法に基づいたミドルウェアの設計と実装の説明

実装自体は，台数のスケーラビリティや処理効率の向である．3 章では，計算機情報やジョブの管理，ジョ上を目指して改良が続けられているが，JXTA の API

ブの実行制御を行うツールやデーモンであるジョブ管は，2001 年末の時点でほぼ固定されている．JXTA を

3用いるプログラムの初回起動時に指定された HTTP
サーバを利用する以外，JXTA は集中サーバをまった
く必要としない．初回起動時には，seed rendezvousと呼ばれるピアのネットワーク上位置を取得する．

JXTA が提供するオーバレイネットワーク上では，計算機はピア ID で識別され，通信メッセージの送信
先はピア ID で指示される．ピアはピアグループを作成することができ，複数のピアグループに参加でき
る．ピアグループ内では，他のピアやピアグループ，
また，通信手段であるパイプを発見することができ

図 1 Host のシェルを用いた受け入れジョブの選択
Fig. 1 Job selection using Host’s shell.

る．JXTA の実装自体は下位の通信プロトコルとして

TCP や HTTP，IP マルチキャストなどを利用する
が，JXTA の利用者はそれを意識する必要はなく，任意のピアを相手に reliable，unreliable 通信を行える．
2.1 JXTA の諸概念の適用法
オーバレイネットワーク上の双方向通信といった恩恵があるだけでなく，JXTA の提供する諸概念は，本ミドルウェアの要件に対して自然に適用して有効に活かせる．本節では，その適用法を提案する．

図 2 Controller のシェルを用いたジョブの投入
Fig. 2 Job submission using Controller’s shell.

2.1.1 ピアグループ
並列処理では，複数の計算機に対する実行制御や，全計算機へのブロードキャストなど，同報通信がしばしば必要となる．これを一対一通信だけで行うと，台数に比例した多数回の通信が発生して効率が悪い．そている．ジョブのピアグループを発見した提供者は，

こで，ジョブ（投入されたアプリケーションとデータ発見の機構は，資源提供者によるジョブの発見だけの組）ごとにピアグループを作成し，そのピアグルー

でなく，計算機の発見にも利用している．資源利用者

プ中で，JXTA のピアグループ内同報通信機能を用いは，発見機構を利用して利用可能な計算機の一覧を取て同報通信を行う．

得する．得られた計算機一覧は，資源利用者に提示さまた，アプリケーション自体や入力ファイルの配布
も，このピアグループ内で行う．これらファイルの配

自らの意志や，何らかのポリシーに基づいて，当該ピ
アグループに参加するか否かを決めることができる．

れるだけでなく，メッセージパッシング型並列アプリ
ケーション（4 章）の起動先指定に用いられる．

布は，JXTA のファイル共有サービス CMS を用いてまた，逆に，資源提供者による資源利用者の発見も行う（3.1 節）．共有を始める際に行われる広報の到行われる．これにより，資源提供側では，資源利用者

達範囲は，ジョブのピアグループ内であり，ちょうどのネットワーク上位置（IP アドレス等）を自動的に当該ファイルを必要とする計算機群と一致させること取得でき，人手での設定が不要となった．

ができる．

3. ジョブ管理機構の設計と実装

2.1.2 発見
計算機資源の利用者には，自由なプログラミングでの他者の計算機群の利用を可能としたい．一方で，計よびツールと，起動されたアプリケーションの並列処

算機資源の提供者，つまり所有者には，その資源の使理を支援する各種のライブラリから成る．本章では前用目的を決める，選ぶ権利が留保されるべきであろう．

者を，次章では後者を説明する．

つまり，提供者は，資源を欲しているジョブとその属るべきである．本ミドルウェアはこれを可能としてお3.1 ジョブ管理ソフトウェア
アプリケーションプログラムの配布や，ジョブの起動，停止といったジョブ管理は，次のプログラム群をり（3.1 節），重要な特徴のひとつである（6 章）．

用いて行う．

性一覧を取得し，自身の資源を提供する先を決められそこで，資源利用者が作成，広報したジョブのピア
グループを，資源提供者が発見する，という方式を採っ

本ミドルウェアは，ジョブ管理のためのデーモンお

Host 資源提供者が起動しておくデーモンプログラ
ムである．ジョブのピアグループを発見し，資源

4

Host

Host

Host
Host
Controller

Job Peer Group

Controller(3) Share application code in the groupwith JXTA CMS service

Host

Host

Controller
Job Peer Group

Application
Application
Code
Code

Controller

Job Peer Group(1) Create a Job Peer Group

Controller(2) Join the Job Peer Group

Job Peer Group

Base Peer GroupNet Peer Group(always existing JXTA’s base group)

Base Peer Group

図 4 ジョブ投入時の Controller の処理
Fig. 4 Job submission process by Controller.

図 3 ジョブ管理ソフトウェアと関係するピアグループの構成
Fig. 3 Organization of job management software andrelated peer groups.

提供者に提示する．提供者は，シェル（図 1）を用いて，実行を受け入れるジョブを選択できる．

Controller 資源利用者が使用するツールである．これを用いて，アプリケーションプログラムを指定
し，ジョブとして投入する（図 2）．
Host と Controller が参加するピアグループを図 3に示す．図中のベースピアグループは本ミドルウェアの既定のピアグループであり，すべての Host，Con-

troller が起動直後に参加する．
以下，アプリケーションの開発からジョブの実行ま

図 5 Controller のシェル上に表示された Host 群
Fig. 5 Job submission using Controller’s shell.

での過程を述べる．

のファイルは，ジョブピアグループ内で発見および取3.1.1 アプリケーション開発
アプリケーションプログラムは Java 言語で開発し，コンパイルして JAR 形式のアーカイブに格納しておく．この JAR ファイルと入力データファイルを，Con-得され得る状態になる．
次に資源利用者が Controller を用いて行う操作は，ジョブの起動である．投入するアプリケーションが，マスタ・ワーカ（4.3 節）のように，起動後であってtroller を用いてジョブとして投入することになる．
アプリケーションは，単に各 Host 上で起動だけされればよいのであれば，通常のスタンドアロン Java
プログラムと同様に，main メソッドさえ持っていればよい．Host 間での通信が必要であったり，並列処

も Host のジョブへの参加を受け入れ得る支援ライブ

理が目的であるなら，4 章で述べる何種類かのプログ

いている場合には，すぐに実行を開始するわけにはいラミングインタフェースを利用できる．

かない．ジョブを投入したこの時点では，Host 群は3.1.2 ジョブの投入
資源利用者が Controller を用いてジョブ，すなわ
ちアプリケーションプログラムと入力データファイル

ラリを用いていれば，この時点で起動を指示して問題はない．しかし，メッセージ・パッシング（4.2 節）といった，起動時にはジョブピアグループにいくつかのHost が参加している必要がある支援ライブラリを用まだ当該ジョブピアグループに参加していないからである．Host 群の参加を確認できてから，起動の指示を出す必要がある．

を投入した際の Controller の処理を図 4 に示す．ま

Host 群の参加確認は，Controller のシェルを目視ず，Controller は（1）ジョブのためのピアグループ

して行う．シェル上に Host 群の名前が表示されていを作成し，（2）そのピアグループに参加する．続いて，る様子を図 5 に示す．Controller は，資源利用者があ

当該ジョブピアグループ内で，JXTA のファイル共有

らかじめ指定しておいたジョブ起動の条件に従って自サービス CMS（Content Management Service）を動的に起動を行う機能を備えることが望ましい．

用いて，アプリケーションと入力ファイルをジョブピ
アグループ内で共有する．この処理によって，これら

3.1.3 ジョブへの参加
資源提供者がデーモンプログラム Host のシェルを

5(4) Discover Application code

(1) Discover Job Peer Groups(5) Obtain the code from a Controller
Application
Application
Code
Code

(2) Decide to join a discovered job

Host
Host

Job Peer Group

Host
Host

(3) Join the Job Peer Group

Base Peer Group

図 6 ジョブ参加時の Host の処理
Fig. 6 Job participation process by Host.

アプリケーション アプリケーション アプリケーション

マスタ・ワーカ API

マスタ・ワーカ
ライブラリ

マスタ・ワーカ
エミュレータ オブジェクト
パッシング
エミュレータ(obsolete)

メッセージパッシング API

メッセージパッシング 他の
ライブラリ
ライブラリ
オブジェクトパッシング
ライブラリ
JXTA

図 7 並列プログラミング支援ライブラリ
Fig. 7 Libraries supporting parallel programming.

は，アプリケーションプログラマが，通信に必要な手
続きや実際の実行環境の詳細を気にすることなく，ア用いてジョブの実行を受け入れる際の，Host の処理をルゴリズムの記述に専念できるようにすることである．

図 6 に示す．まず，Host は（1）ジョブピアグループ

現実装が提供している支援ライブラリの構成を図 7を発見する．発見されたジョブピアグループが Hostに示す．図中で長方形や円が上下に接している箇所は，のシェル（図 1）に表示される．資源提供者は，ジョ上のソフトウェアが下位のソフトウェアを直接利用すブの名前，投入者といった属性を見て，（2）そのジョることを示している．

るのであれば，シェルを用いて，その旨の指示をする．

4.1 オブジェクトパッシングライブラリ
図 7 中のライブラリのうち，アプリケーションプ

ブの実行を受け入れるか否かを判断できる．受け入れ（3）ジョブピアグループに参指示を受けた Host は，ログラマが直接利用するのは，マスタ・ワーカおよび

加し，当該ピアグループ内にてアプリケーションプロ

メッセージパッシングである．両ライブラリとも，オ（5）取得する．
グラムを（4）発見し，ブジェクトパッシングライブラリを用いて実装されてこのように，資源提供者が人手で選択しない限り
Host がジョブに参加しないのでは，提供者の労力がて，Java のオブジェクトを送受信するライブラリで大きく，資源の提供はなかなか進まないだろう．そこある．図 7 にその API を示す．オブジェクトはシリいる．これは，通信相手を JXTA のピア ID で識別し

で，資源提供者が記述したポリシーに従って Host がアライザを用いてバイト列に変換され，JXTA のメッ

自動的に参加ジョブを決定できるようにすることを計

セージに埋め込まれる．オブジェクトパッシングライ

画している．現実装では，Host の自動運転を行う場合

ブラリのインスタンスは，特定のピアグループ内で動は，あらゆるジョブへの参加というポリシーだけが指作するように初期化される．broadcast メソッドを呼定できる．本ミドルウェアを，インターネット上でのぶことで，そのピアグループ内の全ピアに対する一斉資源授受ではなく組織内計算機群の集中制御に利用す送信を行うことが可能である．

る場合，Host の自動運転およびそのためのポリシー

オブジェクトパッシング API は，メッセージの送受設定機能が重要となろう．

信という多くのプログラマにとってごく一般的な概念

3.2 ジョブの起動と停止さえ理解していれば容易に利用できる．一方，JXTA の

続いて，資源利用者は，Controller を用いて，起動通信機構であるパイプを直接利用するためには，JXTAの指示を行う．この指示は，ジョブピアグループ内同特有のいくつかの概念を理解し，広告の作成，広報，

報通信で各 Host に伝達される．また，実行停止の指発見などを行わなければならない．オブジェクトパッ

示も任意の時点で行える．

シング API が JXTA の通信 API の繁雑さを吸収し4. 並列プログラミング支援ライブラリているため，マスタ・ワーカといった，並列処理のパ

本章では，本ミドルウェア向けにアプリケーションのとなっている．

ターンに応じた各種支援ライブラリの開発は容易なもいる並列プログラミング支援ライブラリについて説明

4.2 メッセージパッシングライブラリ
メッセージパッシング API は，オブジェクトパッ

する．現実装は，アプリケーションプログラマ向けに，

シング API と同様に，Host 間でオブジェクトを送受メッセージパッシングとマスタ・ワーカという 2 種類信するための API である．オブジェクトパッシング
API との唯一の違いは，通信相手の識別方法である．

を開発する際に用いる API と，その API を実装しての API を提供している．これら支援ライブラリの目的6interface ObjectPassing {void send(PeerID receiver, Serializable obj);
void broadcast(Serializable obj);
Envelope recv(PeerID sender);Envelope recv(PeerID sender, long timeout);class AWorker implements Worker {void init(Serializable initData) {// initialize this worker instance}
ResultSet process(ProblemSet p) {// process a subproblem and// return the result}// receive a message from anyone
Envelope recv();
Envelope recv(long timeout);// check if a message is available
boolean available();boolean available(PeerID sender);// register and unregister a message listenervoid addObjectPassingListener(
ObjectPassingListener listener);void removeObjectPassingListener(
ObjectPassingListener listener);}
図 8 オブジェクトパッシング API
Fig. 8 API of object passing libarary.

}
図 10 ワーカ側アプリケーションプログラムの構造
Fig. 10 Worker side of an application program complying
with master-worker API.

て，ワーカ側プログラムと，問題全体から部分問題を作成してワーカ群に向けて投入するマスタ側プログラ
ムを記述する．本 API に沿って記述したプログラムの構造を，図 9，図 10 に示す．図 9 がマスタ側プログラム，図 10 がワーカ側プログラムであり，図中の下線で示した箇所は，本 API が規定または提供するclass AMaster implements Master {Serializable getWorkerInitData() {return <data to initialize a worker>;}
start() {while (...) {ProblemSet p = <a subproblem>;// submit a subproblem
submitProblemSet(p);}}}図 9 マスタ側アプリケーションプログラムの構造
Fig. 9 Master side of an application program complying
with master-worker API.

クラス，インタフェース，メソッドを示している．
本ライブラリは，ワーカ側がマスタ側に対して部分問題を要求し，それに対してマスタ側が部分問題を配布するというプロトコルを採用している．そのため，ジョブの起動後にジョブに参加した Host であっても，処理に参加できる．また，ジョブ実行中に Host が離脱しても，ジョブ全体の実行は完遂される．

4.3.1 マスタを動作させる Host の選択
すべての Host は，JXTA の提供するオーバレイネッ
トワーク上で双方向に通信が可能である．ゆえに，どのHost でマスタ側プログラムを起動してもアプリケー
ションは動作する．
しかし，通信のコスト，すなわち遅延の大きさや帯域幅は，送信元と送信先ピアの組や通信方向によって

JXTA のピア ID ではなく，MPI7) と同様に，各 Hostに割り当てられた非負整数 rank で識別する．メッセー
ジパッシングライブラリは rank とピア ID の対応表

まちまちである．マスタ・ワーカ型並列処理では，マを管理し，アプリケーションプログラムとオブジェク

影響を与える．マスタ側プログラムを起動する Host

トパッシングライブラリの間で，rank とピア ID の相は，通信コストを考慮して選ばれることが望ましい．

互変換を行う．

スタ側にトラフィックが集中するため，どの Host でマ
スタ側プログラムを起動するかが，全体の処理効率に現実装は，暫定的に，Host デーモンの起動時に，そ

各 Host の rank は Controller が割り当て，rank との Host ではワーカ側ではなくマスタ側プログラム

ピア ID の対応表をジョブピアグループ内の全 Host

を起動する，という指示を与える方式を採っている．

に配布する．これにより，全 Host が同一の対応表を4.3 マスタ・ワーカライブラリ
マスタ・ワーカ API は，マスタ・ワーカ型の並列

Controller から指示するように変更する予定である．
4.3.2 障害と妨害への対応
ワーカに割り当てた部分問題に対して，必ず処理結果の返戻があることは期待できない．本ミドルウェア

処理の記述を支援する API である．アプリケーショ

はインターネット上の個人情報機器を対象とするため，保持できる．

ンプログラマは，ワーカが処理する部分問題を表すク

Host の故障や電源断，ネットワーク障害，通信メッ

ラスと，その処理結果を表すクラスを定義する．続いセージの喪失を前堤とする必要がある．また，Host 提7
供者が悪意をもって，部分問題の割り当てを受けておド間で，オブジェクトパッシング API を利用した通信

きながら処理結果をマスタに返さないことも想定されを可能とする．オブジェクトパッシング API 上に実る．こういった障害や妨害があった場合でも，すべて装された支援ライブラリ（マスタ・ワーカとメッセーの部分問題が処理されて，ジョブ全体としては実行がジパッシング）をこのエミュレータと組み合わせて利完了されることが望ましい．

用することで，支援ライブラリの API を利用していジョブの実行完了を保証するために，本マスタ・ワー
カライブラリは部分問題の再割り当て機能を備えているアプリケーションプログラムを，計算機 1 台上で動作させることができる．

る．ワーカへ一旦割り当てた部分問題に対して一定時

エミュレータは，アプリケーションプログラムの開間処理結果の返戻がない場合，その部分問題を，再び，発だけでなく，支援ライブラリ自体の開発においてもワーカへの割り当て対象とする．

活用できる．実際に，マスタ・ワーカライブラリの動

悪意ある Host 提供者の存在を前堤とする以上，処理

作確認とデバッグは，オブジェクトパッシングライブ

結果の返戻がない場合だけでなく，虚偽の処理結果がラリのエミュレータ上で行った．エミュレータ上で動マスタに返されることも想定する必要がある．虚偽の作を確認できたマスタ・ワーカライブラリが，そのま返戻があってもジョブ全体として正しい実行結果を得

ま JXTA を用いるオブジェクトパッシングライブラるためには，虚偽を検出する必要がある．このためにリ上で動作し，分散環境でのデバッグを完全に回避では，投票（voting）や抜き取り検査（spot-checking）

きた．

が一般的に行われている8) ．例えば，United Devices
社のインターネット上分散処理プロジェクトは，同一

5. 支援ライブラリの性能評価の部分問題を 5 回配布し，最初に返戻された 2 つの処

本ミドルウェアは，P2P 通信ライブラリを利用し理結果が一致すれば，その結果を正しい結果として採て，その提供する機能の様々な恩恵を受けている．例

用するという投票方式を採っている9) ．

えば，オーバレイネットワーク上での任意計算機間の本マスタ・ワーカライブラリは，投票方式の虚偽検双方向通信や，同一ジョブを実行する Host 群への同出機能を備えている．同一の部分問題を m 個配布し報通信，ジョブ情報と Host 情報の発見による集中管て最初に返戻された n 個の処理結果を照合し，それら理回避などがその代表である．

が一致すれば正しい結果として採用，一致しなければ一方で，これらの機能のためには，通信性能が犠牲再び配布されている個数が m となるようにする．ことなっていることが予想できる．そこで，本ミドルウェ

こで，m と n は調節可能である．m = n = 1 と設定

アの提供する支援ライブラリの通信性能が，目的とすすることで，虚偽検出機能を無効化できる．

る高スループット計算に耐えるものであるかどうか，

この虚偽検出機能は，マスタ側プログラムが悪意あまた，どういったアプリケーションプログラムであれる Host で実行された場合は想定していない．マスタ

ば本ミドルウェア上で効率良い処理が可能であるのか

側プログラムだけは，信頼できる Host，例えば Con-を見積もるために，支援ライブラリの通信性能を測定

troller 使用者が提供する Host で起動する，といった運用での対策を検討している．
マスタ・ワーカライブラリが備える再割り当て機能した．

および虚偽検出機能は，アプリケーションプログラム

た PC クラスタ上で行った．PC 群は 1000BASE-Tとは完全に独立している．すなわち，プログラマがア

イーサネットスイッチで結合されている．OS は Linux

プリケーションを開発する際は，これらの機能につい2.4.19，Java 実行系は Sun Microsystems 社が配布している Java 2 SDK 1.4.2 を用いた．以下の実験では，て意識する必要はまったくない．

実験は，Intel 社 2.4 GHz Xeon プロセッサを 2 つ搭載した PC を計算ノードとし，それを 32 台を備え

4.4 エミュレータ
並列処理プログラムのデバッグは難しい．プログラ
ムが複数の計算機上で動作することに起因する，挙動の監視，把握の難しさが一因である．
そこで，本ミドルウェア向けの並列処理プログラム

装のバージョン 2.1 を用いた．JXTA には，一対一通の計算機 1 台上での動作確認，デバッグを可能とする

ギガビットイーサネット 1000BASE-T の LAN でために，オブジェクトパッシングライブラリのエミュ得られる通信性能は，現在のインターネット上で通常レータを用意した．単一の Java 仮想マシン上のスレッ得られる性能よりはるかに高い．本ミドルウェアの主

特に断わりのない限り HotSpot Client VM を使用している．JXTA の実装としては，Java 2 SE 用参照実信には必ず TCP が使われるよう，HTTP の使用禁止という設定を施した．

8
表 1 通信遅延
Table 1 Communication latency.

120108.0 MB/s

100

TCP（C プログラム）
TCP（Java プログラム）
メッセージパッシング

0.062
0.064
4.5
（ミリ秒）

c）e 80s/
MB（ 60
トッ
プ
ー
ル
ス 40

15.57 MB/s (C)15.38 MB/s (Java)

C言語のプログラム
Java言語のプログラム
1000BASE-T の物理的な帯域幅:
10 ** 9 bps = 119.2 MB/s

20

1210.97 MB/s

JXTA-MPI

100

10 x 10**6 bps

）s
/B 8
（Mト
ップ 6
ー
ル
ス4

1

2

4

8

16

32

64

128

256

512

1024

送受信データサイズ（KB）

100 x 10**6 bps

図 12 TCP のスループット
Fig. 12 TCP throughput.

は低下する．JXTA 参照実装が数百 KB 以上の大きなメッセージを扱う際に，何らかのオーバヘッドがあ2
0105.5 MB/s

ると考えられる．この原因は，今後，より詳細に調査
1

2

4

8

16

32

64

128

256

512

1024

する．メッセージパッシング，または，オブジェクト

図 11 メッセージパッシングライブラリのスループット
Fig. 11 Throughput of message passing library on JXTA.

パッシングライブラリ内で，メッセージを 128 KB 程

送受信データサイズ（KB）

度に分割して送受信することにより，512 KB 以上の
大きなメッセージも，より高いスループットで送受信

要ターゲットであるインターネット環境とは大きな差できると考えられる．

がある．しかし，むしろ，十分に高い性能を持つネッ

比較対象として，図 12 に，TCP を BSD ソケット

トワーク上で実験を行うことによって，本ミドルウェ

インタフェースで直接利用した場合のスループットを

アや JXTA 自体の性能やオーバヘッドを明確に測定示す．TCP は，1 回の送受信データサイズを 1 MBできる．

にした場合，物理的な帯域幅の約 9 割のスループッ

5.1 遅延とスループット
メッセージパッシングライブラリの通信遅延とス
ループットを測定し，TCP のそれと比較した．メッセージパッシングライブラリ，ひいては JXTA による通信は実験環境では TCP で行われるので，この比較トを達成している．それに対し，JXTA を利用する

域幅である 100 × 106 bps をほぼ埋められる程度のスによって，JXTA と支援ライブラリのオーバヘッドを

ループットは達成している．10 × 106 bps であれば，8見積もることができる．

1 バイトを 2 台の計算機間で 1000 回往復させ，要した時間を 2000 で割ることで片道の通信遅延を算出した．結果を表 1 に示す．この実験で用いている程KB という比較的小さい単位での送受信で達成できている．家庭や小規模オフィスのインターネット接続線（1 ∼ 100 × 106 bps）や 100 × 106 bps 程度までの低速な LAN の帯域幅なら，JXTA および支援ライブラリ度の性能を持つ計算機，OS，Java 実行系では，メッの現実装でも充分に活用できることがわかった．

セージパッシングライブラリを用いた通信には 4 ∼ 5
信遅延は，5.2 節で評価するマスタの部分問題処理ス

5.2 マスタの部分問題処理スループット
マスタ・ワーカ型の並列処理では，ワーカ群の処理能力を無駄なく発揮させて効率の良い並列処理を行う

ループットに大きな影響を与えている．

ためには，マスタに集中する，部分問題の配布およびミリ秒を要することがわかった．この比較的大きな通メッセージパッシングライブラリのスループットは，物理的な帯域幅の 1 割弱にとどまっている．とはいえ，それでも，100BASE イーサネットの物理的な帯

スループットは，1 回に送受信するメッセージに含

結果回収処理が律速とならないようにすることが重要

めるデータのサイズを変化させて，2 台の Host 間でである．そのため，単位時間あたりに処理できる部分

100 回往復させて測定した．結果を図 11 に示す．以下では，すべて，キロ（K）は 1000 ではなく 1024，

問題の数，すなわち部分問題処理のスループットが，メガ（M）は 10242 ，以下同様である．データサイズ

マスタ・ワーカライブラリについて，このスループッが 128 KB のときに最もスループットが高くなっておトを求めた．

り，データサイズを大きくすると，再びスループット

マスタ側プログラムの性能を表す重要な指標となる．

測定には，共通鍵暗号方式 RC5 の鍵探索アプリケー

930(1) Request for a subproblem

28.0

25
20
（msec）

MasterMaster

19.6
16.5

15
13.6

10

17.7

18.8

(2) A subproblem(3) A result of the processing

WorkerWorker

図 15 マスタとワーカの間の対話手順
Fig. 15 Communication protocol between master andworker.

13.1

50

を 200 として，配布と回収に要した時間を 200 で割
0

4

8

12
16
20
Number of workers

24

28

32

図 13 部分問題 1 つの配布と結果の回収に要する時間（HotSpot
Client VM 使用）
Fig. 13 Handling time per subproblem with HotSpot
Client VM.

り，部分問題 1 つあたりの配布，回収時間を求めた．

HotSpot Client VM での結果を図 13 に，HotSpot
Server VM での結果を図 14 に示す．
実験結果のうち，最も悪い場合で，部分問題 1 つあたり 28 ミリ秒，最も良い場合には 13 ミリ秒を要している．悪い場合で 1 秒あたり約 35 の部分問題，良い場合で 76 の部分問題を処理したことになる．これは

30

27.1

25

22.1

20.9

（msec）

20

アをインターネット上分散処理に適用する場合を想定

20.2

する．United Devices 社のあるプロジェクトでは，部

15.4

15

13.8

10

分問題配布サーバが取扱う部分問題の数を，1 秒あたり 120 程度に調整している11) ．このスループットが13.4

何秒，何分あたりの平均値かは不明であるが，部分問

50

充分なスループットだろうか．例えば，本ミドルウェ

題配布サーバの性能は，少なくとも，この平均スルー
プットの数倍，数百個/秒には達していると考えるこ
0

4

8

12
16
20
Number of workers

24

28

32

図 14 部分問題 1 つの配布と結果の回収に要する時間（HotSpot
Server VM 使用）
Fig. 14 Handling time per subproblem with HotSpot
Server VM.

とが自然である．単一のジョブに数万台規模のワーカを参加させようとするなら，本ミドルウェアには，現実装と比較しておよそ 101 ∼ 102 倍のスループットが望まれる．
では，ミドルウェアのどの部分が律速なのかを考察する．マスタ，ワーカ間での部分問題および処理結果

ションを用いた．これは，distributed.net の ProjectRC510) で行われている処理を，本ミドルウェアのマ
スタ・ワーカ API を用いて実装したものである．問題として暗号文が 1 つ与えられ，その暗号化に使われの授受は，次の手順で行われる（図 15）．

た鍵を求めるというアプリケーションであり，RC5 がスタは，適当な数の鍵候補を部分問題としてワーカに( 4 ) （以下，繰り返し）
1 つの部分問題について，処理結果がマスタに返戻されるまでに（1）∼（3）の 3 回のメッセージ送受信が行われる．このメッセージ送受信は，マスタ・ワーカ

割り当て，ワーカは与えられたすべての鍵候補についライブラリがオブジェクトパッシングライブラリを用てそれが求める鍵であるかどうかを検証する．

いて行う．ここで，オブジェクトパッシングライブラ

数学的に破られていない以上は，膨大な数の鍵候補を総当たりで試すことが最も効率のよい解法である．マ

ここでは，マスタ・ワーカライブラリの性能測定が

(1)
(2)
(3)

ワーカがマスタに対して，部分問題を要求する．
マスタがワーカに対して，部分問題を送付する．
ワーカがマスタに対して，処理結果を送付する．

リの通信遅延はメッセージパッシングライブラリのそ目的なので，部分問題に含める鍵候補の数を 0 とする

れとほぼ同じ，約 4.5 ミリ秒（5.1 節）であると考えらことで，アプリケーション固有の処理にかかる時間をれる．なぜなら，メッセージパッシングライブラリが可能な限り小さくした．これによって，マスタ・ワー

行う処理は整数値 rank と JXTA のピア ID 間の相互

カライブラリが部分問題の配布と結果回収処理に要し変換だけであり，これはハッシュ表を索くという，4.5

た時間だけを計測できる．ここでは，部分問題の総数

ミリ秒と比較すると無視し得るくらいのごく軽い処理

10
表 2 部分問題 1 つあたりの計算時間
Table 2 Calculation time per subproblem.
部分問題あたりの鍵候補の数（16 進）

0x80000x40000x2000HotSpot
Client VM
1.7
0.84
0.42

HotSpot
Server VM
1.4
0.69
0.36
（秒）

600000部分問題あたりの鍵数 0x8000
部分問題あたりの鍵数 0x4000

500000部分問題あたりの鍵数 0x2000
理想的な性能向上（鍵数 0x8000））400000/秒
数（鍵300000度
速理200000
処

理想的な性能向上（鍵数 0x4000）
理想的な性能向上（鍵数 0x2000）

100000だからである．

0

部分問題 1 つあたり，メッセージ送受信に要する時間
だけで，約 4.5 ミリ秒 × 3 = 13.5 ミリ秒を要すると見積もることができる．これでは，1 秒あたりに処理できる部分問題は，最大でも 1000 ミリ秒 ÷ 13.5 ミリ秒 =約 74 個 に制限されてしまう．

0

4

8

12

16
ワーカの台数

20

24

28

32

図 16

部分問題の粒度に応じたスループットの変化（HotSpot
Client VM 使用）
Fig. 16 Variation in key crunching throughput according to granularities of subproblems (with HotSpot
Client VM).

マスタが処理できる部分問題数を向上させるには，オブジェクトパッシング，および，それが利用する JXTA

700000自体の性能向上が必要であることがわかった．

600000

もっとも，マスタ，ワーカ間プロトコル（図 15）の分問題処理スループットは最高で 1.5 倍まで向上し得）500000
秒/
数400000
鍵（度300000
速理処200000

る．しかし，それでも 101 ∼ 102 倍には大きく及ば100000（3）と（1）を単一のメッセージに含めるという最適化も考えられる．これにより，部分問題 1 つあたりメッ
セージ送受信回数は 3 から 2 となり，マスタによる部

ない．数万台規模のワーカに対応するためには，オブ0

ジェクトパッシングライブラリと JXTA 自体の性能向上は不可避である．
また，ワーカとの通信がマスタ側のボトルネックであるなら，ワーカとの通信を複数のマスタで分担するという方法もある．将来はマスタ群のフェデレーショ

部分問題あたりの鍵数 0x8000
部分問題あたりの鍵数 0x4000
部分問題あたりの鍵数 0x2000
理想的な性能向上（鍵数 0x8000）
理想的な性能向上（鍵数 0x4000）
理想的な性能向上（鍵数 0x2000）

0

4

8

12

16
ワーカの台数

20

24

28

32

図 17

部分問題の粒度に応じたスループットの変化（HotSpot
Server VM 使用）
Fig. 17 Variation in key crunching throughput according to granularities of subproblems (with HotSpot
Server VM).

ンを可能とするために，マスタの設計においては，部
分問題をマスタ外部の DBMS（データベース管理シさせることで行った．部分問題の総数は 200 である．

ステム）に格納しやすい構造を採っている．

それぞれの粒度について，ワーカの台数を 1 から 32

5.3 粒度の細かい部分問題への耐性
ワーカ側プログラムでの部分問題の処理時間が短台まで変化させて実行に要した時間を計測し，単位時

いほど，マスタが部分問題を配布，回収する頻度が高

Client VM での結果を図 16 に，HotSpot Server VM
での結果を図 17 に示す．また，両グラフについて，鍵処理のスループットを並列化効率に置き換えたものを
図 18，図 19 に示す．表 2 には，それぞれの粒度にくなる．そして，その頻度がマスタの部分問題処理ス
ループットを超えると，ワーカは部分問題に飢えて，
ワーカの台数に応じた性能向上は得られなくなる．
マスタ・ワーカライブラリが，どの程度まで計算時間あたりに処理できた鍵候補の数を求めた．HotSpot

ついて，部分問題 1 つあたりの計算時間を示す．

間の短い部分問題，つまり，粒度の細かい部分問題に

部分問題あたりの鍵候補数が 0x4000，0x8000 の場

耐えられるかを見積もるために，いくつかの異なる粒合は 32 台まで性能が向上しているのに対し，0x2000

度について並列化効率を観察した．

の場合，性能向上はワーカ数 24 台で頭打ちとなって

アプリケーションプログラムとしては，5.2 節と同いる．表 2 と合わせて見ることで，部分問題あたりのじ RC5 の鍵探索アプリケーションを用いた．部分問

計算時間が 0.4 秒前後の場合，ワーカ数を増やしてス

題の粒度の調整は，部分問題 1 つあたりに含める鍵

ループットが向上するのは，24 台程度までだという候補の数を 0x8000，0x4000，0x2000（16 進）と変化ことがわかる．

11
表 3 インターネット上での分散処理を目的とするソフトウェアと P3 の比較
Table 3 Comparison between other Internet-wide distributed computing software and P3.
一般利用者による
プログラミングと
ジョブ投入

資源提供者
による
ジョブ選択

通信
プロトコル

アプリケーション
開発言語

並列
プログラミング
モデル

虚偽の
処理結果
検出

P3

yes

yes

JXTA

Java

yes

JNGI
XtremWeb

yes
yes

no
no

GreenTea
Javelin
Bayanihan

yes
yes
yes

no
no
no

JXTA
選択可能
（RMI 等）
RMI
RMI
HORB

Java
ネイティブ
（C 等）
Java
Java
Java

マスタ・ワーカ，
メッセージパッシング
マスタ・ワーカ
分割統治

Ninﬂetdistributed.net
SETI@home

yes
no

no
yes

RMI
HTTP

no

no

HTTP

Java
C，C++，
アセンブリコード不明

32

マスタ・ワーカ
分枝限定モデルマスタ・ワーカ，
BSP
マスタ・ワーカ
分割統治

no
言及なし
不明

分割統治

yes

no
yes

32

部分問題あたりの鍵数 0x8000
2824

部分問題あたりの鍵数 0x4000

28

部分問題あたりの鍵数 0x2000

24

理想的な性能向上

20

率
上16
向
能
性12
4

4

4

8

部分問題あたりの鍵数 0x4000
部分問題あたりの鍵数 0x2000
理想的な性能向上2080

部分問題あたりの鍵数 0x8000

率
上16
向
能
性12

8

0

no
言及なし

12

16
ワーカの台数

20

24

28

32

図 18

部分問題の粒度に応じた並列化効率の変化（HotSpot
Client VM 使用）
Fig. 18 Variation in eﬃciency of parallel key crunchingaccording to granularities of subproblems (with
HotSpot Client VM).

0

0

4

8

12

16
ワーカの台数

20

24

28

32

図 19 部分問題の粒度に応じた並列化効率の変化（HotSpot
Server VM 使用）
Fig. 19 Variation in eﬃciency of parallel key crunchingaccording to granularities of subproblems (with
HotSpot Server VM).

6. 関 連 研 究

織を単位とした選択が可能なソフトウェアもある．し我々は，個人間での計算機資源の授受という目的の究ジョブには資源を提供するが，娯楽目的の音声デー

ためには，以下が重要な要件であると考えている．

タ変換には提供しない，といった要求には対応でき• 誰でも，自由なプログラミングでアプリケーショ
ンプログラムの開発を行えて，他者の計算機に対してジョブとして投入できること．
• 資源提供者が，ジョブを単位として，受け入れる
か否かを決められること．

かしこの粒度での選択では，例えば，A さんの暗号研

ない．

JNGI12) は大規模分散処理向けフレームワークである．本ミドルウェアと同様に，通信プロトコルに JXTAを採用している．しかし，本ミドルウェアとはピアグ
ループの利用法が大きく異なっている．本ミドルウェ

本ミドルウェアはこれらの機能を備えている．表 3 は，

アはジョブごとにピアグループを用意することで，そこれらの観点について，本ミドルウェア P3 と，インのピアグループを，ジョブに関与する全計算機への同ターネット上での分散処理，ひいては，計算機資源の報通信とアプリケーションプログラム配布のための領募集や授受を目的とするソフトウェアを比較したもの

域として活用している（2.1 節）．一方，JNGI は，一である．

定数までの計算機群を効率良く集中管理するための後者については，資源提供者がジョブの配布元計算

領域としてピアグループを活用している．あるピアグ

機を選択でき，それによって配布元計算機や配布元組

ループ内の計算機が増え過ぎないように，複数のピア12
グループを階層的に管理する方式も提案している．こ部分問題が処理されるので，単純な分割統治型の並列の方式では，本ミドルウェアとは異なり，資源提供者

処理を記述できる．

がジョブを選ぶことはできない．また，2003 年 7 月

Bayanihan17) は，プログラミングモデルとして，マ
スタ・ワーカだけでなく，BSP（Bulk Synchronous

末時点の実装は，計算機管理のためのピアグループをGroup というピアグループ上で全計算機が通信を行うようになっている．
論文12) では JNGI を用いた分散処理で得られた性能も報告されている．実験に用いられているアプリケー

Parallel）18) をサポートしている．これは，計算，大域通信，バリア同期の 3 ステップを繰り返して計算を進めるというモデルであり，任意のワーカ間での直接通信を記述できるが，通信結果がローカルメモリに反映されるのはバリア同期後になるというモデルである．

ションプログラムは，1 つの部分問題の処理に 130 秒

実際のワーカ間通信はマスタが中継しており，ワーカという長い時間を要するものであり，通信性能に対す間で直接通信を行っているわけではない．

る要求は非常に低い．この実験では，JXTA が分散

distributed.net4) は，共通鍵方式 RC5 の鍵探索など，いくつかのアプリケーションプログラムについて
インターネット上分散処理プロジェクトを主宰していまったく作らず，JXTA では常に存在する Net Peer

処理に耐える性能を達成していたのか否かは評価できていない．また，Solaris，Windows 2000，RedHat

Linux を合わせて最大 150 ワーカ用いるという非均質環境での実験にもかかわらず，結果として示されている性能向上率の基準が述べられていない．
XtremWeb13) も，インターネット上での大規模分散処理を目的としたソフトウェアである．複数のアプリ

る．SETI@home2),3) とは異なり，資源提供者は，ソフトウェアを起動する際に，実行を行うアプリケーショ
ンプログラムを指定できる．
インターネット上での大規模分散処理において虚偽の処理結果を検出する方法として，投票（voting）とケーションに対応することと高い性能を発揮すること

抜き取り検査（spot-checking）が提案されている8) ．

がその設計目標である．投入可能なアプリケーションプ

また，部分問題の割り当て方法，処理結果の正しさをログラムはコンパイル済みのネイティブコードである．

確認する方法，部分問題の処理に対する報酬の支払い

並列処理の方式は，あらかじめ用意しておいた多数の方を調節することで，虚偽の処理結果を返戻すること

入力ファイルを多数の計算機に配布して処理させるとで得られる利得を，虚偽発覚のリスクよりも小さくすいう，単純な分割統治である．計算機間の通信プロトコ

るという方法も検討されている19) ．

ルは差し替えが可能であり，現在，TCP，Java RMI，

XML-RPC の実装が用意されている．XtremWeb 自体が提供しているアプリケーションのプログラミング
モデルは以上の通りであるが，耐故障性を備えたメッ

CPM（Compute Power Market）20) は，計算機資源の提供者と利用者それぞれが条件を提示してお互いを見つけるための市場の枠組である．その目的は需要と供給を仲介することであり，CPM 自体は並列処理

セージパッシングライブラリ MPICH-V14) を用いるを支援する機能は用意していない．

アプリケーションプログラムを，XtremWeb を用いてGreenTea (GT) Distributed Network Computing
Platform15) は，米 GreenTea Technologies 社が開発

Phoenix21),22) は，メッセージパッシング型の並列処理において，処理の途中での計算機の参加，離脱を可能とする並列プログラミングモデルである．MPI7)であれば，送信先，送信元の識別子，すなわち通信のエ

しているソフトウェアである．通信には Java RMI を

ンドポイントは，各計算機で起動されるプロセスごと用いており，IP アドレス等計算機情報の管理，部分にひとつずつ整数値 rank が割り当てられる．Phoenix

問題の配布などは，GTServer と呼ばれるサーバプロの場合，例えば 0 から 232 − 1 といった膨大な数のエグラムが行う．部分問題をどのワーカに割り当てるか

ンドポイントを，各プロセスで分担して保持する．新は，GTServer 内のスケジューラに決めさせることも，

たなプロセスが計算に参加してきた場合は，エンドポ

アプリケーションプログラムが自身で指定することもイントを分け与え，離脱する際は他のプロセスに対し可能となっている．

て返却することで，参加と離脱を可能としている．本

多数の計算機上で起動するという実験が行われている．

16)

Javelin 2.0

は，多数の部分問題を計算機群に配ミドルウェアが提供しているメッセージパッシングプ

布するという点では他のソフトウェアと同じであるが，ログラミングモデルは一般的かつ単純なものであり，分枝限定計算モデルを採っている点に特徴がある．プ

ジョブ実行中の Host の参加，離脱は考慮していない．

ログラミングモデルも計算モデルを反映したものと本ミドルウェア用の支援ライブラリとして Phoenix のなっている．枝刈りをまったく行わなければすべてのプログラミングモデルを設計することは興味深い課題

13
である．

7. ま と め
PC に代表される個人情報機器の計算機資源を個人間で授受し，ひいては集約して分散処理を行うためのミドルウェア P3 の設計と実装を述べた．P3 は，自由な並列プログラミングを可能とするために，P2P 通信
ライブラリ JXTA を採用している．本発表では，そのJXTA が P2P ソフトウェア向けに提供している諸概念を本ミドルウェアの目的に対していかに適用するかを提案した．また，提案した適用法に基づいて実装したミドルウェアについて，基本的な通信性能やマスタ・
ワーカ型並列処理用ライブラリのスループット，実際のアプリケーションでの性能向上率を測定し，報告した．スループットは 100BASE イーサネットの帯域幅を埋められる程度であること，マスタ・ワーカライブ
ラリは，部分問題 1 つの配布，結果回収に 10 ∼ 30 ミ
リ秒を要しており，部分問題の粒度が細かい場合にはこのスループットが律速となると予想されること，また，粒度によっては良好な性能向上が得られることがわかった．
本ミドルウェア開発の目標は，アイディアの検証や試作ではなく，実用的な有用性，品質の達成である．
そのため，本発表では言及していないものも含め，数多くの課題が残されている．参加ジョブ選択ポリシー（3.1 節）の記述方法や，ジョブのチェックポインティ
ングを支援する方法，ジョブが使用する計算機資源を制限する方法といった研究課題だけでなく，容易なイ
ンストールや，ミドルウェア自体の自動更新など，実用上は欠かせない要件の達成にも取り組んでいく．
謝辞 本研究の一部は，情報処理振興事業協会の次世代ソフトウェア開発事業の委託業務として実施さ
れた．

参

考 文

献

1) Foster, I. and Kesselman, C.: Globus: A Metacomputing Infrastructure Toolkit, Int’l Journal
on Supercomputer Applications, Vol. 11, No. 2,
pp. 115–128 (1997).
2) Korpela, E., Werthimer, D., Anderson, D.,
Cobb, J. and Lebofsky, M.: SETI@home: Massively Distributed Computing for SETI, Computing in Science and Engineering, Vol.3, No.1,
pp. 78–83 (2001).
3) SETI@home: SETI@home: Search for Extraterrestrial Intelligence at Home.
http://setiathome.ssl.berkeley.edu/.
4) distributed.net: distributed.net: Node Zero.

http://www.distributed.net/.
5) GIMPS: The Great Internet Mersenne Prime
Search. http://www.mersenne.org/.
6) Project JXTA: jxta.org.
http://www.jxta.org/.
7) Message Passing Interface Forum: MPI-2:
Extensions to the Message-Passing Interface(1997).
8) Sarmenta, L. F.G.: Sabotage-Tolerance Mechanisms for Volunteer Computing Systems, Future Generation Computer Systems (FGCS),
Vol. 18, No. 4, pp. 561–572 (2002).
9) Patel, P.: Personal communication (2002).
10) distributed.net: Project RC5.
http://www.distributed.net/rc5/.
11) Ueno, K.: Personal communication (2003).
12) Jerome Verbeke, Neelakanth Nadgir, G. R. andSharapov, I.: Framework for Peer-to-Peer Distributed Computing in a Heterogeneous, Decentralized Environment, Proc. of Third International Workshop on Grid Computing (GRID
2002), pp. 1–12 (2002).
13) Fedak, G., Germain, C., Néri, V. and Cappello, F.: XtremWeb: A Generic Global Computing System, CCGrid2001 Special Session
Global Computing on Personal Devices (2001).
14) Bosilca, G., Bouteiller, A., Cappello, F., Djilali, S., Fedak, G., Germain, C., Herault, T.,
Lemarinier, P., Lodygensky, O., Magniette, F.,
Neri, V. and Selikhov, A.: MPICH-V: Toward a
Scalable Fault Tolerant MPI for Volatile Nodes,
Proc. SC2002: International Conference forHigh Performance Networking and Computing(2002).
15) GreenTea Technologies, Inc.: GreenTea Platform Whitepaper (2002).
16) Neary, M. O., Phipps, A., Richman, S. andCappello, P.: Javelin 2.0: Java-Based Parallel
Computing on the Internet, Lecture Notes in
Computer Science (LNCS) for 6th Int’l EuroPar Conference (Euro-Par 2000), Vol. 1900,
Springer Verlag, pp. 1231–1238 (2000).
17) Sarmenta, L. F. G. and Hirano, S.: Bayanihan:
Building and Studying Web-based Volunteer
Computing Systems using Java, Future Generation Computer Systems (FGCS), Vol. 15,
No. 5-6, pp. 675–686 (1999).
18) Sarmenta, L. F. G.: An Adaptive, Faulttolerant Implementation of BSP for Java-based
Volunteer Computing Systems, Lecture Notes
on Computer Science (LNCS) for IPPS’99
Workshop on Java for Parallel and Distributed
Computing, Vol.1586, Springer Verlag, pp.763–
780 (1999).

1419) Golle, P. and Stubblebine, S.: Distributed
Computing with Payout: Task Assignment for
Financial- and Strong- Security, Proc. Financial Cryptography ’01 (FC01) (2001).
20) Buyya, R. and Vazhkudai, S.: Compute Power
Market: Towards a Market-Oriented Grid,
Proc. 1st International Conference on Cluster
Computing and the Grid (CCGrid2001) (2001).
21) Taura, K., Kaneda, K., Endo, T. andYonezawa, A.: Phoenix : a Parallel Programming Model for Accommodating Dynamically Joining/Leaving Resources, Proc. of
ACM SIGPLAN Symposium on Principles andPractice of Parallel Programming (PPoPP’03)(2003).
22) 田浦健次朗: Phoenix: 動的な資源の増減をサポートする並列計算プラットフォーム, 情報処理学会
研究報告, 2001-HPC-87-24, pp. 135–140 (2001).