Abstract:
A system and method is provided for improving throughput of an in-order multithreading processor. A dependent instruction is identified to follow at least one long latency instruction with register dependencies from a first thread. The dependent instruction is recycled by providing it to an earlier pipeline stage. The dependent instruction is delayed at dispatch. The completion of the long latency instruction is detected from the first thread. An alternate thread is allowed to issue one or more instructions while the long latency instruction is being executed.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The invention relates generally to improving throughput of an in-order processor and, more particularly, to multithreading techniques in an in-order processor.  
           [0003]    2. Description of the Related Art  
           [0004]    “Multithreading” is a common technique used in computer systems to allow multiple threads to run on a shared dataflow. If used in a single-processor system, multithreading gives operating system software of the single-processor system the appearance of a multi-processor system.  
           [0005]    There are several multithreading techniques used in the prior art. For example, coarse-grain multithreading allows only one thread to be active at a time and flushes the entire pipeline whenever there is a thread swap. In this technique, a single thread runs until it encounters an event, such as a cache miss, and then the pipeline is drained and the alternate thread is activated (i.e., swapped in).  
           [0006]    In another example, simultaneous multithreading (SMT) allows multiple threads to be active simultaneously and uses the resources of an out-of-order design, such as register renaming, and completion reorder buffers to track the multiple active threads. SMT can be fairly expensive in hardware implementation.  
           [0007]    Therefore, a need exists for a system and method for improving throughput of an in-order multithreading processor without using the out-of-order design technique.  
         SUMMARY OF THE INVENTION  
         [0008]    The present invention provides a system and method for improving throughput of an in-order multithreading processor. A dependent instruction is identified to follow at least one long latency instruction with register dependencies from a first thread. The dependent instruction is recycled by providing it to an earlier pipeline stage. The dependent instruction is delayed at dispatch. The completion of the long latency instruction is detected from the first thread. An alternate thread is allowed to issue one or more instructions while the long latency instruction is being executed. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    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:  
         [0010]    [0010]FIG. 1 is a block diagram illustrating multithreading instruction flows in a processor;  
         [0011]    [0011]FIG. 2 is a timing diagram illustrating normal thread switching; and  
         [0012]    [0012]FIG. 3 is a timing diagram illustrating thread switching when a dependent instruction follows a load miss in a thread. 
     
    
     DETAILED DESCRIPTION  
       [0013]    In the following discussion, 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 elements have been illustrated in schematic or block diagram form in order not to obscure the present invention in unnecessary detail.  
         [0014]    It is further noted that, unless indicated otherwise, all functions described herein may be performed in either hardware or software, or some combination thereof. In a preferred embodiment, however, the functions are performed by a processor such as a computer or an electronic data processor in accordance with code such as computer program code, software, and/or integrated circuits that are coded to perform such functions, unless indicated otherwise.  
         [0015]    Referring to FIG. 1 of the drawings, the reference numeral  100  generally designates a processor  100  having multithreading instruction flows in a block diagram. Preferably, the processor  100  is an in-order multithreading processor. The processor  100  has two threads (A and B); however, it may have more than two threads.  
         [0016]    The processor  100  comprises instruction fetch address registers (IFARs)  102  and  104  for threads A and B, respectively. The IFARs  102  and  104  are coupled to an instruction cache (ICACHE)  106  having IC 1 , IC 2  and IC 3 . The processor  100  also comprises instruction buffers (IBUFs)  108  and  110  for threads A and B, respectively. Each of the IBUFs  108  and  110  is two entries deep and four instructions wide. Specifically, IBUF  108  comprises IBUF A(0) and IBUF A(1). Similarly, IBUF  110  comprises IBUF B(0) and IBUF B(1). The processor  100  further includes instruction dispatch blocks ID 1   112  and ID 2   114 . The ID 1   112  includes a multiplexer  116  coupled to the ICACHE  106  and the IBUFs  108  and  110 . The multiplexer  116  is configured to receive a thread dispatch request signal  118  as a control signal. The ID 1   112  is also coupled to the ID 2   114 .  
         [0017]    The processor  100  further comprises instruction issue blocks IS 1   120  and IS 2   122 . The IS 1   120  is coupled to the ID 2   114  to receive an instruction. The IS 1   120  is also coupled to the IS 2   122  to transmit the instruction to the IS 2   122 . The processor  100  further comprises various register files coupled to execution units in order to process the instruction. Specifically, the processor  100  comprises a vector register file (VRF)  124  coupled to a vector/SIMD multimedia extension (VMX)  126 . The processor  100  also comprises a floating-point register file (FPR)  128  coupled to a floating-point unit (FPU)  130 . Further, the processor  100  comprises a general-purpose register file (GPR)  132  coupled to a fixed-point unit/load-store unit (FXU/LSU)  134  and a data cache (DCACHE)  136 . The processor  100  also includes condition register file/link register file/count register file (CR/LNK/CNT)  138  and a branch  140 . The IS 2   122  is coupled to the VRF  124 , the FPR  128 , the GPR  132 , and the CR/LNK/CNT  138 . The processor  100  also comprises a dependency checking logic  142 , which is preferably coupled to the IS 2   122 .  
         [0018]    Instruction fetch will maintain separate IFARs  102  and  104  per thread. Fetching will alternate every cycle between threads. The instruction fetch is pipelined and takes three cycles in this implementation. At the end of the three cycles, four instructions are fetched from the ICACHE  106  and forwarded to the ID 1   112 . The four instructions are either dispatched or inserted into the IBUFs  108  and/or  110 .  
         [0019]    The selection for thread switch is determined at the ID 1   112 . The determination is based on the thread dispatch request signal  118  and available instructions for that thread. Preferably, the thread dispatch request signal  118  toggles every cycle per thread. If there is an available instruction for a given thread and it is an active thread for that thread, then an instruction will be dispatched for that thread. If there are no available instructions for a thread during its active thread cycle, then an alternate thread can use this dispatch slot if it has available instructions.  
         [0020]    In a prior art system, when a long latency instruction is followed by a dependent instruction in a first thread (e.g., thread A), the dependent instruction cannot be executed until the long latency instruction is processed. Therefore, the dependent instruction will be stored in the IS 2   122  until the long latency instruction is processed. In the present invention, however, the dependency checking logic  142  identifies the dependent instruction following the long latency instruction. Preferably, the dependent instruction is marked so that the dependency checking logic will be able to identify it. The dependent instruction is recycled by providing the dependent instruction to an earlier pipeline stage (e.g., the fetch stage). The dependent instruction is delayed at dispatch. An alternate thread is allowed to issue one or more instructions while the long latency instruction is being executed. Upon completion of the long latency instruction, the dependent instruction of the first thread gets executed.  
         [0021]    Now referring to FIG. 2, a timing diagram  200  illustrates normal thread switching. The timing diagram  200  shows normal fetch, dispatch and issue processes with no branch redirects or pipeline stalls. Preferably, fetch, dispatch and issue processes alternate between threads every cycle. Specifically, A(0:3) is the group of four instructions fetched for thread A. Similarly, B(0:3) is the group of four instructions fetched for thread B. There are no branches so that both fetch and dispatch toggles threads every cycle.  
         [0022]    Now referring to FIG. 3, a timing diagram  300  shows a DCACHE load miss on thread A followed by a dependent instruction on thread A. In cycle  1 , the load  302  is in pipeline stage EX 2 . In cycle  1 , a dependent instruction  304  in thread A is in pipeline stage IS 2 . In cycle  4 , a DCACHE miss signal  306  is activated. This in turn causes a writeback enable signal  308  for thread A to be disabled. In cycle  7 , the dependent instruction  304  in thread A is flushed by a FLUSH (A) signal  310 . The dependent instruction  304  will then be recycled and held at dispatch until the data returns from the load that missed the DCACHE. After the flush occurs, thread B is given all of the dispatch slots starting in cycle  21 . This continues until the DCACHE load data returns.  
         [0023]    It is noted that, after the load  302  is completely executed, the thread A sends the dependent instruction  304  through the pipeline for execution.  
         [0024]    A long latency instruction may take many different forms. A load miss as shown in FIG. 3 is one example of the long latency instruction. Additionally, there are other types of long latency instructions including, but not limited to: (1) an address translation miss; (2) a fixed point complex instruction; (3) a floating point complex instruction; and (4) a floating point denorm instruction. Although FIG. 3 shows a load miss case, it will be generally understood by a person of ordinary skill in the art that the present invention is applicable to other types of long latency instructions as well.  
         [0025]    It will be understood from the foregoing description that various modifications and changes may be made in the preferred embodiment of the present invention without departing from its true spirit. This description is intended for purposes of illustration only and should not be construed in a limiting sense. The scope of this invention should be limited only by the language of the following claims.