Prefetcher with arbitrary downstream prefetch cancelation

CLAIM OF PRIORITY

p-0002This application for Patent claims priority to U.S. Provisional Application No. 61/387,367 (attorney docket TI-69642PS) entitled “Combined integer to floating point conversions with varied precision formats” filed Sep. 28, 2010, and claims priority to U.S. Provisional Application No. 61/384,932 (attorney docket TI-69858) entitled “Prefetch Stream Filter with FIFO Allocation and Stream Direction Prediction” filed Sep. 21, 2010, wherein the applications listed above are incorporated by reference herein.

BACKGROUND

p-0003In computer architecture applications, processors often use caches and other memory local to the processor to access data during execution. The processors more efficiently execute instructions when, for example, program data (e.g., machine code) and data (e.g., operands) accessed by a processor are stored locally in a cache. However, a local cache often accesses a shared memory which can result in contention issues that arise when multiple requesters try to access a shared memory resource. The problem is compounded when multiple caches (often having differing line sizes and timing requirements) of multiple processors are used together in a multiprocessor system. Speculative fetches from various memory controllers in a multiple processor system also contend for the same downstream memory resources.

p-0004The problems noted above are solved in large part by a prefetching system that allows downstream memory controllers to arbitrarily cancel various speculative prefetches. The disclosed prefetch cancelation arbiter improves access to a shared memory resource by arbitrarily canceling speculative prefetches. The prefetch cancelation arbiter applies a set of arbitrary policies to speculative prefetches to select one or more of the received speculative prefetches to cancel. The selected speculative prefetches are canceled and a cancelation notification of each canceled speculative prefetch is sent to a higher-level memory component such as a prefetch unit or a local memory arbiter that is local to the processor associated with the canceled speculative prefetch. The set of arbitrary policies is used to reduce memory accesses to the shared memory resource in certain conditions.

BRIEF DESCRIPTION OF THE DRAWINGS

p-0005<figref idrefs="DRAWINGS">FIG. 1</figref> depicts an illustrative computing device <b>100</b> in accordance with embodiments of the disclosure.

p-0006<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram illustrating a computing system including a (local) memory arbiter in accordance with embodiments of the disclosure.

p-0007<figref idrefs="DRAWINGS">FIG. 3</figref> is a timing diagram illustrating multi-stream memory accesses over time.

p-0008<figref idrefs="DRAWINGS">FIG. 4</figref> is a block diagram illustrating a memory controller that includes a multi-stream prefetch unit in accordance with embodiments of the present disclosure.

p-0009<figref idrefs="DRAWINGS">FIG. 5</figref> is a block diagram illustrating a data prefetch unit in accordance with embodiments of the present disclosure.

p-0010<figref idrefs="DRAWINGS">FIG. 6</figref> is a block diagram illustrating a program prefetch unit in accordance with embodiments of the present disclosure.

p-0011<figref idrefs="DRAWINGS">FIG. 7</figref> is a block diagram illustrating a local memory arbiter in accordance with embodiments of the present disclosure.

p-0012<figref idrefs="DRAWINGS">FIG. 8</figref> is a process diagram illustrating arbitrary cancelation of speculative prefetches in accordance with embodiments of the present disclosure.

DETAILED DESCRIPTION

p-0013The following discussion is directed to various embodiments of the invention. Although one or more of these embodiments may be preferred, the embodiments disclosed should not be interpreted, or otherwise used, as limiting the scope of the disclosure, including the claims. In addition, one skilled in the art will understand that the following description has broad application, and the discussion of any embodiment is meant only to be exemplary of that embodiment, and not intended to intimate that the scope of the disclosure, including the claims, is limited to that embodiment.

p-0014Certain terms are used (throughout the following description and claims) to refer to particular system components. As one skilled in the art will appreciate, various names can be used to refer to a component. Accordingly, distinctions are not necessarily made herein between components that differ in name but not function. In the following discussion and in the claims, the terms “including” and “comprising” are used in an open-ended fashion, and thus are to be interpreted to mean “including, but not limited to . . . .” Also, the terms “coupled to” or “couples with” (and the like) are intended to describe either an indirect or direct electrical connection. Thus, if a first device couples to a second device, that connection can be through a direct electrical connection, or through an indirect electrical connection via other devices and connections. As used herein, a single device that is coupled to a bus (which includes one or more signals) can represent all instances of the devices that are coupled to each signal of the bus.

p-0015<figref idrefs="DRAWINGS">FIG. 1</figref> depicts an illustrative computing device <b>100</b> in accordance with embodiments of the disclosure. The computing device <b>100</b> is, or is incorporated into, a mobile communication device <b>129</b> (such as a mobile phone or a personal digital assistant such as a BLACKBERRY® device), a personal computer, automotive electronics, or any other type of electronic system.

p-0016In some embodiments, the computing device <b>100</b> comprises a megacell or a system-on-chip (SoC) which includes control logic such as a CPU <b>112</b> (Central Processing Unit), a storage <b>114</b> (e.g., random access memory (RAM)) and tester 110. The CPU <b>112</b> can be, for example, a CISC-type (Complex Instruction Set Computer) CPU, RISC-type CPU (Reduced Instruction Set Computer), or a digital signal processor (DSP). The storage <b>114</b> (which can be memory such as SRAM (static RAM), flash memory, or disk storage) stores one or more software applications <b>130</b> (e.g., embedded applications) that, when executed by the CPU <b>112</b>, perform any suitable function associated with the computing device <b>100</b>. The tester <b>110</b> comprises logic that supports testing and debugging of the computing device <b>100</b> executing the software application <b>130</b>. For example, the tester <b>110</b> can be used to emulate a defective or unavailable component(s) of the computing device <b>100</b> to allow verification of how the component(s), were it actually present on the computing device <b>100</b>, would perform in various situations (e.g., how the component(s) would interact with the software application <b>130</b>). In this way, the software application <b>130</b> can be debugged in an environment which resembles post-production operation.

p-0017The CPU <b>112</b> typically comprises memory and logic which store information frequently accessed from the storage <b>114</b>. Various subsystems (such as the CPU <b>112</b> and/or the storage <b>114</b>) of the computing device <b>100</b> include one or more prefetching systems <b>116</b>, which are used to arbitrate certain memory operations during the execution of the software application <b>130</b>.

p-0018Prefetching systems <b>116</b> track memory commands from one or more streams using “slots” to maintain pointers to memory addresses used to prefetch data for each stream. In a multi-core shared memory system, the requests are generated by there are multiple cores competing for the same memory resources. However, speculative fetches from a prefetch unit can actually decrease performance in a system by flooding a shared resource with potentially useless requests (e.g., such as program prefetches that might not be used in the case of a program flow branch). This can actually reduce performance during windows of time where heavy accessing of memory occurs.

