Patent Description:
A computing device may include multiple subsystems that communicate with one another via buses or other interconnects. Such a computing device may be, for example, a portable computing device ("PCD"), such as a laptop or palmtop computer, a cellular telephone or smartphone, portable digital assistant, portable game console, etc. The communicating subsystems may be included within the same integrated circuit chip or in different chips. A "system-on-a-chip" or "SoC" is an example of one such chip that integrates numerous components to provide system-level functionality. For example, an SoC may include one or more types of processors, such as central processing units ("CPU"s), graphics processing units ("GPU"s), digital signal processors ("DSP"s), and neural processing units ("NPU"s). An SoC may include other subsystems, such as a transceiver or "modem" that provides wireless connectivity, a main or system memory, one or more cache memories, etc. Some subsystems may include processing engines that may perform memory transactions with the system memory. The system memory in PCDs and other computing devices commonly comprises dynamic random access memory ("DRAM").

DRAM is organized in arrays of rows and columns. A row must be opened before its data can be accessed. Only one row in an array may be open at any time. To help reduce latency, a DRAM may be organized in multiple banks, each comprising an array of the aforementioned type. A DRAM controller may initiate access to one bank while waiting for a previous access to another bank to complete. To provide further performance advantages, the banks may be organized in multiple bank groups. In addition, a DRAM may be organized in multiple ranks, each having multiple bank groups.

One task of the DRAM controller is to schedule or direct transactions among the ranks, bank groups and banks. The term "DRAM-aware" scheduling is sometimes used to describe how a DRAM controller may perform such scheduling in a manner that leverages the efficiencies afforded by the organization of the DRAM. For example, a DRAM controller may randomize its selection of a bank to access so that there is a low likelihood of sequential accesses being directed to different rows of the same bank. Also, for example, a DRAM controller may direct as many accesses as possible to one rank before switching to another rank because switching ranks incurs a high latency penalty.

A cache memory system may be interposed in the memory transaction path between the processing engine requesting the transaction and the DRAM controller. As the cache memory fills or becomes "dirty," the cache memory controller writes back or "evicts" some of the dirty cache lines to the DRAM to free up space in the cache memory. The DRAM-aware scheduling techniques employed by the DRAM controller may be insufficient to maximize efficiency in some circumstances.

Attention is drawn to document <CIT> which relates to a method for cleaning dirty data in an intermediate cache. A dirty data notification, including a memory address and a data class, is transmitted by a level <NUM> (L2) cache to frame buffer logic when dirty data is stored in the L2 cache. The data classes may include evict first, evict normal and evict last. In one embodiment, data belonging to the evict first data class is raster operations data with little reuse potential. The frame buffer logic uses a notification sorter to organize dirty data notifications, where an entry in the notification sorter stores the DRAM bank page number, a first count of cache lines that have resident dirty data and a second count of cache lines that have resident evict_first dirty data associated with that DRAM bank. The frame buffer logic transmits dirty data associated with an entry when the first count reaches a threshold.

Attention is also drawn to document <CIT> which relates to an apparatus including a memory controller. The memory controller includes a command queue and an arbiter. The command queue receives and stores memory access requests. The arbiter picks the memory access requests from the command queue based on a plurality of criteria, and provides picked memory access requests to a memory channel. The arbiter includes a streak counter for counting a number of consecutive memory access requests of a first type that the arbiter picks from the command queue. When the streak counter reaches a threshold, the arbiter suspends picking requests of the first type and picks at least one memory access request of a second type. The arbiter provides the at least one memory access request of the second type to the memory channel.

Finally, attention is drawn to document <CIT> which relates to a memory controller which includes a batch unit, a batch scheduler, and a memory command scheduler. The batch unit includes a plurality of source queues for receiving memory requests from a plurality of sources. Each source is associated with a selected one of the source queues. The batch unit is operable to generate batches of memory requests in the source queues. The batch scheduler is operable to select a batch from one of the source queues. The memory command scheduler is operable to receive the selected batch from the batch scheduler and issue the memory requests in the selected batch to a memory interfacing with the memory controller.

Further embodiments of the invention are defined by the appended dependent claims. Systems, methods, computer-readable media, and other examples are disclosed for controlling data caching in a DRAM-aware manner.

An exemplary system for controlling data caching may include a plurality of data storage structures collectively having an organization corresponding to a structural organization of a DRAM. The exemplary system may further include a cache controller system. The cache controller system may be configured to receive a plurality of transaction requests. The cache controller system may further be configured to store data associated with the transaction requests in one or more data storage structures selected from among the plurality of data storage structures based on a memory address associated with each transaction request. The cache controller system may also be configured to control data transfer to the DRAM using the plurality of data storage structures.

An exemplary method for controlling data caching may include receiving a plurality of transaction requests. The exemplary method may further include storing data associated with the transaction requests in one or more data storage structures selected from among the plurality of data storage structures based on a memory address associated with each transaction request. The exemplary method may also include controlling data transfer to a DRAM using the plurality of data storage structures. The plurality of data storage structures may collectively have an organization corresponding to a structural organization of the DRAM.

Another exemplary system for controlling data caching may include means for receiving a plurality of transaction requests. The exemplary system may further include means for storing data associated with the transaction requests in one or more data storage structures selected from among the plurality of data storage structures based on a memory address associated with each transaction request. The exemplary system may also include means for controlling data transfer to a DRAM using the plurality of data storage structures. The plurality of data storage structures may collectively have an organization corresponding to a structural organization of the DRAM.

An exemplary computer-readable medium for controlling data caching may include a non-transitory computer-readable medium having instructions stored thereon in computer-executable form. The instructions, when executed by a processor, may configure the processor to receive a plurality of transaction requests. The instructions may further configure the processor to store data associated with the transaction requests in one or more data storage structures selected from among the plurality of data storage structures based on a memory address associated with each transaction request. The instructions may also configure the processor to control data transfer to a DRAM using the plurality of data storage structures.

" The word "illustrative" may be used herein synonymously with "exemplary.

As illustrated in <FIG>, a system <NUM> for controlling aspects of data caching may be provided. The system <NUM> may be configured for controlling aspects of caching data relating to memory transactions between a client device (not shown) and a DRAM (not shown). Although in the exemplary embodiments described herein write transactions serve as examples of memory transactions, aspects of the systems, methods and other embodiments described herein may also be applicable to other types of transactions. The system <NUM> may include a plurality of data storage structures <NUM>. The plurality of data storage structures <NUM> may collectively have an organization corresponding to an organization of the DRAM. For example, as described below, a DRAM may be organized in banks, bank groups, ranks, etc. The plurality of data storage structures <NUM> may have an organization corresponding to one or more of: a bank organization of the DRAM, a bank group organization of the DRAM, a rank organization of the DRAM, etc..

The system <NUM> may further include a cache controller system <NUM>. The cache controller system <NUM> may be configured to receive DRAM transaction requests from one or more client devices (not shown). A client device may be of any type capable of initiating bus transactions, such as, for example, a CPU or other processor. Transaction requests may include read transaction requests and write transaction requests (which may also be referred to herein for brevity as read requests and write requests). The arrows in <FIG> indicate logical flows relating to transactions, and more specifically, indicate logical flows relating to the request-related aspects of transactions; response-related aspects, such as aspects relating to the return flow of data in response to a request, are not indicated by the arrows in <FIG> for purposes of clarity. It should also be understood that the arrows in <FIG> indicate logical flows in a conceptual manner, and are not intended to indicate specific physical interconnections, such as specific signal lines, buses, etc. Further, references in this disclosure to an "indication" may be broadly interpreted to include any type or combination of signals, bits, commands, instructions, etc..

A transaction request may include a target memory (i.e., DRAM) address and may also include other information as described below. The cache controller system <NUM> may further be configured to store data associated with the transaction request in a selected one of the data storage structures <NUM>. The data storage structure <NUM> in which the data is stored may be selected from among the data storage structures <NUM> based on, among other information, the target memory address associated with the transaction request. For example, in the case of a write request, the information or data stored in the selected data structure <NUM> may be a form of cache address. As described below, such a cache address may indicate a location in a payload cache (not shown in <FIG>) in which the data that is the subject of the write request is cached.

