Patent Publication Number: US-7213135-B2

Title: Method using a dispatch flush in a simultaneous multithread processor to resolve exception conditions

Description:
CROSS REFERENCE TO RELATED APPLICATION 
   The present invention is related to the following U.S. patent application which is incorporated by reference: 
   Ser. No. 10/422,685 entitled “A Method for Resource Balancing Using Dispatch Flush In A Simultaneous Multithread Processor,” filed concurrently herewith. 
   TECHNICAL FIELD 
   The present invention relates in general to methods and circuitry for a processor having simultaneous multithreading (SMT) and single thread operation modes. 
   BACKGROUND INFORMATION 
   For a long time, the secret to more performance was to execute more instructions per cycle, otherwise known as Instruction Level Parallelism (ILP), or decreasing the latency of instructions. To execute more instructions each cycle, more functional units (e.g., integer, floating point, load/store units, etc.) have to be added. In order to more consistently execute multiple instructions, a processing paradigm called out-of-order processing (OOP) may be used, and in fact, this type of processing has become mainstream. 
   OOP arose because many instructions are dependent upon the outcome of other instructions, which have already been sent into the processing pipeline. To help alleviate this problem, a larger number of instructions are stored in order to allow immediate execution. The reason this is done is to find more instructions that are not dependent upon each other. The area of storage used to store the instructions that are ready to execute immediately is called the reorder buffer. The size of reorder buffers have been growing in most modern commercial computer architectures with some systems able to store as many as 126 instructions. The reason for increasing the size of the reorder buffer is simple: code that is spatially related tends also to be temporally related in terms of execution (with the possible exclusion of arrays of complex structures and linked lists). The only problem is that these instructions also have a tendency to depend upon the outcome of prior instructions. With a CPU&#39;s ever increasing amount of required code, the only current way to find more independent instructions has been to increase the size of the reorder buffer. 
   However, using this technique has achieved a rather impressive downturn in the rate of increased performance and in fact has been showing diminishing returns. It is now taking more and more transistors to achieve the same rate of performance increase. Instead of focusing intently upon uniprocessor ILP extraction, one can focus upon a coarser form of extracting performance at the instruction or thread level, via multithreading (multiprocessing), but without the system bus as a major constraint. 
   The ability to put more transistors on a single chip has allowed on-chip multiprocessing (CMP). To take advantage of the potential performance increases, the architecture cannot use these multiple processors as uniprocessors but rather must use multiprocessing that relies on executing instructions in a parallel manner. This requires the programs executed on the CMP to also be written to execute in a parallel manner rather than in a purely serial or sequential manner. Assuming that the application is written to execute in a parallel manner (multithreaded), there are inherent difficulties in making the program written in this fashion execute faster proportional to the number of added processors. 
   The general concept behind using multiple cores on one die is to extract more performance by executing two threads at once. By doing so, the two CPUs together are able to keep a higher percentage of the aggregate number of functional units doing useful work at all times. If a processor has more functional units, then a lower percentage of those units may be doing useful work at any one time. The on-chip multiprocessor lowers the number of functional units per processor, and distributes separate tasks (or threads) to each processor. In this way, it is able to achieve a higher throughput on both tasks combined. A comparative uniprocessor would be able to get through one thread, or task, faster than a CMP chip could, because, although there are wasted functional units, there are also “bursts” of activity produced when the processor computes multiple pieces of data at the same time and uses all available functional units. One idea behind multiprocessors is to keep the individual processors from experiencing such burst activity times and instead have each processor use what resources it has available more frequently and therefore efficiently. The non-use of some of the functional units during a clock cycle is known as “horizontal waste,” which CMP tries to avoid. 
   However, there are problems with CMP. The traditional CMP chip sacrifices single-thread performance in order to expedite the completion of two or more threads. In this way, a CMP chip is comparatively less flexible for general use, because if there is only one thread, an entire half of the allotted resources are idle and completely useless (Oust as adding another processor in a system that uses a singly threaded program is useless in a traditional multiprocessor (MP) system). One approach to making the functional units in a CMP more efficient is to use course-grained multithreading (CMT). CMT improves the efficiency with respect to the usage of the functional units by executing one thread for a certain number of clock cycles. The efficiency is improved due to a decrease in “vertical waste.” Vertical waste describes situations in which none of the functional units are working due to one thread stalling. 
   When switching to another thread, the processor saves the state of that thread (i.e., it saves where instructions are in the pipeline, which units are being used) and switches to another one. It does so by using multiple register sets. The advantage of this is due to the fact that often a thread can only go for so long before it falls upon a cache miss, or runs out of independent instructions to execute. A CMT processor can only execute as many different threads in this way as it has support for. So, it can only store as many threads as there are physical locations for each of these threads to store the state of their execution. An N-way CMT processor would therefore need to have the ability to store the state of N threads. 
   A variation on this concept would be to execute one thread until it has experienced a cache miss (usually a L2 (secondary) cache miss), at which point the system would switch to another thread. This has the advantage of simplifying the logic needed to rotate the threads through a processor, as it will simply switch to another thread as soon as the prior thread is stalled. The penalty of waiting for a requested block to be transferred back into the cache is then alleviated. This is similar to the hit under miss (or hit under multiple miss) caching scheme used by some processors, but it differs because it operates on threads instead of upon instructions. The advantages of CMT over CMP are CMT does not sacrifice single-thread performance, and there is less hardware duplication (less hardware that is halved to make the two processors “equal” to a comparable CMT). 
   A more aggressive approach to multithreading is called fine-grained multithreading (FMT). Like CMT, the basis of FMT is to switch rapidly between threads. Unlike CMT, however, the idea is to switch each and every cycle. While both CMT and FMT actually do indeed slow down the completion of one thread, FMT expedites the completion of all the threads being worked on, and it is overall throughput which generally matters most. 
   CMPs may remove some horizontal waste in and unto themselves. CMT and FMT may remove some (or all) vertical waste. However an architecture that comprises an advanced form of multithreading, referred to as Simultaneous Multithreading (SMT), may be used to reduce both horizontal and vertical waste. The major goal of SMT is to have the ability to run instructions from different threads at any given time and in any given functional unit. By rotating through threads, an SMT architecture acts like an FMT processor, and by executing instructions from different threads at the same time, it acts like CMP. Because of this, it allows architects to design wider cores without the worry of diminishing returns. It is reasonable for SMT to achieve higher efficiency than FMT due to its ability to share “unused” functional units among differing threads; in this way, SMT achieves the efficiency of a CMP machine. However, unlike a CMP system, an SMT system makes little to no sacrifice (the small sacrifice is discussed later) for single threaded performance. The reason for this is simple. Whereas much of a CMP processor remains idle when running a single thread and the more processors on the CMP chip makes this problem more pronounced, an SMT processor can dedicate all functional units to the single thread. While this is obviously not as valuable as being able to run multiple threads, the ability to balance between single thread and multithreaded environments is a very useful feature. This means that an SMT processor may exploit thread-level parallelism (TLP) if it is present, and if not, will give full attention to instruction level parallelism (ILP). 
   In order to support multiple threads, an SMT processor requires more registers than the traditional superscalar processor. The general aim is to provide as many registers for each supported thread as there would be for a uniprocessor. For a traditional reduced instruction set computer (RISC) chip, this implies 32 times N registers (where N is the number of threads an SMT processor could handle in one cycle), plus whatever renaming registers are required. For a 4-way SMT processor RISC processor, this would mean 128 registers, plus however many renaming registers are needed. 
   Most SMT models are straightforward extensions of a conventional out-of-order processor. With an increase in the actual throughput comes more demands upon instruction issue width, which should be increased accordingly. Because of the aforementioned increase in the register file size, an SMT pipeline length may be increased by two stages (one to select register bank and one to do a read or write) so as not to slow down the length of the clock cycle. The register read and register write stages are therefore both broken up into two pipelined stages. 
   In order to not allow any one thread to dominate the pipeline, an effort should be made to ensure that the other threads get a realistic slice of the execution time and resources. When the functional units are requesting work to do, the fetch mechanism will provide a higher priority to those threads that have the fewest instructions already in the pipeline. Of course, if the other threads have little they can do, more instructions from the thread are already dominating the pipelines. 
   SMT is about sharing whatever possible. However, in some instances, this disrupts the traditional organization of data, as well as instruction flow. The branch prediction unit becomes less effective when shared, because it has to keep track of more threads with more instructions and will therefore be less efficient at giving an accurate prediction. This means that the pipeline will need to be flushed more often due to misprediction, but the ability to run multiple threads more than makes up for this deficit. 
   The penalty for a misprediction is greater due to the longer pipeline used by an SMT architecture (by two stages), which is in turn due to the rather large register file required. However, techniques have been developed to minimize the number of registers needed per thread in an SMT architecture. This is done by more efficient operating system (OS) and hardware support for better deallocation of registers, and the ability to share registers from another thread context if another thread is not using all of them. 
   Another issue is the number of threads in relation to the size of caches, the line sizes of caches, and the bandwidth afforded by them. As is the case for single-threaded programs, increasing the cache-line size decreases the miss rate but also increases the miss penalty. Having support for more threads which use more differing data exacerbates this problem and thus less of the cache is effectively useful for each thread. This contention for the cache is even more pronounced when dealing with a multiprogrammed workload over a multithreaded workload. Thus, if more threads are in use, then the caches should be larger. This also applies to CMP processors with shared L2 caches. 
   The more threads that are in use results in a higher overall performance and the differences in association of memory data become more readily apparent. There is an indication that when the L1 (primary) cache size is kept constant, the highest level of performance is achieved using a more associative cache, despite longer access times. Tests have been conducted to determine performance with varying block sizes that differ associatively while varying the numbers of threads. As before, increasing the associative level of blocks increased the performance at all times; however, increasing the block size decreased performance if more than two threads were in use. This was so much so that the increase in the degree of association of blocks could not make up for the deficit caused by the greater miss penalty of the larger block size. 
   An SMT processor has various elements that are broadly termed resources. A resource may be an execution unit, a register rename array, a completion table, etc. Some resources are thread specific, for example each thread may have its own instruction queue where instructions for each thread are buffered. Execution units are shared resources where instructions from each thread are executed. Likewise a register rename array and a completion table in a completion unit may be shared resources. If the entries in a shared register rename array are mostly assigned to one thread then that thread may be using an excessive amount of this shared resource. If the other thread needs a rename register to proceed, then it may be blocked because of a resource requirement and be unable to be dispatched. Other elements in a system that comprises an SMT processor may be termed resources and may not apply to the problems addressed by the present invention if those resources do not slow execution of instructions from multiple threads. 
   In an SMT processor, there may be an in-order shared pipeline that is part of a larger pipelined process for doing out-of-order instruction execution in multiple execution units. For example, instructions from two threads may be alternately loaded into a shared pipeline comprising an instruction fetch unit (IFU) and instruction dispatch unit (IDU). The instruction addresses are alternately loaded into an instruction fetch address register (IFAR) in the IFU. In this case, it is possible for one thread in the shared pipeline to be “stalled” and thus block the other thread from progressing through the pipeline. There are additional conditions where a first instruction of a first thread generates an exception condition during execution that needs an exception address from a following second instruction of the same first thread that has not reached dispatch to resolve the exception condition. If the first instruction generating the exception condition has shared resources that it needs to release to allow blocking instruction from a second thread to dispatch before the second instruction can proceed to dispatch, then the shared pipeline may be additionally blocked. 
   There are also cases where the blocking instruction from the second thread that is preventing the second instruction from proceeding to dispatch is of a type that has a long latency resource requirements and may potentially block for a very long time. This also prevents the exception condition from being resolved. If the blocking instruction of the second thread is simply flushed and refetched, little progress may made in removing the blockage stalling the second instruction from making progress. There is, therefore, a need for a method and circuitry to detect this condition and to flush the thread with the blocking instruction from the pipeline to make room for the other thread with the exception condition to make progress. Additionally, a hold off mechanism is needed that prevents a long resource latency blocking instruction from being refetched until its resource requirements are resolved or the exception condition being blocked is resolved. Two such instructions that suffer from long latency are the Translation Look Aside Buffer Invalidate Entry instruction and a Sync instruction. 
   There is, therefore, a need for a method and circuitry to detect and remedy exception condition stalls due to resources usage. Additionally, a hold off mechanism is needed that controls when instructions with long latency resource requirements are refetched and reenter the dispatch pipeline. 
   SUMMARY OF THE INVENTION 
   A dispatch flush operation is usually issued when it is desirable to flush instructions of a thread in a shared dispatch pipeline that is causing a pipeline stall. Dispatch flushes are more efficient than a general flush as they affect a smaller portion of the SMT processor. A first instruction of a first thread may cause an exception condition that requires an address of a second instruction of the first thread to resolve the exception. In this case the second instruction must make it to the dispatch stage of the pipeline for the address to be acquired. In the single thread mode, this is not a problem because in a few cycles the needed instruction will appear in the dispatch stage and the exception may be resolved. When the first instruction is using resources that are not released until it completes, then a blocking instruction of the second thread that also requires these resources may block the shared pipeline preventing the second instruction of the first thread from reaching the dispatch pipeline. This condition causes a pipeline stall that may be resolved by flushing the first thread or using some type of exception handler that can resolve the blockage. 
   When a first instruction of a first thread causes an exception condition that requires an address of a second instruction of the first thread to resolve the exception, embodiments of the present invention use a dispatch flush operation to resolve this condition. A dispatch flush is issued for instructions of the second thread. This allows instructions of the first thread to proceed and the second instruction of the first thread is allowed to dispatch to resolve the exception. 
   If the blocking instruction of a second thread is blocking the shared pipeline because it has resource requirements that have a long latency, then the second instruction for the first thread may not be issued for a long time thus also preventing the exception from being resolved. In this case, a hold may be issued controlling when the instructions of the second thread that are flushed are refetched and re-enter the pipeline to allow the resource latency to be satisfied. 
   The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: 
       FIG. 1  is a block diagram of functional units in an SMT processor according to embodiments of the present invention; 
       FIG. 2  is a flow diagram of method steps used in dispatching a group of instructions in an SMT processor; 
       FIG. 3  is a flow diagram of method steps according to embodiments of the present invention; 
       FIG. 4  is a representative hardware environment for practicing the present invention; and 
       FIG. 5  is a flow diagram of method steps used in a dispatch flush operation in an SMT processor. 
   

   DETAILED DESCRIPTION 
   In the following description, numerous specific details are set forth to provide a thorough understanding of the present invention. However, it will be obvious to those skilled in the art that the present invention may be practiced without such specific details. In other instances, well-known circuits may be shown in block diagram form in order not to obscure the present invention in unnecessary detail. For the most part, details concerning timing, data formats within communication protocols, and the like have been omitted inasmuch as such details are not necessary to obtain a complete understanding of the present invention and are within the skills of persons of ordinary skill in the relevant art. 
   Refer now to the drawings wherein depicted elements are not necessarily shown to scale and wherein like or similar elements are designated by the same reference numeral through the several views. 
   Referring to  FIG. 1 , there are illustrated details of CPU  410 . CPU  410  is designed to execute multiple instructions per clock cycle. Thus, multiple instructions may be executing in any of the execution units, fixed point units (FXUs)  114 , floating point units (FPUs)  118 , and load/store units (LSUs)  116  during any one clock cycle. Likewise, CPU  410  may simultaneously execute instructions from multiple threads in an SMT mode. 
   Program counters (PCs)  134  correspond to thread zero (T0) and thread one (T1) that have instructions for execution. Thread selector  133  alternately selects between T0 and T1 to couple an instruction address to instruction fetch unit (IFU)  108 . Instruction addresses are loaded into instruction fetch address register (IFAR)  103 . IFAR  103  alternately fetches instructions for each thread from instruction cache (I-Cache)  104 . Instructions are buffered in instruction queue (IQ)  135  for T0 and IQ  136  for T1. IQ  135  and IQ  136  are coupled to instruction dispatch unit (IDU)  132 . Instructions are selected and read from IQ  135  and IQ  136  under control of thread priority selector  137 . Normally, thread priority selector  137  reads instructions from IQ  135  and IQ  136  substantially proportional to each thread&#39;s program controlled priority. A Cache Line Buffer (CLB) hold allows instructions of the second thread to be flushed from a dispatch queue in the dispatch pipeline and entered into the dispatch queue, but not dispatched until the CLB hold is removed. 
   The instructions are decoded in a decoder (not shown) in IDU  132 . Instruction sequencer  113  then may place the instructions in groups in an order determined by various algorithms. The groups of instructions are dispatched to instruction issue queue (IIQ)  131  by dispatch stage  140 . The instruction sequencer  113  receives instructions from both threads in program order, but the instructions may be issued from the IIQ  131  out of program order and from either thread. The general purpose register (GPR) file  115  and floating point register (FPR) file  117  are used by multiple executing units and represent the program state of the system. These hardware registers maybe referred to as the “architected” registers. When an instruction is dispatched to an issue queue, each architected register is renamed. Each architected register that is being modified is assigned a physical register and a corresponding look-up table identifies physical registers that are associated with an architected register. Therefore in the issue queues, the architected register has been renamed so that multiple copies of an architected register may exist at the same time. This allows instructions to be executed out-of-order as long as source operands are available. Register renaming unit  141 , renames and maps the registers so that unused physical registers may be reassigned when all instructions referencing a particular physical register complete and the physical register does not contain the latest architected state. 
   Instructions are queued in HQ  131  for execution in the appropriate execution unit. If an instruction contains a fixed point operation, then any of the multiple fixed point units (FXUs)  114  may be used. All of the execution units, FXU  114 , FPU  118  and LSU  116  are coupled to completion unit  119  that has completion tables (not shown) indicating which of the issued instructions have completed and other status information. Information from completion unit  119  is forwarded to IFU  108 . IDU  132  may also send information to completion unit  119 . Data from a store operation from LSU  116  is coupled to data cache (D-Cache)  102 . This data may be stored in D-Cache  102  for near term use and/or forwarded to bus interface unit (BIU)  101  which sends the data over bus  412  to memory  139 . LSU  116  may load data from D-Cache  102  for use by the execution units (e.g., FXU  114 ). 
   SMT processor  410  has pipeline stages comprising circuitry of the IFU  108  and circuitry of the IDU  132  that is shared between two threads. Instructions are loaded into a pipeline stage alternately from each thread in program order. As the instructions are accessed from I-Cache,  104  they are queued in a T0 queue  135  and a T1 queue  137 . Instructions are selected from these queues either equally or according to a thread priority selector  137  which selects from each thread substantially in proportions the thread&#39;s priority An instruction sequencer  113  in the IDU  132  combines the instructions from each thread into instruction groups of up to five instructions per group. The instructions from the thread groups are issued to instruction issue queues  131  that feed multiple execution units (e.g.,  114 ,  116 , and  118 ). Instructions in the instruction groups are in program order when they are dispatched to instruction issue queues  131  and to the completion table (not shown) in completion unit  119 . However, instructions may be issued to the execution units out-of-order. 
   When instructions are executing in an execution unit (e.g., FPU  118 ), there may be an exception condition (e.g., divide by zero in an FPU  118 ) that occurs that prevents the instruction from completing. If the instruction does not complete it may not release shared resources (e.g., group completion table entry). If this resource is needed by an instruction awaiting dispatch from dispatch stage  140 , then that instruction may not be dispatched because of shared resource requirements. 
     FIG. 2  is a flow diagram of method steps used in dispatching a group of instructions from a thread in an SMT processor  410  using embodiments of the present invention. In step  201 , a test is done to determine if there is a group of instructions at the dispatch stage  140  of a shared pipeline in IDU  132 . If the result of the test in step  201  is NO, then a branch is taken back to the input of step  201 . If the result of the test in step  201  is YES, then in step  202 , the thread identification (ID) is checked to identify the particular thread for the instruction group at the dispatch stage (in IDU  132 ). In step  203 , the group is queued to dispatch from IDU  132  speculatively if appropriate. In step  204 , a test is done to determine if required shared resources for the instruction group is available. If the shared resources are not available, then in step  209 , the dispatch of the instruction group from IDU  132  is rejected. If the shared resources are available, then in step  205 , a test is done to determine if thread specific resources are available. If the required thread specific resources are not available, then step  209  is executed and the dispatch is rejected. In step  206 , a test is done to determine if any dispatch flush in IDU  132  is already in progress. If a dispatch flush is already in progress, then in step  209 , the dispatch is rejected. If no dispatch flush is in progress, then in step  207 , a test is done to determine if any flush of the thread corresponding to the instruction group in the dispatch stage is in progress. If the result of the test in step  207  is YES, then in step  209 , the dispatch is rejected. If the result of the test in step  207  is NO, then in step  208 , the instruction group is dispatched from dispatch stage  140 . 
     FIG. 3  is a flow diagram of method steps used in embodiments of the present invention to manage instruction flow using dispatch flush because conflicts in shared resources between threads. In step  301 , an exception condition is detected in an execution unit (e.g., FXU  114 , LSU  116  or FPU  118 ) while executing a first instruction for the first thread that requires an exception address from a second instruction of the first thread that has not reached dispatch stage  140  in IDU  132 . In step  302 , a test is done to determine if the dispatch of the second instruction for the first thread is stalled in dispatch stage  140  by a blocking instruction of the second thread. If the result of the test in step  302  is NO, then in step  303  a branch is taken to step  308  where dispatch of the second instruction from dispatch stage  140  will allow the exception address to be dispatched. If the result of the test in step  302  is YES, then in step  304  a test is done to determine if the blocking instruction requires resources held by the first instruction of the first thread with the exception condition. If the result of the test in step  304  is YES, then in step  309  a dispatch flush for the second thread is issued to IDU  132  and then in step  308  dispatching of instructions from IDU  132  is continued. If the result of the test in step  304  is NO, then in step  305  a test is done to determine if the blocking instruction has a long latency resource requirement. If the result of the test in step  305  is NO, then a return is taken to step  308 . If the result of the test in step  305  is YES, then in step  306  a dispatch flush to IDU  132  for the second thread comprising the blocking instruction is issued. In step  307 , a hold operation is issued, generating a hold controlling when flushed instructions of the second thread are refetched and reenter the shared pipeline in SMT  410 . Then in step  308 , instructions continue to be dispatched from IDU  132 . 
     FIG. 5  is a flow diagram of method steps used in processing a dispatch flush operation in an SMT processor  410  using embodiments of the present invention. In step  500 , a request foradispatch flush fora selected thread is issued to IDU  132 . In step  501 , a test is done if the selected thread with the requested dispatch flush is dispatching an instruction group from IDU  132 . If the selected thread is not dispatching an instruction group, then no dispatch flush is issued and a branch is taken back to the input of step  501 . If the selected thread is dispatching an instruction group, then in step  502  a test is done to determine if any group instructions in the selected thread are micro code, the thread needs an exception address, or the SMT mode is not selected. If the result of the test in step  502  is YES, then in step  504  the dispatch flush is not issued. If the result of the test in step  502  is NO, then in step  503  a test is done to determine if the selected thread has any flush in progress. If the result of the test in step  503  is YES, then step  504  is again executed. If the result of the test in step  503  is NO, then in step  505  test is done to determine if any type of flush for the selected thread has started. At this time, if no flush has started, then in step  506  the dispatch flush for the selected thread is issued to IDU  132 . If the result of the test in step  505  is YES, then step  504  is again executed and the dispatch flush to IDU  132  for the selected thread is not issued. 
   A representative hardware environment for practicing the present invention is depicted in  FIG. 4 , which illustrates a typical hardware configuration of a workstation  400  in accordance with the subject invention having central processing unit (CPU)  410  with simultaneous multithread (SMT) processing and a number of other units interconnected via system bus  412 . The workstation shown in  FIG. 4  includes random access memory (RAM)  414 , read only memory (ROM)  416 , and input/output ( 110 ) adapter  418  for connecting peripheral devices such as disk units  420  and tape drives  440  to bus  412 , user interface adapter  422  for connecting keyboard  424 , mouse  426 , speaker  428 , microphone  432 , and/or other user interface devices such as a touch screen device (not shown) to bus  412 , communication adapter  434  for connecting the workstation to a data processing network, and display adapter  436  for connecting bus  412  to display device  438 . 
   Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.