


CRPC's Differential Equations Group Seeks Parallel Solutions DecCRPC's Differential Equations Group Seeks Parallel Solutions Dec 3 RESEARCH REGISTER HPCwire Editor's Note: Dan Meiron, a member of the Differential Equations group, has been made the Executive Officer of Applied Mathematics (officially as of November 1) at Caltech. For more information of Merion, select 2869. *****************************************************************************
*****************************************************************************
TEMPLATES FOR SCIENTIFIC COMPUTATION In collaboration with the CRPC's Parallel Paradigm Integration group, many of the algorithms developed by the Differential Equations group are being incorporated into programming templates. Research in regular mesh templates for scientific computation attempts to encapsulate common data distributions and communication patterns that arise in diverse scientific applications. The goal is to allow users to write portable deterministic code. This approach shows promise for a wide variety of applications, including spectral methods in two and three dimensions for the equations of fluid motion as well as other partial differential equations, finite difference methods on regular grids, and largescale molecular orbital calculations. Each of these applications displays a typical data distribution and communication pattern. If a particular application shares this pattern, then conversion of a serial algorithm to a parallel one using the appropriate template becomes straightforward. At present, the group has implemented all templates under development in Fortran M, a small extension of Fortran 77 developed by the Parallel Paradigm Integration group that provides facilities for both task and data parallelism. However, the templates can also be implemented using standard Fortran 77 and any of the popular messagepassing libraries such as PVM or P4. So far, the group has completed the development of several templates and ported them to different architectures. Future plans include implementing these templates on heterogeneous networks of workstations using PVM or P4. Also under investigation is the extension of the template concept to much more sophisticated algorithms such as the fast particle methods for astrophysical Nbody calculations developed by CRPC researchers John Salmon and Michael Warren. These fast particle methods can be used, for example, to implement fast panel methods as a way of computing fluid flow over complex threedimensional bodies. The SalmonWarren algorithm has recently been re designed using a new parallel data structure, the hashed octtree, and several calculations have been completed using this new approach. The research group will investigate implementation of this algorithm as a template in CC++, another parallel language developed by the Parallel Paradigm Integration group that provides parallel extensions to the C++ language and thus allows for the design of classes that encapsulate parallel computation. Several of the templates being developed are potential candidates for use in the CRPC's PCETech program. OBJECTORIENTED APPROACHES Research in the application of an objectoriented approach to parallel computation has as its objective the development of class libraries for parallel structured mesh computations that are compatible across serial, vector, and parallel machines. These libraries facilitate the design, for example, of portable hydrodynamics codes that utilize adaptive mesh refinement. Researchers from the group have to date developed serial array class libraries in C++ for structured mesh computations. The array libraries may be used in the PCETech program. Plans are underway to include parallel objects for array operations and to develop adaptive mesh refinement for specific applications like steady and transient problems. Other objectoriented research focuses on parallel particleincell simulations for plasma physics and concurrent adaptive methods for reaction diffusion equations. For the latter project, software is being developed for concurrent computations using dynamically adaptive triangular meshes. This is an interdisciplinary collaboration involving methods in concurrent computation, linear algebra, and numerical error estimation. ADAPTIVE MESH REFINEMENT AND COMPUTATIONAL FLUID DYNAMICS The group is planning to investigate reduction of the communications costs in adaptive mesh refinement (AMR) by using a data structure that requires only fast communications. AMR techniques for finite difference methods have resolved approximate solutions of partial differential equations of high speed fluid flow without requiring a fine lattice or a small time step in every part of the field. Use of AMR, however, can lead to load imbalances and a large communications overhead if not carefully implemented. Computational fluid dynamics projects concerning vortex reconnection and chemically reacting hypersonic flows also play an important part in the group's plans. The goal here is to implement the template ideas described above to these grand challenge applications and to use largescale parallel simulations to answer key questions on the nature of smallscale structures in fluid flow. DOMAIN DECOMPOSITION Domain decomposition can be used to impose a structure on the code that advantageously restricts the amount and type of interprocessor communication required to solve the problem. The Differential Equations group is developing codes for parallel domain decomposition and multigrid for large nonlinear systems of coupled elliptic and parabolic partial differential equations. Other research areas include the development of operatorbased averaging techniques for rough coefficient problems, local mesh refinements near localized heterogeneities or singularities (such as around horizontal and vertical wells), and extensions of the algorithms to unstructured grids. Major difficulties that arise in these models include load balancing, time step constraints, the definition of effective preconditioners for solving the interface problem that connects the subdomains, and the ability to follow interacting reactive and advective flows. HOMOTOPY AND CONTINUATION METHODS Research in continuation and homotopy methods for solving nonlinear problems will emphasize parallel algorithms and implementations. A basic class of model problems to which the new techniques should be applicable is the discretization of the steadystate NavierStokes equations in two or three dimensions. New procedures for stabilization of steady states in time evolution methods will be applied to handle general fixedpoint iterations, stiff systems, periodic solutions, and other areas where possible. MULTILEVEL METHODS Algorithms involving nested grids have proven to be particularly useful in scientific computation. However, they have usually not performed optimally on distributedmemory parallel architectures because of problems with data structures and locality. The Differential Equations group is concentrating on multilevel algorithms in four areas: discretized algebraic equations, segment relaxation, nonlinear equations, and homogenization. NEW DIRECTIONS Research in parallel I/O will become more important to this group in the future. This will be an interdisciplinary effort focusing on Fortran M and CC++. Support from research initiatives in scalable I/O and from the NSF HPCC community has been obtained for this work. In the long term, the group plans to deploy and evaluate many of the software technologies under development on selected grand challenge applications.  Reprinted with permission from the October 1993 issue of Parallel Computing Research, Volume 1, Issue 4, the newsletter of the Center for Research on Parallel Computation. *****************************************************************************
901) ANS 902) IBM Corp. 904) Intel SSD 905) Maximum Strategy 906) nCUBE 907) Digital Equipment 908) HewlettPackard 909) Fujitsu America 910) Convex Computer 912) Avalon Computer 914) Applied Parallel Res. 915) Genias Software 916) MasPar Computer 919) Transtech Parallel 921) Cray Research Inc. *****************************************************************************
Sites & Affiliations  Leadership  Research & Applications  Major Accomplishments  FAQ  Search  Knowledge & Technology Transfer  Calendar of Events  Education & Outreach  Media Resources  Technical Reports & Publications  Parallel Computing Research Quarterly Newsletter  News Archives  Contact Information