The cache controller system <NUM> may further be configured to control a transfer of data to the DRAM using the data storage structures <NUM>. For example, as described below, data that is stored in the data storage structures <NUM> may be used to indicate locations or addresses of cached data to evict to the DRAM. The cache controller system <NUM> may be configured to control the transfer of data by selecting among the data storage structures <NUM> based on a sequence. The sequence may be based on, for example, a round-robin selection among the data storage structures <NUM>. The sequence may be based on, for example, selecting between a first subset of the data storage structures <NUM> associated with a first rank of the DRAM and a second subset of the data storage structures <NUM> associated with a second rank of the DRAM. The sequence may be based on, for example, whether entries in the data storage structures indicate DRAM page hits. These aspects relating to selecting among the data storage structures <NUM> are further described below.

As illustrated in <FIG>, a system <NUM> may include a client device <NUM> (i.e., a processor or other processing engine), a cache system <NUM>, a memory controller <NUM>, and a DRAM <NUM>. The client device <NUM> may issue DRAM transaction requests that may include read requests, i.e., requests to read data from the DRAM <NUM>, and write requests, i.e., requests to store data in the DRAM <NUM>. The DRAM transaction requests may also be referred to as requests to access the DRAM <NUM>. Each DRAM transaction request may include a target address in the DRAM <NUM>, a size or amount of data to be accessed, and other information. A write request also includes the data, which may be referred to as a payload, that the memory controller <NUM> is to store in the DRAM <NUM> in response to the write request.

The cache system <NUM> may include the features and operate in the manner of the above-described system <NUM> (<FIG>). The cache system <NUM> may also include conventional features. For example, in some respects the cache system <NUM> may operate in the manner of a conventional write-back cache, which is well understood be one of ordinary skill in the art. For example, the cache system <NUM> may temporarily store or "cache" data requested to be written to the DRAM <NUM> responsive to a write request or data that has been read from the DRAM <NUM> responsive to a read request. As understood by one of ordinary skill in the art, data that has been stored in the cache system <NUM> but not yet written to the DRAM <NUM> is commonly referred to as "dirty" data. Conventionally, dirty data is periodically written to the DRAM <NUM>, a process commonly referred to as eviction or cleaning. The eviction-related methods described herein may be included instead of, or in addition to, conventional eviction methods. Cleaning a cache also may be referred to colloquially as "scrubbing. " Although not separately shown for purposes of clarity, the cache system <NUM> may include one or more processors (configurable by software or firmware) or other logic configurable to operate in the manner described herein, including in accordance with the methods described below.

The memory controller <NUM> may have a conventional structure and operate in a conventional manner. For example, the memory controller <NUM> may, among other functions, translate the transaction requests into DRAM commands and physical DRAM addresses. As the memory controller <NUM> and the manner in which it operates are well understood by one of ordinary skill in the art, such aspects of the memory controller <NUM> are not described herein.

The DRAM <NUM> may have a conventional structure and operate in a conventional manner. The DRAM <NUM> may be of any type not inconsistent with the descriptions herein. For example, the DRAM <NUM> may be a double data rate synchronous DRAM ("DDR-SDRAM"), sometimes referred to for brevity as "DDR. " As DDR technology has evolved, DDR versions such as fourth generation low-power DDR ("LPDDR4") and fifth generation low-power DDR ("LPDDR5") have been developed. The DRAM <NUM> may be, for example, LPDDR4, LPDDR4X, LPDDR5, LPDDR5X, etc. Although the structure and operation of the DRAM <NUM> are well understood by one of ordinary skill in the art, the following brief description is provided as background.

The DRAM <NUM> may comprise two ranks <NUM>, which may be referred to as Rank_0 and Rank_1. As the two ranks <NUM> are identical to each other, the following description applies to each rank <NUM>. The rank <NUM> comprises two or more ("M") banks <NUM>, which may be referred to as Bank_0 through Bank_M-<NUM>. Each bank <NUM> is organized as a two-dimensional array <NUM> of cells or storage locations, where the storage locations in the array <NUM> are accessed by selecting rows and columns. An exemplary row and an exemplary column are highlighted in cross-hatch in <FIG> for purposes of illustration. Also, although not illustrated in <FIG> for purposes of clarity, the DRAM <NUM> may further be organized in bank groups. For example, each rank <NUM> may consist of four bank groups (not shown), and each of those bank groups may consist of four banks. In such an embodiment the DRAM <NUM> therefore consists of <NUM> distinct (i.e., individually addressable) banks <NUM>. Although in the exemplary embodiment described herein the DRAM <NUM> has two ranks <NUM>, each having four bank groups, and each of the four bank groups has four banks <NUM>, in other embodiments such a DRAM may be organized in any other way, including more or fewer ranks, banks, bank groups, etc., than in the exemplary embodiment.

The physical addresses by which the memory controller <NUM> accesses the DRAM <NUM> may include row addresses, column addresses, bank group addresses, and bank addresses. Also, although not shown for purposes of clarity, in response to a rank address (e.g., a chip select bit included in the read or write command) provided by the memory controller <NUM>, rank address decoding logic may select one of the ranks <NUM>. Although likewise not shown for purposes of clarity, in response to a bank address provided by the memory controller <NUM>, bank address decoding logic may select one of the banks <NUM> in a selected bank group of a selected rank <NUM>. In response to a row address provided by the memory controller <NUM>, a row address decoder <NUM> may select one of the rows in a selected bank <NUM> of a selected bank group in a selected rank <NUM>. Similarly, in response to a column address provided by the memory controller <NUM>, a column address decoder <NUM> may select one of the columns in a selected bank <NUM> of a selected bank group in a selected rank <NUM>.

Each rank <NUM> may have a read latch <NUM> to buffer the read data, and a write latch <NUM> to buffer the write data. Each rank <NUM> may also have input/output ("I/O") logic <NUM> configured to direct the read and write data from and to selected memory locations.

Each bank <NUM> may have a row buffer <NUM>. The row buffer <NUM> stores the contents of the selected row (also referred to as a "page"). A row must be selected or "opened" before it may be written to or read from. Once a row is opened, the DRAM <NUM> may read from or write to any number of columns in the row buffer <NUM> in response to read or write commands. Following a read or write command, the data is transferred serially between the memory controller <NUM> and DRAM <NUM> in units known as a "burst," which may be, for example, eight bits per data signal line. The row must be restored or "closed" after writing to or reading from the row buffer <NUM>.

A read or write transaction to a row that is already open is referred to as a "page hit. " A read or write transaction to a row that is not open (and therefore needs to be opened) is referred to as a "page miss. " A page miss incurs greater latency than a page hit. Performing a number of sequential transactions to the same open row (i.e., sequential page hits) rather than having to close one row and open another row is desirable, as it reduces latency. Also, sequential transactions directed to the same bank incur more latency than sequential transactions to different banks. The structure or organization of the DRAM <NUM> in bank groups and banks enables the DRAM controller <NUM> to initiate access to a row in one bank while waiting for a previous access to a row in another bank to complete. Such timing overlap helps minimize transaction latency. The DRAM controller <NUM> may employ a conventional bank hashing algorithm to help randomize its selection of a bank to access so that there is a low likelihood of sequential accesses being directed to the same bank. This randomization effect is commonly referred to as increasing bank and/or bank group "spread. " The DRAM controller <NUM> may employ other algorithms to attempt to reduce other sources of latency, such as read-to-write switching, write-to-read switching, or rank-to-rank switching. The cache system <NUM> may include features, described below, which may further increase bank spread, increase page hit rate, and decrease read-to-write, write-to-read, or rank-to-rank switching, with a goal of further reducing latency.

As illustrated in <FIG>, a system <NUM> for controlling aspects of data caching may be provided. The system <NUM> may be an example of the above-described system <NUM> (<FIG>). The system <NUM> may be configured to receive transaction ("txn") requests from a client device (not shown in <FIG>) that are directed to a DRAM (not shown in <FIG>), in the manner described above with regard to <FIG>. The system <NUM> may include a scrubber <NUM>. The scrubber <NUM> may include a plurality of queues <NUM>. The queues <NUM> may be an example of the above-described data storage structures <NUM> (<FIG>). As further described below, the queues <NUM> may be organized in a manner corresponding to the organization of the DRAM. For example, each queue <NUM> may correspond to one bank of the DRAM.

The system <NUM> may further include a cache data (or "payload") memory <NUM>. The cache data memory <NUM> may be configured to store (i.e., to cache) data that is the subject of DRAM transaction requests. Data stored in the cache data memory <NUM> may be referred to as cached data. Data may be stored in the cache data memory <NUM> in units commonly referred to as cache lines. The cache data memory <NUM> may be organized as a set-associative cache. Although a set-associative cache is well understood by one of ordinary skill in the art, the following brief description is provided as background.

