An Introduction to MasPar C

MasPar Computer Corporation 749 North Mary Avenue Sunnyvale, CA 94086 (408) 736-3300

April 3, 1996

Abstract

MasPar C (MPC) is a data parallel superset of the ANSI standard C programming language. A generalized concept of parallel data is added to the ANSI C language along with syntactical extensions that support operations on parallel data. Some concepts are also borrowed from C++, including function overloading and call by reference. The language is defined in a parallel architecture independent manner while at the same time keeping potentially expensive inter-processor communication visible to the programmer for performance considerations. The MPC programming environment is enhanced by an accompanying parallel applications library that provides support for common parallel operations.

1 Introduction

There have been a variety of attempts at defining a C language for vector and parallel machines. Some definitions have tried to leave the traditional C language definition[2] unchanged by using vectorizing compiler technology to find implicit parallelism[3]. Other languages have defined new expression syntax to indicate that multiple array elements may be evaluated at once[4].

Although these approaches are potentially useful for monolithic and shared memory machines, the linear memory model which underlies them is incompatible with distributed memory computer architectures. The central problem is that there is little difference between pointers and arrays in C. For example, if the variable foobar is an array, the expression foobar+1 implies pointer arithmetic rather than the addition of the scalar 1 to the array foobar.

MasPar C (MPC)[1] introduces parallel data to the ANSI C programming language by allowing existing C data types to be declared as shaped objects. The concept and application of shaped or parallel objects is explored in subsequent sections.

2 Parallel Objects

The conceptual difference between MPC and C is the introduction of parallel data objects. Distribution of data across a number of processors is supported by introducing the concept of shaped data. Shapes are essentially a purer form of array than exist in standard C. The shape of an object is introduced in the same syntactic position and binding as the ANSI C const and volatile keywords in a declaration.

A fully specified shape is defined by two attributes, namely rank and extents. Shapes are defined in a hierarchy, where the predefined shape named “shape” has neither of these attributes defined. New named shapes are derived from this fundamental base shape as shown in the following example.

     shape:[][]shape2D;

Here a rank two shape is defined where the extent attributes are still left unspecified. Partially specified shapes that lack extent information are useful in writing code that is problem size independent. Another shape can be derived from shape2D with fixed extents as follows.

     shape2D:[100][100]shape2D_100x100;

Alternative, one could specify the shape shape2D 100x100 in a single step by writing the following.

     shape:[100][100]shape2D_100x100;

Mapping and virtualization attributes are also bound to a shape name using special syntax. Mapping and virtualization are critical for performance considerations but are beyond the scope of this introductory treatment of MPC.

The most useful shapes are predefined in the standard MPC include file (mpc.h), each in an assumed extent form. The shapes that are predefined are designed to be particularly appropriate for the 2-D grid topology of the MasPar architecture. For example, shape1d c is a rank one shape and shape2d c is a rank two shape. Both of these have assumed extents so many other similar, but different sized shapes can be derived from of them by specifying extents for the derived shape. An example of shape derivation and shaped variable declaration follows.

     shape1d_c:[1000]shapeA;
     shape2d_c:[1000][1000]shapeB;
     shapeA int a,A;
     shapeB int b,B;

It is convenient to think of each shape as a separate virtual parallel machine. For example think of anything of shapeA from the above example as existing in a 1, 000 processor machine where the processors are laid out along a straight line. There is a single copy of an integer on each of these virtual processors in the case of the shaped objects a and A. Likewise, shapeB parallel objects exist on a 1, 000 × 1, 000 processor virtual machine laid out as a two dimensional grid. Of course in reality, every defined shape utilizes the same collection of physical processors but this conceptual model helps to visualize a shape and will also help later in visualizing communication of data between various shapes.

3 C Operators