p-0019Disclosed herein are techniques for reducing memory contention issues that are compounded by speculative fetching of memory. The disclosed techniques allow “downstream” memory components (e.g., that receive prefetch requests for data in memory) to cancel any prefetch for any reason. This flexibility allows any downstream component in the memory system to throttle (e.g., selectively scale back amounts of) speculative prefetches on an as-needed basis (such as during times of heavy memory accesses). Distributing the control for cancelation of speculative prefetches allows an arbitrary memory controller to flexibly enforce its own rules on bandwidth management of its own environment. This approach of distributed prefetch cancelation also thus minimizes the amount of communication (and wiring) used between various memory system components that would be otherwise used.

p-0020<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram illustrating a computing system including a (local) memory arbiter in accordance with embodiments of the disclosure. Computing device <b>100</b> is illustrated as an SoC <b>200</b> that includes one or more DSP cores <b>210</b>, L2 (level-2) SRAM/Caches <b>220</b>, and shared memory <b>230</b>. Although the illustrated elements of the computing system <b>200</b> are formed using a common substrate, the elements can also be implemented in separate substrates, circuit boards, and packages (including the shared memory <b>230</b>).

p-0021Each DSP core <b>210</b> optionally includes a prefetch unit <b>222</b> for prefetching data for, for example, an L1 (level-one) data cache such as L1 SRAM/Cache <b>212</b> and/or an L2 (level-two cache) such as L2 SRAM/Cache <b>220</b>. Each DSP core <b>210</b> has a local memory such as L2 SRAM/Cache <b>220</b> to provide relatively quick access to read and write memory. Additionally, each DSP core <b>210</b> is coupled to a shared memory <b>230</b>, which usually provides slower (and typically less expensive) memory accesses than SRAM/Cache <b>220</b>. The shared memory <b>230</b> stores program and data information that can be shared between each DSP core <b>210</b>.

p-0022In various embodiments, each DSP core <b>210</b> is associated with a local memory arbiter <b>224</b> for reordering memory commands in accordance with a set of reordering rules. Thus, memory requests from differing streams from different processors are each arbitrated in accordance with each local level before the memory requests before sending the memory requests to a central memory arbiter <b>234</b>. The central memory arbiter <b>234</b> is arranged to control memory accesses for shared memory that are generated by differing “cores” (e.g., processors) that do not share a common memory arbiter <b>224</b>. As discussed further below, the central memory arbiter is arranged to cancel (e.g., squash) pending, speculative prefetches on an as-needed (or as-desired) basis.

p-0023<figref idrefs="DRAWINGS">FIG. 3</figref> is a timing diagram illustrating multi-stream memory accesses over time. Plot <b>300</b> vertically represents increasing memory addresses and horizontally represents memory accesses of data over time. The time continuum illustrated horizontally is divided into three periods (<b>302</b>, <b>304</b>, and <b>306</b>) that represent periods in time in which an execution of a program is, for example, evaluating different equations. In period <b>302</b>, a program executing a programming loop statement [1] such as (in “c” language):

p-0024<br />for (<i>i</i>=<b>0</b>; <i>i&lt;n; i++</i>){<i>d[i]=a[i]+b[i]+c[i]} </i>  [1]

p-0025performs memory accesses that, when plotted, produces traces (designated generally) <b>310</b>. Each reference to an element of arrays “a,” “b,” “c,” and “d” respectively produces a trace that, over time, progresses higher in address space. Thus, each trace of traces <b>310</b> is an illustration of a stream.

p-0026When variable “i” reaches terminal count “n,” the program execution proceeds to period <b>304</b>, where (for example) traces <b>320</b> are formed when another loop statement is executed. Likewise, traces <b>330</b> are formed when program execution proceeds into period <b>306</b> and re-executes programming loop statement [1]. Thus, each trace of the traces <b>320</b> and <b>330</b> is an illustration of a stream, and the plot <b>300</b> generally illustrates multi-stream memory accesses.

p-0027<figref idrefs="DRAWINGS">FIG. 4</figref> is a block diagram illustrating a memory controller that includes a multi-stream prefetch unit in accordance with embodiments of the present disclosure. Memory controller <b>400</b> includes a local memory interface <b>410</b>. The local memory interface <b>410</b> provides an interface and protocol system to handle memory requests for a local memory such as L2 SRAM/Cache <b>220</b>. In addition to providing address, read data, and write data signals, the local memory interface <b>410</b> provides information concerning prefetchability, cacheability, and an indication of half-line L2 (e.g., cache “level two”) line allocation in metadata signals. The local memory interface <b>410</b> signals include information concerning command signals detailing a request, elevating the priority of a request, indicating a data versus instruction (e.g., program data) fetch, indicating whether a request is “cacheable in L2” cache, indicating a cache line size of request, and indicating a privilege/secure level of the request.

p-0028Memory controller <b>400</b> includes a shared memory interface <b>420</b>. The shared memory interface <b>420</b> provides an interface and protocol system to handle memory requests for a shared memory such as shared memory <b>230</b>. The shared memory interface <b>420</b> also provides additional metadata to shared memory and/or external slaves. The metadata provides information such as memory segmentation endpoints, physical addresses within sections of segmented memory, cacheability of requests, deferred privilege checking, request for access type (data, instruction or prefetch), and request priority and elevated priority.

p-0029Memory controller <b>400</b> includes unit for memory protection/address extension <b>430</b>. The unit for memory protection/address extension <b>430</b> performs address range lookups, memory protection checks, and address extensions by combining memory protection and address extension into a single, unified process. The memory protection checks determine what types of accesses are permitted on various address ranges within the memory controller <b>400</b>'s 32-bit logical address map. The address extension step projects those accesses onto a larger 36-bit physical address space.

p-0030Memory controller <b>400</b> can be controlled and configured using configuration tieoffs <b>440</b> and configuration/status registers <b>450</b>. Configuration tieoffs <b>440</b>, for example, can be set during the manufacturing process to configure operation of the memory controller <b>400</b> for a specific system. Configuration/status registers <b>450</b>, for example, can be set during operation to configure and control operation of the memory controller <b>400</b> by reading status indications and providing commands.

p-0031Memory controller <b>400</b> includes a multi-stream prefetch unit <b>460</b>. The multi-stream prefetch unit <b>460</b> includes a selector <b>462</b> that chooses a prefetch unit based upon the type of memory request that is received. When, for example, a request from a level-one data cache is received, the selector <b>462</b> enables data prefetch unit <b>464</b> to handle potential prefetches for the received data memory request. Likewise, when a request from a level-one program cache is received, the selector <b>462</b> enables program prefetch unit <b>466</b> to handle potential prefetches for the received program memory request. The prefetch units are notified by “downstream” memory components when their pending prefetch requests are canceled by a downstream memory component, and can regenerate the canceled prefetch requests in certain circumstances as discussed below. The data prefetch unit <b>464</b> is discussed below with respect to <figref idrefs="DRAWINGS">FIG. 5</figref> and the program prefetch unit <b>466</b> is discussed below with respect to <figref idrefs="DRAWINGS">FIG. 6</figref>.

