Patent Description:
A cache is a device that stores data retrieved from memory or data to be written to memory for one or more different hardware devices in a system. The hardware devices can be different components integrated into a system on a chip (SOC). In this specification, the devices that provide read requests and write requests through caches will be referred to as client devices. Some caches service memory requests for multiple different client devices integrated into a single system.

Caches can be used to reduce power consumption by reducing overall requests to the main memory. In addition, as long as client devices can access the data they need in the cache, power can further be saved by placing the main memory as well as data paths to the main memory in a low-power state. Therefore, cache usage is correlated with overall power consumption, and increasing cache usage results in a decrease in overall power consumption. Therefore, devices that rely on battery power, e.g., mobile computing devices, can extend their battery life by increasing cache usage for the integrated client devices.

A cache placement policy determines how a memory block is placed in the cache. For a set-associative cache, a least recently used (LRU) replacement policy can be used. In conventional LRU replacement implementations, a system fits all the cache replacement operations in the same clock cycle for a transaction. However, because the execution time for most of the operations in the LRU replacement policy increases with the number of cache lines in a set of the cache, it can be challenging to fit all the operations for the transaction into a single clock cycle for a set-associative cache with high associativity. <CIT> describes a first cache storage, a second cache storage, wherein the second cache storage includes a first portion operable to store a first set of data evicted from the first cache storage and a second portion, a cache controller coupled to the first cache storage and the second cache storage and operable to receive a write operation, determine that the write operation produces a miss in the first cache storage, and in response to the miss in the first cache storage, provide write miss information associated with the write operation to the second cache storage for storing in the second portion. <CIT>describes a method which determines to generate a prefetch request, obtains a confidence value for target data associated with the prefetch request, writes the target data into a set of the n-way set associative cache memory, modifies an n-position array of the cache memory, such that a particular one of n array positions identifies one of the n ways, wherein the particular one of the n LRU array positions is determined by the confidence value.

This specification describes a cache system including multiple sets of cache lines and replacement logic configured to implement a two-stage least recently used (LRU) replacement policy. By performing the LRU replacement in two stages, the cache system overcomes some limitations of conventional LRU replacement implementations, and improves the time efficiencies for performing multiple cache transactions.

In one particular aspect of the specification, a cache system is provided. The cache system includes multiple sets with each set having multiple respective ways, and replacement logic configured to implement a two-stage least recently used (LRU) replacement computation. The two-stage LRU replacement computation causes the cache to perform: a first stage during which the cache computes an LRU way for a set, and a second stage during which the cache updates an LRU data structure with information of a transaction accessed way.

In some implementation of the cache system, the cache is configured to perform the two-stage LRU replacement computation in consecutive clock cycles.

In some implementation of the cache system, the cache is configured to implement an LRU replacement policy using the computed LRU way.

In some implementation of the cache system, the replacement logic comprises a plurality of nodes storing respective way values for each set, and wherein performing the second stage comprises shifting the way values stored between the nodes for the set.

In some implementation of the cache system, to perform the second stage, the cache system is configured to update each node for a set with data the node already stores or data shifted from another node.

In some implementation of the cache system, when performing the first stage for a current transaction, in response to a hazard condition resulted from the second stage of a previous transaction being performed on a same particular set, the cache system performs hazard resolution for the current transaction.

In some implementation of the cache system, performing the hazard resolution for the current transaction includes: in response to determining that all of the respective ways in the particular set are eligible for replacement, determining the LRU way for the current transaction based on the LRU data structure after the LRU data structure has been updated for the previous transaction.

In some implementation of the cache system, the replacement logic is configured to, in response to determining that not all of the respective ways in the particular set are eligible for replacement: determining hazard-resolved eligible nodes from the plurality of nodes; selecting an eligible node from the hazard-resolved eligible nodes; and determining the LRU way using the way value stored in the selected eligible node.

In some implementation of the cache system, the replacement logic is configured to start determining the hazard-resolved eligible nodes from the plurality of nodes before the second stage of the previous transaction has been completed.

