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

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

提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.

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.