Across-thread out of order instruction dispatch in a multithreaded microprocessor

Dispatching of non-sequential instructions across threads in a multi-threaded microprocessor

The present invention generally relates to a multi-threaded microprocessor, and particularly relates to dispatching instructions to be executed in a multi-threaded microprocessor without considering the order between the threads.

In order to meet the needs of video gamers, simulation program creators and other programmers, complex graphics co-processors have been developed for various computer systems. These are usually processors that operate under the control of a general-purpose central processing unit or other main control processor. They are typically optimized to perform the conversion of scene data into pixels of an image, which can be displayed in a standard On raster-based display devices. In a common configuration, the graphics processor is provided with "geometric data", which usually contains a set of primitives (for example, lines, triangles, or Other polygons) and additional information, such as textures, lighting models, and the like. The graphics processor performs model building, viewpoint, perspective, lighting and similar transformations on geometric data (this level is usually called "vertex" processing). After these conversions, "pixel" processing begins. During pixel processing, geometric data is converted into raster data, which generally contains the color value and other information at each sample position in an array corresponding to the visible area; further conversions can be applied to the raster data, It includes texture blending and downfiltering (reducing the number of sample positions to correspond to the number of pixels in the display device). The final result is a set of color values that can be provided to the display device.

In order to provide smooth animation and instant response, the graphics processor is generally required to complete these calculations on the pixel data of a new frame at a minimum rate of about 30 Hz. As images become more realistic with more pixels, finer textures, etc., the performance requirements for graphics processors will increase.

To help meet these requirements, some existing graphics processors implement a multi-threaded architecture that utilizes parallel operations. For example, during vertex processing, the same operation is usually performed for each vertex; similarly, during pixel processing, the same operation is usually performed for each sample position or pixel position. The tendency of calculations on various vertices (or pixels) is independent of calculations on other vertices (pixels); therefore, each vertex (pixel) can be processed as a separate thread that executes a common program. The common program provides an instruction sequence to the execution unit in the execution core of the graphics processor; at a certain time, different threads may be different points in the sequence of the program. Since the execution time of an instruction (called latency here) may exceed one clock cycle, these execution units are generally made in a pipelined manner, so the second instruction can be completed in all previous instructions It has been issued before, as long as the second instruction does not require the data generated by the execution of the unfinished instruction.

In this type of processor, the execution core is usually designed in a cyclic manner (that is, an instruction from the first thread, then an instruction from the second thread, and so on) to fetch different things. Effectively execute the instructions that are executed by the thread, and sequentially present each extracted instruction to an issuing control circuit. The issuing control circuit keeps the extracted instruction until the source data is available and the execution unit is ready, and then sends the extracted instruction to the execution units. Since these threads are independent, the issuance of cycles reduces the possibility that an instruction will depend on the result of an instruction that is still executing. Therefore, the delay of instructions in one thread can be hidden by fetching and issuing an instruction from another thread. For example, a typical instruction may have a delay of 20 clock cycles, which can be hidden when the core supports 20 threads.

However, it is not always possible to conceal this delay with the issuance of loops. For example, pixel processing programs often include instructions to retrieve texture data from system memory. Such instructions may have a very long delay (for example, more than 100 clock cycles). After a texture fetching instruction of the first thread is issued, the issuing control circuit can continue to issue instructions (including subsequent instructions from the first thread that do not depend on the texture fetching instruction) until the issuing control circuit comes Until a command from the first thread that requires the texture data. This instruction cannot be issued until the texture fetch instruction is completed. Then, the issuing control circuit stops issuing the instruction, and it waits for the texture fetching instruction to be completed before starting to issue the instruction again. Therefore, "bubbles" may appear in the execution pipeline, which results in idle time of the execution unit and inefficiency in the processor.

One way to reduce this inefficiency is by increasing the number of threads that can be executed by the core at the same time. However, this is an expensive solution because each thread requires additional circuitry. For example, in order to consider the frequent thread switching that occurs in this parallel design, each thread is generally provided with its own dedicated data register group. Increasing the number of threads increases the number of registers required, which may significantly increase the cost of the processor chip, the complexity of the design, and the overall chip area. Other circuits used to support multiple threads, for example, the program counter control logic that maintains a program counter for each thread also becomes more complicated and takes up more area as the number of threads increases.

Therefore, it would be desirable to provide an execution core architecture that efficiently and effectively reduces the occurrence of bubbles in the execution pipeline without requiring a significant increase in chip area.

The embodiment of the present invention provides a system and method for dispatching instructions in a multi-threaded microprocessor (such as a graphics processor) in a way that is not limited to the inter-threading order. The instructions are fetched into an instruction buffer, which is configured to store one instruction from each thread. A dispatch circuit determines which instructions in the instruction buffer are ready for execution, and can issue any ready instructions; instructions from any thread can be issued before instructions from another thread, and No matter which instruction is fetched into the buffer first. Once a command from a specific thread has been issued, the fetch circuit can fill the available buffer location with the next command from the thread.

According to a feature of the present invention, a microprocessor configured for parallel processing of some threads is proposed, wherein each thread contains an instruction sequence. The microprocessor includes an execution module, an instruction buffer, an fetch circuit and a dispatch circuit. The execution module is configured to execute instructions of all threads. The instruction buffer contains a number of storage locations, and each storage location is associated with a different thread. The fetch circuit is configured to select one of the threads based at least in part on whether the associated storage location in the instruction buffer is available, and extract one of the threads The next instruction in the selected thread sequence goes to the instruction buffer. The dispatch circuit is configured to determine which of the instructions stored in the instruction buffer are ready for execution, and select one of the ready instructions to be issued to the execution unit. The fetch circuit can fetch instructions into the instruction buffer in a first order, and the dispatch circuit can select a ready instruction in a second order different from the first order.

