非均匀间隔查表的FPGA索引

Question

我们试图在FPGA上实现不动点非线性数学函数。我们希望能够实现非常低的延迟(2-4个时钟周期最大)，使计算流水线的方式，使我们能够收到一个新的答案，每个时钟周期(没有下降的输入，因为他们在每一个时钟周期)，有良好的准确性，并有合理的FPGA资源利用率。

我们使用CORDIC计算机和DSP块相结合进行了计算，得到了一个很好的解决方案，除了CORDIC计算机需要12个时钟周期才能达到很好的精度。

使用LUT没有插值将需要太多的RAMs，因为我们有32位，所以我们扔掉了。

我们的下一个选择是使用带内插的查找表。延迟很好，因为我们可以使用输入值的上位自动索引LUT。这方面的问题是，在非线性部分，精度不是很好。

我们现在正在尝试使用一个在样本之间具有非均匀间隔的LUT。基本上，我们在非线性部分对函数进行了更多的采样，当函数看起来更线性时，样本更少。这在很大程度上有助于解决我们的准确性问题，但我们现在面临的问题是，我们不能用输入值的上位自动索引LUT。我们研究了如何进行二进制搜索来查找索引，但延迟受到了影响。资源利用率也不是很好，因为为了在每个时钟周期中不断地得到输出的答案，我们不得不在不同的流水线阶段复制LUTs，以处理二进制搜索。我们尝试了一些技巧，比如使用双端口报，但延迟仍然是致命的。

因此，我们想知道是否有人遇到过类似的问题，并且知道一个很好的索引解决方案，或者是否有特殊/智能的方法来不统一地采样我们的函数，并以这样的方式构建LUT，以便仍然可以相当快地计算索引。

Answer 1

假设您的功能执行

y = f(x)

首先，可以用分段线性压缩x。

z = g(x)

实现为一个小的LUT +线性插值(仅考虑到x的少数几个最重要的部分)，这样您就可以将更多的内存用于函数的感兴趣区域，而不是用于几乎不变的区域。然后将y计算为

y = f(x)
  = h(z)
  = h(g(x))

在h将是一个预处理，“扭曲”版本的原始表。

h(z) = f(g'(x))

和

g'(g(x)) = x

然后，在前几位加上线性插值时，仍然只使用LUTs，但分两个阶段：

        +--------+        +--------+
        | LUT #1 |        | LUT #2 | 
        |        |        |        | 
-- x -->|  g(x)  |-- z -->|  h(z)  |--> y
        |        |        |        | 
        |        |        |        | 
        +--------+        +--------+

简略地勾勒出这幅画的样子：

Y= f(x)

^
|              :              :            ..:..............:   
|              :              :    ........  :              :   
|              :              :  ..          :              :   
|              :              :..            :              :   
|              :           ...:              :              :   
|              :...........   :              :              :   
|..............:              :              :              :   
+-----------------------------------------------------------+-> 
|              |              |              |              | 

Z= g(x)

^
|              :              :           ...O..............O   
|              :              :       ....   :              :   
|              :              :   ....       :              :   
|              :           ...O...           :              :   
|              :       ....   :              :              :   
|              :   ....       :              :              :   
O..............O...           :              :              :   
+-----------------------------------------------------------+-> 
|              |              |              |              | 

Y= h(z)

^
|   :                          :                      ..:...:   
|   :                          :             .........  :   :   
|   :                          :      .......           :   :   
|   :                          :......                  :   :   
|   :                  ........:                        :   :   
|   :..................        :                        :   :   
|...:                          :                        :   :   
+-----------------------------------------------------------+-> 
|   |                          |                        |   |

当然，有趣的问题是如何找到最优的g(x)，以便最大限度地减少最坏情况(或平均情况)的错误。但这是你可以在线下执行甚至分析的东西。