cnrs (1158306)
Текст из файла
Libraries and Tools for Object Parallel Programming.D. Gannona 1aCICA and Dept. of Computer Science, Indiana University, Bloomington, Indiana 47401USAAbstractThis paper describes a large project to build a complete programming environmentfor "object parallel" computation. We dene object parallelism as the extension of dataparallel computation to the domain of object oriented software.
In this model, collectionsof objects are distributed over processors in a manner consistent with HPF and Fortran90D. Class methods are invoked on all objects in the collection concurrently. There is arich hierarchy of "collection" classes which builds on the algebraic structures inherent inscientic applications.1. IntroductionThe proposed High Performance Fortran (HPF) standard represents a critical advancein software design for massively parallel (MP) computer systems. While largely motivatedby the preponderance of multicomputer system designs in which each processor has privatememory and all inter-thread communication is accomplished by message passing, HPF isalso important to any non-uniform memory access system. HPF is Fortran 90 togetherwith a system of annotations that enables the programmer to specify the way in whichdata structures are distributed throughout the machine.
The idea is not only simple andelegant, it will be supported by all the MP vendors.HPF is, by design, a conservative approach to the problem of how to involve the programmer in the task of parallelization. Consequently, it is limited in its range of applications to simple array data structures and dynamic or linked structures are not considered.(These limitations were essential to getting an agreed upon subset of annotations speciedthat all vendors could implement in a short time frame.)However, as applications become more complex they tend to use more complex datastructures.
A growing number of scientic and engineering programmers have turned tolanguages like C++ to build these applications because of the superior support providedfor data abstractions, [6], [5]. In addition, a style of parallel programming in C++ isemerging that encapsulates parallelism within a class hierarchy and allows the user towork with mathematical structures that are closer to the application [3], [2], [4]. In thispaper we will discuss the extension of the HPF ideas to a language like C++. We willargue that data distribution annotations are, by themselves, not sucient and present asimple extension to C++ that allows an "Object Parallel" data style similar in spirit to1Research Supported by NSF grant ASC-9111616 and DARPAconcurrent aggregates concept of Dally and Chien [9].
We will also discuss some of thecompiler issues and a strategy for using the class hierarchy to aid in the animation ofalgorithm and performance behavior.2. C++ Programming Using HPF Data Distribution Directive StyleA key idea in High Performance Fortran is to use data distribution directives to guidethe compiler to an ecient generation of SPMD code for MP systems.
In order to avoidconfusion with the ocial HPF standard, which has not yet been published, we willonly discuss the application of HPF-style data distributions ideas to C++ in this paper.(The interested reader can refer to the public HPF working notes from Rice Universitywhich are available by anonymous ftp from titan.cs.rice.edu. The C++ implementationdescribed here will be made consistent with the ocial HPF model after the committeehas nished their work.) It should also be noted that the ideas below are also found inthe Kali language [8], Fortran-D [7] and Vienna Fortran [13].The process of mapping data arrays to processors is seen as a two stage process: Arraysare aligned to templates and templates are distributed over processors .
For example,consider the trivial problem multiplying an n by n matrix A time a vector x of length nusing p processors. A naive solution would be to partition the the matrix into p blocks ofn=p rows each of size n and partition the operand vector x and the result vector y into pblocks of size n=p. The code and annotations to do this is given below./* MATRIX*VECTOR Version 1. Row-Blocked*/float A[n][n];float x[n], y[n];/*annotation( template T[n] )*//*annotation( align A[:][*] with T[:])*//*annotation( align x[:], y[:] with T[:]) *//*annotation( processors P[p] )*//*annotation( distribute T over P by(Block))*/for(i = 0; i < n; i++)for(j = 0; j < n; j++)y[i] += A[i][j]*x[j];The abstract template provides a target for array alignment and the processors annotation gives an abstraction of virtual processors.
The distribution directive species afunction that binds nodes of the template to the virtual processors. The "Block" distribution means that the rst n=p template nodes map to the rst virtual processor, thesecond n=p nodes map to the second virtual processor node, etc.The parallelism is derived by an analysis of the code using the "owner computes" rulewhich states that if a modication to a distributed data item is executed, then it will beexecuted by the processor that "owns" (via the distribution mappings) that data item.In the case at hand, this means the outer loop will be parallelized.
The kth processor willexecutefor(i = (n/p)*k; i < (n/p)*(k+1); i++)for(j = 0; j < n; j++)y[i] += A[i][j]*x[j];The only communication required is a copy of x to each processor. However, as observedby Schreiber in [12], this is version of the program is communication inecient, i.e. as thenumber of processors are scaled the time spent in communication will dominate, becauseit does not decrease as p increases.As advocated by Schreiber, a better scheme is to use a blocked partition of the arrayinto squares n=p1=2 on a side.
Unfortunately, it is nearly impossible to force the compilerto generate a parallel version of the program that achieves the optimal communicationeciency if the owner computes rule is to be respected. (The problem is that the vectory is modied, so the computation is based on how y is partitioned and not on how A isblocked.) Consequently, to achieve the best algorithm one must modify the program andintroduce a temporary two dimensional array which can be the target of the compilerscode generation strategy. The code is shown below./* MATRIX*VECTOR Version 1. Square-Blocked*/#define q sqrt(p)float A[n][n];float x[n], y[n], tmp[n][q];/*annotation( template T[n][n], T2[n][q])*//*annotation( align A[:][:] with T[:][:])*//*annotation( align x[:]with T[0][:])*//*annotation( align y[:]with T[:][0])*//*annotation( align tmp with T2)*//*annotation( processors P[q][q] )*//*annotation( distribute T over P by(Block, Block))*//*annotation( distribute T2 over P by(Block, Block))*/for(s = 0; s < q; s++)// parallelfor(i = 0; i < n; i++)// parallelfor(j = s*(n/q); j < (s+1)*(n/q); j++)tmp[i][s] += A[i][j]*x[j];for(i = 0; i < n; i++)// parallelfor(j = 0; j < q; j++)y[i] += tmp[i][j];With q = p1=2, the array x is aligned with the rst row of the template and y is mappedto the rst column.
The array tmp is used to contain the results of local matrix vectorproducts of the n=q by n=q matrix blocks times the operand vector x.The critical observation to make about this program is that we have had to modifythe source code in addition to adding annotations in order to coax the compiler intorecognizing a communications ecient assignment of work to processors. Consequently,we cannot view the process of inserting HFP style distribution annotations as sucientfor achieving high performance. This fact should be of no surprise; the processes ofparallelization is not independent of algorithm design.3. Object ParallelismIn spite of the awkward example from the preceding section, the Kali/Fortran-D/HPFmodel is very powerful and works well in many situations.
Furthermore, there is anobvious extension to array distributions in C and C++. One very interesting extension isto allow the concurrent evaluation of an class method on an array of objects. For example,let C be a class and X be an array of objects of that class.class C{.....public:void f(...);...};C X[100][100];/* annotation( template T[100][100] ) *//* annotation( align X[:][:] with T[:][:] */for(i = 0; i < 100; i++)for(j = 0; j < 100; j++)X[i][j].f(...);The parallelization of this can mean the concurrent application of the function f () to everyobject in the array. Because of the binding of f () to the object, the owner computes ruleextends nicely to object oriented program.
In other words, the distribution directivesallows objects to be assigned to processor which then own the objects. Invocation of anobject method means that the processor that owns the object is responsible for executingthe method function.Another way to achieve parallelism in C++ is to allow range expressions by overloadingthe colon operator \:" and the index operator [...] so that we may use expressions of theformX[0:99][0:99].f(...);to mean the Fortran90-like array expression parallel form of the loop above. Unfortunately, we cannot overload the [...] operator in this way for arrays in C++ unless wedene a special class. Even if we do this, the overloading of [...] is restricted in a waythat would prohibit this extension.In principle it is not hard to adapt the HPF annotations to the C and C++ environment.As described above, there are problems with the extension of Fortran 90 style vectorexpression syntax, but this is a minor issue.
Of greater signicant are the problemsassociated with pointers. For example, given the specication of a two dimensional arrayas a vector of pointers to rows of objects, as is often done in C programs,C *X[100];/* annotation( template T[100] )*//* annotation( align X[:] with T[:]*//* annotation( processors P[100] )*//* annotation( distribute T[:] over P[:] by (Block) */....for(i = 0; i < n; i++)X[i] = new C[100];we are saying that the array of pointers is distributed, but this does not say anythingabout the objects being referenced. If we assume that the new operator allocates withinthe same memory domain as the pointer to which it is being assigned it may be possibleto build a consistent semantics. A more serious problem is the realignment of the onedimensional array of one dimension arrays over a two dimensional template.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
