×

Performance modeling of parallel applications for grid scheduling. (English) Zbl 1243.68124

Summary: Grids consist of both dedicated and non-dedicated clusters. For effective mapping of parallel applications on grid resources, a grid metascheduler has to evaluate different sets of resources in terms of predicted execution times for the applications when executed on the sets of resources. In this work, we have developed a comprehensive set of performance modeling strategies for predicting execution times of parallel applications on both dedicated and non-dedicated environments. Our strategies adapt to changing network and CPU loads on the grid resources. We have evaluated our strategies on 8, 16, 24 and 32-node clusters with random loads and load traces from a grid system. Our strategies give less than 30% average percentage prediction errors in all cases, which, to our knowledge, is the best reported for non-dedicated environments. We also found that grid scheduling using predictions of execution times from our performance modeling techniques will lead to perfect mapping of applications to resources in many cases.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adve, V.; Vernon, M.: Parallel program performance prediction using deterministic task graph analysis, ACM transactions on computer systems 22, No. 1, 94-136 (2004)
[2] Alkindi, A. M.; Kerbyson, D. J.; Nudd, G. R.: Dynamic instrumentation and performance prediction of application execution, In high performance computing and networking (HPCN2001) 2110, 313-323 (2001) · Zbl 0997.68694
[3] G. Allen, T. Dramlitsch, I. Foster, N. Karonis, M. Ripeanu, E. Seidel, B. Toonen, Supporting efficient execution in heterogeneous distributed computing environments with cactus and globus, in: Supercomputing ’01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), 2001
[4] C. Anglano, Predicting parallel applications performance on non-dedicated cluster platforms, in: ICS ’98: Proceedings of the 12th international conference on Supercomputing, 1998
[5] ApGrid - Asia Pacific Grid, http://apgrid.org
[6] R. Badia, J. Labarta, J. Gimenez, F. Escale, DIMEMAS: Predicting MPI applications behavior in grid enviornaments., in: In Workshop on Grid Applications and Programming Tools (GGF8), Seattle York, U.S.A, 2003
[7] O. Beaumont, L. Carter, J. Ferrante, A. Legrand, L. Marchal, Y. Robert, Centralized versus distributed schedulers for multiple bag-of-task applications, in: 20th International Parallel and Distributed Processing Symposium, 2006
[8] F. Berman, R. Wolski, The AppLeS Project: A Status Report, in: Proceedings of the 8th NEC Research Symposium
[9] L.S. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, R.C. Whaley, ScaLAPACK Users’ Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
[10] R. Block, S. Sarukkai, P. Mehra, Automated performance prediction of message-passing parallel programs, in: Supercomputing ’95: Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), 1995
[11] Carrington, L.; Snavely, A.; Wolter, N.: A performance prediction framework for scientific applications, Future generation computer systems 22, No. 3, 336-346 (2006)
[12] CurveExpert, http://curveexpert.webhop.biz
[13] DataFit, http://www.curvefitting.com
[14] A. Dhodapkar, J. Smith, Comparing program phase detection techniques, in: Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003
[15] W. Dick, M. Heath, Whole system simulation of solid propellant rockets, in: Proceedings of the 38th Joint Propulsion Conference and Exhibit, Indianapolis, IN, USA, 2002
[16] C. Ding, S. Dwarkadas, M. Huang, K. Shen, J. Carter, Program Phase Detection and Exploitation, in: 20th International Parallel and Distributed Processing Symposium, 2006
[17] M. Frigo, S. Johnson, The design and implementation of FFTW3, Proceedings of the IEEE 93 (2) (2005) 216–231, special issue on Program Generation, Optimization, and Platform Adaptation
[18] The GrADS Project, http://www.hipersoft.rice.edu/grads
[19] GrADS Traces, http://pompone.cs.ucsb.edu/rich/data
[20] Grove, D. A.; Coddington, P. D.: Modeling message-passing programs with a performance evaluating virtual parallel machine, Performance evaluation 60, No. 1-4, 165-187 (2005)
[21] Ipek, E.; De Supinski, B.; Schulz, M.; Mckee, S.: An approach to performance prediction for parallel applications, Euro-par 3648 (2005)
[22] D. Kerbyson, H. Alme, A. Hoisie, F. Petrini, H. Wasserman, M. Gittings, Predictive performance and scalability modeling of a large-scale application, in: Supercomputing ’01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), Denver, Colorado, USA, 2001
[23] LabFit, http://www.angelfire.com/rnb/labfit
[24] Lee, B.; Brooks, D.; De Supinski, B.; Schulz, M.; Singh, K.; Mckee, S.: Methods of inference and learning for performance modeling of parallel applications, (2007)
[25] Nudd, G.; Kerbysin, D.; Papaefstathiou, E.; Perry, S.; Harper, J.; Wilcox, D.: PACE - a toolset for the performance prediction of parallel and distributed systems, The international journal of high performance computing applications 14, No. 3, 228-251 (2000)
[26] L. Oliker, R. Biswas, H. Shan, J. Singh, Design strategies for irregularly adapting parallel applications, in: Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, 2001
[27] E. Perelman, M. Polito, J.-Y. Bouguet, J. Sampson, B. Calder, C. Dulong, Detecting phases in parallel applications on shared memory architectures, in: 20th International Parallel and Distributed Processing Symposium, 2006
[28] Petitet, A.; Blackford, S.; Dongarra, J.; Ellis, B.; Fagg, G.; Roche, K.; Vadhiyar, S.: Numerical libraries and the grid: the grads experiments with scalapack, Journal of high performance applications and supercomputing 15, No. 4, 359-374 (2001)
[29] J. Schopf, Structural prediction models for high performance distriuted applications, in: Proceedings of Cluster Computing Conference (CCC’97), Atlanta, USA, 1997
[30] J. Schopf, F. Berman, Performance prediction in production environments, in: Proceedings of 12th International Parallel Processing Symposium, Orlando, USA, 1998
[31] Schopf, J.; Berman, F.: Using stochastic information to predict application behavior on contended resources, International journal on foundation in computer science 12, No. 3, 341-364 (2001) · Zbl 1319.68046
[32] T. Sherwood, S. Sair, B. Calder, Phase tracking and prediction, in: ISCA ’03: Proceedings of the 30th Annual International Symposium on Computer architecture, 2003
[33] V. Taylor, X. Wu, J. Geisler, X. Li, Z. Lan, M. Hereld, I. Judson, R. Stevens, Prophesy: Automating the modeling process, in: Proceedings of the Third Annual International Workshop on Active Middleware Services, Tokyo, Japan, 2001
[34] Taylor, V.; Wu, X.; Stevens, R.: Prophesy: an infrastructure for performance analysis and modeling of parallel and grid applications, ACM SIGMETRICS performance evaluation review 30, No. 4, 13-18 (2003)
[35] TeraGrid, http://www.teragrid.org
[36] UK e-Science, http://www.rcuk.ac.uk/escience/default.htm
[37] Wolski, R.: Dynamically forecasting network performance using the network weather service, Journal of cluster computing 1, No. 1, 119-132 (1998)
[38] Wolski, R.; Spring, N.; Hayes, J.: The network weather service: A distributed resource performance forecasting service for metacomputing, Journal of future generation computing systems 15, No. 5-6, 757-768 (1999)
[39] Xu, Z.; Zhang, X.; Sun, L.: Semi-empirical multiprocessor performance predictions, Journal of parallel and distributed computing 39, No. 1, 14-28 (1996) · Zbl 1114.68339 · doi:10.1006/jpdc.1996.0151
[40] J. Yagnik, H.A. Sanjay, S. Vadhiyar, Performance modeling based on multidimensional surface learning for performance predictions of parallel applications in non-dedicated environments, in: ICPP ’06: Proceedings of the 2006 International Conference on Parallel Processing, 2006
[41] Yan, Y.; Zhang, X.; Song, Y.: An effective and practical performance prediction model for parallel computing on nondedicated heterogeneous NOW, Journal of parallel and distributed computing 38, No. 1, 63-80 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.