supercomp91 (1158319), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

During the initialization, the tree aggregate can set up proper links between representatives,so they can refer to each other through corresponding \myparent", \left", and \right" methods. CAalso supports delegation which allows programmersto compose an concurrent aggregate behavior from anumber of aggregates or objects. Therefore, in CA,2ideas that the designers have introduced is very powerful and is completely extendible to an environmentwith more powerful data abstraction facilities.neous collection of class elements which are groupedtogether and can be referenced by a single collectionname. Each collection is also associated with a distribution and a set of active computational representatives.

Another name for the active computationalrepresentative is processor representative which represents virtual processors at run time. The elements ina collection will be distributed among the processorrepresentatives. How the elements of the collectionare distributed among computational representativesis described by the distribution associated with thecollection.A new idea involving hierarchies of abstractions isemployed in the Distributed Collection Model in orderto build useful abstractions. In the Distributed Collection Model not only can methods of collections bedescribed and inherited by the other collection, butalso the element class can inherit knowledge of the algebraic and geometric structure of the collection. Furthermore algebraic properties of the element class canbe used by methods of the collection without detailedknowledge of implementation in the element class. Forexample, we can have a DistributedList Collection ofwhich the basic element is a SemiGroup by describingthe general properties of a SemiGroup element in theCollection.

We then can build a ParallelPrex methodfor the collection based on the operator of the abstractSemiGroup element without knowing the specic details about element class. Consequently ParallelPrexcan be a generic library operator which can be appliedto any user dened element class that has an associative operator. This ability of a collection to describethe abstraction of elements gives us great exibilitiesin building libraries of powerful distributed data structures.The computational behavior in the distributed collection model can be described as follows.

Any message sent to an element of a collection is, by default,received, processed, computed, and replied to by theprocessor representative which owns the particular element. To initiate a parallel action, an element methodcan be invoked by the collection which means that thecorresponding method is applied to all elements of thecollection logically in parallel (with each processor representative applying the method to the elements thatit owns.) If the number of elements of the collectionis large relative to the number of processors, the compiler is free to use whatever technique is available toexploit any \parallel slack" [?] to hide latency.

ADOALL operator can also be used to send a messageto a particular subset of the processor representativesin the distributed collection.2.3 Other Related WorksSOS[12] is a distributed, object-oriented operating system based on the proxy principle. One of thegoal of SOS is to oer an object management supportlayer common to object-oriented applications and languages. SOS also supports Fragmented Objects(FOs),i.e.

objects whose representation spreads across multiple address spaces. Fragments of a single FO areobjects that enjoy mutual communication privileges.A fragment acts as a proxy, i.e a local interface to theFO. Our assessment is that the SOS does not supportmany of distribution patterns which are frequentlyused in the parallel programming. The creation ofa distributed collection and the mapping of a globalindex to a local index may take longer time than necessary when supported by FOs.Bain[1] uses a global object name space to supportn-dimensional array of simple objects, which are calledindexed objects.

Indexed objects are created throughthe procedure call Alloc iobj and allow the invocationof the specied procedure on all elements of an indexedobject. While indexed objects support a very usefulinterface, it does not allow users to specify how objects are distributed among processors and since it isnot based on an object-oriented environments, it doesnot support the hierarchies of abstractions for buildingdierent abstract structures of indexed objects.3 Distributed Collection ModelThe Distributed Collection Model, described below,is an object-based model for programmers to build distributed data structures, such as arrays, lists, sets andbinary trees.

In the model, programmers can keep aglobal view of the whole data structure as an abstractdata type and also specify how the global structuresare arranged and distributed among dierent processors to exploit memory locality. The model also supports hierarchies of abstractions and thus it is easyto build libraries and reusable implementation of distributed programs. Massive parallelism is expressedby sending a message to the collection to invoke amethod belonging to the class of the constituent element.The major components in the distributed collectionmodel are the collection, element, processor representatives, and distribution. A collection is a homoge3The model also supports a group of useful operators.

A set of reshape operators support dynamic realignment of the distribution of the collection at runtime. While the number of elements of the whole collection still remains the same, the distribution of thecollection can change from parallel phase to parallelphase. The model also support operators for an element to refer to other elements in its neighborhood,methods to refer to an element of the whole collection,and methods to refer to sub-groups of elements of aparticular processor representative.details later. The third point to observe is the constructor method and its three parameters.

We willpostpone discussion of this briey.Next we must dene the basic element of our distributed list. This is done as follows.class element: ElementTypeOf DistributedList {int value, average;update(){average=1/2*(self(1)->value+self(-1)->value);}};The keyword ElementTypeOf identies the distributed collection to which this element class will belong. As mentioned above the reason that the element needs such an identication is that we may inherit functions that identify the algebraic structure ofthe collection. In this case, we have dened a simple method update() which makes the average of thecurrent element equal to the numerical average of thevalue eld of its two neighbors.

Notice that self() istreated like a pointer (in the C sense) into our orderedlist and that we can add osets to access the eld variables of sibling elements in the collection.At this point we have not indicated how collectionsare distributed and what role the programmer playsin this.

Following the mechanism in Kali, we breakthe process down into three components. First eachcollection must be associated with a number of processors which we view as indexed in some manner.Second we must describe the global shape of the collection and third, we must describe how the collectionis partitioned over the processors.In each case we use a special new C built-in classcalled a vector constant, or vconstant in short, to denote explicit vector values. Vector constants are delimited by \[" and \]". For example [14, 33] is a vector element of Z 2 whose rst component is 14 andwhose second component is 33.

If we wish to declarea distributed list G to be viewed as being distributedover a one dimensional set of MAXP ROC processors and we wish the list to be indexed as a list ofM elements which are distributed by a block scheme(each processor representative getting a sequential setof M=MAXP ROC elements) we invoke the collectionconstructor as follows4 The PC++ LanguageIn this section, we present a parallel C++ languagewith a collection construct that we use as a testbed forexperimenting with algorithm descriptions and compiler optimizations. A set of built-in abstractions ofdistributed data structures and several examples arealso presented.4.1 Collection ConstructsThe Collection construct is similar to class construct in the C++ language[7]. The syntax can bedescribed as follows:Collection <collection-name>:<inherited_collection>{ method_list; };To illustrate how a collection is used consider thefollowing problem.

Let us design a distributed collection which will be an abstraction for an indexed list(one dimensional array). We would like each list element to have two elds: value and average. We rstdene the collection structure.Collection DistributedList : Kernel {MethodOfElement:self(...):Public:DistributedList(ProcSet,shape,distribution);};There are three points to observe here. First, thekeyword MethodOfElement refers to the method self().This specication means that self() is a method thatcan be used as part of the basic elements of the list torefer to the structure as a whole. (Methods declaredthis way are virtual and public by default.) The second point to consider is the super \collection class"called Kernel. This is a basic built-in collection witha number of special methods that are fundamental tothe runtime system which will be described in greaterDistributedList<element> G([MAXPROC],[M],[Block]);The common distribution keywords other thanBlock are W hole which means no distribution, Cyclicwhich is a round-robin rotation and Random whichis random.

Характеристики

Список файлов учебной работы