Abstract:
A SIMD processor efficiently utilizes its hardware resources to achieve higher data processing throughput. The effective width of a SIMD processor is extended by clocking the instruction processing side of the SIMD processor at a fraction of the rate of the data processing side and by providing multiple execution pipelines, each with multiple data paths. As a result, higher data processing throughput is achieved while an instruction is fetched and issued once per clock. This configuration also allows a large group of threads to be clustered and executed together through the SIMD processor so that greater memory efficiency can be achieved for certain types of operations like texture memory accesses performed in connection with graphics processing.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     Embodiments of the present invention relate generally to single-instruction, multiple-data (SIMD) processing and, more particularly, to a system and method for processing thread groups in a SIMD processor. 
     2. Description of the Related Art 
     A SIMD processor associates a single instruction with multiple data paths to allow the hardware to efficiently execute data-parallel algorithms. The usual benefits of a SIMD processor implementation results from the reduction in pipeline control hardware and instruction processing that comes from running multiple data paths in lockstep. 
     In general, increasing the number of data paths in a SIMD processor will allow more data to be processed in parallel and will lead to performance improvements. Processor size constraints, however, limit the number of data paths beyond a certain number. Also, if the number of data paths is too large, there may be under-utilization of hardware resources. 
     SUMMARY OF THE INVENTION 
     The present invention provides a processor with an improved SIMD architecture that efficiently utilizes its hardware resources to achieve higher data processing throughput. According to an embodiment of the present invention, the effective width of a SIMD processing unit is extended to a multiple of the actual hardware width by clocking the instruction processing side of the SIMD processing unit at a fraction of the rate of the data processing side. According to another embodiment of the present invention, the effective width of a SIMD processing unit is extended by providing multiple execution pipelines. By using different clock rates and providing multiple execution pipelines, a large amount of threads can be grouped together into a convoy of threads according to the formula: convoy_size=(number of execution pipelines)×(number of data paths in each execution pipeline)×(ratio of the clock rate of the data processing side to the clock rate of the instruction processing side). 
     A SIMD processing unit according to an embodiment of the present invention includes an instruction processing section that operates at a first clock rate and a data processing section that operates at a second clock rate that is different from the first clock rate. Preferably, the second clock rate is at least twice the first clock rate. The instruction processing section issues an instruction to be executed in the data processing section and collects operands to be used in executing the issued instruction. Multiple sets of such operands are collected. 
     The data processing section includes at least first and second execution pipelines. The first execution pipeline is configured to execute instructions of a first type, e.g., multiply and add (MAD), and the second execution pipeline is configured to execute instructions of a second type, e.g., special function instructions such as reciprocal, exponential, logarithmic, etc. (SFU). Each execution pipeline has multiple data paths that are identically configured in accordance with the issued instruction. 
     Each set of operands collected in the instruction processing section is supplied to one of the data paths. A set of operands associated with an MAD instruction is supplied to one of the data paths in the first execution pipeline. A set of operands associated with an SFU instruction is supplied to one of the data paths in the second execution pipeline. 
     The number of sets of operands collected for an issued instruction is preferably equal to the number of actual data paths in the first and second execution pipelines multiplied by the ratio of the second clock rate to the first clock rate. For example, when the ratio of the second clock rate to the first clock rate is 2, the number of sets of operands collected for an issued instruction should be 2×(number of data paths in the first and second execution pipelines). 
     According to embodiments of the present invention, a new instruction need not be issued at every cycle of the data processing rate to keep the data processing section fully utilized. This allows the instruction processing section to operate at a reduced clock rate that is more suitable for instruction processing and as a result reduces the hardware requirements for the instruction processing section. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
         FIG. 1  is a simplified block diagram of a computer system implementing a GPU with a plurality of SIMD processors. 
         FIG. 2  is a block diagram of a SIMD processor according to an embodiment of the present invention. 
         FIG. 3  is a block diagram of an instruction dispatch unit of the SIMD processor shown in  FIG. 2 . 
         FIG. 4  is a conceptual diagram showing the contents of an instruction buffer. 
         FIGS. 5A-5D  illustrate the processing of a group of threads through an SIMD execution pipeline. 
         FIG. 6  is a flow diagram that illustrates the process steps carried out by a SIMD processor when executing an instruction for a group of threads. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a simplified block diagram of a computer system  100  implementing a graphics processing unit (GPU)  120  with an interface unit  122  coupled to a plurality of SIMD processors  124 - 1 ,  124 - 2 , . . . ,  124 -N. The SIMD processors  124  have access to a local graphics memory  130  through a memory controller  126 . The GPU  120  and the local graphics memory  130  represent a graphics subsystem that is accessed by a central processing unit (CPU)  110  of the computer system  100  using a driver that is stored in a system memory  112 . 
     The present invention is applicable to any processing unit with one or more SIMD processors  124 . Therefore, N can be any integer greater than or equal to 1. Also, the processing unit including the SIMD processors  124  may be a CPU, a GPU or any other type of processing unit. 
       FIG. 2  illustrates a SIMD processor according to an embodiment of the invention in greater detail. As shown, the SIMD processor  200 , which may be any one of the SIMD processors  124  shown in  FIG. 1 , includes an instruction processing section  210  and a data processing section  220 . The instruction processing section  210  operates at a clock rate that is half the clock rate of the data processing section  220 . For convenience, the clock for the instruction processing section  210  will be referred to hereafter as the T clock, and the clock for the data processing section  220  will be referred to hereafter as the H clock. 
     The instruction processing section  210  includes an instruction dispatch unit  212  for issuing an instruction to be executed by the SIMD processor  200 , a register file  214  that stores the operands used in executing the instruction, and a pair of operand collection units  216 ,  218 . The operand collection unit  216  is coupled to a first execution pipeline  222  and collects operands to be supplied to the first execution pipeline  222 . The operand collection unit  218  is coupled to a second execution pipeline  224  and collects operands to be supplied to the second execution pipeline  224 . In the embodiment of the present invention illustrated herein, the first execution pipeline is configured to execute instructions of a first type, e.g., multiply and add (MAD), and the second execution pipeline is configured to execute instructions of a second type, e.g., special function instructions such as reciprocal, exponential, logarithmic, etc. (SFU). Certain instructions may be carried out in either of the execution pipelines  222 ,  224 . For example, instructions MOV and FMUL may be executed in either of the execution pipelines  222 ,  224 . Each of the execution pipelines  222 ,  224  has 8 parallel and identically configured data paths. 
     When the instruction dispatch unit  212  issues an instruction, the instruction dispatch unit  212  sends pipeline configuration signals to one of the two execution pipelines  222 ,  224 . If the instruction is of the MAD type, the pipeline configuration signals are sent to the first execution pipeline  222 . If the instruction is of the SFU type, the pipeline configuration signals are sent to the second execution pipeline  222 . 
     Upon issuing an instruction, the instruction dispatch unit  212  also transmits a mask that corresponds to a convoy (which in the embodiment illustrated herein is a group of 32) of threads associated with the issued instruction. If the issued instruction is of the MAD type, the operand collection unit  216  reads the registers within the register file  214  that are associated with the convoy of threads and, for each thread in the convoy, collects a set of operands that are needed to execute the issued instruction. A single set of operands may include one or more operands. Typically a set of operands associated with an instruction of the MAD type includes two or three operands, and a set of operands associated with an instruction of the SFU type includes one operand. 
     If the issued instruction is of the SFU type, the operand collection unit  218  reads the registers within the register file  124  that are associated with the convoy of threads and, for each thread in the convoy, collects a set of operands that are needed to execute the issued instruction. For each cycle of the T clock, each of the operand collection units  216 ,  218  is able to collect  16  sets of operands. These sets are supplied to the execution pipelines  222 ,  224  at a rate of eight sets per H clock cycle. Therefore, the 32 sets of operands associated with a convoy of threads are processed in two T clock cycles or four H clock cycles. 
     The execution results from the execution pipelines  222 ,  224  are collected in a pair of accumulators  226 ,  228 . The accumulator  226  collects execution results from the execution pipeline  222  and the accumulator  228  collects execution results from the execution pipeline  224 . The execution pipelines  222 ,  224  and the accumulators  226 ,  228  are part of the data processing section  220  and operate at a clock rate that is twice the clock rate of the instruction processing section  210 . The accumulators  226 ,  228  write the execution results back to the register file  214  every two H clock cycles, or every one T clock cycle, because the register file  214  operates at the T clock rate. Thus, each of the accumulators  226 ,  228  collects  16  sets of execution results before it writes back to the register file  214 . 
     The H clock is configured to be a fast clock, because of the types of operations, primarily math operations, being carried out in the execution pipelines  222 ,  224 . The efficient operating speed for math operations, however, is generally different from the efficient operating speed for instruction processing and for the register file  214 . The instruction processing and the register file  214  operate more efficiently with a slower clock. Therefore, the SIMD processor  200  is configured with two clock domains, with the instruction processing being carried out at the T clock rate and the data processing being carried out at the H clock rate, which is equal to twice the T clock rate. 
       FIG. 3  is a functional block diagram of the instruction dispatch unit  212  of the instruction processing section  210 . The instruction dispatch unit  212  includes an instruction buffer  310  with a plurality of slots (one slot per convoy of threads). The number of slots in this exemplary embodiment is 24 and each slot can hold up to two instructions from a corresponding convoy of threads. If any one of the slots has a space for another instruction, a fetch  312  is made from memory into an instruction cache  314 . Before the instruction stored in the instruction cache  314  is added to a scoreboard  322  that tracks the instructions that are in flight, i.e., instructions that have been issued but have not completed, and placed in the empty space of the instruction buffer  310 , the instruction undergoes a decode  316 . Upon decoding of the instruction, a determination can be made as to whether the instruction is of the MAD type or the SFU type. 
     The instruction dispatch unit  212  further includes an issue logic  320 . The issue logic  320  examines the scoreboard  322  and issues an instruction out of the instruction buffer  310  that is not dependent on any of the instructions in flight. In conjunction with the issuance out of the instruction buffer  310 , the issue logic  320  sends pipeline configuration signals to the appropriate execution pipeline and transmits a mask that corresponds to a convoy of threads associated with the issued instruction. The mask indicates which of the threads in the convoy are active, i.e., should be affected by the issued instruction. 
       FIG. 4  illustrates the instruction buffer  310  in further detail. As shown, the instruction buffer  310  has 24 slots. Each slot in the instruction buffer can hold up to two instructions from a convoy (a group of 32) of threads. In the example shown, the two instructions from a convoy of threads, T 0  through T 31 , having program counters of  102  and  110  are stored in slot  0  of the instruction buffer  310 . These instructions will be either the MAD type or the SFU type. If an instruction is of the MAD type and is issued out of the instruction buffer  310 , the 32 sets of operands associated with the convoy of threads, T 0  through T 31 , will be collected in the operand collection unit  216  and supplied to the execution pipeline  222 . On the other hand, if an instruction is of the SFU type and is issued out of the instruction buffer  310 , the 32 sets of operands associated with the convoy of threads, T 0  through T 31 , will be collected in the operand collection unit  218  and supplied to the execution pipeline  224 . 
       FIGS. 5A-5D  illustrate selected processing states of the convoy of threads, T 0  through T 31 , through the execution pipeline  222  that is configured to execute a MAD instruction, e.g., Instruction A, issued out of the instruction buffer  310 .  FIG. 5A  shows the state of the execution pipeline  222  after one H clock cycle has elapsed. As shown, after one H clock cycle, 8 sets of operands, identified as  0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 , that are respectively associated with threads T 0 , T 1 , T 2 , T 3 , T 4 , T 5 , T 6 , T 7 , has entered the execution pipeline  222  and is operated on by the first pipe stage of Instruction A. In the very next H clock cycle, a new group of 8 sets of operands will enter the execution pipeline  222  and will be operated on by the first pipe stage of Instruction A, and the initial group of 8 sets of operands will have advanced down one pipe stage and will further be operated on by the second pipe stage of Instruction A. After four H clock cycles, all sets of operands associated with a convoy of threads will have entered the execution pipeline  222 . Therefore, each pipe stage of Instruction A will be active for four H clock cycles. At the fifth H clock cycle, it will be configured in accordance with a newly issued instruction of the MAD type. 
       FIG. 5B  shows the state of the execution pipeline  222  after all sets of operands associated with a convoy of threads have entered the execution pipeline  222  and been operated on by a few pipe stages of Instruction A.  FIG. 5C  shows the state of the execution pipeline  222  just before any set of operands exit the execution pipeline  222 .  FIG. 5D  shows the state of the execution pipeline  222  three H clock cycles after the state shown in  FIG. 5C . After one more H clock cycle has elapsed, all sets of operands associated with a convoy of threads will have exited the execution pipeline  222 . 
     In the preferred embodiment, the issue logic  320 , when issuing instructions out of the instruction buffer  310 , alternates between instructions of the MAD type and instructions of the SFU type. In this manner, both of the execution pipelines  222 ,  224  can be kept completely busy. Successive issuances of MAD type instructions or SFU type instructions may be permitted if the instruction buffer  310  contains only single type of instructions. However, a convoy of 32 threads requires 2 T clocks or 4H clocks to execute, and so, successive issuances of same-type instructions (e.g. MAD-MAD or SFU-SFU) can occur at most every other T clock. Issuing different-type instructions alternately to the two pipelines, on the other hand, permits an instruction to be issued at every T clock and provides for higher performance. The compiler can help with the scheduling of the instructions so as to ensure that different-type instructions are stored in the instruction buffer  310 . Allowing different convoys to be slightly apart in the program may also improve performance. 
       FIG. 6  is a flow diagram that illustrates the process steps carried out by the SIMD processor  200  when executing one instruction for a convoy of threads in accordance with an embodiment of the present invention. In step  610 , an instruction is issued out of the instruction buffer  310 . Then, multiple sets of operands are read from the register file  216  and collected in the operand collection unit  216  or  218  corresponding to the type of instruction issued (step  612 ). In step  614 , the execution pipeline  222  or  224  corresponding to the type of instruction issued is configured to execute the issued instruction. In step  616 , the collected operands are advanced down the execution pipeline and operated on by multiple pipe stages of the issued instruction. Steps  614  and  616  are carried out continuously until all of the operands collected in step  612  have exited the execution pipeline. While steps  614  and  616  are being carried out, the accumulators  226 ,  228  collect operands exiting the execution pipelines  222 ,  224  and write back to the register file  216  every other H clock (i.e., half convoy at a time). When all of the operands collected in step  612  have exited the execution pipeline (step  620 ), the SIMD processing for the instruction issued in step  610  ends. In the example shown in  FIGS. 5A-5D , the initial write-back to the register file  216  occurs two H clocks after the state of the execution pipeline shown in  FIG. 5C  and the final write-back to the register file  216  occurs four H clocks after the state of the execution pipeline shown in  FIG. 5C . 
     With the embodiments of the present invention described above, the amount of data that is processed through a SIMD processor is increased without increasing the physical data width of the execution pipelines. As a result, the effective instruction processing rate of the SIMD processor is increased. 
     Furthermore, the present invention provides a flexible way to group threads. In the embodiments of the present invention described above, a convoy is configured as a group of 32 threads, in accordance with the formula: convoy_size=(number of execution pipelines)×(number of data paths in each execution pipeline)×(ratio of the H clock rate to the T clock rate)=2×8×2=32. The flexibility provided by the present invention is that the convoy size could be adjusted. For example, the convoy size could be increased to 64 by issuing an instruction to each execution pipeline at every fourth T clock or at every other T clock when alternating between execution pipelines. 
     A benefit of having a larger convoy size is that in graphics processing a lot of the instructions that are executed are memory accesses like textures. These instructions are carried out much more efficiently by the memory system if there are a large group of related memory accesses, instead of smaller groups of memory accesses. By clustering or convoying the threads together, the present invention provides for greater memory efficiency. The downside of using convoys that are too large is that things like branches cause some threads in a convoy to execute different instructions than others in the same convoy. In such cases, performance will be lowered since all threads within the same convoy can only execute one instruction at a time. 
     While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof. The scope of the present invention is determined by the claims that follow.