research-article

Latency modeling and minimization for large-scale scientific workflows in distributed network environments

Authors:

Nageswara S. V. RaoAuthors Info & Claims

ANSS '11: Proceedings of the 44th Annual Simulation Symposium

Pages 205 - 212

Published: 03 April 2011 Publication History

Abstract

Large-scale e-science applications feature complex workflows consisting of many computing modules. Mapping such workflows in distributed network environments and minimizing their latency are crucial to those applications that require fast system response and prompt user interaction. We model the time cost of each workflow component and design an efficient algorithm to compute the exact end-to-end delay of the entire workflow by explicitly accounting for the resource sharing dynamics. We further propose a workflow mapping approach to minimize the workflow latency using a recursive optimization procedure. The validity of the cost models and the accuracy of the latency computing algorithm are verified in comparison with an approximate solution, a dynamic system simulation program, and a workflow engine deployed in a real network. The performance superiority of the proposed mapping approach is illustrated by extensive simulation-based comparisons with existing algorithms.

References

[1]

B. Agarwalla, N. Ahmed, D. Hilley, and U. Ramachandran. Streamline: a scheduling heuristic for streaming application on the grid. In Proc. of the 13th Multimedia Comp. and Net. Conf., San Jose, CA, 2006.

[2]

A. F. Bashir, V. Susarla, and K. Vairavan. A statistical study of the performance of a task scheduling algorithm. IEEE Trans. on Computers, 32(12):774--777, Dec. 1975.

Digital Library

[3]

C. Boeres, J. V. Filho, and V. E. F. Rebello. A cluster-based strategy for scheduling task on heterogeneous processors. In Proc. of 16th Symp. on Computer Architecture and High Performance Computing, pages 214--221, 2004.

Digital Library

[4]

D. Bozdag, U. Catalyurek, and F. Ozguner. A task duplication based bottom-up scheduling algorithm for heterogeneous environments. In Proc. of the 20th Int. Parallel and Distributed Processing Symposium, Apr. 2006.

Digital Library

[5]

T. D. Braun, H. J. Siegel, N. Beck, L. L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, and R. F. Freund. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. JPDC, 61(6):810--837, June 2001.

Digital Library

[6]

V. Chaudhary and J. K. Aggarwal. A generalized scheme for mapping parallel algorithms. IEEE Trans. on Parallel and Distributed Systems, 4(3):328--346, May 1993.

Digital Library

[7]

L. Chen and G. Agrawal. Resource allocation in a middleware for streaming data. In Proc. of the 2nd Workshop on Middleware for Grid Comp., Toronto, Canada, Oct. 2004.

Digital Library

[8]

L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. An improved algorithm for matching large graphs. In Proc. of the 3rd IAPR-TC-15 Int. Workshop on Graph-based Representations, Italy, 2001.

[9]

A. Gerasoulis and T. Yang. A comparison of clustering heuristics for scheduling DAGs on multiprocessors. JPDC, 16(4):276--291, Dec. 1992.

[10]

J. Hopcroft and J. Wong. Linear time algorithm for isomorphism of planar graphs. In Proc. of the 6th Annual ACM Symp., Theory of Computing, pages 172--184, 1974.

Digital Library

[11]

Y. Kwok and I. Ahmad. Dynamic critical-path scheduling: An effective technique for allocating task graph to multiprocessors. IEEE Trans. on Parallel and Distributed Systems, 7(5):506--521, May 1996.

Digital Library

[12]

Y. Kwok and I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406--471, Dec. 1999.

Digital Library

[13]

E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. of Computer System Science, pages 42--65, 1982.

[14]

T. Ma and R. Buyya. Critical-path and priority based algorithms for scheduling workflows with parameter sweep tasks on global grids. In Proc. of the 17th Int. Symp. on Computer Architecture on HPC, pages 251--258, 2005.

Digital Library

[15]

C. McCreary, A. A. Khan, J. J. Thompson, and M. E. McArdle. A comparison of heuristics for scheduling DAGs on multiprocessors. In Proc. of the 8th Int. Symp. on Parallel Processing, pages 446--451. IEEE Computer Society, 1994.

Digital Library

[16]

B. T. Messmer. Efficient Graph Matching Algorithms for Pre-processed Model Graphs. PhD thesis, Institute of Computer Science and Applied Mathematics, University of Bern, 1996.

[17]

M. Rahman, S. Venugopal, and R. Buyya. A dynamic critical path algorithm for scheduling scientific workflow applications on global grids. In Proc. of the 3rd IEEE Int. Conf. on e-Sci. and Grid Comp., pages 35--42, 2007.

Digital Library

[18]

A. Sekhar, B. S. Manoj, and C. S. R. Murthy. A state-space search approach for optimizing reliability and cost of execution in distributed sensor networks. In Proc. of Int. Workshop on Dist. Comp., pages 63--74, 2005.

