Efficient array descriptors for variable-sized, dynamically...

Details Efficient array descriptors for variable-sized, dynamically... Efficient array descriptors for variable-sized, dynamically...

1999-02-01

2002-04-02

Dam, Tuan Q. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000, C717S152000

Reexamination Certificate

active

06367069

ABSTRACT:

COPYRIGHT NOTICE PURSUANT TO 37 C.F.R. § 1.71(E)
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND
The present invention relates to compilers and programming languages for computer systems. More particularly, the present invention relates to a method and apparatus for efficiently accessing variable-sized, dynamically allocated arrays.
Certain programming languages, such as the FORTRAN programming language, facilitate operations on variable-sized dynamically allocated arrays. In order to manipulate such arrays, these programming languages maintain certain information. This information includes static information, such as the type and rank of the array, which does not have to be tracked during run time. This information also includes dynamic information, such as the allocation status of the array, the locations of the array elements, and the array bounds in each dimension. These dynamic properties can change, and hence, must be tracked during program execution.
Most programming languages that support variable-sized dynamically allocated arrays, such as the FORTRAN programming language, maintain this information in a data structure known as an “array descriptor” (or informally, as a “dope vector”).
Referring to
FIG. 2
, in an existing array descriptor data structure
200
, the array descriptor data structure
200
comprises a fixed part
202
followed by a sequence of triplets, wherein the number of triplets equals the rank (number of dimensions) of the array. In the example illustrated in
FIG. 2
, the fixed part
202
includes a start address
204
(actual origin) of the array as well as a virtual origin address
206
of the array. The start address
204
points to the starting location of the array of data values
226
. The virtual origin address
206
contains an address of a virtual array element, possibly outside the array, that has a zero index value for each dimension in the array.
Each triplet typically contains a lower bound value, an extent value (or upper bound) and a stride value. A given extent value quantifies a number of elements in a given dimension of the array. A given stride value quantifies a distance in array elements (or machine addressable units) between consecutive array locations in a given dimension. Note that the upper bound for a given dimension equals the lower bound for the given dimension added to the extent for the given dimension plus one. Hence, given a lower bound, the corresponding upper bound can be computed from the extent; likewise the extent can be computed from the upper bound.
Note that a triplet is associated with each dimension of the array. More specifically, dimension one has an associated triplet containing a lower bound
208
, an extent or upper bound
210
and a stride
212
. Dimension two has an associated triplet containing a lower bound
214
, an extent or upper bound
216
and a stride
218
. Dimension N has an associated triplet containing a lower bound
220
, an extent or upper bound
222
and a stride
224
.
One problem with the above-described layout of an array descriptor is that the information needed to perform common array access operations is interspersed with unnecessary information. In modem computer systems, this can lead to a large number of cache misses, which can significantly degrade system performance. This problem is particularly acute for microprocessors with small on-chip caches. This can create significant performance problems for common array access operations if accesses to array descriptors routinely cause cache misses.
SUMMARY
One embodiment of the present invention provides a computer readable memory including an array descriptor data structure which contains information on an organization of an array of data values in order to facilitate accesses into the array of data values. This array descriptor data structure includes a starting address of the array in the memory, and a group of extents, including an extent value for each dimension of the array, the extent value for a given dimension quantifying a number of elements in the given dimension. This array descriptor additionally includes a group of strides, including a stride value for each dimension of the array, the stride value of a given dimension quantifying a distance in array elements between consecutive array locations in the given dimension. Also included in the array descriptor data structure is a group of lower bound values, including a lower bound value for each dimension of the array. According to one aspect of the present invention, the group of strides is located in consecutive memory locations, so that an access to an array element through subscripts retrieves strides from consecutive memory locations, thereby exhibiting good cache performance. According to another aspect of the present invention, the group of extents is located in consecutive memory locations, and the group of strides is located in consecutive memory locations, so that a whole array operation, which accesses all locations in the array, first retrieves extents from consecutive memory locations, and then retrieves strides from consecutive memory locations so as to exhibit good cache performance.


REFERENCES:
patent: 5274818 (1993-12-01), Vasilevsky et al.
patent: 5475842 (1995-12-01), Gilbert et al.
patent: 5659753 (1997-08-01), Murphy et al.
patent: 5805915 (1998-09-01), Wilkinson et al.
patent: 5862385 (1999-01-01), Iitsuka
patent: 6128639 (2000-10-01), Pase
Paek et al., “Simplification of Array Access Patterns for Compiler Optimizations”, ACM, pp. 60-71, Jun. 1998.*
Shen et al., “An Empirical Study of Fortran Programs for Parallelizing Compilers”, IEEE, pp. 356-364, Jul. 1990.*
Hemlet et al., “Exploring Dataflow Testing of Arrays”, IEEE, pp. 118-129, May 1993.

Affiliated with

Also associated with

Rating

Efficient array descriptors for variable-sized, dynamically... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient array descriptors for variable-sized, dynamically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient array descriptors for variable-sized, dynamically... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2912111