Patent Description:
A system cache shares cache line fills from multiple requestors to retrieve requested information for performing read or write transactions. The requestors may include any combination of devices, such as, for example, central processing units (CPUs), microprocessors, microcontrollers, bus masters, etc. The information may include any combination of code, instructions, data, etc. The shared system cache, however, is a limited resource in which evictions should be managed to keep requestor hit rate sufficiently high for optimal performance. Many configurations include requestors with local caches having prefetch mechanisms with different strategies for requesting information, in which duplicate requests tend to reduce overall efficiency. <CIT> Al describes techniques relating to suspending execution of a processor thread while monitoring for a write to a specified memory location. Near-side prefetch throttling adaptive prefetching is described by <NPL>.

In a first aspect there is defined an adaptive prefetcher for a shared system cache of a processing system including a plurality of requestors, comprising: a cache miss monitor that is configured to monitor requests for information to be stored in the shared system cache and to identify one of the plurality of requestors for which an identified cache line is requested; and a prefetch controller that is configured to submit an adaptive request to request a subsequent cache line to be stored the shared system cache for the identified requestor, wherein the subsequent cache line is determined based on a latency comparison between a loop latency of the prefetch controller and a stream latency of the identified requestor, wherein the loop latency includes a decision delay of the prefetch controller plus a latency of a switch fabric coupled between the plurality of requestors and the shared system cache and the stream latency is a delay between successive operations of the identified requestor.

In a second aspect, there is defined a method of prefetching cache lines into a shared system cache of a processing system including a plurality of requestors, comprising: monitoring memory requests for information to be stored in the shared system cache; identifying one of the plurality of requestors for which an identified cache line is requested; comparing a loop latency of a prefetcher with a stream latency of the identified requestor; determining a subsequent cache line relative to the identified cache line to request based on the latency comparison; and submitting an adaptive request for the subsequent cache line to the shared system cache. In some embodiments, the determining a subsequent cache line comprises skipping a number of cache lines after the identified cache line based on the latency comparison wherein the loop latency includes a decision delay of the prefetch controller plus a latency of a switch fabric coupled between the plurality of requestors and the shared system cache and the stream latency is a delay between successive operations of the identified requestor.

Embodiments of the present invention are illustrated by way of example and are not limited by the accompanying figures. Similar references in the figures may indicate similar elements.

An adaptive prefetcher for a shared system cache as described herein prefetches a selected subsequent cache line based on a latency comparison between a loop latency of the adaptive prefetcher and a stream latency of an identified requestor. The loop latency of a prefetch controller of the adaptive prefetcher includes a decision delay of the prefetch controller plus a latency of switch fabric coupled between multiple requestors and the shared system cache. Each requestor has a stream latency which is a delay between successive operations of that requestor. In one embodiment, the adaptive prefetcher includes a prefetch controller that submits an adaptive request to request the next cache line after skipping SK cache lines for a requestor when the loop latency is greater than SK multiplied by the stream latency and less than or equal to SK+<NUM> multiplied by the stream latency of the requestor, in which SK is an integer of at least zero. The adaptive prefetcher may include a latency memory that stores a stream latency for each of the requestors. The loop and stream latencies may be fixed or may be programmable. The adaptive prefetcher may include, for example, a requestor monitor that updates the stream latencies based on actual measured stream latencies.

A processing system as described herein includes a switch fabric, a system memory, a shared system cache coupled to the switch fabric and to the memory, multiple requestors coupled to the switch fabric, each configured to submit requests to the shared system cache via the switch fabric for information stored in the system memory, and an adaptive prefetcher. The adaptive prefetcher may include a cache miss monitor and a prefetch controller. The cache miss monitor monitors requests for information by the system cache to the system memory and identifies a requestor for which an identified cache line is requested. The prefetch controller submits an adaptive request to the shared system cache via the switch fabric to request a subsequent cache line for the identified requestor, in which the subsequent cache line is determined based on a latency comparison between a loop latency of the prefetch controller and a stream latency of the identified requestor.

