利用层次任务图和多种群遗传算法的可重构计算任务划分  

A Partition Algorithm Exploiting Hierarchical Task Graph and Multi-population Genetic Algorithm for Reconfigurable Computing

作　　者：周军[1] 张强[1] 于晓洲[1] 

机构地区：[1]西北工业大学精确制导与控制研究所,西安710072

出　　处：《计算机辅助设计与图形学学报》2011年第3期508-513,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：教育部博士点基金(20070699004);西北工业大学科技创新基金(2008KJ02010)

摘　　要：为实现可重构计算中软硬件任务的自动划分,提出一种基于层次任务图模型和采用遗传算法作为搜索算法的任务划分算法.首先设计了一个层次任务图模型,其不同于基于有向非循环图(DAG)的模型,可以在任务划分时动态改变任务颗粒度,进而得到不同任务粒度下的最优解;其次设计了一个考虑了时间、功耗、资源和通信代价的适应度函数,并根据任务数量不固定的特点对遗传算法进行了改进.对文中算法在FPGA上进行实验验证和分析的结果表明,该算法的结果优于基于DAG任务图模型的任务划分.A software/hardware task partition algorithm was proposed for reconfigurable computing. It exploits a hierarchical task graph to describe the application. Then, it can change task granularity dynamically during searching process and find out the best granularity, which was different from the current directed acyclic graph （DAG） based method. Based on hierarchical task graph, a multipopulation genetic algorithm was designed to perform a multi-object optimization, including time, power, resources and communication cost. The chromosome＇s length was variable, so it can be applied to variable task granularity and different task number. Finally, partition solution was implemented and analyzed in FPGA device. Experimental results show that the proposed algorithm gets better partition solution than DAG based method.

关 键 词：可重构计算 任务划分 层次任务图 遗传算法 

分 类 号：TP331[自动化与计算机技术—计算机系统结构]