Patent Description:
To support execution of instructions at a processor, a processing system typically includes a memory subsystem consisting of memory modules to store data to be accessed by the executing instructions. To facilitate processing efficiency, the memory subsystem can be organized into a memory hierarchy having main memory at the top of the hierarchy to store all data that can be accessed by the executing instructions, and one or more caches at lower levels of the memory hierarchy to store subsets of the data stored at main memory. To further enhance processing efficiency, the processing system can implement a memory management protocol that governs the fetching of data from main memory to the one or more lower levels of memory through one or more cache controllers. For example, if data required by the processor is not found at a cache of the memory hierarchy (referred to as a "cache miss"), the cache controller issues a memory access request to retrieve the data from a different level of the memory hierarchy, such as from a different cache or from main memory.

To prevent the issuance of multiple memory access requests for the same data from a given level of the memory hierarchy, which can waste processor resources, the cache controller stores the memory address corresponding to each unit of data that is the subject of a pending memory access request in a buffer. When a subsequent request for the same data is presented to the cache controller, upon determining that the data is not present in the corresponding level of the memory hierarchy, the cache controller typically queries the buffer to determine whether the memory address of the data being requested is stored there. If the main memory address for the requested data is present in the memory buffer, indicating that a request for the data is already pending, the cache controller will not issue an additional request for the data. However, the memory buffer requires a relatively large amount of space, and can consume a relatively large amount of power.

<CIT>) relates to a system cache with a data pending state for cache misses. A cache line storage location is allocated in the system cache for a miss and the state of the cache line storage location is set to data pending. A subsequent request that hits to the cache line storage location will detect the data pending state and as a result, the subsequent request will be sent to a replay buffer. When the fill for the original miss comes back from external memory, the state of the cache line storage location is updated to a clean state. Then, the request stored in the replay buffer is reactivated and allowed to complete its access to the cache line storage location. <CIT>) discloses an apparatus and method for a distributed non-blocking multi-level cache. <CIT> discloses a storage system and device having a tag storage device with multiple tag entries associated with the same data storage line for data recycling.

The invention relates to a method and to a processor as defined by the appended claims.

<FIG> illustrate techniques for improving memory management efficiency by indicating the pendency of a memory access request for data at the cache entry that is assigned to store the data in response to the memory access request. The processing system includes a processor and a memory hierarchy, including main memory at the top of the hierarchy, and one or more caches of memory at lower levels of the memory hierarchy to store subsets of the data stored at main memory. While executing instructions, the processor issues requests for data to the cache most proximal to the processor. In response to a cache miss, a cache controller issues a memory access request for the data to a higher level of the memory hierarchy. Further, the cache controller identifies an entry of the cache to store the data in response to the memory access request, and stores an indication that the memory access request is pending at the identified cache entry. If the cache controller receives a subsequent memory access request for the data while the memory access request is pending at the higher level of the memory hierarchy, the cache controller identifies that the memory access request is pending based on the indicator stored at the entry. By employing the cache entry that is to store the data, rather than a separate miss address buffer, to store the indicator of the pendency of the memory access request, the processor is able to save both circuit area and power.

To illustrate via an example, one of the caches of the processor (e.g., a level <NUM> (L3) cache) is located in the memory hierarchy just below the main memory of the processing system. During the time that data that is the subject of a cache miss at the L3 cache is being fetched from main memory, subsequent requests for the same data may be presented to the L3 cache. In order to avoid creating additional memory access requests for the same data while a memory access request for the data is pending, which would consume system resources without improving processor performance, the cache controller of the L3 cache immediately assigns a cache entry to store data while the data is being fetched from main memory, and also stores at the cache entry an indicator that a memory access request for the data is pending at the main memory. In some embodiments, the indicator is a miss tag including the main memory address of the data being fetched as well as status information indicating that the data is the subject of a pending memory access request. The cache controller also stores in a side structure, such as a buffer, a cache entry tag comprising a data identifier and location information for the assigned cache entry.

