Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-11-05
2002-07-30
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S153000
Reexamination Certificate
active
06427235
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to compilers for computer systems. More specifically, the present invention provides a method and an apparatus for compiling source code into executable code that performs prefetching for memory operations within regions of code that tend to generate a large number of cache misses.
2. Related Art
As processor clock speeds continue to increase at an exponential rate, memory latencies are becoming a major bottleneck to computer system performance. On some applications a processor can spend as much as half of its time waiting for outstanding memory operations to move data from cache or main memory into registers within the processor. A single memory operation can cause the processor to wait for many clock cycles if the memory operation causes a cache miss from fast L
1
cache and a corresponding access from slower L
2
cache, or worse yet, causes a cache miss from L
2
cache and a corresponding access from main memory.
It is possible to alleviate some of the performance limiting effects of memory operations by designing a system so that it can initiate a memory operation in advance of instructions that make use of the data returned from the memory operation. However, designing such capabilities into a processor can greatly increase the complexity of the processor. This increased complexity can increase the cost of the processor and can potentially decrease the clock speed of the processor if the additional complexity lengthens a critical path through the processor. Furthermore, the potential performance gains through the use of such techniques can be limited.
It is also possible to modify executable code during the compilation process so that it explicitly prefetches data associated with a memory operation in advance of where the memory operation takes place. This makes it likely that the data will be present in L
1
cache when the memory operation occurs. This type of prefetching can be accomplished by scheduling an explicit prefetch operation into the code in advance of an associated memory operation in order to prefetch the data into L
1
cache before the memory operation is encountered in the code.
Unfortunately, it is very hard to determine which data items should be prefetched and which ones should not. Prefetching all data items is wasteful because the memory system can become bottlenecked prefetching data items that are not referenced. On the other hand, analyzing individual memory operations to determine if they are good candidates for prefetching can consume a great deal of computational time.
What is needed is a method and an apparatus that selects a set of memory operations for prefetching without spending a great deal of time analyzing individual memory operations.
SUMMARY
One embodiment of the present invention provides a system for compiling source code into executable code that performs prefetching for memory operations within regions of code that tend to generate cache misses. The system operates by compiling a source code module containing programming language instructions into an executable code module containing instructions suitable for execution by a processor. Next, the system runs the executable code module in a training mode on a representative workload and keeps statistics on cache miss rates for functions within the executable code module. These statistics are used to identify a set of “hot” functions that generate a large number of cache misses. Next, explicit prefetch instructions are scheduled in advance of memory operations within the set of hot functions.
In one embodiment, explicit prefetch operations are scheduled into the executable code module by activating prefetch generation at a start of an identified function, and by deactivating prefetch generation at a return from the identified function.
In embodiment, the system further schedules prefetch operations for the memory operations by identifying a subset of memory operations of a particular type within the set of hot functions, and scheduling explicit prefetch operations for memory operations belonging to the subset. The particular type of memory operation can include, memory operations through pointers, memory operations involving static data, memory operations from locations that have not been previously accessed, memory operations outside of the system stack, and memory operations that are likely to be executed.
In one embodiment, the system schedules the prefetch operations by identifying a subset of prefetch operations with a particular property, and by scheduling the prefetch operations based on the property. For example, the particular property can include having an available issue slot, being located on an opposite side of a function call site from an associated memory operation, being located on the same side of a function call site from the associated memory operation, and being associated with a cache block that is not already subject to a scheduled prefetch operation.
One embodiment of the present invention provides a system for compiling source code into executable code that performs prefetching for memory operations within critical sections of code that are subject to mutual exclusion. The system operates by compiling a source code module containing programming language instructions into an executable code module containing instructions suitable for execution by a processor. Next, the system identifies a critical section within the executable code module by identifying a region of code between a mutual exclusion lock operation and a mutual exclusion unlock operation. The system schedules explicit prefetch instructions into the critical section in advance of associated memory operations.
In one embodiment, the system identifies the critical section of code by using a first macro to perform the mutual exclusion lock operation, wherein the first macro additionally activates prefetching. The system also uses a second macro to perform the mutual exclusion unlock operation, wherein the second macro additionally deactivates prefetching. Note that the second macro does not deactivate prefetching if the mutual exclusion unlock operation is nested within another critical section.
REFERENCES:
patent: 5854934 (1998-12-01), Hsu et al.
patent: 5862385 (1999-01-01), Iitsuka
patent: 5930507 (1999-07-01), Nakahira et al.
patent: 5964867 (1999-10-01), Anderson et al.
patent: 5987477 (1999-11-01), Schmuck et al.
patent: 6026413 (2000-02-01), Challenger et al.
patent: 6092180 (2000-07-01), Anderson et al.
patent: 6119075 (2000-09-01), Dean et al.
patent: 6134710 (2000-10-01), Levine et al.
patent: 6189072 (2001-02-01), Levine et al.
patent: 6237073 (2001-05-01), Dean et al.
patent: 0 743 598 (1996-11-01), None
patent: 0 883 059 (1998-12-01), None
Publication entitled “Compiler's New Role in Data Cache Prefetching”, by Chi-Hung Chi, XP 000478803, 13thWorld Computer Congress 94, vol. 1, pp. 189-194.
Publication entitled “Compiler-Based Prefetching for Recursive Data Structures”, by Chi-Keung Luk and Todd C. Mowry, XP 000639234, University of Toronto, 1996 ACM 0-89791-767-7/96/70010, pp. 222-233.
Damron Peter C.
Kosche Nicolai
Chaki Kakali
Chavis John Q.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for performing prefetching at the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing prefetching at the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing prefetching at the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2898206