Rather than adding new operators to perform parallel versions of standard operations, MPC extends the semantics of existing C operators to operate on shaped objects. For the variable a defined in the previous example as shapeA int a, the expression a++ increments the value of a at every position in shapeA. Other operators (such as +,∗, and <<) are similarly overloaded. Scalar expressions have semantics identical to those of traditional C expressions. In a binary expression, if one of the objects is scalar and the other is shaped, the scalar is promoted to the same shape as the shaped object before the operation. The only exception to this is when a scalar variable is on the left hand side of an assignment and a parallel expression is on the right hand side where this action is defined to be illegal. Additionally, all shaped objects in an expression must have the same shape name to conform.

     shape1d_c:[1000]myShape;
     shape1d_c:[999]myOtherShape
     myShape          int a, b;
     myOtherShape     int c;
                      int i;
     a = a * b;      // A parallel operation.
     a = i;          // i gets promoted to myShape.
     a = b + c       // ILLEGAL! Non-conforming shapes.
     i = b;          // ILLEGAL! Demotion to scalar not allowed.

Note that even if myOtherShape has the same extent as myShape (i.e. the two shapes structurally conform), the expression b+c would still be illegal because shape conformance is done at the name level.

4 Control Flow

The control flow statements of ANSI C are extended such that those positions in a shape that evaluate the controlling expression as true are termed the active set. Only those positions of the shape that are in the active set execute the body of the statement; the other positions do nothing. If no positions of the shape are evaluated as true, the body of the statement is not evaluated. All operations performed must conform to the shape of the current active set or be scalar, unless the current active set is explicitly escaped using an all statement (see example section 8.2).

In the following example, those positions in myShape that evaluate a less than 5 add the value of 10 to their a. The scalar i is also incremented by two if any position of a is less than 5.

     shape2d_c:[100][100]myShape;
     myShape int a;
                 int i;
     if (a < 5) {
          a += 10;
          i += 2;
     }

If no position in myShape evaluates a < 5 as true, then neither a nor i is accessed since the body of the if statement is skipped.

If we add an else clause, only those positions in myShape that evaluate a < 5 as false execute the body of the else. Again, if no positions in myShape evaluate a < 5 as false, then the else block, including any embedded scalar expressions, is not executed. Therefore, both halves of the if/else can be executed, each by a disjoint subset of the positions of the myShape. Semantically, the if block is executed before the else block.

The parallel semantics of the if statement extend to the while statement. The controlling shaped expression is evaluated once for each iteration of the while loop until no position in the current shape evaluates it as true. At each iteration, only the positions of the shape that are active evaluate the controlling expression, and those positions that evaluate it as false are removed from the active set. The active set is therefore monotonically non-increasing. When no positions in the active shape remain active, control skips to the end of the while statement, and the active set is restored to the active set that existed before the controlling expression of the while was evaluated the first time (which may be no active set at all).

For each position of myShape, the following example counts the number bits required to represent the value of a in that position and stores this count in the same position of b. The total number of times the body of the while is executed is counted in the scalar variable i.

shape1d_c:[1000]myShape;
myShape int a, b;
            int i;
b = 0;      // Initialize.
i = 0;
while (a > 0) {
     a >>= 1;
     b++;
     i++;
}

Other control flow statements (such as for, switch, and do) are analogously defined. The combination of adding the concept of shapes and overloading the C operators and control statements is the essence of MPC.

5 Parallel Element Identification

Positions within a shape are specified by the use of left indexing. If, for example, one desires the 57^{th} element of a rank one shape the following syntax is used.

shape1d_c:[10000]myShape;
myShape int data;
     int val57;
val57 = [56]data;

In higher ranked parallel objects, additional left indicies must be used. For example, to access the element in the 25^{th} row and the 37^{th} column in a rank two shape^{1}, the following syntax is used.

shape1d_c:[1000][1000]myShape;
myShape int data;
int val25_37;
val25_37 = [24][36]data;

In general, a lower ranked shape can always be extracted from a higher ranked shape. Extracting single positions from a shape as demonstrated in the previous examples are special cases of this functionality. For example, a row can be extracted from a two dimensional shape as follows.