In some embodiments, the microprocessor also includes an instruction cache configured to store instructions, and the fetch circuit may be further configured to send a request including the value of a program counter to the instruction Cache memory to fetch the next instruction. The extraction circuit may include program counter logic, a selection logic circuit, and an arbitration circuit. The program counter logic is configured to generate a candidate program counter value for each thread. The selection logic circuit is configured to select one of the threads based at least in part on determining which storage location in the instruction buffer is available; the selection logic circuit is further configured to Provide a corresponding selection signal. The arbitration circuit is configured to receive the selection signal and transmit the value of the program counter corresponding to the candidate of the selected thread to the instruction cache. In another embodiment, the threads may include a first thread group having a first thread type and a second thread group having a second thread type. The selection logic circuit may be further configured to select one of the threads based at least in part on the individual thread type of each thread.

In other embodiments, the microprocessor may also include a register file configured to store data for each thread, which contains the result data generated by the execution module. The dispatch circuit may include a scoreboard circuit, a scheduler circuit, and an issuer circuit. The scoreboard circuit is coupled to the command buffer and register file, and is configured to generate a ready signal for each command in the command buffer, wherein the ready signal for each command is at least partially It is enabled or disabled based on whether a source operand of the instruction exists in the register file. The scheduler circuit, which is coupled to the scoreboard and the command buffer, is configured to select one of the commands in the command buffer, and its ready signal is enabled as the next one to be issued Command and send a corresponding permission signal to the command buffer. The issuer circuit is coupled to the instruction buffer, and the instruction buffer is further configured to transmit the instruction selected by the scheduler circuit to the issuer circuit in response to the permission signal. The issuer circuit is configured to collect the source operand of the selected instruction from the register file, and transmit the selected instruction and source operand to the execution module. In another embodiment, the scheduler circuit is further configured to select the next instruction to be issued based at least in part on the length of time each instruction has been stored in the instruction buffer.

According to another feature of the present invention, a method for processing instructions in a microprocessor configured for simultaneous execution of multiple threads is proposed. The first instruction from the first thread among the threads is fetched into an instruction buffer, which is configured to store an instruction from each thread. Then, the second instruction from the second thread among the plurality of threads is fetched into the instruction buffer. One or more of the first instruction and the second instruction is determined whether it is ready for execution, and one of the first instruction and the second instruction is ready for execution. In the case where the second instruction is ready for execution and the first instruction is not yet ready for execution, the second instruction is selected before the first instruction is selected.

The following detailed description and accompanying drawings will provide a better understanding of the nature and advantages of the present invention.

The embodiment of the present invention provides a system and method for enabling instruction dispatch in a multi-threaded microprocessor (such as a graphics processor), which is not determined by the order of the threads. The instruction system is fetched into an instruction buffer, which is configured to store one instruction from each thread. A dispatch circuit determines which instructions in the instruction buffer are ready for execution, and can issue any ready instructions; instructions from any thread can be issued before instructions from another thread, and No matter which instruction is fetched into the buffer first. Once a command from a specific thread has been issued, the fetch circuit uses the next command from the thread to fill the available buffer location. Therefore, the idle time caused by blocked threads in the execution pipeline can be shortened. For example, if one of the threads is blocked (because the next instruction is based on an unfinished instruction), the processor can continue to issue any number of threads from any other thread during this period of time Instructions.

FIG. 1 is a block diagram of a computer system 100 according to an embodiment of the present invention. The computer system 100 includes a central processing unit (CPU) 102 and a system memory 104, which are connected via a bus 106. User input is received from one or more user input devices 108 (eg, keyboard, mouse) coupled to the bus 106. The visible output is provided on a pixel-based display device 110 (for example, a conventional CRT or LCD-based monitor), which is coupled to the graphics processing subsystem 112 of the system bus 106 Operate under control. The system disc 128 and other components, for example, one or more removable storage devices 129 (for example, a floppy disk drive, a compact disc (CD) drive, and/or a DVD drive), can also be coupled to the system The busbar 106. The system bus 106 can be made by one or more of various bus protocols including PCI (peripheral component interconnect), AGP (accelerated graphics port), and/or high-speed PCI (PCI-E); An appropriate "bridge" chip known as North Bridge and Nanqiao (not shown) can be provided to interconnect various components and/or buses.

The graphics processing subsystem 112 includes a graphics processing unit (GPU) 114, a graphics memory 116, and a scanout control logic 120. For example, it can utilize one or more such as programmable processors and/or Special-purpose integrated circuit (ASIC) integrated circuit components are implemented. The GPU 114 can be configured to perform various tasks, including generating pixel data from the graphics data supplied by the system bus 106, interacting with the graphics memory 116 to store and update pixel data, and the like. The related features of GPU 114 are further described below.

The scan output control logic 120 reads pixel data from the graphics memory 116 (or from the system memory 104 in some embodiments), and transmits the data to the display device 110 for display. In one embodiment, the scan output occurs at a fixed update rate (eg, 80 Hz); the update rate may be a user-selectable parameter. The scan output control logic 120 can also perform other operations, such as adjusting the color value for a specific display hardware; by combining pixel data with, for example, the graphics memory 116, the system memory 104, or other data sources (not shown). Display) obtained a video or cursor overlay image or the like to generate a composite screen image; convert digital pixel data into an analog signal used by the display device; and so on. It will be appreciated that the specific configuration of the graphics processing subsystem 112 is not important to the present invention.

