nach oben

International Journal of Parallel Programming

Erschienen in:

01.06.2015

A Parallel Job Execution Time Estimation Approach Based on User Submission Patterns within Computational Grids

verfasst von: Feng Liang, Yunzhen Liu, Hai Liu, Shilong Ma, Bettina Schnor

Erschienen in: International Journal of Parallel Programming | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Scheduling performance in computational grid can potentially benefit a lot from accurate execution time estimation for parallel jobs. Most existing approaches for the parallel job execution time estimation, however, require ample past job traces and the explicit correlations between the job execution time and the outer layout parameters such as the consumed processor numbers, the user-estimated execution time and the job ID, which are hard to obtain or reveal. This paper presents and evaluates a novel execution time estimation approach for parallel jobs, the user-behavior clustering for execution time estimation, which can give more accurate execution time estimation for parallel jobs through exploring the job similarity and revealing the user submission patterns. Experiment results show that compared to the state-of-art algorithms, our approach can improve the accuracy of the job execution time estimation up to 5.6 %, meanwhile the time that our approach spends on calculation can be reduced up to 3.8 %.

Vorheriger Artikel Efficiently Restoring Virtual Machines

Nächster Artikel A Virtualization Based Monitoring System for Mini-intrusive Live Forensics

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Carvalho, M., Brasileiro, F.: A user-based model of grid computing workloads. In: Proceedings of the 2012 ACM/IEEE 13th International Conference on Grid Computing, GRID ’12, pp. 40–48. IEEE Computer Society, Washington, DC, USA (2012). doi:10.1109/Grid.2012.13

Castillo, C., Rouskas, G.N., Harfoush, K.: Efficient resource management using advance reservations for heterogeneous grids. In: Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium, pp. 1–12 (2008)

Dan, T., Dan, T.: Using inaccurate estimates accurately. In: Frachtenberg, E., Schwiegelshohn, U. (eds.) Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 6253, pp. 208–221. Springer, Berlin Heidelberg, Los Alamitos, CA, USA (2010)

den Bossche, R.V., Vanmechelen, K., Broeckhove, J.: An evaluation of the benefits of fine-grained value-based scheduling on general purpose clusters. Future Gener. Comput. Syst. 27(1), 1–9 (2011). doi:10.1016/j.future.2010.06.009. http://www.sciencedirect.com/science/article/pii/S0167739X10001226

Dimitriadou, S., Karatza, H.: Job scheduling in a distributed system using backfilling with inaccurate runtime computations. In: International Conference on Complex, Intelligent and Software Intensive Systems (CISIS), 2010, pp. 329–336 (2010). doi:10.1109/CISIS.2010.65

Downey, A.: Predicting queue times on space-sharing parallel computers. In: Proceedings of 11th International Parallel Processing Symposium, 1997, pp. 209–218 (1997). doi:10.1109/IPPS.1997.580894

Elmroth, E., Tordsson, J.: Grid resource brokering algorithms enabling advance reservations and resource selection based on performance predictions. Future Gener. Comput. Syst. 24, 585–593 (2008)CrossRef

Elmroth, E., Tordsson, J.: A standards-based grid resource brokering service supporting advance reservations, coallocation, and cross-grid interoperability. Concurr. Comput. Pract. Experience 21(18), 2298–2335 (2009). doi:10.1002/cpe.v21:18 CrossRef

Feitelson, D.: Experimental analysis of the root causes of performance evaluation results: a backfilling case study. IEEE Trans. Parallel Distrib. Systems 16(2), 175–182 (2005). doi:10.1109/TPDS.2005.18 CrossRef

10.

Feitelson, D.: The parallel workload archive (2010). http://www.cs.huji.ac.il/labs/parallel/workload/

11.

Feitelson, D.: Workload Modeling for Computer Systems Performance Evaluation, vol. 0.34. School of Computer Science and Engineering, The Hebrew University of Jerusalem 91904 Jerusalem, Israel (2012). [Online Book draft] www.cs.huji.ac.il/feit/wlmod/

