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

On Using Object Oriented ParallelProgramming to BuildDistributed Algebraic AbstractionsDennis Gannon, Jenq Kuen Lee, Srinivas NarayanaCICA and Department of Computer ScienceIndiana UniversityAbstract. This paper considers the problem of designing numerical lin-ear algebra computations with a parallel object oriented programminglanguage. An extension to C++ based on a Concurrent Aggregate concept is used to describe a hierarchy of distributed structures includingdense matrices, sparse matrices, banded matrices, vectors and the associated linear algebra. We show that these abstractions are ideal fordescribing BLAS3 style blocked computation.

As an example we showhow to build a distributed conjugate gradient algorithms for sparse matrix (based on the NAS sparse benchmark and we show results for fourdierent parallel machines.1 IntroductionThere are two major problems with parallel computation as it applies to scienticprogramming. First, automatic parallelization of old Fortran programs is notshowing the types of speed-ups necessary to scale to hundreds or thousands ofprocessors.

Second, the alternative to compiling old programs is either to rewritethem in a machine specic, low level language or to wait for solutions like theHPC Fortran90-D [5] eort to become available. While the later alternative isnot bad, one is still left with a Fortran program with a structure that is a longway from the mathematical models that go into the design of the computations.In this paper we propose a methodology for using object-oriented style tobuild portable parallel programs that allow users to express computation completely in terms of the basic mathematical operators that describe the underlyingalgorithms.Our approach is to extend the C++ language with a new construct called thedistributed collection.

This new language is called pC++ [3, 4] and it currentlyruns on several dierent parallel processing platforms. To illustrate the ideasbehind pC++ in the context of scientic computation we will outline a designfor a distributed linear algebra collection-class hierarchy. By \distributed", wemean structures that have been partitioned among the available processors insuch a way that local memory and cache have been used to optimal advantage.In the last section of this paper we describe a large benchmark that we haveimplemented with this "object parallel" library and show some early results.2 Parallel C++ (pC++) and the Collection ConstructThe Collection construct is similar to class construct in the C++ language[6].The dierence is that a collection is a structured set of objects from some standard C++ class type that has been distributed over a set of processors.

The ideais very simple. Let C be a class of the formClass C{float data;....public:C operator +(C x);float foo();}C has an overloaded binary operator + and two functions. The collection classDistributedArray is part of the standard pC++ library. To dene a 2-dimensionalm by n array X of objects of type C which are distributed over a "vector" ofprocessors of size P, one writesDistributedArray<C> X([P], [m, n], [Block, Whole]);The key words Block and Whole describe how each dimension of the arrayis mapped to the 1-D array of processors. (This is identical to the Fortran-D,HP-Fortran model.)Parallelism now comes from two possible sources.

First, the operationX.foo();means the parallel invocation of the C class function foo on each element ofthe collection. Because foo returns a oat, the value returned by this call isof type DistributedArray < float > with the same shape and distribution asX. Similarly, the operator X + X is a parallel, pointwise application of the +operator to every member of the collection.The second source of parallelism is the invocation of parallel operators associated with the global Collection structure. For distributed arrays this includesglobal data movement and reduction operators.3 Inheritance and A Distributed Matrix Class HierarchyThe most powerful feature of C++, or any other object oriented language, is theability to dene a class hierarchy where one class is dened in terms of propertiesthat are inherited from another.

Our implementation for a parallel linear algebrasystem begins with such a C++ class hierarchy for standard sequential linearalgebra. In what follows we assume that there is a class vector which can be dened over the reals or complex numbers (single or double precision). In addition,we will make use of a class matrix with subclasses dense matrix, sparse matrixand banded matrix and all the associated operators. (For the complete details,the full version of this paper is available from gannon@iuvax.cs.indiana.edu.)In the same manner as C++ classes, pC++ collections form an inheritancehierarchy. To build a distributed vector collection we derive it from the DistributedArray class asCollection Dvector: DistributedArray{public:Dvector operator +(Dvector x);....};The collection Dvector has all the basic operators associated with a vector inthe standard linear algebra.

Consequently we can dene a distributed vector VasDvector<float> V(...);In our case we create a large-grain distributed vector by the declarationDvector<vector> V(...);We use a very simple method to build a distributed matrix. We view theprocessor set as a 1-D array and partition the c columns into c=P blocks whereP is the total number of available processors in exactly the same way as wehave described for distributed vectors.

as shown in Figure 1. The collection thatimplements this is called a Dcol matrix.P1P2P3Pp.....Dcol_matrix< sparse_matrix > M(..)Fig.1. A Distributed Column matrix of Sparse Matrices.By using the algebraic abstractions provided by this hierarchy a programmercan easily specify the type and structure for distributed vectors and matrices.For example, to dene a distributed sparse matrix A, and a pair of distributedvectors, x and y and to do a matrix vector multiply, one writesDcol_matrix<sparse_matrix> A(n,n);Dvector<vector> x(n), y(n);y = A*x;4 A Benchmark ExperimentTo illustrate the utility of these concepts we have rewritten the NASA AmesNAS Sparse Conjugate Gradient Benchmark to use these distributed matrixand vector abstractions.

This benchmark uses the CG algorithm to compute anapproximation of the smallest eigenvalue of a large, sparse, symmetric positivedenite matrix. According to the NASA team that designed the benchmark, thiscomputation is typical of unstructured grid computations in that it tests irregularlong distance communication in parallel machines by employing unstructuredmatrix vector multiplication.The benchmark code builds a large randomly sparse matrix and then makesfrequent calls to a CG solver, which when translated into pC++ is shown below.Our implementation uses one distributed sparse matrix and six distributedvectors.

There is a great deal more to this benchmark, but the following routineis the key component.void cgsol(int n, Dcol_matrix<sparse_matrix>& S, Dvector<vector>& b,Dvector<vector> & x, int nitcg, Dvector<vector> & r,Dvector<vector> & p, Dvector<vector> & q) {int i, iter;doublealpha, beta, rho, rho0, dinv;x = 0; r = b; p = r; rho = r*r;for(iter = 1; iter <= nitcg; iter++){q = S*p;alpha = rho /(p*q);x += alpha*p;rho0 = rho;r -= alpha*q;rho = r*r;beta = rho / rho0;p = (beta)*p + r;}r = S*x;r = b - r;resid = r.norm();}While we would like to say that our compiler can handle this routine asshown, there are still a few basic transformations that we have not completed.The most important of these involves the use of expressions of the formp = (beta)*p + r;A standard C++ compiler would allocate two temporary arrays: one to computethe product (beta)*p and another to return the value of the sum.

In pC++ wemust be more careful, because such an allocation would generate a distributedallocation and a lot of unnecessary copying. We plan to have these optimizationimplemented in the next version of the compiler.We have run the pC++ version of the program on four dierent machines.The BBN GP1000, the BBN TC2000, the Alliant FX/2800 and the ThinkingMachines CM-5. With the exception of the current CM-5 implementation (discussed below), the program is completely portable, so no no changes in the sourcecode was needed in moving from one machine to another.

The problem size canbe set by a parameter. We selected the largest problem that would run on allfour machines. The matrix size 2400 by 2400 with a total of 135238 randomzeros. Execution time and speed-up numbers are given in the table below. Thetimes are in seconds and the horizontal axis is the number of processors.MachineP= 5 P= 10 P= 12 P= 20 P= 25 P= 40GP1000 time 439 244 215 146 135 128speed-up4.98 8.95 10.16 14.95 16.19 17.07FX/2800 time 76.5 43.6 40.8speed-up4.6 8.01 8.6TC2000 time 91 54 49 36.5 35speed-up4.8 8.1 8.9 12 12.5As is clear from the experiments, the program is far from showing unboundedspeed-up.