蔡媚媚外文翻译及原文2.doc

本科毕业设计（论文）外文参考文献译文及原文学 院 自动化学院 专 业 电子信息科学与技术 年级班别 2009级（2）班 学 号 3109001230 学生姓名 钟小洲 指导教师 夏益民 2013 年 6 月目 录基于FPGA采用流水线加法器图的高速度低复杂度FIR滤波器11 绪论12 流水线加法器图33 使用二进制整数线性规划最小化流水线操作44 结果6结论9致谢9参考文献9High Speed Low Complexity FPGA-based FIR Filters Using Pipelined Adder Graphs111 INTRODUCTION122 PIPELINING OF ADDER GRAPHS133 OPERATION MINIMIZED PIPELINING USING BINARY INTEGER LINEAR PROGRAMMING.154 RESULTS17CONCLUSION20ACKNOWLEDGMENT21REFERENCES21基于FPGA采用流水线加法器图的高速度低复杂度FIR滤波器马丁库姆和彼得齐夫德国卡塞尔大学数码科技集团Email: kumm, zipfuni-kassel.de摘 要 本文介绍了基于FPGA的高速度、低复杂度的FIR滤波器的方法。其实现可分为两部分。首先，一个加法器图是使用现有的多个常数乘法（MCM）算法获得。该加法器图说明所需的乘数模块滤波只使用了加法或者减法和移位运算。其次，执行特定的FPGA-specific联合调度和流水线优化，使得在使用最小的性能损失时能获得最大的速度。FPGA-specific的特征体现在优化过程中，包括通过复制稍后阶段的加法器来减少流水线寄存器。优化作为二进制整数线性规划（bilp）问题被制定。它表明在HCUB MCM算法中流水线操作所产生的数字比使用割集定时的as-soon-as-possible（ASAP）调度平均减少了29.1%。由生成VHDL代码所得的综合结果显示，该方法在资源复杂性方面（减少54.1%的平均水平），优于最近提出的加法/移位方法，有竞争力的表现是（平均速度是加法/移位方法的88.2%）。1 绪论 有限单位脉冲响应滤波器（FIR）是数字信号处理（DSP）中的一个关键的应用。它由于严格的线性相位、稳定性以及高通量被用于许多数字信号处理系统。如今，现场可编程门阵列（FPGA）常常被用于滤波器的应用，因为它们提供高达几兆赫兹的实时信号处理时比特定应用集成电路（ASIC）能提供更多的灵活性。 目前，许多研究已经完成了硬件实施有效的滤波器。FIR滤波器在转置形式中的结构如图1所示。这种结构是比直接形式有利的，因为延迟元件（z1）可以被用来作为流水线寄存器结构的加法器（加法器在虚线方框内）。在专用集成电路设计中，乘法的几个常数通常是简化为加法，减法以及移位。发现最小配置adders1（转变被认为是免费的）的问题被称为多个常数乘法（MCM）问题1 -6 。优化问题是NP完全问题 6 ，并成为近二十年来一个活跃的研究课题。MCM算法可以被分为公共子表达式消除法（CSE） 1 3和图形的方法 4 6。CSE方法试图确定共同模式的系数，而图的方法试图以一个自下而上的方式构建系数的值。基于图的方法更为复杂（在运行时），但数字的表示是独立的 3，通常能找到比cse-based方法 6更好的解决方案。一个领先的MCM启发式在质量和运行方面的优化结果是HCUB算法 6，这比以前的以图形为基础的方法BH 4，BHM和RAG-n 5更优。HCUB的实现是开源的 7。在最近的一个版本中，加法器的总深度（AD）可以是有限的，这是从输入到输出的加法阶段的最大数。这就导致了较短的关键路径，而加法器的资源只是略有增加。基于FPGA的高效数字滤波器的实现必须考虑结构的特征。这些都是特定的算术部件，如全加器和嵌入式乘法器以及查找表（LUTs）和触发器（FF）。分布式算法一直是最受青睐的实现滤波器的方法，因为查找表和加法器的使用，完全匹配FPGA的体系结构。不过meyer-baese 8等人表示，基于FPGA的并行分布式算法的实现比一个基于RAG-n算法 5的流水线加法器图的实现需要多出平均71%的资源。类似的结果也取得了添加/移位方法的提出者mirzaei等人的认同，这里用到了CSE方法与FPGA-specific成本函数。一个查找表和触发器减少58.7%和25%可以实现，分别相对于并行执行，这两种方法的性能几乎是相同的。这就表明 2，该加法器图中，HCUB比起CES方法一方面导致了一个较低的资源使用率（减少72%查找表和11%触发器），但另一方面，导致业绩不佳（下降68%），例如流水线和FPGA-specific的特点的使用在算法中是不考虑的。图1 转置形式的FIR滤波器 在这项工作中，一种新的方法被用来产生流水线乘法器模块且能够使用较少的资源。它是基于加法器图的方法，例如通过MCM算法，进一步优化fpga-specific调度定时。2 流水线加法器图2.1 利用割集定时的流水线 起点是由MCM算法得到的一个加法器定时图。一个例子如图2（a）所示，从而实现一个乘法模块常数系数设置C= 480，512，846，1020 。这个例子贯穿于本文算法的验证。本图需要四个加法器，使用HCUB算法计算。除了输入结点外的所有节点以圆圈表示，相当于加法器或者减法器。每个节点的值和实现这个节点的因数相等。输出节点是无圈的。所有边的权值是移位的因数。例如，节点15实现了将输入x移位4位和减去未移位的输入：15x=24x20x。流水线有向无环图，如加法器图，很容易利用割集定时来进行（CSR） 9。这个实现最复杂的系数的例子有一个3级的AD（423节点）。因此，一些流水线的阶段设置为三（没有输入/输出寄存器）。CSR后的一个可能的流水线加法器结构如图2（b）所示。每个节点被画为一个盒子，包括一个寄存器，即是一个纯寄存器（一个输入）或者存储加法器（两个输入）。假设每次加法计算的时间相同，如图2（b），如果输入和输出已经存储，最大时钟频率的结构可以是原来结构的约三倍以上，共有11个额外的寄存器用于流水图，比起没有流水线结构的四个加法器的结构，这将是一个巨大的费用。仔细看看流水线结构，它揭示了通过使用不同的调度，一些寄存器可以被淘汰。例如，系数255取决于输入节点1，这也可在流水线的阶段2实现，因此它可以搬到阶段3，这样可以节省2个寄存器。2.2 FPGA架构的流水线应用于现代FPGA的基本逻辑元素至少包括一个查找表（LUT），具有快速进位链的全加器（FA）逻辑和一个可选的输出触发器（FF）。这些元素是所有现代FPGA的共同点，即使FPGA硬件厂商将他们组织在不同的单位。以下将包含一个查找表，全加器和触发器的单元称为基本逻辑元素（BLE）。加法器通常为纹波进位加法器，其每个位在FPGA上需要一个FA或者一个BLE 来实现。因此，一位加法器或者减法器需要N个BLE。此外，实现一个N位加法器所需的BLE个数等于实现一个N位存储加法器的个数。因此，一个加法器的流水线可无额外费用地实现。一个N位寄存器需要N个BLE。为了简化，利用该模型并假设每个边缘的字长相同，很明显，如图2（b）中的每个节点需要大约相同的硬件资源。因此，如果系数在最后阶段重新计算，图2（b）中流水线阶段2中的寄存器因子15可以消除。下面将这种优化的步骤称为加法器重复。比起图2（b）总共可以节省三个寄存器操作。图2. （a）加法图的系数集合 480，512，846，1020 ，（b）流水线加法器图割后定时，（c）FPGA的优化流水线加法图3 使用二进制整数线性规划最小化流水线操作 该程序在寻找最佳的调度以及最好的加法器重复时一般是没有如上面例子这样简单的一个任务的。在一个流水线阶段清除一个寄存器可以排除清除其他几个寄存器。找到具有最小节点数的流水线加法图的优化问题，可以制定二进制整数线性规划（bilp）问题。使用二进制PK调度矩阵S描述流水线加法器图， 如果常数ck在流水线阶段p被调度，则元素sp,k为“1” ，K和P分别表示独特的奇系数（包括未输出系数）的个数和流水线的级数。P等于加法器图的加法深度。所有的偶系数可以由奇系数的有线移位来实现。图2(c)中的调度矩阵图是由以下式子 (3.1)给出的，其中的列对应于排序的奇系数c1 = 1, c2 = 15, c3 = 47, c4 = 255 and c5 = 423。 优化问题现在可以归结为最小化线性目标函数问题 (3.2)例如，尽量减少S中“1”的个数，同时考虑额外的设计约束条件。对于每一个系数和流水线阶段的约束条件，利用等式和不等式体现所有的依赖关系。加法器输入值计算实际的系数ck，它们被记为ci和cj。取决于系数的值和输入节点，有三种情况导致不同的等式/不等式：i）ck=1：A 1可在阶段1实现而不需要计算。为了在阶段P产生a 1，a 1必须在阶段P1实现，对于所有P1，以下不等式必须保持成立： 0 (3.3)ii）ck 1, ci = cj : 节点ck依赖于一个单一的节点（如15，255或者423中的例子），所以它只能在阶段P实现，如果节点ci（或cj）在阶段P1实现或者ck已经在P1阶段实现。此外，如果ci=1（如ck=423），这是不可能在阶段1实现的，从而导致以下等式或不等式：= 0 | for ci _= 1 and p = 1 0 | for p 1 (3.4)iii）ck 1, ci cj : 这一情况涉及的节点，取决于前两个节点ci和cj（如节点47取决于节点1和节点15）。它只能在阶段P实现如果节点ci和cj在阶段P1实现或者ck已经在P1阶段实现。在阶段1实现一般是不可能的，它的结果是= 0 | for p = 12 2 0 | for p 1 (3.5)当然，所有的输出系数必须根据约束在流水线最后阶段实现。= 1 (3.6)4 结果4.1 最优流水线的结果下面的实验是使用滤波器基准设置 2的，其中包含从6个到151个水龙头滤波器。系数数据是在线提供的FIR滤波器基准组 10 ，标记为mirzaei10 N，其中N表示系数的个数。加法器图使用以最小加法器计数或者最小加法器深度进行配置的HCUB算法来获得，这被称为“HCUB AD MIN”。 加法器的深度是流水线的关键，因为它直接决定了流水线阶段P的个数，因此，即使为了一个较低的加法器深度需要更多的加法器，但由于较低的流水线级数可以节省下流水线寄存器这也是值得的。 BILP问题的进度与流水线优化的解决方法是使用MATLAB的bintprog方法。为比较而言，实施CSR的同时另外使用了as-soon-as-possible（ASAP）方法。表1 HCUB和HCUB AD MIN的优化结果，使用基准一套 2,没有任何流水线（WO.PIP.），CSR流水线和最优流水线的提出（OPT.PIP.）。图3. 加法器图方法的资源和速度比较 由此操作的结果列于表一中，这些操作无论是没有流水线的加法器/减法器的实现，还是寄存器和使用CSR或者优化流水线的存储加法器/减法器，正如预期所料的那样，没有流水线的最少的加/减法资源由HCUB得到。当没有流水线时加法器图HCUB AD MIN导致平均6.9%以上的加法器的增加。然而，由于较低的加法器深度，流水线操作通过使用HCUB AD MIN得到。最佳流水线的提出导致运算量的大量减少，对比CSR方法，是HCUB为29.1%和HCUB AD MIN 为6.8%。优化流水线开销相比组合加法图的平均水平是45.4%。HCUB共有21个操作可以节省重复使用加法器，但HCUB AD MIN只有2个操作可以节省。BILP算法的优化时间在2.4GHz的四核处理器中为0.9秒到36分钟。表2 滤波器基准 2 所提出的方法（HCUB AD MIN.OPT.PIP）和其他方法比较的综合结果。4.2 综合结果 我们得到了使用HCUB AD MIN的滤波器综合结果。结合所提出的优化流水线，这些结果将和基于HCUB的没有流水线的滤波器，加法/移位 2（数据取自 1）和转置MAC滤波器进行比较，这里所使用的编译器为Xilinx Coregen FIR Compiler（v4.0）。如加法/移位的结果，所有的设计都采用ISE11.1标准，基于 Xilinx virtex-4FPGA（xc4vlx100-10和xc4vsx5510基于MAC的滤波器）进行综合并进行速度的优化。滤波器的输入和输出被寄存以使能一个公平的速度比较。在 2 ，输入字的大小是12位。综合的结果总结于表二。所有过滤器以充分的精度实现，产生不同字长的输出（表二中的w0）。表二中基于加法器图方法的切片的数目以及最大频率绘制在图3中。结果表明，所提出的最佳流水线，在大多数情况下（除了N=13），采用HCUB AD MIN方法在资源的使用方面优于加法/移位方法，而性能却相似。平均来说，HCUB AD MIN方法减少了54.1%片而获得的最大频率减少11.8%。关于HCUB，优化流水线的开销平均是18%片，其中主要是额外的触发器。比起平均加速比为308%，这是小比例。基于MAC的FIR滤波器的综合结果见表二的最后一栏。FIR编译器选择了转置结构，其使用了数字信号处理模块的乘法和加法。可以看出，MAC滤波器有利于他们以非常高的速度滤波，他们相比所建议的方法提供的进一步的加速比为55.2%。然而，数字信号处理模块必须是可用的，这仍然是一个FPGA的低成本化，甚至现代化的问题。结论 本文表明，所提出的优化流水线加法器图方法导致滤波器的设计比起加法器图方法使用的资源低得多，而性能却相似。如加法/移位方法 1， 2 比并行分布式算法的实现需要更少的资源，人们可以得出这样的结论：本文所介绍的方法也优于并行分布式算法的实现。因此，该方法对于具有较少嵌入式乘数器数目的较小的FPGA或者当使用嵌入式乘法器时需要一个较长的字长的高分辨率的滤波器是很有吸引力的。 该方法原则上可以用于任何的MCM算法。然而，结果表明，对于FPGA上的资源高效的流水线，较低的加法器深度比最小加法器计数更为重要。这是大部分MCM算法的目标。该方法不局限于FPGA。它可根据加法器和触发器的不同成本要求修改为专用集成电路的设计。致谢 非常感谢shahnam mirzaei为我们提供了滤波器系数以及综合的细节，帮助复制结果 1和 2。他们也非常感谢马蒂亚斯福斯特从新加坡卓有成效地讨论和管理基准滤波器 10。参考文献1 S. Mirzaei, A. Hosangadi, and R. Kastner, “FPGA implementation of high speed FIR filters using add and shift method,” in IEEE ICCD 2006, 2006, pp. 308313.2 S. Mirzaei, R. Kastner, and A. Hosangadi, “Layout aware optimization of high speed fixed coefficient FIR filters for FPGAs,” Int. Journal of Reconfigurable Computing, vol. 3, pp. 117, Jan 2010.3 M. Imran, K. Khursheed, and M. ONils, “On the number representation in sub-expression sharing,” IEEE ICSES 2010, pp. 17 20, 2010.4 D. Bull and D. Horrocks, “Primitive operator digital filters,” IEEProceedings, vol. 138, pp. 401411, 1991.5 A. Dempster and M. Macleod, “Use of minimum-adder multiplier blocks in FIR digital filters,” IEEE Trans. Circuits Syst. II, vol. 42, no. 9, pp.569577, 1995.6 Y. Voronenko and M. Puschel, “Multiplierless multiple constant multiplications,”ACM Trans. Algorithms, vol. 3, no. 2, pp. 138, 2007.7 Spiral Project Website. (2011) Software/hardware generation for DSP algorithms. Online. Available: 8 U. Meyer-Baese, J. Chen, C. H. Chang, and Dempster, “A comparison of pipelined RAG-n and DA FPGA-based multiplierless filters,” in IEEEAPCCAS 2006, 2006, pp. 1555 1558.9 K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation.John Wiley & Sons, 1999.10FIRsuite. (2011) Suite of constant coefficient FIR filters. Online.Available: .High Speed Low Complexity FPGA-based FIR Filters Using Pipelined Adder GraphsMartin Kumm and Peter ZipfDigital Technology GroupUniversity of Kassel, 34121 Kassel, GermanyEmail: kumm, zipfuni-kassel.deABSTRACT A method for generating high speed FIR filters with low complexity for FPGAs is presented.First, an adder graph is obtained using an existing multiple constant multiplication (MCM) algorithm. This adder graph describes the required multiplier block of the FIR filter using only additions/subtractions and shifts. Secondly, a novel FPGA-specific combined schedule and pipeline optimization is performed to gain the maximum speed while using a minimal performance penalty. FPGA-specific characteristics are exploited during optimization including the reduction of pipeline registers by duplicating adders in later stages. The optimization is formulated as binary integer linear programming (BILP) problem. It is shown that the generated number of pipelined operations based on the Hcub MCM algorithm is reduced up to 29.1% on average compared to an as-soon-as-possible (ASAP) scheduling using cut-set retiming. Synthesis results are obtained by generating VHDL code, showing that the proposed method outperforms the recently proposed Add/Shift method in resource complexity (54.1% reduction on average) while a competitive performance is achieved (88.2% speed of Add/Shift on average).1 INTRODUCTION The finite impulse response (FIR) filter is one of the key applications in digital signal processing (DSP). It is used in many DSP systems due to its linear-phase, strict stability, and high-throughput. Nowadays, field programmable gate arrays (FPGAs) are often used for filter applications as they offer the processing of real time signals up to several MHz while providing more flexibility than application specific integrated circuits (ASICs).A lot of research has been done so far on the hardware efficient implementation of FIR filters.The structure of an FIR filter in transposed form is shown in Fig. 1. This structure is beneficial compared to the direct form as the delay elements (z1) can be used as pipeline registers for the structural adders (adders outside the dashed box). In ASIC designs, the multiplication by several constants is usually reduced to additions, subtractions and shifts. Finding the minimal configuration of adders1 (shifts are assumed to be free) is known as multiple constant multiplication (MCM) problem 16. The optimization problem is NP-complete 6 and has been an active research topic for almost the last two decades. MCM algorithms can be divided into common-sub expression elimination (CSE) 13 and graph based methods 46. CSE methods try to identify common patterns in the coefficients while graph based methods try to construct the coefficient values in a bottom-up manner. Graph based methods are more complex (in runtime) but are independent of the number representation 3 and usually find better solutions than CSE-based methods 6. One of the leading MCM heuristics in terms of quality of optimization results and runtime is the Hcub algorithm 6 which outperforms the previous graph based methods BH 4, BHM and RAG-n 5.The implementation of Hcub is open source 7. In a recent version, the total adder depth (AD) can be limited, which is the maximum number of adder stages from the input to all outputs. This leads to a shorter critical path while the amount of adders is slightly increased. For efficient FPGA-based realizations of FIR filters the features of the architecture must be considered. These are inparticular arithmetic components like full adders and embedded multipliers as well as look-up tables (LUTs) and flip-flops (FF). Distributed arithmetic (DA) has long been the favored method to implement FIR filters, as LUTs and adders are used, which perfectly matches the FPGA architecture. However, Meyer-Baese 8 et al. showed that an FPGA-based parallel DA implementation needs 71% more resources on average than a pipelined adder graph realization computed by the RAG-n algorithm 5. Similar results were also achieved by the Add/Shift method of Mirzaei et al. 2, where a CSE method with FPGA-specific cost function was used. A LUT and FF reduction of 58.7% and 25% could be achieved, respectively, compared to the parallel DA implementation. The performance of both methods was almost the same. It was pointed out in2, that adder graphs of Hcub on the one hand lead to a much lower resource usage compared to their CSE method (72% LUT and 11% FF reduction) but on the other hand lead to a poor performance (68% drop), as pipelining and the use of FPGA-specific features are not considered in the algorithm. Fig. 1. FIR filter in transposed formIn this work, a novel method to produce pipelined multiplier blocks with low resource usage is presented. It is based on adder graphs, e. g. obtained by an MCM algorithm, whichare further optimized with FPGA-specific scheduling and retiming.2 PIPELINING OF ADDER GRAPHS2.1 Pipelining using Cut-Set RetimingThe starting point for retiming is an adder graph obtained by an MCM algorithm. An example adder graph is shown in Fig. 2(a), which realizes a multiplier block with constants of the coefficient set C = 480, 512, 846, 1020. This example is used throughout this paper to illustrate the algorithms. The graph needs four adders and was computed using Hcub.Fig. 2. Adder graph for the coefficient set 480, 512, 846, 1020 (a), thepipelined adder graph after cut-set retiming (b), the FPGA optimized pipelined adder graph (c)All nodes drawn as circle except the input node (value 1) correspond to adders or subtractors. The value of each node is equal to the factor that is realized at this node, output nodes are drawn without circle. All edge weights are shift factors, e. g., node 15 is realized by shifting the input x by 4 bit and subtracting the unshifted input: 15x = 24x 20x.Pipelining of directed acyclic graphs like adder graphs can be easily performed using cut-set retiming (CSR) 9. The realization of the most complex coefficient in the example has an AD of three (node 423). Therefore, the number of pipeline stages is set to three (without input/output registers).One possible pipelined adder structure after CSR is shown in Fig. 2(b). Each node drawn as box includes a register, i. e. stands for either a pure register (one input) or a registered adder (two inputs). Assuming the same computation time for each addition, the maximum clock frequency of the structure in Fig. 2(b) can be approximately three times higher than for the original structure if inputs and outputs are registered. In total 11 additional registers are used to pipeline the graph,which is a huge expense compared to the four adders of the structure without pipelining.Taking a closer look at the pipelined structure it reveals that by using a different scheduling, some of the registers can be eliminated. For example, coefficient 255 depends on input node 1, which is also available in pipeline stage 2, so it can be moved to stage 3 saving two registers. Further registers can be saved by utilizing FPGA characteristics, which are discussed in the following.2.2 Pipelining for FPGA-ArchitecturesThe basic logic elements used in modern FPGAs consist at least of a look-up table (LUT), full-adder (FA) logic with fast carry chain and an optional output flip-flop (FF). These elements are common to all modern FPGAs even if FPGA manufacturers organize them in different units. The unit containing one LUT, FA and FF is referred as basic logic element (BLE) in the following. Adders are usually implemented as ripple-carry adders on FPGAs requiring one FA or one BLE for each bit. Hence, an N bit adder or subtractor needs N BLEs. Furthermore, the number of BLEs needed to implement an N bit adder is equal to the implementation of an N bit registered adder. Thus, the pipelining of single adders can be realized without extra costs. A pure N bit register needs N BLEs. Using this model and assuming equal word sizes on each edge for simplification, it becomes obvious that each node drawn as box in Fig. 2(b) requires approximately the same hardware resources. Therefore, the register for factor 15 in pipeline stage 2 of Fig. 2(b) can be eliminated if the coefficient is computed again in the last stage. This optimization step is called adder duplication in the following. The optimized pipelined adder graph is shown in Fig. 2(c). Three registered operations could be saved in total compared to Fig. 2(b).3 OPERATION MINIMIZED PIPELINING USING BINARY INTEGER LINEAR PROGRAMMINGThe procedure in finding the best scheduling as well as the best adder duplication is in general not such a trivial task as in the example above. For example, eliminating a register in one pipeline stage may exclude the elimination of several other registers. The optimization problem of finding the pipelined adder graph with minimal number of nodes can be formulated as binary integer linear programming (BILP) problem which is derived in the following. The pipelined adder graph is described using a binary PK scheduling matrix S. Element sp,kof S is 1 if constant ck is scheduled in pipeline stage p. K and P denote the number of unique odd coefficients (including non-output coefficients) and the number of pipeline stages, respectively. P is equal to the adder depth of the adder graph. All even coefficients can be realized by wired shifts from odd coefficients. The scheduling matrix of the graph in Fig. 2(c) is given by (3.1)where the columns correspond to the sorted od