A method of prefetching cache lines into a shared system cache of a processing system including a plurality of requestors may include monitoring memory requests for information to be stored the shared system cache, identifying a requestor for which an identified cache line is requested, comparing a loop latency of a prefetcher with a stream latency of the identified requestor, determining a subsequent cache line relative to the identified cache line to request based on the latency comparison, and submitting an adaptive request for the subsequent cache line to the shared system cache. The method may include skipping a number of cache lines after the identified cache line based on the latency comparison. More specifically, the method may include skipping SK cache lines after the identified cache line when the loop latency is greater than SK multiplied by the stream latency and less than or equal to SK+<NUM> multiplied by the stream latency associated with the identified requestor, in which SK is an integer of at least zero. The method may include storing a stream latency for each requestor. The method may include monitoring actual stream latencies of the requestors and updating the stored stream latencies.

<FIG> is a simplified block diagram of a processing system <NUM> including an adaptive shared cache prefetcher (ASCP) <NUM> implemented according to one embodiment of the present disclosure. The processing system <NUM> includes multiple requestors <NUM>, a switch fabric <NUM>, one or more slave devices <NUM>, a memory <NUM>, a shared system level cache (SSLC) <NUM>, and the ASCP <NUM>. Various other supporting devices and circuitry may be included but are not shown as not necessary for a complete understanding of the present disclosure. Any number of requestors <NUM> may be included, such as "N" requestors individually shown as R1, R2,. RN (R1 - RN), and may include one or more of any type of processing device, such as a bus master, a central processing unit (CPU), a microprocessor, a microcontroller, etc. Each of the requestors <NUM> is configured for requesting and processing information, such as code, instructions, data, etc., according to a corresponding read or write transaction. Each of the requestors <NUM> is coupled to the switch fabric <NUM> via a bidirectional interface for reading or writing information.

The switch fabric <NUM> is configured for distributing information requests from the requestors <NUM> to any one or more of the slaves <NUM> or to the memory <NUM> via the SSLC <NUM>, such as according to a memory-mapped scheme or the like. The switch fabric <NUM> may include, for example, a bus system or an array or matrix of switches and the like (not shown). Any number of slave devices <NUM> may be included, such as "M" slaves <NUM> individually shown as S1,. , SM (S1 - SM) and are not further described in detail. The SSLC <NUM> is coupled to the switch fabric <NUM> via a bidirectional interface and may be configured with relatively fast memory devices, such as registers or the like. The memory <NUM> is shown coupled to the SSLC <NUM> via a bidirectional interface for reading or writing information. The memory <NUM> may be configured as any combination of random-access memory (RAM) and read-only memory (ROM) devices for storing information from, or providing information to, the requestors <NUM>.

In one embodiment, the processing system <NUM> is configured as a System-on-Chip (SoC) in which each of the blocks and corresponding circuitry are implemented on a single semiconductor device or integrated circuit (IC). Alternative configurations are contemplated, such as discrete configurations in which one or more of the blocks are implemented or integrated separately.

In operation of the processing system <NUM>, the requestors <NUM> submit requests for information to the slaves <NUM> or the memory <NUM>, in which requests to the memory <NUM> are first submitted to the SSLC <NUM>. In the event of a hit in which the requested information is found stored in the SSLC <NUM>, the requested information may be provided by the SSLC <NUM> directly to the applicable requestor <NUM> via the switch fabric <NUM>. It is noted that each request incorporates a requestor identifier used by the switch fabric <NUM> to identify the applicable requestor <NUM>. In the event of a miss in which the requested information is not stored in the SSLC <NUM>, the SSLC <NUM> forwards the request to the memory <NUM>. The memory <NUM> incorporates addressing circuitry and the like (not shown) which uses addressing information contained within each request for accessing requested information. The memory <NUM> responds to each request by accessing and providing one or more cache lines incorporating the requested information for temporary storage in the SSLC <NUM>, which ultimately forwards the requested information to the applicable requestor <NUM> via the switch fabric <NUM> using the corresponding requestor identifier.

It is appreciated that the SSLC <NUM> is a limited resource having a size targeted to optimize performance without excessive cost. Also, once the SSLC <NUM> becomes full of information retrieved from the memory <NUM> during operation, additional requests cause previously stored information to be evicted according to an applicable eviction policy. Such requests and corresponding evictions should be managed for a given cache size while optimizing the hit rate of requests from the requestors <NUM>.

One or more of the requestors <NUM> may submit a stream of requests from time to time in which each stream includes multiple requests to sequential cache lines in the memory <NUM>. For example, a stream may be submitted for requesting sequential instructions stored in the memory <NUM>, or sequential lines or blocks of data and the like. Although not specifically shown, one or more of the requestors <NUM> may include a local cache with a local prefetcher for requesting a stream of requests for sequentially stored information. The ASCP <NUM> monitors forwarded memory requests from the SSLC <NUM> to the memory <NUM> via a monitor (MON) interface <NUM> (shown as a dashed line). As shown, for example, a memory request <NUM> forwarded from the SSLC <NUM> to the memory <NUM> includes a memory address (M_ADDR) identifying a cache line location within the memory <NUM> storing the requested information to be stored in the SSLC <NUM>. The memory request <NUM> may further include a requestor identifier (RID) identifying one of the requestors <NUM> that requested the information. In addition, depending upon the particular implementation, the information packet <NUM> and may also a thread identifier (TID) for identifying the thread being executed on the requestor that requested the information.

As described further herein, the ASCP <NUM> is configured to anticipate future requests of one or more of the requestors <NUM> and to submit corresponding adaptive requests via an adaptive request (AREQ) interface <NUM> provided to another input of the switch fabric <NUM>. The adaptive requests are made by the ASCP <NUM> to minimize duplication of, and reduce the total number of, requests submitted by one or more of the requesters <NUM>. Each adaptive request submitted by the ASCP <NUM> via the AREQ interface <NUM> is treated in a similar manner as the requests by the requestors <NUM>. In particular, each adaptive request is forwarded by the switch fabric <NUM> to the SSLC <NUM>, which in turn forwards the adaptive requests to the memory <NUM> for retrieving and storing requested information into the SSLC <NUM>. The ASCP <NUM> may retrieve the RID (and the TID, if applicable) from the memory request <NUM> detected via the monitor interface <NUM> and submit at least one corresponding adaptive request on behalf of the identified entity (e.g., requestor and thread).

The processing system <NUM> incorporates several latencies or delays in which each latency is a measure of elapsed time or delay between successive operations or for a function to complete. Each of the requestors R1 - RN has a stream latency (SL) which is a measure of elapsed time between successive read (RD) or write (WR) transactions. In other words, SL measures delay between successive requests for information to the switch fabric <NUM>. It is noted that the SL may be different for each of the requestors <NUM>. The stream latencies of the requestors R1 - RN are defined as stream latency values SL1, SL2,. , SLN (SL1 - SLN), respectively. Although the SL may be different for different requestors from one implementation to the next, for a given implementation, the SL is generally the same for a given requestor <NUM> over time. In other words, the stream latency values SL1 - SLN may be predetermined and pre-stored for a given configuration. One or more of the requestors <NUM> may execute multiple threads, each associated with a corresponding one of multiple applications or software programs or the like. Each thread of a given requestor <NUM> is assumed to have the same stream latency unless separately identified.

The switch fabric <NUM> has a switch fabric latency (SFL), which is a delay between a request from a requestor <NUM> or from the ASCP <NUM> and when the request is submitted to the SSLC <NUM>. The SSLC <NUM> has a cache latency (CL) which is a measure of the delay from when a request for information is submitted to the SSLC <NUM> to when a miss is determined causing a corresponding request to the memory <NUM>. The delay of a hit depends upon where the information is located within the SSLC <NUM> and is usually less than CL. The ASCP <NUM> has an adaptive decision latency (ADL) from when it detects a miss transaction via the monitor interface <NUM> to when it makes a decision and corresponding adaptive request via the AREQ interface <NUM>. A loop latency (LL) value is defined for the ASCP <NUM> as LL = ADL + SFL which is a delay from a detected miss to when a corresponding adaptive request is provided to the SSC <NUM> from the switch matrix <NUM>.