A set-associative cache is addressable using address portions commonly referred to as "set" and "way. " Conceptually, a set is a row in the cache. Each DRAM address maps to one of the sets. An "N-way set-associative cache" consists of some number (N) of ways, and each DRAM address may map to (or select) any one of the N ways in the set. A reference herein to looking up a tag means that the contents of all N ways are read (e.g., from the tag memory <NUM> described below), and the tag of each way as well as the Valid flag of each way are checked to determine whether a cache hit occurred in one of the ways of the set. A hit in one of the ways means that the data is cached in a location (e.g., in the cache data memory <NUM>) associated with that way. The cache data memory <NUM> may be implemented in static RAM ("SRAM").

The system <NUM> may also include a tag processor <NUM>, which may be an example of the above-described cache controller system <NUM> (<FIG>) or portion thereof. Although not shown in <FIG> for purposes of clarity, the tag processor <NUM> may include a processor (e.g., configurable by software or firmware) or other logic (e.g., finite state machines, etc.) configurable to provide the functionality described below. As further described below, when the data that is the subject of a write request is stored in the cache data memory <NUM> (at a cache address) but has not yet been written to the DRAM, i.e., the cached data is "dirty," the tag processor <NUM> may store the cache address of the dirty data in a selected one of the queues <NUM>. In other words, the queues <NUM> may be used to store the cache addresses (e.g., set and way) of dirty cache lines. A reference to a cache line being "registered" in the queues <NUM> means the cache address in which the cached data is stored in the cache data memory <NUM> is stored in the queues <NUM>. The queue <NUM> in which that data (i.e., the cache address) is stored may be selected based on, for example, which DRAM bank corresponds to the target memory address associated with the write request. Although in the exemplary embodiment illustrated in <FIG> the queues <NUM> are used by the tag processor <NUM> to store the cache addresses of dirty cache lines, in other embodiments (not shown) such queues may be used to store other types of information or data associated with transaction requests.

The system <NUM> may include a tag memory <NUM>. The tag memory <NUM> may be configured to store tags associated with cached data. As understood by one of ordinary skill in the art, a tag may be derived from a portion of the target address in a memory transaction request, and may be used to identify cached data. Each tag stored in the tag memory <NUM> may identify one cache line stored in the cache data memory <NUM>. The tag memory <NUM> may be implemented in SRAM. As addressing a cache memory (e.g., by set and way), using stored tags to identify cached data, and other such data caching principles are well understood by one of ordinary skill in the art, such aspects are not described in further detail herein.

The tag memory <NUM> may be configured to store not only a tag itself but also information associated with the tag. Such information may include one or more flags associated with each tag that may indicate various states of the cache line identified by the tag. For example, a Valid flag may indicate whether the cache line identified by the tag is valid (i.e., the Valid flag is true) or invalid (i.e., the Valid flag is false). A Dirty flag may indicate whether the cache line identified by the tag is dirty (i.e., the Dirty flag is true) or clean (i.e., the Dirty flag is false). A Cleanable flag may indicate whether the cache line identified by the tag is registered in the queues <NUM> (i.e., the Cleanable flag is true) or is not registered in the queues <NUM> (i.e., the Cleanable flag is false). A Stale flag may indicate whether the cache line identified by the tag is older than a predetermined threshold age (i.e., the Stale flag is true) or is not older than the threshold age (i.e., the Stale flag is false). Aspects relating to cache line age are described below.

The system <NUM> may further include an arbiter <NUM>, which in the illustrated embodiment may be included in the scrubber <NUM>. More generally, however, the arbiter <NUM> may be an example of a portion of the above-described cache controller system <NUM> (<FIG>) relating to controlling the eviction of dirty cache lines to the DRAM. As the arbiter <NUM> may include selection logic (not separately shown) based on the DRAM's rank, bank group and bank organization, the arbiter <NUM> may be referred to as having "DDR-aware" characteristics. Although not shown in <FIG> for purposes of clarity, the selection logic of the arbiter <NUM> may include a processor (e.g., configurable by software or firmware) or other logic (e.g., finite state machines, etc.) configurable in accordance with selection algorithms or methods, such as the exemplary methods described below. As further described below, based on such selection methods, the arbiter <NUM> may select from among the queues <NUM>. Selected queues <NUM> are used to control which dirty cache lines are evicted from the cache data memory <NUM> to the DRAM. The system <NUM> may include a cache traffic processor <NUM>, which, among other functions, may control the transfer of the evicted cache lines from the cache data memory <NUM>. The result or output provided by the arbiter <NUM>, identifying a cache line to evict or clean, may be referred to as a Clean transaction request. The tag processor <NUM> may direct Clean transaction requests to the cache traffic processor <NUM>. A memory controller (e.g., as described above with regard to <FIG>) may receive the evicted cache line data from the cache traffic processor <NUM> and control the manner in which the data is ultimately written to the DRAM.

The system <NUM> may also include a transaction buffer <NUM> configured to receive and buffer (e.g., in a transaction pool) incoming write requests from a client device (not shown in <FIG>). The system <NUM> may further include an input arbiter <NUM> that is configured to select from among any transactions that may be in the buffer <NUM> and any Clean transaction that may be provided by the arbiter <NUM> and provide the selected transaction request to the tag processor <NUM>. The input arbiter <NUM> may base the selection upon factors that may include, for example, a priority associated with each transaction, an age associated with each transaction request (e.g., how long a write transaction request has been in the transaction buffer <NUM>), or other factors.

An incoming transaction request received by the system <NUM> may include not only a target address, data, length, etc., but also additional information. The additional information may include caching "hints. " A client may include a caching hint in a write request to indicate, for example, whether the client prefers that the transaction be cached (a "write allocate" hint) or prefers that the transaction be passed through the system <NUM> without caching (a "write no-allocate") hint. A transaction request may also include an indication identifying a sub-cache. Although not shown in <FIG> for purposes of clarity, the system <NUM> may include multiple sub-caches, and different sub-caches may correspond to different priorities in which the transactions directed to one sub-cache are processed relative to the transactions directed to another sub-cache.

It should be noted that the arrows in <FIG> indicate flows relating to request-related aspects of write transactions; response-related aspects, such as the return flow of data in response to a request, are not indicated by the arrows in <FIG> for purposes of clarity. Also, in addition to being configured to process write requests in the manner described herein, the system <NUM> may be configured to process read requests. The system <NUM> may be configured to process read requests in any manner, including in a conventional manner. It should also be understood that the arrows in <FIG> indicate information flow in a conceptual manner, and are not intended to indicate specific physical interconnections, such as specific signal lines, buses, etc..

As illustrated in <FIG>, a scrubber structure <NUM> includes linked list queues ("LLQs") <NUM> and selection logic <NUM>. The LLQs <NUM> may be examples of the queues <NUM> described above with regard to <FIG> and examples of the data storage structures <NUM> described above with regard <FIG>. The LLQs <NUM> are, in the present invention, organized in a manner corresponding to the rank, bank group and bank organization of the DRAM (not shown). Accordingly, in an embodiment in which the DRAM has two ranks (Rank_0 and Rank_1), each consisting of four bank groups (BG0, BG1, BG2 and BG3), each consisting of four banks (totaling <NUM> banks), the LLQs <NUM> may be organized as a first sub-group 404A of <NUM> LLQs <NUM> corresponding to the <NUM> banks of one of the ranks (e.g. Rank_0) and a second sub-group 404B of <NUM> LLQs <NUM> corresponding to the <NUM> banks of the other rank (e.g. Rank_1).

In each sub-group 404A and 404B, the LLQs <NUM> may be organized by bank and bank group. In accordance with an exemplary pattern or organization, the bank group may increment from one LLQ <NUM> to the next, through each of the banks: a first LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_0 in BG_0; a second LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_0 in BG_1; a third LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_0 in BG_2; and a fourth LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_0 in BG_3. Continuing this pattern or organization with the next bank (i.e., Bank_1): a fifth LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_1 in BG_0; a sixth LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_1 in BG_1; a seventh LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_1 in BG_2, and an eighth LLQ <NUM> in each sub-group 404A and 404B may correspond to Bank_1 in BG_3. This pattern or organization may continue through Bank_2 and then Bank_3. In accordance with this pattern or organization, a 16th LLQ <NUM> corresponds to Bank_3 in BG3.

