Resource Management for Rapid Application Turnaround on Enterprise Desktop Grids

ABSTRACT

Desktop grids are popular platforms for high throughput applications, but due their inherent resource volatility it is difficult to exploit them for applications that require rapid turnaround. Efficient desktop grid execution of short-lived applications is an attractive proposition and we claim that it is achievable via intelligent resource selection. We propose three general techniques for resource selection: resource prioritization, resource exclusion, and task duplication. We use these techniques to instantiate several scheduling heuristics. We evaluate these heuristics through trace-driven simulations of four representative desktop grid configurations. We find that ranking desk-top resources according to their clock rates, without taking into account their availability history, is surprisingly effective in practice. Our main result is that a heuristic that uses the appropriate combination of resource prioritization, resource exclusion, and task replication achieves performance within a factor of 1.7 of optimal.

REFERENCES

• 1: Anurag Acharya , Guy Edjlali , Joel Saltz, The utility of exploiting idle workstations for parallel computation, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.225-234, June 15-18, 1997, Seattle, Washington, United States
• 2: Klaus E. Schauser , Chris J. Scheiman , Gyung-Leen Park , Behrooz Shirazi , Jeff Marquis, SuperWeb: Towards a Global Web-Based Parallel Computing Infrastructure, Proceedings of the 11th International Symposium on Parallel Processing, p.100-106, April 01-05, 1997
• 3: Remzi H. Arpaci , Andrea C. Dusseau , Amin M. Vahdat , Lok T. Liu , Thomas E. Anderson , David A. Patterson, The interaction of parallel and sequential workloads on a network of workstations, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.267-278, May 15-19, 1995, Ottawa, Ontario, Canada
• 4: Amnon Barak , Shai Guday , Richard G. Wheeler, The MOSIX Distributed Operating System: Load Balancing for UNIX, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 5: [5] A. Baratloo, M. Karaul, Z. Kedem, and P. Wyckoff. Charlotte: Metacomputing on the Web. In Proc. of the 9th International Conference on Parallel and Distributed Computing Systems (PDCS-96), 1996.
• 6: [6] A. Bestavros. Load Profiling In Distributed Real-Time Systems. In The 17th International Conference on Distributed Computer Systems, May 1997.
• 7: [7] R. Bhagwan, S. Savage, and G. Voelker. Understanding Availability. In Proceedings of IPTPS'03, 2003.
• 8: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 9: [9] N. Camiel, S. London, N. Nisan, and O. Regev. The PopCorn Project: Distributed Computation over the Internet in Java. In Proc. of the 6th International World Wide Web Conference, April 1997.
• 10: [10] The Compute Against Cancer project. http:// www.computeagainstcancer.org/.
• 11: [11] P. Cappello, B. Christiansen, M. Ionescu, M. Neary, K. Schauser, and D. Wu. Javelin: Internet-Based Parallel Computing Using Java. In Proceedings of the Sixth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1997.
• 12: Henri Casanova , Dmitrii Zagorodnov , Francine Berman , Arnaud Legrand, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proceedings of the 9th Heterogeneous Computing Workshop, p.349, May 01-01, 2000
• 13: Andrew Chien , Brad Calder , Stephen Elbert , Karan Bhatia, Entropia: architecture and performance of an enterprise desktop grid system, Journal of Parallel and Distributed Computing, v.63 n.5, p.597-610, May 2003 [doi>10.1016/S0743-7315(03)00006-6]
• 14: [14] J. Chu, K. Labonte, and B. Levine. Availability and locality measurements of peer-to-peer file systems. In Proceedings of ITCom: Scalability and Traffic Control in IP Networks, July 2003.
• 15: Peter A. Dinda, The statistical properties of host load, Scientific Programming, v.7 n.3-4, p.211-229, August 1999
• 16: Peter A. Dinda, A Prediction-Based Real-Time Scheduling Advisor, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.35, April 15-19, 2002
• 17: Peter A. Dinda, Online Prediction of the Running Time of Tasks, Cluster Computing, v.5 n.3, p.225-236, July 2002 [doi>10.1023/A:1015634802585]
• 18: [18] Entropia, Inc. http://www.entropia.com.
• 19: Gilles Fedak , Cecile Germain , Vincent Neri , Franck Cappello, XtremWeb: A Generic Global Computing System, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.582, May 15-18, 2001
• 20: [20] The Fight Aids At Home project. http://www. fightaidsathome.org/.
• 21: [21] The Berkeley Open Infrastructure for Network Computing. http://boinc.berkeley.edu/.
• 22: James Frey , Todd Tannenbaum , Miron Livny , Ian Foster , Steven Tuecke, Condor-G: A Computation Management Agent for Multi-Institutional Grids, Cluster Computing, v.5 n.3, p.237-246, July 2002 [doi>10.1023/A:1015617019423]
• 23: Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Amin M. Vahdat , Thomas E. Anderson, GLUnix: a global layer Unix for a network of workstations, Software—Practice & Experience, v.28 n.9, p.929-961, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<929::AID-SPE183>3.0.CO;2-C]
• 24: [24] The great internet mersene prime search (gimps). http://www.mersenne.org/.
• 25: John F. Shoch , Jon A. Hupp, The “worm” programs—early experience with a distributed computation, Communications of the ACM, v.25 n.3, p.172-180, March 1982 [doi>10.1145/358453.358455]
• 26: [26] D. Kondo and H. Casanova. Computing the Optimal Makespan for Jobs with Identical and Independent Tasks Scheduled on Volatile Hosts. Technical Report CS2004-0796, Dept. of Computer Science and Engineering, University of California at San Diego, July 2004.
• 27: [27] D. Kondo, M. Taufer, C. Brooks, H. Casanova, and A. Chien. Characterizing and Evaluating Desktop Grids: An Empirical Study. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'04), April 2004.
• 28: [28] M. Litzkow, M. Livny, and M. Mutka. Condor - A Hunter of Idle Workstations. In Proceedings of the 8th International Conference of Distributed Computing Systems (ICDCS), 1988.
• 29: O. Lodygensky , G. Fedak , F. Cappello , V. Neri , M. Livny , D. Thain, XtremWeb & Condor sharing resources between Internet connected Condor pools., Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.382, May 12-15, 2003
• 30: [30] Maui Scheduler. http://www. supercluster.org/maui.
• 31: Matt W. Mutka , Miron Livny, The available capacity of a privately owned workstation environment, Performance Evaluation, v.12 n.4, p.269-284, July 1991 [doi>10.1016/0166-5316(91)90005-N]
• 32: [32] J. Nabrzyski, J. Schopf, and J.Weglarz, editors. Grid Resource Management, chapter 26. Kluwer Press, 2003.
• 33: Andrew Oram , Andy Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 34: [34] The Portable Batch System Webpage. http:// www.openpbs.com.
• 35: [35] J. Pedroso, L. M. Silva, and J. G. Silva. Web-based metacomputing with JET. In Proc. of the ACM PPoPPWorkshop on Java for Science and Engineering Computation, June 1997.
• 36: [36] Platform Computing Inc. http://www. platform.com/.
• 37: D. H. J. Epema , M. Livny , R. van Dantzig , X. Evers , J. Pruyne, A worldwide flock of Condors: load sharing among workstation clusters, Future Generation Computer Systems, v.12 n.1, p.53-65, May 1996 [doi>10.1016/0167-739X(95)00035-Q]
• 38: Luis F. G. Sarmenta , Satoshi Hirano, Bayanihan: building and studying web-based volunteer computing systems using Java, Future Generation Computer Systems, v.15 n.5-6, p.675-686, Oct. 1999 [doi>10.1016/S0167-739X(99)00018-7]
• 39: [39] S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedinsg of MMCN, January 2002.
• 40: [40] The seti@home project. http://setiathome. ssl.berkeley.edu/.
• 41: [41] M. R. Shirts and V. S. Pande. Screen Savers of the World, Unite! Science, 290:1903-1904, 2000.
• 42: Shava Smallen , Henri Casanova , Francine Berman, Applying scheduling and tuning to on-line parallel tomography, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.12-12, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582046]
• 43: [43] W. T. Sullivan, D. Werthimer, S. Bowyer, J. Cobb, G. Gedye, and D. Anderson. A new major SETI project based on Project Serendip data and 100,000 personal computers. In Proc. of the Fifth Intl. Conf. on Bioastronomy, 1997.
• 44: [44] DataSynapse Inc. http://www. datasynapse.com/.
• 45: [45] United Devices Inc. http://www.ud.com/.
• 46: [46] Vijay Pande. Private communication, 2004.
• 47: Rich Wolski , Neil Spring , Jim Hayes, Predicting the CPU Availability of Time-Shared Unix Systems on the Computational Grid, Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, p.12, August 03-06, 1999
• 48: P. Wyckoff , K. Jeong , T. Johnson, Finding Idle Work Periods on Networks of Workstation, New York University, New York, NY, 1998