Performance Evaluation Model for Scheduling in Global Computing Systems

Abstract

Striking progress of network technology is enabling high performance global computing, in which computational and data resources in a wide-area network (WAN) are transparently employed to solve large-scale problems. Several high performance global computing systems, such as Ninf, NetSolve, RCS, Legion, and Globus, have already been proposed. Each of these systems proposes to effectively achieve high performance with some efficient scheduling scheme, whereby a scheduler selects a set of appropriate computing resources that solve the client’s computational problem. This paper proposes a performance evaluation model for effective scheduling in global computing systems. The proposed model represents a global computing system by a queuing network, in which servers and networks are represented by queuing systems. Verification of the proposed model and evaluation of scheduling schemes on the model showed that the model could simulate behavior of an actual global computing system and scheduling on the system effectively.

Get full access to this article

View all access options for this article.

References

Abramson, D. , and Giddy, J. 1997. Scheduling large parametric modelling experiments on a distributed meta-computer . In PCW ‘97.

Arbenz, P. , Gander, W. , and Oettli, M. 1996. The remote computation system. In High Performance Computing and Networking, Lecture Notes in Computer Science 1067, pp. 820-825. New York: Springer-Verlag .

Berman, F. 1997. High-performance schedulers. In The Grid: Blueprint for a New Computing Infrastructure, eds. I. Foster and C. Kesselman. San Francisco: Morgan Kaufmann .

Berman, F. , and Wolski, R. 1997. The AppLeS project: A status report . In Proceedings of the 8th NEC Research Symposium.

Berman, F. , Wolski, R. , Figueira, S. , Schopf, J. , and Shao, G. 1996. Application-level scheduling on distributed heterogeneous networks . In Proceedings of Supercomputing ’96.

Bonomi, F. , and Kumar, A. 1990. Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler . IEEE Trans. on Computers 39 (10): 1232-1250 .

Casanova, H. , and Dongarra, J. 1996. NetSolve: A network server for solving computational science problems . In Proceedings of Supercomputing ’96.

Casanova, H. , Dongarra, J. , Johnson, C. , and Miller, M. 1998. Application specific tools. In The Grid: Blueprint for a New Computing Infrastructure, eds. I. Foster and C. Kesselman. San Francisco: Morgan Kaufmann .

Chow, Y. , and Kohler, W. H. 1979. Models for dynamic load balancing in a heterogeneous multiple processor system . IEEE Trans. on Computers C-28 (5): 354-361 .

10.

Eager, D. L. , Lazowska, E. D. , and Zahorjan, J. 1986. Adaptive load sharing in homogeneous distributed systems . IEEE Trans. on Software Engineering SE-12 (5): 662-675 .

11.

Feitelson, D. G. , and Rudolph, L. , eds. 1995-1998. Job Scheduling Strategies for Parallel Processing: Lecture Notes in Computer Science. New York: Springer-Verlag .

12.

Ferrari, D. , and Zhou, S. 1987. An empirical investigation of load indices for load balancing applications . In Proceedings Performance ’87, the 12th International Symposium on Computer Performance Modeling, Measurement, and Evaluation, pp. 515-528 .

13.

Foster, I. , and Kesselman, C. 1997a. Globus: A metacomputing infrastructure toolkit . International Journal of Supercomputing Applicatons 11 (2): 115-128 .

14.

Foster, I. , and Kesselman, C. 1997b. The globus toolkit. In The Grid: Blueprint for a New Computing Infrastructure, eds. I. Foster and C. Kesselman. San Francisco: Morgan Kaufmann .

15.

Gannon, D. , and Grimshaw, A. 1998. Object-based approaches. In The Grid: Blueprint for a New Computing Infrastructure, eds. I. Foster and C. Kesselman. San Francisco: Morgan Kaufmann .

16.

Grimshaw, A. S. , Wulf, W. A. , and the Legion Team . 1997. The Legion vision of a worldwide virtual computer . Comm ACM 40 (1): 39-45 .

17.

Jain, R. 1991. The Art of Computer Systems Performance Analysis. New York: John Wiley .

18.

Kunz, T. 1991. The influence of difference workload descriptions on a heuristic load balancing scheme . IEEE Trans. on Software Engineering 17 (7): 725-730 .

19.

Livny, M. , and Raman, R. 1997. High-throughput resource management. In The Grid: Blueprint for a New Computing Infrastructure, eds. I. Foster and C. Kesselman. San Francisco: Morgan Kaufmann .

20.

Lu, C. , and Lau, S. 1996. An adaptive load balancing algorithm for heterogeneous distributed systems with multiple task classes . In Proceedings of the 16th International Conference on Distributed Computing Systems, pp. 629-636 .

21.

Paxson, V. , and Floyd, S. 1998. Wide-area traffic: The failure of poisson modeling . In Proceedings of 1994 ACM SIGCOMM Conference, pp. 257-268 .

22.

Raman, R. , Livny, M. , and Solomon, M. 1998. Matchmaking: Distributed resource management for high throughput computing . In Proceedings of the 7th IEEE International Symposium on High Performance Distributed Computing.

23.

Sato, M. , Nakada, H. , Sekiguchi, S. , Matsuoka, S. , Nagashima, U. , and Takagi, H. 1997. Ninf: Network based information library for a global world-wide computing infrastructure . In Proceedings of High Performance Computing and Networking ’97. New York: Springer-Verlag.

24.

Shivaratori, N. G. , Krueger, P. , and Singhal, M. 1992. Load distributing for locally distributed systems . Computer 25 (12): 33-44 .

25.

Takefusa, A. , Matsuoka, S. , Ogawa, H. , Nakada, H. , Takagi, H. , Sato, M. , Sekiguchi, S. , and Nagashima, U. 1997. Multi-client LAN/WAN performance analysis of Ninf: A high-performance global computing system . In Proceedings of the ACM/IEEE SC97 Conference.

26.

Weissman, J. B. , and Zhao, X. Forthcoming. Scheduling parallel applications in distributed networks . J. Cluster Computing.

27.

Wolski, R. 1997. Forecasting network performance to support dynamic scheduling using the Network Weather Service . In Proceedings of the 6th High-Performance Distributed Computing Conference.

28.

Wolski, R. , Spring, N. , and Peterson, C. 1997. Implementing a performance forecasting system for metacomputing: The Network Weather Service . In Proceedings of the ACM/IEEE SC97 Conference.