Each LLQ <NUM> is implemented as a linked list (data structure). Although an exemplary linked list structure is described below, it may be noted that each entry in each LLQ <NUM> identifies a dirty cache line. The head entry in each LLQ <NUM> identifies a dirty cache line that may be a candidate for cleaning (i.e., eviction) before the next entry in that LLQ <NUM> becomes a candidate.

The selection logic <NUM> may be used to select a cache line for cleaning from among the candidate dirty cache lines. That is, the selection logic <NUM> may be used to select one LLQ <NUM> from among the <NUM> LLQs <NUM> and thereby select or identify the dirty cache line at the head of that selected queue (LLQ) <NUM>. It should be understood that the selection logic <NUM> is depicted in a conceptual manner in <FIG> and may comprise, for example, a processor (e.g., configurable by software or firmware), finite state machine, or other logic. The selection logic <NUM> may be included in the arbiter <NUM> described above with regard to <FIG>.

Conceptually, the selection logic <NUM> may comprise first queue selection logic 408A configured to select an LLQ <NUM> from among the <NUM> LLQs <NUM> of the first sub-group 404A corresponding to the banks of Rank_0, and second queue selection logic 408B configured to select an LLQ <NUM> from among the <NUM> LLQs <NUM> of the second sub-group 404B corresponding to the banks of Rank_1. Conceptually, the results produced by the first and second queue selection logic 408A and 408B may operate multiplexers or queue selectors 414A and 414B, respectively. Each of first and second queue selection logic 408A and 408B may operate independently of the other but in accordance with the same queue selection method, which is described below. The selection logic <NUM> may further conceptually include rank selection logic <NUM> configured to select between an LLQ <NUM> selected by the first queue selection logic 408A and an LLQ <NUM> selected by the second queue selection logic 408B. The rank selection logic <NUM> may operate in accordance with a rank selection method described below. Conceptually, the results produced by the rank selection logic <NUM> may operate a multiplexer or rank selector <NUM>. The output of the rank selector <NUM> identifies one selected LLQ <NUM>. Yet another method, described below, may control whether the selection logic <NUM> outputs an indication of that one selected LLQ <NUM> (i.e., an indication that a cache line has been identified for eviction) or does not output a selection (i.e., an indication that no cache line has been identified for eviction at that time). The method of controlling whether the rank selector <NUM> outputs an indication of a selected LLQ <NUM> (and thus an indication identifying a cache line) may be referred to as a scrubber enable or scrubber activation method. Selectively enabling the output of the rank selector <NUM> is conceptually represented in <FIG> by a <NUM>-input logical-AND <NUM> having one input representing an indication of a selected LLQ <NUM> and another input representing a controlling determination by the scrubber enable method.

Referring briefly again to <FIG>, the output of the selection logic <NUM> forms the scrubber output <NUM>. The scrubber output <NUM> is provided to the input arbiter <NUM>. As described above, if a cache line has been identified for eviction, the input arbiter <NUM> may select to proceed with evicting the identified cache line. If no cache line has been identified for eviction at that time, the input arbiter <NUM> may select an incoming transaction from the transaction buffer <NUM>. The input arbiter <NUM> may select the clean request provided by the scrubber output <NUM> or a transaction from the transaction buffer <NUM> according to a priority. In one embodiment, the clean request provided by the scrubber output <NUM> may have the lowest priority and will be served only when no transactions are pending in the transaction buffer <NUM>. In another embodiment, the priority of the clean request provided by the scrubber output <NUM> may be dynamically changed according to the fullness of the scrubber LLQ.

In <FIG>, a method <NUM> for controlling data caching is depicted in flow diagram form. The method <NUM> may, for example, represent aspects of the above-described operation of the system <NUM> (<FIG>). Although the arrows in <FIG> (as well as <FIG>) indicate an order among the various blocks it should be understood that blocks are depicted in an order for convenience of description and guiding the reader through the method, and the operations or actions indicated by the blocks are not limited to such an order. Rather, in other exemplary methods such actions may be performed or otherwise may occur in various orders. Also, some actions may occur concurrently with others. For example, with regard to <FIG>, actions relating to receiving transactions, storing information in the queues, etc., may occur substantially concurrently with actions relating to selecting from among the queues and using the information stored in selected queues to evict cached data. In relation to <FIG>, operation of the tag processor <NUM> and related elements may occur substantially concurrently with operation of the scrubber <NUM>. Further, in other exemplary methods some of the actions or operations may be omitted or combined with other actions.

As indicated by block <NUM>, write requests may be received. The write requests may be received by, for example, the tag processor (<FIG>). As indicated by block <NUM>, data associated with write requests may be cached (e.g., in locations in the cache data memory <NUM> described above with regard to <FIG>).

As indicated by block <NUM>, queues may be selected based on DRAM banks corresponding to the write requests, and information associated with the write requests may be stored in the selected queues. For example, linked list LLQs <NUM> (<FIG>) may be selected by the scrubber <NUM> (<FIG>), and cache address information (e.g., set and way) indicating locations in the cache data memory <NUM> (<FIG>) in which data associated with the write requests has been cached may be stored in selected LLQ s <NUM> (<FIG>) as described above with regard to <FIG>.

Although not shown for purposes of clarity, the actions described above with regard to blocks <NUM>-<NUM> may be performed essentially continuously, independently of other actions. Accordingly, the LLQs <NUM> (<FIG>) may fill as additional write requests are received and information associated with the additional write requests stored in the queues. In the exemplary embodiments described herein, the information associated with the write requests may include not only cache address information (e.g., way and set) but also page hit indications, as described below.

In <FIG>, a linked list queue or LLQ <NUM>, which may be an example of each of the above-described data storage structures <NUM> (<FIG>), queues <NUM> (<FIG>) or LLQs <NUM> (<FIG>), is illustrated. The LLQ <NUM> may comprise any number of entries <NUM> (or linked list "nodes," as sometimes referred to) from a first or "tail" entry 602A to a last or "head" entry 602N. As linked list principles are well understood by one of ordinary skill in the art, details such as pointers that link the nodes are not shown in <FIG> for purposes of clarity. Each entry <NUM> may include cache address information (e.g., way and set) and page hit information (e.g., a bit). The page hit bit indicates whether that entry <NUM> is a page hit with respect to the preceding entry in the LLQ <NUM>.

Referring again to <FIG>, the processing of a write request by the tag processor <NUM> may include controlling (e.g., via the cache traffic processor <NUM>) storing the data that is the subject of the write request (the payload) in the cache data memory <NUM>. The processing of a write request by the tag processor <NUM> may also include deriving a tag, way and set from the target address of the write request. The tag processor <NUM> may derive this cache address information in a conventional manner, as understood by one of ordinary skill in the art. The way and set determine the location (i.e., cache line) in the cache data memory <NUM> which the data is stored or cached. The tag may be stored in the tag memory <NUM> and used along with the target address of a subsequent transaction request (e.g., a read request) to uniquely identify whether the subsequent transaction request is directed to the same cached data.

When the data that is the subject of the write request is stored in a location in the cache data memory <NUM>, the scrubber <NUM> (or alternatively, the tag processor <NUM>) may also determine whether the write request is directed to the same DRAM page, i.e. the same row in the same bank in the same bank group in the same rank, as the DRAM page indicated by the tail of the queue <NUM> the write request is directed to. If two successive write requests are directed to the same DRAM page, the second write request may be referred to as a page hit with respect to the first write request, because the corresponding accesses to that DRAM row may occur in succession while the DRAM row remains open.

Based on the target address, the scrubber <NUM> (or alternatively, the tag processor <NUM>) may determine the DRAM row, bank, bank group and rank addresses. When the data that is the subject of the write request is stored in a location in the cache data memory <NUM>, the tag processor <NUM> may provide the way and set that together indicate that location to the scrubber <NUM>. The scrubber <NUM> may select the corresponding one of the queues <NUM> and add a new entry (or with regard to <FIG>, select one of the LLQs <NUM> and add a new (tail) entry or node). The scrubber <NUM> may store in the new entry the way and set as well as a bit indicating whether the cache line data located at that way and set is a page hit with respect to the preceding entry.

Returning to <FIG>, another portion of the method <NUM> may relate to controlling a transfer of data to the DRAM. In an embodiment relating to operation of the system <NUM> (<FIG>), data transfer from the cache data memory <NUM> to the DRAM may be controlled using the queues <NUM>.

