CN106951217A - By the instruction prefetch device of readily available prefetcher accuracy dynamic control - Google Patents

Abstract

An instruction prefetcher dynamically controlled by readily available prefetcher accuracy. According to one general aspect, an apparatus may include a branch prediction unit, a fetch unit, and a prefetcher circuit or unit. The branch prediction unit may be configured to output predicted instructions. The fetch unit may be configured to fetch the next instruction from the cache memory. The prefetcher circuit may be configured to prefetch previously predicted instructions into the cache memory based on a relationship between the predicted instruction and the next instruction.

Description

Instruction prefetcher dynamically controlled by readily available prefetcher accuracy

This application claims U.S. Provisional Patent Application No. 62/276,067, filed January 7, 2016, entitled "Instruction Prefetcher Dynamically Controlled by Readily Available Prefetcher Accuracy," and filed on April 18, 2016. Priority to U.S. Nonprovisional Patent Application No. 15/132,230 filed on . The subject matter of this previously filed application is hereby incorporated by reference.

technical field

This description relates to prefetching data, and more specifically, to the control of instruction prefetching.

Background technique

In computer system architecture, instruction prefetching is a technique used to speed up the execution of programs by reducing wait states. Prefetching generally occurs when a processor or subunit of a processor (eg, a prefetch unit) requests an instruction or data block from main memory before the instruction or data block is actually needed. Once an instruction/data block is returned from main memory or system memory, the instruction/data block is typically placed in cache memory. When a request is made to access an instruction/data block from cache, it can be accessed much faster from cache than if the request had to be made to main memory or system memory. Therefore, prefetching hides memory access latency.

Since programs are generally executed sequentially, performance is likely to be best when instructions are prefetched in program order. Alternatively, prefetching can be part of a complex branch prediction algorithm, in which the processor tries to anticipate the outcome of a computation, and prefetches the correct instruction ahead of time.

In computer system architecture, a branch predictor or branch prediction unit that attempts to predict that a branch will be taken before the result is actually calculated and known (eg, if-then-else constructs, jump instructions) Which path of the digital circuit. The purpose of a branch predictor is usually to improve the flow in the instruction pipeline. In many modern pipelined microprocessor system architectures, branch predictors play an extremely important role in achieving efficient performance.

Two-way branches are usually implemented using conditional jump instructions. A conditional jump can be "not taken" and use the first branch of the code immediately following the conditional branch to continue execution, or a conditional jump can be "taken" and jump to the store A different location in program memory for the second branch of code. It is often not known with certainty whether a conditional jump will be a jump or not until the condition has been evaluated and the conditional branch has gone to the execute stage in the instruction pipeline.

Without branch prediction, the processor would typically have to wait until the conditional jump instruction has passed to the execute stage in the pipeline before the next instruction can enter the fetch stage. Branch predictors try to avoid such time-wasting by trying to guess which jump instruction is most likely to take or not to take. The branch guessed to be the most likely is then fetched and executed speculatively. If the branch predictor detects that the guessed branch is wrong, speculatively executed or partially executed instructions are usually discarded and the pipeline restarts with the correct branch, inducing a delay.

Contents of the invention

According to one general aspect, an apparatus may include a branch prediction unit, a fetch unit, and a prefetcher circuit or unit. The branch prediction unit may be configured to output predicted instructions. The fetch unit may be configured to fetch the next instruction from the cache memory. The prefetcher circuit may be configured to prefetch previously predicted instructions into the cache memory based on a relationship between the predicted instruction and the next instruction.

According to another general aspect, a method may include predicting, by a predictive circuit, a predicted instruction to be executed by a processor. The method may include fetching, by the fetch circuit, a next instruction from the cache memory. The method may also include determining whether a relationship between the predicted instruction and the next instruction satisfies a set of one or more predetermined criteria. The method may include prefetching the predicted instruction into the cache memory if the set of one or more predetermined criteria is present.

According to another general aspect, an apparatus may include a processor, a cache memory, a branch prediction unit, a fetch unit, and a prefetcher circuit or unit. Processors can be configured to execute instructions. The cache memory may be configured to temporarily store instructions. The branch prediction unit may be configured to output predicted instructions, wherein the predicted instructions are speculatively predicted to be executed by the processor, wherein the branch prediction unit is separate from the fetch unit. The fetch unit may be configured to fetch the next instruction from the cache memory. The prefetcher circuit may be configured to prefetch previously predicted instructions into the cache memory in response to a relationship between the predicted instruction and the next instruction satisfying one or more predetermined criteria.

The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features will be apparent from the description and drawings, and from the claims.

A system and/or method for prefetching data, and more particularly for controlling instruction prefetching, is fully shown and/or described in connection with at least one of the various figures, more fully in the specification The system and/or method are described in detail.

Description of drawings

FIG. 1 is a block diagram of an example embodiment of a system according to the disclosed subject matter.

FIG. 2 is a block diagram of an example embodiment of a device according to the disclosed subject matter.