p-0032<figref idrefs="DRAWINGS">FIG. 5</figref> is a block diagram illustrating a data prefetch unit in accordance with embodiments of the present disclosure. Data prefetch unit <b>464</b> typically includes a prefetch filter <b>510</b> (which is used for identification of streams), a data prefetch buffer <b>520</b> (which is used to prefetch data for streams having assigned slots), and a prefetch predictor <b>550</b> (for predicting and controlling output buffers of the data prefetch buffer).

p-0033Identification of streams is a difficult problem as modern DSP (digital signal processor) code often contains data streams that progress in both incrementing (upward) and decrementing (downward) directions. Memory accesses also include many non-streaming accesses (which often have the appearance of random accesses as viewed in a memory access footprint plot, and are thus referred to as “random accesses” herein) that are not part of a predictable access pattern such as streams. Attempting to prefetch cache lines based on every memory request would result in a lot of unusable speculative traffic, which greatly amplifies memory bandwidth requirements and negatively impacts performance. The disclosed prefetch filter <b>510</b> works to filter out these random (non-streaming and/or non-prefetchable) accesses so that only predictable streams are used by the data prefetch buffer <b>520</b> to prefetch.

p-0034Prefetch filter <b>510</b> is also arranged to correctly predict direction as well as the location of streams. Stream detectors typically hold addresses for potentially identifying streams while waiting for a cache read to “hit” an address associated with one of the potential streams. Thus, address prediction, direction prediction, and replacement policies for the stream detector affect the performance of the data prefetch unit <b>464</b>.

p-0035Prefetch filter <b>510</b> uses an aligned power-of-two address window, which is used to detect sequential accesses and to determine a direction of a stream. (As discussed below, the disclosed prefetch filter <b>510</b> in most cases only takes two sequential accesses to detect a stream, and otherwise, when the direction estimate is wrong, it would only take a third access to verify the direction of a stream to be identified.)

p-0036The direction estimate heuristic and FIFO-based allocation architecture minimizes power and area requirements due to their implementation efficiency while maintaining a high level of performance when executing DSP algorithms for emerging applications. Not requiring an adder to generate a sequential address for the address prediction function minimizes latency and thus improves the operating frequency of a filter implemented by a DSP that incorporates a data prefetch unit <b>464</b>.

p-0037Prefetch filter <b>510</b> is a stream detection filter that includes a 12-address candidate buffer. Each slot of prefetch filter <b>510</b> stores one of up to 12 potential stream “head” (e.g., starting) addresses as logical addresses, along with a single bit (field <b>514</b>) to indicate the predicted stream direction associated with that slot. Prefetch filter <b>510</b> uses a FIFO allocation order to assign a candidate stream to a slot, which is determined by a simple FIFO counter <b>516</b> (various counting systems, such as Gray code, can be used). Each new allocation of a candidate stream in the prefetch filter <b>510</b> uses the next slot number indicated by the FIFO counter <b>516</b>. Allocation in the prefetch filter <b>510</b> proceeds, starting at slot #<b>0</b>, counting to slot #<b>11</b>, and then wrapping back to slot #<b>0</b> when all 12 slots have been previously allocated.

p-0038Each candidate field <b>512</b> is initialized with zeros and is used to store a significant portion (e.g., most significant bits or portion) of an address of a memory access of a potential stream. Likewise, each direction field (DIR) <b>514</b> is initialized with a bit set to indicate a positive (or, alternatively, a negative) direction that is used to determine a successive prefetch address. A particular direction field <b>514</b> can be set by comparing the next memory request of a stream with the address of the stream head (or an incremented stream head).

p-0039For example, a demand request (a memory request that originates from the program processor) is received. An address of the demand request is compared with each of the candidate field <b>512</b> values, and if none match, the demand request is passed to shared (or main) memory, and the address of the demand request is modified (e.g., incremented or decremented in accordance with the direction field <b>514</b>) and placed in the candidate field <b>512</b> that is pointed to by FIFO counter <b>516</b> (which in turn is incremented or wrapped around to zero at a terminal count). When a subsequent demand request is received and matches one of the candidate field <b>512</b> values (a “hit”), the value of the candidate field <b>512</b> (or a modified value thereof) is entered into the data prefetch buffer <b>520</b> (and the hit is “qualified” as discussed below), and the candidate field <b>512</b> is reset (e.g., erased or invalidated). If the subsequent demand request that is received matches one of the candidate fields <b>512</b> by a value modified (e.g., decremented or incremented) twice, the direction field is inverted and the value of the candidate field is transferred (as discussed below). In the event of a qualified hit, the direction field <b>514</b> value is transferred to the direction field <b>524</b> of the data prefetch buffer <b>520</b>.

p-0040Thus, candidate field <b>512</b> entries in the prefetch filter <b>510</b> have the potential to become prefetch streams. The detection filter first determines whether memory accesses meet criteria such as whether the memory access is prefetchable, whether the memory access is a cache line fill for data, whether the memory access is an L1D (level-one data cache) access, whether the memory access is a non-critical half of an L2 line (level-two cache) line access, and whether the memory access is not already present in the data prefetch buffer <b>520</b>.

p-0041The memory accesses meeting the preceding qualifications are then compared against the existing entries of potential streams in the various slots of the prefetch filter <b>510</b>. L1D requests are compared at 64 byte granularity, whereas L2 requests are compared at 128 byte granularity. Whether a stream associated with a memory access is entered in to a slot is determined by whether the memory access matches an entry in the prefetch filter <b>510</b>.

p-0042If the memory access does not match an existing entry (a “miss”), the prefetch filter <b>510</b> allocates a new filter slot and places the predicted next address and predicted stream direction in the newly allocated slot (selected by FIFO counter <b>516</b>). The prefetch filter <b>510</b> does not always protect against redundant entries, which normally only occur when thrashing the cache, and are thus relatively rare occurrences. Table 1 illustrates the logic for how a direction of a stream is predicted on the basis of the origin of the memory access (request), the requested address, and the predicted address.

p-0043<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="35pt" align="left" /><colspec colname="3" colwidth="77pt" align="left" /><colspec colname="4" colwidth="63pt" align="left" /><thead><row><entry namest="1" nameend="4" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row><row><entry /><entry>Requested</entry><entry /><entry /></row><row><entry>Requestor</entry><entry>Address</entry><entry>Predicted Address</entry><entry>Predicted Direction</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>L1D</entry><entry>Bit 6 = 0</entry><entry>Requested address + 64</entry><entry>Increasing address</entry></row><row><entry>L1D</entry><entry>Bit 6 = 1</entry><entry>Requested address − 64</entry><entry>Decreasing address</entry></row><row><entry>L2</entry><entry>Bit 7 = 0</entry><entry>Requested address + 128</entry><entry>Increasing address</entry></row><row><entry>L2</entry><entry>Bit 7 = 1</entry><entry>Requested address − 128</entry><entry>Decreasing address</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

