粒子群优化在嵌入式软硬件划分中的应用.doc

周雁 等 粒子群优化在软硬件划分中的应用 3
粒子群优化在嵌入式软硬件划分中的应用
摘要：针对嵌入式系统设计中的软硬件划分问题，本文提出了一种基于粒子群优化（PSO）算法的划分策略，并将该算法与整数线性规划、遗传算法、蚁群算法等进行计算机仿真比较。结果表明，该方法获得的最优解优于遗传算法和蚁群算法两种元启发式算法，充分接近由整数线性规划得到的最优解；在算法执行时间方面，该方法也优于其它三种算法。
关键字：粒子群优化　软硬件划分　元启发式　整数线性规划　群智能
Research on the Use of Particles Swarm Optimization in Hardware/Software Partitioning in embedded system
Abstract To solve the hardware/software partitioning problem in embedded system, this paper proposes a meta-heuristic Particles Swarm Optimization Algorithm. Computer simulation on standard benchmarks was performed, the empirical test reveals that the present Particles Swarm Optimization generates solutions close to the results of Integer Linear Programming, and it outperforms Integer Linear Programming Genetic Algorithm and Ant Colony Optimization with respect to runtime requirements for the given partitioning problem.
Key words Particles Swarm Optimization, hardware/software partitioning, meta-heuristic, Integer Linear Programming, Swarm Intelligence

1 引言
嵌入式系统是以应用为中心，以计算机技术为基础，软硬件可裁剪，适用于应用系统，对功能、可靠性、成本、体积、功耗等方面有特殊要求的专用计算机系统[1]。嵌入式系统和典型的计算机系统类似，也包含硬件和软件。硬件通常比软件更快、性能更好，但比较昂贵；相反，软件较便宜、易于开发和修改，但是执行速度较慢并具有较大的功耗。因此，嵌入式系统的目标是使软件延时代价、硬件面积代价及功耗等代价的加权总和最小化。软硬件协同设计就是处理嵌入式系统的这一问题的。其中，软硬件自动划分，即决定系统的哪些部分或组件用硬件实现、哪些用软件实现，是一个根本性的问题。
收稿日期:2010-0-0。周雁，硕士，主研领域：嵌入式系统等。
经典的软硬件划分方法分为两类：确定的和启发式的。确定的算法包括分支定界算法、动态规划法和整数线性规划。然而，在现有文献中，大部分常用的划分方法还是启发式的。这是因为软硬件划分是个NP难问题，当划分规模较大时，确定的算法通常会变得非常慢[2][3]。常见的启发式算法有：遗传算法（GA）、模拟退火、禁忌搜索算法、贪心算法和蚁群优化（ACO）等。
本文提出一个基于元启发式算法的划分策略，该算法起源于鹰、蜜蜂、蚂蚁等智能生物的群体行为。这些生物个体行为都很简单，但当它们一起协同工作时，却能够“突现”出非常复杂（智能）的行为特征，比如觅食、筑巢、迁徙等[4]。基于这些生物的群体行为的算法称为群体智能算法。粒子群优化（PSO）就是一个这样的群智能算法。在此算法中，定义粒子为在给定的搜索空间中搜寻最优解的行为个体。在典型优化技术中常引入导数来寻找最优解，但此种方法在搜索面不连续的情况下不能使用。粒子群优化是一个解决此种工程优化问题、确定最优解的可能方案。软硬件划分问题其根本是一个优化问题，而像粒子群优化这样的多实体搜索算法能引用来找到问题的最优解。算法中的每个粒子的位置都是对问题的一个候选解，各个粒子反复执行粒子群优化算法的步骤来寻找的更好的候选解，直到没有发现更优的解为止。这时候最优粒子的位置对应于问题的最终解。
2 经典的粒子群优化算法
粒子群优化算法与著名的遗传算法类似，是一种基于迭代的进化计算技术，最早由Kenedy和Eberhartt 提出[4]。该算法源于对鸟类觅食的行为研究，他们通过观察发现，鸟群通常通过集体的努力来找到食物。每只鸟根据三个因素来确定它运动状态的改变以接近最终目标（食物源位置）：①自身的当前飞行方向；②到目前为止整个鸟群发现的全局最优位置；③到目前为止自身经历过的个体最优位置。
设xi(t)为粒子i在时间t时的位置，vi(t)为时间t时的速度，pip(t)为到时间t为止粒子i经历的个体最优位置，pg(t)为时间t时所有粒子的全局最优位置。粒子i的运动状态改变可用以下两式来描述：
(1)
(2)
其中，α0、α1和α2分别是速度惯性系数、个体加速度系数和全局加速度系数。α0取值一般在0~1之间，α1和α2根据实际需要取值，一般在0~2之间。三个系数可以为常数，也可随着时间改变，视实际情况而定。研究发现，较大的α0值有利于粒子跳出局部极值位置，而较小的α0值有利于算法收敛[4]。
粒子群优化算法已用于解决优化、搜索和机器学习问题。经典的优化算法通常需要计算给定目标函数的部分或全部导数。但在许多工程和科学的优化问题中，由于非线性目标函数在若干点的不连续，使基于导数的优化技术不能在此类问题中被引入使用。粒子群优化是一种不依赖导数的优化技术，能根据给定目标函数执行粒子群优化算法确定最优解。
在粒子群优化算法中，用粒子来模拟觅食的鸟，用适应度函数来判断粒子位置的优劣，适应度函数越大表示对应位置越优。基本粒子群优化算法概述如下：
输入：每个粒子i的初始位置xi(0)、初始速度vi(0)，适应度函数f(•)；
输出：由最优粒子得到的全局最优位置；
算法步骤：
ⅰ）初始化粒子群，指定或随机产生每个粒子的初始位置和初始速度；
ⅱ）对每个粒子i：计算适应度函数f(xi)，如果满足，则把粒子此时的位置xi作为新的个体最优位置赋给pip(t)；
ⅲ）根据全部粒子的个体最优位置确定全局最优位置pg(t)；
ⅳ）根据粒子群优化基本等式（1）和（2）依次更新粒子的速度和位置。
ⅴ）重复步骤ⅱ）、ⅲ）、ⅳ）直到满足：，其中δ是一个预先设定的小的正数。
3 基于粒子群优化算法的软硬件划分
3.1 软硬件划分问题的形式化定义
首先把嵌入式系统划分成各个功能模块，并采用任务图来定义，具体定义如下：
一个任务图是由一个由节点集V和有向边集E组成的有向图。即：
，
，