As indicated by block <NUM>, controlling the transfer of data may include selecting among the queues <NUM>. For example, referring again to <FIG>, the arbiter <NUM> may select from among the queues <NUM>. The arbiter <NUM> may select queues <NUM> in a repeated or iterative manner, i.e., selecting each successive or next queue <NUM> after selecting a previous queue <NUM>. The arbiter <NUM> may base the queue selection in part on information obtained from the head entries of linked list queues, such as, for example, the page hit (bit) information. Note that a reference herein to selecting a queue <NUM> also refers to selecting an entry in the queue <NUM>, and therefore further refers to selecting a dirty cache line identified by that entry. The arbiter <NUM> may select the queues <NUM> in this manner based on, for example, one or more of: a sequence; the page hit information; a threshold level of cache dirtiness; a selected rank; etc. These aspects of the operation of the arbiter <NUM> are described below with regard to <FIG>.

As indicated by block <NUM> (<FIG>), the method <NUM> may include evicting cached data indicated by the selected queues. For example, queues <NUM> (<FIG>) may be selected by the arbiter <NUM>. A dirty cache line in a location in the cache data memory <NUM> identified by the selected (also referred to below as "winner") queue entry may be evicted. The scrubber output <NUM> may identify the selected dirty cache line to the tag processor <NUM> (via the input arbiter <NUM>). The tag processor <NUM> may, in turn, identify the selected dirty cache line to the cache traffic processor <NUM>. The cache traffic processor <NUM> may then control the transfer of the dirty cache line out of the cache data memory <NUM>.

As indicated in <FIG>, a tag processor <NUM> may include features relating to storing or caching the data that is the subject of a write request. The tag processor <NUM> may be an example of the above-described tag processor <NUM> (<FIG>). In the illustrated example, such features may include write hint change logic <NUM>, staling logic <NUM>, victim search logic <NUM>, and tag lookup and cleanable line search logic <NUM>.

The write hint change logic <NUM> relates to a feature by which a client's write request may include a caching "hint" that indicates whether the data associated with the write request is to be cached (an "allocate" hint) or passed through the system <NUM> without caching (a "no allocate") hint. Exemplary embodiments may address a client's use of caching hints by changing "no allocate" hints to "allocate" under most circumstances.

As illustrated in <FIG>, the above-described write hint change logic <NUM> (<FIG>) may be configured to control a method <NUM>. Incoming transactions (e.g., from the arbiter <NUM> (<FIG>)), may be provided to the write hint change logic <NUM> and processed in the following manner.

As indicated by block <NUM>, it may be determined whether the incoming transaction request is for a write transaction. The exemplary embodiments described herein relate to write transactions. Nevertheless, aspects of the embodiments described herein may be applied in other embodiments to read transactions. If it is determined (block <NUM>) that the incoming transaction is not a write request, the remainder of the method <NUM> is not performed.

If it is determined (block <NUM>) that the incoming transaction is a write request, then it may be determined whether the selected queue (e.g., one of the LLQs <NUM> described above with regard to <FIG>) is full or there is otherwise no room left in the LLQ <NUM> to store a new entry, as indicated by block <NUM>. In the exemplary embodiment described herein, each queue may not have a predetermined size or capacity, and a new entry may be added to a queue only if the storage capacity used by the LLQs <NUM> is not full. Nevertheless, in other embodiments a queue may have a predetermined size. As described above, a queue may be selected based on, for example, which DRAM bank corresponds to the target memory address associated with the transaction request. If it is determined (block <NUM>) that the selected queue is full, the remainder of the method <NUM> is not performed.

If it is determined (block <NUM>) that the selected queue has room left to store a new entry, then it may be determined whether the write request includes a "no allocate" cache hint, as indicated by block <NUM>. If it is determined (block <NUM>) that the write request does not include a "no allocate" cache hint, the remainder of the method <NUM> is not performed. For example, if the write request includes an "allocate" cache hint, the method <NUM> does not change that transaction's cache hint, which thus remains "allocate.

If it is determined (block <NUM>) that the write request includes a "no allocate" cache hint, then that cache hint may be changed to "allocate. " However, whether the "no allocate" cache hint is changed to "allocate" may be conditioned upon a property of a sub-cache to which the write request is directed. As described above, a transaction request may include an indication identifying a sub-cache from among a number of sub-caches into which the cache system may be partitioned. One such sub-cache, which may be referred to as the Write Sub-Cache or "WRSC," may be used to cache the payloads whose locations are registered in the LLQ <NUM>. Each sub-cache may have a property referred to herein as a "Write_Buffer" property, and the Write_Buffer properties of some sub-caches may be different from the Write_Buffer properties of other sub-caches. The Write_Buffer property may have one of two values: true or false. As indicated by block <NUM>, it may be determined whether the Write_Buffer property of the sub-cache to which the write request is directed is true. If it is determined that the Write_Buffer property is true, then write requests having a "no allocate" hint may be allocated to the WRSC sub-cache and the associated information may be registered in (i.e., stored in) the queues as described above. If it is determined (block <NUM>) that the Write_Buffer property of the sub-cache to which the write request is directed is not true, i.e., is false, then write requests having an "allocate" hint may be registered in the selected queue at a later point when (not shown in <FIG>) the cached data is stale and selected by the tag lookup and cleanable line search logic <NUM> (<FIG>). A method by which cached data may be tagged with a "stale" indication, referring to as a "staling" method, is described below. If it is determined (block <NUM>) that the Write_Buffer property is true, then the "no allocate" cache hint of that write request may be replaced with an "allocate" cache hint, as indicated by block <NUM>. As also indicated by block <NUM>, the indication of the sub-cache to which the write transaction is directed may be replaced with an indication of the Write Sub-Cache.

Referring briefly again to <FIG>, the tag lookup and cleanable line search logic <NUM> relates to further processing the write request after the write hint change logic <NUM> has performed the above-described method <NUM> (<FIG>). As described below, such processing may include looking up a tag associated with the write request, searching for a location in which to store or cache the data associated with the write request, etc..

As illustrated in <FIG>, the tag lookup and cleanable line search logic <NUM> (<FIG>) may be configured to control a method <NUM>. Alternatively, or in addition, the scrubber <NUM> (<FIG>) may be configured to control a portion of the method <NUM>.

Although not shown in <FIG>, before tag lookup is performed (as described below), the staling logic <NUM> (<FIG>) may operate to check the age of each cache line in the set being accessed by the tag lookup operation. If the age of a cache line exceeds a predetermined threshold, the Stale flag may be set to a state of true. The age of a cache line may be calculated by comparing a current time with a time stamp that was associated to the cache line when it was allocated in the cache. Each subcache may have its own current time which is progressing at each new allocation in that subcache.

As indicated by block <NUM>, it may be determined whether the write request results in a cache hit. (Note that a "cache hit" is not the same as the DRAM "page hit" described above. ) Whether a write request results in a cache hit may be determined in a conventional manner. For example, as understood by one of ordinary skill in the art, for an N-way set-associative cache, each set contains N ways or degrees of associativity. Each way include a data block, the tag, and the above-described Valid flag, Dirty flag, Cleanable flag, and Stale flag. The set and way may be determined from a portion of the target address associated with the write request. In the exemplary embodiment, the tag and associated flags may then be read from the tag memory <NUM> (<FIG>). (In the exemplary embodiment, the cached data (lines) may be stored separately in the cache data memory <NUM>. ) For each way in a set, the tag read from the tag memory <NUM> is compared with the tag bits of the target address of the write request, and if they match, and if the Valid flag is true, then it is determined that the write request results in a cache hit. Note that the above-referenced target address decoding may also identify the DRAM rank, bank group and bank to which the write request is directed and thereby identify or select one of the LLQs <NUM> (which may be referred to herein as the LLQ <NUM> or the selected LLQ <NUM>).

If it is determined (block <NUM>) that the write request does not result in a cache hit, then further processing may be performed to determine a location in the cache data memory <NUM> (<FIG>) in which the data may be stored and to add an entry to the LLQ <NUM> indicating that location contains dirty data. Preliminary to this further processing, it may be determined whether the write request includes an "allocate" cache hint, as indicated by block <NUM>.

If it is determined (block <NUM>) that the write request includes an "allocate" cache hint, then a victim search method may be performed. Block <NUM> indicates performing a victim search method that is further described below. A result of performing the victim search method may be a location of a "victim" cache line in the cache data memory <NUM> (<FIG>). However, another possible result of the victim search method may be that no victim cache line has been found. Furthermore, the victim search method may prefer choosing clean victim line to minimize the occurrence of dirty line eviction that would pollute the DRAM aware stream of write back consecutive to the scrubber operations.