If a subsequent request for the same data is received at the L3 cache while the data is still in the process of being fetched from main memory, the cache controller checks the cache memory to determine whether the data is already stored at the cache memory, and identifies that the cache entry stores the miss tag, indicating that the requested data is already the subject of a memory access request. In response, the cache controller places the memory access request in a pending state to await the storage of the data at the cache entry.

Once the requested data has been retrieved from the main memory, the cache controller queries the side structure for the data identifier for the retrieved data to determine if a cache entry tag corresponding to the data identifier is present. Upon reading the cache entry tag corresponding to the data, the processing system stores the retrieved data at the cache entry indicated by the cache entry tag, and updates the status information to a valid state to indicate that the data is now present in the cache. In addition, the cache controller satisfies any pending memory access requests that target the data. Thus, the L3 cache uses the cache entry itself to store the indicator of the pendency of the memory access request, rather than a separate buffer, thereby saving both power and circuit area.

<FIG> illustrates an example of a processing system <NUM> configured to store an indication of the pendency of a memory access request at a cache entry that is to store data responsive to the memory access request in accordance with some embodiments. As such, the processing system <NUM> may be employed in any of a number of devices, such as a personal computer, workstation, mobile device such as a smartphone, a video game console, smart TV and the like. As described further herein, the processing system <NUM> includes a processor core <NUM>, one or more levels of cache memory (e.g., cache memory <NUM>), a cache controller <NUM>, a pending miss buffer <NUM>, and a main memory <NUM>.

The processor core <NUM> includes one or more instruction pipelines to execute instructions, organized in the form of computer programs, thereby carrying out tasks on behalf of an electronic device. While the processor core <NUM> may have some amount of integral memory, for example, in the form of registers, such memory is typically limited in storage capacity. Accordingly, in order to execute instructions, the processor core <NUM> stores and retrieves data from the memory hierarchy of the processing system <NUM>, including the one or more levels of cache memory (herein represented as a single level of cache memory <NUM>) and main memory <NUM>. In particular, in the course of executing instructions, the processor core <NUM> generates operations, referred to as memory access requests <NUM>, to store (a store operation) or load (a read operation) data from the memory hierarchy. The one or more levels of cache memory <NUM> and main memory <NUM> work together to satisfy the memory access requests <NUM>, as described further herein.

The cache memory <NUM> is a memory module that stores data for access by the processor core <NUM>. In at least one embodiment, the cache memory <NUM> includes a set of entries, each of which stores an associated unit of data, referred to as a cache line. In some embodiments, each of the one or more levels of cache memory <NUM> are set associative caches, wherein each cache is divided into a number of sets. Each set includes a number of data positions, or ways, with each way corresponding to a cache entry that stores a cache line. Each set only stores a cache line associated with subset of memory addresses, wherein the subset associated with a set is identified by the corresponding cache controller based on a portion of the memory address referred to as the index. By employing set associativity, the one or more levels of cache memory <NUM> facilitate relatively quick identification of cache misses and cache hits.

The cache controller <NUM> is a module configured to receive memory access requests <NUM> for data from the processor core <NUM> and search the cache memory <NUM> to determine if one of the cache entries stores a cache line associated with the memory address targeted by the memory access request <NUM>. If the requested cache line is found in the cache memory <NUM>, a cache hit has occurred. In the event of a cache hit, the cache controller <NUM> satisfies the memory access request <NUM> by, in the case of a read operation, providing the requested cache line from the cache memory <NUM> to the processor core <NUM> or, in the case of a write operation, storing the write data to the cache entry.

If the requested cache line is not found in the cache memory <NUM>, a cache miss has occurred. In the event of a cache miss at the cache memory <NUM>, the cache controller <NUM> provides the memory access request <NUM> to the main memory <NUM>. In response to the memory access request <NUM>, the main memory <NUM> retrieves the cache line at the main memory address targeted by the request <NUM> and provides the cache line to cache memory <NUM>, where the memory access request <NUM> is satisfied.