FIG. 3 is a block diagram of an example embodiment of a device according to the disclosed subject matter.

Fig. 4 is a functional block diagram of an information handling system that may include an apparatus produced in accordance with the principles of the disclosed subject matter.

The same reference numerals in the various drawings represent the same elements.

detailed description

Various example embodiments will be described more fully hereinafter with reference to the accompanying drawings, in which some example embodiments are shown. The disclosed subject matter may, however, be embodied in many different forms and should not be construed as limited to the example embodiments set forth herein. Rather, these example embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the disclosed subject matter to those skilled in the art. In the drawings, the size and relative sizes of layers and regions may be exaggerated for clarity.

It will be understood that when an element or layer is referred to as being "on," "connected to" or "coupled to" another element or layer, it can be directly on, directly connected to, or to another element or layer, or intervening elements or layers may be present. In contrast, when an element is referred to as being "directly on," "directly connected to" or "directly coupled to" another element or layer, there are no intervening elements or layers present. Like reference numerals refer to like elements throughout. As used herein, the term "and/or" includes any and all combinations of one or more of the associated listed items.

It will be understood that although the terms "first", "second", "third" etc. may be used herein to describe various elements, components, regions, layers and/or sections, these elements, components, regions, layers and/or sections or parts should not be limited by these terms. These terms are only used to distinguish one element, component, region, layer or section from another element, component, region, layer or section. Thus, a first element, component, region, layer or section discussed below could be termed a second element, component, region, layer or section without departing from the teachings of the presently disclosed subject matter.

For ease of description, spatially relative terms (such as "under", "below", "below", "above", "above", etc.) may be used herein to describe the The relationship of one element or feature to another element or feature. It will be understood that the spatially relative terms are intended to encompass different orientations of the device in use or operation in addition to the orientation depicted in the figures. For example, if the device in the figures is turned over, elements described as "below" or "beneath" other elements or features would then be oriented "above" the other elements or features. Thus, the exemplary term "below" can encompass both an orientation of above and below. The device may be otherwise oriented (rotated 90 degrees or oriented in other orientations) and the spatially relative descriptors used herein interpreted accordingly.

The terminology used herein is for the purpose of describing particular example embodiments only and is not intended to be limiting of the subject matter of the present disclosure. As used herein, singular forms are intended to include plural forms unless the context clearly dictates otherwise. It will also be understood that when the terms "comprising" and/or "comprising" are used in this specification, it indicates the presence of the described features, integers, steps, operations, elements and/or components, but does not exclude the presence or addition of one or more Other features, integers, steps, operations, elements, components and/or groups thereof.

Example embodiments are described herein with reference to cross-sectional illustrations that are schematic illustrations of idealized example embodiments (and intermediate structures). Accordingly, variations in the shapes of the illustrations as a result, for example, of manufacturing techniques and/or tolerances are to be expected. Thus, example embodiments should not be construed as limited to the particular shapes of regions illustrated herein but are to include deviations in shapes that result, for example, from manufacturing. For example, an implanted region illustrated as a rectangle will, typically, have rounded or curved features and/or a gradient of implant concentration at its edges rather than an abrupt change from implanted to non-implanted region. Similarly, a buried region formed by implantation may result in some implantation in the region between the buried region and the surface where the implantation occurs. Thus, the regions illustrated in the figures are schematic in nature and their shapes are not intended to illustrate the actual shape of a region of a device and are not intended to limit the scope of the presently disclosed subject matter.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the disclosed subject matter belongs. It will also be understood that, unless expressly defined herein, terms (such as those defined in commonly used dictionaries) should be construed to have a meaning consistent with their meaning in the context of the relevant art, and not to be construed as ideal cultured or overly formal.

Hereinafter, example embodiments will be described in detail with reference to the accompanying drawings.

FIG. 1 is a block diagram of an example embodiment of a system 100 in accordance with the disclosed subject matter. In various embodiments, system 100 may include a computer, a number of discrete integrated circuits, or a system on a chip (SoC). As described below, system 100 may include some other components that are not shown in the figures in order not to obscure the subject matter of the present disclosure.

In the illustrated embodiment, system 100 includes system memory or main memory 104 . In various embodiments, system memory 104 may consist of dynamic random access memory (DRAM). However, it should be understood that the above is merely an illustrative example which does not limit the subject matter of the present disclosure. In such an embodiment, the system memory 104 may comprise memory on a module (e.g., a dual in-line memory module (DIMM)), the system memory 104 may be an integrated chip that is soldered or otherwise fixedly integrated with the system 100, Or system memory 104 may even be incorporated as part of an integrated chip comprising system 100 (eg, SoC). It should be understood that the above are merely illustrative examples that do not limit the subject matter of the present disclosure.

