Techniques for Multi-Level Indirect Data Prefetching

• US 20090198906A1
• Filed: 02/01/2008
• Published: 08/06/2009
• Est. Priority Date: 02/01/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Armilli, Ravi K., Zhang, Lixin, Sinharoy, Balaram, Speight, William E.
• Granted Patent: US 8,161,265 B2
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 2212/681 Multi-level TLB, e.g. microTLB and main TLB

Abstract

A technique for performing data prefetching using multi-level indirect data prefetching includes determining a first memory address of a pointer associated with a data prefetch instruction. Content that is included in a first data block (e.g., a first cache line of a memory) at the first memory address is then fetched. A second memory address is then determined based on the content at the first memory address. Content that is included in a second data block (e.g., a second cache line) at the second memory address is then fetched (e.g., from the memory or another memory). A third memory address is then determined based on the content at the second memory address. Finally, a third data block (e.g., a third cache line) that includes another pointer or data at the third memory address is fetched (e.g., from the memory or the another memory).

Claims

1. A method of performing multi-level indirect data prefetching, comprising:

determining a first memory address of a pointer associated with a data prefetch instruction;

fetching a first data block that includes content at the first memory address;

determining a second memory address from the content at the first memory address;

fetching a second data block that includes content at the second memory address;

determining a third memory address from the content at the second memory address; and

fetching a third data block that includes another pointer or data at the third memory address.

2. The method of claim 1, wherein the determining a first memory address further comprises:

determining a first effective address of the pointer;

translating the first effective address to a first virtual address; and

translating the first virtual address to a first real address that corresponds to the first memory address.

3. The method of claim 2, wherein the determining a second memory address further comprises:

determining a second effective address based on the content at the first memory address;

translating the second effective address to a second virtual address; and

translating the second virtual address to a second real address that corresponds to the second memory address.

4. The method of claim 3, wherein the determining a third memory address further comprises:

determining a third effective address based on the content at the second memory address;

translating the third effective address to a third virtual address; and

translating the third virtual address to a third real address that corresponds to the third memory address.

5. The method of claim 1, wherein the determining a first memory address further comprises:

determining a first effective address of the pointer; and

translating the first effective address to a first real address that corresponds to the first memory address.

6. The method of claim 5, wherein the determining a second memory address further comprises:

determining a second effective address based on the content at the first memory address; and

translating the second effective address to a second real address that corresponds to the second memory address.

7. The method of claim 6, wherein the determining a third memory address further comprises:

determining a third effective address based on the content of the memory at the second memory address; and

translating the third effective address to a third real address that corresponds to the third memory address.

8. A method of performing multi-level indirect data prefetching, comprising:

determining a first memory address of a pointer associated with a data prefetch instruction;

fetching a first data block that includes content at the first memory address;

adding a first offset to the content at the first memory address to provide a first offset memory address;

determining a second memory address based on the first offset memory address;

fetching a second data block that includes content at the second memory address;

adding a second offset to the content at the second memory address to provide a second offset memory address;

determining a third memory address based on the second offset memory address; and

fetching a third data block that includes another pointer or data at the third memory address.

9. The method of claim 8, wherein the first offset memory address is a first effective address and the method further comprises:

translating the first effective address to a first virtual address; and

translating the first virtual address to a first real address that corresponds to the second memory address.

10. The method of claim 9, wherein the second offset memory address is a second effective address and the method further comprises:

translating the second effective address to a second virtual address; and

translating the second effective address to a second real address that corresponds to the third memory address.

11. The method of claim 8, wherein the data prefetch instruction includes an opcode field that uniquely identifies the data prefetch instruction.

12. The method of claim 8, wherein the data prefetch instruction includes an indirect address field that identifies whether an effective address associated with the data prefetch instruction is a pointer for desired data that is to be prefetched.

13. A method of performing multi-level indirect data prefetching, comprising:

determining a first memory address of a pointer associated with a data prefetch instruction;

fetching a first data block that includes content at the first memory address;

determining a second memory address based on content at the first memory address;

adding an offset to the second memory address to provide a second offset memory address;

fetching a second data block that includes content at the second offset memory address;

