CONTENTS

1 HPSPMD PROGRAMMING MODEL AND ITS JAVA LANGUAGE

BINDING 1

Guansong Zhang, Bryan Carpenter, Geoffrey Fox Xinying Li and Yuhong Wen

1.1 Introduction 1 1.2 Java language Binding 2

1.2.1 Basic concepts 3 1.2.2 Global variables 5 1.2.3 Program execution control 9 1.2.4 Communication library functions 10

1.3 Programming examples 10 1.4 Java packages for HPspmd programming 11 1.5 Issues in the language design 14

1.5.1 Extending the Java language 14 1.5.2 Why not HPF? 15 1.5.3 Datatypes in HPJava 16 1.5.4 Programming convenience 17

1.6 Project in progress 17 1.7 Summary 19 1.8 Bibliography 20 ii

Chapter 1

HPSPMD PROGRAMMING MODEL AND ITS JAVA LANGUAGE BINDING

Guansong Zhang, Bryan Carpenter, Geoffrey Fox Xinying Li and Yuhong Wen

NPAC at Syracuse University

Syracuse, NY, 13244

{zgs,dbc,gcf,xli,wen}@npac.syr.edu

Abstract This chapter introduces a new language, HPJava, for parallel programming on message passing systems, including workstation clusters. The language provides a high level SPMD programming model, called HPspmd. Through examples and performance results, the features of the new programming style, and its implementation, are illustrated.

Keywords: Java, data parallel programming, SPMD

1.1 Introduction

In this chapter, we introduce HPJava language, a programming language extended from Java for parallel programming on message passing systems, from multiprocessor systems to workstation clusters.

Although it has a close relationship with HPF[4], the design of HPJava does not follow HPF directly. Instead it introduces a high level structured SPMD programming style, HPspmd, which can be summarized as follows:

• Structured SPMD programming. Programs written in the programming language presented here explicitly coordinate a well-organized process group. As in a conventional distributed-memory SPMD program, only a process owning a data item is allowed to access the item directly. The language provides special constructs that allow programmers to meet this constraint conveniently.

• Global name space. Besides the normal local variables of the sequential base language, the language provides classes of variables accompanied by nontrivial data descriptors, providing a global name space in the form of globally subscripted arrays, with assorted distributed patterns. This helps to relieve programmers of error-prone activities such as the local-to-global, global-to-local address translations which occur in data parallel applications.

• Hybrid of data and task parallel programming. The language also provides special constructs to facilitate both data parallel and task parallel programming. Through language constructs, different processors can either simultaneously work on global addressed data, or independently execute complex procedures on their own local data. The conversion between these phases is seamless.

• Communication libraries. In the traditional SPMD model, the language itself does not provide implicit data movement semantics. Different communication patterns are implemented as library functions. This greatly simplifies the task of the compiler, and should encourage programmers to use algorithms that exploit locality. Data on remote processors are accessed exclusively through explicit library calls. In particular, the initial HPJava implementation relies on a library of powerful collective communication routines. Other distributed-array oriented communication libraries may be bound to the language later. The low level MPI communication is always available as a fall-back. Since the language itself only provides basic concepts to organize data arrays and process groups, it allows the possibility that when a new communication pattern is needed, it should be relatively easy to integrate through new libraries.

In our earlier work on HPF compilation [10] the role of runtime support was emphasized. Difficulties in compiling HPF efficiently suggested to make the runtime communication library directly visible in the programming model. Since Java language is simple, elegant language, we implemented our prototype based upon this language.

1.2 Java language Binding

String is a class in Java, but there is language syntax, including construction and concatenation operations, to support it. In HPJava, we add several similar built-in classes.

1.2.1 Basic concepts

Key concepts in the programming model are built around process groups, used to describe program execution control in a parallel program.

The first category of concepts is process group. Group is a class representing a process group, typically with a grid structure and an associated set of process dimensions. It has its subclasses that represent different grid dimensionalities, such as Procs1, Procs2, etc. For example,

Procs2 p = new Procs2(2,4);

An HPJava program will be executed in parallel across the processes of a grid. The second category of concepts is distributed dimension. The elements of an

ordinary array can be represented by an array name and an integer sequence. Here, we have two concepts reflected by int values: an index to access each array element and a range that index can be chosen from. In describing a distributed array, we use two new built-in classes in HPJava to represent the analogous concepts:

