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

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 multi-population 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.