12.

Iosup, A., Epema, D.H.J.: Grid computing workloads. IEEE Internet Comput. 15(2), 19–26 (2011)CrossRef

13.

Klusavek, D., Rudova, H.: The importance of complete data sets for job scheduling simulations. In: Proceedings of the 15th International Conference on Job Scheduling Strategies for Parallel Processing, JSSPP10, pp. 132–153. Springer, Berlin, Heidelberg (2010)

14.

Lee, C.B., Snavely, A., Lee, C.B., Snavely, A.: On the user-scheduler dialogue: studies of user-provided runtime estimates and utility functions. Int. J. High Perform. Comput. Appl. 20, 495–506 (2006)CrossRef

15.

Lee, C.B., Snavely, A.E.: Precise and realistic utility functions for user-centric performance analysis of schedulers. In: Proceedings of the 16th International Symposium on High Performance Distributed Computing, HPDC ’07, pp. 107–116. ACM, New York, NY, USA (2007). doi:10.1145/1272366.1272381

16.

Lee, S.B., Schwartzman, Y., Hardy, J., Snavely, A.: Are user runtime estimates inherently inaccurate? In: Feitelson, D., Rudolph, L., U. Schwiegelshohn (eds.) Job Scheduling Strategies for Parallel Processing: 10th International Workshop, JSSPP 2004, pp. 253–263. Springer (2005)

17.

Li, H.: Workload dynamics on clusters and grids. J. Supercomput. 47, 1–20 (2009). doi:10.1007/s11227-008-0189-x CrossRefMATH

18.

Liang, F., Ma, S., Luckow, A., Schnor, B.: Earliest start time estimation for advance reservation-based resource brokering within computational grids. In: International Symposium on Parallel and Distributed Processing with Applications (ISPA), 2010, pp. 8–15 (2010). doi:10.1109/ISPA.2010.30

19.

Liang, F., Ma, S., Luckow, A., Schnor, B.: Advance reservation-based computational resource brokering using earliest start time estimation. J. Comput. 7(6), 1329–1336 (2012)CrossRef

20.

Machine Learning Group, The University of Waikato: WEKA 3 webpage (2013). http://www.cs.waikato.ac.nz/ml/weka/

21.

Nadeem, F., Prodan, R., Fahringer, T.: Benchmarking grid applications for performance and scalability predictions. In: Li, K.C., Hsu, C.H., Yang, L.T., Dongarra, J., Zima H. (eds.) Handbook of Research on Scalable Computing Technologies. IGI Global, Hershey, PA (2010). doi:10.4018/978-1-60566-661-7.ch005, http://www.igi-global.com/bookstore/TitleDetails.aspx?TitleId=498

22.

Nadeem, F., Yousaf, M., Prodan, R., Fahringer, T.: Soft benchmarks-based application performance prediction using a minimum training set. In: Second IEEE International Conference on e-Science and Grid Computing, 2006. e-Science ’06, p. 71 (2006). doi:10.1109/E-SCIENCE.2006.261155

23.

Oikonomakos, M., Christodoulopoulos, K., Varvarigos, E.: Profiling computation jobs in grid systems. In: Seventh IEEE International Symposium on Cluster Computing and the Grid, 2007. CCGRID 2007, pp. 197–204 (2007). doi:10.1109/CCGRID.2007.87

24.

Parallel and Distributd System Group, Technische Universiteit Delft: The grid workloads archive webpage (2010). http://gwa.ewi.tudelft.nl/pmwiki/

25.

Qu, C.: A grid advance reservation framework for co-allocation and co-reservation across heterogeneous local resource management systems. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) 7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007, vol. 4967, pp. 770–779. Springer, Gdansk, Poland (2007)

26.

Ramírez-Alcaraz, J.M., Tchernykh, A., Yahyapour, R., Schwiegelshohn, U., Quezada-Pina, A., González-García, J.L., Hirales-Carbajal, A.: Job allocation strategies with user run time estimates for online scheduling in hierarchical grids. J. Grid Comput. 9(1), 95–116 (2011)CrossRef

