x86/x64における小数から整数への丸め処理命令の変遷 - Cybozu Inside Out

こんにちは、サイボウズ・ラボの光成です。

今回は小数を整数に丸める処理に関して、x86/x64における命令がどのように変わってきたかを紹介します。

C++における小数から整数への変換ルール

まずC++における浮動小数点数型（float, double）を整数型（int, int64_tなど）に丸めるルールをおさらいしましょう。 floating-integral conversionsによるとその変換では小数点部分を取り除きます。つまり1.5, 2.3, -2.9をintにキャストするとそれぞれ1, 2, -2になります。

なお整数型に入りきらないときの挙動は未定義です。

4種類の丸め規則

x86の浮動小数点数を扱うFPUは丸め処理のモードを4種類持ちます。これはIEEE標準754の丸めモードの規則に従ったものです。

最近接丸め（round to nearest（even） : RN）
切り捨て（round down toward -∞ : RD）
切り上げ（round up toward +∞ : RU）
0への丸め（round toward zero（truncate） : RZ）

f:id:cybozuinsideout:20170814151516p:plain

それぞれの処理を図にしてみました。矢印で示される区間内の値が矢印の先の整数に丸められます。黒丸●はその点を含み、白丸○は含まないことを意味します。

切り捨ては負の無限大方向に切り捨てる、切り上げは正の無限大方向に切り上げます。それぞれfloor()関数、ceil()関数に相当します。 0への丸めは0に向かう方向に切り捨てます。doubleからintにキャストするときのルールはこれに相当します。

最近接丸めは若干馴染みが無いかもしれません。通常よく使われる四捨五入では1.5, 2.5, 3.5は全て2, 3, 4と切り上げます。しかし、この方法だと多数の値を処理したときに全体として正の方向に大きくなる可能性があります。そこで端数が0.5のときは偶数に向かう方向に処理します。つまり0.5は0に、1.5は2に、2.5は2になります。こうすると多数のランダムな値に対しては切り上げと切り下げが均等になります。

丸めモードの中に四捨五入はありません。これはxが0以上なら0.5を足し、xが負なら0.5を引いて0へ丸めればよいからです。

コードとしては

double round(double x)
{
    double c = (x >= 0) ? 0.5 : -0.5;
    return (double)(int)(x + c);
}

で実現できます。

昔のx86における整数型への変換方法

FPUの丸めモードは、通常最近接丸めに設定されています。そうするとdoubleをintにキャストするにはモードを変更しなくてはなりません。もしかしたらプログラム実行中にどこかでモードが変更されているかもしれないので、

現在の丸めモードを取得して保持する
丸めモードをRZに変更する
fist命令でdouble→intキャストを行う
丸めモードを1.で取得したモードに戻す

という処理が必要になります。 FPUのモードを変更するのはなかなかコストが大きく、多数の小数を整数に変換する際にはそこがボトルネックになることもありました。この状況はベクトル演算命令が追加されたSSE, SSE2でも変わりませんでした（cvtsd2si ～2004年）。

2017/8/21加筆。「丸めモードを変更・に依存せずに0切り捨てを行う手法は遅くとも1997年には存在した」というご指摘があったので最終段に「Pentium4での改良点」の段を加筆しました。

0への丸め命令の追加

そこでIntelはSSE3で0への丸め専用命令（fisttp, cvttsd2siなど）を追加します（2004年）。これはFPU/SSEの制御レジスタに関わらず常に0への丸めを行う命令です。そのためdoubleからintへのキャストを丸めモードを変更せずに実現可能となり、処理性能が向上しました。

切り捨て、切り上げ対応命令の追加

intへのキャストは高速に処理できるようになっていましたが、floor()やceil()関数の実装では従来のintへのキャスト同様、丸めモードを変更するか、あるいは符号を考慮しつつcvttsd2siをうまく使う必要がありました。そこで丸めモードを自由に設定できるroundsdなどの命令がSSE4.1で追加されました（2007年）。

roundsd  xmm1, xmm2/mem, imm8
vroundsd xmm1, xmm2, xmm3/mem, imm8

