mardigras (Раздаточные материалы)

OBJECT-ORIENTED METHODS FORPARALLEL EXECUTION OFASTROPHYSICS SIMULATIONS Dennis Gannon, Shelby X. Yang, Paul Bode,Vladimir Me~nkov, and Suresh SrinivasDepartment of Computer Science, Indiana UniversityBloomington, Indiana 47405, U.S.A.1 INTRODUCTIONObject-oriented technology now forms the basis for a very large part of the softwaredevelopment industry.

This is especially true in the areas of computer graphics, database, graphical interface design and modern operating systems. We are also beginningto see the emergence of object-oriented methodology in scientic programming.1 Forparallel programming of scientic applications, there exist a number of new tools tohelp build portable, object-oriented software. Most of them are extensions to C++,the dominant object-oriented programming language. They include COOL [3], CC++[5, 4], Mentat [13], Charm++, and C** [15].

In addition, there are C++ libraries,such as P++ [17], which provide support for advanced data structure handling inparallel systems. Such libraries are an essential part of applications requiring adaptivestructured grids.In this paper we describe another C++ extension for parallel programming calledpC++ [16, 11, 2, 10, 12] and its use in Grand Challenge Cosmology Consortium (GC3)simulations. Section 2 of this paper contains a brief overview of pC++. In section 3and 4 we describe the implementation of two GC3 N-body codes in pC++.

Finally, wediscuss ideas of how pC++ can be used in adaptive mesh renement applications.2 OVERVIEW OF pC++The goal of the pC++ project is to design a simple extension to C++ for parallelprogramming that provides:This research is supported in part by ARPA under contract AF 30602-92-C-0135, the National Science Foundation Oce of Advanced Scientic Computing under grant ASC-9111616, and the NationalScience Foundation and ARPA Grand Challenge Award, \The Formation of Galaxies and Large-scaleStructure."1 For example, see the proceedings of the 1993 and 1994 Object-Oriented Numerics Conference.2 parallel object-oriented software that runs without modication on all commercialscalable parallel Multiple Instruction Multiple Data (MIMD) systems, an interface to Single Program Multiple Data (SPMD) libraries such as ScaLapack++ [8] and P++, an interface to High Performance Fortran (HPF), and an interface to \multithreaded" C++ languages like CC++.We emphasize that pC++, or other object-oriented parallel programming languages,should not be viewed as a replacement for Fortran90 or HPF.

Rather, object-orientedparallelism should be a tool to express the types of parallelism that cannot be easilyexpressed in Fortran. To accomplish this task pC++ exploits the two major characteristics of object-oriented design: encapsulation and inheritance.Encapsulation reects the principle of object-oriented language: closely related variables and functions are grouped together into a user-dened data type called class.

Aninstance of the data type is called an object and the associated functions are calledmember functions or methods of the class. Invoking a member function of an objectis often viewed as sending the object a message to carry out a specic task. In thisway an object-oriented program can be visualized as a network of objects each of whichmanages its own data structure and operates collectively by sending messages to otherobjects. This metaphor of communication lends itself perfectly to parallel execution,and most parallel programming extensions to C++ rely on this model.Inheritance allows a class to inherit selected data members and member functionsof other classes, rather than reimplementing them.

The inheritance mechanism used tobuild distributed data structures in pC++ is the same as in C++, i.e., through classderivation.pC++ has two basic extensions to the C++ language: a mechanism to describehow operations can be invoked over a set of objects in parallel, and a mechanism torefer to an individual object.A data structure called collection is used to describe a set of objects distributed overthe processors of a parallel machine. To build a collection of some class type T, whichis called an element class in pC++, one needs a distribution and an alignment object.The distribution object denes a grid and a mapping from the grid to the physicalprocessors on a parallel machine.

The alignment object species the shape, size, andthe mapping of the element objects to the grid points. In addition, a processor object,Processors, is needed to represent the set of processors available to use.Processors P;Distribution D(100,&P,BLOCK);Align A(20,"[ALIGN(X[i],D[i+10])]");creates a one dimensional grid of a size of 100 which is mapped to the processorsof the machine by blocks. If there are 20 processors, grid positions 0 through 4 aremapped to processor 0, positions 5 through 9 are mapped to processor 1, ..., etc. Thealignment aligns the logical vector X[0:19] with the grid positions D[10:29].

