J3/04-134

Date:    16 Dec. 2003
To:      J3
From:    Dan Nagle
Subject: Better Description of Memory- Permutation Arrays


Processor speeds have increased to very much faster rates
than memory speeds, compilers have improved to the point
where most code sequences are nearly perfectly optimized.
Separate compilation confounds "application compilers",
pointers and targets complicate aliasing analysis.
Therefore, more information regarding aliasing is essential
for very high computational rates.  The "Better Description
of Memory" features attempt to define features which may
provide this missing information to compilers.  Since several
features combine to do so, they are broken into individual
papers for consideration.

Title: Better Description of Memory- Permutation Arrays

Submitted By: J3

Status: For Consideration

References:

Basic Functionality: Allow a declaration that an array vector index
                     is a permutation of the extent, thereby preserving
                     the array's contiguity and ensuring that no elements
                     are repeated.

Rationale:  An array with a vector index is not as useful as an array
            with a triplet index, due to the possibility of missing
            or repeated elements.  If a means can be defined to overcome
            this drawback, vector indices become more useful, and
            compilers will have less need to copy arrays.

Estimated Impact:  Compilers must recognize a new keywork, and
                   carry that information to new code, and generate
                   instructions for the new situation.

Detailed Specification: PERMTUATION Attribute of Arrays

                        Consider:

                        real, dimension( N) :: A
                        integer, dimension( N) :: IDX

                        A = ...
                        IDX = ...
                        ...  A( IDX) ...

                        Here, a copy is forced no matter how A is used.
                        If the compiler has no knowledge of IDX (as is
                        very likely the case), a very inefficient copy
                        will be done.

                        Therefore, add the concept of a permutation index,
                        and declare it with a PERMUTATION keyword:

                        real, dimension( N) :: A
                        integer, permutation, dimension( N) :: IDX

                        A permutation index is a rank-1 integer array
                        whose elements are defined to be LBOUND ... UBOUND.

                        Assignment to permutation index arrays is only via
                        a swap statement between elements of the same array:

                        SWAP( IDX( I), IDX( J))

                        (Note that the degenerate case I == J need not
                        be checked, it's just a no-op.)

                        Therefore, by construction, IDX always holds
                        all and only one value of LBOUND ... UBOUND.

                        An alternative spelling might be:

                        integer, permutation( LB: UB) :: IDX

History: