research-article

Cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds

Authors:

Maciej Malawski,

Jarek NabrzyskiAuthors Info & Claims

SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

Article No.: 22, Pages 1 - 11

Published: 10 November 2012 Publication History

Abstract

Large-scale applications expressed as scientific workflows are often grouped into ensembles of inter-related workflows. In this paper, we address a new and important problem concerning the efficient management of such ensembles under budget and deadline constraints on Infrastructure- as-a-Service (IaaS) clouds. We discuss, develop, and assess algorithms based on static and dynamic strategies for both task scheduling and resource provisioning. We perform the evaluation via simulation using a set of scientific workflow ensembles with a broad range of budget and deadline parameters, taking into account uncertainties in task runtime estimations, provisioning delays, and failures. We find that the key factor determining the performance of an algorithm is its ability to decide which workflows in an ensemble to admit or reject for execution. Our results show that an admission procedure based on workflow structure and estimates of task runtimes can significantly improve the quality of solutions.

References

[1]

S. Callaghan, P. Maechling, P. Small, K. Milner, G. Juve, T. Jordan, E. Deelman, G. Mehta, K. Vahi, D. Gunter, K. Beattie, and C. X. Brooks, "Metrics for heterogeneous scientific workflows: A case study of an earthquake science application," International Journal of High Performance Computing Applications, vol. 25, no. 3, pp. 274--285, 2011.

Digital Library

[2]

E. Deelman, G. Singh, M. Livny, B. Berriman, and J. Good, "The cost of doing science on the cloud: The montage example," in 2008 ACM/IEEE Conference on Supercomputing (SC 08), 2008.

Digital Library

[3]

J. Vöckler, G. Juve, E. Deelman, M. Rynge, and G. B. Berriman, "Experiences using cloud computing for a scientific workflow application," in 2nd Workshop on Scientific Cloud Computing (ScienceCloud '11), 2011.

Digital Library

[4]

S. Ostermann, A. Iosup, N. Yigitbasi, R. Prodan, T. Fahringer, and D. Epema, "A performance analysis of EC2 cloud computing services for scientific computing," in Cloud Computing, ser. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, O. Akan et al., Eds. Springer Berlin Heidelberg, 2010, vol. 34, pp. 115--131.

[5]

K. Keahey, M. Tsugawa, A. Matsunaga, and J. Fortes, "Sky computing," IEEE Internet Computing, vol. 13, no. 5, pp. 43--51, 2009.

Digital Library

[6]

D. Durkee, "Why cloud computing will never be free," Communications of the ACM, vol. 53, no. 5, pp. 62--69, May 2010.

Digital Library

[7]

R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. F. De Rose, and R. Buyya, "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms," Software: Practice and Experience, vol. 41, no. 1, pp. 23--50, Jan. 2011.

Digital Library

[8]

"Amazon Auto Scaling." {Online}. Available: http://aws.amazon.com/autoscaling

[9]

"RightScale." {Online}. Available: http://www.rightscale.com

[10]

P. Marshall, K. Keahey, and T. Freeman, "Elastic site: Using clouds to elastically extend site resources," in 10th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2010), 2010.

Digital Library

[11]

H. Kim, Y. el-Khamra, I. Rodero, S. Jha, and M. Parashar, "Autonomic management of application workflows on hybrid computing infrastructure," Scientific Programming, vol. 19, pp. 75--89, April 2011.

Digital Library

[12]

J. Yu, R. Buyya, and C. Tham, "Cost-Based scheduling of scientific workflow application on utility grids," in First International Conference on e-Science and Grid Computing, 2005.

Digital Library

[13]

S. Abrishami, M. Naghibzadeh, and D. Epema, "Cost-driven scheduling of grid workflows using partial critical paths," in 11th IEEE/ACM International Conference on Grid Computing, 2010.

[14]

M. Mao and M. Humphrey, "Auto-scaling to minimize cost and meet application deadlines in cloud workflows," in 2011 ACM/IEEE Conference on Supercomputing (SC '11), 2011.

Digital Library

[15]

M. Wieczorek, A. Hoheisel, and R. Prodan, "Towards a general model of the multi-criteria workflow scheduling on the grid," Future Generation Computer Systems, vol. 25, no. 3, pp. 237--256, Mar. 2009.

Digital Library

[16]

R. Prodan and M. Wieczorek, "Bi-Criteria Scheduling of Scientific Grid Workflows," IEEE Transactions on Automation Science and Engineering, vol. 7, no. 2, pp. 364--376, 2010.

[17]

J. J. Dongarra, E. Jeannot, E. Saule, and Z. Shi, "Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on Heterogeneous Systems," in 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '07), 2007.

Digital Library

[18]

A. K. M. K. A. Talukder, M. Kirley, and R. Buyya, "Multiobjective differential evolution for scheduling workflow applications on global Grids," Concurrency Computation: Practice and Experience, vol. 21, no. 13, pp. 1742--1756, 2009.

Digital Library

[19]

S. Pandey, L. Wu, S. M. Guru, and R. Buyya, "A Particle Swarm Optimization-Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments," in International Conference on Advanced Information Networking and Applications, 2010.

Digital Library

[20]

R. Sakellariou, H. Zhao, E. Tsiakkouri, and M. D. Dikaiakos, "Scheduling workflows with budget constraints," in Integrated Research in GRID Computing, ser. COREGrid Series. Springer-Verlag, 2007.

[21]

G. Juve, E. Deelman, K. Vahi, G. Mehta, B. Berriman, B. P. Berman, and P. Maechling, "Scientific workflow applications on amazon EC2," in 2009 5th IEEE International Conference on E-Science Workshops, Dec. 2009.

[22]

S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M. Su, and K. Vahi, "Characterization of scientific workflows," in 3rd Workshop on Workflows in Support of Large Scale Science (WORKS 08), 2008.

[23]

"Workflow Generator." {Online}. Available: https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator

[24]

"Cloud Workflow Simulator." {Online}. Available: https://github.com/malawski/cloudworkflowsimulator

[25]

E. Deelman, G. Singh, M. Su, J. Blythe, Y. Gil, C. Kesselman, G. Mehta, K. Vahi, G. B. Berriman, J. Good, A. Laity, J. C. Jacob, and D. S. Katz, "Pegasus: A framework for mapping complex scientific workflows onto distributed systems," Scientific Programming, vol. 13, no. 3, pp. 219--237, 2005.

Digital Library

[26]

G. Juve, E. Deelman, K. Vahi, G. Mehta, B. P. Berman, B. Berriman, and P. Maechling, "Data sharing options for scientific workflows on amazon EC2," in 2010 ACM/IEEE conference on Supercomputing (SC 10), 2010.

Digital Library

[27]

D. Nurmi, R. Wolski, C. Grzegorczyk, G. Obertelli, S. Soman, L. Youseff, and D. Zagorodnov, "Eucalyptus: A technical report on an elastic utility computing architecture linking your programs to useful systems," UCSB Computer Science Technical Report 2008-10, 2008.

[28]

G. Juve and E. Deelman, "Automating Application Deployment in Infrastructure Clouds," in 3rd IEEE International Conference on Cloud Computing Technology and Science (CloudCom 2011), 2011.

Digital Library

[29]

National Energy Research Scientific Computing Center (NERSC), "Magellan." {Online}. Available: http://magellan.nersc.gov

[30]

"FutureGrid." {Online}. Available: http://futuregrid.org/

Cited By

Zhou AXiao YHe BIbrahim SCheng R(2019)Incorporating Probabilistic Optimizations for Resource Provisioning of Data Processing WorkflowsProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337847(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337847
Adhikari MAmgoth TSrirama S(2019)A Survey on Scheduling Strategies for Workflows in Cloud Environment and Emerging TrendsACM Computing Surveys10.1145/332509752:4(1-36)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3325097
Nikitin NVychuzhanin PHvatov ADeeva IKalyuzhnaya AKovalchuk SAuger AStützle T(2019)Deadline-driven approach for multi-fidelity surrogate-assisted environmental model calibrationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326876(1583-1591)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326876
Show More Cited By

Cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Algorithms for cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds

Large-scale applications expressed as scientific workflows are often grouped into ensembles of inter-related workflows. In this paper, we address a new and important problem concerning the efficient management of such ensembles under budget and deadline ...
Cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds
SC '12: Proceedings of the 2012 International Conference for High Performance Computing, Networking, Storage and Analysis

Large-scale applications expressed as scientific workflows are often grouped into ensembles of inter-related workflows. In this paper, we address a new and important problem concerning the efficient management of such ensembles under budget and deadline ...
Executing Large Scale Scientific Workflow Ensembles in Public Clouds
ICPP '15: Proceedings of the 2015 44th International Conference on Parallel Processing (ICPP)

Scientists in different fields, such as high energy physics, earth science, and astronomy are developing large-scale workflow applications. In many use cases, scientists need to run a set of interrelated but independent workflows (i.e., Workflow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

November 2012

1161 pages

ISBN:9781467308045

General Chair:
Jeffrey K. Hollingsworth
University of Maryland

Sponsors

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 10 November 2012

Check for updates

Qualifiers

Research-article

Conference

SC '12

Sponsor:

SIGHPC
SIGARCH
IEEE-CS

SC '12: International Conference for High Performance Computing, Networking, Storage and Analysis

November 10 - 16, 2012

Utah, Salt Lake City

Acceptance Rates

SC '12 Paper Acceptance Rate 100 of 461 submissions, 22%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
804
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou AXiao YHe BIbrahim SCheng R(2019)Incorporating Probabilistic Optimizations for Resource Provisioning of Data Processing WorkflowsProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337847(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337847
Adhikari MAmgoth TSrirama S(2019)A Survey on Scheduling Strategies for Workflows in Cloud Environment and Emerging TrendsACM Computing Surveys10.1145/332509752:4(1-36)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3325097
Nikitin NVychuzhanin PHvatov ADeeva IKalyuzhnaya AKovalchuk SAuger AStützle T(2019)Deadline-driven approach for multi-fidelity surrogate-assisted environmental model calibrationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326876(1583-1591)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326876
Chahal DMathew BNambiar MApte VDi Marco ALitoiu MMerseguer J(2019)Simulation Based Job Scheduling Optimization for Batch WorkloadsProceedings of the 2019 ACM/SPEC International Conference on Performance Engineering10.1145/3297663.3310312(313-320)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297663.3310312
Ilyushkin AAli-Eldin AHerbst NBauer APapadopoulos AEpema DIosup A(2018)An Experimental Performance Evaluation of Autoscalers for Complex WorkflowsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/31645373:2(1-32)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3164537
Zhang MLi HLiu LBuyya R(2018)An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in CloudsDistributed and Parallel Databases10.1007/s10619-017-7215-z36:2(339-368)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10619-017-7215-z
Gonzalez NCarvalho TMiers C(2017)Cloud resource managementJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-017-0081-46:1(1-20)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1186/s13677-017-0081-4
Muhammad-Bello BAritsugi MAnjum ASill AFox GChen Y(2017)Robust Deadline-Constrained Resource Provisioning and Workflow Scheduling Algorithm for Handling Performance Uncertainty in IaaS CloudsCompanion Proceedings of the10th International Conference on Utility and Cloud Computing10.1145/3147234.3148110(29-34)Online publication date: 5-Dec-2017
https://dl.acm.org/doi/10.1145/3147234.3148110
Rodriguez MBuyya R(2017)Budget-Driven Scheduling of Scientific Workflows in IaaS Clouds with Fine-Grained Billing PeriodsACM Transactions on Autonomous and Adaptive Systems10.1145/304103612:2(1-22)Online publication date: 29-May-2017
https://dl.acm.org/doi/10.1145/3041036
Sharif SWatson PTaheri JNepal SZomaya A(2017)Privacy-Aware Scheduling SaaS in High Performance Computing EnvironmentsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.260315328:4(1176-1188)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2603153
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents