A customized balanced-objective genetic algorithm for task scheduling in reconfigurable computing systems

Reconfiguration and hardware implementation capabilities in reconfigurable computing (RC) systems make them more appropriate to recent computationally intensive applications. However, reaching optimal resource utilization remained as one of the main challenges in these systems. In order to implement more tasks in each reconfiguration interval, several decisive factors such as execution time, data communication cost, and required hardware resources must be analyzed simultaneously. In this paper, we proposed a novel balanced-objective task selector combined with a genetic algorithm to efficiently pick up the tasks of an application and occupy the resources as more as possible. The multi-objective fitness function of this algorithm adequately partitions the input application and provides the desirable intra and inter-cluster characteristics. Moreover, a new chromosome encoding technique has been developed to prevent precedence constraint violation of invalid solutions by removing forbidden regions in the search space. We classified the input applications with topological features such as first level parallel tasks (FLPT) and critical path length (CPL) for comprehensive evaluation. Several experiments are performed on randomly generated and real-world Directed Acyclic Graphs (DAGs), and the results are more satisfying in DAGs with more FLPTs and shorter CPLs where up to 28.63% makespan and 29.3% resource utilization improvement have been achieved in comparison with previous methods.