{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T01:40:12Z","timestamp":1686274812527},"reference-count":32,"publisher":"Sociedade Brasileira de Computacao - SB","issue":"2","license":[{"start":{"date-parts":[[2011,8,27]],"date-time":"2011-08-27T00:00:00Z","timestamp":1314403200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2011,8,27]],"date-time":"2011-08-27T00:00:00Z","timestamp":1314403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Internet Serv Appl"],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>There are increasingly more computing problems requiring lengthy parallel computations. For those without access to current cluster or grid infrastructures, a recent and proven viable solution can be found with on-demand utility computing infrastructures, such as Amazon Elastic Compute Cloud (EC2). A relevant class of such problems, Bag-of-Tasks (BoT), can be easily deployed over such infrastructures (to run on pools of virtual computers), if provided with suitable software for host allocation. BoT problems are found in several and relevant scenarios such as image rendering and software testing.<\/jats:p><jats:p>In BoT jobs, tasks are mostly independent; thus, they can run in parallel with no communication among them. The number of allocated hosts is relevant as it impacts both the speedup and the cost: if too many hosts are used, the speedup is high but this may not be cost-effective; if too few are used, the cost is low but speedup falls below expectations. For each BoT job, given that there is no prior knowledge of neither the total job processing time nor the time each task takes to complete, it is hard to determine the number of hosts to allocate. Current solutions (e.g., bin-packing algorithms) are not adequate as they require knowing in advance either the time that the next task will take to execute or, for higher efficiency, the time taken by each one of the tasks in each job considered.<\/jats:p><jats:p>Thus, we present an algorithm and heuristics that adaptively predicts the number of hosts to be allocated, so that the maximum speedup can be obtained while respecting a given predefined budget. The algorithm and heuristics were simulated against real and theoretical workloads. With the proposed solution, it is possible to obtain speedups in line with the number of allocated hosts, while being charged less than the predefined budget.<\/jats:p>","DOI":"10.1007\/s13174-011-0033-z","type":"journal-article","created":{"date-parts":[[2011,8,26]],"date-time":"2011-08-26T17:10:02Z","timestamp":1314378602000},"page":"171-185","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A2HA\u2014automatic and adaptive host allocation in utility computing for bag-of-tasks"],"prefix":"10.5753","volume":"2","author":[{"given":"Jo\u00e3o Nuno","family":"Silva","sequence":"first","affiliation":[]},{"given":"Lu\u00eds","family":"Veiga","sequence":"additional","affiliation":[]},{"given":"Paulo","family":"Ferreira","sequence":"additional","affiliation":[]}],"member":"3742","published-online":{"date-parts":[[2011,8,27]]},"reference":[{"key":"33_CR1","unstructured":"Amazon Web Services LLC (2011) Amazon elastic compute cloud (amazon ec2). http:\/\/aws.amazon.com\/ec2"},{"key":"33_CR2","first-page":"1","volume-title":"IEEE international parallel and distributed processing symposium, IPDPS 2007","author":"DP Anderson","year":"2007","unstructured":"Anderson DP (2007) Local scheduling for volunteer computing. In: IEEE international parallel and distributed processing symposium, IPDPS 2007, 26\u201330 March 2007, pp\u00a01\u20138"},{"key":"33_CR3","volume-title":"IEEE\/ACM international symposium on cluster computing and the grid","author":"DP Anderson","year":"2006","unstructured":"Anderson DP, Fedak G (2006) The computational and storage potential of volunteer computing. In: IEEE\/ACM international symposium on cluster computing and the grid"},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1145\/945445.945462","volume-title":"SOSP","author":"P Barham","year":"2003","unstructured":"Barham P, Dragovic B, Fraser K, Hand S, Harris TL, Ho A, Neugebauer R, Pratt I, Warfield A (2003) Xen and the art of virtualization. In: Scott ML, Peterson LL (eds) SOSP. ACM, New York, pp 164\u2013177"},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1177\/1094342006062526","volume":"20","author":"A Bouteiller","year":"2006","unstructured":"Bouteiller A, Bouziane HL, H\u00e9rault T, Lemarinier P, Cappello F (2006) Hybrid preemptive scheduling of mpi applications on the grids. Int J High Perform Comput Appl 20:77\u201390. Special issue","journal-title":"Int J High Perform Comput Appl"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/1966445.1966463","volume-title":"Proceedings of the sixth conference on computer systems, EuroSys\u201911","author":"S Bucur","year":"2011","unstructured":"Bucur S, Ureche V, Zamfir C, Candea G (2011) Parallel symbolic execution for automated real-world software testing. In: Proceedings of the sixth conference on computer systems, EuroSys\u201911. ACM, New York, pp 183\u2013198. http:\/\/doi.acm.org\/10.1145\/1966445.1966463"},{"issue":"13\u201315","key":"33_CR7","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1002\/cpe.690","volume":"14","author":"R Buyya","year":"2002","unstructured":"Buyya R, Abramson D, Giddy J, Stockinger H (2002) Economic models for resource management and scheduling in grid computing. Concurr Comput, Pract Exp 14(13\u201315):1507\u20131542","journal-title":"Concurr Comput, Pract Exp"},{"issue":"3","key":"33_CR8","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1109\/JPROC.2004.842784","volume":"93","author":"R Buyya","year":"2005","unstructured":"Buyya R, Abramson D, Venugopal S (2005) The grid economy. Proc IEEE 93(3):698\u2013714","journal-title":"Proc IEEE"},{"key":"33_CR9","first-page":"349","volume-title":"Proceedings 9th heterogeneous computing workshop, HCW 2000","author":"H Casanova","year":"2000","unstructured":"Casanova H, Legrand A, Zagorodnov D, Berman F (2000) Heuristics for scheduling parameter sweep applications in grid environments. In: Proceedings 9th heterogeneous computing workshop, HCW 2000, pp 349\u2013363"},{"issue":"3","key":"33_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.ipl.2006.01.002","volume":"98","author":"L Chunlin","year":"2006","unstructured":"Chunlin L, Layuan L (2006) QoS based resource scheduling by computational economy in computational grid. Inf Process Lett 98(3):119\u2013126","journal-title":"Inf Process Lett"},{"key":"33_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"E Coffman Jr","year":"1978","unstructured":"Coffman E Jr, Garey M, Johnson D (1978) An application of bin-packing to multiprocessor scheduling. SIAM J Comput 7:1","journal-title":"SIAM J Comput"},{"issue":"2","key":"33_CR12","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0196-6774(02)00202-X","volume":"44","author":"J Csirik","year":"2002","unstructured":"Csirik J, Woeginger GJ (2002) Resource augmentation for online bounded space bin packing. J Algorithms 44(2):308\u2013320","journal-title":"J Algorithms"},{"key":"33_CR13","unstructured":"Enomaly Inc (2008) Enomaly: Elastic computing. http:\/\/enomalism.com"},{"key":"33_CR14","volume-title":"Proceedings of cloud computing and its applications","author":"C Evangelinos","year":"2008","unstructured":"Evangelinos C, Hill CN (2008) Cloud computing for parallel scientific hpc applications: feasibility of running coupled atmosphere-ocean climate models on amazon\u2019s ec2. In: Proceedings of cloud computing and its applications. http:\/\/www.cca08.org"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1109\/ICDCS.2003.1203506","volume-title":"Proceedings 23rd international conference on distributed computing systems","author":"R Figueiredo","year":"2003","unstructured":"Figueiredo R, Dinda P, Fortes J (2003) A case for grid computing on virtual machines. In: Proceedings 23rd international conference on distributed computing systems, pp 550\u2013559. doi:10.1109\/ICDCS.2003.1203506"},{"key":"33_CR16","first-page":"513","volume-title":"CCGRID","author":"IT Foster","year":"2006","unstructured":"Foster IT, Freeman T, Keahey K, Scheftner D, Sotomayor B, Zhang X (2006) Virtual clusters for grid communities. In: CCGRID. IEEE Computer Society, Los Alamitos, pp 513\u2013520"},{"key":"33_CR17","first-page":"640","volume-title":"IEEE international conference on eScience","author":"C Hoffa","year":"2008","unstructured":"Hoffa C, Mehta G, Freeman T, Deelman E, Keahey K, Berriman B, Good J (2008) On the use of cloud computing for scientific workflows. In: IEEE international conference on eScience, vol\u00a00, pp\u00a0640\u2013645. http:\/\/doi.ieeecomputersociety.org\/10.1109\/eScience.2008.167"},{"key":"33_CR18","volume-title":"Job scheduling strategies for parallel processing, 10th international workshop, JSSPP 2004","author":"CB Lee","year":"2005","unstructured":"Lee CB, Schwartzman Y, Hardy J, Snavely A (2005) Are user runtime estimates inherently inaccurate? In: Job scheduling strategies for parallel processing, 10th international workshop, JSSPP 2004. Springer, Berlin"},{"issue":"2","key":"33_CR19","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.jpdc.2006.09.003","volume":"67","author":"C Li","year":"2007","unstructured":"Li C, Li L (2007) Utility-based QoS optimisation strategy for multi-criteria scheduling on the grid. J Parallel Distrib Comput 67(2):142\u2013153","journal-title":"J Parallel Distrib Comput"},{"key":"33_CR20","unstructured":"Message Passing Interface Forum (1994) MPI: a message-passing interface standard. Tech rep, University of Tennessee, Knoxville, TN, USA"},{"issue":"6","key":"33_CR21","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/71.932708","volume":"12","author":"AW Mu\u2019alem","year":"2001","unstructured":"Mu\u2019alem AW, Feitelson DG (2001) Utilization predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling. IEEE Trans Parallel Distrib Syst 12(6):529\u2013543","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"33_CR22","volume-title":"First international conference on e-science and grid computing","author":"M Netto","year":"2005","unstructured":"Netto M, Calheiros R, Silva R, De Rose C, Northfleet\u00a0C, Cirne\u00a0W (2005) Transparent resource allocation to exploit idle cluster nodes in computational grids. In: First international conference on e-science and grid computing"},{"key":"33_CR23","volume-title":"Proceedings of cloud computing and its applications","author":"D Nurmi","year":"2008","unstructured":"Nurmi D, Wolski R, Grzegorczyk C, Obertelli G, Soman S, Youseff L, Zagorodnov D (2008) The eucalyptus open-source cloud-computing system. In: Proceedings of cloud computing and its applications. http:\/\/www.cca08.org"},{"key":"33_CR24","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-72521-3_18","volume-title":"Languages and compilers for parallel computing","author":"S Olivier","year":"2007","unstructured":"Olivier S, Huan J, Liu J, Prins J, Dinan J, Sadayappan P, Tseng CW (2007) Uts: an unbalanced tree search benchmark. In: Alm\u00e1si G, Cascaval C, Wu P (eds) Languages and compilers for parallel computing. Lecture notes in computer science, vol 4382. Springer, Berlin, pp 235\u2013250. doi:10.1007\/978-3-540-72521-3-18"},{"key":"33_CR25","unstructured":"Persistence of Vision Raytracer Pty Ltd (2008) Persistence of vision raytracer. http:\/\/www.povray.org\/"},{"key":"33_CR26","unstructured":"Python Software Foundation (2008) Python programming language. http:\/\/python.org\/"},{"issue":"5","key":"33_CR27","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.future.2007.05.005","volume":"24","author":"CAFD Rose","year":"2008","unstructured":"Rose CAFD, Ferreto T, Calheiros RN, Cirne W, Costa LB, Fireman D (2008) Allocation strategies for utilization of space-shared resources in bag of tasks grids. Future Gener Comput Syst 24(5):331\u2013341","journal-title":"Future Gener Comput Syst"},{"key":"33_CR28","first-page":"9:1","volume-title":"Proceedings of the 6th international workshop on Middleware for grid computing, MGC\u201908","author":"JN Silva","year":"2008","unstructured":"Silva JN, Veiga L, Ferreira P (2008) Heuristic for resources allocation on utility computing infrastructures. In: Proceedings of the 6th international workshop on Middleware for grid computing, MGC\u201908. ACM, New York, pp\u00a09:1\u20139:6. http:\/\/doi.acm.org\/10.1145\/1462704.1462713"},{"key":"33_CR29","unstructured":"SimPy Developer Team: Simpy homepage (2009) http:\/\/simpy.sourceforge.net\/"},{"key":"33_CR30","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/1383422.1383434","volume-title":"HPDC","author":"B Sotomayor","year":"2008","unstructured":"Sotomayor B, Keahey K, Foster IT (2008) Combining batch execution and leasing using virtual machines. In: Parashar M, Schwan K, Weissman JB, Laforenza D (eds) HPDC. ACM, New York, pp\u00a087\u201396"},{"key":"33_CR31","unstructured":"Viale E (2010) Yasrt\u2014yet another simple raytracer. http:\/\/www.yasrt.org\/"},{"key":"33_CR32","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/CCGrid.2004.1336550","volume-title":"IEEE international symposium on cluster computing and the grid, 2004. CCGrid 2004","author":"D Zhou","year":"2004","unstructured":"Zhou D, Lo V (2004) Cluster computing on the fly: resource discovery in a cycle sharing peer-to-peer system. In: IEEE international symposium on cluster computing and the grid, 2004. CCGrid 2004, pp 66\u201373"}],"container-title":["Journal of Internet Services and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13174-011-0033-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13174-011-0033-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s13174-011-0033-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13174-011-0033-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T01:00:04Z","timestamp":1686272404000},"score":1,"resource":{"primary":{"URL":"https:\/\/jisajournal.springeropen.com\/articles\/10.1007\/s13174-011-0033-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,27]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["33"],"URL":"https:\/\/doi.org\/10.1007\/s13174-011-0033-z","relation":{},"ISSN":["1867-4828","1869-0238"],"issn-type":[{"value":"1867-4828","type":"print"},{"value":"1869-0238","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,27]]},"assertion":[{"value":"8 November 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}