call とか ret は無くてもなんとかなる
2008/07/11(金) 01:02:33
Linux Kernel の include/asm-i386/system.h の switch_to() マクロとかで使われていたりして,わりと有名なテクニックなのかもしれませんが, call foo とかは,機械的に pushl $1f jmp foo 1: みたいに,スタックの頭に戻り番地をプッシュして,関数にジャンプする感じに書き換えられるのではないかと思いました. ret もまぁ, pop %ecx jmp *%ecx みたいに,適当に壊しても良いレジスタに戻り値を pop して間接ジャンプすれば大丈夫な気がします. もちろん,本来一命令で済むものを,わざわざメモリ触った挙句命令数増やすのはバカバカしいので,実用性は無いわけですが. アセンブラとか,x86 命令レベルのクロック数とか μOP (マイクロオペレーション) レベルの話とか全然わからない子なので,大きな勘違いをしている恐れがあります (ツッコミ期待) 最近の x86 は,インタフェースだけは x86 のままでも,中身は全然別物らしいです.一個の x86 的 CISC 命令が複数の μOP に分解されて実行されたり,逆に複数の命令が一個の μOP で実行できたり. x86 レベルではレジスタは 8 つしかありませんが,たとえば Pentium 4 は,物理レジスタは 128 本あるそうです.なので μOP レベルでは,x86 命令からさらにレジスタ割付みたいなことが行われて,レジスタリネーミングとかいう最適化技術が使われていたりも. アセンブリのレベルの見た目と,実際の速度が全然異なるようです.なので,よく 「高級言語なんて当てにするな,アセンブリリスト出して見ろ」 とか言う古いプログラマの人がいたりするようですが,最近の CPU はアセンブリ自体がある種の高級言語で,x86 命令が内部的には μOP に JIT されて,命令が分解されたりまとめられたり実行順序が勝手に変更されたり同時実行されたりレジスタリネーミングされてものすごいパイプライニングされたり,わけわからんことになってみたいなので,アセンブリ見ても本当に早いのかどうかはわからない気がします. なんかとりとめなくなってしまいましたが,要するに niha さんとかが最近アセンブリプログラミングについて書いてるみたいなので,僕もなんとなく思いついたことを書いてみたくなっただけなのでした. CPU って,ガチガチのハードウェアみたいに思われてますけど,現在の x86 CPU は,IA-32 っていう高級な CISC 命令セットを実行するための仮想機械 (VM) なんですよね.本当にガチのハードウェアは,μOP っていう,もっと細かいオペレーションを実行する,レジスタがいっぱいある RISC プロセッサです.そういう非常に複雑な二重構造になっているのに,あれだけの性能が出ているという奇跡.すごいなぁと思います. # icc の最適化がすごくて,gcc とかは一生かなわないってのも,ある意味当たり前です.インテル社だけが,μOP の仕様や,それへの変換アルゴリズムなど,もろもろの内部の秘密テクノロジを知っているのですから,他のコンパイラベンダは,ベンチマークの結果から内部を推測して,最適化ルーチンを作るしかありません.そりゃ,一生追いつけませんよ ということは,実は x86 命令セットに限らず,ppc とか sparc とか arm とか,他のプロセッサの命令セットもハードレベルで JIT して実行できるポテンシャルはあるのでは ? と. インテルが μOP の仕様を公開してくれれば,それの上の LLVM みたいなフレームワークを被せて,ハードウェアとソフトウェアが協調して,高速に低レベル命令を実行する VM フレームワークみたいなのが作れて良いのになぁ,とか妄想したりも. んでまぁ,ここまで巨大なブラックボックスの上で世界が動いているという現状を考えると,やっぱりフォーマルメソッドには一定の限界があるのかなぁ,とか思うわけです. 原理的には,全てをロジックで記述し尽くして,プロファイルとか泥臭いことしなくても,(実時間の許す範囲で) 可能な限りの最適化とか可能だと思うんですけど.企業が秘密を握っている限り,それは不可能.実験と計測の世界のままです. やっぱり,プロセッサアーキテクチャもオープンになって欲しいというか,やはり究極的には,FPGA とかで,全て明確な世界に持ってくる必要があるのだと思います.アプリケーションの仕様に合わせて,逆算的に命令セットや,最適なハードウェアをロジカルに生成すると.まぁ,今のところは夢物語ですが. あー,分岐予測か.確かに.call/ret の組が無いと,どこからどこまでが関数なのかわからないとか,そういう話なのかな ?http://d.hatena.ne.jp/scinfaxi/20080711/1215724490 そういえば JVM とかも,手書きで作った変なパターンのバイトコードに対しては,あんまり JIT が効かないので,javac とかはむしろほとんど最適化しない,素直な構造のコードを吐くようになってるとかいう話があったような.つくづく x86 って,ハードウェアというよりは VM に近いよなぁ. 追記 敬愛している id:shinichiro_h さんと id:w_o さんに同時に dis られるという快挙を達成しましたので,大満足です!書いたかいがあるというもので,非常にうれしい.天にも昇る気分です (ドM)http://d.hatena.ne.jp/shinichiro_h/20080711#1215786569 http://morihyphen.hp.infoseek.co.jp/log2/200807.html#07110
C 言語/コンパイラ/BinaryHacks |TB:0 |CM:8 |
|
▲
コメント
こんにちは
> icc の最適化がすごくて,gcc とかは一生かなわないってのも,ある意味当たり前です.インテル社だけが,μOP の仕様や,それへの変換アルゴリズムなど,もろもろの内部の秘密テクノロジを知っているのですから,他のコンパイラベンダは,ベンチマークの結果から内部を推測して,最適化ルーチンを作るしかありません.そりゃ,一生追いつけませんよ
Vienna MAP vectorizer の backend optimizer
ftp://ftp.vcpc.univie.ac.at/projects/aurora/reports/auroratr2004-03.ps.gz
や
Rapidly Selecting Good Compiler Optimizations Using Performance Counters
http://www.cgo.org/cgo2007/presentations/cgo2007-p5-1-cavazos.pdf
の既存研究に見られるように、それなりに限られたアプリ用途なら、
インストラクションを流してプロファイルを取って CPU 内部の特性を govern して、その結果を元にインストラクションをいじってまた流してプロファイルを取って、、、、
というような処理を自動で行うことで、プログラムを CPU の内部仕様(uOP の仕様とか)を知らずともそれなりに最適化することができると思います(要素技術として機会学習、動的最適化, etc. を使う)
FFTW や Spiral プロジェクトなどはそのような最適化をやっている実例のひとつで、icc が吐くコードよりもよりよいパフォーマンスを得ることにも成功しています.
URL |
syoyo #-|2008/07/11(金) 02:29 [ 編集 ]
おー,そのやり方で,実際に icc より良いコードを得られたとか,すごいですね.
フィードバックだけでブラックボックスを最適化しようとするとか,まるでニューラルネットワークとかみたい.CPU が複雑になりすぎると,ハードウェアロジックというよりも,生物とか自然を相手にするような感じになってきて面白いですね〜 (笑)
こういうプログラムの自動最適化にとても興味がある (というか,将来的な研究テーマにすることを目指してます.今はそれの前段階の基礎理論を研究しています) 人なので,大変参考になりました.論文読んでみます.コメントありがとうございました!
URL |
あろは #AT7bd66s|2008/07/11(金) 10:44 [ 編集 ]
あろはさんはちょっと知識が偏っているような気がしますまる
RISCチップでは、サブルーチンをcallするときに戻り値番地がスタックにつまれないで、
適当なレジスタ(命令コードにしているフィールドがある)に値がロードされるのがあるとか。
そもそもスタック、なにそれというプロセッサもあるし。
どいつもこいつも低レベルな話というとすぐIA-32だ。(以下ジャギ様のような口調で(ry
それはさておき、だから実用的でないとかいう話は(多分)ないし、
>確かに.call/ret の組が無いと,どこからどこまでが関数なのかわからないとか
これも多分ない。
いちど EDSACエミュレーターでEDSACプログラミングを楽しみやがれッ(笑)
URL |
きむら(K) #grGQ8zlQ|2008/07/11(金) 15:27 [ 編集 ]
それは全くおっしゃる通りで,自分でも自覚してます.というか,僕が物心付いて,初めて PC に触った 2002 年には,既に x86 しか存在しない世界になってましたので (笑)
URL |
あろは #wNX6xxGw|2008/07/11(金) 18:01 [ 編集 ]
確かにcallとかretはなくてもなんとかなると思います。
アーキテクチャとかが絡んできて難しいですね。
callやretといった機械語命令がいつ頃から導入されたものかは知りませんが、
必要があって生まれたはずだと思います。
よく使われるから少しでもメモリやクロック数を節約したいとか、
あったらプログラマが楽に (可読性の向上, 記述する時間の短縮, レジスタを気にかける度合いを減らす) なるからとか。
こういう考え方もあるのかなと思います。
URL |
ココサブ #GpJA0K56|2008/07/11(金) 20:12 [ 編集 ]
いや〜,タイトルはなんとなくつけたものだから,本当にそう思ってるってわけでもないです (笑)なんとなく思いついたことを書いただけ.
>> よく使われるから少しでもメモリやクロック数を節約したいとか、
>> あったらプログラマが楽に (可読性の向上, 記述する時間の短縮, レジスタを気にかける度合いを減らす) なるからとか。
その通りだと思います.CISC は CISC で,RISC は RISC で,それぞれ考え方があって.以前はかなり論争もあったようですが.現在の x86 は,外見は CISC で,中身は RISC という,中間の形になってるってのが,面白いところだと思います.
だいたい,こういう類のどっちが良いか論争は,両極端はどっちもあんまり流行らず,非純粋な,中間の形の形態に落ち着く気が.
例えば,マイクロカーネル/モノリシックカーネルとかも,Linux みたいな,モノリシックカーネル + モジュールシステムの形で落としどころがついたり.
URL |
あろは #wNX6xxGw|2008/07/11(金) 20:59 [ 編集 ]
>こういうプログラムの自動最適化にとても興味がある (というか,将来的な研究テーマにすることを目指してます.今はそれの前段階の基礎理論を研究しています) 人なので,大変参考になりました.論文読んでみます.コメントありがとうございました!
おぉ、実は私も自動最適化に興味があります(専門はグラフィックスなので、コンパイラとか最適化は専門ではないのですが、非常に必要性を今感じています)。FFTW や Spiral のような自動最適化技術を web で調べていたときにはまったく日本の研究にはひっかからなかったので、日本にはそのようなことに興味のあるひとがいないのだろうかと思っていました。
ちょっと個別にメールを出しますので、もう少し込み入ってお話させていただきたいと思います :-)
URL |
syoyo #-|2008/07/13(日) 22:28 [ 編集 ]
私はどちらかというと,CG (OpenGL など向けの GPU programming や,挙げられていた論文のようなマルチメディア命令系)などの特定用途向けの (icc や LLVM のような) プロファイルに基づく自動最適化技術やコンパイラなどの言語処理系というよりは,もっと AI 的な方向に興味がある (実行環境に適応し,使われ方に応じて進化するようなソフトウェア)人です.
そして,今はそういう研究をするための土台,プログラム変換や自動生成の際の変換の正当性などに関する理論という,かなり遠回りなところから基礎研究を進めているので,グラフィックスが専門家の syoyo さんのように,比較的すぐに実用になるような技術を求めている方の興味とは少し方向性が異なる気がします (どちらかというと,実用性よりも,プログラミングという行為そのものに対する,哲学的な興味の方が強いのかも.もちろん,最終的には実用にならなければ意味が無いのですが)
他の(もっとハードウェアに近いようなレベルでの)自動最適化技術については,正直深くサーベイするような段階には至ってません (し,興味の方向性が異なる)のでよくわかりませんが.
自分がやっているような方向での,AI とプログラムの自動最適化技術の融合みたいな研究ってのは,あまり無いんじゃないかなと思っています (加えて,うちの研究室は,等価変換計算モデルという,ちょっと特殊な原理に基づいて,プログラミングという行為の体系的な研究を目指しているところなので,ますます独自色が強いと思います)
お恥ずかしいことに,未だにまとまった論文は書けてないのですが.もしよろしければ,この間学振に提出した研究計画書などをお見せすることはできると思います (未だに暗中模索状態なので,このあとどのように変わっていくかわからないのですが)
URL |
あろは #wNX6xxGw|2008/07/15(火) 18:39 [ 編集 ]
コメントの投稿
トラックバック
トラックバックURLはこちら
http://alohakun.blog7.fc2.com/tb.php/952-8ba8fbb4