Global execution time minimization by allocating tasks in parallel systems

We have studied the allocation of directed acyclic graphs (DAGs) into a given parallel machine (PM); this is an NP-complete problem. Previous papers presented allocation algorithms all making many rough simplifications so that the achieved allocations are too far from the optimum and do not minimize the actual execution time of the program. We analyzed the impact of the precedence relations on the execution time of DAG into PM issuing a new cost function (f_PR) which takes into account both the PM topology and the precedence relations. f_PR is minimized through a genetic algorithm and, in order to speed up its convergence, we developed a heuristic criterion, based on the critical path idea, for the choice of the starting population. The best results achievable using our cost function have been illustrated by comparing the actual execution times of the allocation given by the minimization of f_PR with the ones obtained using the allocations given by the minimization of two cost functions described in literature