当前位置：
  1. 首页
  2. 可编辑器件

FPGA开发中分治法的应用

2023-08-16

分治法是经典优化算法之一。分治分治，即分而治之。分治，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法的思想我们也可以用在FPGA开发中，使得设计更加高效。
本文以 leading zero count 为例来看一下分治法的应用。
这个题目是计算一个 vector 的 leading zero 的数目。比如 8'b00001111，结果为4，而8'b00111111，结果为2。
Casex 优先级选择器,我们可以用最简单的 casex 优先级选择器来实现。假设输入的vector位宽为64。
综合结果如图一所示。Vivado综合完预估的slack为8.572ns，critical path是5级，共消耗71个LUT。
FPGA开发中分治法的应用 (https://ic.work/) 可编辑器件 第1张
图1 - leading zero count 1,分治法 - Tree Structure,现在我们使用分治法来实现这个功能。通过一个 balanced tree structure 来实现。
首先将 64bit 的 vector 分成32个 2bit 的小 vector。先对2bit的小 vector 做encode>
然后按照如下规则将相邻的 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。
FPGA开发中分治法的应用 (https://ic.work/) 可编辑器件 第2张
图2 - leading zero count 2,可以看到相比于casex的设计，tree structure节省了超过50%的LUT，同时逻辑级数也减少了一级。
总结,分治法的思想也可以应用在FPGA开发中。尤其是当我们遇到大位宽数据的处理时，分治法往往可以提升设计的资源使用率和时序结果。

文章推荐
Tags：

上一篇

下一篇

相关推荐