这几天比较勤奋哈，干脆再更一篇。
最开始做 CPU M-Extension 的时候，是想实现 SRT 除法的，但是让 copilot 调了很久，烧了很多 token 都还是有问题。加上自己其实也不会（心虚），最后还是写了一个简单的 Radix-16 恢复除法。那个除法器的设计过于恐怖，我直接拿当前余数 $R$ 和 1~15 倍的 $d$ 并行相减比较来确定商位。不过好像大家也都不是很在意这个，两轮 cr 都没有人来拷打这个沟槽的设计。
XiangShan 的代码中（ nanhu 版）做了好几个除法器，本文主要基于其中的 SRT4Divider。不过我们的重心会还是放在 SRT 除法的原理上，不会涉及到对代码的详细讲解。
Before Reading#
依个人观点，写代码时适合听 vocal ，看数学时适合听纯音（雾）。
考虑到 AV2 对我入坑车万的影响，这首歌确实算是我初入幻想乡的地方了…
Why SRT#
如果你对恢复除法和非恢复除法不了解，最好去恶补一下相关知识。注意甄别内容，我在看非恢复除法时，有一个帖子把 wiki 上的伪代码跟恢复除法的示例混在一起讲，给我晕完了。
对于恢复除法，为了选择商都必须精确比较 $R$ 和 $d$ 的关系。而且随着基数 $r$ 变大，恢复除法面临很大的比较压力（比如我的沟槽设计），非恢复除法的逻辑则变得很复杂。 SRT 除法不想做 64 位的减法，它希望只通过看 $R$ 和 $d$ 的高几位，通过查表就可以“猜”出一个商，并且保证后续迭代可以修正到正确的结果。
后面讨论的对象均为 Radix-4 SRT 除法。
归一化与对齐#
SRT 除法要求将除数左移，让除数位于 $\left[ 0.5,1 \right)$ 之间。并对齐被除数。
为什么一定要控制除数 $d$ 的范围呢？
SRT 独特的点在于商数集是“冗余”的。Radix-2 恢复除法的商数集是 $\{ 0,1 \}$ ，非恢复除法的商数集是 $\{ -1,1 \}$ ，最终商的表示应该是唯一的。但是 Radix-2 SRT 的商数集是 $\{ -1,0,1 \}$ ，存在可能的多种表示。也就是说，即使高位的商算的“不准”，后续也能救回来。
SRT 除法的迭代公式如下，其中 $R_j$ 是当前余数， $r$ 是基数：
$$R_{j+1} = r \cdot R_j - q_{j+1} \cdot d$$考虑 Radix-4 SRT 除法：商数集是 $\{ -2,-1,0,1,2 \}$ ，如果余数过大，靠 $- q_{j+1} \cdot d$ 这项拉不回来时，显然商就有问题了。必须要求迭代方程收敛，那么可以给余数定一个界限 $|R| \leq \rho \cdot d$ 。
考虑最极端的情况：当前的余数 $R_j$ 已经达到了上限 $\rho \cdot d$ ，做最大修正 $R_{j+1} = r \cdot (\rho \cdot d) - q_{max} \cdot d$ 仍要满足 $\leq \rho \cdot d$ ，于是解不等式：
$$r \cdot \rho \cdot d - q_{max} \cdot d \leq \rho \cdot d$$得到 $\rho \geq \frac{q_{max}}{r - 1}$ ，对于 Radix-4 ，这个值是 $\frac{2}{3}$ 。
回到为什么要归一化除数的问题：假如不归一，除数 $d$ 没有确定的范围。当 $d$ 很小时，SRT 除法的收敛性不能保证，很可能越除余数越大。如果想要提高选商的准确性，就很难只依赖 $R$ 和 $d$ 的高几位确定除数，有悖 SRT 的优化初衷。
余数的存在形式#
之前我们给出了 SRT 除法的迭代公式，如果每个周期我们做一次减法，那其实并不比非恢复除法好多少。但是如果余数 $R$ 表示成 $Sum(S) + Carry(C)$ ，迭代公式就变成了一个 3 变 2 的加法。有了上期 Wallace Tree 积累的经验，我们知道全加器就能做到。
$$(S_{j+1}, C_{j+1}) = CSA(r \cdot S_j, r \cdot C_j, -q_{j+1} \cdot d)$$也正是因为余数是 $(S, C)$ 形式，我们无法准确的知道它的值（除非做一次 CPA ，但是太慢了）。我们只能依赖 $S$ 和 $C$ 的高几位来“猜”这个商，由于舍弃了 $S$ 和 $C$ 的一些低位，我们相当于忽略了低位会产生的最大进位。截断之后得到的是一个余数的范围。
之前我们提到，因为商数集的冗余，我们在选择商数时其实是有容错的。可以理解成 $\{ -2,-1,0,1,2 \}$ 里每个商数都对应一片区域，只要 $R$ 和 $d$ 落在区域内，选择对应的 $q$ 就是安全的（迭代收敛）。并且这些商数对应的区域会有一些重叠，在重叠区就有多种商数选择。我们拿到的 $R$ 和 $d$ 都会有一定误差，但只要误差比重叠区小，选的商就还是安全的。
截断保留的位数越多，误差越小。 XiangShan 看了余数的高 7 位和除数的高 4 位，这时误差已经小于重叠区了。
所谓的 QDS 就是选取商数的模块，做好表后查表就行。
#
理解 SRT 除法还是有点难，说实话没有特别好的资料。
wikipedia 上恢复除法和非恢复除法讲得都挺详细，还附了伪代码，但是 SRT 写的很含糊。我主要的资料来源也就是 XiangShan 和别人的博客，很难说我真的理解了 SRT 除法，至少在硬件实现上还有很多细节我不了解。
本文的主要目的还是研究 SRT 除法的理论基础，为什么要有冗余的商数集？为什么可以只凭高位选商？希望这些问题在看完本文后能有答案。至于表怎么做，迭代怎么写，好像也都只是比较 technical 的事，我是不太感兴趣的。
之后大概要远离 HDL 一段时间，其实这几篇文章都是在为 CPU 填坑，然而那两坨屎山都已经留在上个学期了，到此也算仁至义尽。停笔于 27 日凌晨 1 点，夜太深，我要睡力。