Patent Description:
Caches and prediction logic employed in many processor-based systems, such as high performance central processing units (CPUs) and graphical processing units (GPUs), often use large static random access memory (SRAM) banks to store state data needed for operation. SRAMs are used in these types of devices because they offer density and power advantages over other structures (e.g., flip-flops or flop-trays, as non-limiting examples) which occupy more processor chip area and consume more power in comparison. Memory tables stored in such SRAM banks may hold hundreds or thousands of individual logical memory table entries, and thus may require careful management of the state data stored therein to be effective.

Many SRAM state management policies rely on a notion of "usefulness" for each memory table entry in a memory table stored in the SRAM. Under a "usefulness" approach, each memory table entry maintains a small "usefulness" indicator (e.g., a bit field providing two (<NUM>) to three (<NUM>) bits). A memory controller implementing an SRAM state management policy increments the usefulness indicator of a memory table entry whenever the memory table entry proves valuable (e.g., when the memory table entry provides a good prediction or prefetch suggestion). The usefulness indicator is likewise decremented in response to each misprediction or invalid prefetch suggestion that occurs. The value of the usefulness indicator at a given time thus represents a measure of the usefulness of the memory table entry. For example, in implementations in which the value of each usefulness indicator is considered to directly correlate with the usefulness of the corresponding memory table entry, a memory table entry with a usefulness indicator of two (<NUM>) bits having a value of 0b00 or 0b01 would be considered less useful than a memory table entry with a usefulness indicator having a value of 0b10 or 0b11.

However, usefulness indicators may also incur a number of disadvantages. Because memory tables tend to retain only the more useful entries, over time the differentiation among the usefulness indicators of the memory table entries decreases. This is because, when every memory table entry indicates that it is useful, the usefulness indicators themselves become less useful. Conventional solutions to this issue attempt to recalibrate the usefulness indicators across all memory table entries in one or more memory tables. For example, some approaches involve shifting each usefulness indicator to the right by one (<NUM>) bit, flash-clearing all usefulness indicator entries within a memory table to reset all memory table entries to the same initial state, or clearing a single bit within the usefulness indicator of each memory table entry. All of these potential solutions require multiple (e.g., often thousands) of memory table entries to be written within a very short period of time, which may be impracticable when using memory devices such as SRAMs. This issue may be mitigated by storing the usefulness indicators within separate additional SRAM or registers, but at the cost of additional processor chip area and power consumption. Consequently, it is desirable to provide a technique for recalibrating the usefulness indicators without requiring additional SRAM or registers to store the usefulness indicators, without incurring the area and power overhead of existing solutions, and without negatively impacting system performance.

<CIT> discusses a streaming media cache comprises a mass storage device configured to store streaming media data, a cache memory coupled to the mass storage device, the cache memory configured to store a subset of the streaming media data in a plurality of locations, and configured to provide the subset of the streaming media data to the processor, and a processor coupled to the mass storage device and to the cache memory, the processor configured to use a first retirement algorithm to determine a first location within the cache memory that is to be retired, configured to copy data from the mass storage device to the first location within the cache memory, con figured to monitor a cache memory age, wherein the cache memory age is determined in response to an age of data in at least a second location within the cache memory, configured to use a second retirement algorithm to determine a third location within the cache memory that is to be retired when the cache memory age falls below a threshold age, and configured to copy data from the mass storage device to the third location within the cache memory.

<CIT> discusses how the hit ratio of a cache memory in a data base processing system is improved by changing the priority of erasing cache data. A forward/backward pointer and a backward/forward pointer are contained as cache management information. At a completion of access of all the data of a table and before the next access of a table begins, the forward/backward pointer is changed to the backward/forward pointer and the backward/forward pointer is changed to the forward/backward pointer if the hit ratio is lower than expected ratio. Depending on the type of data access or external commands, the priority of erasing cache data is further changed to achieve a high hit ratio.

