高位合成による浮動小数点用QR分解ハードウェアの設計

本論文は，連立方程式を解くのによく利用される QR 分解と，浮動小数点向けギブンス回転の高速近似解法である FasInvSqrt 処理を高位合成で設計する方法を論じる．2008 年に，インテルが，サイズ 4 からサイズ 12 までの並列ギブンス回転によるパイプライン QR 分解を発表した [1]．QR 分解の加速を並列ギブンス回転を利用したものである．この処理の中で，ギブンス回転行列の計算速度と精度は全体性能に大きな影響を持っている．インテルの FPGA のマニュアルで推奨されている CORDIC による近似計算法は，回転角からの計算に適しているが，QR 分解には，回転角の大きさの計算が不要あり，より高速化できる可能性がある．本提案は，ギブンス回転行列を計算する浮動小数点用の FasInvSqrt と Newton 近似法を用いた手法を高位合成で設計した．8 bit精度を達成するのに，CORDIC では 20 回程度必要であるが，提案の Newton 法では 1 回でよく，また，高い精度なら CODIC では 40 回以上，1 Newton 法では 3 回で実現でき，合成された回路の低レイテンシ動作が可能となる．また，QR 法は，行列に 0 と 1 が多く単純に合成すると 0 や 1 との掛け算等が無駄になり，それらを最適化する，また，高位合成を行う時に多重ループを 1 重ループに自動変換する等の技法を用いて高速化した結果を報告する．

This paper discusses how to design a QR decomposition based on Givens rotations (typically used to solve linear equations) using advanced synthesis tools, and a method for computing floating-point Givens rotations using the FasInvSqrt approximation. In 2008, Intel designed a pipeline QR decomposition based on Givens rotation. In this process, the computational speed and accuracy of the Givens rotation matrix has a significant impact on the overall performance. The approximation method using CORDIC recommended in the Intel FPGA manual is suitable for rotation angle-based calculations, but the QR decomposition does not need to calculate the magnitude of the rotation angle. The proposed QR decomposition method does not need to calculate the magnitude of the rotation angle and may be faster. CODIC requires more than 40 times, while the proposed Newton method requires only 3 times, thus enabling low latency operation of the synthesized circuit. In addition, the matrix of the QR method has many zeros and ones, and if the synthesis is simply performed, multiplications with zeros and ones, etc., will be wasted. This report shows the speedup by optimizing matrix multiplication and using techniques such as automatic conversion of multiple cycles to single cycles in High-Level Synthesis (HLS).