In the illustrated embodiment, system memory 104 may be configured to store multiple pieces of data or information. These pieces of data may include instructions that cause processor 102 to perform various operations. System memory 104 may typically be part of a larger memory hierarchy including several cache memories. In various embodiments, the operations described herein may be performed by another layer or level of that memory hierarchy (eg, Level 2 (L2) cache memory). Those skilled in the art will appreciate that although operations are described with reference to system memory 104 , the disclosed subject matter is not limited to this illustrative example.

In the illustrated embodiment, system 100 also includes processor 102 . Processor 102 may be configured to perform a number of operations commanded by various instructions. These instructions may be executed by various execution units (probably not shown), such as the arithmetic logic unit (ALU), floating point unit (FPU), load/store unit (LSU), and instruction fetch unit 116 (IFU). It should be understood that a unit is merely an aggregation of circuits combined together to perform a portion of the functions of the processor 102 . A unit typically performs one or more operations in the pipelined architecture of processor 102 .

In the illustrated embodiment, processor 102 may include a branch prediction unit (BPU) or circuit 112 . As noted above, when processor 102 is executing a stream of multiple instructions, one (or more) of the multiple instructions may be a branch instruction. A branch instruction is an instruction that causes instruction flow to branch or fork between one of two or more paths. A typical example of a branch instruction is an if-then structure, where, in an if-then structure, a first set of instructions will be executed if a certain condition is met (for example, the user clicks an "OK" button), if If the specified condition is not met (for example, the user clicks on the "Cancel" button), the second set of instructions will be executed. As mentioned above, since the new instruction must enter the pipeline of the processor 102 before the result of the branch, jump, or if-then structure is known (when the pipeline stage that resolves the branch instruction is deep in the pipeline), this is done in the pipeline. is a problem in the architecture of the server. Therefore, new instructions must be blocked from entering the pipeline until the branch instruction is resolved (thus negating the main advantage of the pipelined architecture), or the processor 102 must make a guess as to which path the instruction stream will branch to and speculatively forward those instructions put in the pipeline. BPU 112 may be configured to predict how the instruction stream will branch. In the illustrated embodiment, BPU 112 may be configured to output predicted instructions 172 , or more precisely, output memory addresses where predicted instructions 172 are stored.

In the illustrated embodiment, processor 102 includes a branch predictive address queue (BPAQ) 114 . BPAQ 114 may include a memory structure configured to store a plurality of addresses of predicted instructions 172 that have been predicted by BPU 112 . BPAQ 114 may store these predicted instruction 172 addresses in a first-in-first-out (FIFO) order so that instruction addresses are output from BPAQ 114 in the same order that BPU 112 predicted them.

In the illustrated embodiment, processor 102 includes an instruction fetch unit (IFU) 116 configured to fetch instructions from the memory hierarchy and place them in the pipeline of processor 102 . In such an embodiment, IFU 116 may be configured to obtain from BPAQ 114 the memory address associated with at least the newest or oldest instruction (next instruction 174 ) and request the actual instruction 174 from the memory hierarchy. Ideally, instructions 174 would be quickly served from the memory hierarchy and placed in the pipeline of processor 102 .

In the illustrated embodiment, BPAQ 114 is configured to separate BPU 112 from IFU 116 . In such embodiments, BPU 112 predicts instructions 172 at a different rate (eg, faster than IFU 116 consumes instructions) than IFU 116 consumes instructions. In connected or unbuffered architectures or embodiments, IFU 116 may be required to fetch predicted instructions as quickly as BPU 112 predicts them. In the illustrated embodiment, since any additional addresses of predicted instructions 172 produced by BPU 112 can simply be stored in BPAQ 114, IFU 116 can experience delays (e.g., cache misses and pipeline stalls, etc.) and BPU 112 is not affected. When the IFU 116 is able to resume consuming the address of the new instruction 174, the address will wait in the BPAQ 114.

