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:
Last modified 12 August 2006.
Return to Roger's home page .
Roger Chamberlain <roger AT wustl.edu>