<CIT> discusses an embodiment wherein, a cache stores tags for cache blocks stored in the cache. Each tag may include an indication identifying which of two or more replacement policies supported by the cache is in use for the corresponding cache block, and a replacement record indicating the status of the corresponding cache block in the replacement policy. Requests may include a replacement attribute that identifies the desired replacement policy for the cache block accessed by the request. If the request is a miss in the cache, a cache block storage location may be allocated to store the corresponding cache block. The tag associated with the cache block storage location may be updated to include the indication of the desired replacement policy, and the cache may manage the block in accordance with the policy. For example, in an embodiment, the cache may support both an LRR and an LRU policy.

<CIT> discusses a cache memory system which includes a cache memory and a block replacement controller. The cache memory may include a plurality of sets, each set including a plurality of block storage locations. The block replacement controller may maintain a separate count value corresponding to each set of the cache memory. The separate count value points to an eligible block storage location within the given set to store replacement data. The block replacement controller may maintain for each of at least some of the block storage locations, an associated recent access bit indicative of whether the corresponding block storage location was recently accessed. In addition, the block replacement controller may store the replacement data within the eligible block storage location pointed to by the separate count value depending upon whether a particular recent access bit indicates that the eligible block storage location was recently accessed.

Aspects according to the disclosure include providing variable interpretation of usefulness indicators for memory tables in processor-based systems. In this regard, in one aspect, a processor-based system includes a memory system that comprises a memory table (e.g., a table storing state data within a static random access memory (SRAM), as a non-limiting example). In some aspects, the memory system may comprise or be part of a cache, a branch predictor, a value predictor, a load address predictor, and/or a hardware data prefetcher, as non-limiting examples. The memory table is made up of multiple memory table entries, each of which includes a usefulness indicator. The memory system further includes a memory controller (for example, an SRAM controller) that provides a global polarity indicator. Some aspects may provide that the global polarity indicator is a single-bit field representing a Boolean value. The global polarity indicator represents a present polarity that indicates how the usefulness indicator for each memory table entry is interpreted and updated by the memory controller. For example, in some aspects, if the global polarity indicator is set, the usefulness indicator of a given memory table entry is interpreted in the conventional fashion, whereby a value of the usefulness indicator directly corresponds to the usefulness of the corresponding memory table entry. Thus, a higher usefulness indicator value indicates a higher level of usefulness, and the usefulness indicator is incremented when the corresponding memory table entry proves valuable, and is decremented otherwise. Conversely, if the global polarity indicator is not set, the polarity is reversed such that the memory controller interprets the usefulness indicator value as inversely corresponding to the usefulness of the corresponding memory table entry. A higher usefulness indicator value therefore is indicative of a lower level of usefulness, and the usefulness indicator is decremented when the corresponding memory table entry proves valuable, and is incremented otherwise. In this manner, the memory controller selects memory table entries for replacement and updates the usefulness indicator based on the interpretation of the usefulness indicators indicated by the global polarity indicator.

In another aspect, a memory system of a processor-based system is provided. The memory system includes a memory table comprising a plurality of memory table entries each providing a usefulness indicator, and further comprises a memory controller providing a global polarity indicator. The memory controller is configured to, responsive to determining that replacement from the memory table is necessary, determine whether the global polarity indicator is not set. The memory controller is further configured to, responsive to determining that the global polarity indicator is not set, interpret a value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry. The memory controller is also configured to, responsive to determining that the global polarity indicator is set, interpret the value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as directly correlating to the usefulness of the memory table entry. The memory controller is additionally configured to select a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table.

In another aspect, a memory system of a processor-based system is provided. The memory system comprises a means for determining that replacement of a memory table entry of a plurality of memory table entries of a memory table is necessary. The memory system further comprises a means for determining whether a global polarity indicator is not set, responsive to determining that replacement of a memory table entry is necessary. The memory system also comprises a means for interpreting a value of a usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry, responsive to determining that the global polarity indicator is not set. The memory system additionally comprises a means for selecting a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table.

