概率构造算法与遗传算法融合的可重构计算系统硬件任务划分  

Hardware Task Partitioning for Reconfigurable Computing Systems Syncretized Probabilistic Constructive Algorithm and Genetic Algorithm

作　　者：陈伟男[1] 周博 彭澄廉[1] 

机构地区：[1]复旦大学计算机与信息技术系 [2]Department of Computer Science & Engineering,University of Notre Dame,South Bend,IN 46617 USA

出　　处：《计算机辅助设计与图形学学报》2007年第8期960-965,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60573105)

摘　　要：提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.A partitioning algorithm is proposed to partition an entire hardware task into interconnected subtasks for reconfigurable computing. The algorithm, called PCGA, syncretizes probabilistic constructive （PC） algorithm and genetic algorithm （GA）. A new approach is proposed to measure the variety of partitions, and an initial population with a variety of better individuals is produced by PC algorithm. Then, the optimal solution is captured by GA based on this initial population. The experimental results show that PCGA can get better results of graph partitioning than those list-based partitioning algorithms, and use less runtime than those genetic algorithms based on a population of randomly generated individuals.

关 键 词：可重构计算系统 有向无环图 图划分 任务簇 

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