テンプレート・メタ・プログラミングによるFFTの適応的最適化

• Item type: Trans(1)
• 公開日: 2005-01-15
• タイトル: テンプレート・メタ・プログラミングによるFFTの適応的最適化
• タイトル / 言語: en
• タイトル: An Adaptive Optimization of FFT with Template Meta-programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: フリーランス
• 著者所属(英): en
• 著者所属(英): freelance
• 著者名: 神戸, 隆行
• 著者名(英): Takayuki, Kando
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 現在，数多くの様々な最適化技術が研究されているが，そのすべての最適化技術，特に問題依存度の高い最適化を組み込むことは処理系の肥大化を招く．そこでこのような問題依存度の高い最適化は問題の解法とともに処理系ではなくプログラム部品としてライブラリ化することが考えられる．その手段の1 つとしてメタ・プログラミングがある．そしてこのように最適化をライブラリに組み込むにあたっては実行環境の違いをどう反映するかという問題がある．これについては最適化に適当なパラメータを導入し，実行環境で試行・計測してパラメータを求める実行時プロファイリングという方法がある．本発表ではFFT を例にとり，メモリ階層を意識した最適化をC++テンプレートの機能を用いたメタ・プログラミングで行うとともに，実行時プロファイリングに基づいて適応的な最適化を行ったので報告する．これは3 つの段階からなる．1) 核となる小さなサイズのデータに対するFFTコードをサイズごとに複数生成（ループの展開，三角関数値の静的計算）．2) 前段で生成したサイズごとの核コードの実行時間計測．3) 計測結果に基づく核コードの選択・合成による最終的なFFT コードの生成．特にこのうち1) と3) でC++テンプレート・メタ・プログラミング技法を利用した．以上の実装と評価について報告を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Although much various optimization technologies are studied now, including all these optimization technologies, especially highly problem dependent optimizations bloats code size of compiler too much. One approach is the following: the optimizations build into a part of component library the solution instead of build into compiler itsself, which is able to realize with meta-programming technique. But including the optimizations in a library in this way, there is a problem how to reflect the difference in execution environment. This problem is dealt with introducing parameters for optimization, profiling trial execution in an execution environment, and looking for a suitable parameter value. In this presentation, FFT is taken for the example, and we describe memory hierarchy conscious optimization for FFT, which is implemented in meta-programming technique, and adaptive optimization based on execution time profiling. Our method consists of three steps. Step1: They are some FFT code generation (ex. unrolling of a loop, static evaluation of a trigonometric-functions value) for each small constant size data used as a kernel. Step2: Execution time measurement of the kernel for every size generated in the preceding step. Step3: Generation of the final FFT code by selection and composition of the kernel based on the measurement results. C++ template meta-programming technique was used in Step 1 and Step3. The above method and its evaluation are reported.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG1(PRO24), p. 78-96, 発行日 2005-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会