In another aspect, a method for providing variable interpretation of memory table usefulness indicators is provided. The method comprises determining, by a memory controller of a processor-based system, that replacement of a memory table entry of a plurality of memory table entries of a memory table is necessary. The method further comprises, responsive to determining that replacement of a memory table entry is necessary, determining whether a global polarity indicator is not set. The method also comprises, responsive to determining that the global polarity indicator is not set, interpreting a value of a usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry. The method additionally comprises selecting a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table.

In another aspect, a non-transitory computer-readable medium is provided. The non-transitory computer-readable medium stores thereon computer-executable instructions which, when executed by a processor, cause the processor to determine that replacement of a memory table entry of a plurality of memory table entries of a memory table is necessary. The computer-executable instructions further cause the processor to, responsive to determining that replacement of a memory table entry is necessary, determine whether a global polarity indicator is not set. The computer-executable instructions also cause the processor to, responsive to determining that the global polarity indicator is not set, interpret a value of a usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry. The computer-executable instructions additional cause the processor to select a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table.

Aspects disclosed in the detailed description include providing variable interpretation of usefulness indicators for memory tables in processor-based systems. In this regard, <FIG> illustrates an exemplary processor-based system <NUM> that includes a central processing unit (CPU) <NUM> and a memory system <NUM> comprising a memory controller <NUM>. The memory system <NUM> according to some aspects may comprise or be part of a cache, a branch predictor, a value predictor, a load address predictor, and/or a hardware data prefetcher, as non-limiting examples. In such aspects, the memory controller <NUM> may comprise a cache controller, a branch predictor controller, a value predictor controller, a load address predictor controller, and/or a hardware data prefetch controller, respectively, as non-limiting examples. The memory system <NUM> may further comprise memory devices, such as static random access memory (SRAM) devices, as non-limiting examples.

It is to be understood that the processor-based system <NUM> of <FIG> may encompass any one of known digital logic elements, semiconductor circuits, and processing cores, and/or memory structures, among other elements, or combinations thereof. Aspects described herein are not restricted to any particular arrangement of elements, and the disclosed techniques may be easily extended to various structures and layouts on semiconductor dies or packages. It is to be further understood that some aspects of the processor-based system <NUM> may include elements in addition to those illustrated in <FIG>. As non-limiting examples, the processor-based system <NUM> may include one or more graphical processing units (GPUs), one or more instruction caches, one or more data caches, one or more execution pipelines, one or more execution units, one or more completion units, and/or one or more registers.

As seen in <FIG>, the memory system <NUM> includes a memory table <NUM> that stores a plurality of memory table entries <NUM>(<NUM>)-<NUM>(X). The memory table <NUM> in some aspects may comprise an SRAM data table for storing state data. Each of the memory table entries <NUM>(<NUM>)-<NUM>(X) includes a corresponding usefulness indicator <NUM>(<NUM>)-<NUM>(X) that is used by the memory controller <NUM> for determining a usefulness of the memory table entry <NUM>(<NUM>)-<NUM>(X) as part of implementing a replacement policy for the memory table <NUM>. For example, if the memory controller <NUM> determines that replacement of one of the memory table entries <NUM>(<NUM>)-<NUM>(X) is necessary, the memory controller <NUM> may be configured to select a memory table entry <NUM>(<NUM>)-<NUM>(X) whose usefulness indicator <NUM>(<NUM>)-<NUM>(X) indicates that the memory table entry <NUM>(<NUM>)-<NUM>(X) is least useful among the memory table entries <NUM>(<NUM>)-<NUM>(X). In this manner, the memory controller <NUM> attempts to minimize any impact on system performance that may result from replacement of one of the memory table entries <NUM>(<NUM>)-<NUM><NUM>(X).

However, as noted above, the usefulness indicators <NUM>(<NUM>)-<NUM>(X) themselves tend to become less useful over time as the memory table <NUM> becomes populated with memory table entries <NUM>(<NUM>)-<NUM>(X) that all indicate that they are useful. While recalibration of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) (e.g., by shifting or flash-clearing all of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) in the memory table <NUM>) can remedy this problem, such solutions require multiple memory table entries <NUM>(<NUM>)-<NUM>(X) to be written within a very short period of time. As a result, these potential solutions may not be practicable when using memory devices such as SRAMs.

