著者

神戸 隆行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.1, pp.78-96, 2005-01-15

参考文献数

17

---

現在,数多くの様々な最適化技術が研究されているが,そのすべての最適化技術,特に問題依存度の高い最適化を組み込むことは処理系の肥大化を招く.そこでこのような問題依存度の高い最適化は問題の解法とともに処理系ではなくプログラム部品としてライブラリ化することが考えられる.その手段の1 つとしてメタ・プログラミングがある.そしてこのように最適化をライブラリに組み込むにあたっては実行環境の違いをどう反映するかという問題がある.これについては最適化に適当なパラメータを導入し,実行環境で試行・計測してパラメータを求める実行時プロファイリングという方法がある.本発表ではFFT を例にとり,メモリ階層を意識した最適化をC++テンプレートの機能を用いたメタ・プログラミングで行うとともに,実行時プロファイリングに基づいて適応的な最適化を行ったので報告する.これは3 つの段階からなる.1) 核となる小さなサイズのデータに対するFFTコードをサイズごとに複数生成(ループの展開,三角関数値の静的計算).2) 前段で生成したサイズごとの核コードの実行時間計測.3) 計測結果に基づく核コードの選択・合成による最終的なFFT コードの生成.特にこのうち1) と3) でC++テンプレート・メタ・プログラミング技法を利用した.以上の実装と評価について報告を行う.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.