基于GPU的自适应邻域压缩禁忌搜索的软硬件划分算法

作     者：侯能 何发智 周毅 陈壹林 Neng HOU;Fazhi HE;Yi ZHOU;Yilin CHEN

作者机构：武汉大学软件工程国家重点实验室武汉430072 武汉大学计算机学院武汉430072 武汉科技大学信息科学与工程学院武汉430081 

基　　金：国家自然科学基金(批准号:61472289) 湖北省自然科学基金(批准号:2015CBF254)资助项目 

出 版 物：《中国科学：信息科学》 (Scientia Sinica(Informationis))

年 卷 期：2018年第48卷第8期

页      码：978-999页

摘      要：软硬件划分是软硬件协同设计中的关键步骤,决定了哪些功能由硬件执行,哪些功能由软件执行.软硬件划分属于NP难问题.现代嵌入式系统的复杂性提高,造成软硬件划分问题规模变大,需要采用启发式方法求解.禁忌搜索是求解软硬件划分的有效方法.然而,算法的求解过程非常耗时.已有的禁忌搜索求解软硬件划分是串行实现,要折中考虑解的质量和算法的运行时间.这种考虑牺牲了解的质量.本文提出基于GPU的自适应邻域压缩(compacting neighborhood)禁忌搜索的软硬件划分算法.首先,提出自适应策略.自适应策略能够增强算法的搜索集中性,提高解的质量.GPU的大规模并行特性可以降低算法的运行时间.其次,为了使算法在GPU上高效地执行,提出基于GPU的任务图表达、线程–候选解映射、数据布局和访存等一系列优化策略.最后,实验采用统一设备架构(CUDA)编程,并根据相关基准任务图,通过不同的计算–通信比和实时约束条件,对提出的方法进行验证.结果表明,本文方法的解质量要优于已有的方法.对比将自适应邻域压缩禁忌搜索自然移植到GPU后的运行时间,提出的GPU上的执行优化策略明显地降低了求解时间.另外,在更大规模的软硬件划分上验证了基于GPU的方法在时间上的优势.

主 题 词：软硬件协同设计 启发式方法 图形处理单元 禁忌搜索 自适应算法 

学科分类：08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.1360/N112017-00024

馆 藏 号：203321183...