4.1 Array Operations



next up previous
Next: 4.2 Array Sections Up: 4 Data Parallelism Previous: 4 Data Parallelism

4.1 Array Operations

 

APL was perhaps in many respects the computer language that pioneered the concept of an array as a data object in its own right and not just a cartesian collection of data objects. Operations can be performed on whole arrays, such as

where A, B, and C may all be arrays; for example A, B, and C could all be two dimensional arrays of size 200x300. The meaning of such an operation is C A + B for all 200 values of i and 300 values of j, for a total in this case of 60,000 individual computations involving the array elements. The APL model, therefore, is concurrent element- by-corresponding-element computation for all the elements in the array(s). (Though few implementations of APL capitalized on this conceptual parallelism.)

In addition to supporting all the usual mathematical operations, in a manner analogous to that shown above for addition, APL defined other whole array operations necessary for a reasonably complete paradigm in which arrays are objects in their own right. These include reduction operations (e.g., +/A means sum all the elements of array A), construction operations (e.g., i4 constructs a vector of four elements whose values are 1,2,3,4), and inquiry operations (e.g., if B returns the shape of array B-a vector whose size is the rank of B and whose element values are the corresponding dimension sizes of B-then */B computes the total number of elements in array B). All such operations can be combined into more arbitrarily complex array-valued expressions (e.g., for a one-dimensional array Q, */Q + i*/Q is evaluated right to left (that's APL!) to generate a 1,2,3, vector the size of Q which is added to Q and the resulting elements multiplied together; if Q is the vector (3,2,4), then the value of */Q+i*/Q = */((3,2,4)+(1,2,3))=*/(4,4,7)=56). APL's introduction well before data parallelism became physically practical and when the processing of dynamic languages was inefficient, coupled with (what turned out to be) unpopular characteristics such as arcane notation and unnatural right-to-left evaluation, resulted in it not being used for many practical applications.

The Fortran 90 array operations provide virtually all of the element-by-element data parallel features of APL, without its disadvantages. These operations are provided as natural extensions of scalar operations, functions, and expressions, using familiar Fortran rules for expression evaluation. Reduction, construction, and inquiry operations are provided with the addition of a number of meaningfully-named intrinsic functions. Care was taken to ensure that these operations can be efficiently implemented on contemporary parallel processing systems.

Generally speaking, except in a few contexts in which an expression is restricted to be scalar, any Fortran 90 expression may have array operands and the result is array valued. Fortran 77 allowed only scalar expressions; (almost) all such expressions in Fortran 90 may be data parallel array valued as well. (Scalar expressions are required in control contexts such as IF statement control conditions (scalar logical expression), DO loop indexing expressions, and I/O specifiers such as unit number, file names, open statement specifiers, etc.) Examples of array operations are as follows (any or all of the variables may be arrays):

 C = A+B
 print*, P*Q-R, S
 call T3(X,Q,Z-V)

Note that in these cases the array expressions are indistinguishable from scalar expressions-you need to know from other contexts that these variables have been declared as arrays-but each potentially represents millions of parallel computations. If A, B, C, P, Q, and R are two- dimensional arrays, and Z and V are one-dimensional arrays, these three statements could be written in the following equivalent form which clearly identifies the array operations.

 C(:,:) = A(:,:)+B(:,:)
 print*, P(:,:)*Q(:,:)-R(:,:), S
 call T3(X,Q(:,:),Z(:)-V(:))

Functions may be defined as array valued and hence be operands in array-valued expressions. These are described in section 4.4, along with array-related intrinsic functions.

Thus, element-by-element data-parallel array- valued expressions are a straight forward natural extension/generalization of scalar expressions, with arrays replacing scalars as operands.

Conformability Requirement
The principal requirement in forming an array expression is conformability of the operands. This means that each operand of an array operation must have the same rank and the same number of elements along each dimension-that is, conformable arrays have exactly the same shape. The result of such an operation is, of course, conformable with the operands, and the value of each element of the array result is the scalar computation involving the corresponding elements of the array operands.

Thus if A and B are the following 2x3 arrays:

the result of is

and the result of is

If there is more than one operation in an expression, the (array-valued) result of the first subexpression is an operand for the second operation, and so on. For example, for and as given above, in the expression the result of is added to ; thus the result of is

Note that, for example, a 3x2 array is not conformable with a 2x3 array-they have the same rank and total number of elements, but corresponding dimensions don't have the same size-and thus two such arrays cannot be the operands in the same array operation. The only exception to this basic conformability rule is in the event that one of the operands is a scalar. In this case the scalar is ``broadcast" into an array conformable with the other operand, the value of each element of this broadcast array being that of the scalar. For example, is a valid array operation and (assuming is as given above) the result of is

Common uses of (broadcast) scalars in array operations are to initialize and scale arrays:

This last example illustrates a key aspect of the Fortran 90 array operations: in an array-valued assignment the effect is as if the right-hand side array value is fully evaluated before any assignment takes place. Otherwise it is possible (though not in this simple example) for the right-hand-side array value to be affected before its evaluation is complete. Thus the Fortran 90 conceptual model is that all elements of the right-hand-side array value are computed in parallel (or in any order) before any assignment takes place, and any implementation is allowed that guarantees this behavior.

An example where this rule is important is in the pivoting step in section 4.5. There the pivot row is normalized with the array operation

  G(P,:) = G(P,:)/G(P,K)

This operation uses an array section, G(P,:); array sections are described in section 4.2 below. In this case G(P,:) is the Pth row (pivot row) of matrix G and G(P,K) is the pivot element (K is the pivot column). The normalization scales the row so that the pivot element value is one. Note that if the value of this element is changed to one before the evaluation of the right-hand side is complete, then the row is not properly normalized (this is typical of a common error in sequential programming). Therefore, array operations should not be thought of as ``loops" over the array elements, which implies a sequentially of the operations; in general, thinking of array operations as loops gives incorrect results when assignment is involved. Array operations should be thought of as integral/parallel computations.

Array Constructors
Array values may be explicitly constructed using the array constructor and, if the desired resultant array has dimension higher than one, the RESHAPE intrinsic function; an array constructor forms a one-dimensional array. An array constructor is simply a list of the element values of the result, separated by commas and enclosed in (/ /) delimiters. The above APL 4 example may be written as the Fortran 90 array constructor
        (/1,2,3,4/)

(though there is a more general way of specifying such an ``iota" sequence). Each element in this example is a simple scalar constant. In general, any element in an array constructor can be any scalar expression. If they are all constants, however, then such a constructor (possibly combined with the RESHAPE function - see below) represents an array constant and may appear in a PARAMETER declaration. Array constructors (combined with RESHAPE) are, therefore, the Fortran 90 means of representing array constants.

If each element had to be explicitly listed, the array constructor would not be very practical for specifying very large array values. Therefore two forms for array constructor list items are provided in addition to scalar expressions. These are implied-do constructs and array expressions. The first of these has the form

 (expression-list, index-variable = first-value, last-value[,increment])
The index-variable is a scalar integer variable serving as an iterative index in exactly the same manner as implied-do loops in Fortran 77 I/O statements. One simple application of an implied-do in an array constructor is to generate any iota sequence. For example, the array constructor
     (/(k, k=1,n)/)
generates the vector whose element values are 1,2,3,4,5,n; if n is 4 the result is identical to (/1,2,3,4/). As another example, a vector of a million alternating ones and zeros,
     (/1,0,1,0,1,0,1,$\ldots$/), can be specified with (/ (1,0, j=1,500000) /).

The implied-do simply replicates the list the specified number of times, and if the index-variable is an operand in an expression in the expression-list, each replication of that item uses the corresponding value of the index-variable. The items in the implied-do expression-list may be any of the three forms allowed in the array constructor itself-scalar expressions, implied-do constructs, and array expressions. The two examples above used only simple scalar expressions in the implied-do lists.

An array expression of any dimension may appear in an array constructor. For example, if is a 10001000 array then

     (/A+1.3/)
is an array constructor of one million elements, each having a value of 1.3 more than the corresponding element value of . The elements of 1.3 are placed in the array constructor in the familiar Fortran ``column-major" order, that is column by column by running down the first dimension and then the second. Thus (/ A+1.3 /) is equivalent to
     (/((A(j,k)+1.3,j=1,1000),k=1,1000)/)
Implied-do constructs may be used for a different order. For example, if a row by row vector of elements of 1.3 is desired, rather than column by column, the following array constructor would do the job:
     (/((A(j,k)+1.3,k=1,1000),j=1,1000)/)

Finally, a simple form of the RESHAPE intrinsic function can be used to reshape the (one-dimensional) result of an array constructor into the desired shape. The form that this takes is

RESHAPE (array-constructor, shape-vector)
where the shape-vector has one element for each dimension of the desired array shape, and the value of each shape-vector element is the number of elements in that dimension in the target array. For example, a 10001000 identity matrix of type real can be specified as the constant named Ident_1000 by the declaration
real, parameter :: Ident_1000 =                                              &
                   RESHAPE((/(1.0,(0.0,k=1,1000),j=1,999),1.0/),(/1000,1000/))

Thus the array constructor, coupled with the RESHAPE intrinsic, is an extremely powerful tool for constructing array values, including array constants.

Masked Array Assignment
A ``mask" is an array of type logical. A masked array operation is one in which a mask conformable to the result of the operation is used to specify that only a subset of the parallel element operations are to be performed. This functionality is available in some of the intrinsic functions and for array assignment. In the latter case an array-valued assignment is placed under mask control in a WHERE statement, the general form of which is:
WHERE (mask) array-assignment-statement

The WHERE mask must be conformable with the array on the left of the assignment (which must be conformable with the expression on the right of the assignment). For all those mask elements that have the value .TRUE. the corresponding element assignments take place; where the mask is .FALSE. the assignment is not made. A typical example of the use of masked array assignment is

WHERE (C.gt.0)  A = B/C
which suppresses the division and assignment for those elements of that have value zero (or negative, in this case). By the rules of conformability, arrays , , and are all conformable and the (array-valued) logical expression C.gt.0 is therefore a mask conformable with these arrays. It is often the case that, as in this example, a WHERE mask is the result of a logical expression involving one or more of the assignment operation operands.

Several assignments can be placed under the control of a single mask, in which case the WHERE takes a block form:

WHERE (mask)
     array-assignment-1
     array-assignment-2
     ...
END WHERE
Any number of array assignments can be grouped in this manner; of course, they all have to be conformable with the mask.

The forms of WHERE described above leave unassigned some elements of the array on the left hand side of the assignment statement. An extension of the block form of WHERE, the ELSEWHERE option, allows a value to be given to the left-hand-side array elements where the mask is .FALSE. This takes the form:

WHERE (mask)
     array-assignment-1
     array-assignment-2
     ...
ELSEWHERE
     array-assignment-n+1
     ...
END WHERE
A simple example of this last form of WHERE is
WHERE (C.gt.0)
     H = B/C
ELSEWHERE
     H = B
END WHERE
In this case those elements of for which is less than or equal to zero are simply assigned the corresponding value of . This is an important form of WHERE, because it results in a fully defined array that can be used in subsequent array operations. Without the ELSEWHERE the array H might end up not being fully defined, in which case it cannot be used in other array expressions.

Assumed-Shape Dummy Arguments
One place that Fortran 77 permitted the appearance of an (unsubscripted) array name was as a procedure argument. Given the limited Fortran 77 concept of an array, this was sufficient to be considered as passing the array object to the procedure. However, a Fortran 77 array always occupied a block of contiguous storage, and therefore only the location of this block needed to be passed to the procedure. The procedure could treat this as the location of a (contiguous) array of the same shape, as an array of a different shape, or even as a scalar. This is not sufficient for Fortran 90, where arrays are full-fledged objects, the conformability rules apply, and array objects need not occupy contiguous storage (as is the case with many array sections-see section 4.2).

In Fortran 90, arbitrary array expressions may be used as actual arguments in procedure calls. The called procedure must handle these arguments properly as array-valued objects, which is not always possible if just a single location is passed. Assumed-shape dummy arguments solve this problem. They accommodate the passing of array ``descriptors", which contain descriptive information about the array in addition to its location. This additional information includes the rank (number of dimensions) of the array object being passed, the type and size of each element, the number of elements in each dimension, and the ``stride" in each dimension; the stride represents the spread between elements in a dimension and hence accounts for any departure from contiguity. Thus any array expression can be passed to an assumed-shape dummy argument. (Any array expression can be passed to an ``old fashioned" dummy argument as well, but that might result in expensive behind-the-scenes packing into and unpacking from contiguous temporary storage.)

An assumed-shape dummy argument is declared with a colon for each dimension, as in the following example in which is a scalar, is a two- dimensional assumed-shape array, and is a one-dimensional assumed-shape array.

SUBROUTINE CALC3(T,U,V)
     REAL   T,U(:,:),V(:)
     ...
END  SUBROUTINE CALC3

In a call to CALC3, any two-dimensional array expression (of type real) may be passed to and any one-dimensional array expression may be passed to ; conversely, a two-dimensional real array must be passed to and a one-dimensional real array must be passed to . In effect the colons in the declarations for and instruct CALC3 to accept the descriptor information supplied by the calling program. and then exactly represent the corresponding array objects in the actual argument list and may be used in array operations in the body of CALC3. If CALC3 is an internal procedure in the calling program, or is a module procedure in a module being used by the calling program, the proper association between the assumed-shape dummy arguments and the corresponding actual arguments is transparently accomplished. If CALC3 is an external procedure, however, an interface block for CALC3 must be provided in the calling program so that it knows that assumed-shape dummy arguments are the receivers and therefore efficient descriptors can be passed; otherwise the calling program cannot assume the dummy arguments are assumed-shape and must therefore provide a contiguous actual argument, packing and unpacking the array(s) if necessary. An adequate interface block for CALC3 is:

INTERFACE
   SUBROUTINE CALC3(T,U,V)
        REAL T,U(:,:),V(:)
   END SUBROUTINE CALC3
END INTERFACE



next up previous
Next: 4.2 Array Sections Up: 4 Data Parallelism Previous: 4 Data Parallelism



verena@csep1.phy.ornl.gov