In some implementation of the cache system, determining the hazard-resolved eligible nodes from the plurality of nodes includes: generating un-resolved node data that identifies eligible nodes from the plurality of nodes based on eligible ways and the LRU data structure before the LRU data structure been updated by the second stage of the previous transaction; and shifting the un-resolved node data using shift information generated during the second stage of the previous transaction to generate hazard-resolved node data that identifies the hazard-resolved eligible nodes.

In another aspect of the present specification, a method for performing LRU replacement computation is provided. The method is performed by the cache system described above and includes the operations described above.

The subject matter described in this specification can be implemented in particular implementations so as to realize one or more advantages. For example, in some implementations, by performing the two-stage LRU replacement policy in two consecutive clock cycles, the cache system improves the time efficiencies for performing multiple cache transactions. Further, in some implementations, when a hazard results between the current transaction and the previous transaction, the system can start the hazard resolution process for the current transaction before the LRU update of the previous transaction has been finished, to minimize the time impact of hazard resolution. The increased timing efficiency can help implement advanced LRU replacement policy for set-associative caches with high associativity numbers.

Aspects of the disclosed subject matter are set out in the appended independent claims.

A cache placement policy determines how a memory block is placed in the cache. This specification focuses on the set-associative cache placement policy, where the cache is divided into multiple sets and each set includes multiple cache lines.

<FIG> shows a cache system <NUM>. The cache system <NUM> may be a part of a processing system, such as a system on a chip (SOC) communicatively coupled to memory devices. In particular, the cache system <NUM> is a set-associative cache and includes multiple sets <NUM>. Each set <NUM> includes multiple respective cache lines <NUM>.

A cache line, also known as a way, is the unit of data transfer between the cache and another memory device, e.g., the main memory of the processing system. All cache lines in the set have a fixed size, e.g., <NUM> bytes. A processor will read or write an entire cache line when any location in the <NUM>-byte region is read or written.

The cache system <NUM> further includes a cache transaction controller <NUM> that manages cache transactions of the cache system <NUM>. In this specification, a cache transaction refers to a process of accessing the cache system with a request for a specific memory block. An example cache transaction process will the described with reference to <FIG>. In general, the cache transaction controller <NUM> maps the requested memory block to a specific set <NUM> using the index bits derived from the address of the memory block. The cache transaction controller <NUM> then performs a tag check to determine whether the requested memory block is already placed in one of the cache lines <NUM>. The tag check is performed based on the tag data <NUM> that stores the tags of all the cache lines <NUM> of the memory device. In particular, the cache transaction controller <NUM> compares the tag bits of the address of the memory block with the tags of the cache lines <NUM> in the mapped set <NUM>. The tag check returns a "cache hit" if the memory block tag matches any of the cache lines in the mapped set. Otherwise, the tag check returns a "cache miss".

In case of a "cache miss", the cache transaction controller <NUM> requests the memory block from another memory device, such as from the main memory of the processing system or from the next-level cache of the processing system, and places the memory block in a selected cache line <NUM> of the mapped set <NUM>. If all the cache lines <NUM> in the mapped set <NUM> have already been allocated (i.e., have been previously placed with respective memory blocks), the cache transaction controller <NUM> uses the new data read from the external memory device to replace the block stored in a cache line identified through a replacement policy.

In particular, the system <NUM> uses the cache replacement logic <NUM> to implement a least recently used (LRU) replacement policy that selects the least recently used cache line (out of K-ways) for replacement. This process requires keeping track of the recency of each cache line <NUM> with respect to the usage of all the other cache lines in a particular set <NUM>. Thus, the system <NUM> maintains the LRU data <NUM> that specifies the recency information for each cache line <NUM> in each set <NUM> of the system <NUM>.

The cache replacement logic <NUM> implements the LRU replacement computation in two stages. During the first stage, the cache system <NUM> determines the least recently used cache line (termed as the LRU way in this application) based at least on the current LRU data <NUM>. The LRU way is selected for replacement. During the second stage, the cache system <NUM> updates the LRU data <NUM> based on the information of the transaction accessed way, so the LRU data <NUM> is up to date for the next transaction.

