Application-level scheduling on distributed heterogeneous networks

ABSTRACT

Heterogeneous networks are increasingly being used as platforms for resource-intensive distributed parallel applications. A critical contributor to the performance of such applications is the scheduling of constituent application tasks on the network. Since often the distributed resources cannot be brought under the control of a single global scheduler, the application must be scheduled by the user. To obtain the best performance, the user must take into account both application-specific and dynamic system information in developing a schedule which meets his or her performance criteria. In this paper, we define a set of principles underlying application-level scheduling and describe our work-in-progress building AppLeS (application-level scheduling) agents. We illustrate the application-level scheduling approach with a detailed description and results for a distributed 2D Jacobi application on two production heterogeneous platforms.

REFERENCES

• 1: C. Moore, WET ICE tools working group report, Proceedings of the 4th Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET-ICE'95), p.2, April 20-22, 1995
• 2: Eric A. Brewer, High-level optimization via automated statistical modeling, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-91, July 19-21, 1995, Santa Barbara, California, United States
• 3: DeFanti, T., Foster, I., Papka, M., Stevens, R. and Kuhfuss, T., Overview of the I-way: Wide area visual supercomputing, to appear in the International Journal of Supercomputer Applications.
• 4: Silvia M. Figueira , Francine Berman, Modeling the Effects of Contention on the Performance of Heterogeneous Applications, Proceedings of the High Performance Distributed Computing (HPDC '96), p.392, August 06-09, 1996
• 5: Fink, S., http://www-cse.ucsd.edu/groups/hpcl/scg/kelp.html, 1995.
• 6: Fink, S. J., Baden, S. B. and Kohn, S. R., Flexible communication mechanisms for dynamic structured applications, in preparation, 1996.
• 7: Freund, R., Proceedings of the 1996 IPPS Workshop on Heterogeneous Computing.
• 8: Gehrinf, J. and Reinfeld, A., Mars - a framework for minimizing the job execution time in a metacomputing environment, Proceedings of Future general Computer Systems (1996).
• 9: Al Geist , Adam Beguelin , Jack Dongarra , Weicheng Jiang , Robert Manchek , Vaidy Sunderam, PVM: Parallel virtual machine: a users' guide and tutorial for networked parallel computing, MIT Press, Cambridge, MA, 1995
• 10: Getov, V. S., Hockney, R. W. and Hey, A. J. G., Performance analysis of distributed applications by suitability functions, in Proceedings of the MPPM Conference (1993).
• 11: Globus, http://www.mcs.anl.gov/globus.
• 12: Andrew S. Grimshaw , William A. Wulf , James C. French , Alfred C. Weaver , Paul F. Reynolds, Jr., Legion: The Next Logical Step Toward a Nationwide Virtual Computer, University of Virginia, Charlottesville, VA, 1994
• 13: Hensgen, D. A., Moore, L., Kidd, T., Freund, R., Keith, E., Kussow, M., Lima, J. and Campbell, M., Adding rescheduling to and integrating condor with smartnet, in Proceedings of the Heterogeneous workshop (1995).
• 14: High Performance Fortran Forum, High performance fortran language specification, Rice Univeristy, Houston, Texas, May 1993.
• 15: Hoffman, J. D., Numerical Methods for Engineers and Scientists, McGraw-Hill, Inc, 1992.
• 16: Korab, H. and Brown, M., Virtual environments and distributed computing at SC'95: GII testbed and HPC challenge applications on the I-way. in Proceedings of Supercomputing '95 (1995).
• 17: Legion, http://www.cs.virginia.edu/~mentat/legion/legion.html.
• 18: Messina, P. and Heirich, A., personal communication, 1995.
• 19: Jim Pruyne , Miron Livny, Parallel Processing on Dynamic Resources with CARMI, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.259-278, April 25, 1995
• 20: PVM, http://www.epm.ornl.gov:80/pvm/.
• 21: Rudolph, L. and Feitelson, D., Proceedings of the 1996 IPPS Workshop on Job Scheduling Strategies for Parallel Processing (1996).
• 22: V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
• 23: Siegel, H., Antonio, J., Metzger, R., Tan, M. and Li, Y. A., Heterogeneous computing. Tech. Rep., Purdue University EE Technical Report TR-EE 94-37.
• 24: Zhang, X. and Yan, Y., A framework of performance prediction of parallel computing nondedicated heterogeneous now, in Proceedings of the 1995 International Conference on Parallel Processing (1995), pp. 163-7.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Design, Performance, Theory