CFP last date
20 June 2024
Reseach Article

Minimizing the Makespan and Economic Cost of Schedule for the Grid Applications

Published on August 2013 by Avdhesh Gupta, Pankaj Agarwal, Shalini Gupta
National Conference on Recent Trends in Engineering and Management
Foundation of Computer Science USA
NCRTEM - Number 1
August 2013
Authors: Avdhesh Gupta, Pankaj Agarwal, Shalini Gupta
297caaec-b68a-498e-8b47-1b75260efce8

Avdhesh Gupta, Pankaj Agarwal, Shalini Gupta . Minimizing the Makespan and Economic Cost of Schedule for the Grid Applications. National Conference on Recent Trends in Engineering and Management. NCRTEM, 1 (August 2013), 28-33.

@article{
author = { Avdhesh Gupta, Pankaj Agarwal, Shalini Gupta },
title = { Minimizing the Makespan and Economic Cost of Schedule for the Grid Applications },
journal = { National Conference on Recent Trends in Engineering and Management },
issue_date = { August 2013 },
volume = { NCRTEM },
number = { 1 },
month = { August },
year = { 2013 },
issn = 0975-8887,
pages = { 28-33 },
numpages = 6,
url = { /proceedings/ncrtem/number1/13071-1307/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 National Conference on Recent Trends in Engineering and Management
%A Avdhesh Gupta
%A Pankaj Agarwal
%A Shalini Gupta
%T Minimizing the Makespan and Economic Cost of Schedule for the Grid Applications
%J National Conference on Recent Trends in Engineering and Management
%@ 0975-8887
%V NCRTEM
%N 1
%P 28-33
%D 2013
%I International Journal of Computer Applications
Abstract

Grid computing is a distributed computing taken to next evolutionary level. In this work, a static methodology has been adopted for defining the weights of the computational tasks and communicating edges. Also, we defined the execution time (makespan) as the total time between the finish time of exit task and start time of the entry task in the given Directed Acyclic Graph (DAG). The algorithm has been implemented for evaluation of time and cost of different random task graph or DAG of different graph size. Also, the algorithm has been executed in a grid of heterogeneous cluster of different sizes with four resources in each cluster. The primary work is to find the primary scheduling i. e. , total execution time and total cost with little or no changes in primary scheduling. We have proposed an efficient scheduling algorithm, which optimize the makespan and economic cost of the schedule and minimize the requirements of processors. The algorithm has been implemented to schedule different random DAGs onto different grids of heterogeneous clusters of various sizes.

References
  1. Fost, Ian, Carl Kesselman, Steve Tuecke, The Aanatomy of the Grid: Enabling Scalble Virtual Organization, International Journal of Supercomputer Application, 2001.
  2. Klaus Krauter, Rajkumar Buyya, and Muthucumaru Maheswaran. ?A Taxonomy and Survey of Grid Resource Management System for Distributed Computing?, Software: Practice and Experience (SPE) journal, Wiley Press, USA, 2001.
  3. H. Topcuoglu, S. Hariri, and M. Wu, ?Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing?, IEEE Transactions on Parallel and Distributed Systems, 13(3), pp. 260-274, 2002.
  4. R. Sakellariou and H. Zhao, ?A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems?, in Proceedings of the 13th Heterogeneous Computing Workshop (HCW'04), Santa Fe, New Mexico, USA, pp. 26 - 30, 2004.
  5. [M. Maheswaran and H. J. Siegel, ? A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems?, in Proceedings of the Seventh Heterogeneous Computing Workshop, 1998.
  6. Abramson D, Giddy J, Kotler L. ? High performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid?? Proceedings International Parallel and Distributed Processing Symposium (IPDPS 2000), Cancun, Mexico, 1–5May 2000. IEEE Computer Society Press: Los Alamitos, CA, 2000.
  7. Buyya R, Abramson D, Giddy J. ? A Case for Economy Grid Architecture for Service-Oriented Grid Computing?. Proceedings of the International Parallel and Distributed Processing Symposium: 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), 23 April 2001, San Francisco, CA. IEEE Computer Society Press: Los Alamitos, CA, 2001.
  8. Sullivan III WT, Werthimer D, Bowyer S, Cobb J, Gedye D, Anderson D. ? A New Major SETIPproject Based on Project Serendip Data and 100,000 Personal Computers?. Proceedings of the 5th International Conference astronomy 1997 http://setiathome. ssl. berkeley. edu/woody paper. html.
  9. Buyya R, Abramson D, Giddy J. Nimrod/G: Architecture for a Resource Management and Scheduling System in a Global Computational Grid?. Proceedings 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region (HPC ASIA 2000), Beijing, China, 14–17 May 2000. IEEE Computer Society Press: Los Alamitos, CA, 2000.
  10. Rajkumar Buyya, David Abramson, and Srikumar Venugopal, "The Grid Economy, Special Issue on Grid Computing", Proceedings of the IEEE, Manish Parashar and Craig Lee, IEEE Press, New York, USA, ISSN 0018-9219, Vol. 93, Issue 3, pp. 698 - 714, March 2005.
  11. R. Garg and A. K. Singh ?Reference Point Based Evolutionary Approach for Workflow Grid Scheduling?. Proceedings of International Journal of Information and Electronics Engineering, Vol. 2, No. 4, July 2012
  12. Buyya R, Giddy J, Abramson D. ? An Evaluation of Economy-Based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications?. Proceedings of the 2nd International Workshop on Active Middleware Services AMS 2000), Pittsburgh, PA, 1 August 2000. Kluwer Academic Press, 2000.
  13. Chapin S, Karpovich J, Grimshaw A, ?The Legion Resource Management System?. Proceedings of the 5th Workshop on Job Scheduling Strategies for Parallel Processing , San Juan, Puerto Rico, 16 April 1999. Springer: Berlin, 1999.
  14. Litzkow M, Livny M, Mutka M. Condor—a Hunter of Idle Workstations. Proceedings 8th International Conference of Distributed Computing Systems (ICDCS 1988), San Jose, CA, January 1988. IEEE Computer Society Press: Los Alamitos, CA, 1988.
  15. Berman F, Wolski R. The AppLeS Project: A status report. Proceedings of the 8th NEC Research Symposium, Berlin, Germany, May 1997.
  16. Casanova H, Dongarra J. NetSolve: ?A Network Server for Solving Computational Science Problems?. International Journal of Supercomputing Applications and High Performance Computing 1997; 11(3):212–223.
  17. Kapadia N, Fortes J. PUNCH: ?Architecture for Web-Enabled Wide-Area Network-Computing?. Cluster Computing: The Journal of Networks, Software Tools and Applications 1999; 2(2):153–164.
  18. P. A. Dinda, ?Design, Implementation, and Performance of an Extensible Toolkit for Resource Prediction in Distributed Systems?, IEEE Trans. Parallel Distrib. Syst. , 2006, 17(2), pp. 160-173.
  19. P. A. Dinda, and D. R. O'Hallaron, ?Host Load Prediction Using Linear Models?, Cluster Computing, 2000, 3(4), pp. 265-280.
  20. D. M. Swany, and R. Wolski, ?Multivariate Resource Performance Forecasting in the Network Weather Service?, In Proceedings of the 2002 ACM/IEEE conference on Supercomputing Baltimore, Maryland, November 2002, pp. 1-10.
  21. R. Wolski, L. Miller, G. Obertelli, and M. Swany, ?Performance Information Services for Computational Grids?, In: Resource Management for Grid Computing, J. Nabrzyski, J. Schopf, and J. Weglarz, editors, Kluwer Publishers, Fall, 2003.
  22. E. Caron, A. Chis, F. Desprez, and A. Su, ?Design of Plug-In Schedulers for a GRIDRPC Environment?, Future Generation Computer Systems, 2008, 24(1), pp. 46-57.
  23. E. Caron, and F. Desprez, ?DIET: A Scalable Toolbox to Build Network Enabled Servers on the Grid?, International Journal of High Performance Computing Applications, 2006, 20(3), pp. 335-352.
  24. A. K. Talukder, M. Kirley, and R. Buyya, ?Multi-Objective Differential Evolution for Scheduling Workflow Applications on Global Grids,? John Wiley and Sons, Ltd. , DOI: 10. 1002/cpe. 1417,
  25. 2009. L. -T. Lee, D. -F. Tao, and C. Tsao, ?An Adaptive Scheme for Predicting the Usage of Grid Resources?, Comput. Electr. Eng. Pergamon Press, Inc. , Tarrytown, NY, USA, 2007, 33(1), pp. 1-11.
  26. Q. Huang, N. Xiao, and B. Liu, ?Grid Load Forecasting Based on Least Squares Support Vector Machine?, Computer Technology and development, 2007, 17(6), pp. 32-35.
  27. B. Vandy, and G. Bruno, ?Brokering Strategies in Computational Grids using Stochastic Prediction Models?, Parallel Computing, May 2007, 33(4-5), pp. 238-249.
  28. Chee Shin Yeo and Rajkumar Buyya, "Service Level Agreement based Allocation of Cluster Resources: Handling Penalty to Enhance Utility", Proceedings of the 7th IEEE International Conference on Cluster Computing, Cluster 2005, IEEE CS Press, Los Alamitos, CA, USA, Boston, Massachusetts, USA, September 27-30, 2005.
  29. Cost Marcos Dias de Assuncao and Rajkumar Buyya, A Cost-Aware Resource Exchange Mechanism for Load Management across Grids, Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS 2008, IEEE CS Press, Los Alamitos, CA, USA), Dec. 8-10, 2008, Melbourne, Australia.
  30. Srikumar Venugopal and Rajkumar Buyya, Cost-based Scheduling for Data-Intensive Applications on Global Grids, Proceedings of the 14th IEEE International Symposium on High Performance Distributed Computing (HPDC-14, 2-pages Poster Paper, IEEE CS Press, Los Alamitos, CA, USA), July 24-27, 2005, Research Triangle Park, North Corolina, USA.
  31. Jia Yu, Rajkumar Buyya, and Chen Khong Tham, Cost-based Scheduling of Workflow Applications on Utility Grids, Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing (e-Science 2005, IEEE CS Press, Los Alamitos, CA, USA), Dec. 5 -8, 2005, Melbourne, Australia.
  32. Weina Lu, Shoubao Yang, Leitao Guo, Rui Zhang, ?Reputation-aware Transaction Mechanisms in Grid Resource Market?, Sixth Intl: conf: on Grid and Cooperative computing(GCC'07), 16-18 Aug, 2007
  33. Chunlin, L. and L. Layuan, "A Pricing Approach For Grid Resource Scheduling With QoS Guarantees " Fundam. Inf. 76 (1-2): 59-73, 2007.
  34. A. Eswaradass, X. -H. Sun, and M. Wu, ?A Neural Network Based Predictive Mechanism for Available Bandwidth?, In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (
Index Terms

Computer Science
Information Sciences

Keywords

Dag Grid Makespan Workflow