shape1d_c:[1000]my1DShape;
shape1d_c:[1000][1000]my2DShape;
my1DShape int data1D;

1Naming the rightmost dimension the column here follows the same convention used in ANSI C arrays, however in MPC there is no particular data layout implied for the different dimensions of a shape. This is in contrast to an array where the columns are always stored in contiguous memory.

     my2DShape int data2D;
     data1D = [3][]data2D;

Here the fourth row of data2D is extracted into data1D.

In practice, it is often necessary to uniquely and simultaneously identify each position of a parallel object. This is addressed in MPC by allowing ordering information or indexing to be derived from the appropriate shape name. This is best examined in reference to the following example.

     shape1d_c:[1000]myShape;
     myShape int idx;
             int numPos;
     numPos = myShape.extent;
     idx    = myShape.index;

In this example the extent of myShape is assigned to numPos as the value 1, 000. The shaped variable idx contains the value 0 at position 0, 1 at position 1, and so on up to 999 at position 999. Note the shape position numbering starts at 0 just as in a standard C array. Conceptually, the shape name identifier may be viewed as a structure that contains the attributes of the shape as fields. In higher dimensional shapes, the extent and index fields are referenced as arrays in order to specify for which dimension the requested information should be reported for. Specifically, a shape name may be conceptually viewed as a structure with the following associated fields.

     struct  shapeName {
                 int rank;
                 int extents[rank];
       shapeName int index[rank];
     }

In the current release of MPC, the rank of a shape is limited to seven.

The index attribute of a shape is especially powerful when combined with control flow constructs. In the following example, the 5^{th} row of a two dimensional shape is set to zero.

     shape2d_c:[100][100]myShape;
     myShape int field;
     if (myShape.index[1] == 4)
          field = 0;

It is important to understand that the shape of the quantity myShape.index[1] in the proceeding example is myShape. An index always has the same shape as the shape from which it is derived.

6 Communications

Communication between parallel objects is required to solve most real world problems. In particular, it is worthwhile to consider two very common but different classes of communications distinctly. More specifically, the concepts of general and regular communication arise in very different situations. MPC utilizes variations in the left index syntax introduced in the previous section to express both of these classes of communication.

6.1 General Communication

General communication allows every position in a shape to communicate with any position in another shape (possibly other positions in the same shape) independently. This is expressed in MPC using shaped valued subscripts. The following example demonstrates a communication operation between two different shapes in MPC and provides example data.

     shape1d_c:[4]myShape1;
     shape1d_c:[8]myShape2;
     myShape1 int dataTable;
     myShape2 int values, idx;
     values = [idx]dataTable;

     dataTable 112 57 62 23

idx  1 3 0 2 2 0 3 1
values 57 23 112 62 62 112 23 57

This example might represent a lookup table operation from a table of myShape1 to data extracted to myShape2. Note that to be meaningful, 0 ≤ idx < 4 for all positions in shape2. This represents a typical gather operation.

This flexible communication support between positions of shaped data may also utilize the index mechanism introduced in the previous section. For example, the following code assigns the transpose of a to aTrans by simply interchanging shape dimensions.

     shape2d_c:[1000][1000]myShape;
     myShape a, aTrans;
     aTrans = [myShape.index[0]][myShape.index[1]]a;

6.2 Regular Communication

Regular communication in MPC can be likened to shifting all the positions within a shape in an identical manner, where toroidal wrap around, is used at the boundaries of the shape. This is commonly called a circular shift. The following example illustrates the use, and result, of a simple data shift operation.

     shape1d_c:[8]myShape;
     myShape a, b;
     a = myShape.index;
     b = [<<3]a;

     myShape.index 0 1 2 3 4 5 6 7

a  0 1 2 3 4 5 6 7
b  3 4 5 6 7 0 1 2

