Memory access request reordering to reduce memory access latency

• US 6,487,640 B1
• Filed: 01/19/1999
• Issued: 11/26/2002
• Est. Priority Date: 01/19/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lipasti, Mikko Herman
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/232,263
• Time in Patent Office: 1,407 Days
• Field of Search: 711/122, 711/140, 711/167, 711/168, 711/169, 711/124, 711/132, 711/137
• US Class Current: 711/140
• CPC Class Codes: G06F 12/0859 with reload from main memory
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3824 Operand accessing

Abstract

A data processing system, circuit arrangement, integrated circuit device, program product, and method reduce the memory access latency of sequences of memory access requests by processing at least one request in a sequence out of order relative to another request based upon whether the other request is likely to be for data maintained in the same organizational block (e.g., a cache line) as data requested by an earlier memory access request in the sequence. Given that multiple requests for data in the same block will collectively hit or miss a given level of memory, whenever a miss occurs as a result of an earlier request, the later requests for data in the same block would otherwise stall until processing of the miss was complete. Thus, by attempting to process other requests prior to processing all of the requests to the same block, overall memory access latency often improves since potentially productive operations can be performed during periods that would otherwise be wasted waiting for a common block of data to be retrieved from a lower level of memory. Among other implementations, request reordering may be used to improve the performance of complex memory instructions that use multiple memory access requests to access a range of contiguous words that span more than one organizational block.

Claims

1. A method of accessing data in a multi-level memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the method comprising:

(a) processing a first memory access request; and

(b) after processing the first memory access request, processing a second memory access request prior to processing a third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request.

2. The method of claim 1, wherein the first level of memory includes a cache memory, wherein each block corresponds to a cache line in the cache memory.

3. The method of claim 1, wherein processing the second memory access request prior to processing the third memory access request is further based upon whether the second memory access request is for data in a different block than the data requested by the first memory access request.

6. The method of claim 1, further comprising:

(a) receiving a complex memory instruction that references a plurality of contiguous words in the multi-level memory architecture, the plurality of contiguous words spanning a plurality of blocks, wherein the first, second and third memory access requests are each for at least one of the plurality of contiguous words, the first and second memory access requests for words in different blocks; and

(b) processing the complex memory instruction, including issuing the first memory access request, thereafter issuing the second memory access request, and thereafter issuing the third memory access request.

7. The method of claim 1, wherein the first, second and third memory access requests are processed responsive to execution of a computer program, the method further comprising determining whether the third memory access request is likely to be for data maintained in the same block as data requested by the first memory access request.

8. The method of claim 7, wherein determining whether the third memory access request is likely to be for data maintained in the same block as data requested by the first memory access request is performed during compilation of the computer program.

9. The method of claim 7, wherein determining whether the third memory access request is likely to be for data maintained in the same block as data requested by the first memory access request is performed during execution of the computer program.

10. The method of claim 1, further comprising fetching the third memory access request prior to fetching the second memory access request, wherein processing the second memory access request prior to processing the third memory access request includes reordering the second and third memory access requests such that the second memory access request is processed prior to processing the third memory access request.

4. A method of accessing data in a multi-level memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the method comprising:

(a) processing a first memory access request; and

(b) after processing the first memory access request, processing a second memory access request prior to processing a third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request;

wherein the first and second memory access requests miss the first level of memory, the method further comprising processing the miss for the second memory access request during processing of the miss for the first memory access request.

5. A method of accessing data in a multi-level memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the method comprising:

(a) processing a first memory access request; and

(b) after processing the first memory access request, processing a second memory access request prior to processing a third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request;

wherein the second memory access request is for data accessed at a higher memory address than that for the third memory access request.

11. A method of accessing data in a multi-level memory architecture of the type including at least one cache, wherein data is arranged in cache lines in the cache, each cache line capable of storing a plurality of contiguous words, the method comprising:

(a) receiving a complex memory instruction that references a plurality of contiguous words in the multi-level memory architecture, the plurality of contiguous words spanning a plurality of cache lines including at least first and second cache lines; and

(b) processing the complex memory instruction by processing a memory access request for at least one word in the plurality of contiguous words that is arranged in a cache line other than the first cache line, prior to processing memory access requests for all of the words in the plurality of contiguous words that are arranged in the first cache line.

12. The method of claim 11, wherein processing the complex memory instruction includes issuing in round robin fashion memory access requests for words in the plurality of contiguous words that are maintained in each of the plurality of cache lines.

13. The method of claim 11, wherein processing the complex memory instruction includes processing a memory access request for at least one word in the plurality of contiguous words that is arranged in a cache line other than the first cache line, prior to processing a memory access request for any of the words in the plurality of contiguous words that are arranged in the first cache line.

