WEKO3
アイテム
Strassenの行列積アルゴリズムのSX-3上でのインプリメント
https://ipsj.ixsq.nii.ac.jp/records/122939
https://ipsj.ixsq.nii.ac.jp/records/1229397271a003-205c-43d7-b42b-264e3a2a8b39
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00001336760.pdf (223.7 kB)
|
|
| Item type | National Convention(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 1993-03-01 | |||||
| タイトル | ||||||
| タイトル | Strassenの行列積アルゴリズムのSX-3上でのインプリメント | |||||
| タイトル | ||||||
| 言語 | en | |||||
| タイトル | Implementation of Strassen's Matrix-matrix Multiplication Algorithm on SX-3 | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者所属 | ||||||
| NEC C&C 情報研究所 | ||||||
| 著者所属 | ||||||
| NEC C&C 情報研究所 | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| C&C Information Technology Research Laboratories, NEC Corp. | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| C&C Information Technology Research Laboratories, NEC Corp. | ||||||
| 論文抄録 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 通常N次正方行列の積を計算するには,2N^3回の浮動小数点演算が必要となるが,1969年にV.Strassenは,分割統治法(divide and conqure)という方略を再帰的に適用することにより,4.7N^<2.81>回の浮動小数点演算で行列積が求められることを示した.このアルゴリズムは計算量のオーダを下げるが,係数が増加するため行列のサイズがある程度大きくないと実際には計算量が減らない.また,アルゴリズムが自然なものに比べ複雑であり,誤差の点で不利であること等の理由から,ほとんど実用に供されることがなかった.しかしながら,近年計算機のハードウェアが発達し,大規模な行列の演算が実用的な時間で計算出来るようになるとともに,実用化される例が現れている.こうしたことから,NECのスーバーコンピュータSX-3上でも,Starassenのアルゴリズムをインプリメントしてみた.一般に,SX-3のようなベクトル計算機の場合,行列のサイズが小さいとベクトル化の利点が活かしにくいため,演算速度が下がる.このため,行列を小行列に分割して計算するStrassenのアルゴリズムでは,必要な演算量を減らしても実行時間が減るとは限らない.しかしながら,評価実験の結果,Strrassenのアルゴリズムにより,行列積の演算時間が最大約15%削減されることが分かった,特に2048次の行列では,見かけ上約5.9GFLOPSの演算速度を達成した.また,誤差の面でも実用上問題が無いことが分かった. | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00349328 | |||||
| 書誌情報 |
全国大会講演論文集 巻 第46回, 号 情報科学一般, p. 57-58, 発行日 1993-03-01 |
|||||
| 出版者 | ||||||
| 言語 | ja | |||||
| 出版者 | 情報処理学会 | |||||
