（电路与系统专业论文）软硬件协同综合算法研究[电路与系统专业优秀论文].pdf

摘要 摘要 随着嵌入式系统应用范围的不断扩展以及系统本身的复杂度的不断增加，系 统设计所面临的问题变得越来越复杂，设计的难度也越来越人。但是系统的改i i 能力并没有跟上相应的步伐。传统的嵌入式系统设计方法是根掘系统设汁帅f f j 的 设计经验对系统进行软硬件手工划分，既费时又费成本而且效率低。针对传统力 法的缺点，提出了一种新的设计方法：软硬件协同设计。软硬件协同设汁通过陀 能评估和建模，进行有效的性能分析，在系统级实现软硬件并行设计。软硬什协 同设计方法加快了设计过程，缩短了产品上市时间。软硬件协f d 综合是软馊什m 同设计的核心部分。 本文综合了启发式算法和演化算法的优点，提出了几种新的锋法柬解决软 硬件协同综合问题。完成的主要工作如下： 1 ) 介绍了嵌入式系统的传统设计方法和软硬件协州设汁力0 上，j i ：给j 两种设计方法的流程和特点；介绍了目6 订协同综合算法，详细说明了算法的流 程和优缺点；介绍了主流的软硬件协同综合工具，给出了各个【具的实现肟刚! 和设计步骤；详细描述了系统的行为模型和目标系统的实现模型，p 旧j ：i - ，j 综合问题的数学模型，给出了适应度函数。 2 ) 提出了基于混合分层遗传算法的软硬件 力、同综合算法。分层结构将软 硬件协同综合的巨大的解空间分割成多个小子空间，再分别在各个子空| 1 = j j 。 ，搜 索最优解，同时引入了启发式算法作为分层遗传算法的初始解。实验结果表叫 了分层结构和启发式算法成功地降低问题的搜索难度，提高了算法效率。 3 ) 提出了基于混合量子遗传算法和混合分层量子遗传算法的软馊什训i i j 综合算法，混合算法结合了启发式算法和演化计算的优点束降低问题的汁算代 价。实验结果表明了混合算法在计算时问上和求解质量较演化算法有f 6 火摊“ 在求解质量上较启发式算法有很大改善。 混合算法综合了启发式算法快速收敛和演化算法搜索能力强的优点，混合 算法在求解质量上较启发式算法有很大提高，同时在汁算时i 冲j 代价i ：较浈f t 计算有很大改善。 关键词：软硬件协同综合遗传算法量子遗传算法启发式算法 ab s t r a c t a b s t r a c t h i 曲c o m p u t a t i o n a l r e q u i r e m e n t s ，f l e x i b i l i t y ，a j l dt i 曲tt i m e t o m a r k e tw i n d o 、 s a r eh a r dc h a u e n g e st ot h ed e s i g no fm o d e r ne m b e d d e ds y s t e m s t h ei n c r e a s i n g d e m a n do fh i g hp e r f o r m a n c ei n e v i t a b l ym a k e st h ea r c h i t e c t u r eo fe m b e d d e d a p p l i c a t i o n sm o r ea n d m o r ec o m p l e x s u c ht r e n d sa n dc h a l l e n g e su r g ed e s i g n e r s t o r e p i a c et r a d i t i o n a la p p r o a c h e sw i t h s o m em o r ee m c i e mt e c h n i q u e ss u c ha s h a r d w a r e s o r w a r e ( h w s w ) c o s y n t h e s i s h w s wc o s y n t h e s i sh e l p sd e s i g n e r sl o 6 n dar e a s o n a b l ea r c h i t e c t u r eo fa na p p l i c a t i o ni nt h ee a r l ys t a g eo fd e s i g nc c l c b e f o r ei m p l e m e n t a t i o n t h i st h e s i sf o c u s e so nt h es o l u t i o n so fo p t i m i z a t i o na l g o r i t h m sf o rhw sw c o s y n t h e s i sa n dm a i n l yf i n i s h e dt h ef o l l o w i n gw o r k ： 1 ) w es u m m a r i z e dt h et r a d i t i o n a lm e t h o d so fe m b e d d e ds y s t e md e s i g na n d h w - s wc o d e s i g n ，l i s t e dt h ef e a t u r e sa n dn o w so fe a c hm e t h o d w es u r v e y e dt h e c o m m o n l y u s e da l g o r i t h m sa n dd e s i g nt o o l sf b rh 、 ，- s wc o - d e s i g n w ed e s c r i b e d t h eb e h a v i o rm o d e la 1 1 da r c h i t e c t u r em o d e lo fe m b e d d e ds y s t e mw i t hm a t h e m a t i c l a n g u a g ei nd e t a i l ，a n dc o n c l u d e dt h em a t h e m a t i cm o d e l0 fc o - s y n t h e s i sp r o b i e m t h e nw el i s t e dt h ef i t n e s sf u n c t i o n ， 2 ) w ep r o p o s e dh g a i it os o l v eh w s wc o - s y n t h e s i sp r o b l e m t h et w o l a y e r s t r u c t u r ep a r t i t i o n st h eh u g es o l u t i o ns p a c ei n t os e v e r a ls u b s p a c e ，t h e nt os e a r c i hi n t h es m a l l e rs p a c e w eu s e dt h er e s u l t so fh e u r i s t i ca l g o r i t h ma st h ei n i t i a ls o l u t i o no f g as i m u l t a n e o u s l y t h er e s u l t ss h o wt h a tt h et w o l a y e rs t m c t u r ea n dh e u r i s t i c a l g o r i t h ms u c c e s s f u l l y r e d u c et h ed i f f l c u l t yo ft h ep r o b l e ma n di m p r o v et h e e 伍c i e n c yo ft h ea l g o r i t h m 3 ) w ep r o p o s e dh g a a n dh q g a - i it os o l v eh w 二s wc o s y n t h e s i sp r o b l e m t h eh y b r i da l g o r i t h mc o m b i n e dt h ea d v a n t a g e so fb o t hh e u r i s t i ca j l de v o l u t i o n a r y a l g o r i t h ms u c c e s s f u l l y e x p e r i m e n t a lr e s u l t ss h o wt h a th y b r i da l g o r i t h m sh a v eb e t t e r p e r f o r n l a n c et h a ng ai nt e 肌o fb o t l lc o m p u t a t i o nt i m ea n ds o l u t i o nq u a l i t y k e yw o r d s ：h w - s wc o s y n t h e s i s ，g e n e t i ca l g o r i t h m ，q u a n m mg e n e t i ca l g o r i t h m h e u r i s t i ca l g o r i t h m 中国科学技术大学论文原创性和授权使用声明 本人声明所呈交的：位论文，足本人在导帅 旨导卜进盯川f j 所取得的成果。除已特别加以标注和致谢的地方外，论文i f i 1 也禽f 何他人已经发表或撰写过的研究成果。与我一同工作的川忐肘小研允 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论义的部分他川杖，l ! l j ：。j j ： 校有权按有关规定向国家有关部f 、i j 或机构送交沦义的复印什和lu i 版，允许论文被查阅和借阅，可以将学位论文编入有天数据博进行枷 索，町以采用影印、缩印或扫描等复制手段保存、 i 编。f _ 沦之 保密的学位论文在解密后也遵守此规定。 作者虢袒一 劢仁厂2 ，i 第1 审绪论 1 1 研究背景 第1 章绪论 嵌入式系统( e m b e d d e ds v s t e m ) 是以应用为目的、以计算机技术为雏础、 软件硬件可裁剪、能适应应用系统对功能、可靠性、成本、体积、功耗等j i l i 格 要求的专用计算机系统。一般出嵌入式微处理器、外阐硬件设备、嵌入擞住 系统以及特定的应用程序四个部分组成，用于实现对其他设箭的栉制、豁w 、 管理等功能。 随着大规模集成电路( v l s i ) 生产上岂的捉岛，柏比f ( f 统i 沃入匕系统，巍 代嵌入式系统的规模有了很大增加，并丌始大量出现片卜系统( s o c ) s ( ) ( 、 是指在单一芯片上集成了数字和模拟电路、信号采集和转换、u 0 、仃储器、做 控制器m c u ( m i c r oc o n t r o lu n i t ) 和数字信号处理器d s p ( d i g i t a ls i g n a l p r o c e s s i n g ) 等i c ，它可以在单一芯片上实现信号采集、转换、存储、处邪嗣】i 7 f ) 接口等功能，使得系统的体积和成本大大下降，顺应了向高性能，低功耗，低 成本的发展趋势。s o c 的出现掀起了微电子设计领域的场革命，随符超人规 模集成电路工艺技术的发展，器件尺寸变得越来越小，单片芯片的集成度也，逃 来越高，系统的功能也越来越复杂。较为复杂的嵌入式系统律，辛包括号田集f 胶 电路部分，以及在嵌入式处理器上运行的软件代码部分，整个系统的性能，改 计制造成本及可编程性都依赖于该系统的软件和硬件设计。冈此，存昂贵的芯 片设计和制造成本，以及越来越短的t i m e t o m a r k e t 的爪力下，盘f i 何能设i 性能和成本都符合要求的系统就成为系统设计的。个课题。 在这样的背景下，软硬件协同设计技术( h a r d w a r e s o f t w a r ec o d e s i 凹j 越术越 受到人们的重视。所谓软硬件协同设计就是通过软件和硬件的并发设计，允分技 挥软件和硬件的协同作用，来达到系统缴的设计目标。 1 2 嵌入式系统设计的发展趋势 随着设计技术的发展以及人们对嵌入产品性能需求的摊- 盘，j 沃入式系统砹 计有以下几个明显的发展趋势 1 】 2 】【3 】： 1 ) 设计复杂性提高，规模变大，设计对象从单机走向系统。 2 ) 产品更新速度加快，设计周期缩短。 3 ) 设计要求由单目标走向多目标，一般来说，山r 应用场合的约束， 妖入 第l 蕈绪沦 式系统对f 系统体积、功耗等有较严格的限制。 1 ) 嵌入j = 系统更多采用软硬件异构方式构造，改计所设计的领域m ，f 1 锨 域走向多个领域( 软件、硬件、应用环境等) 。 嵌入式系统有两种基本的实现手段，软件和硬件。软件手段是通过延i j - 九做 处理嚣卜的程序实现系统功能，而硬件手段是通过专用电路实现系统功能。 救 来说，软件比硬件更加灵活、成本低，而专用硬件提供了史高的性能。这阳干l | lr 段在功能、性能上存在巨大的差异，为了达到成本和性能的最佳结合，兼顾速j 受 和灵活性，目自，j 的嵌入式系统大部分采用软硬件异构的构成方式。 5 ) 实现上集成化程度提高，设计更强调设计重用。 随着半导体技术的不断发展，单芯片上晶体管数最及集成存芯片 ：的功能f 1 ： 不断增加。系统级芯片( s o c ) f 1d 仃已绛成为集成电路、f k 界的。坟幄币：t i 系缝j j ：甚片觇模大，设计复杂，需提高设计复用的层次，更多地采川i p 复川技术，改i i 再利用建立在l p 核( c o r e ) 的基础上。由于单片系统级芯片i 焚计住速度、助l 屯、 成本 ：与多j 毒片系统相比，b + 有较人的优势，符合嵌入系统的改汁前求；阪入，t l 系统采用系统级j 占片方式实现成为种趋锷。 6 ) 嵌入式微处理器重要性增加。 近二十年来，微处理器性能借助微电了工艺和体系结构模7 弘的进步荻甜b 生 地发展，平均每年增长3 0 。微处理器的迅速发展推动了其在嵌入式领域的扁i 州， 目前几乎所有的嵌入式系统都将嵌入式微处理器作为核心部件。在传统设计h 微处理器以芯片的形式使用，本身是不能更改的。随者嵌入式系统采刖系统缴心 片技术，嵌入式微处理器更多的以微处理器核的万式存钥 丁s ( ) c 匕”一卜 7 ) 嵌入式系统复杂性的提高，导致设计过程由传统的个人设计为t ，转变为 有组织的团队设计协同工作。 1 3 嵌入式系统传统设计方法 传统设计方法实际上是一种软硬件分割的设计方法，遵循如图1 1 所乃j | ( j 设计流程，实际上是一种将系统任务软硬件分割的设计方法，即软硬件分离的 设计方法。设计人员首先根据系统的需求定义，完成系统功能描述，确定系统 的规范，然后根据自己的设计经验将系统分割成硬件实现部分和软件实现部分， 即硬件子系统和软件子系统，并确定m 硬件规格指标和软件觇格指标硬仆剐 软件设计人员依据各自指标要求完成相应子系统的设计并完成子系统测试。最 后，设计人员将硬件子系统和软件子系统结合一起进行验证，如果满足系统蛳 范要求，则完成设计。否则将返回功能分割处进行分割调整，相应地调整符f 第1 章绪论 系统的觇格指标，再重复硬件设计、软件设计、验证流程直至完成系统设汁。 需求定义； - _ _ _ _ - 。_ _ - _ - _ _ _ _ 1 _ _ _ _ _ _ _ 。_ - _ _ 。- 。_ _ _ _ - _ - 。一 ! 一 系统规范 l r 一一一功能分割 c 二歹y 弋 ：硬件子系：l 软件子系 ；统规范!统规范 ：一，一 ：一一 ! 一 i 硬件子系! 软件子系1 。统殴；|。统殴；l 图1 1 传统嵌入式系统设计流科 从图1 的设计流程可以看出，传统嵌入式系统设计局限性：t 要自 4 l i51 1 6 l ： 1 ) 软硬件的丌发过程割裂，缺乏沟通。目自订的嵌入式系统力! 设汁t l i 脚j 溉j 、 丌进行，由于异构型系统的软硬件的复杂性，这种设计过程使软硬件刁 乏渊i 1 二； 求转化为卜类约柬，软硬件协同综合的口标函数定义为住满足系统个m ：约爪n ：j 条件下最小化系统总成本。 s o s 方法建立的规划模型较好地刻画了协同综合的各个过程，同时，筷弘 还可以根据具体应用做迸一步扩展，如可通过对输 _ 数扼有效约束的修矿捕 述任务执行过程中允许部分数掘输出的情况。另外，通过。| 入业多牟由助叟酞， 可以刻画任务执行的流水线结构。s o s 乃法的水解2 占粜埘j 矗i 系统软他f | i 之i j ，广i f ：j 最优解集。但由于约束条件多，求解过程中时问外销人，例奠u 刈+ “个91 7 t l fr 务建模，变量达2 7 2 个以及1 0 8 个约束，得到最终解集有5 个解，神：类似s l i n s p a r c 4 4 9 0 平台上运行时间达数小时。在实际嵌入式系统中，系统仟务图r 1 ，仆 往有数十个节点，因此混合整数线性规划方法在具体应用中有很大局限一陆。此 外，s o s 模型中对数据传输的处理与实际嵌入式系统仍有较人入，l 婴放映 在：首先，模型中隐含了任意两个处理问j 以建立通讯 i i 生路的条仆，这n 妃- 、 系统中可能无法满足；其次，通讯链路冲突只是简单描述了在一对处理器之| i i j 的数据传输的可能冲突，而对于使用总线进行数据传输的系统，由j 二多刈处川l 器| u j 的数据传输可能刚刚仔住资源竞争的悄况，刈i 这类系统的她摸1 6 j 婴。：，；、 更多的约束关系式，从而进一步增加求解过程中的复杂度和时| jj l ：销；墩j 1 1 ， 线性规划方法应用于处理所谓多模式的嵌入式系统设计有很大闲难。 2 1 2 启发式算法 启发式方法就是设计者利用自 ! l 的发计经验制定些规则。算；上执i ju j 投 照这些既定的规则快速收敛。现有的启发式方法主要可以分为n 发j 眦。芹 和启发式调度算法。 l 、启发式配置算法 目i ，j ，见十义献的启发式配置算法主要有h y u n o k 在【1 4 】提出的资源配晶 法。h y u n o k 方法是存满足系统忭能约束的要求卜选择系统代价竹：“j 优化| | h y u n o k 方法的基本思想是：首先选择出一个能处理系统全部任务并且成本最低 的处理单元子集，即系统的最低成本实现；然后根据调度结果和h y u n o k 提m 的启发式算法逐步增加可用处理单元，从而得到在满足系统性能约束卜的最低 成本的系统实现。 0 第2 章软硬什协同殴计相关研究 定义三个变量： e m d ( i j ，k ) 2 e t ( i ，j 牛，k 乖) 一e t ( i ，j k ) ； e c i ( i ，j ，k ) = c ( i ，j ，k ) 一c ( i ，j 幸，k ) ： sl a c k = m a k e s p a n c o n s t r a i n t ： e f f = m i n ( e m d s l a c k ) e c i ： i 表示节点， 表示处理器，k 表示系统实现，i 木和k 宰表示最低成本的处：f 1 1 单元和实现，e t 表示执行时间，c 表示成本，e m d 为起期望跨度减小量，e c i 为期望成本增加量，m a k e s p a n 为当前调度跨度，c o n s t r a i n t 为系统性能约束，e f f 为处理单元的效率。 算法的流程如下： l 、选择能完成系统全部任务的最低成本处理单元子集； 2 、利用当前选择的处理单元集合，完成系统调度，得到系统的性能： 3 、比较当前的调度结果( m a k e s p a n ) 和系统设计约束，若满足设计要求转5 ： 4 、对当前配置计算出s l a c k ，对剩余的所有处理单元，计算出每个处理单酣f i 对于每个任务的e m d 和e c i ，再计算出e f f 。e f f 越大说明引入该处珲币 元可以再相对成本增加较小的情况下得到最大的性能提高，更新系统配臀， 转2 ； 5 、按照增加处理引擎的相反规则，从当前子集中去掉部分处理单元，输出结粜。 调度算法的优劣对h y u n o k 的配置算法影响很大。若调度算法的计算复杂 度为o ( s ) ，对于n 任务节点，m 个可用处理单元的系统，其配置算法的复荔鼍嫂， 为o ( ( m n ) 2 s ) 。高效的调度算法是启发式配置算法的关键。 2 、启发式调度算法 软硬件协同设计中，一般都采用基于优先级的启发式凋度算法完成系统渊 度，也就是线性序列调度。调度算法的主要思想是：给任务图中每个仟务按照 某种启发式规则赋一个优先级，把所有的就绪任务按优先级的大小排序，建移 就绪队列，当出现任务竞争时选择就绪队列中的优先级最高的先执行，直到所 有任务全部完成调度。现有的启发式调度算法主要有：g i i b e nc s i h 等提n 勺 g d l 【1 5 】算法、h y u n o k 等提出的b i l 1 4 】算法和邹谊等提出的m u l t i p r i 【1 8 】算 法。 1 ) g d l ( g e n e r a l i z e dd y n 锄i cl e v e l ) 算法 g d l 算法的基本思想是：根据系统任务图的信息确定各个任务诲_ i 的静态 优先级( s l ) ，每次调度时度量就绪队列的任务在不同处理单元上的执行时州以 及与后继任务间通讯开销来修讵s l ，得到就绪队列中的任务相对应不同处理- 巾 元的g d l 。选择g d l 最大的任务一处理单元对，完成该任务的调度。 第2 章软硬f ，l 仂、f 改汁4 f i 义训究 参数定义： s l ( s ) 为其关键路径：所有节点的执行时间之和l ，执行时| j j 驭存所仃处| | ：，j i 擎 二的平局执行时问： d a ( s 。刚表示任务节点s ，所需的全部数捌到达处理单几p 。的域f j i t f ( p i ) 表j ：分配剑处理单几p i 上的所有任务蜮迟允成l j l t l j j ： t ( s 。p j ) 表示任务s 在处理币元p i 卜的最早执行时l 自j t p 1 ) m 抓：d a f p j ) t f ( p ；) ，t ( s hp 1 ) 越小税明s ，和p if h j 的匹配发越高； e ( s i ) 表示所有任务s i 在所有处理单元上的平均执行时间； e ( s ，p j ) 表示任务s 。在处理单元p l 上的执行时| 日j ； ( s 。，p j ) = e ( s ，) 一e ( s 。，p i ) ，( s ，p j ) 越人晚叫s 伍p j 上f l 勺执行时| i i j 越少，n 能越高； g d l 可以修f 为：d l i ( s 。，p j ) = s l ( s ) 一t ( s ，p j ) 十( s hp i ) ；d l i 【s 卜p j ) 越l 、， 说明s 。在p l 上有较早的执行时刻或者较高的执行性能。 f ( s ，s ，p i ) = c + m i n e ( s p k ) ( k j ) ，s 表示s j 所有后绺节点中通信1 1 ：销骷 大的节点，c i ；表示s 和s i 之间的通信开销。f ( s i ，s ，p j ) 越小表示s 。其有最大通f l i 开销的后继节点s 在非p 。上的执行性能越高： d c ( s 。，p j ) = e ( s ) 一m i n e ( s ，p _ i ) ，f ( s i ，s p - ) ，d c ( s i p i ) 表玎一厂s 与p i 之m j 小j i 儿 配度。d l l ( s i ，p i ) 主要考虑了s i 和之恻的匹配，没有考虑后继竹点以及通信jm j 因此g d l 进步修f 为： d l 2 ( s i ，p j ) = d l i ( s ，p 1 ) + d c ( s i ，p j ) ，对于任务s i 计算所有l l j 用处胖巾，c 刈 、j i 的d l 2 值，若最大值对应于处理单元西，则将仟务s i 调度钏一 7 ( j i ) l 钾i j i 同时处理多个就绪任务，可能 f 现多个仟务存同。处理引擎 j 取得极人f r i 晰晴 况。因此，要进一步修话d l 2 。 c ( s ) = d l 2 ( s 。，p j ) m a x d l 2 ( s i ，p k ) ( k j ) ，c 【s ) 表示s 。不能测嫂剑蜮f 处 理单元上“的性能损失，当多个任务存同处理巾元f ：取得极j 价时一伊0 分配c ( s 。) 最大的任务。 g d l ( s i ) = d l 2 ( s i ，p i ) + c ( s j ) ，调度过程r f l ，每次选择g d l 最人l ：! i ，j 处 对于n 个任务节点，m 个处理单尢的系统，每次取3 个仃务求( j i ) i ，i i i g d l 算法的计算复杂度为o ( n 3 十n 2 m ) 。 2 ) b i l ( b e s ti m a g i n a r yl e v e l ) 算法 g d l 方法在调度过程中考虑了每个节点的商接后继节点中通信j 婚j 蛾 大的节点，但是对后继任务以后的任务没有考虑，凶此g d l 力法缺乏全j 耐性。 针对g d l 的缺点，h y u n o k 等提出了b i l 算法。 第2 章软硬什协同殴汁相犬研究 b i l 算法在计算每一个任务的关键路径长度时，考虑了任务问的通信j l ： 销。对f 处理单元p i ，任务s 。的b i l 关键路径长度定义为： b i l ( s i ，p i ) = e ( s i ，p i ) + m a x m i n b i l ( s 。p i ) 】，m i n b i l ( s ，p k ) + c s 】 ( k j ) s ，c i 。定义于g d l 相同。b i l ( s ，p j ) 表示s 。调度到p j 上以后的关键路径k 度。 b i m ( s i ，p j ) = t ( s i ，p j ) + b i l ( s ，p i ) ，t ( s hp j ) 表示任务s i 在处理单元p j ：的最i 。- 执行时间，b i m ( s ，p j ) 表示任务s i 调度到p j 时的系统调度跨度。每个处理单元选 择b i m 值最大的任务执行。对于有m 个可处理单元的系统，尽管可以选择b i m 值最小的处理单元，但是如果系统就绪任务数目k 大于可用处理单元数目m 时， 系统的并行性将增大，此时应把任务在处理单元上的执行性能置于主导地位。 b i m 。( s ，p ) 2b i l ( s i ，p j ) + t ( s i ，p - i ) + e ( s i ，p | ) 水m a x 1 m 一1 ，0 b i m ( s i ，p i ) 表示考虑了系统并行补偿之后任务s i 和之i 白j 的匹配度。如果对 于某个节点有多个处理单元有相同的b i m + 值，则选取其他任务节点b i m + 恤之 和最大的处理单元。 对于有n 个任务，m 个处理单元的系统，b i l 算法的计算复杂度为o ( n 2 m 1 0 9 m ) ，小于g d l 的复杂度。 3 ) m u l t i p r i 调度算法 g d l 和b i l 算法参数繁多，计算复杂，而且都没有考虑总线竞争对调度结 果的影响。为此邹谊等提出了m u l t i p r i 算法。 当两个或多个就绪节点被分配到一个处理器上时，由于对资源的独占性， 就绪节点必须竞争。竞争依据如下多优先级： 1 ) 节点松弛度( i n s t a n c y ) 。i n s t a n c y = m l f t i m e m e f t i m e ，其中m e f t i m e 为最早完成时间，m l f t i m e 为节点最迟完成时间。 2 ) 节点的开始时问( s t i m e ) 。 3 ) 节点的最早完成时间( f t i m e ) 。 4 ) 随机优先级( r a n d ) 。 以上优先级依次由高到低。节点松弛度既考虑了节点的后续节点的结构， 又考虑前驱节点的实际情况，综合了一个节点在整个系统任务图中的位胃信息。 节点松弛度优先级，不会只因为局部的某个节点先达到而先被调度，兼顾的是 系统的整体性能，将松弛度作为多优先级结构中的第一优先级是合理的。节 的开始时间作为优先级是遵循先来先服务的原则，使处理器尽量不空闲。节点 的最早完成时间作为优先级考虑的是先结束的节点可以提前让该处理器空闲， 以供其他任务使用。当自咎3 个优先级一样时，选择随机优先缎。 第2 章软硬仆协使计相天研究 寓发式调度算法利脯任务图本身包含的些 ： 发式信，色、水，ji 导州j 生j _ f l l l 以墩得最优凋度的近似解，扁发式方法运锋效率商f r l 足埘j j ；发一 灿，、 赖犁很高。在协同综合中将此类方法应用于不同系统时，结果 ： = 辛会柯特甘 性和不稳定性。 2 1 3 演化算法 基于演化算法的方法，丰要有d i c k 等提 ”j ；勺基于遗传算： 削向m ( ) g a ( - 法等【9 】，v i d a 等提出的c h a r m e d 方法【1 6 ，d a v e 等提出的c o s y n 力；上l 17l 等。该类算法利用演化计算较强的搜索能力束寻找系统的最f i r l ! ! i l 笛：弄u 州艘。t 谚 类算法能得到比较满意的结果。 1 、基l f 遗传算法的m o g a c 算法 m o g a c 【9 】【4 3 】是由d i c k 提出的一种基于遗传算法的多日标软馊件协m 综 合算法。m o g a c 采用任务流图柬描述嵌入弋系统。为了降f 氐弹：上的馊索。h i j 和搜索难度，m o g a c 采用了分层优化的结构，外坛进行酋c 舀! 串0 j j f 仇，内j ，： 则进行分配串优化。m o g a c 优化的目标包括成本和功耗。算法步骤为： 、系绞仞始化：争成系统仟务。处珲引擎和通苈姿潭 2 、外层配置空间初始化：随机选择处理引擎直至选中的处理引擎能处理所有仟 务节点：随机选择通信资源直至选中的通信资源能完成所有通信 3 、内层分配空间初始化：射每个配置串进行任务分l ! ! i 已，每个任务点， 能订： 到一个处理引擎，每个通信有向边只能分配剑个通信链拔 4 、内层寻优：执行遗传交叉和变异算f ，若不满足内层结火条f - ，继续内j z “ 优 5 、外层寻优：执行遗传操作，外层完成次进化继续内筐了优 6 、条件终止：输出结果 2 、基于s p e a 的c h a e m e d 算7 去 c h a r m e d 【1 6 】是由v i d a 提出的一种基于s p e a ( s t r e n g t h p a r e t o e v o l u 的n a 搿a l g q r i t h m ) 的软硬件协同综合算法。算法的主要框架如图2 ，l 所豕： 第2 章软锲什协同改计卡h 火训究 厂面蕊丽耐 一一一一，一j 一j 模型解析 一j 一 叫m c f a ：任务聚类 一! 叫s p e a ：资源配置 任务分恺 任务调度i 二二二二( 二二 | l 了一 对系统的描述采用和m o g a c 相同的任务流图描述，模型解析为将输入n 勺 任务图数据转化为系统所需的数据结构。m c f a ( m u l t i m o d ec l u s t e r i z a t i o n f u n c t i o na l g o r i t h i l l ) 是文献【4 2 】提出的一种任务节点聚类算法，肖任务图的符 数目增加时，通信( 有向边) 的数目也会随之增大。当很多节点分配到卜川的 处理单元上时，就不得不使用大量的通信资源来实现系统，从而导致系统的实 现成本和处理时l 日j 增大，也使得算法的搜索难度大大增加。m c f af l 卜是为丫降 低算法搜索空间和算法搜索难度而提出的，其主要思想是将任务图中通信节较 大的节点组织成一个较大的节点集合，在处理时把节点集合当作一个肖点术处 理，那么集合中的节点就被分配到同一个处理单元上，而同处理单元上的1 7 点不需要占用通信资源，从而降低了通信成本。经过聚类后的任务图再输入到 s p e a 中进行综合，主要步骤包括：处理引擎和通信资源的配置、任务节点利 通信的分配、任务节点的调度。 s p e a 模块是c h a r m e d 的关键，其目标是找出m c f a 解集的最佳实圳力 法。主要步骤为： 1 、初始化：随机生成二进制初始解的集合，每个解表示节点向处理，) l 擎平1 1 迎亿 边向通信资源的映射。 2 、遗传操作：执行交叉和变异算子，增加执行代数。 3 、适应度评估：计算出每个解的实现代价。 4 、更新解集池：将所有的非支配解拷贝到解集池中。 5 、终止条件：若满足终止，否则继续2 操作。 第2 章软硬件协同殴计相关研究 2 2 软硬件划分的相关方法 在过去大量深入的研究和探索的基础上，软硬件划分的研究l 经取得了 k 大进展，产生出些行之有效的划分方法。但是，在传统的软硬件划分方法t h 系统的属性描述都是基于吲定状态的，然而随着一些新的应用模式的出现，如 视频数据流处理，系统属性中的一些关键参数，如任务的执行时l 日j ，是根捌 0 处理的数据流量的大小而动态变化的，而这一类的应用往往还对时日j 有着史为 严格的约束，因此要求划分算法具有处理动态问题的能力。 半导体技术的进步使得s o c 成为了现实。可重配置逻辑( d r l ) 的出现使 得在线( r u n t i m e ) 配置成为了可能。可重配置计算( r c ) 不但具有软件处理 器的弹性同时也具有硬件协处理器的高效和吞吐量。d r l 的出现同时也给e i 动 化设计领域带来了新的挑战。主要的挑战就是重配置延时，我们必须要最小化 重配置延时使系统的性能能最大化。现有的很多划分和调度算法没有考虑d r l 的特性，具有d r l 的结构需要考虑新的不同的算法。 对于动态划分问题，目前的研究工作并不是很多，文献【4 5 】给出动念软硬什 划分方法。作者在一系列的文献中指出，动念软硬件划分方法可以既节竹j 力托 又提高系统性能。这种简单划分技术有效性主要原因是对多数平台，大多数的 执行时| 且j 只花在几个循环中。而这些循环经常是用少量的代码实现的，这就意 味着在多数情况下，硬件的实现只需要少量的面积。作者给出了适应这种划分 的体系结构。使用了硬件方法来决定哪些软件代码应该由硬件实现。对关键循 环的探测使用了基于硬件的非干扰p r o n l i n g 方法，使用缓存来决定关键区域， 把分支访问和他们的执行频率存储在类似缓存的结构中。文献 4 6 提出了另 种实时重配置方法，通过完整的o n i i n ef e e d b a c km e c h a n i s m ，动态建立p a r t i t i o n i n g s c h e d u l ed a t a b a s e ，通过迭代操作，混合使用u p s p e e d i n g 和u p ，f r e e i n g 两种策略， 在执行速度和系统实现代价两者之问寻找合适的平衡点。义献 4 7 l 提”；j 种 基于软硬件实时再分配的方法，针对系统中时i 白j 消耗最大的循环，对系统的软 硬件映射方案进行重新配置。文献 4 8 提出了一种离散事件的方法柬实现动态 配置，【4 9 】提出了一种基于d p b i l ( d u a lp o p u l a t i o n b a s e di n c r e m e n t a ll e a m i n g j 的动态划分算法。 2 2 1 基于d p b i l 算法的动态划分方法 对称性和互补性是自然界中非常普遍的现象，如生物学中，d n a 分子就包 含两个对称的链，相互缠绕形成个双链。受自然界中这种对称机制的启发， 文献【5 0 】针对动念优化问题提出了一种基于对称机制的p b i l 算法称为【) p i 训 算法。文献 4 9 提出了一种新的动念环境生成方法，并利用d p b i l 算法来斛 儿 第2 章软硬件协同设计相芙研究 动念环境下的软硬件划分。 l 、动念环境生成 为了能更合理的描述动念环境的特点， 4 9 】使用了两个动念舅：境参数：7 乏 化的速度t 和变化的幅度r 。第一个参数t 和环境变化的周期有关，被定义为i q 次变化之问演化算法执行的周期数( 代数) ，即每隔t 代适应度函数发尘变化。 第二个参数r 和变化的幅度相关，定义为二进制模板e ( k ) 0 ，l l ( l 衷j 模饭 长度，即染色体长度) 中“l ”的耿值概率。对于每一个环境变化的周期k = f t 1 ， 用e ( k ) 迭代产生一个新= 进制模板f ( k ) 0 ，1 ) ，l ：f ( k ) = f ( k 一1 ) oe ( k ) 。 对于第一个周期，f ( 1 ) 被初始化为零向量。e ( k ) 在每个新的周期丌始时被随 机初始化，其中包含r l 个“1 ”。“o ”是按位异或操作符f 例如1o1 = o 1oo = 1 o0 0 = 0 ) 在f ( k ) 和e ( k ) 用来改变适应度函数中的t 参数。主要是基于以 下考虑：适应度函数代表了个体对环境的适应程度，改变适应度函数中的t 参 数将改变解空间中适应度函数的分布形态，进而改变个体的评估值，这是埘实 际动念环境更自然的模拟。在具体操作中，f ( k ) 模板是t 参数墩值的杯志模板， 当f ( k ) 中的某位为l ，相应节点的t 参数就取值为t m a x 反之川j 妙1 州ji 参数就取值为t m i n 。e ( k ) 通过按位异或操作翻转f ( k ) 中的标志位，当e ( k ) q r 的某一位为l ， f ( k ) 中相应的标志位就被翻转，反之则不变。山此可以石ir 参数控制着环境变化的幅度，r 越大，e ( k ) 中就有更多的“l ”，f ( k ) 中就有给多 的位被翻转，相应的就有更多的节点的t 参数发生改变，也就意味着环境变化 得越剧烈。 2 、基于d p b i l 的动态划分算法 给定一个长度为l 的概率向量p = ( p 【1 】，p l ) i = 【o 1 1 l 其埘称m 可以被定义为：p f = d u a l ( p ) = ( p 【l 】，p 【l 】) i ，其中p 【i 】：= l - p 【i 】( i ：l l ) 。也就是说这两个向量在解空间中关于中心点对称。 算法的主要步骤如下： 1 ) 初始化两个对称概率向量p 和p ，群体规模，以及符向芾的样本槲梭 配额。 2 ) 分别根据两个向量的样本规模对两个对称向量进行一次采样，产生代 群体，然后计算每个个体的适应度函数，分别从每个概率向量产，j t 的 样本中选出适应度最优的个体。 3 ) 比较这两个最优的个体，选出较优的个，然后按照殴定的步k ，川j ： 生较优个体的向量来学习该个体的概率，同时相应的修j f 另一个向量， 以保持两个向量之间的对称性。 4 ) 修正两个向量的样本规模，将产生第3 步中较优个体的向量的样本规模 第2 擎软慢”协- 同使汁相父 j 丌究 适! 与增犬，但是要保持其对称i 旬量的样本规模配额小低j 改：疋的瞳， 以保汪广扛个体的多样件。 5 ) 如果未达到终止条件，则返( ；1 1 第2 ) 步，循环操作。2 3 软硬什协川改f 工具介绍 2 2 2 离散事件系统的动态配置 软硬件划分和调度可以从几个巧f 司的房自来区分。划分州以分为纠j 牲搜tj 土 本调度块) 和粗粒度( 任务级) 。调度可以分为静念调度和动念渊皮，；鄂念m l 心 就是所有的任务的执行顺序在离线时都已经决定，晰动念调度就是仃务的执f i f 顺序是在线决定的。复杂的嵌入式系统的任务执行顺序是口_ 以动念改变的，比 如控制占主导的系统，这些系统要存不同的情况卜。| _ 作。动念渊j 曼的力法蛳 很少，最小化重配置延时有好几种方法。土要的万泫足重眦一! 颅收技术l - 1 8 l 为了达到在线重配置的目的，【4 8 】将系统描述划分成临时独立片断，称之 为重配置上下文( r e c o n 矗g u r a t i o nc o l l e e x t ) 。这个过程就称为犏时划分( 1 e m p m i p a r t i t i o n i n g ) ，这个也是d r l 提出的一个新的挑战。 该方法分为三个阶段：应用阶段，静念阶段和动态阶段：j 遁川阶段剐? 扎j 阶段处理离散事件类和对象，静态阶段只处理类。应用阶段包括离散事件系统 的描述和设计约束。首先，相互独立的离散事件类必须建立，然后用这蝼类t 。 生相关的对象束描述整个系统，这些对象之间通过事件来通信。个i 打竹刘 来时，对象计算就被激发。 静念阶段