【经验】如何在FPGA上实现低成本开根号运算？

开根号运算是科学计算和工程应用中基本而重要的运算之一，在QuartusII和ISE开发软件中，都集成了开根号的ip核，这些底层源码对于用户来说是不可见的，那么如何在西安智多晶的FPGA中实现开根号运算，是本文要探讨的课题。

开根号运算介绍

开根号运算属于非线性运算，无法用解析的方程来求解，常利用迭代法来逐次逼近求解，常用的开方算法有牛顿-莱福森算法、逐次逼近算法和非冗余开方算法等。这几种算法，单纯从FPGA应用的角度来看，逐次逼近算法是最适合在FPGA上实现。利用FPGA的流水线结构，可以实现全并行数据吞吐的开方运算，其资源开销较大。然而在很多应用场合，开方运算并不需要实时的吞吐，有些应用仅仅需要在某一个时刻对一个数值进行开根号，取其结果用在另一个物理量上的运算。因此这里我们将实现一种非实时数据吞吐的开根号运算，在输入有效使能拉高后，数据进入开根号模块，若干周期后，输出使能拉高，并输出开方运算结果，资源占用率低，适合大多数应用场景。

逐次逼近算法原理

逐次逼近算法简单些讲，就是假定一个输出暂存值，先取MSB为‘1’，其余为‘0’。用其平方值与被开方数比较，如果前者大于后者，则把MSB置零，取次高位为‘1’，再进行比较；若前者小于后者，则次高位不变，次次高位再取‘1’，再进行比较。以此类推，直到最后LSB也判别完毕。这样对于一个n bit输入的数据，理论需要判断n/2次。这里我们进行了改进，首先把输入数据的符号位去除，再进行迭代，这样可以缩短迭代次数。但是有一点需要注意，平方运算需要用到一个乘法器，为了让系统时钟能跑高，乘法运算总的打3级流水。因此迭代次数要算上乘法带来的延迟，对于非实时吞吐的应用，迭代次数的额外开销不会对整体应用带来多大的影响。迭代流程如下图所示：

程序Modelsim仿真

根据上述迭代过程，编写sqrt_serial.v程序，设计输入待开方数据为36bit位宽，输出数据18bit位宽，余数19bit：

接下来先在Modelsim里进行仿真，先编写相应的testbench，部分测试程序：

//--------------------------------------------------------------------------------

         sqrt_serial  sqrt_serial

         (

                   .clk             (        clk                        ),

                   .rst             (        rst                        ),

                   .i_vaild       (        i_vaild                 ),

                   .i_data                 (        i_data                  ),

                   .o_vaild      (        o_vaild                ),

                   .o_data                (        o_data                 ),

                  .r_data                (        r_data                 )

         );

//--------------------------------------------------------------------------------

         initial begin

                   // Initialize Inputs

                   clk = 0;

                   rst = 1;

                   // Wait 100 ns for global reset to finish

                   #100;

        rst = 0;                 

         end

         always #5 clk  = ~ clk ;        

         reg    [7:0]  cnt ; 

         reg x;

//--------------------------------------------------------------------------------

         always@(posedge       clk or posedge     rst)

                   begin

                            if(rst)

                                     begin

                                               i_vaild <= 0;

                                               i_data <= 0;

                                               cnt <= 0;

                                               x <= 1'b0;

                                     end

                            else if(!x)

                                     begin

                                               i_vaild <= 1;

                                               i_data <= i_data + 1'b1;

                                               cnt <= 0;

                                               x <= 1'b1;

                                     end

                            else if(x)

                                     begin

                                               if (o_vaild)

                                                        begin x <= 1'b0; end

                                               i_vaild <= 0;                                             

                                               cnt <= cnt + 1'b1;

                                     end

                   end

//--------------------------------------------------------------------------------

在testbench里，让i_data从1开始，sqrt计算完毕就让i_data加1再输入，观察开方运算的结果，仿真之后验证了设计的可行性：

资源消耗

在海麟软件里编译，其资源消耗小，不过需要额外消耗一个乘法器：