基于扩展背包问题的的软硬件划分算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于扩展背包问题的的软硬件划分算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：软硬件划分问题常以时间为约束对硬件面积进行优化。随着嵌入式的发展，功耗这一因素也越来越重要，故在约束条件中加入了功耗的约束。贪婪算法是解决0-1背包问题的一种简单有效的方法，因此建立多约束的软硬件划分问题与0-1背包问题之间的联系，采用扩展的贪婪算法解决多性能指标的软硬件划分问题。利用仿真与动态规划方法的对比，进行了有效性验证。

关键词：软硬件划分； 0-1背包问题； 多约束； 贪婪算法

中图分类号： 文献标识码：A

文章编号：1004-373X(2011)20-0096-03

Hardware/Software Partitioning Algorithm Based on Extension Knapsack

YU Juan1, LI Xiao-qiang2

(1. School of Physics & Information Technology, Shaanxi Normal University, Xi’an 710062, China;

2. Xi’an University of Technology, Xi’an 710048, China)

Abstract： The hardware/software partitioning often takes time as the restraint to optimize hardware area. With the development of embedded technology, the factor of power consumption becomes more important. Therefore, the restraint to power consumption is added into the restraint condition. Since the greedy algorithm is an easy but effective method to solve the 0-1 knapsack problem, a relationship between the text multi-restraint hardware/software partitioning and 0-1 knapsack is established. The extended greedy algorithm is adopted to solve the problem of the hardware/software partitioning with many performance indexes. A effective verification was implemented with the method of the contrast between the simulation and dynamic planning results. The simulation reults show that the method can ruduce execution time and get good approximate solutions.

Keywords： hardware/software partitioning; 0-1 knapsack; multi-restraint; greedy algorithm

嵌入式系统是软件和硬件一体化的系统，系统中许多功能模块既可以由硬件来完成，也可以由软件来实现，当设计这样的软硬件混合系统时,将面临软硬件划分问题。软硬件划分的目的是决定哪些模块用硬件实现，哪些模块用软件实现，以满足约束使某一指标最优。一般而言，软件实现相对比较灵活和廉价，硬件实现可提高系统速度，但成本比较高。

常用的软硬件划分算法有面向硬件和面向软件的启发式方法。文献［1-3］是面向硬件的方法，其基本思想就是，最初系统的所有任务全部以硬件实现，然后逐步将系统中部分硬件实现的任务用软件实现方式来取代，以降低功耗和面积，经过反复的叠代替换，直到不能满足系统性能约束为止;文献［4-7］是面向软件的方法，其基本思想就是，系统最初所有的任务均以软件实现，然后将部分软件任务以硬件方式来替代，以改善系统的速度，直到能够满足系统的时间约束为止。

通常，软硬件划分是在一个约束条件下对某一性能进行优化，常见的是以时间为约束条件，对硬件面积进行优化。由于功耗这一因素也变得越来越重要，功耗过高导致芯片过热而破坏电路；另一方面，依赖电池供电的移动计算设备，其有效工作时间受电池电量的严格限制，因而降低设备功耗就意味着延长了设备的有效工作时间，后者对消费者的购买决定有很大影响。因此本文在约束条件中加入了功耗这一条件，以功耗和执行时间为约束条件，以最小化面积为目标进行优化。

贪婪算法是解决0-1背包问题\的一种简单有效的方法,因此本文建立软硬件划分与0-1背包问题的关系,使用基于扩展背包问题的贪婪算法解决多约束的软硬件划分问题。

1 目标架构

在实际的设计过程中可能出现多种目标架构，如单处理器结构、多处理器结构等，本文采用单处理器结构。所有的软件实现节点都可以映射到处理器上进行执行。所有的硬件实现节点都可以映射到硬件单元上进行执行。本文未考虑相邻节点间的通信代价。

2 软硬件划分

2.1 软硬件划分模型

软硬件划分过程中，系统由高级语言描述，输入由一系列的基本调度模块实现。所有的模块都转化为由节点和边组成的有向无环图（DAG），节点表示基本调度模块，边代表节点间的数据流动。划分算法决定哪些节点由硬件实现，哪些节点由软件实现。

图1 目标架构

每个基本调度模块（BSB）都能从它的父节点接收数据，并将数据传给它的后继节点。