• A range maps an integer interval into a process dimension according to certain distribution format. Ranges describe the extent and mapping of array dimensions.

• A location, or slot, is an abstract element of a range. A range can be regarded as a set of locations, actually it is a one-to-one mapping between the global index and locations.

For example,

Range x = new BlockRange(100, p.dim(0)) ;
Range y = new CyclicRange(200, p.dim(1)) ;

creates two ranges on the different process dimensions of the group p. One is block distributed, the other is cyclic distributed. There are 100 different Location items mapped by the range x from integers, for example, the first one is

Location i = x[0];

In addition, we have the concepts of subgroup and subrange. A subgroup is some slice of a process array, formed by restricting the process coordinates in one or more dimensions to single values.

Suppose i is a location in a range distributed over a dimension of group p. The expression

p / i

represents a smaller group—the slice of p to which location i is mapped.

Similarly, a subrange is a section of a range, parameterized by a global index triplet. Logically, it represents a subset of the locations of the original range.

The syntax for a subrange expression is

x [ 1 : 49 ]

The symbol “:” is a special separator. It is used to compose a triplet with optional int expressions to represent an integer subset. The default initial and final values are respectively zero and the extent of the range. The default stride size is 1.

When a process group is defined, a set of ranges and locations are also implicitly defined, as shown in figure 1.1.

Figure 1.1. Structured processes group

The two (primitive) ranges associated with dimensions of the group p are,

Range u=p.dim(0);
Range v=p.dim(1);

dim() is a member function that returns a range reference, directly representing a processor dimension.

We can obtain a location in range v, and use it to create a new group,

Location j = v[1];
Group q = p/j;

As shown in the figure, group p is highly structured. The notions introduced around it contribute to program execution control in the new programming language.

In a traditional SPMD program, execution control is based on if statements and process id or rank numbers. In the new programming language, switching execution control is based on the structured process group. For example, it is not difficult to guess that the following code:

on(p) {
  ...
}

will restrict the execution control inside the bracket to processes in group p.

The language also provided well-defined constructs to split execution control across processes according to data items we want to access. This will be discussed later.

1.2.2 Global variables

When an SPMD program starts on a group of n processes, there will be n control threads mapped to n physical processors. In each control thread, the program can define variables in the same way as in a sequential program. The variables created in this way are local variables. Their names may be replicated across processes, but they will be accessed individually (their scope is local to a process).

Besides local variables, HPJava allows a program to define global variables, explicitly mapped to a process group. A global variable will be treated by the process group that creating it as a single entity. The language has special syntax for the definition of global data. Global variables are all defined by using the new operator from free storage. When a global variable is created, a data descriptor is also allocated to describe where the data are held.

Data descriptor and global data. The concept of data descriptor is not new. It exists in the Java language itself. For example, the field length in the Java array reflects the fact that an array is accessed through a data descriptor.

On a single processor, an array variable might be parametrized by a simple record containing a memory address and an int value for its length. On a multi-processor, a more complicated structure is needed to describe a distributed array. The data descriptor specifies where the data is created, and how they are distributed. The logical structure of a descriptor is shown in figure 1.2.

Figure 1.2. Descriptor

New syntax is added in HPJava to define data with descriptors.

on(p)
  int # s = new int #;

creates a global scalar on the current executing process group. In the statement, s is a data descriptor handle, in HPJava term, a global scalar reference. The scalar contains an integer value. Global scalar references can be defined for any primitive type (or, in principle, class type) of Java. The symbol # in the right hand side of the assignment indicates a data descriptor is allocated as the scalar is created.

For a scalar variable, a field value is used to access the value.

on(p) {
  int # s = new int #;

  s.value = 100;
}

Figure 1.3 shows a possible memory mapping for this scalar on different processes. Note, the value field of s is identical in each process in the current executing pro-

Figure 1.3. Memory mapping

cesses. Replicated value variables are different from local variables with replicated names. The associated descriptors can be used to ensure the value is maintained identically in each process, throughout program execution.

The group inside a descriptor is called the data owner group, it defines where the global values are held.

on(p)
  int # s = new int # on q;

will set data owner field in the descriptor to group q. In general this may be a subset of the default, p (the whole of the current active process group).