During the operation of the system 100, the CPU 102 executes various programs, such as operating system (OS) programs and application programs, and driver programs for the graphics processing subsystem 112. These programs can be general conventional designs. For example, the graphics driver can implement one or more standard application programming interfaces (APIs), such as Open GL, Microsoft DirectX or D3D, to communicate with the graphics processing subsystem 112; any number of APIs or APIs The combination of can be supported, and in some embodiments, individual drivers can be provided to implement different APIs. The operating system program and/or application program instructs the graphics driver to transmit the graphics data or pixel data to the graphics processing subsystem 112 via the system bus 106 by invoking appropriate API function calls to invoke various functions of the GPU 114 Delineate functions, etc. The specific commands and/or data sent to the graphics processing subsystem 112 by the graphics driver in response to an API function call may vary with the GPU 114, and the graphics driver may also transmit and implement Commands and/or data for additional functions controlled by the operating system or application programs (for example, special visual effects).

According to an embodiment of the present invention, the GPU 114 is configured for simultaneous processing of a large number of threads, where each thread corresponds to an independent sequence of processing instructions. The GPU 114 can execute the next instruction from any one of the threads at any point in time.

For example, each vertex of the image can be processed by a different thread, where the simultaneous thread executes the same processing program on different data in the image; at a specific point in time, different threads may be The difference in the program. In some embodiments, there may be multiple types of threads. All threads of one type execute the same processing program, and different types of threads execute different processing programs. For example, there may be a "vertex" thread type, whose processing program includes geometry and lighting conversion, and a "pixel" thread type, whose processing program includes texture blending and reduction filtering of over-sampling data.

In the embodiment of FIG. 1, the GPU 114 includes a number of independent execution cores 118, and each execution core 118 is configured to process instructions received from a number of threads (not shown). The maximum number of simultaneous threads supported by the GPU 114 is the number of cores 118 multiplied by the number of threads per core; for example, in one embodiment, there are eight cores 118, and each core 118 can support up to 16 Threads, the total number is 128 threads executing simultaneously. The number of cores and the number of threads can be changed; for example, there can be eight cores, each core supporting 24 threads (total 192 threads); ten cores, each core supporting 24 threads (total 240 threads), etc.

Each execution core 118 includes an instruction cache 132, an instruction fetch circuit 136, a buffer 138, a dispatch circuit 140, an execution module 142 including a set of execution units (not shown), and a register file 144. The instruction cache (Icache) 132, which may be a conventional design, stores executable instructions, and these instructions are obtained from the graphics memory 116, for example. Each instruction in Icache 132 can be identified by a program counter (PC) value. The fetch circuit 136 fetches the instructions of all the threads processed by the execution core 118 from the Icache 132, maintains the sequential program sequence within each thread, and supplies the fetched instructions to the buffer 138. In each clock cycle, the dispatch circuit 140 selects a command from the buffer 138 to be issued to the execution module 142.

In one embodiment, the buffer 138 is configured to store at least one instruction for each thread and maintain the sequential program sequence of each thread. In each clock cycle, the dispatch circuit 140 selects one of the instructions from the buffer 138 for execution, obtains the source operand from the register file 144, and transmits the instruction and operand to the execution module 142 For execution. The dispatch circuit 140 advantageously selects the next instruction to be executed according to which instruction's source operand in the buffer 138 is already available in the register file 144, and can select the next instruction to be executed regardless of which thread It is the selected command under the source of the selected command. The fetch circuit 136 monitors the buffer 138, and after an instruction of a particular thread has been issued from the buffer 138, it fetches the next instruction of the thread. Therefore, for a particular clock cycle, instructions from most or all valid threads may be available in the buffer 138, and the dispatch circuit 140 can select an instruction from any thread. , Regardless of which thread was selected last time. Specific embodiments of the extraction circuit 136, the buffer 138, and the dispatch circuit 140 are described below.

The execution module 142 may be a conventional design, and may include any number of individual execution units. Some or all of these execution units can be configured for single instruction multiple data (SIMD) operations known in the art. The execution module 142 receives an instruction and its source operand from the dispatch circuit 140, processes the source operands according to the instruction, and stores the result data in the register file 144. The register file 144 is advantageous in that each thread processed by the execution unit 118 contains a separate register group, thereby avoiding the need to enter and exit the temporary register when switching from one thread to another. Exchange data in memory. The data written into the register file 144 can be used as the source operand of subsequent commands. These commands can vary in characteristics, and can include any number of source operands and any amount and/or type of result data.

Each instruction generally has a certain delay associated with it; in other words, the execution unit of the execution module 142 requires a certain number of clock cycles (which may be one or more clock cycles) to process the instruction and write the result Data to the register file 144. Different instructions may have different delays. For example, a simple vector addition operation can be completed in only one or two clock cycles, while a texture extraction operation may require a large number of cycles (for example, 100 or more cycles). The execution unit of the execution module 142 is advantageously made in a pipelined architecture. Therefore, despite the delay, one instruction can be dispatched per clock cycle; this architecture is known in the art. Different execution units (or groups of execution units) can be specially adapted to process specific instructions, that is, as known in the art, and the dispatch circuit 140 can select an appropriate execution within the execution module 142 Unit (or execution unit group) to process a specific command.

An instruction of a thread may have dependence on the data of other instructions of the thread; in other words, an instruction may use the result data of a previous instruction as its source operand. A data-dependent command cannot be executed until the result data of the command it depends on becomes available in the register file 144. If the next instruction of a particular thread is an instruction with such data dependency, the thread is blocked. According to an embodiment of the present invention, the dispatch circuit 140 detects a blocked thread, and selects a different thread from the buffer 138 (which can be any non-blocked thread) to follow the next instruction Is issued instead of waiting for the blocked thread to become unblocked. In this way, the delay in one thread can be hidden by executing another thread, and the efficiency of the GPU 114 is improved.

In addition to the execution core 118, the GPU 114 may also include other features not shown in Figure 1, for example, a circuit for receiving and responding to commands received via the system bus 106; such a circuit can be configured with The thread in the execution core 118 is started and/or terminated as appropriate. Various control registers, status registers, data caches, and the like can be set globally, per core, or per thread. This feature is known in the technology, and therefore the detailed description is omitted because it is not the focus for understanding the present invention.

