pC++SciPro (1158313), страница 3
Текст из файла (страница 3)
Theidea behind these classes to be able to exploit well tuned sequential class libraries formatrix vector computation. Many of these are becoming available in both the publicdomain and commercial sources. A blocked vector is a segment of a large vector thatNote that potential race conditions can occur at this point. One processor may be modifying a localelement while another processor is reading a copy that may be out of date.
It is up to the programmer tomake sure that this does not cause problems.39resides on a processor. By supplying a well tuned Vector class as the element type,very good performance can be obtained.Distributing and blocking a vector does not change its functionality. For example,the operator sub() is a blocked vector subtraction and, when called asDistBlkVector<Vector> A,B,C;C.sub(A,B)it does the vector operation C = A B . Because sub operates on collections it must, inturn, invoke a function that knows how to do a subtraction of elements. In the library,sub() is dened asCollection DistBlkVector: DistributedArray{float dotProduct(DistBlkVector<ElementType>);double dotprodtemp; // used for dot product....MethodOfElement:int index1; // the index of "this" element....void sub(DistBlkVector<ElementType> &arg1,DistBlkVector<ElementType> &arg2){this->elementSub(*(arg1(index1)),*(arg2(index1)));};virtual void elementSub(ElementType &arg1, ElementType &arg2);void LocalDotProduct(Vector<ElementType> &arg){ThisCollection->dotprodtemp += this->elementDot(*arg1(index1));};virtual void elementDot(ElementType &arg);.....}The sub() function applies the element subtraction function elementSub() tocopies of the corresponding elements in the argument collections.
elementSub(),a virtual ElementType member function, does the actual elementwise subtraction.Consequently, any class that is provided as the element type of a DistBlkVectorcollection must provide this function.virtual can also be used in a class that is the basic element of a collection torefer to the element eld declared in the collection. However, we do not encouragethis practice.3 The Kernel ClassBefore proceeding further with examples of the language it is essential to take a brieflook at the functions provided by the kernel class.The role of the kernel is to provide a global name space for the collection elementsand also provides method for managing parallelism and collection element accesses.The kernel methods are the following:10intintintintintintintintintInstall_Collection(Template *T, Align *A, int sizeelem);Is_Local(int index);Is_Local(int index1, int index2);*Get_Element(int index);*Get_Element(int index1, int index2 );*Get_ElementPart(int index,int startof, int size);*Get_ElementPart(int index1, int index2,int startof, int size);*Get_CopyElem(int index);*Get_CopyElem(int index1, int index2 );The Install_Collection() takes a template and an alignment class to create thecollection.
For each collection in the program, there is a special data structure thatis created and stored on each processor of the system. This \local collection" objectcontains all the elements that are assigned to the processor by the initial alignment andtemplate distribution. In addition the local collection object contains a table thatdescribes how non-local elements may be accessed. This table is very similar to thedistributed manager used in shared virtual memory systems [8] [14]. Every elementhas a manager processor that is responsible for keeping track of where an elementresides and every processor knows who the manager of each element is.
The owner ofan element is the processor that has that element in its local collection.The Get_Element(i) method returns the ith collection element. If the elementis local then a reference to the element is returned. Otherwise a buer, owned by thecollection, is loaded with a copy of the remote element. The protocol consists of tworequests:1. Ask to the manager of the element which processor currently owns the element.2.
Load a copy of the element from the processor that owns the element.The reason for this two stage manager-owner scheme is to simplify dynamic collectionsand to provide a simple mechanism for load balancing. Our initial experiments on theCM-5 have shown that the added latency introduced by this scheme is very small (see[13]).Get_ElementPart() and Get_CopyElem() are similar. The former returns part ofthe elements and the latter allocates a new buer to keep a copy the element.
Howeverthere is no coherence for element copies and, at this time, no methods for updating aremote element is provided. However this has not been ruled out for the future.The current kernel is implemented on the NCSA CM5 using the CMAM communication package [2], the Intel Paragon using NX.4 Collection Function SPMD ExecutionThe greatest potential hazard for programmers using pC++ lies in managing the interface between the single control thread of the main program and the \multi-threadedSPMD" functions of the collections.
In particular, if a public collection functionreturns a value, care must be taken to insure each thread returns the same value! Forexample, consider the case of a standard parallel reduction like the dot product.DistBlkVector<Vector>float alpha;X, Y;11alpha = X.dotproduct(Y);If dotproduct() is called from the main control thread then each processor threadwill compute a value for the function. Because the result is assigned to a single scalar,the operation is not well dened unless all of the results are identical. This problemis easy to understand if one considers the runtime behavior on a distributed memorymulticomputer. The main control thread is run concurrently on each processor.
Allglobal variables and the stack are duplicated on each processor. (It is the job of thecompiler to make sure that any problems with a concurrent execution of the \sequentialcode", such as I/O, are properly handled.)To solve the problem of making sure the collection member functions all return aconsistant value, the library provides a family of special reduction functions.
Considerthe case of the dotproduct() function.double DistBlkVector::dotproduct(DistBlkVector<ElementType> & arg){dotprodtemp = 0.0;this->LocalDotProduct(arg); // called for each elementreturn( sumReduction(dotprodtemp));}To execute X.dotproduct(Y) each processor thread rst sets the variable dotprodtempin the corresponding local collection to zero. Then data parallel action of LocalDotProduct(arg)computes the element level dot products.
This computation is a simple sequential iteration on each processor thread which accumulates the values into the dotprodtempvariable of the collection:ThisCollection->dotprodtemp += this->elementDot(*arg1(index1));The pointer ThisCollection is a inherited from the DistributedArray and it provides away for each element to identify the collection to which it belongs. The sumReductionfunction computes and returns the total of the arguments on each processor thread.The reader may object to the fact that we have left the burden of synchronizingthread and returning consistent values to scalar functions up to the programmer.
Thealternative is to use a language extension that requires each collection function to usea special form of the return statement. Experience with applications should tell uswhich is the correct path.Other functions that can be used to synchronize and assure consistent returned values are multReduction, andRedcution and orReduction. Functions like broadcastBuffercan be used transmit a block of data from one processor thread to all the others.5 The Collection LibraryThe collection library for pC++ is designed to provide a set of primitive algebraicstructures that may be used in scientic and engineering computations.
Organized asa class hierarchy, the collection class tree is rooted with the kernel. There are twobasic types of collections: dynamic and static. Within the category of static structures,we have all the standard array, matrix and grid classes. These are described in detail12KernelDistributedArrayDistributedVectorDistributedBlkVectDistributedMatrixDistributedBlkMatrixDistributedRowMatrixDistributedColMatrixDistGridDisUnstrucMeshDistributedTreeFigure 2: The Collection Hierarchybelow. The other category includes collection types like trees, unstructured meshesdynamic lists and distributed queues.
This later category is still far from complete indesign and will be a subject of intense research over the next few years.There are two aspects to the problem of designing a parallel library for a languagelike pC++. First, one needs a basic set of element classes for numerical computationthat are well tuned to the individual processors of each parallel system.
Second, onemust have a set of collection denitions and the associated parallel operators that areboth scalable and easy for the user to extend. In addition, these collections must beeasy to integrate with other C++ numerical packages, like the LaPack++ system beingdesigned at Oak Ridge and Tennessee. Consequently, one can expect the denitionsshown below will change as these other packages come available.5.1 The Distributed ArrayThe DistributedArray class provides essential operators for manipulating arrays ofobjects.
Distributed arrays can be of arbitrary dimension and the element class typeis restricted only by the nature of the application. More accurately, distributed arrayshave a number of special global operators. These can only be used if the underlyingelement has the required properties. For example, it is not possible to nd the maximum value of a one dimensional array of elements if the elements do not have a totalorder based on the >; =; < operators.The Distributed array operators also include a generalization of the Fortran 90array section operators. By this we mean that if A is a DistributedArray of dimensionk, the expressionA[l1 : u1 : s1 ; l2 : u2 : s2; :::; lk : uk : sk ]13refers to the subdomain of the array specied in the ith dimension by the lower-bound,upper-bound, stride triplet li : ui : si .As with Fortran 90, a subarray can be used whereever a full array can be used. Forexample, if M is dened byDistributedArray<...> *M;M = new DistributedArray(&A, &T);where the alignment A gives the dimension of M to be 2, then if(*M).sin(x)means to apply the element function sin() to all the elements of the collection, thenM[1:100:2, 1:100:2].sin(x)means apply sin() to the odd indexed lattice points in M.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
