next up previous contents index
Next: 17.2.4 Model for MIMD-parallelism Up: 17.2 System Overview Previous: 17.2.2 MovieScript as Virtual

17.2.3 Data-Parallel Computing

 

A currently popular approach to portable data-parallel computing is based on the Fortran90 model, which extends the scalar arithmetic of Fortran77 towards the index-free matrix arithmetic. This concept, originally implemented as CM Fortran by TMC on CM-2, is now extended as in Chapter 13 in the form of Fortran90D and High Performance Fortran model towards the MIMD-parallel systems as well.

The Fortran90-based data-parallel model allows us to treat massively parallel machines as superfast mathematical co-processors/accelerators for matrix operations. The details of the parallel hardware architecture and even its existence are transparent to the Fortran programmer. Good programming practice is simply to minimize explicit loops and index manipulations and to maximize the use of matrices and index-free matrix arithmetic, optionally supported by the compiler directives to optimize data decompositions. The resultant product is a metaproblem  programming system having as its core, for synchronous and loosely synchronous problems, an interpreter of High Performance Fortran.

The index-free vector/matrix algebra constructs appear in various languages, starting from the historically first APL model [Brown:88b]. Also, database query languages such as SQL can be viewed as vector models, operating on table components such as rows or columns. In interpreted languages, vector operations are useful also in sequential implementations since they allow reduction of the interpreter overhead. For example, scalar arithmetic in MovieScript is slower by a factor of five or more than the C arithmetic-the C-coded interpreter performs the actual arithmetical operation and additionally a few control and stack manipulation operations. The absolute value of such overhead is similar for scalar and vector operands and hence it becomes relatively negligible with the increasing vector size.

In MovieScript, the numerical computing is implemented in terms of the following types: number, record, and field. MovieScript numbers extend the PostScript model by adding the formatted numbers such as Char, Short, Double, Complex, and so on. The original PostScript arithmetic preserves value (e.g., an integer result is converted to real in case of overflow), whereas the extended formatted arithmetic preserves format as in the C language.

Record is the interpreted abstraction of the C language structure. The MovieScript interface is similar to that for dictionary objects. The memory layout of the record buffer coincides with the C language layout of the corresponding structure. This feature is C compiler-dependent and it is parametrized in the MOVIE Server code in terms of a few typical alignment models, covering all currently popular 32-bit processors.

Field is an n-dimensional array of numbers, records, or object handles. All scalar arithmetic operators are polymorphically extended to the field domain in a way similar to Fortran90. This basic set of field operators is then further expanded to provide vectorial support for domains such as imaging, neural nets, databases,  and so on.

Images are represented as two-dimensional fields of bytes, and the image-processing algorithms can typically be reduced to the appropriate field algebra. Since the interpreter overhead is negligible for large fields, MovieScript offers natural rapid prototyping tools for experimentation with the image-processing algorithms and with other regular computational domains such as PDEs or neural networks.

A table in the relational database can be represented as a one-dimensional field of records, with the record elements used as column labels. Most of the basic SQL commands can be expressed again in terms of the suitably extended field algebra operators.

PostScript syntax provides flexible language tools for manipulating field objects and it facilitates operations such as constructing regions (object-oriented version of sections in Fortran90) or building multi-dimensional fields. The MovieScript field operator creates an instance of the field type. For example,

/image Byte [256 512] field def

creates a image (array of bytes) and

/cube Bit [ 10 { 2 } repeat ] field def

creates a 10-dimensional binary hypercube. Regions are created by the ptr operator. For example,

/p image [ [ 0 2 $ ] [ 1 2 $ ] ] ptr def

creates a ``checkerboard pattern''   pointer p, and

/c image [ [1[ ]1] [1[ ]1] ] ptr def

creates the ``central region'' pointer c containing the original image excluding the one-pixel wide boundaries. Pointers can be moved by the move operator, for example, one can move the central pointer c to the right by one pixel as follows:

/r c [ 1 0 ] move def.

To act with the Laplace  operator on the original image, we construct the right, left, up, and down shifts as above, denoted by r, l, u, d. We store the content of c in the temporary field t and then we perform the following data-parallel arithmetic operation:

t 4 mul [ r l u d ] { sub } forall,

which is equivalent to the set of scalar arithmetic operations - for each pixel in t.

The above examples illustrate the way new components of MovieScript are cooperating with the existing PostScript constructs. For example, we use literal PostScript arrays to define grid pointers and we extend polymorphic PostScript operators such as mul or sub to the field domain. New operators such as ptr are also polymorphic; for example, a two-dimensional region can be pointed to by either a two-element array or a two-component field, and so on. Array objects used as pointers can also be manipulated by appropriate language tools (e.g., they can be generated in the run time, concatenated, superposed, and so on), which provides flexibility in handling more complex matrix operations.

All section operations from the Fortran90 model are supported and appropriately encoded in terms of literal array pointers. Some of the resulting regions, such as rows, columns, scattered or contiguous windows, and so on, are shown in Figure 17.2. Furthermore, there is nothing special about rectangular regions in the Postscript model, which is armed with the vector graphics operators. Hence, the ptr operator can also be polymorphically extended to select arbitrary irregular regions, such as illustrated in Figure 17.2-for example, by allowing the PostScript path as a valid pointer object argument. This is a simple example of the uniform high-level design which crosses the boundaries of matrix algebra and graphics. Another example is provided by allowing the PostScript vector (and hence data-parallel) drawing operators to act on field objects. A diagonal two-dimensional array can then be constructed, for example, by ``drawing'' a diagonal line across the corresponding field ``canvas.''

  
Figure: Some Data-Parallel Pointers in the MovieScript Model, Created by the ptr Operator. Row, column, contiguous, and scattered rectangle correspond to various Fortran90 style sections, here appropriately encoded as grid pointers in terms of literal array objects. Other irregular regions in the figure can be generated by using the corresponding PostScript graphics path objects as arguments of the ptr operator. The n-dim grid pointer is given as an n-element array of 1-dim axis pointers. Axis pointers are given by numbers or arrays. A number pointer selects the corresponding single element along the axis and the 1, 2, or 3-element array selects 1-dim region. If all elements of such an array are numbers, they are interpreted as min, step, and max offset values. If one (central) element is an array itself, the other elements are interpreted as the left/right margins and the array corresponds to the axis interior and is interpreted recursively according to the above rules. Special convenience symbols $ and [ ] stand for ``infinity'' and ``full span.''

Unlike the Fortran90 model where the arithmetic is part of the syntax design, there is nothing special about the arithmetic operators such as mul or add in MovieScript. New, more specialized and/or more complex regular field operators can be smoothly added to the design, extending the index-free arithmetic and supporting computational domains such as signal processing, neural networks, databases, and so on.

The implementation of data-parallel operations in MovieScript is clearly hardware-dependent. The regular, grid-based component of the design is functionally equivalent to Fortran90 and its implementation can directly benefit from the existing or forthcoming parallel Fortran support. Some more specialized operators can in fact be difficult or impractical to implement on particular systems, such as, for example, data-parallel PostScript drawing on some SIMD-parallel processor arrays. In such cases, only the restricted regular subset of the language will be supported. The main strength of the concurrent MOVIE model is in the domain of MIMD-parallel computing discussed below.



next up previous contents index
Next: 17.2.4 Model for MIMD-parallelism Up: 17.2 System Overview Previous: 17.2.2 MovieScript as Virtual



Guy Robinson
Wed Mar 1 10:19:35 EST 1995