World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

BUDGET ESTIMATION AND CONTROL FOR BAG-OF-TASKS SCHEDULING IN CLOUDS

    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

    • D. Thain, T. Tannenbaum and M. Livny, Concurrency - Practice and Experience 17(2-4), 323 (2005), DOI: 10.1002/cpe.938. Crossref, ISIGoogle 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). CrossrefGoogle 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
    • H. E. Balet al., Computer 43(8), 54 (2010), DOI: 10.1109/MC.2010.184. Crossref, ISIGoogle Scholar
    • A. Iosupet al., 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
    • Y. C. Lee and A. Y. Zomaya, IEEE Transactions on Computers 56(6), 815 (2007), DOI: 10.1109/TC.2007.1042. Crossref, ISIGoogle Scholar
    • P.   Sugavanam et al. , Robust processor allocation for independent tasks when dollar cost for processors is a constraint , IEEE International Conference on Cluster Computing . Google Scholar
    • P. Sugavanamet al., J. Parallel Distrib. Comput. 67(4), 400 (2007). Crossref, ISIGoogle Scholar
    • C. Weng and X. Lu, Future Generation Comp. Syst. 21(2), 271 (2005). Crossref, ISIGoogle Scholar
    • H. González-Vélez, Parallel Comput. 32(7), 479 (2006). CrossrefGoogle Scholar
    • J.   Smith et al. , 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 Scholar
    • Q. 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 et al. , Running bag-of-tasks applications on computational grids: The mygrid approach , ICPP . Google Scholar
    • O. H. Ibarra and C. E. Kim, J. ACM 24(2), 280 (1977), DOI: 10.1145/322003.322011. Crossref, ISIGoogle Scholar
    • M. Maheswaranet al., 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
    • K. Liuet al., International Journal of High Performance Computing Applications 24(4), 445 (2010). Crossref, ISIGoogle Scholar