文献

J-GLOBAL ID：201402272278505989   整理番号：14A0298712

Strassenのアルゴリズムを用いた行列積自動チューニングライブラリ

著者 (3件)： 坂本真貴人 (工学院大) ,  藤井昭宏 (工学院大) ,  田中輝雄 (工学院大)
資料名： 電子情報通信学会論文誌 D  (IEICE Transactions on Information and Systems (Japanese Edition))
巻： J97-D  号： 3  ページ： 405-413  発行年： 2014年03月01日 
JST資料番号： S0757C  ISSN： 1880-4535  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *アルゴリズム ,  *行列 ,  *ライブラリ【計算機】 ,  計算 ,  高速化 ,  線形代数
準シソーラス用語： *Strassenのアルゴリズム ,  科学技術計算 ,  *行列積 ,  *自動チューニング

分類 (1件)： 数値計算  (JE02000J)

引用文献 (9件)：

• V. Strassen, ”Gaussian elimination is not optimal,” Numer. Math., vol.13, pp.354-356, Aug. 1969.
• 平田富夫,”分割統治法,”アルゴリズムとデータ構造,滑川敏彦(編),pp.142-144,森北出版,東京,2004.
• P. D'Alberto and A. Nicolau, ”Adaptive Strassen and ATLAS's DGEMM: A fast square-matrix multiply for modern high-performance systems,” HPCASIA' 05, pp.45-52, Beijing, China, July 2005.
• R.C. Whaley, A. Petitet, and J.J. Dongarra, ”Automated empirical optimizations of software and the ATLAS project,” Parallel Computing, vol.27, no.1-2, pp.3-35, Jan. 2001.
• C.L. Lawson, R.J. Hanson, D.R. Kincaid, and F.T. Krogh, ”Basic linear algebra subprograms for fortran usage,” ACM Trans. Mathematical Software (TOMS), vol.5, pp.308-323, Sept. 1979.

タイトルに関連する用語 (4件)： アルゴリズム ,  行列積 ,  自動チューニング ,  ライブラリ