Call for Paper - November 2023 Edition
IJCA solicits original research papers for the November 2023 Edition. Last date of manuscript submission is October 20, 2023. Read More

Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path

Print
PDF
 
Download Full Text
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 55 - Number 4
Year of Publication: 2012
Authors:
D. I. George Amalarethinam
P. Muthulakshmi
10.5120/8740-2612

George D I Amalarethinam and P Muthulakshmi. Article: Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path. International Journal of Computer Applications 55(4):1-7, October 2012. Full text available. BibTeX

@article{key:article,
	author = {D. I. George Amalarethinam and P. Muthulakshmi},
	title = {Article: Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {55},
	number = {4},
	pages = {1-7},
	month = {October},
	note = {Full text available}
}

Abstract

The need for scheduling algorithms arise from the requirement to perform multitasking, essentially for modern computing systems. Scheduling is the greatest cause that optimizes the objective function that involved with the selection of resources. In scheduling, every aspect of execution is based on decision(s). The general objective of scheduling algorithms is to effectively use the available processors to execute parallel programs, possibly in the least utilization of time. A group of interdependent jobs/tasks forms the workflow application. Scheduling is to map the jobs/tasks on to the collection of heterogeneous resources available in a massive geographic spread. Most complicated applications consist of interdependent jobs that coordinate to solve a problem. The completion of a particular job is the criterion function that has to be essentially met in order to start the execution of those jobs that depend upon it [1]. This kind of workflow application may be represented in the form of a Directed Acyclic Graph (DAG). Grid Workflow is such an application and is modeled by DAG. DAGitizer could generate DAG in a random fashion [2]. This paper proposes a tool (developed using Java) which is an enhanced form of DAGitizer that could find the least cost path between source and destination nodes.

References

  • Maria M. Lopez, Elisa Heymann, Miquel A. Senar,"Analysis of Dynamic Heuristics for Workflow Scheduling on Grid Systems", IEEE Proceedings of The Fifth International Symposium on Parallel and Distributed Computing,2006.
  • Dr. D. I. George Amalarethinam, P. Muthulakshmi, "DAGITIZER – A Tool to Generate Directed Acyclic Graph through Randomizer to Model Scheduling in Grid Computing", Proceedings f the second International Conference on Computer Science, Engineering and Applications, Vol. 2, Publisher: Springer-Verlag, pp. 969-978, 2012.
  • Christofides, Nicos , Graph theory: an algorithmic approach, Academic Press, pp. 170–174, 1975.
  • Thulasiraman, K. ; Swamy, M. N. S. , "Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, ISBN 9780471513568, 1992.
  • Bang-Jensen, Jørgen, "2. 1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed. ), Springer-Verlag, pp. 32–34, 2008.
  • E. Ilavarasan, P. Thambidurai, R. Mahilmannan, "Performance Effective Task Scheduling Algorithm For Heterogeneous Computing System", Proceedings of the Fourth International Symposium on Parallel and Distributed Computing, France, pp. 28–38, 2005.
  • G. C. Sih, E. A. Lee," A Compile-Time Scheduling Heuristic For Interconnection-Constrained Heterogeneous Processor Architectures," IEEE Trans. Parallel Distributed Systems, Vol. 4 (2), pp. 175–187, 1993.
  • J. Kim, J. Rho, J. -O. Lee, M. -C. Ko, CPOC: "Effective Static Task Scheduling For Grid Computing," Proceedings of the 2005 International Conference on High Performance Computing and Communications, Italy, pp. 477–486, 2005.
  • Yang, T and Gerasoulis, A, "PYROSS: Static Task Scheduling and Code Generation for Message Passing Multiprocessors", Proceedings of 1992 International Conference on Super Computing (ICS '92) Washington DC, July 19-23, K. Kennedy and C. D. Polychronopoulos Eds. ACM press, New York, pp. 428-437, 1992.
  • Shirazi, B, Kavi, K, Hurson, A. R and Biswas, P, "PARSA: A Parallel Program Scheduling and Assessment Environment", Proceedings of the International Conference on Parallel Processing, CRC Press Inc. , Boca Raton, FL, pp. 68-72, 1993.
  • Yu-Kwong Kwok, Ishfaq Ahmad, "Static Algorithms for Allocating Directed Task Graphs to Mutiporcessors," ACM Computing Surveys, Volume 31, No. , 4, December 1999.
  • Chu, W. W. , Lan, M. T. , and Hellerstein, J, "Estimation of Intermodule Communication (IMC) and its Applications in Distributed Processing Systems", IEEE Transactions and Computing C-33, pp. 691-699, 1984.
  • Hu, T. C. "Parallel Sequencing and Assembly Line Problems", Operational Research 19, pp 841-848, 1961.
  • Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, "Fundamentals of Computer Algorithms", Galgotia Publications Pvt. Ltd. , 2006.
  • Sipser, Michael. " Introduction to the Theory of Computation", Course Technology Inc. ISBN 0-619-21764-2, 2006.
  • Herbert Schildt, "The Complete Reference Java2", Fifth Edition, Tata McGraw Hill Publishing Company, 2002.