A Multiobjective Evolutionary Approach for Multisite Mapping on Grids

Grid systems, constituted bymultisite andmulti-owner time- shared resources, make a great amount of locally unemployed computational power accessible to users. To profitably exploit this power for processing computationally intensive grid applications, an efficient multisite mapping must be conceived. The mapping of cooperating and communicating application subtasks, already known as NP-complete for parallel systems, results even harder in grid computing because the availability and workload of grid resources change dynamically, so evolutionary techniques can be adopted to find near-optimal solutions. In this paper a mapping tool based on a multiobjective Differential Evolution algorithm is presented. The aim is to reduce the execution time of the application by selecting among all the potential solutions the one which minimizes the degree of use of the grid resources and, at the same time, complies with Quality of Service requirements. The proposed mapper is assessed on some artificial problems differing in application sizes and workload constraints.