CP-96-003.ps.gz, gzip compressed PostScript (74K)
| Index | Publications | edac92 | nasecode92 | spe92 | Thesis | Implementing HPF | A HPF implementation framework | A design strategy for instrumentation amplifiers | A generalized Forall |
The forall statement is an important language construct in many (data) parallel languages. It gives an indication to the compiler which computations can be performed independently.
In this abstract, we will define a generalized forall statement and discuss its implementation. This forall statement has the ability to spawn more complex independent activities than can be found in these languages. Existing forall statements can be mapped to this generalized concept. The context of our forall statement is supplied by V-nus, a concise intermediate language for data parallelism. The purpose of V-nus is providing a language platform to which other data parallel languages can be translated, and subsequently optimized.
Our forall statement consists of two parts: an index-space specification specifying the range of the index variable, and a body representing a block of statements. The body is parameterized with respect to, and will be executed for, every index in the index-space specification. Each separate instance of the body is called a body-instance. We use the denotational semantics to define the meaning of the V-nus language constructs. With these we can verify and optimize a forall statement.
It is our target to find a forall statement that complies with the following requirements: (1) The denotational semantics of a forall statement must represent only one possible program state change; that is, only one outcome should be possible after execution of the rol. (2) It must be feasible to implement the forall statement efficiently. This means that the administration that is needed to execute the forall should not use excessive amounts of computational resources. (3) The forall statement must be capable of representing a wide class of forall definitions as can be found in (data) parallel languages. (4) It must be possible to give a concise operational semantics of the forall statement that can easily be used in programming.
Body-instances of the V-nus forall statement are to be executed completely independently. By this we mean that data that can be changed by a body-instance i should not affect the outcome of another body-instance j. However, a global interference is still possible when there is a define-define dependence between the possible body-instances; i.e. two body-instances that write to the same variable. We say that
We use denotational semantics, in which the meaning of a program can be expressed by the composition of the meanings of its parts, to record the concept of the forall statement. Because we do not want to describe the forall as an interleaving of atomic actions, the difference is computed between begin and end state of all body-instances. These differences are merged with the original program state to create the final program state. However, the implementation of the forall statement needs a different approach when efficiency is considered.
At the start of a forall statement the program state ps is preserved. For the execution of a body-instance a subset psi of ps is used for the context in which this body-instance will be executed. Only the data that is needed in the body-instance is extracted from ps and will be used for psi. Every time something needs to be read from memory, it is read from psi. When something needs to be written to memory, it is not only stored in psi, but the same store action is also performed on ps. In this way, each change that is made by a single body-instance is also visible in the global program state, but will not be used by the other body-instances. This is how the final program state ps' arises from the original program state ps, without the need for a merge or a difference operation.
Last modified Friday 23 February 2007 13:45:50 UT by Kees van Reeuwijk.