Patent Publication Number: US-7587584-B2

Title: Mechanism to exploit synchronization overhead to improve multithreaded performance

Description:
RELATED APPLICATIONS 
     This application is a continuation-in-part of application Ser. No. 10/370,251, filed Feb. 19, 2003, now U.S. Pat. No. 7,487,502. 
    
    
     BACKGROUND 
     1. Field 
     The present disclosure pertains to the field of processing apparatuses and systems that process sequences of instructions or the like, as well as certain instruction sequences to program such apparatuses and/or systems. Some embodiments relate to monitoring and/or responding to conditions or events within execution resources of such processing apparatuses. 
     2. Description of Related Art 
     Various mechanisms are presently used to change the flow of control (i.e., the processing path or instruction sequence being followed) in a processing system. For example, a jump instruction in a program sequence explicitly and precisely causes a jump to a new address. The jump instruction is an example of an explicit change of the control flow because the instruction directs the processor to jump to a location and continue executing at that point. A traditional jump instruction is “precise” (or synchronous) because the jump occurs as a direct result of execution of the jump instruction. 
     Another traditional example of a change in the flow of control is an interrupt. An interrupt may be an external signal provided to an apparatus such as a processor. The processor may respond by jumping to an interrupt handler, a routine that handles the event(s) signaled by a particular interrupt. Interrupts are typically also relatively precise in that they are recognized and acted upon by a processor within a particular window of time in relation to their receipt. In particular, interrupts are often serviced at the next instruction boundary after they are received internally. In some cases, only the operating system or other software operating at a high privilege level is allowed to mask interrupts, so a user program may have no opportunity to enable or disable these control flow changing events. 
     Another traditional example of a change in the flow of control occurs in response to an exception. An exception typically reflects a predefined architectural condition such as a result of a mathematical instruction meeting certain criteria (denormal, underflow, overflow, not a number, etc.). Some exceptions can be masked, for example, by setting a bit in a control register. If an exception occurs and is not masked, then an exception handler is called to handle the exception. 
     Another technique that changes the flow of control of a processor is the use of breakpoints. Breakpoints are typically used in debugging. A particular instruction address may be programmed into a breakpoint register. The processor may do various acts (other than continue with the program as usual) when a breakpoint is active and the target address is reached. Breakpoints allow single-stepping through a program, among other things. 
     Multi-threading is a technique by which processor hardware may be utilized by multiple different threads. Multi-threaded processors may switch between threads for a variety of reasons. For example, a processor may have an algorithm that automatically switches between available threads. Other processors use switch-on-event multithreading (SoEMT), whereby certain events such as a cache miss may give rise to a thread switch. Thread switching can be considered a change of control flow because the processor switches the instruction sequence or stream which it executes. 
     In one prior art reference, a quiesce instruction is detailed (see U.S. Pat. No. 6,493,741). In one example, the quiesce instruction stops processing in one thread until either a timer expires or a memory write to a memory location occurs. Therefore, an instruction such as the quiesce instruction may itself trigger the temporary cessation of processing of the thread containing the quiesce instruction and a switch to another thread. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
       The present invention is illustrated by way of example and not limitation in the Figures of the accompanying drawings. 
         FIG. 1  illustrates one embodiment of a system that can detect and respond to processing conditions of execution resources. 
         FIG. 2  illustrates a flow diagram of operations for one embodiment of the system of  FIG. 1 . 
         FIG. 3  illustrates a flow diagram of operations for another embodiment of the system of  FIG. 1 . 
         FIG. 4  illustrates another embodiment of a system that can respond to multiple different performance events and/or to composite performance events. 
         FIG. 5   a  illustrates one embodiment of a monitor that may recognize composite events. 
         FIG. 5   b  illustrates another embodiment of a monitor. 
         FIG. 5   c  illustrates another embodiment of a monitor. 
         FIG. 6  illustrates a flow diagram for execution of a user program that activates helper threads in response to program-definable triggers according to one embodiment. 
         FIG. 7  illustrates a flow diagram for a process of refining monitor settings according to one embodiment. 
         FIG. 8  illustrates a flow diagram for a process of updating software according to one embodiment. 
         FIG. 9   a  illustrates a flow diagram in which multiple nested helper threads are activated to assist processing of a program. 
         FIG. 9   b  illustrates thread switching logic for one embodiment which supports virtual threads. 
         FIG. 10   a  illustrates one embodiment of a context-sensitive event schema vector and mask implementation. 
         FIG. 10   b  illustrates one embodiment of a context-sensitive event schema vector and mask implementation. 
         FIG. 11  illustrates one embodiment of a multithreaded processor which performs thread switching based on monitor events. 
         FIG. 12  illustrates one embodiment of a system having event detection and handling capabilities pertaining to synchronization objects. 
         FIG. 13  illustrates a flow diagram for synchronization event handling according to several embodiments. 
         FIG. 14  illustrates a flow diagram of thread scheduling improvement based on lock profiling by an event handler thread. 
     
    
    
     DETAILED DESCRIPTION 
     The following description describes embodiments of a programmable event driven yield mechanism which may activate other threads. In the following description, numerous specific details such as processor types, microarchitectural conditions, events, enablement mechanisms, and the like are set forth in order to provide a more thorough understanding of the present invention. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. Additionally, some well known structures, circuits, and the like have not been shown in detail to avoid unnecessarily obscuring the present invention. 
     In some embodiments, disclosed techniques may allow a program to actively monitor and respond to conditions of the execution resources which execute the program while executing the program. Effectively, such embodiments may incorporate real-time execution resource operating condition feedback to improve performance. If the execution resources encounter execution delaying conditions, the program execution may be disrupted to make adjustments. In some embodiments, a handler may be activated and may spawn a helper thread to attempt to improve execution of the original thread. In other embodiments, the disruption may be accomplished by switching to another program thread that may not be a helper thread. These and other embodiments may in some cases advantageously improve processing throughput and/or allow optimizations to be tailored to particular hardware. 
     Turning to  FIG. 1 , one embodiment of a system that can detect and respond to processing conditions of execution resources is illustrated. In the embodiment of  FIG. 1 , execution resources  105 , a monitor  110 , and enable logic  120  form a portion of a processor  100  that is capable of executing instructions. The execution resources may include hardware resources that may be integrated into a single component or integrated circuit in some embodiments. However, the execution resources may include software or firmware resources or any combination of hardware and software and/or firmware that may also be used in execution of program instructions. For example, firmware may be used as a part of an abstraction layer or may add functions to processing hardware, as may software. Software also may be used to emulate part or all of an instruction set or to otherwise assist in processing. 
     The processor may be any of a variety of different types of processors that execute instructions. For example, the processor may be a general purpose processor such as a processor in the Pentium® Processor Family or the Itanium® Processor Family or other processor families from Intel Corporation or other processors from other companies. Thus, the processor may be a reduced instruction set computing (RISC) processor, a complex instruction set computing (CISC) processor, a very long instruction word (VLIW) processor, or any hybrid or alternative processor type. Moreover, special purpose processors such as network or communication processors, co-processors, embedded processors, compression engines, graphics processors, etc., may use disclosed techniques. As integration trends continue and processors become even more complex, the need to monitor and react to internal performance indicators may further increase, thus making presently disclosed techniques more desirable. However, due to rapid technological advance in this area of technology, it is difficult to foresee all the applications of disclosed technology, though they may be widespread for complex hardware that executes program sequences. 
     As shown in  FIG. 1 , the processor  100  is coupled to a storage medium  150  such as a memory. The storage medium  150  may be a memory subsystem having various levels of hierarchy which may include but are not limited to various levels of cache memory, system memory such as dynamic random access memory or the like, and non-volatile storage such as flash memory (e.g. memory stick etc.), a magnetic or optical disk. As illustrated, the storage medium stores a program  160  and a handler and/or other thread such as a helper thread  170 . 
     To allow the monitor to monitor the desired events, the monitor  110  may be coupled to various portions of execution resources in order to detect particular conditions or to be informed of certain microarchitectural events. Signal lines may be routed to the monitor  110 , or the monitor may be strategically placed with or integrated with relevant resources. The monitor may include various programmable logic or software or firmware elements or may be custom designed to detect a particular condition. The monitor tracks the various events or conditions, and if the events or conditions it is programmed to detect occur, then the execution resources  105  are signaled to disrupt the normal control flow the program would otherwise follow. As indicated in  FIG. 1 , the disruption may result in an event handler being called or a thread switch occurring. 
     One example of a specific detectable condition is that data may be missing from a cache memory, resulting in the event of a cache miss occurring. In fact, a program may generate a pattern of memory accesses that causes repeated cache misses, thereby degrading performance. Such an occurrence of a certain number of cache misses within a period of time or during execution of a portion of code is one example of an event that indicates a relatively low level of progress is being made in executing that section of code. 
     Other detectable events which may be low progress indicators may relate to various other microarchitectural or structural details of the execution resources. A monitor may detect a condition involving one or more of a stall of a resource, a cache event, a retirement event, a branch or branch prediction result, an exception, a bus event, or a variety of other commonly monitored or performance-impacting events or conditions. The monitor may count or otherwise time, quantify, or characterize such events or conditions, and may be programmable when a particular metric associated with one or more events or conditions occurs. 
       FIG. 2  illustrates a flow diagram of operations for one embodiment of the system of  FIG. 1 . As indicated in block  200  of  FIG. 2 , the program  160  may set conditions to cause a change in the execution control flow. For example, the enablement logic  120  may control both activation of the monitor and which event(s) to detect. Alternatively, the enablement logic  120  may enable and/or mask events, and the monitor  110  may itself also be programmable for further flexibility in specifying the events or conditions within the execution resources or system that are tracked. In either case, the program  160  itself may specify conditions that are to be watched during its own execution. The program  160  may also provide the handler or thread  170  which is activated when the monitored condition(s) occur. For example, the program may be a program which includes a main thread and a helper thread or helper routine that attempts to improve execution of the main thread if conditions the program specifies occur. 
     As indicated in block  205 , the program instructions are executed. Execution of the program causes the state of the execution resources to change. For example, a variety of conditions may occur or be present that inhibit forward progress in execution of the program. As indicated in block  210 , the various processing metrics and/or microarchitectural conditions may be monitored to determine if the triggering event programmed in block  200  occurs. If the triggering state does not occur in block  210 , the monitor is not triggered, and program execution continues by returning to block  205 . 
     In some cases, the triggering state bears only an indirect relationship to execution of any single instruction. For example, a prior art breakpoint detector typically causes a break when an instruction pointer reaches a designed address. Such breakpoints are precise because a particular instruction (i.e., its address) directly triggers the break. Also, the prior art quiesce instruction itself causes a thread to stop at least temporarily. In contrast, some embodiments utilizing disclosed techniques trigger control flow changes on a set of conditions that are not necessarily caused by a single instruction, but rather may be caused by the overall program flow and/or system environment. Thus, while the monitor may repeatedly trigger at the same instruction execution state in a single system, other conditions, environments, system, etc., may cause different trigger points for the same program. In this sense, disclosed techniques, in some cases, provide an imprecise or asynchronous mechanism generating a control flow change that is not directly tied to an instruction execution boundary. Moreover, such an imprecise mechanism may, in some embodiments, test for events at a less fine granularity than each instruction and/or may delay recognition of events for some period of time because architectural correctness does not depend on any processing-rate-enhancing helper routines executing at any particular point in time. 
     When the triggering state is detected by the monitor in block  210 , processing of the program is disrupted as indicated in block  215 . Generally, the system may responsively adjust because processing of the program is occurring inefficiently or in a manner other than the manner the programmer desired. For example, another software routine such as another program portion may be invoked. The other program portion may be another thread unrelated to the original thread or may be a helper thread that helps in the processing of instructions from the original thread, for example by prefetching data to reduce cache misses. Alternatively, a program-transparent (e.g., hardware) mechanism may perform some optimizations, reconfiguration (including, but not limited to reconfiguration of the monitor setup), reallocation of resources or the like to hopefully improve processing. 
     One example which invokes a helper thread is illustrated in  FIG. 3 . In particular, the flow diagram of  FIG. 3  details operations for one embodiment of the system of  FIG. 1  in which the execution resources are multithreaded resources and the program invokes a helper thread when a certain triggering condition occurs. Thus, as indicated in block  300 , a first thread (e.g., a main program) sets a monitor condition. The condition may be any one or more of the variety of conditions discussed herein. The first thread executes a code section as indicated in block  310 . If the triggering condition does not occur, as tested in block  320 , then the code section continues executing, as indicated in block  310 . 
     If the triggering condition does occur, then a helper thread is activated to assist the first thread as indicated in block  330 . The helper thread may be activated by a routine such as a handler routine or just be activated by a thread switch. For example, in one embodiment, the trigger condition signaled by the monitor to the execution resource may cause the execution resource to jump to an event handler that spawns a helper thread. In another embodiment, the helper thread may just be one of the other active threads. In yet another embodiment, one or more special helper thread execution slots may be provided by the processor and the monitor may cause a switch to a helper thread from one of these slots. As indicated in block  340 , both threads may then continue to execute. Hopefully, the helper thread runs ahead and clears up conditions that would otherwise cause the first thread to stall or perform poorly. 
       FIG. 4  illustrates another embodiment of a system that can respond to multiple different performance events and/or to composite performance events. In the embodiment of  FIG. 4 , execution resources  400  are shown as including a set of N monitors  410 - 1  through  410 -N. Additionally, an event schema vector (ESV) storage location  420  and an event schema vector mask (ESVM) storage location  425  are provided. The embodiment of  FIG. 4  shows a number of monitors (N) corresponding to the number of bits in the event schema vector and the event schema mask vector. In other embodiments, there may be different numbers of monitors and bits in these vectors, and the monitors may or may not correlate directly to the bits. For example, a condition involving multiple monitors may correlate to a single vector bit in some embodiments. 
     The execution resources  400  are optionally coupled to an event descriptor table  430  (EDT), which may be locally implemented on the processor or in a co-processor or system memory. Control flow logic  435  is coupled the monitors  410 - 1  through  410 -N and to receive values from the event schema vector and the event schema vector mask. The control flow logic  435  changes the control flow for processing logic when a condition detected by one or more of the monitors is enabled according to the event schema vector and event schema vector mask. 
     The embodiment of  FIG. 4  also illustrates decode logic  402  and a set of machine or model specific registers  404  (MSRs). Either or both of the decode logic  402  and the model specific registers may be used to program and/or activate the monitors and the event schema vector and mask. For example, MSRs may be used to program the types or number of events that trigger the monitors. MSRs may also be used to program the event schema vector and mask. Alternatively, one or more new dedicated instruction(s) to be decoded by the decoder  402  may be used for either or both of programming the monitors and the event schema vector and mask. For example, a yield instruction may be used to enable disruption of processing a program when a certain set of conditions occurs. Some or all of the conditions may be specified by an operand to the yield instruction or otherwise programmed in advance of its execution. Such a yield instruction may be decoded by the decoder  402  to trigger a microcode routine, to produce a corresponding micro-operation or micro-instruction, or sequences of micro-operations to directly signal appropriate logic, or activate a co-processor or to otherwise implement the yield functionality. The concept of yielding may appropriately describe the instruction in some embodiments in which one thread is allowed to continue after executing the yield instruction but may be slowed at some point by execution of another thread or handler. For example, a largely single-threaded program may invoke extra helper threads and share the processor with those extra helper threads. 
     In the embodiment of  FIG. 4 , a memory  440  includes event handlers  450  and a main thread  460 . In some embodiments, the event descriptor table may be stored in the same memory or in the same memory hierarchy as the main thread  460  and handlers  450 . As previously discussed, the handler(s) may spawn a helper thread to assist the main program in executing efficiently. 
     The memory  440  may also store an update module  442  to communicate via a communications interface  444 . The update module  442  may be a hardware module or a software routine executed by the execution resources to obtain new conditions to be programmed into various monitors and/or enablement logic. The update module  442  may also obtain new helper threads or routines. For example, these may be downloaded by a software program from the vendor of the software program to provide enhanced performance. Thus, the network interface  444  may be any network and/or communication interface that allows information transfer via a communication channel. In some cases, the network interface may interface to the Internet to download new conditions and/or helper routines or threads. 
     In one embodiment, each bit of the event schema vector indicates the occurrence or non-occurrence of a particular event, with the particular event possibly being a composite event reflective of (and/or expressed via Boolean operations in terms of) a variety of conditions or other events. Occurrence of the particular event may set the bit in the event schema vector. Each bit in the event schema vector may have a corresponding bit in the event schema mask vector. If the mask bit indicates that the particular event is masked, then the control flow logic  435  may disregard the event, although the bit in the event schema vector may remain set due to its occurrence. The user may choose whether to clear the event schema vector when unmasking events. Thus, an event may be masked for some time and handled later. In some embodiments, the user may choose to specify the trigger as a level trigger or an edge trigger, depending upon various issues such as the relationship between event update, sampling and reset (or the hold time of a trigger event in the ESV) 
     If the mask bit indicates that an event is unmasked, then the control flow logic  435  calls an event handler for that particular event in this embodiment. The control flow logic  435  may vector into the event descriptor table  430  based on the bit position in the event schema vector, and accordingly, the event descriptor table may have N entries corresponding to the N bits in the event schema vector. The event descriptor table may contain a handler address indicating an address to which the control flow logic  435  should re-direct execution, and may also include other information as may be useful in a particular embodiment. For example, privilege level, thread, process, and/or other information may be maintained or updated in the event descriptor table. 
     In another embodiment, the event descriptor table  430  may not be necessary or may be a single entry that indicates an address for a single event handler to handle all events. In this case, the entry may be stored in a register or other processor storage location. In one embodiment, a single handler may be used, and that handler may access the event schema vector to determine which event occurred and therefore how to respond. In another embodiment, the event schema vector may collectively define an event that causes the control flow logic  435  to call a handler. In other words, the event schema vector may represent a variety of conditions that together signal one event. For example, the event schema mask vector may be used to designate which of the events indicated by the event schema vector must occur to trigger execution of the handler. Each bit may represent a monitor reaching a programmable condition. When all the non-masked monitors reach their respective designated conditions, then the handler is called. Thus, the entire event schema vector may be used to designate some complex composite condition that should trigger the execution of the handler. 
     In another embodiment, multiple event schema vectors and masks may be used to designate different conditions. The different vectors may vector to different handlers via the event descriptor table or some other mechanism. In another embodiment, some bits of one or more event schema vectors may be grouped to form events that trigger the calling of handlers. A variety of other different permutations will be apparent to those of skill in the art. 
       FIG. 5   a  illustrates one embodiment of a monitor  500  that is programmable and capable of interfacing with a variety of performance monitors to signal a composite event. For example, such performance monitors may record occurrences of various microarchitectural events or conditions such as: cache misses incurred at a given level of cache hierarchy, branch retirement; branch misprediction (or retirement of mispredicted branches); trace cache delivery mode changes or events; branch prediction unit fetch requests; cancellations of memory request; cache line splits (count of completion of a split load, store, etc.); replay events; various types of bus transactions (e.g., locks, burst reads, writebacks, invalidates); allocations in a bus sequencer (or only certain types); numerical assist (an underflow, denormal, etc.); execution/retirement of a particular type of instruction or micro-operation (uOP); machine clear (or count of pipeline flushes); resource stalls (register renaming resources, pipeline, etc.); processing of tagged uOPs; instructions or uOPs retired; lines allocated (&amp;/or of a particular state (e.g., M)) in cache; a number of cycles instruction fetch is stalled; a number of cycles instruction length decoder is stalled; a number of cache fetches; a number of lines allocated (or evicted) in cache or the like. These are only a few examples of microarchitectural events or conditions that may be monitored. Various other possibilities as well as combinations of these or other conditions will be apparent to one of skill in the art. Moreover, those and/or other conditions or events may be monitored with any of the disclosed or like monitors in any of the disclosed embodiments. 
     Performance monitors are often included in processors to count certain events. The programmer may read such performance monitors&#39; counts by manufacturer-defined interfaces such as specific processor macro-instructions like the RDPMC instruction supported by known Intel Processors. See, e.g., Appendix A of Volume III of the Intel Software Developers Guide for the Pentium® 4 Processor. Other internal or micro-instructions or micro-operations may be used to read performance counters in some embodiments. Thus, for example, performance monitors may be adapted for use with disclosed techniques. In some cases, a programmable performance monitor may be modified to provide event signaling capabilities. In other embodiments, performance monitors may be readable by other monitors to establish events. 
     In the embodiment of  FIG. 5   a , the monitor  500  may include a set of programmable entries. Each entry may include an entry number  510 , an enable field  511 , a performance monitor number (EMON #)  512  to specify one of a set of performance monitors and a triggering condition  514 . The triggering condition may be, for example, a certain count that is reached, a count that is reached within a certain period, a difference in count, etc. The monitor  500  may include logic to read or otherwise be coupled to receive counts from the designated performance monitors. The monitor  500  signals the control flow logic when the various M conditions occur. A subset of the M entries may be used by selectively programming the enable fields for each entry. 
       FIG. 5   b  illustrates another embodiment of a monitor  520 . The monitor  520  represents a custom composite event monitor. The monitor  520  receives a set of signals via signal lines  528 - 1  through  528 -X from various execution resources or resource portions and combines them via combinational logic  530 . If the proper combination of signals is received, the monitor  520  signals the control flow logic via an output signal line  532 . 
       FIG. 5   c  illustrates another embodiment of a monitor  540 . The monitor  540  includes a table having M entries. Each entry includes an enable field  552 , a condition field  554 , and a trigger field  556 . The condition field may be programmed to specify what combination of input signals is to be monitored. The conditions may or may not be tied to other event detecting structures such as performance monitors, and therefore may be more general than those discussed with respect to  FIG. 5   a . The trigger field  556  may specify the state of those input signals needed to signal the control flow logic. Again, each entry may be enabled/disabled via the enable field  552 . In some embodiments, the condition and trigger fields may be combined. Various combinations of these and other types of known or otherwise available like, simpler, or more complex monitors will be apparent to one of skill in the art. 
       FIG. 6  illustrates a flow diagram for execution of a user program that activates helper threads in response to program-definable triggers according to one embodiment. In block  600 , the program first tests whether the yield capability is present. The “yield capability” may be used herein as shorthand to refer to the ability of to disrupt processing flow based on a condition or event occurring. Alternatively to testing for yield compatibility support, the yield capability may use opcodes previous defined as no-operation opcodes and/or previously unused or undefined MSRs so that use of the yield capability will have no effect on processor lacking such capabilities. The presence of such capabilities can also be queried via checking special CPU-ID that encodes hints indicating if such capabilities are present on a given processor or platform. Similarly, special instruction such as Itanium&#39;s PAL (processor-abstraction layer) call or SALE (system abstraction layer environment) can be used to query the processor specific configuration information including availability of such program-definable yield capability. Assuming the yield capability is present, then the user program may read and/or reset various counters, as indicated in block  610 . For example, performance monitor counters may be read so that a delta may be computed, or the values may be reset if that capability is available. 
     As indicated in block  620 , the user program then sets the helper thread trigger condition. The yield capability may be accessible at a low privileged level (e.g., a user level) such that any program or most programs can utilize this feature. For example, the yield capability may be available to ring three privilege level programs in a Pentium® Processor family processor, or the like. Therefore, the user program itself is able to set its own performance-based trigger conditions. A user program or operating system that is aware of existence of such context-sensitive monitor configurations, may choose to save and restore such application specific monitor configuration/setup across thread/process context switch, if the application demands or the operating system can provide persistent monitoring capability. 
     As indicated in block  630 , the user program continues to execute after programming the yield conditions. Whether the yield conditions occur is tested in block  640 . If the yield condition does not occur, then program execution continues as indicated in block  630 . If the yield condition does occur, then a helper thread is activated, as indicated in block  650 . The flowchart form of  FIG. 6  tends to imply that a synchronous polling for events occurs, and this approach may be used in some embodiments. However, some embodiments asynchronously react to events when they occur or within a number of clock cycles of when they occur rather than polling for them at certain intervals. In some embodiments, a monitor condition may be set outside of a loop or other code section to detect a particular condition. This concept is demonstrated by the following pseudo-code example for a main thread and a helper thread. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 main( ) 
               
               
                   
                  { 
               
               
                   
                   CreateThread(T) 
               
               
                   
                   WaitForEvent( ) 
               
               
                   
                   n = NodeArray[0] 
               
               
                   
                   setup Helper Trigger //Intrinsic 
               
               
                   
                   while(n and remaining) 
               
               
                   
                    { 
               
               
                   
                     work( ) 
               
               
                   
                     n-&gt;i = n-&gt;next-&gt;j + n-&gt;next-&gt;k + n-&gt;next-&gt;1 
               
               
                   
                     n = n-&gt;next 
               
               
                   
                     remaining-- 
               
               
                   
                     //Every Stride Time 
               
               
                   
                     // global_n = n 
               
               
                   
                     // global_r = remaining 
               
               
                   
                     // SetEvent( ) 
               
               
                   
                    } 
               
               
                   
                   disable Helper Trigger //Instrinsic 
               
               
                   
                  } 
               
               
                   
                 T( ) 
               
               
                   
                  { 
               
               
                   
                   Do Stride times 
               
               
                   
                     n-&gt;i = n-&gt;next-&gt;j + n-&gt;next-&gt;k + n-&gt;next-&gt;1 
               
               
                   
                     n = n-&gt;next 
               
               
                   
                     remaining-- 
               
               
                   
                   SetEvent( ) 
               
               
                   
                   while(remaining) 
               
               
                   
                    { 
               
               
                   
                    Do Stride times 
               
               
                   
                     n-&gt;i = n-&gt;next-&gt;j + n-&gt;next-&gt;k + n-&gt;next-&gt;1 
               
               
                   
                     //Responsible for most effective prefetch 
               
               
                   
                     //due to run-ahead 
               
               
                   
                     n = n-&gt;next 
               
               
                   
                     remaining-- 
               
               
                   
                     WaitForEvent( ) 
               
               
                   
                     if(remaining &lt; global_r)   //Detect Run-Behind 
               
               
                   
                      remaining = global_r  //Adjust by jump ahead 
               
               
                   
                      n = global_n 
               
               
                   
                    } 
               
               
                   
                  } 
               
               
                   
                   
               
            
           
         
       
     
     One advantage of setting the trigger outside the loop is that compiler optimizations within the loop will not be inhibited. For example, some compilers do not optimize loops or sections of code with intrinsics such as those which may be used to activate the yield capability. By placing such intrinsics outside the loop, interference with compiler optimizations may be removed. 
       FIG. 7  illustrates a flow diagram for a process of refining yield settings according to one embodiment. Using a processor with a yield capability or the like, a programmer may design a program as well as helper routines to be invokes under various circumstances as indicated in block  700 . Thus, helper routines may be provided for various processing-impeding conditions that the programmer anticipates. The processor can invoke these routines if and when they are needed during execution of the program. The yield settings may include the event schema vector and mask values and/or monitor settings or the like. 
     On a particular processor, a certain yield setting might result in a favorable execution throughput. However, such determination may be quite difficult manually and thus better derived empirically. Therefore a compiler or other tuning software (e.g., the Intel VTune code analyzer) may repeatedly simulate the code with different yield settings, thereby deriving optimal or desirable settings as indicated in block  710 . Thus, desirable values for yield settings for runtime may be chosen as indicated in block  720 . A program may be simulated on multiple different versions of a processor or multiple different processors, or in multiple different systems to derive different yield settings. A system or processor identification such as a CPU ID may be used by the program to select which yield settings to apply when it runs as indicated in block  730 . 
     Furthermore, the use of a compact group of settings to optimize performance may facilitate software updates. For example, new yield values may be downloaded to optimize performance for a given processor or may be used to update software when new processors are released. Such new values may allow a binary or modular modification which does not substantially disturb or jeopardize the functionality of the existing software. 
       FIG. 8  illustrates a flow diagram for a process of updating software according to one embodiment. As indicated in block  800 , a new version of a microprocessor is released. The new version may have different latencies associated with microarchitectural events such as cache misses. Therefore, a routine previously written to activate helper threads after a given number of cache misses may be less effective due to a new cache miss latency. Therefore, the yield settings are re-optimized as indicated in block  810 . 
     Once new settings are derived, the program can be updated (e.g., via an update module that may be a part of the program) as indicated in block  820 . A modification or addition to the yield values may be performed, depending on the details of the implementation. Moreover, additional or different helper routines may be added to assist on the new processor implementations. In either case, the yield capability can enable the delivery of performance enhancements after the initial delivery of the software. Such a capability may be quite advantageous in a great variety of scenarios, and may be used just to provide new optimizations without any change in the underlying hardware. Additionally, the underlying software may be maintained in some cases. For example, if a helper routine is written to deal with a synthetic event (e.g., bad cache misses), then on different hardware the composition of events which triggers this routine may be changed without changing the actual routines themselves. For example, the monitor configuration values and/or ESV/ESVM values may be changed and the routines left in tact. 
     The effectiveness of disclosed techniques may be further enhanced by creating nested helper threads, and  FIG. 9   a  illustrates one example of such usage. In the embodiment of  FIG. 9   a , the program sets the yield event(s) in block  900 . The program continues execution in block  910 . Whether a yield event (a trigger) occurs is tested in block  920 . If no yield event occurs, then program execution continues as shown via block  910 . If a yield event occurs, then a helper thread is activated as indicated in block  925 . The helper thread sets another yield event as indicated in block  930 . Thus, the helper thread effectively identifies a further condition that indicates that further processing assistance may be helpful. Such further condition may indicate whether the first helper thread is effective and/or may be designed to indicate a further condition that may be suspected to develop as a result of or in spite of activation of the first helper thread. 
     As indicated in block  940 , both the program and the helper thread are active and executing threads. These threads execute concurrently in the sense that they are both active and executing in a multithreaded processing resource. Whether the new trigger condition has occurred by the combination of both the program and the helper thread is tested in block  950 . If the new triggering condition does not occur, then execution for both threads continues as indicated in block  940 . If the new triggering condition does occur, a second or nested helper thread is activated as indicated in block  960 . Thereafter, the program and multiple helper threads may be active and execute as indicated in block  962 . Thus, multiple nested helper threads may be employed in some embodiments. 
     In one embodiment, multiple helper threads (either nested or non-nested) may be activated by the use of virtual threads. Rather than dedicating a full set of resources to expand the number of threads a processor can handle, a processor may effectively cache context data (in a cache location, a register location, or other storage location). Accordingly, one physical thread slot may be rapidly switched between multiple threads. 
     For example, the embodiment of  FIG. 9   b  illustrates thread switching logic according to one embodiment that allows virtual threads to be switched into a limited number of physical thread slots which have dedicated hardware to maintain a thread context. In the embodiment of  FIG. 9   b , a plurality of helper threads  965 - 1  through  965 -k may be presented to a virtual thread switcher  970 . The virtual thread switcher  970  may also include other logic and/or microcode (not shown) to swap context information between the new and previously selected helper threads. The virtual thread switcher  970  may be triggered to switch threads by either a synchronous or an asynchronous stimulus. For example, an asynchronous event defined by a yield-type of instruction may cause a thread switch between the virtual threads. Additionally, helper threads may include synchronous means such as a halt, quiesce, or other type of execution-stopping instruction to signal a switch to another thread. The virtual thread switch logic  970  presents a subset (e.g., in the embodiment of  FIG. 9   b , one) of the virtual threads to the processor thread switch logic  980 . The processor thread switch logic  980  then switches between one of the helper threads as a first thread  967 - 1  and its other N-1 threads, up to thread  967 -N. 
     In some embodiments, it may be advantageous to confine the yield capability to a particular program or thread. Therefore, the yield capability may be made context sensitive or non-promiscuous. For example,  FIG. 10   a  illustrates one embodiment of a context-sensitive event schema vector and mask implementation. In the embodiment of  FIG. 10   a , a storage area  1000  includes a context indicator field  1010  associated with each event schema vector and mask storage location  1020 . The context indicator field identifies the context to which each event schema vector and mask pair applies. For example, a context value such as value of a control register (e.g., CR3 in an x86 processor indicating operating system process ID) may be used. Additional or alternatively, thread number information may be used to define context. Therefore, in some embodiment, when a particular context is active, certain context specific events may be enabled to disrupt processing. As such, the yield mechanism may be non-promiscuous in that its events only affect certain contexts. 
       FIG. 10   b  illustrates another embodiment of a context-sensitive event schema vector and mask implementation. In the embodiment of  FIG. 10   b , an integer number k of contexts may be handled by providing one set of event schema vector and mask locations  1050 - 1  through  1050 -k for each of the k contexts. For example, there may be k threads in a multithreaded processor, and each thread may have an event schema vector and mask or like yield-enablement mechanism. Notably, in other embodiments, it may be undesirable to track events only in certain contexts. For example, events may be reflective of overall processing activity and/or events may be pertain to or be caused by to multiple related threads. 
       FIG. 11  illustrates one embodiment of a multithreaded processor which performs thread switching based on monitor or yield-type events. Although many embodiments have been discussed as disrupting processing flow by causing a handler to execute, other embodiments may define events that cause thread switches in a multithreaded processor. For example, in the embodiment of  FIG. 1 , thread switch logic is coupled to receive signals from a set of N monitors  1110 - 1  through  1110 -N. The thread switch logic  1105  may also be coupled to one or more sets of event schema and mask pairs  1130 - 1  through  1130 -p (p is a positive whole number). The event schema and mask pairs may allow the thread switch to combine and/or disregard certain monitor events in determining when to switch threads. 
     Execution resource  1120  may support execution of p threads, yet may be indifferent to whether an instruction belongs to a particular thread. The execution resource may be an execution unit, fetch logic, a decoder, or any other resource used in instruction execution. A multiplexer  1115  or other selection resource arbitrates between the various threads for access to the execution resource  1120 . One of skill in the art will recognize that various resources may be shared or duplicated in a multithreaded processor and that various resources may have thread-switched access which allows a limited number of threads (e.g., one) to access the resource at a time. 
     If a set of conditions indicated by one or more monitors and/or one of the event schema vector and mask pairs occurs, the thread switch logic  1105  switches threads of execution. Thus, another thread may be activated instead of the thread that was active when the processor conditions matched those programmed. For example, a user program may control events that trigger thread switches. 
     In some multithreaded processors, each thread may have an associated set of event schema vector and mask pairs or the like. Thus, as shown in  FIG. 11 , the multiplexer  1115  may arbitrate between p threads, and there may be a corresponding p event schema and mask pairs. Just because a processor is multithreaded, however, does not mean that all implementations use multiple event schema vectors and masks. Some embodiments may use only one pair, or may use other enablement indicators. For example a single bit could be used as an enablement indicator to turn on or off a particular yield-type capability. 
       FIG. 12  illustrates one embodiment of a system having event detection and handling capabilities pertaining to synchronization objects. Synchronization objects may be locks or lock variables, barriers, or other hardware, software, and/or memory resources which may be used for synchronization between threads or processes. As multiprocessing gains popularity either in terms of multiple cores and/or multithreading of various types, synchronization between such threads or processes becomes a more important facet to address for performance. Thus, a system with enhanced synchronization efficiencies may have wide applicability in various fields of general and/or special purpose processing where parallel processing is used (e.g., graphics, natural media types, digital signal processing, communications, etc.). 
     The system shown in  FIG. 12  illustrates a processor  1200  coupled to a memory  1250 , as well as to a communications interface  1292  and one or more peripheral(s)  1294  (e.g., may be audio interface, display, keyboard, mouse, other input devices, I/O devices, etc.). These devices may be coupled directly or indirectly, via buses, bridges, and/or point-to-point links. The processor  1200  includes execution resources  1210  and an event detector  1220  to monitor aspects of the execution resources  1210 . The processor  1200  and the event detector  1220  may have the various traits as previously described with respect to prior embodiments. Thus, the event detector  1220  may be programmable to activate a thread (e.g., trigger a thread switch or fork a new thread) based upon a defined event. The event may be a hard wired event, or as defined by a software program and a mechanism like an event schema vector, etc., as previously discussed. 
     The processor  1200  may also have a lock and/or spin detector  1222 . The lock/spin detector may be a separate detector in some embodiments as indicated in  FIG. 12 . Such a separate detector may be a hardware portion that detects certain predefined or even programmable conditions that indicate a lock. The detector thus may be partially hardware and partially software. In other embodiments, lock or spin-lock detection may be accomplished by programming various conditions into a general event detector. Thus, a general event detector may be programmed to detect such a condition, effectively forming a spin/lock detector when appropriately programmed. For example, the application  1254  may include an event detector programming module (EDPM)  1256  to program the event detector  1220  to trigger on the desired event(s). 
     One event relating to locks that may be detected is a long latency fetch of a lock variable. A lock variable that will incur a long latency to fetch may be detected by programming the event detector  1220  to trigger on a cache miss at a point in a program where the lock variable is about to be accessed in memory. The cache miss indicates that the processor does not have lock variable cached. A handler to address the long-latency-lock-fetch situation may then be activated to execute in response to this particular event being triggered. 
     Secondly, the lock/spin detector  1222  may also detect a spin condition, or a condition where a program is waiting on a highly contended lock and looping to check if the variable is available. For example, a spin condition may be detected by sensing repeated accesses to a known lock variable location. A second thread may be activated upon detecting such a spin condition, as will be discussed further below. Some embodiments may utilize a helper thread to deal with the contended lock situation independent of whether a long latency lock fetch (triggering a first helper thread) occurs first. 
     The embodiment of  FIG. 12  includes a light-weight threading context store  1230 . This context store allows a small subset of state to be preserved to allow “lightweight” or “fly weight” context switching. For example, only the instruction pointer of the parent process may be saved in some cases, leaving preservation of any additional context to the responsibility of the programmer. More or less context may be stored, but generally less than the full context is preserved in the subset. Such lightweight threading may be exposed at the user level (e.g., the application layer of programming, such as privileged level 3 programs in the x86 architecture) with specialized instructions to let the user enable threads to execute on the multithreaded execution resources in conjunction with a particular application. In this case, the event handlers triggered as lightweight threads should preserve any unsaved context they disturb that might be needed for the parent application to properly execute. In other embodiments, the helper threads triggered may be threads that have a full separate context. 
     The embodiment of  FIG. 12  also includes a memory  1250  that is coupled to the processor. In this embodiment, various lock overhead usage modules and an application  1254  are shown. The modules, in this embodiment, are software routines. In one embodiment, various of the modules are separate threads that are activated upon an event occurrence. One or more of the shown modules may be combined into a single helper thread, and the helper threads may be full or lightweight context threads. In other embodiments, these modules may be implemented as hardware or a combination of hardware and/or software and/or firmware. 
     The application  1254  may be a user level application that may have locks or other synchronization objects or techniques. A fetch critical section data module  1258  may be used to speculatively move beyond a lock and fetch data for within the critical portion protected by the lock. An obtain future locks module  1260  may run ahead and obtain locks for other lock-protected sections. A lock may be obtained by merely fetching the data location into a cache or in other embodiments may be obtained by changing the lock variable so that the lock is owned. The future locks module  1260  may also include a throttling module  1262  to ensure that the speculative lock activity does not reduce overall productivity by inhibiting other threads. A runahead execution module  1280  may execute ahead to accomplish some work outside the section protected by a lock. 
     A lock profiling module  1270  may gather data on the progress made by a particular thread in relation to a lock variable and/or other threads. A user thread scheduler module  1290  may receive scheduling hints from the lock profiling module to allow more efficient scheduling of threads. For example, the profiling module  1270  may detect that a first thread (e.g., the initial consumer) obtains a lock and causes significant spinning in a second thread (e.g., the initial producer). In such an instance, notifying the scheduler that the second thread (the initial producer) should be scheduled first may result in more efficient processing. In some embodiments, the scheduler may be a user level thread scheduler that is exposed to the programmer to allow scheduling of user level (e.g., lightweight) threads. In some embodiments, the user thread scheduler  1290  may be a portion of the application  1254 . 
     One example interaction of such modules may be further understood with reference to  FIG. 13 . In the embodiment of  FIG. 13 , in block  1310 , a lock fetch delay is detected. Such detection may be done by programming of the event detector  1220  to sense a condition. For example, the application  1254  may call the event detector programming module  1256  to program the event detector  1220  to trigger on a cache miss just prior to an access to a lock variable. Alternatively, the lock may be detected by a specialized lock/spin detector  1222  as previously discussed. 
     In block  1315 , a thread switch (e.g., a fly-weight thread switch) may be performed in response to detecting the fetch delay of the lock variable. This thread switch activates a first helper thread, which may perform various of the functions illustrated in the following blocks in various embodiments. Thus, while various blocks follow block  1315 , not all need be present in any particular embodiment, nor is the order necessarily critical. 
     In block  1320 , data beyond the code obtaining the lock, but within the section of code protected by the lock, may be fetched. For example, the fetch critical section data module  1258  may be executed in the embodiment of  FIG. 12 . Such prefetching of data in the lock-protected code section may reduce cache misses or general data retrieval latency when ownership of the lock is finally obtained. 
     Additionally (either as a separate thread or as part of the same thread), future locks may be fetched as indicated in blocks  1330 - 1365 . In particular, N additional locks may be obtained, where N is a positive integer number. The number of locks to obtain may be programmable or hard coded, and may be varied during execution (e.g., by reprogramming or the throttling module  1262 ). In block  1330 , a loop variable, i, is set to one. A future lock is fetched (e.g., may be prefetched or actually locked in various embodiments) as indicated in block  1340 . Future lock addresses may be statically calculated in generating a helper thread or may be determined through lock profiling, which is discussed below. As indicated in block  1350 , whether the lock is contended may be tested. If the future lock is contended (e.g., may be indicated by cache state of the lock variable, the value of the lock variable, or by program behavior of spinning), then fetching of that and/or other future lock(s) may be aborted as indicated in block  1355 . 
     In the case where the lock is not found to be contended in block  1350 , operation continues in block  1360 . If the count of locks fetched is not equal to the target number N, as tested in block  1360 , then the variable i is incremented in block  1365  and the process returns to block  1340 . If the count reaches N in block  1360 , then the process continues on to block  1370  in one embodiment. These lock fetching operations  1330 - 1365  may be performed by the obtain future locks module  1260  in the embodiment of  FIG. 12 . Fetching or obtaining ownership of future locks may advantageously expedite program execution because the lock is more likely to be readily available when encountered. Many programs encounter relatively few highly contended locks. Therefore, the enhancement of prefetching locks may outweigh any negative impact to the progress of other processes. 
     In some embodiments, the work to be performed by the thread triggered in block  1315  may end with block  1365  and thus the thread may be switched out (via a halt or join type operation) and control returned to the main thread, as indicated in block  1370 . In other embodiments, the helper thread may continue and execute the operations of blocks  1372 - 1375  and/or other operations. Further, other embodiments may trigger other numbers of helper threads or other combinations of the illustrated operations. 
     In the embodiment of  FIG. 13 , as shown in block  1372 , the application may fail to secure the lock. In other words, the lock variable may indicate some other process owns the lock. In some embodiments, repeated failure is detected. A spin threshold may be programmed or otherwise set to provide a threshold number of failed attempts to gain ownership of a lock variable prior to action being taken. In block  1374 , a second helper thread is triggered to accomplish further work in the shadow of the overhead necessary to obtain ownership of the lock variable. One example is that code outside of the critical section may be executed, as indicated by block  1375 . For example, in the embodiment of  FIG. 12 , the runahead execution module  1280  may be executed. In some embodiments, the code may be executed to prefetch instructions or data only and not to actually compute results and/or commit results to machine state. In other embodiments, results may be computed and/or committed as a part of the runahead execution if dependency checking is performed to ensure accurate results. 
     Alternatively, additional locks could be obtained by the second helper thread in response to this second event similarly to the process of blocks  1330 - 1365 . Another alternative is that lock profiling may be performed. Yet another alternative is that previously held locks may be pushed out of at least the highest level cache (perhaps even to the external interface) to reduce a transfer latency for another processor to obtain the lock. These various examples of other work that can be done in the shadow of lock overhead may all be combined in various permutations in different embodiments. 
       FIG. 14  illustrates one embodiment that includes lock profiling. In the embodiment of  FIG. 14 , various threads are scheduled in block  1410 . These threads may be lightweight threads that are scheduled and controlled at a user or application level in one embodiment. For example, application  1254  may include the user thread scheduler  1290  in  FIG. 12 . In another embodiment, these threads may be operating system visible threads with full context. In block  1420 , a contended lock is detected. The contended lock causes a profiling thread to be enabled or activated. This thread profiles the behavior of the lock as indicated in block  1430 . In one embodiment, the profiling entails capturing data such as event counter data from performance counters or other similar structures. The profiling information is then used to help determine priorities and/or ordering of threads when thread scheduling is done again in block  1410 . Thus, lock overhead time is again used to improve overall program performance. As previously noted, such scheduling information may assist a thread scheduler in scheduling producer/consumer thread pairs more efficiently. 
     During development, a design may go through various stages, from creation to simulation to fabrication. Data representing a design may represent the design in a number of manners. First, as is useful in simulations, the hardware may be represented using a hardware description language or another functional description language Additionally, a circuit level model with logic and/or transistor gates may be produced at some stages of the design process. Furthermore, most designs, at some stage, reach a level of data representing the physical placement of various devices in the hardware model. In the case where conventional semiconductor fabrication techniques are used, the data representing the hardware model may be the data specifying the presence or absence of various features on different mask layers for masks used to produce the integrated circuit. In any representation of the design, the data may be stored in any form of a machine readable medium. An optical or electrical wave modulated or otherwise generated to transmit such information, a memory, or a magnetic or optical storage such as a disc may be the machine readable medium. Any of these mediums may “carry” or “indicate” the design or software information. When an electrical carrier wave indicating or carrying the code or design is transmitted, to the extent that copying, buffering, or re-transmission of the electrical signal is performed, a new copy is made. Thus, a communication provider or a network provider may make copies of an article (a carrier wave) embodying techniques of the present invention. 
     Thus, techniques for a programmable event driven yield mechanism which may activate other threads are disclosed. While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications may occur to those ordinarily skilled in the art upon studying this disclosure. In an area of technology such as this, where growth is fast and further advancements are not easily foreseen, the disclosed embodiments may be readily modifiable in arrangement and detail as facilitated by enabling technological advancements without departing from the principles of the present disclosure or the scope of the accompanying claims.