Intelプロセッサ最適化マニュアルを読もう

今まである程度は読んでたけど, 『Intel 64 and IA-32 Architectures Optimization Reference Manual』を読み直して, 気づいたことなどをまとめてみようという試み.
今手元にあるのは248966-024 April 2011のもの. 日本語版もありますが, 多少古いので英語版がよいでしょう.

表記について
プロセッサと書いたり, CPUと書いたりします.
Intel64をx64と書いたりします. 例えば3サイクルのことを個人的な慣習で3clkと書くことが多いです. すいません.

間違いなどございましたらメール(herumi@nifty.com)か@herumiにお願いします.


2章 Intel64/IA-32 CPUアーキテクチャ
2.1 Sandy Bridge概要
1サイクルあたり, 最大6μop(マイクロオペレーション)の発行. L1命令キャッシュは32Kbyte.
命令predecode

命令キャッシュから16bteずつ読んで命令長を決定する. 命令長を変更するプレフィックス(LCP:length changing prefix)があるとLCPあたり3clkのペナルティがある. 以前のCPUでは16byteあたり6clkのペナルティだった. 16byte内に2個以上LCPが無ければSandy Bridgeの方が優れている.
LCPは次のものがある:

命令deocde

命令をμopに変換する4個のユニットがある. 一つは全ての命令を最大4個のμopに変換する. 残りの三つは一つのμopのみを扱う.

マイクロフュージョン

複数のμopを一つの複雑なμopに変換する. メモリへの書き込み, メモリからの読み込みと何らかの演算, 読み込みとジャンプの形はマクロフュージョンされる.
rip相対アドレスアドレッシングはフュージョンされない.

マクロフュージョン

二つの命令を一つの簡単なμopに変換する. ある条件の元でcmp, test(Nehalemまで), add, sub, and, inc, dec(Sandy Bridgeから)と条件分岐がペアになったときにマクロフュージョンされる(詳細は略).

デコードされたicache

命令のデコーダの出力結果を保持する. 次回からは命令でコードをせずに, icacheから直接実行することで効率化する. SSE命令を多用すると命令長が長くなるので命令predecodeの制約(1clkに最大16byte)にひっかかることがあるが, icacheがあると大丈夫.
# perfでL1命令キャッシュミスをみてみる参照.

分岐予測ユニット(BPU:branch prediction unit)

条件分岐や直接call, jump, 間接call, jumpやretなどに対して予測する.

2.1.3 out-of-orderエンジン
命令の依存関係を検出して正しいデータフローを保ったまま実行命令の順序を入れ換える. 主にリネーマ(renamer), スケジューラ(scheduler), リタイアメント(retirement)の三つの部分からなる:
リネーマ

命令を実行コアに移動する. 複数のμop間の偽の依存関係を排除する. 1clkあたり最大4μopを移動する. zeroイデオム(後述), nop, vzeroupper, fxchgなどの命令はこの処理の中で実行されてパイプラインからは消える. indexレジスタを使うメモリアドレッシングは二つのμopに分解される.

スケジューラ

μopの全てのソースオペランドの値が確定したら, そのμopを実行可能として実行ユニットに割り当てる. 実行ユニットは6ポートあり, 1clkあたり各ポートに一つ, 最大6μopを割り当てる.

リタイアメント

命令やμopを正しい順序でリタイアする. フォールトや例外も扱う.

依存中断イデオム(dependency breaking idiom)

命令の並列性はレジスタの中身を0クリアすることで改善できる. リネーマはzeroイデオム, つまりデスティネーションレジスタが0になる命令群, たとえば

  xor reg, reg

などを検出する. 他には
xor, sub, pxor, vpxor, psubb/w/d/q, vpsubb/w/d/q, xorps/pd, vxrops/pd などがある.

実行コア

命令を順序に関係なく(out-of-order)スーパースカラーで実行する. out-of-orderコアは三つの実行スタックからなる. 各スタックはデータの型(汎用整数, SIMD整数と浮動小数点数, x87)をカプセル化する.

実行後, データはライトバックバス(writeback bus)に書き込まれる.

異なるスタック間でデータ(SSE-intとSSE-fpの間でも)をやりとりする場合は, 1clkのレイテンシが発生する.

2.1.5 キャッシュ階層
最初のレベルのデータのキャッシュ(L1 Data)は32Kbyte. 次のキャッシュ(L2)は256Kbyte. 三つ目のキャッシュ(LLC:last level cache)は0.5~2MB.
キャッシュの整合性はMESIプロトコル(Modified/Exclusive/Shared/Invalid)を用いて維持される.
# MESIプロトコルについてはいずれ
読み込み

LLCは他の全てのレベルのキャッシュを含む. LLCの各キャッシュラインには, それがL2やL1キャッシュにあるかもしれないという目印(indication)が付与されている.