It will be appreciated that the system described here is exemplary, and changes and modifications are possible. For example, the graphics processor can be implemented as one or more integrated circuit elements using any suitable technology. The graphics processor can be installed on an expansion card (which can include one or more such processors) or integrated into a system chipset (for example, integrated into the Northbridge chip). The graphics processing subsystem can include any number of dedicated graphics memory (some implementations may not have dedicated graphics memory), and can use any combination of system memory and dedicated graphics memory.

The number of execution cores in the graphics processor depends on the implementation, and the best choice is generally based on the trade-off between performance and cost. Each execution core can support simultaneous operations of one or more thread types; in the case of multiple cores, different cores in the same processor can be configured the same or differently. These cores are advantageously made into independent sub-processors that do not share execution units, and execute a specific thread in one core.

The number of threads in a specific core can also be changed according to the specific implementation and the amount of delay to be hidden. With this relationship, it should be noted that in some embodiments, instruction sequencing can also be used to hide certain delays. For example, as is known in the art, the compiler for graphics processor code can be optimized to arrange the instructions of the program so that if there is a first instruction to generate data and a second instruction to use the data, Then one or more other commands that do not use the data generated by the first command are set between the first and second commands. This system allows the processing of a thread to continue while the first instruction is being executed. It is also known in the art that, for instructions with long delays, it is usually impractical to set enough independent instructions between the producer and the user to completely hide the delay. In determining the number of threads per core, the availability of this optimization (or lack of such optimization) can be considered; for example, the number of threads supported by a core can be based on the maximum of any instruction Latency and the average (or minimum or maximum) number of instructions that a particular compiler can be expected to provide between a most-delayed instruction and its first dependent instruction.

The instruction cache used for an execution core can be shared among the threads, or can be partitioned physically or logically. In addition, in the case that the core supports multiple thread types, the instruction cache may contain a physical and/or logical partition corresponding to each thread type, and each partition may further be as desired Subdivide (or not subdivide) between individual threads of this type.

The register file used for an execution core is advantageous in that each thread contains a set of registers and can have any number of read and/or write ports. In addition, actual and/or logically separate register files can be set for different threads.

Although the configuration of the extraction circuit 136, the buffer 138, and the dispatch circuit 140 may also be changed, a specific example will now be described. Figure 2 is a simplified block diagram of an extraction circuit 140 and a buffer 138 for an execution core 118 according to an embodiment of the present invention. In this embodiment, the execution core 118 is configured to simultaneously process the maximum number<i>(N)</i>Threads, although what you will learn is that at any particular point in time,<i>N</i>Some or all of a thread may be idle or useless.

The extraction circuit 136 series contains the number (<i>N</i>) A program counter logic block 202 and an arbitration unit 204 controlled by the selection logic circuit 206. (Here, multiple examples of similar objects are represented by the number in parentheses of the component symbols for recognizing the object and the examples required for recognition.)

Each program counter logic block 202 is<i>N</i>A sequence of instructions under an individual thread in one of the threads generates a program counter (PC) value. The program counter logic block 202 may be a conventional design generally used to update a program counter, and may include an incremented counter, branch detection logic, and other features that are not important to the present invention.

The PC value generated by the PC logic block 202 is presented to the arbitration unit 204, which responds to a selection signal SEL provided by the selection block 206 (described below) <i>i</i>, To start from one of these threads (indicated here as thread<i>i</i>For reference) select these PC signals PC <i>i</i>(Where 0<img file="TW200529071A_D0001.tif" /><i>i</i><img file="TW200529071A_D0002.tif" />n-1). The selected signal PC<i>i</i>Is sent to the Icache 132, the Icache 132 returns the corresponding command to the buffer 138, and the corresponding thread identifier (<i>i</i>) Is sent to the buffer 138.

Buffer 138 contains<i>N</i>One storage location 208 (for example, it can be made using a register), one storage location 208 corresponds to the<i>N</i>One thread of each thread, and an array 210 is configured to store<i>N</i>A valid bit (each register has a valid bit). The buffer 138 receives the instruction (INST) from the Icache 132 and receives the thread identifier of the corresponding thread from the arbitration unit 204 (<i>i</i>), and it directs the instruction INST to the corresponding thread<i>i</i>One position 208. When the command is stored, the corresponding valid bit in the array 210 is set to logically true (for example, "1").

The buffer 138 is advantageously configured such that the dispatch circuit 140 can select an instruction to be issued from any storage location 208, so that instructions from different threads can be issued in any order. The dispatch circuit 140 is described below; it should now be noted that when a specific thread instruction is issued, the corresponding valid bit in the array 210 is advantageously set to a logical pseudo (for example, " 0"). As used here, a "valid thread" is a thread that has a valid instruction in the storage location 208, and an "invalid thread" is an execution that does not have a valid instruction in the storage location 208 thread.

As shown in Figure 2, the selection logic circuit 206 receives the valid bits of the array 210 from the buffer 138. The selection logic circuit 206 selects a thread from which an instruction will be fetched<i>i</i>The above system uses the validity or invalidity of each thread. For example, the selection logic circuit 206 can be configured to select only invalid threads; in the case where multiple threads are invalid, the selection logic circuit 206 can select the thread that has become invalid for the longest time, or can select the thread that has become invalid for the longest time. The priority level between threads is used to select a thread, where the priority level will change from one clock cycle to the next.

