（计算机科学与技术专业论文）soc软硬件协同设计关键技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 集成电路技术的飞速发展，促使了s o c 技术的诞生，从而给集成电路的发展 带来了前所未有的机遇，面对传统集成电路设计方法的不足，系统软硬件协同设 计方法学应运而生。 首先，本文综述了软硬件协同设计方法学的国内外研究现状，并着重综述了 作为软硬件协同设计的核心的系统软硬件划分技术。 其次，论述了目前主要的系统描述模型，并分析了各模型的特点及适用范围， 并以改进了的任务图作为本文的系统描述模型。 再次，我们深入研究了遗传算法( g a ) 和粒子群优化( p s o ) 算法这两种软硬件划 分方法，并提出了基于粒子群优化与免疫克隆算法相融合( p s o i c ) 的软硬件划分方 法。通过三种软硬件划分方法的对比，可见我们提出的p s o i c 算法则能够很好的 进行划分时间和划分质量的折中，是一种有效的软硬件划分方法。 最后，我们对访存控制器和p d a 手机平台音频、视频发放子系统进行了软硬 件划分。在对访存控制器进行软硬件划分的过程中，着重对访存请求的时序关系 进行了分析，并对访存控制器进行了总体设计，然后对访存控制器进行基于i p 核 的软硬件划分，分别采用g a 、p s o 算法和p s o i c 算法实现划分。在对访存控制 器的访存调度模块的研究中，提出了基于优先级的访存调度算法和基于预测的自 适应访存调度算法，分别使用随机访存地址序列和s p e c 2 0 0 0 测试集中部分程序的 访存地址序列进行测试，均取得了很好的调度效果。在论述p d a 手机平台的音频 和视频发放子系统的软硬件划分的过程中，我们分别采用了g a 、p s o 算法和 p s o i c 算法实现软硬件划分。在使用g a 进行软硬件划分时，适应度函数方面我 们采用了双适应度个体评价模式，通过与单适应度个体评价模式的对比，发现采 用双适应度评价模式比单适应度模式提高了收敛速度，降低了结果发散的次数。 主题词：软硬件协同设计，软硬件划分，遗传算法，粒子群优化算法，p $ o i c 算法，访存调度 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t p a c t w i n lt h ed e v e l o p m e n to fi n t e g r a t e dc i r c u i t ( i c ) ，t h et e c h n i q u eo fs o cc o m e so u t n l i sg i v e sag r e a to p p o r t u n i t yt ot h ed e v e l o p m e n to fi c f o rt h et r a d i t i o n a ld e s i g n m e t h o do fl ch a sl o t so fs h o r t a g e ，h a r d w a r e s o f t w a r ec o d e s i g nc o m e so u tn a t u r a l l y i nt h i sp a p e r , w ef i r s t l ys u m m a r i z et h er e s e a r c ha c t u a l i t yo fh a r d w a r e s o f t w a r e c o d e s i g n , a n dm a i n l y t a l ka b o u tc o r e t e c h n i q u e o fh a r d w a r e s o f t w a r e c o d 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 t h e nw ei n t r o d u c et h em a i nd e s c r i p t i o nm o d e lo fs y s t e m ，a n da n a l y z et h e c h a r a c t e r sa n da p p l y i n ga r e ao fe v e r ym o d e l w eu s em o d i f i e dt a s kg r a p ha so r rs y s t e m m o d e l d e e p l yr e s e a r c hi su s e dt og e n e t i ca l g o r i t h ma n dp s oa l g o r i t h m 仲e ya r eb o t h 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 ga l g o r i t h m s ) t h e n w e p r o p o s e an e w 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 ga l g o r i t h m - - p s o i ca l g o r i t h m c o m p a r i n g 、加t l lt h e o t h e rt w oa l g o r i t h m s ，p s o - i ca l g o r i t h mc a ng e tb e t t e rt r a d e o f fb e t w e e np a r t i t i o n i n g t i m ea n dp a r t i t i o n i n gq u a l i t y s oo u ra l g o r i t h mi sa l le f f e c t i v ea l g o r i t h m t h i sp a p e ra l s og i v e st w op a r t i t i o n i n ge x a m p l e s - - m e m o r ya c c e s sc o n t r o l l e ra n d a u d i of r e q u e n c y v i d e of r e q u e n c ys e n d i n ga n dg e t t i n gs u b s y s t e mb a s e do np d a m o b i l et e l e p h o n e i nt h ep r o c e s so fm e m o r ya c c e s sc o n t r o l l e rp a r t i t i o n i n g ，w em a i n l y t a l ka b o u tt i m i n gr e l a t i o n s h i pb e t w e e na c c e s sr e q u e s t s ，c o l l e c t i v i t yd e s i g no fm e m o r y a c c e s sc o n t r o l l e ra n dp a r t i t i o n i n gb a s e do ni pc o r e n l ep a r t i t i o n i n gm e t h o d sa l eg a ， p s oa l g o r i t h m ，a n dp s o - i ca l g o r i t h m w em a k ed e e pr e s e a r c ho na c c e s ss c h e d u l i n g m o d u l ew h i c hi st h ec o r eo fm e m o r ya c c e s sc o n t r o l l e r ，a n dp r o p o s et w on e w s c h e d u l i n ga l g o r i t h m s - - p r i o r i t yb a s e ds c h e d u l i n ga l g o r i t h ma n da n t i c i p a t e _ b a s e d s e l f - a d a p t i v e _ s c h e d u l i n ga l g o r i t h m w h e nu s i n gs t o c h a s t i ca d d r e s ss e q u e n c e sa n d t h e a d d r e s ss e q u e n c e so fs p e c 2 0 0 0t e s tp r o g r a m st ot e s t , w eg e te x c e l l e n tr e s u l t s t h e nw e u s eg a ，p s oa l g o r i t h m ，a n dp s o i ca l g o r i t h mt op a r t i t i o n i n ga u d i of r e q u e n c y v i d e of r e q u e n c ys e n d i n ga n dg e t t i n gs u b s y s t e mb a s e do np d am o b i l et e l e p h o n e t h e e v a l u a t i o no fp a r t i t i o n i n gr e s u l ti sf i t n e s sf u n c t i o n i nt h ep r o c e s so fu s i n gg at o p a r t i t i o n i n g ，w eu s ed o u b l ef i t n e s se v a l u a t i o ns t r a t e g y c o m p a r i n gw i t hs i n g l ef i t n e s s e v a l u a t i o ns t r a t e g y ，t h ep r i o ro n ec a ne n h a n c et h es p e e do fc o n s t r i n g e n c ya n dr e d u c et h e e m a n a t i v et i m e so ft h er e s u l t k e yw o r d s ：h a r d w a r e s o f t w a r ec o d 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 ca l g o r i t h m ，p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，p s o i ca l g o r i t h m 。 a c c e s ss c h e d u l i n g 第i i 页 国防科学技术大学研究生院硕士学位论文 表3 1 表3 2 表3 3 表3 3 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表4 9 表4 1 0 表4 1 1 表4 1 2 表4 1 3 表4 1 4 表4 1 5 表4 1 6 表4 1 7 表4 1 8 表4 1 9 表5 1 表 表 表 表 2 3 4 5 表5 6 表目录 各p e 成本及运行时间2 3 g a 运行结果2 4 p s o 算法运行结果2 4 p s o i c 算法运行结果2 4 相邻两个访存请求之间的最小等待时间间隔( t ) 3 0 两个访存请求关系分类3 5 六种三个访存请求之间的关系。3 6 部分调度序列连续两个访存请求关系统计3 6 三个连续访存请求关系统计3 7 对称双通道r a n k 的地址映射策略4 2 不同调度算法下各测试程序访存序列的处理时间( t ) 。4 2 两种调度算法对各访存序列的优化效果( t ) 4 3 不同测试程序下各调度算法的运行时间( s ) 4 3 各s p e c n 试程序中r e a d 和w r i t e 请求数目分类统计4 3 访存序列中连续两个同类型访存请求的数目4 4 访存序列中各体访存请求数目4 4 访存序列中连续两个同体同行r - _ r 和w 数目4 5 基于预测的自适应访存调度算法不同m 值下的优化结果( t ) 4 6 各功能模块对应的i p 核及i p 核性能参数4 8 基于g a 的访存控制器划分结果4 9 基于p s o 算法的访存控制器划分结果5 0 基于p s o i c 算法的访存控制器划分结果5 0 三种软硬件划分算法划分效果对比5 0 各功能模块对应软件构件及i p 核性能参数表5 3 g a 划分结果5 6 不同适应度函数下g a 各性能各对比5 6 p s o 算法划分结果5 7 p s o i c 算法划分结果5 8 三种软硬件划分算法性能对比5 8 第1 v 页 国防科学技术大学研究生院硕士学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图 图 图 图 2 3 4 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图目录 软硬件协同设计流程2 有限状态自动机示例图8 多项式! 二笠的数据流图一8 c p e t r i 网示例图一9 任务图示例图9 任务图变换示例图。1 0 目标结构图1 1 遗传算法流程图。13 个体编码1 3 交叉过程图l5 变异操作过程图。l6 计算任务图运行时间的算法伪码1 7 p s o i c 算法流程图2 0 克隆操作图21 超变异操作图21 任务图测试实例图2 3 实验中的改进任务图2 3 三种算法平均系统运行时间对比曲线2 5 三种算法平均收敛代数对比曲线2 5 三种算法平均划分时间对比曲线2 5 d d r 2 函r j 气m 与d d rs d r a m l 匕较2 7 d d r 2s d f 乙蝴c e l l 结构示意图2 9 d d r 2k ) r a m 结构图。2 9 d d r 2 访存控制器结构图31 交叉操作过程3 4 变异操作过程3 4 经g a 调度的请求序列的处理时间3 5 连续两个请求1 2 种关系所占的平均比重3 7 连续三个访存请求6 种关系所占的平均比重3 8 基于优先级的访存调度算法3 9 各调度算法调度结果对比曲线4 0 第v 页 国防科学技术大学研究生院硕士学位论文 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图5 1 图5 2 两种调度算法运行时间对比4 0 s i m p l e s c a l a r i 具集结构4 1 基于预测的自适应访存调度算法4 6 三种访存调度算法优化效果对比4 7 p d a 手机平台视频、音频发放子系统5 2 p s o 软硬件划分算法伪码5 7 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：墨q 筮亟佳迹回遮进去链技苤盈窀 学位论文作者签名： 舡牛 b 翔：籼吁每| 2 其蕊b 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：墨鳗敦亟往迹回遮i 士羞毽茧盔盟究 学位论文作者签名： 作者指导教师签名： 日期：山哆年3 月厢 日期：】唧7 年，2 月谚日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景和意义 在过去的3 0 年中，集成电路几乎就是遵循着m o o r e 定律的发展，集成度平均 每1 8 个月翻一番，这样的发展速度使将一个计算机系统集成到一个芯片上变成了 现实，即诞生了s o c ( s y s t e m - o n - a - c h i p ) 技术。传统的集成电路设计基本上属于硬 件设计的范畴，而在s o c 设计中，设计者必须面对新的挑战，不仅要考虑复杂的 硬件逻辑设计，而且要考虑软件设计，所以采用传统的r t l 设计方法对s o c 进行 设计将导致诸多的错误与困难。 1 1 1s o c 技术 随着微电子技术的发展，芯片的集成度也越来越高，系统芯片( s o c ) 的诞生已 是必然的发展趋势。s o c 可以将微处理器、存储器、i o 设备等硬件组成单元集成 到单个芯片上，将过去由几个芯片共同完成的功能集成到一个芯片来完成，但是 s o c 不是原系统各个芯片功能的简单叠加，而是对整个系统功能与性能的整合， 在满足系统功能要求的前提下提高系统的综合性能。s o c 技术缩小了系统的体积 与重量，为其广泛应用奠定了良好的基础；降低了板级系统s o b ( s y s t e m0 1 1b o a r d ) 中芯片与芯片之间的数据传输延迟，从而提高了系统的性能；突出设计的重用性， 从而提高了设计效率，缩短了产品面市时间，提高产品的竞争力。因此s o c 以其 集成度高、体积小、功耗低、可靠性高、产品面市周期短等优点得到了越来越广 泛地应用，并且逐渐成为当前集成电路设计的主流技术。 对于s o c 的确切形式划定义并没有一致的结论，通常我们认为一个集成电路 芯片具有以下5 个特性我们就认为它是s o c ： ( 1 ) 实现复杂系统功能的v l s i 。能在单一芯片上实现存储、处理和i o 等多种 功能； ( 2 ) 采用超深亚微米工艺技术。特征尺寸一般都在o 1 8 1 a m 以下，工艺技术难度 大，需要考虑因工艺加工线宽的减少而带来的互连、串扰等影响； ( 3 ) 使用一个或多个嵌入式微处理器或数字信号处理器，完成某一特定领域或 特殊任务的功能； ( 4 ) 具备外部对芯片进行编程的功能，从而定制部分应用程序软件，以满足应 用的特殊需求； ( 5 ) 主要采用第三方i p 核或已有的模块进行设计，利用重用技术缩短设计周期， 降低设计复杂性； 第1 页 国防科学技术大学研究生院硕士学位论文 鉴于上述s o c 的特性，我们发现在对s o c 进行设计时采用传统的r t l 设计方 法已经不再适用，这样软硬件协同设计便应运而生。 1 1 2 软硬件协同设计 针对传统设计方法的不足，研究者们开始探索新的集成电路设计方法，软硬 件协同设计方法学淡入人们的视野。软硬件协同设计方法学的研究始于第一届 i n t e r n a t i o n a lw o r k s h o po nh a r d w a r e s o f t w a r ec o d e s i g n 会议，此次会议上软硬件协 同设计方法学被正式提出，从而标志着软硬件协同设计领域的正式确立。 软硬件协同设计不仅是一种新的设计技术，还是一门新的设计方法学，其核 心问题就是在设计过程中沟通软件设计和硬件设计，克服传统设计方法中这两部 分过早分离引起的弊端。为了实现这一目标，我们在系统级的抽象层次上对系统 进行描述，并在设计的各个阶段，包括系统软硬件划分、软硬件综合、协同验证 等部分不断的进行协同，力求及早发现设计错误，合理平衡系统功能、成本、功 耗等相关因子，达到系统高效工作的目的，具体的软硬件协同设计流程如图1 2 所 示，主要的设计过程有系统模型描述、系统软硬件划分、协同验证和设计实现。 系统模型描述就是采用抽象的、形式化的方法描述系统：系统软硬件划分就把系 统的功能分别指派到目标结构的软件部分和硬件部分；协同验证主要是为了检验 系统的设计错误，并及时修正；设计实现就是对设计结果进行编译综合。 同传统设计方法相比，软硬件协同设计提高了设计抽象的层次，拓展了设计 覆盖的范围，有利于提高设计质量，缩短设计周期。 图1 1 软硬件协同设计流程 1 2 软硬件协同设计研究现状 软硬件协同设计作为- - f - j 新的设计方法学，一经提出就得到了国内外相关研 第2 页 国防科学技术大学研究生院硕士学位论文 究领域的高度关注，经过近2 0 年的研究，国外国内相关研究机构业已取得很多研 究成果，为进一步对该方法学进行研究奠定了良好的基础。与此同时，软硬件协 同设计方法学作为一个新的研究领域，尚处在理论研究和试验性应用阶段，若要 普遍的应用到商业领域中，该设计技术尚需进步发展与完善。 1 - 2 。1 国外研究现状 对软硬件协同设计的研究，国外相对国内来说起步较早，很多科研机构和学 校都成立了专门的研究小组。经过近2 0 年的研究，到目前为止，己经研制出了多 种针对传统嵌入式系统和基于s o c 的嵌入式系统软硬件协同设计原型系统和环 境。 美国斯坦福大学的g u p t a 等研究者经过不懈的努力，开发出了软硬件协同设 计工具v u l c a n t l l 。该系统基于o l y m p u s 开发，采用硬件描述语言h a r d w a r ec 进 行系统模型的描述，并将h a r d w a r ec 描述编译为控制数据流图，并作为综合工具 的内部表示形式。- 儿c a n 中采用基于贪婪算法的硬件协同综合，将可转换为软 件实现的部分从硬件描述中逐步划分出来，v u l c a n 可以看作是考虑了软件因素 的高层综合工具。 s o s 系统是由加利福尼亚大学的p r a k a s h 和p a r k e r 等人研制开发的最早的软硬 件协同设计系统之一【2 】，该系统采用混合线性规划方法实现系统综合，原理简单， 但是运行速度较慢，不适合大规模系统。s o s 系统还可以综合任意多处理器拓扑 结构，实现多个处理器上的调度任务。s o s 系统虽然有一些设计缺陷，但仍然为 软硬件协同设计方法学的深入研究做出了一定的贡献。 除了对整体软硬件协同设计方法学的研究外，还有一些机构和研究人员对软 硬件协同设计中一些关键技术进行了研究，也取得了一定的成果，进一步丰富了 软硬件协同设计方法学。其中，最热点的研究当属对系统软硬件划分问题的研究， 比较有代表性的划分方法有： ( 1 ) 规划类算法：主要有p v k n u d s e n 等提出的基于动态规划的软硬件划分算 法 3 1 、b e n d e r 等人提出的基于混合整数线性规划( m i l p ) 的分布式系统软硬件划 分算法1 4 等，这类算法原理简单，能得到最优解，但是计算复杂度高，并且随问题 规模的扩大时间耗费程指数增长； ( 2 ) 启发式搜索算法：主要有瑞典l i n k o p i n g 大学的e l e s 等人采用禁忌搜索和 模拟退火两种方法进行的软硬件划分1 5 1 、p e t e r 等人使用遗传算法进行系统的软硬 件划分 6 1 、a b h a t t a c h a r y a 等提出了使用粒子群算法进行系统软硬件划分【_ 7 1 ，划分 得结果虽然没有得到最优解，而是近似最优解，但是采用启发式搜索算法进行软 硬件划分的时间却大大降低，在解决大规模问题时具有更大的优势； 第3 页 国防科学技术大学研究生院硕士学位论文 ( 3 ) 构造式算法：p o t k o n j a k 和r a b a e y 提出的类似经典任务指派问题的a s i c 选 择算法【8 1 、d a v e 等人针对多周期分布式系统的经典协同综合问题提出的算法【9 】【1 0 】， 使用这种方法进行系统软硬件划分得到是近似最优解，并且求解效率较高，但是 构造启发式规则较困难； 1 2 2 国内研究现状 受国外研究热潮的影响，近些年来，国内一些院校和科研机构也开始对软硬 件协同设计方法学和关键技术展开研究，主要的研究有： 东北大学计算机软件国家工程研究中心在嵌入式医疗电子设备的研制过程 中，引入了软硬件协同设计方法学，并对嵌入式系统软件开发方法、软硬件协同 仿真验证技术进行了一定的研究【1 1 1 ，最后研制出面向微控制器的嵌入式软件虚拟 开发环境。北京大学开发了j b c o d e s 软硬件协同设计平台1 1 2 1 ，该平台是基于1 6 位j b c o r e 微处理器核设计的，其中的重要研究成果是可重定向目标的编译器和 可配置的微处理器软核。国防科技大学依靠其已建立的仿真开发平台，开发了面 向嵌入式微处理器虚拟原型v c p u 的并行设计环境y h c d e ( 4 6 ) t 1 3 】，其中的软硬 件协同综合问题是采用遗传算法解决的。y h c d e ( 4 6 ) 支持嵌入式微处理器的指令 集仿真与建模。 另外，复旦大学、武汉大学等相关单位也进行了相应的研究。关于软硬件协 同设计关键技术的研究，也是主要集中在软硬件划分方法上，主要有东南大学的 彭艺频提出基于关键路径和面积预测的软硬件划分方法1 1 4 1 、国防科技大学的熊志 辉等提出的遗传算法和蚂蚁算法动态融合的软硬件划分算法【l5 1 、桂林电子科技大 学的黄源提出的基于时间p e t r i 网的嵌入式系统软硬件划分方法【l 酬、哈尔滨工业大 学的马天义等提出的基于神经网络的禁忌搜索软硬件划分算法【l7 】等，此外还有许 多相应的改进算法。 综上国内外关于软硬件协同设计的研究，虽然取得了一定成果，但是研究理 论仍未成熟，仍处于发展阶段。伴随着s o c 技术的大量应用，传统的集成电路设 计方法将面临更多的困难与挑战。鉴于此，如何在s o c 设计的各个环节同步的考 虑和权衡软硬件的功耗、成本、时间等约束因子，最大程度的优化系统结构，是 我们必须面临和解决得问题，所以研究软硬件协同设计具有紧迫而重要的现实意 义。 1 3 课题研究目标及主要工作 作为系统软硬件协同设计核心部分的软硬件划分，一直以来都是人们研究的 热点。为了更好的平衡s o c 系统软硬件之间的各性能参数，我们尝试探索新的软 第4 页 国防科学技术大学研究生院硕士学位论文 硬件划分算法。此类算法不仅要能够更好的完成系统划分，提高系统的整体性能， 而且具有更理想的划分速度和收敛性。 本文的主要工作有： ( 1 ) 系统软硬件划分模型论述。列举了其中常用的模型，包括离散事件模型、 有限状态自动机模型、数据流图模型、p e t r i 网模型和任务图模型，并分别分析了 各模型的特点与适用范围，并采用改进的任务图模型作为本文中软硬件划分的问 题描述模型。 ( 2 ) 深入的研究了遗传算法( g a ) 和粒子群优化( v s o ) 算法这两种软硬件划分算 法，并提出了粒子群优化与免疫克隆相融合( p s o i c ) 的软硬件划分算法。实验结果 显示p s o i c 算法能够在划分时间和划分质量之间进行很好的折中，较g a 能够有 效的降低划分时间，较p s o 能够提高划分质量，是一种有效的软硬件划分算法。 ( 3 ) 访存控制器软硬件划分。在对访存控制器进行划分的过程中，我们首先对 d d r 2s d r a m 访存请求的时序约束进行了深入分析。其次对访存控制器进行了总 体设计，在访存调度模块的研究中，主要对访存调度算法进行了研究，提出了基 于优先级( p r i o r i t yb a s e da c c e s ss c h e d u l i n g p b a s ) 访存调度算法和基于预测的自适 应访存调度( a n t i c i p a t eb a s e ds e l f - a d a p t i v ea c c e s ss c h e d u l i n g a b s a a s ) 算法。最后 对访存控制器进行基于i p 核的软硬件划分，分别采用了g a 、p s o 算法和p s o i c 算法进行实现，划分结果进一步证明了p s o i c 算法的有效性。 ( 4 ) p d a 手机平台音频、视频发放子系统软硬件划分。我们分别使用了g a 、 p s o 算法和p s o i c 算法进行了该系统的软硬件划分实现，划分结果再次证明了 p s o i c 算法的有效性。在g a 进行软硬件划分实现时，我们采用了双适应度个体 评价模式，较单适应度评价模式，提高了划分算法的收敛速度，降低了结果发散 的次数，是一种有效的个体评估方法。 1 4 论文结构 本文共分六章，各章的组织如下： 第一章概述了课题背景、研究现状与主要工作。 第二章对软硬件协同设计中的系统描述模型进行了论述。 第三章将任务图作为s o c 系统的描述模型，并运用遗传算法、粒子群优 化算法和粒子群优化与免疫克隆相融合的算法进行软硬件划分模拟，并分 析各算法的优点与不足。 第四章对访存控制器分别采用了g a 、p s o 和p s o i c 算法进行s o c 软硬 件划分实现；对访存控制器的访存调度策略进行了分析研究，分别提出了 基于优先级的访存调度算法和基于预测的自适应访存调度算法。 第5 页 国防科学技术大学研究生院硕士学位论文 第五章分别采用g a 、p s o 和p s o i c 算法对p d a 手机平台的音频和视频 的发方子系统进行了s o c 软硬件划分实现。在采用g a 实现时，我们提出 了基于双适度的个体评价模式。 第六章总结全文，并阐述了需要进一步开展的工作。 第6 页 国防科学技术大学研究生院硕士学位论文 第二章s o c 软硬件协同设计的系统描述模型 2 1 系统描述模型 系统描述是s o c 软硬件协同设计的第一步，它对最后实现的设计结果有着至 关重要的影响，在一定程度上决定了s o c 系统设计过程中软硬件划分、高层综合 以致整个目标s o c 系统的质量，并且对i p 的可重用性具有重要的影响。那么，采 用什么样的模型进行系统描述才能取得较好的设计结果呢? 答案不是唯一，具体 采用何种模型，主要看所采用的模型能否准确而简洁地描述所要实现的系统功能、 合理体现系统设计约束、能否在不涉及具体实现的情况下进行仿真等。下面就几 种常见的系统描述模型，论述其特点及适用范围。 2 1 1 离散事件模型 使用离散事件模型对系统进行建模，就是将系统描述为由一个离散事件集合 驱动的系统【l 引，某时刻一个事件的发生会触发相应的功能模块，而该功能模块的 执行又会产生某一时刻发生的事件，以此方式来实现整个系统的功能。这些离散 事件有着严格的执行顺序，按着系统设定的全局时间戳，依次触发相应的功能模 块。可见，时间是离散事件模型不可或缺的部分。目前，典型的离散事件仿真器 都需要维护一个全局事件队列，它按照事件的时间戳对事件进行排序，正是基于 这一点，如果一个系统的事件较多且变化较快，那么事件的重排序时间耗费较大， 降低了模拟效率，因此该模型只适合描述事件较少且变化较缓慢的系统。 2 1 2 有限状态自动机模型 有限状态自动机模型是将系统描述为一系列状态的集合，这些状态不断的互 相转换以实现系统的各种功能，在任何时刻系统只处于状态集合中的一种状态 f 1 9 】【2 0 】。目前，有限状态自动机模型得到了广泛而深入的研究，主要有状态转移图 和状态转移表两种方式来建立有限状态自动机，并有着完整的数学模型和理论分 析方法。 有限状态自动机主要由三部分构成：一个有限状态集合r ；一个有限的输入集 合，；变迁函数c 伊j ，i ) = r 2 。变迁函数c f ，是为了完成给定状态和输入条件下的状 态转换。下面给出一个简单的有限状态自动机事例，如图2 1 所示。其中，j 、力 和，3 是三个状态，f f ，f 2 和乃是三个输入，状态，j 和输入f j 在变迁函数c ( r l ，i o 的作用下转变为状态心。 第7 页 国防科学技术大学研究生院硕士学位论文 有限状态机最大的优点就是简单易懂，但是每个时刻系统能且只能处在一个 状态，限制了其在并发系统中的应用，并且随着系统状态的增加，会出现“状态 爆炸”问题。 图2 1 有限状态自动机示例图 2 1 3 数据流图模型 数据流图是程序设计时常采用的一种简单模型【2 l 】，节点表示程序中的操作， 根据给定数据输入得到相应的数据输出，有向边表示数据，其方向表示数据流向。 在数据流图中，只有节点的所有输入都准备完毕，相应的操作才会被触发，才会 得到相应的输出，并作为下一节点的输入。图2 2 给出一个简单多项式阳2 + b 2 ) c 求解的数据流图，初始输入为口、b 和c ，节点由运算符号构成。 图2 2 多项式旦! 笙的数据流图 c 由图2 2 我们可以很容易的发现数据流图具有很好的并发性，并且对数据处理 和转换具有很好的描述性，但是表示控制结构的能力有限。 2 1 4p e t r i 网模型 p e t r i 网是一种适用于多种系统的形式化描述模型【2 2 1 ，具有良好的数学基础， 目前已被应用到诸多领域。这里我们将p e t r i 网定义为三元组尸肛僻z 圳，其中， 尸n r = 驴，p u t 驴，p 表示位置的集合，即尸= 加，印，州，丁表示迁移 的集合，即皿m ，t 2 ，纠，彳表示有向弧的集合，a = p xt u t xp 。 在p e t r i 网的位置节点中可能零个或多个令牌，这些令牌可以通过触发相应的 第8 页 国防科学技术大学研究生院硕士学位论文 迁移使令牌在位置节点不断的变化，表征着系统状态的变化。迁移的触法是有条 件的，其所有输入位置节点都至少包含一个令牌才能触发该迁移。一个迁移被触 发，其所有输出位置节点都对应的得到一个令牌。图2 3 给出了一个简单的p e t r i 示例，其中圆节点表示位置节点，方节点表示迁移节点，圆节点中有t 表示该节 点已持有令牌。 aop 2 的 白t l曲t 2 p 5oo 一 曲t 3 o p 7 图2 3p e l r i 网示例图 p e t r i 网易于描述系统的并发、竞争、同步等特性，对评价和改进系统有着良 好的效果。目前，p e t r i 网模型已经应用到多种系统的建模和电子设计的辅助验证 中。 2 1 5 任务图模型 任务图是一种带权有向无环图( d a g ) 1 3 】，可形式化定义为g = 形习，其中v 代 表任务图中节点的集合，e 代表任务图中边的集合，吲表示任务图中节点的数目， 蚓表示边的数目。任务图中的节点1 ，。表示任务z ，边p ，表示节点m 与，之间的依赖 关系，且数据流向是单向的，边上的权值表示节点间的数据通信流量。任务图中 可以有多个始节点和终节点。一个简单任务图如图2 4 所示，共1 1 个节点和1 3 条 边，其中始节点1 个，终节点3 个，终节点有时间限制d e a d l i n e 。 图2 4 任务图示例图 第9 页 国防科学技术大学研究生院硕士学位论文 任务图表述直观，易于理解，任务图中各节点间具有明确的数据依赖关系， 并且具有一定的时间约束能力，非常适合实时系统的设计描述。 2 2 改进的任务图描述模型 建立s o c 系统模型的基本原则是该模型应该能有效支持后续的软硬件划分、 综合与软硬件协同仿真，支持s o c 系统与i p 核的重用。本章我们假设研究的是实 时信息处理s o c 系统，设计约束仅为时间约束。系统的主要操作为计算操作，控 制操作较少，这样上述的这些系统描述模型中，任务图模型是比较合适的模型选 择。任务图中的每一个节点代表s o c 系统的一个功能模块，所有节点的集合组成 了一个s o c 系统。 为了便于计算任务图运行时间，我们对初始任务图进行改进。一方面使每个 任务图只有一个始节点和一个终节点，新增加的始节点和终结点对应的处理时间 为0 ，产生的边的通信开销也为0 。另一方面，我们忽略节点间的通信开销。具体 改变过程如图2 5 所示。其中d e a d l i n e 为d e a d l i n e l 和d e a d l i n e 2 中较大者的值。 图2 5 任务图变换示例图 2 3 本章小结 本章首先主要对s o c 系统软硬件划分模型进行了论述，列举了其中常用的模 型，有离散事件模型、有限状态自动机模型、数据流图模型、p e t r i 网模型和任务 图模型，并分别分析了各模型的特点与适用范围。其次我们论述将改进了的任务 图作为本文的系统描述模型，改进后的任务图只有一个始节点和一个终节点，并 且忽略通信开销，这样更方便后续s o c 系统的软硬件划分工作。 第1 0 页 国防科学技术大学研究生院硕士学位论文 第三章s o c 软硬件划分模拟 在基于s o c 的嵌入式系统设计中，系统级设计阶段的软硬件划分过程十分重 要，这一过程决定了系统的哪些功能由硬件来实现，哪些功能由软件来实现，由 软件实现的功能单元具有较好的灵活性，但是性能比较低，而由硬件实现的功能 单元性能较高但是灵活性差、成本高，因此软硬件划分最终决定能否实现一个最 优的s o c 系统。软硬件划分问题是一个n p - h a r d 问题。本节中以任务图作为s o c 式系统的描述模型，分别运用遗传算法( g e n e t i ca l g o r i t h m g a ) 和粒子群优化 ( p a r t i c l es w a r mo p t i m i z a t i o n - p s o ) 算法进行了系统软硬件划分的模拟，并且提出了 基于粒子群优化和免疫克隆算法相融合( p a r t i c l es w a r mo p t i m i z a t i o na n di m m u n e c l o n e p s o i c ) 的划分算法。p s o i c 算法能够在划分时间和划分质量之间进行很好 的折中，较g a 能够有效的降低划分时间，较p s o 能够提高划分质量，是一种有 效的软硬件划分算法。 3 1 软硬件划分问题描述 定义1 ：片为系统功能u 中由硬件实现的功能单元的集合，s 为系统功能u 中 由软件实现的功能单元的集合，且日u s = u ，h n s = 痧。 软硬件划分就是在满足系统各项性能约束的前提下，把系统的功能划分到相 应的软件功能单元集合s 和硬件功能单元集合日，使系统的各项性能达到最佳或 近似最佳。 3 2 目标结构及目标函数 为了便于进行软硬件划分的模拟，我们采用任务图作为系统描述模型，每个 任务图表示一个s o c 软硬件划分系统，每一个任务节点代表一个功能单元。 系统的目标结构：共享主存的多机系统，如图3 i 所示。处理单元( 尸四分别是 通用处理器、a s i c 或f p g a 器件实现，共享存储器系统。 通信假设：所有通信均采用共享内存的方式，通信开销为常值。 图3 1 目标结构图 为了便于后续部分的表述，我们做如下定义： 第l l 页 国防科学技术大学研究生院硕士学位论文 定义2 ：系统成本( c o s t ( s ) ) 是指经过划分后的任务图中