p-0044If the memory access request does match an existing entry in a slot of the prefetch filter <b>510</b>, the prefetch filter <b>510</b> allocates a new stream slot for the stream. The new stream slot is allocated by initializing its address to the next address in that stream according to the direction bit stored with that slot. After allocating the new stream slot, prefetches are initiated for the new stream slot. Thus, all new streams are initiated by having addresses that (over time) cross a 128 byte (L1D stream) or 256 byte (L2 stream) boundary. Thus, the first two fetches for each L1D stream (being half the size of L2 streams) normally correspond to the two half-slots of a single slot.

p-0045When an applicable L1 request hits in the buffer, the presence of the second half of the 128-byte line is queried. If it is not valid (such as because the prefetch has been canceled), then a prefetch is generated to refetch the neighboring half of the 128-byte line.

p-0046Data prefetch unit <b>464</b> includes the data prefetch buffer <b>520</b>, which is used to prefetch data for streams having assigned slots. In an embodiment, data prefetch unit <b>464</b> is a relatively simple prefetch engine for servicing direct L1D (level-one data) cache requests and L2 data fetches. The data prefetch unit <b>464</b> uses an extended memory prefetch scheme, extended to the full address space in shared memory. The data prefetch unit <b>464</b> handles cacheable, prefetchable data fetches as candidates for prefetching.

p-0047The data prefetch unit <b>464</b> holds eight logical slots, each of which is associated with storage for two 64-byte data fetches such as buffer A and B of PF (prefetch) data <b>536</b>. Double buffering the data for each slot in PF data <b>536</b> allows for a prefetch to be started on a subsequent prefetch (for example) using buffer B before a memory request is made for the data in buffer A of the slot (e.g., a return-wait situation). The data prefetch unit <b>464</b> can reallocate a slot immediately if at least one of its two halves (e.g., buffer A or buffer B of PF data <b>536</b>) is not busy and the slot is not in a hit-wait state (e.g., waiting for data associated with a data prefetch unit <b>464</b> hit to be read-out). The double-buffer approach allows new prefetch generation to proceed immediately in case a prefetch hit results in a return-wait situation (where, for example, for a prefetch to be started on a subsequent prefetch (for example) using buffer B before a memory request is made for the data in buffer A of the slot). Double buffering each slot of the data prefetch unit <b>464</b> speeds prefetching because the data prefetch unit <b>464</b> will normally need to reallocate the slot that the most recent demand fetch just hit, and the time of allocation when the local memory will read the data for the hit is not ascertainable beforehand. Thus the double-buffer approach allows the prefetch generation to proceed even before data prefetch unit <b>464</b> sends the hit data to the upstream local memory (e.g., SRAM/Cache <b>220</b>).

p-0048Also, the data prefetch buffer <b>520</b> avoids reallocating a slot in the hit-wait state in case the prefetch associated with the slot is canceled. When the prefetch is canceled, the data prefetch unit <b>464</b> uses the address stored in the slot to regenerate the demand fetch (“demand fetch reconstruction”). When prefetches are canceled the address in the data prefetch buffer <b>520</b> remains active so that streams can be resumed without re-learning them (e.g., being “discovered” by the prefetch filter <b>510</b>).

p-0049For example, a prefetch can be canceled by a downstream memory component when a new prefetch too generated early by the data prefetch unit <b>464</b> may force the stream prefetch unit <b>460</b> (belonging to a neighboring slave, for example) to cancel the earlier prefetch. Thus, a prefetch (for which a hit has later occurred) may be canceled by a downstream memory component in accordance with the (e.g., arbitrary) policies of the downstream memory component.

p-0050Each of the eight slots has at least one address field <b>522</b>, a direction field (DIR) <b>524</b>, a data pending (DP) field <b>526</b>, a data valid (DV) field <b>528</b>, an address valid (AV) field <b>530</b>, a prefetch canceled (PC) field <b>544</b>, and a predicted next prefetch half-slot (PHP) field <b>536</b>. Address field <b>522</b> stores upper bits of a logical address associated with the associated slot. The logical address is generated by a data prefetch address generator <b>568</b> that is arranged to generate data prefetch addresses in response to received addresses that are associated with memory requests. Data pending (DP) field <b>526</b> is used to indicate whether a prefetch is outstanding the associated slot. Data valid (DV) field <b>528</b> is used to indicate whether the program data in the associated slot is valid. Prefetch cancel (PC) field <b>544</b> is used to prevent the slot from being reallocated in the event a prefetch generated by the slot is canceled (which allows the prefetch to be regenerated for demand fetch reconstruction and half-line neighbors in the L1 cache). The data prefetch unit <b>464</b> does not necessarily keep a separate “address valid” bit for each stream. Instead, the data prefetch unit <b>464</b> launches prefetch requests for any slot that has data pending or data valid bit that is set to be valid. Thus, a demand fetch would normally only “hit” slots for which DP is pending or DV is valid.

p-0051A data pending (DP) field <b>526</b>, a data valid (DV) field <b>528</b>, and an address valid (AV) field <b>530</b> is used for each half-slot. Thus (for example), group <b>532</b> includes a data pending (DP) field <b>526</b>, a data valid (DV) field <b>528</b>, and an address valid (AV) field <b>530</b> for a first half slot of a slot, and group <b>534</b> includes a data pending (DP) field <b>526</b>, a data valid (DV) field <b>528</b>, an address valid (AV) field <b>530</b> for a second half-slot of the slot.

p-0052The data prefetch unit <b>464</b> allocates slots using a FIFO allocation ordering system (such described above with respect to the prefetch filter <b>510</b>). For example, slot #<b>0</b> is allocated first (by using FIFO counter <b>540</b> to point to slot #<b>0</b>), followed by slot #<b>1</b>, #<b>2</b> and #<b>3</b>, and so on until the last slot (such as slot #<b>7</b>) before wrapping back to slot #<b>0</b>. Each slot is associated with two 32-byte data buffers that are structured respectively as a first and second portion of a double-buffer.

p-0053In the case of a typical prefetch hit (determined by prefetch address comparators <b>552</b>, for example) that occurs in response to a memory request, the data prefetch unit <b>464</b> queues the prefetch data for return. If the data prefetch unit <b>464</b> queues has no other return data queued, the data prefetch unit <b>464</b> can begin returning data in response to the memory request.