As indicated by block <NUM>, it may be determined whether a victim cache line was found. If it is determined (block <NUM>) that a victim cache line was found, then that cache line may be allocated for the data associated with the write request. The data associated with the write request is thus stored in the allocated cache line in the cache data memory <NUM>. Also, as described below, the tag memory <NUM> may be updated, and an entry may be added to the LLQ <NUM>. Adding an entry to the LLQ <NUM> may be conditioned upon some further conditions, one of which is that the LLQ <NUM> is not yet full, as indicated by block <NUM>.

Referring back to block <NUM>, if it is determined that the write request results in a hit, then it may be determined as indicated by block <NUM> whether the hit is on a clean line (i.e., the Dirty flag has a state of false). If it is determined that the hit is on a clean line, the method <NUM> may return to above-described block <NUM>, where it may be determined whether the LLQ <NUM> is full. If it is determined (block <NUM>) that the LLQ <NUM> is full, then the method <NUM> ends with respect to the processing of that write request, and no entry is added to the LLQ <NUM>.

If it is determined (block <NUM>) that the LLQ <NUM> is not full, then another combination of conditions may be determined, as indicated by block <NUM>: the cache line is dirty (i.e., the Dirty flag has a state of true), and the cache line is cleanable (i.e., the Cleanable flag has a state of true), and the above-described Write_Buffer property has a state of true. As noted above, a true Cleanable flag means that the cache line is not yet registered in the LLQ <NUM>.

If the above-described combination of conditions is determined (block <NUM>) to be true, then an entry may be added to the LLQ <NUM>, as indicated by block <NUM>. A new "head" of the LLQ <NUM>, comprising the set and way address of the allocated cache line, may be "pushed" or added to the LLQ <NUM>, effectively placing the entry that was previously the head behind the new head. The new head row information may be compared to the row information of the previous head to determine if the pageHit flag is true. The pageHit flag is also pushed into the queue. The Cleanable flag in the location in the tag memory <NUM> associated with the allocated cache line may be set to a state of false. The write request having been processed in the above-described manner may signify the end of the method <NUM> with respect to that write request.

Nevertheless, if it is determined in accordance with above-described block <NUM> that cache hit is not on a clean line, or if it is determined in accordance with above-described block <NUM> that the cache hint is not "allocate," or if it is determined in accordance with above-described block <NUM> that no victim cache line was found, or if it is determined that the combination of conditions described above with regard to block <NUM> is not true, then the method <NUM> may continue (see <FIG>) as indicated by block <NUM>.

It may then be determined (block <NUM>) whether the LLQ <NUM> is full. If it is determined that the LLQ <NUM> is full, then the method <NUM> ends with respect to the processing of that write request, and no entry is added to the LLQ <NUM>.

If it is determined (block <NUM>) that the LLQ <NUM> is not full, then as indicated by block <NUM> it may be determined whether the set has any cache lines having the combination of conditions: dirty, cleanable, and stale (i.e., the Dirty, Cleanable, and Stale flags are all true). If that combination of conditions is determined to be true, then one of those cache lines (e.g., the first such cache line found) may be selected for adding to the list of dirty cache lines in the LLQ <NUM>, as indicated by block <NUM>. Returning to block <NUM> (<FIG>), an entry for that cache line may then be added to the LLQ <NUM>.

As illustrated in <FIG>, a "victim search" method <NUM> may be an example of the sub-method of the above-described method <NUM> (<FIG>) that is indicated by block <NUM>. As indicated by block <NUM>, it may be determined whether there are one or more invalid lines (i.e., the Valid flag is false) in the set. If it is determined (block <NUM>) that there are one or more invalid lines in the set, then one of those invalid lines may be selected as the victim line, as indicated by block <NUM>. If more than one such line is found, then the first such line that is found may be selected in accordance with block <NUM>.

However, if it is determined (block <NUM>) that there are no invalid lines in the set, then it may be determined whether there are one or more clean stale lines (i.e., the Clean and Stale flags are true) in the set, as indicated by block <NUM>. If it is determined (block <NUM>) that there are one or more clean stale lines in the set, then one of those clean stale lines may be selected as the victim line, as indicated by block <NUM>. If more than one such line is found, then the first such line that is found may be selected in accordance with block <NUM>. It should be understood that the likelihood to find a clean stale line is high as the scrubber is ensuring a low level of dirty lines in the cache and the staling process ensure a high probability to find a stale line in each set.

However, if it is determined (block <NUM>) that there are no clean stale lines in the set, then it may be determined whether there are one or more dirty stale lines in the set, as indicated by block <NUM>. If it is determined (block <NUM>) that there are one or more dirty stale lines in the set, then one of those dirty stale lines may be selected as the victim line, as indicated by block <NUM>. If more than one such line is found, then the first such line that is found may be selected in accordance with block <NUM>. It should be understood that selecting a dirty victim will cause a dirty eviction and consequently pollute the DRAM aware stream of write back consecutive to the scrubber operations.

However, if it is determined (block <NUM>) that there are no clean stale lines in the set, then it may be determined whether there are one or more clean lines in the set that have a lower priority than the incoming line (i.e., the priority of the write request being processed), as indicated by block <NUM>. As described above, the "priority" of a write request may refer to the priority of the sub-cache to which the write request is directed, as each sub-cache may have a predetermined priority relative to other sub-caches. If it is determined (block <NUM>) that there are one or more clean lines in the set that have a lower priority than the incoming line, then one of those lines having the lowest priority may be selected as the victim line, as indicated by block <NUM>. If two or more lines each have the lowest level of priority, then the first such line that is found may be selected in accordance with block <NUM>.

However, if it is determined (block <NUM>) that there are no clean lines in the set that have a lower priority than the incoming line, then it may be determined whether there are one or more dirty lines in the set that have a lower priority than the incoming line, as indicated by block <NUM>. If it is determined (block <NUM>) that there are one or more dirty lines in the set that have a lower priority than the incoming line, then one of those lines may be selected as the victim line, as indicated by block <NUM>. If more than one such line is found, then the first such line that is found may be selected in accordance with block <NUM>. However, if it is determined (block <NUM>) that there are no clean lines in the set that have a lower priority than the incoming line, then the result of the method <NUM> may be that no victim line is found.

An alternative victim search method (not shown) may be similar to the above-described method <NUM> (<FIG>), except that dirty lines may be omitted from consideration as victim line candidates. Accordingly, in the alternative method blocks <NUM>, <NUM>, <NUM> and <NUM> may be omitted. That is, the method flow may proceed from a "no" determination in block <NUM> directly to block <NUM>.

The above-described methods <NUM> (<FIG>), <NUM> (<FIG>) and <NUM> (<FIG>) relate to caching data associated with incoming transaction requests and registering dirty cache lines in the LLQs <NUM> (<FIG>). The methods <NUM>, <NUM> and <NUM> thus may also represent examples of processing described above with regard to blocks <NUM>, <NUM> and <NUM> of the method <NUM> (<FIG>).

As illustrated in <FIG>, a method <NUM> relating to controlling the transfer of cached data to the DRAM using the LLQs <NUM> (<FIG>) is depicted in flow diagram form. The method <NUM> may represent a portion of the processing described above with regard to blocks <NUM> and <NUM> of the method <NUM> (<FIG>). The method <NUM> may represent an example of selecting among the LLQs <NUM> of the sub-group 404A or 404B (<FIG>) based on a sequence. The method <NUM> may control the selection that is conceptually represented in <FIG> by the queue selection logic 408A and 408B. The first and second queue selection logic 408A and 408B (<FIG>) may operate independently of each other. Stated another way, two instances of the method <NUM> may operate independently of and concurrently with each other, a first instance of the method <NUM> controlling the selection represented by the first queue selection logic 408A, and a second instance of the method <NUM> controlling the selection represented by the second queue selection logic 408B. The selection logic <NUM> (<FIG>) may be configured to control the two instances of the method <NUM>.

As indicated by block <NUM>, it may be determined whether the page hit list count (Page_Hit_List_Count) is greater than or equal to a predetermined threshold number (LLQ_PH_TH). The page hit list count is the number of LLQs <NUM> (<FIG>) in which the head entry (page hit bit) indicates a page hit. If it is determined (block <NUM>) that the page hit list count is greater than or equal to the threshold number, then it may be determined whether there are one or more LLQs <NUM> having head entries indicating page hits in a different bank group than the "last winner" (i.e., the LLQ <NUM> that was most recently selected by the method <NUM>), as indicated by block <NUM>. If there is no "last winner" because the determination in block <NUM> is a first iteration after initially beginning the method <NUM>, then the determination in block <NUM> may default to a result of "yes. " If it is determined (block <NUM>) that there are one or more LLQs <NUM> having head entries indicating page hits in a different bank group than the "last winner" (or the determination defaults to "yes"), then the current list (Current_List) may be incremented. The method <NUM> maintains a record or pointer to one of the lists or LLQs <NUM> (<FIG>) that may be referred to as the "current list.