Returning to the fetch mechanism of IFU 116 , ideally, instructions 174 may be fetched (via memory access 178 ) from level 1 (L1 ) instruction cache 118 . In such an embodiment, as the top level or higher of the memory hierarchy, the L1 instruction cache 118 may be relatively fast and induce little or no delay in the pipeline. However, the L1 instruction cache 118 may sometimes not include the desired instruction 174 . This would cause a cache miss, and the instruction would have to be fetched or loaded from a lower, slower level of the memory hierarchy (eg, system memory 104). Such a cache miss may cause a delay in the pipeline of the processor 102 since instructions will not be fed into the pipeline at a pre-cycle speed (or whatever maximum speed the processor's architecture is).

In the illustrated embodiment, processor 102 includes an instruction prefetch unit (IPFU) 120 . IPFU 120 is configured to prefetch instructions into L1 instruction cache 118 before IFU 116 performs the actual fetch operation. Thus, IPFU 120 reduces the occurrence of any cache misses experienced by IFU 116 . IPFU 120 may do this by requesting predicted instructions 172 from L1 instruction cache 118 before IFU 116 requests. In such an embodiment, if a cache miss subsequently occurs, L1 instruction cache 118 will begin requesting processing of the missing instruction from system memory 104 . In such embodiments, instructions may be received and stored in L1 instruction cache 118 as IFU 116 requests it.

In various embodiments, IPFU 120 may discard any returned instructions 172 or may not Contains the structure that actually receives the instruction 172 . For example, signals 177 between IPFU 120 and L1 instruction cache 118 may include control signals needed to request memory addresses and receive any status updates regarding those requests (e.g., whether there was a cache miss, whether the request was fulfilled), But data lines or signals that would carry the actual data requested by the memory access (eg, the values that make up the instruction 172 itself) may not be included. It should be understood that the above is merely an illustrative example which does not limit the subject matter of the present disclosure.

In the illustrated embodiment, the IPFU 120 may be configured to only prefetch the predicted instruction 172 (issued by the BPU 112) and the next instruction 174 (fetched by the IFU 116) if there is a definite relationship Directive 172. In various embodiments, the relationship between two instructions 172 and instructions 174 may be a measure of how speculative the BPU 112's predictions are. For example, IPFU 120 may not wish to prefetch predicted instructions 172 if BPU 112 is uncertain about the correctness of its prediction.

In various embodiments, prefetching incorrectly predicted instructions 172 may have unwanted effects. For example, if an incorrectly predicted instruction 172 is fetched and placed in the pipeline, it will have to be flushed later and the results of any calculations will have to be undone, causing an expensive dispatch of the processor 102 . Furthermore, any instructions loaded into the L1 instruction cache 118 but never fetched or used may cause cache pollution. Cache pollution typically evictes data that may be expected or available when unused or unwanted data fills the limited space of the cache. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In some embodiments, BPU 112 may indicate to IPFU 120 the degree of speculativeness of predicted instructions 172 . However, in the example shown, the degree of speculativeness may be inferred from readily available information found within the BPAQ 114 (shown by signal 176 ). In such an embodiment, the relationship between the predicted instruction 172 and the next instruction 174 may be their distance from each other for their respective addresses in the BPAQ 114 or the current depth of the BPAQ 114 . In such an embodiment, the further back the IFU 116 is, the more speculative the predicted instructions 172 become. In various embodiments, IPFU 120 may throttle or suppress any prefetch actions if the distance exceeds a predetermined threshold (discussed in FIG. 2 ). However, if the depth is below the threshold, IPFU 120 may prefetch predicted instructions 172 . It should be understood that the above is merely an illustrative example which does not limit the subject matter of the present disclosure.

In one embodiment, if IPFU 120 has limited prefetching and subsequently does not limit or resume prefetching, IPFU 120 may be configured to begin resuming prefetching at any instruction that had been predicted when the throttling began, so that all instructions ( as long as they are in BPAQ 114). In another embodiment, the IPFU 120 may simply not prefetch any predicted instructions 172 sent by the BPU 112 during a restricted period of time, but start or resume prefetching when a new address for a predicted instruction 172 is output by the BPU 112 . In such an embodiment, IFU 116 is responsible for fetching the missed instruction even if the missed instruction was not prefetched. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

FIG. 2 is a block diagram of an example embodiment of a device 200 consistent with the subject matter of this disclosure. In various embodiments, device 200 may be part of a processor, as described above. In some embodiments, device 200 may be part of a larger or unified instruction fetch unit or prefetch unit configured to predict, prefetch, and ultimately fetch instructions for processor execution. In another embodiment, the elements described herein may be discrete. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In the illustrated embodiment, device 200 includes a branch prediction unit (BPU) 212 . In the illustrated embodiment, device 200 includes an instruction fetch unit (IFU) 216 . Device 200 also includes an instruction prefetch unit (IPFU) 220 and a branch predictive address queue (BPAQ) 214 .

In the illustrated embodiment, the interior of the BPAQ 214 is highlighted and clearly shown. While six queue entries or fields are specifically shown, it should be understood that the above is merely an illustrative example that does not limit the subject matter of the present disclosure. As BPU 212 outputs predicted instructions, or more specifically, memory addresses of predicted instructions, they may be queued within BPAQ 214 in a FIFO fashion. In the illustrated embodiment, there are four instruction addresses queued within BPAQ 214 : the address of predicted instruction 254 b , the address of predicted instruction 254 a , the address of predicted instruction 254 , and the address of next instruction 252 . Since next instruction 252 is the next instruction to be processed by IFU 216 (assuming no exceptional events such as pipeline flushes occur), the oldest predicted instruction refers to next instruction 252 .

In the illustrated embodiment, BPAQ 214 maintains a valid instruction count (VIC) 256 . In such an embodiment, VIC 256 may simply be a count of the number of addresses of predicted instructions currently stored by BPAQ 214 (eg, four in the example shown). In some embodiments, it may be the index of the most recently queued instruction address (predicted instruction 254b). In another embodiment, VIC 256 may be the difference between the index of the address of the next instruction 252 and the index of the address of the latest predicted instruction 254b. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In such embodiments, VIC 256 is provided to IPFU 220 . The IPFU 220 receives the VIC 256 as an identifier of the degree of speculation or confidence associated with the latest predicted instruction 254b. In the illustrated embodiment, IPFU 220 may compare VIC 256 to threshold 266 (stored by IPFU 220 ). If VIC 256 is below threshold 266, IPFU 220 may prefetch the latest predicted instruction 254b. If VIC 256 is greater than or equal to threshold 266 , IPFU 220 may limit or otherwise suppress prefetching of the most recently predicted instruction 254b. In such an embodiment, IPFU 220 may be configured to halt any prefetching if the degree of speculation associated with the most recently predicted instruction 254b is too high or the degree of confidence is too low. It should be understood that the above is merely one illustrative example that does not limit the disclosed subject matter, and that, in other embodiments, the limitation may be based on whether VIC 256 is less than a threshold or any other comparison mechanism (such as a sliding comparison). It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In various embodiments, threshold 266 may be dynamically adjusted. However, in the illustrated embodiment, threshold 266 may be a static predetermined value. In one embodiment, while threshold 266 may include a value of 2, it should be understood that the above is merely one illustrative example that does not limit the subject matter of the present disclosure.

FIG. 3 is a block diagram of an example embodiment of a device 300 consistent with the subject matter of the present disclosure. In various embodiments, device 300 may be part of a processor, as described above. In some embodiments, device 300 may be part of a larger or unified instruction fetch unit or prefetch unit configured to predict, prefetch, and ultimately fetch instructions for processor execution. In another embodiment, the elements described herein may be discrete. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In the illustrated embodiment, device 300 includes a branch prediction unit (BPU) 312 . In the illustrated embodiment, device 300 includes instruction fetch unit (IFU) 216 , instruction prefetch unit (IPFU) 320 , and branch predictive address queue (BPAQ) 314 .

While BPAQ 314 shows six queue entries or fields, it should be understood that the above is merely one illustrative example that does not limit the subject matter of the present disclosure. As BPU 312 outputs predicted instructions, or more specifically, memory addresses of predicted instructions, they may be queued within BPAQ 314 in a FIFO fashion. In the illustrated embodiment, there are four instruction addresses currently queued within BPAQ 314 : the address of predicted instruction 254 b , the address of predicted instruction 254 a , the address of predicted instruction 254 , and the address of next instruction 252 .

In the illustrated embodiment, the BPU 312 outputs a confidence level 354b, a confidence level 354a, Confidence level 354 and confidence level 352 . Confidence level 354b, confidence level 354a, confidence level 354, and confidence level 352 may indicate a degree of confidence or speculation by BPU 320 that the predicted instruction will actually be executed by the processor.

In some embodiments, Confidence Level 354b, Confidence Level 354a, Confidence Level 354, and Confidence Level 352 may be binary and indicate whether there are any guesses in all predictions. For example, if no unresolved branch instruction is encountered in the instruction stream, all instructions in the stream will necessarily be jumped (unless an unforeseen error occurs, such as a division by zero error). Thus, any of predicted instruction 254b, predicted instruction 254a, predicted instruction 254, and next instruction 252 can be predicted with absolute confidence, and it can be assumed that they will always need to be prefetched. Conversely, as described below, if an unresolved branch instruction has been encountered, predicted instruction 254b, predicted instruction 254a, predicted instruction 254, and next instruction 252 may all be speculative in nature, and IPFU 320 may respond accordingly. take action.

In another embodiment, confidence level 354b, confidence level 354a, confidence level 354, and confidence level 352 indicate the number of branch instructions in the instruction stream that are still unresolved. For example, if no unresolved branch instructions were encountered, the predicted instruction 254 issued may be associated with a confidence level 354 of 0 (where a lower value indicates a higher confidence). Confidence level 354 may be increased to 1 upon encountering the first unresolved branch instruction. The predicted instruction 254 predicted between the first unresolved branch instruction and the second unresolved branch instruction can also be associated with a confidence level of 1 because the predicted instruction 254 is associated with this The first branch instruction of a fork or branch is relevant, so the BPU 312 will not care whether those predicted instructions are right or wrong. However, when a second unresolved branch instruction is encountered, the confidence level 354 may increase to 2, and all subsequent instructions may be marked with a value of 2 (unless a third unresolved branch instruction is encountered). A value of 2 indicates that those instructions are double speculative and based on two levels of guesswork.

In another embodiment, the confidence level (eg, confidence level 354 ) is indicative of an internal state of a state machine or counter of the BPU 312 . In various embodiments, the BPU 312 may base its predictions away from an internal state machine (not shown). In some embodiments, a four-state state machine is employed having states such as, for example, Strong Not Jumped, Weak Not Jumped, Weakly Jumped, and Strongly Jumped. In such an embodiment, information about the state (eg, "strong" or "weak" aspects) may be included in the confidence level (eg, confidence level 354). It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

In the illustrated embodiment, each confidence level 354b, confidence level 354a, confidence level 354, and confidence level 352 may be stored within the BPAQ 314 for a respective predicted instruction 254b, predicted instruction 254a, predicted instruction 254, and next Next to an instruction 252. In the illustrated embodiment, next instruction 252 is associated with confidence level 352; predicted instruction 254 is associated with confidence level 354; predicted instruction 254a is associated with confidence level 352a; predicted instruction 254b is associated with confidence level 354b. However, in other embodiments, BPAQ 314 may not store confidence level 354b, confidence level 354a, confidence level 354, and confidence level 352, so that IPFU 320 only uses the confidence level associated with the most recently predicted instruction (e.g., Confidence level of association 354b).

In such an embodiment, IPFU 320 receives confidence level 352 and a predicted instruction address (eg, confidence level 354 associated with the address of predicted instruction 254 ). In the illustrated embodiment, the IPFU 320 may be configured to consider the confidence level 354b when determining to prefetch a predicted instruction 254b or limit any prefetch. In the illustrated embodiment, IPFU 320 may include or store a confidence level threshold 366 . In such an embodiment, if the confidence level 354b (in the case of the predicted instruction 254b) is greater than the confidence level threshold 366, prefetching is stopped or limited. However, predicted instructions 254b having a confidence level 354b below a confidence level threshold 366 may be prefetched.

In some embodiments, the IPFU 320 may base the prefetch decision on the difference between the confidence level 352 of the next instruction 252 and the confidence level 354b of the most recently predicted instruction 245b. In such an embodiment, the threshold 366 may be compared to relative confidence levels rather than absolute values. That is, the confidence level relationship or difference between the next instruction 252 and the predicted instruction 254b is a determining factor in the prefetch decision. It should be understood that the above is merely an illustrative example which does not limit the subject matter of the present disclosure.

In another embodiment, IPFU 320 may also employ VIC 256 as described above. For example, if the BPU 312 generates a large number of predicted instructions 254 with high confidence, but the IFU 216 fetches only a small number of next instructions 252, the depth of the BPAQ 314 becomes relatively large. As a result, an embodiment of the IPFU 320 that makes prefetch decisions based solely on the confidence level 354 may prefetch so many predicted instructions 254 that the cache becomes full or polluted. When the IFU 216 finally begins to consider fetching the next instruction 252, the cache may have already moved it out in favor of a later predicted instruction (eg, predicted instruction 254b), thus negating the desired benefit of prefetching.

In such embodiments, a multi-criteria IPFU 320 may be employed. IPFU 320 may be configured to take confidence level 354 into account, as well as VIC 256 . IPFU 320 may limit prefetch operations if the value of confidence level 352 or the value of VIC 256 exceeds its respective threshold 366 or 266 . In such an embodiment, IPFU 320 may be configured to prefetch predicted instructions 254 that are less speculative, and not to fill the cache with instructions 254 that have not been requested by IFU 216 . It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure. In other embodiments, various other schemes may be employed by the IFPU of an embodiment to determine whether a predicted instruction should be prefetched. The disclosed subject matter is not limited to the embodiments discussed with respect to FIG. 2 or FIG. 3 .

FIG. 4 is a functional block diagram of an information handling system 400 that may include a semiconductor device produced in accordance with the principles of the disclosed subject matter.

Referring to FIG. 4 , an information handling system 400 may include one or more devices constructed in accordance with the principles of the disclosed subject matter. In another embodiment, information handling system 400 may employ or perform one or more techniques in accordance with principles of the disclosed subject matter.

In various embodiments, information handling system 400 may include computing devices such as, for example, laptop computers, desktop computers, workstations, servers, blade servers, personal digital assistants, smartphones, tablet computers, and other suitable computers, etc. or a virtual machine or its virtual computing appliance. In various embodiments, information handling system 400 may be used by a user (not shown).

Information handling system 400 according to the disclosed subject matter may also include a central processing unit (CPU), logic or processor 410 . In some embodiments, processor 410 may include one or more functional unit blocks (FUBs) or combinational logic blocks (CLBs) 415 . In such embodiments, the combinational logic blocks may include various Boolean logic operations (eg, NAND, NOR, NOT, XOR, etc.), stable logic devices (eg, flip-flops and latches, etc.), other logic devices or combinations thereof. These logical combinational operations can be configured in simple or complex ways to process input signals to obtain desired results. It should be understood that while some illustrative examples of synchronous combinatorial logic operations are described, the disclosed subject matter is not so limited and may include asynchronous operations or mixtures thereof. In one embodiment, a combinational logic operation may include a plurality of complementary metal oxide semiconductor (CMOS) transistors. In various embodiments, while these CMOS transistors may be arranged in gates performing logic operations, it should be understood that other techniques may be used and fall within the scope of the disclosed subject matter.

The information handling system 400 according to the presently disclosed subject matter may also include a volatile memory 420 (eg, random access memory (RAM), etc.). The information handling system 400 according to the presently disclosed subject matter may also include a non-volatile memory 430 (eg, hard disk drive, optical memory, NAND or flash memory, etc.). In some embodiments, volatile memory 420, non-volatile memory 430, or combinations or portions thereof may be referred to as "storage media." In various embodiments, volatile memory 420 and/or nonvolatile memory 430 may be configured to store data in a semi-permanent or substantially permanent form.

In various embodiments, information handling system 400 may include one or more network interfaces 440 configured to allow information handling system 400 to be part of and communicate over a communication network. Examples of Wi-Fi protocols may include, but are not limited to, Institute of Electrical and Electronics Engineers (IEEE) 802.11g and IEEE 802.11n, among others. Examples of cellular protocols may include (but are not limited to) IEEE 802.16m (aka Wireless MAN Advanced (Metropolitan Area Network)), Long Term Evolution (LTE) Advanced), Enhanced Data Rates for GSM (Global System for Mobile Communications) Evolution (EDGE ), Evolved High Speed Packet Access (HSPA+), etc. Examples of wired protocols may include, but are not limited to, IEEE 802.3 (aka, Ethernet), Fiber Channel, Powerline Communications (eg, HomePlug and IEEE 1901, etc.), and the like. It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

