Management of reuse invalidation buffer for computation reuse

Details Management of reuse invalidation buffer for computation reuse Management of reuse invalidation buffer for computation reuse

2000-06-29

2003-09-30

Dam, Tuan Q. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S159000, C712S240000

Reexamination Certificate

active

06629314

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to microprocessors, and more specifically to microprocessors capable of reusing regions of software code.
BACKGROUND OF THE INVENTION
Modem software programs include many instructions that are executed multiple times each time the program is executed. Typically, large programs have logical “regions” of instructions, each of which may be executed many times. When a region is one that is executed more than once, and the results produced by the region are the same for more than one execution, the region is a candidate for “reuse.” The term “reuse” refers to the reusing of results from a previous execution of the region.
For example, a reuse region could be a region of software instructions that, when executed, read a first set of registers and modify a second set of registers. The data values in the first set of registers are the “inputs” to the reuse region, and the data values deposited into the second set of registers are the “results” of the reuse region. A buffer holding inputs and results can be maintained for the region. An entry in the buffer is termed an “instance.” When the region is encountered during the execution of the program, the buffer is consulted and if an instance with matching input values is found, the results can be used without having to execute the software instructions in the reuse region. When reusing the results is faster than executing the software instructions in the region, performance improves.
The example of the previous paragraph works well when the results are a function of nothing but the input values. When the results are a function of more than the input values, reuse is more complicated. For example, if a memory load instruction occurs in the reuse region, the results can be a function of the input values as previously described, and can also be a function of the data value loaded from the memory. If the memory load instruction accesses a memory location that is changed by a memory update instruction outside the region, then the region is said to be “aliased.”
Aliased regions present a problem for reuse. Even when a matching instance exists in the reuse buffer, the reuse instance may not be usable because the aliased memory load instruction may read a different value that causes the correct results to differ from the results in the instance. Therefore, it is important to identify reuse instances that cannot be reused. One approach is to use an “invalidate” instruction that is placed after memory update instructions capable of writing to the same location that the aliased load instruction accesses. Typically, the invalidation instruction includes a parameter identifying a reuse region. When the invalidation instruction is executed, reuse instances of the reuse region are invalidated.
However, it can be difficult and time consuming to find all of the memory update instructions that may update the aliased address and to insert an invalidation instruction after each found update instruction. Furthermore, even if all of the appropriate instructions can be found, this approach is conservative in part because the memory update instruction may update an address other than the aliased address, but the invalidate instruction will invalidate the region nonetheless.
Therefore, there is a need in the art for an alternate method and apparatus for invalidating instances of aliased reuse regions.


REFERENCES:
patent: 5845103 (1998-12-01), Sodani et al.
Avinash Sodani and Gurindar S. Sohi, “Dynamic Instruction Reuse”, Jun. 1-4, 1997, “Proceedings of the 24th international symposium on Computer architecture”, p. 194-205.*
Jian Huang and Lilja, D.J, “Exploiting basic block value locality with block reuse”, Jan. 9-13, 1999, IEEE, “High-Performance Computer Architecture, 1999. Proceedings. Fifth International Symposium On”, p. 106-114.*
Daniel A. Connors and Wen-mei W. Hwu, “Compiler-Directed Dynamic Computation Reuse: Rationale and Initial Results”, Nov. 1999, “Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture”, p. 158-169.*
Connors, D., et al., “Compiler-Directed Dynamic Computation Reuse: Rationale and Initial Results,” 32th International Symposium on Microarchitecture (Micro32), Nov.-Dec. 1999.
Dulong, C., “An Overview of the Intel IA-64 Compiler,” Intel Technology Journal, Q4, An Overview of the Intel IA-64 Compiler, 1999.

Affiliated with

Also associated with

Rating

Management of reuse invalidation buffer for computation reuse does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Management of reuse invalidation buffer for computation reuse, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Management of reuse invalidation buffer for computation reuse will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3069474