When a miss occurs in the SSLC <NUM>, a significant latency occurs for retrieving a cache line from the memory <NUM> for storage into the SSLC <NUM> and for ultimately providing the information to the applicable requestor <NUM>. Miss latency can be substantially greater than hit latency, such as on the order of <NUM> times greater or more. Thus, it is desired to optimize operation of the SSLC <NUM> using the ASCP <NUM> to reduce the number of misses as much as possible.

The actual time delay associated with each of the latencies depend upon the specific implementation and configuration. In one embodiment, for example, the processing system <NUM> operates at about <NUM> megahertz (MHz) in which each of the latencies are determined based on a number of cycles of a system clock operating at <NUM> or the like. In a specific <NUM> embodiment, the SFL and CL latencies are each <NUM> cycles or <NUM> nanoseconds (ns), ADL is about <NUM> cycles or <NUM>. 5ns so that LL is about <NUM> cycles or <NUM>. Such specific latency values are exemplary only in which actual latencies may vary for different clock frequencies and circuitry configurations.

<FIG> is a more detailed block diagram of the ASCP <NUM> according to one embodiment of the present disclosure. The ASCP <NUM> includes, or otherwise has access to, a latency memory <NUM> that stores the stream latency values SL1 - SLN for the requestors R1 - RN, respectively. The latency memory <NUM> may also store the LL value defining the loop latency of the ASCP <NUM>. The ASCP <NUM> may further include a cache miss monitor <NUM>, a prefetch controller <NUM>, and a requestor monitor <NUM>. In one embodiment, the loop latency value LL and the stream latency values SL1 - SLN are predetermined and fixed in which the latency memory <NUM> may be implemented using a ROM device or the like. The ROM device may be programmable, such as implemented as an electrically erasable programmable ROM (EEPROM) or the like. In an alternative embodiment, the latency memory <NUM> may be implemented as RAM device. The SL1 - SLN and LL values may still be predetermined and fixed, in which the values may be loaded into the latency memory <NUM> upon power up or reset (POR) or the like. Alternatively, one or more of the loop latency value LL and stream latency values SL1 - SLN may be programmable and may even be adjusted over time. In one embodiment, for example, the requestor monitor <NUM> that monitors activity and timing of one or more of the Requestors <NUM> and updates the corresponding stream latency values SL1 - SLN accordingly.

The cache miss monitor <NUM> monitors requests from the SSLC <NUM> to the memory <NUM> via a monitor interface <NUM> in response to misses of the SSLC <NUM>, such as, for example, the memory request <NUM>. In one embodiment, the cache miss monitor <NUM> forwards the RID (and if applicable, the TID) of the memory request <NUM> to the prefetch controller <NUM>. The prefetch controller <NUM> retrieves the LL value and uses the RID value to retrieve a corresponding stream latency value SLX from the latency memory <NUM>, in which SLX is a selected one of the stream latency values SL1 - SLN. For example, RID may be used as or converted to a lookup value for retrieving the corresponding SLX. It is noted that the LL value may alternatively be stored or otherwise hardwired within the prefetch controller <NUM>. In addition, or in the alternative, the cache miss monitor may use RID to assert a stream latency select (SL_S) value (e.g., a lookup value or the like) to the latency memory <NUM> for selecting the corresponding SLX. The prefetch controller <NUM> uses the retrieved information to construct and submit a corresponding adaptive request to the switch controller <NUM> via the AREQ interface <NUM>. As further described herein, the adaptive requests are selected as anticipatory requests to optimize performance of the system cache SSLC <NUM>. In various embodiments, the prefetch controller <NUM> compares LL with SLX of the applicable requestor <NUM> to determine which information from the memory <NUM> to subsequently request for the requestor <NUM> identified by RID.

