skip to main content
10.1145/1274971.1274980acmconferencesArticle/Chapter ViewAbstractPublication PagesicsConference Proceedingsconference-collections
Article

GridRod: a dynamic runtime scheduler for grid workflows

Published: 17 June 2007 Publication History

Abstract

Grid Workflows are emerging as practical programming models for solving large e-scientific problems on the Grid. However, it is typically assumed that the workflow components either read or write data to conventional files, which are copied from one execution stage to another, or they are tightly coupled using IPC libraries such as MPI or distributed streaming. More flexible communication can be achieved by overloading conventional READ and WRITE operations with advanced IO mechanisms such as sockets, streams and pipes, as is done in the GriddLeS environment. Such flexibility allows the pipelining of temporally dependent components, or in contrast, delaying of tightly coupled computations based on the current resource availability and network connectivity. However, it is also harder to schedule the workflow, because the communication mode may not be decided until run time. In this paper, we propose a new scheduling model that leverages such communication flexibility and allows us to generate dynamic runtime schedules. The scheduler in this case, not only allocates components to distributed Grid resources, but also specifies the inter-component communication mechanism (socket, pipe etc.) The current model is implemented as a dynamic workflow scheduling tool called GridRod, which harnesses Nimrod/G's [1] Grid services and GriddLeS [2] web services.

References

