一种实现迭代算法的FPGA并行计算电路自动生成方法

摘要

一种实现迭代算法的FPGA并行计算电路自动生成方法，步骤如下：（1）用串行计算电路实现所述迭代算法；（2）针对所述串行计算电路，提取该电路时序逻辑中的寄存器及组合逻辑，将提取出的寄存器作为存储部分，组合逻辑作为计算部分；（3）将所述迭代算法的串行计算电路表示为迭代函数及输出函数的形式；（4）将所述串行计算电路中需要多个时钟执行的计算全部压缩到1个时钟内执行，得到并行计算迭代式；（5）使用FPGA的设计语言描述所述并行计算迭代式；（6）根据步骤（5）中描述出的并行计算迭代式生成FPGA并行计算电路。使用本发明可不再使用手工推导并行计算式，可直接生成并行计算电路，可显著加速和简化迭代型算法VLSI并行计算电路的设计过程。

说明书

技术领域

本发明涉及一种实现迭代算法的FPGA并行计算电路自动生成方法，可 以不借助手工推导并行迭代式直接生成迭代算法并行计算电路，属于信号处 理及微电子芯片技术领域。

背景技术

基于VLSI（大规模集成电路）的高性能计算技术在嵌入式高速信号处理 领域扮演着举足轻重的地位。在系统计算需求激增的今天，针对多维高速数 据实时处理的计算速率要求动辄上千GMACS，嵌入式系统中传统哈弗结构 或冯·诺依曼结构的处理器只能望洋兴叹。基于VLSI的高性能计算技术凭 借现代微电子技术规模的指数增加及硬件电路固有的并行特性，提供了强大 的计算能力，弥补了传统处理器与嵌入式高性能计算需求之间的鸿沟。以 Xilinx公司7系列FPGA为代表的大容量FPGA，单芯片最高可提供 3960×2×638MHz=5053GMACS的计算能力，而同期最高性能8核DSP仅 能达到320GMACS的计算能力的计算速率。在基于VLSI实现高速海量信号 处理算法过程中，绝大部分涉及数据的迭代计算。而如何充分发挥VLSI计 算技术的优势的关键，就是如何为相关算法设计高并行度的计算结构。传统 设计算法并行计算电路时，主要以手动推导并行计算表达式，并按照其表达 式设计电路，当并行度或相关参数需要调整时，又需要再次推导新的并行表 达式，并重新设计并行计算电路。这种方法即耗时耗力，又需要设计人员具 有较深厚的技术能力。

发明内容

本发明解决的问题是：克服现有技术的不足，提供一种实现迭代算法的 FPGA并行计算电路自动生成方法，使设计人员不用借助手工推导并行迭代 式而直接生成迭代算法并行计算电路，大大简化相关FPGA芯片的开发难度 及加速开发速度。

本发明的技术解决方案是：

一种实现迭代算法的FPGA并行计算电路自动生成方法，步骤如下：

（1）用串行计算电路实现所述迭代算法；

（2）针对所述串行计算电路，提取该电路时序逻辑中的寄存器及组合 逻辑，将提取出的寄存器作为存储部分M，组合逻辑作为计算部分f()和 h()；

（3）将所述迭代算法的串行计算电路表示为迭代函数及输出函数的形 式；

（4）将所述串行计算电路中需要多个时钟执行的计算全部压缩到1个 时钟内执行，得到并行计算迭代式；

（5）使用FPGA的设计语言描述所述并行计算迭代式；

（6）根据步骤（5）中描述出的并行计算迭代式生成FPGA并行计算电 路。

所述步骤（3）中迭代算法的串行计算电路表示为迭代函数及输出函数 的形式具体为：$\left(\begin{array}{c}{M}_{n+1}=f(M_n,D_n,\alpha ),(\alpha \in \Lambda )\\ Y_n=h(M_n,D_n,\beta ),(\beta \in \Lambda )\end{array}\right),$其中，M_n表示n时刻的存 储部分，D_n表示n时刻的输入数据，f(,,α)表示存储部分的更新函数，Y_n为 n时刻输出数据，h(,,β)表示输出函数；α和β均表示任一参数。

所述并行计算迭代式具体为：

$\left(\begin{array}{c}{M}_{n+k}=f(f(f(....f(M_n,D_n,\alpha )....,D_{n+k-3},\alpha ),D_{n+k-2},\alpha ),D_{n+k-1},\alpha ),(\alpha \in \Lambda )\\ Y_n=h(M_n,D_n,\beta ),(\beta \in \Lambda )\\ Y_{n+1}=h(f(M_n,D_n,\alpha ),D_{n+1},\beta ),(\beta \in \Lambda )\\ ·\\ ·\\ ·\\ Y_{n+k-1}=h(f(f(....f(,D_n,\alpha )....,D_{n+k-3},\alpha ),D_{n+k-2},\alpha ),D_{n+k-1},\beta ),(\beta \in \Lambda )\end{array}\right)$

其中，k为并行计算电路的并行度且k为正整数。

本发明与现有技术相比的有益效果是：

