Subject: More discussion fodder

From: [email-masked]
Date: Tue, 14 Apr 92 10:46:06 -0500

Here's my attempt at bringing out the issues in choosing a FORALL
semantics.  No recommendations yet.  Surveys of potential users and
implementors to follow - hopefully those views won't be too
divergent...

                Parallel Loops Position Paper
               Chuck Koelbel, Rice University
			   
The purpose of this paper is to identify the major issues in
defining a parallel loop for High Performance Fortran. Here,
we are only considering the possible semantics of single-
and multi-statement parallel loops with no explicit
synchronization or processor control. Those features will be
discussed after the more basic issues in this document are
settled.

The remainder of this document is organized as follows.
First, a discussion of the underlying tradeoffs in defining
parallel loops is given. Using this discussion, four styles
of parallel loops are listed which may be acceptable to both
users and implementors. This is followed by a discussion of
the possible semantics of multi-statement loops. A survey of
user views on these features will be added in later
additions to this document.

1.   Tradeoffs in Parallel Loops

1.1. Assertions vs. Commands

"Parallel loops" are used in two distinct ways in current
programming languages and compilers.

Some systems treat a parallel loop as an assertion that the
iterations of the loop may safely be executed in any order
(particularly in parallel). The compiler may then take
advantage of this additional information in optimizing the
program. Cray compiler directives fall into this class. This
mode of use can enable large amounts of optimization; on the
other hand, since such assertions are often unchecked they
can create subtle bugs if they are false.

Other systems treat parallel loops as commands to execute
the iterations of the loop in parallel. If there are data
dependences in the loop that make this unsafe, they are
either given an exact semantics that can be executed in
parallel (as in the CM Fortran FORALL loop) or explicitly
left undefined (as in the PCF DOALL). The advantage of such
loops is that parallel execution is ensured; a disadvantage
is that finding a portable parallel semantics may be
difficult.

Because there is substantial existing practice with both
styles of loops, the choice of which style to use in HPFF is
not clear. A substantial part of the user poll below is
devoted to this topic. It is possible, and indeed likely,
that HPFF will want to support both loop styles.

1.2. Expressiveness vs. Implementation

As with many areas of language design, there is a tradeoff
between generality of expression and feasibility of
implementation.

At one end of the spectrum are parallel loops with precise
semantics for very general loop bodies. These constructs
have the advantage that the meaning of the statement is
always well-defined. The disadvantage is that compiler
implementation is very difficult because of the generality
needed; this is particularly a difficulty when portability
is a requirement.

Near the middle of the spectrum are parallel loops with
exact semantics for a more restricted class of loop bodies.
For example, the CM Fortran FORALL is well-defined for most
assignments, but disallows subroutine calls. An important
distinction that can be drawn is when the restrictions can
be checked: at compile time, at run time, or not at all.
Continuing with the CM Fortran example, the absence of CALL
statements can be checked by the compiler The advantage of
these constructs is that the right set of restrictions can
provide a convenient interface for the programmer and a
manageable task for the compiler writer. The disadvantage is
that finding the right trade-off between these options may
be difficult, particularly when considering portability.
At the far end of the spectrum are semantics which provide
an exact meaning for a restricted set of cases, and
explicitly leave the results in other cases undefined. For
example, the results of a CM Fortran loop with an indirect
assignment are well-defined if and only if the indirection
vector is one-to-one. As above, a distinction can be drawn
according to when the restrictions can be checked. In the
indirection example, the restriction can only be checked
while the program is running. The advantages and
disadvantages of this approach are much the same as the last
approach.

It is most likely that HPFF will adopt some sort of
compromise position. The important variables to be decided
are where the dividing lines are drawn between what is
allowed and what is not.

1.3. Loop Semantics

Orthogonal to the above question of expressibility is the
question of what semantics a parallel loop should use in
cases where it is defined. At the very restrictive end of
the spectrum, this is often not an issue because few
difficult cases remain to be defined. Most other positions,
however, admit a variety of reasonable interpretations for
the parallel loop semantics. For example, consider the case
where multiple iterations assign to the same array element.
Some choices for this case are: generate a run-time error,
use the value from the lexically last iteration to make the
assignment, and select a value arbitrarily from among the
iterations making the assignment. Questions such as this are
perhaps most prominent in multiple-statement parallel loops.
A later section will examine possible semantics for those
loops in detail.

2.   Styles of Parallel Loops

2.1. Assertions