In this regard, the memory controller <NUM> of <FIG> provides a global polarity indicator <NUM> that determines how the memory controller <NUM> interprets and updates the usefulness indicators <NUM>(<NUM>)-<NUM>(X) of the memory table entries <NUM>(<NUM>)-<NUM>(X). In some aspects, the global polarity indicator <NUM> comprises a single-bit field that represents a Boolean value. When the global polarity indicator <NUM> is set (e.g., has a Boolean value of true), the memory controller <NUM> interprets the usefulness indicator <NUM>(<NUM>)-<NUM>(X) in the conventional fashion, whereby a value of each of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) directly corresponds to the usefulness of the corresponding memory table entry <NUM><NUM>(<NUM>)-<NUM>(X). Thus, a usefulness indicator <NUM>(<NUM>)-<NUM>(X) having a higher value indicates a higher level of usefulness, and the usefulness indicator <NUM>(<NUM>)-<NUM>(X) is incremented when the corresponding memory table entry <NUM>(<NUM>)-<NUM>(X) proves valuable, and is decremented otherwise.

If the global polarity indicator <NUM> is not set (e.g., has a Boolean value of false), the memory controller <NUM> interprets the value of each usefulness indicator <NUM>(<NUM>)-<NUM>(X) as inversely corresponding to the usefulness of the corresponding memory table entry <NUM>(<NUM>)-<NUM>(X). A usefulness indicator <NUM>(<NUM>)-<NUM>(X) having a higher value therefore is indicative of a lower level of usefulness, and the usefulness indicator <NUM>(<NUM>)-<NUM>(X) is decremented when the corresponding memory table entry <NUM>(<NUM>)-<NUM>(X) proves valuable, and is incremented otherwise. In this manner, the memory controller <NUM> selects memory table entries <NUM>(<NUM>)-<NUM>(X) for replacement and updates the usefulness indicators <NUM>(<NUM>)-<NUM>(X) based on the interpretation of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) indicated by the global polarity indicator <NUM>. It is to be understood that, in some aspects, the global polarity indicator <NUM> may be considered to be "set" when storing a Boolean value of false and "not set" when storing a Boolean value of true.

In some aspects, the memory controller <NUM> is further configured to determine an optimal time to invert the value of the global polarity indicator <NUM> by tracking how many times an installation of a new memory table entry <NUM>(<NUM>)-<NUM>(X) is successful versus how many installations fail (e.g., resulting in forfeiting placement of the new memory table entry <NUM>(<NUM>)-<NUM>(X) or selecting a memory table entry <NUM>(<NUM>)-<NUM>(X) that is indicated to be useful). In this regard, the memory controller <NUM> in such aspects provides an installation failure count indicator <NUM> that is incremented upon a failed attempt to install a new memory table entry <NUM>(<NUM>)-<NUM>(X), and decremented upon a successful attempt to install a new memory table entry <NUM>(<NUM>)-<NUM>(X). The memory controller <NUM> may further provide an installation failure threshold indicator <NUM>, the value of which is set to indicate a maximum allowable number of failed installations. When the value of the installation failure count indicator <NUM> exceeds the value of the installation failure threshold indicator <NUM>, the memory controller <NUM> is configured to invert the value of the global polarity indicator <NUM>. As a non-limiting example, if the global polarity indicator <NUM> has a current Boolean value of true, the memory controller <NUM> sets the global polarity indicator <NUM> to a Boolean value of false, and vice versa. This has the effect of reversing the interpretation of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) by the memory controller <NUM>, transforming the most useful memory table entries <NUM>(<NUM>)-<NUM>(X) into the least useful.

Some aspects may provide that the performance of the memory controller <NUM> and the global polarity indicator <NUM> is enhanced by ensuring that the usefulness indicators <NUM>(<NUM>)-<NUM>(X) of the memory table entries <NUM>(<NUM>)-<NUM>(X) represent symmetric ranges of useful states and non-useful states. For example, for usefulness indicators <NUM>(<NUM>)-<NUM>(X) having two (<NUM>) bits (and thus four (<NUM>) potential usefulness values), the performance of the memory controller <NUM> may be optimized where the four (<NUM>) potential usefulness values represent two (<NUM>) useful states and two (<NUM>) non-useful states.