p-0054In the event where the prefetch predictor <b>550</b> has not successfully predicted the memory request in the event of a hit in the data prefetch buffer <b>520</b>, the data can be retrieved from data prefetch buffer in two clock cycles. During the first clock cycle prefetch address comparators <b>552</b> drives an enable line (e.g., in bus <b>542</b>) to select a slot that is associated with the address of the memory request and to set-up a selected portion (e.g., upper-half and/or lower-half) of the slot for a memory read. During the second clock cycle, data is read from buffer A and/or B of prefetch (PF) data <b>536</b> for the selected slot. Data prefetch buffer driver <b>556</b> is enabled to drive a data portion of a bus so that the requested data can be retrieved in response to the memory request.

p-0055Because of bus width limitations, the length of the memory lines associated with slots are often wider than the bus width used to retrieve data for filling the lines. Thus memory lines are typically requested (for example) on a half-line or sub-line basis where the data to be cached is sent from a lower-level memory to the higher-level cache as a series of data bursts to retrieve the entire line. The data for storing in the allocated cache line are sent such that the requested portion (e.g., the data that is addressed by the demand memory request) of the line returns first (the “critical” sub-line), which is then followed by the subsequent (“non-critical”) sub-lines. A CPU (for example) that generated the demand request then “un-stalls” and resumes execution when the critical sub-line is fetched from the cache.

p-0056<figref idrefs="DRAWINGS">FIG. 6</figref> is a block diagram illustrating a program prefetch unit <b>466</b> in accordance with embodiments of the present disclosure. Program prefetch unit <b>466</b> typically includes a program prefetch buffer <b>620</b> (for prefetching program data for a program stream) and a requested read register predictor <b>660</b> (for maintaining read requests and controlling reads of the double buffers of the program prefetch buffer). Although a program prefetch unit <b>466</b> is described in an embodiment as being a prefetch buffer for program accesses, the program prefetch unit <b>466</b> can also be used in the context of fetching data for multiple streams.

p-0057Program prefetch unit <b>466</b> includes the program prefetch buffer <b>620</b>, which is used to prefetch program data for a program stream. In an embodiment, the program prefetch buffer <b>620</b> is a relatively simple prefetch engine for servicing direct L1P (level-one program) cache requests and L2 program fetches. The program prefetch buffer <b>620</b> uses an extended memory prefetch scheme, extended to the full address space in shared memory. The program prefetch buffer <b>620</b> handles cacheable, prefetchable program fetches as candidates for prefetching.

p-0058The program prefetch buffer <b>620</b> as illustrated holds four logical slots, each of which is associated with storage for two <b>32</b>-byte program fetches, stored in buffer A and B of PF (prefetch) data <b>636</b>. Double buffering the data for each slot in PF data <b>636</b> allows for a prefetch to be started on a subsequent prefetch using buffer B (for example) before a memory request is made (or completed) for the data in buffer A of the slot (e.g., a return-wait state). The program prefetch buffer <b>620</b> can reallocate a slot immediately if at least one of its two halves (e.g., buffer A or buffer B of PF data <b>636</b>) is not busy and the slot is not in a hit-wait state (e.g., waiting for data associated with a program prefetch buffer <b>620</b> hit to be read-out).

p-0059Field A/B <b>646</b> is a data buffer selector used to determine which buffer (Buffer A or Buffer B) is used to hold data that is in a return-wait state (and conversely, which buffer is used to hold data returned from a new prefetch generation). Field A/B <b>646</b> is toggled to avoid overwriting stored data when a return-wait state is encountered (such as when the program prefetch unit <b>620</b> has not finished forwarding the prefetch data to an upstream memory component). Toggling field A/B <b>646</b> allows, for example, the data stored as a result of the new prefetch generation to be returned (e.g., read-out) to the requesting processor or cache without having to transfer the data to the “other” buffer, which minimizes latency. (Likewise, a data buffer selector similar to field A/B <b>646</b> can be used to implement double buffering of the data prefetch unit <b>464</b>, described above with reference to <figref idrefs="DRAWINGS">FIG. 5</figref>.)

p-0060The double-buffer approach allows new prefetch generation to proceed immediately when a prefetch hit results in a return-wait situation. Double buffering each slot of the program prefetch unit <b>466</b> speeds prefetching because the program prefetch buffer <b>620</b> normally reallocates the slot associated with the demand fetch that most recently hits. Double buffering each slot of the program prefetch buffer <b>620</b> also speeds prefetching when the time of allocation (when the local memory will read the data for the hit) is not ascertainable beforehand. Thus, the double-buffer approach allows the prefetch generation to proceed even before program prefetch buffer <b>620</b> sends the hit data to the upstream local memory (e.g., L1 SRAM/Cache <b>212</b> or L2 SRAM/Cache <b>220</b>).

p-0061Also, the program prefetch buffer <b>620</b> avoids reallocating a slot in the hit-wait state in case the prefetch associated with the slot is canceled. When the prefetch is canceled, the program prefetch buffer <b>620</b> uses the address stored in the slot to regenerate the demand fetch. For example, a new prefetch generated too early by the program prefetch buffer <b>620</b> may force another multi-stream prefetch unit <b>460</b> (belonging to a neighboring slave, for example) to cancel the earlier prefetch.

p-0062Each of the slots of the program prefetch buffer <b>620</b> has at least one address field <b>622</b>, a data pending (DP) field <b>626</b>, a data valid (DV) field <b>628</b>, a prefetch canceled (PC) field, <b>644</b>, a double buffer <b>636</b> that contains a Buffer A and a Buffer B, and the A/B field <b>646</b> as described above. Address field <b>622</b> typically stores (at least) the upper bits of a logical address associated with the associated slot. Data pending (DP) field <b>626</b> is used to indicate whether a prefetch is outstanding the associated slot. Data valid (DV) field <b>628</b> is used to indicate whether the program data in the associated slot is valid. The program prefetch buffer <b>620</b> does not necessarily keep a separate “address valid” bit for each slot. Instead, the program prefetch buffer <b>620</b> launches prefetch requests for any slot that has data pending or data valid bit that is set to be valid. Thus, a demand fetch would normally only “hit” slots for which DP field <b>626</b> is pending or DV field <b>628</b> is valid.

p-0063The program prefetch buffer <b>620</b> allocates slots using a FIFO allocation ordering system. For example, a first slot is allocated first (by using FIFO counter <b>640</b> to point the first slot), followed by the second slot, the third slot, and so on until the last slot (such as the fourth slot) before wrapping back to the first slot. Each slot is associated with two 32-byte data buffers that are structured respectively as a first and second portion of a double-buffer. Metadata returned with a fetch (such as returned memory access permissions) can be stored in additional or otherwise unused bits of the first and/or second portions of the double buffer.

