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

摘要：

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

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

所属期刊栏目：48

分类号：TP301.6;TN911.73;TP18

资助基金：国家自然科学基金;湖北省自然科学基金

在线出版日期：2018-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共22页

页码：978-999