<FIG> and <FIG> provide state diagrams to compare and contrast the manner in which the state of each of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) may be interpreted and updated by a conventional memory controller and the memory controller <NUM> of <FIG>. In particular, <FIG> shows the potential states of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) and the transitions between states according to a conventional memory controller. <FIG> shows the possible states of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) and how they are interpreted and updated by the memory controller <NUM> based on the usefulness of the corresponding memory table entries <NUM>(<NUM>)-<NUM>(X) and the value of the global polarity indicator <NUM>. In both <FIG> and <FIG>, it is assumed that the usefulness indicators <NUM>(<NUM>)-<NUM>(X) are bit fields storing two (<NUM>) bits each.

In <FIG>, a state diagram <NUM> illustrates four possible states <NUM>(<NUM>)-<NUM>(<NUM>) of each of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) of <FIG>. As seen in <FIG>, the four possible states <NUM>(<NUM>)-<NUM>(<NUM>) have corresponding binary values of 0b00, 0b01, 0b10, and 0b11, with the allowable transitions between the states <NUM>(<NUM>)-<NUM>(<NUM>) indicated by transition arrows <NUM>(<NUM>)-<NUM>(<NUM>). A legend <NUM> indicates how the value of each of the states <NUM>(<NUM>)-<NUM>(<NUM>) is interpreted by a conventional memory controller. In the example of <FIG>, the binary value 0b00 is interpreted as "useless," while the binary value 0b01 is interpreted as "less useful," the binary value 0b10 as "more useful," and the binary value 0b11 as "most useful.

When a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM><NUM>(X) is determined by the conventional memory controller to be useful (e.g., in response to a correct prediction or prefetch suggestion), the value of the corresponding usefulness indicator <NUM>(<NUM>)-<NUM><NUM>(X) is incremented. This results in a transition to a more useful" state (as indicated by transition arrows <NUM>(<NUM>)-<NUM>(<NUM>)) ultimately reaching the state <NUM>(<NUM>) representing "most useful. " Conversely, when the conventional memory controller judges a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) to be less useful, the value of the corresponding usefulness indicator <NUM>(<NUM>)-<NUM>(X) is decremented, resulting in a transition to a "less useful" state (as shown by transition arrows <NUM>(<NUM>)-<NUM>(<NUM>)) until the state <NUM>(<NUM>) representing "useless" is reached.

<FIG>, in contrast, shows how the memory controller <NUM> of <FIG> may vary the interpretation of the value of the usefulness indicators <NUM><NUM>(<NUM>)-<NUM>(X) based on the value of the global polarity indicator <NUM> of <FIG>. As seen in <FIG>, a state diagram <NUM> comprises states <NUM>(<NUM>)-<NUM>(<NUM>) that have corresponding binary values of 0b00, 0b01, 0b10, and 0b11, with possible transitions between the states <NUM>(<NUM>)-<NUM>(<NUM>) indicated by transition arrows <NUM>(<NUM>)-<NUM>(<NUM>). A legend <NUM> indicates how the value of each state <NUM>(<NUM>)-<NUM>(<NUM>) is interpreted by the memory controller <NUM>, depending on the global polarity indicator <NUM>. The logic for determining how to interpret a given binary value is shown in <FIG> in the format "X?Y:Z," which is intended to be read as "if condition X is true, interpret as Y; otherwise, interpret as Z. " Thus, if the global polarity indicator <NUM> is set (e.g., has a Boolean value of true), then the values of the states <NUM>(<NUM>)-<NUM>(<NUM>) are interpreted in conventional fashion. The binary value 0b00 is interpreted as "useless," the binary value 0b01 as "less useful," the binary value 0b10 as "more useful," and the binary value 0b11 as "most useful. " However, if the global polarity indicator <NUM> is not set (e.g., has a Boolean value of false), the interpretation of each binary value is reversed. As a result, the binary value 0b00 is interpreted as "most useful," the binary value 0b01 as "more useful," the binary value 0b10 as "less useful," and the binary value 0b11 as "useless.