Given adistribution, an alignment and the class type of the element objects, it is easy to build3a collection. One of the base collections that pC++ collection library provides is theSuperKernel collection. It is designed to be used as the base collection for all othercollections. It builds arrays of element objects and provides global name space for theelement objects. The declarationSuperKernel<T> MyCollection(&D, &A);creates a collection called MyCollection which is a set of objects of type T.The most important feature of a collection is the ability to apply a function inparallel across all the element objects. For example, if T is dened asclass T{...public:void foo();...};where function foo() is a member function of the class, a parallel application of foo()to all the elements would take the following form:MyCollection.foo();To access an individual member of a collection, one can use the overloaded operator() which returns a global pointer to an element.

For example,MyCollection(i)returns a global pointer to the ith element in the collection. A global pointer is apointer that spans the entire address space of a distributed memory machine. In thisway, any object can have a global address. The following function callMyCollection(i)->foo();is a remote invocation, it sends a message to the processor that contains the ith elementand a thread on that processor executes the function. The remote invocation featureis an essential part of pC++ 2.0 and is not part of the current pC++ 1.0 distribution.Usually, a user would want to create a specialized collection that has propertiesappropriate for the application at hand.

The task of building a new derived collectionis almost the same as building a derived class in C++. A collection denition takesthe form shown below.Collection MyCollectionType: SuperKernel {public:// data members here are duplicated on each processor of a// parallel system. members functions here are executed in// parallel on all processors of the system.MethodOfElement:// data members and member functions here are// added to the element class.};4There are two types of data and member functions in a collection denition. Datamembers and functions labeled as MethodOfElement represent new functions and datathat are added to each element class.

The member functions are invoked just as ifthey are member functions of the element class. Other data member not labeled asMethodOfElement are duplicated on each processor and the functions are invoked inthe SPMD mode.In the next two sections we will illustrate the use of collection to dene paralleldata structures for the N-body simulation codes which are a part of the GC3 project.We will also show how our prototype Fortran interface is used in one of the codes, theSelf-Consistent Field code.3 THE SELF-CONSISTENT FIELD CODEOne of the N-body codes developed by GC3 researchers is the Self-Consistent Field(SCF) code, which is used to simulate the evolution of galaxies. It solves the coupled Vlasov and Poisson equation for collisionless stellar systems using the N-bodyapproximation approach.

To solve Poisson's equation for gravitational potential,r2(~r) = 4(~r);density and potential are expanded in a set of basis functions. The basis set isconstructed so that the lowest order members well-approximate a galaxy obeying thede Vaucouleurs R1=4 projected density prole law. The algorithm used in the SCF codeis described in detail in Hernquist and Ostriker 1992 [14].The original SCF code was written in Fortran77 by Lars Hernquist in 1991. In1993, the code was converted to Thinking Machines CM Fortran by Greg Bryan. Expirements conducted on the 512-node CM-5 at the National Center for SupercomputingApplications (NCSA) by Greg Bryan indicate that with 10 million particles the CMFcode can achieve 14.4 Gops on 512 nodes of the CM-5 (private communication).The expansions of the density and potential take the following forms:X Anlmnlm(~r);nlmX(~r) = Anlmnlm (~r);(~r) =nlmwhere n is the radial \quantum" number and l and m are quantum numbers for theangular variables.

Generally, the two sums will involve dierent expansion coecients.But the assumption of bi-orthogonality ensures a one-to-one relationship between termsin the expansions for the density and potential. The basis sets nlm and nlm also satisfyPoisson's equation:r2nlm (~r) = 4nlm(~r):The basis sets nlm and nlm are given bylpnlm (~r) = K2nl r(1 +rr)2l+3 Cn2l+3=2() 4Ylm(; );5pnlm (~r) = (1 +rr)2l+1 Cn2l+3=2() 4Ylm(; );where Knl is a number related only to n and l, and Cn2l+3=2() and Ylm(; ) are ultrasperical polynomials and spherical harmonics, respectively. After some algebra, theexpansion coecients becomeAnlm = I1 mk [nlm(rk ; k; k )];nl klXwhere Inl is a number and mk is the mass of the kth particle.

Once the gravitationalpotential is found, the gravitational force per unit mass can be obtained by taking thegradient of the potential and the particles can be accelerated accordingly.3.1 The pC++/Fortran Version of the SCF CodeWe design a C++ class called Segment to represent a subgroup of the N particles usedin the simulation. As we have discussed earlier, the major procedure in the SCF codeis to compute the sums for the expansion coecients Anlm . Our approach is to rstcompute local sums within each Segment object. After this, global sums are formed bya global reduction. The global sums are then broadcast back to each Segment objectwhere the particles are accelerated by the gravitational force.