著者

坂本真貴人 藤井昭宏 田中輝雄

雑誌

研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.2013-HPC-138, no.6, pp.1-7, 2013-02-14

---

行列行列積を計算する DGEMM の性能は,さまざまな科学技術計算において重要である.DGEMM の高速化の手法の 1 つに Strassen のアルゴリズムがある.これは再帰的アルゴリズムであり,適用する回数を増やすことで計算量を O(N3) から O(Nlog7) まで削減することができる.しかし,計算機や行列サイズに合わせた適切な回数を選択しないと高速化できない.本研究では,Strassen のアルゴリズムを,自動チューニング機能付きの線形代数ライブラリである ATLAS をベースにして組み合わせた.そして,最適な適用回数を自動的に選択する機能をもつ行列行列積計算ライブラリを試作し,計算性能の評価を行った.実験の結果,さまざまな行列サイズで ATLAS 単体より高い性能を引き出すことができた.また,通常の方法に比べて誤差がどの程度になるか確認した.

著者

坂本 真貴人 藤井 昭宏 田中 輝雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.97, no.3, pp.405-413, 2014-03-01

---

さまざまな科学技術計算で用いられる行列行列積計算の高速化手法の一つに,Strassenのアルゴリズムがある.これは1回の適用で計算量を約7/8に削減するアルゴリズムである.また,このアルゴリズムは再帰的に適用することができ,段数(Strassenの適用回数)を増やすことで計算量をO(N^3)からO(N^<log_2 7>)まで削減できる.高速化のためには,計算機環境に合わせて適切な段数を選択する必要がある.適切な段数は行列サイズごとに決まるのでチューニングに多くの時間を要する.本研究では,線形代数ライブラリATLASをベースとしたStrassenの段数を自動チューニングする行列積計算ライブラリSAT Lib(Strassen Auto Tuning Library)を試作した.SAT LibではStrassen及びATLASの特性を利用し,チューニングにかかる時間を削減する.SAT Libの評価を行った結果,全行列サイズを計測する場合に比べXeon X5660上で約1/61,Intel Core i7 2600上では約1/53までチューニング時間を削減できた.