<FIG> is a simplified graphic diagram plotting stream latency (SL) versus loop latency LL illustrating operation of the prefetch controller <NUM> according to one embodiment of the present disclosure. SL and LL may be measured in units of time or in units of cycles of a clock or frequency of operation. The prefetch controller <NUM> compares SL and LL for construction an adaptive request for requesting a subsequent cache line for an applicable one of the requestors <NUM>. The comparison between SL and LL determines how many cache lines to skip for selecting the cache line to request in the adaptive request. The LL value is the loop latency of the ASCP <NUM>, and the SL value generally represents a selected one of the latency SL1 - SLN values for a corresponding one of the requestors R1 - RN, respectively, where it is understood that each of the requestors <NUM> may have a different SL value. Again, the LL value or the SL1 - SLN values may be fixed for a given configuration or may be programmable.

A first plotted line <NUM> represents the case in which LL = SL, a second plotted line <NUM> represents the case in which LL = SL*<NUM> (in which an asterisk denotes multiplication), and so on up to a last line <NUM> representing the case in which LL = SL*(SK+<NUM>), where SK is an integer factor value of <NUM> or greater. According to the graphic diagram, when LL ≤ SL such that operation is in a first area <NUM> (SK = <NUM>), then the prefetch controller <NUM> of the ASCP <NUM> does not skip any cache lines (e.g., skips SK = <NUM> cache lines) and requests the next cache line. When SL < LL ≤ SL*<NUM> such that operation is in area <NUM> (SK = <NUM>), then the prefetch controller <NUM> skips SK = <NUM> cache line and then requests the next cache line. Although not specifically shown, this pattern repeats for each successive line defining a corresponding area between sequential lines. Thus, for example, when SL*<NUM> < LL ≤ SL*<NUM>, then the prefetch controller <NUM> skips <NUM> cache lines, or when SL*<NUM> < LL < SL*<NUM>, then the prefetch controller <NUM> skips <NUM> cache lines, and so on. The last plotted line <NUM> represents the general case in which the prefetch controller <NUM> skips SK cache lines when SL*SK < LL ≤ SL*(SK+<NUM>) as shown by area <NUM>. For example, the first line <NUM> and area <NUM> are applicable when SK = <NUM> in which case the prefetch controller <NUM> skips SK = <NUM> cache lines when <NUM> < LL ≤ SL, the second line <NUM> and area <NUM> are applicable when SK = <NUM> in which case the prefetch controller <NUM> skips SK = <NUM> cache line when SL < LL ≤ SL*<NUM>, and so on.

<FIG> is a diagram illustrating operation of the ASCP <NUM> having loop latency LL for requesting cache lines for various ones of the requestors <NUM> with different stream latencies according to one embodiment of the present disclosure. In each of three illustrated scenarios <NUM>, <NUM>, and <NUM>, cache lines are being requested by an applicable one of the requestors <NUM>, in which the ASCP <NUM> is submitting adaptive cache line requests for that same requestor.

In the first scenario <NUM>, LL is less than the stream latency SL1 of the requestor R1. After R1 requests a first cache line <NUM>, the ASCP <NUM> does not skip any cache lines but requests the next cache line <NUM>. Operation may continue in similar manner, in which R1 requests line <NUM> followed by ASCP <NUM> requesting the next cache line <NUM>, and so on. Assuming that R1 continues to request sequential cache lines, the ASCP <NUM> avoids duplicate requests and enables R1 to skip every other cache line thereby improving overall efficiency.

In the second scenario <NUM>, LL is greater than the stream latency SL2 of the requestor R2 but is less than <NUM>*SL2. In this case, after R2 requests the first cache line <NUM>, the ASCP <NUM> skips cache line <NUM> and requests cache line <NUM>. Operation may continue in similar manner, such that before the ASCP <NUM> requests cache line <NUM>, R2 has requested cache line <NUM>, so that the cache lines are requested in order. Assuming that R2 continues to request sequential cache lines, the ASCP <NUM> avoids duplicate requests and enables R2 to skip every third cache line thereby improving overall efficiency.

In the second scenario <NUM>, LL is greater than twice the stream latency SLX of an arbitrary numbered requestor RXbut is less than <NUM>*SLX. In this case, after RX requests the first cache line <NUM>, the ASCP <NUM> skips <NUM> cache lines <NUM> and <NUM> and requests cache line <NUM>. Operation may continue in similar manner, such that before the ASCP <NUM> requests cache line <NUM>, RXhas requested cache lines <NUM> and <NUM>, so that the cache lines are requested in order. Assuming that RX continues to request sequential cache lines, the ASCP <NUM> avoids duplicate requests and enables RXto skip every fourth cache line thereby improving overall efficiency.

