遗传算法在软硬件划分中的应用！

《遗传算法在软硬件划分中的应用！》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、国防科技大学学报第24卷第2期JOURNALOFNATIONALUNIVERSITYOFDEFENSETECHNOLOGYVoI.24No.22002文章编号：1001-2486（2002）02-0064-05!遗传算法在软硬件划分中的应用刘功杰，张鲁峰，李思昆（国防科技大学计算机学院，湖南长沙410073）摘要：软硬件划分是软硬协同设计中的一个关键问题。针对单处理器嵌入式系统，给出了基于遗传算法的解决方案，并引入了模拟退火和按概率选择两种技术。结果表明，算法有效地解决了软硬件划分问题，稳定性好、效率高，模拟退火和按概率选择的引入，进一步提高了算法效率，保证了算法的自适应性及结果的

2、全局最优性。关键词：遗传算法；软硬件划分；软硬协同设计中图分类号：TP302文献标识码：AResearchontheUseofGeneticAlgorithminHW-SWPartitionLIUGong-jie，ZHANGLu-feng，LISi-kun（CoIIegeofComputer，NationaIUniv.ofDefenseTechnoIogy，Changsha410073，China）Abstract：Hardware-softwarepartitioningisakeyprobIeminHardware-softwareco-designofembeddedsyst

3、em.Thispaperde-scribesanapproachbasedongeneticaIgorithm.Twomethods，simuIatedanneaIingandseIectinganindividuaIinIightoftheprobabiIity，areusedtoenhancetheaIgorithmsseIf-adaptabiIity，efficiencyandgIobaIoptimization.ItisvaIidatedviathepartitioningresuItsthattheapproachisstabIe，effectiveandefficien

4、t.Keywords：geneticaIgorithm；hardware-softwarepartition；hardware-softwareco-design嵌入式系统一般有软件和硬件两种基本实现方式，同硬件相比，软件容易修改、成本较低，而硬件可以提供更高的性能。软硬件划分问题，就是在嵌入式系统的高层次设计阶段，根据设计约束及系统各个部分的特点，确定各部分的软件或者硬件实现方式，以获得高性能、低成本的优化设计方案。软硬件划分是嵌入式系统的软硬协同设计中的一个关键问题。常用于软硬件划分的算法有整数规划［1］、混合线性规划［7］、启发式算法［6］等。对于规划类算法，难以给出明确的目

5、标函数，约束条件太多，不易使用，而且当目标系统的结点很多时，算法的计算时间会很长。启发式算法对启发式规则的要求很高，结果很容易受其影响。这几种算法还有一个共同的弊端：容易陷入局部最优。1软硬件划分模型一个系统使用任务流图（taskgraph）（参见图1）来描述，任务流图是有向无环图，只有一个起始节点和一个终止节点，两个节点之间最多只有一条边。图中的一个节点表示系统的一个任务，边表示任务之间的控制关系或数据流向，每条边的终点任务必须在此边的始点任务完成之后才可以开始执行。每个节点包含其软件、硬件代价信息，边的权重代表两个节点之间的通讯开销。任务流图是系统的行为级描述，主要描述系统中任

6、务间的控制、数据关系及每个任务的代价信息，而与系统实现时采用什么样的体系结构无关。图1任务流图定义1目标系统的体系结构［1］：包括一个处理器!，一个ASIC"=｛#，⋯，1Fig.1Taskgraph!收稿日期：2001-10-09基本项目：国家863计划资助项目（863-SOC-Y-3-2-1）作者简介：刘功杰（1977—），男，硕士生。65hI｝，存储器和总线，目标系统的组件集合定义为A=H!｛P｝。其中，hI，⋯，hI是ASIC中具有不同功能的硬件电路，参见图2。定义!一个系统定义为一个三元组S=｛V，R，M｝：V=｛1I，⋯，1N｝是系统中的节点集合，N为系统的节点总数；R

7、=｛rI，⋯，rN｝，ri"A=H!｛P｝代表节点i的实现方式集合，P表示用软件实现，hi表示用硬件i实现；二维矩图2目标系统结构简图阵M"VXV代表节点之间的连接关系。Fig.2ThearchitectureOfthetargetSyStem节点i应该包含以下信息：用方式I（0#I