計算機資源の流通および集約のための P2P ミドルウェア
首藤一幸 大西丈治
田中良夫 関口智嗣
産業技術総合研究所 グリッド研究センター

背景
計算機資源の流通に向けた動きが活発化
w 資源: CPU能力、ストレージ、デバイス等
n

ASP (アプリケーションサービスプロバイダ) の出現

nユーティリティコンピューティングの提唱
w 電気、水道のように、利用料に応じた課金nGlobus Toolkitの認証、認可機能を利用した、PCクラスタ等の組織間での融通
w スパコンのグリッドによる大規模な科学技術計算
n 他組織へのジョブ投入や、MPICH-G2, Ninf-Gを用いた組織をまたいだ分散実行

動機
PC をはじめとする個人情報機器では…
n

インターネット上分散処理プロジェクト
w i.e. SETI@home, distributed.net, GIMPS, …
w 運営者だけがアプリケーションプログラムを用意できる。
参加者は一方的に計算能力を提供する。

nアカウントの発行
w 計算機資源 提供側の手間が大きい。
w 単一目的に機器群を連係させることは難しい。

n i.e. 並列処理, センサーからのデータを別計算機で処理

計算機資源 授受のためのミドルウェア
P3: Personal Power Plant
個人情報機器の資源を容易に授受し、n 自由な並列プログラミングでそれらを連係、集約して活用するためのミドルウェア。
n 資源提供者は、自らの意志で、どういった処理に資源を提供するのかを決めることができる。
nw 授受における重要な要件であり、P3 の特徴。

n応用例
w 計算してくれる人、ストレージを貸してくれる人、カメラ等センサーを使わせてくれる人 （資源提供者）の募集
w インターネット上分散処理プロジェクトの運営
w 組織内遊休 PC の cycle harvestingn

当面のターゲットは、PC 群を用いた並列・分散処理

オーバレイネットワークの利用
自由な並列プログラミングのために…
n

昨今の IPv4 インターネットには、通信の相手や方向に制約がある。
w Privateアドレス, DHCP: インターネット側から計算機を識別できない。NAT,NAPTゲートウェイがあっても、通信開始の方向は一方向。
w ファイアウォール: IPv6 だろうと必要。

n通信には、P2P 通信ライブラリが提供するオーバレイネットワークを利用。
w 下位通信網（TCP/IP, Bluetooth等）の差異、混在や、通信相手、方向の制約を吸収する。
w 任意の計算機（ピア）間の双方向通信機能を提供する。

n

本発表では、P2P通信ライブラリが提供する各種の概念を、本ミドルウェアの目的に対していかに適用するかを提案する。

P2P 通信ライブラリJXTAJXTA (じゃくすた) を採用
P2P ソフトウェアに共通の機能を提供するプロトコ
ル、参照実装 (Java, C)、プロジェクト。
n Sun Microsystems 社が 2001年に公開した。
n （比較的）安心して使える理由：
nw API が、2001年末の時点でほぼ固定されている。
w 利用者が多い。
njxta.org でのユーザ登録は15,000 以上。

w PCから携帯電話器まで、様々な規模の計算機で稼動する。
w ライセンスが緩い：BSD由来である Apache と同じ内容。

JXTA の提供するオーバレイネットワーク“Project JXTA 2.0 Super-Peer
Virtual Network” 中の図

計算機はピアIDで識別される。
n

JXTAの実装は通信にTCPやHTTP, IPマルチキャストなどを用いるが、JXTAの利用者はそれを意識せずに、任意のピアを相手に通信を行う。

ピアはピアグループを作成でき、複数のピアグループに参加できる。
Peer ID

Peer ID

Peer ID

Peer ID

Peer ID

Peer IDJXTA Virtual Network
Physical Network

Peer ID

Peer ID

Virtual Mapping

TCP/IP
NAT
FirewallHTTPJXTAの諸概念の適用法
JXTAが提供する諸概念を、いかに本ミドルウェアの目的に適用するかを提案する。
w ピアグループ、発見「ピアグループ」
nn

並列処理には同報通信が欠かせない。
ジョブごとにピアグループを作成し、計算中のブロードキャストや、実行制御を、ピアグループ内同報通信によって行う。
w cf. JNGI: 計算機を集合的に管理する目的にピアグループを使用。

nまた、このピアグループ内で、アプリケーションプログラムの配布を行う。
w JXTA のファイル共有サービス CMS (Content Management Service) を使用。
w そのピアグループが、ファイルの配布範囲となる。

→ ファイルを必要とする計算機と一致。

JXTAの諸概念の適用法「発見」
n