本发明提供实现迭代算法的FPGA并行计算电路自动生成方法，使用本 发明所述方法可以在设计相关并行电路时，不再使用手工推导并行计算式， 可直接生成并行计算电路，可显著加速和简化迭代型算法VLSI并行计算电 路的设计过程。

附图说明

图1为一种实现迭代算法的FPGA并行计算电路自动生成方法流程图

图2为串行迭代计算的数据流图

图3为串行迭代计算的VLSI硬件结构图

图4为k并行度迭代计算的数据流图

图5为k并行度迭代计算的VLSI硬件结构图

图6为自动生成电路计算并行CRC仿真波形

图7为手工推导电路计算并行CRC仿真波形

具体实施方式

基于VLSI的高性能计算技术在嵌入式高速信号处理领域扮演着举足轻 重的地位，而并行计算结构的设计在其中起到关键作用。传统迭代算法的并 行计算电路设计主要以手工推导并行计算公式为基础，再以电路搭建并行计 算电路，较为繁琐，并要求设计者有较高的专业水平。为简化和加速迭代型 算法并行电路的设计，本发明给出一种实现迭代算法的FPGA并行计算电路 自动生成方法，可以直接描述并行计算电路并自动综合生成优化的并行计算 结构。

如图1所示，本发明提供了一种实现迭代算法的FPGA并行计算电路自 动生成方法，步骤如下：

（1）用串行计算电路实现所述迭代算法

用串行计算电路实现所述迭代算法，该串行电路可以直观地实现迭代 算法，同时该电路也用于提取算法的“存储+更新”计算模型。

（2）针对所述串行计算电路，提取该电路时序逻辑中的寄存器及组合 逻辑，将提取出的寄存器作为存储部分M，组合逻辑作为计算部分f()和 h()；

迭代算法的计算实现过程包括几个要素：输入数据、计算方法、计算缓 存、输出数据。

（3）将所述迭代算法的串行计算电路表示为迭代函数及输出函数的形 式；

所述步骤（3）中迭代算法的串行计算电路表示为迭代函数及输出函数 的形式具体为：

$\left(\begin{array}{c}{M}_{n+1}=f(M_n,D_n,\alpha ),(\alpha \in \Lambda )\\ Y_n=h(M_n,D_n,\beta ),(\beta \in \Lambda )\end{array}\right)$

其中，M_n表示n时刻的存储部分，D_n表示n时刻的输入数据，f(,,α)表 示存储部分的更新函数，Y_n为n时刻输出数据，h(,,β)表示输出函数；α和β 均表示任一参数

（4）将所述串行计算电路中需要多个时钟执行的计算全部压缩到1个 时钟内执行，得到并行计算迭代式；

具体是将迭代算法的计算过程在时间和空间上展开，可得到其计算流图 表达，如图2所示，其对应的串行迭代计算的VLSI硬件结构如图3所示。 图2中，每个时间单位，即VLSI电路的1个时钟执行一次迭代计算，完成 f()，更新存储部分M_n，同时完成h()，计算输出数据。图3中，VLSI 电路中使用寄存器缓存存储部分，利用两个组合逻辑电路f()，h()完成存储 部分更新计算及输出计算，每个时钟上升沿输入一个数据，并完成一次迭代， 同时输出一个输出数据。

在串行迭代计算的数据流图中，每个时间单位完成一次迭代计算，而本 发明使其k个时间单位内完成的k次迭代计算在1个时间单位内完成。如图4 所示，将k个时间周期折叠到1个时间周期内，其中的过程计算数据不再经 过寄存器存储。图5给出了按照图4中“时钟折叠”方法设计的k并行度迭 代计算的VLSI硬件结构。其中每个时钟周期输入k个数据D_n～D_n+k-1，输出k 个数据Y_n～Y_n+k-1。其中将一系列组合逻辑进行了级联得到f(f(f(...)))及h(.)、 h(f(.))、…h(f(f(f(...))))。

（5）使用FPGA的设计语言描述所述并行计算迭代式；

所述并行计算迭代式具体为：

$\left(\begin{array}{c}{M}_{n+k}=f(f(f(....f(M_n,D_n,\alpha )....,D_{n+k-3},\alpha ),D_{n+k-2},\alpha ),D_{n+k-1},\alpha ),(\alpha \in \Lambda )\\ Y_n=h(M_n,D_n,\beta ),(\beta \in \Lambda )\\ Y_{n+1}=h(f(M_n,D_n,\alpha ),D_{n+1},\beta ),(\beta \in \Lambda )\\ ·\\ ·\\ ·\\ Y_{n+k-1}=h(f(f(....f(,D_n,\alpha )....,D_{n+k-3},\alpha ),D_{n+k-2},\alpha ),D_{n+k-1},\beta ),(\beta \in \Lambda )\end{array}\right)$

其中，k为并行计算电路的并行度且k为正整数。利用VHDL硬件描述语 言中variable的特性，在一个时钟周期内完成多步迭代算法的计算。

（6）根据步骤（5）中描述出的并行计算迭代式生成FPGA并行计算电 路。 使用FPGA设计语言直接描述图5或并行计算迭代式即可综合得到并行 计算电路。为了验证其正确性，设计相应测试向量，使用仿真软件验证其计 算结果的正确性（以CRC计算为例，如图6、图7所示）。