B級科学者もどきの憂鬱

とある理系になりきれない奴のつれづれなる活動記

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最適化の限界について

プログラムを最適化するにあたって、
これ以上絶対に高速化できないという
限界はあるだろうかという考察。

本格的に考察し始めると
めちゃくちゃ複雑になりそうなので、
今回は非常に単純な場合のみに関して考える。

まず、CPUとプログラムにこれらの仮定を課す。
1.CPUは、一つ一つの命令を全て1クロックで実行できる
2.プログラムはデータの入力処理と出力処理を一度だけ持ち、
 それらは最適化対象には含まない
3.プログラム中の全ての命令はただ一度だけ実行される

このとき、n個の命令列で書かれたプログラムを、
最適化によって、全く同じ結果を返すm(<n)個の
命令列に変換出来れば、高速化できたことになる。

そのためには、CPUの持つ命令を使って、
m個の重複順列を作り、それを命令列として見て、
元のプログラムとの等価性を調べればいい。

等価性は、考えられる全ての入力に対して、
出力が元のプログラムと全く同じかどうかで判定できる。
非常に冗長な手段ではあるけど、
有限なので、少なくとも判定可能ではある。

つまり、仮定のようなプログラムとCPUであれば、
最適化の限界を決定することは可能だということだ。

逆に、一つでも上に書いた仮定を満たさない場合、
議論は途端に難しくなりそうだ。
1が無ければ、2クロック命令まで考慮しなくてはならない。
2が無ければ、判定可能であることの証明が難しい。
3が無ければ、条件分岐やループについて考えなくてはならない。

まぁ、この難しさをとりあえず無視できるように、
あの仮定を導入したんだけどw
誰か代わりに考えてー!

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://scientistb.blog42.fc2.com/tb.php/78-3ec24194
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

まとめ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。