复用器重构降低FPGA成本..doc

复用器重构降低FPGA成本 2005-06-14 ?? Paul Metzgen, Dominic Nancekievill, Altera欧洲技术 本文介绍了一种新的能够降低FPGA实际设计20％成本的综合算法。该算法通过减少复用器所需查找表（LUT）的数量来实现。算法以效率更高的4:1复用器替代2:1复用器树。算法性能关键在于寻找总线上出现的复用器数量。新的优化方法占用一定的逻辑，这些逻辑由总线进行分担，从而减少了总线上每个比特位所需的逻辑。 关键词 FPGA、复用器、重构、重新编码、总线、逻辑优化、综合。 ? 1.???? 引言 复用器是数据通道常用的构建模块，被广泛应用在处理器[1]、处理器总线、网络交换，甚至是资源共享的DSP设计中。据估计，复用器一般要占用一个FPGA设计[2] 25%以上的面积。因此，优化FPGA设计的关键在于怎样优化复用器。 本文介绍了一种新的复用器重构算法，该算法减小了复用器在基于4输入查找表（4-LUT）FPGA体系结构中所占用的面积。基准测试结果表明复用器平均减少了17%，在一些设计中，4-LUT整体减少20%。 2.1节阐述了复用器是如何由行为级VHDL[4]或Verilog[5]代码产生的，2.2和2.3节阐述复用器树和复用器总线在设计中是怎样生成的。2.4节说明这些结构怎样由4-LUT实现，阐述如何采用两个4-LUT有效实现一个4:1二进制复用器。 第3节介绍了一种叫做压缩的新技术，该技术附加一些控制逻辑，将多个2:1复用器重新组合为有效的4:1复用器，从而减少了为总线上每一个比特位实现复用器所需要的4-LUT数量，所附加的控制逻辑代价由整个总线来分担。优化复用器总线是复用器重构算法的核心。 4.1节阐述复用器重构算法如何构建设计中的复用器树总线。4.2节的重构方法用于执行4.3节中定义的均衡算法。均衡增加了由压缩生成的有效4:1复用器的数量。 第5节总结了在Altera Quartus II集成综合中运行的整个算法。第6节列出了来自120个Altera真实用户设计实例的基准测试结果，测试表明面积减少超过20%，平均节省了4.2%。 ? 2.???? 背景知识 2.1???? 复用器在设计中是怎样实现的 行为级HDL设计中的任何条件代码通常会综合为复用器。本节阐述两个最常用的复用器生成代码实例。 图1是VHDL的case声明及其2:1复用器树的实现。采用Verilog case声明的“parallel case”指令[5]可产生相似的结果。 注意，并不是所有的case声明将可能的事件都描述清楚，需要依靠“default”或者“others”条件来进一步说明。在这些情况下，可以继续将case声明表征为2:1复用器树，但是这种树结构可能达不到平衡。 图2显示了“if-then-else”声明是怎样产生一个2:1复用器链的。Verilog的“?:”和非平行cases可同样产生相似的结构。注意，复用器链确保如果第一个if条件为“真”，将选择“a”数据输入，而复用器其他部分将被忽略。 本文阐述的复用器重构算法应用于2:1复用器。综合工具由行为级代码开始通常会生成较大的复用器。较大的复用器总是被分解为2:1复用器树，如何实现这种分解已经超出本文讨论范围。 ? 2.2???? 复用器树 设计中复用器之间的馈入是常见的现象。例如，在一段HDL代码中，如下面的图3所示，if-then-else声明中含有case声明就会产生这种现象。 在复用器重构算法中，识别出较大的复用器树对于尽可能减少面积是非常重要的。 ? 2.3???? 复用器总线 VHDL信号或Verilog线宽通常会超过一个比特位。当采用if-then-else和case声明时，将会生成大量具有不同数据输入的相同复用器树，图4是一个实例。 一组具有相同结构的复用器称为复用器树总线。 本文阐述的复用器重构技术采用了新的对整个复用器总线进行优化的方法，它通过由4.1节中进一步阐述的总线识别和形成技术来实现。 ? 2.4???? 复用器代价 2:1复用器都需要一个单独的4-LUT。这样，图1和图2中的复用器结构都需要三个4-LUT。尽管这些结构控制编码不同，但是它们都具有4个不同的数据输入，因此可以当作4:1复用器。本节阐述如何实现只需要两个4-LUT的4:1复用器。 图5是控制输入S0低电平时，一个有效的4:1复用器是如何工作的。4:1复用器由两个链接在一起的4-LUT（阴影框所示）构成。每个4-LUT被设置为含有阴影框中的逻辑功能。如白框所示，复用器含有四个输入——a、b、c和d，以及两个控制输入——S0和S1。 S0低电平时，低位控制比特S1在输入c和d中进行选择，其结果通过第二个4-LUT，将a或者b输入旁路。