When defining a global array, it is not necessary to allocate a data descriptor for each array element. So the syntax for defining a global array is not derived directly from the one for a scalar. An array can defined with different kinds of ranges introduced earlier. Suppose we still have

Range x = new BlockRange(100, p.dim(0)) ;

and the process group defined in figure 1.1, then

on(q)
  float [[ ]] a = new float [[x]];

will create a global array with range y on group q. Here a is a descriptor handle describing a one-dimensional array of float. It is block distributed on group q^{1}. In HPJava term, a is also called a global or distributed array reference.

A distributed array range can also be collapsed (or sequential). An integer range is specified, eg

1The on clause restrict the data owner group of the array to q. If group p is used instead, the one dimenstion array will be replicated in the first dimenstion of the group, and block distributed over the second dimension.

on(p)
  float [[*]] b = new float [[100]];

When defining an array with collapsed dimensions, * can optionally be added in a type signatures to mark these dimensions.

The typical method of accessing global array elements is not exactly the same as for local array elements, or for global scalar references. Since global arrays may have position information in their dimensions, we often use named-locations as their subscripts:

at(i=x[3])
  a[i]=3;

Here the fourth element of array a is assigned the value 3. We will leave discussion of the at construct to section 1.2.3, and give a simpler example here: if a global array is defined with a collapsed dimension, accessing its elements can be modelled on local arrays. For example:

for(int i=0; i<100; i++)
  b[i]=i;

assigns the loop index to each corresponding element in the array.

When defining a multi-dimensional global array, a single descriptor parametrizes a rectangular array of any dimensions.

Range x = new BlockRange(100, p.dim(0)) ;
Range y = new CyclicRange(100, p.dim(1)) ;
float [[,]] c = new float [[x, y]];

This creates a two-dimension global array with the first dimension block distributed and the second cyclic distributed. Now c is a global array reference. Its elements can be accessed using single brackets with two suitable locations inside.

The global array introduced here is a Fortran-style multi-dimensional array, not a Java-like array-of-arrays. Java-style arrays-of-arrays are still useful. For example, one can define a local array of distributed arrays:

int[] size = {100, 200, 400};
float [[,]] d[] = new float [size.length][[,]] ;
Range x[], y[];
for (int l = 0; l < size.length; l++) {
  const int n = size [l] ;
  x[l] = new BlockRange(n, p.dim(0)) ;
  y[l] = new BlockRange(n, p.dim(1)) ;
  d[l] = new float [[x[l], y[l]]];
}

creates an array shown in figure 1.4.

Figure 1.4. Array of distributed array

Array sections and type signatures. HPJava allows to construct sections of global arrays. The syntax of section subscripting uses double brackets. The subscripts can be scalar (integers or locations) or triplets.

Suppose we still have array a and c defined as above, then, a[[i]], c, c[[i, 1::2]], and c[[i, :]] are all array sections. Here i is a location in the first range of a and c (it could also be an integer in the appropriate interval). Both the expressions c[[i, 1::2]] and c[[i, :]] represent one-dimensional distributed arrays, providing aliases for subsets of the elements in c. The expression a[[i]] contains a single element of a, but the result is a global scalar reference (unlike the expression a[i] which is a simple variable).

global var  array section type
2-dimension c

                                c[[:,:]]       float [[,]]

1-dimension c[[i,:]]

                                c[[i,1::2]]    float [[ ]]
                  scalar(0-dim) c[[i,j]]       float #

Table 1.1. Section expression and type signature

Array section expressions are often used as arguments in function calls^{2}. Table 1.1 shows the type signatures of global data with different dimensions.

Inquiry fields and functions The size of an array in Java can be had from its length field. Similarly, in HPJava, information like data owner group and distributed dimensions can be accessed from the following fields,

Group group;   //data owner group

2When used in method calls, the collapsed dimension array is a subtype of the ordinary one. i.e.

an argument of float[[*,*]], float[[*,]] and float[[,*]] type can all be passed to a dummy of type float[[,]]. The converse is not true.

Range range[]; //dimension array

Further inquiry functions on Range yield values such as extents and distribution formats.

1.2.3 Program execution control

