Discovery Sagaサイレントキーワード俯瞰

コンテンツ配信 / P2P / マルチキャスト / 負荷分散 / ネットワーク / 情報通信工学 / ピア・ツー・ピア / 階層化

近年、インターネットを介した映像配信が普及しつつある。インターネットを用いることにより、チャンネル数に縛られることなく、多くのコンテンツを配信できる。しかしながら、放送と異なり、今後利用者が増加するにつれ、ネットワーク帯域不足や輻輳やサーバへの負荷増大など種々の問題が出てくる。それに対して、P2Pやマルチキャストといった技術を組み合わせ、サーバへの負荷を軽減した新しい通信プロトコルを提案した。また、計算機シミュレーションにより性能評価を行い、提案の有効性を示した。

オークション / マルチエージェント / 負荷分量 / フェアネス / 資源割当て / 資源選択 / 経路探索 / ネットワーク / 負荷分散

本研究では,ネットワーク上の各リソースを市場原理に基づいて公平かつ効率的に割り当てるプロトコルを,その実装に向けて評価することを目的とする.
P2Pや分散センサネットワークなどのアドホックなネットワークにおけるデータ転送では,個々のノードの所有者や規格が異なる.この場合,各ノードにデータを適切に転送するための誘因(報酬)を考慮しなければならない.この報酬の決定にはしばしばオークションプロトコルが用いられる.しかし従来のプロトコルでは,あるノードが架空のノードを用いるか他ノードと共謀することで,不正に報酬を獲得できることを示した.この場合、理論的にもっとも優れているVickrey-Clarke-Grovesプロトコル(VCG)でも、不正行為は防げない。
本研究では、さらに、選択されうる経路を所有しているエージェントの数に応じたペナルティをVCGに適用し、Reserve-Costプロトコル(RC)を提案し、このプロトコルが架空名義を用いた操作の影響を受けないことを理論的に明らかにした。計算機上に再現した小世界ネットワークに対して、提案プロトコルを評価し、VCGに対して約60〜80%の効率性を達成することも示した。
また実際のネットワークでは,各ノードでオークションなど取得可能な情報に基づいてどこからデータを受ける(送る)べきかを決定する必要がある.これは,入札可能な対象(サーバなど)が複数あるときに,適切な入札箇所をある程度推定することに相当する.しかし、ネットワークの資源割当てのように非常にたくさんの要求が同時に起こり、かつ多くの地点から独立に処理をする必要がある.このような状況で資源割り当てプロトコルで見られる現象の解析も行った。それぞれが合理的に判断をすると全体の効率が落ちる現象があり、このために揺らぎや学習を導入することが一定の効果を上げることを示した。

連立一次方程式 / マルチグリッド法 / 共役勾配法 / 前処理 / 並列化 / ベクトル化 / 負荷分散 / ネットワーク / 共役傾斜法 / 偏微分方程式 / 線形方程式 / 反復解法 / 並列処理 / 領域分割 / 異方性問題 / データ構造 / ベクトル計算機 / 偏微分方程式解法 / 代数的マルチグリッド法 / 格納方法

共役勾配法の前処理としては,並列性が高く,かつ収束加速性の良いものが必要であるが,この二つはしばしば矛盾する.この二つを兼ね備えているものとして,代表者らはマルチグリッド前処理を提唱し,その高い性能を実証してきた.
本研究では,これをさらに非構造格子まで拡張し,任意形状の問題や物理定数に異方性のある問題について研究を進めた.SA-AMG法は,問題行列から性質の似たサイズの小さい行列を生成し利用する効率の良い解法であるが,サイズの小さい行列を生成する際に領域分割境界を考慮して生成することにより異方性のある問題でも,効率よく,かつ高並列に実現できることを示した.
またSA-AMG法の実装技術として,ベクトル化の研究を進めた.SA-AMG法内で大きな計算コストを占めるものとして三つの疎行列の積を求める計算が挙げられる.その疎行列積のベクトル性能を出すためには,代表的な疎行列のデータ構造を組み合わせ,三次元弾性体問題に対してはJDSとCRSの組み合わせた手法が最も高速に処理できることを示した.また大規模疎行列を伴う問題に対する実装技術として,分散疎行列の再分散・リオーダリングライブラリを作成し,評価を行った.このライブラリにより,疎行列問題に対して再分散やリオーダリングの処理を動的に、かつ簡易にできる枠組みを実現した.
その他の並列実装技術の基盤的な研究として,有限サイズのmulti-master divisible load問題についての再分散スケジューリング問題について研究し,いくつかのパラメータを同定することにより,シミュレーションが実システムの振る舞いを正しく再現することを示した.関連する問題として,並列分子動力学のデータ分散の問題についても研究し,ノード間相互接続ネットワークのバンド幅やレーテンシが一様でない場合について,最適な並列分散を与える方法を求めた.これらの基本的な技術が,マルチグリッド法の多様なプラットフォームの上での並列実装にどのように生かせるかは今後の課題である.

【研究分担者】
山中直明	慶應義塾大学	理工学部	教授	(Kakenデータベース)
岡本聡	慶應義塾大学	大学院・理工学研究科	准教授	(Kakenデータベース)

【研究分担者】
横尾真	九州大学	大学院システム情報科学研究院	教授	(Kakenデータベース)
松原繁夫	京都大学	情報学研究科	助教授	(Kakenデータベース)
岩崎敦	九州大学	大学院システム情報科学研究院	助手	(Kakenデータベース)

【研究分担者】
須田礼仁	東京大学	大学院・情報理工学系研究科	助教授	(Kakenデータベース)
西田晃	東京大学	大学院・情報理工学系研究科	助手	(Kakenデータベース)