Reassembling abstracted memory accesses for prefetching

• US 8,832,384 B1
• Filed: 07/29/2010
• Issued: 09/09/2014
• Est. Priority Date: 07/29/2010
• Status: Expired due to Fees

• Current Assignee: Violin Systems LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: de la Iglesia, Erik
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US12/846,568
• Time in Patent Office: 1,503 Days
• Field of Search: 711/137, 711/213, 712/207, 712/237
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A storage proxy receives different abstracted memory access requests that are abstracted from the original memory access requests from different sources. The storage proxy reconstructs the characteristics of the original memory access requests from the abstracted memory access requests and makes prefetch decisions based on the reconstructed characteristics. An inflight table is configured to identify contiguous address ranges formed by an accumulation of sub-address ranges used by different abstracted memory access requests. An operation table is configured to identify the number of times the contiguous address ranges are formed by the memory access operations. A processor is then configured to prefetch the contiguous address ranges for certain corresponding read requests.

Claims

1. An apparatus, comprising:

logic circuitry configured to receive memory access requests that are abstracted from memory access requests, the logic circuitry further configured to reconstruct characteristics of the original memory access requests from the abstracted memory access requests and make prefetch decisions based on the reconstructed characteristics.

2. The apparatus of claim 1 further comprising an inflight table including operation records that identify start addresses, end addresses, and timestamps associated with the abstracted memory access requests.

3. The apparatus of claim 2 wherein the logic circuitry is configured to combine contiguous address ranges for two abstracted memory access requests into a same one of the operation records.

4. The apparatus of claim 2 wherein the logic circuit is configured to:

identify one of the operation records that has not been modified for the longest period of time; and

remove the identified one of the operation records when a threshold number of operation records are contained in the inflight table.

5. The apparatus of claim 4 wherein the logic circuit is configured to replace the removed one of the operation records with a new operation record that includes the start address, end address, and timestamp for a newly received one of the abstracted memory access requests.

6. The apparatus of claim 4 wherein the logic circuit is configured to identify a size for one of the original memory access requests from a starting address and ending address in the removed one of the operation records.

7. The apparatus of claim 6 wherein the logic circuit is configured to make a prefetch recommendation corresponding with the size identified from the removed one of the operation records.

8. The apparatus of claim 4 wherein the logic circuit is configured to identify an address offset for one of the original memory access requests from the starting address in the removed one of the operation records.

9. The apparatus according to claim 4 further comprising an operation table configured to track numbers of different address ranges and different address offsets identified in the operation records removed from the inflight table, and wherein the logic circuit is configured to make prefetch recommendations according to the tracked numbers in the operation table.

10. The apparatus of claim 2 wherein the logic circuit is configured to:

identify one of the operation records that has an starting address offset that matches a starting address offset for a received one of the abstracted memory access requests; and

conduct a prefetch for an address range identified in the identified one of the operation records.

11. The apparatus of claim 2 wherein the logic circuitry is configured to combine abstracted memory requests having contiguous address ranges into a same one of the records, including updating the timestamp.

12. The apparatus of claim 1 further comprising an inflight table including records that characterize the abstracted memory requests by start address, end address, and a timestamp representing a latest record update time.

13. A non-transitory computer readable medium containing instructions configured to be executed by a computer system, the instructions when executed by the computer system comprising:

receiving a read operation;

updating an operation record in a table when a read start address in the read operation corresponds with a read end address in the operation record;

updating the operation record by replacing the read end address in the operation record with a read end address of the read operation;

conducting prefetch operations according to the operation record.

14. The computer readable medium of claim 13 further comprising updating the operation record by replacing a timestamp in the operation record with a time value associated with the read operation.

15. The computer readable medium of claim 13 further comprising:

removing the operation record from the table when the table has a threshold number of operation records and a last update for the operation record was longer than all other operation records in the table; and

conducting the prefetch operations only on information contained in operation records after being removed from the table.

16. The computer readable medium of claim 13 further comprising:

identifying an address range and a starting address offset for the operation record removed from the table; and

generating count values identifying how many operation records removed from the table are within the address ranges and have the starting address offsets.

17. The computer readable medium of claim 16 further comprising:

identifying a starting address offset for a new read operation;

identifying a group of the count values that have starting address offsets corresponding with the starting address offset of the new read operation;

summing all of the count values for the group; and

recommending a prefetch operation when the sum of all of the count values of the group is over a given threshold.

18. The computer readable medium of claim 17 further comprising:

identifying a highest one of the count values in the group;

identifying the address range associated with the highest one of the count values; and

prefetching an amount of data corresponding with the identified address range.

19. The computer readable medium of claim 16 further comprising identifying the starting address offsets by taking a modulus value of a starting address value.

20. A storage proxy, comprising:

an operation table configured to store a record of a contiguous address range of a plurality of contiguous address ranges of stored data, the contiguous address range formed by accumulation of sub-address ranges used by a plurality of memory access operations;

a count table containing a count value representing a number of times the record of the contiguous address range of the plurality of contiguous address ranges is formed by the memory access operations; and

a processor configured to prefetch stored data according to the count value.

21. The storage proxy according to claim 20 wherein the processor is further configured to:

receive a read operation of the plurality of memory access operations;

identify a record in an inflight table that contains an ending address corresponding with a starting address in the read operation;

replace an ending address in the identified record with an ending address of the read operation to form the contiguous address range;

incrementing the count value in the count table having a same address range as the contiguous address range.

22. The storage proxy according to claim 20 wherein the processor is further configured to:

group the count values in the count table according to a starting address offset of a plurality of starting address offsets of the contiguous address range;

receive a read operation;

identify the starting address offset for the read operation;

identify the group of the count values in the count table with a same starting address offset as the starting address offset of the read operation;

identify a highest one of the count values in the group of count values;

identify the contiguous address range associated with the highest one of the count values; and

prefetch data-stored at the identified contiguous address range.

23. An apparatus, comprising:

logic circuitry configured to receive a plurality of memory access requests that are abstracted from an original memory access request, the logic circuitry further configured to reconstruct characteristics of the original memory access request from the plurality of abstracted memory access request and make prefetch decisions based on the reconstructed characteristics of the original memory access request.