p-0064In the case of a typical prefetch hit (determined by prefetch address comparators <b>652</b>, for example) that occurs in response to a memory request, the program prefetch buffer <b>620</b> queues the prefetch program data for return to the requesting processor or cache. If the program prefetch buffer <b>620</b> queues has no other return data queued, the program prefetch buffer <b>620</b> can begin returning data in response to the memory request.

p-0065Program prefetch address generator <b>658</b> generates program prefetch addresses in response to received addresses that are associated with memory requests. When a candidate program fetch misses the program prefetch buffer, addresses are generated for fetching the next 128 bytes following the last demand fetch address that missed the buffer. When a program fetch hits the program prefetch buffer, addresses are generated for the next 32, 64, 96, or 128 bytes, depending on whether the fetch hit the oldest (e.g., first stored with respect to the data stored in the other slots), second oldest, second youngest or youngest slot (respectively) in the buffer. Thus, the program prefetch address generator <b>658</b> keeps the prefetch buffer 128 bytes ahead of the current program stream, and provides the addresses to quickly switch streams when the program branches to a new location.

p-0066Because of bus width limitations, the length of the memory lines associated with slots are often wider than the bus width used to retrieve data for filling the lines. Thus memory lines are typically requested (for example) on a half-line or sub-line basis where the data to be cached is sent from a lower-level memory to the higher-level cache as a series of data bursts to retrieve the entire line. The program data for storing in the allocated cache line are sent such that the requested portion (e.g., the data that is addressed by the demand memory request) of the line returns first (the “critical” sub-line), which is then followed by the subsequent (“non-critical”) sub-lines. A CPU (for example) that generated the demand request then “un-stalls” and resumes execution when the critical sub-line is fetched from the cache.

p-0067When a memory request for program instructions misses the prefetch buffer, the prefetch program prefetch address generator <b>658</b> sets the predicted next prefetch slot to the first allocated slot. When a prefetch hit of a critical sub-line occurs due to an L2 request for program prefetching, no action is taken because no new prefetches typically result. When a prefetch hit of a non-critical sub-line occurs due to an L2 request (which typically triggers new prefetches), the predicted next prefetch slot is set to the first allocated slot. When a prefetch hit occurs due to an L1P (level-one program) request, the predicted next prefetch slot is set to one slot after the slot just hit in accordance with the FIFO slot allocation order. The program prefetch address generator <b>658</b> determines the criticality of the sub-line being fetched and the origin of the memory request by evaluating the metadata signals discussed above with respect to <figref idrefs="DRAWINGS">FIG. 4</figref>.

p-0068Requested read register <b>660</b> receives a memory request having an address for reading data (including program instruction data) stored in memory. Requested read register <b>660</b> stores the requested address in the requested address (Req. Addr.) field <b>662</b>. The requested address is evaluated (using bus <b>642</b>, for example) by address comparator <b>652</b> to determine whether the requested address “hits” the program prefetch buffer <b>620</b>. If a hit occurs, the address comparator <b>652</b> passes to the requested read register <b>660</b> the slot number of the slot “hit” by the requested address. The hit slot number for the received memory request is stored in the Slot # field <b>664</b>.

p-0069Requested read register <b>660</b> is organized as a FIFO such that received memory requests are handled using a First In, First Out policy. FIFO counter <b>670</b> is cycled such that each request (e.g., row) is handled in the order received, and that the each of the four slots is handled (e.g., the data associated with a slot is returned) before the FIFO counter <b>670</b> is recycled back to the first slot.

p-0070The program prefetch unit <b>466</b> heuristically determines the predicted next prefetch (PNP) by anticipating that the next prefetch hit will be for the slot “after” the slot for the current hit in the prefetch buffer. The slot “after” the currently hit slot is the next slot that follows the currently hit slot in accordance with the direction of the stream that is associated with the currently hit slot. The probabilities for correctly predicting the next prefetch are increased (over random estimates, for example) because (as disclosed herein) prefetch slots are allocated in a FIFO allocation order, and thus prefetch hits are more likely to occur in the order used for FIFO allocation (e.g., the FIFO allocation order). The program prefetch unit <b>466</b> uses FIFO counter <b>638</b> to point to the predicted next prefetch.

p-0071In the case of a typical prefetch hit (determined by prefetch address comparators <b>652</b>, for example) that occurs in response to a memory request, the multi-stream prefetch unit <b>460</b> queues the prefetch data for return. If the multi-stream prefetch unit <b>460</b> queues has no other return data queued, the multi-stream prefetch unit <b>460</b> can begin returning data in response to the memory request.

p-0072In the event where the program prefetch unit <b>466</b> has not successfully predicted the memory request in the event of a hit in the data prefetch buffer <b>620</b>, the data can be retrieved from data prefetch buffer in two clock cycles. During the first clock cycle prefetch address comparators <b>652</b> drives an enable line (e.g., in bus <b>642</b>) to select a slot that is associated with the address of the memory request and to set-up a selected portion (e.g., upper-half and/or lower-half) of the slot for a memory read. During the second clock cycle, data is read from buffer A and/or B of prefetch (PF) data <b>636</b> for the selected slot. A prefetch buffer driver is enabled to drive a data portion of a bus so that the requested data can be returned to the requestor in response to the memory request.

p-0073Thus, the prefetch buffer would ordinarily take two full clock cycles to reply to a prefetch hit: to potentially reduce the latency of two clock cycles, anticipating which slot (and which “side” of the double buffer of the slot) would likely be hit next and provisions the data for readout in one clock cycle. In an embodiment, the anticipated slot number and the read out half of the double buffer are enable ahead of time (e.g., before a next memory request is processed) to minimize (for example) the time required to retrieve the data from the associated half-slot. Thus, when a new memory request arrives that matches the previously asserted address, the prefetch buffer can respond with data in the following clock cycle, and thus respond within a zero wait-state response time.

p-0074When a memory request for program instructions misses the program prefetch unit <b>466</b>, the program prefetch unit <b>466</b> sets the predicted next prefetch slot to the first allocated slot. When a prefetch hit of a critical sub-line occurs due to an L2 request for program prefetching, no action is taken because no new prefetches typically result. When a prefetch hit of a non-critical sub-line occurs due to an L2 request (which typically triggers new prefetches), the predicted next prefetch slot is set to the first allocated slot.

p-0075When a prefetch hit occurs due to an L1P (level-one program) request, the predicted next prefetch slot is set to one slot after (e.g., in the order determined by the stream associated with the hit slot) the slot just hit in accordance with the FIFO slot allocation order. The program prefetch unit <b>466</b> determines the criticality of the sub-line being fetched and the origin of the memory request by evaluating the metadata signals discussed above with respect to <figref idrefs="DRAWINGS">FIG. 4</figref>.