The selection logic circuit 206 may also include a rule that limits the frequency at which a particular thread can be selected, for example, in order to avoid a thread disproportionately occupying resources. For example, a rule may stipulate that a particular thread is not eligible to be selected again until at least the time since it was last selected<i>M</i>Clock cycles, where<i>M</i>Is a fixed number (for example,<i>M</i>Can be established as a configurable parameter of the processor). In the case where such a rule is implemented, there may be some clock cycles where no thread meets the selection rule (for example, the only invalid thread is less than<i>M</i>Was selected three cycles ago). In this case, the arbitration unit 204 may not transmit the PC in this clock cycle<i>i</i>Value to Icache 132; next PC <i>i</i>The value is transferred during the subsequent cycle when a thread that satisfies the condition is found. In an embodiment where one thread is selected for each clock cycle,<i>M</i>The system is set to a value not greater than the minimum number of threads that are expected to be valid at a specific time, thereby reducing the possibility of occurrence of clock cycles in which no threads are selected.

FIG. 3 is a simplified block diagram of a selection logic circuit 300 that implements a thread selection rule according to an embodiment of the present invention. The selection logic circuit 300 includes a priority encoder 302 and a phase (or token) counter 304. The valid signal of each thread is inverted by another inverter 306, and the generated /valid signal is provided to the priority encoder 302. The priority encoder 302, which can be made using a conventional digital logic circuit, selects the highest priority thread whose /valid signal is enabled (that is, the highest priority invalid thread), where the The priority level between these threads is determined according to a control signal (CTL) provided by the phase counter 304. Phase counter 304 is a modulo<i>N</i>The counter is incremented by 1 in each clock cycle; the control signal CTL corresponds to the current value of the phase counter 304. In this embodiment, the control signal CTL determines the thread number of the highest priority thread, and the priority encoder 302 uses the ascending (or descending) thread number as the modulus<i>N</i>The order of operations is to arrange the levels of the remaining threads.

Because the phase counter 304 is incremented by 1 in each clock cycle, the priority level of the thread is different with different clock cycles. For example, during the first clock cycle, the current thread counter 304 has a value of 0, and the priority encoder 302 gives thread 0 the highest priority. In other words, during the first clock cycle, if thread 0 is invalid, the priority encoder 302 generates a SEL that selects thread 0<i>i</i>The state of the signal. If thread 0 is valid, thread 1 is the next thread to be considered, and so on, until an invalid thread or the maximum number of threads is found (which may be less than or equal to<i>N</i>) Have been considered so far. During the next clock cycle, the current thread counter 304 has a value of 1, and the priority encoder 302 gives the thread 1 the highest priority, if the thread 1 is valid, it gives it to the thread 2, and so on.

Once a thread becomes invalid, it remains invalid until its next instruction is fetched. Therefore, although the selection logic circuit 300 does not guarantee that the thread that has been invalid for the longest time in any particular clock cycle will be selected, it will be recognized that any thread that becomes invalid will become invalid.<i>N</i>Are selected within a clock period. In some embodiments, the maximum number of threads considered by the priority encoder 302 during one clock cycle<i>C</i>Can be limited to a number less than the total number of threads<i>N</i>The number. This prevents a thread from being selected in consecutive clock cycles, so the minimum number of clock cycles required before a thread can be selected again can be adjusted by<i>C</i>Value to control. (In some embodiments,<i>C</i>It can be a configurable parameter of the system. )

It will be appreciated that the selection logic circuits and selection rules described herein are exemplary, and many changes and modifications are possible. The various circuit components described herein can be implemented using conventional digital logic circuit designs and technologies. Different logic circuits can also be made to support different selection rules. For example, in an embodiment where more than one instruction can be fetched per clock cycle, the priority encoder can be configured to select multiple threads per clock cycle. Furthermore, devices other than priority encoders can also be used to determine which invalid thread to select. For example, the selection logic circuit can maintain a "least recently valid" bit field, which is detected when one of the valid bits is between the logically true and logically false states It is updated on transition. In still other embodiments, a counter or similar circuit can be used to determine the elapsed time since a thread became invalid and/or the elapsed time since a thread was last selected; in the counter The comparison logic for operations on values can be set to identify a thread that is least recently valid.

In addition, between a selected time point and a time point when an instruction corresponding to a thread appears in the buffer 138, the selection logic may include another circuit to prohibit the selection of the thread. For example, in the case of an Icache miss, it may take several cycles to fetch an instruction from the primary instruction store (or a secondary cache) and provide the instruction to the buffer 138. In some embodiments, it may be desirable to prohibit the thread from being selected again during this interval, for example, to prevent instructions within a thread from being provided to the buffer 138 and/or not following its program sequence Was issued. It should be noted that because the fetch circuit 136 does not select threads in a circular manner, when fetching an instruction that encounters a thread missed by Icache is prohibited, instructions from other threads can continue to be fetched to the buffer 138 and was issued. Therefore, certain embodiments described herein can avoid pipeline bubbles and inefficiencies in the case of Icache misses.

In the case of supporting multiple thread types, the selection logic may consider or not consider the thread type as desired. For example, in the embodiment shown in FIG. 2, the information about the thread type is not provided to the selection logic circuit 206. FIG. 4 is a block diagram of an extraction circuit 400 considering the thread type according to an alternative embodiment of the present invention. In this embodiment, the execution core also supports<i>N</i>Threads, which can contain up to<i>K</i>Threads of the first type ("A") and up to<i>N</i>-<i>K</i>A second type ("B") thread.

The type A arbitration unit 402 is from the effective type A threads (numbered from 0 to 0 for reference purposes)<i>K</i>-1) Receive the program counter signal, and the type B arbitration unit 404 is from the effective type B thread (numbered for reference purposes<i>K</i>to<i>N</i>-1) Receive program counter signal. The type A arbitration unit 402 selects one of the type A threads in response to a selection signal from the selection logic circuit 406, and the type B arbitration unit 404 selects one of them in response to a selection signal from the selection logic circuit 408 Type B thread. In one embodiment, the configuration of each selection logic circuit 406, 408 is roughly similar to that described above with reference to Figure 3. Therefore, each selection logic circuit 406, 408 selects its individual type for the longest time it has become invalid. Thread; what you will realize is that other configuration and selection rules can also be used. As described above, according to the selection rules, it is possible that the time pulse period is one of the arbitration units (or both) of the arbitration units 402 and 404 and does not select any threads.

