整数除算を浮動小数点演算に移行するのは容易である
Moving integer division to floating-point is trivial (marc-b-reynolds.github.io)
要約
この記事では、現代のハードウェアにおける整数除算と浮動小数点除算のパフォーマンスの違いに着目し、整数除算を浮動小数点演算で代替する手法を提案しています。浮動小数点除算が高速である一方、整数除算は遅いという現状を踏まえ、特定のビット幅以下の整数であれば、浮動小数点演算の丸め誤差の特性を利用して、整数除算と同等の結果を効率的に得られることを数学的に解説しています。
全文翻訳
整数除算を浮動小数点演算に移行するのは容易である
整数除算 q=(x/y) と剰余(ユークリッド除算の) r=(x%y) のハードウェア演算は、現在のハードウェアでは非常に遅いです。通常、レイテンシが非常に長く、スループットも低いです。対照的に、浮動小数点除算は非常に高速で、レイテンシが短く、スループットが高く、多くの場合、演算を実行するための実行ユニットも豊富です。そのため、一部の整数除算/剰余演算を浮動小数点演算に移行することが興味深い場合があります。しかし、それは面倒なことでしょうか?実は、簡単だと思います。数学は非常に単純なので、もし間違いがあればすぐにわかるはずです。
私の主張は次のとおりです。2つの整数 x と y(符号付きまたは符号なし)がそれぞれ double/single 精度で53/24ビットに収まる場合、両方を浮動小数点数に変換すると、以下のようになります。
// 浮動小数点演算:
// d は整数除算 x / y と同じ整数値
// m は整数剰余 x % y と同じ整数値
// (標準の丸めモード: 最近接丸め、偶数への丸め)
d = trunc(x/y); // 符号なしの場合は floor も機能する
m = -fma(d,y,-x); // fma が必要
// 注意: 'd' のみが必要で、それが整数に変換される場合、
// 浮動小数点から整数への変換における切り捨てまたは床関数は無料です。
標準の丸めモードにおいて。
ここからは、符号なし整数のみを考慮します。なぜなら、それがより難しいケースだからです(符号付きはより小さい最大値を持つ)が、浮動小数点数は実質的に符号付きの絶対値として格納されることを思い出してください。
いくつかの実用的な点:
- これは、丸めモードを
TOWARD_ZEROに設定し、完了後に元に戻すことで機能しますが、制御ワードへのアクセスはしばしば非常に高コストです。 - 一部のハードウェアには、除算などの一部の操作で丸めモードを選択できる除算オペコードがあります。例として AVX-512 には
_mm_div_round_sdという命令があり、例としてリストされているレイテンシは14サイクルです。 - 整数から浮動小数点数への変換、およびその逆にはコストがかかります。(注意:多くの x64 CPU には、符号なし整数から浮動小数点数への変換、およびその逆のオペコードがありません。したがって、これは実装上の懸念事項です。)
- 明らかに、浮動小数点数の精度 $p$ は、整数の幅の上限を決定します。これが $p$ で機能する場合、それより小さいすべての幅は自明に機能します。例として、double($p=53$)での32ビット整数、および single($p=24$)での16ビット整数があります。この場合、整数から浮動小数点数への変換を回避する「トリック」が存在する可能性があります。
- 明らかに、最も有望なケースは、オーバーヘッドを償却するために SIMD で作業する場合です。
- 定数除数については、コンパイラが最適化するはずです。実行時に既知で、少数回再利用される除数については、libdivide のようなソフトウェアソリューションがあります。
証明済みの方法があることに注意してください(参照:Formally verified 32- and 64-bit integer division using double-precision floating-point arithmetic)。
標準の丸めモードは「最近接丸め(偶数への丸め)」であり、最初の重要な観察は「偶数への丸め」の部分です。タイ(tie)は、操作の正確な結果が2つの浮動小数点数のちょうど中間にある場合に発生します。浮動小数点除算(この場合の基数2および同じ作業精度)には中間値がゼロであるため(参照:Midpoints and exact points of some algebraic functions in floating-point arithmetic セクション6.1、系1)、タイが発生することはありません。したがって、タイは決してなく、最近接丸め部分のみが適用されます。
正確な結果が1より小さいが、丸めアップに最も近い、4ビット精度浮動小数点フォーマットを使用した例を、可能なすべての構成で見てみましょう。
|GRS x = 無視
.1111|0xx .1111 (丸めなし)
.1111|100 タイケースは不可能
.1111|101 1.000 (丸めアップ)
.1111|11x 1.000 (丸めアップ)
丸め前には、ハードウェアは3つの追加ビット(ガードビット G、ラウンドビット R、スティッキービット S)を計算しますが、タイケースは不可能なので、G のみを知る必要があります。したがって、正確な結果が $r$ ビットの小数部を持つフォーマットでは、次の整数への丸めが発生するには、小数部が少なくとも $r+1$ 個の連続する1を持つ必要があります。これは合法的な入力では不可能であると主張します。
小数部のみを考慮すればよいので、$x/y$ の正確な結果を整数部 $n$ と小数部 $a/b$ に分解してみましょう。
\[\frac{x}{y} = n + \frac{a}{b}\]
(ここで、$b=y$ とします。見栄えを良くするためです。)したがって、明らかに:
\[\frac{a}{b} \in \left[0,1\right)\]
$p$ ビット精度のバイナリ浮動小数点フォーマットでは、除算は $d$ ビットの整数を生成し、$r$ ビットを剰余のために残します。
\[\begin{align*}
d & = \left \lfloor \log_2 \left(n \right)+1 \right \rfloor \
r & = p-d \
\end{align*}\]
$r$ ビットの小数部に対して、その値の範囲の下限と上限を $b$ について定義できます。
\[\begin{align
*}
\func{b_l}{r} & = 2^r \
\func{b_u}{r} & = 2^{r+1}-1 \
\end{align
*}\]
この時点で、$p$、$n$ およびそれから導出される $d$ についてはほぼ完了です。 $r$ ビットで可能な最大小数部を知りたいのです。
下限から生成できる1に最も近い値は次のとおりです。
\[\begin{align
*},
\frac{2^r-1}{2^r} = \sum
]_{i=1}^r \frac{1}{2^i}\
\end{align
*}\]
これは、そのバイナリ展開で $r$ 個の連続する1を生成する最小の数であることを、合計で示しています。
次に、上限の1に最も近い値で繰り返し、 $r+1$ 個の連続する1を持つ最小の数と比較します( $r+1$ の下限)。
\[\begin{align
*},
\frac{2^{r+1}-2}{2^{r+1}-1} &< \frac{2^{r+1}-1}{2^{r+1}-0}\
\end{align
*}\]
ここで、マイナスゼロは式を揃え、パターンを強調するためです。いずれにせよ、この不等式は、上限が $r$ 個の連続する1を持つことに限定されることを意味します。
実際には、境界のバイナリ展開について具体的に述べることができます。下限は $r$ 個の1で終了します。上限の正確な値は、 $r+1$ の周期を持ち、$r$ 個の1の後に1個のゼロが続く純粋に循環します。最初の4つの表を以下に示します。
| $r$ | lower | binary expansion | upper | binary expansion |
|---|---|---|---|---|
| 1 | $\frac{1}{2}$ | .1 | $\frac{2}{3} $ | .(10) |
| 2 | $\frac{3}{4}$ | .11 | $\frac{6}{7} $ | .(110) |
| 3 | $\frac{7}{8}$ | .111 | $\frac{14}{15}$ | .(1110) |
| 4 | $\frac{15}{16}$ | .1111 | $\frac{30}{31}$ | .(11110) |
しかし、いずれにしても重要な部分です。
いくつかの除数について、部分を簡単に結びつけてみましょう。
除算:
- $1$ は正しいです。
- $2$ は指数のみを変更し、丸めは一切発生しません。
- $3$ ($r=1$)の場合、最大
x % 3の値は $2$ なので、最大小数部は $\frac{2}{3}$ です。次の整数に丸めることはできません。 - $\set{4,5,6,7}$ は $r=2$ を持ちます。正確な除数は関係ありません。なぜなら、すべて
.110xで始まるからです。
そして、可能なすべての除数について同様です。
最悪ケースの $a$, $b$ のペアをテストするコード:godbolt (binary32 と binary64 の両方)。