System and method for processing memory instructions using a forced order queue

• US 7,519,771 B1
• Filed: 08/18/2003
• Issued: 04/14/2009
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Lundberg, Eric P., Baird, Robert J., Scott, Steven L., Faanes, Gregory J.
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US10/643,577
• Time in Patent Office: 2,066 Days
• Field of Search: 711/118, 711/154
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0859 with reload from main memory
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency

Abstract

A novel system and method for processing memory instructions. One embodiment of the invention provides a method for processing a memory instruction. In this embodiment, the method includes obtaining a memory request; storing the memory request in an Initial Request Queue (IRQ); and processing the memory request from the IRQ by a cache controller, wherein processing includes: identifying a type of the memory request, and processing the memory request in both a local cache and an Force Order Queue (FOQ), wherein processing includes determining if a portion of an address associated with the memory request matches one or more partial addresses in the FOQ and, if the memory request misses in the cache and the address does not match one or more partial addresses in the FOQ, adding the memory request to the FOQ and allocating a cache line in the local cache corresponding to the local cache miss.

Claims

1. A computerized method for accessing data in a memory system having a local cache and a higher level cache, comprising:

obtaining a memory request;

storing the memory request in an Initial Request Queue (IRQ); and

processing the memory request from the IRQ by a cache controller, wherein processing includes;

determining whether the memory request hits in the local cache;

determining whether a portion of an address associated with the memory request matches one or more partial addresses in a Force Order Queue (FOQ),

wherein the FOQ stores a memory request that is pending to the higher level cache;

when the portion of an address associated with the memory request does not match the one or more partial addresses in the FOQ and, at the same time, the memory request hits in the local cache, servicing the memory request immediately using data in the local cache without adding the memory request to the FOQ;

when the portion of an address associated with the memory request does not match the one or more partial addresses in the FOQ and, at the same time, the memory request misses in the local cache, adding the memory request to the FOQ, allocating a cache line in the local cache corresponding to the local cache miss and servicing the memory request using data received from the higher level cache;

when the portion of an address associated with the memory request matches the one or more partial addresses in the FOQ and, at the same time, the memory request hits in the local cache, preventing the memory request from being satisfied in the local cache, wherein preventing includes adding the memory request to the FOQ and servicing the memory request using data received from the higher level cache; and

when the portion of an address associated with the memory request matches the one or more partial addresses in the FOQ and, at the same time, the memory request misses in the local cache, preventing the memory request from being satisfied in the local cache, wherein preventing includes adding the memory request to the FOQ and servicing the memory request using data received from the higher level cache.

2. The computerized method of claim 1, wherein the obtaining of the memory request includes obtaining a memory load or a memory store request.

3. The computerized method of claim 1, wherein determining whether a portion of an address associated with the memory request matches one or more partial addresses in an Force Order Queue (FOQ) includes processing the memory request in the FOQ when local cache processing is bypassed.

4. The computerized method of claim 1, wherein determining whether a portion of an address associated with the memory request matches one or more partial addresses in an Force Order Queue (FOQ) includes processing the memory request in the FOQ when the memory request includes a synchronization request that causes local cache processing to be bypassed.

5. The computerized method of claim 1, wherein the FOQ is divided logically into a first and second queue, wherein the first queue monitors scalar memory requests to the higher level cache and the second queue monitors scalar memory requests that are serviced by the higher level cache but not yet written to the local cache.

6. A scalar processor, comprising:

a local cache;

an Initial Request Queue (IRQ); and

a cache controller having a Force Order Queue (FOQ), wherein the FOQ stores a scalar memory request that missed in the local cache and is pending to a higher level cache;

wherein the IRQ buffers a scalar load/store memory request having a scalar load/store instruction and its one or more associated addresses and sends the scalar load/store memory request to the cache controller and the local cache;

wherein, when a portion of the one or more associated addresses of the scalar load/store memory request does not match one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request hits in the local cache, the local cache services the scalar load/store memory request received from the IRQ without adding the memory request to the FOQ;

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request does not match the one or more partial addressed in the FOQ and, at the same time, the scalar load/store memory request misses in the local cache, the scalar load/store memory request is added to the FOQ, one or more lines in the local cache are allocated for cache line replacement, and the scalar load/store memory request is passed to the higher level cache;

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request matches the one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request hits in the local cache, the scalar load/store memory request is added to the FOQ and the scalar load/store memory request is passed to the higher level cache; and

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request matches the one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request misses in the local cache, the scalar load/store memory request is added to the FOQ and the scalar load/store memory request is passed to the higher level cache.

7. The scalar processor of claim 6, wherein the scalar processor further includes a scalar load/store unit, wherein the scalar load/store unit includes an address generator to generate one or more physical addresses from the one or more associated addresses of the scalar load/store command.

8. The scalar processor of claim 7, wherein the address generator generates the one or more physical addresses using a translation look-aside buffer (TLB).

9. The scalar processor of claim 6, wherein the FOQ is divided logically into a first and second queue, wherein the first queue monitors scalar memory requests to the higher level cache and the second queue monitors scalar memory requests that are serviced by the higher level cache but not yet written to the local cache.

10. A scalar processor, comprising:

a local cache;

an Initial Request Queue (IRQ); and

a plurality of cache controllers, wherein each cache controller includes a Force Order Queue (FOQ), wherein the cache controllers receive scalar memory requests from the IRQ and wherein, when a cache controller receives such a scalar memory request, the cache controller stores the scalar memory request in its FOQ if the scalar memory request misses in the local cache and is pending to a higher level cache;

wherein the IRQ buffers a scalar load/store memory request having a scalar load/store instruction and its one or more associated addresses and sends the scalar load/store memory request to the local cache and to one of the plurality of cache controllers corresponding to the one or more associated addresses of the scalar load/store memory request;

wherein, when a portion of the one or more associated addresses of the scalar load/store memory request does not match one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request hits in the local cache, the local cache services the scalar load/store memory request received from the IRQ without adding the memory request to the FOQ;

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request does not match the one or more partial addressed in the FOQ and, at the same time, the scalar load/store memory request misses in the local cache, the scalar load/store memory request is added to the FOQ, one or more lines in the local cache are allocated for cache line replacement, and the scalar load/store memory request is passed to the higher level cache;

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request matches the one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request hits in the local cache, the scalar load/store command is added to the FOQ and the scalar load/store memory request is passed to the higher level cache; and

wherein, when the portion of the one or more associated addresses of the scalar load/store memory request matches the one or more partial addresses in the FOQ and, at the same time, the scalar load/store memory request misses in the local cache, the scalar load/store memory request is added to the FOQ and the scalar load/store memory request is passed to the higher level cache.

11. The scalar processor of claim 10, wherein the FOQ includes a FOQ index array, wherein the FOQ index array contains a copy of indices and control information for the FOQ entries.

12. The scalar processor of claim 10, wherein the FOQ is divided logically into a first and second queue, wherein the first queue monitors scalar memory requests to the higher level cache and the second queue monitors scalar memory requests that are serviced by the higher level cache but not yet written to the local cache.