Digital Library

[19]

B. Shirazi, M. Wang, and G. Pathak. Analysis and evaluation of heuristic methods for static scheduling. J. of Parallel and Distributed Computing, (10):222--232, 1990.

Digital Library

[20]

P. Shroff, D. W. Watson, N. S. Flann, and R. F. Freund. Genetic simulated annealing for scheduling data-dependent tasks in heterogeneous environments. In Proc. of Heterogeneous Computing Workshop, pages 98--104, Apr. 1996.

[21]

G. C. Sih and E. A. Lee. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. on Para. and Dist. Systems, 4(2):175--187, 1993.

Digital Library

[22]

H. Topcuoglu, S. Hariri, and M. Y. Wu. Performance effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. on Parallel and Distributed Systems, 13(3), 2002.

Digital Library

[23]

L. Wang, H. J. Siege, V. P. Roychowdhury, and A. A. Maciejewski. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J. of Parallel and Distributed Computing, 47:8--22, 1997.

Digital Library

[24]

M. Wieczorek, R. Prodan, and T. Fahringer. Scheduling of scientific workflows in the ASKALON grid environment. ACM SIGMOD, Record J., 34(3):56--62, Sep. 2005.

Digital Library

[25]

Q. Wu and Y. Gu. Supporting distributed application workflows in heterogeneous computing environments. In Proc. of the 14th IEEE Int. Conf. on Parallel and Distributed Systems, pages 3--10, Melbourne, Australia, Dec. 2008.

Digital Library

[26]

Q. Wu, Y. Gu, and Z. Wang. Simulation-based analysis of performance dynamics of distributed applications in heterogeneous network environments. In SpringSim'09: Proc. of the 2009 Spring Simulation Multiconference, pages 1--8, San Diego, CA, March 22--27 2009.

Digital Library

[27]

Q. Wu, M. Zhu, X. Lu, P. Brown, Y. Lin, Y. Gu, F. Cao, and M. A. Reuter. Automation and management of scientific workflows in distributed network environments. In Proc. of the 6th Int. Workshop on Sys. Man. Tech., Proc., and Serv., Atlanta, GA, April 19 2010.

Cited By

Cao FZhu M(2018)Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environmentInternational Journal of High Performance Computing and Networking10.1504/IJHPCN.2015.0727838:4(324-336)Online publication date: 19-Dec-2018
https://dl.acm.org/doi/10.1504/IJHPCN.2015.072783
Wu QZhu MGu YBrown PLu XLin WLiu Y(2018)A Distributed Workflow Management System with Case Study of Real-life Scientific Applications on GridsJournal of Grid Computing10.1007/s10723-012-9222-710:3(367-393)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1007/s10723-012-9222-7

Index Terms

Latency modeling and minimization for large-scale scientific workflows in distributed network environments

Recommendations

Using Explicit Control Processes in Distributed Workflows to Gather Provenance
Provenance and Annotation of Data and Processes

Distributing workflow tasks among high performance environments involves local processing and remote execution on clusters and grids. This dis-tribution often needs interoperation between heterogeneous workflow definition languages and their ...
Deploying High Throughput Scientific Workflows on Container Schedulers with Makeflow and Mesos
CCGrid '17: Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing

Workflows are a widely used abstraction for describing large scientific applications and running them on distributed systems. However, most workflow systems have been silent on the question of what execution environment each task in the workflow is ...
Fine-Grain Interoperability of Scientific Workflows in Distributed Computing Infrastructures

Today there exist a wide variety of scientific workflow management systems, each designed to fulfill the needs of a certain scientific community. Unfortunately, once a workflow application has been designed in one particular system it becomes very hard ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ANSS '11: Proceedings of the 44th Annual Simulation Symposium

April 2011

238 pages

ISBN:1930638566

General Chair:
Saad Biaz,
Program Chair:
Shaoen Wu

Sponsors

SCS: Society for Modeling and Simulation International

In-Cooperation

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Society for Computer Simulation International

San Diego, CA, United States

Publication History

Published: 03 April 2011

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SpringSim '11

Sponsor:

SCS

SpringSim '11: 2011 Spring Simulation Multi-conference

April 3 - 7, 2011

Massachusetts, Boston

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
117
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cao FZhu M(2018)Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environmentInternational Journal of High Performance Computing and Networking10.1504/IJHPCN.2015.0727838:4(324-336)Online publication date: 19-Dec-2018
https://dl.acm.org/doi/10.1504/IJHPCN.2015.072783
Wu QZhu MGu YBrown PLu XLin WLiu Y(2018)A Distributed Workflow Management System with Case Study of Real-life Scientific Applications on GridsJournal of Grid Computing10.1007/s10723-012-9222-710:3(367-393)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1007/s10723-012-9222-7

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.

Figures

Tables

Media

View Table of Conten