vroundsdはAVXで追加された命令です（2011年）。 imm8で丸めモードを指定できます。

たとえば前述のround関数は次のように実装できます。浮動小数点数の符号は最上位ビットにあるので条件分岐を使わずに実装しています。

// xmm0にxが入っているとする
vandpd   xmm1, xmm0, ptr [const1] // xの符号ビットを取り出す
vorpd    xmm1, xmm1, ptr [const2] // xmm1 = (x >= 0) ? 0.5 : -0.5
vaddsd   xmm0, xmm0, xmm1         // xmm0 += xmm1
vroundsd xmm0, xmm0, 3            // truncate

const1: // 最上位ビットが符号ビット
  dd 0x00000000
  dd 0x80000000
  dd 0, 0
const2: // double(0.5)のビットパターン
  dd 0x00000000
  dd 0x3fe00000
  dd 0, 0

ただfloorやceilは整数が欲しいときに使うことが多いのにroundsd命令は結果が浮動小数点数型なので, 更にもう一度cvtsd2si命令を使って整数レジスタに変換しなければなりません。冗長な感じがします。

AVX-512命令

2016年IntelはAVX-512対応CPUを発表しました。従来の256ビットSIMD命令だったAVX-2を2倍に拡張することで512ビットSIMD命令が使えるようになりました。同時にほとんどの演算命令に個別に丸めモードを指定できるようになっています。

従来のvcvtsd2siも拡張されています。したがってこれ1命令でdoubleからintへの切り上げ、切り捨て、0への丸めが可能になりました。

アセンブリ言語では

vcvtsd2si eax, xmm0, {rn-sae}

のように指定します。", {rn-sae}“のカンマや丸括弧が気持ち悪い（というかパースしにくい）ですがこのように指定します。saeはSuppress All Exceptionsの略で小数演算例外を抑制します。

対応するintrinsic命令は _mm_cvt_roundsd_i64(__m128d, int r)です。

ただ手元で実験した限り、NASM 2.14rc0でアセンブルすると{rn-sae}を無視したコード生成をするようです（バグ? 報告してみました）。 intrinsic関数についてはVisual Studio 2017は非対応で、gcc-7.1やclang-4でコンパイルエラーになりました（もしかしたら私の使い方が悪いのかもしれません→2017/8/16 「intrinsic関数での使い方」で加筆）。

拙作のXbyakはAVX-512に対応しておりたとえばvcvtsd2si(eax, xmm0 | T_rn_sae);と記述できます（サンプルコード round.cpp）。 AVX-512対応CPUを持っていない人でもIntel Software Development Emulatorを使えば正しく動いていることを確認できます。

sde -- round.exe

intrinsic関数での使い方

_mm_cvt_roundsd_i64(__m128d, int r)のrに指定する丸めモードはRN, RD, RU, RZに対応する0～3の整数ではなく、それと8（SAE）とのorをとる必要がありました。_mm_round_pdなら0～3を指定できるので私はそれと同じだと思い込んでいました。

int x = _mm_cvt_roundsd_i64(m1, 0); // error: incorrect rounding operand
int y = _mm_cvt_roundsd_i64(m2, 0 | 8); // ok

0, 1, 2, 3, 8はヘッダでそれぞれ

#define _MM_FROUND_TO_NEAREST_INT 0
#define _MM_FROUND_TO_NEG_INF     1
#define _MM_FROUND_TO_POS_INF     2
#define _MM_FROUND_TO_ZERO        3
#define _MM_FROUND_NO_EXC         8

と定義されているのでこれらのマクロを利用してもよいでしょう。

Pentium4での改良点

昔の資料を探して1997年のIntelの最適化マニュアルに「丸めモードの変更を避けるアルゴリズム」が載っていたことを確認しました。情報ありがとうございます。ただ記事では省略したのですが2000年に登場したPentium 4では丸めモード（＋α）のみを変更するときに限りfldcwが高速化されています。そのためマニュアルにも書かれていますが2種類の丸めモード間で切り替えるだけのときは丸めモードを変更する方が速そうです（未確認）。