（计算机应用技术专业论文）基于遗传和禁忌搜索混合的soc软硬件划分方法研究.pdf

哈尔滨理工大学工学硕士学位论文 基于遗传和禁忌搜索混合的s o o 软硬件 划分方法研究 摘要 微电子工艺的快速发展促使集成电路进入s o c 时代，但是随着设计复杂 度的提高，传统的设计方法已经无法满足片上系统设计的需要。因此软硬件 协同设计方法学应运而生，而软硬件划分技术又是软硬件协同设计技术中的 关键技术之一。因此，研究s o c 设计中的软硬件划分方法，构建一种合理的 系统描述模型，提出划分算法并对其进行优化改进，将有十分重要的理论及 应用价值。 本文介绍了软硬件协同设计的研究领域以及国内外的发展现状，重点研 究了在解决软硬件划分问题所使采用的数学模型，同时分析了目前划分技术 中普遍存在的问题。比较遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和禁忌搜索 ( t a b us e a r c h ，t s ) 各自优缺点的基础上，面向嵌入式系统和s o c 软硬件双 路划分问题，本文创新性地提出了提出遗传禁忌搜索混合算法( g e n e t i c a l g o r i t h ma n dt a b us e a r c h ，g a t s ) 的策略，采用免费任务图( t a s kg r a p h f o rf r e e ，t g f f ) 工具生成的有向无环图作为软硬件双路划分的数学模型， 用g a 提供并行搜索的主框架，t s 作为g a 的变异算子，g a 中变异过程解空 间的搜索由t s 实现。 最后，将g a 、t s 算法与g a t s 算法分别使用由t g f f 工具生成的真实 数据进行编程，对比验证，验证结果表明g a t s 算法能够克服g a 爬山能力 差、t s 单点出发的弱点，从而得到更优秀，精度更高的划分结果。 关键词片上系统设计；软硬件划分；遗传算法；禁忌搜索；变异算子 哈尔滨理工人学丁学硕上学位论文 r e s e a r c ho fs o ch a r d w a r e s o f t w a r ep a r t i t i o n i n g m e t h o d o l o g yb a s e d o ng e n e t i ca l g o r i t h ma n d t a b us e a r c h a b s t r a c t i n t e g r a t e d c i r c u i te n t e r si n t ot h ee r ao fs y s t e mo nc h i p ( s o c ) a st h e d e v e l o p m e n to fm i c r o e l e c t r o n i ct e c h n i q u e s ，h o w e v e r , a st h ed e s i g nc o m p l e x i t y i n c r e a s e s ，t r a d i t i o n a ld e s i g nm e t h o d o l o g yi su n a b l et os a t i s f yt h en e e d so fs y s t e m o n c h i p ，h a r d w a r e s o f t w a r ec o - d e s i g nm e t h o d o l o g ym e r g e s a sn e e d e d h a r d w a r e s o f t w a r e p a r t i t i o n i n g i s o n eo f t h ec r i t i c a l t e c h n i q u e s i n s o f t w a r e h a r d w a r ec o d e s i g n s t u d y i n go nt h eh a r d w a r e s o f t w a r ep a r t i t i o n i n g m e t h o d o l o g y , b u i l d i n gar e a s o n a b l es y s t e md e s c r i p t i o nm o d e l ，p r o p o s i n ga n d i m p r o v i n g ap a r t i t i o n i n ga l g o r i t h mp o s s e s sd r a m a t i c a l l yi m p o r t a n tv a l u ei n t h e o r ya n di na p p l i c a t i o n t h i sd i s s e r t a t i o ng e n e r a l i z e st h ed o m e s t i ca n da b r o a dd e v e l o p i n gs i t u a t i o n i nt h er e s e a r c hf i e l do f h a r d w a r e s o f t w a r ec o - d e s i g n ，e m p h a s i z e s o nt h e m a t h e m a t i c a lm o d e lc o n s t r u c t e di nt h ep r o c e s so fs o l v i n gh a r d w a r e s o f t w a r e p a r t i t i o n i n gp r o b l e ma n da l s oa n a l y z e st h ep r o b l e m sc o m m o n l y e x i s t e di nc u r r e n t p a r t i t i o n i n gt e c h n o l o g y a f t e r t h e c o m p a r i s o n o ft h ep r o p e r t i e so fg e n e t i c a l g o r i t h m ( g a ) a n dt a b us e a r c h ( t s ) ，o r i e n t e dh a r d w a r e s o f t w a r ep a r t i t i o n i n g p r o b l e mi ne m b e d d e ds y s t e ma n ds o c ，ah y b r i da l g o r i t h mi si n n o v a t i v e l yp u t s f o r w a r db a s e do ng e n e t i ca l g o r i t h ma n dt a b us e a r c h ，n a m e l yg a t s ，w h e r et h e m a i nf r a m eo ft h ea l g o r i t h mi sp r o v i d e db yg e n e t i ca l g o r i t h ma n dt a b us e a r c hi s t a k e na st h em u t a t i o no p e r a t o r ，s o l u t i o ns p a c es e a r c hi sa c c o m p l i s h e db yt si n t h ep r o c e s so fm u t a t i o n d i r e c t e da c y c l i cg r a p hp r o d u c e db yt g f fa r eu s e di n h a r d w a r e s o f t w a r eb i p a r t i t i o n i n ga st h em a t h e m a t i c a lm o d e l a tt h ee n do ft h i sd i s s e r t a t i o n ，g a ，t sa n dg a t sa r er e s p e c t i v e l y p r o g r a m m e da n dv e r i f i e du s i n gt h e r e a ld a t ag e n e r a t e db yt g f ft 0 0 1 t h e v e r i f i c a t i o nr e s u l t ss h o wt h a tg a t si sa b l et oo v e r c o m et h ep o o rm o u n t a i n i i 哈尔滨理t 大学t 学硕仁学位论文 c l i m b i n ga b i l i t yo fg aa n dt h ew e a ks i n g l es t a r t i n g p o i n tc a p a c i t yo ft s ，w h i c h g i v ea b e t t e ra n dm o r ea c c u r a t ep a r t i t i o n i n gr e s u l t k e y w o r d ss y s t e m o n c h i pd e s i g n ，h a r d w a r e s o f t w a r ep a r t i t i o n i n g ，g e n e t i c a l g o r i t h m ，t a b us e a r c h ，m u t a t i o no p e r a t o r i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于遗传和禁忌搜索混合的 s o c 软硬件划分方法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士 学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分 外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和 集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者答名：乃私醐：2 垆弘渊 哈尔滨理工大学硕士学位论文使用授权书 基于遗传和禁忌搜索混合的s o c 软硬件划分方法研究系本人在哈尔滨 理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究 成果归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。 本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留 并向有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨 理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部 或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密。 ( 请在以上相应方框内打) 作者签名： 乃稳s 刷磴各i 季壤一昀 ， 日期：。护矽年? 月2 勺日 日期：庐。口7 年弓月幻同 哈尔滨理t 大学t 学顾士学位论文 第1 章绪论 1 1课题研究背景及意义 嵌入式系统是用于完成特定功能的计算机系统，它一般由软件和硬件混合 构成。随着嵌入式系统复杂度的提高，其设计的难度也越来越大，传统的设计 方法已经不能满足需要了n 1 。软硬件协同设计是一种新的设计方法，它协调软 硬件开发过程并行展开，一方面可以缩短设计周期，极大地提高设计效率；另 一方面可以根据系统各个部分的特点和设计约束选择软件或硬件实现方式，得 到高性能、低成本的优化设计方案。 在传统的嵌入式系统设计过程中，系统的设计将软件和硬件分开进行，即 先进行硬件的规划和设计，再进行软件的设计，最后进行验证和仿真，而硬件 设计是一个容易出错的过程，当硬件设计完成后进行验证和仿真时如果出错， 一方面由于软硬件之间的相互作用，很难简单地判断出是软件上的还是硬件上 的错误，另外如果是硬件错误则将不得不重新回到硬件设计上来，进行大量的 修改甚至重新设计，其设计成败很大程度上取决于设计者的经验，而且存在着 开发周期长、开发成本高、设计效果优化困难，甚至不能满足苛刻的设计要求 的事实。对于技术发展迅速的今天，这种反复是无法忍受的。针对这种情况， 提出了软、硬件统一的设计方法：软硬件协同设计( h a r d w a r e s o f t w a r ec o d e s i g n ) 或者协同设计( c o d e s i g n ) 幢3 1 。 所谓的软硬件协同设计方法，是一个从高层抽象建模到低层硬件建模的过 程，就是用自动、优化的系统体系结构开发替代人工的软硬件子系统分割d 1 ， 在系统设计的高层阶段同时考虑软、硬件，实现系统原型的快速开发并预估系 统实现的性能，实现系统在性能、成本等方面的最优化h 1 。此方法强调在设计 的最初阶段就将软件与硬件两方面结合起来，从整体上权衡功能的分配，从设 计任务出发，通过有效分析系统任务和资源需求，最大限度地挖掘系统软硬件 的潜能，协同设计软硬件体系结构，并在设计的全过程控制软硬件的一致性和 系统的正确性，以使系统能够工作在最佳状态喳1 。 s o c 系统芯片作为嵌入式系统的一种新形式，是2 1 世纪集成电路发展的必 然趋势，s o c 系统将原来由许多芯片完成的功能，集中到一块芯片中完成，实 现了能够完成一个计算机系统功能所需的硬件集成电路和嵌入式软件。但 哈尔演理t 人学t 学硕f j 学位论文 s o c 不是各个芯片功能的简单叠加，而是从整个系统的功能和性能出发，用软 硬结合的设计和验证方法，利用i p 复用及深亚微米技术，在一个芯片上实现复 杂的功能。软硬件协同设计技术以其集成度高、可靠性好、产品问世周期短等 特点逐步成为当前嵌入式系统设计技术的主流盯1 。s o c 芯片设计结合了i c 设计 和嵌入式软件开发两方面的内容，不但是国家软件产业和集成电路产业支持的 重点，而且是学术界的研究热点和业界大力推广应用的一项新技术。因此，研 究软硬件协同技术具有非常大的实际意义。 1 2 软硬件协同设计研究领域 软硬件协同设计是当前一个活跃的研究领域。软硬件协同设计问题睛1 从软 件和硬件设计工作紧密耦合的需要中演化而来的。由于上市时间缩短和系统复 杂性增加，使得芯片设计必须向系统集成化转移，这对协同设计技术的发展起 了很大的推动作用。初始协同设计概念现在已经包括很多研究领域如建模、分 析和估计，系统层划分，实现生成，协同仿真和模拟，可重配置计算平台归1 。 软硬件协同设计的一般流程如图1 - 1 n 0 1 所示。 软硬件协同设计中主要有五个要解决的任务： 1 系统描述：包括功能和非功能性的需求； 2 形式化转移和优化系统说明，使之成为中间格瓦； 3 把系统划分成软件和硬件模块； 4 系统综合：包括硬件综合、软件代码生成和接口生成； 5 对系统的功能和限制进行协同模拟和仿真。 1 2 1系统任务描述 设计一个s o c 系统，首先要明确系统需求，即系统的性能和所要实现的功 能，然后对系统进行建模。系统的模型主要有有限状态机模型、数据流图模 型、任务流图模型、离散事件模型、耐网模型等，各种模型的建立方法在后文 给出了详细说明n 0 1 。 系统任务描述方法解决系统的统一描述。这种描述应当是对软硬件通用 的，目前一般采用系统描述语言的方式。在软硬件划分后，能编译并映射成为 硬件描述语言和软件实现语言，为目标系统的软硬件协同工作提供强有力的保 证。 哈尔滨理丁人学t 学硕卜学位论文 图1 1 软硬件协同设计流程图 f i g 1 - 1h w s wc o - d e s i g nf l o wc h a r t 1 2 2软硬件划分 软硬件划分是指在设计系统时确定各个模块是采取软件还是硬件的实现方 式，应解决节点的映射方式问题，使系统在满足约束的条件下性能最优。它是 软硬件协同设计中的一个关键内容1 ，划分结果的好坏直接影响着系统的性 能。这也是本论文研究的主要内容。 常见的软硬件协同划分算法有遗传算法、禁忌搜索算法等，后文将详细介 绍这两种算法。 1 2 3软硬件并行综合 软硬件详细设计完成划分后，进行软件和硬件的设计实现。硬件综合是在 厂家综合库的支持下，完成行为级、r t l ( r e a lt i m el e v e l ) 以及逻辑级的综 哈尔滨理t 人学t 学硕 = 学位论文 合。代码优化完成对设计实现后的系统进行优化，主要是与处理器相关的优化 和与处理器无关的优化。与处理器相关的优化受不同的处理器类型影响很大， 一般根据处理器进行代码选择、主要是指令的选择和指令的调度( 并行、流水 线) 等、寄存器的分配策略等与处理器无关的优化主要有常量优化、变量优化 和代换、表达式优化、消除无用变量、控制流优化和循环内优化等引。 软硬件协同综合是从软硬件统一的行为描述开始，构造包含软件和硬件的 实现结构描述的设计转换过程。软硬件协同综合过程包括三个设计步骤： 1 处理单元分配决定嵌入式系统由哪些处理器、数字信号处理器 ( d a t as i g n a lp r o c e s s o r ，d s p ) 及专用硬件等体系结构级别的单元组成； 2 软硬件划分决定系统中哪些功能由硬件处理单元实现，哪些由处理 器用软件实现，也称任务指派； 3 任务调度决定分派在各个处理单元上任务的执行顺序和开始时间。 1 2 4软硬件协同模拟和仿真 系统层的软硬件协同仿真为设计者提供关于软硬件划分、选择和调度等设 计选择方面的反馈。模拟软硬件之间的互操作，要求协同仿真工具要足够快， 允许重要的嵌入式系统的功能性端口在一定合理的时间内得到实现n 副。 在协同仿真中，硬件可以用c c + + 建模，整个系统可以像单个c c + + 程序 一样执行。但是，这不是实现级别的系统验证，而是行为确认。验证需要用 h d i r t i ，描述，因为它代表着硬件的实现。协同仿真需要一个或多个h d l ( h i g hd e s c r i p t i o nl a n g u a g e ) 仿真器和一个c c + + 平台( 编译器、装入程序、 链接器和计算机操作系统到其他部分) 。在协同仿真中，包括h d l 仿真器和软 件仿真器在内的两个或多个仿真器互相链接，所以，不同仿真器间的通信是一 个关键。 1 3软硬件协同设计的国内外研究现状 1 3 1国外研究现状 国外有很多软硬件协同设计系统，开始的时候所有的任务节点都由硬件实 现，然后将对实时性要求不强的部件转移到由软件实现。软硬件划分在整个设 计过程中起到了非常重要的作用，划分的结果直接关系到系统开销和性能，因 哈尔滨理丁人学r 学硕l j 学位论文 此在软硬件协同设计的整个流程，国内外的文献大都着眼于软硬件划分。1 9 9 2 年，针对嵌入式实时系统，g u p t a 和d em i c h e l i 提出了在协处理器和通用 处理器上进行软硬件划分的迭代算法1 。同年，h e n k e l 和e r n s t 等以模拟 退火算法为基础提出了另一种划分方法，提出了一种面向软件的软硬件划分方 法，它首先将构成系统的所有顶点映射至软件，然后将顶点的映射逐一移至硬 件直至满足实时性约束，但这种方法一般需要很长的运行时间，并且划分质量 依赖于使用的冷却调度。c o s y m a 划分方法也主要是面向软件，目的是计算 优化的软硬件划分以通过协处理器获得最大的加速比。在c o s y m a 中，它允 许定义并发和时间约束，软硬件划分也由基于使用估计调度时间的模拟退火算 法自动实现。c o s y m a 主要的缺点是处理器和协处理器不能并行工作纠。 1 9 9 4 年，a m b r o s i o 和h u 提出了一种通过抽象估计可被调度系统结构的概 率来实现软硬件划分的算法n 引。文献n 提出了基于软硬件划分的动态规划方 法。1 9 9 5 年，k a l a v a d e 等讨论了一种将任务映射至软件和硬件的改进型表 调度算法，它利用自适应g c l p ( g l o b a lc r i t i c a l i t yl o c a lp h a s e ) 探试搜索来最 小化目标系统的执行时间或芯片面积，该算法能够自适应地根据优化规则对相 应的面积和时间的权重进行调整n 引。w u 等人将搜索空间平滑技术应用于求解 软硬件划分问题，提高了划分算法求解质量n 9 1 。1 9 9 7 年，e l e s 等提出采用模 拟退火算法和禁忌搜索算法来实现软硬件划分，描述了一种条件任务图模型， 使用表调度算法为实现结构中每个处理单元形成调度表，并以此为基础进行软 硬件实现选择，实验证明禁忌搜索算法更适合软硬件划分堙叭。v a h i d 等扩展 了k l 启发式算法眩，实验证明此算法在执行时间上与模拟退火算法相比，具 有更短的执行时间。1 9 9 8 年，d i c k 和j h a 设计了用多目标遗传算法划分并 调度嵌入式系统的任务图，尽力获得多个被优化目标之间的最佳折衷，功耗只 是诸多优化目标中的一个位引。1 9 9 9 年，h e n k e l 介绍了基于i p 核的嵌入式系 统低功耗软硬件划分算法，其核心思想是减少系统的空闲时间以降低功耗他劓。 2 0 0 0 年，c h a t h a 和v e m u r i 提出了采用改进迭代算法对任务图在单个协处 理器和通用处理器进行划分。2 0 0 2 年，t h e e r a y o dw i a n g t o n g 等人比较 分析了在软硬件协同设计上的三种启发式算法，实验证明禁忌搜索在软硬件划 分上优于遗传算法和模拟退火算法心引。2 0 0 5 年，d a n gv a nh u n g 等提出了 一种针对于同步模型的软硬件划分的最优方法幢引。m i c h a l i sdg a l a n i s 等 人在2 0 0 6 年提出了一种对于混合可重配置体系结构的划分方法2 6 1 。同年， m i c h a l i sdg a i a n i s 等人又提出了对于不同种类的可重配置功能单元的划 分方法川。郭兵等人幢8 l 提出了一种基于h o p f i e l d 神经网络的片上系统实时操作 哈尔滨理t 人学t 学硕i j 学位论文 系统( s y s t e mo nc h i p r e a lt i m eo p e r a t i n gs y s t e m ，s o c r t o s ) 软硬件划分方 法，在硬件面积约束条件下优化s o c r t o s 的运行时间，明显地提高了多任务 s o c r t o s 的运行性能。通过上述材料可知，国外在嵌入式系统软硬件划分方 法的研究上开展得比较早，针对嵌入式系统不同的体系结构及划分粒度均有研 究，其特点是在不同时期的研究重点及方法不同，在研究方法中能够融入当时 的新算法，新思想，扩展了研究思路及领域。 1 3 2国内研究现状 在国内，s o c 软硬件划分方法学的研究还处于起步阶段。当前许多的基于 s o c 平台的软硬件划分技术多数采用了单处理器结构，所有的软件实现节点都 映射到处理器上执行，所有的硬件实现节点都映射到硬件单元上执行，嵌入式 处理器和硬件单元通过共享存储器或者专用通道通信。在软硬件划分算法上， 研究者们做了更多的尝试，在改进搜索划分解空间算法上，研究并应用了各具 特色的划分算法。其中，应用效果较好的典型算法是：模拟退火算法，禁忌搜 索算法，演化算法，蚂蚁算法，迭代移动，迭代改进，动态粒度模拟退火，动 态规划，遗传算法，线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ，i l p ) ，贪婪迭代 改进算法等。对于s o c 所应用的不同场合及不同的划分粒度，又有基于关键路 径的，在资源争用条件下的，基于性能受限的m 1 ，针对单c p u 单a s i c 结构 的；完成不同的目标，如在时间或面积限制条件下，最小化执行时间，优化性 能或做到功耗最省。其中爬山法有很强的局部搜索能力，当更优解处在当前解 附近时，算法能继续朝更优解前进，但因此也易陷入局部最优；遗传算法从 生物进化和遗传的过程中得到启示，模拟这一自然行为，是一种全局优化算 法，但其后期收敛速度非常缓慢，解大规模问题的能力有限；蚂蚁算法恤1 模拟 蚂蚁搜寻蚁巢到食物之间的最短路径的过程，具有很高的并行性和全局搜索能 力，比较适合于解决复杂问题，但其搜索初期，由于信息素缺乏而使搜索时间 大幅增加且初始群体是通过用随机的方法来产生的，盲目性比较高；熊志辉等 人将蚂蚁算法与遗传算法动态融合用来解决软硬件划分问题，但是这两种算法 的动态融合时机很难确定，而且不同的控制参数对算法性能影响很大；禁忌搜 索法采取类似人类思考问题的过程的方法，使用一定的禁忌准则来避免迂回搜 索，但由于需要保存及判断大量的禁忌数据，影响了算法的搜索速度；模拟退 火算法模拟固体退火的过程，找到物质能量最低状态，通过引入接受准则，模 拟退火算法能避免陷入局部最小，但问题规模较大时，系统进入热平衡状态 哈尔滨理t 人学f t 学硕卜学化论文 ( 即找到最优解) 的时间较长，这些算法适用于不同的结构和不同的代价函 数。文献旧鲫中基于整数规划的软硬件划分模型已经考虑了多处理器的情况，但 其基本估算参数还是基于双路划分的，硬件实现中也未考虑到不同i p 核的情 况。经典遗传算法m 1 求解图的划分优化问题时，其求解时间较长，求得最优解 的成功率很低。因而，有必要针对该类具体应用问题的特点，对经典的遗传算 法加以改进。很多研究者更是基于这些算法针对各类应用作了改进。有将k 均 值聚类和模拟退火相融合的算法汹1 ，有加初始信息素的蚂蚁算法汹，有改进的 模拟退火算法 ，有遗传算法和蚂蚁算法动态融合的算法旧1 ，有基于量子遗传 算法的嵌入式系统软硬件划分算法旧1 ，有的引入了混沌优化算法叫。采用启发 式分支定界的软硬件划分，提出了一种以任务图为描述方法的软硬件划分方 法，首先分别计算芯片所需面积时间通信软硬件倾向度，并结合各节点的比 重因子获得启发参数，然后采用启发式的分支定界法对系统进行划分，实验数 据证明此算法适用于划分粒度较粗和中小规模的系统h 。而郭兵等人研究的基 于离散h o p f i e l d 神经网络的r t o s 功耗优化算法，引入了r t o s p o w e r 划分问题 的一个新模型，然后提出了一种基于离散h o p f i e l d 神经网络的r t o s p o w e r 划分 方法，重新定义了神经网络的神经元表示、能量函数、运行方程和系数。实验 表明该算法能够以较小的代价获得高达6 0 的功耗节省m 1 ，比较适合于对功耗 要求严格的嵌入式应用。马天义等人提出的面向多处理器s o c 设计的低功耗软 硬件划分采用了基于神经网络的禁忌搜索算法，针对多个软件子集( 如多个通 用的微处理器) 和多个硬件子集( 如多个专用集成电路( a p p l i c a t i o ns p e c i f i c i n t e g r a t e dc i r c u i t ，a s i c ) 或现场可编程门阵列( f i e l d p r o g r a m m a b l eg a t e a r r a y ，f p g a ) ) 的进行的多路划分，与传统的双路划分不同h 引。除此以外， 人们将新近比较热门的算法也应用到了s o c 软硬件划分算法当中来，为软硬件 协同设计增加了更多的划分方法。 1 3 3研究不足 可以看出，当前软硬件划分问题方法的研究趋势，是使用经典搜索算法与 现代智能优化算法相结合的方式求解；使用这些方法求出的一般不是最优解， 但是常常能满足实际的需求。尽管研究的成果颇丰，但是在各种具体情况的应 用中，软硬件划分问题具有以下一些共同难点h 引。 1 没有确定的多项式时间算法，它在计算理论上属于n t ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 完全问题| 4 引。 哈尔滨理t 大学t 学硕 ：学位论文 2 很难设计出有效的启发算法，即使用上各种高级的启发式搜索技术， 进行高效的状态空间剪枝，仍无法保证找到最优解。 3 不存在通用算法，适用于某些情况的算法的方法可能不适用于其他情 况，特定的条件往往只适用于特定的实例。 4 现实应用中的软硬件划分问题常常需要考虑许多约束条件，如功耗限 制，硬件面积约束，成本，性能指标等，如何兼顾系统的速度和成本，如何达 到成本和性能的最佳结合是研究的难点。 5 划分所基于的粒度大小难以确定。粒度太粗，算法简单，但结果不 好；粒度太细，探索解空间太大，很难找到优化解。 1 4课题的来源及研究内容 1 4 1课题来源 本课题全名为“基于遗传和禁忌搜索混合的s o c 软硬件划分方法研究 ， 它是通过分析了嵌入式系统的发展需要和软硬件协同设计的过程及s o c 设计的 必然趋势之后，自拟的此课题。 1 4 2课题的主要研究内容 本课题在学习和掌握s o c 软硬件划分思想的基础上，根据国内外对嵌入式 系统软硬件划分的研究情况，考虑到嵌入式系统的发展趋势和人们需求的增 加，本论文研究的主要内容包括以下几个方面。 1 理论准备翻查资料，对软硬件协同设计研究领域和已有的软硬件划 分算法进行研究，分析各自的应用领域及优缺点，为自己的研究做好理论准 备。 2 模型抽象及研究针对嵌入式系统软硬件协同设计中的软硬件划分问 题，提出一个基于基本调度块图的软硬件双路划分模型，考虑可以抽象出一个 模型来表示嵌入式系统的构成情况，进而能够从理论上更好、更方便地对s o c 软硬件划分方法进行研究。 3 找出研究切入点软硬件划分问题本质上是一类组合优化问题，问题 模型和求解算法选择是解决软硬件划分问题的关键，同时划分模型中必须考虑 数据通讯的影响。本文使用基于有向无环图的软硬件划分模型，针对软硬件划 哈尔滨理t 人学t 学硕十学位论文 分性能要求严格系统，提出基于遗传和禁忌搜索混合的软硬件划分算法。 4 提出实现算法在研究了国内外软硬件划分研究现状的基础上，比较 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和禁忌搜索( t a b us e a r c h ，t s ) 各自优缺 点，面向嵌入式系统和s o c 软硬件双路划分问题，本文提出采用遗传禁忌搜索 混合算法( g e n e t i ca l g o r i t h ma n dt a b us e a r c h ，g a t s ) 的策略，用g a 提供并 行搜索的主框架，t s 作为g a 的变异算子，g a 中变异过程解空间的搜索由t s 实 现。 5 验证和总结由于目前已有文献分别使用g a 和t s 算法作为软硬件划分 算法，因此本文将g a 、t s 和本文设计的g a t s 分别编程对比运行，验证本文提 出算法的有效性。并对软硬件协同设计的趋势和有待进一步研究的问题和后续 工作进行展望。 哈：j ：演理丁大学t 学顾- i 学位论文 2 1概述 第2 章软硬件划分的相关理论 软硬件划分是嵌入式系统和s o c 软硬件协同设计的关键步骤，其基本任务 是：在满足某些约束的条件下，将系统功能行为“最优地”分配到一定的软硬 件系统结构上。 2 1 1系统结构 软硬件划分的任务是确定系统的结构，即根据系统功能和非功能描述进行 软硬件的划分与优化，即软硬件划分技术。软硬件划分决定了系统的哪些部分 用软件算法实现，哪些部分用硬件a s i c 或f p g a 实现。软硬件划分的主要目 标是使系统满足速度，延迟，成本等非功能方面的要求，获得正确完整的功能 和较优的性能。在完成功能的软硬件分配后，要对系统的性能，灵活性等参数 进行预测，以评估功能划分优劣及合理性。如果划分不合理，就需要重新进行 软硬件划分m 1 。 划分同目标体系结构和应用领域密切相关，没有体系结构的约束，划分得 不到实际的结果。目前有很多嵌入式系统采用如图2 1 所示的单c p u 单a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 系统结构n 7 1 。这种结构有以下一些特 点。 1 系统中有一个固定的c p u ，它可以完成大部分系统功能，但不能完全 满足系统要求； 2 系统中的a s i c 作为硬件加速器，可以实现系统的一个或者多个功能： 3 硬件实现的代价远高于软件实现，系统造价主要取决于硬件面积； 4 硬件实现的性能远高于软件实现。对这种系统来说，应该在满足时间 要求的前提下尽可能用软件实现各种任务，使占用的硬件面积最小。 另一种目标系统结构为单c p u 多a s i c s 类型，所有的软件实现结点都映射 到处理器上执行；所有的硬件实现结点都映射到硬件单元上执行。a s i c s 的数 量可自由选择，处理单元之问通过共享内存实现信息交互，协同运行用户提交 的任务。任务通过共享内存实现相互之间的通信，通信时间可分解为对共享内 存读写的问和数据在总线上的传输时间。为简化计算起见，本文在满足任务 哈尔滨理t 人学t 学硕 ：学位论文 之间先后关系的基础上，将任务之间的通信时问分别计入相互通信的两个任务 的执行时间上。 图2 1 单c p u 单a s i c 结 f i g 2 - 1s i n g l ec p u a n ds i n g l ea s i ca r c h i t e c t u r e 2 1 2软硬件划分种类 根据目标系统结构不同，软硬件划分问题可分为双路划分( b i p a r t i t i o n i n g ) 和多路划分( m u l t i w a yp a r t i t i o n i n g ) 。其中双路划分应用最广 泛，也是软硬件划分问题的基础。 定义2 - 1k 路划分问题：对于模块集合m 一伽1 ，m 29 0 0 0 ，m 刀) ，k 路划分问题 就是寻找簇的集合p 一 p l ，p 29 0 0 0 ，p k ，满足： i ，jsk ，i ，j 。 k 路划分问题的求解通常是要在满足某些约束的条件下优化目标函数。当 k ；2 时，称为双路划分；当k 2 时，称为多路划分问题。目前，对软硬件划 分的研究主要是双路划分。 2 2系统模型的建立方法 计算模型是软硬件划分要考虑的一个重要内容。对系统的不同层次的抽象 形成不同的计算模型，使划分可以在不同粒度上进行。划分中用到的计算模型 有有限状态机模型、数据流图引、p e t r i 网啪1 、数据控制流图嵋、任务流图即有 向无环图等。 、i j 正 b m 冲 虮 刮 巧 所七u汹戌 哈尔滨理t 人学t 学硕i j 学位论义 目前，在嵌入式系统设计领域，存在多种行为级描述模型。这些模型各有 特点和应用领域，并不能简单地对比模型的优劣。本文对这些模型进行了分 析，常用的模型可以分为如下几类。 2 2 1有限状态机建模 一个有限状态机是描述控制系统的最常用的模型，因为系统的行为可以很 自然地用状态和状态之间的转换来描述。有限状态自动机模型可以用一个5 元 式来表示：岱，i ，o ，厂，j 1 1 ) ，s ，i ，o 分别表示所有状态集，输入状态集和输出状态 集；厂，h 分别表示为下一状态函数和输出函数。下一状态函数，定义为输入改 变后状态机的下一个状态，输出函数定义为状态改变后输出的符号。按照以上 定义，每个集合s ，和d 中可能有任意多个符号。然而，现实中仅仅处理二 元变量操作符和内存元素。因而，s ，o 必然作为二元的信号或是内存元素的 叉积实现，而厂和h 函数则被定义为布尔表达式，用逻辑门来实现。由于有限 状态机的各状态及其转换可以用来描述控制系统的行为，所以有限状态机模型 成为用来描述控制系统最常用的模型。对于控制领域的应用系统，有限状态自 动机是很好的描述手段，但有限状态自动机模型也有其自身的缺点，系统的节 点数与有限状态机的状态数为指数关系，当节点数超过一定量时就出现状态爆 炸现象。 2 2 2数据流图建模 数据流图( d a t an o wg r a p h ) 是一组节点与连接它们的有向边的集合，表 示为g 一( n ，e ) 。其中，n 为节点集合，e 为有向边，e i f o f ，厅f ) 的集合， n i , n ，e n ，f f ，e i ，为节点i 到节点_ 的有向边，表示节点间的数据依赖性 一 ，一7 ， 关系。 d f g 是适合用来描述计算密集型系统的模型，因为数学表达式可以很容易 的表示为一个有向图，图中节点表示操作，而边表示节点操作执行的顺序关 系，数据流图模型是基于两个原理异步性和功能性。异步性原理表明当且仅当 所有需要的操作对象得到时相应的操作才可执行。功能性原理表示所有操作的 执行都像函数一样没有任何副作用。这意味着任何两个操作既可以顺序执行也 可以并发执行。 这种模型的特点是：硬件实现时，每个节点有固定的面积，与其他节点是 否用硬件实现无关；节点的硬件实现比其软件实现有一固定的加速值，与其他 哈尔滨理t 人学t 学顾卜学位论_ ! = 节点是否由硬件实现无关；硬件域的相邻模块之间可以通信，不需要软件域的 参与，但通信也占用硬件面积。图2 2 中m 表示第f 个节点，图2 2 左边表示 软硬件节点间实际的数据依赖关系，右边表示在此划分模型中硬件节点和软件 节点之间的数据关系。从图2 2 中可以看出，寻找系统的软硬件划分可以看作 是寻找一组硬件节点序列，此节点序列只和软件域交换有效的读入和写出变量 集，如图2 2 中的& ，4 和& 7 。 w s h w w s h w 图2 - 2 数据流图划分模型 f i g 2 - 2d a t af l o wg r a p hp a r t i t i o n i n gm o d e l 2 2 3p e t r i 网建模 p e t r in e t s 是德国当代数学家c a r la d a mp e t r i 定义的一种通用的数学模型， 用以描述存在于条件和事物间的关系嘞1 。p e t r in e t s 能够对具有并行 ( p a r a l l e l i s m ) 、并发( c o n c u r r e n c y ) 、同步( s y n c h r o n i z a t i o n ) 、资源共享 ( r e s o u r c es h a r i n g ) 等特性的系统建立形象化的模型，p e t r in e t s 非常适用于 描述大规模复杂系统的控制流，经过扩展的p e t r in e t s 也可以描述系统的数据 流。广泛使用的f s m 模型是p e t r in e t s 的一个子集，因此用p e t r in e t s 建立的 系统模型，可以方便地转化为可实现的软硬件结构。把p e t r in e t s 与整个软硬 件协同设计的系统设计阶段结合起来，包括建立软硬件模型、时序估计、面积 哈尔滨理工人学t 学硕 j 学位论义 估计等，其中还能生成硬件r t l 代码和软件c 语言代码；p e t r in e t s 作为统一 建模语言u m l ( u n i f i e dm o d e l i n gl a n g u a g e ) 的补充来建立系统模型。 p e t r i 网是近年来提出的形式化描述模型，在嵌入式系统建模中也得到了应 用。在p e t r i 网模型中，包含位置，标记，转换等概念。位置可以保存标记， 标记代表流过系统的信息，转换同事件相关。p e t r i 网可以对系统的动态特性进 行精确的描述，较好地对数据流和控制流的动态执行过程实施控制。p e t r i 网的 理论模型严谨，有形式化的分析手段。 2 2 4数据控制流图 在数据控制流图中，节点代表对数据的处理步骤或者控制条件判断，而 边则代表数据和控制的相关性。它可以很方便的描述控制步、数据流和并发等 概念，通常用于高层次综合工具。数据流图又可以分为同步数据流图和动态数 据流图。在同步数据流图中，数据的流向在系统运行前就可以确定，而在动态 数据流图中，数据的流向还要受到运行时数据内容的影响。数据控制流图适 合用于硬件综合工具，作为系统层设计的描述模型，数据控制流图的粒度太 细。 2 2 5任务流图 任务流图模型是一个系统被描述为一些进程的集合，每个进程相对独立， 可看作一个操作序列，以单向的通道和同步的协议进行通信。同步通信的含义 是在通信时先使接受方处于接受状态，再进入通信过程，通信时进程的运行会 暂停。任务流图与前文的数据流图类似，但是只有一个起始节点和一个终止节 点，两个节点之间最多只有一条边。 任务流图也称有向无环图，可表示为g = ，e ) ，如图2 3 所示，v 代表 任务节点的集合，如果任务用硬件集合，则需要一定的a s i c 面积和执行时 间。如果用软件执行，则需要一定的存储器的容量和处理器时间。e 是连接节 点的弧，它的权代表节点问的通信。通信也需要一定的时间和占用一定的内存 或硬件面积。图中每个节点表示系统的一个任务( 或功能模块) ，边表示任务 之问的控制关系或数据流向，每条边的终点任务必须在此边的终点任务完成之 后可以开始进行。每个节点包含其软件、硬件成本信息，边的权重代表两个节 点之间的通信开销。任务流图是系统的行为级描述，主要描述系统中任务间的 控制、数据关系及每个任务的成本信息，而与系统实现时采用什么样的体系结 哈尔演理工大学t 学硕i j 学位论文 构无关，任务流图之间的映射关系如图2 4 所示。 图2 - 3 任务流图 f i g 2 - 3t a s kf l o wg r a p h 图2 _ 4 任务流图的映射 f i g 2 _ 41 h s kg r a p hm a p p i n g 2 3软硬件划分技术中存在问题的分析 映射边 划分中的问题嵋3 1 主要有：说明抽象的层次；划分粒度；系统元件分配；指 标和估计；划分算法；目标函数；输出；控制流