p-0076When a cancelation of a prefetch occurs during a hit-wait state caused by a hit by a program fetch (that hits the previously generated memory requests, but where the data has not been returned to the program prefetch unit <b>466</b> yet), the program prefetch unit evaluates the associated metadata signals to determine whether a memory request (from an upstream memory device) is not a demand fetch. If the memory request occurs during the hit-wait state and is generated by other than a demand fetch (e.g., made by the upstream processor), the memory request is stalled by the program prefetch unit <b>466</b>. For example, if a target branch predictor has generated memory requests for program branch targets, the memory requests for program branch targets that do not hit in the program prefetch buffer <b>466</b> are stalled until there are no active hit-waits outstanding.

p-0077<figref idrefs="DRAWINGS">FIG. 7</figref> is a block diagram illustrating a local memory arbiter in accordance with embodiments of the present disclosure. Local memory arbiter <b>224</b> is arranged to receive a command from an “upstream” (e.g., higher-level hierarchical) memory controller such as (local) memory controller <b>400</b>. Command buffer <b>710</b> is arranged to latch a received memory request command and associated data. The latched command and data are selected for output to a central arbiter (e.g., central memory arbiter <b>234</b>) when the latched command has sufficient priority. When the latched command does not have sufficient priority during a portion of the memory cycle at which the command is latched, the command latched in the command buffer <b>710</b> is stored in one of the storage queues.

p-0078The type of the command is used to determine in which storage queue the command is to be saved. The separate demand, program and data prefetch command buffers allow incoming request to be reordered without delaying the incoming traffic of memory requests. For example, the storage queues include the program prefetch command buffer <b>720</b>, the data prefetch command buffer <b>740</b>, or demand elastic buffer <b>740</b>.

p-0079The storage queues (including command buffer <b>710</b>) are used to form a command reordering buffer <b>730</b> that stores up to a total of ten commands (two demand read or write requests and eight prefetch requests, four of which are for program prefetch commands, and four of which are for data prefetch commands). The command priority controller <b>770</b> uses a set of reordering rules to allow reordering of the requests stored in the above buffers in the local memory arbiter <b>224</b>. Demand reads have the highest priority, prefetch reads have the next highest priority, while writes typically have the lowest priority. Reordering of writes is disabled when read requests and write requests have an overlapped address range (e.g. when a read command depends on the results of a write command). Reordering read/write commands (when there is not forced ordering required by the user) reduces the processor stall cycles on cache read misses.

p-0080The command priority controller <b>770</b> also uses write merging to better utilize the bandwidth to the shared memory resources when writes are pending for central arbitration. For example, if a partial write to an SRAM location is still pending arbitration in the local memory arbiter <b>224</b>, and a subsequent write command is received that implicates the same line address as the partial write (which would normally be different bytes of the same cache line), then the local memory arbiter <b>224</b> merges the two writes into a single request that is presented to the central memory arbiter <b>234</b>.

p-0081The local memory arbiter <b>224</b> also asserts priority escalation for the amount of time a high priority command is propagated into and through the local memory arbiter <b>224</b> as well as into and through the central memory arbiter <b>234</b>. In contrast, conventional systems generally elevate the priority of all the commands that have been received before the high priority command is received from a given local memory arbiter <b>224</b>.

p-0082Propagation of commands through the local memory arbiter <b>224</b> depends on whether the commands to be propagated are demand requests or prefetch requests. For demand requests, the command reorder buffer <b>730</b> can store up to two non-speculative (demand request) commands—one in the command pipeline register and another in the demand elastic buffer. Further demand requests are stalled when two demand requests remain pending in the command reorder buffer <b>730</b> when the further demand requests are received. The demand elastic buffer <b>740</b> is used to store a demand request when the demand request in the command pipe register <b>710</b> is presented to the central memory arbiter <b>234</b> and the stored demand request fails to win arbitration with the central memory arbiter <b>234</b>. (The stored demand request is latched in the demand elastic buffer <b>740</b> when the demand elastic buffer <b>740</b> is empty: if the demand elastic buffer <b>740</b> if full, further demand requests are stalled as explained above.)

p-0083For prefetch requests, the command reorder buffer <b>730</b> can store up to four 32-byte prefetch requests (such as program prefetches due to a level-one program cache miss) in program prefetch command buffer <b>720</b> and up to four 64-byte prefetch requests (data prefetches due to an level-one data cache miss or prefetches due to a level-two unified cache miss) in data prefetch command buffer <b>750</b>. The program prefetch command buffer <b>720</b> and the data prefetch command buffer <b>750</b> are each are arranged as FIFO (First In First Out) buffers wherein the oldest entry is overwritten when the respective FIFO is full.

p-0084Commands addressing the shared memory (e.g., shared memory <b>230</b>) or external memory are reordered by the command reorder buffer <b>730</b> to improve performance in accordance with the following set of rules. Firstly, demand reads are selected ahead of prefetch reads of any size. Secondly, demand read requests are selected ahead of independent write requests (as long as there is no addressed range overlap between the read and the write commands). Next, prefetch reads are selected ahead of independent write requests (as long as there is no addressed range overlap between the prefetch read and the write command) with a lower priority such that 64-byte prefetch reads are selected ahead of write requests and 32-byte prefetch requests, while 32-byte prefetch requests are selected ahead of write requests.

p-0085The prefetch commands stored in command reorder buffer <b>730</b> can be canceled in accordance with a set of prefetch canceling rules used to discard prefetch requests that have been determined to be unneeded or undesired. The command reorder buffer supports a prefetch “squashing” (e.g., canceling) mechanism wherein one or more buffered prefetch requests are terminated. The prefetch requests are squashed (e.g., by returning bus read timeout errors returned in response to a read status request) when one of the below-discussed conditions is encountered (in order of precedence). Prefetch squashing reduces redundant traffic downstream by not allowing out of date prefetch requests to be presented for endpoint arbitration (by a central memory arbiter, for example).

p-0086Firstly, a prefetch request is canceled when the prefetch request arrives when a write request is received that has an address range that overlaps an address range of a read request. Canceling the overlapping request maintains a write-before-read dependency, while still allowing read requests to have priority over write requests.

p-0087Secondly, all buffered 32-byte prefetch requests are canceled when a demand program read request of any size arrives. All buffered 32-byte prefetch requests are canceled (flushed) because the demand program fetch because the buffered 32-byte prefetch requests are now considered to be out-of-date. The buffered 32-byte prefetch requests are considered to be out-of-date because the demand program fetch is indicative that a program branch has been taken, and the currently buffered prefetch requests are thus along the “not-taken” path of the processor.

p-0088Next, the oldest individual command request pending in a prefetch command buffer of either the program-prefetch type or the data-prefetch type is canceled when the prefetch command buffer is full. For example, when four 32-byte prefetch command requests are buffered in the program prefetch command <b>750</b> and have not been granted arbitration by the local memory arbiter <b>224</b>, a new 32-byte prefetch request replaces the oldest 32-byte prefetch request pending in the program prefetch command buffer <b>750</b>. Similarly, a 64-byte data program prefetch request received when the data prefetch command buffer <b>720</b> is full would squash the oldest outstanding 64-byte prefetch request in the program prefetch command buffer <b>720</b>.

