Patent Publication Number: US-9891918-B2

Title: Fractional use of prediction history storage for operating system routines

Description:
CROSS REFERENCE TO RELATED APPLICATION(S) 
     This application is a continuation-in-part (CIP) of U.S. Non-Provisional application Ser. No. 14/165,354, filed Jan. 27, 2014, which is hereby incorporated by reference in its entirety. This application claims priority based on U.S. Provisional Application, Ser. No. 62/069,602, filed Oct. 28, 2014, which is hereby incorporated by reference in its entirety. 
    
    
     BACKGROUND 
     Modern microprocessors employ various prediction techniques to improve their performance. For example, branch predictors predict whether branch instructions will be taken or not taken and, if taken, predict the target address of the branch instruction. Dynamic branch predictors accumulate a history of outcomes of different branch instruction executions and make their predictions based on the history. The prediction accuracy of a dynamic branch predictor is largely a function of the amount of history it is capable of accumulating. As long as the set of branch instructions that are being executed by a program within a given time is small enough to be contained within the prediction history, the accuracy may be very high. 
     However, the prediction accuracy may be greatly diminished by certain events. One such event is when the currently running program is interrupted temporarily while another program runs. For example, a packet may be received by a network interface controller, which signals an interrupt to the processor. The processor transfers control to the operating system to service the interrupt, which temporarily suspends the currently running program A until the operating system returns control back to running program A. While the processor is executing branch instructions of the operating system, it is polluting the prediction history in the branch predictor for program A. This is likely to diminish the accuracy of the branch predictor for predicting branches of program A. 
     BRIEF SUMMARY 
     In one aspect the present invention provides a microprocessor. The microprocessor includes a predicting unit having storage for holding a prediction history of characteristics of instructions previously executed by the microprocessor. The predicting unit accumulates the prediction history and uses the prediction history to make predictions related to subsequent instruction executions. The storage comprises a plurality of portions separately controllable for accumulating the prediction history. The microprocessor also includes a control unit that detects the microprocessor is running an operating system routine and controls the predicting unit to use only a fraction of the plurality of portions of the storage to accumulate the prediction history while the microprocessor is running the operating system routine. 
     In another aspect, the present invention provides a method for operating a microprocessor having a predicting unit with storage for holding a prediction history of characteristics of instructions previously executed by the microprocessor, wherein the predicting unit accumulates the prediction history and uses the prediction history to make predictions related to subsequent instruction executions, wherein the storage comprises a plurality of portions separately controllable for accumulating the prediction history. The method includes detecting the microprocessor is running an operating system routine and controlling the predicting unit to use only a fraction of the plurality of portions of the storage to accumulate the prediction history while the microprocessor is running the operating system routine. 
     In yet another aspect, the present invention provides a method for improving performance of a microprocessor having a predicting unit having storage that accumulates prediction history of previously executed instructions used by the predicting unit to predict execution of subsequent instructions, wherein the predicting unit is dynamically controllable to use only a fraction of the storage to accumulate the prediction history. The method includes identifying a plurality of operating system routines called by software applications and counting respective numbers of instructions executed by each of the plurality of operating system routines. The method also includes selecting a subset of the plurality of operating system routines based on the respective numbers of instructions executed. The method also includes conducting performance analysis by varying values of the fraction of the predicting unit storage for the subset of the plurality of operating system routines to determine values of the fraction that optimizes performance of the software applications. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a microprocessor. 
         FIG. 2  is a flowchart illustrating operation of the microprocessor of  FIG. 1 . 
         FIG. 3  is a flowchart illustrating operation of the microprocessor of  FIG. 1  according to an alternate embodiment. 
         FIG. 4  is a flowchart illustrating operation of the microprocessor of  FIG. 1  according to an alternate embodiment. 
         FIG. 5  is a block diagram illustrating a control information table. 
         FIG. 6  is a block diagram illustrating a prediction history cache. 
         FIG. 7  is a block diagram illustrating a prediction history cache according to an alternate embodiment. 
         FIG. 8  is a block diagram illustrating a prediction history queue. 
         FIG. 9  is a flowchart illustrating a process for generating values with which to populate the table of  FIG. 5 . 
         FIG. 10  is a flowchart illustrating operation of a system that includes the microprocessor of  FIG. 1 . 
         FIG. 11  is a flowchart illustrating operation of a system that includes the microprocessor of  FIG. 1  according to an alternate embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Embodiments are described that may improve the performance of a microprocessor by selectively suspending accumulation of prediction history and prediction by predicting units (such as branch predictors, data prefetchers and store collision detection predictors) using the prediction history in favor of using static predictions while the dynamic predictions are suspended. More specifically, prediction history accumulation and use may be suspended while the microprocessor is running some threads but not others. For example, the suspension may be selective based on the privilege level at which the thread runs, more specifically, whether or not the thread runs at a supervisor privilege level, such as current privilege level (CPL) zero of an x86 architecture processor, which is also referred to as ring 0. For another example, the suspension may be selective based on the type of thread, such as whether the thread is an interrupt handler. For yet another example, the suspension may be selective based on whether the transition to a new thread was made in response to a system call instruction. For still another example, the microprocessor gathers information about previous execution instances of threads and the suspension may be selective based on the information, such as instruction length and performance information. For an additional example, the suspension may be selective based on the identity of the thread. The thread identity may be determined based on the type of event that caused the transition, architectural state of the processor when the event happened, and a combination thereof, for example. The event types may include execution of a system call, execution of a software interrupt instruction, execution of an inter-privilege or task switch procedure call and detection of an exception condition, for example. Still further, the microprocessor may save and restore the prediction histories to a local storage during the suspension of prediction history accumulation and use. 
     GLOSSARY 
     A predicting unit is hardware, software, or a combination of hardware and software of a microprocessor that makes predictions about actions that a stream of instructions running on the microprocessor will take. The predictions may include, but are not limited to, a prediction of whether a branch instruction will instruct the microprocessor to branch; a prediction of a target address of a branch instruction; a prediction of data that will be accessed by an instruction of the stream; a prediction of whether a store collision will occur. The predicting unit makes predictions based on a history of characteristics of instructions executed by the microprocessor, which predictions are referred to as dynamic predictions. The predicting unit accumulates the history as the microprocessor executes instructions of the stream. The history may include, but is not limited to, an outcome of whether a branch instruction instructed the microprocessor to branch; a target address of a taken branch instruction; addresses of data that was loaded or stored by instructions of the stream; information related to store instructions that specify cacheable memory locations, such as the address of the store instruction, identifiers of the sources used to calculate the store address, a reorder buffer index of an instruction upon which the store data depends, the address and reorder buffer index of a load instruction that previously collided with the store instruction, a reorder buffer index delta between colliding load and store instructions, an indicator of the number of times a colliding load instruction was replayed. The predicting unit may also make predictions not based on the history, which predictions are referred to as static predictions. 
     A privilege level of a microprocessor is defined by the microprocessor&#39;s instruction set architecture and controls the access of a currently running program to system resources, such as memory regions, I/O ports and certain instructions of the instruction set. 
     A thread is a sequence of instructions that are executed by a microprocessor. 
     A process is a thread and its associated state that is managed, along with other processes, by an operating system. The operating system assigns a process identifier to the process. 
     Referring now to  FIG. 1 , a block diagram of a microprocessor  100  is shown. The microprocessor  100  includes predicting units  109 . The predicting units  109  are coupled to a control unit  124  and a prediction history storage  108 . The control unit  124  is coupled to a retired instruction counter  113 , performance counters  114 , a current privilege level register  111 , and storage for holding optimization information  112 . In one embodiment, the microprocessor  100  includes one or more pipelines of functional units (not shown), including an instruction cache, instruction translation unit or instruction decoder, register renaming unit, reservation stations, data caches, execution units, memory subsystem and a retire unit including a reorder buffer. Preferably, the microprocessor  100  includes a superscalar, out-of-order execution microarchitecture. The predicting units  109  may be incorporated into the various functional units of the microprocessor  100  or may be functional units themselves. 
     The predicting units  109  comprise hardware, software, or a combination or hardware and software. The predicting units  109  include a branch prediction unit  102  comprising a storage array for storing a prediction history  132 A, a data prefetch unit  104  comprising a storage array for storing a prediction history  132 B, and a store collision prediction unit  106  comprising a storage array for storing a prediction history  132 C. The prediction histories are referred to either individually or collectively as prediction history  132  or prediction histories  132 , respectively. The predicting units  109  use their respective prediction histories  132  to make predictions about various aspects of instruction/data processing in order to attempt to improve the performance and/or reduce the power consumption of the microprocessor  100  through speculative operation. More specifically, the branch prediction unit  102  accumulates a history of the instruction address, direction (taken or not taken), and target address of branch instructions executed by the microprocessor  100  to enable the branch prediction unit  102  to dynamically predict the direction and target address of subsequent execution instances of the branch instructions. Dynamic branch prediction techniques are well known in the art of branch prediction. The data prefetch unit  104  accumulates a history of accesses to cacheable memory regions by program instructions in order to detect memory access patterns that it uses to predict which data from the cacheable memory regions will be accessed by the program in the future in order to prefetch the predicted data from system memory into a cache memory of the microprocessor  100  before the program requests the data in order to reduce the memory access time (since system memory latency is much greater than cache memory latency). Dynamic data prefetch techniques are well known in the art of data prefetching. The store collision prediction unit  106  accumulates a history of store instructions that specify cacheable memory locations in order to predict when a store collision will occur. A store collision occurs when a newer load instruction specifies data that overlaps data of an older store instruction. Predicting a store collision may enable the microprocessor  100  to speculatively forward data from the store instruction to the load instruction and/or to avoid executing a colliding load instruction out-of-order with respect to the older store instruction. It should be understood that the embodiments are not limited to these particular types of predicting units, but may include other types of predicting units that accumulate a history of characteristics of instructions as they are executed by the microprocessor  100  that are useful in enabling the predicting unit to make predictions about aspects of subsequently executed instructions or perform other speculative operations to attempt to increase the performance of the microprocessor  100  and/or reduce its power consumption. 
     In addition to the dynamic predictions made by each of the predicting units  109 , i.e., the predictions made using the prediction histories  132 , each of the predicting units  109  is also configured to make static predictions, i.e., predictions made without the use of the prediction histories  132 . For example, in one embodiment, the branch prediction unit  102  statically predicts all branch instructions whose target address is backward (e.g., a relative branch whose offset is a negative value) will be taken and all branch instructions whose target address is forward will be not taken, which does not require any history of previously executed instructions. For another example, in one embodiment, the data prefetch unit  104  statically predicts that when it detects a program accesses cacheable memory, the next sequential cache line of data will be needed, so it prefetches the next sequential cache line of data. Static prediction methods are also well known in the art of central processing units. 
     In one embodiment, the prediction history storage  108  is used by the predicting units  109  to save the prediction histories  132  in response to an event that causes the microprocessor  100  to transition from running one thread to running a different thread, such as a transition from a user privilege level to supervisor privilege level, and to restore the prediction histories  132  in response to an event that causes the microprocessor  100  to transition from the supervisor to privilege level back to a user privilege level, preferably if returning to a different user process than was running when the transition to supervisor privilege level was performed, as described in more detail below. 
     The current privilege level register  111  stores the current privilege level of the microprocessor  100 . In embodiments in which the microprocessor  100  substantially conforms to the x86 architecture, otherwise known as the Intel IA-32 Architecture and/or Intel 64 Architecture, which is effectively described in the Intel 64 and IA-32 Architectures Software Developer&#39;s Manual, Combined Volumes: 1, 2A, 2B, 2C, 3B and 3C, Order Number 325464-043US, May 2012, by the Intel Corporation of Santa Clara, Calif. In particular, in an x86 embodiment, the current privilege level register  111  indicates whether the microprocessor  100  is running at current privilege level 0, 1, 2 or 3, i.e., in ring 0, ring 1, ring 2 or ring 3. Ring 0 is the most privileged level, and ring 3 is the least privileged level (user privilege level). Rings 0, 1 and 2 are supervisor privilege levels. 
     The retired instruction counter  113  increments each time an instruction is retired. By subtracting the instruction counter  113  value when the microprocessor  100  begins running a thread, e.g., enters ring 0, from the instruction counter  113  value when the microprocessor  100  begins running a different thread, e.g., exits ring 0, the control unit  124  may determine how many instructions were retired by the thread, as described in more detail below. In one embodiment, the instruction counter  113  counts the number of macroinstructions retired (i.e., architectural instructions, such as x86 instructions), whereas in another embodiment the instruction counter  113  counts the number of microinstructions retired (i.e., non-architectural instructions defined by the microarchitecture instruction set of the microprocessor  100  into which the macroinstructions are translated by an instruction translator of the microprocessor  100  and that are executed by the execution units of the microprocessor  100 ). 
     The performance counters  114  comprise a plurality of counters that count many aspects related to the performance and/or power consumption of the microprocessor  100 . In one embodiment, the performance counters  114  count predicted branch instructions; correctly predicted branch instructions; incorrectly predicted branch instructions; cache lines allocated by a data prefetch; cache lines allocated by a non-prefetch mechanism, such as a demand load/store or direct memory access (DMA) request; program accesses to a cache line allocated by a data prefetch; cache lines allocated by a data prefetch that is evicted before it is used; store collision predictions; actual store collisions detected. 
     The optimization information  112  is used to selectively suspend accumulation and use of the prediction histories  132 , e.g., during supervisor level operation, as described in more detail herein, particularly with respect to the embodiment of  FIG. 3 . 
     The control unit  124  comprises hardware, software, or a combination or hardware and software. Based on its inputs—primarily the current privilege level  111 , the optimization information  112 , the retired instruction counter  113 , the performance counters  114 , thread transition event types, and architectural state—the control unit  124  controls the predicting units  109  to continue or to suspend accumulating their respective prediction histories  132  and making predictions using the prediction histories  132  and/or to save/restore the prediction histories  132  to/from the predictor history store  108 . In one embodiment, the control unit  124  comprises hardware state machines, microcode or a combination of hardware state machines and microcode. In one embodiment, the microcode comprises instructions that are executed by the execution units of the microprocessor  100 . 
     In one embodiment, a microcode unit (not shown) that controls fetching of the microcode includes its own fetch unit, or sequencer, and does not employ the branch prediction unit  102 , which predicts user program branch instructions only. 
     Referring now to  FIG. 2 , a flowchart illustrating operation of the microprocessor  100  of  FIG. 1  is shown. Flow begins at block  202 . 
     At block  202 , while running a thread operating at a user privilege level, e.g., ring 3, each of the predicting units  109  accumulates its respective prediction history  132  and makes dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions of the thread. Flow proceeds to block  212 . 
     At block  212 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a supervisor privilege level, e.g., ring 0. The event also causes the microprocessor  100  to transfer control to a different thread than the currently running thread. Examples of the event include, but are not limited to execution of an instruction, such as a system call instruction (e.g., x86 SYSENTER/SYSCALL instruction), a software interrupt (e.g., x86 INT instruction), or inter-privilege level or task switch procedure call instruction (e.g., x86 CALL instruction); and detection of an exception condition, such as a hardware interrupt (e.g., a timer tick, an I/O device) or page fault. In one embodiment, the event causes the microprocessor  100  to transfer control to the microcode, which performs various operations (e.g., permissions checks) before transferring control to the ring-0 thread, or routine, of the operating system that will handle the event. Flow proceeds to block  222 . 
     At block  222 , in response to the event detected at block  212 , the control unit  124  controls the predicting units  109  to suspend accumulating their respective prediction histories  132  and making predictions using the prediction history while the microprocessor  100  is running the new thread at the supervisor privilege level. However, the predicting units  109  continue to make static predictions that do not require use of the prediction histories  132 . In one embodiment, the control unit  124  may suspend accumulating prediction history  132  and making predictions with respect to some of the predicting units  109  but may not suspend the accumulating and making predictions for others. Furthermore, the decision regarding which predicting units  109  to suspend and which not to suspend may be dynamic as the microprocessor  100  operates. For example, the subsets of suspending and non-suspending predicting unit  109  may be programmable, such as by the operating system or BIOS. For another example, the subsets may be configurable via fuses that may be blown during manufacturing of the microprocessor  100  or in the field, either by a user or by service personnel. For another example, the subsets may be determined based on the particular ring-0 thread that will run, such as described below with respect to the embodiment of  FIG. 3 . Flow proceeds to block  232 . 
     At block  232 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a user privilege level, e.g., ring 3. The event also causes the microprocessor  100  to transfer control to a different thread than the currently running thread. Examples of the event include, but are not limited to, execution of an instruction, such as a system call return instruction (e.g., x86 SYSEXIT/SYSRET instruction), a return from interrupt or exception (e.g., x86 IRET instruction), or inter-privilege level return from procedure instruction (e.g., x86 RETF instruction). In one embodiment, the event causes the microprocessor  100  to transfer control to the microcode, which performs various operations before transferring control to the ring-3 process. Flow proceeds to block  242 . 
     At block  242 , the predicting units  109  resume accumulating their respective prediction histories  132  and making dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions. Flow ends at block  242 . 
     As may be observed, if the ring-3 process to which control is returned at block  242  is the same ring-3 process that was interrupted by the event at block  212 , then the prediction histories  132  should be the same as they were prior to the ring-0 transition, i.e., what they were when the ring-3 process was interrupted, since they are not being polluted by the ring-0 thread. Therefore, it is highly likely that the predicting units  109  will advantageously continue to make as accurate dynamic predictions for the threads of the ring-3 process after the event as before. It is also likely that the prediction performance when executing the ring-0 thread will be less than the prediction performance when executing the ring-3 process since only static prediction will be used for the ring-0 thread predictions. However, depending upon the characteristics of the ring-0 thread and/or ring-3 process, it may be advantageous to sacrifice performance when executing the ring-0 thread in hopes that the ring-3 performance improvement—due to less or no pollution of the ring-3 process prediction history—will dominate the loss in ring-0 performance, particularly if the ring-0 thread is short and/or infrequently run. 
     Referring now to  FIG. 3 , a flowchart illustrating operation of the microprocessor  100  of  FIG. 1  according to an alternate embodiment is shown. Several blocks of  FIG. 3  are the same as blocks of  FIG. 2  and are identically numbered. Preferably, at reset, the control unit  124  initializes the optimization information  112  data structure described in more detail below. Flow begins at block  202 . 
     At block  202 , while a thread operating at a user privilege level, e.g., ring-3, each of the predicting units  109  accumulates its respective prediction history  132  and makes dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions. Flow proceeds to block  212 . 
     At block  212 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a supervisor privilege level, e.g., ring-0, and causes the microprocessor  100  to transfer control to a different thread than the currently running thread. Flow proceeds to block  311 . 
     At block  311 , the control unit  124  attempts to identify the thread that will run at ring-0 and generates an identifier for the ring-0 thread. In one embodiment, the optimization information  112  data structure described below comprises a table kept by the control unit  124  in a private memory of the microprocessor  100 . Each entry in the table is associated with a different ring-0 thread identifier. The function employed to generate the ring-0 thread identifier may receive various inputs such as the event type and state values of the microprocessor  100  when the thread transition is detected. The event type may be one of the various event types described above with respect to block  212  of  FIG. 2 , but is not limited to those examples. The state values may be general purpose register values, model specific register values, the instruction pointer (IP) or program counter (PC) value of the ring-3 process that made a system call, software interrupt, inter-privilege or task switch procedure call, and the interrupt vector number associated with the interrupt or exception, but is not limited to these examples. The state value inputs may vary depending upon the event type. For example, it has been observed that when ring-3 processes make a system call (e.g., via the x86 SYSENTER instruction) to the Microsoft® Windows® operating system, Windows runs different threads depending upon the value in the x86 EAX register and, in some instances, the value of other registers. Hence, in one embodiment, when the event type is a system call instruction, the control unit  124  examines the value of the EAX register and generates different ring-0 identifiers for the different EAX values. Other embodiments are contemplated for other operating systems. For another example, the control unit  124  may generate different ring-0 identifier values for the different interrupt vector values. Flow proceeds to block  313 . 
     At block  313 , the control unit  124  looks up the ring-0 identifier generated at block  311  in the optimization information  112  data structure to obtain the optimization information  112  associated with the ring-0 thread identified by the ring-0 identifier. In one embodiment, if the ring-0 identifier is not present in the optimization information  112  data structure, the control unit  124  performs the default ring-0 entry action (i.e., the default action associated with entry into ring-0 with respect to whether or not to accumulate prediction history  132  and makes dynamic predictions using the prediction history  132 ) and allocates an entry in the optimization information  112  data structure for the ring-0 identifier. In one embodiment, the default ring-0 entry action is to suspend accumulating prediction histories  132  and using them to make predictions. If the ring-0 identifier is present, the control unit  124  decides whether to override the default ring-0 entry action based on the associated optimization information  112 . In one embodiment, the optimization information  112  comprises a length associated with the ring-0 thread and the control unit  124  decides to suspend accumulating and using the prediction histories  132  if the length of the ring-0 thread is less than a predetermined length, and otherwise to continue accumulating and using the prediction histories  132 . In one embodiment, the length is represented as the number of instructions retired during a previous run of the ring-0 thread, which is obtained using the retired instruction counter  113 . In one embodiment, the optimization information  112  comprises information about the effectiveness of the predictions made based on the prediction histories  132  during a previous execution instance of the ring-0 thread and/or during a previous run of the ring-3 process subsequent to the previous execution instance of the ring-0 thread. In one embodiment, the effectiveness is obtained using the performance counters  114 . Flow proceeds to decision block  315 . 
     At decision block  315 , the control unit  124  decides whether to suspend accumulating the prediction histories  132  and using them to make predictions. If so, flow proceeds to block  222 ; otherwise, flow proceeds to block  321 . Although embodiments are described in which the decision whether or not to accumulate prediction history  132  and make dynamic predictions using the prediction history  132  is made based on the optimization information  112  associated with a thread identifier, the decision may be made by criteria. For example, the control unit  124  may make the decision based on the identity, or characteristics, of the new thread (using any combination of the various inputs described) to which the running transition is made without reference to the optimization information  112 . That is, the characteristics of the new thread (e.g., event type and/or architectural state associated with the transition to the new thread; privilege level, as described with respect to  FIG. 2 , for example; or whether the new thread is an interrupt handler) may be sufficient to base the decision whether or not to accumulate prediction history  132  and make dynamic predictions using it, i.e., whether to selectively suspend accumulating the prediction history  132  and making dynamic predictions using it. Generally speaking, the approach is to suspend accumulating the prediction history  132  and making dynamic predictions using it for threads that are significantly short and/or infrequently run since it is likely that running threads with those characteristics with poorer prediction accuracy in exchange for not polluting the prediction histories  132  of other significantly long and/or frequently run threads will result in higher prediction accuracy for the other threads and overall higher performance of the microprocessor  100 . 
     At block  222 , in response to the event detected at block  212 , the control unit  124  controls the predicting units  109  to suspend accumulating their respective prediction histories  132  and making predictions using the prediction history while the microprocessor  100  is running at the supervisor privilege level. However, the predicting units  109  continue to make static predictions that do not require use of the prediction histories  132 . Flow proceeds to block  321 . 
     At block  321 , while the ring-0 thread is running, the control unit  124  continuously gathers optimization information about the ring-0 thread, such as prediction effectiveness via the performance counters  114  and thread length from the retired instruction counter  113 . In one embodiment, the control unit  124  gathers prediction effectiveness regarding static predictions in addition to dynamic predictions made by the predicting units  109 . In one embodiment, the control unit  124  also gathers prediction effectiveness information for ring-3 threads. Preferably, if the performance of the statically-predicted thread is acceptable, then the control unit  124  may continue to suspend prediction history accumulation and use when the thread is running, particularly if the performance of other threads is significantly improved; otherwise, the control unit  124  may accumulate and use the prediction history when the thread is running Flow proceeds to block  232 . 
     At block  232 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a user privilege level, e.g., ring 3, and to transfer control to a different thread than the currently running thread. Flow proceeds to block  333 . 
     At block  333 , the control unit  124  uses the optimization information gathered at block  321  to update the optimization information  112  data structure entry associated with the ring-0 thread. In one embodiment, the update comprises simply replacing the optimization information  112  in the entry with the newly gathered optimization information. In other embodiments, the update involves making calculations using the gathered optimization information and updating the optimization information  112  using the calculations. For example, the control unit  124  may calculate an average of the number of retired instructions and/or prediction effectiveness based on the last N executions of the ring-0 thread. Furthermore, the average may be a weighted or rolling average. Additionally, the control unit  124  may filter out extreme values for exclusion from the optimization information  112 . Furthermore, various ways of maintaining the optimization information  112  data structure are contemplated. For example, in one embodiment, the control unit  124  only keeps entries in the optimization information  112  data structure for ring-0 threads for which the control unit  124  wants to override the default ring-0 entry action; that is, if the control unit  124  looks up the ring-0 thread identifier at block  313  and finds it in the optimization information  112  data structure, then the control unit  124  decides at decision block  315  to override the default action. Flow proceeds to decision block  335 . 
     At decision block  335 , the control unit  124  determines whether accumulating and using the prediction histories  132  was suspended at block  222 . If so, flow proceeds to block  242 ; otherwise, the predicting units  109  have been accumulating and continue to accumulate prediction histories  132  and use them to make predictions, and flow ends. 
     At block  242 , the predicting units  109  resume accumulating their respective prediction histories  132  and making dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions. Flow ends at block  242 . 
     Referring now to  FIG. 4 , a flowchart illustrating operation of the microprocessor  100  of  FIG. 1  according to an alternate embodiment is shown. Several blocks of  FIG. 4  are the same as blocks of  FIG. 2  and are identically numbered. Flow begins at block  202 . 
     At block  202 , while a thread operating at a user privilege level, e.g., ring-3, each of the predicting units  109  accumulates its respective prediction history  132  and makes dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions. Flow proceeds to block  212 . 
     At block  212 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a supervisor privilege level, e.g., ring-0, and causes the microprocessor  100  to transfer control to a different thread than the currently running thread. Flow proceeds to block  222 . 
     At block  222 , in response to the event detected at block  212 , the control unit  124  controls the predicting units  109  to suspend accumulating their respective prediction histories  132  and making predictions using the prediction history while the microprocessor  100  is running the new thread at the supervisor privilege level. However, the predicting units  109  continue to make static predictions that do not require use of the prediction histories  132 . Flow proceeds to block  413 . 
     At block  413 , the control unit  124  stores the current instance of the prediction histories  132  to the prediction history storage  108 . In one embodiment, the control unit  124  saves only a portion of a given prediction history  132  in order to reduce the amount of time required to perform the save. For example, if the prediction history  132 A of the branch prediction unit  102  is relatively large (e.g., 8 KB), the control unit  124  may save only the most recently accessed entries (e.g., 512 bytes) rather than the entire prediction history  132 A. In one embodiment, the control unit  124  invalidates the unsaved portions of the prediction histories  132 . Furthermore, in one embodiment, the control unit  124  saves the prediction history  132  for only some of the predicting units  109 , but not all of them. For example, if it is determined that the prediction effectiveness of a first subset of the predicting units  109  is much more greatly adversely affected when interrupted by a ring-0 thread than a second subset of the predicting units  109 , then the control unit  124  may save the prediction histories  132  of the first subset but not the second. Preferably, the control unit  124  maintains multiple entries in the prediction history storage  108  each associated with a different ring-3 process identified by a unique ring-3 identifier. In one embodiment, the ring-3 process is identified by its x86 process-context identifier (PCID), such as described in section 4.10, on pages 4-46 through 4-62 of Volume 3A of the Intel 64 and IA-32 Architectures Software Developer&#39;s Manual mentioned above. In another embodiment, the ring-3 process is identified by the address of the page directory used by the ring-3 process, which is loaded into the x86 CR3 control register. In one embodiment, the control unit  124  maintains the prediction history storage  108  as a first-in-first-out buffer. In another embodiment, the control unit  124  employs a more sophisticated replacement policy, such as least-recently-used or least-frequently-used. Preferably, the saving of the prediction histories  132  to the prediction history storage  108  is performed while the functional units of the microprocessor  100  continue to process instructions of the ring-0 thread, and the ring-0 thread execution time is likely to be longer than the prediction history save time. However, advantageously, there is no contention for access to the read and write ports of the storage arrays that store the prediction histories  132  between the prediction history saving and the ring-0 instruction processing since the prediction history  132  arrays are not being accessed (i.e., written) to accumulate prediction history or make predictions (i.e., read) to process the ring-0 instructions but only are being read to save the prediction history. This is advantageous because the amount of additional hardware needed to accommodate the saving of the prediction history is minimized because there is no need to include additional read ports on the storage arrays for that purpose. Flow proceeds to block  232 . 
     At block  232 , the control unit  124  detects an event that instructs the microprocessor  100  to operate at a user privilege level, e.g., ring 3, and to transfer control to a different thread than the currently running thread. Flow proceeds to block  433 . 
     At decision block  433 , the control unit  124  determines whether the new ring-3 thread to which control is being transitioned and the old ring-3 thread from which control was transitioned at block  212  are part of the same process. As discussed above with respect to block  413 , the control unit  124  may make this determination by comparing the process identifiers associated with the two threads, such as the x86 PCID. If the new ring-3 thread process is different from the old ring-3 thread process, flow proceeds to block  435 ; otherwise, flow proceeds to block  242 . 
     At block  435 , the control unit  124  restores the prediction histories  132  for the new ring-3 process from the prediction history storage  108 . That is, the control unit  124  uses the new ring-3 process identifier to find its prediction histories in the prediction history storage  108  and loads the prediction histories  132  of the predicting units  109  from the prediction history storage  108  based on the ring-3 process identifier. Preferably, the restoring of the prediction histories  132  from the prediction history storage  108  is performed while the functional units of the microprocessor  100  continue to process instructions of the microcode that performs the transition from ring 0 to ring 3. The execution time of the microcode may be a significant number of clock cycles and may be longer than the time required to perform the restore of the prediction histories  132 , which may be advantageous since there may be little or no contention for access to the read and write ports of the prediction history  132  storage arrays between the ring transition microcode and the prediction history restoring since many of the prediction history  132  arrays are not being accessed (i.e., written) to accumulate prediction history or make predictions (i.e., read) to process the ring-0 instructions but only to restore the prediction history. For example, in one embodiment, the microcode unit does not employ the branch prediction unit  102 , i.e., the branch prediction unit  102  does not make predictions for microcode instructions. For another example, in one embodiment, the ring transition microcode does not access system memory; therefore, the data prefetch unit  104  does not need to make data prefetches for the ring transition microcode and the store collision prediction unit  106  does not need to make predictions for the ring transition microcode. This is advantageous because the amount of additional hardware needed to accommodate the restoring of the prediction history is minimized because there is no need to include additional write ports on the storage arrays for that purpose. Flow proceeds to block  242 . 
     At block  242 , the predicting units  109  resume accumulating their respective prediction histories  132  and making dynamic predictions using the prediction history  132  as the microprocessor  100  is processing instructions. Flow ends at block  242 . 
     Advantageously, the processing of instructions of the new ring-3 thread is not polluting the prediction histories  132  associated with the old ring-3 thread, which may result in greater prediction accuracy for both ring-3 threads. 
     Other embodiments are contemplated in which the embodiments of  FIG. 3  and  FIG. 4  are effectively combined such that the control unit  124  saves and restores the prediction histories  132  associated with ring-0 threads for which the control unit  124  decides not to suspend accumulating and using the prediction histories  132 , e.g., for relatively long ring-0 threads and/or for ring-0 threads that merit accumulating and using the prediction histories  132  based on the effectiveness of the predictions made during previous execution instances of the ring-0 thread and/or the ring-3 process. As noted above, the time required for the microprocessor  100  to transition from ring 3 to ring 0 and vice versa may be a substantial number of clock cycles during which there is no need to accumulate the prediction histories  132  nor to make predictions using them; therefore, during this time the control unit  124  may save/restore the relevant prediction histories  132  to/from the prediction history storage  108  effectively without significant, if any, performance penalty. In such embodiments it may be particularly advantageous to limit the amount of prediction history  132  saved and restored to an amount that may be saved and restored during the ring 0 to ring 3 and ring 3 to ring 0 transitions in order to be able to avoid stopping instruction execution by the microprocessor  100  until the save and restore is complete. 
     Additionally, although embodiments are described in which the microprocessor  100  selectively suspends accumulation of the prediction history and its use to make predictions in response to thread transitions from one privilege level to a different privilege level, other embodiments are contemplated in which the microprocessor  100  selectively suspends or resumes accumulation of the prediction history and its use to make predictions in response to thread transitions within the same privilege level. For example, the microprocessor  100  may detect a thread transition by detecting an event that does not involve a privilege level change and decide to suspend or resume accumulation of the prediction history and it use to make predictions in response. For example, the microprocessor  100  may simply detect the execution of an instruction (such as a subroutine call or return instruction) at a particular IP value, and in some instances with a particular value of other architectural state, such as general purpose register values. For another example, the microprocessor  100  may detect a sequence of instructions and/or IP values. 
     Fractional Use of Prediction History Storage for OS Routines 
     Referring now to  FIG. 5 , a block diagram illustrating a control information table  500  is shown. The control information table  500  is an embodiment of the storage for holding optimization information  112  of  FIG. 1 . The table  500  includes a plurality of entries each holding an operating system (OS) routine identifier  502  and associated control information  504 . The OS routine identifier  502  may include various information such as described above with respect to the optimization information  112 , such as state values (e.g., the IP of the OS routine and general purpose register values when an x86 SYSCALL instruction is executed), that enable the control unit  124  to identify an OS routine when it begins to run. The control information  504  specifies a fraction, among other things. The prediction history  132  storage comprises portions that separately controllable to accumulate the prediction history. That is, the control unit  124  may control the predicting units  109  to use only a fraction of the portions of the prediction history storage  132  to accumulate prediction history while an OS routine is running, and the fraction may vary based on the OS routine that is running. For example, the prediction history storage  132  may be arranged by ways (e.g., see  FIG. 6 ); or the prediction history storage  132  may be arranged by sets (e.g., see  FIG. 7 ); or the prediction history storage  132  may be arranged as a queue of entries (e.g., see  FIG. 8 ). In each of these cases, the ways/sets/entries in the prediction history storage  132  may be separately controllable to accumulate prediction history, and the fraction in the control information  504  associated with an OS routine specifies of the fraction of the prediction history  132  storage to be used to accumulate prediction history while the associated OS routine is running, as described in more detail below. Preferably, the control information  504  specifies a fraction for the prediction history  132  storage of each of the predicting units  109  of the microprocessor  100 . 
     In one embodiment, the information in the table  500  is determined prior to manufacture of the microprocessor  100  and manufactured therein, e.g., into the microcode of the microprocessor  100 . The microcode may be field-upgradeable by a microcode patch, such as may be accomplished by the BIOS of the system that comprises the microprocessor  100 . Additionally, a device driver for the microprocessor  100  may download the information  500  to the microprocessor  100  during operation of the system. In one embodiment, the device driver detects that a predetermined software application is running and in response downloads the information  500  to the microprocessor  100 , which advantageously enables the fractions in the information  500  to be tailored with finer granularity for optimizing the performance of software applications of particular interest. 
     Referring now to  FIG. 6 , a block diagram illustrating a prediction history cache  600  is shown. The prediction history cache  600  comprises a cache memory arranged an associative cache having a plurality of ways  602 . The embodiment of  FIG. 6  includes eight ways  602 ; however, other embodiments with different numbers of ways are contemplated. The ways  602  are storage for holding prediction history  132 . As an example, each entry in the ways  602  of the prediction history cache  600  may hold prediction history used to perform branch prediction (e.g., branch target cache data) or data prefetching, as described above. Advantageously, the ways  602  are separately controllable to accumulate the prediction history  132 . For example, when an OS routine identified by one of the OS identifiers  502  in the table  500  of  FIG. 5  is detected as running, the prediction history cache  600  receives the fraction from the control information  504  associated with the running OS routine and allows only N ways  602  to be used to accumulate prediction history  132 , in which N is the numerator of the fraction and the denominator of the fraction is the total number of ways  602  in the prediction history cache  600 . For example, the control unit  124  may allow only two ways  602  of the eight total ways  602  of the prediction history cache  600  to be used to accumulate the prediction history  132  while the associated OS routine is running. In one embodiment, the allowable ways  602  (e.g., ways  4  and  5  only) are specified in the control information  504 . Although not shown, it should be understood that, in addition to the arrangement by ways  602 , the prediction history cache  600  of  FIG. 6  may also be arranged as a plurality of sets that are indexed by an index input, similar to the manner described below with respect to  FIG. 7 . 
     Referring now to  FIG. 7 , a block diagram illustrating a prediction history cache  700  according to an alternate embodiment is shown. The prediction history cache  700  comprises a cache memory arranged an indexed cache having a plurality of sets  702  that are indexed by an index input  704  (e.g., memory address of an instruction or a load/store address) to select one of the sets  702 . The embodiment of  FIG. 7  includes eight sets  702 ; however, other embodiments with different numbers of sets are contemplated. The sets  702  are storage for holding prediction history  132 . As an example, each entry in the sets  702  of the prediction history cache  700  may hold prediction history used to perform branch prediction or data prefetching, as described above. Advantageously, the sets  702  are separately controllable to accumulate the prediction history  132 . For example, when an OS routine identified by one of the OS identifiers  502  in the table  500  of  FIG. 5  is detected as running, the prediction history cache  700  receives the fraction from the control information  504  associated with the running OS routine and allows only N sets  702  to be used to accumulate prediction history  132 , in which N is the numerator of the fraction and the denominator of the fraction is the total number of sets  702  in the prediction history cache  700 . For example, the control unit  124  may allow only two sets  702  of the eight total sets  702  of the prediction history cache  700  to be used to accumulate the prediction history  132  while the associated OS routine is running. In one embodiment, the allowable sets  702  (e.g., sets 0 and 1 only) are specified in the control information  504 . For example, the control unit  124  may control the prediction history cache  700  to modify upper bits of the index  704  to a predetermined value to limit the particular sets  702  that are used to accumulate the prediction history  132  when the OS routine is running. For example, assuming 64 sets  702  (an index  704  of six bits), the control unit  124  could control the prediction history cache  700  to use only sets 0 and 1 to accumulate prediction history for the associated OS routine by modifying the upper seven bits of the index  704  to zero. Although not shown, it should be understood that, in addition to the arrangement by sets  702 , the prediction history cache  700  of  FIG. 7  may also be arranged as a plurality of ways, similar to the manner described above with respect to  FIG. 6 . 
     Referring now to  FIG. 8 , a block diagram illustrating a prediction history queue  800  is shown. The prediction history queue  800  comprises storage for holding prediction history  132 . The storage is arranged as a queue. The queue storage  800  comprises prediction history queue entries  802  each having an associated OS flag  804 . The OS flag  804  indicates whether the entry  802  is associated with an OS routine or with a user routine. As an example, each prediction history queue entry  802  may hold prediction history used to perform memory disambiguation, e.g., store collision detection, as described above. For example, the entry  802  may hold a store address; information about the sources of a store instruction used to calculate its store address; the IP value of a previously store-colliding load instruction; a delta between a reorder buffer index of a load instruction that was replayed because it received incorrect data because its load address collided with an older store instruction whose address had not yet been generated and the colliding store instruction; and reorder buffer indices, such as the index of a store instruction, or the index of an instruction upon which a store instruction depends for its store data, the index of the most recent instance of a load instruction that was replayed because it received incorrect data because its load address collided with an older store instruction whose store data was not available when the load instruction was executed. Examples of prediction history queues  800  that store similar information are described in more detail with respect to U.S. Non-Provisional application Ser. No. 12/604,767 filed on Oct. 23, 2009 and claiming priority to U.S. Provisional Application 61/182,283 filed on May 29, 2009, each of which is incorporated by reference herein in its entirety. 
     In one embodiment, the prediction history queue  800  includes a counter that keeps track of the number of valid entries  802  that are currently associated with an OS routine, e.g., that have their OS flag  804  set. When an OS routine identified by one of the OS identifiers  502  in the table  500  of  FIG. 5  is detected as running, the prediction history queue  800  receives the fraction from the control information  504  associated with the running OS routine and allows only N entries  802  to be occupied by OS routines, in which N is the numerator of the fraction and the denominator of the fraction is the total number of entries  802  in the queue  800 . In one embodiment, the queue  800  evicts the oldest of the N OS-routine entries  802  when pushing the new entry  802 . In one embodiment, the queue  800  maintains least-recently-used (LRU) information and evicts the least recently used of the N OS-routine entries  802  when pushing the new entry  802 . In one embodiment, if the prediction history queue  800  is not full when an OS-routine entry wants to push into the queue  800 , then the queue  800  allows it to push without evicting another OS entry, i.e., in this case, the queue  800  temporarily allows more than N OS entries to be present. Preferably, N is dynamically configurable. 
     Referring now to  FIG. 9 , a flowchart illustrating a process for generating values with which to populate the table  500  of  FIG. 5  is shown. Flow begins at block  902 . 
     At block  902 , various software applications (e.g., popular or critical software applications, benchmarks, etc.) are profiled to identify different operating system routines called by the software applications. The software applications may be profiled on different operating systems, such as the Microsoft® Windows®, Linux®, Apple Mac OS X®, and Google® Android™ operating systems, each having its own set of OS routines that may be called by the software applications. Flow proceeds to block  904 . 
     At block  904 , for each of the OS routines identified at block  902 , the number of instructions executed by the OS routine each time it is called is counted. Then the total number of executed instructions is computed for OS routines, and the average number of executed instructions is computed as the total divided by the number of times the OS routine was called. In one embodiment, the average and total number of instructions is computed on a per application basis in addition to on a per operating system basis. In an alternate embodiment, the average and total number of clock cycles of the microprocessor  100  spent in the OS routine is calculated rather than number of instructions executed. Flow proceeds to block  906 . 
     At block  906 , for each of the OS routines identified at block  902 , the OS routine is classified as being in one of three categories. The first category is classified as having a relatively small number of instructions executed by the OS routine, the second category is classified as having a moderate number of instructions executed by the OS routine, and the third category is classified as having a relatively large number of instructions executed by the OS routine. Intuitively, an OS routine in the first category is unlikely to significantly pollute the prediction history  132  associated with the user code (i.e., the instructions of the software application) that calls the OS routine and thereby negatively impact the performance of the user code by reducing the accuracy of the predictions of the user code instructions. Conversely, an OS routine in the third category is likely to significantly benefit from the prediction of its instructions based on accumulation of its prediction history. Stated alternatively, an OS routine in the third category is likely to significantly negatively impact the performance of the software application whose user code calls it since the performance of the software application depends, at least in part, upon the performance of the OS routines that it calls, and OS routines that execute a large number of instructions are likely to run slowly if they do not have the benefit of the prediction of their instructions based on their prediction history. Finally, an OS routine in the second category is likely to pollute the user code prediction history enough to negatively impact its performance; however, it is unclear whether this negative effect is offset by the increased performance of the OS routine. Stated alternatively, by accumulating the prediction history of OS routines in the second category using only a fraction of the storage of the predicting units  109 , overall performance of the software applications may be improved. Preferably, both the average number of executed instructions and the total number of executed instructions is analyzed to perform the classification. This is because even if an OS routine is relatively short (i.e., would fall into the first category if only looking at average number of instructions), if it is called relatively frequently, it may need to be analyzed per block  908  because it may be important for it to run fast (i.e., benefit from prediction history accumulation); however, it may be so short that it cannot significantly benefit from the prediction history accumulation. Advantageously, by selecting a subset of the OS routines into the second category, the amount of performance analysis that must be performed at block  908  may be greatly reduced. Flow proceeds to block  908 . 
     At block  908 , performance analysis of the software applications is conducted by varying the fractions of the predicting units  109  prediction history storage (e.g.,  600 ,  700  and  800  of  FIGS. 6, 7 and 8 ) used to accumulate the prediction history for each of the OS routines selected into the second category at block  906  to determine the optimal fraction values. That is, the table  500  of  FIG. 5  is loaded with OS routine identifiers  502  associated with the relevant OS routines and different permutations of values of the control information  504  are tried to determine which combinations yield the best performance for individual software applications as well as for the software applications as a whole across a given operating system. The performance-optimized combinations of fraction values are retained so that they may be loaded into the table  500  of  FIG. 5  for use by the microprocessor  100 . The performance-optimized fraction values may be manufactured into the microprocessor  100  and/or a device driver may download the values into the microprocessor  100 , as described below with respect to  FIGS. 10 and 11 . 
     Referring now to  FIG. 10 , a flowchart illustrating operation of a system that includes the microprocessor  100  of  FIG. 1  is shown. Flow begins at block  1002 . 
     At block  1002 , an operating system for whose OS routines analysis has been performed such as according to  FIG. 9 , referred to herein as OS Y, is loaded onto a system that includes the microprocessor  100 . Flow proceeds to block  1004 . 
     At block  1004 , the operating system loaded at block  1002  begins to call the initialization routines of its device drivers and calls the initialization routine for a device driver for the microprocessor  100 . The microprocessor  100  device driver initialization routine downloads values determined at block  908  of  FIG. 9  to the microprocessor  100  for populating the table  500  of  FIG. 5  so that software applications running on the microprocessor  100  may benefit from the fractional use of the prediction history  132  storage to accumulate prediction history while running selected OS routines and hopefully realize increased performance. In one embodiment, the device driver downloads the values by executing x86 WRMSR instructions addressed to an MSR associated with the prediction history fractional use feature, or by a similar model specific register-writing instruction of other instruction set architectures. Flow ends at block  1004 . 
     Referring now to  FIG. 11 , a flowchart illustrating operation of a system that includes the microprocessor  100  of  FIG. 1  is shown. Flow begins at block  1102 . 
     At block  1102 , a device driver for the microprocessor  100  detects that the operating system has scheduled a software application, referred to herein as software application X, to run on a system that includes the microprocessor  100 . The operating system has had its routines analyzed according to  FIG. 9 , for example. Flow proceeds to block  1104 . 
     At block  1104 , the device driver responsively downloads values determined at block  908  of  FIG. 9  to the microprocessor  100  for populating the table  500  of  FIG. 5  so that the software applications running on the microprocessor  100  may benefit from the fractional use of the prediction history  132  storage to accumulate prediction history while running selected OS routines and hopefully realize increased performance. Flow ends at block  1104 . 
     While various embodiments of the present invention have been described herein, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant computer arts that various changes in form and detail can be made therein without departing from the scope of the invention. For example, software can enable, for example, the function, fabrication, modeling, simulation, description and/or testing of the apparatus and methods described herein. This can be accomplished through the use of general programming languages (e.g., C, C++), hardware description languages (HDL) including Verilog HDL, VHDL, and so on, or other available programs. Such software can be disposed in any known computer usable medium such as magnetic tape, semiconductor, magnetic disk, or optical disc (e.g., CD-ROM, DVD-ROM, etc.), a network, wire line, wireless or other communications medium. Embodiments of the apparatus and method described herein may be included in a semiconductor intellectual property core, such as a microprocessor core (e.g., embodied, or specified, in a HDL) and transformed to hardware in the production of integrated circuits. Additionally, the apparatus and methods described herein may be embodied as a combination of hardware and software. Thus, the present invention should not be limited by any of the exemplary embodiments described herein, but should be defined only in accordance with the following claims and their equivalents. Specifically, the present invention may be implemented within a microprocessor device that may be used in a general-purpose computer. Finally, those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiments as a basis for designing or modifying other structures for carrying out the same purposes of the present invention without departing from the scope of the invention as defined by the appended claims.