In similar fashion, the transitions between the potential states <NUM>(<NUM>)-<NUM>(<NUM>) for each of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) vary based on the value of the global polarity indicator <NUM> and the determined usefulness of the corresponding memory table entries <NUM>(<NUM>)-<NUM>(X). In the example of <FIG>, if the global polarity indicator <NUM> is set, the transitions between the states <NUM>(<NUM>)-<NUM>(<NUM>) occur in the same manner as shown in <FIG>. Thus, when a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) is determined by the memory controller <NUM> to be useful, the value of the corresponding usefulness indicator <NUM>(<NUM>)-<NUM>(X) is incremented, resulting in a transition to a "more useful" state as shown by the transition arrows <NUM>(<NUM>)-<NUM>(<NUM>). The value of the usefulness indicator <NUM>(<NUM>)-<NUM>(X) corresponding to a less useful memory table entry <NUM>(<NUM>)-<NUM>(X) is decremented, resulting in a transition to a "less useful" state as shown by the transition arrows <NUM>(<NUM>)-<NUM>(<NUM>).

However, if the global polarity indicator <NUM> is not set, the memory controller <NUM> applies the reverse logic to state transitions. Consequently, when a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) is determined to be useful, the value of the corresponding usefulness indicator <NUM>(<NUM>)-<NUM>(X) is decremented, resulting in a transition to a "more useful" state as shown by the transition arrows <NUM>(<NUM>)-<NUM>(<NUM>). Likewise, the value of the usefulness indicator <NUM>(<NUM>)-<NUM>(X) corresponding to a less useful memory table entry <NUM>(<NUM>)-<NUM>(X) is incremented, resulting in a transition to a "less useful" state as shown by the transition arrows <NUM>(<NUM>)-<NUM>(<NUM>).

<FIG> is a flowchart illustrating exemplary operations for providing variable interpretation of usefulness indicators by the memory controller <NUM> of <FIG> using the global polarity indicator <NUM> of <FIG>. In describing <FIG>, elements of <FIG> are referenced for the sake of clarity. In <FIG>, operations begin with the memory controller <NUM> determining whether replacement of a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) of the memory table <NUM> is necessary (block <NUM>). In this regard, the memory controller <NUM> may be referred to herein as "a means for determining that replacement of a memory table entry of a plurality of memory table entries of a memory table is necessary. " The operations of block <NUM> for determining whether replacement of one of the memory table entries <NUM>(<NUM>)-<NUM>(X) may be based on conventional techniques for applying a replacement policy by the memory controller <NUM>. If replacement is not necessary, processing continues (block <NUM>).

However, if the memory controller <NUM> determines at decision block <NUM> that replacement of a memory table entry of the plurality of memory table entries <NUM><NUM>(<NUM>)-<NUM>(X) is necessary, the memory controller <NUM> next determines whether the global polarity indicator <NUM> is set (block <NUM>). Accordingly, the memory controller <NUM> may be referred to herein as "a means for determining whether a global polarity indicator is set, responsive to determining that replacement of a memory table entry is necessary. " According to some aspects, if the global polarity indicator <NUM> is set, the memory controller <NUM> will interpret a value of a usefulness indicator <NUM>(<NUM>)-<NUM>(X) of each memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM><NUM>(X) of the memory table <NUM> as directly correlating to the usefulness of the memory table entry <NUM>(<NUM>)-<NUM>(X) (block <NUM>). If the memory controller <NUM> determines at decision block <NUM> that the global polarity indicator <NUM> is not set, the memory controller <NUM> will interpret the value of the usefulness indicator <NUM>(<NUM>)-<NUM>(X) of each memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) of the memory table <NUM> as inversely correlating to the usefulness of the memory table entry <NUM>(<NUM>)-<NUM>(X) (block <NUM>). The memory controller <NUM> thus may be referred to herein as "a means for interpreting a value of a usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry, responsive to determining that the global polarity indicator is not set.

