A ghost cell expansion method for reducing communications in solving PDE problems

ABSTRACT

In solving Partial Differential Equations, such as the Barotropic equations in ocean models, on Distributed Memory Computers, finite difference methods are commonly used. Most often, processor subdomain boundaries must be updated at each time step. This boundary update process involves many messages of small sizes, therefore large communication overhead. Here we propose a new approach which expands the ghost cell layers and thus updates boundaries much less frequently --- reducing total message volume and groupping small messages into bigger ones. Together with a technique for eliminating diagonal communications, the method speedup communication substantially, upto 170%. We explain the method and implementation in details, provide systematic timing results and performance analysis on the Cray T3E and IBM SP.

REFERENCES

• 1: V. Balaji, 2000. "Abstract Parallel Dynamical Kernels for Flexible Climate Models." Talk presented at ECMWF TeraComputing Workshop, Reading, England, Nov, 2000.
• 2: X.-C. Cai, D. E. Keyes and V. Venkatakrishnan. 1997. "Newton-Krylov-Schwarz: An Implicit Solver for CFD", Proc. 8th Int'l Conf. on Domain Decomposition Methods (R. Glowinski et al., eds.), Wiley, New York, pp.387-400.
• 3: T.F. Chan and J. Zou. 1994. Additive Schwarz Domain Decomposition Methods For Elliptic Problems On Unstructured Meshes. Numerical Algorithms, 8, pp.329-346.
• 4: Hong-Qiang Ding, Simulating lattice QCD on a CALTEC/JPL Hypercube, International Journal of Supercomputer Applications and High Performance Engineering, v.5 n.2, p.73-80, Summer 1991
• 5: Chris H. Q. Ding , Yun He, Data organization and I/O in a parallel ocean circulation model, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.33-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331565]
• 6: Chris H. Q. Ding, An Optimal Index Reshuffle Algorithm for Multidimensional Arrays and Its Applications for Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, v.12 n.3, p.306-315, March 2001 [doi>10.1109/71.914776]
• 7: John Drake , Ian Foster , John Michalakes , Brian Toonen , Patrick Worley, Design and performance of a scalable parallel community climate model, Parallel Computing, v.21 n.10, p.1571-1591, Oct. 1995 [doi>10.1016/0167-8191(96)80001-9]
• 8: J. Drake and P. Worley. 2000. Unpublished results.
• 9: James J. Hack , James M. Rosinski , David L. Williamson , Byron A. Boville , John E. Truesdale, Computational design of the NCAR community climate model, Parallel Computing, v.21 n.10, p.1545-1569, Oct. 1995 [doi>10.1016/0167-8191(95)00036-6]
• 10: S.M. Griffies, R.C. Pacanowski, M.Schmidt, V. Balaji. "Tracer Conservation with an Explicit Free Surface Method for Z-coordinate Ocean Models." Monthly Weather Review, 2001: 129, pp.1081-1098. See also http://www.gfdl.gov/~smg/MOM/MOM.html.
• 11: A. A. Mirin , D. E. Shumaker , M. F. Wehner, Efficient filtering techniques for finite-difference atmospheric general circulation models on parallel processors, Parallel Computing, v.24 n.5-6, p.729-740, June 1998 [doi>10.1016/S0167-8191(98)00012-X]
• 12: R. D. Smith , J. K. Dukowicz , R. C. Malone, Parallel ocean general circulation modeling, Physica D, v.60 n.1-4, p.38-61, Nov. 1, 1992
• 13: S. Atlas, S. Banerjee, J.C. Cummings, P.J. Hinker, M. Srikant, J.V.W. Reynders, and M. Tholburn. "POOMA: A high performance distributed simulation environment for scientific applications." Proc. Supercomputing '95, Nov 1995. see also http://www.acl.lanl.gov/pooma/.
• 14: D.L. Brown, W.D. Henshaw and D.J. Quinlan. "Overture: An Object-Oriented Framework for Solving Partial Differential Equations on Overlapping Grids." SIAM conference on Object Oriented Methods for Scientfic Computing, 1999. See also http://www.llnl.gov/CASC/Overture/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite difference methods

General Terms:
Algorithms, Design, Performance

Keywords:
PDE, bandwidth, ghost cells, latency, near neighbor communication