金田憲二

	背景と目標ソフトウェア

	背景−P2Pアプリケーション−

広域に分散した多数の資源を利用する並列分散計算

	遊休なPCを利用した並列計算
	50TFlopsにも達する処理能力

	問題点

実際に稼動しているシステムのほとんどは単純な並列計算しか行っていない

	お互いに依存関係のないタスクを遊休のPCにばらまくだけ
	通信は基本的にはサーバのみ

	大目標

様々な広域並列分散アプリの効率的な開発を可能にするプラットフォーム

SETI@homeよりタスク間の依存関係が複雑な広域並列アプリの簡便な実装を可能にする

	大目標への一歩として

P2Pコンピュータ将棋

多数の動的に増減する計算機上でのゲーム木探索

より短時間で深く探索することを目指す

	仕様

	P2Pコンピュータ将棋の仕様

	通信処理

タスク生成・実行結果の送信メッセージ

UDPの再送処理

ackを受信するまでメッセージの送信

ハッシュ表の更新メッセージ

	UDPのブロードキャスト
	再送処理なし
	その代わり定期的にブロードキャスト

	タスクの生成

	タスクのID（将棋の盤面）から実行先PCを一意に決定
	同じ盤面は同じPCが計算
	⇒ローカルのハッシュ表にアクセスするだけで済む

	オリジナルでは，枝狩りの生じやすい手を優先的に探索
	分散版でもタスクに優先度をつけ，枝狩りの生じやすい手を優先的に探索

	計算機の参加方法

	すでに動作中の計算機のどれかに参加リクエストを送信
	リクエストを受信した計算機は、ハッシュ表の半分を委譲

委譲されるハッシュに対応するタスクも委譲

	オリジナルの将棋プログラム

int search(ban, depth, alpha, beta, …) {
if(hash_lookup(ban, &eval)) { //すでに探索済みの盤面なら探索を省く
return eval;
}
for(move in possible_moves) {
ban.move(move); 　　　　　　//盤面の更新
eval = search(ban, depth+1, alpha, beta, …);
ban.reverse() 　　　　　　　　//盤面の復元
if(eval > beta) { 　　　　　　// 枝狩り
return eval;
}
update(eval, &alpha, &beta, &possible_moves, &best_eval);
}
return best_eval;
}

	分散版の将棋プログラム

void search(ban, depth, alpha, beta, …) {
if(hash_lookup(ban, &eval)) { //すでに探索済みの盤面なら探索を省く
return eval;
}
for(move in possible_moves) {
ban.move(move); 　　　//盤面の更新
spawn_task(search(ban, depth+1, alpha, beta, …));　//タスク生成
ban.reverse() 　　　　　//盤面の復元
}
sync();　　　　　　　　　//タスクの終了を待つ
}

void search_cont(ban, depth, alpha, beta) {
for(move in possible_moves) {
eval = get_child_result();
if(eval > beta) { 　　　　　　　// 枝狩り
send_result(eval);
return;
}
update(eval, &alpha, &beta, &possible_moves, &best_eval);
}
send_result(best_eval);
return;
}

	ローダー

簡便なコマンド実行・ファイル配布

EXECUTE

サブネット内の全ホストでコマンドを実行

PUT

サブネット内の全ホストにファイルを転送

GET

サブネット内の全ホストからファイルを取得

	ローダーの動作の流れ

1.DETECT

	今現在生きているPCの検出
	数回ブロードキャストを行い、ackの返って来たホストを生きているとみなす

2.EXECUTE, PUT or GET

再送処理つきのブロードキャスト

	線表

	実験

	実験目標

実際の720台のノートPCを用いての動作確認・性能測定

	実験環境

東芝TECRA

	Pentium M 1.3Ghz
	Memory 512MB

	実験環境

以下の盤面から深さ12と深さ14で探索

	探索時間（深さ12）

速度向上：最大7倍(96ノード)
実行時間：オリジナルの4倍以上

	探索時間（深さ14）

速度向上：最大8倍(192ノード)
実行時間：オリジナルの15倍以上

	探索ノード数

総計

深さ12

	分散版		154508
	オリジナル		79686

深さ14

	分散版		2137545
	オリジナル		324197

	ネットワークの負荷

深さ14
ノード数48

	CPUの負荷

深さ14
ノード数48

	ハッシュ表とタスクの分布

	得られた最善手

分散版

▲５五歩△同角▲３五歩△２二銀▲８六歩△同歩▲同銀△３三銀▲３四歩△同金

オリジナル

▲３五歩△同歩▲同飛△３一金▲３七桂△３四歩打▲３六飛△２二銀▲５八銀△５五歩▲４七銀△パス

※子タスク生成のタイミングによって，得られる手が悪化する

	実験結果の考察

性能はでなかった原因は？

CPUロードがあがらない

	タスクのアンバランスな分散
	タスク生成の同期

タスク生成処理が重たい

タスクの粒度をあげると，ハッシュ表のヒット率が下がる

	まとめと今後の課題

	今後の課題

性能向上

とりあえず激指の開発者に色々聞いてみる

耐故障性

任意のシチュエーションで動作可能にするためには，もう少し厳密に考える必要がありそう

その他アプリへの応用

プレスリリース

アルバム