algorithm - 如何仅在一个时钟周期内获得 32 位输入的平方根？

Question

我想用 Verilog 设计一个可综合的模块，只需一个周期即可计算给定 32 位输入的平方根。

Answer 1

[Edit1]修复代码

最近发现即使测试确定一切正常，结果也是如此，所以我更深入地研究，发现我的方程中有一个愚蠢的错误，并且由于与我的 pgm 环境的名称冲突，测试出现误报，所以我忽略了它前。现在它在所有情况下都能正常工作。

我能想到的最好的事情(除了近似或大LUT)是没有乘法的二分搜索，这里C++代码:

//---------------------------------------------------------------------------
WORD u32_sqrt(DWORD xx) // 16 T
    {
    DWORD x,m,a0,a1,i;
    const DWORD lut[16]=
        {
        //     m*m
        0x40000000,
        0x10000000,
        0x04000000,
        0x01000000,
        0x00400000,
        0x00100000,
        0x00040000,
        0x00010000,
        0x00004000,
        0x00001000,
        0x00000400,
        0x00000100,
        0x00000040,
        0x00000010,
        0x00000004,
        0x00000001,
        };
    for (x=0,a0=0,m=0x8000,i=0;m;m>>=1,i++)
        {
        a1=a0+lut[i]+(x<<(16-i));
        if (a1<=xx) { a0=a1; x|=m; }
        }
    return x;
    }
//---------------------------------------------------------------------------

标准二分查找sqrt(xx)正在设置 x 的位从MSB到LSB，这样的结果是x*x <= xx 。幸运的是，我们可以通过简单地将其重写为递增乘数来避免乘法......在每次迭代中较旧的 x*x结果可以这样使用:

x1 = x0+m
x1*x1 = (x0+m)*(x0+m) = (x0*x0) + (2*m*x0) + (m*m)

哪里x0值为x从上次迭代和 x1是实际值。 m是实际处理位的权重。 (2*m)和(m*m)是常数，可以用作LUT和位移位，因此不需要乘法。只需要添加即可。遗憾的是，迭代绑定(bind)到顺序计算，禁止并行化，因此结果是 16T充其量。

代码中a0代表最后一个x*x和a1代表实际迭代x*x

如您所见 sqrt完成于16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare)其中位移位和LUT可以硬连线。

如果你有超快的门，与其他门相比，你可以将输入时钟乘以 16并将其用作 SQRT 模块的内部计时。类似于过去的情况，在旧的 Intel CPU/MCU 中，有 MC 时钟作为源 CPU 时钟的划分......这样你可以得到1T时间(或倍数取决于乘法比)。