PREFETCHING BASED UPON RETURN ADDRESSES

• US 20140143522A1
• Filed: 11/20/2012
• Published: 05/22/2014
• Est. Priority Date: 11/20/2012
• Status: Active Grant

• Current Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.), Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.), Board of Regents of the University of Michigan (University of Michigan)
• Inventors: SAIDI, Ali, WENISCH, Thomas Friedrich, KOLLI, Aasheesh
• Granted Patent: US 10,042,776 B2
• Time in Patent Office: Days
• US Class Current: 712/207
• CPC Class Codes: G06F 12/0862 with prefetch
• 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/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer

Abstract

An apparatus for processing data includes signature generation circuitry 30, 32 for generating a signature value indicative of the current state of the apparatus in dependence upon a sequence of immediately preceding return addresses generating during execution of a stream of program instructions to reach that state of the apparatus. Prefetch circuitry 10 performs one or more prefetch operations in dependence upon the signature value that is generated. The signature value may be generated by a hashing operation (such as an XOR) performed upon return addresses stored within a return address stack 28.

Claims

1. Apparatus for processing data in response to execution of a stream of program instructions including call instructions with respective associated return addresses, said apparatus comprising:

signature generation circuitry configured to generate a signature value indicative of a current state of said apparatus in dependence upon a plurality of return addresses generated during execution of said stream; and

prefetch circuitry configured to perform one or more prefetch operations in dependence upon said signature value.

2. Apparatus as claimed in claim 1, wherein when execution of said stream either generates a new return address or performs a return operation that consumes a previously generated return address, said signature generation circuitry generates an updated signature value.

3. Apparatus as claimed in claim 2, wherein said prefetch circuitry performs one or more prefetch operations in dependence upon said updated signature value.

4. Apparatus as claimed in claim 2, wherein said updated signature value is dependent upon whether said updated signature value was generated in response to generation of said new return address or consumption of said previously generated return address.

5. Apparatus as claimed in claim 4, wherein when said updated signature value is generated in response to generation of said new return address, then said updated signature value is dependent upon said plurality of return addresses including said new return address.

6. Apparatus as claimed in claim 4, wherein when said updated signature value is generated in response to consumption of said previously generated return address, then said updated signature value is dependent upon said plurality of return addresses including said previously generated return address.

7. Apparatus as claimed in claim 4, wherein said new signature includes a direction bit indicating whether said updated signature value was generated in response to generation of said new return address or consumption of said previously generated return address.

8. Apparatus as claimed in claim 1, wherein said signature generation circuitry is configured to perform a hashing function upon said plurality of return addresses to generate said signature value.

9. Apparatus as claimed in claim 8, wherein said hashing function includes one or more of:

an XOR operation performed upon said plurality of return addresses; and

a truncated addition performed upon said plurality of return addresses.

10. Apparatus as claimed in claim 1, comprising a memory system having a hierarchy of memory levels and wherein said one or more prefetch operations prefetch from said memory system at least one of:

a program instruction;

a block of program instructions;

a data value;

a block of data values; and

translation data for translating between virtual addresses and physical addresses within said memory.

11. Apparatus as claimed in claim 1, comprising a signature cache memory configured to store for each of a plurality of signature values respective prefetch data indicative of one or more prefetch operations to be performed.

12. Apparatus as claimed in claim 11, comprising at least one further cache memory and wherein said prefetch data for a given signature value identifies one or more addresses associated with respective cache misses within said one or more further cache memories that previously occurred when said apparatus had a state corresponding to said given signature and said one or more prefetch operations comprise cache prefetch operations corresponding to said cache misses.

13. Apparatus as claimed in claim 12, wherein said prefetch data identifies at least one base memory address and for each base memory address a bit field identifying one or more further memory addresses relative to said base memory address.

14. Apparatus as claimed in claim 12, comprising miss detecting circuitry coupled to said one or more further cache memories and configured to detect cache misses within said one or more further cache memories.

15. Apparatus as claimed in claim 14, wherein said miss detecting circuitry accumulates data identifying cache misses for a current signature value and updates said prefetch data for said current signature value when said current signature value changes to a new current signature value.

16. Apparatus as claimed in claim 1, wherein said signature generation circuitry comprises a return address stack memory storing data identifying a sequence of return addresses generated during immediately preceding execution of said stream of program instructions.

17. Apparatus as claimed in claim 16, wherein said return address stack memory is a ring buffer memory.

18. Apparatus as claimed in claim 2, wherein said prefetch circuitry is configured to use said updated signature value to predict an N^th following updated signature value that will be generated based upon a sequence of previously generated updated signature values, where N is an integer of one or more, and said one or more prefetch operations performed are prefetch operations associated with said N^th following updated signature value.

19. Apparatus as claimed in claim 18, wherein said prefetch circuitry comprises table storage circuitry configured to store data mapping updated signature values to respective N^th following updated signature values.

20. Apparatus for processing data in response to execution of a stream of program instructions including call instructions with respective associated return addresses, said apparatus comprising:

signature generation means for generating a signature value indicative of a current state of said apparatus in dependence upon a plurality of return addresses generated during execution of said stream; and

prefetch means for performing one or more prefetch operations in dependence upon said signature value.

21. A method of processing data, using apparatus for processing data, in response to execution of a stream of program instructions including call instructions with respective associated return addresses, said method comprising the steps of:

generating a signature value indicative of a current state of said apparatus in dependence upon a plurality of return addresses generated during execution of said stream; and

performing one or more prefetch operations in dependence upon said signature value.