Incrementing the current list means that the next LLQ <NUM> in the sequence becomes the new current list. For example, if the current list is the LLQ <NUM> for Bank <NUM> in BG0, the next list in the sequence is the LLQ <NUM> for Bank <NUM> in BG1. Stated another way, referring to the LLQ <NUM> for Bank_0 in BG0 as the first LLQ <NUM> and to the LLQ <NUM> for Bank_3 in BG3 as the 16th LLQ <NUM>, then the lists may be incremented from the first LLQ <NUM> to the second LLQ <NUM>, etc., to the 16th LLQ <NUM>. The incrementing that is performed in accordance with block <NUM> is modulo <NUM>. That is, if the 16th LLQ <NUM> (i.e., Bank_3 in BG3) is the current list, then incrementing the current list means that the first LLQ <NUM> (i.e., Bank_0 in BG0) becomes the new current list. It may be noted that the sequence represented by the method <NUM> is based on a round-robin sequence among the LLQs <NUM>. While a conventional round-robin sequence would progress from each LLQ <NUM> to the next without regard to other conditions, the method <NUM> represents a modification of a conventional round-robin sequence based on the page hit information.

As indicated by block <NUM>, after incrementing the current list, it may then be determined whether the current list (head entry) indicates a page hit and that page hit is in a different bank group than the last winner. If it is determined that the current list indicates a page hit and in a different bank group than the last winner, then the current list is selected, as indicated by block <NUM>. Referring to <FIG>, information identifying a first selected list is conceptually the output of the first selection logic 408A, and information identifying a second selected list is conceptually the output of the second selection logic 408B. The method flow returns from block <NUM> to block <NUM> in an iterative manner. Note that the selected list also becomes the new "last winner" for purposes of blocks <NUM>, <NUM>, etc..

If it is determined (block <NUM>) that the page hit list count is not greater than or equal to the threshold number, i.e., the page hit list count is less than the threshold number, then the current list may be assigned a value of a saved list (Saved_List). That is, the saved list becomes the new current list. If there is no "saved list" because the method flow has reached the block <NUM> on a first iteration of the method <NUM>, then the saved list may be the same as the current list. That is, the saved list may initially be set to the same list as the current list when the method <NUM> begins operating. Also, referring back to block <NUM>, if it is determined that that there are no LLQs <NUM> having head entries indicating page hits in a different bank group than the last winner, then the method <NUM> continues as described above with regard to block <NUM>.

As indicated by block <NUM>, after the saved list becomes the new current list (block <NUM>) the current list may be incremented. Then, as indicated by block <NUM>, it may then be determined whether the current list is empty. If it is determined that the current list is empty, then the current list may be incremented (block <NUM>) until the current list is not empty.

As indicated by block <NUM> it is determined (block <NUM>) that the current list is not empty, then it may be determined whether there are one or more lists in a different bank group than the last winner, or if the current list is in a different bank group than the last winner. If it is determined that there are no lists in a different bank group than the last winner, or the current list is in a different bank group than the last winner, then the current list may become the saved list (i.e., the current list is saved for a next iteration of the method <NUM>), as indicated by block <NUM>. However, if it is determined that there are one or more lists in a different bank group than the last winner, and the current list is not in a different bank group than the last winner, then the current list may be incremented and the method <NUM> may continue as described above with regard to block <NUM>.

As illustrated in <FIG>, a method <NUM> relating to selecting a rank is depicted in flow diagram form. The method <NUM> may represent a portion of the processing described above with regard to block <NUM> of the method <NUM> (<FIG>). With further reference to <FIG>, the selection logic <NUM> may be configured to control the method <NUM>. The method <NUM> selects a rank (e.g., Rank_0 or Rank_1 in the exemplary embodiment),. The rank selection logic <NUM> may be configured in accordance with the method <NUM>. The rank selection logic <NUM> is thus configured to select a rank. In <FIG>, whichever of Rank_0 and Rank_1 was previously selected at the time the determination indicated by block <NUM> is begun is referred to as the "current rank" (Current_Rank), and whichever of Rank_0 and Rank_1 is not the current rank referred to as the "other rank" (Other_Rank). The current rank may be initialized to either rank prior to the first iteration through the method <NUM>. In <FIG>, the term "list spread" (List_Spread) refers to the number of LLQs <NUM> in a rank that are not empty. The term "minimum list spread" refers to a threshold number that may be predetermined or fixed.

As indicated by block <NUM>, a first condition may be determined: whether the list spread of the current rank is less than the minimum list spread and the list spread of the other rank is greater than or equal to the minimum list spread. As also indicated by block <NUM>, a second condition may be determined: the list spread of the current rank is equal to zero and the list spread of the other rank is not equal to zero. If it is determined that either of the first or second conditions is true, then the current rank may be changed or switched to the other rank, as indicated by block <NUM>. That is, the current rank becomes the other rank, and vice versa. Following block <NUM>, the method <NUM> may return to block <NUM>. However, if it is determined (block <NUM>) that neither of the first and second conditions is true, then the method <NUM> may return to block <NUM> without changing the current rank. That is, the determination indicated by block <NUM> may be repeated essentially continuously without changing the rank so long as neither the first nor second condition is true.

Referring briefly again to <FIG>, the output of the rank selection logic <NUM> is an indication identifying either an LLQ <NUM> in Rank_0 selected by the first queue selection logic 408A or an LLQ <NUM> in Rank_1 selected by the second queue selection logic 408B. In the illustrated embodiment, the output of the rank selection logic <NUM> becomes the output of the selection logic <NUM> (conceptually represented by a logical-AND symbol in <FIG>) only if the selection enable logic <NUM> is enabled; if the selection enable logic <NUM> is not enabled, then the output of the selection logic <NUM> is an indication that no LLQ <NUM> is currently selected. In the illustrated embodiment, a scrubber enable or scrubber activation method, described below with regard to <FIG>, may control whether the selection enable logic <NUM> is enabled. Nevertheless, it should be understood that such a scrubber enable or activation method may enable any of the above-described logic and methods relating to controlling the transfer of cached data to the DRAM using the LLQs <NUM>; enabling the output of the selection logic <NUM> as a final action immediately before the output, after queue selection by queue selection logic 408A and 408B and rank selection by rank selection logic <NUM>, is intended only as an example.

The method <NUM> (<FIG>) may control whether the scrubber <NUM> (<FIG>) is active or inactive, since in the exemplary embodiment the selection logic <NUM> (<FIG>) effectively controls the scrubber operation. When the scrubber <NUM> is active, it identifies dirty cached data for eviction to the DRAM. Evicting (or "cleaning") decreases cache dirtiness. The method <NUM> attempts to adjust the level of scrubber activity to maintain a level of cache dirtiness within a range or window between a high threshold (HT) and a low threshold (LT). This feature may be beneficial in examples of operation in which read and write traffic are competing with each other for memory controller bandwidth. For example, in a PCD write request traffic from a camera client may compete with read request traffic from a display client.

The selection logic <NUM> (<FIG>) or other element of the scrubber <NUM> (<FIG>) may be configured to monitor the total number of linked list entries among all of the LLQs <NUM> as a measure of cache dirtiness. For example, a count of the total number of entries among all of the LLQs <NUM> may be incremented when an entry is added (or "pushed") and decremented when an entry is removed (or "popped") in conjunction with an eviction. In the method <NUM> this measure of cache dirtiness is referred to as "LLQ level.

