时间戳

首页 > 解决方案 > 如何在verilog中优化二维数组中的查找值

function - 如何在verilog中优化二维数组中的查找值

问题描述

我需要设置一个函数来确定二维数组（索引）中是否存在匹配项。我当前的实现工作，但由于 if 语句检查数组的每个元素，正在创建一个大的 LUT 链。

function result_type index_search ( index_type index, logic[7:0] address );

     for ( int i=0; i < 8; i++ ) begin
         if ( index[i] == address ) begin
            result = i;
         end
     end

有没有办法以更有效的方式检查匹配项？

标签： functionoptimizationsystem-verilog

解决方案

真的没什么可做的；至少对于手头的代码。由于您的代码以硬件为目标，因此要对其进行优化，请考虑硬件，而不是功能/verilog 代码。

对于通用实现，在没有任何已知数据模式的情况下，您肯定需要 (a)N W位相等检查，以及 (b)N:1返回第一个匹配项的 FPA（固定优先级仲裁器，又名优先级编码器，又名前导零检测器） ，假设N W-bit 输入。像这样的东西：

在此处输入图像描述

没有太多优化要做，但这里有一些可能的通用优化：

  • 流水线，如图所示，如果时间是一个问题。
  • 考虑使用 2 的补码特性的替代 FPA 实现，并可能导致更高效的 LUT 实现：（assign fpa_out = fpa_in & ((~fpa_in)+1);导致单热编码，而不是加权二进制，如您的代码中那样）
  • 坚持 one-hot 编码可以派上用场，并减少你的一些逻辑，但在我们看到更多代码之前我不能肯定地说。

这就是实现的样子：

logic[N-1:0] addr_eq_idx;
logic[N-1:0] result;
for (genvar i=0; i<N; i++) begin: g_eq_N
    // multiple matches may exist in this vector
    assign addr_eq_idx[i] = (address == index[i]) ? 1'b1 : 1'b0;

    // pipelined version:
    // always_ff @(posedge clk, negedge arstn)
    //     if (!arstn)
    //         addr_eq_idx[i] <= 1'b0;
    //     else
    //         addr_eq_idx[i] <= (address == index[i]) ? 1'b1 : 1'b0;
end

// result has a '1' at the position where the first match is found
assign result = addr_eq_idx & ((~addr_eq_idx) + 1);

最后，尝试考虑由于已知的运行时数据特征，您的设计是否可以被简化。例如，假设您 100% 确定您要查找的索引 2D 数组中最多存在一个位置。如果是这种情况，那么您根本不需要 FPA，因为第一个匹配项将是唯一匹配项。在那种情况下，已经指向匹配索引，作为一个单热向量。addressaddr_eq_idx

推荐阅读