Ice Lakeプロセッサは整数除算がアツい　数値計算編

下記の前回の記事でIce Lakeプロセッサは整数除算命令が強化されていることが実験を通じてわかった．

lcstmarck.hatenablog.com

ただこの記事では単にidiv命令をただ実行しまくっただけなので，特に意味がない処理をしている．そのため，もう少しだけそれらしい処理をさせて整数除算が強化されているかどうかをもう少しだけ見ていこうと思う．

今回は多倍長整数除算の処理をさせていく．といっても，除数と被除数が共に任意精度の時の除算処理は実装が非常に大変であるため，除数に関しては1ワードのみとし「（多倍長整数） / （1ワード整数）」の計算の処理とした．

実装

以下が簡易的多倍長整数除算の実装である．

（追記：aやbなどはuint32_tで十分というご指摘をいただきました．ありがとうございます．）

void divide(uint32_t *a, uint32_t b, uint64_t len, uint32_t *q, uint32_t r){

    int i;
    uint64_t tmp;
    for(i=len-1; i>=0; i--){

        tmp = (a[i+1] << 32) | a[i];
        q[i] = tmp / b;
        a[i] = tmp % b;
    }

    r = a[0];
}

除算は複雑であるがゆえに，「2ワード / 1ワード」というシンプルな除算ですら実装が難しい．したがって簡単のため，「128ビット / 64ビット」ではなく「64ビット / 32ビット」の計算に出来るようにするため，uint64_t変数tmpにuint32_t変数を2つ詰めて計算をすることにした．そのため除算の前にシフト演算等を行なっている．

本実験の主眼はプロセッサの除算命令の演算能力を見ることなので，被除数の配列が壊れてしまうなどの問題点こそあるが，正しく商と剰余が計算できていたのでこれで良しとした．

また以下が実装した除算関数のobjdumpの出力である．下線部のように符号なし除算命令であるdiv命令が実行されることが確認できた．

00000000000009f0 <divide>:
    for(i=len-1; i>=0; i--){
 9f0:   83 ea 01                sub    $0x1,%edx
 9f3:   78 2e                   js     a23 <divide+0x33>
 9f5:   4c 63 ca                movslq %edx,%r9
 9f8:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
 9ff:   00
        tmp = (a[i+1] << 32) | a[i];
 a00:   4a 8b 44 cf 08          mov    0x8(%rdi,%r9,8),%rax
 a05:   31 d2                   xor    %edx,%edx
 a07:   48 c1 e0 20             shl    $0x20,%rax
 a0b:   4a 0b 04 cf             or     (%rdi,%r9,8),%rax
 a0f:   48 f7 f6                div    %rsi
        q[i] = tmp / b;
 a12:   4a 89 04 c9             mov    %rax,(%rcx,%r9,8)
        a[i] = tmp % b;
 a16:   4a 89 14 cf             mov    %rdx,(%rdi,%r9,8)
 a1a:   49 83 e9 01             sub    $0x1,%r9
    for(i=alen-1; i>=0; i--){
 a1e:   45 85 c9                test   %r9d,%r9d
 a21:   79 dd                   jns    a00 <divide+0x10>
    }

    r = a[0];
 a23:   48 8b 07                mov    (%rdi),%rax
 a26:   49 89 00                mov    %rax,(%r8)
}
 a29:   c3                      retq
 a2a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

実験

今回実験に使用したプロセッサは以下の3つである．

Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz　（Coffee Lake）
Intel(R) Core(TM) i7-7820X CPU @ 3.60GHz　（Skylake-X）
Intel(R) Core(TM) i3-8121U CPU @ 2.20GHz　（Cannon Lake）

また被除数のワード数を4096ワードとし，これを3000回実行した．この除算関数を3000回実行した実行時間を取って比較することとした．

実験結果

"Time: ~~ [ms]"が除算関数の総実行時間である．

Coffee Lake @ 2.70GHz

$ time ./a.out

Time: 114.418000 [ms]

real 0m0.122s

user 0m0.115s

sys 0m0.003s

Skylake@ 3.60GHz

$ time ./a.out

Time: 99.025000 [ms]

real 0m0.102s

user 0m0.100s

sys 0m0.000s

Cannon Lake（実質Ice Lake）@ 2.20GHz

$ time ./a.out

Time: 89.798000 [ms]

real 0m0.094s

user 0m0.093s

sys 0m0.000s

動作周波数の観点でいうと「Cannon Lake < Coffee Lake < Skylake」であるが，実行時間の性能の観点では「Coffee Lake < Skylake < Cannon Lake」となった．

したがって除算命令の高速化により，条件付き多倍長整数除算の高速化が見込めることがわかった．

Ice Lakeプロセッサは除算がアツい．

chroot("/home/hibari")

備忘録とかに使えそうなノート

Ice Lakeプロセッサは整数除算がアツい　数値計算編

実装

実験

実験結果