<FIG> illustrates an example process <NUM> for performing a cache transaction. For convenience, the process <NUM> will be described as being performed by a cache system, such as the cache system <NUM> of <FIG>.

Before performing the process <NUM>, the system has determined the set for the cache transaction. The output of the process <NUM> specifies a particular cache line (termed as the "accessing way" in this specification) in the set for accessing the memory block specified in the cache transaction request.

After receiving the cache transaction request specifying the memory block, the system performs a tag check in step <NUM>. In particular, the system compares the tag bits associated with the address of the memory block with the tags of the cache lines in the set.

The system determines whether the tag check results in a cache HIT or MISS in step <NUM>. That is, if the tag bits associated with the address of the memory block match the tag of one of the cache lines in the set, the system determines that the tag check result is a cache HIT. For convenience, the cache line that has the tag matching the memory block tag is termed as "HIT way". If the tag bits associated with the address of the memory block do not match any of the tags of the cache lines in the set, the system determines that the tag check result is a MISS.

If the system determines that the tag check result is a cache HIT, the system uses the HIT way for the transaction, and thus assigns the accessing way to the HIT way in step <NUM>.

If the system determines that the tag check result is a cache MISS, this means that the data in the specified memory block has not been loaded into any of the cache lines in the set, and the system needs to request the data from a next level in the memory hierarchy, and load the data into a selected cache line in the set.

The system checks for a cache line in the set that has not been occupied in step <NUM>. For convenience, an unoccupied cache line is termed the "free way". If the system determines that a free way is available in step <NUM>, the system uses the free way for performing the transaction for the cache MISS scenario. That is, the system assigns the accessing way to the free way in step <NUM>.

If the system determines that a free way is not available in step <NUM>, this means that all the cache lines in the set have been occupied, and the system needs to identify a cache line for replacement through the replacement policy, and place the data in the cache line identified for replacement.

Because the system implements the LRU replacement policy, the system computes the LRU way in step <NUM>. The system assigns the accessing way to the LRU way in step <NUM>.

Once the accessing way is determined (by steps <NUM>, <NUM>, or <NUM>), the system updates the LRU data in step <NUM>. The LRU data tracks the recency of the cache lines in the set, i.e., specifies how recently a particular cache line has been accessed for a transaction compared to other cache lines in the set. The update process will be described in more detail with references to <FIG>.

In conventional LRU replacement implementations, a system fits all the operations shown in <FIG> in the same clock cycle for a transaction. In this case, the time needed for completing these operations can be estimated as: <MAT>.

Here, <NUM> (< operation >) denotes the timing depth for completing the <operation>, C is a constant time delay for operations such as selecting one of the HIT way/free way/compute LRU way branches shown in <FIG>.

Note that each of the three terms O(determine hitway), O(select freeway), and O(compute LRU way) increases when the total number of cache lines in the set increases. That is, the time for determining the accessing way increases with increased cache associativity. When the cache associativity is significant (e.g., when the total number of cache lines in the set exceeds a threshold), it can be challenging to fit all the operations for the transaction into a single clock cycle.

In order to overcome the limitations of conventional LRU replacement implementations, the system described in this specification performs the LRU replacement using a <NUM>-stage scheme. That is, the system implements the two-stage LRU replacement policy in consecutive clock cycles.

In the first stage, the system determines the accessing way. In the second stage, the system updates the LRU data.

Thus, the required time for the first clock cycle is: <MAT>.

The time required for the second clock cycle is: <MAT>.

By splitting the time required for performing the operations for the transaction into the two clock cycles, the system can generally improve the time efficiencies for performing the cache transaction. For example, after the system has determined the accessing way in the first stage for a particular transaction, instead of waiting for the LRU data update to finish for the particular transaction in the second stage, the system can start the first stage for the next cache transaction, i.e. start determining the accessing way for the next cache transaction while performing the second stage for the particular cache transaction. Thus, second stage of a current transaction and the first stage of the next transaction can be performed in parallel. This scheme generally shortens the total time required for performing the multiple cache transactions.