In some embodiments, the cache memory <NUM> is sized such that it cannot store, at a given point in time, all the data that is requested by the processor core <NUM>, thereby requiring data to be transferred through the memory hierarchy as described above. Each time a cache miss occurs and the requested cache line must be fetched from main memory <NUM>, the retrieval of the cache line from main memory takes time, during which the processor core <NUM> may receive one or more additional requests for the same cache line. To reduce the inefficiency that would result from generating multiple memory access requests for the same cache line while an outstanding access request for the cache line is pending, the processing system <NUM> tracks outstanding access requests at the cache memory <NUM>.

To illustrate, in operation, the processor core <NUM> sends a memory access request <NUM> to the cache controller <NUM>, which searches the cache memory <NUM> for the requested cache line. If the requested cache line is found in the cache memory <NUM>, it is provided to the processor core <NUM>. If the requested cache line is not found in the cache memory <NUM>, the cache controller <NUM> provides the memory access request <NUM> to the main memory <NUM>.

While the requested cache line is in the process of being retrieved (fetched) from main memory <NUM> by the processor core <NUM>, the cache controller <NUM> assigns a cache entry to the cache line that is being fetched. In some embodiments, the cache controller <NUM> assigns the cache entry corresponding to the cache set and way in which the cache line will be stored once it has been retrieved from main memory <NUM>. The cache controller <NUM> stores at the cache entry a miss tag <NUM> including the main memory address of the cache line that is being fetched, and a status bit indicating that the cache line is the subject of a pending cache miss. The cache controller <NUM> also stores in as a pending miss buffer <NUM> a cache entry (CE) tag <NUM> including the data index and location information concerning the cache entry that has been assigned to the cache line that is being fetched. For example, in some embodiments, the cache controller <NUM> stores in the pending miss buffer <NUM> a cache entry tag <NUM> including the data index and the cache way that has been assigned in cache memory <NUM> to the cache line that is being fetched.

The pending miss buffer <NUM> is a memory module that stores cache entry tags <NUM> including data index and cache entry location information for cache entries that have been assigned by the cache controller <NUM> to store cache lines that are the subject of outstanding access requests. In some embodiments, the pending miss buffer <NUM> is configured to store cache entry tags including the data index and cache way that has been assigned for each cache line that is in the process of being fetched from main memory <NUM>. In some embodiments, each cache entry tag in the pending miss buffer <NUM> including a data index and assigned cache way is smaller (i.e., requires fewer bits) than the full main memory address of the cache line that is in the process of being fetched from main memory <NUM>.

In the event that, while the first memory access request <NUM> for the cache line is still in the process of being fulfilled from main memory <NUM>, a subsequent memory access request <NUM> for the cache line is received by the cache controller <NUM> from the processor core <NUM>, the cache controller <NUM> searches the cache memory <NUM> to determine if one of the cache entries contains the cache line associated with the memory address targeted by the subsequent memory access request <NUM>. In this event, the cache controller <NUM> identifies at the cache entry the main memory address of the cache line that is being fetched and the status bit indicating that the cache line is the subject of a pending cache miss. Based on its reading of the status bit, the cache controller will not forward the subsequent memory access request <NUM> for the requested cache line to the main memory <NUM>, but will instead resume its other tasks.

When the main memory <NUM> retrieves the cache line at the main memory address targeted by the request and provides the cache line to cache memory <NUM>, the cache controller <NUM> compares the data index of the cache line against the cache entry tags <NUM> stored in the pending miss buffer <NUM>. The cache controller matches the data index of the cache line to the stored cache entry tag, and reads from the cache entry tag <NUM> the cache entry in the cache memory <NUM> that has been assigned to store the cache line. The cache controller <NUM> stores the cache line at the previously assigned set and way of the cache entry and updates the status bit to a valid state, indicating that the cache line is present in the cache memory <NUM>.

