ペアリングの基礎

Pentium以降のCPUでは1clockの間に2命令以上実行できるようになりましたが, それにはいくつかの制限があります。ここではおおざっぱにその説明をします.
詳しくはこちらの有名な P5での最適化方法を参照して下さい

No. 001
Pentiumではuパイプとvパイプがあり, 通常はuパイプで1つずつ実行されますが, 条件が整った時にはその次の命令がvパイプで同時に実行されます.

絶対条件はuとvで実行される命令間に依存関係がないことです.
これはまあ当然といえば当然です.
それからuパイプでしか実行出来ない命令, 逆にvパイプでしか実行できない命令, どちらでも実行できる命令のグループがあるのでそれにも注意します.

他にも命令長の制限やプレフィクスなど細かいことがありますが, ここでは触れません.
No. 002
Pentiumにおいて
u, vどちらでもペアリング可能な命令群
`簡単'な命令は大抵このグループに属します.
add, sub, and, or, xor, cmp, test, dec, inc, lea, mov, nop, push, popなど.

uパイプのみでペアリング可能な命令群
少し複雑な命令がこのグループに属します.
adc, sbb, rcl, rcr, rol, ror, sal, sar, shl, shr(clを使わない時のみ)など.

vパイプのみでペアリング可能な命令群
ジャンプ関連の命令がこのグループに属します.
call direct, jcc, jmp shortなど.

ペアリング出来ない命令群
その他の複雑な命令がこのグループに属します.
mul, divなどは当然として, 何故かneg, not, movsx, movzxも該当します.
No. 003
K6-2, K6-IIIでは内部でRISCに変換するため同じ訳ではありませんが体感的にはcarryを伴う演算 adc, sbb がペアリング不可, 逆に neg, not は可能でした. またレジスタのサイズによっても変化します. (後日触れます)
PPro, PII, PIII, Athlonは全然違います. (これについても触れられれば...)
No. 004
具体例として256色パレット画像を16bitカラー画像に変換する方法を考えます
    ebx = src     (256入力画像)
    ecx = counter (画素数)
    edi = dest    (16bit出力画像)
    ebp = palette (各パレットを16bitカラーに変換するテーブル)

    xor   eax,eax
.lp:
    mov    al,[ebx]        ;u-1
    inc    ebx             ;v-1
    mov    si,[ebp+eax*2]  ;u-2
    mov    [edi],si        ;v-2
    add    edi,2           ;u-3
    dec    ecx             ;v-3
    jnz    short .lp       ;v-4
*PPro系CPUでは1行目は movzx eax,byte [ebx] の方がよいです... *

u, vのペアは同時実行されるので全部で4clockかかる(はず)です.
ただPentiumではAGIストールと呼ばれるペナルティがあります.
アドレスに使うレジスタは1clock以上前に確定しないと駄目 という話なのですが, 小さいループではこれが結構足枷になります.
上の例ではu-2がそれに該当するのでそこで1clock遅れ結局は5clock/1loopかかります.
No. 005
では完全ペアリングを目指して修正します.
全部で7命令と奇数なので1命令減らします.
そのため edi とカウンタを共有します.
    lea    edi,[edi+ecx*2] ;edi = edi + counter * 2
    neg    ecx             ;ecx = -counter
.lp:
    mov    al,[ebx]        ;u-1
    inc    ebx             ;v-1
    mov    si,[ebp+eax*2]  ;u-2 3
    mov    [edi+ecx*2],si  ;u-4
    inc    ecx             ;v-4
    jnz    short .lp       ;u-5
では命令の順序を並び換えます.
v-1とu-2をなるべく離すようにするのです.
No. 006
    lea    edi,[edi+ecx*2] ;edi = edi + counter * 2
    neg    ecx             ;ecx = -counter
    mov    al,[ebx]
    inc    ebx
    mov    si,[ebp+eax*2]
    inc    ecx
    jz     .quit
.lp:
    mov    al,[ebx]        ;u-1
    inc    ebx             ;v-1
    mov    [edi+ecx*2],si  ;u-2
    inc    ecx             ;v-2
    mov    si,[ebp+eax*2]  ;u-3
    jnz    .lp             ;v-3
.quit:
    mov    [edi+ecx*2-2],si
ループの中の順序が入れ替わったので前処理と後処理が必要になりやや複雑になりましたが, これで3clock/1loopとなりました.
次回はループをほぐしてより高速化出来るか検討します.
[Back]
御意見は光成滋生<herumi@nifty.com>までお願いします