Fine grained multi-thread dispatch block mechanism

The present invention provides a method, a computer program product, and an apparatus for blocking a thread at dispatch in a multi-thread processor for fine-grained control of thread performance. Multiple threads share a pipeline within a processor. Therefore, a long latency condition for an instruction on one thread can stall all of the threads that share the pipeline. A dispatch-block signaling instruction blocks the thread containing the long latency condition at dispatch. The length of the block matches the length of the latency, so the pipeline can dispatch instructions from the blocked thread after the long latency condition is resolved. In one embodiment the dispatch-block signaling instruction is a modified OR instruction and in another embodiment it is a Nop instruction. By blocking one thread at dispatch, the processor can dispatch instructions from the other threads during the block.

FIELD OF THE INVENTION

The present invention relates generally to a block mechanism in multi-thread processors, and more particularly, to a dispatch block mechanism to allow fine-grained control of thread performance.

DESCRIPTION OF THE RELATED ART

Multi-thread technology allows two or more separate threads to execute on the same single processing core. A thread is a part of a program or a group of instructions that can execute independently. Accordingly, a group of instructions in a single thread must execute in program order, whereas a group of instructions in separate threads can execute independently, and concurrently. Multiple threads within a processor enable the processor to better utilize its resources. Multi-thread technology allows a single processor to appear as two or more processors to software.

Ideally, each thread would operate independently on its own resources. Each thread would utilize its own instruction pipelines and units, execution pipelines and units, and the like. In practice, this type of implementation is not feasible because there is a limited area and amount of resources on the chip. Therefore, different threads have to share some resources. For example, multiple threads may share the same instruction issue unit or execution pipeline. With multi-thread processors, issues involving sharing resources, handling instruction dependencies, and determining the priority of access to the resources become problematic for performance since a resource “bottleneck” is created.

The problem with sharing resources between threads is that an instruction with a long latency on one thread can stall the execution of instructions on another thread. For example, thread1and thread2share the same instruction issue unit. If thread1is stalling for many cycles in the instruction unit, then thread2will also be stalled for many cycles, since the instruction unit is shared. Thread1could be stalling due to a non-pipelined operation being executed, or a dependency waiting many cycles to be cleared. Accordingly, thread2, which is independent of thread1, cannot issue instructions and must wait for thread1. This problem leads to wasted time and resources for thread2.

One method to handle this problem is to decouple the issue point between threads. This is a valid solution, but it has the drawback of increasing the complexity of issuing instructions and it requires substantial area on the chip. Another method is flushing the instructions at dispatch when a long-latency instruction is detected. This is problematic because the flush-penalty most likely will not match the precise latency of the instruction, which leads to wasted cycles. It is clear that a simple system or method that allows multiple threads sharing the same resources to truly operate independently without wasting cycles would provide a vast improvement over the prior art.

SUMMARY OF THE INVENTION

The present invention provides a method, a computer program product, and an apparatus for fine-grained control of thread performance by blocking a thread at dispatch in a multi-thread processor. Multiple threads share a pipeline within a processor. Therefore, a long latency condition for an instruction on one thread can stall all of the threads that share the pipeline. A long latency condition can be a non-pipelined operation or a dependency. When a compiler can predict this long latency condition, it injects a dispatch-block signaling instruction into the code to block the specific thread. The processor detects this instruction and blocks the thread at dispatch for the number of cycles specified by the instruction (plus any additional cycles the hardware may add if additional latency is detected). The length of the block matches the length of the latency, so the pipeline can dispatch instructions from the blocked thread after the long latency condition is resolved. In one embodiment, the dispatch-block signaling instruction is a modified OR instruction and in another embodiment the instruction is one Nop instruction. The OR instruction and the Nop instruction block a thread for a specific amount of cycles that matches the latency of the condition. The modified OR instruction does not influence the execution of the program, the register file state, the memory state, or the input/output, and it only operates as a dispatch block. By blocking one thread at dispatch, the processor can dispatch instructions from the other threads during the block. This insures that a long latency condition on one thread does not lead to a stall on multiple threads and that the current thread is stalled for the precise number of cycles that is necessary.

