Prefetch queue

RELATED APPLICATIONS

0001[0001] This application is a continuation-in-part of U.S. patent application Ser. No. 08/999,241, entitled “Prefetch Queue,” filed Dec. 29, 1997, is incorporated herein by reference and may benefit from the priority thereof.

BACKGROUND OF THE INVENTION

0002[0002] The present invention relates to a prefetch queue provided for an external cache memory in a processor.

0003[0003] Prefetching is a known technique implemented in processor devices. Prefetching causes data or instructions to be read into the processor before it is called for by the processor's core execution unit (“core”). By having the data available within the processor when the core is ready for it, the core need not wait for the data to be read from slower external memories. Instead, the data is available to the core at the relatively higher data rates of internal buses within the processor. Because prefetching can free a core from having to wait for an external bus transaction to be completed before the core can use the requested data, prefetching can improve processor performance.

0004[0004] If implemented incorrectly, however, prefetching can impair processor performance. By reading data from external memories into the processor, prefetch operations occupy resources on the external bus. Due to the limited size of the core cache, prefetching may write data over other data that the processor may use. Further, prefetching may read data into the processor that may never be used. Thus, prefetching is useful only if it improves processor performance more often than it impairs such performance. Instruction streaming, a type of prefetching, occurs when a core causes data to be read sequentially from several adjacent positions in external memory. Instruction streaming suffers from the above disadvantages.

0005[0005] It is known that prefetching may provide significant performance improvements when a processor either executes instructions or manipulates data held in adjacent memory locations. However, no known prefetching scheme adequately distinguishes programs that perform sequential memory reads from those that perform non-sequential memory reads. Further, many processors, particularly out-of-order superscalar machines, tend to perform several interlaced sequential reads “in parallel.” They may read data from sequential memory positions in a first area of memory interspersed with reads from sequential memory positions in a second area of memory. Traditional prefetching techniques do not recognize multiple streams of sequential memory reads as appropriate for prefetching.

0006[0006] Accordingly, there is a need in the art for a prefetch scheme that prefetches only when there exists a pattern demonstrating that performance improvements are to be obtained by prefetching. There is a need in the art for a prefetch scheme that incurs low performance costs for erroneous prefetches. Further, there is a need in the art for a prefetch scheme that detects and observes parallel prefetch operations.

SUMMARY OF THE INVENTION

0007[0007] Embodiments of the present invention provide a prefetch queue for an agent that can detect request patterns in both an ascending direction in memory and a descending direction in memory. Having detected a request pattern and a direction, the prefetch queue requests data from a next memory location in the direction.

BRIEF DESCRIPTION OF THE DRAWINGS

0008[0008]FIG. 1 is block diagram of a processor constructed in accordance with an embodiment of the present invention.

0009[0009]FIG. 2 is a block diagram of a prefetch queue according to an embodiment of the present invention.

0010[0010]FIG. 3 is a flow diagram of a method of operation of the prefetch queue in accordance with an embodiment of the present invention.

0011[0011]FIG. 4 illustrates relationships between a home address, the flags and external memory locations.

DETAILED DESCRIPTION

0012[0012] Embodiments of the present invention provide a prefetch queue for an agent that can identify multiple parallel sequential read patterns from a sequence of read requests issued by an agent core. The prefetch queue also may identify read patterns directed to advancing or retreating locations in memory.

0013[0013]FIG. 1 illustrates an embodiment of a processor <b>10</b> constructed in accordance with an embodiment of the present invention. The processor <b>10</b> may include a bus sequencing unit <b>100</b> (“BSU”) and a core <b>200</b>. Both the BSU <b>100</b> and the core <b>200</b> may operate at much greater speeds than are associated with an external bus <b>250</b>. The external bus <b>250</b> interconnects the processor <b>10</b> with other components such as other processors, memories and other devices (not shown).

0014[0014] BSUs per se are known. They may include an arbiter <b>110</b>, a cache memory <b>120</b>, an internal queue <b>130</b>, a bus queue <b>140</b> and an external bus controller <b>150</b>. The arbiter <b>110</b> may receive requests from a variety of inputs <b>110</b><i>a</i>-<i>e, </i>such as from the core <b>200</b> and perhaps from other sources such as from the bus queue <b>140</b> (communication path not shown). Requests may include a request code representing the type of request being made and, where appropriate, an address identifying a memory location to which the request is directed. The arbiter <b>110</b> may prioritize the requests and may implement them in the order of priority.