A popular form of parallel loops is the simple assertion
that it is safe to execute all iterations in parallel.
"Safe" may be defined differently for different purposes.
The most common meaning is that no data item is assigned in
one iteration and used in another, that is, there is no loop-
carried data dependence. Another possible meaning is that
the computed results will be equivalent regardless of the
order of execution (for example, because the operations in
the loop are associative and commutative). Yet another is
that any result that could be produced by reordering loop
iterations is acceptable to the result's consumer (for
example, a search loop for any instance of a value).
Assertions are popular because, as simple statements of
fact, they are more portable than new statement semantics.
They may also be used for different purposes by different
machines; a compiler for a parallel machine may use a "no
dependence" directive for parallelization, while a
vectorizing compiler could produce vector instructions and a
scalar compiler might use it to optimize cache behavior. A
disadvantage of assertions is that programmers may not know
what assertion will produce good results. For example, the
assertion that a loop does not carry any data dependences is
irrelevant if poor performance is caused by excessive
communication.

An important aspect of assertions is how (or even if) they
can be checked. Assertions that can be efficiently checked
are advantageous because they are safer; their disadvantage
is that the checking itself may overcome any advantage from
using the assertion.

2.1.1.    Checked Assertions
  
In theory, assertions could be checked at compile time or at
run time We discuss both possibilities here. In practice, a
system will usually provide a means to turn assertion
testing off. We are not concerned with that matter here; we
are interested in classifying the types of assertions that
can be checked.

Compile-time checking is seldom used, because if the
compiler can do the checking then the assertion does not
provide new information. It has some uses for checking the
correctness of code written for other compilers, however. An
example of this might be an assertion that a loop does not
carry data dependences; a powerful compiler might attempt to
check such assertions, producing a warning if it found a
provable error.

Run-time checking is the most popular option. In this case,
the compiler inserts code to test the truth of an assertion.
Depending on the system, failure of the test either causes
an error or branches to less optimized code. Some conditions
may be testable, but only at a prohibitive cost (for
example, checking if an array is a permutation). Examples of
assertions that can be checked at run time are statements
regarding the values of variables.

2.1.2.    Unchecked Assertions

Some assertions are simply undecidable, and thus cannot be
checked in general (although methods for special cases may
be useful). In these cases, the compiler has little choice
but to believe the programmer and act accordingly. An
example of this type of assertion would be the claim that
any solution found by a (indeterminate) search could be
used.

As mentioned above, programmers may want the ability to turn
off assertion checking, even when the checking is feasible.
This is certainly an easy feature to build into the
compiler, but it may encourage sloppy coding.

2.2. Commands

The other major form of parallel loops is the command form.
In this style, a parallel loop is a special statement that
is guaranteed to execute in parallel, just as an IF
statement is guaranteed to perform a test and branch. There
are a number of possible semantics for the complex cases
that can arise in these loops; we will discuss these in the
next section. Here, we concentrate on a different aspect of
parallel command loops, the expressiveness of the loops.
Regardless of the exact semantics of the parallel loop,
there is a range of choices available for what constructs
are allowed in them. For the purposes of this discussion, we
group this range into two divisions, strict and nonstrict
commands.

Commands are a popular form because they give the programmer
fairly direct control over what will be executed in
parallel. This control can be improved even more by
additional constructs like the ON clause. The disadvantages
of this approach are possible implementation complexity,
when the detailed semantics do not match the actual machine
well, and possible programmer confusion stemming from the
difference between parallel and sequential semantics.

2.2.1.    Strict Commands

Strict commands limit the possible bodies of parallel loops
to operations that are unambiguous and relatively easily
implemented. Loops which do not conform to these
restrictions are not legal. For example, CM Fortran FORALL
loops cannot contain subroutine calls. These restrictions,
like the assertions above, may be checked at compile time or
run time, or may be unchecked. Earlier checking generally
allows more efficient safe code to be generated. Care must
be take when defining the set of restrictions to retain
enough expressiveness and to allow efficient implementation.

2.2.2.    Nonstrict Commands

Nonstrict commands allow more freedom in the bodies of
parallel loops, at the price of more complex semantics or
implementations. For example, the Myrias PARDO statement
allowed arbitrary statements within the loop body, governed
by a nondeterministic merging semantics. Another example is
the Fortran D FORALL, which provides a deterministic merging
semantics in the same situation that may be very difficult
to implement.

3.   Semantics of Parallel Loops

3.1. Basic Semantic Principles