DETAILED DESCRIPTION

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 implemented in hardware in order to provide the most efficient implementation. Alternatively, the functions may be 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.

FIG. 1depicts a block diagram of a processor100with multi-thread capabilities. This processor contains memory controller102. Memory controller102controls the flow of data and instructions to and from the processor100. Accordingly, instruction unit104issues instructions that are sent to execution unit106. Memory controller102interfaces with a level 2 (L2) cache108. The L2 cache108stores both instructions and data. The L2 cache interfaces with separate level 1 (L1) caches on instruction unit104and execution unit106. Instruction unit104has an L1 cache110to store instructions and execution unit106has an L1 cache114to store data. Instruction unit104draws instructions from L1 cache110and execution unit114draws data from and writes data to L1 cache114. Processor100may contain many other components that are not shown inFIG. 1.FIG. 1is a basic representation of a processor and does not limit the scope of the present invention.

FIG. 2depicts a block diagram of an instruction pipeline200within a processor that can accommodate multiple threads. This apparatus200resides within instruction unit104ofFIG. 1, and accommodates three separate threads, thread0, thread1, and thread2(not shown). As previously described, a thread is a program or a group of instructions that can execute independently. Instruction fetch unit202fetches instructions for all three threads. Instruction fetch unit202fetches the instructions in a priority order. Normally, instruction fetch unit202alternates between the three threads to give each thread equal access to the instruction pipeline. Instruction fetch unit202transmits these instructions to instruction buffers. Accordingly, IBUF0204stores instructions for thread0, IBUF1206stores instructions for thread1, and IBUF2208stores instructions for thread2. The instruction buffers204,206, and208transmit the instructions to dispatch mechanism210.FIG. 2illustrates three separate threads, but this number is arbitrary and this type of apparatus200can handle a larger or smaller amount of threads.

Dispatch mechanism210is a multiplexer (“MUX”) that selects the correct instruction for dispatch to instruction pipeline216.FIG. 2uses a MUX as dispatch mechanism210, but other components can be implemented to accomplish the same result. Dispatch mechanism210toggles between the output of IBUF0204, IBUF1206, or IBUF2208to give each thread equal priority and access to instruction pipeline216. Dispatch control block214selects which thread gets dispatched. If dispatch control block214detects the modified OR instruction it disrupts the normal toggle mechanism of dispatch mechanism210. After dispatch, the instructions stage down instruction pipeline216. Instruction pipeline216feeds execution unit106fromFIG. 1. Execution unit106executes the instructions. This application describes the illustrative embodiment with reference to an issue pipeline, and more specifically an instruction pipeline. The embodiment applies to any point in a pipeline where there is resource contention. For example, the embodiment also applies to an execution pipeline.

The illustrative embodiment concerns dispatch mechanism210, dispatch control block214, and the compiler (not shown). Consequently, an instruction that leads to a stall for thread0also causes a stall for independent threads1and2because all three threads share instruction pipeline216. The illustrative embodiment operates a block mechanism at the dispatch point (dispatch mechanism210) in the pipeline by using a dispatch-block signaling instruction. The compiler controls dispatch mechanism210such that it can dispatch instructions from threads1and2, while thread0is blocking at dispatch. This allows independent threads1and2to continue executing instructions in instruction pipeline216, while thread0is blocked at dispatch. This fine-grained thread control of thread performance saves time and resources for this multi-thread processor.

In one embodiment, the compiler executes these dispatch-block signaling instructions by using new forms of the OR instructions that are inserted into the pipeline. These instructions block all instructions on a particular thread at dispatch for a programmable number of cycles, which allows the other threads to access dispatch mechanism210during the block of one thread. The special forms of the OR instruction have no effect on the system other than to block the thread at the dispatch point. These OR instructions can be easily decoded and configured to different block times that produce the best results for the compiler. In one embodiment, the compiler can configure the block delay for each of the different decoded instruction types.