[1]
Abramson, D., et al., High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid?, in International Parallel and Distributed Processing Symposium. 2000.
[2]
Abramson, D. and J. Komineni, A Flexible IO Scheme for Grid Workflows, in IPDPS-04. 2004: New Mexico.
[3]
Ilkay Altintas, A. B., Kim Baldridge, Wibke Sudholt, Mark Miller, Celine Amoreira, Yohann Potier and Bertram Ludaescher. A Framework for the Design and Reuse of Grid Workflows. in Intl. Workshop on Scientific Applications on Grid Computing (SAG'04). 2005: Springer.
[4]
The Taverna Project. {cited; Available from: http://taverna.sourceforge.net.
[5]
The Genie Project. {cited; Available from: http://www.genie.ac.uk
[6]
Anthony Mayer, S. M., Nathalie Furmento, Jeremy Cohen, Murtaza Gulamali, Laurie Young, Ali Afzal Contact Information, Steven Newhouse and John Darlington. ICENI: An Integrated Grid Middleware to Support E-Science. in Workshop on Component Models and Systems for Grid Applications. 2004. Saint Malo, France: Springer US.
[7]
K. Seymour, H. N., S. Matsuoka, D. Dongarra, C. Lee, and H. Casanova, GridRPC: A remote procedure call api for grid computing, in ICL Technical Report ICL-UT-02-06. June 2002, Innovative Computing Laboratory, Department of Computer Science, University of Tennessee: Baltimore, MD, USA.
[8]
The VrGrads Project. {cited; Available from: http://vgrads.rice.edu/.
[9]
The Kepler Project. {cited; Available from: http://keplerproject.org/.
[10]
Messerschmitt, E.A.L.a.D.G. Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing. in IEEE Transactions on Computers. Jan 1987.
[11]
Thomas L. Adam, K. M. C., J. R. Dickson. A comparison of list schedules for parallel processing systems. in Communications of the ACM. 1974: ACM Press New York, NY, USA.
[12]
Messerschmitt, E.A.L.a.D.G. Synchronous Data Flow. in Proceedings of the IEEE. 1987.
[13]
Kahn., G. The Semantics of a Simple language for Parallel Programming. in In Proceedings of IFIP Congress. 1974: North Holland Publishing Company.
[14]
Matias, P.B.G.a.Y. New sampling-based summary statistics for improving approximate query answers. in Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 1998. Seattle, Washington, United States.
[15]
Charu C. Aggarwal, J. H., Jianyong Wang, Philip S. Yu. A Framework for Clustering Evolving Data Streams in In Proceeings of the 29th VLDB conference. 2003.
[16]
Liang Chen Reddy, K. A., G.GATES: a grid-based middleware for processing distributed data streams. in In Proceedings of IEEE Conference on High performance Distributed Computing, 2004. Proceedings. 4-6 June 2004: IEEE Computer Society Press.
[17]
Ahmad, Y.-K.K.a.I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. in ACM Computing Surveys. 1999.
[18]
Anthony Mayer, S. M., Nathalie Furmento, William Lee, Steven Newhouse, John Darlington. ICENI Dataflow and Workflow: Composition and Scheduling in Space and Time in Proceedings of the Workshop on Component Models and Systems for Grid Applications. 2003. Saint Malo, France: SpringerLink.
[19]
Ron Oldfield, D. K., Applications of Parallel I/O Oct 1996.
[20]
Abramson, D., Kommineni, J., McGregor, J. and Katzfey, J. An Atmospheric Sciences Workflow and its Implementation with Web Services. in The International Conference on Computational Sciences. June 6 - 9, 2004. Krakow Poland.
[21]
Jette., M. A. Performance Characteristics of Gang Scheduling in Multiprogrammed Environments. in In Proceedings of the 1997 ACM/IEEE conference on Supercomputing. Nov - 1997.
[22]
Luiz Meyer, Mike Wilde, Marta Mattoso, Ian Foster. Planning spatial workflows to optimize grid performance. in Distributed systems and grid computing (DSGC). 2006: ACM Press New York, NY, USA.
[23]
Casanova, H., et al. Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. in In Proceedings of the 9th Heterogeneous Computing Workshop (HCW00). 2000.
[24]
Casanova, H., et al., The AppLeS Parameter Sweep Template: User-Level Middleware for the Grid, in In Proceedings of the Super Computing Conference (SC'2000). 2001.
[25]
Abramson, J.K.a.D. GriddLeS Enhancements and Building Virtual Applications for the GRID with Legacy Components. in European grid conference. 2005. Amsterdam: Springer.
[26]
Stiles, J. R., et al., Monte Carlo simulation of neuromuscular transmitter release using MCell, a general simulator of cellular physiological processes. Computational Neuroscience, 1998: p. 279--284.
[27]
Foster, I. and C. Kesselman, Globus: A Meta-computing Infrastructure Toolkit. International Journal of Supercomputer Applications, 1997. 11(2): p. 115--128.
[28]
Hategan, M., et al., GridAnt - A Client Controllable Grid Workflow System. 2003, Argonne National Laboratory.
[29]
Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors. 1989: Paperback. 215.
[30]
S. Cheng, J.S.a.K.R. Dynamic Scheduling of Groups of Tasks with Precedence Constraints in Distributed Hard Real-Time Systems. in Real-Time Symposium. December 1986.
[31]
H. Topcuoglu, S. H., and M. Y. Wu. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. in IEEE Trans. Parallel and Distributed Systems. 2002.
[32]
Andrea C. Arpaci-Dusseau, D. E. C., Alan M. Mainwaring. Scheduling with Implicit Information in Distributed Systems. in Joint Conference Measurement and Modeling Computer Systems. 1998. Madison, Wisconsin.
[33]
Python xml.dom
[34]
DAGMan (Directed Acyclic Graph Manager).
[35]
Garg, A.a.R., Adrian Straight-Line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio. in Proceedings Graph Drawing. 2002. Irvine, CA, USA.
[36]
Rich Wolski, N.T.S., Jim Hayes. The Network Weather Service: A Distributed Resource Performance Forecasting Service for Metacomputing in Future Generation Computer Systems. 1998.

Cited By

View all
  • (2017)A task-based parallel rendering component for large-scale visualization applicationsProceedings of the 17th Eurographics Symposium on Parallel Graphics and Visualization10.2312/pgv.20171094(63-71)Online publication date: 12-Jun-2017
  • (2015)A Design Proposal for a Next Generation Scientific Software FrameworkEuro-Par 2015: Parallel Processing Workshops10.1007/978-3-319-27308-2_19(221-232)Online publication date: 18-Dec-2015
  • (2011)Parallel Mapping with Time Optimization for SLA-Aware Compositional Services in the Business GridIEEE Transactions on Services Computing10.1109/TSC.2011.274:3(196-206)Online publication date: Jul-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICS '07: Proceedings of the 21st annual international conference on Supercomputing
June 2007
315 pages
ISBN:9781595937681
DOI:10.1145/1274971
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. communication specification
  2. models of computation
  3. runtime scheduling
  4. spatial and temporal concurrency

Qualifiers

  • Article

Conference

ICS07
Sponsor:
ICS07: International Conference on Supercomputing
June 17 - 21, 2007
Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)A task-based parallel rendering component for large-scale visualization applicationsProceedings of the 17th Eurographics Symposium on Parallel Graphics and Visualization10.2312/pgv.20171094(63-71)Online publication date: 12-Jun-2017
  • (2015)A Design Proposal for a Next Generation Scientific Software FrameworkEuro-Par 2015: Parallel Processing Workshops10.1007/978-3-319-27308-2_19(221-232)Online publication date: 18-Dec-2015
  • (2011)Parallel Mapping with Time Optimization for SLA-Aware Compositional Services in the Business GridIEEE Transactions on Services Computing10.1109/TSC.2011.274:3(196-206)Online publication date: Jul-2011
  • (2009)Robust workflows for science and engineeringProceedings of the 2nd Workshop on Many-Task Computing on Grids and Supercomputers10.1145/1646468.1646469(1-9)Online publication date: 16-Nov-2009
  • (2008)Nimrod/KProceedings of the 2008 ACM/IEEE conference on Supercomputing10.5555/1413370.1413395(1-11)Online publication date: 15-Nov-2008
  • (2008)Nimrod/K: Towards massively parallel dynamic Grid workflows2008 SC - International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC.2008.5215726(1-11)Online publication date: Nov-2008
  • (2008)Optimizing the Execution Time of the SLA-based Workflow in the Grid with Parallel Processing TechnologyProceedings of the 2008 IEEE Asia-Pacific Services Computing Conference10.1109/APSCC.2008.114(15-20)Online publication date: 9-Dec-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media