<FIG> illustrates clock cycles for performing cache operations for <NUM> cache transactions. The first transaction (txt <NUM>) is performed on a first set (Set A) in the cache. The second transaction (txt <NUM>) is performed on a second set (Set B) in the cache. The third transaction (txt <NUM>) is also performed on the second set (Set B).

As shown in <FIG>, at clk = <NUM>, the system performs the first stage of the first transaction. At clk = <NUM>, the system performs the second stage of the first transaction and the first stage of the second transaction. At clk = <NUM>, the system performs the second stage of the second transaction and the first stage of the third transaction.

Note that at clk = <NUM>, the system performs two stages, i.e., the second stage of the first transaction and the first stage of the second transaction, in parallel. This overlap in timing does not result in a hazard since the first and the second transactions are performed on different sets of the cache, i.e., the first transaction being performed on Set A and the second transaction being performed on Set B. In this specification, a hazard refers to a problem with the instruction pipeline when the next instruction cannot correctly execute in the following clock cycle, e.g., due to instructions that exhibit data dependence upon modified data in different stages of a pipeline. Because the first and the second transactions are performed on different sets, there is no data dependence between the two transactions, and hazards do not occur.

By contrast, the overlap in the timing of the two stages at clk = <NUM> may result in hazard because both the second and the third transactions are performed on the same set (Set B). In the cycle of clk = <NUM>, the first stage of the third transaction may need to use the LRU data of the set to determine the accessing way (e.g., for computing LRU way), while the LRU data of the same set is being updated in the second stage of the second transaction. This results in a hazard. Therefore, in order to correctly compute the LRU way for the third transaction, the hazard needs to be resolved. Example processes and implementations for resolving the hazard will be described with reference to <FIG> and <FIG>.

<FIG> shows an example data structure <NUM> for storing the LRU data. The data structure includes a sequence of K nodes having one-to-one correspondence to the K cache lines in the set. Each node <NUM> stores a way value <NUM> identifying the corresponding cache line. Each node <NUM> is associated with a respective node index e.g., k = <NUM>,<NUM>,. , (K - <NUM>). The respective node index k of a node <NUM> specifies the recency of the cache line identified by the way value <NUM> of the node <NUM>. For example, the cache line identified by the way value stored in the <NUM>th node is the least recently accessed cache line in the set, and the cache line identified by the way value stored in the (k - <NUM>)th node is the most recently accessed cache line in the set.

During the processing of updating the LRU data, i.e., during the second stage of a cache transaction, the system updates the LRU data by shifting the way values <NUM> stored in the sequence of nodes <NUM>.

<FIG> illustrates an example process for updating the LRU data stored in a data structure, e.g., in the sequence of nodes shown in <FIG>. In <FIG>, the top row of nodes store way values before the LRU data update. The bottom row of nodes store way values after the LRU data update. Both rows of nodes are arranged in decreasing order of recency from left to right. That is, the left-most node of each row stores the way value of the most recently used (MRU) cache line, and the right-most node of each row stores the way value of the least recently used (LRU) cache line.

In the example shown in <FIG>, the accessing way for the transaction is identified by the way value "<NUM>" stored in the 4th node from the left of the top row. The system updates the LRU data to reflect the change in the recency by moving the way value "<NUM>" to the MRU node and shifting the way values stored in the 1st through 3rd nodes from the left to the right by one node, resulting in the way values shown in the bottom row.

<FIG> shows an example process <NUM> for performing hazard resolution in LRU computation. For convenience, the process <NUM> will be described as being performed by a cache system, such as the cache system <NUM> of <FIG>.

When the system starts to compute the LRU way for a current transaction, if the current transaction is mapped to the same set that a previous transaction is mapped to, and the previous transaction has been started one clock cycle before the current transaction, data hazard may occur and the system performs the process <NUM> to resolve the hazard.

As an illustrative example, referring to <FIG>, when Transaction #<NUM> (txn3) is the current transaction performed on Set B, data hazard may result between computing the LRU way (T1 stage) for txn3 and updating the LRU data (T2 stage) of the previous transaction (txn2) that is also performed on Set B.

