Performance Optimization in Grid Resource Allocation Using Linear Programming

Abstract

In Grid computing environment, range of computing devices coexists stating from personal computers to supercomputers. These devices are inter-connected to provide a variety of computational capabilities in order to execute applications that have diverse requirements. An important decision for such computing infrastructure is how to optimally allocate computational and communication resources to these applications and to schedule their execution in order to maximize performance benefits. It is apparent that resource heterogeneity impacts the resource allocation in quite significant way in terms of overall performance, reliability, robustness, scalability and fault tolerance. So, the system managing these complex environments needs to be scalable, reliable, smart and adaptable to change its allocation mechanism depending upon the environment and its user requirements. Therefore, a scalable approach for resource allocation where the system can adapt itself to the changing environment and fluctuating resources, is essentially needed.

Given limited resources and competing constraints we can formulate the problems as the problem of maximizing or minimizing an objective function. So, we specify the objective function as a linear function of certain variables, and constraints on resources as equalities or inequalities on those variables, and we get Linear Formulation of the problem. For this reformulated problem; a linear programming based resource allocation method is proposed. The method is composed of a large numbers of independent tasks, with the goal of using idle computing resources.

The method has been implemented using Java. The result obtained by this method demonstrates the proposed method optimally allocates resources on Grids and finally compared with Round Robin Approach.