After determining how to interpret the usefulness indicator <NUM>(<NUM>)-<NUM>(X) of each memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X), the memory controller <NUM> then selects a least useful memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) for replacement based on the interpreted value of the usefulness indicator <NUM>(<NUM>)-<NUM>(X) of each memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) of the memory table <NUM> (block <NUM>). In this regard, the memory controller <NUM> may be referred to herein as "a means for selecting a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table. " As a non-limiting example, the "least useful" memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) may comprise a memory table entry of the plurality of memory table entries <NUM>(<NUM>)-<NUM>(X) having a usefulness indicator <NUM>(<NUM>)-<NUM>(X) with a value closest to the "useless" value as determined based on the global polarity indicator <NUM>. Some aspects of the memory controller <NUM> may be further configured to update a value of the usefulness indicator <NUM>(<NUM>)-<NUM>(X) of a memory table entry of the plurality of memory table entries <NUM><NUM>(<NUM>)-<NUM>(X) of the memory table <NUM> based on a determined usefulness of the memory table entry <NUM>(<NUM>)-<NUM>(X) and a value of the global polarity indicator <NUM> (block <NUM>).

As noted above, to maintain the usefulness of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) themselves, the value of the global polarity indicator <NUM> may be inverted to reverse how the usefulness indicators <NUM><NUM>(<NUM>)-<NUM>(X) are interpreted by the memory controller <NUM>. To illustrate exemplary operations of the memory controller <NUM> for determining when to invert the value of the global polarity indicator <NUM>, <FIG> is provided. For the sake of clarity, elements of <FIG> are referenced in describing <FIG>. Operations in <FIG> begin with the memory controller <NUM> determining whether an attempt to install a new memory table entry, such as the memory table entry <NUM>(<NUM>), in the memory table <NUM> was successful (block <NUM>). If so, the memory controller <NUM> decrements the installation failure count indicator <NUM> (block <NUM>). Processing then continues at block <NUM>. However, if the memory controller <NUM> determines at decision block <NUM> that the attempt to install the new memory table entry <NUM>(<NUM>) in the memory table <NUM> was not successful, the memory controller <NUM> increments the installation failure count indicator <NUM> (block <NUM>). The memory controller <NUM> then determines whether a value of the installation failure count indicator <NUM> exceeds a value of the installation failure threshold indicator <NUM> (block <NUM>). If not, processing continues at block <NUM>. If the value of the installation failure count indicator <NUM> is determined at decision block <NUM> to exceed the value of the installation failure threshold indicator <NUM>, the memory controller <NUM> inverts a value of the global polarity indicator <NUM> (block <NUM>). Consequently, from this point forward, the memory controller <NUM> will reverse its interpretation of the usefulness indicators <NUM>(<NUM>)-<NUM>(X) relative to how the usefulness indicators <NUM>(<NUM>)-<NUM>(X) were interpreted prior to inverting the global polarity indicator <NUM>. Processing then continues (block <NUM>).

Providing variable interpretation of usefulness indicators for memory tables in processor-based systems according to aspects disclosed herein may be provided in or integrated into any processor-based system. Examples, without limitation, include a set top box, an entertainment unit, a navigation device, a communications device, a fixed location data unit, a mobile location data unit, a global positioning system (GPS) device, a mobile phone, a cellular phone, a smart phone, a session initiation protocol (SIP) phone, a tablet, a phablet, a server, a computer, a portable computer, a mobile computing device, a wearable computing device (e.g., a smart watch, a health or fitness tracker, eyewear, etc.), a desktop computer, a personal digital assistant (PDA), a monitor, a computer monitor, a television, a tuner, a radio, a satellite radio, a music player, a digital music player, a portable music player, a digital video player, a video player, a digital video disc (DVD) player, a portable digital video player, an automobile, a vehicle component, avionics systems, a drone, and a multicopter.

