Distributed Program Execution on Shared, Heterogeneous Systems

Introduction

The goal of the this project is the effective utilization of existing networked computers as a general purpose computational resource for executing parallel programs. Specifically, we are focusing on synchronization mechanisms and scheduling algorithms that manage distributed execution on networks of workstations that are not dedicated to the problem of interest. Here, the communications resources are those provided either by a local area network (for physically co-located computers) or a wide area network (for geographically remote computers). In addition, the computational resources are shared, typically with a primary user that is allowing spare cycles to be used as long as the distributed computation does not significantly interfere with the primary user's utilization of the machine.

To ensure that our work is relevant to the real world, we have four parallel applications we are using to test our ideas. The first is a simple toy problem designed to simplify the analysis of performance and ease the understanding of how the system operates. The remaining three applications are production codes used by academic research groups, one in transportation network design optimization (work directed by James Campbell at UMSL), a Barnes-Hut solver for the N-Body problem, and discrete-event simulation of VLSI systems (joint work with Bradley Noble at SIUE).

Historical Context

Previous work we have done in this area includes the development of an analytic performance model of synchronous iterative algorithms executing on shared, heterogeneous resources. Publications describing this work include:

• G.D. Peterson, and R.D. Chamberlain. ``Parallel Application Performance in a Shared Resource Environment.'' Distributed Systems Engineering, 3:9-19, 1996.

• B.L. Noble and R.D. Chamberlain. ``Performance of Speculative Computation in Synchronous Parallel Discrete-Event Simulation on Multiuser Execution Platforms.'' In Proc. of the 8th IASTED Int'l Conf. on Parallel and Distributed Computing and Systems, October 1996, pp. 489-494.

• G.D. Peterson and R.D. Chamberlain. ``Parallel Processing the Easy Way: How to Do It and When It Works.'' Journal of Computers and Their Applications , October 1995.

• R.D. Chamberlain, M.A. Franklin, G.D. Peterson, and M.A. Province. ``Genetic Epidemiology, Parallel Algorithms, and Workstation Networks.'' In Proc. of 28th Hawaii Int'l Conf. on System Sciences, Vol. V, January 1995, pp. 101-110.

• B.L. Noble, G.D. Peterson, and R.D. Chamberlain. ``Performance of Synchronous Parallel Discrete-Event Simulation.'' In Proc. of 28th Hawaii Int'l Conf. on System Sciences, Vol. II, January 1995, pp. 185-186.

• G.D. Peterson and R.D. Chamberlain. ``Stealing Cycles: Can We Get Along?'' In Proc. of 28th Hawaii Int'l Conf. on System Sciences, Vol. II, January 1995, pp. 422-431.

• G.D. Peterson and R.D. Chamberlain. ``Sharing Networked Workstations: A Performance Model.'' In Proc. of 6th Symp. on Parallel and Distributed Processing, October 1994, pp. 308-315.

• G.D. Peterson and R.D. Chamberlain. ``Beyond Execution Time: Expanding the Use of Performance Models.'' IEEE Parallel & Distributed Technology, 2(2):37-49, Summer 1994.

Recent Activities

We have recently extended the models described above to incorporate the effects of speculative computation. This work is reported in:

• B.L. Noble and R.D. Chamberlain, ``Analytic Performance Model for Speculative, Synchronous, Discrete-Event Simulation,'' In Proc. of 14th Workshop on Parallel and Distributed Simulation, June 2000.

• B.L. Noble and R.D. Chamberlain. ``Performance Model for Speculative Simulation Using Predictive Optimism.'' In Proc. of 32nd Hawaii Int'l Conf. on System Sciences, January 1999. (This paper won the Best Paper Award in the Software Technology Track at HICSS.)

Follow-on Activities

We are currently implementing an experimental testbed to investigate the properties of a whole host of scheduling algorithms and synchronization performance issues. This includes investigations into appropriate figures of merit for parallel application performance in a shared, heterogeneous execution environment. Publications describing this work include:

• B.L. Noble, J.C. Wade, and R.D. Chamberlain, ``Performance Predictions for Speculative, Synchronous, VLSI Logic Simulation,'' In Proc. of the 34th Annual Simulation Symposium, April 2001, pp. 56-64.

• R.D. Chamberlain and D.P. Discher, ``Simbench: A Logic Simulation Benchmark Set.'' In Proc. of the Mentor User's Group Conference, October 2000.

• R.D. Chamberlain, D. Chace, and A. Patil. ``How Are We Doing? An Efficiency Measure for Shared, Heterogeneous Systems.'' In Proc. of the ISCA 11th Int'l Conf. on Parallel and Distributed Computing Systems, September 1998, pp. 15-21.

Finally, we have investigated scheduling algorithms for clusters than enable background cycles to be effectively used without impacting the performance of the primary tasks on the system. This work is reported in:

• Gary Stiehr and Roger D. Chamberlain, "Improving Cluster Utilization through Intelligent Processor Sharing." In Proc. of Workshop on System Management Tools for Large-Scale Parallel Systems, April 2006.

Last modified 12 August 2006. Return to Roger's home page .

Roger Chamberlain <roger AT wustl.edu>