HPJava has all the Java statements for execution control within a single process. It introduces three new control constructs, on, at and overall for execution control across processes. A new concept, the active process group, is introduced. It is the set of processes sharing the current thread of control.

In a traditional SPMD program, switching the active process group is effectively implemented by if statements such as:

if(myid>=0 && myid<4) {
  ...
}

Inside the braces, only processes numbered 0 to 3 share the control thread. In HPJava, this effect is expressed using a Group. When a HPJava program starts, the active process group has a system-defined value. During the execution, the active process group can be changed explicitly through an on construct in the program.

In a shared memory program, accessing the value of a variable is straightforward. In a message passing system, only the process which holds data can read and write the data. We sometimes call this SPMD constraint. A traditional SPMD program respects this constraint by using an idiom like

if(myid==1)
  my_data=3;

The if statement makes sure that only my data on process 1 is assigned to. In the language we present here similar constraints must be respected. Besides

on construct introduced earlier, there is a convenient way to change the active process group to access a required array element, namely at construct. Suppose array a is defined as in the previous section, then:

on (q) {
  Location i=x[1];
  a[i]=3;   //error
  at(j=x[1])
    a[j]=3; //correct
}

The assignment statement guarded by an at construct is correct; the one without it may cause run-time error. Here the at construct introduce a new variable j, with its scope valid only inside the block controled by the at.

A more powerful construct called overall combines switching of the active process group with a loop:

on(q)
  overall(i= x[0:3])
    a[i]=3;

is essentially equivalent to^{3}

on(q)
  for(int n=0;n<4;n++)
    at(i=x[n])
      a[i]=3;

In each iteration, the active process group is changed to q/i. In section 1.3, we will illustrate with further programs how at and overall constructs conveniently allow one to keep the active process group equal to the data owner group for the assigned data.

1.2.4 Communication library functions

When accessing data on another process, HPJava needs explicit communication, as in a ordinary SPMD program. Communication libraries are provided as packages in HPJava. Detailed function specifications will be introduced in other papers. Here we will only introduce a small number of top level collective communication functions.

In the current design, the collective communications are static methods of a class Adlib. Adlib.remap will copy the corresponding element from one to another, regardless of their distribution format. Adlib.shift will shift certain amount in a specific dimension of the array in either cyclic or edge-off mode. Adlib.writeHalo is used to support ghost regions.

It is possible to integrate other communication library as communication packages of the language. We have already implemented a Java MPI interface. Currently CHAOS [3] and GA [7] are being considered as “add-on” packages.

1.3 Programming examples

In this section we only give out example programs to show the new language features.

The first example is Choleski decomposition,

Procs1 p = new Procs1(4);
on(p) {
  Range x = new CyclicRange(n, p.dim(0));
  float a[[*,]] = new float [[n, x]];
  ... some code to initialise `a' ...
  float b[[*]] = new float [[n]]; // buffer

3A compiler can implement overall construct in a more efficient way, using linearized address calculation. For detailed translation scheme on overall construct, please refer to [2]

Section 1.4. Java packages for HPspmd programming  11

for(int k = 0 ; k < N - 1 ; k++) {
  at(l = x[k]) {
    float d =  Math.sqrt(a[k,l]) ;
    a[k,l] = d ;
    for(int s = k + 1 ; s < N ; s++)
      a[s,l] /= d ;
  }
  Adlib.remap(b[[k+1:]], a[[k+1:,  k]]);
  overall(m = x [k + 1 :] )
    for(int i = x.idx(m) ; i < N ; i++)
      a[i,m] -= b[i] * b[x.idx(m)] ;
}
at(l = x [N - 1])
  a[N - 1,l] = Math.sqrt(a[N-1,l]) ;
}

Here, remap is used to broadcast one updated column to each process. idx is a function to get the global index of m inside x.

The second example is Jacobi iteration,

Procs2 p = new Procs2(2, 4);
Range
  x = new BlockRange(100, p.dim(0), 1),
  y = new BlockRange(200, p.dim(1), 1);
on(p) {
float [[,]] a = new int [[x,y]] ;
... some code to initialize `a'
float [[,]] b = new int [[x,y]];
Adlib.writeHalo(a);
overall(i=x)
  overall(j=y)
    b[i,j] = 0.25 * (a[i-1,j] + a[i+1,j] + a[i,j-1] + a[i,j+1]);
overall(i=x)
  overall(j=y)
    a[i,j] = b[i,j];
}