In an illustrative embodiment, the dispatch-block signaling instruction is a Nop instruction. A Nop instruction is an instruction that does not influence the execution of the program, register file state, memory state, or input/output. In this embodiment the Nop instruction operates as a dispatch block. There are varying types of Nop instructions, some of which do not block the thread and just do nothing. By designing the Nop instruction to have no effect on the system, processor100receives the benefit of not consuming any register resources to request the block. For one example, dispatch control block214needs to block thread0for 10 cycles. Compiler may dispatch 10 Nop instructions (normal), which prevents instruction pipeline216from stalling. This allows threads1and2to be dispatched during the block. In an embodiment, compiler dispatches one modified Nop instruction that delays thread0for 10 cycles. By only issuing one modified Nop instruction the compiler saves time and resources through a smaller code footprint.

There is a priority scheme for dispatch mechanism210. Accordingly, dispatch mechanism210toggles between threads0,1, and2to provide equal access to the instruction pipeline. In the present invention, a modified Nop (OR) instruction leads dispatch mechanism210to ignore the specific thread and toggle between the other threads. For example, a Nop instruction for 10 cycles on thread1causes dispatch mechanism210to toggle between threads0and2for 10 cycles. Accordingly, threads0and2have exclusive access to dispatch mechanism210while thread1is blocked at dispatch.

As an example of the modified OR instructions, the following OR instructions cause the following dispatch delays.OR28,28,28//block for 8 cyclesOR29,29,29//block for 10 cyclesOR30,30,30//block for 12 cyclesOR31,31,31//block for 16 cycles
These groups of cycle numbers are arbitrary and only provide an example of the modified OR instructions. The fixed timings for these instructions are programmed into the software. Therefore, when the compiler detects a specific sequence of instructions that will lead to a delay due to stalling the instruction pipeline, it will issue a modified OR instruction to handle the delay. The corresponding OR operation can precisely match the long-latency condition or approximate the long-latency condition. Accordingly, the hardware may add cycles to the OR instruction if additional latency is detected.

FIG. 3is a flow chart300illustrating the use of this modified dispatch block mechanism within a multi-thread instruction pipeline. First, instruction fetch unit202fetches instructions in step302. Then in step304, instruction buffers204,206and208store the instructions. Dispatch mechanism210dispatches non-blocked instructions in order of priority in step306. As previously described, dispatch mechanism210toggles between threads0,1, and2. In step308the dispatch mechanism210determines whether there is a modified OR instruction. If there is not a modified OR instruction, then in step306dispatch mechanism210continues to dispatch non-blocked instructions in order of priority. If there is a modified OR instruction, then in step312dispatch mechanism210blocks the thread from dispatching and allows non-blocked other threads to dispatch instructions for the length of the “OR” instruction. Accordingly, “OR” instructions on multiple threads can cause dispatch mechanism210to block multiple threads at the same time. This type of blocking is not limited to one thread at a time.

FIG. 4is a flow chart400illustrating an example of a modified OR mechanism that is used to block one thread of a multi-thread instruction pipeline. This example involves a floating add instruction (“FAA”) followed by another floating add instruction (“FAB”) that is dependent upon FAA. These two instructions are on thread0fromFIG. 2. For this example, thread0takes 10 cycles to execute or produce a result. Therefore, dependent operation FAB must stall 10 cycles in instruction pipeline216to wait for the dependency to clear. Accordingly, the compiler must know that a floating add instruction followed by a dependent floating add instruction on thread0corresponds to the OR instruction OR29,29,29. The compiler inserts this OR instruction into thread0. This assumes that dispatch control unit214can immediately block dispatch at the presence of one of these modified OR instructions, in time to block dependent instruction FAB. If this is not true and there is a latency before blocking dispatch, then the compiler can put normal Nop instuctions after the modified OR instruction to compensate.