p-0089The local memory arbiter <b>224</b> returns notifications of the squashed prefetch commands to an upstream memory controller. For example, the squashed prefetch commands can be reported by returning a read status with the timeout error. However, such notifications might conflict with read returns (and other notifications) from other endpoints (such as main memory <b>230</b> or the central memory arbiter <b>234</b>) that are being returned to the read return interface to the upstream memory controller. The notifications of the local memory arbiter <b>224</b> for the prefetch cancelations are given a lower bus access priority so the notifications of the local memory arbiter <b>224</b> would wait for other read status returns to finish, and are thus stored until the prefetch command bus is available. The prefetch squashing logic is typically not required to send the notifications of the timeout statuses back in any specific order.

p-0090The local memory arbiter <b>224</b> uses write merging logic (in the command priority controller <b>770</b>, for example) to better maximize the write bandwidth to the main memory <b>230</b> by using write merging. For example, adjacent 32-byte write requests can be merged into a smaller number of write requests while the write commands are pending arbitration at a downstream memory arbiter such as the central memory arbiter <b>234</b>. Write merging reduces processor stalls that may be caused by serial, non-cacheable writes having overlapping address windows. The write merging is ideally accomplished without stopping the write stream nor affecting other unmerged writes from cores (or processors) writing to main memory <b>230</b>.

p-0091For better performance for communications for each of the endpoint slaves and evenly provide accesses from all masters, the local memory arbiter <b>224</b> monitors the access size of each command closely when performing write merging. For external memory, the local memory arbiter <b>224</b> splits larger commands into multiple subcommands in accordance with an optimum access size of 64 bytes. Each of the merged write accesses is no larger than 64 bytes, and is also aligned to a 64-byte boundary. For on-chip shared memory, the physical width of the RAM (random access memory) access port determines the optimum command size, which is 32 bytes in an embodiment. Accordingly, the local memory arbiter <b>224</b> adjusts the subcommand (e.g., write-merged commands) sizes according to operating parameters of the endpoint slaves.

p-0092With reference again to <figref idrefs="DRAWINGS">FIG. 2</figref>, the central memory arbiter <b>234</b> is arranged to receive memory requests from one or more (local) memory arbiters <b>224</b>. The central memory arbiter <b>234</b> evaluates the context and metadata associated with each request to determine a priority for processing the received memory requests. For example, the central memory arbiter <b>234</b> determines whether the received memory request is a demand request (which is normally assigned a higher priority) or a prefetch request (which is normally given a lower priority). If the memory request is a prefetch request, the type of prefetch request (such as whether the prefetch request is a program data fetch or the prefetch request is a non-program data fetch) is considered.

p-0093The central memory arbiter <b>234</b> applies policies to balance speculative prefetches (and the relative amounts of the different types of speculative prefetches) to maximize the “traffic” of memory accesses of a downstream (e.g., lower-hierarchy) shared memory resource. The rates of the differing types of memory requests are balanced by selectively squashing (e.g., canceling) certain types of memory request in favor of other types of memory requests. For example, program branching can lead to an excess of program prefetches (as described above) so program prefetches can be squashed in progressively higher amounts such that data-type prefetches are not “crowded out” of access to the requested downstream memory resource.

p-0094As described above, a notification that the prefetch has been canceled is sent to the (upstream) entity (as described above) that generated the prefetch. The notification is used by the notified entity to change an operating parameter. For example, a prefetch buffer can change the number of allocated slots so as to decrease the number of generated prefetches. (Contrary-wise, the prefetch buffer can increase the number of prefetches when no cancelations are received). Likewise, the (local) memory arbiter <b>224</b> can change the heuristics of the command priority controller <b>770</b> to decrease the number of prefetches of the type of prefetch that was canceled. (Again, the memory arbiter <b>224</b> can change the heuristics when no such cancelations are received within a given period of time.)

p-0095Upstream modification of prefetch generation in response to downstream cancelations reduces the numbers of prefetches that need to be canceled (to maintain sufficient bandwidth for the higher priority memory requests) and thus reduces the processing load of the central memory arbiter <b>234</b>. Also, the distributed cancelation control hides many of the details of the cancelation mechanism from upstream memory controllers (thus reducing communication requirements and increasing overall speed of the entire processing system).

p-0096<figref idrefs="DRAWINGS">FIG. 8</figref> is a process diagram illustrating prefetching with arbitrary downstream prefetch cancelation in accordance with embodiments of the present disclosure. Process <b>800</b> is entered at node <b>802</b> and proceeds to function <b>804</b>. At function <b>804</b>, a prefetch request is generated for data (and/or program data) stored in a downstream (lower-level hierarchy) shared memory.

p-0097The generated prefetch request is prioritized with other memory requests (with respect to a local processor) by a (local) memory arbiter <b>224</b>. After being prioritized, the generated prefetch request is passed to a central memory arbiter <b>234</b>. The central memory arbiter <b>234</b> evaluates the context and metadata associated with each request to determine a priority for processing the received memory requests. As discussed above, the central memory arbiter <b>234</b> applies policies to balance speculative prefetches to maximize the “traffic” of memory accesses of the downstream shared memory resource.

p-0098In function <b>806</b>, if a cancelation notification (that the prefetch request has been canceled) is sent to the (upstream) entity that generated the prefetch request, the process flow proceeds to function <b>808</b>; otherwise, the program flow proceeds to node <b>890</b> where the process flow ends.

p-0099In function <b>808</b>, it is determined whether a hit-wait state exists for the prefetch that was canceled. For example, a hit-wait state exists when a demand fetch has been received that requests the same data for which the prefetch request has been previously generated (but the requested data has not been returned to the prefetch unit). When the hit-wait state exists, process flow proceeds to function <b>812</b> where the request is regenerated; otherwise, the process flow continues in function <b>810</b>.

p-0100In function <b>810</b>, it is determined whether the canceled prefetch is neighbor to (e.g., is the “other” half of) a half-line for which a prefetch request has been successfully concluded. If so, the process flow proceeds to function <b>812</b> where the request is regenerated; otherwise, the process flow continues to node <b>890</b>, where the process flow exits.

p-0101In function <b>812</b>, the prefetch request is regenerated (for example, as a demand fetch) and resent to the downstream shared memory resource. After the prefetch request is regenerated, the process flow continues to node <b>890</b>, where the process flow exits.

p-0102The various embodiments described above are provided by way of illustration only and should not be construed to limit the claims attached hereto. Those skilled in the art will readily recognize various modifications and changes that may be made without following the example embodiments and applications illustrated and described herein, and without departing from the true spirit and scope of the following claims.