小ポイントFFTのマルチコア上での自動並列化手法

• Item type: SIG Technical Reports(1)
• 公開日: 2014-02-27
• タイトル: 小ポイントFFTのマルチコア上での自動並列化手法
• タイトル / 言語: en
• タイトル: Automatic Parallelization of Small Point FFT on Multicore Processor
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 実行効率化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 古山, 祐樹; 見神, 広紀; 木村, 啓二; 笠原, 博徳
• 著者名(英): Yuuki, Furuyama; Hiroki, Mikami; Keiji, Kimura; Hironori, Kasahara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 高速フーリエ変換 (FFT) は，ディジタル信号処理や画像圧縮など様々な分野で使用される非常に応用性の高い計算アルゴリズムである．その中でも，LTE 等のベースバンド処理で用いられる小ポイントの FFT プログラムは，データ転送や制御のオーバーヘッドを伴う専用ハードウェアを使用しにくく，マルチコア上での並列化の要求が高まっている．本稿では，そのような小ポイントの FFT プログラムに対しコンパイラによる自動並列化及び，false sharing 回避を目的としたキャッシュ最適化を適用し，データキャッシュを持つ種々の共有メモリ型マルチコアアーキテクチャに向けて低オーバーヘッドな並列化コードを生成する自動並列化手法を提案する．提案手法を OSCAR 自動並列化コンパイラに実装し，32 ポイントから 256 ポイントまでの小ポイントFFTを並列化し，8 つの SH4A コアを集積した情報家電用マルチコアプロセッサ RP2 上で性能評価を行ったところ，256 ポイントの FFT プログラムで，逐次プログラムに対し 2 コア並列化で 1.97 倍，4 コア並列化で 3.9 倍というスケーラブルな速度向上を得ることが出来た．また，FFT と同様にバタフライ演算を行う高速アダマール変換のプログラムにも同手法を適用し評価を行い，256 ポイントのプログラムで 2 コア並列化で 1.91 倍，4 コア並列化で 3.32 倍という高い速度向上が得られ，提案手法の有用性が確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Fast Fourier Transorm (FFT) is one of the most frequently used algorihtms in many applications including digital signal processing and image processing to compute Descrite Fourier Transform (DFT). Although small size FFT programs must be used in baseband signal processing such as LTE and so on, it's difficult to use special hardwares like DSPs for computing such a small problem because of their relatively large data transfer and control overhead. This paper proposes an automatic parallelization method to generate parallelized programs with low overhead for small size FFTs suited for shared memory multicore processor by applying cache optimization to avoide false sharing between cores. The proposed method has been implemented in OSCAR automatic parallelizing compiler, parallelized small point FFT programs from 32 points to 256 points and evaluated them on RP2 multicore processor having 8 SH-4A cores. It achieved 1.97 times speedup on 2 SH-4A cores and 3.9 times speedup on 4 SH-4A cores in a 256 points FFT program. In addition to the FFT programs, the proposed approach is applied to Fast Hadamard Transform (FHT) which has similar computation to the FFT. The results are 1.91 times speedup on 2 SH-4A cores and 3.32 times speedup on 4 SH-4A cores. It shows effectiveness of the proposed method and easiness of applying the method to many kinds of programs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告計算機アーキテクチャ（ARC）; 巻 2014-ARC-209, 号 3, p. 1-8, 発行日 2014-02-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会