非均匀间隔查找的 FPGA 索引 table

Question

我们正在尝试在 FPGA 上实现定点非线性数学函数。我们希望能够实现非常低的延迟（最多 2-4 个时钟周期），以这样一种方式对计算进行流水线处理，以便我们可以在每个时钟周期收到一个新的答案（不会丢失输入，因为它们在每个时钟周期都出现），具有不错的准确性，并且具有合理的 FPGA 资源利用率。

我们使用 CORDIC 计算机和 DSP 块的组合来执行计算以获得非常好的解决方案，除了 CORDIC 计算机需要大约 12 个时钟周期才能获得良好的准确性。

使用没有插值的 LUT 需要太多的 RAM，因为我们有 32 位，所以我们放弃了它。

我们的下一个选择是使用带插值的查找 table。延迟很好，因为我们可以使用输入值的高位自动索引 LUT。这样做的问题是非线性部分的准确性不是很好。

我们现在正在尝试使用样本间距不均匀的 LUT。基本上我们在非线性部分对函数进行更多采样，当函数看起来更线性时采样更少。这应该对我们的准确性问题有很大帮助，但我们现在面临无法使用输入值的高位自动索引 LUT 的问题。我们研究了进行二进制搜索以查找索引的方法，但延迟受到了影响。资源利用率也不是很好，因为为了在每个时钟周期都得到输出的答案，我们不得不在不同的流水线阶段复制我们的 LUT 来处理二进制搜索。我们尝试了一些技巧，例如使用双端口 ram，但延迟仍然很严重。

所以我们想知道是否有人遇到过类似的问题并且知道一个好的索引解决方案，或者是否有 special/smart 方法对我们的函数进行非均匀采样并以这样的方式构建 LUT仍然可以相当快速地计算索引。

Answer 1

假设您的函数执行

y = f(x)

你可以先用 piece-wise 线性压缩 x

z = g(x)

作为小型 LUT + 线性插值实现（仅考虑 x 的几个最高有效位），这样您就可以将更多内存用于函数的有趣区域，而将更少内存用于几乎恒定的区域. 然后你计算 y 为

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

其中 h 将是原始 table 的 pre-process、"warped" 版本。

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

和

g'(g(x)) = x

那么您仍将仅在前几位上使用 LUT 加上线性插值，但分两个阶段：

        +--------+        +--------+
        | 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) 以使 worst-case（或 average-case）误差最小化。但这是您可以离线甚至分析执行的事情。

非均匀间隔查找的 FPGA 索引 table

FPGA indexing of nonuniform spaced look up table

signal-processing

lookup-tables

fpga