罗超，阎威武

0 引言

二次规划是一类重要的优化问题，它广泛的应用在运筹学，金融学中，许多工程上的优化问题也可以归结为二次规划的求解，如：预测控制，最小二乘等。嵌入式技术的发展使得嵌入式系统广泛地应用于人类生活的方方面面。由于二次规划的求解需要大量的计算，因此在传统的基于ARM的嵌入式平台上实现比较困难。

FPGA(Field Programmable Gate Array)作为一种半定制的集成电路已经广泛应用在汽车，工业，通信，航空航天等领域。FPGA并行计算，硬件加速的特点使得在嵌入式平台上快速求解二次规划成为了可能。

本文主要提出了一种基于FPGA的二次规划求解方法。首先介绍了二次规划的求解算法，然后将算法进行优化与在PC上实现，再将算法在FPGA平台上实现，最后进行了实验验证。

1 二次规划算法介绍

二次规划是非线性规划中的一种特殊情形，它的目标函数是二次实函数，约束是线性的，由于二次规划应用较广且一些非线性规划可以转化为一系列二次规划来求解，因此二次规划引起了人们广泛的关注[1]。二次规划的一般形式如（1），常用的最有效的两种方法是：内点法和有效集法[2]。

本文采用的算法是不可行-原始对偶-路径跟踪法，顾名思义，这种算法结合了不可行，原始对偶，路径跟踪三种方法的优点。内点法要求我们在实现算法之前要找出一个内点，这样不利于算法的实用性[3]，不可行内点法解决的问题是常规内点法初始点不好找的问题。而原始对偶法利用了对偶原理，从对偶问题的一个可行解出发，同时解原始和对偶问题，求出原问题满足互补松弛条件的可行解，这样可以达到减少迭代次数的目的。路径跟踪法在松弛KKT条件和原始对偶的基础上，给出了一条中心路径以使得迭代更快的收敛。算法的具体介绍可以参考文献[4]。

2 C语言算法实现与优化

本文先在PC上采用C语言实现二次规划求解算法，该程序主要参照了Alex J. Smola编写的pr_loqo。程序中包括以下几个基本模块：

(1) choldc模块，此模块的作用是将矩阵A切比雪夫分解，A=L’L，其中A是对称正定矩阵，L是上三角矩阵。

(2) cholsb模块，此模块的作用是求解方程组AX=b，其中A是对称正矩阵，需要用到上面的choldc模块。

(3) chol_forward，chol_backward模块用于求解Ax=b，其中 A是对称正定阵，则经过 cholesky分解得 LL'x=b,令y=L'x，采用 chol_forward解出 Ly=b，采用 chol_backward解出L'x=y

(4) matrix_vector模块，此模块的作用是计算对称矩阵与向量的乘积。

(5) solver_reduced模块，此模块的作用是采用预估-校正方法来计算方程组。

(6) pr_loqo模块，求解二次规划的核心模块，该模块通过递归调用上面各个模块得到二次规划的最终结果。

以上程序是双精度浮点型算法，在FPGA中用硬件实现浮点数运算是非常低效的，将浮点算法改为定点算法能降低FPGA资源消耗，提高运算速度。

浮点小数是指小数点位置不固定的小数，有单精度和双精度两种，分别在计算机中占用4，8个字节，IEEE754是浮点运算的工业标准。定点小数的小数点位置固定不变，比如规定小数点后面有2位，10位，12位，相应的定点格式称为Q2，Q10，Q12。当实际小数小数点后面位数小于n时用0补齐，反之则采用四舍五入阶段后面的位数，因此定点小数存在舍入误差。采用定点数的目的就是为了将小数变为整数来运算以达到加快运算的目的。假如采用Qn格式的定点小数，x表示一个实际的浮点数，q表示它的Qn型定点小数，则他们之间的转换关系为：

由此可以得出定点小数的+-*/算法：假设q1,,q2,q3表达的值分别为x1,,x2,x3

其中整数乘除2n可以通过右移，左移n位来实现以加快计算速度。

浮点算法转为定点算法要注意以下两点：

（1）要注意定点数能表示的数值大小范围，防止上溢和下溢，如：采用int型来表示定点小数，末尾12位为小数部分，能表示的最小的正数约为0.000244。

（2）浮点算法中的常整数要也要变为定点小数形式，如：a=a+1应该变为a=a+ (1＜n)

3 FPGA中算法实现

在 FPGA中实现二次规划，采用的开发工具主要是Impulse C。Impulse C 包 括 由 Impulse Accelerated Technologies提供的一个函数库，编译器，调试工具，这些工具与ANSI C兼容[5]。系统开发者能够用Impulse C语言开发FPGA，Impulse C主要用于算法级别描述。Impulse C的集成开发环境是 Codeveloper，在里面可以编辑，编译，调试，仿真，生成HDL，导出软，硬件到特定平台如Altera NIOS II，Xinlinx Microblaze 等。

Impulse C是以流为核心的编程语言，流是进程同步通信的主要方式。进程是Impulse C应用程序的核心，对应于VHDL中的entity，Verilog中的module，进程分为软件进程和硬件进程两种，硬件进程是FPGA中的硬件电路，软件进程运行在软核中。软件进程与硬件进程，软件进程之间，硬件进程之间通过流，信号，共享存储器来实现并行独立进程之间的同步。图一是硬件进程的一个示意图：

图1 Impulse C应用程序核心：进程

将第二节中的定点算法由Impulse C语言来描述，进程通信图如图二。图二中椭圆代表进程，双箭头线代表流通信，其中 matrix_vector，pr_loqo，solver_reduced，cholsb，chol_forward，chol_backward为硬件进程，其余的为软件进程。

图2 进程通信图

采用Impulse C编程要注意以下三点：

（1）Impulse c的两个进程间同方向不允许多条流存在，只允许一条流的存在。

（2）流的方向是单一的，不能即是输出流又是输入流。

（3）Impulse c不支持malloc，因此要采用宏的形式用定长数组来代替内存动态。

4 实验验证

本文中采用的FPGA为Altera公司的cyclone II系列，开发软件为Impulse C，Quartus II，NIOS II IDE。在FPGA内实现了一个NIOS II软核和二次规划的硬件进程。下面通过一个例子来测试此方法是否能得到正确的结果。

x1=通过比较可以看出结果误差很小。

5 结束语

本文介绍了一种基于FPGA的二次规划求解方法，首先介绍了二次规划的求解算法，然后将算法进行优化与在PC上实现，再将算法在FPGA平台上实现，通过实例证明了此方法的正确性。

[1] 陈宝林.最优化理论与算法[M] .北京:清华大学出版社.2005.

[2] Ling K V, Yue S P and J M,Maciejowski A.FPGA Implementation of Model Predictive,Control[R] .Proceedings of the 2006 American Control Conference Minneapolis, Minnesota, USA, June 14-16, 2006.

[3] 王言金.最优化的不可行内点算法研究[D] .武汉.武汉大学. 2004.

[4] Vanderbei R. LOQO: an Interior Point Code for Quadratic Programming. Optimization Methods and Software[J] .1999(11) :451-484.

[5] David Pellerin, scott thibault.实用C语言FPGA编程.机械工业出版社[M] .2007.