Note the new << operator used to express the circular shift operation. It is only allowed in a left index position and the shift amount (3 in the example) can be any scalar expression resulting in an integral data type. The left pointing shift operator (<<) move elements to lower indexed positions with toroidal wrap around, in the specified dimension of a shape. Likewise, the right pointing shift operator (>>) move elements to higher indexed positions also with toroidal wrap around. The shift direction is also affected by the sign of the shift amount. The functionality of the shift operator is similar to the CSHIFT intrinsic in Fortran 90[5].

More than one dimension of a multi-dimensional shape may be shifted at the same time as demonstrated in the following simple rank two example.

     shape1d_c:[4][4]myShape;
     myShape a, b;
     b = [<<1][>>2]a;

a     7 0 9 5 8 5 2 4 2 1 3 2 3 6 1 8  b     1 3 2 2 6 1 8 3 0 9 5 7 5 2 4 8

In the proceeding example, the [0][0] position of the shape is in the top left corner of the data shapes depicted.

It can now be recognized that the various forms of left indexing in MPC are really just a general symbolism for various types of communication within or between shaped objects. In fact, left indexing may be applied to any shaped expression. A left indexed shaped expression is evaluated in the connected-to positions (i.e. the set of positions communicating with the current active set). In the following example, the active set in the if block is those positions that are in the first column of the two dimensional myShape and the active set in the function foo is the connected-to set associated with the current active set, which in the example is the third column of myShape.

     shape2d_c:[100][100] myShape;
     myShape int  a;
     if (myShape.index[0]==0)
          a = [<<2][]foo();

It may be helpful here to write brackets around the call to foo(), that is [<<2][](foo()), and explicitly treat left indexing as a very flexible communications operator. This a more meaningful model than viewing the left index simply as extra array dimensions. Communication is typically the most important performance consideration when programming any parallel machine and left indexing makes this consideration visible to the programmer. In most cases regular communication should be viewed as less expensive than the shaped valued subscript syntax presented under the heading of general communication. It should also be noted that the shape of the return value of foo() in the proceeding example must be of shape myShape and this will be discussed in greater detail later.

7 Pointer and Derived Data Types

Shapes may also be applied to structures, arrays, and pointers. Since the shape specifier is syntactically like const and volatile, a pointer may itself be shaped and/or point to shaped data. The following examples demonstrate the four different types of pointers possible.

     shape1d_c:[1000] myShape;

             int *a;           // Scalar pointer to scalar data.
     myShape int *b;           // Scalar pointer to shaped data.
     local   int * myShape c;  // Shaped pointer to shaped data.
             int * myShape d;  // Shaped pointer to scalar data.

In the case of shaped pointers, each position in the shape contains a potentially different address into either its own local memory (as in variable c) or in scalar memory (as in variable d). Thus, dereferencing a shaped pointer or a pointer to shaped data yields a value having the same shape as the pointer.

A shaped array allocates the same amount of memory at each position in the shape. In the following example, the first element of B at each position of shapeB is set to 1. Then each position in shapeB stores the value 99 into its own B array at the location specified by its own value of b.

     shape1d_c:[1000] shapeB;
     shapeB int b,B[10];
     b = (shapeB.index) % 10;
     B[0] = 1;
     B[b] = 99;

It follows that the address of a shaped index into a shaped array is a shaped pointer to shaped data as in the following example.

     shape1d_c:[1000] shapeB;
     shapeB int b,B[10];
     local  int * shapeB ptr;
     b   = (shapeB.index) % 10;
     ptr = &B[b];

8 Functions

Three different categories of functions are available in the MPC language. These include scalar, shaped, and elemental functions. Each of these are now examined in more detail.

8.1 Scalar functions

Scalar functions are allowed to be called under any current active set and return only scalar results. Computation can be performed on different shaped objects within the function as long as there is no active set defined at the call site. If an active set is defined at the call site, all shaped expressions in the function must conform to the shape of the active set, unless the active set is explicitly escaped using the all statement (see example section 8.2). Normal ANSI C functions are a special case in this category including the main() function.