根据划分算法的设计要求以及上述的基本假设，对于每一个BSB节点Bi结都进行了如下形式的参数化：Bi=БQai esi ehi psi phiR。各参数含义:ai表示Bi采用硬件实现时的面积开销；esi,psi为Bi用软件实现时的时间及功耗;ehi，phi为Bi用硬件实现所需要的时间及功耗。令ei=esi-ehi表示Bi用硬件实现相对用软件实现的时间节余;pi=psi-phi表示Bi用硬件实现相对用软件实现的功率节余。一般情况下，对于同一个调度块，用硬件实现时的功率损耗与执行时间都小于用软件实现的，所以设esi>ehi，psi>phi ，即ei>0,pi>0 。

因此软硬件划分问题的数学模型建立如下:

ИИmin∑ni=1aixi

s.t.∑ni=1［esi(1－xi)+ehixi］≤E

∑ni=1［psi(1－xi)+phixi］≤P

xi∈{0,1}（1） И

式中：xi表示当前节点的实现选择；xi=1表示硬件实现, xi=0表示软件实现；E为时间约束；P为功率约束。

2.2 基于扩展背包问题的软硬件划分算法

本文通过建立问题（1）与背包问题之间的联系，采用扩展的贪婪算法解决本文以时间和功耗为约束条件，以面积为优化目标的软硬件划分问题。因此需做以下变换，将式（1）整理变化为下式：

И

min∑ni=1aixi

s.t.∑ni=1［esi－eixi］≤E

∑ni=1［psi－pixi］≤P

xi∈{0,1}(2)И

令xi=1－yi,则:min∑ni=1aixi=min(∑ni=1ai－∑ni=1aiyi)=max∑ni=1aiyi ∑ni=1esi－eixi=∑ni=1eiyi+esi－ei=∑ni=1eiyi+ehi≤E，则∑ni = 1eiyi≤E-∑ni = 1e┆hi 。

设 E-∑ni = 1e┆hi = E′，则∑ni=1eiyi≤E′，同理：∑ni=1piyi≤P－∑ni=1phi；设P-∑ni = 1p┆hi = P′，则∑ni=1piyi≤P′。其中，作为合理的约束，应满足E-∑ni=1e┆hi = E′ > 0，P-∑ni=1p┆hi = P′ > 0。

因为前文已叙述过对于同一个节点，用硬件实现时的功率损耗与执行时间都小于用软件实现。如果所有节点都用硬件实现也无法满足约束条件的话，说明此约束设定不合理。

通过以上推导，式(2)可转化为式（3）:

ИИmax∑ni=1aiyi

s.t.∑ni=1eiyi≤E′

∑ni=1piyi≤P′

yi∈{0,1}(3)И

式中：yi=1表示软件实现；yi=0表示硬件实现。

对比式(3)所表示的软硬件划分问题与背包问题,发现二者相似,只是式(3)中约束条件为2个。因此可借鉴解决背包问题的贪婪思想来解决软硬件划分问题。

因此设c=QE′,P′R,wi=Qei,piR,г蚴(3)可变为:

ИИmax∑ni=1aiyi

s.t.∑ni=1wiyi≤c

yi∈{0,1}(4)И

式中：|wi|=e2i + p2i；记bi =ai/|wi|为节点i的优先度。

通过上述变换,软硬件划分模型已转化为标准的0-1背包问题模型,因此可对贪婪思想进行扩展，以解决本文的软硬件划分问题，算法伪代码如下：

(1) 按照各任务的优先度降序排列，设排列之后为：b1≥b2≥…≥bn－1≥bn

(2) 设eu=0,pu=0;

(3) For(i=1;i≤n;i++)