27.

Röblitz, T., Rzadca, K.: On the placement of reservations into job schedules. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006 Proceedings, Lecture Notes in Computer Science, vol. 4128. Springer, pp. 198–210 (2006)

28.

Roy, S., Mukherjee, N.: Adaptive execution of jobs in computational grid environment. J. Comput. Sci. Technol. 24, 925–938 (2009)CrossRef

29.

Sarkar, M., Roy, S., Mukherjee, N.: Prediction of resource requirement using feedback on job execution performance. Procedia Comput. Sci. 3, 1271–1276 (2011)CrossRef

30.

Sipser, M.: Introduction to the Theory of Computation (Ise). Thomson Course Technology, Stamford, CT (2006). http://www.google.com.tw/books?id=VJ1mQgAACAAJ

31.

Smith, W.: Prediction services for distributed computing. In: International Parallel and Distributed Processing Symposium, pp. 1–10. IEEE Computer Society, Los Alamitos, CA, USA (2007). doi:10.1109/IPDPS.2007.370276

32.

Smith, W., Foster, I., Taylor, V.: Predicting application run times with historical information. J. Parallel Distrib. Comput. 64, 1007–1016 (2004). doi:10.1016/j.jpdc.2004.06.008 CrossRefMATH

33.

Takefusa, A., Nakada, H., Kudoh, T., Tanaka, Y., Sekiguchi, S.: GridARS: an advance reservation-based grid co-allocation framework for distributed computing and network resources. In: Frachtenberg, E., Schwiegelshohn, U. (eds.) 13th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2007, Lecture Notes in Computer Science, vol. 4942, pp. 152–168. Springer, Seattle, WA, USA (2007)

34.

Talby, D., Tsafrir, D., Goldberg, Z., Feitelson, D.G.: Session-based, estimation-less, and information-less runtime prediction algorithms for parallel and grid job scheduling. Technical report 2006-77, School of Computer Science and Engineering, the Hebrew University, Jerusalem, Israel (2006)

35.

Tang, W., Desai, N., Buettner, D., Lan, Z.: Analyzing and adjusting user runtime estimates to improve job scheduling on the blue gene p. In: International Parallel and Distributed Processing Symposium, pp. 1–11. IEEE Computer Society, Los Alamitos, CA, USA (2010)

36.

Tong, Y., Chen, L., Ding, B.: Discovering threshold-based frequent closed itemsets over probabilistic data. In: IEEE 28th International Conference on Data Engineering (ICDE), 2012, pp. 270–281 (2012). doi:10.1109/ICDE.2012.51

37.

Tong, Y., Chen, L., Yu, P.S.: Ufimt: an uncertain frequent itemset mining toolbox. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’12, pp. 1508–1511. ACM, New York, NY, USA (2012). doi:10.1145/2339530.2339767

38.

Tran, N.M., Wolters, L.: Towards a profound analysis of bags-of-tasks in parallel systems and their performance impact. In: Proceedings of the 20th International Symposium on High Performance Distributed Computing, HPDC’11, pp. 111–122. ACM, New York, NY, USA (2011) doi:10.1145/1996130.1996148

Titel: A Parallel Job Execution Time Estimation Approach Based on User Submission Patterns within Computational Grids
verfasst von: Feng Liang
Yunzhen Liu
Hai Liu
Shilong Ma
Bettina Schnor
Publikationsdatum: 01.06.2015
Verlag: Springer US
Erschienen in: International Journal of Parallel Programming / Ausgabe 3/2015
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-013-0294-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2015

Network and Parallel Computing

Accelerating Smith-Waterman Alignment of Species-Based Protein Sequences on GPU

A Virtualization Based Monitoring System for Mini-intrusive Live Forensics

Inaccuracy in Private BitTorrent Measurements

An Adaptive and Memory Efficient Sampling Mechanism for Partitioning in MapReduce

Automatic Composition of Heterogeneous Models Based on Semantic Web Services