no divdi3 in x64 libgcc?

Win64 環境(mingw x64)で LLVM 2.6 をビルドしようとして、 libgcc の奇妙な?構成に気がつきました. libgcc には、除算器がないハードでも、除算をソフトウェア実現するコードなどがあります. そこには、たとえば __divdi3 というものがあるのですが、 これがなぜか 64bit libgcc では, object 名は divdi3 なのに、実装の関数は divti3 と、名前が変わっています. nm で libgcc を調べると、以下のようになります. _divdi3.o: … 0000000000000000 T ___divti3 はてなんででしょう? ちなみに divdi3 は 64bit integer の除算、divti3 は 128bit integer の除算という役割になっています(なっているはず). なので、divti3 は、object 名も divti3.o にして、divdi3.o には divdi3 の関数を実装するべきだとおもうのですが… gcc ML にでも聞いてみますかね.

World’s first SIMD ray-triangle intersection with ARM/NEON

I’ve wrote possibly world’s first SIMD ray-triangle intersection code with ARM/NEON instruction. The code runs finely on iPod touch 3G(ARM Cortex) and iPhone 3GS. The performance on iPod touch 3G is around 348 cycles per isect4(). # of assembly instruction of isect4() is around 140, thus the CPI = 348/140 = 2.48, which is notContinue reading “World’s first SIMD ray-triangle intersection with ARM/NEON”

[Google groups] SIMD-cafe for SIMD lovers

なぜ SIMD が重要か プロセッサのクロック数は頭打ち… マルチコア化ではコアが増えるたびにコア間の通信がネックになる問題がある. 専用プロセッサを作るにも, 固定したアルゴリズム&量が出ないとビジネスにならないので, やはり CPU 的にソフトなプロセッサが求められる. 一方で、エコ時代であるので省電力が求められる. そんな HW の制約の中で、SW(アプリ)は富豪的プログラミングで HW の向上に頼るだけでは対応しきれなくなってきています. 特に認識処理、グラフィックス、データベース処理でパフォーマンスを出していくことが求められている. このような、現在のプロセッサ(半導体)の技術的壁やプロセッサデザインの収益モデル(ビジネスモデル)を考えると、 特に SIMD 演算器とその活用が重要になってきます. 実際, x86/AVX(wider SIMD), iPhone 3GS(ARM/NEON), Atom/SSE が登場してきています. アプリを SIMD 最適化する必要性は今後また重要になってくるでしょう. (SIMD 最適化の最初のブームは、 MMX/SSE/SSE2 の出てきた 2000 年頃でしょうか) しかし、どんなにコンパイラが賢くても、効率的な SIMD コードを自動で吐いてくれるのはまだまだ難しい. そこで、プログラマがいかにアルゴリズムを SIMD フレンドリーにするか、 SIMD 演算器をいかにまく使ってプログラムを最適化していくかが、 今また大きく求められている、そんな気がしています. また、ときどき SIMD 野郎と話すことがあるのですが、 結構みんな「ほかに SIMD のことを濃く話すことができるひとが居なくて…」 と言われることもあり, SIMD 野郎のための googleContinue reading “[Google groups] SIMD-cafe for SIMD lovers”

OpenCL ray-triangle intersection kernel.

I’ve wrote possibly World’s first ray-triangle intersection kernel in OpenCL. I am now working with porting full raytracing kernel(traversal, shader, isector, etc) into OpenCL. This article is just exposing the small part of my professional(?) OpenCL work to you. Here’s the sample code of ray-triangle intersection kernel in OpenCL. // // Copyright 2009 Syoyo Fujita.Continue reading “OpenCL ray-triangle intersection kernel.”

KLEE : Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs

KLEE は LLVM を使ったシンボリック実行ツール. http://klee.llvm.org/ シンボリック実行とは? シンボリック実行(Symbolic execution)とは、論文によれば以下のようなシステムだそう. Instead of running code on manually- or randomly-constructed input, they run it on symbolic input initially allowed to be “anything.” They substitute program inputs with symbolic values and replace corresponding concrete program operations with ones that manipulate symbolic values. このシステムの使い道として論文が述べているのは主に二つ. カバレッジツールと、自動バグ発見ツールである. カバレッジツール シンボリック実行を行うことにより、KLEE が自動生成するテストデータでは 90% 以上と高いコードカバレッジを実現する. たとえばContinue reading “KLEE : Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs”

