next up previous contents
Next: Syntax of Data Alignment Up: Data Mapping Previous: Data Mapping

Model

 

HPF adds directives to Fortran to allow the user to advise the compiler on the allocation of data objects to processor memories. The model is that there is a two-level mapping of data objects to memory regions, referred to as ``abstract processors.'' Data objects (typically array elements) are first aligned relative to one another; this group of arrays is then distributed onto a rectilinear arrangement of abstract processors. (The implementation then uses the same number, or perhaps some smaller number, of physical processors to implement these abstract processors. This mapping of abstract processors to physical processors is implementation-dependent.)

The following diagram illustrates the model:





The underlying assumptions are that an operation on two or more data objects is likely to be carried out much faster if they all reside in the same processor, and that it may be possible to carry out many such operations concurrently if they can be performed on different processors.

Fortran provides a number of features, notably array syntax, that make it easy for a compiler to determine that many operations may be carried out concurrently. The HPF directives provide a way to inform the compiler of the recommendation that certain data objects should reside in the same processor: if two data objects are mapped (via the two-level mapping of alignment and distribution) to the same abstract processor, it is a strong recommendation to the implementation that they ought to reside in the same physical processor. There is also a provision for recommending that a data object be stored in multiple locations, which may complicate any updating of the object but makes it faster for multiple processors to read the object.

There is a clear separation between directives that serve as specification statements and directives that serve as executable statements (in the sense of the Fortran standards). Specification statements are carried out on entry to a program unit, as if all at once; only then are executable statements carried out. (While it is often convenient to think of specification statements as being handled at compile time, some of them contain specification expressions, which are permitted to depend on run-time quantities such as dummy arguments, and so the values of these expressions may not be available until run time, specifically the very moment that program control enters the scoping unit.)

The basic concept is that every array (indeed, every object) is created with some alignment to an entity, which in turn has some distribution onto some arrangement of abstract processors. If the specification statements contain explicit specification directives specifying the alignment of an array A with respect to another array B, then the distribution of A will be dictated by the distribution of B; otherwise, the distribution of A itself may be specified explicitly. In either case, any such explicit declarative information is used when the array is created.

In the case of an allocatable object, we say that the object is created whenever it is allocated. Specification directives for an allocatable object may appear in the specification-part of a program unit, but take effect each time the object is created, rather than on entry to the scoping unit.

Alignment is considered an attribute (in the Fortran sense) of a data object. If an object A is aligned with an object B, which in turn is already aligned to an object C, this is regarded as an alignment of A with C directly, with B serving only as an intermediary at the time of specification. We say that A is immediately aligned with B but ultimately aligned with C. If an object is not explicitly aligned with another object, we say that it is ultimately aligned with itself. The alignment relationships form a tree with everything ultimately aligned to the object at the root of the tree; however, the tree is always immediately ``collapsed'' so that every object is related directly to the root.

Every object that is the root of an alignment tree has an associated template or index space. Typically, this template has the same rank and size in each dimension as the object associated with it. (The most important exception to this rule is dummy arguments with the INHERIT attribute, described in Section 4.4.2.) We often refer to ``the template for an array,'' which means the template of the object to which the array is ultimately aligned. (When an explicit TEMPLATE (see section 3.7) is used, this may be simply the template to which the array is explicitly aligned.)

The distribution step of the HPF model technically applies to the template of an array, although because of the close relationship noted above we often speak loosely of the distribution of an array. Distribution partitions the template among a set of abstract processors according to a given pattern. The combination of alignment (from arrays to templates) and distribution (from templates to processors) thus determines the relationship of an array to the processors; we refer to this relationship as the mapping of the array. (These remarks also apply to a scalar, which may be regarded as having an index space whose sole position is indicated by an empty list of subscripts.)

Every object is created as if according to some complete set of specification directives; if the program does not include complete specifications for the mapping of some object, the compiler provides defaults. By default an object is not aligned with any other object; it is ultimately aligned with itself. The default distribution is implementation-dependent, but must be expressible as explicit directives for that implementation. Identically declared objects need not be provided with identical default distribution specifications; the compiler may, for example, take into account the contexts in which objects are used in executable code. The programmer may force identically declared objects to have identical distributions by specifying such distributions explicitly. (On the other hand, identically declared processor arrangements are guaranteed to represent ``the same processors arranged the same way.'' This is discussed in more detail in section 3.6.)

Sometimes it is desirable to consider a large index space with which several smaller arrays are to be aligned, but not to declare any array that spans the entire index space. HPF allows one to declare a TEMPLATE, which is like an array whose elements have no content and therefore occupy no storage; it is merely an abstract index space that can be distributed and with which arrays may be aligned.

An object is considered to be explicitly mapped if it appears in an HPF mapping directive within the scoping unit in which it is declared; otherwise it is implicitly mapped. A mapping directive is an ALIGN, or DISTRIBUTE, or INHERIT directive, or any directive that confers an alignment, a distribution, or the INHERIT attribute.

Note that we extend this model in Section 8 to allow dynamic redistribution and remapping of objects.


next up previous contents
Next: Syntax of Data Alignment Up: Data Mapping Previous: Data Mapping