| Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline -> Monitor Keywords |
|
|
  Method and apparatus for managing instruction flushing in a microprocessor's instruction pipelineUSPTO Application #: 20060282829Title: Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline Abstract: In one or more embodiments, a processor includes one or more circuits to flush instructions from an instruction pipeline on a selective basis responsive to detecting a branch misprediction, such that those instructions marked as being dependent on the branch instruction associated with the branch misprediction are flushed. Thus, the one or more circuits may be configured to mark instructions fetched into the processor's instruction pipeline(s) to indicate their branch prediction dependencies, directly or indirectly detect incorrect branch predictions, and directly or indirectly flush instructions in the instruction pipeline(s) that are marked as being dependent on an incorrect branch prediction. (end of abstract) Agent: Qualcomm Incorporated - San Diego, CA, US Inventors: Michael Scott Mcllvaine, James Norris Dieffenderfer, Thomas Andrew Sartorius USPTO Applicaton #: 20060282829 - Class: 717131000 (USPTO) Related Patent Categories: Data Processing: Software Development, Installation, And Management, Software Program Development Tool (e.g., Integrated Case Tool Or Stand-alone Development Tool), Testing Or Debugging, Including Analysis Of Program Execution The Patent Description & Claims data below is from USPTO Patent Application 20060282829. Brief Patent Description - Full Patent Description - Patent Application Claims