The information processing system 400 according to the presently disclosed subject matter may further include a user interface unit 450 (eg, a display adapter, a tactile interface, and a human interface device, etc.). In various embodiments, this user interface unit 450 may be configured to receive input from a user and/or provide output to the user. Other types of devices may also be used to provide interaction with the user; for example, the feedback provided to the user may be any form of sensory feedback (e.g., visual, auditory, or tactile feedback); input from the user may include Any form of acoustic, speech or tactile input is received.

In various embodiments, information handling system 400 may include one or more other devices or hardware components 460 (eg, display or monitor, keyboard, mouse, camera, fingerprint reader, video processor, etc.). It should be understood that the above are merely some illustrative examples which do not limit the subject matter of the present disclosure.

Information handling system 400 according to the presently disclosed subject matter may also include one or more system buses 405 . In such an embodiment, system bus 405 may be configured to communicatively couple processor 410, volatile memory 420, nonvolatile memory 430, network interface 440, user interface unit 450, and one or more hardware components 460 . Data processed by the processor 410 or data input from the outside of the nonvolatile memory 430 may be stored in the nonvolatile memory 430 or the volatile memory 420 .

In various embodiments, information handling system 400 may include or execute one or more software components 470 . In some embodiments, software components 470 may include an operating system (OS) and/or applications. In some embodiments, the OS may be configured to: provide one or more services to applications, and manage applications and various hardware components (eg, processor 410 and network interface 440 , etc.) of information handling system 400 or serve as an information The intermediary between the applications of the processing system 400 and the various hardware components. In such an embodiment, information handling system 400 may include one or more local applications that may be installed locally (eg, within non-volatile memory 430 , etc.) and configured to directly Executed directly by the processor 410 and interacting directly with the OS. In such an embodiment, the native application may include pre-compiled machine-readable code. In some embodiments, a native application may include a script interpreter (e.g., C shell (csh), AppleScript, AutoHotkey, etc.) configured to convert source code or object code into executable code that is then executed by processor 410 Or a virtual execution machine (VM) (for example, a Java virtual machine and a Microsoft public speech runtime library, etc.).

