レイヤーの合成アルゴリズム(2) MMXを使って高速化してみよう

前回ではレイヤー合成の基本的な考え方を見てみました。

基本式はいろんなページにありますが、それ以上につっこんだ記事はほとんど無いと思いますのでそれをやってみます。

今回はMMXを使った高速化にチャレンジしてみます。SSE2版ではちょっとアクロバティックなことをやりますので。

まずは高速化の前に必要な前情報からです。

除算式を乗算式に変更する

問題となるcaでの除算ですが、整数の除算は加算や乗算に比べてかなり遅い上に、MMXには除算を行う命令はありません。

なので、除算を別の演算でエミュレートする必要があります。

コラム:整数の除算ってどれくらい遅いものなのか?

これはCPUによってかなり違います。なので資料が簡単に手に入るIntelのCPUだけで論じてみたいと思います。

Intelのページには各命令を実行するのにどれくらいのクロック数が必要になるかを記述してある資料がありますのでそれから抜粋します。

命令はそれぞれadd、imul、idiv(すべて符号あり整数)のものを使います。なお、同じ名前のCPUでもコードネームで違うこともありますので、それも一緒に記述します。

CPUの種別 加算時のクロック数 乗算時のクロック数 除算時のクロック数
Pentium4(Northwood) 0.5 15-18 56-70
Core2Duo(Conroe) 1 3 17-41
Core i7(Nehalem) 1 3 11-21

よく言う、「Pentium4ではx5をするなら5回加算した方が早い」とはこういうことなんですね。(0.5 * 5 < 15)

命令発行までの時間だけなので、実際はもっとほかの要素(メモリペナルティなど)でこれより増えることはあります。

これを見ればわかりますが、除算は乗算よりかなり遅い(4倍から5倍ほどかかる)です。なお、Core2Duo(Penryn)以降の機能である「Radix 16 Divider」のおかげで

Corei7の除算クロックはかなり少なくなっているようです。

除算式は数学でもよくやりますが、逆数を用いることで乗算式に変更することができます。

普通に浮動小数なら

a / b = a * (1 / b)

の変換を使って、あらかじめ(1 / b)を計算しておけば乗算の計算に早変わり、というわけです。

整数でも同じようなことができます。これはあらかじめ誤差が出ないレベルでの大きい数cを用意して

a / b = a * (c / b) / c

の変換を使って、あらかじめ(c / b)を計算しておけば乗算の計算に早変わり、というわけです。(上と同じ事書いている・・・)

なお、このcは2の乗数を選んでおけば最後のcでの除算をビットシフトに変換できますので除算が無くなる、というわけです。c = 2 ^ nとして、

a / b = (a * (c / b)) >> n

という計算が使えます。なお、c / b = (1 << n) / bを計算するところはあらかじめテーブル計算としてレイヤー合成演算が始まる前に計算しておくのがいいと思います。

また、(1 << n) / bの演算はそのままやると整数の除算が0方向への丸めを行う関係上、乗算時に誤差が出ることになります。これはあらかじめつぶしておきましょう。

MMXを使ったレイヤー合成

というわけで、ここまでくればそれほど難しくありません。

MMXは64bitレジスタなので、ARGB8888のデータは16bit単位で扱えば普通に計算できます。

面倒なポイントは透過率の範囲が0~255なので、これをうまく演算できる形にすることと、乗算を行うとビット数が増えるのでそれを制御する必要がありことです。

今回は考え方だけ示しておきます。

逆数テーブルの作成方法

演算後の有効ビット数を考えて逆数テーブルを作る必要があります。値は15bitまでしか使用できないので注意が必要です。

16bit値を使用しようとしても、MSBは符号ビット扱いになるのでその部分を含めることができないからです。

演算後の有効ビット数を正確に把握する

前回出てきた式をそのまま変更してみます。出てくる関数を以下のように定義します。

MulBlend(a,b) a[0-255]とb[0-255]を乗算ブレンドして結果を0-255の範囲で返す
MulBlendInv(a,b) a[0-255]と(255-b)[0-255]を乗算ブレンドして結果を0-255の範囲で返す

これで計算をしてみると、

ca = sa + MulBlendInv(da,sa)

c’ = cs * MulBlendInv(sa,da) + cd * da

c = c / ca (= (c * invca) >> n)

caの値の範囲は[0-255]となりますが、c’の範囲は[0-65535]となります。

また、cの値の範囲は[0-255]となる必要があります。

計算手順

上の式をそのまま使うとするなら、

  1. caをMMXを使わずに計算しておく
  2. c’をMMXを使って並列演算(これはただのアルファブレンドの式)
  3. caから逆数テーブル(invca)を取得して乗算、シフト

MMX云々といっていたくせにMMXのコードがありませんでした。すみません。次回以降でコードを示すかもしれませんが・・・

それでは。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

この記事のトラックバック用URL