<FIG> is a simplified flowchart diagram illustrating operation of the ASCP <NUM> according to an embodiment of the present disclosure. At first block <NUM>, the cache miss monitor <NUM> monitors memory access requests from the SSLC <NUM> to the memory <NUM>, such as, for example, the memory request <NUM>. At next block <NUM>, the cache miss monitor <NUM> or the like identifies one of the requestors <NUM> for which an identified cache line is requested. The memory request <NUM>, for example, includes a requestor identifier RID identifying one of the requestors R1 - RN, and also includes a memory address M_ADD or the like for identifying the requested cache line. At next block <NUM>, either the cache miss monitor <NUM> or the prefetch controller <NUM> determines or otherwise retrieves the stream latency SLX for the identified requestor RX, such as from the latency memory <NUM>. At next block <NUM>, the prefetch controller <NUM> compares the loop latency LL with the stream latency SLX of the identified requestor RX. At next block <NUM>, the prefetch controller <NUM> determines a subsequent cache line relative to the identified cache line to request based on the latency comparison, such as according to SL*SK < LL ≤ SL*(SK+<NUM>) for determining a number of lines to skip from the identified cache line. At next block <NUM>, the prefetch controller <NUM> submits an adaptive request to the SSLC <NUM> via the switch fabric <NUM> for the subsequent cache line.

At next block <NUM>, it is queried whether to continue monitoring and adaptive requesting. If so, operation loops back to block <NUM> for continued monitoring. Operation may continue for subsequent lines of the same requestor <NUM> or for another requestor depending upon memory requests submitted by the SSLC <NUM>. If operation is not to be continued, operation is completed.

An adaptive prefetcher for a shared system cache of a processing system including multiple requestors having a cache miss monitor and a prefetch controller. The cache miss monitor monitors requests for information from memory and identifies one of the requestors for which an identified cache line is requested. The prefetch controller submits an adaptive request for a subsequent cache line. The subsequent cache line may be determined based on a latency comparison between a loop latency (LL) of the prefetch controller and a stream latency (SL) of the identified requestor. A latency memory may be included that stores stream latencies for the requestors. The latency comparison may be used to determine how many cache lines to skip relative to the identified cache line, such as according to SL*SK < LL ≤ SL*(SK+<NUM>) in which SK is the number of cache lines to skip.

Although the present invention has been described in connection with several embodiments, the invention is not intended to be limited to the specific forms set forth herein. For example, variations of positive circuitry or negative circuitry may be used in various embodiments in which the present invention is not limited to specific circuitry polarities, device types or voltage or error levels or the like. For example, circuitry states, such as circuitry low and circuitry high may be reversed depending upon whether the pin or signal is implemented in positive or negative circuitry or the like. In some cases, the circuitry state may be programmable in which the circuitry state may be reversed for a given circuitry function.

Claim 1:
An adaptive prefetcher (<NUM>) for a shared system cache (<NUM>) of a processing system (<NUM>) including a plurality of requestors (<NUM>), the adaptive prefetcher (<NUM>) comprising:
a cache miss monitor (<NUM>) that is configured to monitor requests for information to be stored in the shared system cache (<NUM>) and to identify one of the plurality of requestors (<NUM>) for which an identified cache line is requested; and
a prefetch controller (<NUM>) that is configured to submit an adaptive request to request a subsequent cache line to be stored in the shared system cache (<NUM>) for the identified requestor, wherein the subsequent cache line is determined based on a latency comparison between a loop latency of the prefetch controller (<NUM>) and a stream latency of the identified requestor;
wherein the loop latency includes a decision delay of the prefetch controller (<NUM>) plus a latency of a switch fabric (<NUM>) coupled between the plurality of requestors (<NUM>) and the shared system cache (<NUM>) and the stream latency is a delay between successive operations of the identified requestor.