著者
神戸 隆行
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌プログラミング(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.

言及状況

Facebook (1 users, 1 posts)

2014/07/16のすいどう後のもぐ俺で、TeXマクロの話から始まって: 「DSL(特定用途向け言語)はちょっとうっかり便利機能を追加するとチューリング完全になっちゃう事例多いよ。」 「実はC++のテンプレートもそう。」 「テンプレートでプログラミングしてコンパイル時にFFTのループを展開とかもできる。…っていうかやった。」の論文。 http://ci.nii.ac.jp/naid/110002 ...

Facebook における性別

Twitter (7 users, 11 posts, 6 favorites)

@keisukefukuda 10年ほど前失業してた頃に就職活動としてテンプレートで浮動小数点演算を実装して、FFTと動的計画法なら計算したw http://t.co/q3sUvgBqmF
@shiracha @torgtaitai 「テンプレート・メタ・プログラミングによるFFTの適応的最適化」http://t.co/gJAZSTxn3I を書いて9年、まったくモテませンンンンッ!
…いやまぁC++のテンプレート・メタプログラミングでコンパイル時に展開されるFFT書いたことある[ http://t.co/TmaGzoeL6I ]んだから書かなきゃいけなくなれば、どうにかこうにか書くだろうけど。
@torgtaitai 詳しくはコチラ → http://t.co/TmaGzoeL6I (「CiNii 論文PDF - オープンアクセス」をクリックするとPDFが見られます。確かソースも幾らか載せといた筈。)
@miwakovamp 無職 de 発表記念論文w > http://t.co/tE04pzT7 同じ研究会に出ていたもう一本の方で「所属:無職」を「それはちょっと…」と共著者に止められたので所属欄が「フリーランス」になってます。
ちょ、変態ここに極まるwww http://ci.nii.ac.jp/naid/110002768692/
CiNii: テンプレート・メタ・プログラミングによるFFTの適応的最適化 http://ci.nii.ac.jp/naid/110002768692/en 確かに FFT は TMP と相性がよいな~.他のアルゴリズムでは何があるだろう?

収集済み URL リスト