Ocelot : Binary translator for PTX.

(via gpupapers) http://code.google.com/p/gpuocelot/ http://code.google.com/p/gpuocelot/wiki/References (papers) CUDA で使われている PTX(中間言語表現)の、バイナリトランスレータ. 名前は Ocelot. PTX の時点で、プログラムは並列性を生かしたものになっているので、 要は PTX コードを変換するツールを書けば, 高級言語(CUDA)の段階からうまーく並列化されたコードが書けていろんなプラットフォームで動かせるぜ、という発想らしい。 PTX へのバイナリトランスレータを作ることで、 – PTX のスレッド階層はメニーコアにもマップ可能 – 変換のテクニックは、メモリレイテンシの隠蔽にも使うことができる。 – GPU データ構造を効率的にエミュレートしたり似たようなプロセッサにマップできる なことを示している。 例として、PTX -> SPE(Cell) アセンブラへのバイナリトランスレータを作り、 うまくいったということを示している. Binary Translator であることの利点 Ocelot は PTX のバイナリトランスレータでり、既存の MCUDA などの CUDA を CPU で動かすなどの手法と比べて以下の 2 点の利点があると述べている. – スレッドの階層レベルをランタイム時に動的に割り当てることができる. – 実行時情報を利用して、hot path 最適化などが行える. 気になる点 SPUContinue reading “Ocelot : Binary translator for PTX.”

AMD OpenCL(x86) v.s. MUDA

Recently, AMD released OpenCL drivers which runs on x86 CPU. I think it’d be better idea to measure performance of Black-Scholes compuation on AMD’s OpenCL(x86) and MUDA(SSE x86). Both was run on 1.86 GHz Core2 Linux 32bit. AMD’s OpenCL(x86) Option samples Time taken(sec) Options / sec 10240000 4.497 2.27707e+06 AMD’s OpenCL results in 2.3 MContinue reading “AMD OpenCL(x86) v.s. MUDA”

OSL(Open Shading Language)

(via Blender to renderman group) http://opensource.imageworks.com/ Open Shading Language (OSL) is a small but rich language for programmable shading in advanced renderers and other applications. OSL is similar to C, as well as other shading languages, however, it is specifically designed for advanced rendering algorithms with features such as radiance closures, BRDFs, and deferred rayContinue reading “OSL(Open Shading Language)”

MILEPOST GCC: optimizing a compiler by machine learning

http://www.milepost.eu/ 機械学習を用いて、いくつかサンプルプログラムを走らせ学習し、そのプロセッサに最適なコンパイルオプションの組み合わせを導出するというもの. 単純に “-O3” 最適化オプションを指定するものと比べて、MILEPOST GCC を使うと 11% ~ 16% 程度の高速化を得ることができる. しかもコンパイラオプションのどの組み合わせが有効かはこのフレームワークが勝手に導出してくれるのでとってもお手軽. たとえば遺伝的アルゴリズムを利用した ACOVEA のように、 http://www.coyotegulch.com/products/acovea/ このような自動で最適化オプションを探すという手法はありましたが、 探索区間が大きかったり試行に時間がかかるなどでチューニング時間がかかり広く使える手法にはほど遠かったとのこと. (ACOVEA は確か 1 日近くかかる) MILEPOST GCC は、その問題を機械学習を使うことで効率化し、 またフレームワークを GCC plugin で実現することで実務的に使えるようにしています. 実際ソースを落としていじろうとしましたが、 最後の最後らへんで、うまく動いてくれませんでした. ちなみに、学習データは ctuning.org でデータベース化していろいろ面白いことをやっていこうとするようです. http://ctuning.org/wiki/index.php/Main_Page

Wirbel, statically typed Python-like language.

http://mathias-kettner.de/wirbel_index.html Python 的な文法だけど、静的型付けな言語. もちろん(?) モダンな言語ということで型付けは型推論により行われます. 出来るコードはネイティブバイナリなので高速動作. また内部データ型は C と合わせてあるので, C/C++ との統合も用意. な、なんかすごくね?… こんな感じで書いて… def main(): a = 1.0 b = 3.0 c = [1, 2, 3] for i in c: print(i) print(“a + b = %f” % (a+b)) print(“The World! Time stops…”) main() こんな感じで実行します. $ wirbel main.w 1 2 3 a + b = 4.000000Continue reading “Wirbel, statically typed Python-like language.”