タスク並列言語Tascellとそのグラフマイニングへの応用
Task-Parallel Language Tascell and Its Application to Graph Mining
概要
近年のプロセッサのマルチコア化に伴い、大規模な探索問題の並列化は高速化のために必要不可欠になっています。グラフマイニングやコンピュータ将棋などを対象にしたバックトラック探索アルゴリズムの並列化も盛んに研究が行われていますが、効率良い並列探索の実現は容易ではありません。そこで我々は、並列化に適した探索アルゴリズム、および効率的な動的負荷分散機能や無駄な探索を早期に打ち切るための例外処理機能を備えるタスク並列言語Tascellの開発を行っています。本発表では、各頂点がアイテムの集合を持つグラフ構造から、ある閾値以上の数の共通アイテム集合を持つ連結部分グラフを抽出するグラフマイニングについて、複数の計算ノードを用いた大規模並列探索に対する取り組みを紹介します。
産業界への展開例・適用分野
本発表で紹介するグラフマイニングは、ソーシャルネットワークや生体ネットワークの分析などに応用できます。例えば、頂点が遺伝子、辺が遺伝子間の相互作用関係を示す遺伝子ネットワークにおいて、投与した薬をアイテムとして対応する頂点に付与させたグラフから共通のアイテム集合を持つ連結部分グラフを抽出できると、どの薬の組み合わせがどの遺伝子間で反応するかがわかり、創薬研究に役立ちます。また、提案する並列化手法はコンピュータ将棋や制約充足問題など他の実用的なアプリケーションへも応用可能です。
研究者
| 氏名 | 専攻 | 研究室 | 役職/学年 |
|---|---|---|---|
| 奥野 伸吾 | システム科学専攻 | 中島研究室 | 博士2回生 |
| 平石 拓 | 学術情報メディアセンター | 中島研究室 | 助教 |
| 中島 浩 | 学術情報メディアセンター | 中島研究室 | 教授 |