Referring back to <FIG>, in step <NUM> of the hazard resolution process <NUM>, the system determines if all the cache lines in the set are eligible for replacement. This step is needed because in some scenarios, the cache system can be accessed by multiple client devices. In this specification, a client device is a device that issues read requests and write requests to the cache system to access data of the cache system. When the cache system is being accessed by multiple client devices, each client device may only use a subset of cache lines in the current set for replacement. Thus, for the current transaction associated with a particular client device, only a subset of cache lines are eligible for replacement, and the system can compute the LRU way only from the eligible cache lines.

If the system determines that all the cache lines in the set are eligible for replacement, the system can simply perform step <NUM> to wait for the LRU update to finish, before performing step <NUM> to determine the LRU way for the current transaction based on the updated LRU data (that has been updated for the previous transaction). For example, in step <NUM>, the system can simply determine the LRU way that is specified by the way value <NUM> stored in the LRU node (node <NUM>) of the LRU data <NUM> as shown in <FIG>, where all the LRU data nodes <NUM> have been updated for the previous transaction. Since the LRU way is selected based on the up-to-date LRU data with regard to the previous transaction, the selected LRU way is hazard resolved.

As an illustrative example, referring to <FIG>, to resolve the hazard between the current transaction (txn3) and the previous transaction (txn2), when all the cache lines in Set B are eligible for replacement, the system can simply wait for the LRU data update of txn2 in clk = <NUM> to finish before starting computing the LRU way for txn3.

Referring back to <FIG>, if the system determines that not all the cache lines in the set are eligible for replacement, i.e., only a subset of cache lines in the set are eligible for replacement for the current transaction, the system needs to identify the eligible subset of cache lines before determining the LRU way from the eligible cache lines. Since the recency information of the cache lines can be stored in the respective LRU data nodes (e.g., as shown in <FIG>), the system can determine the eligible cache lines by determining the eligible set of LRU data nodes, and using the respective stored way values <NUM> stored in the eligible LRU data nodes to identify the eligible cache lines. Here, an eligible LRU data nodes refers to an LRU data node that stores a way value identifying an eligible cache line.

Since the process <NUM> is performed for the current transaction during the same clock cycle when the previous transaction is updating the LRU data, to correctly identify the eligible ways, the system needs to determine the hazard-resolved eligible nodes in step <NUM>. Here, a hazard-resolved eligible node refers to an LRU data node that stores an up-to-date way value that identifies an eligible cache line. The up-to-date way value refers to the way value that is consistent with the updated LRU data from the previous transaction.

In some implementations, in order to improve time efficiency, the system starts the step of determining the hazard-resolved eligible nodes for the current transaction before the LRU data update is completed for the previous transaction. This can be achieved by directly using the node shift information of updating the LRU data in the previous transaction. The node shift information specifies, for each node of the LRU data for the current set, whether the node is shifted (or to be shifted) by the LRU data update process for the previous transaction. An example implementation of determining the hazard-resolved eligible nodes in a time-efficient manner will be described with reference to <FIG>.

After the hazard-resolved eligible nodes have been determined in step <NUM>, the system selects the LRU node from the hazard-resolved eligible nodes in step <NUM>. The selected LRU node is the least recently used node among the set of hazard-resolved eligible nodes. In step <NUM>, the system determines the LRU way using the way value stored in the selected LRU node.

<FIG> shows an example hardware implementation <NUM> of an LRU cache replacement policy applied to the LRU data (i.e., respective way values for the cache lines in the set) stored in a sequence of nodes <NUM>. Similar to the data structure shown in <FIG>, the sequence of K nodes <NUM> are arranged according to the recency (with decreasing recency from left to right) of the cache lines identified by the respective way values stored in the nodes. That is, in the example shown in <FIG>, the leftmost node, i.e., node (K - <NUM>), stores the way value of the MRU cache line while the rightmost node, i.e., node <NUM>, stores the way value of the LRU cache line.

The circuit <NUM> includes a plurality of comparators <NUM>, a plurality of OR gates <NUM>, and a plurality of multiplexers <NUM>. The circuit receives as an input the accessing way <NUM> determined by the first stage of the cache transaction, and compares the accessing way <NUM> with each of the way values stored in the nodes <NUM> using a respective comparator <NUM>. The output of the comparator <NUM> is connected to a first input to a respective logic OR gate <NUM>.