0015[0015] The cache <b>120</b> may be an internal memory. As is known, relative to core cache memories (not shown), the cache <b>120</b> typically possesses much greater capacity. For example, a typical cache <b>120</b> may be a 128 k memory. By contrast a core data cache <b>210</b> may be a 32 k memory and a core instruction cache may be an 8 k memory. The cache <b>120</b> may be a unified cache, one that stores both instruction data and variable data (collectively, “data”).

0016[0016] Read requests from the arbiter <b>110</b> may be input to both the cache <b>120</b> and to the internal queue <b>130</b>. The cache <b>120</b> may include control logic (not shown) that can determine whether the requested data is stored in the cache <b>120</b>. If so, the request is said to “hit” the cache <b>120</b>. The cache <b>120</b> will furnish the requested data to the core <b>200</b> over a communication path (also not shown). Otherwise, the request is said to “miss” the cache. The cache <b>120</b> may communicate a hit or a miss to the internal queue <b>130</b> over a line <b>122</b>.

0017[0017] The internal queue <b>130</b> may include control circuitry and buffer memory to process requests from the arbiter <b>110</b>. The internal queue <b>130</b> also receives hit/miss indicators from the cache <b>120</b>. If a read request hits the cache <b>120</b>, the internal queue <b>130</b> permits the queued request to terminate as it advances out of the queue <b>130</b>. But if a read request misses the cache <b>120</b>, the request should be completed by retrieving the requested data from an external memory (not shown). In this case, when the read request advances out of the internal queue <b>130</b>, the internal queue <b>130</b> causes the request to be entered in the bus queue <b>140</b>.

0018[0018] The bus queue <b>140</b> also may include control circuitry and buffer memory. It may cause external bus transactions to be posted on the external bus <b>250</b> pursuant to queued requests issued from within the processor. The bus queue <b>140</b> may control operation of the bus <b>250</b> via an external bus controller <b>150</b>. Typically, a bus protocol will have been defined for the bus <b>250</b>, the bus queue <b>140</b> and external bus controller <b>150</b> may generate and receive signals in accordance with such a protocol.

0019[0019] In an alternate embodiment, the internal queue <b>130</b> and bus queue <b>140</b> may be replaced by a unitary queue. Accordingly, FIG. 1 illustrates the internal queue <b>130</b> and bus queue <b>140</b> as included in a single “transaction queue.” The principles of the present invention find application with either embodiment.

0020[0020] For a read request, an external bus transaction typically causes data of a predetermined unit size to be read to the processor. For example, a single bus transaction may cause 64 bytes of data to be read to the processor. This predetermined unit size often is referred to as a “cache line.” Different systems have different cache line sizes. Thus, although a processor may require data of only a portion of a cache line, the processor may read the entire cache line. From the cache line, the processor will use as much data as is required by its program flow.

0021[0021] An embodiment of the present invention provides a prefetch queue <b>160</b> for an agent <b>10</b>. The prefetch queue <b>160</b> may monitor read requests issued by the arbiter <b>110</b> and determine whether the read requests exhibit one or more predetermined patterns. If any such pattern is identified, the prefetch queue <b>160</b> may issue a read request to be issued (a “prefetch request”). The prefetch request may be made prior to a core request for the same data. Prefetching may contribute to improved processor performance by having data stored in the internal cache <b>120</b> prior to the time the core <b>200</b> requests the data. If the data is present in the cache <b>120</b> when the core <b>200</b> needs the data, the core <b>200</b> will not be forced to wait for the data to be retrieved via the slower external bus. Instead, the core <b>200</b> can use the data immediately.

0022[0022] According to an embodiment of the present invention, the prefetch queue <b>160</b> may identify predetermined read patterns from the core <b>200</b>. In a first embodiment, the prefetch queue <b>160</b> may monitor read requests issued by the core <b>200</b> to determine whether the requests exhibit a pattern of reads in either a forward or a backward direction or memory (i.e. N, N+1, N+2, . . . or N, N−1, N−2, . . . ). The prefetch queue <b>160</b> may detect the direction of sequential reads and orient its prefetch requests to correspond to this direction. For example, the prefetch queue <b>160</b> may cause prefetches to occur in an ascending or a descending order of memory address.

0023[0023] According to an embodiment, the prefetch queue <b>160</b> may identify sequential reads from a larger series of core requests. A series of sequential reads from memory may be interrupted by read requests directed to other memory addresses. Thus, for example, the prefetch queue <b>160</b> may identify a sequential read pattern from the following sequence of core read requests: A, B, A+1, C, A+2. While no sequential read pattern may be established for addresses B or C, a sequential read pattern may be detected beginning at address A. Similarly, the prefetch queue <b>160</b> may identify sequential read patterns from a sequence of core read requests directed to the following addresses A, B, A+1, B−1, A+2, B−2. In this example, sequential read patterns exist starting at address A and advancing in a forward direction in memory and also starting at address B and advancing in a backward direction in memory.

