基于模拟退火算法的可重构计算系统软硬件划分方法分析-analysis of hardware and software partition method of reconfigurable computing system based on simulated annealing algorithm.docx

湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在______年解密后适用本授权书。2、不保密?。（请在以上相应方框内打―?‖）作者签名：日期：年月日导师签名：日期：年月日摘要可重构计算系统通常由通用处理器和可编程器件组成，同时拥有受限的硬件资源和软件资源。任务可以被划分到软件或者硬件上执行，但两者将在任务执行时间、功耗等方面产生显著的差别。为了充分利用硬件资源并使系统满足应用场景需求，需要对任务进行有效的软硬件划分。软硬件划分是当前可重构计算系统设计中的关键步骤和研究热点。软硬件划分为组合优化问题，已经被证明为NP问题,目前的研究主要是基于启发式算法来解决此类问题，研究的重点在于提高算法的收敛速度和解的质量。因此本文在两种任务集规模下，提出改进的启发式划分算法来提高算法收敛速度和解质量。在中小规模任务集的情况下，使用改进的模拟退火算法进行软硬件划分。模拟退火算法是解决软硬件划分问题常用的启发式算法，但是其收敛速度过慢且解的质量有待提高。本文通过改进算法的扰动模型和退火进度来改进其收敛速度慢的问题。针对算法存在解质量较差的问题，本文在总结现有代价函数的基础上提出一种新的代价函数计算方法。该方法对算法在解空间上的搜索方向进行引导，避免了搜索的盲目性，从而使算法能快速搜索到近似最优解，提高划分质量。在大规模任务集的情况下，结合改进的贪心算法和模拟退火算法对软硬件划分进行了研究。在大任务集下，单纯使用一种启发式算法会导致算法运行时间增加及划分质量下降。针对存在的上述问题，在文中首先使用改进的贪心算法对任务集进行初始化。贪心算法时间复杂度较低且容易实现，输出的解能接近全局近似最优解所在区域。然后使用改进的模拟退火算法，在初始化的基础上继续进行搜索。模拟退火算法全局搜索能力较强，能最终获得全局近似最优解。为验证本文算法，使用通用的TGFF工具生成随机的测试任务集，在同一平台上实现了本文算法和对比算法。实验分析表明，本文的算法在中小任务规模下，运行时间较对比的算法减少，同时解的质量有所提高。在大任务集下，本文算法的运行时间虽较贪心算法要长，但解得质量要高；同时本文算法在运行时间和解的质量上都较对比的模拟退火算法要优。关键字：可重构计算系统；软硬件划分；启发式算法；模拟退火算法；贪心算法；AbstractReconfigurablecomputingsystemistypicallycomposedofgeneralpurposeprocessorsandprogrammabledevices,andithaslimitedhardwareresourceandsoftwareresource.Taskscanbeimplementedinsoftwareresourceorhardwareresource,buttaskexecutiontimeandpowerconsumptionmaybesignificantdifference.Totakefulladvantageofhardwareresourceandtomeetthedemandscenarios,Hardware/softwarepartitioningisrequired.Hardware/softwarepartitioningisakeystepandresearchfocusinthedesignofreconfigurablecomputingsystem.Hardware/softwarepartitioningisacombinatorialoptimizationproblem,whichhasbeenprovedtobeNP-hard,thepresentstudyusuallyusestheheuristicalgorithmtosolvethisproblem,andthestudyfocusesonimprovingthealgorithm’sconvergencerateandsolutionquality.Thispaperpresentsimprovedheurist