Speculative reuse of code regions

Details Speculative reuse of code regions Speculative reuse of code regions

1999-12-22

2003-09-23

Pan, Daniel H. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Processing sequence control

C712S248000, C712S228000, C717S165000, C717S145000, C717S131000, C709S241000, C709S241000

Reexamination Certificate

active

06625725

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
Modern 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. Each entry in the buffer is termed an “instance.” When the region is encountered during 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. Such a buffer is described in: Daniel Connors & Wen-mei Hwu, “Compiler-Directed Dynamic Computation Reuse: Rationale and Initial Results,” Proceedings of the 32nd Annual International Symposium on Microarchitecture (MICRO), November 1999.
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 may read a different value that causes the correct results to differ from the results in the instance. Connors and Hwu present an “invalidate” instruction that invalidates the reuse buffer instances for a region such that they cannot be reused. The invalidate instruction is placed after memory update instructions capable of writing to the same location that the aliased load instruction accesses, but it can be difficult to find all of the memory update instructions that may update the aliased address. Even if all of the appropriate instructions are 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.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for an alternate method and apparatus for code reuse.
SUMMARY
In one embodiment, a processing apparatus includes a first processor core configured to speculatively execute instructions based on results from an instance of a reuse region, and a second processor core configured to verify the results from the instance of the reuse region. The processing apparatus can also include a thread queue coupled between the first processor core and the second processor core, where the thread queue is configured to communicate a thread structure describing the reuse region from the first processor core to the second processor core.
In another embodiment, a processing apparatus includes a reuse buffer configured to hold instances of reuse regions, and also includes a reuse invalidation buffer configured to have entries that point to at least one of the instances of reuse regions held in the reuse buffer.
In another embodiment, a computer-implemented method for annotating a software program includes identifying a reuse region within the software program, determining whether the reuse region is aliased, and when the reuse region is aliased, adding a speculative reuse instruction to the reuse region.


REFERENCES:
patent: 5845101 (1998-12-01), Johnson et al.
patent: 5845103 (1998-12-01), Sodani et al.
Connors, D.A., et al., “Compiler-Directed Dynamic Computation Reuse: Rationale and Initial Results”,Proceedings of the 32nd Annual International Symposium on Microarchitecture(MICRO), 12 pgs., (Nov. 1999).
Gallagher, D.M., et al., “Dynamic Memory Disambiguation Using the Memory, Conflict Buffer”,ASPOLS-VI Proceedings, vol. 29,pp. 183-193, (Nov. 1994).
Tsia, J., et al., “The Superthreaded Processor Architecture”, 1-40.
Vijaykumar, T.N., et al., “Task Selection for a Multiscalar Processor”,31st International Symposium on Microarchitecture,12 pgs., (Dec. 1998).
Calder, B., et al., “Value Profiling”,IEEE, Proceedings of Micro-30,11 pgs., (Dec. 1-3, 1997).
Steffan, J.G., et al., “Architectural Support for Thread-Level Data Speculation”,Computer Science Technical Report,Computer Science Department School of Computer Science, Carnegie Mellon University, CMU-CS-97-188, 1-41, (Nov. 1997).
Steffan, J.G., et al., “The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization”,HPCA-4,1-12, (Feb. 1-4, 1998).
Sodani, A., et al., “Dynamic Instruction Reuse”,ACM, (1997).

Affiliated with

Also associated with

Rating

Speculative reuse of code regions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Speculative reuse of code regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Speculative reuse of code regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3014578