0024[0024] According to another embodiment, the prefetch queue <b>160</b> may be a multi-mode prefetch queue. In this embodiment, the prefetch queue <b>160</b> may operate in a first mode prior to detecting a sequential read pattern at an address. This first mode may require a first threshold number of sequential reads to be detected before the prefetch queue <b>160</b> determines to issue a prefetch request directed to a next address in the series. The prefetch queue <b>160</b> may operate in a second mode after issuing the prefetch request. In the second mode, the prefetch queue <b>160</b> may issue prefetch requests after a second, lower threshold number of sequential reads are detected. In one embodiment, in a second mode, a prefetch request may be issued each time the core requests data to a previously prefetched address.

0025[0025]FIG. 2 is a block diagram of a prefetch queue <b>300</b> according to an embodiment of the present invention. The prefetch queue <b>300</b> may be populated by a plurality of queue registers <b>301</b>-<b>309</b> and a controller <b>310</b>. Each of the queue registers <b>301</b>-<b>309</b> may include a page ID field <b>320</b>, a marker field <b>330</b>, a home address field <b>340</b> and a mode identifying flag <b>350</b>. The page ID field <b>320</b> and home address field <b>340</b> may include value matching logic that permits a comparison to be made between stored addresses and new addresses input to the prefetch queue <b>300</b>. Thus, the collection of page ID fields <b>320</b> of the registers <b>301</b>-<b>309</b> may be considered a “page queue”; the collection of home address fields <b>340</b> of the registers may be considered a “home queue.”

0026[0026] New addresses may be input to the prefetch queue <b>300</b> from the arbiter <b>110</b> or the internal queue <b>130</b> (FIG. 1). The controller <b>310</b> may write data to various portions of the queue registers <b>301</b>-<b>309</b> over lines <b>311</b>, <b>312</b> and <b>313</b>.

0027[0027] As is known, external memory typically is organized into units of a predetermined size called “pages.” Memory may be allocated to different uses and applications on a page-by-page basis. Each page may include a predetermined number of cache lines. For example, in a system having 4 kilobyte pages, there may be 64 cache lines of 64 bytes each. In other systems, pages and cache lines may be defined to other sizes. For the purposes of this discussion, it suffices to note that an external memory address may include a portions that identify pages and cache line positions of the address.

0028[0028] Within the prefetch cache <b>300</b>, page ID portions <b>320</b> and home address portions <b>340</b> of the registers <b>301</b>-<b>309</b> may store predetermined portions of the addresses of read requests received from the BSU <b>100</b>. When an address is stored in a register (say, register <b>301</b>) the portion that identifies the address's page may be stored in the page ID portion <b>320</b> and the portion that identifies the position of the cache line internally to the page may be stored in the home address portion <b>340</b>.

0029[0029] The marker field <b>330</b> in each register <b>301</b>-<b>309</b> may maintain a record of past core requests that were directed to locations at or near the home address. If a core request matches the page address stored in a register and is directed to a location that is sufficiently close to the home address, then a flag may be marked. A sequential read pattern may be detected based upon the content of the marker field <b>330</b> of a register.

0030[0030] The prefetch queue <b>300</b> also may include a mode identifying flag <b>350</b> for each register <b>301</b>-<b>309</b> identifying whether the address stored therein is part of a sequential read pattern. Thus, the mode identifying flag <b>350</b> may distinguish addresses that are part of active prefetches from those addresses where the prefetch queue <b>300</b> is merely searching for a read pattern.

0031[0031]FIG. 3 is a flow diagram of a prefetch control method <b>1000</b> according to an embodiment of the present invention. The method <b>1000</b> may begin when the prefetch queue receives a read request (Step <b>1010</b>). Upon receipt, the method <b>1000</b> may determine whether the address of the read request coincides with any page addresses stored previously in the prefetch queue (Step <b>1020</b>). If not, the read request misses the prefetch queue. No request pattern will be identified.

0032[0032] When a received address misses the prefetch queue, the prefetch queue stores data from the newly received request in the queue. The prefetch queue may allocate a register and write the page address and cache address portions of the received address into respective page and home address portions of the allocated register speculatively (Step <b>1030</b>). The prefetch queue may identify a prefetch direction as forward (Step <b>1040</b>). The prefetch queue also may initialize the flag portion of the allocated register speculatively (Step <b>1050</b>). Further, the prefetch queue may indicate that no prefetch pattern has been identified for the newly stored address (Step <b>1060</b>).