cache latency
レベル レイテンシ
L1 Data4
L2 12
LLC 26~31
他のコアのL2やL1 cleanなら43, dirtyなら60

キャッシュの検索時に他のコアからデータをフェッチする必要がないならcleanという. そうではなくて, 他のコアのキャッシュから修正されたデータをフェッチしなければならないとき, dirtyという.

書き込み

メモリを書き込む際, L1キャッシュ内のそのメモリラインがE(排他), またはM(変更)状態であることを確認する. もし, 正しい状態で, キャッシュラインが無かったら, 次のメモリ階層からRFO(Read for Ownership)に従ってデータをフェッチする.

キャッシュラインは次の順序で探される:

  1. L1
  2. L2
  3. LLC
  4. あるなら他のコアのL2とL1
  5. メモリ
ストアフォワーディング

データを書き込んだあと, そのデータを読み直す場合, store操作からload側に直接データを転送することができる. これによりサイクルを短縮できる. 但しいくつかの条件がある. ざっくり言うと, データのアライメントがあっていて, それをまたがず, かつstoreよりもloadのサイズが小さい場合のみ可能.

10章 SSE4.2 テキスト処理
いくつかの実装例はhttps://github.com/herumi/mie/. スライドはQuick Search algorithm and strstr.
10.2 SSE4.2文字列処理命令
pcmpestri, pcmpestrm, pcmpistri, pcmpistrmは文字列処理のための命令群. 文字列の長さの取得や文字列比較などを行う.
文字列の種類と結果取得による命令の選択

pcmpXstrY命令は, 文字列として0終端なものかサイズ指定のもの, そして出力結果の取得方法によって使う命令が変わる.

文字列処理命令
0終端による不定長文字列を扱う(i) edx/eax指定による固定長文字列を扱う(e)
処理の結果をecxに出力する(i) pcmpistri pcmpestri
処理の結果をxmm0のビットマスクに出力する(m) pcmpistrm pcmpestrm

これらの命令には8bitの即値(imm8)を指定することで様々な機能を選択できる.

imm8[0] : 入力データの型の選択

imm8[0]が0ならbyte(1byte), 1ならword(2byte)となる.

imm8[1] : 入力データの符号選択

imm8[1]が0なら符号無し, 1なら符号ありとなる.

imm8[3:2] : 集計操作の選択

文字列の比較方法を選択できる.

00b : equal any
マッチする最初の文字を探す.
初期値を0として各要素ごとに文字が等しいかどうかを調べて結果をorで蓄積する.
01b : ranges
範囲内から文字列を探す.
初期値を0として各要素ごとに文字が範囲に入っているかどうかを調べて結果をorしてく. 範囲指定はオペランドの偶数に範囲の始まり, 奇数番目に範囲の終わりを入れておく.
10b : equal each
文字列比較をする.
各要素ごとに文字列が等しいかを調べる.
11b : equal ordered
部分文字列比較をする.
初期値を~0として各要素ごとに比較した結果をandで蓄積する. Intelのマニュアルの擬似命令による表記がよく分からん. 多分下記の擬似コードなんだと思う.
 比較命令 str, text, imm8のimm8[3:2]に関する部分の擬似命令

 src ← 検索したい文字列
 text ← 検索対象のテキスト
 int len = (入力の型がbyte) ? 16 : 8;

 switch (imm8[3:2]) {
 case 00b:
    for (int j = 0; j < len; j++) {
        int tmp = 0;
        for (int i = 0; i < len; i++) {
            tmp |= text[j] == str[i];
        }
        IntRes1[j] = tmp;
    }
    break;
 case 01b:
    for (int j = 0; j < len; j++) {
        int tmp = 0;
        for (int i = 0; i < len; i += 2) {
            tmp |= (str[i] <= text[j]) && (text[j] <= str[i + 1]);
        }
        IntRes1[j] = tmp;
    }
    break;
 case 10b:
    for (int j = 0; j < len; j++) {
        IntRes1[j] = text[j] == str[j];
    }
    break;
 case 11b:
    for (int j = 0; j < len; j++) {
        int tmp = 1;
        for (int i = 0; i < len - j; i++) {
            tmp &= text[j + i] == str[i];
        }
        IntRes1[j] = tmp;
    }
    break;
 }
invalid文字の扱い

上記比較の際に, EOS(end-of-string)を越えた部分の文字はinvalidとして処理できる. invalidな文字とvalidな文字との比較は次のルールに従う.

文字比較結果
xmm1(str) xmm2(text) equal any ranges equal each equal ordered
valid valid 通常通り 通常通り 通常通り 通常通り
valid invalid 常に0 常に0 常に0 常に0
invalid valid 常に0 常に0 常に0 常に1
invalid invalid 常に0 常に0 常に1 常に1
imm8[5:4] : 中間結果操作

