Load to MUDA. SIMD code generation, domain specific language, automatic optimization, functional programming, etc.

by syoyo

[En]

To realize my MUDA lanuage idea[1], I started research on portable SIMD code generation.
And I found a lot of and good previous work about it, and also find a keyoword to express such a research topic in that field.

The keyword to express MUDA is Domain Specific Language.

Domain Specific Language(DSL, from wikipedia)

DSL is a problem specific langauge. It isn’t a generic language, but useful for some problem to express it.
Usually DSL is implemented with LEX/YACC, ANTLR and functional programming langauges such like Haskell or Ocaml.

Here is some lists of previous works of SIMD code generation with DSL(or dynamic code generation) I found.

A Domain-Specific Language for the Generation of Optimized SIMD-Parallel Assembly Code
Christopher Kumar Anand, Wolfram Kahl.
SQRL Report No. 43.
http://www.cas.mcmaster.ca/~anand/papers/preprints.html

They reported how optimized tanh(hyperbolic tangent) function can be mapped to native codes
with DSL enbedded in Haskell.
They doesn’t uses SSE, but the idea can be valuable to code MUDA.

Page linked also contains a lot of interesting papers.

Efficient Utilization of SIMD Extensions
Franchetti, F. Kral, S. Lorenz, J. Ueberhuber, C.W.
Proceedings of the IEEE Special Issue on “Program Generation, Optimization, and Adaptation,” Vol. 93, No. 2, 2005, pages 409-425.
http://www.ece.cmu.edu/~franzf/publications.htm

This paper is a summary/survey paper on SIMD code geneation and automatic optimzation.
It includes a lot of pointers for this research topic, thus it’s a good paper to start with doing reaserch on
SIMD code genration and automatic optimzation.

CorePy
http://www.corepy.org/
CorePy doesn’t support SSE, but their design are useful for me to code MUDA language.
Writing efficient SIMD code with script language seems good.

FFTW
http://www.fftw.org/

Instead of statically optimized code, FFTW uses their FFT language and compiler for dynamic code generation and automatic optimizer for high perfomance FFT computation on various platform.
Performance of produced codes are comparable or overcomes vendor tuned FFT code.
Their FFT language and compiler is implemented with Ocaml.

Their technique is also published as below(see FFTW’s site).
Matteo Frigo and Steven G. Johnson, “The Design and Implementation of FFTW3,” Proceedings of the IEEE 93 (2), 216–231 (2005). Invited paper, Special Issue on Program Generation, Optimization, and Platform Adaptation.

SAC(Single Assignment C)
http://www.sac-home.org

SaC is an array programming language predominantly suited for application areas such as numerically intensive applications and signal processing. Its distinctive feature is that it combines high-level program specifications with runtime efficiency similar to that of hand-optimized low-level specifications

SAC provides their prerelease compiler for array based application and hosts a lot of research papers.

Conclusions at present

Playing with FFTW’s genfft might be a good point to start with
learning SIMD code generation technique.

And more, common language used in this research topic seem functional programming(FP) language, especially Haskell and Ocaml.
It would be a good time for me to learn FP language.
thus I decided, in front of playing with FFTW, I must learn about FP language. Ocaml for first, then Haskell.
(Because FFTW’s genfft uses Ocaml 😉 )

[Ja]

詳細は英語の方を見てもらうとして、まとめますと以下の通り。

– FFTW すげぇ。中身は結構 cutting edge なことやっているのね。FFTW の code は必読だ。
– MUDA に限らず自分の頭の中にあるアイデアを実現するには、やっぱオレ様言語(DSL)を作るのがよさそうだ。
一番費用対コストが高いのと、トータルでみたときの coding 時間の節約になる、気がする。
今まで何でもなるべく C で書いてきたが、実はいままでとても効率が悪いことをやっていたのではなかっただろうか。
– とにもかくにも Ocaml や Haskell を習う必要を感じた。論文のいたるところで関数型言語が出てくるし、
FFTW の FFT compiler が ocaml だし。
– というわけでまずは関数型言語の習得から…

[1] Idea: MUDA, MUltiple Data Accelerator language for high performance computing
http://lucille.atso-net.jp/blog/?p=322

Advertisements