14. A method of accessing data in a multi-level memory architecture of the type including at least one cache, wherein data is arranged in cache lines in the cache, each cache line capable of storing a plurality of contiguous words, the method comprising:

(a) receiving a complex memory instruction that references a plurality of contiguous words in the multi-level memory architecture, the plurality of contiguous words spanning a plurality of cache lines including at least first and second cache lines; and

(b) processing the complex memory instruction by processing a memory access request for at least one word in the plurality of contiguous words that is arranged in a cache line other than the first cache line, prior to processing memory access requests for all of the words in the plurality of contiguous words that are arranged in the first cache line, wherein processing the complex memory instruction includes;

(i) processing a memory access request for a last word among the plurality of contiguous words; and

(ii) thereafter processing in sequence at least one memory access request for each additional word in the plurality of contiguous words starting with the first word in the plurality of contiguous words.

15. A circuit arrangement configured to access data in a multi-level memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the circuit arrangement comprising:

(a) an execution unit configured to execute memory access requests to access data in the multi-level memory architecture; and

(b) request reordering logic circuitry configured to order the execution of first, second and third memory access requests by the execution unit, the request reordering logic circuitry configured to order the first memory access request to be executed prior to the second and third memory access requests, and to order the second memory access request to be executed prior to the third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request.

16. The circuit arrangement of claim 15, further comprising issue logic circuitry, coupled to the execution unit, the issue logic circuitry configured to issue memory access requests to the execution unit for execution thereby, wherein the request reordering logic circuitry is disposed in at least one of the execution unit and the issue logic circuitry.

17. The circuit arrangement of claim 15, further comprising decode logic circuitry, coupled to the execution unit, the decode logic circuitry configured to receive a complex memory access instruction and to generate memory access requests responsive thereto, wherein the request reordering logic circuitry is disposed in the decode logic circuitry.

18. The circuit arrangement of claim 15, wherein the request reordering logic circuitry is configured to order the execution of first, second and third memory access requests by reordering the memory access requests relative to an initial order in which the memory access requests are received by the request reordering logic circuitry.

19. The circuit arrangement of claim 15, wherein the request reordering logic circuitry is configured to order the execution of first, second and third memory access requests by generating the memory access requests in a predetermined order.

20. The circuit arrangement of claim 15, wherein the first level of memory includes a cache memory, wherein each block corresponds to a cache line in the cache memory.

21. The circuit arrangement of claim 15, wherein the request reordering logic is further configured to order the second memory access request to be executed prior to the third memory access request based upon whether the second memory access request is for data in a different block than the data requested by the first memory access request.

23. An integrated circuit device comprising the circuit arrangement of claim 15.

24. A data processing system comprising the circuit arrangement of claim 15.

25. A program product, comprising a hardware definition program that defines the circuit arrangement of claim 15;

and a signal bearing media bearing the hardware definition program, the signal bearing media including at least one of a transmission type media and a recordable media.

22. A circuit arrangement configured to access data in a multilevel memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the circuit arrangement comprising:

(a) an execution unit configured to execute memory access requests to access data in the multi-level memory architecture; and

(b) request reordering logic circuitry configured to order the execution of first, second and third memory access requests by the execution unit, the request reordering logic circuitry configured to order the first memory access request to be executed prior to the second and third memory access requests, and to order the second memory access request to be executed prior to the third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request, wherein the second memory access request is for data accessed at a higher memory address than that for the third memory access request.

26. An apparatus, comprising:

(a) a multi-level memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks; and

(b) a processor coupled to the multi-level memory architecture, the processor including;

(1) an execution unit configured to execute memory access requests to access data in the multi-level memory architecture; and

(2) request reordering logic circuitry configured to order the execution of first, second and third memory access requests by the execution unit, the request reordering logic circuitry configured to order the first memory access request to be executed prior to the second and third memory access requests, and to order the second memory access request to be executed prior to the third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request.

27. The apparatus of claim 26, wherein the first level of memory includes a pipelined cache memory configured to process a miss generated responsive to the second memory access request during processing of a miss generated responsive to the first memory access request.

28. A circuit arrangement configured to access data in a multilevel memory architecture of the type including at least first and second levels of memory, wherein data in at least the first level of memory is arranged in blocks, the circuit arrangement comprising:

(a) an execution unit configured to execute memory access requests to access data in the multi-level memory architecture; and

(b) request reordering logic circuitry configured to order the execution of first, second and third memory access requests by the execution unit, the request reordering logic circuitry configured to order the first memory access request to be executed prior to the second and third memory access requests, and to order the second memory access request to be executed prior to the third memory access request based upon whether the third memory access request is for data maintained in the same block as data requested by the first memory access request, wherein the first and second memory access requests miss the first level of memory, the request reordering logic circuitry further configured to process the miss for the second memory access request during processing of the miss for the first memory access request.