[ HPF Home | Versions | Compilers | Projects | Publications | Applications | Benchmarks | Events | Contact ]

---

Equivalence and Partial Order on the Set of Mappings

The set of mappings of named objects is endowed with a partial order modulo a certain equivalence. Roughly speaking, if and are two mappings, then to say that is a specialization of (i.e., `` is below '' in this ordering) is to say that is partially specified and that is one of the mappings that is consistent with . This notion is used below in Section 4.6, and also in Section 8.8.

Advice to users.Since these conditions are complex to state, it is worth noting that if you always provide explicit interfaces (which, as explained below, is quite easy and generally happens automatically) and if you don't use mapped pointers (an Approved Extension, explained

below in Section 8.8), then you need not read this Section. (End of advice to users.)

The precise definition is as follows.

First, we define a notion of equivalence for dist-format specifications:

1. Using the notation for the phrase ``is equivalent to'',

              BLOCK = BLOCK
             CYCLIC = CYCLIC
                  * = *
           BLOCK(n) = BLOCK(m)  iff m and n have the same value
          CYCLIC(n) = CYCLIC(m)  iff m and n have the same value
             CYCLIC = CYCLIC(1)
     

2. Other than this, no two lexically distinct dist-format specifications are equivalent.

This is an equivalence relation in the usual mathematical sense.

Now we define the partial order on mappings: Let S (``special'') and G (``general'') be two data objects.

The mapping of S is a specialization of the mapping of G if and only if either:

1. G has the INHERIT attribute, or
2. S does not have the INHERIT attribute, and the following constraints all hold:
   1. S is a named object, and
   2. The shapes of the ultimate align targets of S and G are the same, and
   3. Corresponding dimensions of S and G are mapped to corresponding dimensions of their respective ultimate align targets, and corresponding elements of S and G are aligned with corresponding elements of their respective ultimate align targets, and
   4. Either
      1. The ultimate align targets of both S and G are not explicitly distributed, or
      2. The ultimate align targets of both S and G are explicitly distributed. In this case, the distribution directive specified for the ultimate align target of G must satisfy one of the following conditions:
         1. It has no dist-onto-clause, or
         2. It has a dist-onto-clause of ``ONTO *'', or
         3. It has a dist-onto-clause specifying a processor arrangement having the same shape as that explicitly specified in a distribution directive for the ultimate align target of S.

         and must also satisfy one of the following conditions:

         1. It has no dist-format-clause, or
         2. It has a dist-format-clause of ``*'', or
         3. Each dist-format is equivalent (in the sense defined above) to the dist-format in the corresponding position of the dist-format-clause in an explicit distribution directive for the ultimate align target of S.

With this definition,

• Any mapping of a named object is a specialization of itself.
• If , , and are named objects, and if the mapping of is a specialization of the mapping of and the mapping of is a specialization of the mapping of , then the mapping of is a specialization of the mapping of .

That is, the specialization relation, as applied to mappings of named objects, is reflexive and transitive, and it can therefore be applied to produce an equivalence relation on the set of mappings of named objects: two such mappings can be said to be equivalent iff each is a specialization of the other. With this definition, the specialization relation yields a partial ordering on the set of mappings of named objects, modulo equivalence. The INHERIT mapping is the unique maximal element in this partial order.