BUDGET ESTIMATION AND CONTROL FOR BAG-OF-TASKS SCHEDULING IN CLOUDS
Abstract
Commercial cloud offerings, such as Amazon's EC2, let users allocate compute resources on demand, charging based on reserved time intervals. While this gives great flexibility to elastic applications, users lack guidance for choosing between multiple offerings, in order to complete their computations within given budget constraints. In this work, we present BaTS, our budget-constrained scheduler. Using a small task sample, BaTS can estimate costs and makespan for a given bag on different cloud offerings. It provides the user with a choice of options before execution and then schedules the bag according to the user's preferences. BaTS requires no a-priori information about task completion times. We evaluate BaTS by emulating different cloud environments on the DAS-3 multi-cluster system. Our results show that BaTS correctly estimates budget and makespan for the scenarios investigated; the user-selected schedule is then executed within the given budget limitations.
References
- Concurrency - Practice and Experience 17(2-4), 323 (2005), DOI: 10.1002/cpe.938. Crossref, ISI, Google Scholar
- Amazon Web Services , http://aws.amazon.com . Google Scholar
-
A.-M. Oprescu and T. Kielmann , Bag-of-Tasks Scheduling under Budget Constraints , 2nd IEEE International Conference on Cloud Computing Technology and Science (CloudCom 2010) ( IEEE ) . Google Scholar -
E. S. Keeping , Introduction to Statistical Inference ( D. Van Nostrand , Princeton, New Jersey , 1962 ) . Google Scholar -
J. F. Kenney and E. S. Keeping , Mathematics of Statistics ( D. Van Nostrand , Princeton, New Jersey , 1962 ) . Google Scholar W. N. Venables and B. D. Ripley , Modern Applied Statistics with S, 4th edn. (Springer, 2002). Crossref, Google Scholar-
S. Martello and P. Toth , Knapsack problems: algorithms and computer implementations ( John Wiley & Sons, Inc. , New York, NY, USA , 1990 ) . Google Scholar - D. Pisinger. A minimal algorithm for the bounded knapsack problem. Technical report, University of Copenhagen, 1994 . Google Scholar
- Computer 43(8), 54 (2010), DOI: 10.1109/MC.2010.184. Crossref, ISI, Google Scholar
A. Iosup , The performance of bags-of-tasks in large-scale distributed systems, HPDC '08: Proceedings of the 17th international symposium on High performance distributed computing (ACM, New York, NY, USA, 2008) pp. 97–108. Google Scholar- IEEE Transactions on Computers 56(6), 815 (2007), DOI: 10.1109/TC.2007.1042. Crossref, ISI, Google Scholar
-
P. Sugavanam , Robust processor allocation for independent tasks when dollar cost for processors is a constraint , IEEE International Conference on Cluster Computing . Google Scholar - J. Parallel Distrib. Comput. 67(4), 400 (2007). Crossref, ISI, Google Scholar
- Future Generation Comp. Syst. 21(2), 271 (2005). Crossref, ISI, Google Scholar
- Parallel Comput. 32(7), 479 (2006). Crossref, Google Scholar
-
J. Smith , Measuring the robustness of resource allocations in a stochastic dynamic environment , IPDPS . Google Scholar -
Ming Mao , Jie Li and Marty Humphrey , Cloud Auto-scaling with Deadline and Budget Constraints , The 11th ACM/IEEE International Conference on Grid Computing (Grid 2010) . Google Scholar Q. Zhu and G. Agrawal , An adaptive middleware for supporting time-critical event response, International Conference on Autonomic Computing (2008) pp. 99–108. Google ScholarQ. Zhu and G. Agrawal , A resource allocation approach for supporting time-critical applications in grid environments, International Symposium on Parallel and Distributed Processing (2009) pp. 1–12. Google Scholar-
W. Cirne , Running bag-of-tasks applications on computational grids: The mygrid approach , ICPP . Google Scholar - J. ACM 24(2), 280 (1977), DOI: 10.1145/322003.322011. Crossref, ISI, Google Scholar
M. Maheswaran , Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems, Eighth Heterogeneous Computing Workshop (IEEE Computer Society Press, 1999) pp. 30–44. Google Scholar- International Journal of High Performance Computing Applications 24(4), 445 (2010). Crossref, ISI, Google Scholar