若(eu+ei≤E′）&&( pu+pi≤P′)

yi=1；eu+=ei；pu+=pi

否则yi=0;

(4) For(i=1;i≤n;i++)

xi=1-yi;

(5) 输出x。

2.3 动态规划方法

动态规划是解决多阶段决策过程最优化问题的一种方法。它首先将复杂的问题分解成相互关联的若干阶段，每一阶段都是一个最优化子问题，然后逐阶段进行决策，当所有阶段决策都决定了，整个问题的决策也就确定了\。因此本文以动态规划方法作为对比算法来检验本文算法的有效性。

用M［t］［e］［p］表示问题（3）在∑ti=1eiyi≤e,∑ti=1piyi≤p条件下对t个调度块进行决策后的max∑it=1atyt，因此问题的最终目标是求解M［n］［E′］［P′］。

动态规划方法的核心是确定状态转移方程，因此鉴于篇幅问题，只列出问题（4）的状态转移方程，如下：

若：

e［i］≥e&p［i］≥pM［i］［e］［p］=max{M［i－1］［e］［p］,M［i－1］［e－e［i］］［p－p［i］］+a［i］}

否则：

M［i］［e］［p］=M［i－1］［e］［p］

3 实 验

本文使用C语言在Core 2 1.83 GHz，2 GB RAM的计算机上进行仿真实验。由于本文着重于算法研究，故其中参数ai, esi,ehi,psi,phi，E，P在一定范围内随机产生，但满足以下条件：

esi>ehipsi>phi;

E-∑ni=1e┆hi = E′ > 0，P-∑ni=1p┆hi = P′ >0。

(1) 分别在不同节点数时采用本文的算法与产生最优解的动态规划算法在时间上进行对比：

实验结果为随机运行20次后的平均值，如表1所示。其中，N表示无法运行。由结果可以看出，在大于150个节点后，动态规划方法已不能运行。这是因为动态规划算法中需要用数组存储数据，而数组大小与节点数及约束大小有关，因此，随着节点数的增大，所产生的约束值也会加大，从而造成过大的内存需求而无法实现。动态规划算法的时间复杂度为Ο(nE′P′)，故随着节点的增多，运行时间急剧加大，因此动态规划算法不适合用于大规模问题。而本文算法的时间复杂度为Ο(nlg n)，因此运行时间比动态规划小。

(2)在同一节点数目下对本文算法与动态规划算法进行仿真，对解的有效性进行研究。设X*为动态规划算法产生的最优解；X为本文算法得到的解。有：

δ=aiX－aiX*aiX*×100%

使用误差［10］δ来表示本文算法解得优劣程度，由于动态规划算法产生的解为全局最优解，故δ越小，表示本文算法越接近全局最优解。在取节点数为50，100的情况下，对两种算法进行仿真，仿真结果如表2所示。

表2 算法精确度比较

节点数aiXaiX*δ

509349150.020

1002 9032 8430.021

通过仿真结果可以看到，本文算法相对动态规划得到的最优解误差分别为2.0%和2.1%。由此看出，误差较小，本文算法可获得较好的近似解。

4 结 语

现以硬件面积为优化目标，用时间及功耗作为约束条件，通过寻求与0-1背包问题之间的联系，对常用于解决背包问题的简单有效的贪婪算法进行扩展，解决了本文的多约束软硬件划分问题。通过仿真证明，本算法与动态规划算法相比，可以获得接近最优解的解，且速度较快，可用于解决大规模问题。

参考文献

［1］NIEMANN R, MARWEDEL P. Hardwre/software partitioning integer programming \//Proe.of IEEE/ACMEuropeanDesign Automation Conf.(EDAC). Washington DC, USA: Computer Society, 1996: 473-479.

［2］GUPTA R K, COELHO C, MIEHELI G D. Synthesis and sirnulation of digtal systems containing interaeting hardware and software components \// Proe.of 29th ACM/ IEEE Design Automation Conf. \: ACM, 1992: 225-230.

［3］GUPTA R K, MICHELI G D. System-level synthesis using re-programmable components \// Proc.of Third European Conf. Design Automation. Europe:.IEEE CS Press, 1992: 2-7.

［4］HARKIN J, MCGINNITY T M, MAGUIRE L P. Partitioning methodology for dynamieally reconfigurable embeddedsystems \. IEE Proeeedings of Computers and Digital Techniques, 2000, 147 (6): 391-396.

［5］VAHID F, GAJSKI D D, GONG J. Abinary-constraint seareh algorithm for minirmzing hardware during hardware/software parritionig \// Proe.of IEEE/ACM European Design Automation Conf.(EDAC). Europe: ACM, 1994: 214-219.

［6］ERNST R, HENKEL J, BENNER T. Hardware/software cosynthesis for microcontrollers \. IEEE design and test of computers, 1993, 10 (4): 64-75.

［7］VAHID F, GAJSKI D D. Clustering fori mproved system-level functional partitioning. Proe. of 8th IEEE/ACM Int. Synlp.Sysrem Synthesis. New York, NY, USA: ACM, 1995: 28-35.

［8］齐德昱.数据结构与算法\.北京：清华大学出版社，2003.

［9］郭科，陈耿，魏友华.最优化方法及其应用\.北京：高等教育出版社，2007.

［10］WU Ji-gang, SRIKANTHAN T, YAN Cheng-bin. Minimizing powerin hardware/software partitioning\// Proceedings of 2005 ACSAC. \: LNCS, 2005: 580-588.

作者简介: 余 娟 女，1980年出生，陕西咸阳人，在读博士研究生，助教。研究方向为软硬件协同设计。

李晓强 男，1980年出生，陕西渭南人，硕士，助教。研究方向为嵌入式系统设计。