資源提供者による、ジョブの発見
w 計算機資源提供者は、資源の使用目的を決めることができるべき。
w 資源利用者 （ジョブ投入者）が作成、広報したジョブのピアグループを、資源提供者が発見する。
w ジョブのピアグループを発見した資源提供者は、自らの意志に基づいて、そのピアグループに参加するか否かを決める。

n

資源利用者 （ジョブ投入者）による、提供されている計算機の発見
w メッセージパッシング型アプリケーションの起動先指定に使用。

n

資源提供者による、資源利用者 （ジョブ投入者）の発見
w 利用者のネットワーク上位置 （IPアドレス等）を人手で事前に設定しておく必要がなくなった。

ミドルウェアの設計
ジョブ管理ソフトウェア
Host :デーモンn Controller : ジョブ投入ツールn並列プログラミング支援ライブラリ
マスタ・ワーカn メッセージパッシングn これらのエミュレータnジョブ管理ソフトウェア：Host
資源提供者が起動しておくデーモン。
ジョブのピアグループを発見し、提供者に提示する。
提供者は、シェルを用いて、ジョブを選択する。
n[将来] ポリシー指定に従い、自動的にジョブを選択する。
特に、集中管理が求められる組織内利用で重要。

投入されているジョブ

Host のシェルジョブ管理ソフトウェア：Controller
資源利用者がジョブ投入に用いるツール。
アプリケーションプログラムを指定し、ジョブとして投入する。
n

アプリ：Java で記述し、JAR 形式のアーカイブに格納しておく。
[将来] C, C++, FORTRANで記述、コンパイルしたネイティブコードのアプリも投入可能とする。

投入された
アプリケーション

Controller のシェル

ピアグループの構成
Net Peer Groupn

Host

Host
Host
Host
HostController

Job Peer GroupController

Base Peer Groupn

Job Peer Group

Job Peer GroupController

HostNet Peer Group(always existing JXTA’s base group)

P3 既定のグループ。
全 Host, Controller
は起動直後に参加する。

Job Peer GroupnBase Peer GroupJXTAで常に存在するグループ。

ジョブの投入ごとに作成されるグループ。

Controller を用いた ジョブの投入(3) Share application code in the groupwith JXTA CMS service
Application
Application
CodeCodeJob Peer Group

Base Peer GroupController(1) Create a Job Peer GroupController(2) Join the Job Peer GroupHost の ジョブへの参加(4) Discover Application code(5) Obtain the code from a Controller
Application
Application
CodeCodeJob Peer Group

Base Peer Group(1) Discover Job Peer Groups(2) Decide to join a discovered job

Host
Host

Host
Host(3) Join the Job Peer GroupController を用いた ジョブの起動
続いて、Controller のシェルから、ジョブの起動を指示する。
nn

アプリが用いる支援ライブラリの種類によって、ジョブを起動できるタイミングが異なる：
ジョブ実行中の Host 参加を許す支援ライブラリ （i.e. マスタ・ワーカ）を用いるアプリの場合、Controller を用いたジョブ投入直後に起動できる。
w Host の参加を待つ必要はない。

n

そうでない支援ライブラリ （i.e. メッセージパッシング）を用いるアプリの場合、ジョブ投入後、Host 群の参加を待ってから、起動する必要がある。

並列プログラミング 支援ライブラリ
プログラマが直接利用するのは、マスタ・ワーカAPI と、メッセージパッシング API。
エミュレータnn

並列プログラムを計算機 1台上で動作させる。
アプリの効率的な開発、デバッグに非常に有効。
我々自身、マスタ・ワーカライブラリの開発に使った。そのまま実環境に載った。

アプリケーション アプリケーション アプリケーションマスタ・ワーカ API

メッセージパッシング API

マスタ・ワーカ
ライブラリ
マスタ・ワーカ
エミュレータ オブジェクト
パッシング
エミュレータメッセージパッシング
他のライブラリ
ライブラリ
オブジェクトパッシング
ライブラリ
JXTA並列プログラミング 支援ライブラリ
オブジェクトパッシングn（Java の）オブジェクトを送受信するライブラリ。
w API: send(PeerID, Object), broadcast(Object),recv(PeerID), recv(), listenerの登録など

通信相手は、JXTA のピアIDで識別する。
n プログラマからは直接使わない。
n この上に他のライブラリを開発する場合、JXTA の知識は不要。
nメッセージパッシング - JXTA-MPIMPI にならった API。
n 通信相手は、JXTA のピアIDの代わりに整数値 rank で識別する。
n

マスタ・ワーカn後述

並列プログラミング 支援ライブラリ

マスタ部分
①問題

マスタ・ワーカ② 結果ワーカ

マスタ・ワーカ型並列処理に特化した API とその実装 （ライブラリ）。
n マスタは、部分問題 （ワークユニット）を投入する。
ワーカは、部分問題を処理し、結果を返戻する。
n 部分問題は要求に応じてワーカに配布する。
nw 動的負荷分散
w アプリは部分問題のスケジュールを意識する必要なし。
n

