维普资讯 http://www.cqvip.com 第28卷第9期 计算机应用 V01.28 No.9 2008年9月 Computer Applications Sep.2008 文章编号:1001—9081(2008)09—2427—03 嵌入式系统软硬件划分方法探索 袁爱平,傅明 (长沙理工大学计算机与通信工程学院,长沙410076) (yuan—ai_ping@21 cn com) 摘要:提出了克隆选择算法在软硬件划分中的应用,讨论了目标函数、系统约束、抗体编码、克隆选择和变异等 问题的处理。实验结果表明该算法具有较快的收敛速度,并获得了近似最优解。 关键词:嵌入式系统;软硬件协同设计;软硬件划分;克隆选择算法 中图分类号:TP302.7 文献标志码:A Research of the method of software/hardware partitioning in the embedded system YUAN Ai—ping,FU Ming f College of Computer and Communication Engineering,Changsha Univenity of Science&Technology,Changsha Hunan 410076,China) Abstract:The clonal selection algorithm in the application of software/hardware partitioning was described,and the problems of target function,system constraint,antibody coding,clonal selection and mutation were discussed.Experiment shows that this algorithm has faster convergence speed and yields solutions close to optical value. Key words:embedded system;software/hardware CO—design;software/hardware partitioning;clonal selection algorithm 0 引言 得很大;2)很难判定所得的解就是全局最优解。 软硬件划分是在系统设计阶段,根据设计约束和系统各 1 软硬件划分问题描述 部分的特点,确定各部分的软件或硬件实现方式,以获得高性 进行软硬件划分之前,设计者应该进行体系结构定义。具 能、低成本的优化设计方案。软硬件划分是嵌入式系统软硬 体的说,设计者要选择采用面向软件的实现方式还是面向硬件 件协同设计中的关键技术。传统的嵌入式系统的设计方法将 的实现方式,采用多处理器结构还是单处理器结构,处理器的 硬件和软件划分为两个的部分,由硬件工程师和软件工 类型,可采用的功能部件互联方式,存储器的组织形式等。 程师按照拟定的设计流程分别完成。这种设计方法只能改善 我们作出这样的假设: 硬件和软件各自的性能,而在有限的设计空间中不可能对整 1)设计的嵌入式系统中包含有一个固定的微处理器,微 个系统做出较好的性能综合优化。软硬件协同设计方法则强 处理器可以完成大部分系统功能,但是纯软件实现方式达不 调硬件设计师和软件设计师相互协作,并行地设计系统的硬 到系统的性能要求; 件和软件,并在设计的全过程中控制软硬件的一致性和系统 2)硬件实现方式的代价远高于软件方式; 的正确性。由于采用了统一的软硬件描述方法,协同设计方 3)硬件实现方式的性能远高于软件实现方式; 法可以在早期的系统设计阶段就能对系统设计的正确性进行 4)划分的目标是将系统功能在硬件功能部件和微处理器 验证,从而及时发现一些设计错误,减少传统方法在硬件和软 上进行分配,在满足性能约束的前提下,系统造价尽量降低。 件的实现阶段才能发现系统设计错误而导致重新设计系统的 本文采用的目标系统结构包括一个微处理器P,一个 工作量。 ASICH=}h。,h ,…,h },存储器和总线,系统的组件集合定 传统的软硬件划分是手工进行的,随着嵌入式系统结构 义为A=日I.J}尸}。其中,h。,h ,…,h 是ASIC中具有不同功 变的更加复杂,开发时间要求更紧迫,传统的方法已不再可 能的硬件电路,如图1所示。 行,日益需要系统层次的设计自动化工具,近年来自动划分算 ASIC 法研究得到重视。目前,在划分问题上采用的方法归纳起来 主要有:1)整型线性规划(Integer Linear Programming,ILP)/混 翠 …[ 合整型线性规划(Mixed Integer Linear Programming,MILP)法; 2)启发式算法,如模拟退火算法、遗传算法和禁忌搜索等;3) 其他方法,例如,基于簇的算法、动态规划法、PACE法、双向 图1系统结构 搜索、Kernighan/Lin算法和GCLP/IBS算法等。 在软硬件协同设计前先将应用系统分为一定粒度大小的 通过研究发现上述方法都试图捕获太多目标结构和划分 任务,然后用控制数据流图(CDFG)来描述系统: 问题的细节,存在两个方面的不足:1)可扩展性差,对于线性 G=} ,E},V=} , 一, } 规划法,随着任务节点数的增加,求得最优解的时间代价将变 E=}e0,e 一,e } 收稿日期:2008一O3—31;修回日期:2008—05—29。 基金项目:湖南省自然科学基金资助项目(O7JJ312O)。 作者简介:袁爱平(1975一),男,湖南邵阳人,硕士研究生,主要研究方向:嵌入式系统;傅明(1961一),男,湖南汩罗人,教授,博士,主要 研究方向:计算机网络、知识工程。 维普资讯 http://www.cqvip.com 2428 计算机应用 第28卷 控制数据流图是一个有向无环图,图的每个节点 表示 系统中的一个任务,可以用软件或者硬件实现,如图2所示。 图G有唯一的开始节点 和唯一的结束节点 , 是G中唯 行修正,使TE:0.95× ,这样,随着演化的进行,目标函数 对不满足约束的非可行解的惩罚越来越大,而对于可行解的 惩罚越来越小。 2.2克隆选择算法的实现 入度为0的节点, 是G中唯一出度为0的节点。边E表示 任务之间的控制关系或数据流向。一个从 。到 的通路P称 为系统的一次处理过程,P={ 。,e 一, },全体处理过程构 克隆选择算法模拟生物免疫系统的克隆选择原理,一般 将待优化的目标函数及其约束条件视为抗原,目标函数的优 成集合P。 给定实现方式集合 : M:{S,h。,·一,h } S表示通用微处理器 (软件程序通过控制和数据 总线和通用微处理器交互, 软件程序的执行时间主要由 处理器的执行时间决定,在 这里通用微处理器就是软件 程序实现的代称),h 代表硬 件电路。 图2控制数据流 定义面积函数A:A: 一 R 代表硬件电路的面积开销。总有A( ,)>0,而A(S)=0,表 示用软件实现不增加面积开销。 定义性能函数t:t:V× 一R ,系统性能由运行时间来衡 量。如果节点 用硬件电路hs来实现,h 运行这个任务需要的 时间是t( ,hs);如果节点 用软件程序实现,则S运行这个 任务需要的时间是t( ,S)。根据上面的假设,有t( ,hj)《 t( ,S),即硬件完成任务需要的时间远小于软件所需要的时 间。 为每个节点 分配实现方式 ∈M,求取解向量J:I= (mo,…,m )∈M 。 使得min∑A(m i=O ),即使硬件面积最小,并且满足约束 Vp,∑fvi P ( ,m )≤ , 为允许的系统总处理时间。 2基于克隆选择算法的软硬件划分 2.1 目标函数和约束条件 软硬件划分是一个约束极小化问题,对于约束优化问题, 划分算法常采用惩罚函数法,即在目标函数中加上一个反映 解是否位于约束集内的惩罚项,来构成一个广义目标函数,从 而使得算法在惩罚项的作用下找到问题的最优解。对约束极 小化问题,惩罚函数应对非可行解产生一个正的惩罚,而对可 行解则不产生惩罚或惩罚尽量小。 对于一个划分,=(m。,…,m ),用Cost(,)表示系统的 总代价,CostA(,)为系统的硬件面积开销,CostT(,)为系统的 运行时间,系统的约束条件定义为: CostT(,)≤T (1) 定义如下的目标函数: Costn,1 r minCost(,)=a×e——彳 一×l CostT(,)一Tl+ b×CostA(,) (2) 系统的总代价由系统的运行时间和硬件面积开销两部分 构成,参数a和b决定了两部分的比重,由于系统性能决定设 计是否可行,所以应保证a大于b。绝对值项是考虑到设计应 该恰好满足时间约束,而不是速度越快越好(速度快往往意 味着代价高)。 是控制惩罚项变化的退火温度参数,它随着 演化过程的进行逐渐变小,种群每经过一代演化后,对 进 化解视为抗体,其算法流程如图3所示。 图3克隆选择算法流程 1)抗体编码。在进行抗体编码前,首先对实现方式集合 中的元素编码,编码规则如表1。 表1 实现方式集合中的元素编码 实现方式 编码 S 0 h1 l h2 2 对于抗体,本文采用整数向量编码,整数向量B=(b。, b )表示系统的一种设计,同时也是算法操作的对象,其 中b 对应于数据控制流图中节点的实现方式(0≤b ≤实现 方式集合中元素的个数),n为任务流图的节点数。如对于向 量B={1,0,7,6,5},它对应的实现方式为h。,S,h ,h ,h 。 2)初始化种群。随机生成初始种群,种群的规模大小为 数据控制流图中节点个数Ⅳ的两倍。 3)计算亲和度。计算出种群中每个抗体的亲和度,也就 是目标函数的适应值。 4)选择和复制。从种群中选择抗体亲和度较高的Ⅳ个抗 体(即适应值较高的Ⅳ个抗体)进行复制。 5)变异。根据每个抗体的适应值,对复制后的Ⅳ个抗体 采用高斯变异,得到新的抗体。根据适应值的高斯变异,遵循 公式 = +aN(0,1),其中, 为变异后的抗体; 为变异前 的抗体;Ⅳ(0,1)是均值为0,方差为1的正态分布随机变量; 是个体的变异率,a=(1 )e 厂是每个抗体的亲和度,即目 标函数的适应值,口是一个参数,用来控制指数函数倒数的大 小。每个变量变异后应该仍处于它的定义域之内。抗体的变异 程度和亲和度成反比,亲和度越低(目标函数的适应值越 小),个体的变异率越高。这样个体在可行域上能朝着适应值 最好的点搜索。该算法没有固定个体的变异率,而是通过自适 维普资讯 http://www.cqvip.com 第9期 袁爱平等:嵌入式系统软硬件划分方法探索 2429 应的方式,寻找到最好解,提高了收敛速度。 取k=15,当N>150时,可取k= ̄N/IO], , 需要根据系 6)替换更新。在变异后的Ⅳ个新抗体中,选择d个亲和度 统的具体时间、代价参数确定。本文取 =0.5, =0.5。这 最高的抗体,替换种群中的d个亲和度最低的抗体,形成新一 种终止策略具有很强的自适应性,既可以避免迭代次数过多 代的抗体群。 而进行无用搜索,又可以防止迭代次数太少而达不到最优解。 7)终止条件。当种群中绝大多数个体所代表的解的代价 可以控制目标种群中个体之间的差异大小和算法的搜 和执行时间都基本相同时,则终止演化,否则转到步骤3)。具 索时间。 体是:进行完一代演化之后,随机选择k个个体对(S ,S ), (S:,S:+ ),…,(S ,S ),每个个体所代表的解的系统处理时 3算法结果与分析 间为time(Si),系统代价为cost(S ),演化的终止条件为: 为评价本文提出的算法性能,随机生成了20、50、100及 ∑I time(s )一time(sⅢ)I/k≤Xt (3) 200个节点的CDFG,并随机生成了各个节点的性能参数,同 且: 时根据对节点的性能参数的分析,确定了系统的约束条件。 对每个CDFG都进行100次的测试,并将系统总代价、处理时 ∑I c0st(S )一c0st(SⅢ)I/k≤ (4) 间及算法执行时间同模拟退火算法和普通遗传算法求出的值 其中,.i}, , 是设计时确定的常量参数,当Ⅳ≤150时,可以 进行了比较,实验数据如表2所示。 表2算法执行代价和处理时间的结果比较 根据实验结果可出如下结论: 与设计,2007,28(14):3426—3428, 1)我们的模型可以有效的指导软硬件划分; 【2】 李晖,姚放吾,邓新颖,等.基于免疫算法的嵌入式系统软硬件 2)三种算法都可以得到较优解; 划分方法【J】,计算机工程与设计,2006,27(22):4239—4242, 3)克隆选择算法较模拟退火算法和遗传算法收敛速度快。 【3】 吴泽俊,钱立进,梁意文,入侵检测系统中基于免疫的克隆选择 算法【J】,计算机工程,2004,30(6):50—52, 4 结1昔 【4】 周泉,章兢,基于克隆选择原理的免疫算法【J】.计算机工程与 本文提出了一种嵌入式系统的软硬件划分模型,此模型 应用,2005,41(21):61—63, 基于单处理器的体系结构。构造了划分的目标函数和系统约 【5】De CASTRO L N,Von ZUBEN F J.The clonal selection algorithm 束,在介绍克隆选择算法的基础上,通过实验比较了克隆选择 with engineering applications【C】//Workshop Proceedings of GEC— 算法、模拟退火算法和遗传算法在软硬件划分问题中的应用。 CO,Workshop on Artiifcila Immune Systems and Their Applica— 为了把注意力集中到系统的划分问题,本文中没有考虑不同 tions,0ralndo:IEEE Press.2000:36—37, 任务之间的通信开销及调度,在实际的应用中,可以综合考虑 【6】 KALAVADE A,SUBRAHMANYAM P A,Hardware/software parti— 这些因素而得到更为完善的划分。 tioning for multi-function systems【C】//Proceedings of the 1997 参考文献: IEEE/ACM International Conference on Computer-aided Design, 【l】 高健,李涛,三种软硬件划分算法的比较分析【J】.计算机工程 Washington,DC:IEEE Computer Society,1997:5 16—52 1. (上接第2426页) 【3】 JOOYONG S,CHANGHA H,SUNKYUN N,Robust LS—SVM re— 【8】LIU F C,WANG D S,Training algorithms for fuzzy support vector gression using fuzzy C-Means clustering【J】.Advances in Natural machines with noisy data【J】.Pattern recogniiton letters,2004 Computation,2006,4221:157—166. (25):1647—1656, 【4】 张英,苏宏业,褚健.基于模糊最小二乘支持向量机的软测量建 DAVID M J T,ROBERT P W D,Support vector machines【J】, 模【J】.控制与决策,2005,25(6):621—624, Pattern recognition letters,1999(20):1 191—1 199, 【5】LIN C F,WANG S D.Fuzzy support vector machines【J】,IEEE KERBEL U H—G,Pairwise classiifcation and support vector ma— Transactions on Neural Networks,2002,13(2):464—471. chines【M】.Advances in kernel methods:support vector learning. 【6】HUANG H P,LIU Y H.Fuzzy support vector machines for pattern Cambridge,MA:MIT Press,1999:255—268. recognition and data mining【J】.International Journal of Fuzzy Sys— HYUN W C.Nonlinear feature extraction and elassiifcation of mulit. tems,2002,4(3):826—835. variate data in kernel feature space【J】.Expert System With Appli— 【7】LAUER F,BLOCH G.Incorporating prior knowledge in support cation,2007,32(2):534—542. vector machines for classiifcation:A review【J】.Neurocomputing, 许亮.基于核函数和知识的化工过程安全运行智能支持系统研 2008,71(7/9):1578—1594. 究【D】.广州:华南理工大学,2007.