A Multicomputer Software Interface for Parallel Dynamic System Simulation

Abstract

This paper describes the creation of an intelligent software tool that performs automatic parallelization of dynamic system simulations for excecution on arbitrary message-passing multi- computing configurations. The tool greatly decreases the amount of time needed to obtain a viable multiple processor implementation of large-scale simulations and can be expanded to include the latest methodologies that exploit functional and data parallelism present within the simulation model and algorithm. Such a unifying tool is designed to increase the likelihood that a parallel realization of a simulation problem can be obtained which has an acceptable level of performance. To illustrate the feasibility of developing such a tool, this paper describes the prototype implementation of the Automated Partitioning and Mapping Engine (APME) and demonstrates its effectiveness when applied to a large-scale simulation executed on a number of multicomputer systems and topological configurations.

Keywords

Dynamic system simulation parallel processing multicomputers

Get full access to this article

View all access options for this article.

References

A. Makoui and W.J. Karplus , "ALI: A CSSL/Multiprocessor Software Interface," SIMULATION , vol 49, no 6, August 1987, pp 56-63.

. A. Makoui , Software Interface for Multiprocessor Simulation, PhD Dissertation, Computer Science Department, University of California, Los Angeles, CA, 1986.

R.E. Buhrer , et al., "The ETH-Multiprocessor EMPRESS: A Dynamically Configurable MIMD System," IEEE Transactions on Computers , vol C-31, no 11, November 1982, pp 1035-1044.

L.G. Birta and O. Abou-Rabia , "Parallel Block Predictor-Corrector Methods for ODE's", IEEE Transactions on Computers, vol C-36, no 3, March 1987, pp 299-311.

P.B. Worland , "Parallel Methods for the Numerical Solution of Ordinary Differential Equations," IEEE Transactions on Computers, vol C-25, no 10, October 1976, pp 1045-1048.

W.L. Miranker and W. Liniger , "Parallel Methods for the Numerical Integration of Ordinary Differential Equations," Mathematics and Computers , vol 21, pp 303-320.

M.A. Franklin , "Parallel Solution of Ordinary Differential Equations", IEEE Transactions on Computers, vol C-27, no 5, May 1978, pp. 413-420.

B. Kruatrachue and T. Lewis , "Grain Size Determination for Parallel Processing," IEEE Software, vol 5, no 1, January 1988, pp 23-31.

C.W. Gear , Numerical Initial-Value Problems in Ordinary Differential Equations, Prentice-Hall, Englewood Cliffs, N. J., 1971.

10.

E.G. Coffman , Computer and Job-Shop Scheduling Theory, New York: Wiley, 1976.

11.

H. Kasahara , and S. Narita , "Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing," IEEE Transactions on Computers , vol C-33, no 11, November 1984, pp 1023-1029.

12.

B. Shirazi , and M. Wang , "Analysis and Evaluation of Heuristic Methods for Static Task Scheduling," Journal of Parallel and Distributed Computing, vol 10, 1990, pp 222-232.

13.

S. Lei , A.Y. Allidina and K. Malinowski , "Clustering Technique for Rearranging ODE Systems", Proceedings of the First European Workshop on Parallel Processing Techniques for Simulation, 1985, pp 31-43.

14.

C.Y. Lee , J.J. Hwang , Y.C. Chow , and F.D. Anger , "Multiprocessor Scheduling with Interprocessor Communication Delays ," Operations Research Letters, vol 7, no 3, June 1988, pp 141-147.

15.

H. El-Rewini and T.G. Lewis , "Scheduling Parallel Program Tasks onto Arbitrary Target Machines," Journal of Parallel and Distributed Computing, vol 9, 1990, pp 138-153.

16.

B. Earl Wells and C.C. Carroll , "An Augmented Approach to Task Allocation: Combining Simulated Annealing with List-Based Heuristics", Proceedings of the Euronucro Workshop on Parallel and Distributed Processing, Gran Canaria, January 1993 , pp 508-515.

17.

J.C. Strauss , "The SCi Continuous System Simulation Language (CSSL)", SIMLILATION, vol 11, no 5, November 1968, pp 219-238.

18.

. Perihelion Software Ltd. , The Helios Parallel Operating System, Prentice-Hall, New Jersey, 1991.

19.

nCube Corporation, nCube 2 Programmer's Reference Manual, nCUBE Corporation, Beaverton, OR, 1992.

20.

A. Beguelin , J. Dongarra and A. Geist , "Visualization and Debugging in a Heterogeneous Environment", Computer, June 1993, pp 88-95.