In this regard, <FIG> illustrates an example of a processor-based system <NUM> that corresponds to the processor-based system <NUM> of <FIG>. The processor-based system <NUM> includes one or more CPUs <NUM>, each including one or more processors <NUM>. The CPU(s) <NUM> may have cache memory <NUM> that is coupled to the processor(s) <NUM> for rapid access to temporarily stored data. The CPU(s) <NUM> is coupled to a system bus <NUM> and can intercouple master and slave devices included in the processor-based system <NUM>. As is well known, the CPU(s) <NUM> communicates with these other devices by exchanging address, control, and data information over the system bus <NUM>. For example, the CPU(s) <NUM> can communicate bus transaction requests to a memory controller <NUM> (which corresponds to the memory controller <NUM> of <FIG>) as an example of a slave device.

Other master and slave devices can be connected to the system bus <NUM>. As illustrated in <FIG>, these devices can include a memory system <NUM>, one or more input devices <NUM>, one or more output devices <NUM>, one or more network interface devices <NUM>, and one or more display controllers <NUM>, as examples. The input device(s) <NUM> can include any type of input device, including, but not limited to, input keys, switches, voice processors, etc. The output device(s) <NUM> can include any type of output device, including, but not limited to, audio, video, other visual indicators, etc. The network interface device(s) <NUM> can be any devices configured to allow exchange of data to and from a network <NUM>. The network <NUM> can be any type of network, including, but not limited to, a wired or wireless network, a private or public network, a local area network (LAN), a wireless local area network (WLAN), a wide area network (WAN), a BLUETOOTH™ network, and the Internet. The network interface device(s) <NUM> can be configured to support any type of communications protocol desired. The memory system <NUM> can include one or more memory units <NUM>(<NUM>)-<NUM>(N).

The CPU(s) <NUM> may also be configured to access the display controller(s) <NUM> over the system bus <NUM> to control information sent to one or more displays <NUM>. The display controller(s) <NUM> sends information to the display(s) <NUM> to be displayed via one or more video processors <NUM>, which process the information to be displayed into a format suitable for the display(s) <NUM>. The display(s) <NUM> can include any type of display, including, but not limited to, a cathode ray tube (CRT), a liquid crystal display (LCD), a plasma display, etc..

Those of skill in the art will further appreciate that the various illustrative logical blocks, modules, circuits, and algorithms described in connection with the aspects disclosed herein may be implemented as electronic hardware, instructions stored in memory or in another computer readable medium and executed by a processor or other processing device, or combinations of both. The master devices, and slave devices described herein may be employed in any circuit, hardware component, integrated circuit (IC), or IC chip, as examples. Memory disclosed herein may be any type and size of memory and may be configured to store any type of information desired. To clearly illustrate this interchangeability, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. How such functionality is implemented depends upon the particular application, design choices, and/or design constraints imposed on the overall system.

It is also noted that the operational steps described in any of the exemplary aspects herein are described to provide examples and discussion. Additionally, one or more operational steps discussed in the exemplary aspects may be combined. It is to be understood that the operational steps illustrated in the flowchart diagrams may be subject to numerous different modifications as will be readily apparent to one of skill in the art. Those of skill in the art will also understand that information and signals may be represented using any of a variety of different technologies and techniques.

Claim 1:
A memory system of a processor-based system, comprising:
a memory table (<NUM>) comprising a plurality of memory table entries (<NUM>(<NUM>) - <NUM>(x)) each comprising a usefulness indicator (<NUM>(<NUM>) - <NUM>(x)); and
a memory controller (<NUM>) comprising a global polarity indicator (<NUM>);
the memory controller configured to, responsive to determining that replacement from the memory table is necessary:
determine whether the global polarity indicator is not set;
responsive to determining that the global polarity indicator is not set, interpret a value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as inversely correlating to a usefulness of the memory table entry;
responsive to determining that the global polarity indicator is set, interpret the value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table as directly correlating to the usefulness of the memory table entry; and
select a least useful memory table entry of the plurality of memory table entries for replacement based on the interpreted value of the usefulness indicator of each memory table entry of the plurality of memory table entries of the memory table.