<FIG> illustrates an example of the cache controller <NUM> storing a miss tag <NUM> at a cache entry <NUM> in cache memory <NUM> in response to a cache miss, and generating and storing a cache entry tag <NUM> in the pending miss buffer <NUM>. The cache controller <NUM> receives a request for a cache line from the processor (not shown), and searches the cache memory <NUM> to determine if one of the cache entries stores a cache line associated with the memory address targeted by the memory access request. In this example, the requested cache line is not present in the cache memory <NUM>, so the cache controller <NUM> provides the memory access request to the main memory (not shown). While the memory access request to the main memory is pending, the cache controller <NUM> assigns a cache entry <NUM> to the cache line that is the subject of the pending memory access request and generates a miss tag <NUM> including the main memory address of the cache line and a status bit indicating that the cache line is the subject of a pending memory access request. The cache controller <NUM> stores the miss tag <NUM> at the assigned cache entry <NUM> in the cache memory <NUM>.

The cache controller <NUM> also generates a cache entry tag <NUM> including the data index for the cache line that is the subject of the pending memory access request and the cache entry <NUM> that it has assigned to the cache line. The cache controller <NUM> stores the cache entry tag <NUM> in the pending miss buffer <NUM>. Typically, a cache entry has a status bit, which indicates whether the cache entry is filled with a valid cache line. In this example, the miss tag <NUM> stored at the cache entry <NUM> includes a status bit indicating that the data associated with the main memory address stored in the miss tag <NUM> the subject of a pending memory access request (a "miss pending").

<FIG> illustrates an example of the processor <NUM> issuing a subsequent request <NUM> to the cache controller <NUM> for a cache line that is the subject of a pending memory access request in accordance with some embodiments. The cache controller <NUM> receives the subsequent request <NUM> and searches the cache memory <NUM> for the requested cache line. The cache controller <NUM> matches the main memory address of the requested cache line to the miss tag <NUM> that is stored at the cache entry <NUM>. The cache controller <NUM> reads the status bit (not shown) of the miss tag <NUM> and determines that the requested cache line is already the subject of a pending memory access request.

Having determined that the requested cache line is already in the process of being retrieved from main memory (not shown), the cache controller <NUM> treats the result of the search of the cache memory <NUM> as a cache hit that has already been copied to the processor (not shown), and resumes its other tasks without creating an additional request to main memory for the requested cache line. Because the cache controller <NUM> is able to determine from its search of the cache memory <NUM> that the requested cache line is the subject of a pending miss, the cache controller <NUM> does not need to check the pending miss buffer (not shown) to determine whether the requested cache line is the subject of a pending miss, thereby conserving power.

<FIG> illustrates an example of the cache controller <NUM> issuing a memory access request <NUM> to main memory <NUM>, copying the requested data <NUM> from the main memory address at which the data <NUM> is stored in main memory <NUM>, and storing the data <NUM> at the cache entry (not shown) in cache memory <NUM> indicated by the cache entry tag <NUM> stored in the pending miss buffer <NUM>. In response to a memory access request <NUM>, the main memory <NUM> retrieves the cache line at the main memory address targeted by the request <NUM> and provides the data <NUM> to the cache controller <NUM>. The cache controller <NUM> compares the data index of the data <NUM> to the cache entry tags stored in the pending miss buffer <NUM>. When the cache controller <NUM> matches the data index of the data <NUM> to the index of the cache entry tag <NUM>, the cache controller <NUM> reads the cache entry from the cache entry tag <NUM>. The cache controller <NUM> stores the data <NUM> at the location in the cache memory <NUM> that was indicated by the cache entry tag <NUM>. The cache controller <NUM> updates the status bit of the entry at the cache entry to a valid state, indicating that the data <NUM> is present in the cache memory <NUM>.

