Models and methods for the profiling and execution time estimation of workflows in supercomputing systems

Authors

  • G.I. Radchenko
  • L.B. Sokolinsky
  • A.V. Shamakina

Keywords:

profiling
execution time estimation
task graphs
workflow PDF (in Russian) (659KB) PDF. zip (in Russian) (557KB)

Abstract

The solution of complex engineering and scientific problems using distributed computing and supercomputer systems can often be efficiently implemented by organizing workflows that integrate the individual program components (grid generators, solvers, visualizers, multi-criteria optimization systems, etc.) to solve the end problem. In order to optimize the load ratio of such platforms, one can use pattern recognition methods to detect such workflows and profiles evaluation methods to estimate their performance and execution time on the provided computing resources. A review of existing methods for the intellectual profiling and workflow execution time estimation is presented. A new mathematical model of representation of a computing job as a marked-up weighted directed acyclic graph is proposed. The problem of task graph clustering and its mapping onto the computing environment is considered. The work was supported by the Russian Ministry of Education (government contract N 14.514.11.4106) under the Federal Program «Research and development on priority directions of scientific-technological complex of Russia for 2007-2013».

New computational technologies

Downloads

Published

2013-11-03

Issue

Vol. 14 (2013): Issue 4.

Section

Section 2. Programming

Author Biographies

G.I. Radchenko

South Ural State University,
School of Electronic Engineering and Computer Science
• Associate Professor

L.B. Sokolinsky

South Ural State University,
School of Electronic Engineering and Computer Science
• Professor

A.V. Shamakina

South Ural State University,
School of Electronic Engineering and Computer Science
• Lecturer

References

  1. Кнут Д.Э. Искусство программирования. 1. Основные алгоритмы. М.: Издательский дом «Вильямс», 2000.
  2. Blythe J. et al. The Role of Planning in Grid Computing // Proc. 13th International Conference on Automated Planning &; Scheduling. Menlo Park: AAAI Press, 2003. 154-163.
  3. Chtepen M. et al. Online execution time prediction for computationally intensive applications with periodic progress updates // J. of Supercomputing. 2012. 62, N 2. 768-786.
  4. Devarakonda M.V., Iyer R.K. Predictability of process resource usage: a measurement-based study of UNIX // IEEE Trans. on Software Engineering. 1989. 15. 1579-1586.
  5. Foster I. et al. Chimera: a virtual data system for representing, querying, and automating data derivation // Proc. 14th International Conference on Scientific and Statistical Database Management. New York: IEEE Press, 2002. 37-46.
  6. Gerasoulis A., Yang T. A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors // J. of Parallel and Distributed Computing. 1992. 16, N 4. 276-291.
  7. Hey T., Papay J. Performance engineering, PSEs and the GRID // Scientific Programming. 2002. 10, N 1. 3-17.
  8. Ilghami O., Nau D.S. A general approach to synthesize problem-specific planners. Technical Report CS-TR-4597. College Park: Univ. of Maryland, 2004.
  9. Iverson M.A., Ozguner F., Potter L.C. Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment // Proc. Eighth Heterogeneous Computing Workshop (HCW’99). New York: IEEE Press, 1999. 99-111.
  10. Kerbyson D.J., Wasserman H.J., Hoisie A. Exploring advanced architectures using performance prediction // International Workshop on Innovative Architecture for Future Generation High Performance Processors and Systems. New York: IEEE Press, 2002. 27-37.
  11. Litke A. et al. Computational workload prediction for grid oriented industrial applications: the case of 3D-image rendering // CCGrid 2005. IEEE International Symposium on Cluster Computing and the Grid. New York: IEEE Press, 2005. 962-969.
  12. Mandal A. et al. Scheduling strategies for mapping application workflows onto the grid // HPDC-14. Proc. 14th IEEE International Symposium on High Performance Distributed Computing. New York: IEEE Press, 2005. 125-134.
  13. Nadeem F., Fahringer T. Using templates to predict execution time of scientific workflow applications in the grid // Proc 9th IEEE/ACM International Symposium on Cluster Computing and the Grid. New York: IEEE Press, 2009. 316-323.
  14. Rodriguez-Moreno M.D. et al. Integrating planning and scheduling in workflow domains // Expert Systems with Applications. 2007. 33, N 2. 389-406.
  15. Rodriguez-Moreno M.D. et al. IPSS: a hybrid approach to planning and scheduling integration // IEEE Trans. on Knowledge and Data Engineering. 2006. 18, N 12. 1681-1695.
  16. Topcuoglu H., Hariri S., Society I.C. Performance-effective and low-complexity // IEEE Trans. on Parallel and Distributed Systems. 2002. 13, N 3. 260-274.
  17. Vraalsen F. et al. Performance contracts: predicting and monitoring grid application behavior // Lecture Notes in Computer Science. Vol. 2242. Berlin: Springer, 2001. 154-165.
  18. Wu Q., Datla V.V. On performance modeling and prediction in support of scientific workflow optimization // Proc. IEEE World Congress on Services. New York: IEEE Press, 2011. 161-168.
  19. Zhang J. et al. Task mapper and application-aware virtual machine scheduler oriented for parallel computing // J. of Zhejiang University SCIENCE C. 2012. 13, N 3. 155-177.