0033[0033] If, at Step <b>1020</b>, the newly received address hit the page queue, the prefetch queue determines whether the address falls within a predetermined range of the address stored in the home address field of the matching register (Step <b>1070</b>). If so, the prefetch queue marks a corresponding flag in the marker field (Step <b>1080</b>). The prefetch queue may determine whether the number of flags in the marker field exceeds a threshold number (Step <b>1090</b>). If so, the prefetch queue may issue a prefetch request (Step <b>1100</b>). The prefetch queue also may determine whether the matching register, the register that caused the match with the newly received address, has been marked as operating in an active prefetch mode (Step <b>1110</b>). If not, the prefetch queue may conclude the method for a present iteration of processing (Step <b>1120</b>). The prefetch queue also may conclude the method if, at step <b>1090</b>, it was determined that the number of flags did not exceed the threshold number.

0034[0034] If the prefetch queue is operating in an active prefetch mode, the prefetch queue may shift the home address (Step <b>1130</b>). This simply may require that a home address portion of the newly issued prefetch be written to the home address field of the matching register. The prefetch queue also may reinitialize the marker field, clearing all flags except the flag corresponding to the home address itself (Step <b>1140</b>). Thereafter, the current iteration of the method may conclude (Step <b>1120</b>).

0035[0035] At step <b>1070</b>, if the newly received address does not match the home address field, the prefetch queue determines whether the number of flags in the marker field of the matching register exceeds a threshold (Step <b>1150</b>). If so, the prefetch queue may set the mode to “active prefetch” (Step <b>1160</b>). The prefetch queue also may determine whether the home address portion of the newly received address is higher or lower than the address stored in the home address portion of the matching register (Step <b>1170</b>). If lower, the prefetch queue changes the prefetch direction to backward (Step <b>1180</b>). Otherwise, the default direction may remain. Thereafter, the prefetch queue may write the newly received address to the home address field and prefetch ahead of the new home address (Steps <b>1190</b>-<b>1200</b>). The method may reinitialize the marker field (Step <b>1140</b>) and conclude.

0036[0036] If, at step <b>1150</b>, the number of flags does not exceed the threshold, the prefetch queue may advance to step <b>1040</b>, write the home address portion in the home address field of the register, reinitialize the marker field and set the mode as “search for pattern.”

0037[0037] In an embodiment, the controller <b>310</b> of FIG. 2 may cause the prefetch queue <b>300</b> to implement the method <b>1000</b> described above.

0038[0038] In another embodiment, the prefetch queue may operate the method <b>1000</b> independently for each register <b>301</b>-<b>309</b>. Thus, a first register <b>301</b> may be designated as operating in a “search for pattern” mode while a second register <b>302</b> may be operating in an active “prefetch mode.” This independence permits the prefetch queue <b>300</b> to detect multiple independent read sequences from the core even if the core read requests from the sequence are interspersed with other requests that are not in the sequence. This property permits the prefetch queue to acquire multiple independent read sequences from the core.

0039[0039] Optionally, the method <b>1000</b> may be tailored to address certain boundary conditions that may arise during operation. For example, following step <b>1150</b>, if the number of flags does not exceed the threshold, the prefetch queue may determine if the request hit the internal cache <b>120</b> (FIG. 1). If not, it represents a likely synchronization error between the core and the prefetch queue. In response the prefetch may advance to step <b>1040</b> and reset the matching register. Otherwise, it may advance to step <b>1120</b> as shown in FIG. 3.

0040[0040] In an embodiment, the prefetch queue may condition operation of steps <b>1030</b>-<b>1060</b> on whether the read request hit the internal cache <b>120</b> (Step <b>1210</b>). In such an embodiment, if the request hits the internal cache, the method <b>1000</b> may conclude (step not shown). Otherwise, steps <b>1030</b>-<b>1060</b> would be performed.

0041[0041]FIG. 4 illustrates relationships that may be established between the home address, the flags and external memory locations according to an embodiment of the present invention. As described, the home address portion of a register identifies a cache-line-aligned address within a page in external memory. Thus, as shown in FIG. 4, the home address may refer to a cache-aligned address N in a page X of external memory. The home address may correspond to a base position <b>331</b> in the marker field <b>330</b> of the register. Flag positions <b>332</b>-<b>336</b> adjacent to the base position <b>331</b> may correspond to external memory addresses adjacent to the address N. Thus, the prefetch queue may record core read requests directed to a window of external memory having a width defined by the width of the marker field <b>300</b>.

