（计算机软件与理论专业论文）面向soc并行软硬件划分算法研究.pdf

上拇大学硕士学位论文 ! 堕! 型竺苎! 堕堡! ! 兰墅翌竖堕望! i 竺i 皇 摘要 微电子工艺的快速发展推动集成电路进入了片上系统s o c ( s y s t e mo i l c h i p ) 时代，随着设计复杂度的提高，传统的设计方法已无法满足s o c 设计的 需要。软硬件协同设计强调在系统设计初期考虑软硬件划分，以最优化设计为 目标，灵活地调整软硬件之间的界限，从而激发了人们对软硬件协同设计技术 的研究兴趣 在整个软硬件协同设计流程中，软硬件划分算法是其中的一个关键技术， 如何兼顾系统的性能和成本，达到性能和成本的最佳结合。是软硬件划分要解 决的问题。由于s o c 软硬件划分属于n p 难问题，对于此类问题现在只能借助 于优化算法对其进行近似求解，本文的工作就是围绕求解s o c 设计中软硬件划 分闯题最优解而展开的。 本文基于软硬件划分性能评价的设计需要，提出一种基于多目标优化的并 行化软硬件划分方法。该方法建立在非劣排序遗传算法的基础上，将划分计算 任务有效分配到多个并行运行的处理机，可直接对多个目标同时进行优化。针 对遗传算法的缺陷和软硬件划分的特点，引入禁忌搜索和按概率选择父个体两 种技术；为了保持遗传算法中群体的多样性，引入小生境技术；为了加快遗传 算法的收敛速度。引入精英保持策略。 结果表明，该算法有效地解决了软硬件划分问题，且稳定性好、效率高。 禁忌搜索、按概率选择、小生境、精英保持策略和并行化五种技术的引入，进 一步提高了算法效率、保证了算法的自适应性及结果的全局最优性。 关键词：s o c ，软硬件协同设诗，软硬件划分，遗传算法，禁忌搜索，并行算 法 v 上海大学硕士学位论文 ! 堕塾窭堡垒! 堡! 堕! 垡! 磐婪! ! 堕塑 a b s t r a c t t h er a p i dd e v e l o p m e n to fm i c r o e l e c t r o n i c st e c h n i q u e sp r o m o t e si ci n t os o c ， e 执b u tw i t ht h ei n c r e a s eo fs d cd 懿i g nc o m p l e x i t y , t h ec o n v e n t i o n a ld e s i g n t e c h n o l o g y c a n t s a t i s f y t h ed e m a n do fs o cd e s i g n t h eh w s w ( h a r d w a r e s o f t w a r e ) c o - d e s i g nt e c h n o l o g y , w h i c ht a k e st h eh w s wp a r t i t i o n i n g i n t oa c c o u n tt oa d j u s tt h ed o m a i no f h wa n ds wa tt h ev e r yb e g i n n i n go f t h ed e s i g n ， a n ds e tt h eo p t i m a ld e s i g na si t so b j e c t i v e , f i r e sl l pr e s e a r c h e r si n t e r e s t d u r i n gt h ew h o l ep r o c e s so fh w s wc o - d e s i g n , t h eh w s wp a r t i t i o n i n g a l g o r i t h mi sak e yt e c h n o l o g y h o wt ok e e pt h eb a l a n c eb e t w e e nt h es y s t e m ss p e e d a n di t sc o s t , a n do b t a i nt h em a x i m u mo fi r f o r m a n c ec o s tr a t i o ，i st h ep u r p o s eo f h w s wp a r t i t i o n i n g b u ts o ch w s wp a r t i t i o n i n gi sr e g a r d e d 嚣a nn p - h a r d p m b l e m ，a n dn o w c a l lo n l yb ea p p r o x i m a t e l ys e t t l e dt h r o u g hs o m ek i n d so f o p t i m a l a l g o r i t h m t h em a i nw o r ko ft h i sd i s s e r t a t i o nf o c u s e so nh o wt og e tt h eo p t i m a l s o l u t i o no f h w s wp a r t i t i o n i n gd u r i n gs o cd e s i g n b a s i n go nt h en e e do fh w s wp a r t i t i o n i n gp e r f o r m a n c ee v a l u a t i o n , an o v e l p a r a l l e lh w s wp a r t i t i o n i n gm e t h o db a s e do nm u l t i - o b j e c t i v ei sp r o p o s e di nt h i s d i s s e r t a t i o n , w h i c hi sb u i l t0 nn o n - d o m i n a t e ds o r tg e n e t i ca l g o r i t h m , a s s i g n st h e t a s l 圆o fp a r t i t i o n i n g 幻an a r n b e ro fp a r a l l e lp r o c e s s o r s , e x e c u t e st h ep a r t i t i o n a l g o r i t h mo nt h o s ep r o c e s s o r ss i m u l t a n e o u s l ya n dp o s s e s s e st h ea b i l i t yt os e a r c h m u l t i - o b j e c t i v es y n c h r o n o u s l y d u p e n d i n go nb o t ht h eh w s wp a r t i t i o n i n ga n dt h e g a sc h a r a c t e r i s t i c ，t a b us e a r c ha l g o r i t h ma n ds e l e c t i n gt h ee l d e r - i n d i v i d u a l si nt h e l i g h to fp r o b a b i l i t ya r ci n t r o d u c e di n t ot h en o v e lm e t h o d t oi c e 印t h ep o p u l a t i o n s d i v e r s i t ya n de n h a n c et h ea l g o r i t h m ss p e e do fc o n v e r g e n c e ，t h en i c h et e c h n o l o g y a n de l i t i s m - p r e s e r v i n gs t r a t e g ys e p a r a t e l ya r ea p p l i e dt ot h en o v e lm e t h o d t h er e s u l ts h o w st h a tt h ea l g o r i t h md e s i g n e dr e s o l v e st h eh 碍猖wp a r t i t i o n i n g w i t hg o o ds t a b i l i t ya n dh i g l le f f i c i e n c y t a b us e a r c h i n ga l g o r i t h m , s e l e c t i n gt h e e l d e r - i n d i v i d u a l si nt h el i g h to fp r o b a b i l i t y , n i c h e ，e l i t i s m - p r e s e r v i n ga n dp a r a l l e l t e c h n i q u e s e n s u r et h ea l g o r i t h m ss e l f - a c h p t a b i l i t ya n dt h er e s u l t sg l o b a l o p t i m i z a t i o n ，f u r t h e r n l o r e ，t h ee f f i c i e n c yi sh e i g h t e n e dm a r k e d l y k e y w o r d s ：s o c ，h w s wc o d e s i g n , h w s wp o r t i o n i n g , g e n e t i ca l g o r i t h m ，t a b u s e a r c l lp a r a l l e la l g o r i t h m 上海大学硕士学位论文 ! 塾! 墅塑望! 坐塑! ! ! ! ! 墼些坐塑巴塑 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：圭童：e t 期：弛主：“ 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：渔z 三：瑾 上 辱大学硕士学位论文 ! 堕! ! 塑苎垂竺墅! ! ! ! ! 竺型坐塑! 堑 第一章前言 大规模集成电路依照摩尔定律在迅速发展，现已能在单一硅芯片上集成 m c u 、m p u 、d s p 等模拟与数字混合电路，所构成的一个完整系统就是s o c ( s y s t e mo nc h i p ) 【i 】。s o c 将原来由许多芯片完成的功能，集中到块芯片中 完成。但s o c 不是各个芯片功能的简单叠加，而是从整个系统的功能和性能出 发，用软硬结合的设计和验证方法，利用i p ( i n t e l l e c t u a lp r o p e r t y ) 复用及深亚 微米技术，在一个芯片上实现复杂的功能。 1 1 s o c 软硬件协同设计理论 s o c 有三大研究领域【2 】：软硬件协同设计技术、m 孩生成与复用技术、超深 亚微米集成电路设计技术。每个研究领域包含一系列的子课题。在s o c 中，尤 其是面向特定应用的s o c ，软件和硬件的结合更加紧密，软硬件之间的功能划 分，以及软件和硬件的实现都没有固定的模式，而是随着应用的不同而变化。 软硬件协同设计的目标是在设计过程中把软件、硬件结合起来，作为一个 系统综合考虑，实现整个系统设计的最优化，以及设计工作的自动化。自2 0 世 纪9 0 年代初兴起以来，一直是一个非常活跃的研究领域，受到包括产品设计者 和工具开发者在内的多方重视。目前，软硬件协同设计的研究内容主要包括系 统描述、软硬件翔分，软硬件协同综合和软硬件协同模拟等方面【，j 。 系统描述 系统描述的目的是在一个较高的抽象层次上描述整个系统的行为，获取用 户需求。以便在详细设计开始之前，验证需求分析和系统描述的正确性，进行 必要的系统分析，并作为后续设计的基础。系统描述独立于后续的实现过程， 可以仿真运行。 软硬件划分 软硬件划分的任务是把系统功能划分为软件实现部分和硬件实现部分，并 使得整个系统的性能、成本指标达到最佳平衡点，是软硬件协同设计中的一个 重要课题，划分结果力求保证速度，减少成本、降低功耗。 软硬件综合 软硬件综合的任务是把高层次的描述自动转化为低层次的实现。软件综合 又称为代码生成。硬件综合通常分为高层次综合和逻辑综合两种层次。目前， 上海大学硕士学位论文 ! 堕垒塑型! 苎竺塑垫! ! ! ! 些型! 墅竺堕 硬件的逻辑综合已经发展的比较成熟，但是软件综合以及硬件的高层次综合都 还没有进入使用阶段。因此，现在还难以从软硬件划分所得的高层描述自动综 合出在功能和性能上满足要求的软硬件 协同模拟 软硬件协同模拟的目的是在硬件生产出来之前，通过模拟的手段验证软硬 件集成方面的问题。软件模拟和硬件模拟都存在着不同的抽象层次：抽象层次 越高，模拟速度越快，但是，反映的细节也越少。 软硬件协同模拟可以分为高层次模拟、低层次模拟、混合层次模拟三种情 况。当前，对于低层次模拟的研究比较成熟。一般的模式是软件调试环境、微 处理器模型和硬件的r t i , 级描述的协同模拟。可以在尚未生产出硬件之前对其 虚拟模型进行一些早期调试，并为软件调试提供虚拟的平台。 1 2 软硬件划分技术 软硬件划分是软硬件协同设计流程中的一个关键技术。所谓软硬件划分， 是指在设计系统时，确定各个模块是采取软件还是硬件的实现方式。软件实现 的特点是灵活、成本低；硬件实现的特点是性能高，成本高。如何兼顾系统的 性能和成本，达到性能和成本的最佳结合，是软硬件划分要解决的问题1 4 】。 在对系统规格说明进行建模后，软硬件划分算法对模型进行划分。划分的 结果将决定整个设计的方向所以，性能优良的划分算法能够在充分考虑系统 设计需要的前提下，给设计人员提供性能优良的划分方案，为下一步设计打下 良好的基础。而性能较差的划分算法将会导致设计周期跌宕，从而影响整个设 计计划，甚至导致整个设计的失败当前的软硬件划分技术可以分为两大类【5 】： 面向功能 面向功能软硬件划分方法首先将系统规范划分为一系列功能单元，然后将 这些单元分别指派为软件或硬件实现主要通过搜索设计空间来得到一个优化 的软硬件实现方案【6 】 面向结构 面向结构软硬件划分方法主要考虑系统的结构转换和组成规则。基于代数 规则的划分方法是一种形式化面向结构的方法，既可以进行语法制导的划分， 又可以用于验证 t j 。 上海大学硕士学位论文 ! 堕塑塑里! 兰坐! 堡! 竺! ! 塾! 竖型望璺! 墅壁 软硬件划分中的问题主要有：说明抽象的层次；划分粒度；系统元件分配 指标与估计和划分算法。 说明抽象层次 抽象的层次的分为三层：( 1 ) 算法层，即每个操作表示一个任务的数据流图， 每个任务被描述为一个顺序程序。( 2 ) 数据流图层，数据流图由算法操作和一 些控制操作组成，是划分中最常用的一种模型。( 3 ) 有数据路径的有限状态机， 包含有限状态机中状态计算或转移时可能存在的复杂表示。 划分粒度 分解粒度是对某个模块说明大小的一个衡量。说明首先被分解为函数对象， 然后对其在系统元件中进行划分。粗粒度意味着每个模块包含大量的说明；而 细粒度意味着每个模块包含少量的说明，也意味着有更多的模块和更多种可能 的划分方案，可以获得更好的优化。 系统元件分配 分配是指从允许的元件中选择一些元件类型，从每个类型中挑选一些来使 用的过程，其中被选择的元件集合称为一个分配。可以使用各种可能的分配来 实现一个说明。每种不同的分配之间的主要区别在于他们的成本和性能；分配 由手工或联合划分算法实现。划分技术必须指派系统元件类型，从而把功能模 块映射到其上，如a s i c 、i p 核、存储器等。 指标和估计 在超大规模集成电路设计中必须定义划分的属性以决定划分的质量，这些 属性称为指标。这些指标包括：成本、执行时间、通信速度、功耗、面积、端 口输入、可测试性、可靠性、程序大小、数据大小、存储器大小用其中最相 关的指标来预测任意两个划分结果的好坏。衡量划分算法好坏的关键指标是成 本、性能和硬件的面积。提高性能通常是把模块的功能移到硬件上实现；而减 少硬件面积的方法则是将模块用软件来实现。指标的计算有两种实现方式：一 种是通过创建一种细节的实现，另一种是创建一种粗略的实现。细节的实现能 产生精确的指标值，缺点是花费时间多不实用。粗略的实现包括一个设计的 主要寄存器传输元件。而忽略精确的布线和优化逻辑等需要大量设计时间的细 节。 上海大学硕士学位论文 ! 墅塑塑巴壁堂! ! 堕垫型塾! 垒量堕望堂螋 划分算法 划分算法根据耗费函数寻找一个最好的划分，可用于软硬件划分的常见算 法有整数规划嗍、混合线性规划【9 l 、启发式算法f 1 0 l 等。但是，如果系统设计时 的划分粒度很小，或者系统功能的复杂度很高，系统中的节点就会显著增多， 划分算法在求解的过程中将面对巨大的搜索空间。这时候，传统算法要么效率 太低，无法让人承受。要么容易陷入局部最优。导致划分结果不能获得很好的 性价比。除此之外，对于规划类算法，难以给出明确的且标函数，而且约束条 件很多，不易使用。而启发式算法对启发式规则要求很高，而且结果很容易受 启发规则的影响。因此，需要对划分算法进行专门的研究。 1 3 并行实现方法 随着集成电路规模的迅速增长、复杂度的不断提升，划分所耗费的时间越 来越长，在追求划分效果的同时，划分速度已经成为设计s o c 过程中的一个瓶 颈。这主要是由以下因素造成的： ( 1 ) 深亚微米技术的发展使得s o c 芯片中需要进行系统性能比较的次数及规模 大大增加； ( 2 ) 母模型库中越来越多标准的m 核的引入增加了球核数据库的复杂度，进而 影响划分算法的复杂度。 为了解决这些问题，有效地提高划分速度，国内外专家提出了很多划分算 法。但是，这些算法基本上都在单机上实现，所得到的效果并不十分显著，划 分速度的提升局限于一个有限的层次，而且缺乏通用性。在传统的划分算法无 法取得突破的情况下，并行软硬件划分算法作为一个新的研究领域开始受到重 视。并行软硬件划分通过划分解搜索区域到并行机的多个处理器或者普通工作 站网络，从而减少模拟时间。 1 4 国内外研究现状 随着并行软硬件协同设计的广泛展开，人们越来越关注并行软硬件划分的 性能。在并行软硬件协同设计的过程中，运行中的软硬件划分在很大程度上影 响着最终性能。国内外学者对软硬件划分算法进行了大量的相关研究，但主要 应用于高性能计算机和方程式的计算等方面，在基于s o c 尤其是并行协同设计 方面的研究并不多。 4 上海大学硕士学位论文 ! 堕塑堕翌! ! 坐! 堕! ! ! ! 墅! 型! 型! 苎翌 软硬件划分最初是设计者依据经验手工划分，而最早的自动划分方法出现 在9 0 年代初期f l ”。就功能划分而言，v a h i d 针对结构性划分，阐述了功能性划 分的优点网；e r n s t 提出的方法是先将所有系统功能模块划分为软件，然后进行 迭代，选择部分功能模块移动到硬件以提高系统的速度 i 司；通过遍历任务表， k a l a v a d e 和l e e 设计了一种构造性系统功能划分算法，该算法能够自适应地根据 优化规则对相应的面积和时间的权重进行调整【1 ：3 1 。就采用的划分算法而言，e l c s 提出采用模拟退火算法和禁忌搜索算法来实现软硬件划分【1 4 l ：k o r o u s i c - - s e l j i a k 和c 0 0 l i l l g 使用遗传算法对任务的分配进行优化 1 y j ；s a l l a 提出基于遗传算法的软 硬件划分算法【1 6 】：a x c l s s o n 比较了禁忌搜索、模拟退火以及遗传算法三类不同 算法解的优劣情况i 7 1 ；b e n d e r 采用混合整数线性规划方法来解决软硬件划分问 题f 1 。】id i c k 等提出使用遗传算法来实现软硬件划分【1 9 】；h e n k e l 和e r n s t 提出了可 变粒度的用于软硬件划分的模拟退火算法1 2 0 l 。针对嵌入式实时系统，g u p t a 和 d em i c h e l i 提出了在协处理器和通用处理器上进行划分的迭代算法【2 1 1 ；c h a t h a 和v e m u r i 提出采用改进迭代算法对任务图在单个协处理器和通用处理器进行划 分固；e c f i l h o 等采用基于p c m 网来进行软硬件划分吲；t o w l s e y 在不考虑实时 限制的条件下，解决了同构分布嵌入式系统任务分配的问题口4 筇捌。就自动划 分技术，k a r a k e h a y o v 提出了用在同构分布式处理器之间进行系统功能自动划分 的算法【2 7 】；g a j s k i 提出允许设计者手动或自动在不同处理器上进行功能划分的 算法t 2 s 。针对系统约束的技术。k n u d s e n 和m a d s e n 采用动态编程技术，使得单 个通用处理器的执行时间最短，同时还能在面积约束条件下使得a s i c 的面积最 小瞄j 。l e e 和s h i n 在考虑了通讯的前提下，解决了同构任务的分配问题刚。 p o t k o n j a k 和r a b y 提出了一种构造性算法来优化系统的吞吐量和代价】。集调 度于一体的技术中，a m b r o s i o 和h u 提出了一种通过抽象估计可被调度系统结 构的概率来实现软硬件划分的算法【3 2 】；l i u 和w o n g 提出了一种集软硬件划分和 调度于一身的改进迭代算法州。 国内对软硬件划分的研究开展得晚一些，但从一开始就赶上了s o c 技术的 机遇，发展比较迅速不少大学和研究机构，以及集成电路设计和制造企业有 研究小组和实验室从事这方面的研究。不管是在并行进程比较多的系统，还是 嵌入式系统( 在或不在资源争用条件下) ，对评估因子的确定、系统性能评价的 方法和耗费函数的构造都取得了一些成果，在划分算法方面在考虑了系统的关 键路径、任务的权重、系统的时间约束以及面积约束等方面之后，对遗传算法、 蚂蚁算法、混合型整数规划法、模拟退火法、达布搜索法、贪心算法、爬山算 法和二分约束搜索算法等的基础上做了改进，也取得了不俗的成绩。 上海大学硕士学位论文 堡塑型竺堡坐! 箜磐鲤些竺塑 总的来说，国内外对并行s o c 协同设计中的软硬件划分技术缺乏深入的研 究，在这方面还有很大的研究空间通过混合软硬件划分算法提高并行s o c 协 同设计的性能有很大的潜力。因此，这方面的研究成果能够促进国内在并行s o c 协同设计方面的研究工作更重要的是，加强并行s o c 协同设计中软硬件划分 的研究对推动国内研制出优秀的并行s o c 协同设计技术也具有重要的意义 1 5 课题的研究内容 本文研究的课题来源于上海一应用材料研究与发展基金项目( 美国a m 基 金) 资助的( s o c 并行软硬件划分与协同模拟验证技术研究中的子课题 面向s o c 并行软硬件划分的研究该基金项目的研究重点是研究与实现一个在 并行环境下运行的高性能软硬件划分与协同模拟系统及验证平台，能将输入的 系统说明，经过一种良好的软硬件划分算法与自动划分方法，划分为比较合理 且符合需求的软件与硬件部分，并根据划分结果建立软硬件各部分的多层次模 拟模型，然后，对所建模型在事务级验证平台上进行快速验证与测试。 本文主要研究内容是如何利用划分来提高软硬件协同设计的性能，研究对 s o c 芯片进行软硬件划分的有效方法，使软件的综合性能达到预期目标的同时 使硬件达到最低的制造和使用成本。还研究多处理器内核的不同功能软件的实 现策略，与处理器类型及性能相结合，研制多处理器结构下的软硬件划分方法。 本文将按如下章节进行探讨： 第一章介绍课题的研究背景及国内外研究现状，并对本文的主要工作进 行概括。 第二章介绍软硬件划分的基本概念和构架，分析其影响因素，对已有的 划分算法进行优缺点分析和研究。 第三章设计$ o c 软硬件划分模型的整体结构。叙述划分模块的实现过程， 包括划分模型的表示方法和建立过程。 第四章设计并行s o c 软硬件划分模型结构，分析本文所采用的并行模拟 模型和划分算法的数据结构。 第五章对划分算法的测试。对混合划分算法和几种传统的划分算法进行 性能分析和比较。 第六章对本文工作做总结，并对下一步工作做介绍。 6 上海大学硕士学位论文 ! 望堡堕! 坐坐! 堕! ! ! ! 墅竖堕! 堂竺堕 第二章软硬件划分算法的研究 2 1 软硬件划分问题描述 本文使用功能流图来描述s o c 系统，功能流图是有向无环图，只有一个起 始节点和一个终止节点，如图2 1 图中的每一个节点表示的是一个系统功能， 节点信息包含其用软、硬件方法实现所耗费的基本时间和成本信息，即软件运 行的成本( 由软件所占内存决定) 、软件运行所需的时间、硬件运行的成本( 由 硬件面积决定) 、硬件运行所需的时间和节点在整个系统中所处的位置等。有向 边表示功能之间的控制关系和数据流向，每条边的终点功能必须在此边的始点 功能完成之后才可以开始执行。边的权重表示两个节点之间的通讯开销。 图2 15 个节点的功能流图模型 功能流图是s o c 系统的行为级描述，主要描述系统中功能间的控制、数据 关系及实现每个功能的成本信息，而与系统实现时采用什么样的体系结构无关。 本文中，s o c 系统功能被描述为单独功能的集合，这些单独的功能可以选 择用硬件方式实现或者用软件方式实现。系统功能用硬件实现可以通过硬件加 速和并发的执行提高系统的性能，但是增加了制造a s i c 的成本，灵活性也比 较小；系统功能用软件实现可以有比较好的灵活性，但是对系统性能有影响。 整个系统的运行是多个功能共同协作的结果，而系统的性能好坏是由整体 的运行时间和运行成本来决定的，进而各个功能的实现方式如何分配就决定整 个系统的优劣。每个功能都可以选择由处理器或某妒核实现，软硬件划分设计 要达到的目标是在满足性能要求的基础上，使得成本最小，所以在选定处理器 和几个专用硬件的体系结构的情况下，存在一个成本和性能的权衡：对于系统 可以用到的i p 核，究竟是选择哪些用到设计中，存在一个选择和评价的问题。 上海大学硕士学位论文 堡塑通唑里坚堕! 墅些型竺堂 本文定义系统的成本为每一个功能节点实现所需要的成本总和，定义系统 的运行时间为该系统功能实现所需要的最大时间，具体规则如下： ( 1 ) 软件实现功能一般由处理器来完成，在单个处理器上采用先来先服务的方 式，而后续任务必须等到之前任务都已完成时才能申请处理器；硬件实现功 能可以并行处理，但是必须等到前序节点功能已经完成的情况下才可运行 ( 2 ) 当一条功能路径( 路径的获取将在第四章具体介绍) 上的相邻节点采用不同 的处理方式时( 分别采用软、硬件处理) ，必须计算通讯开销。而在相邻节 点采用相同的处理方式时，节点问的通讯开销可以忽略不计 用性能矩阵d 表达系统功能与处理节点的关系。假设系统有m 个功能， 个处理节点，则性能矩阵d 为一个膨n 的矩阵，d ( i , ) 表示处理节点_ ，实现 功能i 需要的时间。如果d ( i , ) = ，就表示处理节点，无法实现功能i 的功能。 定义h = 协，嚏 是系统功能中实现在硬件上的功能集合，其中， ，气是具有不同功能的硬件模块。s 是系统功能中实现在软件上功能的集 合，o 是全部系统功能的集合，而且日cd ，s 1 - d h u s = d h n s = 一。 定义一个s o c 系统为三元组s = f 一足z ：y = 屹，) 是系统中的处理 节点集合，n 为系统的节点总避；r ； ， ，c = 日u s 表示节点珀q 实现方式集合，二维矩阵z c v x v 代表节点之问的连接关系。 在满足性能约束的条件下，软硬件划分过程即寻找一个从节点集合矿到设 计的映射：矿啼4 。使得系统耗费成本最小。本文中软硬件划分的截止条件是 优化解的平均耗费时间和平均消耗成本均小于系统要求时间和系统要求成本， 算法结束后输出最优划分结果。 由于在s o c 软硬件划分过程中需考虑多个目标的优化，因此软硬件划分问 题属于组合优化问题，每一个组合最优化问题都可以通过枚举的方法求得最优 解，但是枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接 受，从而形成n p 完全问题的概念。 上海大学硕士学位论文 ! 望望塑型垫竺竺! 丝坐! ! 塑! 竖墅望璺塑墅 2 2n p 完全问题 组合问题的求解常常要从多个方案中选出一个满意的。也许有人认为，从 多个方案中挑选一个总是比较容易的，然而事实并非如此，关键在于问题的规 模。由于计算机的出现，人们对问题的求解在观念上发生了改变。一个在理论 上可解的问题如果在求解时需要花费相当多，以至于不太合理的时间( 如几百 年甚至更长时间) ，我们不能认为它已解决，而应当努力寻找更好的算法由于 这个原因，对算法可作如下分类删； 定义l ( 多项式算法)设口是求解问题d 的一个算法，耳为问题d 的规 模，用厶( d ，一) 表示用算法占在计算机上求解这一问题时需作的初等运算的次 数。若存在一个多项式p ( 一) 和正整数，当疗时，总有石( d ，一) s ，( ”) ， 则称算法占是求解问题d 的一企多项式算法。 定义2 ( 指数算法)设算法c 是求解问题d 的一个算法，若存在一个常 数_ j 0 ，对任意疗。总可以找到问题d 的一个规模为h 的实例，用算法c 求解 时t 所需的计算量约为c ( d , n ) = d ( 垆) ，则称c 为求解问题d 的一个指数算 法。 多项式算法被称为是“好。算法，而指数算法则一般认为是“坏”算法， 因为它只能用来求解规模很小的问题。这样看来，对一个问题只有在找到求解 它的多项式算法后才能较为放心。然而可惜的是。对于许多具有十分广泛应用 价值的离散模型，人们至今仍未找到多项式算法。我们称找不到多项式算法的 问题为n p ( 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 ) 完全类问题它们具有两个性质： ( 1 ) 这类问题中的任何一个问题至今均未发现有多项式算法。 ( 2 ) 只要其中任一个问题找到了多项式算法，那么其他所有问题也就有了多项式 算法。 现在n p 完全类中的问题已经被扩充到了四千多个，其中包括本文讨论的软 硬件划分问题嗍，所以软硬件划分不存在求解最优解的多项式时间算法。正因 为到目前为止，软硬件划分最优化问题还没有找到求最优解的多项式时间算法， 而这个问题又有非常强的实际应用背景，人们才不得不尝试用一些并不一定可 以求解到最优解的算法来求解软硬件划分问题。 9 上海大学硕士学位论文 堡塑壁型些里坚! 竖! 塑幽型竺堑 2 3 多目标优化 在实际应用中，遇到的很多都是需要使多个目标在给定区域上都尽可能好 的优化问题，这些设计目标的改善有可能是相互抵触的。这种多于一个的目标 在给定区域上的最优化问题就称为多目标问题。 在上一章已经提到，s o c 芯片设计的要求是面积小、功效低、速度快以及 成本低，即软硬件划分问题实际上是一类多目标优化问题。解决这类多目标优 化问题的方法有3 类： ( 1 ) 将多个目标分割对待，取出其中的一个目标作为优化目标； ( 2 ) 通过线性加权，将多个目标转化为单个目标来求解； ( 3 ) 通过多目标优化算法直接对多个目标进行求解。 对于方法( 1 ) ，由于只取多个优化目标中的一个目标作为整体的优化目标， 这是一种典型的单目标优化问题，而对于多目标优化问题来说，往往多个目标 是相互影响、相互抵触的，一个目标的改善，可能会导致其他目标的下降，所 以该方法不能从根本上求得多食目标的最优解。 对于方法( 2 ) ，由于采用了线性加权的思想，将多个目标转化为单个目标， 从而将多目标优化问题转化为单目标优化问题来求解。这种方法对权值向量的 选取十分困难，而且选用不同的权值，算法得到的解相差很大，具有较大的主 观性 方法( 3 ) 采用多目标优化算法可以直接对多个目标进行优化，从而能够从根 本上克服方法( 1 ) 和( 2 ) 的缺陷。多目标优化算法将会在下面详细的讨论。 严格地说，软硬件划分是一个多目标约束极小化问题，即在约束条件下， 使得划分结果耗费的资源最小。对于约束优化问题，常常采用惩罚函数法，即 在目标函数中加上一个可以反映解是否位于约束集内的惩罚项，来构成一个广 义目标函数，从而使得算法在惩罚项的作用下找到问题的最优解【3 那。对约束极 小化问题，惩罚函数应对非可行解产生一个正的惩罚，而对可行解则不产生惩 罚或惩罚尽量小设计者在进行权衡中要依据成本、性能，全面地对系统进行 分析，得到一个满足性能要求的，成本较低的系统划分方案。 l o 。 上海大学硕士学位论文 堡墅坚坐坐卫兰蜜! ! ! ! 鲤鲤塑! 型璺= 2 4 几种典型的划分算法 如何快速有效地搜索到问题的全局最优解或近似最优解是设计算法时所必 须考虑的问题至今为止，已经有许多基于图形化的划分算法被开发设计出来， 这些划分算法在优化解的选取、处理并行性和算法收敛速度方面都很有特色， 下面将对那些已经存在或正处于研发过程中的基于s o c 软硬件划分的算法作一 个简短的介绍，并且比较分析它们各自的优点和缺陷。 ( 1 ) 爬山算法 爬山算法采用“以退为进”的策略寻优，能够接受负方向的移动，因此可 以逃出多数局部最小点阁。只需要建立一个初始划分，然后应用该算法即可。 其难点在于耗费函数必须考虑性能约束和最小化硬件两方面因素，一项为所有 性能不满足的和，另一项为硬件尺寸为保证找到的优化解能满足性能要求， 性能项需要较大的权，即最小化硬件尺寸应次要考虑。此算法易于陷入局部最 优。 ( 2 ) 局部搜索算法之禁忌搜索算法 局部搜索算法首先建立一个初始可行解为当前最优解，然后在可选邻域中 寻找更优的解作为新的最优解唧其优点是简单易行，容易理解，但其缺点是 无法保证全局最优性。禁忌搜索算法是局部领域搜索算法的推广，是人工智能 在组合优化算法中的一个成功应用禁忌搜索算法的特点是采用了禁忌技术， 所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的不 足，禁忌搜索算法用一个禁忌表将已经到达过的局部最优点记录下来，在下一 次搜索中，根据禁忌表中的信息不再重复地或有选择地搜索解空间的点，以此 来跳出局部最优点。 ( 3 ) 蒙特卡罗算法之模拟退火法 蒙特卡罗算法是以一定的概率接受一个较坏的解，从而就可能遍历所有的 解。模拟退火算法就是这样的搜索方法，模拟退火算法来源于固体退火原理， 模拟物质材料的冷却与结晶过程，通过退火温度控制搜索过程f 退火过程受 冷却进度表控制，包括控制参数的初值t 及其衰减因子，、每个f 值时的迭代次 数工和停止条件s 。问题规模较大时，系统进入热平衡状态( 对应于最优解) 的 时间较长。不同于蒙特卡罗随机搜索算法的思想，禁忌搜索则是用确定的方法 跳出局部最优解p ”。 上海大学硕士学位论文 ! 墅塾堕型! 坐婴! ! ! ! ! 型型! 堕! 竺堕 ( 4 ) 蚂蚁算法 蚂蚁算法融八人类智能，通过路径上信息素的不断更新形成了一种正反馈 机制，从而使算法高效收敛到最优解，而且具有通用随机优化特性。蚂蚁算法 是一种全局分布式优化方法，有利于并行计算，既可求解单目标优化问题，也 可求解多且标优化问题。但是如果初期信息素缺乏，将导致搜索初期积累信息 素占用的时间较长t a g 。 ( 5 ) 遗传算法 遗传算法主要模拟生物进化的过程，对初始解进行交叉变异得到一个更优 的解嗍。遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出优点。 目前，遗传算法已经成功地应用到机器学习、模糊系统、人工神经网络训练、 程序自动生成、专家系统的知识库维护、数据挖掘、大分子计算、蛋白质预测、 基因对比、各种图论与网络中的组合问题、多目标规划等广泛复杂、困难优化 问题的求解。 总的来说，由于爬山算法接受负方向的移动，因此可以逃出多数局部最小 点，但易于陷入局部最优。禁忌搜索算法是全局逐步寻优算法，具有较强的“爬 山”能力，并且搜索速度比较快，总的性能优于爬山算法。模拟退火算法性能 普遍较优，但当问题规模较大时进入热平衡状态时闯较长蚂蚁算法具有正反 馈、分布式计算的特点，但对初始信息素要求过高，影响算法搜索的速度。遗 传算法具有群体性全局搜索能力，可得出若干个最优、次优方案，供工作人员 根据实际情况进行决策选择，但是计算速度慢，有时会收敛到局部最优解。应 用表明，遗传算法效率、寻优能力均强于目前己有的其它优化算法，适宜于求 解多目标有约束问题。 2 5 混合遗传算法策略 本文拟采用遗传算法解决s o c 软硬件划分问题。如果系统运算规模比较大， 遗传算法通常需要比较长的计算时间，对于s o c 软硬件划分问题而言，还存在 许多专门针对该问题的指示型启发算法，这些专门的算法虽然保证不了一定能 找到软硬件划分的全局最优解，但通常计算效率比较高，而且有相当多的算法 其局部寻优能力极强。于是，一个自然的想法是：在遗传算法的搜索过程中融 合这些专门领域知识或快速局部搜索算法，以形成一种混合遗传算法执行策略 来解决s o c 软硬件划分问题，这无疑是提高s o c 软硬件划分效率和质量的一个有 效手段 4 0 , 4 1 , 4 2 , 4 3 1 。 上海大学硕士学位论文 ! 竺塑塑塑壁兰坐! 壁! 竖2 11 坐坚堕望竺塑塑 混合专门领域知识和局部搜索算法到遗传算法通常有以下途径： ( 1 ) 在遗传算法的执行步骤中增加局部搜索步。基于群体中各个个体所对应的表 现型，进行局部搜索，从而找出各个个体在目前的环境下所对应的局部最优 解，以便达到了改善群体总体性能的目的。 ( 2 ) 在编解码过程、繁殖操作中融合专门领域知识。对局部搜索过程所得到的局 部最优解，再通过编码过程将它们变换为新的个体，以便能够以一个性能较 优的新群体为基础来进行下代的遗传进化操作。 在构成混合遗传算法时，d e 1 0 n g 提出下面三条基本原则叫： ( 1 ) 尽量采用原有算法的编码这样就便于利用原有算法的相关知识，也便于实 现混合遗传算法 ( 2 ) 利用原有算法的优点。这样就可保证由混合遗传算法所求到的解的质量不会 低于由原有算法所求到的解的质量 ( 3 ) 改进遗传算子。设计能适应新的编码方式的遗传算子，并在遗传算子中溶入 与问题相关的启发式知识，遗样就可使得混合遗传算法既能够保持遗传算法 的全局寻优特点，又能够提高其运行效率 另外，局部搜索算法的选择在混合遗传算法中也很重要一般的说，这种 局部搜索算法应该具有快速收敛、计算复杂性不高、且所设计使用的辅助信息 与所求解问题匹配等形态9 6 】。 基于这些策略，本文提出一种将遗传算法与禁忌搜索算法混合的划分算法。 具体设计与实现将在接下来的章节中叙述 2 6 小结 本章首先介绍n p 难问题和多目标优化的定义，讨论了软硬件划分的问题 及框架，指出软硬件划分实际上属于n p 难一多目标优化问题。对于n p 难问题， 人们常常采用不能求得最优解的优化算法来处理，本文随后研究常用的优化算 法，包括爬山算法、模拟退火算法、禁忌搜索算法、蚂蚁算法和遗传算法。最 后讨论混合遗传算法的特点及重要性，指出本文将采用混合遗传算法来解决软 硬件划分问题。 上海大学硕士学位论文 堡塑壁型些里兰坐! ! 燮! 旦! 塑里塑 第三章遗传禁忌算法在软硬件划分中的应用设计 遗传算法g a ( g e n e t i ca l g o r i t h m ) 是近代发展起来的一种崭新的全局优化算 法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实 现各个个体的适应度值的提高，从而最终取得最优解。由于遗传算法采取群体 搜索策略，且优化计算时不依赖于梯度信息，所以它的应用范围非常广泛，己 迅速推广到优化、搜索、机器学习等方面 3 6 j 下面先介绍遗传算法在软硬件划 分中的应用原理。 3 1 遗传算法的生物原理 生物的产生、生物的进化、旧物种的灭亡和新物种的出现一直以来是人们 热衷研究的课题。在各个时期，人们都对此有着不同的解释，而目前流行的学 说是达尔文的进化论【4 5 】。达尔文进化论是物竞天择适者生存的自然选择学说， 认为生物大都要经过繁殖、变异、竞争和选择这四个基本过程实现生存与进化。 繁殖是任何生物得以延续下去的基础，生物的繁殖包括无性和有性繁殖， 其中有性繁殖是生物中普遍的繁殖方式，也是被证明为最有利于进化的方式。 变异可以促使生物的不断进化，是生物进步的根本保证。变异既有有利的 变异也有不利的变异，不利的变异自然会被淘汰，而有利的变异在生存中，会 有更大的机会延续下去，从而使整个生物群体趋向优化。 竞争是规模有无限扩大趋势的生物体分享有限生存资源的直接结果。在没 有外界的影响下，生物个体数目总保持在一个稳定的范围内，而繁殖后的数目 则大大超过这一界限，竞争可以使得劣质个体被淘汰，由此导致自然选择。 选择使得各生物间保持平衡，优秀的个体得以生存下来，如此不断地进行， 最终促使整个群体素质的提高。 3 1 1 遗传算法数学定义 遗传算法通过对种群中的个体的基因按照一定的概率规则进行变异操作和 个体之间基因的杂交操作来修改个体的基因构成，然后根据某一确定的衡量标 准通过优胜劣汰机制不断改善该种群在该衡量标准下的质量【柏】。下面介绍遗传 算法中三个关键的数学定义。遗传算法搜索最优解模仿了生物的进化过程，使 用所谓的选择算子、交叉算子与变异算子等来模拟进化，从而产生一代又一代 种群