In response to the selection signals from the selection logic circuits 406 and 408, the type A arbitration unit 402 and the type B arbitration unit 404 provide the values of the individually selected program counters (PC <i>a</i>, PC <i>b</i>) To a global arbitration unit 410. The arbitration unit 402, 404 also has the advantage of identifying individual threads that have been selected (<i>a</i>，<i>b</i>). The global arbitration unit 410 responds to a type selection signal (A/B) generated by the thread type priority circuit 412, and then the PC<i>a</i>And PC <i>b</i>Choose between.

The thread type priority circuit 412 can be configured in various ways to define the desired relative priority between the thread types A and B. In one embodiment, the thread-type priority circuit 412 can be configured to give the two equal priority, for example, by selecting the PC on alternate clock cycles<i>a</i>With PC <i>b</i>. In another embodiment, the thread-type priority circuit 412 may select the thread that is least effective among the two candidate threads.

In still another embodiment, the thread type priority circuit 412 gives priority to one of the thread types according to a static or dynamic "importance" criterion. Various standards can be used. For example, if the thread types correspond to pixel threads and vertex threads, it may be desirable to give priority to vertex threads (for example, because some pixel threads may complete processing of related vertex threads) It could not be initiated before). Therefore, a selection rule can always take precedence over pixel threads to select vertex threads. Another selection rule can be defined as an iterative sequence of a certain number of vertices followed by a certain number of pixels (for example, two vertices after one pixel, or three vertices after two pixels, or, more Generally speaking,<i>v</i>Vertices followed<i>p</i>Pixels,<i>v</i>and<i>p</i>Is any integer). The importance can also be dynamically defined, for example, it is based on the number of vertices and/or pixel threads that are currently active or are currently waiting to be processed. The selection rules of the priority circuit 412 for the thread type can be made configurable to support the optimization of a specific system approach.

The global arbitration unit 410 is based on the type selection signal A/B to connect to the PC <i>a</i>and<i>PCb</i>Choose between, and it essentially provides the value of the selected program counter (labeled as PC <i>i</i>) To Icache 132. In some embodiments, the type selection signal A/B may occasionally indicate the thread type A during a clock cycle in which no thread of type A (B) is selected by the specific type of arbiter 402 (404). (Or B). The global arbitration unit 110 can be configured to select in this event<i>PCb</i>(PCa), or do not select any threads (that is, no Pc <i>i</i>It is sent to Icache 132).

It will be appreciated that the extraction circuit and buffer described herein are exemplary, and many changes and modifications are possible. In the case where different threads (or different thread types) have physically or logically separate instruction caches, the fetch circuit can be configured to guide the selected PC value to the appropriate Cache memory, or provide a thread (or thread type) identifier that can be used to select the appropriate cache memory. The buffer can store more than one instruction per thread, for example, by providing a FIFO register per thread, and the extraction circuit can be based on the invalid or unused in each FIFO The number of items to select the next thread to be extracted.

In some embodiments, it is not necessary for the fetch circuit to pre-fill the buffer to any specific extent before the instruction is issued. Instead, because the command is issued occasionally skip some clock cycles due to the data dependency and the relationship between similar ones, the buffer may tend to fill naturally. The thread selection logic of the fetch circuit is advantageously configured to select the thread only when there is space in the buffer for storing instructions from a thread, thereby avoiding buffer overflow.

FIG. 5 is a simplified block diagram of the dispatch circuit 140 according to an embodiment of the present invention. The dispatch circuit 140 includes a scoreboard circuit 502, a scheduler 504, and a issuing circuit (or issuer) 506. The scoreboard circuit 502, which can be a general conventional design, reads each (valid) instruction in the buffer 138. For each command, the scoreboard circuit 502 checks the register file 144 to determine whether the source operand is available. The scoreboard circuit 502 generates a set of ready signals (for example, each thread has a bit), which indicates which instructions in the buffer 138 are ready to be executed, that is, which instructions are It has source operands available in the register file 144. The scheduler 504 receives the ready signals from the scoreboard 502 and the valid signals from the buffer 138, and selects the next instruction to be dispatched. The selected instruction is dispatched to the issuer 506, and the issuer 506 issues the instruction by sending the instruction to the execution module 142. The thread identifier of the thread to which the selected instruction belongs can also be sent to the issuer 506 and/or the execution module 142, for example, to make it feasible to select an appropriate register for the source operand and result data of.

The scheduler 504 is advantageously configured to choose between ready instructions in the buffer 138 according to an order between threads, with little or no restriction. For example, the scheduler 504 can select the prepared instruction that has been waiting (valid) the longest in the buffer 138, regardless of when the thread was selected last.

FIG. 6 is a simplified block diagram of a selection logic circuit 600 that can be included in the scheduler 504 for selecting a thread to be dispatched from the buffer 138. The selection logic circuit 600 includes a priority encoder 602 and a phase (or sign) counter 604. The valid signal and ready signal of each thread are provided as the input of another AND circuit 606. The priority encoder 602 receives the output signal from the AND circuit 606, that is, the signal of each thread, which is caused when the instruction of the thread is valid in the buffer 138 and is ready to be executed. can. (In some embodiments, the ready signal of the thread is not enabled when the thread is invalid, so the AND circuit 606 can be omitted.) The priority can be made by using a conventional digital logic circuit The right encoder 602 selects the highest-priority thread (that is, the highest-priority ready thread) in which both ready and valid signals are enabled, wherein the priority level between these threads is It is determined according to a control signal (CTL2) provided by the phase counter 604. Phase counter 604 is a modulo<i>N</i>The counter is incremented by 1 in each clock cycle; the control signal CTL2 corresponds to the current value of the counter 604. In this embodiment, the control signal CTL2 determines the thread number of the highest priority thread, and the priority encoder 602 uses the rising (or falling) thread number as the modulus<i>N</i>The order of operations is to arrange the levels of the remaining threads. The phase counter 604 can have the same phase as the current thread counter 304 in FIG. 3 (the two counters can be implemented as the same counter if required), or the phase counter 604 can have a different phase.