0042[0042] Consider the prefetch queue in operation with respect to a sequence of core requests beginning at an address A. When the first address in the sequence is input to the prefetch queue, the prefetch queue may traverse steps <b>1030</b>-<b>1060</b> and write the newly received address to a new queue entry. Thereafter, the core may issue further requests in the sequence that cause flags to be set in the marker field (Step <b>1080</b>) but are insufficient to raise the total number of flags to pass the threshold of step <b>1090</b>. For example, if the threshold were set to three, a core request to address A+1 would cause the threshold test to fail. The prefetch queue would perform steps <b>1070</b>-<b>1090</b> and conclude.

0043[0043] Eventually, the core may issue enough requests to pass the threshold of step <b>1090</b>. Using the above example, when the prefetch queue receives a core request to address A+2, a third bit may be set in the marker field. The flags may pass the threshold of Step <b>1090</b> and the prefetch queue may issue a prefetch request. In this iteration, the prefetch queue may prefetch an address at A+4. This is appropriate because the core read request to A+2, by virtue of an associated blind prefetch, may cause data at addresses A+2 and A+3 to be read to the agent. After the prefetch, however, because the prefetch queue has not advanced to active prefetch mode, the prefetch queue would conclude the present iteration of the method.

0044[0044] When the prefetch queue receives a core request to address A+3, the prefetch queue again may progress through steps <b>1070</b>-<b>1110</b>. The prefetch queue may issue a prefetch request to address A+5. Because data at address A+5 may have been read to the agent as part of a blind prefetch associated with the prefetch request A+4, the prefetch request may hit the internal cache <b>120</b> (FIG. 1). It need not generate an external bus transaction.

0045[0045] When the prefetch queue receives a core read request to address A+4, the address may hit the page queue but miss the home address queue. In this case, the prefetch queue may advance through steps <b>1150</b>-<b>1190</b>. The prefetch queue switches modes (to active prefetch mode) and determines the prefetch direction. In this example, the direction does not change; it remains designated as “forward.” The prefetch queue also writes A+4 to the home address and prefetches based upon it. In this example, the prefetch queue prefetches to address A+6. Thereafter, additional core read requests in the sequence may cause the prefetch queue to traverse steps <b>1070</b>-<b>1140</b>.

0046[0046] According to an embodiment, the method <b>1000</b> may employ a different threshold at step <b>1090</b> when the marker field of a register indicates that the prefetch queue is searching for a pattern than when the marker field indicates that an active prefetch is underway. In the example above, three flags were required for a first prefetch to be made. When an active prefetch is underway, it may be appropriate to lower the required number of flags. Thus, using the foregoing example, the threshold may be dropped to one. This would cause a prefetch to be issued every time a new core request “touched” the marker field.

0047[0047] According to another embodiment, the method <b>1000</b> may test only a portion of the marker field during an active prefetch. As shown in FIG. 4, the marker field records core reads to external memory locations that surround the home address. When an active prefetch is underway, a prefetch direction is known to be forward or backward. According to this embodiment, when an active prefetch is underway, step <b>1090</b> may test only that portion of the marker field that is associated with the prefetch direction. For forward direction prefetches, the method <b>1000</b> may restrict its threshold test only to those field positions from the base address to the front of the marker field (Positions <b>331</b>-<b>334</b> in FIG. 4). For backward direction prefetches, the method <b>1000</b> may restrict its threshold test only to those field positions toward the back of the marker field (Positions <b>331</b>-<b>332</b> and <b>335</b>-<b>336</b> in FIG. 4).

0048[0048] According to a further embodiment, the method <b>1000</b> may prefetch two cache lines ahead of the newly received address that caused the prefetch. Such an embodiment is appropriate for use with systems that augment the prefetch request to with a blind prefetch to an adjacent memory location (reading data three cache lines ahead of the newly received address).

0049[0049] The discussion of the foregoing embodiments presents the prefetch queue operating in a physical address space, where external memory locations are addressed by page and cache line locations. Note that the principles of the present invention transcend this specific embodiment. The prefetch queue may be applied to other embodiments using other addressing schemes. For example, the prefetch queue may be applied to a virtual address space where memory is addressed by an object identifier and an offset representing a location within memory. Such an embodiment would include an object ID queue in place of a page queue and an offset queue instead of a home queue. Notwithstanding these modifications, the principles of the present invention find application in such a scheme.

0050[0050] Several embodiments of the present invention are specifically illustrated and described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.