The semiconductor devices described above may be packaged using various packaging techniques. For example, semiconductor devices constructed in accordance with the principles of the presently disclosed subject matter may be packaged using any of the following: stack-on-package (POP) technology, ball grid array (BGA) technology, chip-scale packaging (CSP) technology, leaded Plastic Chip Carrier (PLCC) Technology, Plastic Dual In-line Package (PDIP) Technology, Waffle Die Package, Die in Wafer Form, Chip on Board (COB) Technology, Ceramic Dual In-line Package (CERDIP) Technology, Plastic Metric Quad Flat Package (PMQFP) Technology, Plastic Quad Flat Package (PQFP) Technology, Small Outline Integrated Circuit (SOIC) Technology, Shrink Small Outline Package (SSOP) Technology, Thin Small Outline Package (TSOP) Technology , thin quad flat package (TQFP) technology, system-in-package (SIP) technology, multi-chip package (MCP) technology, wafer-level manufacturing package (WFP) technology, and wafer-level processing stacked package (WSP) technology or technology in this field Other techniques will be known to persons.

Method steps may be performed by one or more programmable processors executing a computer program to perform functions by operating on input data and generating output. Method steps can also be performed by, and apparatus can be implemented as, special purpose logic circuitry, such as an FPGA (Field Programmable Gate Array) or an ASIC (Application Specific Integrated Circuit).