In the above code, there is only one iteration, it is used to demonstrate how to define range reference with halo area, and how to use the writeHalo function.

1.4 Java packages for HPspmd programming

The implementation of the HPJava compiler is based on runtime system. It is actually a source-to-source translator converting an HPJava program to a Java node program, with function calls to the runtime system, called adJava.

The runtime interface consists of several Java packages. The most important one is the HPspmd runtime proper. It includes the classes needed to translate language constructs. Other packages provide communication and some simple I/O functions.

The important classes in the packages include an environment class, distributed array “container classes”, and related classes describing process groups and index ranges.

The environment class SpmdEnv provides functions to initialize and finalize the underlying communication library (currently MPI). Constructors call native functions to prepare the lower level communication package. An important field, apg, defines the group of processes that is cooperating in “loose synchrony” at the current point of execution.

The other classes correspond directly to HPJava built-in classes. The first hierarchy is based on Group. A group, or process group, defines some subset of the processes executing the SPMD program. They can be used either to describe how program variables such as arrays are distributed or replicated across the process pool, or to specify which subset of processes execute a particular code fragment. Important members of adJava Group class include the pair on(), no() used to translate the on construct.

The most common way to create a group object is through the constructor for one of the subclasses representing a process grid. The subclass Procs represents a grid of processes and carries information on process dimensions: in particular an inquiry function dim(r) returns a range object describing the r-th process dimension. Procs is further subclassed by Procs0, Procs1, Procs2, … which provide simpler constructors for fixed dimensionality process grids.

The second hierarchy in the package is based on Range. A range is a map from the integer interval 0, …, n − 1 into some process dimension (ie, some dimension of a process grid). Ranges are used to parametrize distributed arrays and the overall distributed loop.

The most common way to create a range object is to use the constructor for one of the subclasses representing ranges with specific distribution formats. Simple block distribution format is implemented by BlockRange, while CyclicRange and BlockCyclicRange represent other standard distribution formats of HPF. The subclass CollapsedRange represents a sequential (undistributed range). Finally, DimRange represents the range of coordinates of a process dimension itself—just one element is mapped to each process.

The related adJava class Location represents an individual location in a particular distributed range. Important members of the adJava Range class include the function location(i) which returns the ith location in a range and its inverse, idx(l), which returns the global subscript associated with a given location. Important members of the Location class include at() and ta(), used in the implementation of the HPJava that at construct.

Finally, we have the rather complex hierarchy of classes representing distributed arrays. HPJava global arrays declared using [[ ]] are represented by Java objects belonging to classes such as:

   Array1dI, Array1cI,
   Array2ddI, Array2dcI, Array2cdI, Array2ccI,
   ...
   Array1dF, Array1cF,
   Array2ddF, Array2dcF, Array2cdF, Array2ccF,
   ...

Generally speaking the class Arrayndc… T represents n-dimensional distributed array with elements of type T, currently one of I, F, …, meaning int, float, …^{4}. The penultimate part of the class name is a string of n “c”s and “d”s specifying whether each dimension is collapsed or normally distributed. These correlate with presence or absence of an asterisk in slots of the HPJava type signature. The concrete Array... classes implement a series of abstract interfaces. These follow a similar naming convention, but the root of their names is Section rather than Array (so Array2dcI, for example, implements Section2dcI). The hierarchy of Section interfaces is illustrated in figure 1.5.

Figure 1.5. The adJava Section hierarchy

The need to introduce the Section interfaces should be evident from the hierarchy diagram. The type hierarchy of HPJava involves a kind of multiple inheritance. The array type int [[*, *]], for example, is a specialization of both the types int [[*, ]] and int [[, *]]. Java allows “multiple inheritance” only from interfaces, not classes.

Some important members of the Section interfaces includes inquiry functions dat(), which returns an ordinary one dimensional Java array used to store the locally held elements of the distributed array. The member pos(i, ...), which takes n arguments, returns the local offset of the element specified by its list of arguments. Each argument is either a location (if the corresponding dimension is distributed) or an integer (if it is collapsed). These functions are used to implement elemental value access of the global data. The inquiry grp() returns the group over which elements of the array are distributed. The inquiry rng(d) returns the dth range of the array.