For the convenience of description and without loss of generality, the way value stored in node k is compared with the accessing way <NUM> using the kth comparator <NUM>, where k = <NUM>,<NUM>,<NUM>,. , (K - <NUM>). The OR gate is present for the kth nodes, where k = <NUM>, <NUM>, <NUM>,. (K - <NUM>). For k > <NUM>, the output of the kth comparator <NUM> is connected to the first input of the kthOR gate, and the second input of the kth OR gate is connected to the output of the (k - <NUM>)th OR gate. For k = <NUM>, the output of the kth comparator <NUM> is connected to the first input of the kth OR gate, and the second input of the kth OR gate is connected to the output of the (k - <NUM>)th comparator. That is, the OR gate performs OR operation to the comparison results for the current node (node Zc) and all preceding nodes (nodes <NUM>, <NUM>,. k - <NUM>). If one of the nodes <NUM>, <NUM>,. k stores the way value that matches the accessing way <NUM>, the kth OR gate outputs "<NUM>". If none of the nodes <NUM>, <NUM>,. , k stores the way value that matches the accessing way <NUM>, the kth OR gate outputs "<NUM>".

The output of the kth OR gate is connected to the control input of a respective multiplexer <NUM> (MUX Zc). Here, k = <NUM>, <NUM>,. , (K - <NUM>). The control input of the rightmost multiplexer (MUX <NUM>) is connected to the comparison result for node <NUM>. The data inputs of MUX k are connected to the current node (node k) and the next node (node (k + <NUM>)), respectively, with k = <NUM>,. , (K - <NUM>). The data inputs of the leftmost multiplexer (MUX (k - <NUM>)) are connected to node (K - <NUM>) and the accessing way input, respectively. Thus, the multiplexers <NUM> output the updated LRU data <NUM>, i.e., the way values that have been shifted according to the control inputs of the multiplexers <NUM>.

The circuit <NUM> further outputs the control inputs of the multiplexers <NUM> as the shift flag signal <NUM>. The shift flag signal <NUM> includes a respective flag value for each particular LRU data node <NUM> for indicating whether a shift operation has been performed (or is to be performed) to the way value stored in the particular LRU data node <NUM>. As described with reference to <FIG>, the system can use the shift flag signal <NUM> for performing hazard resolution between two transactions.

<FIG> shows an example hardware implementation <NUM> for cache hazard resolution between the current cache transaction and previous cache transaction. In particular, the circuit <NUM> performs hazard resolution when the second stage (for LRU data update) of the previous cache transaction and the first stage (for LRU way computation) of the current cache transaction are being performed in the same clock cycle, as illustrated in the clk = <NUM> cycle of <FIG>, during which the previous transaction (txn2) performs the LRU data update and the current transaction (txn3) performs the LRU way computation.

Referring back to <FIG>, the circuit <NUM> receives several input signals, including: (<NUM>) the eligible ways <NUM> identifying the cache lines that are eligible for replacement in the set for the current transaction; (<NUM>) the accessing way <NUM> for the previous transaction; (<NUM>) the shift flag <NUM> outputted by the previous transaction and specifies shift information for the LRU data nodes for the LRU data update in the previous transaction; (<NUM>) the updated LRU data <NUM> that specifies the way values that have been updated by the previous transaction; (<NUM>) the un-updated LRU data <NUM> that specifies the way values that have not been updated by the previous transaction; and (<NUM>) the hazard flag <NUM> that indicates whether to perform hazard resolution between the previous transaction and the current transaction. The circuit <NUM> outputs the LRU way <NUM> computed for the current transaction.

Note that the input signals <NUM>, <NUM>, and <NUM> can be available for the current transaction before the LRU data update process has been completed for the previous transaction. Thus, the data processing using these input signals can be started for the current transaction before the LRU data update process has been completed for the previous transaction.

