CFP last date
20 August 2024
Reseach Article

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

by D. I. George Amalarethinam, P. Muthulakshmi
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 55 - Number 4
Year of Publication: 2012
Authors: D. I. George Amalarethinam, P. Muthulakshmi
10.5120/8740-2612

D. I. George Amalarethinam, P. Muthulakshmi . Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path. International Journal of Computer Applications. 55, 4 ( October 2012), 1-7. DOI=10.5120/8740-2612

@article{ 10.5120/8740-2612,
author = { D. I. George Amalarethinam, P. Muthulakshmi },
title = { Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path },
journal = { International Journal of Computer Applications },
issue_date = { October 2012 },
volume = { 55 },
number = { 4 },
month = { October },
year = { 2012 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume55/number4/8740-2612/ },
doi = { 10.5120/8740-2612 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:56:22.163221+05:30
%A D. I. George Amalarethinam
%A P. Muthulakshmi
%T Enhanced DAGitizer for Grid Computing through the Discovery of Least Cost Path
%J International Journal of Computer Applications
%@ 0975-8887
%V 55
%N 4
%P 1-7
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. 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.
  3. Christofides, Nicos , Graph theory: an algorithmic approach, Academic Press, pp. 170–174, 1975.
  4. Thulasiraman, K. ; Swamy, M. N. S. , "Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, ISBN 9780471513568, 1992.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Yu-Kwong Kwok, Ishfaq Ahmad, "Static Algorithms for Allocating Directed Task Graphs to Mutiporcessors," ACM Computing Surveys, Volume 31, No. , 4, December 1999.
  12. 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.
  13. Hu, T. C. "Parallel Sequencing and Assembly Line Problems", Operational Research 19, pp 841-848, 1961.
  14. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, "Fundamentals of Computer Algorithms", Galgotia Publications Pvt. Ltd. , 2006.
  15. Sipser, Michael. " Introduction to the Theory of Computation", Course Technology Inc. ISBN 0-619-21764-2, 2006.
  16. Herbert Schildt, "The Complete Reference Java2", Fifth Edition, Tata McGraw Hill Publishing Company, 2002.
Index Terms

Computer Science
Information Sciences

Keywords

Grid Workflow Scheduling Directed Acyclic Graph Randomizer Communication Cost Computation Cost Cost Matrix Least Cost Path