复用器重构降低FPGA成本

--- 图5是控制输入S0低电平时，一个有效的4:1复用器是如何工作的。4:1复用器由两个链接在一起的4-LUT（阴影框所示）构成。每个4-LUT被设置为含有阴影框中的逻辑功能。如白框所示，复用器含有四个输入——a、b、c和d，以及两个控制输入——S0和S1。

图5

--- S0低电平时，低位控制比特S1在输入c和d中进行选择，其结果通过第二个4-LUT，将a或者b输入旁路。

图6

--- 图6是控制输入S0高电平时，一个有效的4:1复用器是如何工作的。低位控制比特S1旁路c和d输入，直接进入第二个4-LUT，对a或者b输入进行选择，其结果成为第二个4-LUT的输出。

--- 第3节描述的压缩算法采用这种有效的4:1复用器，重新实现复用器结构，达到了减小面积的目的。

3. 压缩

--- 压缩是将低效的4:1复用器实现转换为高效实现的过程。复用器重构算法的面积节省由压缩实现。但是，在不同的复用器表征中进行转换，通常需要附加控制逻辑。实际上，由于附加逻辑结构抵消了使用高效复用器结构的优势，这种转换很少能够产生真正的面积节省。而复用器重构算法采用新颖的将整个复用器总线进行转换的方法，这样，总线上的多个复用器可以共享控制逻辑，因此，改善后的复用器结构优势可通过总线上的每个复用器来实现。

图7

--- 图7显示了如何将三个2:1复用器组成的优先级链转换为一个4:1二进制复用器。假设控制输入由不相关的逻辑馈入，那么这种转换至多需要两个额外的4-LUT控制逻辑。如果最初的复用器至少占用三个4-LUT，而4:1复用器只需要两个即可实现，那么这种转换将节省3宽度或者更宽总线的面积。

图8

--- 图8显示了如何将一组排列成树的2:1复用器转换为一个4:1复用器。在这种情况下，通过仔细为4:1复用器选择编码方式，使S0在（A、B）和（C、D）之间进行选择，限制附加控制逻辑，只加入最多一个4-LUT。此时，这种转换将节省2宽度或者更宽总线的面积。

--- 一般来讲，任何的三个2:1复用器组都可以通过图7或图8的方式转换为一个4:1复用器。但是，这两种转换必须在宽度大于2的复用器总线上进行，以减小所需4-LUT的数量，实际上，如果这两种转换不在总线上进行，将没有意义。

--- 总线上2:1复用器三联重新编码是复用器重构算法的核心。 第4节将阐述形成数量最多三联的新方法。

4. 复用器总线

4.1 "库"的构造

--- 压缩减小了其所编码的每一个2:1复用器三联面积，因此，压缩应用在较大的复用器树上最有效。本节阐述大型复用器树是如何构建的。设计中所有的总线都将被存储在一种称为"库"的数据结构中。

--- 复用器树采用下面的方法构建。设计中所有2:1复用器以反向深度顺序排列。这意味着那些离寄存器或者输出引脚最近的复用器将排在列表前面。然后从头至尾扫描列表，寻找每一个2:1复用器，如果其输出仅与另一个2:1复用器相连，则将该复用器和与其相连的复用器一起加到复用器树中。否则，将此2:1复用器作为一个新复用器树的首复用器。以此方式来构建的复用器树含有最大数量的复用器。

--- 如果复用器树中复用器的所有数据输入均不是由同一个树中其他的2:1复用器馈入，则称此复用器为初级输入（对整个树而言）。

--- 一旦所有的复用器树已经形成，则将其合并成总线。如果两个复用器树要并入同一个总线，它们必须具有相同的结构，即2:1复用器的排列相同，并且都有完全一致的控制输入。这可以通过根据复用器结构，对所有复用器树列表排序来实现，在列表中将结构相同的树靠近排列。总线可直接由结构相同的树构成。

--- 通过规则选取来实现总线宽度最大化。宽总线可以将由压缩引入的控制逻辑开销降低到最小。

--- 4.2 重构

--- 4.3节描述均衡方法，该方法能够使压缩得到的面积减小最大化。均衡建立在重构的基础上，其概念由本节给出。

--- 通过2:1复用器所馈入的一个2:1复用器，重构移动该复用器及其一个输入。图9显示了阴影复用器与其"f"输入的重构。为保持原始复用器总线的功能，需要附加一些控制逻辑。这些控制逻辑同样可以由总线上的每一个复用器树来分担。

图9

--- 图9中，重新编码逻辑(c6 AND (NOT c3))必须确保当c1、c3为"假"而c6为"真"时，选择输入"f"（与转换前的情况一致）。同样，当c1、c3、c6为"假"时，选择输入"g"，即(c6 AND (NOT c3))也是"假"。

--- 重构转换将选中的复用器进一步向复用器树顶端移动。因此，不断重复重构转换，可以将任意位置的复用器向顶端移动。

--- 4.3 均衡

--- 压缩通过转换2:1复用器三联，能够减少实现复用器总线所需的4-LUT数量。但是，如果不进行复用器树重构，有些结构是不可能得到最佳三联分组的。例如，无法将图10中所有的2:1复用器进行分组，这是因为每一种可能的分组都将会剩余一个2:1复用器而无法处理。

--- 均衡的目的在于通过最少的重构得到最佳的压缩。对于图10的例子，可以采用图11所示的方法，得到两组2:1复用器三联。

--- 均衡算法由图12的递归定义。由首复用器开始，算法首先均衡复用器树左面和右面数据输入。均衡返回还没有连接为三联的2:1复用器的数量。均衡确保形成尽可能多的三联，这样只会剩余一个或者两个2:1复用器，甚至没有剩余。

--- 均衡中的任何阶段，都需要对1～5个2:1复用器进行均衡（从左侧分支开始最多两个，从右侧分支开始为两个，还要算上当前的2:1复用器本身）。1或2个复用器不会形成更多的三联，而3个复用器总是能够形成三联。4或5个复用器则需要进行重构，以免剩余无法处理的复用器，这种重构方法在图13和图14中示出。

图10 复用器树次优压缩的例子

来源：维库开发网