基于深度优先贪婪搜索的可重构硬件任务划分算法

作     者：陈乃金 CHEN Nai-jin

作者机构：安徽工程大学计算机与信息学院安徽芜湖241000 嵌入式系统与服务计算教育部重点实验室(同济大学)上海201804 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2012年第32卷第1期

页      面：158-162页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家863计划项目(2009AA011705) 芜湖市科技计划自然科学资金资助项目(芜科计字190号) 安徽省教育厅自然科学资金资助项目(KJ2007B247 KJ2010B018) 安徽省高等学校青年教师科研资助计划自然科学基金资助项目(2007jq1086) 

主　　题：可重构计算 时域划分 深度优先贪婪搜索 通信成本 资源约束 硬件碎片 

摘      要：针对可重构计算硬件任务划分通信成本较小化的问题,提出了一种基于深度优先贪婪搜索划分(DFGSP)算法。首先,从待调度的就绪队列中取出队首任务,在某一硬件面积约束下,按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG),逐个划入满足要求的节点;然后,一遇到不满足面积要求的任务节点时,就计算当前划分模块间输出边数(可量化为通信成本);最后,跳过当前不满足要求的任务节点,继续搜索该点之后处于就绪状态的节点,当搜索到满足要求的点时,按加入该点后不增加当前划分块间输出边数和尽可能填满可重构运算阵列的原则进行。实验结果表明,与现有的簇划分(CBP)、簇层次敏感两种划分算法相比,提出的算法获得了最小划分模块数和平均跨模块间I/O边数最小的均值,通过实际验证,算法显著地改善了硬件任务的划分效果,而且运行开销没有明显增加。