（信息与通信工程专业论文）基于模拟退火算法的可重构计算系统软硬件划分方法研究.pdf

r e s e a r c ho nh w s wp a r t i t i o n i n gf o rr e c o n n g u r a b l ec o m p u t i n g s y s t e mb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h m b y x i a op i n g b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n s y s t e mo fi n f o r m a t i o na n dc o m m u n i c a t i o n i nt h e g r a d u a t es c h 0 0 1 o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rx uc h e n g m a y ，2 0 11 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 高乎 e l 期：1 , p 1 1 年，月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 日期：b 7 年j 月刀日 日期：沙i7 年月日 吸乎、f 誊 a园多11 名名签签 者师作导 摹于模拟退火算法的可重构计算系统软硬件划分方法研究 摘要 可重构计算系统通常由通用处理器和可编程器件组成，同时拥有受限的硬件 资源和软件资源。任务可以被划分到软件或者硬件上执行，但两者将在任务执行 时间、功耗等方面产生显著的差别。为了充分利用硬件资源并使系统满足应用场 景需求，需要对任务进行有效的软硬件划分。软硬件划分是当前可重构计算系统 设计中的关键步骤和研究热点。 软硬件划分为组合优化问题，已经被证明为n p 问题，目前的研究主要是基于 启发式算法来解决此类问题，研究的重点在于提高算法的收敛速度和解的质量。 因此本文在两种任务集规模下，提出改进的启发式划分算法来提高算法收敛速度 和解质量。 在中小规模任务集的情况下，使用改进的模拟退火算法进行软硬件划分。模 拟退火算法是解决软硬件划分问题常用的启发式算法，但是其收敛速度过慢且解 的质量有待提高。本文通过改进算法的扰动模型和退火进度来改进其收敛速度慢 的问题。针对算法存在解质量较差的问题，本文在总结现有代价函数的基础上提 出一种新的代价函数计算方法。该方法对算法在解空间上的搜索方向进行引导， 避免了搜索的盲目性，从而使算法能快速搜索到近似最优解，提高划分质量。 在大规模任务集的情况下，结合改进的贪心算法和模拟退火算法对软硬件划 分进行了研究。在大任务集下，单纯使用一种启发式算法会导致算法运行时间增 加及划分质量下降。针对存在的上述问题，在文中首先使用改进的贪心算法对任 务集进行初始化。贪心算法时间复杂度较低且容易实现，输出的解能接近全局近 似最优解所在区域。然后使用改进的模拟退火算法，在初始化的基础上继续进行 搜索。模拟退火算法全局搜索能力较强，能最终获得全局近似最优解。 为验证本文算法，使用通用的t g f f 工具生成随机的测试任务集，在同一平 台上实现了本文算法和对比算法。实验分析表明，本文的算法在中小任务规模下， 运行时间较对比的算法减少，同时解的质量有所提高。在大任务集下，本文算法 的运行时间虽较贪心算法要长，但解得质量要高；同时本文算法在运行时间和解 的质量上都较对比的模拟退火算法要优。 关键字：可重构计算系统；软硬件划分；启发式算法；模拟退火算法；贪心算法； 硕士学位论文 a b s t r a c t r e c o n f i g u r a b l ec o m p u t i n gs y s t e mi st y p i c a l l yc o m p o s e do fg e n e r a lp u r p o s e p r o c e s s o r sa n dp r o g r a m m a b l ed e v i c e s ，a n di th a sl i m i t e dh a r d w a r er e s o u r c ea n d s o f t w a r er e s o u r c e t a s k sc a nb ei m p l e m e n t e di ns o f t w a r er e s o u r c eo rh a r d w a r e r e s o u r c e ，b u tt a s k e x e c u t i o nt i m ea n dp o w e rc o n s u m p t i o n m a yb es i g n i f i c a n t d i f f e r e n c e t ot a k ef u l la d v a n t a g eo fh a r d w a r er e s o u r c ea n dt om e e tt h ed e m a n d s c e n a r i o s ，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 gi sr e q u i r e d 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 i sak e ys t e pa n dr e s e a r c hf o c u si nt h ed e s i g no fr e c o n f i g u r a b l ec o m p u t i n gs y s t e m 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 gi sac o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，w h i c h h a sb e e np r o v e dt ob en p - h a r d ，t h ep r e s e n ts t u d yu s u a l l yu s e st h eh e u r i s t i ca l g o r i t h m t os o l v et h i s p r o b l e m ，a n dt h es t u d yf o c u s e so ni m p r o v i n gt h ea l g o r i t h m s c o n v e r g e n c er a t ea n ds o l u t i o nq u a l i t y t h i sp a p e rp r e s e n t si m p r o v e dh e u r i s t i c a l g o r i t h mt oi m p r o v i n gc o n v e r g e n c er a t ea n ds o l u t i o nq u a l i t yf o rt w ot y p es e t so f t a s k s i nt h ec a s eo fs m a l la n dm e d i u ms i z es e to ft a s k s ，t h i sp a p e ru s e ss i m u l a t e d a n n e a l i n g ( s a ) a l g o r i t h mt os o l v 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 gp r o b l e m ，w h i c hi sa u s e dh e u r i s t i ca l g o r i t h m ，b u ts ah a ss l o wc o n v e r g e n c es p e e da n dp o o rs o l u t i o n q u a l i t y s ot h i sp a p e ru s e sa ni m p r o v e dd i s t u r b a n c em o d e la n da n n e a l i n gs c h e d u l et o i m p r o v ei t sc o n v e r g e n c es p e e d f o ra l g o r i t h m sp o o rs o l u t i o nq u a l i t y ，t h i sp a p e rg i v e s an e wc o s tf u n c t i o n t h en e wc o s tf u n c t i o ng u i d et h e a l g o r i t h m ss e a r c hi nt h e s o l u t i o ns p a c e ，w h i c ha v o i dt h eb l i n d n e s so ft h es e a r c h ，s ot h em e t h o dc a nq u i c k l y f i n dn e a ro p t i m a ls o l u t i o n sa n di m p r o v et h es o l u t i o nq u a l i t y i nt h ec a s eo fl a r g es i z es e to ft a s k s ，t h i sp a p e rc o m b i n e sb o t ht h ei m p r o v e d g r e e d ya l g o r i t h ma n ds at os o l v et 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 i nal a r g et a s k s e t ，t h em e t h o dw h i c hs i m p l yu s e sah e u r i s t i ca l g o r i t h mt os l o v ep a r t i t i o n i n gp r o b l e m w i l ll e a dt oi n c r e a s e dr u n n i n gt i m ea n dp o o rs o l u t i o n f o rt h e s ep r o b l e m s ，f i r s t l y ，t h i s p a p e ru s e st h ei m p r o v e dg r e e d ya l g o r i t h mt oi n i t i a l i z et h et a s ks e t g r e e d ya l g o r i t h m t i m ec o m p l e x i t yi sl o wa n de a s yt oi m p l e m e n t ，a n da l g o r i t h m ss o l u t i o nc a nb ec l o s e t ot h eg l o b a la p p r o x i m a t eo p t i m a ls o l u t i o nr e g i o n s e c o n d l y ，t h es ai sb eu s e dt o c o n t i n u et h es e a r c h s aa l g o r i t h mh a sg l o b a ls e a r c ha b i l i t y ，a n dc a nf i n a l l yg e tt h e g l o b a la p p r o x i m a t eo p t i m a ls o l u t i o n t ov a l i d a t et h ea l g o r i t h m ，t h i sp a p e ru s e sac o m m o nt o o l - t g f ft o g e n e r a t e r a n d o mt e s tt a s ks e t ，a n da c h i e v et h ep r o p o s e da l g o r i t h ma n dc o m p a r i s o na l g o r i t h m s n i i nt h es a m ep l a t f o r m e x p e r i m e n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mh a sl e s s r u n n i n g t i m et h a nt h ec o m p a r i s o na l g o r i t h m s ，a n dh a si m p r o v e ds o l u t i o nq u a l i t yi nt h i ss m a l l a n dm i d d l es c a l eo ft h et a s k i nal a r g et a s ks e t ，t h e r u n n i n gt i m eo ft h ep r o p o s e d a l g o r i t h m ，a l t h o u g hh a sl o n g e rt h a nt h eg r e e d ya l g o r i t h m ，b u th a sb e t t e rs o l u t i o n q u a l i t y ；a n dt h ep r o p o s e da l g o r i t h mp r o d u c e sb e t t e rs o l u t i o n sa n dr e d u c e st h er u n n i n g t i m ew h e nc o m p a r e dt ot h es a k e yw o r d s ：r e c o n f i g u r a b l ec o m p u t i n g ；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 ；h e u r i s t i c a l g o r i t h m ；s i m u l a t e da n n e a l i n g ；g r e e d ya l g o r i t h m ； i v 硕士学f = ：) = 论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要一i i a b s t r a c t i i i 插图索引v i i 插表索引v i i i 第1 章绪论l 1 1 研究背景及意义1 1 1 1 嵌入式系统发展趋势1 1 1 2 软硬件协同设计一2 1 1 3 研究意义5 1 2 课题来源5 1 3 研究目标5 1 4 主要工作6 1 5 本文的组织结构6 第2 章可重构计算系统中软硬件划分相关研究8 2 1 可重构计算系统8 2 1 1 可重构计算系统概述8 2 1 2 可重构计算系统分类一1 0 2 1 3 可重构计算系统耦合方式1 l 2 2 软硬件划分问题1 2 2 2 1 软硬件划分概述一1 2 2 2 2 系统描述1 4 2 2 3 粒度选择15 2 3 软硬件划分算法的研究现状一1 6 2 3 1 通用处理器不参与运算的方法一1 6 2 3 2 精确求解的算法_ 1 6 2 3 3 启发式算法16 2 3 4 非启发式算法1 8 2 4 软硬件划分性能评价指标1 9 2 4 1 时间性能19 2 4 2 功耗2 0 2 4 3 硬件面积2 l v 基于模拟退火算法的可重构计算系统软硬件划分方法研究 2 5 小结2 l 第3 章基于改进模拟退火算法的软硬件划分2 2 3 1 引言2 2 3 2 软硬件划分系统抽象模型2 2 3 2 1 系统体系结构抽象2 2 3 2 2 系统建模2 3 3 3 改进的软硬件划分算法：2 8 3 3 1 模拟退火算法分析2 8 3 3 2 模拟退火算法改进3 0 3 4 算法评价3 4 3 4 1 评价指标：3 4 3 4 2 仿真系统设计与实现3 4 3 4 3 实验结果分析一3 6 3 5 小结3 8 第4 章面向大任务集的软硬件划分一3 9 4 1 引言3 9 4 2 大任务集下初始化划分4 0 4 2 1 基于0 1 背包的软硬件划分模型4 0 4 2 2 基于贪心算法的初始化策略4 2 4 3 改进的软硬件划分算法4 4 4 4 实验结果分析一4 5 4 5 小结4 7 总结4 9 参考文献5 1 致谢5 6 附录a 攻读学位期间发表的学术论文及参与的科研项目5 7 v i 硕士学位论文 插图索引 图1 1 传统软硬件设计流程3 图1 2 软硬件协同设计流程4 图2 1 可重构计算系统的系统结构一9 图2 2 使用s r a m 技术的f p g a 编程原理1 0 图2 3r u 与处理器的耦合方式1 2 图2 4 软硬件划分的流程1 4 图2 5 系统架构模型19 图3 1 系统体系结构2 3 图3 2 简单d a g 图2 4 图3 3 模拟退火算法流程图2 9 图3 4 解空间3 2 图3 5 节点扰动图3 3 图3 6s h p s i m u l a t o r 模块关系图一3 6 图3 7 在任务数为5 0 ，硬件约束比为0 3 的情况下，算法的收敛曲线图一3 6 图3 8 在任务数为5 0 ，硬件约束比为0 1 的情况下，算法的收敛曲线图一3 7 图3 9 硬件面积约束比为o 3 ，s a ，s a 1 和f s a 算法执行时间的比较3 7 图4 1 初始化任务图一3 9 图4 2 硬件面积约束比为0 3 ，s a ，f s a ，g r e e d y - s a - a l g 算法执行时间比较4 7 基于模拟退火算法的可重构计算系统软硬件划分方法研究 插表索引 表2 1 三者实现计算目标的比较9 表2 2 软硬件执行对性能指标的影响1 3 表3 1 仿真实验环境一3 5 表3 2 任务数为5 0 0 ，s a ，s a 1 ，f s a 算法的比较3 8 表4 1 在硬件约束比为0 3 的情况下，g r e e d y 和g r e e d y s a - a l g 算法的比较4 6 表4 2 任务数为1 0 0 0 ，f s a 和g r e e d y s a - a l g 算法的比较一4 7 v 硕士学位论文 第1 章绪论 1 1 研究背景及意义 1 1 1 嵌入式系统发展趋势 嵌入式系统至今没有统一的严格定义，比较通用的定义为【l 】：以应用为中心、 以计算机技术为基础、软件硬件可裁剪，对功能、可靠性、成本、体积、功耗等 都有严格要求的专用计算机系统；嵌入式系统是将先进的计算机技术、半导体技 术、电子技术和各个行业的具体应用相结合后的产物。随着科技的发展，嵌入式 系统已经广泛应用于各种各样的设备中，典型的应用包括：消费电子，通信网络， 医疗仪器，汽车电子等。通常嵌入式系统由软件和硬件两部分组成，硬件部分主 要由处理器，存储器和其它外围电路组成；软件部分包括板级支持包、嵌入式操 作系统、设备驱动和各种用户程序；在比较低端的应用中，软件部分可能只包含 用户应用软件 tj 1 2 。近年来，随着技术的进步和应用需求的增长，嵌入式系统的发 展主要呈以下趋势： ( 1 ) 随着科技的进步，半导体技术和计算机技术迅猛发展，嵌入式处理器也飞 速发展，其处理能力得到不断增强，不再是单一功能的单元电路，而是集成了信 号采集、处理和输出的完整系统，这样集成在一个单芯片中的系统被称为片上系 统( s y s t e mo f c h i p ，s o c ) ；同时随着集成电路制造工艺的发展，已经进入深纳米工 艺时代，集成度进一步提高，芯片的封装尺寸也越来越小，但是功耗更低，性能 更强【3 j 。多核技术的出现改变了半导体产业的状况，近年来出现了针对嵌入式系 统的嵌入式多核片上系统( m u l t i p r o c e s s o rs o c ，m p s o c ) ，以满足日益复杂的功能 需求f 4 1 【5 1 。 ( 2 ) 嵌入式处理器的迅猛发展，也给软件设计提出了新的挑战。传统的无操作 系统的软件开发已经不能满足用户的需求，各种针对嵌入式系统的操作系统应运 而生，这类操作系统往往内核可裁剪，能在有限的硬件资源上运行，具备很好的 实时性和多任务管理能力，同时在操作系统和应用软件之间出现了中间软件层。 随着近年来多核处理器的出现，为了充分发挥多核的优势，操作系统开发者和开 发商做了许多工作，但是多核带来更高的系统复杂性，如何降低嵌入式多核系统 软件开发的复杂度，使得用户可以容易地进行应用开发，这也是嵌入式操作系统 面临的挑战。 ( 3 ) 设计方法学在嵌入式系统设计中扮演着越来越重要的角色，掀起了对设计 方法学研究的热潮【3 】。设计成本通常为整个系统成本的重要部分，使用传统的针 基丁模拟退火算法的可重构计算系统软硬件划分方法研究 对a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ) 先硬件后软件的设计方法进行s o c 的设计，将导致成本和性能上的缺陷，因此传统的设计方法学已经不能适应s o c 的开发要求。在当今产品更新速度加快，面临越来越短的上市时间压力，能够设 计出满足功耗、成本、性能和体积等约束的嵌入式系统成为新的挑战 ( 4 ) 同构多核对系统性能的提升有一定的局限，近年来出现了异构多核的 m s o c ，该类系统可以针对特殊的应用组合不同的核心在一个i c 中，通常包括通 用处理器( g e n e r a lp u r p o s ep r o c e s s o r ，g p p ) 核和d s p ( d i g i t a ls i g n a lp r o c e s s o r ) 核，不 同核心之间的通信可能使用复杂的片上网络( n e t w o r k so nc h i p s ，n o c ) 结构，甚至 有专门负责通信的处理器核心f 3 】和硬件加速部件。异构处理器可以大大提高系统 的处理能力，提高系统吞吐量来满足不同应用场合的需求，典型的如t io m a p 、t i 达芬奇和i b mc e l l ，这些异构处理器可以通过开发程序获得任务之间的并行，以 较低的功耗获得较好的性能。但是异构系统的通常性能高端、内部结构复杂， 对开发人员的要求较高，同时复杂的结构也导致开发成本较高，这制约了它的应 用；同时在系统层面对异构系统的任务进行有效的调度和管理，这也是异构系统面 临的挑战。 ( 5 ) 近年来出现了可重构计算平台作为一种新的高性能计算解决方案【t 】，已经 成为嵌入式系统设计的一种解决方案，现阶段可重构计算基本都使用现场可编程 门阵列( f i e l dp r o g r a m m a b l eg a t ea r r a y s ，f p g a ) 作为实验平台，它结合了通用处理 器和a s i c 的优点，具有较高的性能和灵活性。可重构计算在硬件设计上的实现基 于软件的灵活性，并且保持了基于硬件方法的执行速度，其系统结构可变的特点， 很好地适应了实际应用中的多元化需求。随着半导体技术的不断发展，呈现的一 个趋势是f p g a 将逐渐地取代a s i c 市场，以f p g a 为基础的可重构计算技术，是当 前计算机科学和半导体技术的研究热点。但是可重构作为新的时空域计算模型， 也给设计方法上面带来了新的挑战，比如基于可重构平台软硬件任务划分就是该 类系统面临的挑战【7 】，该问题是软硬件协同设计中的关键步骤，但是并没有得到 很好的解决，这是本论文研究的重点。 1 1 2 软硬件协同设计 嵌入式系统通常由若干个功能模块组成，按照其性质可以把这些功能模块分 为软件模块和硬件模块，传统的设计方法按照这两个模块分为两个独立的设计阶 段【2 】：硬件设计开发和软件设计开发，分别由硬件开发人员和软件开发人员独立 完成。尽管在过去的几十年里，有相当多的研究关注嵌入式系统的设计方法，出 现了许多经典的系统设计方法，典型的有模块化的设计方法和自顶向下的设计方 法。但是总体上都是基于硬件优先的原则进行设计，在完成硬件平台的设计之后 再进行软件开发。其基本思路如图1 1 所示。 2 硕士学位论文 系统描述 硬件描述软件描述 ll 硬件设计软件设计 系统集成 图1 1 传统软硬件设计流程 在传统的设计方法中，设计者分别进行软件设计和硬件设计，在设计过程中 设计者往往缺乏有效的交互，设计完成之后需要进行多次反复的实验和修改，如 果在设计的后阶段出现问题，可能需要重新设计系统来满足设计要求，因此导致 整个系统的开发周期增长和开发成本增加，而嵌入式系统的设计往往要求短的上 市时间，因此这种设计方法存在缺陷。同时在整个设计过程中遵循的是硬件优先 的原则，首先进行硬件设计，硬件设计者在理解软件需求的情况下，根据已有的 设计经验完成硬件设计。完成硬件设计之后，由软件设计人员在完成的硬件平台 上进行软件设计。由于硬件设计者往往对软件架构和其实现机制缺乏有效、清晰 的理解，因此导致硬件设计工作带有很大的盲目性，最终在系统的优化阶段，由 于设计空间的局限，软件和硬件部分只能孤立地改变和优化各自的性能，不可能 对整个系统做出较好的综合优化，得到的最终设计结果很难充分利用硬软件资源， 得到的设计结果可能在某些方面背离原始的设计需求。随着嵌入式系统变得越来 越复杂，传统的设计方法已经无法胜任大规模和复杂的系统设计任务。因此，软 硬件协同设计技术被提出并有相当多的研究者进行了研究1 1 3 e s 1 0 ，成为嵌入式系 统设计的一个趋势。 软硬件协同设计在学术界并没有统一的被接受的定义，一个较为通用的定义 如下：软硬件协同设计是指软硬件结构联合设计，达到性能、成本和功耗各个方 面的设计要求【2 】；传统的通用计算机系统设计通常采用分层抽象的设计方法，而 软硬件协同设计是一种根本上不同的设计方法，因为协同设计设计尽可能同时进 行系统各部分的优化，它广泛使用各种工具来进行设计分析和优化。 软硬件协同设计作为一种灵活的和全新的设计方法，在设计过程中强调软硬 件之间的协同性，把软件设计和硬件设计作为一个并行过程，并强调设计过程中 二者的相互交互，克服了传统设计方法中独立进行软硬件开发存在的缺陷。软硬 基于模拟退火算法的可重构计算系统软硬件划分方法研究 件协同设计是在系统设计目标的指导下，分析系统所拥有的软硬件资源，充分利 用系统软硬件资源之间的并行性，选择适合系统需求的软硬件体系结构，然后进 行具体的软硬件开发和测试，使得设计出的系统满足原始的设计需求，并且使得 系统取得较好的系统性能。在软硬件功能的设计和仿真评价过程中，软件和硬件 是相互独立又相互依赖的部分，软硬件协同设计技术使得软硬件模块在设计的初 始阶段就能相互结合，从而能尽早地发现设计中存在的问题，使得大多数设计问 题能够在设计的初始阶段解决，减少了在设计的后期修改系统设计所带来的时间 和开发上的成本，使得系统能够满足原始的设计需求，而且有利于系统运行在最 佳的工作状态和降低整个系统的开发成本。 文献 2 8 1 给出了软硬件协同设计的基本步骤，其可分为系统描述、软硬件任 务划分、软硬件设计和及其接口设计、系统集成设计、设计仿真和综合实现等几 个步骤，其基本步骤如图1 2 所示。 图1 2 软硬件协同设计流程 从图1 2 可以看出，系统的设计首先进行系统描述，该过程又称为系统建模， 设计人员使用系统描述语言对系统的功能模块和及其各模块之间的关系进行具体 描述，以指导后续的设计。在该阶段使用的系统描述语言较为灵活，可以使用专 门的系统描述语言，也可以自然语言或者其它非正式的语言。然后，在系统描述 的基础上，使用软硬件划分算法对系统的各个功能模块进行软硬件划分，软硬件 划分的实质就是决定那些功能模块由软件来执行，那些由硬件部分来执行。软件 4 硕士学位论文 实现的特点是成本低廉和实现灵活，但是性能较差，硬件实现性能较好，但是成 本较高，因此执行相同的功能任务，软件和硬件在成本、功耗和性能上都将产生 不同的结果，因此划分的结果将直接影响整个系统的性能和成本，所以对功能模 块进行软硬件划分是整个系统设计过程中最复杂和关键的步骤。在完成任务划分 之后，选择满足系统需求的体系结构，由不同的设计人员具体完成软件部分、硬 件部分及接口部分的设计；完成之后，进行整个系统的集成，再进行系统的协同 仿真，验证整个系统设计的正确性。最后完成系统的综合实现，如果在这个阶段 再发现问题，那么返回到软硬件任务划分阶段重新进行前面的步骤，直到满足系 统设计的需求。 1 1 3 研究意义 在整个软硬件协同设计过程中，对功能模块( 任务) 进行软硬件划分是最关键 和最困难的工作，划分的结果将对系统的功耗、性能等关键指标产生影响吲，因 此进行软硬件划分的研究具有很强的理论研究价值和实际应用价值。 软硬件划分是一个研究多年的问题，传统的划分方法采用纯手工实现，划分 的结果依靠设计人员的经验和对系统的认识。随着系统功能模块规模的增加，需 要搜索的解( 划分) 空间成指数增加，软硬件划分已经被证明是一个n p 难问题， 显然传统的手工划分的方法已经不再满足需求。当前基于算法的软硬件自动划分 受到越来越多的重视，因此软硬件自动划分技术的相关研究成为当前研究的热点。 1 2 课题来源 基于可重构的嵌入式计算系统运用越来越广泛，已经有很多的相关研究，是 当前研究的热点问题。而软硬件划分是软硬件协同设计的关键问题，尽管已经研 究多年，但是划分算法还是存在诸多改进的空间，因此针对此问题自拟本课题。 同时本文受到了国家自然基金项目异构多核片上系统自适应实时任务调度机制 及算法研究的支持，因为该项目主要研究异构系统上节能任务调度技术，异构 平台通常拥有不同的处理器核心，可能同时拥有硬件资源和软件资源，而进行任 务划分是进行任务调度的前提，在该类平台上的任务划分在数学上进行抽象出来 也为组合优化问题，和本课题的区别仅在于约束参数和目标函数的不同，而本文 的算法可以用来解决该类组合优化问题，因此本文的算法进行适当参数调整，可 以为该国家自然基金的相关研究提供参考。 1 3 研究目标 软硬件划分已经被证明是一个n p 难问题，在数学上可抽象为一类组合优化问 题，启发式算法是解决该类问题的有效算法。软硬件划分根据划分发生的时间不 基于模拟退火算法的可重构计算系统软硬件划分方法研究 同可以分为静态软硬件划分算法和动态软硬件划分算法；静态软硬件划分根据系 统设计阶段抽象的系统信息进行软硬件任务划分，并不考虑系统运行时的具体情 况；动态软硬件划分考虑到了系统运行时候的具体信息，跟实际情况较为接近， 但是相对复杂。静态软硬件划分算法大都采用启发式算法，尽管已经研究多年， 但通常存在收敛速度或者搜寻到的解并不是近似最优解的问题：针对存在的该问 题，本文的主要的研究工作是在可重构计算系统上，在中小任务集和大任务集两 种情况下，选取常用的启发式算法，提出改进的思路，以求加快算法的收敛速度 和取得较好的近似最优解，并通过实验验证结果。 1 4 主要工作 本文主要研究可重构计算系统中的静态软硬件划分方法，重点关注启发式算 法对软硬件划分问题的影响。在深入理解软硬件划分技术的基础上，分析和研究 了软硬件划分中存在的关键问题，使用改进的启发式算法来求解软硬件划分问题， 本文的主要研究内容如下： 1 软硬件划分是一个研究多年的问题，首先对已有的划分算法进行研究和 分析，分析各自的优缺点，为提出改进算法做好必要的理论准备。 2 系统的抽象层次、任务粒度的选择、软硬件划分算法和性能指标等是影 响软硬件划分性能的关键问题，因此本文对这几个方面进行了研究，重点关注软 硬件划分算法。针对本文研究的重点，确定可重构片上系统作( r e c o n n g u r a b i e s y s t e m o i l c h i p r s o c ) 为本文的系统体系结构，选择d a g 图作为系统描述工具， 并选择模拟退火算法作为改进的算法。 3 软硬件划分是n p 问题，模拟退火算法是求解该类问题的有效算法，但是 其存在收敛速度过慢的问题和解质量不高的问题。针对这些问题，在本文中给出 了改进的思路，设计出改进的算法，运用到软硬件划分问题中，并且通过实验验 证。 4 在大任务集的情况下，解的搜索能力通常下降，并且算法的运行时间增 加。针对该问题，本文研究了大任务集的软硬件划分问题，首先使用贪心算法对 任务集进行初始化，再使用改进的模拟退火算法来搜索全局近似最优解，并且通 过实验验证工作的有效性。 1 5 本文的组织结构 本文的内容分为4 章，具体安排如下： 第l 章：绪论。本章主要介绍了本文的研究背景及其相关知识，并给出了本 课题的来源、研究的目标和研究的主要内容，最后给出了本文的安排。 6 硕士学位论文 第2 章：可重构计算系统中软硬件划分的相关研究。首先，介绍了可重构技 术以及可重构计算平台上的软硬件划分技术的基本原理，然后，详细介绍了软硬 件划分技术及其关键问题：系统抽象、粒度选择和软硬件划分算法，并详细分析了 软硬件划分的性能指标。 第3 章：基于改进模拟退火算法的软硬件划分。软硬件划分是嵌入式系统协 同设计中的关键问题。模拟退火算法是解决该问题常用的启发式算法，但是其存 在收敛速度过慢和解的质量不高的问题。在本章中首先介绍了模拟退火算法，然 后分析导致其收敛速度过慢的原因，并通过改进算法的扰动模型和退火进度来加 快算法收敛，并提出一种新的代价函数计算方法来提高解的质量。最后通过实验 和已有的算法进行比较，验证本章算法的有效性。 第4 章：面向大任务集的软硬件划分算法。大任务集下，启发式算法搜索的 解空间有限，很难取得全局近似最优解。在本章中针对任务规模较大的情况，首 先使用贪心算法来初始化划分，然后使用改进的模拟退火算法来搜寻全局最优解。 最后通过实验对比，验证本章算法的有效性。 7 基于模拟退火算法的可重构计算系统软硬件划分方法研究 第2 章可重构计算系统中软硬件划分相关研究 2 1 可重构计算系统 2 1 1 可重构计算系统概述 可重构计算( r e c o n f i g u r a b l ec o m p u t e r ，r c ) 是指使用f p g a 来实现计算任务】， 通常是通过对f p g a 中特定的可重构单元( r e c o n f i g u r a b l eu n i t ，r u ) 进行配置来实 现。可重构计算的概念最早出现在2 0 世纪6 0 年代，但是可重构计算真正开始发展 是在2 0 世纪8 0 年代f p g a 发明之后；进入2 1 世纪之后，硬件技术飞速发展，可重 构计算使用的硬件平台也飞速发展，随着f p g a 器件中集成的门数不断增加，能 够提供的硬件资源更加丰富，促进了可重构计算领域的相关研究，同时出现了运 用可重构计算系统进行模式识别【1 2 】和数据压缩【”】的成功案例，进一步推动了人们 对可重构计算领域相关理论和应用的关注。 传统计算目标的实现通常使用a s i c 或通用处理器。a s i c 通常针对特定的应 用进行定制，是一种使用纯硬件来进行运算的方式，由于是针对特定的应用进行 设计，利用任务在硬件上面高度并行，能够达到很高的运算效率和速度，但是缺 点也是显而易见的，由于a s i c 不可编程，一旦应用场合稍微发生改变，那么必 须重新修改电路以适应新的应用，缺乏灵活性，并且每次进行电路的重新设计成 本较高，现代嵌入式系统面临极短的上市时间和苛刻的成本控制压力，在许多情 况下使用a s i c 进行开发已经变的不再现实；另一种实现计算目标的方法是使用 通用处理器，通常通用处理器具备指令级处理能力，通过开发软件组合指令集中 的某些指令，可以构成指令序列，放在处理器串行执行可以完成特定的计算任务， 通用处理器的最大优势在于修改软件可以改变系统的功能，而无需对硬件进行任 何的改变，具备很好的灵活性，同时价格低廉，但这些优势是以牺牲系统的计算 速度和计算效率作为代价。在同样的物理条件下，a s i c 的计算效率要远远高于 通用处理器，造成该结果的主要原因在于通用处理器按预先定义的指令顺序执行 指令，而且一般每条指令的执行需要经过“取指一译码一执行一数据存储”等几 个步骤，这样导致每条指令耗费较多的系统时间，同时增加了系统的复杂度，使 得系统可靠性变差【，-