4In the inital implementation, the element type is restricted to the Java primitive types.

Another package in adJava is the communication library. The adJava communication package includes classes corresponding to the various collective communication schedules provided in the NPAC PCRC kernel. Most of them provide of a constructor to establish a schedule, and an execute method, which carries out the data movement specified by the schedule. The communication schedules provided in this package are based on the NPAC runtime library. Different communication models may eventually be added through further packages.

The collective communication schedules can be used directly by the programmer or invoked through invoked through certain wrapper functions. A class named Adlib is defined with static members that create and execute communication schedules and perform simple I/O functions. This class includes, for example, the following methods, each implemented by constructing the appropriate schedule and then executing it.

static public void remap(Section dst,Section src)
static public void shift(Section dst,Section src,int shift,int dim,int mode)
static public void copy(Section dst,Section src)
static public void writeHalo(Section src,int[] wlo,int[] whi,int[] mode)

Given these classes, one can program in the HPspmd style in pure java program. The idea of the HPJava compiler is just to translate the HPJava program onto this interface, except it will use rather optimized address caculation instead of those function calls to do elementary access. For detailed translation scheme, please refer to [11].

1.5 Issues in the language design

With some of the implementation mechanisms exposed, we can better discuss the language design itself.

1.5.1 Extending the Java language

The first question to answer is why use Java as a base language? Actually, the programming model embodied in HPJava is largely language independent. It can bound to other languages like C, C++ and Fortran. But Java is a convenient base language, especially for initial experiments, because it provides full objectorientation—convenient for describing complex distributed data—implemented in a relatively simple setting, conducive to implementation of source-to-source translators. It has been noted elsewhere that Java has various features suggesting it could be an attractive language for science and engineering [6].

With Java as base language, an obvious question is whether we can extend the language by simply adding packages, instead of changing the syntax. There are two problems with doing this for data-parallel programming.

Our baseline is HPF, and any package supporting parallel arrays as general as HPF is likely cumbersome to code with. The examples given earlier using the adJava interface illustrate this point. Our runtime system needs an (in principle) infinite series of class names

   Array1dI, Array1cI, Array2ddI, Array2dcI, ...

to express the HPJava types

  int [[]], int [[*]], int [[,]], int [[,*]] ...

as well as the corresponding series for char, float, and so on. To access an element of a distributed array in HPJava, one writes

  a[i] = 3 ;

In the adJava interface, it must be written as,

  a.dat()[a.pos(i)] = 3 ;

This is only for simple subscripting. For passing array section it will become even more complex using the raw class library interface.

The second problems is that a Java program using a package like adJava in a direct, naive way will have very poor performance, because all the local address of the global array are expressed by functions such as pos. An optimization pass is needed to transform offset computation to a more intelligent style. So if a preprocessor must do these optimizations anyway, it makes most sense to design a set of syntax to express the concepts of the programming model more naturally.

1.5.2 Why not HPF?

The design of the HPJava language is strongly influenced by HPF. The language emerged partly out of practices adopted in our efforts to implement an HPF compilation system [10]. For example:

  !HPF$ POCESSOR    P(4)
  !HPF$ TEMPLET     T(100)
  !HPF$ DISTRIBUTE  T(BLOCK) ONTO P
        REAL        A(100,100), B(100)
  !HPF$ ALIGN       A(:,*) WITH T(:)
  !HPF$ ALIGN       B WITH T

have their conterparts in HPJava:

  Procs1 p = new Procs1(4);
  Range x = new BlockRange (100, p.dim(0));
  float [[,*]] a = new float [[x,100]] on p;
  float [[ ]] b = new float [[x]] on p;

Both languages provide a globally addressed name space for data parallel applications. Both of them can specify how data are mapped on to a processor grid. The difference between the two lies in their communication aspects. In HPF, a simple assignment statement may cause data movement. For example, given the above distribution, the assignment

  A(10,10) = B(30)

will cause communication between processor 1 and 2. In HPJava, similar communication must be done through explicit function calls^{5}:

  Adlib.remap(a[[9,9]], b[[29]]);

