Component-Based Derivation of a Parallel Stiff ODE Solver Implemented in a Cluster of Computers

ABSTRACT

A component-based methodological approach to derive distributed implementations of parallel ODE solvers is proposed. The proposal is based on the incorporation of explicit constructs for performance polymorphism into a methodology to derive group parallel programs of numerical methods from SPMD modules. These constructs enable the structuring of the derivation process into clearly defined steps, each one associated with a different type of optimization. The approach makes possible to obtain a flexible tuning of a parallel ODE solver for several execution contexts and applications. Following this methodological approach, a relevant parallel numerical scheme for solving stiff ODES has been optimized and implemented on a PC cluster. This numerical scheme is obtained from a Radau IIA Implicit Runge–Kutta method and exhibits a high degree of potential parallelism. Several numerical experiments have been performed by using several test problems with different structural characteristics. These experiments show satisfactory speedup results.

REFERENCES

• 1: 1. D. G. Zill, A First Course in Differential Equations with Modeling Applications, Brooks/ Cole (1997).
• 2: J. D. Lambert, Numerical methods for ordinary differential systems: the initial value problem, John Wiley & Sons, Inc., New York, NY, 1991
• 3: 3. W. M. Lioen, J. J. B. De Swart, and W. A. Van Der Veen, Test set for IVP solvers, Technical Report NM-89615, CWI (1996).
• 4: E. Hairer , S. P. Nørsett , G. Wanner, Solving ordinary differential equations I (2nd revised. ed.): nonstiff problems, Springer-Verlag New York, Inc., New York, NY, 1993
• 5: Kevin Burrage, Parallel and sequential methods for ordinary differential equations, Clarendon Press, New York, NY, 1995
• 6: 6. K. Dekker and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations, North Holland, Amsterdam (1984).
• 7: 7. G. Bjurel, G. Dahlquist, B. Lindberg, S. Linde, and L. Odén, Survey of Stiff Ordinary Differential Equations, Technical Report TRITA-NA-70. 11, Dept. of Numerical Analysis and Computing Science, The Royal Institute of Technology (1970).
• 8: Thomas Rauber , Gudula Rünger, Deriving structured parallel implementations for numerical methods, Microprocessing and Microprogramming, v.41 n.8-9, p.589-608, April 1996 [doi>10.1016/0165-6074(96)00007-5]
• 9: 9. C. Bendtsen, ParSODES--A Parallel Stiff ODE Solver. User's Guide, Technical Report 96- 07, UNI-C, DTU, Bldg (1996).
• 10: 10. Message Passing Interface Forum. MPI: A Message Passing Interface Standard, University of Tennessee, Knoxville, Tennessee (1995).
• 11: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 12: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 13: Jack J. Dongarra , David W. Walker, Software libraries for linear algebra computations on high performance computers, SIAM Review, v.37 n.2, p.151-180, June 1995 [doi>10.1137/1037042]
• 14: J. Choi , J. Dongarra , S. Ostrouchov , A. Petitet , D. Walker, A Proposal for a Set of Parallel Basic Linear Algebra Subprograms, University of Tennessee, Knoxville, TN, 1995
• 15: 15. A. Skjellum, A. P. Leung, S. G. Smith, R. D. Falgout, C. H. Still, and C. H. Baldwin, The Multicomputer Toolbox--First-Generation Scalable Libraries, HICSS-27, pp. 644-654 (1994).
• 16: 16. T. Rauber and G. Rünger, Diagonal-implicitly Runge-Kutta methods on distributed memory machines, International Journal of High Speed Computing 10:185-207 (June 1999).
• 17: 17. T. Rauber and G. Rünger, Parallel execution of embedded and iterated Runge-Kutta methods, Concurrency: Practice and Experience 11:367-385 (1999).
• 18: Lei Zhou , Elke A. Rundensteiner , Kang G. Shin, OODB Support for Real-Time Open-Architecture Controllers, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.206-213, April 11-13, 1995
• 19: 19. J. M. Mantas and J. Ortega Lopera, A Component-Based Stiff ODE Solver on a Cluster of Computers, 4th International Meeting on Vector and Parallel Processing, VECPAR'2000 (June 2000).
• 20: 20. C. Bendtsen, Parallel Numerical Algorithms for the Solution of Systems of Ordinary Differential Equations, Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark (1996).
• 21: P. J. van der Houwen , E. Messina, Parallel linear system solvers for Runge-Kutta-Nyström methods, Journal of Computational and Applied Mathematics, v.82 n.1-2, p.407-422, Sept. 15, 1997
• 22: 22. J. J. B. de Swart, Parallel Software for Implicit Differential Equations, Ph.D. thesis, Amsterdam University (1997).
• 23: Ernst Hairer , Gerhard Wanner, Stiff differential equations solved by Radau methods, Journal of Computational and Applied Mathematics, v.111 n.1-2, p.93-111, Nov. 15, 1999
• 24: 24. K. Gustafsson, Control of Error and Convergence in ODE Solvers, Ph.D. thesis,Lund Institute of Technology (1992).
• 25: T. Rauber , G. Runger , R. Wilhelm, Deriving optimal data distributions for group parallel numerical algorithms, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.33, October 09-12, 1995
• 26: 26. J. J. Dongarra and R. Clint Whaley, A user's guide to the BLACS v1.0, Technical Report CS-95-292, Computer Science Dept., University of Tennesee (1995).
• 27: 27. J. Li, A Poly-Algorithm for Parallel Dense Matrix Multiplication on Two-Dimensional Process Grid Topologies, Master's thesis, Mississippi State University (December 1996).
• 28: J. M. Mantas , A. Palma, Designing Reusable Software Components Following the CSP Distributed Programming Model, Proceedings of the 2nd International Workshop on Software Engineering for Parallel and Distributed Systems, p.174, May 17-18, 1997
• 29: Marulli Sitariman , Bruce Weide, Component-based software using RESOLVE, ACM SIGSOFT Software Engineering Notes, v.19 n.4, p.21-22, Oct. 1994 [doi>10.1145/190679.199221]
• 30: 30. O. Ciupke and R. Schmidt, Components as context-independent units of software, Workshop Reader of the 10th Eutopean Conference on Object-Oriented Programming ECOOP96 (1996).
• 31: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 32: Xiaolin Zhong, Additive semi-implicit Runge-Kutta methods for computing high-speed nonequilibrium reactive flows, Journal of Computational Physics, v.128 n.1, p.19-31, Oct. 1996 [doi>10.1006/jcph.1996.0193]
• 33: Behrooz A. Shirazi , Krishna M. Kavi , Ali R. Hurson, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 34: Ian Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 35: 35. W. Gropp and E. Lusk, User's guide for mpich, a portable implementation of MPI, Technical Report ANL-96/6, Argonne National Laboratory (1996). The updated version is at ftp://ftp.mcs.anl.gov/pub/mpi/userguide.ps.
• 36: Kjell Gustafsson , Gustaf Söderlind, Control Strategies for the Iterative Solution of Nonlinear Equations in ODE Solvers, SIAM Journal on Scientific Computing, v.18 n.1, p.23-40, January. 1997 [doi>10.1137/S1064827595287109]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software development

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods

General Terms:
Algorithms, Design

Keywords:
component-based software development, distributed memory machines, numerical algorithms with multilevel parallelism, parallel linear algebra libraries, stiff ordinary differential equations