Resource use pattern analysis for opportunistic grids

ABSTRACT

This work presents a method for predicting resource availability in opportunistic grids by means of Use Pattern Analysis (UPA), a technique based on non-supervised learning methods. The basic assumptions of the method and its capability to predict resource availability were demonstrated by simulations; accurate learning techniques and distance metrics are determined. The UPA method was implemented and experiments showed the feasibility of its use in low-overhead scheduling of grid tasks and its superiority over other predictive and non-predictive methods.

REFERENCES

• 1: David P. Anderson, BOINC: A System for Public-Resource Computing and Storage, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.4-10, November 08-08, 2004 [doi>10.1109/GRID.2004.14]
• 2: H. B. Barlow, Unsupervised learning, Unsupervised learning, Bradford Company, Scituate, MA, 1999
• 3: W. Cirne, F. Brasileiro, N. Andrade, L. Costa, A. Andrade, R. Novaes, and M. Mowbray. Labs of the world, unite!!! Journal of Grid Computing, 4(3):225--246, September 2006.
• 4: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.
• 5: B. Everitt, S. Landau, and M. Leese. Cluster Analysis. Hodder Arnold, 4th edition edition, 2001.
• 6: Andrei Goldchleger , Fabio Kon , Alfredo Goldman , Marcelo Finger , Germano Capistrano Bezerra, InteGrade object-oriented Grid middleware leveraging the idle computing power of desktop machines: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.5, p.449-459, April 2004 [doi>10.1002/cpe.v16:5]
• 7: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 8: D. Kondo, A. Andrzejak, and D. P. Anderson. On correlated availability in internet-distributed systems. In 9th IEEE/ACM International Conference on Grid Computing (Grid 2008), 2008.
• 9: C. B. Lee, Y. Schwartzman, J. Hardy, and A. Snavely. Are user runtime estimates inherently inaccurate? In JSSPP, volume 3277 of Lecture Notes in Computer Science, pages 253--263, 2004.
• 10: M. Litzkow, M. Livny, and M. Mutka. Condor - A hunter of idle workstations. In ICDCS '88: Proceedings of the 8th Int. Conference of Distributed Computing Systems, pages 104--111, June 1988.
• 11: N. T. Loc, S. Elnaffar, T. Katayama, and H. T. Bao. Grid scheduling using 2-phase prediction (2pp) of cpu power. Innovations in Information Technology, 150, issue 2:1--5, 2006.
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: M. Silberstein, D. Geiger, and A. Schuster. Scheduling mixed workloads in multi-grids: the grid execution hierarchy. In Proceedings of the 15th International Symposium on High Performance Distributed Computing (HPDC06), pages 291--302, 2006.
• 14: D. Wright. Cheap cycles from the desktop to the dedicated cluster: Combining opportunistic and dedicated scheduling with Condor. In Proceedings of Linux Clusters: The HPC Revolution, 2001.
• 15: Lingyun Yang , Jennifer M. Schopf , Ian Foster, Conservative Scheduling: Using Predicted Variance to Improve Scheduling Decisions in Dynamic Environments, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.31, November 15-21, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Performance

Keywords:
grid computing, opportunistic grids, scheduling, use pattern analysis