Although initializations are not shown in <FIG> or other flow diagrams herein for purposes of clarity, the scrubber <NUM> (<FIG>) may be initialized to an inactive state. As indicated by block <NUM>, it may be determined whether the LLQ level is greater than or equal to a predetermined minimum threshold (i.e., a "rock bottom threshold" or RBT). The minimum threshold may be determined empirically. For example, it may be determined statistically that if the pool of candidate cache lines for eviction in a rank is maintained above <NUM> candidates, the result is, with a high probability, a bank spread of about <NUM>. The determination indicated by block <NUM> may repeat until it may be determined that the LLQ level is greater than or equal to the minimum threshold. If it is determined that the LLQ level is greater than or equal to the minimum threshold, then it may be determined whether the scrubber is active, as indicated by block <NUM>. If it is determined that the scrubber is not active, then it may be determined whether the LLQ level is greater than or equal to the high threshold or the number of read requests pending in the memory controller (MCreadOT) is less than a predetermined or fixed threshold (readOTthreshold), as indicated by block <NUM>. If it is determined that the LLQ level is greater than or equal to the high threshold or the number of read requests pending in the memory controller (MCreadOT) is less than the predetermined or fixed threshold (readOTthreshold), then the scrubber may be activated or enabled, as indicated by block <NUM>. The method <NUM> may then return to above-described block <NUM>. If it is determined that the LLQ level is not greater than or equal to the high threshold and the number of read requests pending in the memory controller (MCreadOT) is not less than the predetermined fixed threshold (readOTthreshold), then the method <NUM> may return to above-described block <NUM>.

If it is determined (block <NUM>) that the scrubber is active, then it may be determined whether the LLQ level is less than the low threshold or the number of read requests pending in the memory controller (MCreadOT) is greater than or equal to the predetermined fixed threshold, as indicated by block <NUM>. If it is determined that the LLQ level is less than the low threshold or the number of read requests pending in the memory controller (MCreadOT)is greater than or equal to the predetermined or fixed threshold (readOTthreshold), then the scrubber may be deactivated or disabled, as indicated by block <NUM>. The method <NUM> may then return to above-described block <NUM>. If it is determined that the LLQ level is not less than the low threshold and the number of read requests pending in the memory controller (MCreadOT)is not greater than or equal to the predetermined or fixed threshold (readOTthreshold), then the method <NUM> may return to above-described block <NUM>.

The above-described methods <NUM> (<FIG>), <NUM> (<FIG>), <NUM> (<FIG>), <NUM> (<FIG>), <NUM> (<FIG>) and <NUM> (<FIG>), relating to processing write requests, may be referred to as "DRAM-aware" because they leverage the latency-reducing organization of the DRAM. Similar methods may be provided for DRAM-aware processing of other types of memory transactions. For example, for processing read prefetch requests, instead of storing information identifying cache locations of dirty data in selected LLQs or other data storage structures as described above with regard to, for example, the method <NUM>, read prefetch requests may be stored. And instead of evicting cache lines identified by the contents stored in the selected LLQs or other data storage structures in a DRAM-aware order as described above with regard to, for example, the method <NUM>, the prefetch requests may be sent from the LLQs or other data storage structures to the DRAM (via a memory controller) in such a DRAM-aware order.

As illustrated in <FIG>, a method <NUM> for controlling data caching is depicted in flow diagram form. As indicated by block <NUM>, the method <NUM> may include receiving DRAM transaction requests. As indicated by block <NUM>, the method may further include storing information associated with the transaction requests in data storage structures that are organized in a manner corresponding to the DRAM organization. As indicated by block <NUM>, the method <NUM> may also include controlling transfer of data to the DRAM using the data storage structures.

As illustrated in <FIG>, exemplary embodiments of systems and methods for controlling data caching in a DRAM-aware manner may be provided in a portable computing device ("PCD") <NUM>. For purposes of clarity, data buses or other data communication interconnects are not shown in <FIG>. Some exemplary interconnections, some of which may represent communication via such buses or interconnects, are described for context. Nevertheless, it should be understood that, more generally, various elements described below may communicate with each other via one or more buses or system interconnects.

The PCD <NUM> may include an SoC <NUM>. The SoC <NUM> may include a CPU <NUM>, a GPU <NUM>, a DSP <NUM>, an analog signal processor <NUM>, or other processors. The CPU <NUM> may include multiple cores, such as a first core 1504A, a second core 1504B, etc., through an Nth core 1504N.

A display controller <NUM> and a touch-screen controller <NUM> may be coupled to the CPU <NUM>. A touchscreen display <NUM> external to the SoC <NUM> may be coupled to the display controller <NUM> and the touch-screen controller <NUM>. The PCD <NUM> may further include a video decoder <NUM> coupled to the CPU <NUM>. A video amplifier <NUM> may be coupled to the video decoder <NUM> and the touchscreen display <NUM>. A video port <NUM> may be coupled to the video amplifier <NUM>. A universal serial bus ("USB") controller <NUM> may also be coupled to CPU <NUM>, and a USB port <NUM> may be coupled to the USB controller <NUM>. A subscriber identity module ("SIM") card <NUM> may also be coupled to the CPU <NUM>.

One or more memories may be coupled to the CPU <NUM>. The one or more memories may include both volatile and non-volatile memories. Examples of volatile memories include static random access memory ("SRAM") <NUM> and dynamic RAMs ("DRAM"s) <NUM> and <NUM>. Such memories may be external to the SoC <NUM>, such as the DRAM <NUM>, or internal to the SoC <NUM>, such as the DRAM <NUM>. A DRAM controller <NUM> coupled to the CPU <NUM> may control the writing of data to, and reading of data from, the DRAMs <NUM> and <NUM>. In other embodiments, such a DRAM controller may be included within a processor, such as the CPU <NUM>. The DRAMs <NUM> and <NUM> may be examples of the DRAM <NUM> (<FIG>) or, more generally, any of the DRAMs referenced above with regard to <FIG>. A cache system <NUM>, which may be an example of the cache system <NUM> (<FIG>), may be coupled to the DRAM controller <NUM>.

A stereo audio CODEC <NUM> may be coupled to the analog signal processor <NUM>. Further, an audio amplifier <NUM> may be coupled to the stereo audio CODEC <NUM>. First and second stereo speakers <NUM> and <NUM>, respectively, may be coupled to the audio amplifier <NUM>. In addition, a microphone amplifier <NUM> may be coupled to the stereo audio CODEC <NUM>, and a microphone <NUM> may be coupled to the microphone amplifier <NUM>. A frequency modulation ("FM") radio tuner <NUM> may be coupled to the stereo audio CODEC <NUM>. An FM antenna <NUM> may be coupled to the FM radio tuner <NUM>. Further, stereo headphones <NUM> may be coupled to the stereo audio CODEC <NUM>. Other devices that may be coupled to the CPU <NUM> include one or more digital (e.g., CCD or CMOS) cameras <NUM>.

A modem or RF transceiver <NUM> may be coupled to the analog signal processor <NUM> and the CPU <NUM>. An RF switch <NUM> may be coupled to the RF transceiver <NUM> and an RF antenna <NUM>. In addition, a keypad <NUM>, a mono headset with a microphone <NUM>, and a vibrator device <NUM> may be coupled to the analog signal processor <NUM>.

The SoC <NUM> may have one or more internal or on-chip thermal sensors 1570A and may be coupled to one or more external or off-chip thermal sensors 1570B. An analog-to-digital converter ("ADC") controller <NUM> may convert voltage drops produced by the thermal sensors 1570A and 1570B to digital signals. A power supply <NUM> and a power management integrated circuit ("PMIC") <NUM> may supply power to the SoC <NUM>.

Firmware or software may be stored in any of the above-described memories, such as DRAM <NUM> or <NUM>, SRAM <NUM>, etc., or may be stored in a local memory directly accessible by the processor hardware on which the software or firmware executes. Execution of such firmware or software may control aspects of any of the above-described methods or configure aspects any of the above-described systems. Any such memory or other non-transitory storage medium having firmware or software stored therein in computer-readable form for execution by processor hardware may be an example of a "computer-readable medium," as the term is understood in the patent lexicon.

Claim 1:
A system (<NUM>) for controlling data caching, comprising:
a plurality of data storage structures (<NUM>) collectively having an organization corresponding to a structural organization of a dynamic random access memory, DRAM, wherein each of the plurality of data storage structures is a linked list queue organized in a manner corresponding to a rank, bank group, and bank organization of the DRAM, and each linked list queue corresponds to one of a plurality of banks of the DRAM; and
a cache controller system (<NUM>) configured to:
receive a plurality of transaction requests;
store data associated with the transaction requests in one or more data storage structures selected from among the plurality of data storage structures based on a memory address associated with each transaction request; and
control data transfer to the DRAM using the plurality of data storage structures;
select among the plurality of data storage structures based on a sequence, wherein the sequence is based on at least one of a round-robin selection and DRAM page hit information stored in the data storage structures; and
evict to the DRAM cached data from locations in a data cache indicated by the data stored in the selected data storage structures.