polarity(極性) : 各文字に対して集計操作をするときに反転操作などの操作を挿入できる.

00b : positive polarity
そのまま(IntRes2 = IntRes1)
01b : negative polarity
ビット反転(IntRes2 = ~IntRes1)
10b : masked(+)
そのまま(IntRes2 = IntRes1)
11b : masked(-)
入力がinvalidならそのまま, そうでなければ反転
imm8[6] : 最終結果操作

pcmpestri, pcmpistriとpcmpestrm, pcmpistrmそれぞれについて2種類の方法を設定可能.

pcmpestri, pcmpistriに対する設定
0ならIntRes2のLSBが入る.
1ならIntRes2のMSBが入る.
ただしIntRes2 == 0なら16(byteのとき)か8(wordのとき)となる.
pcmpestrm, pcmpistrmに対する設定
0ならIntRes2が0拡張されてxmm0に入る.
1ならIntRes2の各ビットが入力データの型の大きさにしたがって1byteか2byte単位のマスクに拡張されてxmm0に入る.
明示的な長さ指定

pcmpestri, pcmpestrmの二つの命令の'e'はexplicit lengthの意味. eaxで一つ目の文字列(str)の長さ, edxで二つ目の文字列(text)の長さを指定する.

フラグレジスタ

これらの文字列処理命令は同時にフラグレジスタも変更する.

文字列処理命令によるフラグ変化
pcmpestri/pcmpestrm pcmpistri/pcmpistrm
CF IntRes2 != 0
ZF |edx| < 16(or 8) 二つ目のオペランドのどれかのbyte/wordが0なら1. そうでなければ0
SF |eax| < 16(or 8) 一つ目のレジスタのどれかのbyte/wordが0なら1. そうでなければ0
OF IntRes2[0]
equal orderedのサンプル

複雑なのでIDF Shanghai 2008にあるPhoto46の右下の図で確認してみよう.

equal ordered sample
text文字列 : "BABCAB\0S"
7 6 5 4 3 2 1 0(j)
'S' '\0' B 'A' 'C' 'B' 'A' 'B'
src文字列 : "ABCA\0XYZ" 0(i) 'A' fF fF F T F F T F
1 'B' fF fF T F F T F x
2 'C' fF fF F F T F x x
3 'A' fF fF F T F x x x
4 '\0'fT fT fT fT x x x x
5 'X' fT fT fT x x x x x
6 'Y' fT fT x x x x x x
7 'Z'fT x x x x x x x

"BABCAB\0S"から"ABCA\0XYZ"を探すサンプルである. '\0'の後ろに文字があるが見ないので(invalid)何であっても影響はない.

文字列命令を実行すると, byte単位での文字列なら内部で16x16(上記サンプルは8x8になってるが)のTrue/Falseのテーブルができる.

'\0'以後の文字列はinvalidとなり, 「invalid文字の扱い」におけるルールに従ってsrc文字列の'\0'以後はfT(force True), text文字列の'\0'の後はfF(force False)となっている.

equal orderedの場合は右上から左下への対角成分の論理積をとるので順に, F, T, F, F, F, F, F, FとなりIntRes1 = 0b00000010となる.

strlen by SSE4.2

さてstrlen()を実装する場合を考えてみよう. 位置情報がそのまま欲しく, 0終端の文字列を扱うのでpcmpistri.

符号無しbyte単位なのでimm8[0] = imm8[1] = 0. 集計は0なもの探索の否定, つまり1~255に入ってるを見るためrangesを選択する. よってimm8[3:2] = 01b.

中間結果操作はビット反転なのでimm8[5:4] = 01b.

最終結果は下から何ビットかをみたいのでLSB. よってimm8[6] = 0. 全部合わせてimm8 = 0x14となる.

テキストに0が含まれればZF = 1となるのでそれでループする.

// 上記 Phot47にあるソースコード(注意 : これは遅い)
int sttni_strlen(const char *src)
{
    char eom_vals[32] = { 1, 255, 0 };
    __asm{
        mov eax, src
        movdqu xmm2, eom_vals
        xor ecx, ecx
    topofloop:
        add eax, ecx
        movdqu xm1, oword ptr [eax]
        pcmpistri xm2, xm1, imm8
        jnz topofloop
    endofstring:
        add eax, ecx
        sub eax, src
        ret
    }
}

Intelの当初の解説には「こうせよ」あったようだが, 今のマニュアルには遅いのでこれは使うなとのこと. 理由はpcmpistriでecxが確定するまでアドレス解決ができないためout-of-order実行ができないからだそうな.

殆どの場合はecx = 16になるので次のようにせよとある. 実際ベンチマークをとってみるとかなり差がでる.