The action of the priority encoder 602 is similar to the action described above for the priority encoder 302 in Figure 3, and because the phase counter 604 is incremented by 1 every clock cycle, the priority level of the thread follows It is different for different clock cycles. For example, during the first clock cycle, the current thread counter 604 has a value of 0, and the priority encoder 602 gives thread 0 the highest priority (that is, if thread 0 is ready, it selects execution Thread 0), if thread 0 is not ready, then thread 1 is given, and so on, until a ready thread is found or the maximum number of threads has been considered. During the next clock cycle, the current thread counter 604 has a value of 1, and the priority encoder 602 gives thread 1 the highest priority. If thread 1 is not ready, it will give thread 2, according to And so on.

Once a thread becomes ready, the thread remains ready until the thread's instructions are dispatched. Therefore, although the selection logic circuit 600 does not guarantee that in any particular clock cycle, the thread that has been ready for the longest time will be selected, but it will recognize that any thread that becomes ready (and effective) will be selected. Will become ready<i>N</i>Are selected within a clock period. In some embodiments, it may be desirable to prevent the same thread from being selected in consecutive clock cycles; the maximum number of threads considered by the priority encoder 602 during one clock cycle can be limited to one Less than the total number of threads<i>N</i>The number. (The maximum number can also be a configurable parameter of the system.)

It will be appreciated that the selection logic circuits and selection rules described herein are exemplary, and many changes and modifications are possible. The various circuit components described herein can be implemented using conventional digital logic circuit designs and technologies. Different logic circuits can also be made to support different selection rules. In a superscalar embodiment (where more than one instruction can be issued per clock cycle), the selection logic can be configured to select multiple instructions per clock cycle. Furthermore, devices other than priority encoders can also be used to determine which ready thread to select. For example, the selection logic circuit can maintain a "least recently invalid" bit field, which is updated when one of the valid bits is detected to transition between logically true and logically false states; This bit field can be used to select the prepared command that has been valid for the longest time. In still other embodiments, the counter can be used to determine the elapsed time since a thread became valid (or ready) and/or the elapsed time since a thread was last selected; The comparison logic that operates on the counter value can be set to identify the ready thread that has been valid for the longest time.

In other embodiments, other kinds of selection rules may be implemented. For example, the selection can be partially based on the type of thread (for example, using selection logic similar to that shown in Figure 4 above). The selection can also be partially determined by the type of operation to be performed (for example, giving different priority to multiplication, call operation, addition operation, etc.). In addition, the selection can consider the status of the execution module. In this embodiment, the execution module 142 includes a dedicated execution unit (or execution pipeline), in which different operations are directed to different execution units; for example, there may be an execution unit that performs floating-point arithmetic and Another execution unit that performs integer arithmetic. If an execution unit required by a ready instruction of a thread is being occupied, an instruction from a different thread can be selected. For example, suppose that at a specific point in time, the floating-point pipeline is occupied, and the integer pipeline is idle. Then the threads of instructions with ready integer arithmetic can be given priority over threads with floating-point instructions.

Please refer to FIG. 5 again. In response to the permission signal from the scheduler 504, the requested instruction in the buffer 138 is dispatched to the issuer 506. In one embodiment, the issuer 506 includes an operand collector 508 and a buffer 510. The buffer 510 receives the dispatched instruction, and the operand collector 508 collects the source operand for the instruction from the register file 144 in the buffer 510. According to the configuration of the register file 144, the collection of source operands may require multiple clock cycles, and given a specific register file configuration, the operand collector 508 can implement various optimizations. The technique of register file access for efficient collection of operands; examples of this technique are known in this technique. The buffer 510 is advantageously configured to store the collected operands and its instructions together, while other operands of the instruction are being collected at the same time. In some embodiments, the issuer 506 is configured to issue the instruction to the execution unit 142 immediately after the operands of the instruction have been collected. The issuer 506 does not necessarily issue the instructions in the order in which the instructions are dispatched. For example, the instructions in the buffer 510 can be stored in a sequence corresponding to the order in which they are dispatched, and the issuer 506 can select the earliest instruction to obtain its operands in each clock cycle, by gradually passing through The sequence (starting with the least recently dispatched instruction) until an instruction that gets all its operands is found. This instruction is issued, and the instruction following the instruction in the sequence is moved forward; the most recently dispatched instruction is added to the end of the sequence. For example, the sequence can be maintained by a set of sequential actual storage locations in the buffer 510, where when the previous instruction is removed, the subsequent instruction is moved to a different location.

In one embodiment, the instruction that has been dispatched to the issuer 506 is maintained in the buffer 138 until the instruction is issued to the execution module 142. After dispatch, the command is advantageously maintained in a valid but not ready state (for example, the valid bit 210 of a dispatched command can remain in a logically true state until the command is issued) . It will be appreciated that in an embodiment in which the issuer 506 may issue instructions out of the order of dispatch, this configuration can help prevent multiple instructions from the same thread from being present in the buffer 510 at the same time. This preserves the order of instructions within a thread.

