Heuristic for resources allocation on utility computing infrastructures

ABSTRACT

The use of utility on-demand computing infrastructures, such as Amazon's Elastic Clouds [1], is a viable solution to speed lengthy parallel computing problems to those without access to other cluster or grid infrastructures. With a suitable middleware, bag-of-tasks problems could be easily deployed over a pool of virtual computers created on such infrastructures.

In bag-of-tasks problems, as there is no communication between tasks, the number of concurrent tasks is allowed to vary over time. In a utility computing infrastructure, if too many virtual computers are created, the speedups are high but may not be cost effective; if too few computers are created, the cost is low but speedups fall below expectations. Without previous knowledge of the processing time of each task, it is difficult to determine how many machines should be created.

In this paper, we present an heuristic to optimize the number of machines that should be allocated to process tasks so that for a given budget the speedups are maximal. We have simulated the proposed heuristics against real and theoretical workloads and evaluated the ratios between number of allocated hosts, charged times, speedups and processing times. With the proposed heuristics, it is possible to obtain speedups in line with the number of allocated computers, while being charged approximately the same predefined budget.

REFERENCES

• 1: Amazon.com, Inc. Amazon elastic compute cloud (amazon ec2). http://aws.amazon.com/ec2.
• 2: David P. Anderson , Gilles Fedak, The Computational and Storage Potential of Volunteer Computing, Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid, p.73-80, May 16-19, 2006 [doi>10.1109/CCGRID.2006.101]
• 3: A. Bouteiller, H. L. Bouziane, T. Hérault, P. Lemarinier, and F. Cappello. Hybrid preemptive scheduling of mpi applications on the grids. In Int. Journal of High Performance Computing Special issue, 20:77--90, 2006.
• 4: Henri Casanova , Dmitrii Zagorodnov , Francine Berman , Arnaud Legrand, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proceedings of the 9th Heterogeneous Computing Workshop, p.349, May 01-01, 2000
• 5: CS Department of Computer Science - University of California, Santa Barbara. Eucalyptus. http://eucalyptus.cs.ucsb.edu/.
• 6: Enomaly Inc. Enomalism: Elastic computing platform - virtual server managemen. http://enomalism.com.
• 7: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 8: C. B. Lee, Y. Schwartzman, J. Hardy, and A. Snavely. Are user runtime estimates inherently inaccurate? In Job Scheduling Strategies for Parallel Processing, 10th International Workshop, JSSPP 2004. Springer, 2005.
• 9: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 10: Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]
• 11: Marco A. S. Netto , Rodrigo N. Calheiros , Rafael K. S. Silva , Cesar A. F. De Rose , Caio Northfleet , Walfredo Cirne, Transparent Resource Allocation to Exploit Idle Cluster Nodes in Computational Grids, Proceedings of the First International Conference on e-Science and Grid Computing, p.238-245, December 05-08, 2005 [doi>10.1109/E-SCIENCE.2005.83]
• 12: Persistence of Vision Raytracer Pty. Ltd. Persistence of vision raytracer. http://www.povray.org/.
• 13: César A. F. De Rose , Tiago Ferreto , Rodrigo N. Calheiros , Walfredo Cirne , Lauro B. Costa , Daniel Fireman, Allocation strategies for utilization of space-shared resources in Bag of Tasks grids, Future Generation Computer Systems, v.24 n.5, p.331-341, May, 2008 [doi>10.1016/j.future.2007.05.005]
• 14: D. Zhou , V. Lo, Cluster Computing on the Fly: resource discovery in a cycle sharing peer-to-peer system, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.66-73, April 19-22, 2004

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Keywords:
bag-of-tasks, resource allocation, resource allocation on utility computing, scheduling heuristics