Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-05-08
2001-12-18
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06332214
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to compilers and, more particularly, to compilers that perform invalidation profiling for data speculation.
2. Background Art
A compiler is a program that reads a source program written in a source language and translates it into a target program in a target language. For example, a compiler may translate a high level source program (such as C++) into compiled code that can be understood by a processor, such as a microprocessor.
Many compilers include three stages: (1) a “front end” in which the source program is translated into intermediate representations; (2) a “middle end” in which machine independent optimizations are made; and (3) a “back end” in which machine dependent optimizations are made and code is generated. Optimizations can significantly improve running time and/or space requirements of the target program. However, “optimized” code is not necessarily optimal under any mathematical measure.
There have been attempts to find invalidation rates by comparing the addresses of load-store pairs. This approach may be referred to as a “pair-wise” approach. The pair-wise approach collects conflict rate as the probability that a load (L) and a store (S) access the same memory location. The pair-wise conflict rate is denoted PCR (L,S). Although pair-wise conflict rate has other uses, such as disambiguation in dependence analysis, it has several serious problems for directing data speculation. A fundamental limitation with the pair-wise approach is that PCR (L, S) is not schedule-region sensitive.
Data speculation may be expensive because recovery can take many CPU cycles. A study of data speculation, Gallagher et al., “Dynamic Memory Disambiguation Using the Memory Conflict Buffer,” ACM SIGPLAN Notices, Nov. 1, 1994, v29 n11, p. 183, considered only register pressure as the cost of data speculation. The recovery cost was ignored by treating the number of cycles in a recover as equaling the number of cycles in a regular load. For many situations, this is not a realistic assumption.
Accordingly, there is a need for a compiler that performs accurate invalidation profiling for data speculation.
SUMMARY OF THE INVENTION
In one implementation, the invention involves a computer implemented method used in compiling a program. The method includes selecting conflict regions of the program. The method further includes performing invalidation profiling of load instructions with respect to certain ones of the conflict regions to determine invalidation rates of the load instructions. The method may further include a feedback step in which the invalidation rates are used by a scheduler of the compiler to determine whether to move the load instructions to target locations.
REFERENCES:
patent: 5119495 (1992-06-01), King
patent: 5170465 (1992-12-01), McKeeman et al.
patent: 5420990 (1995-05-01), McKeen et al.
patent: 5421022 (1995-05-01), McKeen et al.
patent: 5457799 (1995-10-01), Srivastava
patent: 5526499 (1996-06-01), Bernstein et al.
patent: 5537620 (1996-07-01), Breternitz, Jr.
patent: 5542075 (1996-07-01), Ebcioglu et al.
patent: 5634023 (1997-05-01), Adler et al.
patent: 5655122 (1997-08-01), Wu
patent: 5664193 (1997-09-01), Tirumalai
patent: 5694577 (1997-12-01), Kiyohara et al.
patent: 5933643 (1999-08-01), Holler
patent: 6158049 (2000-12-01), Goodwin et al.
Wu et al.; “Parallel processor balance through loop spreading”. ACM Digital Library[online], 1989 Conference on High Performance Networking and Computing, pp. 665-674, Nov. 1989.*
Wu, Y., “Ordering functions for improving memory reference locality in a shared memory multiprocessor system”. ACM Digital Library[online], 25th Annual International Symposium on Microarchitecture, pp. 218-221, Dec. 1992.*
Wu et al.; “Static branch frequency and program profile analysis”. ACM Digital Library[online], 27th Annual International symposium on Microarchitecture, pp. 1-11, Nov. 1994.*
Su et al.; “A Study of pointer aliasing for software pipelining using run-time disambiguation”. ACM Digital Library[online], 27th Annual International Symposium on Microarchitecture, pp. 112-117, Nov. 1994.*
Huang et al.; “Speculative Disambiguation: A compilation technique for dynamic memory disambiguation”. IEEE Xplore[online], 21st Annual International Symposium on Computer Architecture, pp. 200-210, Apr. 1994.*
Sato, T.; “Speculative resolution of ambiguous memory aliasing”, IEEE Explore[online], 1997 Innovative Architecture for Future Generation High-Performance Processors and Systems, pp. 17-26, Oct. 1997.*
Ball et al.; “Optimally Profiling and Tracing Programs”. ACM Digital Library[online]. ACM Transactions on Programming Languages and Systems, vol. 16, No. 4, pp. 1319-1360, Jul. 1994.*
Ball et al.; “Efficient Path Profiling”. IEEE/IEE Electronic Library[online], Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, 1996, Dec. 1996.*
T. Ball et al., “Efficient Path Profiling,” IEEE/ACM Intl Symp. on MicroArchitecture, MICRO-29, Dec. 2-4, 1996, pp. 46-57.
D. Chase et al., “Analysis of Pointers and Structures,” Proc. of ACM SIGPLAN' 90 Conference on Programming Language Design and Implementation, Jun. 1990. pp. 296-310.
D. Connors, “Memory Profiling for Directing Data Speculative Optimizations and Scheduling,” M.S. Thesis, University of Illinois, Urbana, IL, 1997, pp. cover through v and pp. 1-68. Note in particular pp. 34-50.
M. Emami et al., “Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers,” In Proc. of the ACM SIGNPLAN '94 Conf. on Programming Language Design and Implementation, Jun. 1994, pp. 242-256.
D. Gallagher et al., “Dynamic Memory Disambiguation Using the Memory Conflict Buffer,” ACM SIGPLAN Notices, Nov. 1994, v 29 n 11, pp. 183-193.
A. Huang et al., “Speculative Disambiguation: A Compilation Technique for Dynamic Memory Disambiguation,” Proc. of 21st Annual Intl. Symp. on Computer, Computer Architecture News, Apr. 1994, v 22 n 2, pp. 200-210.
A Nicolau, “Run-time Disambiguation: Coping with Statically Unpredictable Dependencies,” IEEE Transactions on Computers, May 1989 v 38 n 5, pp. 663-678.
S. Weiss, “Memory Conflict Resolution in Vector Supercomputers,” The Journal of Supercomputing, Mar. 1992 v 6 n 1, pp. 71-85.
R. Wilson et al., “Efficient Context-Sensitive Pointer Analysis for C Programs,” In Proc. of ACM SIGPLAN '95 Conf. on Programming Language Design and Implementation, Jun. 1995, pp. 1-12.
Aldous Alan K.
Booker Kelvin
Chaki Kakali
Intel Corporation
LandOfFree
Accurate invalidation profiling for cost effective data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accurate invalidation profiling for cost effective data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurate invalidation profiling for cost effective data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556508