IP Library › Granted Patent US 7,461,237
Granted Patent B2
US 7,461,237 · App. 11/111,654 · Granted Dec 2, 2008

Method and apparatus for suppressing duplicative prefetches for branch target cache lines

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 7,461,237
App. No.
11/111,654
Granted
Dec 2, 2008
Kind
B2
Abstract

A system that suppresses duplicative prefetches for branch target cache lines. During operation, the system fetches a first cache line into in a fetch buffer. The system then prefetches a second cache line, which immediately follows the first cache line, into the fetch buffer. If a control transfer instruction in the first cache line has a target instruction which is located in the second cache line, the system determines if the control transfer instruction is also located at the end of the first cache line so that a corresponding delay slot for the control transfer instruction is located at the beginning of the second cache line. If so, the system suppresses a subsequent prefetch for a target cache line containing the target instruction because the target instruction is located in the second cache line which has already been prefetched.

Claims (79)

1. A method for improving performance in a processor which supports prefetching of cache lines, comprising:

fetching a first cache line into in a fetch buffer;

prefetching a second cache line, which immediately follows the first cache line, into the fetch buffer;

scanning the first cache line to determine a location for a target instruction for a control transfer instruction in the first cache line and a position for a corresponding delay slot for the control transfer instruction;

if the control transfer instruction in the first cache line has a target instruction which is located in the second cache line, determining if the control transfer instruction is located at the end of the first cache line so that the corresponding delay slot for the control transfer instruction is located at the beginning of the second cache line;

if so, suppressing a subsequent prefetch for a target cache line containing the target instruction because the target instruction is located in the second cache line which has already been prefetched; and

if the target instruction for the control transfer instruction is not located in the first cache line and is not located in the second cache line, determining if the control transfer instruction is located at the end of the first cache line;

if not,

retrieving the corresponding delay slot instruction for the control transfer instruction from the first cache line;

terminating the prefetch for the second cache line and instead prefetching the target cache line containing the target instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the target cache line containing the target instruction.

2. The method of claim 1 ,

wherein if the control transfer instruction is located at the end of the first cache line, the method further comprises retrieving the corresponding delay slot instruction from the second cache line;

otherwise, retrieving the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the second cache line.

3. The method of claim 1 , wherein if the control transfer instruction has a target instruction which is located in the first cache line, the method further comprises:

retrieving the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the first cache line.

4. The method of claim 1 , wherein if the control transfer instruction is located at the end of the first cache line, the method further comprises:

retrieving the corresponding delay slot instruction for the control transfer instruction from the second cache line;

prefetching the target cache line containing the target instruction of the control transfer instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the target cache line containing the target instruction.

5. The method of claim 1 , wherein the fetch buffer contains two entries for storing cache lines.

6. An apparatus for improving performance in a processor which supports prefetching of cache lines, comprising:

a processor;

a cache;

a memory; and

a fetch unit;

wherein the fetch unit is configured to:

fetch a first cache line into in a fetch buffer;

prefetch a second cache line, which immediately follows the first cache line, into the fetch buffer;

scan the first cache line to determine a location for a target instruction for a control transfer instruction in the first cache line and a position for a corresponding delay slot for the control transfer instruction;

if the control transfer instruction in the first cache line has a target instruction which is located in the second cache line, to determine if the control transfer instruction is located at the end of the first cache line so that the corresponding delay slot for the control transfer instruction is located at the beginning of the second cache line; and

if so, to suppress a subsequent prefetch for a target cache line containing the target instruction because the target instruction is located in the second cache line which has already been prefetched; and

if the target instruction for the control transfer instruction is not located in the first cache line and is not located in the second cache line, determining if the control transfer instruction is located at the end of the first cache line;

if not,

retrieving the corresponding delay slot instruction for the control transfer instruction from the first cache line;

terminating the prefetch for the second cache line and instead prefetching the target cache line containing the target instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the target cache line containing the target instruction.

7. The apparatus of claim 6 ,

wherein if the control transfer instruction is located at the end of the first cache line, the fetch unit is configured to retrieve the corresponding delay slot instruction from the second cache line;

otherwise the fetch unit is configured to retrieve the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the second cache line.

8. The apparatus of claim 6 , wherein if the control transfer instruction has a target instruction which is located in the first cache line, the fetch unit is configured to:

retrieve the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the first cache line.

9. The apparatus of claim 6 , wherein if the control transfer instruction is located at the end of the first cache line, the fetch unit is configured to:

retrieve the corresponding delay slot instruction for the control transfer instruction from the second cache line;

prefetch the target cache line containing the target instruction of the control transfer instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the target cache line containing the target instruction.

10. The apparatus of claim 6 , wherein the fetch buffer contains two entries for storing cache lines.

11. A computer system including a fetch unit that improves performance in a processor which supports prefetching of cache lines, comprising:

a processor;

a cache;

a memory; and

a fetch unit;

wherein the fetch unit is configured to:

fetch a first cache line into in a fetch buffer;

prefetch a second cache line, which immediately follows the first cache line, into the fetch buffer;

scan the first cache line to determine a location for a target instruction for a control transfer instruction in the first cache line and a position for a corresponding delay slot for the control transfer instruction;

if the control transfer instruction in the first cache line has a target instruction which is located in the second cache line, to determine if the control transfer instruction is located at the end of the first cache line so that the corresponding delay slot for the control transfer instruction is located at the beginning of the second cache line; and

if so, to suppress a subsequent prefetch for a target cache line containing the target instruction because the target instruction is located in the second cache line which has already been prefetched; and

if the target instruction for the control transfer instruction is not located in the first cache line and is not located in the second cache line, determining if the control transfer instruction is located at the end of the first cache line;

if not,

retrieving the corresponding delay slot instruction for the control transfer instruction from the first cache line;

terminating the prefetch for the second cache line and instead prefetching the target cache line containing the target instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, jumping to the target instruction in the target cache line containing the target instruction.

12. The computer system of claim 11 ,

wherein if the control transfer instruction is located at the end of the first cache line, the fetch unit is configured to retrieve the corresponding delay slot instruction from the second cache line;

otherwise, the fetch unit is configured to retrieve the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the second cache line.

13. The computer system of claim 11 , wherein if the control transfer instruction has a target instruction which is located in the first cache line, the fetch unit is configured to:

retrieve the corresponding delay slot instruction from the first cache line; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the first cache line.

14. The computer system of claim 11 , wherein if the control transfer instruction is located at the end of the first cache line, the fetch unit is configured to:

retrieve the corresponding delay slot instruction for the control transfer instruction from the second cache line;

prefetch the target cache line containing the target instruction of the control transfer instruction into the fetch buffer; and

when the control transfer instruction is encountered and the control transfer instruction transfers control to the target instruction, the processor is configured to jump to the target instruction in the target cache line containing the target instruction.

15. The computer system of claim 11 , wherein the fetch buffer contains two entries for storing cache lines.

Assignments (2)
MERGER AND CHANGE OF NAME Recorded Dec 16, 2015
From: ORACLE USA, INC.; SUN MICROSYSTEMS, INC.; ORACLE AMERICA, INC.
To: ORACLE AMERICA, INC.
Reel/Frame 037303/0926 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 21, 2005
From: ALI, ABID; CAPRIOLI, PAUL; CHAUDHRY, SHAILENDER; LEE, MILES
To: SUN MICROSYSTEMS, INC.
Reel/Frame 016506/0290 →