其中V表示任务集，E表示从节点i指向节点j的有向边集。有向边在这里代表一种依赖关系，即有向边eij表示节点i代表的任务必须在节点j代表的任务之前执行。
软硬件划分的任务便是要寻找一种使系统总代价最小的划分方案，把V划分成两个集合IH和IS，其中IH中的任务节点用硬件实现，IS中的任务节点用软件实现。
3.2 基于粒子群优化的软硬件划分
粒子群优化可以用于解决软硬件划分问题，在这里，把每个粒子看成是n维的，n表示给定的任务图的任务数目。由此，可以用n维的二进制字符串描述粒子。一个粒子的具体二进制字符串描述如下：

其中二进制位bi表示第i个任务的实现方式，“1”和“0”分别表示该任务用硬件和软件实现；二进制位之间的“･”表示字符的连接。
粒子i对应的划分方案的硬件面积Ai和执行时间Ti分别为
和，
其中，aj为任务j的硬件实现所需面积，tj表示任务j在给定软件平台上的执行时间。如果任务j为软件实现，则aj为0。
定义粒子i的适应度函数为
， (3)
其中，Ca为系统硬件面积约束常量，Ct为执行时间约束常量，σa和σt分别为硬件面积和执行时间的归一化因子。
如此，各粒子在任务的n维空间中穿越，并根据适应度函数反复探测确定最优解。个体最佳位置指到一个粒子的本次重复为止适应度函数最大的位置，全局最佳位置指到本次重复为止整个粒子群中适应度函数最大的位置。经典软硬件划分问题的解就是找出具有最大适应度函数的最优粒子。本例中粒子i的每一维都是二进制的（1表示硬件，0表示软件），因此最优解就是一个描述n个任务硬件或软件实现的二进制字符串。
4 仿真及结果分析
针对文中提出的基于粒子群优化的软硬件划分问题，利用计算机进行了仿真实验。仿真中，为扩大粒子群优化算法前期搜索范围、加速后期收敛速度，将（1）式中的α0设为初值1.2并随时间变化，即，α1和α2固定为1.5。
实验使用IDEA、RC6和MARS三种基准，分别对粒子群优化（PSO）、蚁群优化（ACO）、整数线性规划（ILP）和遗传算法（GA）的执行时间及获得的最优解（即依照算法找到的最佳划分方案实现系统时，该系统的总代价）进行了计算机仿真，其结果分别如表1所示。
已知整数线性规划产生的解总是最优的[[5]，粒子群优化、蚁群优化和遗传算法等元启发算法可搜寻到的解接近最优，在要求不太高的嵌入式系统设计中可接受。但由于整数线性规划需要大量的计算实现起来成本相当高，所以可以把关注点放在三种元启发算法的性能比较上。
表1 各算法仿真结果对比

IDEA(112个节点)
RC6(324个节点)
MARS(412个节点)
算法执行时间
ACO
40
750
2833
GA
26
492
1500
PSO
20
233
750
ILP
82
1500
5083
获得的最优解
ACO
4538
2880
4402
GA
4795
3368
4889
PSO
4299
2162
3949
ILP
4077
1453
3504
对于每个基准问题，由表1可知，作为衡量优化算法质量的重要标准之一，粒子群优化找到的解总是最接近整数线性规划的最优解，优于其它元启发算法。
由表1亦可知，对于每个基准问题，粒子群优化在累积运行方面均为最少，优于其它三种优化算法。
因此，对于软硬件划分问题，粒子群优化在元启发算法中的优势是很明显的。
5 结束语
针对NP难的软硬件划分问题，本文引入群智能技术，提出了一种基于粒子群优化的解决方案。将本文提出的算法的性能与整数线性规划、遗传算法及蚁群优化进行比较，其结果表明，基于ILP的方案产生最优的解，而粒子群优化算法能给出最接近最优解的结果。进一步分析指出，对于每个基准问题，基于粒子群优化的算法在执行时间方面优于遗传算法、蚁群优化和整数线性规划。
参考文献
[1] 孙天泽．嵌入式Linux操作系统[M]．北京：人民邮电出版社，2009．
[2] N N Binh, M Imai, A Shiomi, et al. A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts. Proceeding of the 33rd Design Automation Conference, Las Vegas, NV, USA, 3-7 June 1996[C].
[3] F Vahid, D Gajski. Clustering for improved system-level functional partitioning. Proceedings of the Eighth International Symposium on System Synthesis Cannes, France, 13-15 September 1995 [C].
[4] 高尚，杨静宇．群智能算法及其应用[M]．北京：中国水利水电出版社，2006．
[5] L Wolsey. Integer Programming[M], John Wiley & sons, 1998.

修改说明：

综合专家审稿意见及本人导师意见，我对此篇论文进行了修改。修改主要体现在以下方面：
（1）论文题目改为“粒子群优化在嵌入式系统软硬件划分中的应用”。
（2）纠正了第2页左右两列段落编排错误。
（3）“3.2基于粒子群优化的软硬件划分”修改了适应度函数，考虑了约束。
（4）修改了“累积代价”、“累积运行时间”等定义不清楚的概念，使用了更清晰的概念，如“算法执行时间”等。
（5）对PSO基本等式的参数设置、收敛情况等作了简要说明。
（6）根据导师意见进行了一些修改，如把原来的第2节“软硬件划分问题的形式化定义”改为第3节的第1小节，把原来的第3节第1小节“经典的粒子群优化算法”改为第2节，使各节长度更均匀，文章结构更紧密。
（7）应原第二作者本人要求，删去了原第二作者（赵俊逸）。并增加了现第四作者（彭博夫）。