整数除算は商のビット数が大きいほど遅い

最近、Assembly Hall of Shame というプロジェクトを知りました。CPU 命令をどれだけ「遅く」実行できるかを競うもので、例えば x86 の fxrstor64 という命令は、条件次第で 1 回の実行に 1 分以上かけられるそうです。

リーダーボードを眺めていて、整数除算命令 idiv に目が止まりました。idiv を遅くする方法の1つに、除数に対して被除数を大きくするということが挙げられています。 これを見て、入力値によって除算命令のレイテンシがどれくらい変わるのか気になりました。 というわけで本稿では、入力値の大きさを変えたときの整数除算命令 idiv のレイテンシの変化を調べてみます¹。

レイテンシの定義

idiv は符号付き整数の除算命令です。64 ビットモードの場合、128 ビットの符号付き被除数を RDX:RAX に入れ、64 ビットの除数をオペランドとして渡します。除算実行後、商は RAX、余りは RDX に入ります²。

Zen 2 における各命令の典型的なレイテンシは、Software Optimization Guide for AMD EPYC 7002 Processors に記載されています。64 ビットのオペランドに対する idiv のレイテンシは 41 サイクルと書かれていますが、オペランドの値によるレイテンシの違いには触れられていません。 そもそも整数除算命令には2つの出力（商と余り）があるため、レイテンシには複数の定義が考えられます³が、そのあたりの詳細についても記述されていません。

本稿では、整数除算命令のレイテンシを、実行開始から商と余りの両方を後続命令が利用できるようになるまでの時間、と定義します。

ベンチマークの設計方針

入力値の大きさを変えたときの idiv のレイテンシの変化を計測するために、2つのベンチマークを用意します。

被除数と商のビット数を変える

1つ目のベンチマークでは、除数を 1 に固定し、被除数を 2 のべき乗で変化させます。すなわち、被除数のビット数を $b \,(= 1, 2, \ldots, 63)$ とおき、

とします。除数を固定しているので、被除数とともに商も変化します。

被除数を固定して商のビット数を変える

2つ目のベンチマークでは、被除数を $2^{62}$ に固定し、商を 2 のべき乗で変化させます。 すなわち、商のビット数を $b \,(= 1, 2, \ldots, 63)$ とおき、

とします。$2^{62}$ は 64 ビット符号付き整数で表せる最大の 2 のべき乗です。

レイテンシの計測

idiv の入力値を固定した依存チェーンを作る

ある命令のレイテンシを計測したければ、その命令だけからなる依存命令列（依存チェーン）を作り、実行にかかったサイクル数を命令数で割ればよいです⁴。

この方法で特定の入力値に対する idiv のレイテンシを計測するには、同じ被除数・除数の idiv のみからなる依存チェーンを作る必要があります。 しかし、命令間の依存関係を作るために idiv の商を次の idiv の被除数にすると、除数が 1 の場合を除いて、idiv の入力値が毎回変わってしまいます。

そこで、レイテンシが既知の命令のみからなる補助依存チェーンを追加し、入力レジスタの値を復元します。 今回は、実験環境における and と or のレイテンシが 1 サイクルであることが既知であると仮定⁵し、and と or のみからなる補助依存チェーンを追加します⁶。

まず idiv の直後に RAX と RDX に依存する and 命令を置くことで、商と余りの両方が利用可能になるのを待ちます。

1
2
3

xor  edx, edx       # RDX = 0
idiv divisor        # RAX = quotient, RDX = remainder
and  rax, rdx       # 商と余りの両方を待つ

次に、and と or で、RAX の値を元の被除数 dividend に戻します。

1
2

and  rax, dividend
or   rax, dividend  # RAX = dividend

これは、ビット演算に関する次の恒等式に基づいています。

以上により、idiv の入力値が常に一定であるような依存チェーンを作ることができました。

除算器の占有時間を考慮する

除算器は、除算の実行が完了してすぐに次の除算を開始できるとは限りません。 次の除算の入力が準備できても、除算器がビジーな間は、実行を開始できないためです。

Zen 2 には、除算器のビジーサイクル数を数えるパフォーマンスイベント DIV_CYCLES_BUSY_COUNT が用意されています。

amd64_fam17h_zen2::DIV_CYCLES_BUSY_COUNT # Number of cycles when the divider is busy.

idiv のレイテンシを $L$、補助依存チェーンのレイテンシを $C$、1 回の除算で除算器がビジーになる時間（除算器の占有時間）を $B$ とすると、

の場合、除算器の占有時間によって idiv のレイテンシが隠蔽されてしまいます。 したがって、idiv のレイテンシを計測するには、補助依存チェーンの長さ $C$ を十分大きくする必要があります。 ここまでに追加した 2 個の and と 1 個の or で、補助依存チェーンの長さは 3 サイクルありますが、除算器の占有時間 $B$ は事前には分からないため、さらに 13 個の or rax, rax を追加しておきます。 これにより、補助依存チェーンは 2 個の and と 14 個の or で構成され、$C = 16$ となります。

1
2
3
4

or   rax, rax       # RAX = RAX or RAX を 13 個並べる
or   rax, rax
or   rax, rax
...

idiv のレイテンシは、依存チェーンの実行にかかるサイクル数から 16 を引くことで求まります。 なお、ループ先頭の xor edx, edx は RAX に依存せず、補助依存チェーンと並行して実行できるため、補助依存チェーンのレイテンシには含めません。

ビルドと実行

リポジトリのルートで Zen 2 向けにビルドし、整数除算ベンチマークを実行します。使用した GCC のバージョンは 16.1.1 です。

1
2
3

$ cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DMICRO_BENCHMARK_SUITE_ARCH=znver2
$ cmake --build build
$ ./build/integer_division/integer_division > result.csv

また、補助依存チェーン単体のベンチマークを実行し、予想していた通りレイテンシが 16 サイクルであることを確認できました。

1
2

$ ./build/integer_division/auxiliary_dependency_chain
Auxiliary dependency chain latency: 16.00 cycles

計測結果

AMD Ryzen 7 4700U (Zen 2) での計測結果を次の図に示します⁷。

左図は1つ目のベンチマークの結果で、被除数と商のビット数が 2 増えるごとにレイテンシが 1 サイクルずつ増加しています。 右図は2つ目のベンチマークの結果です。被除数を固定していますが、商のビット数に対して同様の傾向が現れました。

これらの結果から、商のビット数に応じて idiv のレイテンシが大きくなることがわかります。 今回計測した範囲では、商のビット数を $b$ とすると、idiv のレイテンシ $L(b)$ は次式で表せます。

商のビット数が 2 以下ならばレイテンシは 10 サイクル、63 ビットの場合は 41 サイクルとなります。

一方、除算器の占有時間 $B(b)$ は、入力値の大きさによらず idiv のレイテンシより約 2 サイクル長くなりました。

つまり、商と余りが利用可能になってから、次の除算を開始できるようになるまでに、約 2 サイクルの時間を要します。

参考

• asm-hall-of-shame
• micro-benchmark-suite
• perf-counter
• Software Optimization Guide for AMD EPYC 7002 Processors
• uops.info — IDIV (R64)