<FIG> illustrates an example of a cache entry tag <NUM>. The cache entry tag <NUM> includes a data index <NUM> for the cache line that is the subject of a memory access request and the cache way <NUM> of the cache entry (not shown) assigned to the cache line. The data index <NUM> includes a subset of the main memory address of the cache line, and is shorter than the full main memory address. The cache way <NUM> includes the way in the cache memory (not shown) that has been assigned to the cache line that is the subject of a memory access request, and which is temporarily occupied by the miss tag (not shown). The cache entry tag <NUM> is smaller (requires less storage capacity) than the full main memory address of the cache line that is the subject of the memory access request.

<FIG> illustrates an example of a miss tag <NUM>. For a fully-associative cache, the miss tag <NUM> includes the full main memory address <NUM> of the cache line that is the subject of a memory access request and a status bit <NUM>, which indicates that the cache line associated with the main memory address <NUM> is the subject of a pending miss. For a set-associative cache, the miss tag <NUM> includes a portion of the full main memory address <NUM> of the cache line that is the subject of a memory access request and a status bit <NUM>, which indicates that the cache line associated with the main memory address <NUM> is the subject of a pending miss.

<FIG> illustrates a method <NUM> of handling subsequent memory access requests for data that is already the subject of a pending memory access request. At block <NUM>, the cache controller receives a request for data. At block <NUM>, the cache controller searches the cache memory for the requested data, and determines whether the data is present in the cache memory or a miss tag for the requested data is present in the cache memory.

If neither the requested data nor a miss tag for the requested data is present in the cache memory, at block <NUM>, the cache controller sends a memory access request to main memory to fetch the requested data from main memory. At block <NUM>, the cache controller assigns a cache entry to the requested data. At block <NUM>, the cache controller generates a miss tag including the main memory address of the requested data and a status bit indicating that the data is the subject of a cache miss and stores the miss tag at the cache entry. At block <NUM>, the cache controller generates a cache entry tag including the index for the requested data and the assigned cache entry, and stores the cache entry tag in the miss pending buffer. At block <NUM>, the cache controller receives the requested data from main memory. At block <NUM>, the cache controller queries the miss pending buffer for a cache entry tag matching the data index of the requested data and reads the cache entry information from the cache entry tag. At block <NUM>, the cache controller copies the requested data to the cache entry specified in the cache entry tag and updates the status bit for the cache entry to a valid state.

Returning to block <NUM>, if the cache controller searches the cache memory for the requested data and determines that the cache memory contains either a miss tag corresponding to the requested data or that it contains the requested data, at block <NUM>, the cache controller determines whether the cache entry for the requested data is a miss tag or the requested data. If the cache entry contains a miss tag for the requested data, at block <NUM>, the cache controller treats the miss tag as it would a cache hit that had already been copied to the processor, and continues executing other instructions pending the memory access request for the requested data. If, at block <NUM>, the cache controller determines that the cache entry for the requested data contains the requested data, at block <NUM> the cache controller copies the requested data to the processor.

The software includes the instructions and certain data that, when executed by the one or more processors, manipulate the one or more processors to perform one or more aspects of the techniques described above. The non-transitory computer readable storage medium includes, for example, a magnetic or optical disk storage device, solid state storage devices such as Flash memory, a cache, random access memory (RAM) or other non-volatile memory device or devices, and the like.

Claim 1:
A method, comprising:
in response to a cache miss for a first request (<NUM>) for a first data at a cache (<NUM>), assigning a cache entry (<NUM>) of the cache to store the data;
while the data is being retrieved from a different level of memory (<NUM>) to the cache,
storing an indicator (<NUM>) at the cache entry that the first request is pending at the cache, the indicator comprising a main memory address of the first data and a status bit indicating that the first data is a subject of a pending cache miss; and
storing an identifier (<NUM>) including a data index and cache entry location information of the cache entry at a buffer (<NUM>);
in response to receiving at the cache a second request (<NUM>) for the data while the data is being retrieved to the cache (<NUM>), reading the indicator at the cache entry; and
in response to identifying based on the indicator that the first request (<NUM>) is pending at the cache, placing the second request (<NUM>) for the first data in a pending state until the data has been retrieved to the cache and treating the second request (<NUM>) as a cache hit that has already been copied to a processor.