Nimrod/K: towards massively parallel dynamic grid workflows

ABSTRACT

A challenge for Grid computing is the difficulty in developing software that is parallel, distributed and highly dynamic. Whilst there have been many general purpose mechanisms developed over the years, Grid programming still remains a low level, error prone task. Scientific workflow engines can double as programming environments, and allow a user to compose 'virtual' Grid applications from pre-existing components. Whilst existing workflow engines can specify arbitrary parallel programs, (where components use message passing) they are typically not effective with large and variable parallelism. Here we discuss dynamic dataflow, originally developed for parallel tagged dataflow architectures (TDAs), and show that these can be used for implementing Grid workflows. TDAs spawn parallel threads dynamically without additional programming. We have added TDAs to Kepler, and show that the system can orchestrate workflows that have large amounts of variable parallelism. We demonstrate the system using case studies in chemistry and in cardiac modelling.

REFERENCES

• 1: David Abramson , Andrew Lewis , Tom Peachey , Clive Fletcher, An automatic design optimization tool and its application to computational fluid dynamics, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.25-25, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582059]
• 2: D. Abramson , G. Egan, The RMIT data flow computer: a hybrid architecture, The Computer Journal, v.33 n.3, p.230-240, June 1990 [doi>10.1093/comjnl/33.3.230]
• 3: High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid?, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.520, May 01-05, 2000
• 4: Altintas, I. Berkley, C. Jaeger, E. Jones, M. Ludäscher B. and Mock, S. "Kepler: Towards a Grid-Enabled System for Scientific Workflows," in the Workflow in Grid Systems Workshop in GGF10 - The 10th Global Grid Forum, Berlin, March 2004.
• 5: Altintas, I., Birnbaum, A., Baldridge, K., Sudholt, W., Miller, M., Amoreira, C., Potier Y. and Ludaescher, B. "A Framework for the Design and Reuse of Grid Workflows" Intl. Workshop on Scientific Applications on Grid Computing (SAG '04), LNCS 3458, Springer, 2005.
• 6: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• 7: Shahaan Ayyub , David Abramson, GridRod: a dynamic runtime scheduler for grid workflows, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1274980]
• 8: Casanova H. and Berman, F. "Parameter Sweeps on The Grid With APST", chapter 26. Wiley Publisher, Inc., 2002. F. Berman, G. Fox, and T. Hey, editors.
• 9: Culler. D. "Managing Parallelism and Resources in Scientific Dataflow Programs", PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, March 1990.
• 10: Deelman, E. Blythe, J. Gil, Y. Kesselman, C. Mehta, G. Vahi. K. "Mapping Abstract Complex Workflows onto Grid Environments", Journal of Grid Computing, 1:25--39, Kluwer Academic Publishers, Netherlands, 2003.
• 11: e-Science Grid Environments Workshop, e-Science Institute, Edinburgh, Scotland, May 2004, http://www.nesc.ac.uk/esi/events/.
• 12: Thomas Fahringer , Alexandru Jugravu , Sabri Pllana , Radu Prodan , Clovis Seragiotto, Jr. , Hong-Linh Truong, ASKALON: a tool set for cluster and Grid computing: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.143-169, February 2005 [doi>10.1002/cpe.v17:2/4]
• 13: Foster I. and Kesselman, C. "Globus: A Metacomputing Infrastructure Toolkit," Int 'l J. of Supercomputer Applications, vol. 11, no. 2, 1997, pp. 115--128.
• 14: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: Antoon Goderis , Christopher Brooks , Ilkay Altintas , Edward A. Lee , Carole Goble, Composing Different Models of Computation in Kepler and Ptolemy II, Proceedings of the 7th international conference on Computational Science, Part III: ICCS 2007, p.182-190, May 27-30, 2007, Beijing, China [doi>10.1007/978-3-540-72588-6_33]
• 16: Gurd J. R. and Watson I. "Data Driven System for High Speed Parallel Computing (1 & 2) Computer Design, vol. 9 nos. 6 & 7, June & July 1980, pp. 91--100 & 97--106.
• 17: http://kepler-project.org
• 18: http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIfaq.htm
• 19: http://taverna.sourceforge.net
• 20: http://www.-unix.globus.org/toolkit/
• 21: http://www.msg.ameslab.gov/GAMESS/
• 22: Lee, E. et al, "Overview of the Ptolemy Project," Technical Memorandum UCB/ERL M01/11, University of California, Berkeley, March 6, 2001.
• 23: Ludäscher, B., Altintas, I., Berkley, C., Higgins, D., Jaeger-Frank, E., Jones, M., Lee, E., Tao J. and Zhao, Y. "Scientific Workflow Management and the Kepler System", Concurrency and Computation: Practice & Experience, Special Issue on Scientific Workflows, 2005.
• 24: Tom Oinn , Matthew Addis , Justin Ferris , Darren Marvin , Martin Senger , Mark Greenwood , Tim Carver , Kevin Glover , Matthew R. Pocock , Anil Wipat , Peter Li, Taverna: a tool for the composition and enactment of bioinformatics workflows, Bioinformatics, v.20 n.17, p.3045-3054, November 2004 [doi>10.1093/bioinformatics/bth361]
• 25: T. C. Peachey , N. T. Diamond , D. A. Abramson , W. Sudholt , A. Michailova , S. Amirriazi, Fractional factorial design for parameter sweep experiments using Nimrod/E, Scientific Programming, v.16 n.2-3, p.217-230, April 2008
• 26: Michael W. Schmidt , Kim K. Baldridge , Jerry A. Boatz , Steven T. Elbert , Mark S. Gordon , Jan H. Jensen , Shiro Koseki , Nikita Matsunaga , Kiet A. Nguyen , Shujun Su , Theresa L. Windus , Michel Dupuis , John A. Montgomery, Jr., General atomic and molecular electronic structure system, Journal of Computational Chemistry, v.14 n.11, p.1347-1363, Nov. 1993 [doi>10.1002/jcc.540141112]
• 27: Scientific Data Management Framework Workshop, Argonne National Labs, August 2003. http://sdm.lbl.gov/~arie/sdm/SDM.Framework.wshp.htm
• 28: Sudholt, W., Baldridge, K. K., Abramson, D., Enticott C. and Garic, S. Applying Grid Computing to the Parameter Sweep of a Group Difference Pseudopotential, in Computational Science -- ICCS 2004: 4th International Conference, Kraków, Poland, June 6-9, 2004, Lecture Notes in Computer Science, v. 3036, 2004, pp. 148--155.
• 29: Wibke Sudholt , Kim K. Baldridge , David Abramson , Colin Enticott , Slavisa Garic, Parameter scan of an effective group difference pseudopotential using grid computing, New Generation Computing, v.22 n.2, p.137-146, January 2004 [doi>10.1007/BF03040952]
• 30: Wibke Sudholt , Kim K. Baldridge , David Abramson , Colin Enticott , Slavisa Garic , Chris Kondric , Duy Nguyen, Application of grid computing to parameter sweeps and optimizations in molecular modeling, Future Generation Computer Systems, v.21 n.1, p.27-35, 1 January 2005 [doi>10.1016/j.future.2004.09.010]
• 31: Todd Tannenbaum , Derek Wright , Karen Miller , Miron Livny, Condor: a distributed job scheduler, Beowulf cluster computing with Linux, MIT Press, Cambridge, MA, 2001
• 32: Taylor, I. Shields, M. and Wang. I. "Resource Management of Triana P2P Services", Grid Resource Management, Kluwer, Netherlands, June 2003.
• 33: Kaizar Amin , Gregor von Laszewski , Mihael Hategan , Nestor J. Zaluzec , Shawn Hampton , Albert Rossi, GridAnt: A Client-Controllable Grid Work.ow System, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 7, p.70210.3, January 05-08, 2004
• 34: Yu J., and Buyya, R., A Taxonomy of Workflow Management Systems for Grid Computing", Journal of Grid Computing, Springer Press, New York, USA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General

General Terms:
Design, Experimentation, Measurement, Performance