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

Distributed pC++: Basic Ideas for an ObjectParallel Language Francois Bodin,Irisa, University of RennesCampus de Beaulieu, 35042 Rennes, FrancePeter Beckman, Dennis Gannon, Srinivas Narayana, Shelby X. YangDepartment of Computer ScienceIndiana University, Bloomington, IndianaAbstractpC++ is an object-parallel extension to the C++ programming language.

Thispaper describes the current language denition and illustrates the programming style.Examples of parallel linear algebra operations are presented and a fast poisson solveris described in complete detail.1 IntroductionThis paper provides an overview of pC++, an object-parallel programming languagefor both shared and distributed memory parallel systems. Traditional data-parallel systems are dened in terms of the parallel action of primative operators on the elementsof array data structures.

Object-parallelism extends this basic model of data-parallelexecution to the domain of object-oriented software by allowing the concurrent application of arbitrary functions to the elements of arbitrary distributed, aggregate datastrucutres.Because C++ is a de facto standard for a growing community of application designers, we have chosen to base the system around that language. More specically,the target audience for pC++ are programmers who have chosen C++ over Fortranfor reasons of software engineering, i.e., the construction of applications with complex,dynamic data structures not easily expressed in Fortran 77, or the need for an objectoriented framework not representable in Fortran 90.

In this situation, we believe pC++is ideal when performance is a premium and parallelism is the solution, so long as theresult is portable.Additional design objectives include:This research is supported by DARPA under contract AF 30602-92-C-0135, the National Science Foundation Oce of Advanced Scientic Computing under grant ASC-9111616, and Esprit BRA APPARC1 pC++ should have few departures from standard C++ syntax. The only newlanguage constructs are the Collection class and vector expressions.

A multi-threaded, Single Program, Multiple Data (SPMD) programming styleshould be available when needed. In addition to a data-parallelism model, aprogrammer can view part of the program as a single thread of control thatinvokes parallel operators on aggregates of data. At the same time, these paralleloperators can be viewed as interacting threads of computation that have explicitknowledge of data locality. There should be no \shared-address-space'' requirement for the runtime model.However, there needs to be a shared name space for distributed collections. Thisallows any execution thread to reference and access any element of any collection. Parallel programs written in pC++ should be portable across all scalable parallelsystems.

The High Performance Fortran Forum has now dened a standard fordata-parallel programs that can be compiled across a wide variety of architectures.We have used much of the HPFF Fortran as a model for mapping data andcomputation to MPP systems in pC++. The pC++ compiler should make extensive use of optimization techniques thathave been developed for transforming programs to run eciently on parallel systems.

pC++ programs should use of libraries of high quality, scalable, parallel algorithms. We expect that more than half of our eort will be devoted to buildingnew libraries and integrating existing ones into the system.pC++ is derived from an earlier experiment by Jenq Kuen Lee [6]. In its originalform, pC++ proved that it was possible to build a language that provided real portability of \object-parallel" programs across a variety of shared-address-space parallelsystems. A major challenge for pC++ is to show that a shared address space is notessential for good performance.2 CollectionspC++ is based on a simple extension to C++ that provides parallelism via distributedaggregates[3, 6]. Distributed aggregates are structured sets of objects distributed overprocessors of a parallel system.

Data structures such as vectors, arrays, matrices,grids, trees, dags or any other large, application specic aggregate can be described inpC++ as a collection class type. In a manner similar to C++ templates, collectionsare parameterized by the data type of the elements that make up the collection. Consequently, it is possible to describe structures such as a \distributed vector of real" or\distributed vector of quaternion" without modication to the concept of distributedvector. Indeed, collections of collections of objects can be dened such as a \tree ofgrids of nite-elements."Parallel operations on a collection can be generated either by the concurrent application of a method of the collection elements to the entire aggregate or by theapplication of a parallel operator associated with the collection itself.

This form ofparallelism is derived from data parallelism and we call it object parallelism.2The way in which elements of a collection are distributed over processors is determined by a two-step mechanism similar to HPFF Fortran. In the rst step, collectionelements are mapped to Template objects.

A template denes a \logical coordinatesystem" for arranging the distributed elements in a given computation in relation toeach other.1 The mapping of collection elements to a template is specied by an alignment object. In the second step, the template is mapped to processors by a mechanismcalled distribution.For example, suppose we want to create a matrix, A, and two vectors, X and Y, ofcomplex numbers and want to distribute them over processors of a parallel machine.Given a C++ class for complex numbers, Complex, we can build distributed matrixand vector collections by using the pC++ library collection classes DistributedMatrixand DistributedVector as follows:DistributedMatrix<Complex>DistributedVector<Complex>DistributedVector<Complex>A(...constructor arguments ...);X(...constructor arguments ...);Y(...constructor arguments ...);The declaration of a collection is specied by a collection type name followed by a typename of the element objects enclosed in angle brackets.

