* メモリアクセスの高速化
-(by [[K]], 2013.04.24)
** 通常のメモリアクセス
-OSECPUではたった一度のメモリアクセスに際して、これだけのメモリアクセスが必要になる。
--ポインタは上限より小さいか。[1]
--ポインタは下限より大きいか。[1]
--アクセスしたい領域はまだfreeされていないかどうかのシグネチャチェック。[3]
--実際のアクセス。[1]
--これはポインタレジスタがP02やP03などの実レジスタだった場合の話で、P05とかだったらポインタをロードするためのメモリアクセスもある。
--これらは[[memo0002]]の2013.04.10の(4)の[2]のレベルの場合の話。
-これはひどい。実際のメモリアクセスの6倍ものアクセスが発生してしまっている。これはいかにも遅そうだ。
--そしてあまりにも遅いと[2]のレベルを使う気がしなくなってしまう危険性がある。
** アイデア0
-ということで、こんなものを考えている。だいぶ前から考えていたんだけど、いくつかの案のうち結局これを最初に説明するのが一番いいんじゃないかと思う。
-OSECPUに専用のバッファを提供する。これは巨大なベクトルレジスタだと思ってもいい。これは整数レジスタを256本を束ねたものになっている。
-OSECPUに専用のバッファを増設する。これは巨大なベクトルレジスタだと思ってもいい。これは整数レジスタを256本を束ねたものになっている。
-このレジスタは256本をいっせいにメモリに読んだり書いたりすることができる。これに際しても前述のチェックは当然働くけど、それは1回で済むので256回の正味のアクセスに対してオーバーヘッドは5で済む。これなら2%ほどしかオーバヘッドがないことになる。
--バッファも結局はメモリなので、このバッファへのアクセスの分でさらに256回のアクセスが必要になる。
-このバッファは添え字をつけて任意の要素にアクセスすることができる。このとき、このバッファはfreeされないのでシグネチャチェックはないし、添え字に対するチェック機構はメモリアクセスを必要としない。
-結局、バッファに転送する際に(256*2+5)回のメモリアクセスが発生し、そしてその256本のデータにアクセスする際に256回のメモリアクセスが発生していることになる。だから3.02倍のアクセス量ということになる。これはまだ十分だとはいえないかもしれないけど、とにかく元の6倍よりは2倍も改善している。
--しかもそれでいて安全性に関しては全く妥協していない。
-この方法は256よりも少ない量の「端数」に対しては有効ではない。しかし大きい単位のときに高速化できれば、全体的な性能は十分に上がると思う。
** アイデア1
-結局性能が2倍しか上がらないのであれば、普通のアクセスで2個のレジスタにアクセスすればいいんじゃないかという気はする。
--でもそれだと正味2のアクセスに対して(2+5)=7のアクセスが発生するので、3.5倍程度にしか下がってない。
--それではということで、4個のレジスタにしたらどうだろうか。4に対して9のアクセスなので、2.25倍にまで下がる。実際は4個目のレジスタは仮想レジスタになるので、「ストア＋あとで実レジスタに持ち替える」コストで11のアクセスになる。そう考えると2.75倍といったところか。
** アイデア2
-そもそもチェックの量を減らすことはできないかという考え方もある。このためにコード内に制限区域というものを設定する。そして以下の制限がある。
--制限区域からは制限区域にしか分岐できない。外へ出ることも、外から入ってくることもできない。制限区域の上端から進入して、末端から出ていくことしかできない。中でループすることはできる。関数呼び出しももちろんできない。
--制限区域内では、管理下に置く管理下に置くポインタレジスタを複数指定できる。管理下に置かれると、そのポインタに対して、値を代入できなくなる。PADDでポインタをシークさせることはできる。許されない演算を試みれば、多くはJITCの段階で検出される。ポインタの上限や下限をプログラム内で所定の手順で明示的に比較して分岐していれば、JITCはそれらのチェックをユーザプログラムに任せてくれる（暗黙のチェックコードを生成しない）。
--制限区域内に入るとき、管理下に置かれたポインタレジスタはその指し示す先がfreeされないように、free禁止属性を付与される。これは制限区域から出るときに解除される。free禁止中に他のスレッドや他のタスクがfreeしようとしたら、それはもちろんエラー終了となる。
-これらの仕組みによってどのくらい高速化されるだろう。まず、シグネチャチェックはなくなる。そして上限下限チェックも、必要な時に必要な方向のみ行うだけになる（制限域内でPADDを実行しないのなら最初にしかチェックされない）。たとえばインクリメントしていくような場合を想定すれば、上限だけはチェックするだろう。
-これをアイデア1と組み合わせれば、アクセス数4に対してオーバヘッドは1にできる（x86の32bitモードでもオーバヘッド3）。つまり25%しか遅くならない（x86なら75%）。これは現実的な範囲ではかなり良いのではないかと思う。
-アイデア2の欠点はJITコンパイラが少々複雑になってしまうことである。・・・まあでも大したことはないかな・・・。

** 考察
-どのアイデアがいいだろうか。
-アイデア0のメリットは、自分でFPGAなどでCPUを作りさえすれば、バッファを全部本当にレジスタ化できてしまうというところだ。そうなれば本当に2%のオーバーヘッドだけで安全が得られてしまう。しかもこれは追加されたレジスタとしても活用できるし、レジスタに添え字アクセスが可能という点でも面白い。
-アイデア1のメリットは、x64やARMのように実レジスタが多いマシンでは、R00からR03はすべて実レジスタ化されるのが確実なので、2.25倍が実現できるということだ（オーバーヘッド125%）。これは現実的な値だと思う。
-アイデア2のメリットは、アイデア0やアイデア1との併用が可能で、しかもかなり高速化できるというところにある。
-どちらにしても、実際の処理内容はメモリアクセスだけではなく、各種の演算もある。だから体感速度が2%（アイデア0）や125%（アイデア1）増えるというわけではない。その半分以下だろう。だからそんなに悲観しなくてもいいのかもしれない。
-アイデア1とアイデア2は早めに対応するつもりだ。アイデア0は様子を見ながら検討する。

-Javaや.NETはどうしているのかというと、まずガーベージコレクト方式なので、シグネチャチェックに相当する処理はいらない。これはうらやましい。もちろんその代償はガーベージコレクト時に支払っているわけだけど、それでも1%未満の負荷上昇に抑えられているらしい。ポインタの上限下限問題についても、たぶん配列しか許さずに、配列の添え字チェックだけにしているのだと思う。オブジェクトポインタに対して++とかはできないから。
--まあでもOSECPUだってアイデア1とアイデア2の併用ならJavaや.NETと同程度になる。
--それにガーベージコレクトは、それはそれで問題を引き起こすことがあるようで、そのための対処テクニックがweb上で散見される。それにガーベージコレクトをやったら、osecpu.exeが複雑化するのではないかと僕は心配だ。

** こめんと欄
-このページにこめんと欄はありません。このページの内容にコメントしたいときは[[impressions]]にお願いします。
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS