FPGA开发中分治法的应用

分治法是经典优化算法之一。分治分治，即分而治之。分治，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的思想我们也可以用在FPGA开发中，使得设计更加高效。

本文以 leading zero count 为例来看一下分治法的应用。

这个题目是计算一个 vector 的 leading zero 的数目。比如 8'b00001111，结果为4，而8'b00111111，结果为2。

Casex 优先级选择器

我们可以用最简单的 casex 优先级选择器来实现。假设输入的vector位宽为64。

always_comb begin
    count = 0;
    casex (vector)
       64'b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000 : count = 64;
       64'b1???????_????????_????????_????????_????????_????????_????????_???????? : count = 0;
       64'b01??????_????????_????????_????????_????????_????????_????????_???????? : count = 1;
       64'b001?????_????????_????????_????????_????????_????????_????????_???????? : count = 2;
       ...
       64'b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 : count = 63;
    encase
end

综合结果如图一所示。Vivado综合完预估的slack为8.572ns，critical path是5级，共消耗71个LUT。

图1 - leading zero count 1

分治法 - Tree Structure

现在我们使用分治法来实现这个功能。通过一个 balanced tree structure 来实现。

首先将 64bit 的 vector 分成32个 2bit 的小 vector。先对2bit的小 vector 做encode：

case(small_vector)
    2'b00: encoded = 2'b10;  // 2 leading zeros
    2'b01: encoded = 2'b01;  // 1 leading zero
    2'b10: encoded = 2'b00;  // 0 leading zero
    2'b11: encoded = 2'b00;  // 0 leading zero
endcase

然后按照如下规则将相邻的 encoded value 进行组合：

如果两边都是 1xxx，那么结果为 10..0

如果左边是 0xxx，那么结果为 0[左边]

如果左边是 1xxx，那么结果为 01[右边[msb-1:0]]

可以看到每个组合的操作是一个mux。每次组合后，新的vector位宽加1，然后新的vector再两两组合，直到得出最终的结果。

我们以8bit输入的vector为例：8'b00000111

按照2bit分解： 00 00 01 11

Encoded value: 10 10 01 00

两两组合： 100 001

再组合： 0101 = 5 leading zeros

当输入为64bit的vector时，此 tree structure 的设计综合结果如图2所示。Vivado综合后预估的slack为8.600ns，critical path为4级，消耗38个LUT。

图2 - leading zero count 2

可以看到相比于casex的设计，tree structure节省了超过50%的LUT，同时逻辑级数也减少了一级。

总结

分治法的思想也可以应用在FPGA开发中。尤其是当我们遇到大位宽数据的处理时，分治法往往可以提升设计的资源使用率和时序结果。