8.2 Shaped functions

Shaped functions return an object having a specific shape. They are entered with the active set of the caller which, must be the same shape as that of the function return. A shaped routine may be called when no active set is defined and in this case all positions in the shape of the function are considered to be active. All computation in the function must be carried out in expressions having the shape of the function (or scalar) unless that shape is explicitly escaped using the all statement. The following example demonstrates a shaped function that does some computation in the context of a second shape.

     shape1d_c:[1000] shapeA;
     shape1d_c:[100] shapeB;
     shapeA int foo(shapeA int a, shapeB int *b)
     {
          all { *b = shapeB.index; }
          a = [shapeA.index % shapeB.extent]*b;
     }

Here, only active positions in shapeA (set at the calling site) alter their copy of a in foo() yet all positions in b are written to. The all keyword can always be used to escape the current active set (and hence any current shape context).

8.3 Elemental functions

Elemental functions can be written that operate on any shaped data (including scalar) as long as there is no communication and only one shape is used in the routine. The current active set is honored in elemental functions. Excellent applications of this capability include library functions such as standard math functions like sqrt(). By writing the function as an elemental it needs only be written once. To specify an elemental function, simply add the keyword elemental in front of the function prototype, as demonstrated in the following example.

     elemental int sqr(float a) {
          return(a*a);
     }

Note that the rest of the function beyond the keyword elemental looks like standard ANSI C. This single function can now be called with an argument of any shape, including scalars. Elementals may not modify global scalar variables and may not make calls to non-elemental functions.

9 Other MPC Features

Several other features exist in the MPC language that are worth noting. Function overloading from C++ has been provided to reduce the name space required to express the same operation on different shapes. Also from C++ is a call by reference capability and the new operation to dynamically allocate shaped data. Machine sized shapes called physical are also predefined for performance tuning code in MPC. MPL syntax is also available from the MPC language on objects having the predefined shape plural.

10 Libraries

MPC is supplied with a powerful set of parallel library functions that provide standard C functionality on both scalar and shaped data. Various specific shift oriented communication operations are defined along with general communication operations, sorts, ranks, scans, enumerations, data movement between shaped and scalar variables, and shaped data remapping. Extensive image processing and math solvers are also available for use from MPC.

11 Closing Remarks

MPC is an attempt to define a parallel computer architecture independent language by extending the syntax of the ANSI C language. In order to provide a language that properly addresses the major performance issue of parallel programming, communication is kept visible to the programmer. Other performance critical aspects of parallel programming like data virtualization are provided in a simplified form to the programmer through the concept of shaped data. It is hoped that MPC will be a useful compromise somewhere between a language that distances parallel hardware from the programmer (most often resulting in low efficiency), and one that is closer to machine coding (most often resulting in low programmer productivity). This is of course the same spirit that defined C as a language for scalar hardware.

References

[1] Dave Alpern, MasPar C Language Specification, Draft of May 6, 1992.

[2] American National Standard Institute technical subcommittee X3J11. American National Standard for Information Systems - Programming Language - C, Document Number ANSI X3.159-1989, 1430 Broadway, New York, NY 10018, 1990.

[3] Cray C Reference Manual, Cray Research Corp.

[4] Hoffman, Marc M., DSP C. NCEG 90-033, 1990.

[5] Metcalf M. and Reid J., Fortran 90 Explained, Oxford Science Publications, 1990.

[6] MasPar computer Corporation, MasPar C Library Specification, March 9, 1993.

[7] Jonathan D. Becher and Kenneth M. Hansen, MPL: A Data Parallel C, The Sixth international Parallel Processing Symposium, Beverly Hills, CA, March 23-26, 1992.

[8] Thinking Machines Corporation, C* Programming Guide, Version 6.0 Pre-Beta, July 1990.

[9] Wavetracer Inc., The multiC Programming Language, Document Part Number: PUB-00003-001-1.00, October 10, 1991.