Experience from compiling the HPF language suggests that, while there are various kinds of algorithms to detect communication automatically, it is often difficult to give the generated node program acceptable performance. In HPF, the need to decide on which processor the computation should be executed further complicates the situation. One may apply “owner computes” or “majority computes” rules to partition computation, but these heuristics are difficult to apply in many situations.

In HPJava, the SPMD programming model is emphasized. The distributed arrays just help the programmer organize data, and simplify global-to-local address translation. The tasks of computation partition and communication are still under control of the programmer. This is certainly an extra onus, and the language is more difficult to program than HPF^{6}; but it helps programmer to understand the performance of the program much better than in HPF, so algorithms exploiting locality and parallelism are encouraged. It also dramatically simplifies the work of the compiler.

Because the communication sector is considered an “add-on” to the basic language, HPJava should interoperate more smoothly than HPF with other successful SPMD libraries, including MPI [5], CHAOS [3], Global Arrays [7], and so on.

1.5.3 Datatypes in HPJava

In a parallel language, it is desirable to have both local variables (like the ones in MPI programming) and global variables (like the ones in HPF programming). The former provide flexibility and are ideal for task parallel programming; the latter are convenient especially for data parallel programming.

In HPJava, variable names are divided into two sets. In general those declared using ordinary Java syntax represent local variables and those declared with [[ ]] represent global variables. The two sectors are independent. In the implementation of HPJava the global variables have special data descriptors associated with them, defining how their components are divided or replicated across processes. The significance of the data descriptor is most obvious when dealing with procedure calls.

5By default Fortran array subscripts starts from 1, while HPJava global subscripts always start from 0.

6The program must meet SPMD constraints, eg, only the owner of an element can access that data. Runtime checking can be added automatically to ensure such conditions are met.

Passing array sections to procedure calls is an important component in the array processing facilities of Fortran90 [1]. The data descriptor of Fortran90 will include stride information for each array dimension. One can assume that HPF needs a much more complex kind of data descriptor to allow passing distributed arrays across procedure boundaries. In either case the descriptor is not visible to the programmer. Java has a more explicit data descriptor concept; its arrays are considered as objects, with, for example, a publicly accessible length field. In HPJava, the data descriptors for global data are similar to those used in HPF, but more explicitly exposed to programmers. Inquiry fields such as group, range have a similar role in global data to the field length in an ordinary Java array.

Keeping two data sectors seems to complicate the language and its syntax. But it provides convenience for both task and data parallel processing. There is no need for things like the LOCAL mechanism in HPF to call a local procedure on the node processor. The descriptors for ordinary Java variables are unchanged in HPJava. On each node processor ordinary Java data will be used as local varables, like in an MPI program.

1.5.4 Programming convenience

The language provides some special syntax for the programmer’s convenience. Unlike the syntax for data declaration, which has fundamental significance in the programming model, these extensions are purely provide syntactic conveniences.

There are a limited number of Java operators overloaded. A group object can be restricted by a location using the / operation, and a sub-range or location can be obtained from a range using the [ ] operator enclosing a triplet expression or an integer, These pieces of syntax can be considered as shorthand for suitable constructors in the corresponding classes. This is comparable to the way Java provides special syntax support for String class constructor.

Another kind of overloading occurs in location shift, which is used to support ghost regions. A shift operator + is defined between a location and an integer. It has be illustrated in the examples in the previous section. This is a restricted operation—it has meaning (and is legal) only in an array subscript expression.

1.6 Project in progress

Projects related to this work include development of MPI, HPF, and other parallel languages such as ZPL[8] and Spar[9]. Here we explain the background and future developments of our own project.

The work originated in our compilation practices for HPF. As described in [10], our compiler emphasize runtime support. Adlib[2], a PCRC runtime kernel library, provides a rich set of collective communication functions. It was realized that by raising the runtime interface to the user level, a rather straightforward (compared to HPF) compiler could be developed to translate the high level language code to a node program calling the runtime functions.

Currently, a Java interface has been implemented on top of the Adlib library. With classes such as Group, Range and Location in the Java interface, one can write Java programs quite similar to HPJava we proposed here. Yet, the program executed in this way will have large overhead due to function calls (such as address translation) when accessing data inside loop constructs.

Given the knowledge of data distribution plus inquiry functions inside runtime library, one can substitute address translation calls with linear operation on the loop variable, and keep most of the inquiry function calls outside the loop.