障害と妨害への対応
w 悪意あるワーカの存在を前提としている。

n voting（投票）により虚偽の結果を検出できる。アプリ非依存。

w タイムアウトに基づく、部分問題の再割り当てを行う。

マスタ・
ワーカ API 使用例
アプリのマスタ側

アプリのワーカ側

class Amaster implements Master {start() {while (…) {ProblemSet p = <a subproblem>;// submit a subproblem
submitProblemSet(p);}}}class Aworker implements Worker {ResultSet process(ProblemSet p) {// process a subpoblem and// return the result}}

支援ライブラリの 性能評価
[Q] オーバレイネットワークの機能はいいけど、通信その他が遅いんじゃないの？
測定の内容
通信の遅延とスループット
n マスタによる部分問題処理スループットnw 単位時間あたりに、いくつの部分問題をさばけるか？
n

アプリケーションプログラムでの性能確認

w 共通鍵暗号方式 RC5 の暗号化鍵総当り探索
w 粒度の細かい部分問題への耐性を確認。

環境
2.4 GHz Xeon × 34台の PC クラスタ, Gigabit Ethernet
n Linux 2.4.19, Java 2 SDK 1.4.2, JXTA 2.1
n 現インターネットよりリッチだが、それだけに、ソフトウェアによるオーバヘッドを明確に測定できる。
n通信遅延1バイトのピンポンを 1000往復。片道あたり：
w TCP (C プログラム)
w TCP (Java プログラム)
w メッセージパッシング

0.062 msec
0.064 msec
4.5 msec

やはり、遅延は小さくない。
送信：Java のオブジェクトをバイト列に変換し、JXTAメッセージに埋め込み、送信。
n 受信：JXTAから呼び出された支援ライブラリ側のlistenerがJXTAメッセージを取得、バイト列を取り出し、オブジェクトを復元。支援ライブラリ中のキューに投入し、アプリに知らせる。
n

この比較的大きな遅延が、マスタの部分問題処理スループット（後述）に大きな影響を与えている。

メッセージパッシングの スループット
100 × 10 ** 6 bps くらいは出ている。
n

家庭、小規模オフィスのインターネット線や、低速LANを埋められるくらい。

送信データサイズが大きい場合に低下が見られる。
JXTA の現実装の問題？
n

分割して送ればよい。

[参考]•TCP (C)108.0 MB/s
•TCP (Java)
105.5 MB/s
(送受信サイズ 1MB)

1210.97 MB/s
JXTA-MPI

10スループット（MB/s）

10 x 10**6 bps
100 x 10**6 bps

864[注] K = 1024
M = 1024 ** 2201248163264

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

1282565121024

マスタの 部分問題処理スループット
並列処理効率のためには、マスタに集中する部分問題の配布、回収処理が律速とならないようにすることが重要。
単位時間あたりにさばける部分問題数が、マスタの性能を表す重要な指標となる。
実験：
3027.1（msec）

2522.120.9nw鍵空間を分割して部分問題とし、ワーカに配布。

20.2

2015.4n15
13.8

アプリは、RC5 暗号化鍵総当たり探索。

部分問題に含める鍵候補の数をゼロとした。
wアプリ固有の処理にかかる時間を可能な限り小さくした。

13.4

10200 の部分問題を配布、回収し、1つあたりの時間を求めた。
n500

4

8

121620
Number of workers

242832

マスタの 部分問題処理スループット
スループットBest:n Worst:nn

13 msec/個 77 個/秒
27 msec/個 37 個/秒

通信遅延だけで片道 4.5 msec かかっている。これがネック。

United Devices 社のインターネット上分散処理プロ
ジェクトの場合
UD社：抗ガン剤探索、インターネットサイトのストレステストのプロジェクトを運営。200万デバイスが登録されているとのこと。
n 120 個/秒
n Grid MP（ミドルウェア）に 4 CPU、DBに 4 CPU。
n ミ
ドルウェア自体の許容量は、最低でもこの数倍はあるだろう。
n

数万台規模のワーカを単一ジョブに参加させるなら、10 倍から 100 倍の性能向上が望まれる。
n

また、複数のマスタでワーカ群を分担できるように、部分問題をマスタの外の DB に格納しやすいような設計をしている。

アプリケーションでの性能確認

暗号鍵探索アプリで、Hostの台数と、部分問題あたりの鍵数を変化させた。
部分問題数は 200。
n部分問題の粒度を細かくしていった場合の、並列化効率の鈍り方を観察。

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

600000

処理速度 （鍵数/秒）

500000部分問題あたりの処理時間
鍵数 0x8000
1.4 秒
n鍵数 0x40000.69 秒
n鍵数 0x2000
0.36 秒n400000

3000002000001000000048

1216
ワーカの台数

2024

28

32

アプリケーションでの性能確認
Y軸を、性能向上率にしたグラフ：
n0.69 秒という比較的細粒度の部分問題でも、32台で20倍以上の性能向上は得られている。
w cf. インターネット上分散処理では数時間〜数日。

n粒度 0.36 秒では、24台で頭打ち。

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

28

部分問題あたりの処理時間

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

24

鍵数 0x8000
1.4 秒
n鍵数 0x4000
0.69 秒n鍵数 0x2000
0.36 秒

性能向上率

理想的な性能向上n201612840048121620
ワーカの台数

242832関連研究
JNGI (by Sunの人)

JXTA を用いた分散処理フレームワーク
n 計算機群の効率的な管理のためにピアグループを利用。
w cf. P3 は、ジョブのピアグループ。
n 2003年 7月現在、構想の主要部分がほとんど実装されていない。
w ピアグループを活用しない。
w 性能評価が信頼に足らない。Solaris, Windows, Linux を合わせて150台でリニアな性能向上？？？
n

XtremWeb, GreenTea, Javelin, Bayanihan,Ninflet, …
資源提供者がジョブを選択できない。
n プログラミ
ングモデルは、マスタ・ワーカや分割統治に限定。
n ファイアウォール越えが考慮されていない。
nw JavaRMI，HORB, TCP などを使用。

n

悪意あるワーカ対策を打っていない or 不明。

まとめ
計算機資源を容易に授受し、自由な並列プログラミングでそれらを連係、集約して活用するためのミドルウェア P3 を開発している。
n

資源提供者は、自らの意志で、どういった処理に資源を提供するのかを決めることができる。

自由なプログラミングのために P2P通信ライブ
ラリJXTAを採用し、P3 の目的に対してその諸概念をいかに適用するかを提案した。
n

ピアグループと発見

まとめ懸念される性能を評価した。
通信遅延は大きく、マスタの部分問題処理スループットを制限している。
n 通信のスループットは、100 × 10 ** 6 bps 程度は出る。
n マスタの部分問題処理スループットは数十/秒であり、改善が望まれる。
n LAN では、部分問題の粒度が比較的細かい （0.7秒）場合でも、32台で 20倍以上の性能向上を得られた。
n今後
研究的参加ジョブ選択ポリシー & Host の自動運転
n ジョブのチェックポインティングn

実用的な有用性、品質に向けて容易なインストールや、ミドルウェアの自動更新
n ネイティ
ブコードのアプリケーションへの対応
nw C, C++, FORTRAN アプリ
w ネイティブコード用サンドボックスを使用して、資源提供者が安心してアプリを実行できるようにする。

n

アプリの実装を通じて要件を抽出し、P3 側からの支援を検討していく。
w 例：気象のアンサンブル予報： 2XX MB の大きな固定データを使う。

その他たくさんおまけ：TCP のスループット
ピンポン 1000往復。
120
108.0 MB/s

スループット（MB/sec）

100

105.5 MB/s

80

60
15.57 MB/s (C)15.38 MB/s (Java)
C言語のプログラム

40

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

20012

48163264

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

128

256

5121024

おまけ：
マスタ・ワーカ間プロトコル(1) Request for a subproblem

MasterMaster(2) A subproblem

WorkerWorker(3) A result of the processing

3-way(3) と(1) をまとめて 1メッセージで送ることで、2way にはできる。
n しかしそれだけでは、10 〜 100 倍の部分問題処理スループットは得られない。
nP2P Supercomputing
稼動環境

ソフトウェアとその機能

ü 概要

利用者

PCやPDA

アプリケーション制御ツール•利用者はこれを用いて、ジョブの投入、削除などの管理作業を行う。

PC
インターネットや組織内ネットワークブローカ•アプリケーション制御ツールからのジョブ投入を受け付ける。
•実際の計算を計算サーバに依頼する。

計算サーバ
１００〜１０００台のPCが構成する計算資源プール

2003年 5月のIPA Spring 用資料•各PCで稼動し、管理サーバから依頼された計算を行う。

遊休PCを用いた自由で容易な大規模分散処理を支援するミドルウェア。多量の計算やストレージを必要とする問題を抱えた利用者が、身のまわりやインターネット上のありあわせのPCを多数利用して、自分自身の手で、自由なプログラミングで分散処理を行うことを可能とする。

プログラミング支援ライブラリ•応用プログラムをサポートし、通信など応用の本質ではない処理を行う。

ü テーマ名 組織内およびインターネット上の遊休PCを用いた大規模並列計算のためのミドルウェア
ü 開発者 （独）産業技術総合研究所