determining a third memory address based on content at the second offset memory address;

adding an offset to the third memory address to provide an offset third memory address; and

fetching a third data block that includes another pointer or data at the offset third memory address.

14. The method of claim 13, wherein the determining a first memory address further comprises:

determining a first effective address of the pointer; and

translating the first effective address to a first real address that corresponds to the first memory address.

15. The method of claim 14, wherein the determining a second memory address further comprises:

determining a second effective address of the content at the first memory address; and

translating the second effective address to a second real address that corresponds to the second memory address.

16. The method of claim 15, wherein the determining a third memory address further comprises:

determining a third effective address of the content of the memory at the second offset memory address; and

translating the third effective address to a third real address that corresponds to the third memory address.

17. The method of claim 13, wherein the data prefetch instruction includes an indirect address field that identifies whether an effective address associated with the data prefetch instruction is a pointer for desired data that is to be prefetched.

18. The method of claim 17, wherein the indirect address field also identifies a number of indirection levels.

19. The method of claim 13, the determining the first memory address includes:

accessing, based on an effective address, a translation table in an effective-to-real address translation buffer; and

retrieving, based on the effective address, the first memory address from the translation table, wherein the first memory address is a real address.

20. The method of claim 13, wherein the determining the first memory address includes:

accessing, based on an effective address, a segment table in a segment lookaside buffer;

retrieving, based on the effective address, a virtual address from the segment table;

accessing, based on the virtual address, a hashed page table in a translation lookaside buffer; and

retrieving, based on the virtual address, the first memory address from the hashed page table, wherein the first memory address is a real address.

21. A processor comprising:

at least one register configured to store information associated with a data prefetch instruction; and

a load store unit coupled to the at least one register, wherein the load store unit is configured to;

determine a first memory address of a pointer associated with the data prefetch instruction;

initiate fetching of a first data block that includes content at the first memory address;

determine a second memory address from the content at the first memory address;

initiate fetching of a second data block that includes content at the second memory address;

determine a third memory address from the content at the second memory address; and

initiate fetching of a third data block that includes another pointer or data at the third memory address.

22. A processor system, comprising:

at least one processor in accordance with claim 21;

an interconnect coupled to the at least one processor; and

a memory subsystem coupled to the at least one processor via the interconnect and operable to communicate the first, second, and third data blocks to the at least one processor.

23. A processor comprising:

at least one register configured to store information associated with a data prefetch instruction; and

a load store unit coupled to the at least one register, wherein the load store unit is configured to;

determine a first memory address of a pointer associated with the data prefetch instruction;

initiate fetching of a first data block that includes content at the first memory address;

add a first offset to the content at the first memory address to provide a first offset memory address;

determine a second memory address based on the first offset memory address;

initiate fetching of a second data block that includes content at the second memory address;

add a second offset to the content at the second memory address to provide a second offset memory address;

determine a third memory address based on the second offset memory address; and

initiate fetching of a third data block that includes another pointer or data at the third memory address.

24. A processor system, comprising:

at least one processor in accordance with claim 23;

an interconnect coupled to the at least one processor; and

a memory subsystem coupled to the at least one processor via the interconnect and operable to communicate the first, second, and third data blocks to the at least one processor.

25. A processor comprising:

a memory controller; and

a load store unit coupled to the memory controller, wherein the load store unit is configured to determine a first memory address of a pointer associated with a data prefetch instruction, initiate fetching of a first data block that includes content at the first memory address, and determine a second memory address based on content at the first memory address, and wherein the memory controller is configured to add an offset to the second memory address to provide a second offset memory address and fetch a second data block that includes content at the second offset memory address, where the load store unit is further configured to determine a third memory address based on content at the second offset memory address, and where the memory controller is further configured to add an offset to the third memory address to provide an offset third memory address and fetch a third data block that includes another pointer or data at the offset third memory address.

26. A processor system, comprising:

at least one processor in accordance with claim 25;

an interconnect coupled to the at least one processor; and

a memory subsystem coupled to the at least one processor via the interconnect and operable to communicate the first, second, and third data blocks to the at least one processor.