First, instruction issue unit202fetches FAA, the modified OR instruction, and FAB in step402. IBUF0204stores the FAA, the “OR,” and the FAB in step404. FAB follows the OR instruction which follows FAA through instruction fetch unit202and IBUF0204. Thread0has to dispatch FAA in step406. Then thread0dispatches the modified OR instruction in step407. The OR instruction blocks thread0for 10 cycles in step408, and dispatch control unit214enables dispatch mechanism210to dispatch instructions from threads1and2for 10 cycles in step412. After 10 cycles dispatch mechanism210dispatches instructions from threads0,1and2in step414. Threads1and2are not affected by the OR instruction for thread0. Actually, threads1and2are executing faster due to the dispatch block on thread0.

This modified OR instruction can also be beneficial when one thread has a non-pipelined operation. Non-pipelined instructions usually take a long time to execute and subsequent instructions that use the same resources are not able to be pipelined. Accordingly, the subsequent instructions have to wait until the non-pipelined instruction is finished executing. This causes a significant stall in instruction pipeline216and penalizes the other threads. If the compiler knows that such a stall will result, then the compiler can block a thread for a specific number of cycles after dispatching the non-pipelined instruction by using the modified OR instruction. Therefore, the non-pipelined instruction will not indirectly stall instruction pipeline216. The other threads are able to dispatch and issue as long as the other threads do not use the same resources as the non-pipelined instruction that is currently executing. Many long latency conditions in the instruction pipeline may be avoided by utilizing this modified OR instruction. The ability to issue instructions from multiple threads in a shared issue pipeline even though one thread has a long-latency condition is a clear improvement over the prior art.

FIG. 5depicts a block diagram of data processing system500that may be implemented, for example, as a server, client computing device, handheld device, notebook, or other types of data processing systems, in accordance with an embodiment of the present invention. Data processing system500may implement aspects of the present invention, and may be a symmetric multiprocessor (“SMP”) system or a non-homogeneous system having a plurality of processors,100and120connected to the system bus506. Alternatively, the system may contain a single processor100.

Memory controller/cache508provides an interface to local memory509and connects to system bus506. I/O Bus Bridge510connects to system bus506and provides an interface to I/O bus512. Memory controller/cache508and I/O Bus Bridge510may be integrated as depicted. Peripheral component interconnect (“PCI”) bus bridge514connected to I/O bus512provides an interface to PCI local bus516. A number of modems may be connected to PCI local bus516. Typical PCI bus implementations will support four PCI expansion slots or add-in connectors. Modem518and network adapter520provide communications links to other computing devices connected to PCI local bus516through add-in connectors (not shown). Additional PCI bus bridges522and524provide interfaces for additional PCI local buses526and528, from which additional modems or network adapters (not shown) may be supported. In this manner, data processing system500allows connections to multiple network computers. A memory-mapped graphics adapter530and hard disk532may also be connected to I/O bus512as depicted, either directly or indirectly.

Accordingly, the hardware depicted inFIG. 5may vary. For example, other peripheral devices, such as optical disk drives and the like, also may be used in addition to or in place of the hardware depicted. The depicted example does not imply architectural limitations with respect to the present invention. For example, data processing system500may be, for example, an IBM Deep Blue system, CMT-5 system, products of International Business Machines Corporation in Armonk, N.Y., or other multi-core processor systems, running the Advanced Interactive Executive (“AIX”) operating system, LINUX operating system, or other operating systems.

It is understood that the present invention can take many forms and embodiments. Accordingly, several variations of the present design may be made without departing from the scope of the invention. The capabilities outlined herein allow for the possibility of a variety of networking models. This disclosure should not be read as preferring any particular networking model, but is instead directed to the underlying concepts on which these networking models can be built.