階層型行列法のタスク並列言語による実装
Implementation of Construction and Arithmetic of Hierarchical Matrices Using a Task Parallel Language

概要

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

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

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

研究者

氏名	専攻	研究室	役職/学年
平石 拓	学術情報メディアセンター	中島研究室	助教

---