The circuit <NUM> includes a plurality of K × <NUM> multiplexers <NUM>, including MUX <NUM>, MUX <NUM>,. Each K × <NUM> multiplexer <NUM> receives the eligible ways <NUM> as the inputs. The eligible ways <NUM> can be encoded into "<NUM>" or "<NUM>" flags in a K-length vector for the K cache lines in the set, where a "<NUM>" flag indicates that the corresponding way is eligible for replacement and a "<NUM>" flag indicates that the corresponding way is not eligible for replacement. Each of MUX <NUM>,. , MUX (K - <NUM>) also obtains the way values from the respective LRU data nodes <NUM> as the control input. Note that way values received by the multiplexers MUX <NUM>,. , MUX (K - <NUM>) are outdated way values, i.e., way values that have not been updated by the second stage (T2) of the pervious transaction. The multiplexer MUX K receives the accessing way <NUM> as the second input. The outputs of the multiplexer <NUM> specify the un-resolved eligible LRU data nodes that have not been hazard-resolved. That is, the output of a multiplexer <NUM> specifies whether a corresponding node stores an outdated way value identifying one of the eligible cache lines. The outdated way value refers to the way value that has not been updated by the LRU data update process of the previous transaction.

The circuit <NUM> includes a plurality of multiplexers <NUM> that receive the shift flag signal <NUM> as control signal. The data inputs of each multiplexer <NUM> are connected to the outputs of two adjacent K × <NUM> multiplexer <NUM>. Thus, the multiplexers <NUM> performs data shifting on the un-resolved eligible LRU data nodes based on the shift flag <NUM> when there is a hazard. The hazard signal <NUM> indicates that the two transactions are performed to the same set i.e., there is hazard. Since the shift flag <NUM> has been outputted by the previous transaction and specifies shift information for the LRU data nodes for the previous transaction, the multiplexers <NUM> performs the same data shifting on the un-resolved eligible LRU data nodes as being performed by the previous transaction on the LRU data nodes. Thus, the outputs of the multiplexers <NUM> specify the hazard-resolved LRU data nodes.

The circuit <NUM> includes a fix priority arbiter <NUM> that performs a fixed priority arbitration among the hazard-resolved eligible nodes and select the LRU node <NUM>, i.e., the least recently used node as indicated by the node indexes, among the hazard-resolved eligible nodes. The circuit <NUM> can use another K × <NUM> multiplexer <NUM> receives the selected LRU node <NUM> as the control signal to select the LRU way <NUM> from the updated LRU data <NUM> or the un-updated LRU data <NUM>, depending on the hazard signal <NUM>.

As described above, the circuit <NUM> is configured to perform hazard resolution on the eligible LRU data nodes for the current transaction at least in part in parallel with the LRU data update process of the previous transaction. Thus, the time required for determining the accessing way in the first stage with hazard resolution can be estimated as: <MAT> where C2 is a constant small time delay for performing additional operations such as performing data shifting on the un-resolved eligible nodes.

Compared to the conventional implementation of the LRU replacement policy, the above-described implementation provides a time saving of: <MAT>.

Since the time for updating the LRU data increases with cache associativity, the time saving as indicated by Eq. (<NUM>) can be significant for set-associative caches having a large number of cache lines in each set.

As shown by the above analysis, by using the cache replacement process described with references to <FIG>, <FIG>, and <FIG>, and the hazard resolution process described with references to <FIG> and <FIG>, the described cache system can overcome certain limitations of conventional LRU replacement implementations, and improve the time efficiencies for performing multiple cache transactions.

Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification, or in combinations of one or more of them.

Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification, or in combinations of one or more of them.

Claim 1:
A cache (<NUM>) comprising:
multiple sets (<NUM>) with each set having multiple respective ways (<NUM>); and
replacement logic (<NUM>) configured to implement a two-stage least recently used (LRU) replacement computation, wherein the two-stage LRU replacement computation causes the cache to perform operations comprising:
a first stage during which the cache computes an LRU way for a set, and
a second stage during which the cache updates an LRU data structure (<NUM>) with information of a transaction accessed way;
characterized in that
performing the first stage for a current transaction comprises:
in response to a hazard condition resulted from the second stage of a previous transaction being performed on a same particular set, performing hazard resolution (<NUM>) for the current transaction.