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

Object Oriented Parallel ProgrammingExperiments and ResultsJenq Kuen LeeDennis GannonDepartment of Computer ScienceIndiana UniversityBloomington, IN 47401AbstractWe present an object-oriented, parallel programming paradigm, called the distributed collection modeland an experimental language PC++ based on thismodel. In the distributed collection model, programmers can describe the data distribution of elementsamong processors to utilize memory locality and a collection construct is employed to build distributed structures. The model also supports the express of massiveparallelism and a new mechanism for building hierarchies of abstractions.We have implemented PC++ on a variety of machines including VAX8800, Alliant FX/8, AlliantFX/2800, and BBN GP1000. Our experience withapplication programs in these environments as well asperformance results are also described in the paper.1 IntroductionMassively parallel systems consisting of thousandsof processors oer huge aggregate computing power.Unfortunately, a new machine of this class is almostuseless unless there is a reasonable mechanism forporting software to it so that the resulting code willboth be ecient and scale well.

FORTRAN 90 hasbeen proposed as a standard for SIMD \data parallel"systems but it cannot be compiled well for distributedmemory machines. Linda[3] is an excellent model fordistributed MIMD processing, but it is not well suitedto systems like the connection machine or the MasParMP1. In this paper we describe a model of programming and an experimental programming language anda compiler project that we hope can be used on a variety of parallel architectures.There are four major issues to be addressed toachieve scalability and portability.

First, many of theMIMD machines available today use a collection of local memories to implement the global memory space.The access to global memory space will normally takeO(Log2 p) time where p is the number of processors,while the access to the processor's local memory willonly take O(1) time. Therefore the language shouldprovide some means for programmers to utilize memory locality in their programs.Second, algorithm designers tend to think interms of synchronous operations on distributed datastructures[5], such as arrays, sets, trees and so forth,but conventional languages provide no support forthe ecient implementation of these abstractions in acomplex memory hierarchy. In the distributed memory case, programmers must decompose each datastructure into a collection of pieces each owned bya single processor.

Furthermore, access to a remotecomponent of the data must be accomplished throughcomplex \send" and \receive" protocols. The globalview of traditional data structures, such as matrices,grids and so on, becomes unreadable and complicatedand decomposing all data structures this way leads toprograms which can be extraordinary complicated.Third, as is the case with large sequential programs,it must be possible to use a hierarchy of abstractions torelegate details to the proper level in a program[2]. Byusing hierarchy of abstractions in concurrent programming, it is easy to hide the low level implementationand to build libraries and reusable implementation ofdistributed programs.Fourth, the language should allow programmers tospecify massive parallelism.

In an object-based model,programmers tend to think in terms of a distributedcollection of elements. To initial a parallel action, anelement method can be invoked by the collection whichmeans that the corresponding method is applied to allelements of the collection simultaneously. This mechanism enables us to express massive parallelism andisolate the communication structure of the computation from the basic local computations.The object-based model presented here, called Dis-tributed Collection Model, will be shown to supporta hierarchy of abstractions can be used to hide lowlevel implementation and build reusable abstractionsof distributed data structures.While we feel that this is an extremely powerfuland elegant construction, there are still several thingsmissing in CA.

First, the model can not specify howthe elements in an aggregate should be distributedamong processors and the percentage of processor resources that should be involved in an aggregate. Whenthe number of elements in an aggregate is signicantlygreater than the number of processors, simple and natural distributions specied by programmers often canbest utilize memory locality resulting in optimal algorithms. The second shortcoming is that the modeldoes not utilize the natural parallelism of an aggregate.

As we will see later, the invocation of an aggregate method \inherited" from the element class of theaggregate can be used as a mechanism to explicitlycontrol concurrency. Thus, the invocation of methods of the element by the aggregate can be used torepresent the massive parallelism.all four of the points described above.

We also describe a parallel C++ language, called PC++, with acollection construct as our rst approximation to thismodel. We have implemented PC++ on a variety ofmachines including VAX8800, Alliant FX/8, AlliantFX/2800, and BBN GP1000 systems. Our experiencewith building application programs as well as experimental results on these machines are described in thepaper.The remainder of this paper is organized as follows.In section 2, we examine two programming paradigmsthat have formed the basis of our thinking: the Concurrent Aggregate model and the Kali programminglanguage. We will look closely at these two languagesto see how they support the issues described above andwe will also examine them what is missing.

Section 3describes the Distributed Collection Model. Section4 presents the parallel C++ language with the collection construct based on the distributed collectionmodel. Section 5 describes several applications constructed by utilizing collection libraries. The experimental results are also presented. Finally, section 6gives our conclusion.2.2 Kali Programming ModelThe Kali programming environment[5] is targetedto scientic applications. The fundamental goal ofKali is to allow programmers to build distributed datastructures and treat distributed data structures as single objects.

Kali thus provides a software layer supporting a global name space on distributed memoryarchitectures. In Kali, programmers can specify theprocessor topology on which the program is to be executed, the distribution of the data structures acrossprocessors, and the parallel loops and how the loopsshould be distributed among processors.

The compilerthen analyze the processor topology and the distribution of data, decompose the array into partitions, andthen specify a mapping of arrays to processors.Because Kali is based on making the scientisttrained in FORTRAN feel at home with parallel processing (indeed, a noble goal), it has had to forego thepotential of more powerful data abstractions. Consequently, the only distributed data structure that Kalisupports is the distributed array.

While this maybe sucient for 90% of scientic codes, various distributed structures such as trees, sets, lists and soforth are not constructible in the language. Second,because Kali is a Fortran-like language and it doesnot support inheritance or other object oriented abstractions. Consequently, useful abstractions can notbe inherited and reused in the construction of parallelprograms.In spite of these limitations, we show that the basic2 Previous Models2.1 Concurrent AggregateDally and Chien[2][4] have proposed an objectoriented language, Concurrent Aggregate, that allowsprogrammers to build unserialized hierarchies of abstractions by using aggregates. CA serves a foundation for building distributed data structures in objectbased languages.

An aggregate in CA is a homogeneous collection of objects (called representatives)which are grouped together and may be referenced bya single aggregate name. Messages sent to the aggregate are directed to arbitrary representatives. Therepresentatives of an aggregate can communicate bysending messages to one another.Various distributed data structures such as trees,vectors and so forth can be built from aggregates.For example, a distributed tree can be built by givingeach representative \myparent", \left", and \right"instances.