CFP last date
22 July 2024
Reseach Article

Anatomy Study of Execution Time Predictions in Heterogeneous Systems

by J. Shanthini, K. R. Shankarkumar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 45 - Number 7
Year of Publication: 2012
Authors: J. Shanthini, K. R. Shankarkumar

J. Shanthini, K. R. Shankarkumar . Anatomy Study of Execution Time Predictions in Heterogeneous Systems. International Journal of Computer Applications. 45, 7 ( May 2012), 39-43. DOI=10.5120/6795-9123

@article{ 10.5120/6795-9123,
author = { J. Shanthini, K. R. Shankarkumar },
title = { Anatomy Study of Execution Time Predictions in Heterogeneous Systems },
journal = { International Journal of Computer Applications },
issue_date = { May 2012 },
volume = { 45 },
number = { 7 },
month = { May },
year = { 2012 },
issn = { 0975-8887 },
pages = { 39-43 },
numpages = {9},
url = { },
doi = { 10.5120/6795-9123 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2024-02-06T20:37:00.578881+05:30
%A J. Shanthini
%A K. R. Shankarkumar
%T Anatomy Study of Execution Time Predictions in Heterogeneous Systems
%J International Journal of Computer Applications
%@ 0975-8887
%V 45
%N 7
%P 39-43
%D 2012
%I Foundation of Computer Science (FCS), NY, USA

To make effective job placement policies for a volatile large scale heterogeneous system or in grid systems, scheduler must consider the job execution time. In most grid schedulers, execution time of job is to be known in the prior. The execution time given by user may not be more precise, execution time predictors are used in order to facilitate the dynamic scheduling. The prediction algorithms use analytical bench marking/ code profiling, historical data, and code analysis. The prediction algorithm should be nonclairvoyant in nature. This study reviews execution time prediction algorithms in a different perspective. This algorithm considers memory accessing, network performance, and fluctuation of competing CPU load and so on, as interference factors for prediction. Based on the understanding comprehensive analysis is made among them

  1. A. A. Khokhar, V. K. Prasanna, M. E. Shaaban, and C. -L. Wang. Heterogeneous computing: Challenges and opportunities. IEEE Computer, 26(6):18–27, June 1993
  2. A. Khokhar, V. Prasanna, M. Shaaban, and C. -L. Wang. Hetro- geneous supercomputing: Problems and issues. In Proc. of the 1992 Workshop on Heterogeneous Processing, pages 3–12 . IEEE Computer Society Press, Mar. 1992
  3. D. Pease, A. Ghafoor, I. Ahmad, D. L. Andrews,K. Foudil-Bey, T. E. Karpinski, M. A. Mikki, and M. Zerrouki. PAWS: A performance evaluation tool for parallel computing systems. IEEE Computer, 24(1):18– 29, Jan. 1991
  4. J. Yang, I. Ahmad, and A. Ghafoor. Estimation of Execution times on heterogeneous supercomputer architectures. In the 1993 Inter. Conf. on Parallel Processing,volume 1, pages 219–226. CRC Press, Aug. 1993.
  5. R. Freund. Optimal selection theory for superconcurrency. In Proceedings of the 1989 Supercomputing Conference,pages 13–17. IEEE Computer Society Press,1989.
  6. J. Yang, I. Ahmad, and A. Ghafoor. Estimation of execution times on heterogeneous supercomputer architectures. In the 1993 Inter. Conf. on Parallel Processing, volume 1, pages 219–226. CRC Press, Aug. 1993.
  7. C. Levit, "Grid Communication on the Connection Machine: Analysis, Performance and Improvements", Tech. Report 88. 19, Research Inst. for Advanced Computer Science, NASA Ames Research Center,1988
  8. Michael A. Iverson, FuEsun OE zguEner and LeePotter,Statistical Prediction of Task Execution Timesthrough Analytic Benchmarking for Scheduling in Heterogeneous Environment, IEEE Transactions On Computers, VOL. 48, NO. 12, DECEMBER 1999.
  9. M. V. Devarakonda and R. K. Iyer. Predictabilityof process resource usage: A measurement-based study on UNIX. IEEE Trans. Software Engineering, 15(12):1579–1586, Dec. 1989
  10. WarrenSmith, ValeirTaylor, and IanFoster, Using Run-Time predictions to estimate queue wait times and improve scheduler performance, Lecture Notes in Computer Science (LNCS), 1659, Springer-Verlag,pp. 202-229.
  11. Warren Smith, Ian Foster, and Valerie Taylor, Predicting application run times using historical information, J. parallel and Dist. computing. 64(2004)1007-1016
  12. Maciej Drozdowski, Estimating execution time of distributed applications,PRAM 2001,LNCS 2328,pp 137-144,2002
  13. Christian Glasner, Jens Volkert, An Architecture for an Adaptive Run-time Prediction System. 2008 International Symposium on Parallel and Distributed Computing.
  14. Xilong Che, Liang Hu, Dong Guo, Kuo Tang and Debin Hu, Information Service Prototype System for Run-time Predictionof Grid Applications, 2nd International conference on Pervasive Computing and Applications, ICPCA 2007.
  15. www. globus. org
  16. Hui Li, Performance Evaluation of grid computing a model and prediction perspective, Seventh IEEE International Symposium on Cluster Computing and the Grid(CCGrid'07)
  17. Shonali Krishnaswamy, Arkady Zaslavsky and Seng Wai Loke,Predicting runtime of application using rough sets. IEEE distributed systems online,April 2004. Vol. 5.
  18. Tran Ngoc Minh, Lex Wolters, Using Historical Data to Predict Application Runtimes on Backfilling Parallel Systems, 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing
  19. D. Tsafrir, Y. Etsion, D. G. Feitelson, "Backfilling Using System Generated Predictions Rather than User Runtime Estimates", IEEE Transactions on Parallel and Distributed Systems, Volume 18, Pages 789-803, 2007
  20. H. Li, D. Groep, L. Wolters, "Mining Performance Data for Metascheduling Decision Support in the Grid", Future Generation Computer Systems 23, Pages 92-99, Elsevier, 2007.
  21. Maleeha Kiran , Aisha-Hassan A. Hashim1, Lim Mei Kuan, Yap Yee Jiun, Execution Time Prediction of Imperative Paradigm Tasks for Grid Scheduling Optimization, IJCSNS International Journal of Computer Science and Network Security, VOL. 9 No. 2,February 2009
  22. Emmanuel Jeannot, Keith Seymour, Jack J. Dongarra, and Asym Yarkhan, Improved runtime and transfer time prediction mechanisms in a network enabled servers middleware, Parallel Processing Letters, World Scientific Publishing Company, January 2006
  23. Marco A. S. Netto , Christian Vecchiola , Michael Kirley , Carlos A. Varelab, Rajkumar Buyya, Use of run time predictions for automatic co-allocation of multi-clusterresources for iterative parallel applications, J. Parallel Distrib. Comput. 71 (2011) 1388–1399
  24. Juaan manuel ramirez, Alcaraz ,Andrei Tchernykh,raminyahyapour,Uwe Schwiegelshohn , Ariel Quezada Pina,Jose Luis Gonzalez,garacia,Adan Hiralgies ,Carbajal, Job Allocation Strategies with with User run time Estimation for online scheduling for hierarchical grids, Journal of Grid Computing, Volume 9 Issue 1, March 2011 9:95–116
  25. Dan Tsafrir, Yoav Etsion, and Dror G. Feitelson, Backfilling Using System-Generated Predictions Rather than User Runtime Estimates, IEEE Trans. on Parallel And Distributed Systems, Vol. 18, No. 6, June 2007
  26. David Talby Dan Tsafrir Zviki Goldberg Dror G. Feitelson, Session-Based, Estimation-less, and Information-less Runtime Prediction Algorithms for Parallel and Grid Job Scheduling, Technical Report, school of computer science and Engineering, Hebrew University of Jerusalem 2006
Index Terms

Computer Science
Information Sciences


Task Scheduling Historical Data Code Analysis Profiling Benchmarking.