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

• 作者: 何发智 侯能 周毅 陈壹林
• 来源期刊: 中国科学（信息科学）
• 关键词: 软硬件协同设计 启发式方法 图形处理单元 禁忌搜索 自适应算法
• 年，卷（期）: 2018,（8）
• 所属期刊栏目: 论文
• 页码范围: 978-999
• 页数: 22页
• 语种: 中文
• DOI: 10.1360/N112017-00024

摘要

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