階層型行列法とその動的負荷分散を用いた並列化
Hierarchical Matrix and Its Parallelization Using Dynamic Load Balancing

概要

階層型行列(H行列)は、N個の要素間のN×N個の相互関係をO(N×logN)のサイズに圧縮して表す密行列の近似表現の一つである。H行列の生成や演算の並列化する際、各タスクの負荷を正確に見積もれないため、単純な実装では負荷不均衡により高い性能が得られない。そこでコアへのタスク割り当てを実行時に行う動的負荷分散により性能改善を行った。特に、行列の区分け処理では、不均衡な木構造の生成、走査をともなうためスパコンで一般に用いられるOpenMPやMPIでの効率的な並列化が困難である。そこで、タスク並列言語のCilk Plusや本研究室で開発中のTascellを用いた実装を行った。

産業界への展開例・適用分野

階層型行列は、要素間の相互関係に基づく現象の解析に広く適用することができ、地震や電磁場などの物理現象の解析から、インターネット上の情報やソーシャルネットワーク解析などの大規模計算にかかる時間や必要メモリ量を削減するのに大きく貢献すると考えられます。また、本発表で紹介する並列言語は、一般に並列化が困難とされているグラフ探索系の計算の高速化を目指して開発しているもので、広い応用分野が考えられます。

研究者

氏名	専攻	研究室	役職/学年
白 正陽	システム科学専攻	中島研究室	修士2回生
平石 拓	学術情報メディアセンター	中島研究室	助教
中島 浩	学術情報メディアセンター	中島研究室	教授

---