At present time, we are working on the design and implementation of the prototype of this translator. Further research works will include optimization and safety-checking techniques in the compiler for HPspmd programming.

Figure 1.6 shows a preliminary benchmark for hand translated versions of our examples. The parallel programs are executed on 4 sparc-sun-solaris2.5.1 with mpich MPI and Java JIT compiler in JDK 1.2Beta2. For Jacobi iteration, the timing is for about 90 iterations, the array size is 1024X1024.

Figure 1.6. Preliminary performance

We also compared the sequential Java, C++ and Fortran version of the code, all with -O flag when compiling. The dotted lines shown in the figure only represent times for the one processor case. We can see that on a single processor, Java program use language own mechanism for calculating array element address, it is slower than HPJava, which uses an optimized scheme.

Similar test was made on an 8-node SGI challenge(mips-sgi-irix6.2), the communication time is much smaller than the one on solaris, due to MPI device using shared memory.

1.7 Summary

Through the simple examples in the chapter, we can see the programming language presented here has the flexibility of a SPMD program, and the convenience of HPF. The language encourages programmers to express parallel algorithms in a more explicit way. We suggest it will help programmers to solve real application problems more easily, compared with using communication packages such as MPI directly, and allow the compiler writer to implement the language compiler without the difficulties met in the HPF compilation.

Figure 1.7. Layers of HPspmd model

The overall structure of the system can be shown as figure 1.7, the centered DAD stands for Distributed Array Descriptor, which is introduced previously. Around it, we have different run time libraries. The Java interface is mainly concerned here. Yet the Java binding is only an introduction of the programming style. (A Fortran binding is being developed.) It can be used as a software tool for teaching parallel programming. As Java for scientific computation become more mature, it will be a practical programming language to solve real application problems in parallel and distribute environments.

1.8 Bibliography

[1] Jeanne C. Adams, Walter S. Brainerd, Jeanne T. Martin, Brian T. Smith, and Jerrold L. Wagener. Fortran 90 Handbook. McGraw-Hill, 1992.

[2] Bryan Carpenter, Guansong Zhang, and Yuhong Wen. NPAC PCRC runtime kernel definition. Technical Report CRPC-TR97726, Center for Research on Parallel Computation, 1997. Up-to-date version maintained at http://www.npac.syr.edu/projects/pcrc/doc.

[3] R. Das, M. Uysal, J.H. Salz, and Y.-S. Hwang. Communication optimizations for irregular scientific computations on distributed memory architectures. Journal of Parallel and Distributed Computing, 22(3):462–479, September 1994.

[4] High Performance Fortran Forum. High Performance Fortran language specification, version 2.0, January 1997. http://www.crpc.rice.edu/HPFF/hpf2.

[5] Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. University of Tenessee, Knoxville, TN, June 1995. http://www.mcs.anl.gov/mpi.

[6] Geoffrey C. Fox, editor. ACM 1998 Workshop on Java for High-Performance Network Computing, February 1998. To appear in Concurrency: Practice and Experience.

[7] J. Nieplocha, R.J. Harrison, and R.J. Littlefield. The Global Array: Nonuniform-memory-access programming model for high-performance computers. The Journal of Supercomputing, 10:197–220, 1996.

[8] Lawrence Snyder.  A ZPL programming guide.  Tech-
nical  report,  University  of  Washington,  May  1997.

http://www.cs.washington.edu/research/projects/zpl/.

[9] Kees van Reeuwijk, Arjan J. C. van Gemund, and Henk J. Sips. Spar: A programming language for semi-automatic compilation of parallel programs. Concurrency: Practice and Experience, 9(11):1193–1205, 1997.

[10] Guansong Zhang, Bryan Carpenter, Geoffrey Fox, Xiaoming Li, Xinying Li, and Yuhong Wen. PCRC-based HPF compilation. In 10th International Workshop on Languages and Compilers for Parallel Computing, 1997. To appear in Lecture Notes in Computer Science.

[11] Guansong Zhang, Bryan Carpenter, Geoffrey Fox, Xinying Li, and Yuhong Wen. Considerations in hpjava language design and implementation. In 11th International Workshop on Languages and Compilers for Parallel Computing, 1998. To appear in Lecture Notes in Computer Science.