The arguments for the threeconstructors dene these collections in terms of alignments and template objects.2.1 Templates, Alignments, and ProcessorsTemplates can be viewed as abstract coordinate systems that allow us to align dierentcollections with respect to each other. If two elements from two dierent collectionsare mapped to the same template point, they will be allocated in the same processormemory.

Consequently, if there is a data communication between two collections, it isbest to align them so that costly interprocessor communication is minimized.Unlike HPFF Fortran, templates in pC++ are rst class objects.2 A template ischaracterized by its number of dimensions, the size in each dimension and the distribution by which the template is mapped to processors. Current distributions allowedin pC++ include BLOCK, CYCLIC, and WHOLE.To map a two-dimensional matrix A to a set of processors one can dene a twodimensional template and align the matrix with the template and then map the template to the processors. Suppose we have a 7 by 7 template and the matrix is of a sizeof 5 by 5, and suppose the template will be distributed over the processors by mappingan entire row of the template to an individual processor and the ith row is mapped toprocessor i mod P on a P processor machine, this mapping scheme corresponds to aCYCLIC distribution in the template row dimension and a WHOLE distribution in thetemplate column dimension.

pC++ has a special library class called Processors whichis implementation dependent. In the current implementations, it represents the set ofall processors available to the program at run time. The template and distribution canbe dened as follows.1We regret the potential confusion between the HPFF Fortran template concept and the C++ keywordtemplate. To avoid any potential problem we will not use examples involving C++ templates in this paper.Because templates are rst class objects they can be created at run-time or passed as a parameter toa function. This is very convenient for creating collections at run time, i.e., when creating a new collectionthe template and align objects can be taken from another collection with which the new collection is to bealigned.23Processors P;Template myTemplate(7, 7, &P, CYCLIC, WHOLE);The alignment of the matrix to the template is constructed by the declarationAlign myAlign(5, 5, "[ALIGN( dummy[i][j], myTemplate[i][j])]" );DistributedMatrix<Complex> A(&myTemplate, &myAlign);Notice that the alignment object myAlign denes a two-dimensional domain of a size5 5, and a mapping function.

The mapping function is described in terms of atext string which corresponds to the HPFF Fortran alignment directive. It denesa mapping from the domain to a template using dummy domain and dummy indexnames.We may now align the vectors to the same template. The choice of the alignmentis best determined by the way the collections are used. For example, suppose we wishto invoke the library function for matrix vector multiply as follows.Y = A*X;While the meaning and computational behavior of this expression is independent ofalignment and distribution, we would achieve best performance if we aligned X alongwith the rst row of the matrix A and Y with the rst column. (This is becausethe matrix vector algorithm, which is described in more detail later, broadcasts theoperand vector along the columns of the array and then performs a reduction alongrows.). The declarations take the formAlign XAlign(5, "[ALIGN( X[i], myTemplate[0][i])]");Align YAlign(5, "[ALIGN( Y[i], myTemplate[i][0])]");DistributedVector<Complex> X(&myTemplate, &XAlign);DistributedVector<Complex> Y(&myTemplate, &YAlign);The alignment and the template form a two stages mapping, as illustrated in Figure 1.The array is mapped into the template by the alignment object and the templatedenition denes the mapping to the processor set.Because all of the standard matrix-vector operators are overloaded with their mathematical meanings.

This permits expressions likeY = A*X;Y = Y + X;even though X and Y are not aligned together. We emphasize that the meaning ofthe computation is independent of the alignment and distribution; the correct datamovements will be generated so that the result will be the same.2.2 The Structure of a CollectionCollections are a special type of class with the following syntax.Collection NameOfCollectionType: Kernel{private:< private data fields and method functions>4XAlignX(myTemplate, XAlign)P(0)P(1)myAlignP(2)A(myTemplate, myAlign)P(3)myTemplate(7,7,&P,Cyclic, Whole)Y(myTemplate, YAlign);Figure 1: Alignment and Templateprotected:< protected data fields and method functions>public:< other public data fields and method functions>MethodOfElement:< data and functions that are added to each element>}; Collections are derived from a special machine dependent root class called Kernel.The Kernel class uses the template and alignment objects of a collection toinitialize the collection and allocate the appropriate element objects on eachmemory module.