In other embodiments, the issuer 506 does not perform the collection of operands. For example, when a command is received and the register file 144 is notified to provide appropriate source operands to the execution module 142 (or a specific execution unit of the execution module 142), the issuer 506 can issue the command to the execution The module 142 (or a specific execution unit of the execution module 142). In this embodiment, the operand collector 508 and the buffer 510 can be omitted. It will be appreciated that the specific configuration of the transmitter 506 is not important to the understanding of the present invention.

It will be appreciated that the dispatch circuit described here is exemplary, and many variations and modifications are possible. The various logic circuits described herein for the scheduler circuit can be implemented using conventional digital logic circuit designs and techniques. Different logic circuits can also be made to support different selection rules. The scheduling may also include the implementation of additional selection rules (e.g., the minimum number of cycles that must pass before a thread can be selected again for issue) and/or different selection rules (e.g., give a thread type Priority over another type of thread) various types of logic circuits. Such rules can be implemented using logic circuits and techniques similar to those previously described in the context of thread selection for the extraction circuit.

Although the present invention has been described in relation to specific embodiments, those skilled in the art will recognize that many modifications are possible. For example, although the embodiment described here is configured for the issuance of scalar (that is, one per clock cycle) instruction, alternative embodiments can support superscalar (that is, each clock cycle). Cycle more than one) instruction is issued. In a superscalar embodiment, the instructions issued in a specific clock cycle can be taken from various threads in any desired combination (for example, some embodiments may limit the issuance to each clock cycle There is one instruction per thread, and other embodiments may allow multiple instructions from the same thread to be issued in the same clock cycle). In the superscalar (or scalar) embodiment, the fetch circuit can also be modified to fetch more than one instruction per clock cycle. Therefore, it will be understood that the present invention involves extracting an arbitrary number per cycle (<i>F</i>) Instructions and issue any number of instructions (<i>P</i>) Examples, where the numbers<i>F</i>and<i>P</i>It can be distributed among multiple threads in any way you want. The embodiments of the present invention can also be adapted for use in non-synchronized processors.

In addition, if desired, non-sequential command issuance in a thread can be implemented, for example, by modifying the general rules that allow the issuance of any prepared command within a "valid window". The non-sequential issue technology of the destination processor.

The execution core described here is not limited to any specific number or configuration of execution units. For example, multiple execution units can work together to process a specific instruction, different execution units can receive different instructions in parallel (or the same instruction with different data), and so on. Execution units can process instructions with fixed or variable delays, and can be pipelined to receive instructions at each clock cycle, or more generally, at intervals formed by a fixed number of clock cycles New instructions.

As indicated above, any number of threads and any number of thread types can be supported, where each thread type corresponds to a programmed sequence of instructions to be executed. Program instructions can be provided in various ways, including built-in instructions stored in the non-electrical memory of the graphics processor or other graphics processing subsystem components, initialized in the system by a graphics driver, and/ Either the command supplied during execution and/or the code supplied by the application (for example, in the case of a programmable shader). The program can be generated in an appropriate high-level language (for example, C, Cg, or the like), and the program can be compiled using the programming language and an appropriate compiler of the graphics processor on which the program will be executed. Translating the input instruction into a different format (or different instruction set) compatible with the execution unit can be provided in the execution core, in other components of the graphics processor, or elsewhere in the computer system.

The graphics processor described herein can be implemented as a co-processor in a wide range of computing devices, including general-purpose desktop, laptop, and/or tablet computers; various handheld devices, such as personal Digital assistants (PDA), mobile phones, etc.; special purpose computer systems, such as video game consoles; and similar ones.

It will also be appreciated that although the present invention has been described with reference to a graphics processor, the systems and methods described herein can also be implemented in other multi-threaded microprocessors.

Therefore, although the present invention has been described in relation to specific embodiments, it will be appreciated that the present invention is intended to cover all modifications and equivalents within the scope of the following patent applications.

<p>100Computer system</p><p>102Central Processing Unit (CPU)</p><p>104System memory</p><p>106Bus</p><p>108Input device</p><p>110Display device</p><p>112Drawing Processing Subsystem</p><p>114Graphics Processing Unit (GPU)</p><p>116Drawing memory</p><p>118Executive core</p><p>120Scan output control logic</p><p>128System Disc</p><p>129Storage Device</p><p>132Command cache (Icache)</p><p>136Instruction extraction circuit</p><p>138Buffer</p><p>140Distribution circuit</p><p>142Execution Module</p><p>144register file</p><p>202Program counter logic block</p><p>204Arbitration Unit</p><p>206Select logic circuit</p><p>208Storage location</p><p>210Array</p><p>300Select logic circuit</p><p>302Priority encoder</p><p>304Phase Counter</p><p>306Inverter</p><p>400Extraction circuit</p><p>402Type A arbitration unit</p><p>404Type B arbitration unit</p><p>406,408Select logic circuit</p><p>410Global Arbitration Unit</p><p>412Priority circuit</p><p>502Scoreboard circuit</p><p>504Scheduler</p><p>506Sender</p><p>508Operator Collector</p><p>510Buffer</p><p>600Select logic circuit</p><p>602Priority encoder</p><p>604Phase Counter</p><p>606AND circuit</p>

Figure 1 is a simplified high-level block diagram of a computer system according to an embodiment of the present invention; Figure 2 is a simplified block diagram of an instruction fetch circuit and instruction buffer according to an embodiment of the present invention; Figure 3 is A simplified block diagram of a selection logic circuit for selecting an instruction to be fetched according to an embodiment of the present invention; Figure 4 is a simplified block diagram of an instruction fetching circuit according to another embodiment of the present invention; fifth Figure is a simplified block diagram of an instruction dispatch circuit according to an embodiment of the present invention; and Figure 6 is a simplified block diagram of a selection logic for selecting an instruction to be issued according to an embodiment of the present invention.