A distributed evolutionary approach for multisite mapping on grids

In this paper attention is concentrated on the mapping of computationally intensive multi-task applications onto shared computational grids. This problem, already known to be as NP-complete in parallel systems, becomes even more arduous in such environments. To find a near-optimal mapping solution a parallel version of a Differential Evolution algorithm is presented and evaluated on different applications and operating conditions of the grid nodes. The purpose is to select for a given application the mapping solutions that minimize the greatest among the time intervals which each node dedicates to the execution of the tasks assigned to it. The experiments, effected with applications represented as task interaction graphs, demonstrate the ability of the evolutionary tool to perform multisite grid mapping, and show that the parallel approach is more effective than the sequential version both in enhancing the quality of the solution and in the time needed to get it.