BACKGROUND [0001] 1. Field of the Invention [0002] The present invention generally relates to microprocessors, and particularly relates to managing instruction flushing in a microprocessor's instruction pipeline. [0003] 2. Relevant Background [0004] Microprocessors find use in a wide variety of products, ranging from high-end computational systems, where processing power represents a paramount design consideration, to low-end embedded systems, where cost, size, and power consumption comprise the primary design considerations. Processors targeted for battery-powered portable devices, such as music players, palmtop computers, Portable Digital Assistants (PDAs), and the like, represent a particularly complex mix of competing design considerations. On the one hand, processor performance must be sufficient to support the device's intended functionality and provide a satisfactory user "experience." On the other hand, low processor power consumption helps to permit the use of reasonably sized battery systems, while achieving acceptable battery life. [0005] The above mix of design tradeoffs has resulted in numerous processor performance and efficiency advancements. For example, modem pipelined processors, such as those based on a Reduced Instruction Set Computer (RISC) architecture, oftentimes employ branch prediction methods to prevent instruction pipeline "stalls." With an instruction pipeline, different aspects of sequential instruction processing generally occur in different stages of the pipeline. For example, a given instruction pipeline may include successively arranged fetch, decode, issue, and execute stages. Each stage generally operates on a different instruction, or instructions, at each instruction clock cycle. For example, as the execution of one instruction is being completed in the execute stage, other instructions are being fetched, decoded, issued, etc. Staged execution allows the pipelined processor on average to execute one instruction per clock cycle. [0006] However, maintaining that one-instruction-per-clock cycle average depends on keeping the pipeline full of instructions. In turn, keeping the pipeline full of instructions means that the pipelined processor generally cannot afford to stop program instruction fetching while determining whether a given program branch will or will not be taken. That is, the processor generally must make a guess (a prediction) about whether a given program branch will be taken or not taken. If the prediction is "taken," then instruction fetching continues from the branch target address. If the prediction is not taken, then instruction fetching continues from the next instruction address after the branch instruction. [0007] In either case, the instructions fetched into the pipeline subsequent to such a prediction will be the "wrong" instructions if that prediction was incorrect. The pipeline may have multiple predictions outstanding at any given time, i.e., it may have multiple undetermined branch instructions in-flight within various ones of its pipeline stages. Thus, any given one of the instructions in-flight within the pipeline may depend on one or more of the outstanding branch predictions, or may not depend on any of them. [0008] Such possibilities introduce a processing complexity in the context of branch mispredictions. Generally, at least some of the in-flight instructions will be dependent on at least one of the outstanding branch predictions, and therefore should be flushed from the instruction pipeline responsive to detecting a corresponding branch misprediction. The challenge arises from the difficulty in accurately identifying or tracking the branch prediction dependencies of the in-flight instructions, particularly because some instructions may be executed out of the original program order. [0009] For example, a given instruction may have to wait on data because of a cache miss and, rather than stalling the pipeline while the data is retrieved from external memory, execution of that instruction may be suspended while the pipeline continues processing other in-flight instructions. More generally, executing instructions out of program order represents one of the processing performance advantages of superscalar instruction pipelines comprising parallel sets of pipeline stages. Such superscalar pipelines may have large numbers of in-flight instructions, with many of them executing out of program order. [0010] Thus, selectively flushing only the instructions dependent on a particular branch misprediction represents a potentially significant challenge in terms of being able to accurately identify such dependencies without introducing too much tracking complexity. Of course, the alternative to selectively flushing instructions is flushing all instructions from the pipeline when a branch misprediction is detected, without regard to whether individual ones of those instructions actually depend on the mispredicted branch instruction. The downside of that approach is the performance and efficiency loss associated with flushing valid instructions from the pipeline that have already been fetched and at least partially processed. SUMMARY OF THE DISCLOSURE [0011] The present invention comprises a method and apparatus for managing instruction flushing in the instruction pipeline of a microprocessor. In at least one embodiment, one or more circuits included in the microprocessor are configured to manage instruction flushing based on marking instructions fetched into the instruction pipeline to indicate their branch prediction dependencies, detecting incorrect branch predictions, and flushing instructions in the instruction pipeline that are marked as being dependent on an incorrect branch prediction. [0012] Marking instructions fetched into the instruction pipeline to indicate their branch prediction dependencies comprises, in at least one embodiment, activating bit indicators responsive to making branch predictions, leaving the corresponding bit indicator active for a particular branch prediction until that branch prediction is resolved, and marking each instruction fetched into the instruction pipeline with an aggregation of the active bit indicators. For example, flushing instructions in the instruction pipeline that are marked as being dependent on an incorrect branch prediction may comprise broadcasting a flush signal based on the bit indicator corresponding to the incorrect branch prediction, and flushing instructions in the instruction pipeline that are marked with that bit indicator. Similarly, a clear signal may be broadcast based on the bit indicator corresponding to a correct branch prediction to clear the corresponding bit indicator from the instructions in the instruction pipeline that were marked as being dependent on that branch prediction. Clearing allows bit indicators to be re-used in the dependency marking process. [0013] In one or more embodiments, marking instructions fetched into the instruction pipeline to indicate their branch prediction dependencies comprises assigning a "branch flush tag" at least to each conditional branch instruction fetched into the instruction pipeline, and appending a "branch path tag" based on the previously assigned branch flush tags to each instruction fetched into the instruction pipeline. In the context of this embodiment, flushing instructions in the instruction pipeline that are marked as being dependent on an incorrect branch prediction may be based on resolving branch conditions in an execution stage of the instruction pipeline to detect correct and incorrect branch predictions, and, for an incorrect branch prediction, broadcasting a flush signal in the instruction pipeline based on the branch flush tag of the associated conditional branch instruction. Instructions in the instruction pipeline whose branch path tags are marked with the branch flush tag of the associated conditional branch instruction may be flushed responsive to the broadcast. [0014] Accordingly, one or more processor embodiments include a flush control circuit configured to mark instructions fetched into the instruction pipeline to indicate their branch prediction dependencies, detect incorrect branch predictions, and flush instructions in the instruction pipeline that are marked as being dependent on an incorrect branch prediction. The flush control circuit may, in carrying out these operations, generate and maintain branch flush tags and branch path tags, and may include circuitry for cooperating with one or more of the instruction pipeline stages, to carry out the clearing and flushing operations described above, or to carry out variations of those operations. BRIEF DESCRIPTION OF THE DRAWINGS [0015] FIG. 1 is a block diagram illustrating a microprocessor, including an instruction pipeline and an associated flush control circuit. [0016] FIG. 2 is a block diagram of one embodiment of an instruction pipeline and its associated flush control circuit. [0017] FIG. 3 is a logic flow diagram of processing logic supporting one embodiment of flushing instructions from an instruction pipeline based on marking and tracking branch prediction dependencies. [0018] FIG. 4 is a program instruction flow diagram illustrating six instructions fetched into an instruction pipeline in program flow order. [0019] FIG. 5 is a block diagram of a superscalar instruction pipeline supporting out-of-order instruction execution. [0020] FIG. 6 is a table illustrating the generation and appending of branch flush tags specifically to branch instructions fetched into an instruction pipeline and appending branch path tags generally to all types of instructions fetched into the instruction pipeline. [0021] FIG. 7 is a block diagram of a representative set of branch flush tags corresponding to a given number of outstanding branch predictions, and a corresponding branch path tag that logically aggregates the individual branch flush tags. Continue reading... Full patent description for Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline or other areas of interest. ### Previous Patent Application: Operating system loader modification Next Patent Application: Analysis of the impact of application programs on resources stored in data stores Industry Class: Data processing: software development, installation, and management ### FreshPatents.com Support Thank you for viewing the Method and apparatus for managing instruction flushing in a microprocessor's instruction pipeline patent info. IP-related news and info Results in 2.2669 seconds Other interesting Feshpatents.com categories: Daimler Chrysler , DirecTV , Exxonmobil Chemical Company , Goodyear , Intel , Kyocera Wireless , |
||