// Xbyakによるstrlen by SSE4.2
struct StrlenSSE42 : Xbyak::CodeGenerator {
    StrlenSSE42()
    {
        using namespace Xbyak;
#if defined(XBYAK64_WIN)
        const Reg64& p1 = rdx;
        const Reg64& c = rcx;
        const Reg64& a = rax;
        mov(rdx, rcx);
#elif defined(XBYAK64_GCC)
        const Reg64& p1 = rdi;
        const Reg64& c = rcx;
        const Reg64& a = rax;
#else
        const Reg32& p1 = edx;
        const Reg32& c = ecx;
        const Reg32& a = eax;
        mov(edx, ptr [esp + 4]);
#endif
        mov(eax, 0xff01);
        movd(xm2, eax);

        xor(c, c);
        lea(a, ptr [p1 - 16]);
    L("@@");
        add(a, 16);
        pcmpistri(xm2, ptr [a], 0x14);
        jnz("@b");
        add(a, c);
        sub(a, p1);
        ret();
    }
};

cf. strlen for SSE4.2のベンチマークをとってみた.

intrinsic version of strlenSSE42

pcmpistriは出力をecxとフラグの二つを出力するのに, intrinsic版は戻り値を一種類しかとれない. 仕方がないのでecxを取得する_mm_cmpistriや, ZFフラグを取得する_mm_cmpistrz, 他には_mm_cmpistrc(CF取得)などいくつか種類がある.

pcmpistriなどのintrinsic命令
返り値 pcmpestri pcmpestrm pcmpistri pcmpistrm
ecx/xmm _mm_cmpestri _mm_cmpestrm _mm_cmpistri _mm_cmpistrm
CF = 0 && ZF == 0 _mm_cmpestra _mm_cmpistra
CF _mm_cmpestrc _mm_cmpistrc
OF _mm_cmpestro _mm_cmpistro
SF _mm_cmpestrs _mm_cmpistrs
ZF _mm_cmpestrz _mm_cmpistrz

IntelのマニュアルにはAFは常に0とあるので_mm_cmpestraって何を返すの?と思った. MSDN(_mm_cmpestra)には, IntRes2 == 0かつedxの絶対値が16(or 8)以上のときは1とある. それから推測すると多分CF == 0 && ZF == 0を返す.

ループ内では_mm_cmpistrzを使ってループを抜けたら_mm_cmpistriを使うのは無駄だなあと思っていたが, 試してみたgcc(4.4.5)もVC10も命令が一つにまとめられていた. 抜かりはないなあ.

#ifdef _WIN32
  #include <intrin.h>
#else
  #include <x86intrin.h>
#endif
size_t strlenSSE42_C(const char* top)
{
    const __m128i im = _mm_set1_epi32(0xff01);
    const char *p = top - 16;
    do {
        p += 16;
    } while (!_mm_cmpistrz(im, *(__m128i*)p, 0x14)); // ZF
    p += _mm_cmpistri(im, *(__m128i*)p, 0x14); // get ecx
    return p - top;
}

(注意)上記コードはたまたまうまく動くが危険. pcmpistri自体はアライメントされていないメモリについても動作するが, *(__m128i*)pは場合によってはmovdqaが発行されて例外で落ちてしまうことがある. _mm_loadu_si128((const __m128i*)p)を使うべき. SSE4.2の文字列処理命令の紹介に関する補足も参照してください.

これが次のように出力された(これはgcc 4.4.5の例).

    lea rax, [rdi-16]
    movdqa  xmm0, XMMWORD PTR .LC3[rip]
    .p2align 4,,10
    .p2align 3
.L98:
    add rax, 16
    pcmpistri   xmm0, XMMWORD PTR [rax], 20
    jne .L98
    movsx   rcx, ecx ; pcmpistriの結果のecxを流用してる
    add rax, rcx
    sub rax, rdi
    ret

これがgcc 4.6.0だと少しループ処理が違う. よりpcmpistriのアドレス生成に使う計算を先にすませようとしている. 試してみると文字列長が短いところでは若干速いが, 長いところでは逆に若干遅い雰囲気.

    lea rdx, [rdi-16]
    movdqa  xmm0, XMMWORD PTR .LC0[rip]
    jmp .L11
    .p2align 4,,10
    .p2align 3
.L12:
    mov rdx, rax
.L11:
    lea rax, [rdx+16]
    pcmpistri   xmm0, XMMWORD PTR [rdx+16], 20
    jne .L12

ちなみにVCもgccもループから抜けたところでecxからrcxを作るためにmovzxを呼んでいたけど必要なのかな. パーシャルレジスタストールでも発生するのだろうか.

1st:2011/06/22, last update:2016/08/29

御意見は光成滋生<herumi@nifty.com>までお願いします