System-wide memoization of array dependence information

Details System-wide memoization of array dependence information System-wide memoization of array dependence information

1997-07-14

1999-11-16

Hafiz, Tariq R.

G06F 9445

Patent

active

059872543

ABSTRACT:
Data dependence information is stored in a global or system-wide cache so as to reduce the necessity for repeated analysis of similar array reference pairs in a compiler. The data dependence cache is not limited to compilation of a single file. Rather, it can be accessed and shared by multiple users and over compilation of various files. This scheme is advantageous because of the similarity of array references among many programs. The data dependence cache is maintained and updated by determining a relative value of each record in the cache in a manner reminiscent of LRU techniques familiar to artisans in the hardware memory cache domain. The data dependence cache can be made available to multiple instances of a compiler using file locking techniques, or it can be managed by a separate dependence analysis process that responds to messages from other processes requesting data dependence information. In view of the high cost of data dependence analysis, the invention provides substantial improvements in compiler performance.

REFERENCES:
patent: 5274812 (1993-12-01), Inoue
patent: 5574875 (1996-11-01), Stansfield et al.
patent: 5761515 (1998-06-01), Barton et al.
"Practical Dependence Testing" Goff/Kennedy/Tseng, Dept. of Computer Science, Rice University, Houston, TX, 1991 (Proceedings of the ACM SIGPLAN '91 Conference).
"Efficient and Exact Data Dependence Analysis" Maydan/Hennessy/Lam, Computer Systems Laboratory, Stanford University, CA, 1991, (Proceedings of the ACM SIGPLAN '91 Conference).
A practical algorithm for exact array dependence analysis, by Pugh, Communications of the ACM, Aug. 1992.
Experiences with Constraint-based Array Dependence Analysis by Pugh et al, UMIACS-TR, Nov. 1994.
Nonlinear Array Dependence Analysis, by Pugh et al, UMIACS-TR, Nov. 1994.
Efficient and Exact Data Dependence Analysis, Maydan et al, Stanford University.
Supporting Array Dependence Testing for an Optimizing/Parallerizing C Compiler, Justiani et al., McGill University.

Affiliated with

Also associated with

Rating

System-wide memoization of array dependence information does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System-wide memoization of array dependence information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System-wide memoization of array dependence information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1335568