This section will describe semantics for nonstrict command
parallel loops. These are the style of loop requiring the
most detailed semantics; strict loops can avoid many of
these complexities by simply disallowing any constructs that
might cause problems in the loop bodies. This section also
assumes mult-statement loops, again because it is the most
general case. We begin by describing the cases that must be
resolved for a full semantics. We will then describe several
methods of resolving these conflicts which are already in
use in other languages.

3.1.1.    Loop-carried Data Dependences

A loop-carried data dependence exists when one iteration
assigns to a memory location that is read by another
iteration. This situation is also called a read-write race
condition in the literature. Sequential semantics in this
situation require that the iterations involved be executed
serially. Parallel semantics can be obtained by leaving the
results of the read undefined, or by forcing the read value
to come from a safe (uncorrupted) copy.

3.1.2.    Loop-carried Output Dependences

This case is similar to the last, except that both
iterations are writing to the same memory location. It is
also referred to as a write-write race condition. Sequential
semantics require that the iterations execute in order.
Parallel semantics can be obtained by leaving the final
value of the location undefined, or by postulating a
parallel merging rule.

A special case that involves loop-carried data and output
dependences is accumulation operations. If the reads and
writes involved in the dependences are performing a series
of commutative and associative operations, such as summing
the elements of an array, then special parallel methods can
be applied. Allowing this type of parallelism may, however,
require a special semantics (possibly in conjunction with
new syntax).

3.1.3.    Other Problems

Multi-statement loops have the semantic problems described
above, but it may also be desirable to have different
resolution rules depending on whether the dependence
involves the same statement in both iterations or different
statements. Similarly, when nested statements are allowed,
it is not always clear what the semantics should be. There
are also interesting issues involving loop-independent
dependences (similar to loop-carried dependences, but
involving statements in the same loop iteration) in multi-
statement loops.

3.2. SIMD Semantics

Perhaps the simplest parallel semantics is SIMD semantics.
The basic rule of this semantics is that all values on the
right-hand side of an assignment are evaluated before any
values are stored into the left-hand side locations.
Statements in multi-statement loops are usually considered
separately, so values stored in one statement are used by
the next one (regardless of the iterations doing the reading
and storing of a particular location). Similarly, statements
within nested constructs are considered separately, with
some iterations masked out during branches they would not
follow. Reductions and output dependences are typically not
allowed, although there is no obvious difficulty with adding
them as special SIMD merge operations.

In terms of the model described above, SIMD semantics can be
described as
     1. Loop-carried data dependences within the same
     statement are resolved by performing all read
     operations first.
     2. Loop-carried output dependences within the same
     statement are left undefined.
     3. All other dependences are resolved by executing
     the statements sequentially, using the above
     rules.

3.3. Copy-in Copy-out Semantics

A semantics similar to the above is Copy-in, Copy-out
semantics. Here, all iterations operate on a conceptually
separate copy of the original memory. Values written by one
iteration are only visible to its own copy of the data
space; thus, the new values will be used by later statements
in the same iteration but not by statements in other
iterations. A deterministic merge operation combines the
values written by individual iterations at the end of the
loop. This merge performs accumulations on explicit REDUCE
operators, and chooses the lexically last iteration as the
controlling value in any other case.

In terms of the above model, Copy-in, Copy-out semantics can
be described as
     1. Loop-carried data dependences are resolved by
     always using the value on entry to the loop or a
     value assigned in the same iteration as the read.
     2. Loop-carried output dependences are resolved by
     a deterministic merge.
     3. Loop-independent dependences are resolved by
     sequential semantics within an iteration.

3.4. Dataflow Semantics

A more radical semantics are dataflow semantics. In this
case, the key rule is the single-assignment rule -- any
value will be assigned once and only once. In parallel
loops, this means that all right-hand side references take
their values from those in force before the loop began,
regardless of any assignments made within the loop itself.
Some provision, such as a new syntax, is usually provided
for reductions. Thus,
     1. Data dependences, whether loop-carried or loop-
     independent, are resolved by always using the
     value on entry to the loop.
     2. Output dependences of any kind are not allowed.

3.5. Undefined or Partially Defined

The final possible semantics is to leave the results of loop-
carried dependences only partially defined. The PCF DOALL,
for example, does not allow the programmer to make any
assumptions about values involved in loop-carried
dependences unless explicit synchronization is used.
Projects in distributed systems often guarantee some well-
defined style of serializability. This means that the
results are equivalent to some valid sequential ordering of
the memory accesses, but there may be many possible orders
to choose from. In general, these semantics provide a set of
possible resolutions to loop-carried dependences, but may
not provide a unique answer.