In various embodiments, a computer-readable medium may include instructions that, when executed, cause an apparatus to perform at least a portion of the method steps. In some embodiments, the computer readable medium may be included in magnetic media, optical media, other media, or combinations thereof (eg, CD-ROM, hard drive, read-only memory or flash drive, etc.). In such embodiments, the computer readable medium may be a tangible and non-transitory embodied article of manufacture.

While the principles of the disclosed subject matter have been described with reference to example embodiments, it will be apparent to those skilled in the art that various changes and modifications can be made to the example embodiments without departing from the spirit and scope of these disclosed concepts. . Therefore, it should be understood that the above-described embodiments are not limiting, but illustrative only. Accordingly, the scope of the disclosed concept is to be determined by the broadest permissible interpretation of the claims and their equivalents, and shall not be restricted or limited by the foregoing description. Therefore, it will be understood that the claims are intended to cover all modifications and changes that fall within the scope of the embodiments.

Claims (20)

1. A device for prefetching data, comprising: a branch prediction unit configured to output predicted instructions; a fetch unit configured to fetch a next instruction from the cache memory; A prefetcher circuit configured to prefetch a previously predicted instruction into a cache memory based on a relationship between the predicted instruction and a next instruction. 2. The apparatus of claim 1, wherein the prefetcher circuit is configured to limit prefetching if a relationship between the predicted instruction and the next instruction does not satisfy a predetermined criterion. 3. The apparatus of claim 1, further comprising a branch prediction queue configured to store one or more predicted instructions of the plurality of predicted instructions and separate the branch prediction unit from the fetch unit. 4. The apparatus of claim 3, wherein the branch prediction queue outputs a valid instruction count to the prefetcher circuit, wherein the valid instruction count indicates a relationship between the predicted instruction and the next instruction. 5. The apparatus of claim 1, wherein the prefetcher circuit is configured to prefetch the previously predicted instruction if the number of predicted instructions between the predicted instruction and the next instruction does not exceed a threshold. 6. The apparatus of claim 1, wherein the relationship between the predicted instruction and the next instruction is indicative of a degree of speculation employed by the branch prediction unit. 7. The apparatus of claim 1, wherein the branch prediction unit provides the memory address of the predicted instruction to the prefetcher circuit. 8. The apparatus of claim 1 , wherein the branch prediction unit uses the predicted instruction to indicate a degree of confidence that the branch prediction unit has that the predicted instruction will be executed by the apparatus; Wherein, the prefetcher circuit is configured to prefetch the predicted instruction if the confidence level is at or above a threshold, and refrain from prefetching the predicted instruction if the confidence level is below the threshold value. 9. A method for prefetching data comprising: predicted instructions to be executed by the processor predicted by the prediction circuit; fetching the next instruction from the cache memory by the fetch circuit; determining whether a relationship between the predicted instruction and the next instruction satisfies a set of one or more predetermined criteria; The predicted instruction is prefetched into the cache memory if the set of one or more predetermined criteria is met. 10. The method of claim 9, further comprising: prefetching instructions into cache memory if the relationship between the predicted instruction and the next instruction does not satisfy the set of one or more predetermined criteria Limit. 11. The method of claim 9, further comprising enqueuing the predicted instructions in a queue, wherein the queue separates the prediction unit from the fetch unit. 12. The method of claim 11, wherein the step of determining the relationship comprises: A valid instruction count is received from the queue by the prefetcher circuit, wherein the valid instruction count indicates a relationship between the predicted instruction and the next instruction. 13. The method of claim 11, wherein determining a relationship comprises determining whether a number of predicted instructions between a predicted instruction and a next instruction exceeds a threshold. 14. The method of claim 9, wherein determining the relationship comprises determining a degree of speculation involved in predicting the predicted instruction. 15. The method of claim 9, wherein prefetching the predicted instruction comprises receiving a memory address of the predicted instruction from a prediction circuit. 16. An apparatus for prefetching data comprising: a processor configured to execute instructions; a cache memory configured to temporarily store instructions; a branch prediction unit configured to output predicted instructions, wherein the predicted instructions are speculatively predicted to be executed by the processor, wherein the branch prediction unit is separate from the fetch unit; the fetch unit may be configured to fetch a next instruction from the cache memory; A prefetcher circuit configured to prefetch a previously predicted instruction into the cache memory in response to a relationship between the predicted instruction and a next instruction satisfying one or more predetermined criteria. 17. The apparatus of claim 16, further comprising a branch prediction queue configured to store one or more predicted instructions of the plurality of predicted instructions and separate the branch prediction unit from the fetch unit. 18. The apparatus of claim 17, wherein the branch prediction queue outputs a valid instruction count to the prefetcher circuit; Wherein, the prefetcher circuit is configured to prefetch the previously predicted instruction if the valid instruction count does not exceed the threshold, and suppress the prefetching of the previously predicted instruction if the valid instruction count exceeds the threshold. 19. The apparatus of claim 16, wherein the relationship between the predicted instruction and the next instruction is indicative of a degree of speculation employed by the branch prediction unit. 20. The apparatus of claim 16, wherein the branch prediction unit provides the memory address of the predicted instruction to the prefetcher circuit.